Кластеризация

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

История и происхождение

Термин «кластер» (от англ. cluster — гроздь, скопление) впервые был введён в психологии и антропологии в 1930-х годах. Первые формальные алгоритмы кластеризации появились в 1950-х годах. В 1952 году К. С. Бёрт предложил метод иерархической кластеризации для анализа психологических тестов. В 1960-х годах Дж. Хартиган и М. Вонг разработали алгоритм k-средних (k-means), ставший одним из самых популярных. В СССР значительный вклад в развитие кластерного анализа внесли математики А. А. Дородницын, Ю. И. Журавлёв и В. В. Рязанов, которые разработали методы распознавания образов и классификации без учителя. С развитием вычислительной техники в 1980–1990-х годах кластеризация стала широко применяться в биоинформатике, маркетинге, геоинформатике и анализе текстов.

Основные подходы и алгоритмы

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

Иерархическая кластеризация

Методы, строящие дерево вложенных кластеров (дендрограмму). Разделяются на агломеративные (снизу вверх: каждый объект — отдельный кластер, затем они последовательно объединяются) и дивизивные (сверху вниз: все объекты — один кластер, затем он рекурсивно разделяется). Расстояние между кластерами может измеряться по-разному: одиночная связь (ближайшие соседи), полная связь (дальние соседи), средняя связь (UPGMA), метод Уорда (минимизация внутригрупповой дисперсии). Иерархические методы наглядны, но вычислительно затратны для больших наборов данных (O(n²) и выше).

Метод k-средних (k-means)

Один из самых распространённых итеративных алгоритмов. Цель — разбить n объектов на k кластеров, минимизируя сумму квадратов расстояний от точек до центроидов кластеров. Алгоритм: 1) случайно выбираются k центроидов; 2) каждый объект приписывается к ближайшему центроиду; 3) центроиды пересчитываются как средние точки в кластере; 4) шаги 2–3 повторяются до сходимости. Требует заранее заданного числа кластеров k, чувствителен к начальному выбору центроидов и к выбросам. Существуют модификации: k-medoids (использует реальные объекты как центры), k-means++ (улучшенная инициализация), mini-batch k-means (для больших данных).

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

Выделяют кластеры как области высокой плотности объектов, разделённые областями низкой плотности. Наиболее известен алгоритм DBSCAN (Density-Based Spatial Clustering of Applications with Noise), который определяет кластеры как связные компоненты графа, где вершины — объекты, а рёбра существуют, если расстояние между объектами меньше заданного порога ε, и объект имеет не менее MinPts соседей. DBSCAN автоматически определяет количество кластеров, устойчив к выбросам и может находить кластеры произвольной формы. Недостаток — чувствительность к параметрам ε и MinPts. Другие плотностные методы: OPTICS (обобщение DBSCAN), HDBSCAN (иерархический вариант).

Методы на основе распределений

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

Спектральная кластеризация

Использует собственные векторы матрицы сходства (или графа) для понижения размерности, после чего применяет k-средних в новом пространстве. Эффективна для кластеров сложной формы, особенно когда данные нелинейно разделимы. Вычислительно сложна для больших графов.

Другие методы

• Метод нечёткой c-средних (Fuzzy C-means) — мягкая версия k-средних, где каждый объект имеет степень принадлежности к каждому кластеру (от 0 до 1).
• Метод сдвига среднего (Mean Shift) — немодальный итеративный алгоритм, сдвигающий точки в сторону наибольшей плотности; не требует задания числа кластеров.
• Алгоритм BIRCH — масштабируемый метод для больших данных, использующий структуру CF-дерева (Clustering Feature tree).
• Алгоритм CURE — компромисс между иерархическим и k-средних, использует несколько репрезентативных точек на кластер.

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

Качество кластеризации оценивается с помощью внутренних (без эталонных меток) и внешних (с эталонными метками) критериев.

Внутренние критерии

• Сумма квадратов ошибок (SSE) — минимизируется в k-средних.
• Коэффициент силуэта (Silhouette score) — для каждого объекта измеряет, насколько он ближе к своему кластеру, чем к соседнему. Значения от -1 до 1.
• Индекс Калински-Харабаса (CH index) — отношение межкластерной дисперсии к внутрикластерной.
• Индекс Дэвиса-Болдина (DB index) — отношение суммы внутрикластерных разбросов к расстоянию между центроидами.
• Индекс Данна (Dunn index) — отношение минимального межкластерного расстояния к максимальному диаметру кластера.

