Оценка качества в задаче кластеризации — различия между версиями
м (→Индекс Adjusted Rand) |
м (→Jaccard Index) |
||
Строка 82: | Строка 82: | ||
В отличие от обычного [[{{NAMESPACE}}:{{PAGENAME}}#Индекс_Rand|индекса Rand]], индекс Adjusted Rand может принимать отрицательные значения, если <math>Index < Expected Index</math>. | В отличие от обычного [[{{NAMESPACE}}:{{PAGENAME}}#Индекс_Rand|индекса Rand]], индекс Adjusted Rand может принимать отрицательные значения, если <math>Index < Expected Index</math>. | ||
− | === Jaccard | + | === Индекс Jaccard === |
− | Индекс Жаккара похож на [[# | + | Индекс Жаккара похож на [[#Индекс_Rand|Индекс Rand]], только не учитывает пары элементов находящиеся в разные классах и разных кластерах (<math>FN</math>). |
: <math> | : <math> | ||
Jaccard = \dfrac{TP}{TP+TN+FP} | Jaccard = \dfrac{TP}{TP+TN+FP} |
Версия 12:15, 26 января 2020
Проблема оценки качества в задаче кластеризации трудноразрешима, как минимум, по двум причинам:
- Теорема невозможности Клейнберга — не существует оптимального алгоритма кластеризации.
- Многие алгоритмы кластеризации не способны определить настоящее количество кластеров в данных. Чаще всего количество кластеров подается на вход алгоритма и подбирается несколькими запусками алгоритма.
Содержание
- 1 Методы оценки качества кластеризации
- 2 Внешние меры оценки качества
- 3 Внутренние меры оценки качества
- 3.1 Компактность кластеров (Cluster Cohesion)
- 3.2 Отделимость кластеров (Cluster Separation)
- 3.3 Индекс Данна (Dunn Index)
- 3.4 Обобщенный Индекс Данна (gD31, gD41, gD51, gD33, gD43, gD53)
- 3.5 Индекс S_Dbw
- 3.6 Силуэт (Silhouette)
- 3.7 Calinski–Harabasz index
- 3.8 C-Index
- 3.9 Davies–Bouldin Index
- 3.10 Score function
- 3.11 Gamma Index
- 3.12 COP Index
- 3.13 CS Index
- 3.14 Sym-index
- 3.15 Point Symmetry-Distance based indices (SymDB, SymD, Sym33)
- 3.16 Negentropy increment
- 3.17 SV-Index
- 3.18 OS-Index
- 4 Сравнение
- 5 См. также
- 6 Источники информации
- 7 Примечания
Методы оценки качества кластеризации
Метод оценки качества кластеризации — инструментарий для количественной оценки результатов кластеризации.
Принято выделять две группы методов оценки качества кластеризации:
- Внешние (англ. Internal) меры основаны на сравнении результата кластеризации с априори известным разделением на классы.
- Внутренние (англ. External) меры отображают качество кластеризации только по информации в данных.
Внешние меры оценки качества
Данные меры используют дополнительные знания о кластеризуемом множестве: распределение по кластерам, количество кластеров и т.д.
Обозначения
Дано множество
из элементов, разделение на классы , и полученное разделение на кластеры , совпадения между и могут быть отражены в таблице сопряженности , где каждое обозначает число объектов, входящих как в , так и в : .Пусть
.Также рассмотрим пары
из элементов кластеризуемого множества . Подсчитаем количество пар, в которых:- Элементы принадлежат одному кластеру и одному классу —
- Элементы принадлежат одному кластеру, но разным классам —
- Элементы принадлежат разным кластерам, но одному классу —
- Элементы принадлежат разным кластерам и разным классам —
Индекс Rand
Индекс Rand оценивает, насколько много из тех пар элементов, которые находились в одном классе, и тех пар элементов, которые находились в разных классах, сохранили это состояние после кластеризации алгоритмом.
Имеет область определения от 0 до 1, где 1 — полное совпадение кластеров с заданными классами, а 0 — отсутствие совпадений.
Индекс Adjusted Rand
где
— значения из таблицы сопряженности.В отличие от обычного индекса Rand, индекс Adjusted Rand может принимать отрицательные значения, если .
Индекс Jaccard
Индекс Жаккара похож на Индекс Rand, только не учитывает пары элементов находящиеся в разные классах и разных кластерах ( ).
Имеет область определения от 0 до 1, где 1 — полное совпадение кластеров с заданными классами, а 0 — отсутствие совпадений.
Folkes and Mallows Index
Индекс Fowlkes-Mallows используется для определения сходства между двумя кластерами.
Более высокое значение индекса означает большее сходство между кластерами. Этот индекс также хорошо работает на зашумленных данных.
Hubert Г statistic
Данная мера отражает среднее расстояние между объектами разных кластеров:
где
, — матрица близости, аМожно заметить, что два объекта влияют на
, только если они находятся в разных кластерах.Чем больше значение меры — тем лучше.
Phi Index
Классическая мера корреляции между двумя переменными:
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 index
Компактность основана на расстоянии от точек кластера до их центроидов, а разделимость - на расстоянии от центроид кластеров до глобального центроида. Должен возрастать.
C-Index
C-Index - нормализованная оценка компактности:
- ,
где:
- ,
- - сумма минимальных (максимальных) расстояний между парами всех объектов во всем датасете.
Davies–Bouldin Index
Это, возможно, одна из самых используемых мер оценки качества кластеризации.
Она вычисляет компактность как расстояние от объектов кластера до их центроидов, а отделимость - как расстояние между центроидами.
- ,
где:
Существует еще одна вариация данной меры, которая была предложена автором вместе с основной версией:
C-индекс и индекс Дэвида-Болдуина должны минимизироваться для роста кластеризации.
Score function
Индекс, основанный на суммировании. Здесь оценка компактности выражается в дистанции от точек кластера до его центроида, а оценка разделимости — в дистанции от центроидов кластеров до глобального центроида.
- ,
где:
- ,
Чем больше данный индекс, тем выше качество.
Gamma Index
где:
- — число пар таких, что (1) и принадлежат разным кластерам, и (2) ,
- .
COP Index
В данной мере компактность вычисляется как расстояние от точек кластера до его центроиды, а разделимость основана на расстоянии до самого отдаленного соседа.
- .
CS Index
Был предложен в области сжатия изображений, но может быть успешно адаптирован для любого другого окружения. Он оценивает компактность по диаметру кластера, а отделимость — как дистанцию между ближайшими элементами двух кластеров.
- .
Чем меньше значение данного индекса, тем выше качество кластеризации.
Sym-index
- .
Здесь
— дистанция симметрии для точки из кластера .Чем выше данное значение, тем лучше.
Point Symmetry-Distance based indices (SymDB, SymD, Sym33)
Модифицируют оценку компактности для индексов Дэвиса-Боулдина, Данна и gD33 соответственно.
SymDB вычисляется аналогично DB с изменением вычисления
на:- .
Данная оценка должна уменьшаться для улучшения качества кластеризации.
В SymD переопределена функция
:- .
в Sym33 аналогично SymD переопределена
:- .
Последние две оценки должны расти для улучшения качества кластеризации.
Negentropy increment
В отличие от подавляющего большинства других оценок, не основывается на сравнении компактности и разделимости. Определяется следующим образом:
- .
Здесь
, - определитель ковариационной матрицы кластера , - определитель ковариационной матрицы всего датасета.Данная оценка должна уменьшаться пропорционально росту качества кластеризации.
SV-Index
Одна из самых новых из рассматриваемых в данном разделе оценок. Измеряет разделимость по дистанции между ближайшими точка кластеров, а компактность — по расстоянию от пограничных точек кластера до его центроида.
- .
Данная оценка должна увеличиваться.
OS-Index
Отличается от предыдущей оценки усложненным способом вычисления оценки разделимости.
- .
Где
- .
при
, и в ином случае.Функции
и определены следующим образом:- .
- .
Данная оценка, как и предыдущая, должна возрастать.
Сравнение
Не существует лучшего метода оценки качества кластеризации. Однако, в рамках исследования[1] была предпринята попытка сравнить существующие меры на различных данных. Полученные результаты показали, что на искусственных датасетах наилучшим образом себя проявили индексы Silhouette(Sil), Davies–Bouldin*(DB*) и Calinski–Harabasz(CH). На реальных датасетах лучше всех показал себя Score function.
См. также
- Кластеризация
- Оценка качества в задачах классификации и регрессии[на 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.