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

Изучим внутренние меры оценки качества кластеризации (internal cluster validity measures), которые не используют информации о внешней разметке, а основаны только на геометрической структуре полученного кластерного разбиения.

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

• $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$, что выполняется для всех стандартных функций расстояния.

Компактность кластеров

Компактность кластеров (cluster cohesion) определяет, насколько близко объекты одного кластера $C_k$ расположены близко относительно друг друга или своего своего центра. Наиболее распространенным способом измерения компактности является сумма квадратов внутрикластерных расстояний (Within-cluster Sum of Squares, WSS):

$$WSS = \sum_{k=1}^{K} \sum_{n \in C_k} \rho^2(\boldsymbol{x}_n, \boldsymbol{\mu}_k)$$

Иногда компактность измеряют как среднее попарное расстояние между всеми объектами внутри кластера.

$$\text{Cohesion}(C_k) = \frac{1}{|C_k|(|C_k|-1)} \sum_{n \in C_k} \sum_{m \in C_k, m \neq n} \rho(\boldsymbol{x}_n, \boldsymbol{x}_m)$$

Обратим внимание, что первая мера имеет вычислительную сложность $O(ND)$, в то время как вторая - уже $O(N^2D)$.

При этом обе меры поощряют выпуклые сферические формы кластеров.

Зависимость от числа кластеров

Представленные величины всегда уменьшаются при увеличении числа кластеров $K$, достигая нуля, когда каждый объект становится отдельным кластером!

Отделимость кластеров

Отделимость кластеров (cluster separation) характеризует, насколько далеко кластеры находятся друг от друга в пространстве признаков. Качественная кластеризация должна порождать различимые группы.

Межкластерная сумма квадратов (Between-cluster Sum of Squares, BSS) является измеряет разброс центроидов $\boldsymbol{\mu}_k$ относительно общего центра данных $\boldsymbol{\mu}$:

$$BSS = \sum_{k=1}^{K} N_k \rho^2(\boldsymbol{\mu}_k, \boldsymbol{\mu})$$

Размеры каждого кластера учитываются за счёт домножения расстояния на число объектов в кластере.

Минимальное межкластерное расстояние (minimum inter-cluster distance) характеризует «узкое место» кластеризации, выделяя самую неблагоприятно разделённую пару кластеров:

$$\text{Separation}_{min} = \min_{i \neq j} \rho(\boldsymbol{\mu}_i, \boldsymbol{\mu}_j)$$

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

Среднее межкластерное расстояние (average inter-cluster distance) вычисляется как среднее арифметическое расстояний между всеми возможными парами центроидов:

$$\text{Separation}_{avg} = \frac{2}{K(K-1)} \sum_{i=1}^{K} \sum_{j=i+1}^{K} \rho(\boldsymbol{\mu}_i, \boldsymbol{\mu}_j)$$

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

Взвешенное межкластерное расстояние (weighted inter-cluster distance) учитывает размер каждого кластера при оценке отделимости, оценивая в первую очередь разделимость крупных кластеров. Для этого в расчёте берётся взвешенное усреднение по числу объектов в каждом кластере:

$$\text{Separation}_{w} = \frac{1}{\sum_{i<j} N_i N_j} \sum_{i=1}^{K} \sum_{j=i+1}^{K} N_i N_j \rho(\boldsymbol{\mu}_i, \boldsymbol{\mu}_j)$$

Композитная мера качества

Для получения итоговой оценки разбиения компактность и отделимость объединяются в единую композитную меру в качестве которой выступает их отношение:

$$Q_1 = \frac{\text{Separation}}{\text{Cohesion}}$$ $$Q_2 = \frac{\text{Cohesion}}{\text{Separation}}$$

При этом если первая величина показывает качество разбиения, и её нужно максимизировать, то вторая - однородность разбиения, и её нужно минимизировать.

Индекс Дэвиса-Болдуина

Индекс Дэвиса-Болдуина (Davies–Bouldin Index [1]) оценивает среднее сходство между кластерами, основываясь на отношении их внутренних размеров к расстоянию между ними. Сначала для каждого кластера $C_i$ вычисляется внутренний разброс каждого кластера как среднее расстояние от от его центроида $\boldsymbol{\mu}_i$ до входящих в него объектов:

$$d_i = \frac{1}{|C_i|} \sum_{n \in C_i} \rho(\boldsymbol{\mu}_i, \boldsymbol{x}_n)$$

Затем для каждой пары кластеров $C_i$ и $C_j$ рассчитывается показатель их взаимного сходства $R_{ij}$. Он представляет собой сумму их внутренних разбросов, делённую на расстояние между их центроидами:

$$R_{ij} = \frac{d_i + d_j}{\rho(\boldsymbol{\mu}_i, \boldsymbol{\mu}_j)}$$

Для каждого кластера $C_i$ определяется значение $D_i$, соответствующее максимальному сходству среди всех остальных кластеров $C_j$ (наихудший случай разделения):

