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

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

История

Первые формальные методы кластеризации были предложены в середине XX века. В 1932 году психолог Р. Трайон (R. C. Tryon) ввёл понятие «кластерный анализ» для описания процедуры группировки переменных в психологических тестах. В 1938 году Р. Фишер (R. A. Fisher) и Л. Тьюки (J. W. Tukey) разработали иерархические алгоритмы, основанные на последовательном объединении ближайших объектов. В 1950-е годы К. Мэлоун (K. Maloney) и М. Андерсон (M. Anderson) формализовали метод k-средних (k-means), который стал одним из самых популярных алгоритмов кластеризации. В 1960-е годы появились работы Г. Болла (G. Ball) и Д. Холла (D. Hall) по адаптивным методам, а также Д. Уишарта (D. Wishart) по иерархической кластеризации с использованием матрицы расстояний. В 1970-е годы кластерный анализ начал активно применяться в биологии (таксономия, экология), медицине (диагностика), социологии (сегментация рынка) и других областях. С развитием вычислительной техники и появлением больших данных в конце XX — начале XXI века алгоритмы кластеризации были адаптированы для работы с многомерными, нечисловыми и потоковыми данными, а также интегрированы в системы машинного обучения.

Основные понятия и принципы

Мера близости (расстояние)

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

• Евклидово расстояние — геометрическое расстояние в многомерном пространстве. Чувствительно к масштабу признаков.
• Манхэттенское расстояние (L1-норма) — сумма модулей разностей координат. Менее чувствительно к выбросам.
• Расстояние Чебышёва — максимум модулей разностей.
• Косинусное расстояние — мера угла между векторами; часто используется для текстурных или текстовых данных.
• Расстояние Махаланобиса — учитывает корреляцию между признаками и масштабирование.

Для категориальных данных применяются меры на основе частот (например, расстояние Жаккара, расстояние Хэмминга).

Критерии качества кластеризации

Качество разбиения оценивается через внутрикластерную дисперсию (сумму квадратов расстояний до центров кластеров) и межкластерную дисперсию. Основные критерии:

• Среднее силуэтов (silhouette score) — мера, показывающая, насколько объект похож на свой кластер по сравнению с соседним.
• Индекс Данна (Dunn index) — отношение минимального расстояния между кластерами к максимальному диаметру кластера.
• Индекс Калински — Харабаса (Calinski-Harabasz index) — отношение межкластерной дисперсии к внутрикластерной.
• Elbow method (метод локтя) — визуальный способ выбора числа кластеров по графику зависимости внутрикластерной суммы квадратов от числа кластеров.

Классификация методов кластеризации

Иерархические методы

Иерархическая кластеризация строит дендрограмму — дерево вложенных кластеров. Различают два подхода:

• Агломеративный (снизу вверх) — каждый объект изначально является отдельным кластером, затем на каждом шаге объединяются два ближайших кластера. Используются различные критерии объединения: одиночная связь (single linkage), полная связь (complete linkage), средняя связь (average linkage), метод Уорда (Ward’s method).
• Дивизивный (сверху вниз) — все объекты образуют один кластер, который последовательно делится на более мелкие.

Неиерархические (плоские) методы

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

• Метод k-средних (k-means) — итеративный алгоритм, минимизирующий сумму квадратов расстояний от объектов до центроидов кластеров. Требует указания числа кластеров k.
• Метод k-медоидов (k-medoids) — аналог k-средних, но в качестве центров кластеров выбираются реальные объекты (медоиды). Более устойчив к выбросам.
• Метод C-средних (fuzzy c-means) — нечёткая кластеризация, где каждый объект может принадлежать нескольким кластерам с разной степенью принадлежности.

Плотностные методы

Основаны на представлении кластеров как областей высокой плотности объектов, разделённых областями низкой плотности.

• DBSCAN (Density-Based Spatial Clustering of Applications with Noise) — выделяет кластеры произвольной формы и автоматически определяет выбросы. Требует задания параметров: радиус окрестности (eps) и минимальное число точек в окрестности (minPts).
• OPTICS (Ordering Points To Identify the Clustering Structure) — обобщение DBSCAN, строящее иерархию кластеров на основе плотности.

Вероятностные методы

Предполагают, что данные порождены смесью вероятностных распределений (чаще всего многомерных нормальных). Алгоритм EM (Expectation-Maximization) итеративно оценивает параметры смеси и апостериорные вероятности принадлежности объектов к компонентам.

Методы на основе графов

Кластеризация рассматривается как задача разбиения графа, где вершины — объекты, а рёбра взвешены мерой сходства. Используются алгоритмы спектральной кластеризации (например, метод нормализованных разрезов — normalized cuts) и методы выделения сообществ (community detection) в социальных сетях.

Применение

Биология и медицина

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

Маркетинг и социология

• Сегментация рынка — разделение потребителей на группы по демографическим, поведенческим или психографическим признакам.
• Анализ социальных сетей — выявление сообществ, групп по интересам.

Информационные технологии

• Сжатие данных — замена группы похожих объектов одним представителем (например, в обработке изображений).
• Обнаружение аномалий — объекты, не попавшие ни в один кластер, могут быть выбросами или мошенническими транзакциями.
• Рекомендательные системы — кластеризация пользователей или товаров для персонализированных рекомендаций.

Геоинформационные системы

• Пространственная кластеризация — выделение скоплений точек (например, очагов преступности, месторождений полезных ископаемых).

Ограничения и критика

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

Программные реализации

Кластерный анализ реализован во многих пакетах статистической обработки и языках программирования:

• Python — библиотеки scikit-learn (KMeans, DBSCAN, AgglomerativeClustering), SciPy (иерархическая кластеризация), hdbscan.
• R — пакеты cluster, fastcluster, dbscan.
• MATLAB — встроенные функции kmeans, clusterdata, linkage.
• SPSS, Statistica, SAS — модули кластерного анализа в коммерческих статистических пакетах.

Источники

• Everitt, B. S., Landau, S., Leese, M., & Stahl, D. (2011). Cluster Analysis (5th ed.). Wiley.
• Kaufman, L., & Rousseeuw, P. J. (2009). Finding Groups in Data: An Introduction to Cluster Analysis. Wiley.
• Hastie, T., Tibshirani, R., & Friedman, J. (2009). The Elements of Statistical Learning (2nd ed.). Springer.
• Jain, A. K., Murty, M. N., & Flynn, P. J. (1999). Data clustering: a review. ACM Computing Surveys, 31(3), 264–323.
• MacQueen, J. (1967). Some methods for classification and analysis of multivariate observations. Proceedings of the Fifth Berkeley Symposium on Mathematical Statistics and Probability, 1, 281–297.