Оценка качества в задаче кластеризации

Проблема оценки качества в задаче кластеризации трудноразрешима, как минимум, по двум причинам:

• Не существует оптимального алгоритма кластеризации. Иными словами, различные алгоритмы (или различные конфигурации одного алгоритма) выдают разные разделения на кластеры, и ни одно из них не является лучшим во всех ситуациях.
• Многие алгоритмы кластеризации не способны определить настоящее количество кластеров в данных. Чаще всего количество кластеров подается на вход алгоритма и подбирается несколькими запусками алгоритма.

Методы оценки качества кластеризации

Метод (индекс) оценки качества кластеризации (англ. cluster validity index, CVI) — инструментарий для количественной оценки результатов кластеризации.

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

• Внешние (англ. Internal) метрики основаны на сравнении результата кластеризации с априори известным разделением на классы.
• Внутренние (англ. External) метрики отображают качество кластеризации только по информации в данных.
• Относительные (англ. Relative) метрики основаны на оценивании полученного разделения на кластеры относительно результатов работы другого алгоритма.

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

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

Данные метрики используют дополнительные знания о кластеризуемом множестве: распределение по кластерам, количество кластеров и т.д.

Rand Index

Рассмотрим пары [math](x_i, x_j)[/math] из элементов кластеризуемого множества [math]X[/math]. Подсчитаем количество пар, в которых:

• Элементы принадлежат одному кластеру и одному классу — [math]TP[/math]
• Элементы принадлежат одному кластеру, но разным классам — [math]TN[/math]
• Элементы принадлежат разным кластерам, но одному классу — [math]FP[/math]
• Элементы принадлежат разным кластерам и разным классам — [math]FN[/math]

Индекс Rand оценивает, насколько много из тех пар элементов, которые находились в одном классе, и тех пар элементов, которые находились в разных классах, сохранили это состояние после кластеризации алгоритмом.

[math] Rand = \dfrac{TP+FN}{TP+TN+FP+FN} [/math]

Имеет область определения от 0 до 1, где 1 - полное совпадение кластеров с заданными классами, а 0 - отсутствие совпадений.

Adjusted Rand Index

Дано множество [math]S[/math] из [math]n[/math] элементов, и два разделения на кластеры [math]X = \{ X_1, X_2, \ldots , X_r \}[/math] и [math]Y = \{ Y_1, Y_2, \ldots , Y_s \}[/math], совпадения между [math]X[/math] и [math]Y[/math] могут быть отражены в таблице сопряженности [math]\left[n_{ij}\right][/math], где каждое [math]n_{ij}[/math] обозначает число объектов, входящих как в[math]X_i[/math], так и в [math]Y_j[/math] : [math]n_{ij}=|X_i \cap Y_j|[/math].

[math]\begin{array}{c|cccc|c} {{} \atop X}\!\diagdown\!^Y & Y_1& Y_2& \ldots& Y_s& \text{Sums} \\ \hline X_1& n_{11}& n_{12}& \ldots& n_{1s}& a_1 \\ X_2& n_{21}& n_{22}& \ldots& n_{2s}& a_2 \\ \vdots& \vdots& \vdots& \ddots& \vdots& \vdots \\ X_r& n_{r1}& n_{r2}& \ldots& n_{rs}& a_r \\ \hline \text{Sums}& b_1& b_2& \ldots& b_s& \end{array}[/math]

Тогда Adjusted Rand Index вычисляется по формуле:

[math]\overbrace{ARI}^\text{Adjusted Index} = \frac{ \overbrace{\sum_{ij} \binom{n_{ij}}{2}}^\text{Index} - \overbrace{[\sum_i \binom{a_i}{2} \sum_j \binom{b_j}{2}] / \binom{n}{2}}^\text{Expected Index} }{ \underbrace{\frac{1}{2} [\sum_i \binom{a_i}{2} + \sum_j \binom{b_j}{2}]}_\text{Max Index} - \underbrace{[\sum_i \binom{a_i}{2} \sum_j \binom{b_j}{2}] / \binom{n}{2}}_\text{Expected Index} }[/math]

