Функционалы качества разбиения. Иерархические кластер-процедуры


Существует большое количество различных способов разбиения заданной совокупности элементов на классы. Поэтому представляет интерес задача сравнительного анализа качества этих способов разбиения Q(S), определенного на множестве всех возможных разбиений.

Тогда под наилучшим разбиением S* понимаем такое разбиение, при котором достигается экстремум выбранного функционала качества. Следует отметить, что выбор того или иного функционала качества, как правило, опирается на эмпирические соображения. Рассмотрим некоторые наиболее распространенные функционалы качества разбиения. Пусть исследованием выбрана метрика ρ в пространстве Х и пусть S=(s1,s2,...,sp) – некоторое фиксированное разбиение наблюдений х1, ...,хn на заданное число р классов

s1,s2,...,sp.

За функционал качества берут сумму («взвешенную») внутриклассовых дисперсий

 

Иерархические кластер-процедуры

 

Иерархические (древообразные) процедуры являются наиболее распространенными (в смысле реализации на ЭВМ) алгоритмами кластерного анализа, Они бывают двух типов: агломеративные и дивизимные. В агломеративных процедурах начальным является разбиение, состоящее из n одноэлементных классов, а конечным – из одного класса; в дивизимных – наоборот. Принцип работы иерархических агломеративных (дивизимных) процедур состоит в последовательном объединении (разделении) групп элементов сначала самых близких (далеких), а затем все более отдаленных (близких) друг от друга. Большинство этих алгоритмов исходит из матрицы расстояний (сходства). К недостаткам иерархических процедур следует отнести громоздкость их вычисли- тельной реализации. Алгоритмы требуют вычисления на каждом шаге матрицы расстояний, а следовательно емкой машинной памяти и большого количества времени. В этой связи реализация таких алгоритмов при числе наблюдений, большем нескольких сотен, нецелесообразна, а в ряде случаев и невозможна. В качестве примера рассмотрим агломеративный иерархический алгоритм. На первом шаге алгоритма каждое наблюдение xi (i=1,2,...n) рассматривается как отдельный кластер. В дальнейшем на каждом шаге работы алгоритма происходит объединение двух самых близких кластеров и с учетом принятого расстояния по формуле пересчитывается матрица расстояний, размерность которой, очевидно, снижается на единицу. Работа алгоритма заканчивается, когда все наблюдения объединены в один класс. Большинство программ, реализующих алгоритм иерархической классификации, предусматривает графическое представление результатов классификации в виде дендрограммы.

 

 

Предыдущие материалы: Следующие материалы: