Оценка качества в задаче кластеризации

Проблема оценки качества в задаче кластеризации трудноразрешима, как минимум, по двум причинам:

• Не существует оптимального алгоритма кластеризации. Иными словами, различные алгоритмы (или различные конфигурации одного алгоритма) выдают разные разделения на кластеры, и ни одно из них не является лучшим во всех ситуациях [8].
• Многие алгоритмы кластеризации не способны определить настоящее количество кластеров в данных. Чаще всего количество кластеров подается на вход алгоритма и подбирается несколькими запусками алгоритма. [1]

Методы оценки качества кластеризации

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

Принято выделять три группы методов оценки качества кластеризации:

• Внешние (англ. Internal) метрики основаны на сравнении результата кластеризации с априори известным разделением на классы.
• Внутренние (англ. External) метрики отображают качество кластеризации только по информации в данных.
• Относительные (англ. 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]\begin{array}{c|cccc|c} {{} \atop X}\!\diagdown\!^Y & Y_1& Y_2& \ldots& Y_s& \text{Sums} \\ \hline X_1& n_{11}& n_{12}& \ldots& n_{1s}& a_1 \\ X_2& n_{21}& n_{22}& \ldots& n_{2s}& a_2 \\ \vdots& \vdots& \vdots& \ddots& \vdots& \vdots \\ X_r& n_{r1}& n_{r2}& \ldots& n_{rs}& a_r \\ \hline \text{Sums}& b_1& b_2& \ldots& b_s& \end{array}[/math]

Тогда Adjusted Rand Index вычисляется по формуле:

[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] — значения из таблицы сопряженности.

В отличие от обычного Rand Index, Adjusted Rand Index может принимать отрицательные значения, если [math]Index \lt Expected Index[/math].

Jaccard Index

Индекс Жаккара похож на |Rand Index, только не учитывает пары элементов находящиеся в разные классах и разных кластерах ([math]FN[/math]).

[math] Jaccard = \dfrac{TP}{TP+TN+FP} [/math]

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

Folkes and Mallows Index

Индекс Fowlkes-Mallows используется для определения сходства между двумя кластерами.

[math] FM = \sqrt{ \dfrac{TP}{TP+TN} \cdot \dfrac{TP}{TP+FP} } [/math]

Более высокое значение индекса означает большее сходство между кластерами. Этот индекс также хорошо работает на зашумленных данных.

См. также

• Кластеризация

Источники информации

1. Arbelaitz, O.; Gurrutxaga, I.; Muguerza, J.; Pérez, J.M.; Perona, I. An extensive comparative study of cluster validity indices. Pattern Recognit. 2013, 46, 243–256.
2. Wikipedia — Category:Clustering criteria
3. Сивоголовка Е. В. Методы оценки качества четкой кластеризации