где [math]n_{ij}, a_i, b_j[/math] — значения из таблицы сопряженности.

В отличие от обычного Rand Index, Adjusted Rand Index может принимать отрицательные значения, если [math]Index \lt Expected Index[/math].

Jaccard Index

Индекс Жаккара похож на Rand Index, только не учитывает пары элементов находящиеся в разные классах и разных кластерах ([math]FN[/math]).

[math] Jaccard = \dfrac{TP}{TP+TN+FP} [/math]

Имеет область определения от 0 до 1, где 1 - полное совпадение кластеров с заданными классами, а 0 - отсутствие совпадений.

Folkes and Mallows Index

Индекс Fowlkes-Mallows используется для определения сходства между двумя кластерами.

[math] FM = \sqrt{ \dfrac{TP}{TP+TN} \cdot \dfrac{TP}{TP+FP} } [/math]

Более высокое значение индекса означает большее сходство между кластерами. Этот индекс также хорошо работает на зашумленных данных.

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

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

Компактность кластеров (Cluster Cohesion)

Идея данного метода в том, что чем ближе друг к другу находятся объекты внутри кластеров, тем лучше разделение.

Таким образом, необходимо минимизировать внутриклассовое расстояние, например, сумму квадратов отклонений (within cluster sum of squares):

[math] WSS = \sum \limits_{j=1}^{M} \sum \limits_{i = 1}^{|C_j|} (x_{ij} - \overline{x_j})^2 [/math], где [math]M[/math] - количество кластеров.

Отделимость кластеров (Cluster Separation)

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

Поэтому здесь стоит задача максимизации суммы квадратов отклонений (between cluster sum of squares):

[math] BSS = n \cdot \sum \limits_{j=1}^{M} (\overline{x_{j}} - \overline{x})^2 [/math], где [math]M[/math] - количество кластеров.

Hubert Г statistic

Данная метрика отражает среднее расстояние между объектами разных кластеров:

[math] Г = \dfrac{1}{M} \sum \limits_{i=1}^{N-1} \sum \limits_{i=i+1}^{N} P(i, j) \cdot Q(i, j), [/math]

где [math]M = n*(n-1)/2[/math], [math]P(i, j)[/math] - матрица близости, а

[math]Q(i, j) = \begin{cases} 0, & \mbox{если x(i) и x(j) лежат в одном кластере} \\ 1, & \mbox{в другом случае } \\ \end{cases} [/math]

Можно заметить, что два объекта влияют на [math]Г[/math], только если они находятся в разных кластерах.

Чем больше значение метрики - тем лучше.

Относительные оценки качества

Индекс Данна (Dunn Index)

Индекс Данна имеет множество вариаций, оригинальная версия выглядит следующим образом:

[math] D(C) = \dfrac{ min_{c_k \in C} \{ min_{c_l \in C \setminus c_k} \{ \delta(c_k, c_l) \} \} }{ max_{c_k \in C} \{ \Delta(c_k) \} } [/math],

где:

[math]\delta[/math] - межкластерное расстояние, [math]\delta(c_k, c_k) = min_{x_i \in c_k, y_j \in c_l} \|x_i - x_j\|[/math],

[math]\Delta(c_k)[/math] - диаметр кластера, [math]\Delta(c_k) = max_{x_i,x_j \in c_k} \|x_i - x_j\|[/math].

Силуэт (Silhouette)

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

Оценка для всей кластерной структуры:

[math] Sil(С) = \dfrac{1}{N} \sum_{c_k \in C} \sum_{x_i \in c_k} \dfrac{ b(x_i, c_k) - a(x_i, c_k) }{ max \{ a(x_i, c_k), b(x_i, c_k) \} } [/math],

где:

[math] a(x_i, c_k) = \dfrac{1}{|c_k|} \sum_{x_j \in c_k} \|x_i - x_j\| [/math] - среднее расстояние от [math]x_i \in c_k[/math] до других объектов из кластера [math]c_k[/math] (компактность),

