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

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

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

2.3.1. Методы кластеризации (Aлгоритмы кластеризации)

../_images/sphx_glr_plot_cluster_comparison_001.png

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

Название метода

Параметры

Масштабируемость

Вариант использования

Геометрия (используемая метрика)

K-Means

количество кластеров

Очень большой n_samples, средний n_clusters с MiniBatch code

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

Дистанции между точек

Affinity propagation

демпфирование, предпочтение выборки

Не масштабируется с помощью n_samples

Множество кластеров, неравномерный размер кластеров, неплоская геометрия, индуктивный.

Расстояние до графа (например, граф ближайших соседей)

Mean-shift

Пропускная способность

Не масштабируется с помощью n_samples

Множество кластеров, неравномерный размер кластеров, неплоская геометрия, индуктивный.

Дистанции между точек

Spectral clustering

количество кластеров

Середина n_samples, Маленький n_clusters

Мало кластеров, одинаковый размер кластеров, неплоская геометрия, трансдуктивный.

Расстояние до графа (например, граф ближайших соседей)

Ward hierarchical clustering

количество кластеров или порог расстояния

Большой n_samples и n_clusters

Множество кластеров, возможно, ограничения связности, трансдуктивный

Дистанции между точек

Agglomerative clustering

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

Большой n_samples и n_clusters

Множество кластеров, возможно, ограничения связности, неевклидовы расстояния, трансдуктивный.

Любое попарное расстояние

DBSCAN

размер района

Очень большой n_samples, середина n_clusters

Неплоская геометрия, неравномерные размеры кластеров, удаление выбросов, трансдуктивный.

Расстояния между ближайшими точками

HDBSCAN

Минимальное количество элементов в кластере, минимальное количество соседей по точкам

large n_samples, середина n_clusters

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

Расстояния между ближайшими точками

OPTICS

Минимальное количество элементов в кластере

Очень большой n_samples, большой n_clusters

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

Дистанции между точек

Gaussian mixtures

Много

Не масштабируемый

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

Mahalanobis distances to centers

BIRCH

коэффициент ветвления, порог, дополнительный глобальный кластеризатор.

Большой n_clusters и n_samples

Большой набор данных, удаление выбросов, сокращение данных, индуктивный метод.

Euclidean distance between points

Bisecting K-Means

количество кластеров

Очень большой n_samples, середина n_clusters

Универсальное назначение, равномерный размер кластера, плоская геометрия, отсутствие пустых кластеров, индуктивный, иерархический.

Дистанции между точек

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

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

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

2.3.2. K-means (K-средних)

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

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

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

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

Инерцию можно рассматривать как меру внутренней согласованности кластеров. Он страдает различными недостатками:

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

  • Инерция не является нормализованной метрикой: мы просто знаем, что более низкие значения лучше, а ноль является оптимальным. Но в очень многомерных пространствах евклидовы расстояния имеют тенденцию раздуваться (это пример так называемого “проклятия размерности”). Выполнение алгоритма снижения размерности, такого как Анализ главных компонент (Principal component analysis - PCA), перед кластеризацией k-средних может облегчить эту проблему и ускорить вычисления.

../_images/sphx_glr_plot_kmeans_assumptions_002.png

Более подробное описание проблем, показанных выше, и способов их решения см. в примерах Demonstration of k-means assumptions и Selecting the number of clusters with silhouette analysis on KMeans clustering.

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

../_images/sphx_glr_plot_kmeans_digits_001.png

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

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

При наличии достаточного количества времени K-средних всегда будут сходиться, однако это может быть локальный минимум. Это сильно зависит от инициализации центроидов. В результате вычисления часто выполняются несколько раз с разной инициализацией центроидов. Одним из методов решения этой проблемы является схема инициализации k-means++, которая реализована в scikit-learn (используйте параметр init='k-means++'). Это инициализирует центроиды так, чтобы они были (как правило) удалены друг от друга, что, вероятно, приводит к лучшим результатам, чем случайная инициализация, как показано в ссылке. Подробный пример сравнения различных схем инициализации см. в A demo of K-Means clustering on the handwritten digits data.

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

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

K-средних можно использовать для векторного квантования. Это достигается с помощью метода transform обученной модели KMeans. Пример выполнения векторного квантования изображения см. в файле Color Quantization using K-Means.

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

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

2.3.2.2. Мини-батчи K-средних

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

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

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

../_images/sphx_glr_plot_mini_batch_kmeans_001.png

