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

Изучим внутренние меры оценки качества кластеризации (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$ - центроиды кластеров, вычисляемые как средние по объектам соответствующих кластеров;

• $\boldsymbol{\mu}=\frac{1}{N}\sum_{n=1}^N\boldsymbol{x}_n$ - среднее от всех объектов;

• $\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$ вычисляется внутренний разброс каждого кластера:

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

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

$$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) = \text{Tr}(\boldsymbol{v}^T\boldsymbol{v}) =\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$:

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

Затем рассчитывается среднее расстояние от $\boldsymbol{x}_n$ до объектов ближайшего чужого кластера $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.