[math] b(x_i, c_k) = min_{c_l \in C \setminus c_k } \{ \dfrac{1}{|c_l|} \sum_{x_j \in c_l} \|x_i - x_j\| [/math] - среднее расстояние от [math]x_i \in c_k[/math] до объектов из другого кластера [math]c_l: k \neq l[/math] (отделимость).

Можно заметить, что

[math] -1 \le Sil(C) \le 1 [/math].

Чем ближе данная оценка к 1, тем лучше.

Есть также упрощенная вариация силуэта: [math]a(x_i, c_k)[/math] и [math]b(x_i, c_k)[/math] вычисляются через центры кластеров.

Calinski–Harabasz index

[math] CH(C) = \dfrac{ N-K }{ K-1 } \cdot \dfrac{ sum_{c_k \in C} |c_k| \cdot \| \overline{c_k} - \overline{X} \| }{ sum_{c_k \in C} sum_{ x_i \in c_k } \| x_i - \overline{c_k} \| } [/math]

Компактность основана на расстоянии от точек кластера до их центроидов, а разделимость - на расстоянии от центроид кластеров до глобального центроида.

C-Index

C-Index - нормализованная оценка компактности:

[math] CI(C) = \dfrac{ S(C) - S_{min}(C) }{ S_{max}(C) - S_{min}(C)} [/math],

где:

[math] S(C) = \sum \limits_{c_k \in C} \sum \limits_{x_i, x_j \in c_k} \| x_i - x_j \| [/math],

[math]S_{min}(C) (S_max(C))[/math] - сумма [math]\dfrac{ |c_k|\cdot(|c_k| - 1) }{2}[/math] минимальных (максимальных) расстояний между всех парами объектов во всем датасете.

Davies–Bouldin Index

Это, возможно, одна из самых используемых мер оценки качества кластеризации.
Она вычисляет компактность как расстояние от объектов кластера до их центроидов, а отделимость - как расстояние между центроидами.

[math] DB(C) = \dfrac{1}{K} \sum \limits_{c_k \in C} \max \limits_{c_l \in C \setminus c_k} \Big\{ \dfrac{ S(c_k)+S(c_l) }{ \| \overline{c_k} - \overline{c_l} \| } \Big\} [/math],

где:

[math] S(c_k) = \dfrac{ 1 }{ |c_k| } \sum \limits_{x_i \in c_k} \|x_i - \overline{c_k}\| [/math]

Существует еще одна вариация данной метрики, которая была предложена автором вместе с основной версией:

[math] DB^*(C) = \dfrac{1}{K} \sum \limits_{c_k \in C} \dfrac { \max \limits_{c_l \in C \setminus c_k} \{ S(c_k)+S(c_l) \} } { \min \limits_{c_l \in C \setminus c_k} \{ \| \overline{c_k} - \overline{c_l} \| \} } [/math]

Score function

[math] SF(C) = 1 - \dfrac{ 1 }{ e^{e^{bcd(C) + wcd(C)}} } [/math],

где:

[math] bcd(C) = \dfrac{ \sum \limits_{c_k \in C} |c_k| \cdot \|\overline{c_k} - \overline{X}\| }{ N \times K } [/math],

[math] wcd(C) = \sum \limits_{c_k \in C} \dfrac{ 1 }{ |c_k| } \sum \limits_{x_i \in c_k} \|x_i - \overline{c_k}\| [/math]

Сравнение

По результатам исследования на искусственных датасетах наилучшие результаты показали индексы Silhouette(Sil), Davies–Bouldin*(DB*) и Calinski–Harabasz(CH). На реальных датасетах лучше всех проявил себя Score function. Однако, на определенных данных другие индексы могут показать лучшие результаты (так, например, на зашумленных данных Calinski–Harabasz(CH) дает оценки значительно хуже).

См. также

• Кластеризация

Источники информации

1. Wikipedia — Category:Clustering criteria
2. Сивоголовка Е. В. Методы оценки качества четкой кластеризации
3. Cluster Validation
4. An extensive comparative study of cluster validity indices