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

Материал из Викиконспекты
Перейти к: навигация, поиск

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

  • Теорема невозможности Клейнберга — не существует оптимального алгоритма кластеризации.
  • Многие алгоритмы кластеризации не способны определить настоящее количество кластеров в данных. Чаще всего количество кластеров подается на вход алгоритма и подбирается несколькими запусками алгоритма.

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

Метод оценки качества кластеризации — инструментарий для количественной оценки результатов кластеризации.

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

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

Внешние метрики оценки качества[править]

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

Обозначения[править]

Дано множество [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& n \end{array}[/math]

Пусть [math]p_{ij} = \dfrac{ n_{ij} }{ n }, p_{i} = \dfrac{ a_{i} }{ n }, p_{j} = \dfrac{ b_{j} }{ n } [/math].

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

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

Rand Index[править]

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

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

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

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]

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

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], только если они находятся в разных кластерах.

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

Phi Index[править]

Классическая мера корреляции между двумя переменными:

[math] \Phi = \dfrac{ TP \times FN - TN \times FP }{ (TP + TN)(TP + FP)(FN + FP)(FN + TN) } [/math]

Minkowski Score[править]

[math] MS = \dfrac{ \sqrt{ \sum_i \binom{a_i}{2} + \sum_j \binom{b_i}{2} - 2\sum_{ij} \binom{ n_{ij} }{ 2 } } }{ \sqrt{ \sum_j \binom{b_i}{2} } } [/math]

Goodman-Kruskal Index[править]

[math] GK = \sum_i p_i(1 - \max_j \dfrac{ p_{ij} }{ p_i }) [/math]

Entropy[править]

Энтропия измеряет "чистоту" меток классов:

[math] E = - \sum_i p_i ( \sum_j \dfrac{ p_{ij} }{ p_i } log( \dfrac{ p_{ij} }{ p_i } ) ) [/math]

Стоит отметить, что если все кластера состоят из объектов одного класса, то энтропия равна 0.

Purity[править]

Чистота ставит в соответствие кластеру самый многочисленный в этом кластере класс.

[math] P = \sum_i p_i ( \max_j \dfrac{ p_{ij} }{ p_i } ) [/math]

Чистота находится в интервале [0, 1], причём значение = 1 отвечает оптимальной кластеризации.

F-мера[править]

F-мера представляет собой гармоническое среднее между точностью (precision) и полнотой (recall).

[math] F = \sum_j p_j \max_i \big\lbrack 2 \dfrac{ p_{ij} }{ p_i } \dfrac{ p_{ij} }{ p_j } \big/ (\dfrac{ p_{ij} }{ p_i } + \dfrac{ p_{ij} }{ p_j }) \big\rbrack [/math]

Variation of Information[править]

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

[math] VI = - \sum_i p_i \log p_i - \sum_i p_j log p_j - 2 \sum_i \sum_j p_{ij} \log \dfrac{ p_{ij} }{ p_i p_j } [/math]

Внутренние метрики оценки качества[править]

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

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

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

Таким образом, необходимо минимизировать внутриклассовое расстояние, например, сумму квадратов отклонений:

[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)[править]

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

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

[math] BSS = n \cdot \sum \limits_{j=1}^{M} (\overline{x_{j}} - \overline{x})^2 [/math], где [math]M[/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]

Gamma Index[править]

[math] G(C) = \dfrac{ \sum_{c_k \in C} \sum_{x_i,x_j \in c_k} |c_k| \cdot dl(x_i, x_j) }{ n_w (\binom{N}{2} - n_w) } [/math]

где:

[math]dl(x_i,x_j)[/math] — число пар [math](x_k, x_l) \in X[/math] таких, что (1) [math]x_k[/math] и [math]x_l[/math] принадлежат разным кластерам, и (2) [math]\|x_k - x_l\| \lt \|x_i - x_j\|[/math],
[math] n_w = \sum_{c_k \in C} \binom{|c_k|}{2} [/math]

COP Index[править]

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

[math] COP(C) = \dfrac{1}{N} \sum \limits_{c_k \in C} |c_k| \dfrac{ 1/|c_k| \sum_{x_i \in c_k} \| x_i - \overline{c_k} \| }{ \min_{x_i \notin c_k} \max_{x_j \in c_k} \| x_i - x_j\| } [/math]

Сравнение[править]

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

См. также[править]

Источники информации[править]

  1. Wikipedia — Category:Clustering criteria
  2. Сивоголовко Е. В. Методы оценки качества четкой кластеризации
  3. Cluster Validation
  4. Halkidi, M., Batistakis, Y., Vazirgiannis, M., 2001. On clustering validation techniques. Journal of intelligent information systems, 17(2-3), pp.107-145.
  5. Pal, N.R., Biswas, J., 1997. Cluster validation using graph theoretic concepts. Pattern Recognition, 30(6), pp.847-857.

Примечания[править]