Этапы кластерного анализа (3-5)

этап. Выбор метода объединения объектов в кластеры

Следующим этапом кластерного анализа является объединение объектов в кластеры при использовании матрицы расстояний.

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

Иерархические методы подразделяются на дивизимные и агломеративные.

В дивизимных процедурах на первом этапе все объекты объединены в один кластер, а на последнем этапе каждый объект представляет отдельный кластер. Другими словами, агломеративная процедура — это объединение объектов в кластеры, а дивизимная процедура — эго разбиение совокупности объектов на кластеры.

В агломеративных процедурах на первом этапе каждый объект представляет собой отдельный кластер, а на последнем этапе — один объединенный кластер из всех объектов.

Рассмотрим иерархические агломеративные методы кластеризации данных, как наиболее предпочитаемые в компьютерных программах. Целью этих методов является классификация объектов в кластеры на основе меры сходства или расстояния.

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

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

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

Перечислим пять методов объединения (связи), которые чаще всего используются в иерархических агломеративных методах кластеризации данных:

• 1) межгрупповое связывание (between groups linkage). Другое название этого метода кластеризации — связывание средних внутри групп. Вычисляется наименьшее среднее значение расстояния между всеми нарами групп. На каждом шаге объединяются кластеры или объекты, расстояние между которыми минимально;
• 2) одиночное связывание (nearest neighbor). Этот метод в отечественной литературе известен под названием «метод ближайшего соседа». Принцип действия этого метода заключается в том, что за расстояние между кластерами принимают расстояние между их ближайшими объектами. Другими словами, сначала объединяются два самых близких наблюдения, имеющих минимальное расстояние, после чего матрица расстояний пересчитывается заново. На последнем шаге все наблюдения будут объединены в один кластер;
• 3) полное связывание (furthest neighbor). Чаще всего этот метод упоминается, как «метод дальнего соседа», в котором за расстояние между кластерами принимают расстояние между наиболее удаленными друг от друга их объектами;
• 4) центроидная кластеризация (centroid clustering). При центроидной кластеризации расстояние между кластерами находится как расстояние между их центрами тяжести;
• 5) метод Варда (Ward's method). Для оценки расстояний между кластерами используется метод дисперсионного анализа. Характеристикой качества кластеризации данных является достижение минимального значения внутриклассовой дисперсии.

Итеративный метод кластерного анализа отличается от иерархического тем, что число кластеров определяется сразу, в самом начале анализа. Чаще всего в итеративном кластерном анализе применяется метод К-средних, являющийся наиболее популярным методом кластеризации. При иерархическом кластерном анализе оптимальное число кластеров определяется на заключительном этапе.

Метод К-средних был предложен в 1950;х гг. математиком Г. Штейнгаузом и почти одновременно С. Ллойдом. Алгоритм метода К-средних заключается в минимизации суммы квадратов отклонений точек кластеров от центров этих кластеров. На каждой итерации центр масс пересчитывается для каждого кластера, полученного на предыдущем шаге. Алгоритм выполняется до тех пор, пока происходит изменения кластеров.

Метод К-средних существенно отличается от иерархического агломеративного метода и является итеративной процедурой, в результате которой на каждой итерации объекты перемещаются в различные кластеры. Метод /С-средних предполагает, что задается число кластеров, на которые надо разбить исходные объекты. Алгоритм этого метода таков: случайным образом отбираются k объектов, которые становятся центрами групп. Затем состав кластеров меняется с тем, чтобы минимизировать изменчивость внутри кластеров и максимизировать изменчивость между кластерами. Каждый следующий объект относится к той группе, мера сходства с центром тяжести которой минимальна. Далее вычисляется новый центр тяжести для кластера. Алгоритм будет повторяться до тех пор, пока состав кластеров не перестанет меняться.

этап. Определение оптимального числа кластеров

Как было отмечено выше, при итеративном алгоритме кластерного анализа число кластеров должно быть задано.

Отметим, что проблема определения оптимального числа кластеров при иерархических процедурах кластерного анализа является нерешенной. Однако имеются некоторые подходы к ее решению.

Одним из результатов иерархического кластерного анализа является таблица слияния, которая содержит коэффициенты. Эти коэффициенты равны значению расстояния между кластерами, которые объединяются на данном шаге. Используя таблицу слияния, можно оценить оптимальное число кластеров. Необходимо проанализировать динамику разности между соседними коэффициентами по шагам кластеризации, другими словами — абсолютный прирост коэффициента. Требуется найти тот шаг, при котором абсолютный прирост коэффициента максимален, и определить оптимальное число кластеров. Для этого находим разность между числом объектов п и порядковыми номерами шагов (по отдельности), между которыми выявлен наибольший абсолютный прирост коэффициента.

Так, например, в расчетах по странам «Группы двадцати» (п = 20) и в таблице последовательного слияния наибольший абсолютный прирост коэффициента выявлен при переходе с 15-го на 16-й шаг: он равен 4,585. Следовательно, оптимальное число кластеров равно пяти кластерам (20 — 15 = 5) или четырем кластерам (20 — 16 = 4). Выбор числа кластеров (5 или 4) зависит от более адекватной интерпретации результатов. В нашем примере мы остановились на выборе пяти кластеров.

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

этап. Интерпретация кластеров и качества разбиения

Для интерпретации результатов необходимо иметь «профиль» кластера, который хорошо описывается средними значениями показателей объектов, вошедших в кластер, и средними квадратическими отклонениями. Расчет этих значений и их анализ позволяет дать условное название кластерам и их характеристику.

Важным вопросом на этом этапе является оценка качества разбиения на кластеры. Чаще всего мерой качества выступает сумма внутриклассовых дисперсий расстояний или сумма попарных внутриклассовых расстояний между внутрикластерными элементами.