Изменения

* Не [[Кластеризация#Теорема невозможности Клейнберга|Теорема невозможности Клейнберга]] {{---}} не существует оптимального алгоритма кластеризации. Иными словами, различные алгоритмы (или различные конфигурации одного алгоритма) выдают разные разделения на кластеры, и ни одно из них не является лучшим во всех ситуациях.

'''Метод (индекс) оценки качества кластеризации''' (англ. ''cluster validity index, CVI'') {{---}} инструментарий для количественной оценки результатов кластеризации.

=== 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>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 Index ===Индекс Rand оценивает, насколько много из тех пар элементов, которые находились в одном классе, и тех пар элементов, которые находились в разных классах, сохранили это состояние после кластеризации алгоритмом.: <math>Rand = \dfrac{TP+FN}{TP+TN+FP+FN}</math>Имеет область определения от 0 до 1, где 1 {{---}} полное совпадение кластеров с заданными классами, а 0 {{---}} отсутствие совпадений. === Adjusted Rand Index вычисляется по формуле:===

== Внешние = 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 Index ===Классическая мера корреляции между двумя переменными:: <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> == Внутренние метрики оценки качества ==

Таким образом, необходимо минимизировать внутриклассовое расстояние, например, сумму квадратов отклонений (within cluster sum of squares):

Поэтому здесь стоит задача максимизации суммы квадратов отклонений (between cluster sum of squares):

По результатам Не существует лучшего метода оценки качества кластеризации. Однако, в рамках исследования<ref>[https://www.sciencedirect.com/science/article/abs/pii/S003132031200338X An extensive comparative study of cluster validity indices]</ref> была предпринята попытка сравнить существующие метрики на различных данных. Полученные результаты показали, что на искусственных датасетах наилучшие результаты показали наилучшим образом себя проявили индексы Silhouette(Sil), Davies–Bouldin*(DB*) и Calinski–Harabasz(CH). На реальных датасетах лучше всех проявил показал себя Score function.Однако, на определенных данных другие индексы могут показать лучшие результаты (так, например, на зашумленных данных Calinski–Harabasz(CH) дает оценки значительно хуже).

# [http://synthesis.ipi.ac.ru/sigmod/seminar/sivogolovko20111124.pdf Сивоголовка Сивоголовко Е. В. Методы оценки качества четкой кластеризации]