Кластерный анализ. Кластерный анализ предназначен для разбиения множест­ва объектов на заданное или неизвестное число классов на основании некоторого математического критерия

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

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

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

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

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

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

Другой важной величиной в кластерном анализе является расстояние между целыми группами объектов.

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

Рис. 3.11.

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

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

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

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

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

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