Оценка качества в задаче кластеризации — различия между версиями
Linarkou (обсуждение | вклад) (→Entropy) |
м (rollbackEdits.php mass rollback) |
||
(не показано 67 промежуточных версий 9 участников) | |||
Строка 6: | Строка 6: | ||
'''Метод оценки качества кластеризации''' {{---}} инструментарий для количественной оценки результатов кластеризации. | '''Метод оценки качества кластеризации''' {{---}} инструментарий для количественной оценки результатов кластеризации. | ||
− | Принято выделять | + | Принято выделять две группы методов оценки качества кластеризации: |
− | * '''Внешние''' (англ. '' | + | * '''Внешние''' (англ. ''External'') меры основаны на сравнении результата кластеризации с априори известным разделением на классы. |
− | * '''Внутренние''' (англ. '' | + | * '''Внутренние''' (англ. ''Internal'') меры отображают качество кластеризации только по информации в данных. |
− | == Внешние | + | == Внешние меры оценки качества == |
− | Данные | + | Данные меры используют дополнительные знания о кластеризуемом множестве: распределение по кластерам, количество кластеров и т.д. |
=== Обозначения === | === Обозначения === | ||
Строка 65: | Строка 65: | ||
Также рассмотрим пары <math>(x_i, x_j)</math> из элементов кластеризуемого множества <math>X</math>. Подсчитаем количество пар, в которых: | Также рассмотрим пары <math>(x_i, x_j)</math> из элементов кластеризуемого множества <math>X</math>. Подсчитаем количество пар, в которых: | ||
* Элементы принадлежат одному кластеру и одному классу {{---}} <math>TP</math> | * Элементы принадлежат одному кластеру и одному классу {{---}} <math>TP</math> | ||
− | * Элементы принадлежат одному кластеру, но разным классам {{---}} <math> | + | * Элементы принадлежат одному кластеру, но разным классам {{---}} <math>FP</math> |
− | * Элементы принадлежат разным кластерам, но одному классу {{---}} <math> | + | * Элементы принадлежат разным кластерам, но одному классу {{---}} <math>FN</math> |
− | * Элементы принадлежат разным кластерам и разным классам {{---}} <math> | + | * Элементы принадлежат разным кластерам и разным классам {{---}} <math>TN</math> |
− | === Rand | + | === Индекс Rand === |
Индекс Rand оценивает, насколько много из тех пар элементов, которые находились в одном классе, и тех пар элементов, которые находились в разных классах, сохранили это состояние после кластеризации алгоритмом. | Индекс Rand оценивает, насколько много из тех пар элементов, которые находились в одном классе, и тех пар элементов, которые находились в разных классах, сохранили это состояние после кластеризации алгоритмом. | ||
: <math> | : <math> | ||
− | Rand = \dfrac{TP+ | + | Rand = \dfrac{TP+TN}{TP+TN+FP+FN} |
</math> | </math> | ||
Имеет область определения от 0 до 1, где 1 {{---}} полное совпадение кластеров с заданными классами, а 0 {{---}} отсутствие совпадений. | Имеет область определения от 0 до 1, где 1 {{---}} полное совпадение кластеров с заданными классами, а 0 {{---}} отсутствие совпадений. | ||
− | === Adjusted Rand | + | === Индекс Adjusted Rand === |
:<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>\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> {{---}} значения из таблицы сопряженности. | где <math>n_{ij}, a_i, b_j</math> {{---}} значения из таблицы сопряженности. | ||
− | В отличие от обычного [[{{NAMESPACE}}:{{PAGENAME}}# | + | В отличие от обычного [[{{NAMESPACE}}:{{PAGENAME}}#Индекс_Rand|индекса Rand]], индекс Adjusted Rand может принимать отрицательные значения, если <math>Index < Expected Index</math>. |
− | === Jaccard Index === | + | === Индекс Жаккара (англ. Jaccard Index) === |
− | Индекс Жаккара похож на [[# | + | Индекс Жаккара похож на [[#Индекс_Rand|Индекс Rand]], только не учитывает пары элементов находящиеся в разные классах и разных кластерах (<math>TN</math>). |
: <math> | : <math> | ||
− | Jaccard = \dfrac{TP}{TP+ | + | Jaccard = \dfrac{TP}{TP+FN+FP} |
</math> | </math> | ||
Имеет область определения от 0 до 1, где 1 {{---}} полное совпадение кластеров с заданными классами, а 0 {{---}} отсутствие совпадений. | Имеет область определения от 0 до 1, где 1 {{---}} полное совпадение кластеров с заданными классами, а 0 {{---}} отсутствие совпадений. | ||
− | === | + | === Индекс Фоулкса – Мэллова (англ. Fowlkes-Mallows Index) === |
− | Индекс | + | Индекс Фоулкса – Мэллова используется для определения сходства между двумя кластерами. |
: <math> | : <math> | ||
− | FM = \sqrt{ \dfrac{TP}{TP+ | + | FM = \sqrt{ \dfrac{TP}{TP+FP} \cdot \dfrac{TP}{TP+FN} } |
</math> | </math> | ||
Более высокое значение индекса означает большее сходство между кластерами. Этот индекс также хорошо работает на зашумленных данных. | Более высокое значение индекса означает большее сходство между кластерами. Этот индекс также хорошо работает на зашумленных данных. | ||
=== Hubert Г statistic === | === Hubert Г statistic === | ||
− | Данная | + | Данная мера отражает среднее расстояние между объектами разных кластеров: |
: <math> | : <math> | ||
Г = \dfrac{1}{M} \sum \limits_{i=1}^{N-1} \sum \limits_{i=i+1}^{N} P(i, j) \cdot Q(i, j), | Г = \dfrac{1}{M} \sum \limits_{i=1}^{N-1} \sum \limits_{i=i+1}^{N} P(i, j) \cdot Q(i, j), | ||
Строка 109: | Строка 109: | ||
Можно заметить, что два объекта влияют на <math>Г</math>, только если они находятся в разных кластерах. | Можно заметить, что два объекта влияют на <math>Г</math>, только если они находятся в разных кластерах. | ||
− | Чем больше значение | + | Чем больше значение меры {{---}} тем лучше. |
− | === Phi | + | === Индекс Phi === |
Классическая мера корреляции между двумя переменными: | Классическая мера корреляции между двумя переменными: | ||
: <math> | : <math> | ||
− | \Phi = \dfrac{ TP \times FN | + | \Phi = \dfrac{ TP \times TN - FN \times FP }{ (TP + FN)(TP + FP)(FN + TN)(FP + TN) } |
</math> | </math> | ||
=== Minkowski Score === | === Minkowski Score === | ||
: <math> | : <math> | ||
− | MS = \dfrac{ \sqrt{ \sum_i \binom{a_i}{2} + \sum_j \binom{ | + | 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> | </math> | ||
− | === Goodman-Kruskal Index === | + | === Индекс Гудмэна-Крускала (англ. Goodman-Kruskal Index) === |
: <math> | : <math> | ||
GK = \sum_i p_i(1 - \max_j \dfrac{ p_{ij} }{ p_i }) | GK = \sum_i p_i(1 - \max_j \dfrac{ p_{ij} }{ p_i }) | ||
Строка 131: | Строка 131: | ||
: <math> | : <math> | ||
E = - \sum_i p_i ( \sum_j \dfrac{ p_{ij} }{ p_i } log( \dfrac{ p_{ij} }{ p_i } ) ) | E = - \sum_i p_i ( \sum_j \dfrac{ p_{ij} }{ p_i } log( \dfrac{ p_{ij} }{ p_i } ) ) | ||
+ | </math> | ||
Стоит отметить, что если все кластера состоят из объектов одного класса, то энтропия равна 0. | Стоит отметить, что если все кластера состоят из объектов одного класса, то энтропия равна 0. | ||
− | |||
=== Purity === | === Purity === | ||
+ | Чистота ставит в соответствие кластеру самый многочисленный в этом кластере класс. | ||
: <math> | : <math> | ||
− | P = \sum_i | + | P = \sum_i \max_j p_{ij} |
</math> | </math> | ||
− | + | Чистота находится в интервале [0, 1], причём значение = 1 отвечает оптимальной кластеризации. | |
=== F-мера === | === F-мера === | ||
+ | F-мера представляет собой гармоническое среднее между точностью (precision) и полнотой (recall). | ||
: <math> | : <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 | 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 | ||
Строка 148: | Строка 150: | ||
=== Variation of Information === | === 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> | ||
+ | == Внутренние меры оценки качества == | ||
+ | Данные меры оценивают качество структуры кластеров опираясь только непосредственно на нее, не используя внешней информации. | ||
− | + | === Компактность кластеров (англ. Cluster Cohesion) === | |
− | |||
− | |||
− | === Компактность кластеров (Cluster Cohesion) === | ||
Идея данного метода в том, что чем ближе друг к другу находятся объекты внутри кластеров, тем лучше разделение. | Идея данного метода в том, что чем ближе друг к другу находятся объекты внутри кластеров, тем лучше разделение. | ||
Строка 159: | Строка 164: | ||
: <math> | : <math> | ||
WSS = \sum \limits_{j=1}^{M} \sum \limits_{i = 1}^{|C_j|} (x_{ij} - \overline{x_j})^2 | WSS = \sum \limits_{j=1}^{M} \sum \limits_{i = 1}^{|C_j|} (x_{ij} - \overline{x_j})^2 | ||
− | </math>, где <math>M</math> {{---}} количество кластеров. | + | </math>, где <math>M</math> {{---}} количество кластеров. |
− | === Отделимость кластеров (Cluster Separation) === | + | === Отделимость кластеров (англ. Cluster Separation) === |
В данном случае идея противоположная {{---}} чем дальше друг от друга находятся объекты разных кластеров, тем лучше. | В данном случае идея противоположная {{---}} чем дальше друг от друга находятся объекты разных кластеров, тем лучше. | ||
Строка 167: | Строка 172: | ||
: <math> | : <math> | ||
BSS = n \cdot \sum \limits_{j=1}^{M} (\overline{x_{j}} - \overline{x})^2 | BSS = n \cdot \sum \limits_{j=1}^{M} (\overline{x_{j}} - \overline{x})^2 | ||
− | </math>, где <math>M</math> {{---}} количество кластеров. | + | </math>, где <math>M</math> {{---}} количество кластеров. |
− | === Индекс Данна (Dunn Index) === | + | === Индекс Данна (англ. Dunn Index) === |
Индекс Данна имеет множество вариаций, оригинальная версия выглядит следующим образом: | Индекс Данна имеет множество вариаций, оригинальная версия выглядит следующим образом: | ||
: <math> | : <math> | ||
Строка 175: | Строка 180: | ||
</math>, | </math>, | ||
где: | где: | ||
− | : <math>\delta</math> {{---}} межкластерное расстояние, <math>\delta(c_k, | + | : <math>\delta</math> {{---}} межкластерное расстояние (оценка разделения), <math>\delta(c_k, c_l) = min_{x_i \in c_k, 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>. | + | : <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> | ||
+ | |||
+ | и стандартных отклонений | ||
− | === Силуэт (Silhouette) === | + | : <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) === | ||
Значение силуэта показывает, насколько объект похож на свой кластер по сравнению с другими кластерами. | Значение силуэта показывает, насколько объект похож на свой кластер по сравнению с другими кластерами. | ||
Строка 190: | Строка 237: | ||
</math> {{---}} среднее расстояние от <math>x_i \in c_k</math> до других объектов из кластера <math>c_k</math> (компактность), | </math> {{---}} среднее расстояние от <math>x_i \in c_k</math> до других объектов из кластера <math>c_k</math> (компактность), | ||
: <math> | : <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\| | + | 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> (отделимость). | </math> {{---}} среднее расстояние от <math>x_i \in c_k</math> до объектов из другого кластера <math>c_l: k \neq l</math> (отделимость). | ||
Можно заметить, что | Можно заметить, что | ||
Строка 199: | Строка 246: | ||
Есть также упрощенная вариация силуэта: <math>a(x_i, c_k)</math> и <math>b(x_i, c_k)</math> вычисляются через центры кластеров. | Есть также упрощенная вариация силуэта: <math>a(x_i, c_k)</math> и <math>b(x_i, c_k)</math> вычисляются через центры кластеров. | ||
− | === Calinski–Harabasz | + | === Индекс Calinski–Harabasz === |
: <math> | : <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} \| } | + | 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} \| } |
</math> | </math> | ||
− | Компактность основана на расстоянии от точек кластера до их центроидов, а разделимость - на расстоянии от центроид кластеров до глобального центроида. | + | Компактность основана на расстоянии от точек кластера до их центроидов, а разделимость - на расстоянии от центроид кластеров до глобального центроида. Должен возрастать. |
− | === C | + | === Индекс C === |
− | C | + | Индекс C представляет собой нормализованную оценку компактности: |
: <math> | : <math> | ||
CI(C) = \dfrac{ S(C) - S_{min}(C) }{ S_{max}(C) - S_{min}(C)} | CI(C) = \dfrac{ S(C) - S_{min}(C) }{ S_{max}(C) - S_{min}(C)} | ||
Строка 216: | Строка 263: | ||
: <math>S_{min}(C) (S_{max}(C))</math> - сумма <math>\dfrac{ |c_k|\cdot(|c_k| - 1) }{2}</math> минимальных (максимальных) расстояний между парами всех объектов во всем датасете. | : <math>S_{min}(C) (S_{max}(C))</math> - сумма <math>\dfrac{ |c_k|\cdot(|c_k| - 1) }{2}</math> минимальных (максимальных) расстояний между парами всех объектов во всем датасете. | ||
− | === Davies–Bouldin Index === | + | === Индекс Дэвиcа-Болдуина (англ. Davies–Bouldin Index) === |
Это, возможно, одна из самых используемых мер оценки качества кластеризации.<br/> | Это, возможно, одна из самых используемых мер оценки качества кластеризации.<br/> | ||
Она вычисляет компактность как расстояние от объектов кластера до их центроидов, а отделимость - как расстояние между центроидами. | Она вычисляет компактность как расстояние от объектов кластера до их центроидов, а отделимость - как расстояние между центроидами. | ||
Строка 227: | Строка 274: | ||
</math> | </math> | ||
− | Существует еще одна вариация данной | + | Существует еще одна вариация данной меры, которая была предложена автором вместе с основной версией: |
: <math> | : <math> | ||
DB^*(C) = \dfrac{1}{K} \sum \limits_{c_k \in C} \dfrac | DB^*(C) = \dfrac{1}{K} \sum \limits_{c_k \in C} \dfrac | ||
Строка 233: | Строка 280: | ||
{ \min \limits_{c_l \in C \setminus c_k} \{ \| \overline{c_k} - \overline{c_l} \| \} } | { \min \limits_{c_l \in C \setminus c_k} \{ \| \overline{c_k} - \overline{c_l} \| \} } | ||
</math> | </math> | ||
+ | |||
+ | C-индекс и индекс Дэвиcа-Болдуина должны минимизироваться для роста кластеризации. | ||
=== Score function === | === Score function === | ||
+ | Индекс, основанный на суммировании. Здесь оценка компактности выражается в дистанции от точек кластера до его центроида, а оценка разделимости — в дистанции от центроидов кластеров до глобального центроида. | ||
+ | |||
: <math> | : <math> | ||
− | SF(C) = 1 - \dfrac{ 1 }{ e^{e^{bcd(C) | + | SF(C) = 1 - \dfrac{ 1 }{ e^{e^{bcd(C) - wcd(C)}} } |
</math>, | </math>, | ||
где: | где: | ||
Строка 245: | Строка 296: | ||
wcd(C) = \sum \limits_{c_k \in C} \dfrac{ 1 }{ |c_k| } \sum \limits_{x_i \in c_k} \|x_i - \overline{c_k}\| | wcd(C) = \sum \limits_{c_k \in C} \dfrac{ 1 }{ |c_k| } \sum \limits_{x_i \in c_k} \|x_i - \overline{c_k}\| | ||
</math> | </math> | ||
+ | |||
+ | Чтобы функция оценки была эффективной, она должна максимизировать bcd, минимизировать wcd и быть ограниченной. Чем больше данный индекс, тем выше качество. | ||
+ | |||
+ | === Индекс Gamma === | ||
+ | : <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> | ||
+ | |||
+ | где: | ||
+ | : <math>dl(x_i,x_j)</math> {{---}} число пар <math>(x_k, x_l) \in X</math> таких, что (1) <math>x_k</math> и <math>x_l</math> принадлежат разным кластерам, и (2) <math>\|x_k - x_l\| < \|x_i - x_j\|</math>, | ||
+ | : <math> | ||
+ | n_w = \sum_{c_k \in C} \binom{|c_k|}{2} | ||
+ | </math>. | ||
+ | |||
+ | === Индекс COP === | ||
+ | В данной мере компактность вычисляется как расстояние от точек кластера до его центроиды, а разделимость основана на расстоянии до самого отдаленного соседа. | ||
+ | : <math> | ||
+ | COP(C) = \dfrac{1}{N} \sum \limits_{c_k \in C} |c_k| \dfrac{ 1/|c_k| \sum_{x_i \in c_k} \| x_i - \overline{c_k} \| }{ \min_{x_i \notin c_k} \max_{x_j \in c_k} \| x_i - x_j\| } | ||
+ | </math>. | ||
+ | |||
+ | === Индекс CS === | ||
+ | Был предложен в области сжатия изображений, но может быть успешно адаптирован для любого другого окружения. Он оценивает компактность по диаметру кластера, а отделимость — как дистанцию между ближайшими элементами двух кластеров. | ||
+ | |||
+ | : <math> | ||
+ | CS(C) = \dfrac{\sum_{c_k \in C} \{ 1 / |c_k| \sum_{x_i \in c_k} \max_{x_j \in c_k}\{\|x_i - x_j\|\} \}}{\sum_{c_k \in C} \min_{c_l \in C \setminus c_k} \{\|\overline{c_k} - \overline{c_l}\| \}} | ||
+ | </math>. | ||
+ | |||
+ | Чем меньше значение данного индекса, тем выше качество кластеризации. | ||
+ | |||
+ | === Индекс Sym === | ||
+ | : <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)} | ||
+ | </math>. | ||
+ | |||
+ | Здесь <math>\overset{\ast}{d_{ps}}(x_i, c_k)</math> — дистанция симметрии для точки <math>x_i</math> из кластера <math>c_k</math>. | ||
+ | |||
+ | Чем выше данное значение, тем лучше. | ||
+ | |||
+ | === Индексы SymDB, SymD, Sym33 === | ||
+ | Модифицируют оценку компактности для индексов Дэвиса-Боулдина, Данна и gD33 соответственно. | ||
+ | |||
+ | SymDB вычисляется аналогично DB с изменением вычисления <math>S</math> на: | ||
+ | |||
+ | : <math> S(c_k) = \dfrac{1}{|c_k| \sum_{x_i \in c_k} \overset{\ast}{d_{ps}}(x_i, c_k)} </math>. | ||
+ | |||
+ | Данная оценка должна уменьшаться для улучшения качества кластеризации. | ||
+ | |||
+ | В SymD переопределена функция <math>\Delta</math>: | ||
+ | |||
+ | : <math> \Delta(c_k) = \max_{x_i \in c_k} \{\overset{\ast}{d_{ps}}(x_i, c_k)\} </math>. | ||
+ | |||
+ | в Sym33 аналогично SymD переопределена <math>\Delta</math>: | ||
+ | |||
+ | : <math> \Delta(c_k) = \dfrac{2}{|c_k| \sum_{x_i \in c_k} \overset{\ast}{d_{ps}}(x_i, c_k)} </math>. | ||
+ | |||
+ | Последние две оценки должны расти для улучшения качества кластеризации. | ||
+ | |||
+ | === Negentropy increment === | ||
+ | В отличие от подавляющего большинства других оценок, не основывается на сравнении компактности и разделимости. Определяется следующим образом: | ||
+ | |||
+ | : <math> | ||
+ | NI(C) = \dfrac{1}{2} \sum_{c_k \in C} p(c_k)log|cov_{c_k}| - \dfrac{1}{2}log|cov_X| - \sum_{c_k \in C} p(c_k)log p(c_k) | ||
+ | </math>. | ||
+ | |||
+ | Здесь <math>p(c_k) = |c_k| / N</math>, <math>|cov_{c_k}|</math> - определитель ковариационной матрицы кластера <math>c_k</math>, <math>|cov_X|</math> - определитель ковариационной матрицы всего датасета. | ||
+ | |||
+ | Данная оценка должна уменьшаться пропорционально росту качества кластеризации. | ||
+ | === Индекс SV === | ||
+ | Одна из самых новых из рассматриваемых в данном разделе оценок. Измеряет разделимость по дистанции между ближайшими точка кластеров, а компактность — по расстоянию от пограничных точек кластера до его центроида. | ||
+ | |||
+ | : <math> | ||
+ | SV(C) = \dfrac{\sum_{c_k \in C} \min_{c_l \in C \setminus c_k} \{\|\overline{c_k} - \overline{c_l}\|\}}{\sum_{c_k \in C} 10 / |c_k| \sum \max_{x_i \in c_k}(0.1 * |c_k|) * \|\overline{x_i} - \overline{c_k}\|} | ||
+ | </math>. | ||
+ | |||
+ | Данная оценка должна увеличиваться. | ||
+ | |||
+ | === Индекс OS === | ||
+ | Отличается от предыдущей оценки усложненным способом вычисления оценки разделимости. | ||
+ | |||
+ | : <math> | ||
+ | OS(C) = \dfrac{\sum_{c_k \in C} \sum_{x_i \in c_k} ov(x_i, c_k)}{\sum_{c_k \in C} 10 / |c_k| \sum \max_{x_i \in c_k}(0.1 * |c_k|) * \|\overline{x_i} - \overline{c_k}\|} | ||
+ | </math>. | ||
+ | |||
+ | Где | ||
+ | |||
+ | : <math> | ||
+ | ov(x_i, c_k) = \dfrac{a(x_i, c_k)}{b(x_i, c_k)} | ||
+ | </math>. | ||
+ | |||
+ | при <math> \dfrac{b(x_i, c_k) - a(x_i, c_k)}{b(x_i, c_k) + a(x_i, c_k)} < 0.4 </math>, и <math>0</math> в ином случае. | ||
+ | |||
+ | Функции <math>a</math> и <math>b</math> определены следующим образом: | ||
+ | |||
+ | : <math> | ||
+ | a(x_i, c_k) = \dfrac{1}{|c_k|\sum_{x_j \in c_k}\|x_i - x_j\|} | ||
+ | </math>. | ||
+ | |||
+ | : <math> | ||
+ | b(x_i, c_k) = \dfrac{1}{|c_k|\sum_{x_j \notin c_k}\ \min(|c_k)\|x_i - x_j\|} | ||
+ | </math>. | ||
+ | |||
+ | Данная оценка, как и предыдущая, должна возрастать. | ||
== Сравнение == | == Сравнение == | ||
− | Не существует лучшего метода оценки качества кластеризации. Однако, в рамках исследования<ref>[https://www.sciencedirect.com/science/article/abs/pii/S003132031200338X An extensive comparative study of cluster validity indices]</ref> была предпринята попытка сравнить существующие | + | Не существует лучшего метода оценки качества кластеризации. Однако, в рамках исследования<ref>[https://www.sciencedirect.com/science/article/abs/pii/S003132031200338X An extensive comparative study of cluster validity indices]</ref> была предпринята попытка сравнить существующие меры на различных данных. Полученные результаты показали, что на искусственных датасетах наилучшим образом себя проявили индексы <math>Silhouette</math>, <math>DB^*</math> и <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>. | ||
== См. также == | == См. также == | ||
Строка 255: | Строка 465: | ||
== Источники информации == | == Источники информации == | ||
# [https://en.wikipedia.org/wiki/Category:Clustering_criteria Wikipedia {{---}} Category:Clustering criteria] | # [https://en.wikipedia.org/wiki/Category:Clustering_criteria Wikipedia {{---}} Category:Clustering criteria] | ||
− | # [http://synthesis.ipi.ac.ru/sigmod/seminar/sivogolovko20111124.pdf | + | # [http://synthesis.ipi.ac.ru/sigmod/seminar/sivogolovko20111124.pdf Сивоголовко Е. В. Методы оценки качества четкой кластеризации] |
# [http://www.cs.kent.edu/~jin/DM08/ClusterValidation.pdf Cluster Validation] | # [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.] | ||
== Примечания == | == Примечания == |
Текущая версия на 19:17, 4 сентября 2022
Проблема оценки качества в задаче кластеризации трудноразрешима, как минимум, по двум причинам:
- Теорема невозможности Клейнберга — не существует оптимального алгоритма кластеризации.
- Многие алгоритмы кластеризации не способны определить настоящее количество кластеров в данных. Чаще всего количество кластеров подается на вход алгоритма и подбирается несколькими запусками алгоритма.
Методы оценки качества кластеризации
Метод оценки качества кластеризации — инструментарий для количественной оценки результатов кластеризации.
Принято выделять две группы методов оценки качества кластеризации:
- Внешние (англ. External) меры основаны на сравнении результата кластеризации с априори известным разделением на классы.
- Внутренние (англ. Internal) меры отображают качество кластеризации только по информации в данных.
Внешние меры оценки качества
Данные меры используют дополнительные знания о кластеризуемом множестве: распределение по кластерам, количество кластеров и т.д.
Обозначения
Дано множество
из элементов, разделение на классы , и полученное разделение на кластеры , совпадения между и могут быть отражены в таблице сопряженности , где каждое обозначает число объектов, входящих как в , так и в : .Пусть
.Также рассмотрим пары
из элементов кластеризуемого множества . Подсчитаем количество пар, в которых:- Элементы принадлежат одному кластеру и одному классу —
- Элементы принадлежат одному кластеру, но разным классам —
- Элементы принадлежат разным кластерам, но одному классу —
- Элементы принадлежат разным кластерам и разным классам —
Индекс Rand
Индекс Rand оценивает, насколько много из тех пар элементов, которые находились в одном классе, и тех пар элементов, которые находились в разных классах, сохранили это состояние после кластеризации алгоритмом.
Имеет область определения от 0 до 1, где 1 — полное совпадение кластеров с заданными классами, а 0 — отсутствие совпадений.
Индекс Adjusted Rand
где
— значения из таблицы сопряженности.В отличие от обычного индекса Rand, индекс Adjusted Rand может принимать отрицательные значения, если .
Индекс Жаккара (англ. Jaccard Index)
Индекс Жаккара похож на Индекс Rand, только не учитывает пары элементов находящиеся в разные классах и разных кластерах ( ).
Имеет область определения от 0 до 1, где 1 — полное совпадение кластеров с заданными классами, а 0 — отсутствие совпадений.
Индекс Фоулкса – Мэллова (англ. Fowlkes-Mallows Index)
Индекс Фоулкса – Мэллова используется для определения сходства между двумя кластерами.
Более высокое значение индекса означает большее сходство между кластерами. Этот индекс также хорошо работает на зашумленных данных.
Hubert Г statistic
Данная мера отражает среднее расстояние между объектами разных кластеров:
где
, — матрица близости, аМожно заметить, что два объекта влияют на
, только если они находятся в разных кластерах.Чем больше значение меры — тем лучше.
Индекс Phi
Классическая мера корреляции между двумя переменными:
Minkowski Score
Индекс Гудмэна-Крускала (англ. Goodman-Kruskal Index)
Entropy
Энтропия измеряет "чистоту" меток классов:
Стоит отметить, что если все кластера состоят из объектов одного класса, то энтропия равна 0.
Purity
Чистота ставит в соответствие кластеру самый многочисленный в этом кластере класс.
Чистота находится в интервале [0, 1], причём значение = 1 отвечает оптимальной кластеризации.
F-мера
F-мера представляет собой гармоническое среднее между точностью (precision) и полнотой (recall).
Variation of Information
Данная мера измеряет количество информации, потерянной и полученной при переходе из одного кластера в другой.
Внутренние меры оценки качества
Данные меры оценивают качество структуры кластеров опираясь только непосредственно на нее, не используя внешней информации.
Компактность кластеров (англ. Cluster Cohesion)
Идея данного метода в том, что чем ближе друг к другу находятся объекты внутри кластеров, тем лучше разделение.
Таким образом, необходимо минимизировать внутриклассовое расстояние, например, сумму квадратов отклонений:
- , где — количество кластеров.
Отделимость кластеров (англ. Cluster Separation)
В данном случае идея противоположная — чем дальше друг от друга находятся объекты разных кластеров, тем лучше.
Поэтому здесь стоит задача максимизации суммы квадратов отклонений:
- , где — количество кластеров.
Индекс Данна (англ. Dunn Index)
Индекс Данна имеет множество вариаций, оригинальная версия выглядит следующим образом:
- ,
где:
- — межкластерное расстояние (оценка разделения), ,
- — диаметр кластера (оценка сплоченности), .
Обобщенный Индекс Данна (gD31, gD41, gD51, gD33, gD43, gD53)
Все эти вариации являются комбинациями 3 вариантов вычисления оценки разделения
и оценки компактностиОценки разделения:
- ,
- ,
- .
Оценки компактности:
- ,
- .
Обобщенный индекс Данна, как и обычный, должен возрастать вместе с улучшением качества кластеризации.
Индекс S_Dbw
Основан на вычислении Евклидовой нормы
и стандартных отклонений
- ,
- .
Сам индекс определяется формулой:
- .
Здесь
- ,
- ,
- , если и в ином случае.
Должен снижаться с улучшением кластеризации.
Силуэт (англ. Silhouette)
Значение силуэта показывает, насколько объект похож на свой кластер по сравнению с другими кластерами.
Оценка для всей кластерной структуры:
- ,
где:
- — среднее расстояние от до других объектов из кластера (компактность),
- — среднее расстояние от до объектов из другого кластера (отделимость).
Можно заметить, что
- .
Чем ближе данная оценка к 1, тем лучше.
Есть также упрощенная вариация силуэта:
и вычисляются через центры кластеров.Индекс Calinski–Harabasz
Компактность основана на расстоянии от точек кластера до их центроидов, а разделимость - на расстоянии от центроид кластеров до глобального центроида. Должен возрастать.
Индекс C
Индекс C представляет собой нормализованную оценку компактности:
- ,
где:
- ,
- - сумма минимальных (максимальных) расстояний между парами всех объектов во всем датасете.
Индекс Дэвиcа-Болдуина (англ. Davies–Bouldin Index)
Это, возможно, одна из самых используемых мер оценки качества кластеризации.
Она вычисляет компактность как расстояние от объектов кластера до их центроидов, а отделимость - как расстояние между центроидами.
- ,
где:
Существует еще одна вариация данной меры, которая была предложена автором вместе с основной версией:
C-индекс и индекс Дэвиcа-Болдуина должны минимизироваться для роста кластеризации.
Score function
Индекс, основанный на суммировании. Здесь оценка компактности выражается в дистанции от точек кластера до его центроида, а оценка разделимости — в дистанции от центроидов кластеров до глобального центроида.
- ,
где:
- ,
Чтобы функция оценки была эффективной, она должна максимизировать bcd, минимизировать wcd и быть ограниченной. Чем больше данный индекс, тем выше качество.
Индекс Gamma
где:
- — число пар таких, что (1) и принадлежат разным кластерам, и (2) ,
- .
Индекс COP
В данной мере компактность вычисляется как расстояние от точек кластера до его центроиды, а разделимость основана на расстоянии до самого отдаленного соседа.
- .
Индекс CS
Был предложен в области сжатия изображений, но может быть успешно адаптирован для любого другого окружения. Он оценивает компактность по диаметру кластера, а отделимость — как дистанцию между ближайшими элементами двух кластеров.
- .
Чем меньше значение данного индекса, тем выше качество кластеризации.
Индекс Sym
- .
Здесь
— дистанция симметрии для точки из кластера .Чем выше данное значение, тем лучше.
Индексы SymDB, SymD, Sym33
Модифицируют оценку компактности для индексов Дэвиса-Боулдина, Данна и gD33 соответственно.
SymDB вычисляется аналогично DB с изменением вычисления
на:- .
Данная оценка должна уменьшаться для улучшения качества кластеризации.
В SymD переопределена функция
:- .
в Sym33 аналогично SymD переопределена
:- .
Последние две оценки должны расти для улучшения качества кластеризации.
Negentropy increment
В отличие от подавляющего большинства других оценок, не основывается на сравнении компактности и разделимости. Определяется следующим образом:
- .
Здесь
, - определитель ковариационной матрицы кластера , - определитель ковариационной матрицы всего датасета.Данная оценка должна уменьшаться пропорционально росту качества кластеризации.
Индекс SV
Одна из самых новых из рассматриваемых в данном разделе оценок. Измеряет разделимость по дистанции между ближайшими точка кластеров, а компактность — по расстоянию от пограничных точек кластера до его центроида.
- .
Данная оценка должна увеличиваться.
Индекс OS
Отличается от предыдущей оценки усложненным способом вычисления оценки разделимости.
- .
Где
- .
при
, и в ином случае.Функции
и определены следующим образом:- .
- .
Данная оценка, как и предыдущая, должна возрастать.
Сравнение
Не существует лучшего метода оценки качества кластеризации. Однако, в рамках исследования[1] была предпринята попытка сравнить существующие меры на различных данных. Полученные результаты показали, что на искусственных датасетах наилучшим образом себя проявили индексы , и . На реальных датасетах лучше всех показал себя .
В Таблице 1 приведены оценки сложности мер качества кластеризации (
— число объектов в рассматриваемом наборе данных):Из всех рассмотренных мер, меры [2].
, , и наиболее полно соответствуют когнитивному представлению асессоров о качестве кластеризацииСм. также
- Кластеризация
- Оценка качества в задачах классификации и регрессии[на 28.01.19 не создан]
Источники информации
- Wikipedia — Category:Clustering criteria
- Сивоголовко Е. В. Методы оценки качества четкой кластеризации
- Cluster Validation
- Halkidi, M., Batistakis, Y., Vazirgiannis, M., 2001. On clustering validation techniques. Journal of intelligent information systems, 17(2-3), pp.107-145.
- Pal, N.R., Biswas, J., 1997. Cluster validation using graph theoretic concepts. Pattern Recognition, 30(6), pp.847-857.