Оценка качества в задаче кластеризации — различия между версиями
(→Purity) |
м (rollbackEdits.php mass rollback) |
(не показана 1 промежуточная версия 1 участника) | |
(нет различий)
|
Текущая версия на 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.