2.3.3. Affinity propagation (AP, метод распространения близости)

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

../_images/sphx_glr_plot_affinity_propagation_001.png

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

Основным недостатком Affinity Propagation является его сложность. Алгоритм имеет временную сложность порядка \(O(N^2 T)\), где \(N\) - количество выборок, а \(T\) - количество итераций до сходимости. Кроме того, сложность памяти имеет порядок \(O(N^2)\), если используется плотная матрица подобия, но снижается, если используется разреженная матрица подобия. Это делает Affinity Propagation наиболее подходящим для наборов данных малого и среднего размера.

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

Сообщения, отправляемые между точками, относятся к одной из двух категорий. Первая - это ответственность \(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\) указывает количество итерации.

2.3.4. Средний сдвиг (Mean Shift)

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

Положение кандидатов в центроиды итеративно корректируется с помощью техники, называемой восхождением на холм, которая находит локальные максимумы оцененной плотности вероятности. При задании кандидата в центроиды \(x\) для итерации \(t\), кандидат обновляется в соответствии со следующим уравнением:

\[x^{t+1} = x^t + m(x^t)\]

Где \(m\) - вектор среднего сдвига, который вычисляется для каждого центроида, указывающего на область максимального увеличения плотности точек. Чтобы вычислить \(m\), мы определяем \(N(x)\) как окрестность выборок на заданном расстоянии вокруг \(x\). Затем \(m\) вычисляется с использованием следующего уравнения, эффективно обновляя центроид, чтобы он стал средним значением выборок в его окрестности:

\[m(x) = \frac{1}{|N(x)|} \sum_{x_j \in N(x)}x_j - x\]

В общем, уравнение для \(m\) зависит от ядра, используемого для оценки плотности. Общая формула:

\[m(x) = \frac{\sum_{x_j \in N(x)}K(x_j - x)x_j}{\sum_{x_j \in N(x)}K(x_j - x)} - x\]

В нашей реализации \(K(x)\) равен 1, если \(x\) достаточно мал, и равен 0 в противном случае. Фактически \(K(y - x)\) указывает, находится ли \(y\) по соседству с \(x\).

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

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

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

../_images/sphx_glr_plot_mean_shift_001.png

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

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

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

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

noisy_img segmented_img

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

Transforming distance to well-behaved similarities

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

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

См. примеры такого приложения.

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

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

assign_labels="kmeans"

assign_labels="discretize"

assign_labels="cluster_qr"

coin_kmeans

coin_discretize

coin_cluster_qr

2.3.5.2. Графы спектральной кластеризации (Spectral Clustering Graphs)

Спектральную кластеризацию также можно использовать для разделения графов посредством их спектральных вложений. В этом случае Аффинная матрица является матрицей смежности графа, а 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-средних, но решается с помощью агломеративного иерархического подхода.

  • Maximum или complete linkage (полная связь) минимизирует максимальное расстояние между наблюдениями пар кластеров.

  • Average linkage (Средняя связь) минимизирует среднее значение расстояний между всеми наблюдениями пар кластеров.

  • Single linkage (Одиночная связь) минимизирует расстояние между ближайшими наблюдениями пар кластеров.

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

2.3.6.1. Другой тип связи: Ward, complete, average и single связь

AgglomerativeClustering поддерживает стратегии Ward, complete, average и single связи

../_images/sphx_glr_plot_linkage_comparison_001.png

Агломеративный кластер действует по принципу “богатые становятся богаче”, что приводит к неравномерным размерам кластеров. В этом отношении single связь является худшей стратегией, и Ward дает наиболее стандартные размеры. Однако близость (или расстояние, используемое при кластеризации) не может изменяться с помощью Ward, поэтому для неевклидовых метрик хорошей альтернативой является Average связь. Single связь, хотя и не устойчива к зашумленным данным, может быть вычислена очень эффективно и, следовательно, может быть полезна для обеспечения иерархической кластеризации больших наборов данных. Single связь также может хорошо работать с нешаровидными данными.

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

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

../_images/sphx_glr_plot_agglomerative_dendrogram_001.png

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

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

unstructured structured

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

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

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

Ограничения связности с single, average и complete связей

Ограничения связности и single, average или complete связь могут усилить аспект агломеративной кластеризации “богатые становятся богаче”, особенно если они построены с помощью sklearn.neighbors.kneighbors_graph. В пределе малого числа кластеров они имеют тенденцию давать немногочисленные макроскопически заполненные кластеры и почти пустые. (см. обсуждение в Agglomerative clustering with and without structure). Single связь является наиболее хрупким вариантом связи в этом вопросе.

