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

Главные понятия

Цель кластерного анализа – формирование групп (классов) объектов, схожих между собой и в то же время отличающихся от объектов других классов. Синонимами слова кластер (cluster – пучок, куст, англ.) служат класс, таксон.

Евклидово расстояние – мера сходства объектов.

Агломеративная классификация (объединение, Joining) предполагает последовательное объединение отдельных объектов, имеющих тесное сходство, в кластеры, затем объединение близких кластеров – до достижения заданного порога сходства или же до полного объединения в один кластер.

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

Правила связывания – linkage rules используются при присоединении объекта к кластеру и объединении кластеров:

- одиночная связь – single linkage (метод ближайшего соседа). Расстояние между двумя кластерами определяется расстоянием между двумя наиболее близкими объектами (ближайшими соседями) в различных кластерах;

- полная связь – complete linkage (метод наиболее удаленных соседей). Расстояния между кластерами определяются наибольшим расстоянием между любыми двумя объектами в различных кластерах (т.е. «наиболее удаленными соседями»).

- невзвешенное попарное среднее – unweighted pair-group average. Расстояние между двумя различными кластерами вычисляется как среднее расстояние между всеми парами объектов в них.

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

- невзвешенный центроидный метод - unweighted pair-group centroid method. В этом методе расстояние между двумя кластерами определяется как расстояние между их центрами тяжести.

- взвешенный центроидный метод (медиана) - weighted pair-group centroid (median) method. При вычислениях используются веса для учёта разницы между размерами кластеров (т.е. числами объектов в них). Если имеются значительные отличия в размерах кластеров, этот метод оказывается предпочтительнее предыдущего.

- метод Варда – Ward’s method. Этот метод отличается от всех других методов, поскольку он использует методы дисперсионного анализа для оценки расстояний между кластерами. Метод минимизирует сумму квадратов (SS) для любых двух (гипотетических) кластеров, которые могут быть сформированы на каждом шаге.

Дивизимная классификация – классификация путем разделения выборки на классы.

Метод K средних (K-means method) строит K различных кластеров, расположенных на возможно больших расстояниях друг от друга.

Пример 4.1. Кластеризации объектов методом объединения - Joining (tree clustering).

Данные взяты из файла cars.sta из Examples/Datasets. Пример основан на выборке различных автомобилей. Для каждого автомобиля зарегистрированы данные, формализованные следующими переменными:

Price – приблизительная цена;

Acceler – ускорение автомобиля (от 0 до 60 в секундах);

Braking – тормозная характеристика автомобиля (тормозной путь при скорости 80 миль в час до полной остановки);

Handling – расстояние, пройденное автомобилем с полным баком;

Mileage – топливное расстояние в милях (мили/галлон).

Шкала измерения. Все алгоритмы кластеризации должны оценить расстояния между кластерами или объектами. Так как используются различные меры (например, число секунд, тысячи долларов, и т.д.), то данные стандартизированы (команда Standardize из меню Data) так, чтобы каждая переменная имела среднее 0 и среднеквадратичное отклонение 1.

Цель анализа: можно ли на основе этих данных сформировать «естественные» кластеры?  

Спецификация анализа. Из меню Statistics/Multivariate Exploratory Techniques выберите Cluster analysis для открытия стартовой панели Clustering Method – Метод кластеризации. Здесь выберите в качестве метода кластеризации метод объединения – Joining (tree clustering) и нажмите OK. Затем на закладке Quick нажмите кнопку Variables (переменные), чтобы задать все переменные (ALL). Поскольку предполагается классификация объектов (автомобилей), необходимо на закладке Advanced в окне Cluster указать Cases (raws) (по умолчанию задан параметр Variables, что соответствует классификации переменных).

