1632
правки
Изменения
м
rollbackEdits.php mass rollback
Принято выделять две группы методов оценки качества кластеризации:
* '''Внешние''' (англ. ''InternalExternal'') меры основаны на сравнении результата кластеризации с априори известным разделением на классы. * '''Внутренние''' (англ. ''ExternalInternal'') меры отображают качество кластеризации только по информации в данных.
== Внешние меры оценки качества ==
Также рассмотрим пары <math>(x_i, x_j)</math> из элементов кластеризуемого множества <math>X</math>. Подсчитаем количество пар, в которых:
* Элементы принадлежат одному кластеру и одному классу {{---}} <math>TP</math>
* Элементы принадлежат одному кластеру, но разным классам {{---}} <math>TNFP</math>* Элементы принадлежат разным кластерам, но одному классу {{---}} <math>FPFN</math>* Элементы принадлежат разным кластерам и разным классам {{---}} <math>FNTN</math>
=== Индекс Rand ===
Индекс Rand оценивает, насколько много из тех пар элементов, которые находились в одном классе, и тех пар элементов, которые находились в разных классах, сохранили это состояние после кластеризации алгоритмом.
: <math>
Rand = \dfrac{TP+FNTN}{TP+TN+FP+FN}
</math>
Имеет область определения от 0 до 1, где 1 {{---}} полное совпадение кластеров с заданными классами, а 0 {{---}} отсутствие совпадений.
=== Индекс Жаккара (англ. Jaccard Index) ===
Индекс Жаккара похож на [[#Индекс_Rand|Индекс Rand]], только не учитывает пары элементов находящиеся в разные классах и разных кластерах (<math>FNTN</math>).
: <math>
Jaccard = \dfrac{TP}{TP+TNFN+FP}
</math>
Имеет область определения от 0 до 1, где 1 {{---}} полное совпадение кластеров с заданными классами, а 0 {{---}} отсутствие совпадений.
Индекс Фоулкса – Мэллова используется для определения сходства между двумя кластерами.
: <math>
FM = \sqrt{ \dfrac{TP}{TP+TNFP} \cdot \dfrac{TP}{TP+FPFN} }
</math>
Более высокое значение индекса означает большее сходство между кластерами. Этот индекс также хорошо работает на зашумленных данных.
Классическая мера корреляции между двумя переменными:
: <math>
\Phi = \dfrac{ TP \times TN - FN - TN \times FP }{ (TP + TNFN)(TP + FP)(FN + FPTN)(FN FP + TN) }
</math>
=== Minkowski Score ===
: <math>
MS = \dfrac{ \sqrt{ \sum_i \binom{a_i}{2} + \sum_j \binom{b_ib_j}{2} - 2\sum_{ij} \binom{ n_{ij} }{ 2 } } }{ \sqrt{ \sum_j \binom{b_ib_j}{2} } }
</math>
Чистота ставит в соответствие кластеру самый многочисленный в этом кластере класс.
: <math>
P = \sum_i p_i ( \max_j \dfrac{ p_{ij} }{ p_i } )
</math>
: <math>
SF(C) = 1 - \dfrac{ 1 }{ e^{e^{bcd(C) + - wcd(C)}} }
</math>,
где:
</math>
Чтобы функция оценки была эффективной, она должна максимизировать bcd, минимизировать wcd и быть ограниченной. Чем больше данный индекс, тем выше качество.
=== Индекс Gamma ===
Чем меньше значение данного индекса, тем выше качество кластеризации.
=== Индекс 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 ===
Отличается от предыдущей оценки усложненным способом вычисления оценки разделимости.
|+ Таблица 1 — Оценка сложности для 19 мер качества кластеризации.
|<math>Davies-Bouldin</math>
|<math>O(nlognn\log{n})</math>
|<math>CS</math>
|<math>O(nlognn\log{n})</math>
|-
|<math>Dunn</math>
|<math>O(n^2)</math>
|<math>DB^*</math>
|<math>O(nlognn\log{n})</math>
|-
|<math>Calinski-Harabasz</math>
|<math>O(nlognn\log{n})</math>
|<math>SF</math>
|<math>O(n)</math>
|<math>O(n^2)</math>
|<math>SV</math>
|<math>O(nlognn\log{n})</math>
|-
|<math>gD51</math>
|<math>O(n^2)</math>
|<math>OS</math>
|<math>O(n^2logn2\log{n})</math>
|-
|<math>gD33</math>
|<math>O(n^2)</math>
|<math>SDbw</math>
|<math>O(nlognn\log{n})</math>
|-
|<math>gD43</math>
|<math>O(n^2)</math>
|<math>C-index</math>
|<math>O(n^2logn2\log{n})</math>
|-
|<math>gD53</math>
|<math>O(nlognn\log{n})</math>
|
|
