Индекс Калински–Харабаша
Метрика оценки кластеризации

Индекс Калински-Харабаша (CHI) , также известный как критерий отношения дисперсии (VRC), представляет собой метрику для оценки алгоритмов кластеризации , введенную Тадеушем Калински и Ежи Харабашем в 1974 году. [1] Это внутренняя метрика оценки, где оценка качества кластеризации основана исключительно на наборе данных и результатах кластеризации, а не на внешних, достоверных метках.

Определение

При наличии набора данных из n точек: { x 1 , ..., x n } и назначении этих точек k кластерам: { C 1 , ..., C k } индекс Калински–Харабаша (CH) определяется как отношение межкластерного разделения (BCSS) к внутрикластерной дисперсии (WCSS), нормализованное по числу степеней свободы:

С ЧАС = Б С С С / ( к − 1 ) Вт С С С / ( н − к ) {\displaystyle CH={\frac {BCSS/(k-1)}{WCSS/(nk)}}}

BCSS (межкластерная сумма квадратов) — это взвешенная сумма квадратов евклидовых расстояний между каждым кластерным центроидом (средним) и общим центроидом данных (средним):

Б С С С = ∑ я = 1 к н я | | с я − с | | 2 {\displaystyle BCSS=\sum _{i=1}^{k}n_{i}||\mathbf {c} _{i}-\mathbf {c} ||^{2}}

где n i — количество точек в кластере C i , c i — центроид C i , а c — общий центроид данных. BCSS измеряет, насколько хорошо кластеры отделены друг от друга (чем выше, тем лучше).

WCSS (внутрикластерная сумма квадратов) — это сумма квадратов евклидовых расстояний между точками данных и их соответствующими кластерными центроидами:

Вт С С С = ∑ я = 1 к ∑ х ∈ С я | | х − с я | | 2 {\displaystyle WCSS=\sum _{i=1}^{k}\sum _{\mathbf {x} \in C_{i}}||\mathbf {x} -\mathbf {c} _{i}||^{2}}

WCSS измеряет компактность или связность кластеров (чем меньше, тем лучше). Минимизация WCSS является целью алгоритмов кластеризации на основе центроидов, таких как k-средние .

Объяснение

Числитель индекса CH - это разделение между кластерами (BCSS), деленное на его степени свободы. Число степеней свободы BCSS равно k - 1, поскольку фиксация центроидов k - 1 кластеров также определяет k -й центроид, поскольку его значение делает взвешенную сумму всех центроидов соответствующей общему центроиду данных.

Знаменатель индекса CH — это дисперсия внутри кластера (WCSS), деленная на его степени свободы . Число степеней свободы WCSS равно n - k , поскольку фиксация центроида каждого кластера уменьшает степени свободы на единицу. Это происходит потому, что при наличии центроида c i кластера C i назначение n i - 1 точек этому кластеру также определяет назначение 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 неизвестно априори. Это можно сделать, выполнив следующие шаги:

  1. Выполнить кластеризацию для различных значений k .
  2. Вычислите индекс CH для каждого результата кластеризации.
  3. В качестве оптимального числа кластеров выбирается значение k , дающее максимальный индекс CH.

Реализации

Библиотека Python scikit-learn обеспечивает реализацию этой метрики в модуле sklearn.metrics. [5]

R предоставляет аналогичную реализацию в своем пакете fpc . [6]

Смотрите также

Ссылки

  1. ^ ab Caliński, Tadeusz; Harabasz, Jerzy (1974). «Метод дендритов для кластерного анализа». Communications in Statistics . 3 (1): 1– 27. doi :10.1080/03610927408827101.
  2. ^ Янчи, Лю; Чжунмоу, Ли; Хуэй, Сюн; Сюэдун, Гао; Цзюньцзе, Ву (2010). «Понимание мер проверки внутренней кластеризации». Международная конференция IEEE 2010 по интеллектуальному анализу данных . стр.  911–916 . doi :10.1109/ICDM.2010.35. ISBN 978-1-4244-9131-5. S2CID  8298336.
  3. ^ Maulik, Ujjwal и Sanghamitra Bandyopadhyay. «Оценка производительности некоторых алгоритмов кластеризации и индексов достоверности». IEEE Transactions on Pattern Analysis and Machine Intelligence 24, № 12 (2002): 1650-1654.
  4. ^ Ван, Сюй и Юйшэн Сюй. «Улучшенный индекс для проверки кластеризации на основе индекса силуэта и индекса Калински–Харабаша». В серии конференций IOP: Материаловедение и инженерия, т. 569, № 5, стр. 052024. Издательство IOP, 2019.
  5. ^ "sklearn.metrics.calinski_harabasz_score". scikit-learn . Получено 29.10.2023 .
  6. ^ "R: Индекс Калински-Харабаша" . search.r-project.org . Проверено 29 октября 2023 г.
Взято с "https://en.wikipedia.org/w/index.php?title=Calinski–Harabasz_index&oldid=1237618066"