Метод k-медоидов

Метод k-медоидов (англ. k-medoids) — это алгоритм кластеризации, относящийся к группе методов машинного обучения без учителя. Он предназначен для разбиения множества объектов (наблюдений) на заданное число кластеров \( k \) таким образом, чтобы каждый объект принадлежал кластеру, представленному наиболее типичным для него объектом — медоидом. В отличие от более распространённого метода k-средних (k-means), k-медоиды в качестве центров кластеров выбирают реально существующие объекты из набора данных, а не вычисляемые средние значения, что делает алгоритм устойчивым к выбросам и пригодным для работы с данными, для которых не определена операция вычисления среднего (например, категориальные или порядковые данные).

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

Метод k-медоидов был впервые предложен в 1987 году американским статистиком Леонардом Кауфманом (Leonard Kaufman) и бельгийским исследователем Питером Руссо (Peter Rousseeuw) в контексте развития методов разведочного анализа данных. Алгоритм был описан в их книге «Finding Groups in Data: An Introduction to Cluster Analysis» (1990). Идея метода возникла как альтернатива методу k-средних, который чувствителен к выбросам и требует, чтобы данные были представлены в евклидовом пространстве. Кауфман и Руссув предложили использовать в качестве центров кластеров не средние значения, а фактические точки данных, названные медоидами (от англ. medoid — «подобный медиане»). Первоначально алгоритм получил название PAM (Partitioning Around Medoids, «разбиение вокруг медоидов»). Впоследствии были разработаны более эффективные модификации, такие как CLARA (Clustering Large Applications) и CLARANS (Clustering Large Applications based on RANdomized Search).

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

Медоид

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

Кластер

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

Функция стоимости

Качество разбиения оценивается с помощью функции стоимости, которая обычно определяется как сумма расстояний от каждого объекта до его ближайшего медоида: \[ \text{Cost} = \sum_{i=1}^{n} \min_{j \in \{1,\dots,k\}} d(x_i, m_j) \] где \( n \) — число объектов, \( k \) — число кластеров, \( d(x_i, m_j) \) — расстояние между объектом \( x_i \) и медоидом \( m_j \). Цель алгоритма — минимизировать эту сумму.

Алгоритм PAM (Partitioning Around Medoids)

PAM является классической реализацией метода k-медоидов. Алгоритм состоит из двух фаз: построение (BUILD) и обмен (SWAP).

Фаза построения (BUILD)

1. Выбрать начальный набор из \( k \) медоидов. Обычно первый медоид выбирается как объект, сумма расстояний от которого до всех остальных объектов минимальна. Затем последовательно добавляются новые медоиды: на каждом шаге выбирается объект, который максимально уменьшает функцию стоимости при добавлении его в качестве медоида.
2. После выбора всех \( k \) медоидов каждый объект приписывается к ближайшему медоиду, формируя начальные кластеры.

Фаза обмена (SWAP)

1. Для каждой пары «текущий медоид \( m \)» и «не-медоид \( o \)» вычисляется изменение функции стоимости, если заменить \( m \) на \( o \).
2. Если существует замена, уменьшающая стоимость, выполняется замена с максимальным уменьшением.
3. Шаги 1–2 повторяются до тех пор, пока замена не перестанет улучшать функцию стоимости.

Сложность

Временная сложность PAM составляет \( O(k(n-k)^2) \) на одну итерацию, что делает его непригодным для больших наборов данных (свыше нескольких тысяч объектов). Для крупных массивов данных применяются аппроксимации.

Модификации и варианты

CLARA (Clustering Large Applications)

CLARA — это модификация PAM, предназначенная для работы с большими данными. Алгоритм многократно выбирает случайные подвыборки (сэмплы) из исходного набора, применяет PAM к каждой подвыборке и выбирает разбиение с наименьшей функцией стоимости на всём наборе данных. Размер подвыборки обычно составляет \( 40 + 2k \) объектов. CLARA менее точен, чем PAM, но значительно быстрее.

CLARANS (Clustering Large Applications based on RANdomized Search)