../_images/sphx_glr_plot_agglomerative_clustering_001.png ../_images/sphx_glr_plot_agglomerative_clustering_002.png ../_images/sphx_glr_plot_agglomerative_clustering_003.png ../_images/sphx_glr_plot_agglomerative_clustering_004.png

2.3.6.4. Метрики расстояния

Single, average и complete связи могут использоваться с различными расстояниями (или связями), в частности евклидовым расстоянием (l2), манхэттенским расстоянием (или городским кварталом, или l1), косинусным расстоянием или любым заранее вычисленным сходством матрицы.

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

  • Косинусное расстояние интересно, поскольку оно инвариантно к глобальному масштабированию сигнала.

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

../_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-средних пополам

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

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

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

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

Этот вариант также не создает пустые кластеры.

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

  • bisecting_strategy="largest_cluster" выбирает кластер, имеющий наибольшее количество точек.

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

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

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

Разницу между Разделенным K-средним и обычным K-средним можно увидеть на примере Bisecting K-Means and Regular K-Means Performance Comparison. В то время как обычный алгоритм K-Means имеет тенденцию создавать несвязанные кластеры, кластеры из Разделенного К-среднего хорошо упорядочены и создают вполне видимую иерархию.

2.3.7. DBSCAN

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

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

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

Хотя параметр min_samples в первую очередь определяет, насколько толерантен алгоритм к шуму (для зашумленных и больших наборов данных может быть желательно увеличить этот параметр), параметр eps критерий выбора соответствия для набора данных и функции расстояния, и обычно его нельзя оставить со значением по умолчанию. Он контролирует локальную окрестность точек. Если выбрано слишком маленькое значение, большая часть данных вообще не будет кластеризована (и помечена как -1 для “шума”). Если выбрано слишком большое значение, это приведет к объединению близких кластеров в один кластер и, в конечном итоге, весь набор данных будет возвращен как один кластер. Некоторые эвристики для выбора этого параметра обсуждались в литературе, например, на основе изгиба на графике расстояний до ближайших соседей (как описано в ссылках ниже).

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

dbscan_results

2.3.8. HDBSCAN

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

Примечание

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

2.3.8.1. Граф взаимной достижимости (Mutual Reachability Graph)

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 сначала извлекает минимальное связующее дерево ( minimum spanning tree - MST) из полносвязного графа взаимной достижимости, а затем жадно отсекает ребра с наибольшим весом. Краткое описание алгоритма HDBSCAN выглядит следующим образом:

  1. Извлечение MST из \(G_{ms}\).

  2. Расширение MST, добавив “самое ребро” для каждой вершины с весом, равным основному расстоянию базового образца.

  3. Инициализация одного кластера и метки для MST.

  4. Удаление с MST край с наибольшим весом (одновременно удаляется завязки).

  5. Присвойте метки кластера связным компонентам, которые содержат конечные точки удаленного ребра. Если у компонента нет хотя бы одного края, ему вместо этого присваивается “null” метка, обозначающая его как шум.

  6. Повторяйте 4-5, пока не останется подключенных компонентов.

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

hdbscan_ground_truth

hdbscan_results

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

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_results

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

2.3.10. BIRCH

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

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

  • Количество образцов в подкластере.

  • Линейная сумма - n-мерный вектор, содержащий сумму всех выборок.

  • Сумма в квадрате - Сумма квадрата нормы L2 всех образцов.

  • Центроиды - Чтобы избежать пересчета линейной суммы/n_samples.

  • Квадрат нормы центроидов.

Алгоритм BIRCH имеет два параметра: порог (threshold) и коэффициент ветвления (branching factor). Коэффициент ветвления ограничивает количество субкластеров в узле, а порог ограничивает расстояние между входящей выборкой и существующими субкластерами.

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

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

  • Новый образец вставлен в корень дерева CF, который является узлом CF. Затем он объединяется с подкластером корня, имеющим наименьший радиус после слияния, ограниченный условиями порога и фактора ветвления. Если в подкластере есть какой-либо дочерний узел, то это делается повторно, пока он не достигнет листа. После нахождения ближайшего подкластера в листе свойства этого подкластера и родительских подкластеров рекурсивно обновляются.

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

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

BIRCH или MiniBatchKMeans?

  • BIRCH не очень хорошо масштабируется для данных большой размерности. Как правило, если n_features больше двадцати, обычно лучше использовать MiniBatchKMeans.

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