Далее выберите правило объединения в окне Amalgamation (linkage) rule: из предложенного списка можно выбрать Single Linkage (простая связь, или метод ближнего соседа) или Complete Linkage (полная связь, или метод дальнего соседа) и т.д. Эти правила позволяют присоединять объект к уже созданному кластеру или объединять два кластера. Рекомендуется в этом примере использовать Complete Linkage.

Для оценки близости объектов используются различные меры: евклидово расстояние (Euclidean distance), расстояние City Block (расстояние городских кварталов, или манхеттенское), мера Чебышева, процент несогласия и другие. В данном примере предлагается выбрать в окне Distance measure евклидово расстояние (Euclidean distance).

Результаты. Для выполнения анализа нажмите OK. После выполнения процедуры объединения объектов результаты отображаются в диалоговом окне Joining Results. На закладке Advanced выберите сначала диаграмму Horizontal hierarchical tree (горизонтальное иерархическое дерево) или Vertical icicle plot (вертикальное дерево).

Ветви диаграмм могут быть прямоугольными или диагональными. Чтобы получить диаграмму с диагональными ветвями, необходимо убрать маркер Rectangular branches. Кроме того, можно использовать стандартизированный масштаб (dlink/dmax*100), отметив маркером поле Scale tree. При выборе этого флажка горизонтальная ось (или вертикальная ось для вертикальных графиков) будет масштабироваться в процентном отношении.

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

Идентифицированные кластеры. Будем рассматривать только горизонтальные иерархические деревья со стандартизированным масштабом. Сначала имеется кластер, состоящий только из Acura и Olds, затем объединяется группа (кластер) из семи автомобилей: Chrysler, Dodge, VW, Honda, Pontiac, Mitsubishi и Nissan. Можно назвать этот кластер «Эконом класс».

Первые два автомобиля, Acura и Olds, присоединяются к этому кластеру на расстоянии 32; после этого ветвь дерева простирается до 60. Таким образом, эти два автомобиля могут также рассматриваться как члены кластера «Эконом класс». Далее виден кластер, начинающийся с Audi и достигающий Ford, а, возможно, до Eagle. Эти автомобили более или менее представляют дорогостоящие, роскошные седаны, поэтому этот кластер может быть идентифицирован как «Бизнес класс».  

И, наконец, в нижней части графика имеются Corvette и Porsche, которые приблизительно соединены на расстоянии связи 30 и образуют отдельный кластер. 

Неграфическое изображение полученных результатов представляет список связи (в Joining Results – Advanced выбрать Amalgamation schedule). Электронная таблица списка связи перечисляет объекты, т.е. автомобили, которые соединены на соответствующих расстояниях связи (в крайнем левом столбце электронной таблицы).

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

Пример 4.2. Кластеризации объектов методом К-средних

(K-means)

Данные из файла cars.sta будут классифицироваться итерационным методом, суть которого состоит в присоединении объектов к эталонам, число которых K задает пользователь.

Цель анализа та же: получить на основе этих данных «естественные» кластеры.

Спецификация анализа. На стартовой панели Clustering Method – Метод кластеризации выберите метод К-средних (K-means) и нажите OK. Затем на закладке Advanced/Variables задайте все переменные (Select All), укажите число классов (Number of clusters) – 3, число итераций (Number of iterations) – оставьте 10. После нажатия OK получите результаты.

Результаты. В окне K-means Clustering Results на закладке Advanced можно ознакомиться с итогами (Summary Cluster Means& Euclidean Distances) – в таблице представлены расстояния между кластерами. В таблице Analysis of Variances приведены итоги дисперсионного анализа по каждой переменной – суммы квадратов расстояний между кластерами (Between SS) и внутри кластеров (Within SS), величины F-отношений и их значимость.

По каждому кластеру получена описательная статистика (Descriptive Statistics). Можно просмотреть диаграмму средних по классам для каждой переменной (Plot of Means). Наибольший интерес представляет список членов кластеров – Members of each Clusters & Distances. Сопоставление с результатами примера 4.1 показывает, что кластеризация в целом совпадает.