$$D_i = \max_{j \neq i} R_{ij}$$

Итоговый индекс Дэвиса-Болдуина вычисляется как среднее значение этих максимумов по всем $K$ кластерам:

$$DB = \frac{1}{K} \sum_{i=1}^{K} D_i$$

Этот индекс вычисляется за $O(DN+K^2)=O(DN)$ при $K^2<N$ (типичный случай). Поскольку мера опирается на центроиды, она смещена в сторону поиска сферических и выпуклых кластеров.

Индекс Данна

Индекс Данна (Dunn Index [2]) является одной из классических композитных метрик, которая сопоставляет минимальное расстояние между кластерами с их максимальным диаметром.

Для вычисления индекса сначала вводится понятие расстояния между двумя кластерами $C_i$ и $C_j$:

$$\delta(C_i, C_j) = \min_{\boldsymbol{x}_n \in C_i, \boldsymbol{x}_m \in C_j} \rho(\boldsymbol{x}_n, \boldsymbol{x}_m)$$

Затем определяется диаметр кластера $C_k$ как максимальное расстояние между любыми двумя его объектами:

$$\Delta(C_k) = \max_{\boldsymbol{x}_n, \boldsymbol{x}_m \in C_k} \rho(\boldsymbol{x}_n, \boldsymbol{x}_m)$$

Итоговый индекс Данна рассчитывается как отношение минимального межкластерного расстояния к максимальному диаметру среди всех кластеров:

$$D = \frac{\min_{i \neq j} \delta(C_i, C_j)}{\max_{k} \Delta(C_k)}$$

Чем выше значение индекса, тем качественнее считается кластеризация.

Метод не аппроксимирует расположение всего кластера его центроидом, поэтому способен корректно оценивать невыпуклые кластеры.

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

Вычислительная сложность составляет $O(DN^2)$.

Существуют и другие способы расчёта величин $\delta(C_i, C_j)$ и $\Delta(C_k)$.

Индекс Калинского-Харабаша

Индекс Калинского-Харабаша (Calinski-Harabasz Index [3]), также называемый критерием отношения дисперсий (variance ratio criterion), оценивает качество разбиения на основе отношения межкластеронго к внутрикластерному разбросу:

$$CH = \frac{\frac{1}{K - 1}\sum_{k=1}^{K} N_k \|\boldsymbol{\mu}_k - \boldsymbol{\mu}\|^2}{\frac{1}{N-K}\sum_{k=1}^{K} \sum_{n \in C_k} \|\boldsymbol{x}_n - \boldsymbol{\mu}_k\|^2}$$

Интерпретация меры

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

Нормировка числителя и знаменателя производится с учётом степень свободы распределения величин.

Данная формула позволяет проводить вычисления за один проход по данным, что обеспечивает временную сложность $O(ND)$.

Ограничение

Эта мера, как и предыдущие предвзята к выпуклости (сферичности) кластеров. Она может давать некорректно низкие оценки для групп сложной формы (например, вытянутых эллипсов или дуг), даже если они идеально отделены друг от друга.

Эквивалентная форма меры

Эквивалентно эту меру можно определить следующим образом:

$$CH = \frac{\frac{1}{K-1}\text{Tr}(B)}{\frac{1}{N-K}\text{Tr}(W)} = \frac{\text{Tr}(B)}{\text{Tr}(W)} \cdot \frac{N - K}{K - 1}$$

Использованы следующие обозначения:

$N,K$ - число объектов и кластеров;

Матрица межкластерного разброса (between-cluster scatter matrix) характеризует дисперсию центроидов кластеров относительно общего центра данных:

$$B = \sum_{k=1}^{K} N_k (\boldsymbol{\mu}_k - \boldsymbol{\mu})(\boldsymbol{\mu}_k - \boldsymbol{\mu})^T$$$$\boldsymbol{\mu} = \frac{1}{N} \sum_{n=1}^{N} \boldsymbol{x}_n$$

Матрица внутрикластерного разброса (within-cluster scatter matrix) и характеризует дисперсию объектов внутри их кластеров:

$$W = \sum_{k=1}^{K} \sum_{n \in C_k} (\boldsymbol{x}_n - \boldsymbol{\mu}_k)(\boldsymbol{x}_n - \boldsymbol{\mu}_k)^T$$

$\text{Tr}A$ обозначает след матрицы $A$ и равен сумме её элементов на главной диагонали:

$$\text{Tr}A=\sum_{i=1}^D A_{ii} \quad \text{для любой матрицы }A\in\mathbb{R}^{D\times D}$$

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

Используя свойство линейности следа:

$$\text{Tr}(\alpha A+\beta B) = \alpha \text{Tr}(A)+\beta \text{Tr}(B),$$

а также свойство

$$\text{Tr}(\boldsymbol{v}\boldsymbol{v}^T) = \sum_{i=1}^{D} \boldsymbol{v}^i \boldsymbol{v}^i = \|\boldsymbol{v}\|^2,$$

