Изменения

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

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

Принято выделять три две группы методов оценки качества кластеризации:* '''Внешние''' (англ. ''InternalExternal'') метрики меры основаны на сравнении результата кластеризации с априори известным разделением на классы. * '''Внутренние''' (англ. ''ExternalInternal'') метрики меры отображают качество кластеризации только по информации в данных. * '''Относительные''' (англ. ''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>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 Index вычисляется по формуле:===

В отличие от обычного [[{{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>).

Jaccard = \dfrac{TP}{TP+TNFN+FP}

Имеет область определения от 0 до 1, где 1 {{- --}} полное совпадение кластеров с заданными классами, а 0 {{--- }} отсутствие совпадений.

=== Folkes and Индекс Фоулкса – Мэллова (англ. Fowlkes-Mallows Index ) ===Индекс Fowlkes-Mallows Фоулкса – Мэллова используется для определения сходства между двумя кластерами.

FM = \sqrt{ \dfrac{TP}{TP+TNFP} \cdot \dfrac{TP}{TP+FPFN} }

== Внешние метрики оценки качества = 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>

=== Компактность кластеров Индекс Гудмэна-Крускала (Cluster Cohesionангл. Goodman-Kruskal Index) ===Идея данного метода в том, что чем ближе друг к другу находятся объекты внутри кластеров, тем лучше разделение.: <math>GK = \sum_i p_i(1 - \max_j \dfrac{ p_{ij} }{ p_i })</math>

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

WSS E = - \sum_i p_i ( \sum sum_j \limits_dfrac{j=1}^p_{Mij} \sum \limits_{i = 1}^{|C_j|p_i } log(x_\dfrac{ p_{ij} - \overline}{x_jp_i })^2)</math>, где <math>M</math> - количество кластеров.

=== Отделимость кластеров (Cluster Separation) ===В данном случае идея противоположная - чем дальше друг от друга находятся объекты разных кластеровСтоит отметить, тем лучшечто если все кластера состоят из объектов одного класса, то энтропия равна 0.

BSS P = n \cdot sum_i \sum \limits_{j=1}^{M} (\overline{x_{j}} - \overlinemax_j p_{xij})^2</math> Чистота находится в интервале [0, 1], где <math>M</math> - количество кластеровпричём значение = 1 отвечает оптимальной кластеризации.

=== Hubert Г statistic F-мера ===Данная метрика отражает F-мера представляет собой гармоническое среднее расстояние между объектами разных кластеров:точностью (precision) и полнотой (recall).

Г F = \sum_j p_j \max_i \big\lbrack 2 \dfrac{1p_{ij} }{Mp_i } \sum \limits_dfrac{ p_{i=1ij} }^{N-1p_j } \sum big/ (\limits_dfrac{ p_{ij} }{i=ip_i } +1\dfrac{ p_{ij} }^{Np_j } P(i, j) \cdot Q(i, j),big\rbrack

где <math>M === Variation of Information === n*(n-1)/2</math>Данная мера измеряет количество информации, <math>P(i, j)</math> - матрица близости, апотерянной и полученной при переходе из одного кластера в другой.: <math>Q(i, j) VI = - \begin{cases} 0, & sum_i p_i \mbox{если x(i) и x(j) лежат в одном кластере} log p_i - \sum_i p_j log p_j - 2 \ 1, & sum_i \mboxsum_j p_{в другом случае ij} \log \\enddfrac{ p_{ij} }{casesp_i p_j }

Чем больше значение метрики == Внутренние меры оценки качества ==Данные меры оценивают качество структуры кластеров опираясь только непосредственно на нее, не используя внешней информации. === Компактность кластеров (англ. 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>\delta</math> {{- --}} межкластерное расстояние(оценка разделения), <math>\delta(c_k, c_kc_l) = min_{x_i \in c_k, y_j 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}\| > stdev(C) </math> и <math>1</math> в ином случае. Должен снижаться с улучшением кластеризации.

=== Силуэт (англ. Silhouette) ===

</math> {{- --}} среднее расстояние от <math>x_i \in c_k</math> до других объектов из кластера <math>c_k</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> (отделимость).

=== Индекс Calinski–Harabasz index ===

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>S_{min}(C) (S_maxS_{max}(C))</math> - сумма <math>\dfrac{ |c_k|\cdot(|c_k| - 1) }{2}</math> минимальных (максимальных) расстояний между парами всех парами объектов во всем датасете.

=== Индекс Дэвиcа-Болдуина (англ. Davies–Bouldin Index ) ===

Существует еще одна вариация данной метрикимеры, которая была предложена автором вместе с основной версией:

# [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.] == Примечания ==