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

Кластеризацию данных без меток можно выполнять с помощью модуля sklearn.cluster.

Каждый алгоритм кластеризации представлен в двух вариантах: класс реализует метод fit для обучения кластеров на обучающих данных, а функция, получая обучающие данные, возвращает массив целочисленных меток, соответствующих различным кластерам. Для класса метки обучающих данных доступны в атрибуте labels_.

2.3.1. Обзор методов кластеризации

../_images/sphx_glr_plot_cluster_comparison_001.png — Сравнение алгоритмов кластеризации в scikit-learn

Название метода	Параметры	Масштабируемость	Применение	Геометрия (используемая метрика)
K-Means	число кластеров	Очень большие `n_samples`, средние `n_clusters` с MiniBatch code	Универсальное применение, кластеры одинакового размера, плоская геометрия, не слишком много кластеров, индуктивный метод	Расстояния между точками
Распространение близости	коэффициент демпфирования, предпочтение для образца	Не масштабируется с ростом n_samples	Много кластеров, кластеры неодинакового размера, неплоская геометрия, индуктивный метод	Расстояние в графе (например, графе ближайших соседей)
Сдвиг среднего	ширина полосы	Не масштабируется с ростом `n_samples`	Много кластеров, кластеры неодинакового размера, неплоская геометрия, индуктивный метод	Расстояния между точками
Спектральная кластеризация	число кластеров	Средние `n_samples`, малые `n_clusters`	Мало кластеров, кластеры одинакового размера, неплоская геометрия, трансдуктивный метод	Расстояние в графе (например, графе ближайших соседей)
Иерархическая кластеризация Уорда	число кластеров или порог расстояния	Большие `n_samples` и `n_clusters`	Много кластеров, возможно, с ограничениями связности, трансдуктивный метод	Расстояния между точками
Агломеративная кластеризация	число кластеров или порог расстояния, тип связи, расстояние	Большие `n_samples` и `n_clusters`	Много кластеров, возможно, с ограничениями связности, неевклидовы расстояния, трансдуктивный метод	Любое попарное расстояние
DBSCAN	размер окрестности	Очень большие `n_samples`, средние `n_clusters`	Неплоская геометрия, кластеры неодинакового размера, удаление выбросов, трансдуктивный метод	Расстояния между ближайшими точками
HDBSCAN	минимальное число элементов кластера, минимальное число соседей точки	Большие `n_samples`, средние `n_clusters`	Неплоская геометрия, кластеры неодинакового размера, удаление выбросов, трансдуктивный метод, иерархический метод, переменная плотность кластеров	Расстояния между ближайшими точками
OPTICS	минимальное число элементов кластера	Очень большие `n_samples`, большие `n_clusters`	Неплоская геометрия, кластеры неодинакового размера, переменная плотность кластеров, удаление выбросов, трансдуктивный метод	Расстояния между точками
Гауссовы смеси	много	Не масштабируется	Плоская геометрия, подходит для оценки плотности, индуктивный метод	Расстояния Махаланобиса до центров
BIRCH	коэффициент ветвления, порог, необязательный глобальный кластеризатор.	Большие `n_clusters` и `n_samples`	Большой набор данных, удаление выбросов, сокращение данных, индуктивный метод	Евклидово расстояние между точками
Бисекционный K-Means	число кластеров	Очень большие `n_samples`, средние `n_clusters`	Универсальное применение, кластеры одинакового размера, плоская геометрия, отсутствие пустых кластеров, индуктивный и иерархический методы	Расстояния между точками

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

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

Трансдуктивные методы кластеризации (в отличие от индуктивных методов кластеризации) не предназначены для работы с новыми, ранее не встречавшимися данными.

Примеры

Индуктивная кластеризация: пример индуктивной модели кластеризации для работы с новыми данными.

2.3.2. K-means

Алгоритм KMeans выполняет кластеризацию данных, пытаясь разделить образцы на n групп с одинаковой дисперсией и минимизируя критерий, известный как инерция или сумма квадратов расстояний внутри кластеров (см. ниже). Для этого алгоритма необходимо задать число кластеров. Он хорошо масштабируется при большом числе образцов и применяется в самых разных областях.

Алгоритм k-means делит набор из \(N\) образцов \(X\) на \(K\) непересекающихся кластеров \(C\), каждый из которых описывается средним значением \(\mu_j\) образцов в кластере. Эти средние обычно называют «центроидами» кластеров; следует отметить, что в общем случае они не являются точками из \(X\), хотя и принадлежат тому же пространству.

Алгоритм K-means стремится выбрать центроиды, минимизирующие инерцию, или критерий суммы квадратов расстояний внутри кластеров:

\[\sum_{i=0}^{n}\min_{\mu_j \in C}(||x_i - \mu_j||^2)\]

Инерцию можно рассматривать как меру внутренней согласованности кластеров. У неё есть несколько недостатков:

Инерция предполагает, что кластеры выпуклые и изотропные, что верно не всегда. Она плохо работает с вытянутыми кластерами и многообразиями неправильной формы.
Инерция не является нормированной метрикой: мы знаем лишь, что меньшие значения лучше, а оптимальное значение равно нулю. Однако в пространствах очень высокой размерности евклидовы расстояния имеют тенденцию увеличиваться (это один из аспектов так называемого «проклятия размерности»). Применение алгоритма снижения размерности, например анализа главных компонент (PCA), перед кластеризацией k-means может смягчить эту проблему и ускорить вычисления.

../_images/sphx_glr_plot_kmeans_assumptions_002.png

Более подробное описание показанных выше проблем и способов их решения см. в примерах Иллюстрация предположений k-means и Выбор числа кластеров с помощью анализа силуэта при кластеризации KMeans.

K-means часто называют алгоритмом Ллойда. В упрощённом виде алгоритм состоит из трёх шагов. На первом шаге выбираются начальные центроиды; самый простой способ — выбрать \(k\) образцов из набора данных \(X\). После инициализации K-means циклически выполняет два следующих шага. Сначала каждый образец назначается ближайшему центроиду. Затем вычисляются новые центроиды — средние значения всех образцов, назначенных каждому из предыдущих центроидов. Вычисляется разница между старыми и новыми центроидами, и алгоритм повторяет эти два шага, пока это значение не станет меньше порогового. Иными словами, повторение продолжается, пока центроиды не перестанут заметно перемещаться.

../_images/sphx_glr_plot_kmeans_digits_001.png

K-means эквивалентен алгоритму максимизации ожидания с малой диагональной матрицей ковариации, одинаковой для всех компонент.

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

При достаточном времени K-means всегда сойдётся, однако результатом может стать локальный минимум. Это в значительной степени зависит от инициализации центроидов. Поэтому вычисления часто выполняются несколько раз с разными начальными центроидами. Один из способов решить эту проблему — схема инициализации k-means++, реализованная в scikit-learn (используйте параметр init='k-means++'). При такой инициализации центроиды, как правило, располагаются на некотором расстоянии друг от друга, что обычно даёт лучшие результаты, чем случайная инициализация, как показано в источнике. Подробные примеры сравнения различных схем инициализации см. в разделах Демонстрация кластеризации K-Means на наборе данных рукописных цифр и Эмпирическая оценка влияния инициализации k-means.