Внешние критерии

Используются, если известна правильная разметка (ground truth):

• Чистота (Purity) — доля объектов, отнесённых к кластеру с преобладающим классом.
• Взаимная информация (NMI, Adjusted Rand Index) — меры согласия между разбиениями.
• Точность, полнота, F-мера — применяются для оценки соответствия кластеров эталонным классам.

Применение

Кластеризация применяется в самых разных областях:

Наука и инженерия

• Биоинформатика: кластеризация генов и белков по профилям экспрессии, выявление подтипов рака, группировка последовательностей ДНК.
• Астрономия: классификация галактик по спектральным характеристикам, выделение звёздных скоплений.
• Физика: анализ данных коллайдеров, группировка частиц по трекам.
• Геология: районирование территорий по сейсмической активности, выделение типов почв.

Бизнес и маркетинг

• Сегментация клиентов: разбиение покупателей на группы по поведению, демографии, предпочтениям для таргетированного маркетинга.
• Анализ корзины покупок: выявление групп товаров, часто покупаемых вместе.
• Обнаружение аномалий: выявление мошеннических транзакций как объектов, не входящих ни в один кластер.

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

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

Социальные науки и психология

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

Медицина

• Классификация заболеваний: выделение подтипов болезни (например, рака молочной железы) по генетическим или клиническим признакам.
• Анализ медицинских изображений: сегментация опухолей на МРТ или КТ.

Проблемы и ограничения

• Выбор числа кластеров: большинство алгоритмов (k-средних, EM) требуют априорного задания k. Методы выбора (локтевой метод, силуэт) не всегда дают однозначный ответ.
• Форма кластеров: k-средних предполагает сферические кластеры равного размера; плотностные методы могут находить произвольные формы, но чувствительны к параметрам.
• Масштабируемость: иерархические и спектральные методы плохо работают на больших данных (миллионы объектов). Для таких случаев используются приближённые алгоритмы (mini-batch k-means, BIRCH, HDBSCAN*).
• Чувствительность к выбросам: k-средних сильно смещается под влиянием выбросов; DBSCAN устойчивее, но может ошибочно отнести выбросы к шуму.
• Интерпретируемость: результаты кластеризации (особенно в многомерных пространствах) сложно визуализировать и интерпретировать. Для снижения размерности часто применяют PCA или t-SNE.
• Неустойчивость: разные запуски алгоритма (из-за случайной инициализации) могут давать разные результаты. Для стабилизации используют ансамблевые методы или фиксацию seed.

Интересные факты

• Кластеризация лежит в основе многих современных технологий: от распознавания лиц в социальных сетях до систем автоматического перевода.
• Алгоритм k-средних был независимо переоткрыт несколько раз: в 1957 году Стюартом Ллойдом (как метод квантования), в 1965 году Эдуардом Форги и в 1967 году Джеймсом МакКуином.
• В 2020 году группа исследователей из Массачусетского технологического института (MIT) разработала алгоритм кластеризации, который может работать на квантовых компьютерах, потенциально ускоряя обработку огромных массивов данных.
• Кластеризация используется в криминалистике для анализа серийных преступлений — группировки мест преступлений по географическим признакам.
• В России кластеризация активно применяется в геоинформационных системах для районирования территорий, в том числе для анализа данных переписи населения и оценки экологической обстановки.

Источники

• Hastie T., Tibshirani R., Friedman J. The Elements of Statistical Learning: Data Mining, Inference, and Prediction. — 2nd ed. — Springer, 2009.
• Jain A. K., Murty M. N., Flynn P. J. Data Clustering: A Review // ACM Computing Surveys. — 1999. — Vol. 31, No. 3.
• Xu R., Wunsch D. C. Clustering. — Wiley-IEEE Press, 2009.
• Дюран Б., Оделл П. Кластерный анализ. — М.: Статистика, 1977.
• Журавлёв Ю. И., Рязанов В. В., Сенько О. В. «Распознавание образов и кластерный анализ» // Математические методы распознавания образов. — М.: Наука, 1990.