Как использовать partial_fit?

Чтобы избежать вычислений глобальной кластеризации, при каждом вызове partial_fit пользователю рекомендуется

  1. Изначально установить n_clusters=None

  2. Обучите все данные с помощью нескольких вызовов partial_fit.

  3. Установите для n_clusters необходимое значение, используя brc.set_params(n_clusters=n_clusters).

  4. Наконец, вызовите partial_fit без аргументов, т.е. brc.partial_fit(), который выполняет глобальную кластеризацию.

../_images/sphx_glr_plot_birch_vs_minibatchkmeans_001.png

2.3.11. Оценка производительности кластеризации

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

2.3.11.1. Индекс Rand

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

>>> 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...

Индекс Rand не гарантирует получение значения, близкого к 0.0 для случайной маркировки. Скорректированный индекс Rand с поправкой на случайность и дает такой базовый уровень.

>>> 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

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

>>> 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.07...

2.3.11.1.1. Преимущества

  • Интерпретируемость: Нескорректированный индекс Rand пропорционален количеству пар выборок, метки которых одинаковы как в labels_pred, так и в labels_true, или различны в обоих.

  • Случайные (однородные) назначения меток имеют скорректированный показатель индекса Rand, близкий к 0.0 для любого значения n_clusters и n_samples (что не относится к нескорректированному индексу Rand или например, V-мера).

  • Ограниченный диапазон: более низкие значения указывают на разные метки, схожие кластеризации имеют высокий (скорректированный или нескорректированный) индекс Rand, 1.0 - идеальный показатель соответствия. Диапазон оценок составляет [0, 1] для нескорректированного индекса Rand и [-1, 1] для скорректированного индекса Rand.

  • Не делается никаких предположений о структуре кластера: Индекс Rand (скорректированный или нескорректированный) может использоваться для сравнения всех типов алгоритмов кластеризации, а также для сравнения алгоритмов кластеризации, таких как k-means, который предполагает изотропные формы шара с результатами алгоритмов спектральной кластеризации, которые могут находить кластеры со “свернутыми” формами.

2.3.11.1.2. Недостатки

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

    Однако (скорректированный или нескорректированный) индекс Rand также может быть полезен в чисто неконтролируемых условиях в качестве строительного блока для Индексации (Consensus Index), который можно использовать для выбора модели кластеризации (TODO).

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

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

Если C - это назначение основного истинного класса, а K - кластеризация, давайте определим \(a\) и \(b\) как:

  • \(a\), количество пар элементов, находящихся в одном наборе в C и в одном наборе в K

  • \(b\), количество пар элементов, находящихся в разных наборах в C и в разных наборах в K

Нескорректированный индекс Rand тогда определяется следующим образом:

\[\text{RI} = \frac{a + b}{C_2^{n_{samples}}}\]

где \(C_2^{n_{samples}}\) - общее количество возможных пар в наборе данных. Не имеет значения, выполняется ли вычисление для упорядоченных или неупорядоченных пар, если вычисление выполняется последовательно.

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

Чтобы противостоять этому эффекту, мы можем исключить ожидаемый RI \(E[\text{RI}]\) случайных разметок, определив скорректированный индекс Rand следующим образом:

\[\text{ARI} = \frac{\text{RI} - E[\text{RI}]}{\max(\text{RI}) - E[\text{RI}]}\]

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

Учитывая знание основных назначений классов labels_true и наших назначений алгоритма кластеризации тех же образцов labels_pred, Взаимная информация - это функция, которая измеряет согласование два присваивания, игнорируя перестановки. Доступны две разные нормализованные версии этого показателя: Нормализованная взаимная информация (Normalized Mutual Information - NMI) и Скорректированная взаимная информация (Adjusted Mutual Information - 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...

2.3.11.2.1. Преимущества

  • Случайные (равномерные) назначения меток имеют оценку AMI, близкую к 0.0 при любом значении n_clusters и n_samples (чего нельзя сказать о простой взаимной информации (MI) или, например, о V-мере).

  • Верхняя граница равна 1: Значения, близкие к нулю, указывают на то, что два назначения меток в значительной степени независимы, в то время как значения, близкие к единице, указывают на значительное согласие. Кроме того, AMI, значение ровно 1, указывает на то, что два назначения меток равны (с перестановкой или без нее).

2.3.11.2.2. Недостатки

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

    Однако показатели на основе МИ также могут быть полезны в чисто неконтролируемых условиях в качестве строительного блока для Индексации (Consensus Index), который можно использовать для выбора модели кластеризации.

  • NMI и MI не корректируются на случайность.

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

Предположим, что присвоены две метки (одним и тем же 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))}\]

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