K-means++ также можно вызвать независимо, чтобы выбрать начальные точки для других алгоритмов кластеризации; подробности и примеры использования см. в описании sklearn.cluster.kmeans_plusplus.

Алгоритм поддерживает веса образцов, задаваемые параметром sample_weight. Это позволяет придавать некоторым образцам больший вес при вычислении центров кластеров и значений инерции. Например, присвоение образцу веса 2 эквивалентно добавлению его дубликата в набор данных \(X\).

Примеры

Кластеризация текстовых документов с помощью k-means: кластеризация документов с помощью KMeans и MiniBatchKMeans на основе разреженных данных
Пример инициализации K-Means++: использование K-means++ для выбора начальных точек для других алгоритмов кластеризации.

2.3.2.1. Низкоуровневый параллелизм

KMeans использует параллелизм на основе OpenMP через Cython. Небольшие блоки данных (256 образцов) обрабатываются параллельно, что также позволяет снизить потребление памяти. Подробнее об управлении числом потоков см. в примечаниях о параллелизме.

Примеры

Иллюстрация предположений k-means: демонстрация случаев, когда k-means работает ожидаемым образом, и случаев, когда это не так
Демонстрация кластеризации K-Means на наборе данных рукописных цифр: кластеризация рукописных цифр

2.3.2.2. Мини-пакетный K-Means

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

Алгоритм циклически выполняет два основных шага, как и обычный k-means. На первом шаге из набора данных случайным образом выбираются \(b\) образцов, образующих мини-пакет. Затем каждый из них назначается ближайшему центроиду. На втором шаге обновляются центроиды. В отличие от k-means, это делается отдельно для каждого образца. Для каждого образца мини-пакета назначенный ему центроид обновляется с помощью потокового среднего этого образца и всех предыдущих образцов, назначенных данному центроиду. В результате скорость изменения центроида со временем уменьшается. Эти шаги выполняются до сходимости или достижения заранее заданного числа итераций.

MiniBatchKMeans сходится быстрее, чем KMeans, однако качество результатов ниже. На практике эта разница в качестве может быть весьма небольшой, как показано в примере и цитируемом источнике.

../_images/sphx_glr_plot_mini_batch_kmeans_001.png

Примеры

Сравнение алгоритмов кластеризации K-Means и MiniBatchKMeans: сравнение KMeans и MiniBatchKMeans
Кластеризация текстовых документов с помощью k-means: кластеризация документов с помощью KMeans и MiniBatchKMeans на основе разреженных данных
Онлайн-обучение словаря частей лиц

2.3.3. Распространение близости

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

../_images/sphx_glr_plot_affinity_propagation_001.png

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

Главный недостаток распространения близости — его вычислительная сложность. Временная сложность алгоритма составляет порядка \(O(N^2 T)\), где \(N\) — число образцов, а \(T\) — число итераций до сходимости. Кроме того, сложность по памяти составляет порядка \(O(N^2)\) при использовании плотной матрицы сходства, но уменьшается при использовании разреженной матрицы сходства. Поэтому распространение близости лучше всего подходит для наборов данных малого и среднего размера.

Описание алгоритма

Сообщения, передаваемые между точками, относятся к одной из двух категорий. Первая — ответственность \(r(i, k)\), то есть накопленное свидетельство того, что образец \(k\) должен быть примером для образца \(i\). Вторая — доступность \(a(i, k)\), то есть накопленное свидетельство того, что образец \(i\) должен выбрать образец \(k\) в качестве своего примера; при этом учитываются значения для всех остальных образцов, для которых \(k\) может быть примером. Таким образом, образцы выбирают примеры, если те (1) достаточно похожи на многие образцы и (2) выбраны многими образцами в качестве их представителей.

Формально ответственность образца \(k\) за то, чтобы быть примером для образца \(i\), задаётся выражением:

