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 кодом	Общего назначения, одинаковый размер кластеров, плоская геометрия, не слишком много кластеров, индуктивный	Расстояния между точками
Affinity propagation	затухание, предпочтение образца	Не масштабируется с n_samples	Много кластеров, неравномерный размер кластеров, не плоская геометрия, индуктивный	Расстояние графа (например, граф ближайших соседей)
Mean-shift	ширина полосы	Не масштабируется с `n_samples`	Много кластеров, неравномерный размер кластеров, не плоская геометрия, индуктивный	Расстояния между точками
Spectral clustering	количество кластеров	Средняя `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-средних	количество кластеров	Очень большая `n_samples`, средняя `n_clusters`	Общего назначения, одинаковый размер кластеров, плоская геометрия, нет пустых кластеров, индуктивный, иерархический	Расстояния между точками

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

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

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

END_OF_DOCUMENT_MARKER

2.3.2. 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)\]

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

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

../_images/sphx_glr_plot_kmeans_assumptions_002.png

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

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

../_images/sphx_glr_plot_kmeans_digits_001.png

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

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

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

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

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

Примеры

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

2.3.2.1. Параллелизм низкого уровня

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

Примеры

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

2.3.2.2. Мини-пакетные K-средние

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

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

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

../_images/sphx_glr_plot_mini_batch_kmeans_001.png

Примеры

Сравнение алгоритмов кластеризации K-средних и MiniBatchKMeans: Сравнение KMeans и MiniBatchKMeans
Кластеризация текстовых документов с помощью K-средних: Кластеризация документов с использованием 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\) обозначает номер итерации.

Примеры

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

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

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

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

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

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

../_images/sphx_glr_plot_mean_shift_001.png

Примеры

Демонстрация алгоритма кластеризации методом среднего сдвига: Кластеризация методом среднего сдвига на синтетических 2D наборах данных с 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" является 100% воспроизводимой, но имеет тенденцию создавать участки с довольно равномерной и геометрической формой. Недавно добавленный вариант "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, поэтому для неевклидовых метрик средняя связь является хорошей альтернативой. Одиночная связь, хотя и не устойчива к шумным данным, может быть вычислена очень эффективно и поэтому может быть полезна для обеспечения иерархического кластерирования больших наборов данных. Одиночная связь также может хорошо работать с неглобулярными данными.

Примеры

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

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

Примеры

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

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

Методы «единственной связи», «средней связи» и «полной связи» могут использоваться с различными расстояниями (или аффинностями), в частности, с евклидовым расстоянием (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-средних можно увидеть на примере Сравнение производительности двоичного K-средних и обычного K-средних. В то время как алгоритм обычного K-средних имеет тенденцию создавать несвязанные кластеры, кластеры от двоичного K-средних упорядочены и образуют довольно чёткую иерархию.

2.3.7. DBSCAN

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

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

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

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

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

Примеры

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

Алгоритм выявления кластеров на основе плотности в больших пространственных базах данных с шумом Ester, M., H. P. Kriegel, J. Sander, and X. Xu, В Трудах 2-й международной конференции по открытию знаний и анализу данных, Портленд, OR, AAAI Press, стр. 226-231. 1996
DBSCAN повторно пересмотрен: почему и как вы всё ещё должны использовать DBSCAN. Schubert, E., Sander, J., Ester, M., Kriegel, H. P., & Xu, X. (2017). В ACM Transactions on Database Systems (TODS), 42(3), 19.

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). Density-Based Clustering Based on Hierarchical Density Estimates. In: Pei, J., Tseng, V.S., Cao, L., Motoda, H., Xu, G. (eds) Advances in Knowledge Discovery and Data Mining. PAKDD 2013. Lecture Notes in Computer Science(), vol 7819. Springer, Berlin, Heidelberg. Density-Based Clustering Based on Hierarchical Density Estimates

[LJ2017]

L. McInnes and J. Healy, (2017). Accelerated Hierarchical Density Based Clustering. In: IEEE International Conference on Data Mining Workshops (ICDMW), 2017, pp. 33-42. Accelerated Hierarchical Density Based Clustering

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

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

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

Алгоритм 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.07...

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

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

Недостатки:

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

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

Недостатки:

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

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

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

Ссылки

Strehl, Alexander, and Joydeep Ghosh (2002). «Cluster ensembles — a knowledge reuse framework for combining multiple partitions». Journal of Machine Learning Research 3: 583-617. doi:10.1162/153244303321897735.
Статья в Википедии о взаимной информации
Статья в Википедии о скорректированной взаимной информации

[VEB2009]

Vinh, Epps, and Bailey, (2009). «Information theoretic measures for clusterings comparison». Proceedings of the 26th Annual International Conference on Machine Learning - ICML ‘09. doi:10.1145/1553374.1553511. ISBN 9781605585161.

[VEB2010]

Vinh, Epps, and Bailey, (2010). «Information Theoretic Measures for Clusterings Comparison: Variants, Properties, Normalization and Correction for Chance». JMLR <https://jmlr.csail.mit.edu/papers/volume11/vinh10a/vinh10a.pdf>

[YAT2016]

Yang, Algesheimer, and Tessone, (2016). «A comparative analysis of community detection algorithms on artificial networks». 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.51...

Формула этой функции такова:

\[v = \frac{(1 + \beta) \times \text{однородность} \times \text{полнота}}{(\beta \times \text{однородность} + \text{полнота})}\]

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

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

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

Мера V фактически эквивалентна взаимной информации (VMI), обсуждаемой выше, где агрегационной функцией является среднее арифметическое [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)

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

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

Недостатки:

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

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

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

Примеры

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

Ссылки

V-Measure: A conditional entropy-based external cluster evaluation measure Andrew Rosenberg и Julia Hirschberg, 2007

[B2011]

Identification and Characterization of Events in Social Media, 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-means, который предполагает изотропные формы облаков, с результатами алгоритмов спектральной кластеризации, которые могут находить кластеры с «сложенными» формами.

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

Примеры

Выбор числа кластеров с помощью анализа силуэта для кластеризации KMeans : В этом примере анализ силуэта используется для выбора оптимального значения 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–2025 The scikit-learn developers
Licensed under the 3-clause BSD License.
https://scikit-learn.org/1.6/modules/clustering.html