Ожидаемое значение взаимной информации можно рассчитать с помощью следующего уравнения [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})!}\]

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

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

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

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

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

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

В частности, Розенберг и Хиршберг (2007) определяют следующие две желательные цели для любого кластерного задания:

  • Однородность (Гомогенность - Homogeneity): каждый кластер содержит только точки одного класса.

  • Полнота (Completeness): все точки данного класса относятся к одному и тому же кластеру.

Мы можем превратить эти понятия в оценки 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.51...

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

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

beta по умолчанию имеет значение 1.0, но для использования нужно использовать значение меньше 1:

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

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

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

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

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

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

>>> metrics.homogeneity_completeness_v_measure(labels_true, labels_pred)
(0.66..., 0.42..., 0.51...)

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

>>> 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)

2.3.11.3.1. Преимущества

  • Ограниченные оценки: 0.0 - это настолько плохо, насколько это возможно, 1.0 - идеальный результат.

  • Интуитивная интерпретация: кластеризацию с плохой V-мерой можно качественно проанализировать с точки зрения однородности и полноты, чтобы лучше почувствовать, какие “типа” ошибок допущены при выполнении задания.

  • Не делается никаких предположений о структуре кластера: может использоваться для сравнения алгоритмов кластеризации, таких как k-средние, которые предполагают изотропные формы шара, с результатами алгоритмов спектральной кластеризации, которые могут находить кластеры со “свернутыми” формами.

2.3.11.3.2. Недостатки

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

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

../_images/sphx_glr_plot_adjusted_for_chance_measures_001.png

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

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

Оценки однородности и полноты формально определяются следующим образом:

\[h = 1 - \frac{H(C|K)}{H(C)}\]
\[c = 1 - \frac{H(K|C)}{H(K)}\]

где \(H(C|K)\) - это условная энтропия классов с учетом назначений кластера и определяется как:

\[H(C|K) = - \sum_{c=1}^{|C|} \sum_{k=1}^{|K|} \frac{n_{c,k}}{n} \cdot \log\left(\frac{n_{c,k}}{n_k}\right)\]

и \(H(C)\) является энтропией классов и определяется:

\[H(C) = - \sum_{c=1}^{|C|} \frac{n_c}{n} \cdot \log\left(\frac{n_c}{n}\right)\]

с \(n\) общее количество выборок, \(n_c\) и \(n_k\) количество выборок, принадлежащих соответственно классу \(c\) и кластеру \(k\) и, наконец, \(n_{c,k}\) количество выборок из класса \(c\), назначенных кластеру \(k\).

условная энтропия кластеров данного класса \(H(K|C)\) и энтропия кластеров \(H(K)\) определяются симметричным образом.

Розенберг и Хиршберг далее определяют V-меру как гармоническое среднее однородности и полноты:

\[v = 2 \cdot \frac{h \cdot c}{h + c}\]

2.3.11.4. Оценка Фаулкс-Мэллоуза (Fowlkes-Mallows score)

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

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

  • TP - это количество Истино-Положительных (True Positive) (т. е. количество пар точек, которые принадлежат одним и тем же кластерам как в истинных метках, так и в предсказанных метках)

  • FP - это количество Ложно-Положительных (False Positive) (т. е. количество пар точек, которые принадлежат одним и тем же кластерам в истинных метках, а не в предсказанных метках)

  • FN - это количество Ложно-Отрицательных (False Negative) ( т. е. количество пар точек, принадлежащих одним и тем же кластерам в предсказанных метках, а не в истинных метках).

Оценка варьируется от 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

2.3.11.4.1. Преимущества

  • Случайные (унифицированные) назначения меток имеют оценку FMI, близкий к 0.0 для любого значения n_clusters и n_samples (что не относится к простой взаимной информации (MI) или V-мере).

  • Верхняя граница равна 1: значения, близкие к нулю, указывают на два назначения меток, которые в значительной степени независимы, а значения, близкие к единице, указывают на значительное согласие. Кроме того, значения, равные ровно 0, указывают на чисто независимые назначения меток, а значение FMI, равное ровно 1, указывает на то, что два назначения меток равны (с перестановкой или без нее).

  • Не делается никаких предположений о структуре кластера: может использоваться для сравнения алгоритмов кластеризации, таких как k-средние, которые предполагают изотропные формы шара, с результатами алгоритмов спектральной кластеризации, которые могут находить кластеры со “свернутой” формой.