\[r(i, k) \leftarrow s(i, k) - max [ a(i, k') + s(i, k') \forall k' \neq k ]\]

Здесь \(s(i, k)\) — сходство между образцами \(i\) и \(k\). Доступность образца \(k\) в качестве примера для образца \(i\) задаётся выражением:

\[a(i, k) \leftarrow min [0, r(k, k) + \sum_{i'~s.t.~i' \notin \{i, k\}}{r(i', k)}]\]

Изначально все значения \(r\) и \(a\) равны нулю, а вычисления повторяются до сходимости. Как упоминалось выше, чтобы избежать численных колебаний при обновлении сообщений, в процесс итераций вводится коэффициент демпфирования \(\lambda\):

\[r_{t+1}(i, k) = \lambda\cdot r_{t}(i, k) + (1-\lambda)\cdot r_{t+1}(i, k)\]

\[a_{t+1}(i, k) = \lambda\cdot a_{t}(i, k) + (1-\lambda)\cdot a_{t+1}(i, k)\]

где \(t\) обозначает номер итерации.

Примеры

Демонстрация алгоритма кластеризации с распространением близости: распространение близости на синтетическом наборе двумерных данных с 3 классами
Визуализация структуры фондового рынка Распространение близости на финансовых временных рядах для поиска групп компаний

2.3.4. Сдвиг среднего

MeanShift кластеризация предназначена для обнаружения областей в гладком распределении плотности образцов. Это алгоритм на основе центроидов, который работает, обновляя кандидатов в центроиды, чтобы они соответствовали среднему значению точек в заданной области. Затем эти кандидаты фильтруются на этапе постобработки, чтобы устранить близкие дубликаты и сформировать итоговый набор центроидов.

Алгоритм автоматически определяет количество кластеров, не полагаясь на параметр bandwidth, который задаёт размер области поиска. Этот параметр можно задать вручную, но его также можно оценить с помощью предоставленной функции estimate_bandwidth, вызываемой, если ширина полосы не задана.

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

Новая выборка получает метку посредством поиска ближайшего центроида.

../_images/sphx_glr_plot_mean_shift_001.png

Примеры

Демонстрация алгоритма кластеризации сдвигом среднего: кластеризация сдвигом среднего на синтетических двумерных наборах данных с 3 классами.

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

SpectralClustering выполняет низкоразмерное вложение матрицы близости между образцами, а затем кластеризацию, например с помощью KMeans, компонент собственных векторов в низкоразмерном пространстве. Этот метод особенно эффективен с вычислительной точки зрения, если матрица близости разрежена и для задачи нахождения собственных значений используется решатель amg (обратите внимание: для решателя amg требуется установленный модуль pyamg).

Текущая версия SpectralClustering требует заранее указать количество кластеров. Метод хорошо работает с небольшим количеством кластеров, но не рекомендуется для большого их числа.

Для двух кластеров SpectralClustering решает выпуклую релаксацию задачи нормализованных разрезов на графе сходства: разделяет граф на две части так, чтобы вес разрезанных рёбер был мал по сравнению с весами рёбер внутри каждого кластера. Этот критерий особенно интересен при работе с изображениями, где вершинами графа являются пиксели, а веса рёбер графа сходства вычисляются с помощью функции от градиента изображения.

Предупреждение

Преобразование расстояний в корректные меры сходства

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

similarity = np.exp(-beta * distance / distance.std())

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

Примеры

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

2.3.5.1. Различные стратегии назначения меток

Можно использовать разные стратегии назначения меток, соответствующие параметру assign_labels объекта SpectralClustering. Стратегия "kmeans" позволяет учитывать более мелкие детали, но может быть нестабильной. В частности, если не контролировать random_state, результаты могут различаться при каждом запуске, поскольку они зависят от случайной инициализации. Альтернативная стратегия "discretize" полностью воспроизводима, но обычно создаёт области довольно равномерной и геометрически правильной формы. Недавно добавленный параметр "cluster_qr" — это детерминированная альтернатива, которая в приведённом ниже примере обычно обеспечивает визуально наилучшее разбиение.

`assign_labels="kmeans"`	`assign_labels="discretize"`	`assign_labels="cluster_qr"`

2.3.5.2. Спектральная кластеризация графов

Спектральную кластеризацию также можно использовать для разбиения графов с помощью их спектральных вложений. В этом случае матрицей близости является матрица смежности графа, а SpectralClustering инициализируется с помощью affinity='precomputed':

>>> from sklearn.cluster import SpectralClustering
>>> sc = SpectralClustering(3, affinity='precomputed', n_init=100,
...                         assign_labels='discretize')
>>> sc.fit_predict(adjacency_matrix)

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

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

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

Ward минимизирует сумму квадратов отклонений внутри всех кластеров. Это подход, минимизирующий дисперсию, и в этом смысле он похож на целевую функцию k-means, но реализуется с помощью агломеративного иерархического подхода.
Максимальная или полная связь минимизирует максимальное расстояние между наблюдениями из пар кластеров.
Средняя связь минимизирует среднее расстояние между всеми наблюдениями из пар кластеров.
Одиночная связь минимизирует расстояние между ближайшими наблюдениями из пар кластеров.

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

2.3.6.1. Различные типы связи: Ward, полная, средняя и одиночная связь

AgglomerativeClustering поддерживает стратегии связи Ward, одиночную, среднюю и полную.

../_images/sphx_glr_plot_linkage_comparison_001.png

Для агломеративной кластеризации характерен эффект «богатые становятся богаче», приводящий к неравномерным размерам кластеров. В этом отношении одиночная связь — худшая стратегия, а Ward обеспечивает наиболее равномерные размеры. Однако при использовании Ward нельзя менять меру близости (или расстояние, используемое при кластеризации), поэтому для неевклидовых метрик хорошей альтернативой является средняя связь. Одиночная связь, хотя и неустойчива к зашумлённым данным, вычисляется очень эффективно и поэтому может быть полезна для иерархической кластеризации больших наборов данных. Одиночная связь также может хорошо работать с неглобулярными данными.

Примеры

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

2.3.6.2. Визуализация иерархии кластеров

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

../_images/sphx_glr_plot_agglomerative_dendrogram_001.png

Примеры

Построение дендрограммы иерархической кластеризации

2.3.6.3. Добавление ограничений связности

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

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

Ограничения связности задаются с помощью матрицы связности: разреженной матрицы scipy, ненулевые элементы которой расположены только на пересечении строк и столбцов с индексами связанных элементов набора данных. Эту матрицу можно построить на основе априорной информации: например, можно кластеризовать веб-страницы, объединяя только те страницы, между которыми есть ссылка. Её также можно построить на основе данных, например с помощью sklearn.neighbors.kneighbors_graph, чтобы ограничить слияние ближайшими соседями, как в этом примере, или с помощью sklearn.feature_extraction.image.grid_to_graph, разрешая объединять только соседние пиксели изображения, как в примере с монетами.

Предупреждение

Ограничения связности при одиночной, средней и полной связи

Ограничения связности в сочетании с одиночной, полной или средней связью могут усиливать эффект «богатые становятся богаче» в агломеративной кластеризации, особенно если они строятся с помощью sklearn.neighbors.kneighbors_graph. При малом количестве кластеров обычно образуется несколько очень крупных кластеров и почти пустые кластеры (см. обсуждение в разделе Иерархическая кластеризация со структурой и без неё). Одиночная связь — наиболее чувствительный к этой проблеме вариант.

../_images/sphx_glr_plot_ward_structured_vs_unstructured_003.png

Примеры

Демонстрация структурированной иерархической кластеризации Ward на изображении монет: кластеризация Ward для разделения изображения монет на области.
Иерархическая кластеризация со структурой и без неё: пример работы алгоритма Ward со швейцарским рулетом, сравнение структурированных и неструктурированных подходов.
Агломерация признаков и отбор отдельных признаков: пример снижения размерности с помощью агломерации признаков на основе иерархической кластеризации Ward.

2.3.6.4. Изменение метрики

Одиночную, среднюю и полную связь можно использовать с различными расстояниями (или мерами близости), в частности с евклидовым расстоянием (l2), расстоянием Манхэттена (или Cityblock, или l1), косинусным расстоянием либо с предварительно вычисленной матрицей близости.

Расстояние l1 часто хорошо подходит для разреженных признаков или разреженного шума, то есть когда многие признаки равны нулю, как при анализе текстов с использованием частот редких слов.
Косинусное расстояние cosine интересно тем, что оно инвариантно относительно глобального масштабирования сигнала.

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

../_images/sphx_glr_plot_agglomerative_clustering_metrics_005.png

../_images/sphx_glr_plot_agglomerative_clustering_metrics_006.png

../_images/sphx_glr_plot_agglomerative_clustering_metrics_007.png

Примеры

Агломеративная кластеризация с различными метриками

2.3.6.5. Бисекция K-Means

Объект BisectingKMeans — это итеративный вариант KMeans, использующий дивизивную иерархическую кластеризацию. Вместо одновременного создания всех центроидов они выбираются последовательно на основе предыдущей кластеризации: кластер повторно разделяется на два новых кластера, пока не будет достигнуто требуемое количество кластеров.

BisectingKMeans эффективнее, чем KMeans, при большом количестве кластеров, поскольку на каждом этапе деления он работает только с подмножеством данных, тогда как KMeans всегда работает со всем набором данных.

Хотя BisectingKMeans по своей конструкции не может использовать преимущества инициализации "k-means++", он всё же обеспечивает результаты по инерции, сопоставимые с KMeans(init="k-means++"), при меньших вычислительных затратах и, вероятно, даёт лучшие результаты, чем KMeans со случайной инициализацией.

Этот вариант эффективнее агломеративной кластеризации, если количество кластеров невелико по сравнению с количеством точек данных.

Кроме того, этот вариант не создаёт пустых кластеров.

Существуют две стратегии выбора кластера для разделения:

bisecting_strategy="largest_cluster" выбирает кластер с наибольшим количеством точек
bisecting_strategy="biggest_inertia" выбирает кластер с наибольшей инерцией (кластер с наибольшей суммой квадратов ошибок внутри)

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

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

Различия между Bisecting K-Means и обычным K-Means можно увидеть в примере Сравнение производительности Bisecting K-Means и обычного K-Means. Обычный алгоритм K-Means обычно создаёт несвязанные кластеры, тогда как кластеры Bisecting K-Means упорядочены и образуют хорошо заметную иерархию.

2.3.7. DBSCAN

Алгоритм DBSCAN рассматривает кластеры как области высокой плотности, разделённые областями низкой плотности. Благодаря такому довольно общему подходу кластеры, обнаруженные DBSCAN, могут иметь любую форму, в отличие от k-means, который предполагает, что кластеры имеют выпуклую форму. Центральным понятием DBSCAN являются опорные точки — точки, находящиеся в областях высокой плотности. Таким образом, кластер представляет собой набор опорных точек, каждая из которых находится близко к другим (расстояние измеряется некоторой метрикой), и набор неопорных точек, расположенных близко к опорной точке (но сами опорными точками не являющихся). Алгоритм имеет два параметра, min_samples и eps, которые формально определяют, что мы подразумеваем под плотной областью. Более высокое значение min_samples или более низкое значение eps указывают на то, что для формирования кластера необходима более высокая плотность.

Если говорить более формально, опорной точкой считается точка набора данных, для которой в пределах расстояния eps существует не менее min_samples других точек; они называются соседями этой опорной точки. Это означает, что опорная точка находится в плотной области векторного пространства. Кластер — это набор опорных точек, который можно построить рекурсивно: взять опорную точку, найти всех её соседей, которые являются опорными точками, найти всех их соседей, которые являются опорными точками, и так далее. В кластер также входит набор неопорных точек — точек, которые являются соседями опорной точки кластера, но сами не являются опорными точками. Интуитивно такие точки находятся на периферии кластера.

По определению любая опорная точка является частью кластера. Любая точка, которая не является опорной и находится на расстоянии не менее eps от любой опорной точки, считается алгоритмом выбросом.

Параметр min_samples в первую очередь определяет, насколько алгоритм устойчив к шуму (для зашумлённых и больших наборов данных может быть желательно увеличить этот параметр), тогда как параметр eps крайне важно выбрать подходящим образом для набора данных и функции расстояния; обычно его нельзя оставлять равным значению по умолчанию. Он определяет локальную окрестность точек. Если выбрать слишком малое значение, большая часть данных вообще не будет кластеризована (и будет помечена как -1 — «шум»). Если выбрать слишком большое значение, близкие кластеры сольются в один, а в конечном итоге весь набор данных будет возвращён как единый кластер. В литературе обсуждались некоторые эвристики выбора этого параметра, например основанные на точке перегиба графика расстояний до ближайших соседей (см. обсуждение в приведённых ниже источниках).

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

Примеры

Демонстрация алгоритма кластеризации DBSCAN

2.3.8. HDBSCAN

Алгоритм HDBSCAN можно рассматривать как расширение DBSCAN и OPTICS. В частности, DBSCAN предполагает, что критерий кластеризации (то есть требование к плотности) однороден во всём пространстве. Иными словами, DBSCAN может испытывать трудности при обнаружении кластеров с разной плотностью. HDBSCAN снимает это ограничение и исследует все возможные уровни плотности, строя альтернативное представление задачи кластеризации.

Примечание

Эта реализация основана на оригинальной реализации HDBSCAN из scikit-learn-contrib/hdbscan, созданной на основе [LJ2017].

Примеры

Демонстрация алгоритма кластеризации HDBSCAN

2.3.8.1. Граф взаимной достижимости

Сначала HDBSCAN определяет \(d_c(x_p)\) — основное расстояние точки выборки \(x_p\) как расстояние до её min_samples-го ближайшего соседа, включая саму точку. Например, если min_samples=5 и \(x_*\) — 5-й ближайший сосед \(x_p\), то основное расстояние равно:

\[d_c(x_p)=d(x_p, x_*).\]

Затем определяется \(d_m(x_p, x_q)\) — расстояние взаимной достижимости двух точек \(x_p, x_q\):

\[d_m(x_p, x_q) = \max\{d_c(x_p), d_c(x_q), d(x_p, x_q)\}\]

Эти два понятия позволяют построить граф взаимной достижимости \(G_{ms}\), определённый для фиксированного значения min_samples: каждой точке выборки \(x_p\) сопоставляется вершина графа, а рёбра между точками \(x_p, x_q\) имеют вес, равный расстоянию взаимной достижимости \(d_m(x_p, x_q)\) между ними. Можно построить подграфы этого графа, обозначаемые \(G_{ms,\varepsilon}\), удалив все рёбра со значением больше \(\varepsilon\): из исходного графа. На этом этапе точки, основное расстояние которых меньше \(\varepsilon\): помечаются как шум. Оставшиеся точки кластеризуются путём нахождения компонент связности полученного графа.

Примечание

Нахождение компонент связности усечённого графа \(G_{ms,\varepsilon}\) эквивалентно запуску DBSCAN* с параметрами min_samples и \(\varepsilon\). DBSCAN* — это слегка модифицированная версия DBSCAN, упомянутая в [CM2013].

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

HDBSCAN можно рассматривать как алгоритм, выполняющий кластеризацию DBSCAN* для всех значений \(\varepsilon\). Как отмечалось выше, это эквивалентно нахождению компонент связности графов взаимной достижимости для всех значений \(\varepsilon\). Для эффективного выполнения этой операции HDBSCAN сначала извлекает минимальное остовное дерево (MST) из полностью связного графа взаимной достижимости, а затем жадно удаляет рёбра с наибольшими весами. Алгоритм HDBSCAN в общих чертах выглядит следующим образом:

Извлечь MST графа \(G_{ms}\).
Расширить MST, добавив для каждой вершины «петлю» с весом, равным основному расстоянию соответствующей точки выборки.
Инициализировать для MST один кластер и одну метку.
Удалить из MST ребро с наибольшим весом (рёбра с одинаковым весом удаляются одновременно).
Назначить метки кластеров компонентам связности, содержащим концы удалённого ребра. Если в компоненте нет хотя бы одного ребра, вместо этого ей назначается метка «null», обозначающая шум.
Повторять шаги 4–5, пока не останется компонент связности.

Таким образом, HDBSCAN позволяет иерархически получить все возможные разбиения, которые можно получить с помощью DBSCAN* для фиксированного значения min_samples. Это позволяет HDBSCAN выполнять кластеризацию при разных уровнях плотности, поэтому задавать \(\varepsilon\) как гиперпараметр больше не требуется. Вместо этого используется только значение min_samples, которое, как правило, является более устойчивым гиперпараметром.

HDBSCAN можно сгладить с помощью дополнительного гиперпараметра min_cluster_size, который задаёт, что во время иерархической кластеризации компоненты, содержащие менее minimum_cluster_size точек, считаются шумом. На практике можно задать minimum_cluster_size = min_samples, чтобы связать параметры и упростить пространство гиперпараметров.

Литература

[CM2013]

Campello, R.J.G.B., Moulavi, D., Sander, J. (2013). Кластеризация на основе плотности с использованием иерархических оценок плотности. В: Pei, J., Tseng, V.S., Cao, L., Motoda, H., Xu, G. (ред.) Advances in Knowledge Discovery and Data Mining. PAKDD 2013. Lecture Notes in Computer Science(), т. 7819. Springer, Берлин, Гейдельберг. Кластеризация на основе плотности с использованием иерархических оценок плотности

[LJ2017]

L. McInnes и J. Healy, (2017). Ускоренная иерархическая кластеризация на основе плотности. В: IEEE International Conference on Data Mining Workshops (ICDMW), 2017, с. 33–42. Ускоренная иерархическая кластеризация на основе плотности

2.3.9. OPTICS

Алгоритм OPTICS во многом похож на алгоритм DBSCAN и может рассматриваться как обобщение DBSCAN, в котором требование eps заменено с одного значения на диапазон значений. Ключевое различие между DBSCAN и OPTICS состоит в том, что алгоритм OPTICS строит граф достижимости, который присваивает каждой точке как расстояние reachability_, так и позицию в кластере — атрибут ordering_; эти два атрибута назначаются при обучении модели и используются для определения принадлежности к кластеру. Если OPTICS запустить со значением inf по умолчанию для max_eps, извлечение кластеров в стиле DBSCAN можно многократно выполнять за линейное время для любого заданного значения eps с помощью метода cluster_optics_dbscan. Установка меньшего значения max_eps сокращает время выполнения; его можно рассматривать как максимальный радиус окрестности каждой точки для поиска других потенциально достижимых точек.

Расстояния достижимости, вычисляемые OPTICS, позволяют выделять кластеры с переменной плотностью в пределах одного набора данных. Как показано на графике выше, сочетание расстояний достижимости и ordering_ набора данных даёт график достижимости, на котором плотность точек представлена по оси Y, а точки упорядочены так, что близкие точки расположены рядом. «Срез» графика достижимости на одном уровне даёт результаты, похожие на DBSCAN: все точки выше «среза» классифицируются как шум, а каждый разрыв при чтении слева направо обозначает новый кластер. При извлечении кластеров OPTICS по умолчанию анализирует крутые склоны графика, чтобы найти кластеры; пользователь может задать, что считать крутым склоном, с помощью параметра xi. Возможны и другие способы анализа самого графика, например построение иерархического представления данных с помощью дендрограмм графика достижимости; иерархию кластеров, обнаруженных алгоритмом, можно получить через параметр cluster_hierarchy_. На графике выше цвета выбраны так, чтобы цвета кластеров в плоскости совпадали с цветами линейных сегментов кластеров на графике достижимости. Обратите внимание, что синий и красный кластеры соседствуют на графике достижимости и могут быть представлены иерархически как дочерние кластеры более крупного родительского кластера.

Примеры

Демонстрация алгоритма кластеризации OPTICS

2.3.10. BIRCH

Birch строит для заданных данных дерево, называемое деревом признаков кластеризации (Clustering Feature Tree, CFT). Данные по сути с потерями сжимаются до набора узлов признаков кластеризации (узлов CF). Узлы CF содержат несколько подкластеров, называемых подкластерами признаков кластеризации (подкластерами CF), а эти подкластеры CF, расположенные в нетерминальных узлах CF, могут иметь дочерние узлы CF.

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

Количество образцов в подкластере.
Линейная сумма — n-мерный вектор, содержащий сумму всех образцов.
Сумма квадратов — сумма квадратов L2-норм всех образцов.
Центроиды — для того, чтобы избежать повторного вычисления линейной суммы / n_samples.
Квадрат нормы центроидов.

У алгоритма BIRCH два параметра: порог и коэффициент ветвления. Коэффициент ветвления ограничивает число подкластеров в узле, а порог ограничивает расстояние между поступающим образцом и существующими подкластерами.

Этот алгоритм можно рассматривать как разновидность метода сокращения объёма данных, поскольку он сокращает входные данные до набора подкластеров, получаемых непосредственно из листьев CFT. Затем эти сокращённые данные можно обработать, передав их глобальному алгоритму кластеризации. Глобальный алгоритм кластеризации можно задать с помощью n_clusters. Если n_clusters имеет значение None, подкластеры считываются непосредственно из листьев; в противном случае глобальный этап кластеризации присваивает этим подкластерам метки глобальных кластеров, а образцы сопоставляются с меткой глобального кластера ближайшего подкластера.

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

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

2.3.11.1. Индекс Рэнда

Если известны истинные назначения классов labels_true и назначения, полученные нашим алгоритмом кластеризации для тех же образцов labels_pred, (скорректированный или нескорректированный) индекс Рэнда — это функция, которая измеряет сходство двух назначений, не учитывая перестановки:

>>> from sklearn import metrics
>>> labels_true = [0, 0, 0, 1, 1, 1]
>>> labels_pred = [0, 0, 1, 1, 2, 2]
>>> metrics.rand_score(labels_true, labels_pred)
0.66

Индекс Рэнда не гарантирует, что при случайной разметке будет получено значение, близкое к 0.0. Скорректированный индекс Рэнда учитывает случайность и задаёт такую базовую оценку.

>>> metrics.adjusted_rand_score(labels_true, labels_pred)
0.24

Как и для всех метрик кластеризации, можно поменять местами 0 и 1 в предсказанных метках, переименовать 2 в 3 и получить ту же оценку:

>>> labels_pred = [1, 1, 0, 0, 3, 3]
>>> metrics.rand_score(labels_true, labels_pred)
0.66
>>> metrics.adjusted_rand_score(labels_true, labels_pred)
0.24

Кроме того, и rand_score, и adjusted_rand_score симметричны: перестановка аргументов не меняет оценки. Поэтому их можно использовать как меры согласованности:

>>> metrics.rand_score(labels_pred, labels_true)
0.66
>>> metrics.adjusted_rand_score(labels_pred, labels_true)
0.24

Идеальная разметка получает оценку 1.0:

>>> labels_pred = labels_true[:]
>>> metrics.rand_score(labels_true, labels_pred)
1.0
>>> metrics.adjusted_rand_score(labels_true, labels_pred)
1.0

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

>>> labels_true = [0, 0, 0, 0, 0, 0, 1, 1]
>>> labels_pred = [0, 1, 2, 3, 4, 5, 5, 6]
>>> metrics.rand_score(labels_true, labels_pred)
0.39
>>> metrics.adjusted_rand_score(labels_true, labels_pred)
-0.072

Преимущества:

Интерпретируемость: нескорректированный индекс Рэнда пропорционален количеству пар образцов, метки которых совпадают в labels_pred и labels_true либо различаются в обоих случаях.
Для случайных (равномерных) назначений меток оценка скорректированного индекса Рэнда близка к 0.0 при любых значениях n_clusters и n_samples (в отличие, например, от нескорректированного индекса Рэнда или V-меры).
Ограниченный диапазон: низкие значения указывают на различие разметок, сходные кластеризации имеют высокий (скорректированный или нескорректированный) индекс Рэнда, а 1.0 соответствует идеальному совпадению. Диапазон оценок составляет [0, 1] для нескорректированного индекса Рэнда и [-0.5, 1] для скорректированного индекса Рэнда.
Предположений о структуре кластеров не делается: (скорректированный или нескорректированный) индекс Рэнда можно использовать для сравнения любых алгоритмов кластеризации, например алгоритма k-средних, предполагающего изотропную форму кластеров-комков, с результатами спектральной кластеризации, способной находить кластеры «складчатой» формы.

Недостатки:

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

Однако (скорректированный или нескорректированный) индекс Рэнда может быть полезен и в полностью неконтролируемом сценарии как строительный блок для индекса согласованности, который можно использовать при выборе модели кластеризации (TODO).
Нескорректированный индекс Рэнда часто близок к 1.0, даже если сами кластеризации существенно различаются. Это можно понять, интерпретируя индекс Рэнда как точность разметки пар элементов, полученной в результате кластеризации: на практике часто большинство пар элементов получают метку пары different и в предсказанной, и в истинной кластеризации. В результате доля совпадающих меток пар высока, что приводит к высокой оценке.

Примеры

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

2.3.11.2. Оценки на основе взаимной информации

Если известны истинные назначения классов labels_true и назначения, полученные нашим алгоритмом кластеризации для тех же образцов labels_pred, взаимная информация — это функция, которая измеряет согласие двух назначений, не учитывая перестановки. Доступны две нормализованные версии этой меры: нормализованная взаимная информация (NMI) и скорректированная взаимная информация (AMI). NMI часто используется в литературе, тогда как AMI была предложена позднее и нормализована с учётом случайности:

>>> from sklearn import metrics
>>> labels_true = [0, 0, 0, 1, 1, 1]
>>> labels_pred = [0, 0, 1, 1, 2, 2]

>>> metrics.adjusted_mutual_info_score(labels_true, labels_pred)
0.22504

Можно поменять местами 0 и 1 в предсказанных метках, переименовать 2 в 3 и получить ту же оценку:

>>> labels_pred = [1, 1, 0, 0, 3, 3]
>>> metrics.adjusted_mutual_info_score(labels_true, labels_pred)
0.22504

Все три меры — mutual_info_score, adjusted_mutual_info_score и normalized_mutual_info_score — симметричны: перестановка аргументов не меняет оценку. Поэтому их можно использовать как меры согласованности:

>>> metrics.adjusted_mutual_info_score(labels_pred, labels_true)
0.22504

Идеальная разметка получает оценку 1.0:

>>> labels_pred = labels_true[:]
>>> metrics.adjusted_mutual_info_score(labels_true, labels_pred)
1.0

>>> metrics.normalized_mutual_info_score(labels_true, labels_pred)
1.0

Для mutual_info_score это неверно, поэтому её сложнее интерпретировать:

>>> metrics.mutual_info_score(labels_true, labels_pred)
0.69

Плохие разметки (например, независимые) дают неположительные оценки:

>>> labels_true = [0, 1, 2, 0, 3, 4, 5, 1]
>>> labels_pred = [1, 1, 0, 0, 2, 2, 2, 2]
>>> metrics.adjusted_mutual_info_score(labels_true, labels_pred)
-0.10526

Преимущества:

Для случайных (равномерных) назначений меток оценка AMI близка к 0.0 при любых значениях n_clusters и n_samples (в отличие, например, от исходной взаимной информации или V-меры).
Верхняя граница равна 1: значения, близкие к нулю, указывают на то, что два назначения меток в значительной степени независимы, а значения, близкие к единице, — на существенное согласие. Кроме того, AMI, в точности равная 1, означает, что два назначения меток совпадают (с перестановкой или без неё).

Недостатки:

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

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

Примеры

Коррекция на случайность при оценке качества кластеризации: анализ влияния размера набора данных на значения метрик кластеризации для случайных назначений. Этот пример также включает скорректированный индекс Рэнда.

Математическая формулировка

Пусть заданы два назначения меток (для одних и тех же N объектов), \(U\) и \(V\). Их энтропия — это мера неопределённости разбиения, определяемая следующим образом:

\[H(U) = - \sum_{i=1}^{|U|}P(i)\log(P(i))\]

где \(P(i) = |U_i| / N\) — вероятность того, что случайно выбранный объект из \(U\) попадёт в класс \(U_i\). Аналогично для \(V\):

\[H(V) = - \sum_{j=1}^{|V|}P'(j)\log(P'(j))\]

где \(P'(j) = |V_j| / N\). Взаимная информация (MI) между \(U\) и \(V\) вычисляется по формуле:

\[\text{MI}(U, V) = \sum_{i=1}^{|U|}\sum_{j=1}^{|V|}P(i, j)\log\left(\frac{P(i,j)}{P(i)P'(j)}\right)\]

где \(P(i, j) = |U_i \cap V_j| / N\) — вероятность того, что случайно выбранный объект попадёт одновременно в оба класса \(U_i\) и \(V_j\).

Её также можно выразить через мощности множеств:

\[\text{MI}(U, V) = \sum_{i=1}^{|U|} \sum_{j=1}^{|V|} \frac{|U_i \cap V_j|}{N}\log\left(\frac{N|U_i \cap V_j|}{|U_i||V_j|}\right)\]

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

\[\text{NMI}(U, V) = \frac{\text{MI}(U, V)}{\text{mean}(H(U), H(V))}\]

Это значение взаимной информации, как и нормализованный вариант, не скорректировано с учётом случайности и будет возрастать с увеличением количества различных меток (кластеров) независимо от фактической величины «взаимной информации» между назначениями меток.

Ожидаемое значение взаимной информации можно вычислить с помощью следующего уравнения [VEB2009]. В этом уравнении \(a_i = |U_i|\) (количество элементов в \(U_i\)), а \(b_j = |V_j|\) (количество элементов в \(V_j\)).

\[E[\text{MI}(U,V)]=\sum_{i=1}^{|U|} \sum_{j=1}^{|V|} \sum_{n_{ij}=(a_i+b_j-N)^+ }^{\min(a_i, b_j)} \frac{n_{ij}}{N}\log \left( \frac{ N.n_{ij}}{a_i b_j}\right) \frac{a_i!b_j!(N-a_i)!(N-b_j)!}{N!n_{ij}!(a_i-n_{ij})!(b_j-n_{ij})! (N-a_i-b_j+n_{ij})!}\]

Используя ожидаемое значение, скорректированную взаимную информацию можно вычислить по формуле, аналогичной формуле скорректированного индекса Рэнда:

\[\text{AMI} = \frac{\text{MI} - E[\text{MI}]}{\text{mean}(H(U), H(V)) - E[\text{MI}]}\]

Для нормализованной и скорректированной взаимной информации в качестве нормирующего значения обычно используется некоторое обобщённое среднее энтропий каждой кластеризации. Существует несколько обобщённых средних, и строгих правил выбора одного из них нет. Выбор во многом зависит от конкретной области; например, в обнаружении сообществ чаще всего используется среднее арифметическое. Различные методы нормализации дают «качественно сходные результаты» [YAT2016]. В нашей реализации этот выбор задаётся параметром average_method.

Vinh и др. (2010) назвали варианты NMI и AMI в соответствии с методом усреднения [VEB2010]. Их варианты ‘sqrt’ и ‘sum’ соответствуют среднему геометрическому и среднему арифметическому; мы используем более распространённые названия этих средних.

Ссылки

Strehl, Alexander и Joydeep Ghosh (2002). «Ансамбли кластеров — структура для повторного использования знаний при объединении нескольких разбиений». Journal of Machine Learning Research 3: 583-617. doi:10.1162/153244303321897735.
Статья о (нормализованной) взаимной информации в Википедии
Статья о скорректированной взаимной информации в Википедии

[VEB2009]

Vinh, Epps и Bailey (2009). «Информационно-теоретические меры для сравнения кластеризаций». Материалы 26-й ежегодной международной конференции по машинному обучению — ICML ‘09. doi:10.1145/1553374.1553511. ISBN 9781605585161.

[VEB2010]

Vinh, Epps и Bailey (2010). «Информационно-теоретические меры для сравнения кластеризаций: варианты, свойства, нормализация и коррекция на случайность». JMLR <https://jmlr.csail.mit.edu/papers/volume11/vinh10a/vinh10a.pdf>

[YAT2016]

Yang, Algesheimer и Tessone (2016). «Сравнительный анализ алгоритмов обнаружения сообществ в искусственных сетях». Scientific Reports 6: 30750. doi:10.1038/srep30750.

2.3.11.3. Однородность, полнота и V-мера

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

В частности, Rosenberg и Hirschberg (2007) определяют следующие два желательных свойства любого назначения кластеров:

однородность: каждый кластер содержит объекты только одного класса.
полнота: все объекты заданного класса назначены одному и тому же кластеру.

Эти понятия можно представить в виде оценок homogeneity_score и completeness_score. Обе оценки находятся в диапазоне от 0.0 до 1.0 (чем выше, тем лучше):

>>> from sklearn import metrics
>>> labels_true = [0, 0, 0, 1, 1, 1]
>>> labels_pred = [0, 0, 1, 1, 2, 2]

>>> metrics.homogeneity_score(labels_true, labels_pred)
0.66

>>> metrics.completeness_score(labels_true, labels_pred)
0.42

Их среднее гармоническое, называемое V-мерой, вычисляется функцией v_measure_score:

>>> metrics.v_measure_score(labels_true, labels_pred)
0.516

Формула этой функции имеет следующий вид:

\[v = \frac{(1 + \beta) \times \text{homogeneity} \times \text{completeness}}{(\beta \times \text{homogeneity} + \text{completeness})}\]

По умолчанию beta равно 1.0. Если использовать значение beta меньше 1:

>>> metrics.v_measure_score(labels_true, labels_pred, beta=0.6)
0.547

больший вес будет придаваться однородности, а если использовать значение больше 1:

>>> metrics.v_measure_score(labels_true, labels_pred, beta=1.8)
0.48

больший вес будет придаваться полноте.

V-мера фактически эквивалентна рассмотренной выше взаимной информации (NMI), если в качестве функции агрегирования используется среднее арифметическое [B2011].

Однородность, полноту и V-меру можно вычислить одновременно с помощью homogeneity_completeness_v_measure следующим образом:

>>> metrics.homogeneity_completeness_v_measure(labels_true, labels_pred)
(0.67, 0.42, 0.52)

Следующее назначение кластеров немного лучше, поскольку оно однородно, но не является полным:

>>> labels_pred = [0, 0, 0, 1, 2, 2]
>>> metrics.homogeneity_completeness_v_measure(labels_true, labels_pred)
(1.0, 0.68, 0.81)

Примечание

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

Это не относится к completeness_score и homogeneity_score: обе связаны следующим соотношением:

homogeneity_score(a, b) == completeness_score(b, a)

Преимущества:

Ограниченный диапазон оценок: 0.0 — наихудшая возможная оценка, 1.0 — идеальная.
Интуитивная интерпретация: кластеризацию с низкой V-мерой можно качественно проанализировать с точки зрения однородности и полноты, чтобы лучше понять, какого «типа» ошибки допущены при назначении.
Предположений о структуре кластеров не делается: можно сравнивать алгоритмы кластеризации, например алгоритм k-средних, предполагающий изотропную форму кластеров-комков, с результатами спектральной кластеризации, способной находить кластеры «складчатой» формы.

Недостатки:

Ранее рассмотренные метрики не нормализованы относительно случайной разметки: это означает, что в зависимости от количества образцов, кластеров и истинных классов полностью случайная разметка не всегда будет давать одинаковые значения однородности, полноты и, следовательно, V-меры. В частности, случайная разметка не даст нулевых оценок, особенно если кластеров много.

Этой проблемой можно пренебречь, если количество образцов превышает тысячу, а количество кластеров меньше 10. Для небольших наборов образцов или большого количества кластеров безопаснее использовать скорректированный индекс, например скорректированный индекс Рэнда (ARI).

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

Примеры

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

Ссылки

V-мера: внешняя метрика оценки кластеризации на основе условной энтропии Andrew Rosenberg и Julia Hirschberg, 2007

[B2011]

Идентификация и характеристика событий в социальных сетях, Hila Becker, докторская диссертация.

2.3.11.4. Оценки Фоулкса — Мэллоуза

Исходный индекс Фоулкса — Мэллоуза (FMI) предназначался для измерения сходства между двумя результатами кластеризации, что по своей сути является сравнением без учителя. Адаптацию индекса Фоулкса — Мэллоуза для обучения с учителем (реализованную в sklearn.metrics.fowlkes_mallows_score) можно использовать, если известны истинные метки классов образцов. FMI определяется как среднее геометрическое точности и полноты попарного сравнения:

\[\text{FMI} = \frac{\text{TP}}{\sqrt{(\text{TP} + \text{FP}) (\text{TP} + \text{FN})}}\]

В приведённой выше формуле:

TP (Истинно положительные): количество пар точек, сгруппированных вместе как в истинных метках, так и в предсказанных.
FP (Ложно положительные): количество пар точек, сгруппированных вместе в предсказанных метках, но не в истинных.
FN (Ложно отрицательные): количество пар точек, сгруппированных вместе в истинных метках, но не в предсказанных.

Оценка принимает значения от 0 до 1. Высокое значение указывает на хорошее сходство двух кластеризаций.

>>> from sklearn import metrics
>>> labels_true = [0, 0, 0, 1, 1, 1]
>>> labels_pred = [0, 0, 1, 1, 2, 2]

>>> metrics.fowlkes_mallows_score(labels_true, labels_pred)
0.47140

Можно поменять местами 0 и 1 в предсказанных метках, переименовать 2 в 3 и получить ту же оценку:

>>> labels_pred = [1, 1, 0, 0, 3, 3]

>>> metrics.fowlkes_mallows_score(labels_true, labels_pred)
0.47140

Идеальная разметка получает оценку 1.0:

>>> labels_pred = labels_true[:]
>>> metrics.fowlkes_mallows_score(labels_true, labels_pred)
1.0

Плохая разметка (например, независимая) получает нулевую оценку:

>>> labels_true = [0, 1, 2, 0, 3, 4, 5, 1]
>>> labels_pred = [1, 1, 0, 0, 2, 2, 2, 2]
>>> metrics.fowlkes_mallows_score(labels_true, labels_pred)
0.0

Преимущества:

При случайном (равномерном) распределении меток оценка FMI близка к 0.0 при любых значениях n_clusters и n_samples (в отличие, например, от обычной взаимной информации или V-меры).
Оценка ограничена сверху значением 1: значения, близкие к нулю, указывают на то, что два распределения меток в значительной степени независимы, а значения, близкие к единице, — на существенное совпадение. Кроме того, значение, равное ровно 0, указывает на полную независимость распределений меток, а FMI, равный ровно 1, означает, что два распределения меток совпадают (с перестановкой или без неё).
Предположения о структуре кластеров не требуются: оценку можно использовать для сравнения алгоритмов кластеризации, таких как k-средних, предполагающий изотропную форму кластеров, с результатами алгоритмов спектральной кластеризации, способных находить кластеры «складчатой» формы.

2.3.11.5. Коэффициент силуэта

Если истинные метки неизвестны, оценку необходимо выполнять с использованием самой модели. Коэффициент силуэта (sklearn.metrics.silhouette_score) — пример такой оценки: более высокий коэффициент силуэта соответствует модели с более чётко определёнными кластерами. Коэффициент силуэта определяется для каждого образца и состоит из двух величин:

a: среднее расстояние между образцом и всеми остальными точками того же класса.
b: среднее расстояние между образцом и всеми остальными точками следующего ближайшего кластера.

Коэффициент силуэта s для отдельного образца определяется следующим образом:

\[s = \frac{b - a}{max(a, b)}\]

Коэффициент силуэта для набора образцов вычисляется как среднее значение коэффициентов силуэта для каждого образца.

>>> from sklearn import metrics
>>> from sklearn.metrics import pairwise_distances
>>> from sklearn import datasets
>>> X, y = datasets.load_iris(return_X_y=True)

Обычно коэффициент силуэта применяют к результатам кластерного анализа.

>>> import numpy as np
>>> from sklearn.cluster import KMeans
>>> kmeans_model = KMeans(n_clusters=3, random_state=1).fit(X)
>>> labels = kmeans_model.labels_
>>> metrics.silhouette_score(X, labels, metric='euclidean')
0.55

Примеры

Выбор числа кластеров с помощью анализа силуэтов при кластеризации методом K-средних : В этом примере анализ силуэтов используется для выбора оптимального значения n_clusters.

2.3.11.6. Индекс Калинского — Харабаша

Если истинные метки неизвестны, для оценки модели можно использовать индекс Калинского — Харабаша (sklearn.metrics.calinski_harabasz_score), также известный как критерий отношения дисперсий. Более высокая оценка Калинского — Харабаша соответствует модели с более чётко определёнными кластерами.

Индекс представляет собой отношение суммы межкластерного разброса к внутрикластерному разбросу для всех кластеров (разброс определяется как сумма квадратов расстояний):

>>> from sklearn import metrics
>>> from sklearn.metrics import pairwise_distances
>>> from sklearn import datasets
>>> X, y = datasets.load_iris(return_X_y=True)

Обычно индекс Калинского — Харабаша применяют к результатам кластерного анализа:

>>> import numpy as np
>>> from sklearn.cluster import KMeans
>>> kmeans_model = KMeans(n_clusters=3, random_state=1).fit(X)
>>> labels = kmeans_model.labels_
>>> metrics.calinski_harabasz_score(X, labels)
561.59

2.3.11.7. Индекс Дэвиса — Болдина

Если истинные метки неизвестны, для оценки модели можно использовать индекс Дэвиса — Болдина (sklearn.metrics.davies_bouldin_score): более низкий индекс Дэвиса — Болдина соответствует модели с лучшим разделением кластеров.

Этот индекс отражает среднее «сходство» между кластерами; сходство является мерой, сопоставляющей расстояние между кластерами с размером самих кластеров.

Ноль — минимально возможная оценка. Значения, близкие к нулю, указывают на лучшее разбиение.

Обычно индекс Дэвиса — Болдина применяют к результатам кластерного анализа следующим образом:

>>> from sklearn import datasets
>>> iris = datasets.load_iris()
>>> X = iris.data
>>> from sklearn.cluster import KMeans
>>> from sklearn.metrics import davies_bouldin_score
>>> kmeans = KMeans(n_clusters=3, random_state=1).fit(X)
>>> labels = kmeans.labels_
>>> davies_bouldin_score(X, labels)
0.666

2.3.11.8. Матрица сопряжённости

Матрица сопряжённости (sklearn.metrics.cluster.contingency_matrix) показывает мощность пересечения для каждой пары истинного и предсказанного кластеров. Матрица сопряжённости содержит достаточную статистику для всех метрик кластеризации в случаях, когда образцы являются независимыми и одинаково распределёнными, и нет необходимости учитывать экземпляры, не отнесённые ни к одному кластеру.

Пример:

>>> from sklearn.metrics.cluster import contingency_matrix
>>> x = ["a", "a", "a", "b", "b", "b"]
>>> y = [0, 0, 1, 1, 2, 2]
>>> contingency_matrix(x, y)
array([[2, 1, 0],
       [0, 1, 2]])

Первая строка выходного массива указывает, что есть три образца, истинный кластер которых — «a». Из них два относятся к предсказанному кластеру 0, один — к кластеру 1, а ни один — к кластеру 2. Вторая строка указывает, что есть три образца, истинный кластер которых — «b». Из них ни один не относится к предсказанному кластеру 0, один относится к кластеру 1, а два — к кластеру 2.

Матрица ошибок для задачи классификации — это квадратная матрица сопряжённости, в которой порядок строк и столбцов соответствует списку классов.

2.3.11.9. Матрица ошибок для пар

Матрица ошибок для пар (sklearn.metrics.cluster.pair_confusion_matrix) — это матрица сходства 2x2

\[\begin{split}C = \left[\begin{matrix} C_{00} & C_{01} \\ C_{10} & C_{11} \end{matrix}\right]\end{split}\]

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

Она содержит следующие элементы:

\(C_{00}\) : количество пар, в которых образцы не сгруппированы вместе ни в одной из кластеризаций

\(C_{10}\) : количество пар, в которых образцы сгруппированы вместе в кластеризации по истинным меткам, но не сгруппированы вместе в другой кластеризации

\(C_{01}\) : количество пар, в которых образцы не сгруппированы вместе в кластеризации по истинным меткам, но сгруппированы вместе в другой кластеризации

\(C_{11}\) : количество пар, в которых образцы сгруппированы вместе в обеих кластеризациях

Если считать пару образцов, сгруппированных вместе, положительной парой, то, как и в бинарной классификации, количество истинно отрицательных пар равно \(C_{00}\), ложно отрицательных — \(C_{10}\), истинно положительных — \(C_{11}\), а ложно положительных — \(C_{01}\).

При полном совпадении разметок все ненулевые элементы находятся на диагонали, независимо от фактических значений меток:

>>> from sklearn.metrics.cluster import pair_confusion_matrix
>>> pair_confusion_matrix([0, 0, 1, 1], [0, 0, 1, 1])
array([[8, 0],
       [0, 4]])

>>> pair_confusion_matrix([0, 0, 1, 1], [1, 1, 0, 0])
array([[8, 0],
       [0, 4]])

Разметка, при которой все образцы классов отнесены к одним и тем же кластерам, является полной, но не всегда чистой, поэтому получает штраф; у такой матрицы есть ненулевые внедиагональные элементы:

>>> pair_confusion_matrix([0, 0, 1, 2], [0, 0, 1, 1])
array([[8, 2],
       [0, 2]])

Матрица не является симметричной:

>>> pair_confusion_matrix([0, 0, 1, 1], [0, 0, 1, 2])
array([[8, 0],
       [2, 2]])

Если образцы классов полностью распределены по разным кластерам, разбиение совершенно неполное, поэтому все диагональные элементы матрицы равны нулю:

>>> pair_confusion_matrix([0, 0, 0, 0], [0, 1, 2, 3])
array([[ 0,  0],
       [12,  0]])

© 2007–2026 The scikit-learn developers
Licensed under the 3-clause BSD License.
https://scikit-learn.org/1.9/modules/clustering.html