Десять минут, чтобы освоить индекс оценки алгоритма кластеризации

Это 18-й день моего участия в августовском испытании обновлений. Узнайте подробности события:Испытание августовского обновления

предисловие

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

Итак, как вы оцениваете, является ли алгоритм кластеризации хорошим или плохим?

Хороший алгоритм кластеризации обычно требует, чтобы кластеры имели:

Высокое внутрикластерное сходство
Пол межкластерного подобия

Вообще говоря, существует два критерия оценки качества кластеризации: индекс внутренней оценки и индекс внешней оценки.

Методы внутренней оценки

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

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

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

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

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

Для набора выборок коэффициент силуэта представляет собой среднее значение всех коэффициентов силуэта выборки.

Диапазон значений коэффициента силуэта составляет [-1, 1].Чем ближе образцы одной категории и чем дальше образцы разных категорий, тем больше значение. Когда значение отрицательное, эффект кластеризации плохой.

недостаток

Не подходит для алгоритмов кластеризации на основе плотности (DBSCAN).

Индекс Калински-Харабаз

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

Индекс Калински-Харабаш пройденВычислите сумму квадратов расстояний между точками в классе и центром класса, чтобы измерить близость внутри класса.,пройти черезВычислите сумму квадратов расстояний между различными центральными точками и центральной точкой набора данных, чтобы измерить степень разделения набора данных., индикатор СНПолучается из отношения разделения к компактности. Следовательно, чем больше КГ, тем ближе сам класс и тем больше он разбросан между классами, то есть лучше результат кластеризации.

преимущество

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

недостаток

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

Индекс Дэвиса-Булдина (DBI)

Индекс БД рассчитывается произвольноВнутриклассовое расстояние Среднее расстояние между двумя классамисумма, деленная наРасстояние между центрами двух кластеровНайдите максимальное значение. Чем меньше БД, тем меньше внутриклассовое расстояние и тем больше межклассовое расстояние.Ноль — это наименьшее возможное значение, а значения, близкие к нулю, указывают на лучшее разбиение.

Его формула:

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

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

в, $s_i$ Представляет среднее расстояние между каждой точкой кластера и центром тяжести этого кластера, также известное как диаметр кластера. $d_{ij}$ представляет собой расстояние между центроидами кластеров i и j.

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

недостаток:

Из-за использования евклидова расстояния оно плохо оценивается для кластеризации круговых распределений.

Методы внешней оценки

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

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

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

Индекс Рэнда (RI, индекс Рэнда)

Индекс Рэнда рассматривает кластеризацию как серию процессов принятия решений, т. $N(N-1)/2$ [пара документов] для принятия решения. Мы объединяем два документа в один и тот же кластер тогда и только тогда, когда они похожи.

Правильное решение:

TP объединяет два похожих документа в кластер (один и тот же)
TN помещает два непохожих документа в разные кластеры (разные - разные)

Плохое решение:

FP объединяет два непохожих документа в один кластер (разные - одинаковые)
FN группирует два похожих документа в разные кластеры (одинаковые-разные)

РИ вычисляет коэффициент «правильных решений» (точность).

Его формула:

\text{RI} = \frac{a + b}{C_2^{n_{samples}}} = \frac {TP+TN} {TP + TN + FP + FN} = \frac {TP+TN} {C_2^{n_{samples}}}

Среди них C представляет фактическую информацию о категории, K представляет результат кластеризации, а a представляет как C, так и K.та же категорияЛогарифм элемента , b означает как в C, так и в Kразные категорииЛогарифм элемента , $C_2^{n_{samples}}$ представляет количество логарифмов, которые могут быть сформированы в наборе данных.

Диапазон значений RI составляет [0, 1], и чем больше значение, тем более согласуются результаты кластеризации с реальной ситуацией.

Скорректированный индекс Рэнда

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

Его формула:

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

Диапазон значений ARI составляет [-1, 1], и чем больше значение, тем более согласуются результаты кластеризации с реальной ситуацией. В широком смысле ARI измеряет, насколько хорошо подходят два распределения данных.

преимущество:

ARI случайных кластеров очень близок к 0 для любого количества центров кластеров и выборок.
Значение находится между [-1, 1], отрицательное число представляет плохой результат, и чем ближе оно к 1, тем лучше.
Никаких предположений о структуре кластеров не делается: ее можно использовать для сравнения алгоритмов кластеризации. .

недостаток:

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

Нормализованная взаимная информация (NMI, Normalized Mutual Information)

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

Предполагая, что U и V являются присвоениями N меток выборки, энтропия двух распределений (энтропия представляет собой степень неопределенности) равна:

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

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

Выражение взаимной информации между 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 и NMI составляет [0, 1].Чем больше значение, тем больше соответствует результат кластеризации реальной ситуации.

Скорректированная взаимная информация (AMI, Скорректированная взаимная информация)

Скорректированная взаимная информацияВнесите коррективы в оценку взаимной информации.

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

Его выражение:

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

Диапазон значений AMI составляет [-1, 1], и чем больше значение, тем более согласуются результаты кластеризации с реальной ситуацией.

AMI возвращает значение 1, когда два набора кластеров идентичны (т. е. точное совпадение); случайные разделы (независимые метки) имеют среднее ожидаемое значение AMI около 0 и может быть отрицательным.

Среднее гармоническое мер однородности и мер целостности (V-мера)

Два индикатора:

Однородность: Каждый кластер содержит только членов одного класса.
Полнота: все члены данного класса относятся к одному и тому же кластеру.

V-мера – это среднее гармоническое однородности и полноты.

Его выражение:

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

Диапазон значений V-меры[0,1], чем больше, тем лучше, но когда размер выборки мал или данные кластера велики, рекомендуется использовать AMI и ARI.

Рейтинг Фаулкса-Мэллоуза (FMI)

FMI — это среднее геометрическое точности и полноты. Диапазон значений — [0,1], чем ближе к 1, тем лучше.

Recall (отзыв) и Precision (точность), формула выглядит следующим образом

Recall = \frac {TP} {TP+FN}

Precision = \frac {TP} {TP+FP}

Однако определенные в нем TP, FP, TN, FN не совпадают с обычными классификационными задачами.Конкретные определения заключаются в следующем:

TP: Образцовая пара представляет собой кластер в GT (истинное значение), а также кластер в Pred (прогнозируемое значение).
FP: Образцовая пара является кластером в Pred, но не кластером в GT.
FN: Образцовая пара является кластером в GT, но не кластером в Pred.
TN: Пара выборок не является кластером в GT и кластером в Pred.

Для задачи кластеризации с n общими выборками, если она $s_1,...,s_n$ тогда можно составить $\frac {(n-1)*n}{2}$ выборочные пары, т. $C_n^2$ , и TP, FP, TN, FN являются основой для определения этих пар выборок, поэтому выполняются следующие уравнения:

TP+FP+TN+FN = \frac {(n-1)*n}{2}

Формула для FMI определяется как:

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

Суммировать

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