49
правок
Изменения
Внешние метрики: done
* '''Внутренние''' (англ. ''External'') метрики отображают качество кластеризации только по информации в данных.
* '''Относительные''' (англ. ''Relative'') метрики основаны на оценивании полученного разделения на кластеры относительно результатов работы другого алгоритма.
Иногда сложно отнести метод оценки качества кластеризации к одному определенной группе, поэтому нижеприведенное разделение является условным, в других источниках можно встретить иное разделение.
Данные метрики используют дополнительные знания о кластеризуемом множестве: распределение по кластерам, количество кластеров и т.д.
Рассмотрим пары <math>(x_i, x_j)</math> из элементов кластеризуемого множества <math>X</math>. Подсчитаем количество пар, в которых:
* Элементы принадлежат одному кластеру и одному классу {{---}} <math>TP</math>
Имеет область определения от 0 до 1, где 1 - полное совпадение кластеров с заданными классами, а 0 - отсутствие совпадений.
Дано множество <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}
В отличие от обычного [[{{NAMESPACE}}:{{PAGENAME}}#Rand_Index|Rand Index]], Adjusted Rand Index может принимать отрицательные значения, если <math>Index < Expected Index</math>.
Индекс Жаккара похож на [[#Rand_Index|Rand Index]], только не учитывает пары элементов находящиеся в разные классах и разных кластерах (<math>FN</math>).
: <math>
Имеет область определения от 0 до 1, где 1 - полное совпадение кластеров с заданными классами, а 0 - отсутствие совпадений.
Индекс Fowlkes-Mallows используется для определения сходства между двумя кластерами.
: <math>
</math>
Более высокое значение индекса означает большее сходство между кластерами. Этот индекс также хорошо работает на зашумленных данных.
== Внешние метрики оценки качества ==
Данные метрики оценивают качество структуры кластеров опираясь только непосредственно на нее, не используя внешней информации.
=== Связность кластеров (Cluster Cohesion) ===
Идея данного метода в том, что чем ближе друг к другу находятся объекты внутри кластеров, тем лучше разделение.
Таким образом, необходимо минимизировать внутриклассовое расстояние, например, сумму квадратов отклонений (within cluster sum of squares):
: <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) ===
В данном случае идея противоположная - чем дальше друг от друга находятся объекты разных кластеров, тем лучше. Поэтому здесь стоит задача максимизации суммы квадратов отклонений (between cluster sum of squares):
: <math>
BSS = n \cdot \sum \limits_{j=1}^{M} (\overline{x_{j}} - \overline{x})^2
</math>, где <math>M</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> только если они находятся в разных кластерах.
Чем больше значение метрики - тем лучше.
=== Силуэт (Silhouette) ===
Значение силуэта показывает, насколько объект похож на свой кластер по сравнению с другими кластерами.
Пусть
: <math>
a_{pj} = \dfrac{1}{n_{c_p} - 1} \sum_{x_i \in c_p} \|x_j - x_k\|
</math> - среднее расстояние от <math>x_j \in c_p</math> до других объектов из кластера <math>c_p</math>, а <math>n_{c_p} = |c_p|</math>,
: <math>
d_{qj} = \dfrac{1}{n_{c_q}} \sum_{x_k \in c_q} \|x_j - x_k\|
</math> - среднее расстояние от <math>x_j \in c_p</math> до объектов из другого кластера <math>c_q: q \neq p</math>.
Положим <math>b_{pj} = min_{q \neq p} d_{qj}</math>.
Тогда "силуэт" элемента <math>x_j:</math>
: <math>
S_{x_j} = \dfrac{ b_{pj} - a_{pj} }{ max (a_{pj}, b_{pj}) }
</math>
Можно заметить, что :<math> -1 \le S_{x_j} \le 1
</math>.
Оценка для всей кластерной структуры:
: <math>
SWC = \dfrac{1}{N} \sum_{j=1}^{N} S_{x_j}
</math>
Чем ближе данная оценка к 1, тем лучше.
Есть также различные вариации силуэта:
* Упрощенный силуэт: <math>a_{pj}</math> и <math>b_{pj}</math> вычисляютсяерез центры кластеров;
* Альтернативный силуэт: S_{x_j} = \dfrac{ b_{pj} }{ a_{pjЪ + \epsilon }
== Относительные оценки качества ==
== См. также ==