можно вывести эквивалентный численно эффективный способ расчёта меры Калинского-Харабаша:

$$\begin{aligned} \text{Tr}(B) &= \text{Tr} \left( \sum_{k=1}^{K} N_k (\boldsymbol{\mu}_k - \boldsymbol{\mu})(\boldsymbol{\mu}_k - \boldsymbol{\mu})^T \right) \\ &= \sum_{k=1}^{K} N_k \text{Tr} \left( (\boldsymbol{\mu}_k - \boldsymbol{\mu})(\boldsymbol{\mu}_k - \boldsymbol{\mu})^T \right) \\ &= \sum_{k=1}^{K} N_k \|\boldsymbol{\mu}_k - \boldsymbol{\mu}\|^2 \end{aligned}$$$$\begin{aligned} \text{Tr}(W) &= \text{Tr} \left( \sum_{k=1}^{K} \sum_{n \in C_k} (\boldsymbol{x}_n - \boldsymbol{\mu}_k)(\boldsymbol{x}_n - \boldsymbol{\mu}_k)^T \right) \\ &= \sum_{k=1}^{K} \sum_{n \in C_k} \text{Tr} \left( (\boldsymbol{x}_n - \boldsymbol{\mu}_k)(\boldsymbol{x}_n - \boldsymbol{\mu}_k)^T \right) \\ &= \sum_{k=1}^{K} \sum_{n \in C_k} \|\boldsymbol{x}_n - \boldsymbol{\mu}_k\|^2 \end{aligned}$$

Следовательно индекс эквивалентно можно записать в виде

$$CH = \frac{\frac{1}{K - 1}\sum_{k=1}^{K} N_k \|\boldsymbol{\mu}_k - \boldsymbol{\mu}\|^2}{\frac{1}{N-K}\sum_{k=1}^{K} \sum_{n \in C_k} \|\boldsymbol{x}_n - \boldsymbol{\mu}_k\|^2}$$

Силуэт

Силуэт (Silhouette [4]) — это коэффициент $s_n$, показывающий, насколько объект $\boldsymbol{x}_n$ вписывается в собственный кластер по сравнению с ближайшим соседним кластером.

Для этого рассчитывается среднее расстояние от $\boldsymbol{x}_n$ до объектов кластера $C_i$, которому $\boldsymbol{x}$ принадлежит:

$$a_n = \frac{1}{|C_i| - 1} \sum_{\boldsymbol{x}_m \in C_i, n \neq m} \rho(\boldsymbol{x}_n, \boldsymbol{x}_m)$$

Затем рассчитывается среднее расстояние до объектов ближайшего чужого кластера $C_j$ (которому $\boldsymbol{x}_n$ не принадлежит):

$$b_n = \min_{j \neq i} \frac{1}{|C_j|} \sum_{\boldsymbol{x}_l \in C_j} \rho(\boldsymbol{x}_n, \boldsymbol{x}_l)$$

Коэффициент силуэта объекта $\boldsymbol{x}_n$ определяется как:

$$s_n = \frac{b_n - a_n}{\max(a_n, b_n)}$$

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

$$s = \frac{1}{N}\sum_{n=1}^N s_n$$

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

Вычислительная сложность расчёта этой меры составляет $O(DN^2)$, что ограничивает применимость метода для больших выборок. В последнем случае коэффициент силуэта нужно приближённо вычислять по подвыборке либо использовать упрощённый индекс силуэта (simplified silhouette index [5]), в котором $a_n$ и $b_n$ вычисляются как расстояния до центроида своего и ближайшего чужого кластера:

$$a_n = \rho(\boldsymbol{x}_n, \boldsymbol{\mu}_i), \\ b_n = \min_{j \neq i} \rho(\boldsymbol{x}_n, \boldsymbol{\mu}_j)$$

В последнем случае сложность вычислений снижается до $O(DNK)$.

Литература

1. Davies D. L., Bouldin D. W. A cluster separation measure //IEEE transactions on pattern analysis and machine intelligence. – 2009. – №. 2. – С. 224-227.
2. Dunn J. C. Well-separated clusters and optimal fuzzy partitions // Journal of Cybernetics. — 1974. — Vol. 4, no. 1. — P. 95–104.
3. Caliński T., Harabasz J. A dendrite method for cluster analysis //Communications in Statistics-theory and Methods. – 1974. – Т. 3. – №. 1. – С. 1-27.
4. Rousseeuw, P. J. Silhouettes: A graphical aid to the interpretation and validation of cluster analysis // Journal of Computational and Applied Mathematics. 1987. Vol. 20. P. 53–65.
5. Vendramin L., Campello R. J. G. B., Hruschka E. R. Relative clustering validity criteria: A comparative overview //Statistical analysis and data mining: the ASA data science journal. – 2010. – Т. 3. – №. 4. – С. 209-235.