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

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

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

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

Метод (индекс) оценки качества кластеризации (англ. 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] вычисляются через центры кластеров.

См. также

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

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

1. Arbelaitz, O.; Gurrutxaga, I.; Muguerza, J.; Pérez, J.M.; Perona, I. An extensive comparative study of cluster validity indices. Pattern Recognit. 2013, 46, 243–256.
2. Wikipedia — Category:Clustering criteria
3. Сивоголовка Е. В. Методы оценки качества четкой кластеризации