Индекс Калинского-Харабаша
Индекс Калинского-Харабаша (CHI) , также известный как критерий коэффициента дисперсии (VRC), представляет собой метрику для оценки алгоритмов кластеризации , введенную Тадеушем Калиньским и Ежи Харабасом в 1974 году. [1] Это внутренняя метрика оценки, при которой оценка качества кластеризации основана исключительно на наборе данных и результатах кластеризации, а не на внешних, достоверных метках.
Определение
[ редактировать ]Учитывая набор данных из n точек: { x 1 , ..., x n } и присвоение этих точек k кластерам: { C 1 , ..., C k }, индекс Калински-Харабаша (CH) определяется как отношение межкластерного разделения (BCSS) к внутрикластерной дисперсии (WCSS), нормализованное по количеству степеней свободы:
BCSS (сумма квадратов между кластерами) — это взвешенная сумма квадратов евклидовых расстояний между каждым центроидом кластера (среднее значение) и общим центроидом данных (среднее значение):
где n i — количество точек в кластере C i , c i — центроид C i , а c — общий центроид данных. BCSS измеряет, насколько хорошо кластеры отделены друг от друга (чем выше, тем лучше).
WCSS (сумма квадратов внутри кластера) — это сумма квадратов евклидовых расстояний между точками данных и соответствующими центроидами кластера:
WCSS измеряет компактность или связность кластеров (чем меньше, тем лучше). Минимизация WCSS является целью алгоритмов кластеризации на основе центроидов, таких как k-means .
Объяснение
[ редактировать ]Числитель индекса CH представляет собой разделение между кластерами (BCSS), разделенное на его степени свободы. Число степеней свободы BCSS равно k - 1, поскольку фиксация центроидов k - 1 кластеров определяет и k й центроид, так как его значение заставляет взвешенную сумму всех центроидов соответствовать общему центроиду данных.
Знаменатель индекса CH — это внутрикластерная дисперсия (WCSS), деленная на его степени свободы . Число степеней свободы WCSS равно n — k , поскольку фиксация центроида каждого кластера уменьшает степени свободы на одну. Это связано с тем, что для данного центроида c i кластера Ci - 1 точек этому кластеру также назначение n i определяет назначение n i й точку, поскольку общее среднее значение точек, присвоенных кластеру, должно быть равно c i .
Разделение BCSS и WCSS на их степени свободы помогает нормализовать значения, делая их сопоставимыми для различного количества кластеров. Без этой нормализации индекс CH может быть искусственно завышен для более высоких значений k , что затрудняет определение того, связано ли увеличение значения индекса с действительно лучшей кластеризацией или просто с увеличением количества кластеров.
Более высокое значение CH указывает на лучшую кластеризацию, поскольку это означает, что точки данных более распределены между кластерами, чем внутри кластеров.
Хотя удовлетворительной вероятностной основы для использования индекса CH не существует, критерий обладает некоторыми желательными математическими свойствами, как показано на рисунке. [1] Например, в частном случае равных расстояний между всеми парами точек индекс CH равен 1. Кроме того, он аналогичен статистике F-теста в одномерном анализе.
Лю и др. [2] обсудите эффективность использования индекса CH для оценки кластера по сравнению с другими внутренними показателями оценки кластеризации. Маулик и Бандиопадхьяй [3] оценить производительность трех алгоритмов кластеризации, используя четыре индекса валидности кластера, включая индекс Дэвиса-Булдина , индекс Данна , индекс Калински-Харабаша и недавно разработанный индекс. Ван и др. [4] предложили улучшенный индекс для проверки кластеризации на основе индексирования Silhouette и индекса Калински-Харабаша.
Нахождение оптимального количества кластеров
[ редактировать ]Подобно другим метрикам оценки кластеризации, таким как Silhouette Score , индекс CH можно использовать для поиска оптимального количества кластеров k в таких алгоритмах, как k-means , где значение k неизвестно априори. Это можно сделать, выполнив следующие действия:
- Выполните кластеризацию для различных значений k .
- Вычислите индекс CH для каждого результата кластеризации.
- Значение k , которое дает максимальный индекс CH, выбирается в качестве оптимального числа кластеров.
Реализации
[ редактировать ]Библиотека Python scikit-learn обеспечивает реализацию этой метрики в модуле sklearn.metrics. [5]
R предоставляет аналогичную реализацию в своем пакете fpc . [6]
См. также
[ редактировать ]Ссылки
[ редактировать ]- ^ Jump up to: Перейти обратно: а б Калинский, Тадеуш; Харабас, Ежи (1974). «Дендритный метод кластерного анализа». Коммуникации в статистике . 3 (1): 1–27. дои : 10.1080/03610927408827101 .
- ^ Цзюньцзе, Ву (2010). Международная конференция IEEE по интеллектуальному анализу данных, 2010 г. . 911–916. , стр , Сюн ; Янчи, Лю; Хуэй ИКДМ.2010.35 . 978-1-4244-9131-5 . S2CID 8298336 .
- ^ Маулик, Уджвал и Сангамитра Бандиопадхьяй. «Оценка производительности некоторых алгоритмов кластеризации и индексов достоверности». Транзакции IEEE по анализу шаблонов и машинному интеллекту 24, вып. 12 (2002): 1650–1654.
- ^ Ван, Сюй и Юшэн Сюй. «Улучшенный индекс для проверки кластеризации на основе индекса Silhouette и индекса Калински-Харабаша». В серии конференций IOP: Материаловедение и инженерия, том. 569, нет. 5, с. 052024. Издательство ИОП, 2019.
- ^ "sklearn.metrics.calinski_harabasz_score" . scikit-учиться . Проверено 29 октября 2023 г.
- ^ «R: Индекс Калински-Харабаша» . search.r-project.org . Проверено 29 октября 2023 г.