13.4.4. Иерархическая кластеризация

Иерархический кластерный анализ является методом кластерного анализа, который стремится построить иерархию кластеров. Стратегии иерархического объединения в кластеры разделяются на два типа:

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

первого уровня иерархии объединяются, образуя второй уровень иерархии кластеров, и т.д. В итоге образуется иерархия кластеров;

• разделительный (divisive) — подход постепенного разделения кластеров. В начале все наблюдения образуют один кластер, который рекуррсн- тно расчленяется, образуя иерархию кластеров.

Результаты иерархического объединения в кластеры обычно представляются в древовидной диаграмме. В общем случае сложность агломератив- ного объединения в кластеры измеряется величиной 0(д3), что приводит к замедлению при больших наборах данных. Разделительное образование кластеров с исчерпывающим поиском имеет сложность 0(2"), что еще хуже. Однако для некоторых частных случаев известны оптимальные эффективные агломеративные методы со сложностью 0(п2).

Метод Уорда. Метод Уорда (Ward) минимальной дисперсии — частный случай подхода с использованием целевой функции, первоначально представленного Дж. Уордом (1963), который предложил общую агломератив- ную иерархическую процедуру объединения в кластеры, где критерий выбора пары кластеров, предназначенных для объединения, на каждом шаге основан на оптимальной величине целевой функции. Эта целевая функция может быть любой функцией, которая отражает цель исследователя. Многие из стандартных процедур объединения в кластеры содержатся в этом очень общем классе. Чтобы иллюстрировать процедуру, Уорд использовал пример, где целевая функция — сумма квадратов ошибок, и именно этот пример известен как метод Уорда или, более точно, метод Уорда минимальной дисперсии.

С помощью критерия минимальной дисперсии Уорда минимизируется полная дисперсия в пределах кластера. На каждом шаге пара кластеров с минимальным расстоянием между кластерами объединяется. При реализации этого метода на каждом шаге находят пару кластеров, которая после слияния приводит к минимальному увеличению полной дисперсии в пределах кластера. Это увеличение — взвешенный квадрат расстояния между центрами кластеров.

Вначале все кластеры состоят из единственного элемента. Чтобы применить рекуррентный алгоритм с использованием целевой функции Уорда, начальное расстояние между отдельными объектами должно быть пропорционально квадрату евклидова расстояния. Поэтому начальные расстояния группы в методе минимальной дисперсии Уорда определены как квадраты евклидова расстояния между точками:

В программном обеспечении, которое реализует метод Уорда, иногда аргументы функции определяют евклидовы расстояния, а иногда — квадраты евклидовых расстояний.

Метод Уорда хорошо работает с небольшим количеством элементов и нацелен на выбор кластеров с примерно одинаковым количеством членов.

Алгоритмы Ланса — Уильяма. Критерий минимальной дисперсии Уорда можно определить и реализовать рекуррентно с помощью алгоритма Ланса — Уильяма (Lance — Williams). Алгоритмы Ланса — Уильяма неограниченное семейство агломеративных иерархических алгоритмов, которые представляются рекуррентными формулами для обновления расстояния кластеров на каждом шаге (каждый раз, когда пара кластеров объединяется). На каждом шаге необходимо оптимизировать целевую функцию (найти оптимальную пару кластеров для объединения). Рекуррентная формула упрощает обнаружение оптимальной пары.

Предположим, что кластеры С, и Cj — очередные претенденты для сливания. В этом состоянии известны все текущие попарные расстояния кластеров. Рекуррентная формула дает обновленные расстояния кластеров после предстоящего слияния групп С, и С}.

Пусть dip dik и djk будут попарными расстояниями между кластерами С,, Cj и Ск, dm будет расстоянием между новыми кластерами Ct и 6) и Ск.

Алгоритм принадлежит семейству Ланса — Уильяма, если обновленное расстояние группы d^k может быть вычислено рекуррентно:

где а,, а,, р и у являются параметрами, которые могут зависеть от размеров кластера и вместе с функцией расстояния кластера dy определяют кластеры текущего уровня иерархии кластеров. Использование обновления расстояний к этому уровню порождает следующий уровень и т.д., что и составляет алгоритм кластеризации. У нескольких стандартных алгоритмов объединения в кластеры такая рекуррентная формула тоже используется.

Для несвязных кластеров С,, 6) и Ск с числом элементов nv rij и пк соответственно

Следовательно, метод Уорда может быть реализован как алгоритм Ланса — Уильяма с параметрами

Что касается целевой функции, то одной из наиболее распространенных целевых функций является внутрикластерная сумма квадратов. При использовании такой целевой функции алгоритм кластерного анализа может сводиться к следующему: если имеются п элементов и матрица расстояний между ними, сначала считается, что каждый элемент есть отдельный кластер. Затем на каждом шаге объединяются такие два кластера, которые приводят к минимальному увеличению целевой функции.

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >