8.5. Быстрый алгоритм иерархической классификации

Опишем сначала основной блок алгоритма.

Пусть — некоторая мера близости между подмножествами из X. Выберем порог с.

Из матрицы взаимных расстояний выберем массив . Допустим, что

Шаг А.

Найдем

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

где — символ удаления элементов.

Сформируем массив из матрицы взаимных расстояний множества включив в него:

причем

Таким образом получаем пару . Если , то описанный шаг А можно повторить.

Итогом работы рассматриваемого блока алгоритма является последовательность пар

где X — множество, полученное из объединением двух каких-либо элементов, W — массив, сформированный из матрицы взаимных расстояний множества — пустой массив.

Схема алгоритма

1. Задаем множество и меру близости

2. Выбираем значение порога и формируем массив Например, выбирается так, чтобы где — числовые параметры.

3. Применяем к () процедуру основного блока алгоритма. В результате находим множество для которого По построению элементам множества соответствуют непересекающиеся классы из разбиение множества X.

4. Если то возвращаемся к шагу 1, заменив X на (В алгоритмах гибкой стратегии заменяется и мера близости.) Если то заканчиваем, работу алгоритма.

Итогом работы алгоритма является бинарная иерархия на X, но в общем случае эта иерархия не совпадает с иерархией, получаемой классической агломеративной процедурой при помощи меры близости .

Соответствующий пример нетрудно привести для меры близости где — центры классов.

В то же время, как уже отмечалось, для редуктивных мер близости (см. определение 8.7) описанная процедура представляет собой ускоренный вариант классической агломеративной процедуры.

Приведем важнейшие редуктивные меры близости. Проверка опирается на теорему 8.2 и проводится в терминах параметров , общей рекуррентной формулы для мер близости.

Положим

Тогда, по теореме 8.2, если параметры таковы, что то определяемая ими мера близости редуктивна.

Для краткости указываем только наименование меры близости:

1) «ближайший сосед» (5.4):

2) «дальний сосед» (5.5):

3) средней связи (5.7):

4) приращение статистического разброса при объединении классов (см. примеры (8.5 и 8.6).