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

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

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

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

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

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

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

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

Другой важной величиной в кластерном анализе является расстояние между целыми группами объектов. Приведем примеры наиболее распространенных расстояний и мер близости, характеризующих взаимное расположение отдельных групп объектов. Пусть w_i - i-я группа (класс, кластер) объектов, N_i - число объектов, образующих группу w_i, вектор m_i - среднее арифме-тическое объектов, входящих в w_i (другими словами [m_i - <центр тяжести> i-й группы), a q (w_l, w_m) - расстояние меж-ду группами w_l и w_m

Рис. 11. Различные способы определения расстояния между кластерами wl и wm: 1 - по центрам тяжести, 2 - по ближайшим объектам, 3 - по самым далеким объектам

Рис. 3.11.

Расстояние ближайшего соседа есть расстояние между бли-жайшими объектами кластеров:

Расстояние дальнего соседа - расстояние между самыми дальними объектами кластеров:

Расстояние центров тяжести равно расстоянию между центральными точками кластеров:

Обобщенное (по Колмогорову) расстояние между классами, или обобщенное K-расстояние, вычисляется по формуле

В частности, при t à ÷ и при t à -÷ имеем

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

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

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

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

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