Внешние метрики качества

Изучим внешние меры оценки качества кластеризации. Внешние метрики основаны на сопоставлении разбивки объектов на кластера $C = \{C_1, \dots, C_K\}$ с истинной разметкой (ground truth) на классы $G = \{G_1, \dots, G_M\}$ . Чем лучше соответствие между разбивкой объектов на классы и кластера, тем кластеризация считается лучше.

Сравнение с оценкой качества классификации

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

Будем использовать следующие обозначения:

$N$ - число объектов, а $D$ - число признаков;
$K$ - общее число кластеров;
$C_i$ - индексы объектов $i$ -го кластера;
$N_1=|C_1|,N_2=|C_2|,...N_K=|C_K|$ - количества объектов в каждом кластере;
$\boldsymbol{\mu}_1,...\boldsymbol{\mu}_K$ - центроиды кластеров, вычисляемые как средние по объектам соответствующих кластеров;
$\rho(\boldsymbol{x}, \boldsymbol{x}')$ - используемая функция расстояния

Далее будем считать, что сложность вычисления расстояния между объектами $\rho(\boldsymbol{x}, \boldsymbol{x}')$ пропорциональна числу признаков $D$ , что выполняется для всех стандартных функций расстояния.

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

Матрица сопряжённости (contingency matrix) — это таблица, используемая для детального сопоставления результатов кластеризации с истинной разметкой данных на классы. Пусть $n_{ij}$ — количество объектов, принадлежащих истинному классу $i$ и отнесённых алгоритмом к кластеру $j$ :

n_{ij} = | \{ \boldsymbol{x}_n : \text{class}(\boldsymbol{x}_n) = i \land \text{cluster}(\boldsymbol{x}_n) = j \} |

Рассмотрим случай, когда $N=100$ объектов двух классов были распределены по трём кластерам. Первый кластер при этом оказался малочисленным и не содержит ярко выраженного доминирующего класса (группа объектов, которые алгоритм не смог однозначно соотнести с основными ядрами).

Кластер 1 Кластер 2 Кластер 3
Класс 1 3 44 3
Класс 2 2 4 44

Анализ таблицы показывает:

Кластер 1 является малочисленным и нерелевантным: в него попало всего 5 объектов из 100, и он не помогает в идентификации структуры классов.

Кластер 2 успешно захватил основную массу объектов первого класса (44 объекта).

Кластер 3 почти идеально выделил второй класс (44 объекта).

	Кластер 1	Кластер 2	Кластер 3
Класс 1	3	44	3
Класс 2	2	4	44

Точность кластеризации

Для сведения матрицы сопряжённости к единому числу используется точность кластеризации (unsupervised clustering accuracy, UCA). Поскольку в обучении без учителя номера кластеров назначаются произвольно, мы не можем просто посчитать долю объектов на диагонали. Необходимо найти такое оптимальное сопоставление меток кластеров и классов, которое максимизирует итоговую точность.

Точность определяется как максимальное количество верно соотнесённых объектов среди всех возможных перестановок номеров кластеров $p$ :

UCA = \max_{p} \frac{1}{N} \sum_{n=1}^{N} \mathbb{I} \{ \text{class}(\boldsymbol{x}_n) = p(\text{cluster}(\boldsymbol{x}_n)) \}

Для примера выше оптимальное соответствие: Кластер 2 $\to$ Класс 1, Кластер 3 $\to$ Класс 2. Кластер 1 при любом сопоставлении даст лишь незначительное количество верных или ошибочных предсказаний, которые не изменят общую картину.

UCA = \frac{44 + 44}{100} = 0.88

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

Матрица парных совпадений

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

Каждая пара объектов относится к одной из четырёх категорий:

TP (True Positive): пара объектов одного класса, отнесённая к одному кластеру.
TN (True Negative): пара объектов разных классов, отнесённая к разным кластерам.
FP (False Positive): пара объектов разных классов, отнесённая к одному кластеру (ошибка «слипания»).
FN (False Negative): пара объектов одного класса, отнесённая к разным кластерам (ошибка «дробления»).

Для этого используется матрица парных совпадений (pair confusion matrix).

	Объекты в одном кластере	Объекты в разных кластерах
Объекты одного класса	$TP$	$FN$
Объекты разных классов	$FP$	$TN$

Сумма всех элементов таблицы равна общему числу из $N(N-1)/2$ уникальных пар.

Более высокое качество кластеризации соответствует случаям, когда сумма диагональных элементов максимальна, а сумма внедиагональных элементов мала.

При этом анализ внедиагональных элементов позволяет делать выводы об источниках проблем:

Высокое $FP$ свидетельствует о слиянии разных классов (under-clustering), и в таком случае нужно увеличить число кластеров $K$ или ужесточить критерии вхождения объекта в группу.
Высокое $FN$ свидетельствует об избыточном дроблении классов (over-clustering), и в таком случае нужно уменьшить количество кластеров $K$ или использовать более «мягкие» меры сходства.

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

Индекс Ранда

Индекс Ранда (Rand Index, RI [2]) определяет долю пар объектов, по которым мнения алгоритма и эксперта совпали:

RI = \frac{TP + TN}{TP + TN + FP + FN}

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

Скорректированный индекс Ранда (Adjusted Rand Index, ARI [3]) вводит поправку на вероятность случайного совпадения пар, поскольку для более точного расчёта нам необходимо нормировать результат так, чтобы для случайного разбиения ожидаемое значение индекса было равно 0, а для идеального — 1.

Он считается по формуле

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

где $E[RI]$ — математическое ожидание индекса Ранда для случайного случая, а $\max(RI)$ — максимально возможное значение индекса Ранда, которое всегда равно 1.

Индекс Фолкса-Мэллоуза

Индекс Фолкса-Мэллоуза (Fowlkes-Mallows Index, FMI [4]) представляет собой среднее геометрическое точности и полноты, вычисленных на парах объектов:

FMI = \sqrt{\frac{TP}{TP + FP} \cdot \frac{TP}{TP + FN}}

Мера полезна, когда нужно проигнорировать пары TN, количество которых в разреженных данных или данных с большим числом классов может быть избыточным и завышать индекс Рэнда.

Индекс принимает значения на отрезке $[0,1]$ , причём 1 соответствует наилучшей кластеризации, а 0 - наихудшей.

Обобщение меры

Для смещения баланса в сторону оценки точности или полноты индекс Фолкса — Мэллоуза обобщается через взвешенное среднее геометрическое:

FMI_{\alpha} = P_{pair}^{\alpha} \cdot R_{pair}^{1-\alpha}

Параметр $\alpha \in [0, 1]$ определяет приоритет одной из составляющих, а при $\alpha = 0.5$ формула возвращается к классическому виду $\sqrt{P \cdot R}$ .

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

Приоритет точности ( $\alpha > 0.5$ ): важнее чистота кластеров, когда нежелательно смешивать разные классы.
Приоритет полноты ( $\alpha < 0.5$ ): важнее целостное восстановление классов, когда нежелательно дробление класса на части.

:::

Коэффициент Жаккара

Коэффициент Жаккара (Jaccard Index [5]), как и индекс Фолкса-Мэллоуза фокусируется исключительно на положительных совпадениях в структуре, игнорируя пары TN. Он вычисляет меру похожести Жаккара между множествами пар объектов, которые отнесены к одному объекту и к одному кластеру и вычисляется по формуле:

J = \frac{TP}{TP + FP + FN}

Задача

Какая мера всегда не ниже другой - коэффициент Жаккара или индекс Фолкса-Мэллоуза?

Коэффициент Жаккара принимает значения на отрезке $[0,1]$ , причём 1 соответствует наилучшей кластеризации, а 0 - наихудшей.

V-мера

V-мера (V-measure [6]) — это среднее гармоническое между двумя характеристиками: гомогенностью и полнотой, каждая из которых по-своему оценивает качество кластеризации:

V_{\beta} = \frac{(1 + \beta) \cdot h \cdot c}{\beta \cdot h + c}

Здесь $h$ — мера гомогенности (homogeneity), а $c$ — мера полноты (completeness). Если $\beta > 1$ , то больший вес придаётся полноте, если $\beta < 1$ — гомогенности. По умолчанию используется $\beta = 1$ .

Гомогенность

Гомогенность (homogeneity) определяет, насколько каждый кластер $C_k$ состоит из объектов, принадлежащих только одному классу. Результат считается идеально гомогенным, если каждый кластер состоит из объектов только одного класса. Пусть $H(G)$ — энтропия распределения классов, а $H(G|C)$ — условная энтропия классов при условии распределения по кластерам:

h = 1 - \frac{H(G|C)}{H(G)}

Если каждый кластер содержит объекты только одного класса, то $H(G|C) = 0$ и гомогенность максимальна и равна 1.

Тривиальное решение

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

Полнота

Полнота (completeness) измеряет, насколько все объекты, принадлежащие к одному классу, отнесены к одному и тому же кластеру. Результат считается идеально полным, если каждый класс содержится лишь в одном кластере. Пусть $H(C)$ — энтропия распределения кластеров, а $H(C|G)$ — условная энтропия кластеров при условии истинных классов:

c = 1 - \frac{H(C|G)}{H(C)}

Если все объекты каждого класса попали в свои уникальные кластеры, то $H(C|G) = 0$ и полнота принимает максимальное значение 1.

Смещённость оценки

Если ориентироваться только на полноту, то тривиальным решением будет поместить все объекты в один кластер. $H(K)$ в таком случае полагается равной 1, чтобы избежать деления на ноль, и мы получаем максимальное значение меры.

Поэтому полнота используется только в паре с гомогенностью.

Метрики на основе взаимной информации

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

Введём вероятностные обозначения для разбиения объектов на истинные классы $G = \{G_1, \dots, G_M\}$ и предсказанные кластеры $C = \{C_1, \dots, C_K\}$ :

$P(G_i) = \frac{|G_i|}{N}$ — вероятность того, что случайно выбранный объект принадлежит классу $G_i$ ;
$P(C_k) = \frac{|C_k|}{N}$ — вероятность того, что случайно выбранный объект принадлежит кластеру $C_k$ ;
$P(G_i, C_k) = \frac{|G_i \cap C_k|}{N}$ — совместная вероятность того, что объект принадлежит классу $G_i$ и кластеру $C_k$ одновременно;
$P(G_i | C_k) = \frac{P(G_i, C_k)}{P(C_k)}$ — условная вероятность принадлежности к классу $G_i$ при условии, что объект попал в кластер $C_k$ .

Взаимная информация (MI)

Взаимная информация (Mutual Information, MI) измеряет степень зависимости между распределением объектов по классам и их распределением по кластерам.

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

MI(G, C) = \sum_{i=1}^{M} \sum_{k=1}^{K} P(G_i, C_k) \log \frac{P(G_i, C_k)}{P(G_i) P(C_k)}

Эту же величину можно выразить через разность безусловной и условной энтропии:

MI(G, C) = H(G) - H(G|C)

Где $H(G)$ — неопределенность принадлежности к классам, а $H(G|C)$ — неопределенность классов после того, как стало известно разбиение по кластерам:

H(G|C) = - \sum_{k=1}^{K} P(C_k) \sum_{i=1}^{M} P(G_i | C_k) \log P(G_i | C_k)

Диапазон значений

Мера принимает значения в диапазоне $[0, \min(H(G), H(C))]$ . Значение $0$ означает полную независимость разбиений.

Нормированная взаимная информация (NMI)

Нормированная взаимная информация (Normalized Mutual Information, NMI) — это версия MI, приведенная к стандартному диапазону [0,1] за счёт нормализации:

NMI(G, C) = \frac{MI(G, C)}{F(H(G), H(C))}

Здесь $F$ — функция агрегации энтропий, для которой доступны следующие варианты:

минимальная: $F = \min(H(G), H(C))$
максимальная: $F = \max(H(G), H(C))$
геометрическая: $F = \sqrt{H(G) \cdot H(C)}$
арифметическая: $F = \frac{H(G) + H(C)}{2}$

Для любого вида агрегации NMI будет принадлежать $[0, 1]$ , а значение 1 будет достижимо только для агрегации минимумом.

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

Скорректированная взаимная информация (Adjusted Mutual Information, AMI [7]) вводит поправку на случайность, что делает её более надежной для задач с большим числом кластеров. Обычные MI и NMI имеют тенденцию увеличиваться при росте количества кластеров $K$ , даже если объекты распределены случайно.

Она вычисляется следующим образом:

AMI = \frac{MI(G, C) - E[MI(G, C)]}{F(H(G), H(C)) - E[MI(G, C)]},

где $E[MI(G, C)]$ — ожидаемое значение взаимной информации для случайных меток.

Верхняя граница меры равна 1. При этом значение может быть и отрицательным, если кластеризация окажется хуже случайной.

Внешние метрики качества

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

Точность кластеризации​

Матрица парных совпадений​

Индекс Ранда​

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

Индекс Фолкса-Мэллоуза​

Коэффициент Жаккара​

V-мера​

Гомогенность​

Полнота​

Метрики на основе взаимной информации​

Взаимная информация (MI)​

Нормированная взаимная информация (NMI)​

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

Литература​