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

Изучим внешние меры оценки качества кластеризации. Внешние метрики основаны на сопоставлении разбивки объектов на кластера $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 объекта).

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

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

Литература

1. Wikipedia: Венгерский алгоритм.
2. Rand W. M. Objective criteria for the evaluation of clustering methods //Journal of the American Statistical association. – 1971. – Т. 66. – №. 336. – С. 846-850.
3. Wikipedia: Rand index.
4. Wikipedia: Fowlkes–Mallows index.
5. Wikipedia: Jaccard index.
6. Rosenberg A., Hirschberg J. V-measure: A conditional entropy-based external cluster evaluation measure //Proceedings of the 2007 joint conference on empirical methods in natural language processing and computational natural language learning (EMNLP-CoNLL). – 2007. – С. 410-420.
7. Vinh N. X., Epps J., Bailey J. Information Theoretic Measures for Clusterings Comparison: Variants, Properties, Normalization and Correction for Chance // Journal of Machine Learning Research. — 2010. — Vol. 11. — P. 2837–2854.