2.3.11.4.2. Недостатки

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

2.3.11.5. Коэффициент силуэта (Silhouette Coefficient)

Если основные истинные метки неизвестны, оценку необходимо выполнить с использованием самой модели. Коэффициент силуэта (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...

2.3.11.5.1. Преимущества

  • Оценка ограничена от -1 за неправильную кластеризацию до +1 за очень плотную кластеризацию. Оценки около нуля указывают на перекрывающиеся кластеры.

  • Оценка выше, когда кластеры плотные и хорошо разделены, что соответствует стандартному понятию кластера.

2.3.11.5.2. Недостатки

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

2.3.11.6. Индекс Калинского-Харабаша (Calinski-Harabasz)

Если основные истинные метки неизвестны, для оценки модели можно использовать индекс Калински-Харабаша (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.6.1. Преимущества

  • Оценка выше, когда кластеры плотные и хорошо разделены, что соответствует стандартному понятию кластера.

  • Оценка быстро подсчитывается.

2.3.11.6.2. Недостатки

  • Индекс Калински-Харабаша обычно выше для выпуклых кластеров, чем для других концепций кластеров, таких как кластеры на основе плотности, подобные тем, которые получены с помощью DBSCAN.

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

Для набора данных \(E\) размером \(n_E\), который был сгруппирован в кластеры \(k\), оценка Калински-Харабаша \(s\) определяется как соотношение среднего значения межкластерной дисперсии и внутрикластерной дисперсии:

\[s = \frac{\mathrm{tr}(B_k)}{\mathrm{tr}(W_k)} \times \frac{n_E - k}{k - 1}\]

где \(\mathrm{tr}(B_k)\) - след матрицы дисперсии между группами, а \(\mathrm{tr}(W_k)\) - след матрицы дисперсии внутри кластера, определяемой формулой:

\[W_k = \sum_{q=1}^k \sum_{x \in C_q} (x - c_q) (x - c_q)^T\]
\[B_k = \sum_{q=1}^k n_q (c_q - c_E) (c_q - c_E)^T\]

с \(C_q\) набор точек в кластере \(q\), \(c_q\) центр кластера \(q\), \(c_E\) центр \(E\) и \(n_q\) количество точек в кластере \(q\).

2.3.11.7. Индекс Дэвиса-Булдина (Davies-Bouldin)

Если основные истинные метки неизвестны, для оценки модели можно использовать индекс Дэвиса-Булдина (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.7.1. Преимущества

  • Расчеты по шкале Дэвиса-Булдина проще, чем по шкале Силуэт.

  • Индекс основан исключительно на количествах и особенностях, присущих набору данных, поскольку при его расчете используются только точечные расстояния.

2.3.11.7.2. Недостатки

  • Индекс Дэвиса-Боулдинга обычно выше для выпуклых кластеров, чем для других концепций кластеров, таких как кластеры на основе плотности, подобные тем, которые получены из DBSCAN.

  • Использование расстояния до центроида ограничивает метрику расстояния евклидовым пространством.

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

Индекс определяется как среднее сходство между каждым кластером \(C_i\) для \(i=1, ..., k\) и его наиболее похожим кластером \(C_j\). В контексте этого индекса сходство определяется как мера \(R_{ij}\), которая колеблется:

  • \(s_i\), среднее расстояние между каждой точкой кластера \(i\) и центроид этого кластера - также известен как диаметр кластера.

  • \(d_{ij}\), расстояние между центроидами кластера \(i\) и \(j\).

Простой вариант построения \(R_{ij}\) так, чтобы он был неотрицательным и симметричным:

\[R_{ij} = \frac{s_i + s_j}{d_{ij}}\]

Тогда индекс Дэвиса-Булдина определяется как:

\[DB = \frac{1}{k} \sum_{i=1}^k \max_{i \neq j} R_{ij}\]

2.3.11.8. Матрица непредвиденных обстоятельств (Contingency Matrix)

Матрица непредвиденных обстоятельств (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.8.1. Преимущества

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

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

2.3.11.8.2. Недостатки

  • Матрицу непредвиденных обстоятельств легко интерпретировать для небольшого количества кластеров, но становится очень сложно интерпретировать для большого количества кластеров.

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

2.3.11.9. Матрица ошибок пар (Pair Confusion Matrix)

Матрица ошибок пар (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]])