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

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

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

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

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

$N$ - число объектов, а $D$ - число признаков;
$K$ - общее число кластеров; $C$ - общее количество классов;
$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 \: \& \: \text{cluster}(\boldsymbol{x}_n) = j \} |

Рассмотрим пример, когда 100 объектов двух классов были распределены по трём кластерам согласно следующей матрице сопряжённости:

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

Полученная матрица сопряжённости позволяет сделать следующие выводы:

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

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

А кластер 3 успешно выделил основную часть объектов второго класса.

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

	Кластер 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], решающий задачу о назначениях за полиномиальное время $O(\min(C, K)^2 \cdot \max(C, K))$ по числу кластеров и классов.

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

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

Каждая пара объектов $(\boldsymbol{x}_i,\boldsymbol{x}_j)$ относится к одной из четырёх категорий:

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}

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

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

Скорректированный индекс Ранда (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{\text{Precision} \cdot \text{Recall}} = \sqrt{\frac{TP}{TP + FP} \cdot \frac{TP}{TP + FN}}

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

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

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

FMI_{\alpha} = \text{Precision}^{\alpha} \cdot \text{Recall}^{1-\alpha}

Гиперпараметр $\alpha \in [0, 1]$ определяет приоритет одной из составляющих, а при $\alpha = 0.5$ формула возвращается к равномерному учёту точности и полноты.

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

Приоритет точности ( $\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}=\frac{(1 + \beta) }{\beta \cdot 1/c + 1/h}

Здесь $h$ - мера гомогенности (homogeneity), а $c$ - мера полноты (completeness).

По умолчанию гиперпараметр $\beta = 1$ , при котором вычисляется обычное среднее гармоническое между $c$ и $h$ .
Если $\beta > 1$ , то больший вес придаётся полноте.
Если $\beta \in (0,1)$ - гомогенности.

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

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

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 [8]) измеряет степень зависимости между распределением объектов по классам и их распределением по кластерам.

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

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

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

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 [9]) вводит поправку на случайность, что делает её более надежной для задач с большим числом кластеров. Обычные меры $MI$ и $NMI$ имеют тенденцию увеличиваться при росте количества кластеров, даже если объекты распределены случайно.

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

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

Литература​