Индекс Данна

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

Предварительные сведения

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

Пусть C _{i —} кластер векторов. Пусть x и y будут любыми двумя n-мерными векторами признаков, присвоенными одному и тому же кластеру C _i .

$\Delta _{i}={\underset {x,y\in C_{i}}{\text{max}}}d(x,y)$ , который вычисляет максимальное расстояние (версия, предложенная Данном).

$\Delta _{i}={\dfrac {2}{|C_{i}|(|C_{i}|-1)}}{\underset {x,y\in C_{i},x\neq y}{\sum }}d(x,y)$ , который вычисляет среднее расстояние между всеми парами.

$\Delta _{i}={\dfrac {{\underset {x\in C_{i}}{\sum }}d(x,\mu )}{|C_{i}|}},\mu ={\dfrac {{\underset {x\in C_{i}}{\sum }}x}{|C_{i}|}}$ , вычисляет расстояние всех точек от среднего значения.

То же самое можно сказать и о расстоянии между кластерами, где аналогичные формулировки могут быть сделаны с использованием либо двух ближайших точек данных (используемых Данном), по одной в каждом кластере, либо двух самых дальних, либо расстояния между центроидами и так далее. Определение индекса включает любую такую ​​формулировку, а семейство индексов, сформированных таким образом, называется индексами типа Данна. Позволять $\delta (C_{i},C_{j})$ быть этой метрикой межкластерного расстояния между кластерами C _i и C _j .

Определение

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

${\mathit {DI}}_{m}={\frac {{\underset {1\leqslant i<j\leqslant m}{\text{min}}}\left.\delta (C_{i},C_{j})\right.}{{\underset {1\leqslant k\leqslant m}{\text{max}}}\left.\Delta _{k}\right.}}$.

Объяснение

Будучи определенным таким образом, DI зависит от m , количества кластеров в наборе. Если количество кластеров заранее неизвестно, m , для которого DI в качестве количества кластеров можно выбрать является наибольшим. Существует также некоторая гибкость, когда дело доходит до определения d(x,y) , где можно использовать любую из хорошо известных метрик, таких как Манхэттенское расстояние или Евклидово расстояние, основанное на геометрии задачи кластеризации. У этой формулировки есть своеобразная проблема: если один из кластеров ведет себя плохо, а остальные плотно упакованы, поскольку знаменатель содержит «максимальный» член вместо среднего, индекс Данна для этого набора кластеров будет равен нехарактерно низкий. Таким образом, это худший показатель, и его следует иметь в виду. Существуют готовые реализации индекса Данна в некоторых векторных языках программирования, таких как MATLAB , R и Apache Mahout .

Внешние ссылки

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