CLARANS — улучшенная версия CLARA, предложенная в 1994 году. Вместо фиксированных подвыборок алгоритм выполняет случайный поиск в пространстве возможных наборов медоидов, используя метод «поиска с возвратом» (hill climbing). CLARANS сочетает эффективность CLARA и качество PAM.

k-medoids с произвольной метрикой

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

Сравнение с методом k-средних

Применение

Метод k-медоидов применяется в задачах, где важна интерпретируемость кластеров и устойчивость к выбросам:

• Биоинформатика: кластеризация генов или белков на основе их экспрессии или структурного сходства. Медоиды представляют типичные образцы.
• Медицина: выделение групп пациентов с похожими симптомами или течением заболевания. Медоиды могут служить прототипами для диагностики.
• Маркетинг: сегментация клиентов на основе их покупательского поведения. Медоиды — «типичные» клиенты каждого сегмента.
• Обработка изображений: кластеризация пикселей или признаков изображений. Медоиды — реальные пиксели, что упрощает визуализацию.
• Анализ текстов: кластеризация документов по тематикам. Медоиды — реальные документы, которые можно использовать как эталонные.
• Социология: выделение типичных респондентов в опросах.

Пример работы алгоритма

Рассмотрим простой пример. Пусть имеется 6 точек на плоскости: A(1,1), B(2,2), C(3,1), D(8,8), E(9,9), F(10,8). Требуется разбить их на 2 кластера методом k-медоидов.

1. Фаза BUILD: Выбираем первый медоид — точку, сумма расстояний до всех остальных минимальна. Для точки A сумма расстояний до B, C, D, E, F: \( \sqrt{2} + 2 + \sqrt{98} + \sqrt{128} + \sqrt{130} \approx 1.41 + 2 + 9.90 + 11.31 + 11.40 = 36.02 \). Для точки D: \( \sqrt{98} + \sqrt{72} + \sqrt{74} + \sqrt{2} + \sqrt{5} \approx 9.90 + 8.49 + 8.60 + 1.41 + 2.24 = 30.64 \). Выбираем D как первый медоид. Затем добавляем второй медоид, который максимально уменьшает стоимость. После расчётов вторым медоидом выбирается A.

1. Фаза SWAP: Пробуем заменить медоиды на другие точки. Например, замена A на B: стоимость уменьшится? После проверок оптимальным оказывается набор медоидов {A, D}. Точки A, B, C приписываются к кластеру с медоидом A; точки D, E, F — к кластеру с медоидом D.

Результат: два кластера — левый (A, B, C) и правый (D, E, F). Медоиды — A и D, являющиеся реальными точками.

Критика и ограничения

• Вычислительная сложность: PAM неприменим для наборов данных с десятками тысяч объектов. CLARA и CLARANS частично решают эту проблему, но теряют в точности.
• Чувствительность к начальному выбору: как и многие алгоритмы кластеризации, k-медоиды могут сходиться к локальному оптимуму. Результат зависит от начального набора медоидов.
• Необходимость задания \( k \): число кластеров должно быть указано заранее. Выбор оптимального \( k \) требует дополнительных методов (например, силуэтный анализ или метод локтя).
• Масштабируемость: даже CLARANS может быть медленным для очень больших данных (миллионы объектов). Для таких случаев чаще используют k-средних или иерархические методы.

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

• Термин «медоид» был введён Кауфманом и Руссувом по аналогии с медианой — как «медиана многомерных данных».
• Метод k-медоидов лежит в основе многих современных алгоритмов кластеризации, таких как PAM, CLARA, CLARANS, а также их параллельных версий.
• В пакетах статистического анализа (R, Python) метод k-медоидов реализован в функциях pam(), clara() и clarans().

Источники

1. Kaufman, L., & Rousseeuw, P. J. (1990). Finding Groups in Data: An Introduction to Cluster Analysis. Wiley.
2. Ng, R. T., & Han, J. (1994). «Efficient and Effective Clustering Methods for Spatial Data Mining». Proceedings of the 20th VLDB Conference.
3. Han, J., Kamber, M., & Pei, J. (2011). Data Mining: Concepts and Techniques (3rd ed.). Morgan Kaufmann.
4. Hastie, T., Tibshirani, R., & Friedman, J. (2009). The Elements of Statistical Learning (2nd ed.). Springer.