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

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

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

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

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

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

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

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

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

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

Обозначения

Дано множество [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]FP[/math]
  • Элементы принадлежат разным кластерам, но одному классу — [math]FN[/math]
  • Элементы принадлежат разным кластерам и разным классам — [math]TN[/math]

Индекс Rand

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

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

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

Индекс Adjusted Rand

[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, индекс Adjusted Rand может принимать отрицательные значения, если [math]Index \lt Expected Index[/math].

Индекс Жаккара (англ. Jaccard Index)

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

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

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

Индекс Фоулкса – Мэллова (англ. Fowlkes-Mallows Index)

Индекс Фоулкса – Мэллова используется для определения сходства между двумя кластерами.

[math] FM = \sqrt{ \dfrac{TP}{TP+FP} \cdot \dfrac{TP}{TP+FN} } [/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

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

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

Minkowski Score

[math] MS = \dfrac{ \sqrt{ \sum_i \binom{a_i}{2} + \sum_j \binom{b_j}{2} - 2\sum_{ij} \binom{ n_{ij} }{ 2 } } }{ \sqrt{ \sum_j \binom{b_j}{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 \max_j p_{ij} [/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_l) = min_{x_i \in c_k, x_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].

Обобщенный Индекс Данна (gD31, gD41, gD51, gD33, gD43, gD53)

Все эти вариации являются комбинациями 3 вариантов вычисления оценки разделения [math]\delta[/math] и оценки компактности [math]\Delta[/math]

Оценки разделения:

[math]\delta^3(c_k, c_l) = \dfrac{1}{|c_k| * |c_l|} \sum_{x_i \in c_k} \sum_{x_j \in c_l} \|x_i - x_j\| [/math],
[math]\delta^4(c_k, c_l) = \|\overline{c_k} - \overline{c_l}\| [/math],
[math]\delta^5(c_k, c_l) = \dfrac{1}{|c_k| + |c_l|} (\sum_{x_i \in c_k} \|x_i - \overline{c_k}\| + \sum_{x_j \in c_l} \|x_j - \overline{c_l}\|) [/math].

Оценки компактности:

[math]\Delta^1(c_k) = \Delta(c_k) [/math],
[math]\Delta^3(c_k) = \dfrac{2}{|c_k|} \sum_{x_i \in c_k} \|x_i - \overline{c_k}\| [/math].

Обобщенный индекс Данна, как и обычный, должен возрастать вместе с улучшением качества кластеризации.

Индекс S_Dbw

Основан на вычислении Евклидовой нормы

[math]\ \|x\| = (x^Tx)^(1/2) [/math]

и стандартных отклонений

[math] \sigma(X) = \dfrac{1}{|X|} \sum_{x_i \in X} (x_i - \overline{x}) ^ 2 [/math],
[math] stdev(C) = \dfrac{1}{K}\sqrt{\sum_{c_k \in C} \|\sigma(c_k)\|} [/math].

Сам индекс определяется формулой:

[math] SDbw(C) = \dfrac{1}{K} \sum_{c_k \in C} \dfrac{\|\sigma(c_k)\|}{\|\sigma(X)\|} + \dfrac{1}{K(K-1)} \sum_{c_k \in C} \sum_{c_l \in C \setminus c_k} \dfrac{den(c_k,c_l)}{max(den(c_k),den(c_l))} [/math].

Здесь

[math] den(c_k) = \sum_{x_i \in c_k} f(x_i, \overline{c_k}) [/math],
[math] den(c_k, c_l) = \sum_{x_i \in c_k \cup c_l} f(x_i, \dfrac{\overline{c_k} + \overline{c_l}}{2}) [/math],
[math] f(x_i, c_k) = 0 [/math], если [math] \|x_i - \overline{c_k}\| \gt stdev(C) [/math] и [math]1[/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

[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

Индекс C представляет собой нормализованную оценку компактности:

[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] минимальных (максимальных) расстояний между парами всех объектов во всем датасете.

Индекс Дэвиcа-Болдуина (англ. 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]

C-индекс и индекс Дэвиcа-Болдуина должны минимизироваться для роста кластеризации.

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]

Чтобы функция оценки была эффективной, она должна максимизировать bcd, минимизировать wcd и быть ограниченной. Чем больше данный индекс, тем выше качество.

Индекс Gamma

[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

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

[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].

Индекс CS

Был предложен в области сжатия изображений, но может быть успешно адаптирован для любого другого окружения. Он оценивает компактность по диаметру кластера, а отделимость — как дистанцию между ближайшими элементами двух кластеров.

[math] CS(C) = \dfrac{\sum_{c_k \in C} \{ 1 / |c_k| \sum_{x_i \in c_k} \max_{x_j \in c_k}\{\|x_i - x_j\|\} \}}{\sum_{c_k \in C} \min_{c_l \in C \setminus c_k} \{\|\overline{c_k} - \overline{c_l}\| \}} [/math].

Чем меньше значение данного индекса, тем выше качество кластеризации.

Индекс Sym

[math] Sym(C) = \dfrac {\max_{c_k, c_l \in C} \{\|\overline{c_k} - \overline{c_l}\|\}}{K\sum_{c_k \in C}\sum_{x_i \in c_k} \overset{\ast}{d_{ps}}(x_i, c_k)} [/math].

Здесь [math]\overset{\ast}{d_{ps}}(x_i, c_k)[/math] — дистанция симметрии для точки [math]x_i[/math] из кластера [math]c_k[/math].

Чем выше данное значение, тем лучше.

Индексы SymDB, SymD, Sym33

Модифицируют оценку компактности для индексов Дэвиса-Боулдина, Данна и gD33 соответственно.

SymDB вычисляется аналогично DB с изменением вычисления [math]S[/math] на:

[math] S(c_k) = \dfrac{1}{|c_k| \sum_{x_i \in c_k} \overset{\ast}{d_{ps}}(x_i, c_k)} [/math].

Данная оценка должна уменьшаться для улучшения качества кластеризации.

В SymD переопределена функция [math]\Delta[/math]:

[math] \Delta(c_k) = \max_{x_i \in c_k} \{\overset{\ast}{d_{ps}}(x_i, c_k)\} [/math].

в Sym33 аналогично SymD переопределена [math]\Delta[/math]:

[math] \Delta(c_k) = \dfrac{2}{|c_k| \sum_{x_i \in c_k} \overset{\ast}{d_{ps}}(x_i, c_k)} [/math].

Последние две оценки должны расти для улучшения качества кластеризации.

Negentropy increment

В отличие от подавляющего большинства других оценок, не основывается на сравнении компактности и разделимости. Определяется следующим образом:

[math] NI(C) = \dfrac{1}{2} \sum_{c_k \in C} p(c_k)log|cov_{c_k}| - \dfrac{1}{2}log|cov_X| - \sum_{c_k \in C} p(c_k)log p(c_k) [/math].

Здесь [math]p(c_k) = |c_k| / N[/math], [math]|cov_{c_k}|[/math] - определитель ковариационной матрицы кластера [math]c_k[/math], [math]|cov_X|[/math] - определитель ковариационной матрицы всего датасета.

Данная оценка должна уменьшаться пропорционально росту качества кластеризации.

Индекс SV

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

[math] SV(C) = \dfrac{\sum_{c_k \in C} \min_{c_l \in C \setminus c_k} \{\|\overline{c_k} - \overline{c_l}\|\}}{\sum_{c_k \in C} 10 / |c_k| \sum \max_{x_i \in c_k}(0.1 * |c_k|) * \|\overline{x_i} - \overline{c_k}\|} [/math].

Данная оценка должна увеличиваться.

Индекс OS

Отличается от предыдущей оценки усложненным способом вычисления оценки разделимости.

[math] OS(C) = \dfrac{\sum_{c_k \in C} \sum_{x_i \in c_k} ov(x_i, c_k)}{\sum_{c_k \in C} 10 / |c_k| \sum \max_{x_i \in c_k}(0.1 * |c_k|) * \|\overline{x_i} - \overline{c_k}\|} [/math].

Где

[math] ov(x_i, c_k) = \dfrac{a(x_i, c_k)}{b(x_i, c_k)} [/math].

при [math] \dfrac{b(x_i, c_k) - a(x_i, c_k)}{b(x_i, c_k) + a(x_i, c_k)} \lt 0.4 [/math], и [math]0[/math] в ином случае.

Функции [math]a[/math] и [math]b[/math] определены следующим образом:

[math] a(x_i, c_k) = \dfrac{1}{|c_k|\sum_{x_j \in c_k}\|x_i - x_j\|} [/math].
[math] b(x_i, c_k) = \dfrac{1}{|c_k|\sum_{x_j \notin c_k}\ \min(|c_k)\|x_i - x_j\|} [/math].

Данная оценка, как и предыдущая, должна возрастать.

Сравнение

Не существует лучшего метода оценки качества кластеризации. Однако, в рамках исследования[1] была предпринята попытка сравнить существующие меры на различных данных. Полученные результаты показали, что на искусственных датасетах наилучшим образом себя проявили индексы [math]Silhouette[/math], [math]DB^*[/math] и [math]Calinski-Harabasz[/math]. На реальных датасетах лучше всех показал себя [math]Score-function[/math].

В Таблице 1 приведены оценки сложности мер качества кластеризации ([math]n[/math] — число объектов в рассматриваемом наборе данных):

Таблица 1 — Оценка сложности для 19 мер качества кластеризации.
[math]Davies-Bouldin[/math] [math]O(n\log{n})[/math] [math]CS[/math] [math]O(n\log{n})[/math]
[math]Dunn[/math] [math]O(n^2)[/math] [math]DB^*[/math] [math]O(n\log{n})[/math]
[math]Calinski-Harabasz[/math] [math]O(n\log{n})[/math] [math]SF[/math] [math]O(n)[/math]
[math]Sillhouette[/math] [math]O(n^2)[/math] [math]Sym[/math] [math]O(n^2)[/math]
[math]gD31[/math] [math]O(n^2)[/math] [math]COP[/math] [math]O(n^2)[/math]
[math]gD41[/math] [math]O(n^2)[/math] [math]SV[/math] [math]O(n\log{n})[/math]
[math]gD51[/math] [math]O(n^2)[/math] [math]OS[/math] [math]O(n^2\log{n})[/math]
[math]gD33[/math] [math]O(n^2)[/math] [math]SDbw[/math] [math]O(n\log{n})[/math]
[math]gD43[/math] [math]O(n^2)[/math] [math]C-index[/math] [math]O(n^2\log{n})[/math]
[math]gD53[/math] [math]O(n\log{n})[/math]

Из всех рассмотренных мер, меры [math]Sym[/math], [math]gD41[/math], [math]OS[/math] и [math]COP[/math] наиболее полно соответствуют когнитивному представлению асессоров о качестве кластеризации[2].

См. также

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

Примечания