Индекс Данна - Dunn index

В Индекс Данна (DI) (введен Дж. К. Данном в 1974 г.) - метрика для оценки алгоритмы кластеризации.[1][2] Это часть группы показателей достоверности, включая Индекс Дэвиса – Боулдина или же Индекс силуэта, в том смысле, что это внутренняя схема оценки, где результат основан на самих сгруппированных данных. Как и все другие подобные индексы, цель состоит в том, чтобы идентифицировать наборы кластеров, которые являются компактными, с небольшими различиями между членами кластера и хорошо разделенными, где средние значения разных кластеров достаточно далеко друг от друга по сравнению с внутри кластера. дисперсия. Для заданного назначения кластеров более высокий индекс Данна указывает на лучшую кластеризацию. Одним из недостатков этого использования является вычислительная стоимость, поскольку количество кластеров и размерность данных увеличиваются.

Предварительные мероприятия

Есть много способов определить размер или диаметр кластера. Это может быть расстояние между двумя самыми дальними точками внутри кластера, это может быть среднее всех попарных расстояний между точками данных внутри кластера, или это также может быть расстояние каждой точки данных от центроида кластера. Каждая из этих формулировок математически показана ниже:

Позволять Cя быть кластером векторов. Позволять Икс и у быть любыми двумя n-мерными векторами признаков, назначенными одному кластеру Cя.

, который вычисляет максимальное расстояние.
, который вычисляет среднее расстояние между всеми парами.
, вычисляет расстояние всех точек от среднего.

Это также можно сказать о межкластерном расстоянии, где могут быть сделаны аналогичные формулировки, используя либо две ближайшие точки данных, по одной в каждом кластере, либо две самые дальние, либо расстояние между центроидами и так далее. Определение индекса включает любую такую ​​формулировку, и сформированное таким образом семейство индексов называется индексами типа Данна. Позволять быть метрикой межкластерного расстояния между кластерами Cя и Cj.

Определение

С указанными выше обозначениями, если есть м кластеры, то индекс Данна для набора определяется как:

.

Объяснение

Определяясь таким образом, DI зависит от м, количество кластеров в наборе. Если количество кластеров априори неизвестно, м для чего DI может быть выбрано как максимальное количество кластеров. Есть также некоторая гибкость в определении термина д (х, у) где можно использовать любые хорошо известные показатели, например Манхэттенское расстояние или же Евклидово расстояние на основе геометрии задачи кластеризации. Эта формулировка имеет специфическую проблему в том, что если один из кластеров ведет себя плохо, а другие плотно упакованы, поскольку знаменатель содержит `` максимальный '' член вместо среднего члена, индекс Данна для этого набора кластеров будет нехарактерно низкий. Таким образом, это показатель наихудшего случая, и его следует иметь в виду. Есть готовые реализации индекса Данна на некоторых векторных языках программирования, таких как MATLAB, р и Apache Mahout.[3][4][5]

Примечания и ссылки

  1. ^ Данн, Дж. К. (17 сентября 1973 г.). «Нечеткий родственник процесса ISODATA и его использование в обнаружении компактных хорошо разделенных кластеров». Журнал кибернетики. 3 (3): 32–57. Дои:10.1080/01969727308546046. S2CID  120919314.
  2. ^ Данн, Дж. К. (1 сентября 1973 г.). «Хорошо разделенные кластеры и оптимальные нечеткие разбиения». Журнал кибернетики (опубликовано в 1974 г.). 4 (1): 95–104. Дои:10.1080/01969727408546059. ISSN  0022-0280.
  3. ^ "Реализация в MATLAB индекса Данна". Получено 5 декабря 2011.
  4. ^ Лукаш, Невегловски. "Пакет" clv'" (PDF). R проект. КРАН. Получено 2 апреля 2013.
  5. ^ "Apache Mahout". Фонд программного обеспечения Apache. Получено 9 мая 2013.

внешняя ссылка

  • Пахира, малайский к .; Bandyopadhyay, Sanghamitra; Маулик, Уджджвал (2004). «Индекс достоверности четких и нечетких кластеров». Распознавание образов. 37 (3): 487–501. Дои:10.1016 / j.patcog.2003.06.005.
  • Bezdek, J.C .; Пал, Н. (1995). «Кластерная проверка с обобщенными индексами Данна». Слушания, 1995 г. Вторая новозеландская международная двухпотоковая конференция по искусственным нейронным сетям и экспертным системам. IEEE Xplore: 190–193. Дои:10.1109 / ANNES.1995.499469. ISBN  0-8186-7174-2.
  • Алгоритмы кластерной валидности