Автор: Сотник С.Л.

Методы и алгоритмы анализа структуры многомерных данных

Кластерный анализ

Кластерный анализ предназначен для разбиения множест¬ва объектов на заданное или неизвестное число классов на основании некоторого математического критерия качества клас-сификации (cluster (англ.) — гроздь, пучок, скопление, группа элементов, характеризуемых ка-ким-либо общим свой¬ством). Критерий качества кластеризации в той или иной мере отражает следующие неформальные требования:

а) внутри групп объекты должны быть тесно связаны между собой;

б) объекты разных групп должны быть далеки друг от друга;

в) при прочих равных условиях распределения объектов по группам должны быть рав-номерными.

Требования а) и б) выражают стандартную концепцию ком¬пактности классов разбие-ния; требование в) состоит в том, чтобы критерий не навязывал объ¬единения отдельных групп объектов.

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

Другой важной величиной в кластерном анализе является расстояние между целыми группами объектов. Приведем примеры наиболее распространенных расстояний и мер близости, характеризующих взаимное расположение отдельных групп объектов. Пусть wi — i-я группа (класс, кластер) объектов, Ni — число объектов, образующих группу wi, вектор i — среднее арифме¬тическое объектов, входящих в wi (другими словами [i — «центр тяжести» i-й группы), a q ( wl, wm ) — расстояние меж¬ду группами wl и wm

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

Нацеленность алгоритмов кластерного анализа на опре¬деленную структуру группировок объектов в пространстве признаков может приводить к неоптимальным или даже неправильным результатам, если гипотеза о типе группировок неверна. В случае отличия реальных распределе-ний от ги¬потетических указанные алгоритмы часто «навязывают» дан¬ным не присущую им структуру и дезориентируют исследо¬вателя. Поэтому экспериментатор, учитывающий данный факт, в условиях априорной неопределенности прибегает к применению батареи алгоритмов кластерного анализа и от¬дает предпочтение какому-либо выводу на основании комп¬лексной оценки совокупности результатов работы этих ал¬горитмов.

Алгоритмы кластерного анализа отличаются большим разнообразием. Это могут быть, например, алгоритмы, реализу¬ющие полный перебор сочетаний объектов или осуществляю¬щие случайные разбиения множества объектов. В то же время большинство таких алгоритмов состо-ит из двух этапов. На первом этапе задается начальное (возможно, искусственное или даже про-извольное) разбиение множества объектов на классы и определяется некоторый математический критерий качества автоматической классификации. Затем, на втором этапе, объек¬ты переносятся из класса в класс до тех пор, пока значение критерия не перестанет улучшаться.

Многообразие алгоритмов кластерного анализа обусловле¬но также множеством различ-ных критериев, выражающих те или иные аспекты качества автоматического группирования. Простейший критерий качества непосредственно базируется на величине расстояния между кла-стерами. Однако такой критерий не учитывает «населенность» кластеров — относи¬тельную плотность распределения объектов внутри выделяе¬мых группировок. Поэтому другие критерии основываются на вычислении средних расстояний между объектами внутри кла¬стеров. Но наи-более часто применяются критерии в виде от¬ношений показателей «населенности» кластеров к расстоянию между ними. Это, например, может быть отношение суммы межклассовых расстоя-ний к сумме внутриклассовых (между объектами) расстояний или отношение общей дисперсии дан¬ных к сумме внутриклассовых дисперсий и дисперсии центров кластеров.

Функционалы качества и конкретные алгоритмы автомати¬ческой классификации доста-точно полно и подробно рассмот¬рены в специальной литературе. Эти функционалы и ал¬горитмы характеризуются различной трудоемкостью и подчас требуют ресурсов высокопроизводитель-ных компьютеров. Раз¬нообразные процедуры кластерного анализа входят в состав практически всех современных пакетов прикладных программ для статистической обработки многомерных данных.

Иерархическое группирование

Рис. 12. Результаты работы иерархической агломеративной процедуры группиро-вания объектов, представленные в виде дендрограммы.

Классификационные процедуры иерархического типа предназначены для получения на-глядного представления о стратификационной структуре всей исследуемой совокупности объек-тов. Эти процедуры основаны на последовательном объе¬динении кластеров (агломеративные процедуры) и на последо¬вательном разбиении (дивизимные процедуры). Наибольшее распро-странение получили агломеративные процедуры. Рас¬смотрим последовательность операций в таких процедурах.

На первом шаге все объекты считаются отдельными кла¬стерами. Затем на каждом по-следующем шаге два ближайших кластера объединяются в один. Каждое объединение уменьша-ет число кластеров на один так, что в конце концов все объекты объединяются в один кластер. Наиболее подходящее разбиение выбирает чаще всего сам исследователь, которому предостав¬ляется дендрограмма, отображающая результаты группирования объектов на всех шагах алго-ритма (Рис. 12). Могут од¬новременно также использоваться и математические критерии качест-ва группирования.

Различные варианты определения расстояния между кла¬стерами дают различные вари-анты иерархических агломеративных процедур. Учитывая специфику подобных процедур, для задания расстояния между классами оказывается достаточным указать порядок пересчета рас-стояний между классом wl и классом w(m, n) являющимся объединением двух других классов wm и wn по расстояниям qmn = q(wm, wn) и qln = q(wl, wn) между этими классами. В литературе предлагается следующая общая формула для вычисления расстояния между некоторым классом wl и классом w(m, n):

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