187
правок
Изменения
Новая страница: «В машинном обучении различают оценки качества для задачи классификации и регрессии. При…»
В машинном обучении различают оценки качества для задачи классификации и регрессии. Причем оценка задачи классификации часто значительно сложнее, чем оценка регрессии.
== Оценки качества классификации ==
Перед переходом к самим метрикам необходимо ввести важную концепцию для описания этих метрик в терминах ошибок классификации — [[матрица ошибок|confusion matrix]] (матрица ошибок).
Допустим, что у нас есть два класса и алгоритм, предсказывающий принадлежность каждого объекта одному из классов, тогда матрица ошибок классификации будет выглядеть следующим образом:
[[Файл:Confusion_matrix.png|500px]]
Здесь '''a(х)''' — это ответ алгоритма на объекте, а '''y''' — истинная метка класса на этом объекте.
Таким образом, ошибки классификации бывают двух видов: False Negative (FN) и False Positive (FP).
'''Проблема оценки качества в [[Кластеризация|задаче кластеризации]]''' трудноразрешима, как минимум, по двум причинам:
* [[Кластеризация#Теорема невозможности Клейнберга|Теорема невозможности Клейнберга]] {{---}} не существует оптимального алгоритма кластеризации.
* Многие алгоритмы кластеризации не способны определить настоящее количество кластеров в данных. Чаще всего количество кластеров подается на вход алгоритма и подбирается несколькими запусками алгоритма.
== Методы оценки качества кластеризации ==
'''Метод оценки качества кластеризации''' {{---}} инструментарий для количественной оценки результатов кластеризации.
Принято выделять две группы методов оценки качества кластеризации:
* '''Внешние''' (англ. ''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 ===
Индекс Rand оценивает, насколько много из тех пар элементов, которые находились в одном классе, и тех пар элементов, которые находились в разных классах, сохранили это состояние после кластеризации алгоритмом.
: <math>
Rand = \dfrac{TP+FN}{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> {{---}} значения из таблицы сопряженности.
В отличие от обычного [[{{NAMESPACE}}:{{PAGENAME}}#Индекс_Rand|индекса Rand]], индекс Adjusted Rand может принимать отрицательные значения, если <math>Index < Expected Index</math>.
=== Индекс Жаккара (англ. Jaccard Index) ===
Индекс Жаккара похож на [[#Индекс_Rand|Индекс Rand]], только не учитывает пары элементов находящиеся в разные классах и разных кластерах (<math>FN</math>).
: <math>
Jaccard = \dfrac{TP}{TP+TN+FP}
</math>
Имеет область определения от 0 до 1, где 1 {{---}} полное совпадение кластеров с заданными классами, а 0 {{---}} отсутствие совпадений.
=== Индекс Фоулкса – Мэллова (англ. Fowlkes-Mallows Index) ===
Индекс Фоулкса – Мэллова используется для определения сходства между двумя кластерами.
: <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 ===
Классическая мера корреляции между двумя переменными:
: <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_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}\| > 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) ===
Это, возможно, одна из самых используемых мер оценки качества кластеризации.<br/>
Она вычисляет компактность как расстояние от объектов кластера до их центроидов, а отделимость - как расстояние между центроидами.
: <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>
Чем больше данный индекс, тем выше качество.
=== Индекс 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\| < \|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)} < 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>.
Данная оценка, как и предыдущая, должна возрастать.
== Сравнение ==
Не существует лучшего метода оценки качества кластеризации. Однако, в рамках исследования<ref>[https://www.sciencedirect.com/science/article/abs/pii/S003132031200338X An extensive comparative study of cluster validity indices]</ref> была предпринята попытка сравнить существующие меры на различных данных. Полученные результаты показали, что на искусственных датасетах наилучшим образом себя проявили индексы <math>Silhouette</math>, <math>DB^*</math> и <math>Calinski-Harabasz</math>. На реальных датасетах лучше всех показал себя <math>Score-function</math>.
В Таблице 1 приведены оценки сложности мер качества кластеризации (<math>n</math> — число объектов в рассматриваемом наборе данных):
{|class="wikitable" style="margin:auto; clear:both;
|+ Таблица 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> наиболее полно соответствуют когнитивному представлению асессоров о качестве кластеризации<ref>[https://ieeexplore.ieee.org/abstract/document/7891855 Towards cluster validity index evaluation and selection]</ref>.
== См. также ==
* [[Кластеризация]]
* [[Оценка качества в задачах классификации и регрессии]]<sup>[на 28.01.19 не создан]</sup>
== Источники информации ==
# [https://en.wikipedia.org/wiki/Category:Clustering_criteria Wikipedia {{---}} Category:Clustering criteria]
# [http://synthesis.ipi.ac.ru/sigmod/seminar/sivogolovko20111124.pdf Сивоголовко Е. В. Методы оценки качества четкой кластеризации]
# [http://www.cs.kent.edu/~jin/DM08/ClusterValidation.pdf Cluster Validation]
# [https://link.springer.com/article/10.1023/A:1012801612483 Halkidi, M., Batistakis, Y., Vazirgiannis, M., 2001. On clustering validation techniques. Journal of intelligent information systems, 17(2-3), pp.107-145.]
# [https://eurekamag.com/pdf/008/008337083.pdf Pal, N.R., Biswas, J., 1997. Cluster validation using graph theoretic concepts. Pattern Recognition, 30(6), pp.847-857.]
== Примечания ==
[[Категория:Машинное обучение]]
[[Категория:Кластеризация]]
== Оценки качества классификации ==
Перед переходом к самим метрикам необходимо ввести важную концепцию для описания этих метрик в терминах ошибок классификации — [[матрица ошибок|confusion matrix]] (матрица ошибок).
Допустим, что у нас есть два класса и алгоритм, предсказывающий принадлежность каждого объекта одному из классов, тогда матрица ошибок классификации будет выглядеть следующим образом:
[[Файл:Confusion_matrix.png|500px]]
Здесь '''a(х)''' — это ответ алгоритма на объекте, а '''y''' — истинная метка класса на этом объекте.
Таким образом, ошибки классификации бывают двух видов: False Negative (FN) и False Positive (FP).
'''Проблема оценки качества в [[Кластеризация|задаче кластеризации]]''' трудноразрешима, как минимум, по двум причинам:
* [[Кластеризация#Теорема невозможности Клейнберга|Теорема невозможности Клейнберга]] {{---}} не существует оптимального алгоритма кластеризации.
* Многие алгоритмы кластеризации не способны определить настоящее количество кластеров в данных. Чаще всего количество кластеров подается на вход алгоритма и подбирается несколькими запусками алгоритма.
== Методы оценки качества кластеризации ==
'''Метод оценки качества кластеризации''' {{---}} инструментарий для количественной оценки результатов кластеризации.
Принято выделять две группы методов оценки качества кластеризации:
* '''Внешние''' (англ. ''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 ===
Индекс Rand оценивает, насколько много из тех пар элементов, которые находились в одном классе, и тех пар элементов, которые находились в разных классах, сохранили это состояние после кластеризации алгоритмом.
: <math>
Rand = \dfrac{TP+FN}{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> {{---}} значения из таблицы сопряженности.
В отличие от обычного [[{{NAMESPACE}}:{{PAGENAME}}#Индекс_Rand|индекса Rand]], индекс Adjusted Rand может принимать отрицательные значения, если <math>Index < Expected Index</math>.
=== Индекс Жаккара (англ. Jaccard Index) ===
Индекс Жаккара похож на [[#Индекс_Rand|Индекс Rand]], только не учитывает пары элементов находящиеся в разные классах и разных кластерах (<math>FN</math>).
: <math>
Jaccard = \dfrac{TP}{TP+TN+FP}
</math>
Имеет область определения от 0 до 1, где 1 {{---}} полное совпадение кластеров с заданными классами, а 0 {{---}} отсутствие совпадений.
=== Индекс Фоулкса – Мэллова (англ. Fowlkes-Mallows Index) ===
Индекс Фоулкса – Мэллова используется для определения сходства между двумя кластерами.
: <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 ===
Классическая мера корреляции между двумя переменными:
: <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_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}\| > 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) ===
Это, возможно, одна из самых используемых мер оценки качества кластеризации.<br/>
Она вычисляет компактность как расстояние от объектов кластера до их центроидов, а отделимость - как расстояние между центроидами.
: <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>
Чем больше данный индекс, тем выше качество.
=== Индекс 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\| < \|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)} < 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>.
Данная оценка, как и предыдущая, должна возрастать.
== Сравнение ==
Не существует лучшего метода оценки качества кластеризации. Однако, в рамках исследования<ref>[https://www.sciencedirect.com/science/article/abs/pii/S003132031200338X An extensive comparative study of cluster validity indices]</ref> была предпринята попытка сравнить существующие меры на различных данных. Полученные результаты показали, что на искусственных датасетах наилучшим образом себя проявили индексы <math>Silhouette</math>, <math>DB^*</math> и <math>Calinski-Harabasz</math>. На реальных датасетах лучше всех показал себя <math>Score-function</math>.
В Таблице 1 приведены оценки сложности мер качества кластеризации (<math>n</math> — число объектов в рассматриваемом наборе данных):
{|class="wikitable" style="margin:auto; clear:both;
|+ Таблица 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> наиболее полно соответствуют когнитивному представлению асессоров о качестве кластеризации<ref>[https://ieeexplore.ieee.org/abstract/document/7891855 Towards cluster validity index evaluation and selection]</ref>.
== См. также ==
* [[Кластеризация]]
* [[Оценка качества в задачах классификации и регрессии]]<sup>[на 28.01.19 не создан]</sup>
== Источники информации ==
# [https://en.wikipedia.org/wiki/Category:Clustering_criteria Wikipedia {{---}} Category:Clustering criteria]
# [http://synthesis.ipi.ac.ru/sigmod/seminar/sivogolovko20111124.pdf Сивоголовко Е. В. Методы оценки качества четкой кластеризации]
# [http://www.cs.kent.edu/~jin/DM08/ClusterValidation.pdf Cluster Validation]
# [https://link.springer.com/article/10.1023/A:1012801612483 Halkidi, M., Batistakis, Y., Vazirgiannis, M., 2001. On clustering validation techniques. Journal of intelligent information systems, 17(2-3), pp.107-145.]
# [https://eurekamag.com/pdf/008/008337083.pdf Pal, N.R., Biswas, J., 1997. Cluster validation using graph theoretic concepts. Pattern Recognition, 30(6), pp.847-857.]
== Примечания ==
[[Категория:Машинное обучение]]
[[Категория:Кластеризация]]
