1
правка
Изменения
м
→Исправление обозначений во внешних мерах оценки качества
Принято выделять две группы методов оценки качества кластеризации:
* '''Внешние''' (англ. ''InternalExternal'') меры основаны на сравнении результата кластеризации с априори известным разделением на классы. * '''Внутренние''' (англ. ''ExternalInternal'') меры отображают качество кластеризации только по информации в данных.
== Внешние меры оценки качества ==
Также рассмотрим пары <math>(x_i, x_j)</math> из элементов кластеризуемого множества <math>X</math>. Подсчитаем количество пар, в которых:
* Элементы принадлежат одному кластеру и одному классу {{---}} <math>TP</math>
* Элементы принадлежат одному кластеру, но разным классам {{---}} <math>TNFP</math>* Элементы принадлежат разным кластерам, но одному классу {{---}} <math>FPFN</math>* Элементы принадлежат разным кластерам и разным классам {{---}} <math>FNTN</math>
=== Индекс Rand Index ===
Индекс Rand оценивает, насколько много из тех пар элементов, которые находились в одном классе, и тех пар элементов, которые находились в разных классах, сохранили это состояние после кластеризации алгоритмом.
: <math>
Rand = \dfrac{TP+FNTN}{TP+TN+FP+FN}
</math>
Имеет область определения от 0 до 1, где 1 {{---}} полное совпадение кластеров с заданными классами, а 0 {{---}} отсутствие совпадений.
=== Индекс Adjusted Rand Index ===
:<math>\overbrace{ARI}^\text{Adjusted Index} = \frac{ \overbrace{\sum_{ij} \binom{n_{ij}}{2}}^\text{Index} - \overbrace{[\sum_i \binom{a_i}{2} \sum_j \binom{b_j}{2}] / \binom{n}{2}}^\text{Expected Index} }{ \underbrace{\frac{1}{2} [\sum_i \binom{a_i}{2} + \sum_j \binom{b_j}{2}]}_\text{Max Index} - \underbrace{[\sum_i \binom{a_i}{2} \sum_j \binom{b_j}{2}] / \binom{n}{2}}_\text{Expected Index} }</math>
где <math>n_{ij}, a_i, b_j</math> {{---}} значения из таблицы сопряженности.
В отличие от обычного [[{{NAMESPACE}}:{{PAGENAME}}#Rand_IndexИндекс_Rand|индекса Rand Index]], индекс Adjusted Rand Index может принимать отрицательные значения, если <math>Index < Expected Index</math>.
=== Индекс Жаккара (англ. Jaccard Index ) ===Индекс Жаккара похож на [[#Rand_IndexИндекс_Rand|Индекс Rand Index]], только не учитывает пары элементов находящиеся в разные классах и разных кластерах (<math>FNTN</math>).
: <math>
Jaccard = \dfrac{TP}{TP+TNFN+FP}
</math>
Имеет область определения от 0 до 1, где 1 {{---}} полное совпадение кластеров с заданными классами, а 0 {{---}} отсутствие совпадений.
=== Folkes and Индекс Фоулкса – Мэллова (англ. Fowlkes-Mallows Index ) ===Индекс Fowlkes-Mallows Фоулкса – Мэллова используется для определения сходства между двумя кластерами.
: <math>
FM = \sqrt{ \dfrac{TP}{TP+TNFP} \cdot \dfrac{TP}{TP+FPFN} }
</math>
Более высокое значение индекса означает большее сходство между кластерами. Этот индекс также хорошо работает на зашумленных данных.
Чем больше значение меры {{---}} тем лучше.
=== Индекс Phi Index ===
Классическая мера корреляции между двумя переменными:
: <math>
\Phi = \dfrac{ TP \times TN - FN - TN \times FP }{ (TP + TNFN)(TP + FP)(FN + FPTN)(FN FP + TN) }
</math>
</math>
=== Индекс Гудмэна-Крускала (англ. Goodman-Kruskal Index ) ===
: <math>
GK = \sum_i p_i(1 - \max_j \dfrac{ p_{ij} }{ p_i })
Данные меры оценивают качество структуры кластеров опираясь только непосредственно на нее, не используя внешней информации.
=== Компактность кластеров (англ. 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>
Должен снижаться с улучшением кластеризации.
=== Силуэт (англ. Silhouette) ===
Значение силуэта показывает, насколько объект похож на свой кластер по сравнению с другими кластерами.
Есть также упрощенная вариация силуэта: <math>a(x_i, c_k)</math> и <math>b(x_i, c_k)</math> вычисляются через центры кластеров.
=== Индекс Calinski–Harabasz index ===
: <math>
CH(C) = \dfrac{ N-K }{ K-1 } \cdot \dfrac{ \sum_{c_k \in C} |c_k| \cdot \| \overline{c_k} - \overline{X} \| }{ \sum_{c_k \in C} \sum_{ x_i \in c_k } \| x_i - \overline{c_k} \| }
Компактность основана на расстоянии от точек кластера до их центроидов, а разделимость - на расстоянии от центроид кластеров до глобального центроида. Должен возрастать.
=== Индекс C-Index ===Индекс C-Index - нормализованная оценка представляет собой нормализованную оценку компактности:
: <math>
CI(C) = \dfrac{ S(C) - S_{min}(C) }{ S_{max}(C) - S_{min}(C)}
: <math>S_{min}(C) (S_{max}(C))</math> - сумма <math>\dfrac{ |c_k|\cdot(|c_k| - 1) }{2}</math> минимальных (максимальных) расстояний между парами всех объектов во всем датасете.
=== Индекс Дэвиcа-Болдуина (англ. Davies–Bouldin Index ) ===
Это, возможно, одна из самых используемых мер оценки качества кластеризации.<br/>
Она вычисляет компактность как расстояние от объектов кластера до их центроидов, а отделимость - как расстояние между центроидами.
</math>
C-индекс и индекс ДэвидаДэвиcа-Болдуина должны минимизироваться для роста кластеризации.
=== Score function ===
: <math>
SF(C) = 1 - \dfrac{ 1 }{ e^{e^{bcd(C) + - wcd(C)}} }
</math>,
где:
</math>
Чтобы функция оценки была эффективной, она должна максимизировать bcd, минимизировать wcd и быть ограниченной. Чем больше данный индекс, тем выше качество.
=== Индекс Gamma Index ===
: <math>
G(C) = \dfrac{ \sum_{c_k \in C} \sum_{x_i,x_j \in c_k} |c_k| \cdot dl(x_i, x_j) }{ n_w (\binom{N}{2} - n_w) }
</math>.
=== Индекс COP Index ===
В данной мере компактность вычисляется как расстояние от точек кластера до его центроиды, а разделимость основана на расстоянии до самого отдаленного соседа.
: <math>
</math>.
=== Индекс CS Index ===
Был предложен в области сжатия изображений, но может быть успешно адаптирован для любого другого окружения. Он оценивает компактность по диаметру кластера, а отделимость — как дистанцию между ближайшими элементами двух кластеров.
Чем меньше значение данного индекса, тем выше качество кластеризации.
=== Индекс Sym-index ===
: <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)}
Чем выше данное значение, тем лучше.
=== Point Symmetry-Distance based indices (Индексы SymDB, SymD, Sym33) ===
Модифицируют оценку компактности для индексов Дэвиса-Боулдина, Данна и gD33 соответственно.
Данная оценка должна уменьшаться пропорционально росту качества кластеризации.
=== Индекс SV-Index ===
Одна из самых новых из рассматриваемых в данном разделе оценок. Измеряет разделимость по дистанции между ближайшими точка кластеров, а компактность — по расстоянию от пограничных точек кластера до его центроида.
Данная оценка должна увеличиваться.
=== Индекс OS-Index ===
Отличается от предыдущей оценки усложненным способом вычисления оценки разделимости.
== Сравнение ==
Не существует лучшего метода оценки качества кластеризации. Однако, в рамках исследования<ref>[https://www.sciencedirect.com/science/article/abs/pii/S003132031200338X An extensive comparative study of cluster validity indices]</ref> была предпринята попытка сравнить существующие меры на различных данных. Полученные результаты показали, что на искусственных датасетах наилучшим образом себя проявили индексы <math>Silhouette(Sil)</math>, Davies–Bouldin*(<math>DB^*) </math> и Calinski–Harabasz(CH)<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>.
== См. также ==
