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

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

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

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

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

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

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

  • Внешние (англ. 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.

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

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

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