8.2. Методы и алгоритмы иерархической классификации

В основе алгоритмов иерархической классификации лежит тот или иной критерии качества разбиения множества S на подмножества (см. § 5.4). Обычно используются бинарные алгоритмы, когда . В этом случае имеет смысл близости между множествами (см § 5.3). Далее, говоря об алгоритмах иерархической классификации, будем иметь в виду только бинарные алгоритмы.

8.2.1. Дивизимные алгоритмы.

Дивизимные алгоритмы строятся на принципе разделения множества 5 на подмножества (, такие, что

В реально используемых алгоритмах берется некоторое приближенное решение задачи (8.1), так как точное решение ее I рудоемко даже при относительно небольшом объеме элементов в S. Вид меры близости может меняться в ходе алгоритма.

Изложим на важном примере основные приемы разделения класса S на подклассы в дивизимных алгоритмах.

Пусть где . В качестве критерия однородности класса возьмем статистический разброс

(8.2)

где -центр класса квадрат евклидова расстояния между X и

Положим

т. е. мерой близости между классами считаем приращение разброса при объединении классов.

Пусть Для фиксированного класса S имеем: . Следовательно, для решения задачи (8.1) разделения класса S достаточно найти

Функционал является функционалом качества разбиения S на подклассы S, и в методе -средних, поэтому для получения классов можно использовать алгоритмы -средних (см. п. 7.2.1).

Опишем теперь распространенный способ разделения множества S на подмножества при помощи линейного классификатора:

где

Для данного вектора v рассмотрим проекцию и обозначим через S образ множества S. Положим где — как и выше, статистический разброс. Пусть

Тогда имеет место формула:

где — число элементов в множествах соответственно. Следовательно, для фиксированного S достаточно найти:

Пустьуг -упорядоченная числовая последовательность элементов множества Так как ищем на прямой точку а, разделяющую эту последовательность на две части, то

для некоторого т. е. в этом случае вместо метода -средних можно применить для решения задачи (8.5) метод последовательного перебора.

Вычислив числовую последовательность получим пару где

и, следовательно,

Таким образом описан алгоритм нахождения порогового значения а для линейного классификатора, задаваемого вектором . В качестве v обычно берется какой-либо координатный вектор либо собственный вектор корреляционной матрицы множества Вектор v можно получить также как решение задачи целенаправленного проецирования (см. гл. 19), дающее проекцию для которой — наиболее неоднородная числовая выборка в смысле некоторого критерия.

Алгоритм иерархической классификации множества X из элементов состоит из шагов. На вход дивизимного алгоритма подается все множество X. На шаге получается разбиение множества X на непересекающихся множеств (классов) называемое разбиением уровня.

Итоговая иерархия s представляет собой систему образованную вложенными разбиениями Здесь (Говорят, что разбиение вложено в разбиение если каждый класс из является подклассом некоторого класса из Если на шаге получается разбиение все классы которого удовлетворяют выбранному критерию однородности, то алгоритм обычно останавливается.

8.2.2. Агломеративные алгоритмы.

На вход агломеративного алгоритма подается разбиение где Разбиение уровня имеет вид и строится из разбиения путем объединения пары классов где

Итоговую иерархию s образует система вложенных разбиений Здесь

Отметим, что иерархическая классификация при помощи бинарного алгоритма всегда дает бинарную иерархию.

Замечание. Иногда (см например, [9]) иерархической классификацией множества X называют построение системы вложенных разбиений где или где

Предыдущие рассуждения показывают эквивалентность такого определения иерархической классификации и данного выше определения 8.4.

Напомним, что наиболее употребительные в агломеративных алгоритмах меры близости приведены в § 5.3 Свойства этих мер близости и методы эффективного решения задачи (8.7) обсуждаются ниже. Здесь же только отметим, что мера близости (8.3) удовлетворяет рекуррентному соотношению (5.10). Как будет видно далее, она обладает рядом важных свойств, которые обеспечивают широкое использование ее при решении задач классификации В то же время ниже показано, что «Расстояние по центрам тяжести» (5.6) не обладает такими свойствами.