Оценка качества в задаче кластеризации — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 99 промежуточных версий 10 участников)
Строка 1: Строка 1:
 
'''Проблема оценки качества в [[Кластеризация|задаче кластеризации]]''' трудноразрешима, как минимум, по двум причинам:
 
'''Проблема оценки качества в [[Кластеризация|задаче кластеризации]]''' трудноразрешима, как минимум, по двум причинам:
* Не существует оптимального алгоритма кластеризации. Иными словами, различные алгоритмы (или различные конфигурации одного алгоритма) выдают разные разделения на кластеры, и ни одно из них не является лучшим во всех ситуациях [8]. 
+
* [[Кластеризация#Теорема невозможности Клейнберга|Теорема невозможности Клейнберга]] {{---}} не существует оптимального алгоритма кластеризации.
* Многие алгоритмы кластеризации не способны определить настоящее количество кластеров в данных. Чаще всего количество кластеров подается на вход алгоритма и подбирается несколькими запусками алгоритма. [1]
+
* Многие алгоритмы кластеризации не способны определить настоящее количество кластеров в данных. Чаще всего количество кластеров подается на вход алгоритма и подбирается несколькими запусками алгоритма.
 
 
  
 
== Методы оценки качества кластеризации ==
 
== Методы оценки качества кластеризации ==
'''Метод (индекс) оценки качества кластеризации''' (англ. ''cluster validity index, CVI''<sup>[осн.статья]</sup>) {{---}} инструментарий для количественной оценки результатов кластеризации.
+
'''Метод оценки качества кластеризации''' {{---}} инструментарий для количественной оценки результатов кластеризации.
  
Принято выделять три группы методов оценки качества кластеризации:
+
Принято выделять две группы методов оценки качества кластеризации:
* '''Внешние''' (англ. ''Internal'') метрики основаны на сравнении результата кластеризации с априори известным разделением на классы.  
+
* '''Внешние''' (англ. ''External'') меры основаны на сравнении результата кластеризации с априори известным разделением на классы.  
* '''Внутренние''' (англ. ''External'') метрики отображают качество кластеризации только по информации в данных.
+
* '''Внутренние''' (англ. ''Internal'') меры отображают качество кластеризации только по информации в данных.
* '''Относительные''' (англ. ''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>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}
 
: <math>\begin{array}{c|cccc|c}
 
{{} \atop X}\!\diagdown\!^Y &
 
{{} \atop X}\!\diagdown\!^Y &
Строка 74: Строка 58:
 
\ldots&
 
\ldots&
 
b_s&
 
b_s&
 +
n
 
\end{array}</math>
 
\end{array}</math>
  
Тогда Adjusted Rand Index вычисляется по формуле:
+
Пусть <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>\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> {{---}} значения из таблицы сопряженности.
 
где <math>n_{ij}, a_i, b_j</math> {{---}} значения из таблицы сопряженности.
  
В отличие от обычного [[{{NAMESPACE}}:{{PAGENAME}}#Rand_Index|Rand Index]], Adjusted Rand Index может принимать отрицательные значения, если <math>Index < Expected Index</math>.
+
В отличие от обычного [[{{NAMESPACE}}:{{PAGENAME}}#Индекс_Rand|индекса Rand]], индекс Adjusted Rand может принимать отрицательные значения, если <math>Index < Expected Index</math>.
  
=== Jaccard Index ===
+
=== Индекс Жаккара (англ. Jaccard Index) ===
Индекс Жаккара похож на [[#Rand_Index|Rand Index]], только не учитывает пары элементов находящиеся в разные классах и разных кластерах (<math>FN</math>).
+
Индекс Жаккара похож на [[#Индекс_Rand|Индекс Rand]], только не учитывает пары элементов находящиеся в разные классах и разных кластерах (<math>TN</math>).
 
: <math>
 
: <math>
Jaccard = \dfrac{TP}{TP+TN+FP}
+
Jaccard = \dfrac{TP}{TP+FN+FP}
 
</math>
 
</math>
Имеет область определения от 0 до 1, где 1 - полное совпадение кластеров с заданными классами, а 0 - отсутствие совпадений.
+
Имеет область определения от 0 до 1, где 1 {{---}} полное совпадение кластеров с заданными классами, а 0 {{---}} отсутствие совпадений.
  
=== Folkes and Mallows Index ===
+
=== Индекс Фоулкса – Мэллова (англ. Fowlkes-Mallows Index) ===
Индекс Fowlkes-Mallows используется для определения сходства между двумя кластерами.
+
Индекс Фоулкса – Мэллова используется для определения сходства между двумя кластерами.
 
: <math>
 
: <math>
FM = \sqrt{ \dfrac{TP}{TP+TN} \cdot \dfrac{TP}{TP+FP} }
+
FM = \sqrt{ \dfrac{TP}{TP+FP} \cdot \dfrac{TP}{TP+FN} }
 
</math>
 
</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.
  
=== Связность кластеров (Cluster Cohesion) ===
+
=== 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) ===
 
Идея данного метода в том, что чем ближе друг к другу находятся объекты внутри кластеров, тем лучше разделение.
 
Идея данного метода в том, что чем ближе друг к другу находятся объекты внутри кластеров, тем лучше разделение.
  
Таким образом, необходимо минимизировать внутриклассовое расстояние, например, сумму квадратов отклонений (within cluster sum of squares):
+
Таким образом, необходимо минимизировать внутриклассовое расстояние, например, сумму квадратов отклонений:
 
: <math>
 
: <math>
 
WSS = \sum \limits_{j=1}^{M} \sum \limits_{i = 1}^{|C_j|} (x_{ij} - \overline{x_j})^2
 
WSS = \sum \limits_{j=1}^{M} \sum \limits_{i = 1}^{|C_j|} (x_{ij} - \overline{x_j})^2
</math>, где <math>M</math> - количество кластеров.  
+
</math>, где <math>M</math> {{---}} количество кластеров.
  
=== Разделимость кластеров (Cluster Separation) ===
+
=== Отделимость кластеров (англ. Cluster Separation) ===
В данном случае идея противоположная - чем дальше друг от друга находятся объекты разных кластеров, тем лучше.  
+
В данном случае идея противоположная {{---}} чем дальше друг от друга находятся объекты разных кластеров, тем лучше.  
  
Поэтому здесь стоит задача максимизации суммы квадратов отклонений (between cluster sum of squares):
+
Поэтому здесь стоит задача максимизации суммы квадратов отклонений:
 
: <math>
 
: <math>
 
BSS = n \cdot \sum \limits_{j=1}^{M} (\overline{x_{j}} - \overline{x})^2
 
BSS = n \cdot \sum \limits_{j=1}^{M} (\overline{x_{j}} - \overline{x})^2
</math>, где <math>M</math> - количество кластеров.  
+
</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>.
  
=== Hubert Г statistic ===
+
Обобщенный индекс Данна, как и обычный, должен возрастать вместе с улучшением качества кластеризации.
Данная метрика отражает среднее расстояние между объектами разных кластеров:
+
 
 +
=== Индекс 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>
 
: <math>
Г = \dfrac{1}{M} \sum \limits_{i=1}^{N-1} \sum \limits_{i=i+1}^{N} P(i, j) \cdot Q(i, j),
+
S(c_k) = \dfrac{ 1 }{ |c_k| } \sum \limits_{x_i \in c_k} \|x_i - \overline{c_k}\|
 
</math>
 
</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) лежат в одном кластере} \\
+
: <math>
  1,  & \mbox{в другом случае } \\
+
DB^*(C) = \dfrac{1}{K} \sum \limits_{c_k \in C} \dfrac
\end{cases}
+
{ \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>
 
</math>
Можно заметить, что два объекта влияют на <math>Г</math> только если они находятся в разных кластерах.
 
  
Чем больше значение метрики - тем лучше.
+
C-индекс и индекс Дэвиcа-Болдуина должны минимизироваться для роста кластеризации.
  
=== Силуэт (Silhouette) ===
+
=== Score function ===
Значение силуэта показывает, насколько объект похож на свой кластер по сравнению с другими кластерами.
+
Индекс, основанный на суммировании. Здесь оценка компактности выражается в дистанции от точек кластера до его центроида, а оценка разделимости — в дистанции от центроидов кластеров до глобального центроида.
  
Пусть
 
 
: <math>
 
: <math>
a_{pj} = \dfrac{1}{n_{c_p} - 1} \sum_{x_i \in c_p} \|x_j - x_k\|
+
SF(C) = 1 - \dfrac{ 1 }{ e^{e^{bcd(C) - wcd(C)}} }
</math> - среднее расстояние от <math>x_j \in c_p</math> до других объектов из кластера <math>c_p</math>, а <math>n_{c_p} = |c_p|</math>,
+
</math>,
 +
где:
 
: <math>
 
: <math>
d_{qj} = \dfrac{1}{n_{c_q}} \sum_{x_k \in c_q} \|x_j - x_k\|
+
bcd(C) = \dfrac{ \sum \limits_{c_k \in C} |c_k| \cdot \|\overline{c_k} - \overline{X}\| }{ N \times K }
</math> - среднее расстояние от <math>x_j \in c_p</math> до объектов из другого кластера <math>c_q: q \neq p</math>.
+
</math>,
Положим <math>b_{pj} = min_{q \neq p} d_{qj}</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>
  
Тогда "силуэт" элемента <math>x_j:</math>
+
Чтобы функция оценки была эффективной, она должна максимизировать bcd, минимизировать wcd и быть ограниченной. Чем больше данный индекс, тем выше качество.
: <math>  
+
 
S_{x_j} = \dfrac{ b_{pj} - a_{pj} }{ max (a_{pj}, b_{pj}) }
+
=== Индекс 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>
Можно заметить, что :<math> -1 \le S_{x_j} \le 1
+
 
 +
где:
 +
: <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>.
 
</math>.
  
Оценка для всей кластерной структуры:
+
Данная оценка должна увеличиваться.
: <math>  
+
 
SWC = \dfrac{1}{N} \sum_{j=1}^{N} S_{x_j}
+
=== Индекс OS ===
</math>
+
Отличается от предыдущей оценки усложненным способом вычисления оценки разделимости.
Чем ближе данная оценка к 1, тем лучше.
+
 
 +
: <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;
* Упрощенный силуэт: <math>a_{pj}</math> и <math>b_{pj}</math> вычисляютсяерез центры кластеров;
+
|+ Таблица 1 — Оценка сложности для 19 мер качества кластеризации.
* Альтернативный силуэт: S_{x_j} = \dfrac{ b_{pj} }{ a_{pjЪ + \epsilon }
+
|<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://www.sciencedirect.com/science/article/abs/pii/S003132031200338X 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.]
 
 
# [https://en.wikipedia.org/wiki/Category:Clustering_criteria Wikipedia {{---}} Category:Clustering criteria]
 
# [https://en.wikipedia.org/wiki/Category:Clustering_criteria Wikipedia {{---}} Category:Clustering criteria]
# [http://synthesis.ipi.ac.ru/sigmod/seminar/sivogolovko20111124.pdf Сивоголовка Е. В. Методы оценки качества четкой кластеризации]
+
# [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.]
 +
 
 +
== Примечания ==
  
 
[[Категория:Машинное обучение]]
 
[[Категория:Машинное обучение]]
 +
[[Категория:Кластеризация]]

Текущая версия на 19:17, 4 сентября 2022

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

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

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

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

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

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

См. также

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

  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.

Примечания