Критерий Данна

Критерий Данна — это количественная мера качества разбиения множества объектов на кластеры, используемая в задачах кластеризации. Он оценивает, насколько компактно расположены объекты внутри каждого кластера и насколько хорошо кластеры отделены друг от друга. Критерий Данна был предложен Дж. К. Данном в 1974 году как внутренняя метрика оценки кластеризации, не требующая внешних данных (например, известных меток классов). Чем выше значение критерия, тем более качественным считается разбиение, так как оно соответствует принципу максимальной компактности и минимального перекрытия кластеров.

Определение

Критерий Данна (Dunn index, DI) определяется как отношение минимального межкластерного расстояния к максимальному внутрикластерному диаметру. Формально, для заданного разбиения множества объектов на \(k\) кластеров \(C_1, C_2, \dots, C_k\) критерий вычисляется по формуле:

\[ DI = \frac{\min_{1 \le i < j \le k} \delta(C_i, C_j)}{\max_{1 \le l \le k} \Delta(C_l)} \]

где:

• \(\delta(C_i, C_j)\) — расстояние между кластерами \(C_i\) и \(C_j\) (межкластерное расстояние);
• \(\Delta(C_l)\) — диаметр кластера \(C_l\) (внутрикластерное расстояние).

Компоненты критерия

Межкластерное расстояние \(\delta(C_i, C_j)\) обычно определяется как минимальное расстояние между любой парой точек из разных кластеров (single-linkage):

\[ \delta(C_i, C_j) = \min_{x \in C_i, y \in C_j} d(x, y) \]

где \(d(x, y)\) — метрика расстояния между объектами (чаще всего евклидово расстояние). Возможны и другие варианты, например, расстояние между центроидами или максимальное расстояние между точками (complete-linkage), но классическое определение использует минимальное расстояние.

Внутрикластерный диаметр \(\Delta(C_l)\) — это максимальное расстояние между любыми двумя точками внутри одного кластера:

\[ \Delta(C_l) = \max_{x, y \in C_l} d(x, y) \]

Таким образом, числитель критерия отражает степень разделимости кластеров (чем больше минимальное расстояние между разными кластерами, тем лучше), а знаменатель — степень компактности (чем меньше максимальный диаметр кластера, тем лучше).

Свойства и интерпретация

Критерий Данна является безразмерной величиной. Его значение может варьироваться от 0 до бесконечности, но на практике для большинства наборов данных оно находится в диапазоне от 0 до 1 или немного выше. Идеальное разбиение, при котором все кластеры бесконечно удалены друг от друга и имеют нулевой диаметр (каждый кластер состоит из одной точки), даёт бесконечное значение, но в реальных задачах это недостижимо.

• Высокое значение DI (близкое к 1 или больше) указывает на то, что кластеры компактны и хорошо разделены. Это свидетельствует о качественном разбиении.
• Низкое значение DI (близкое к 0) говорит о том, что кластеры либо сильно перекрываются, либо имеют большой разброс точек, что указывает на плохое качество кластеризации.
• Нулевое значение возможно, если хотя бы один кластер имеет нулевой диаметр (состоит из одной точки) и при этом минимальное межкластерное расстояние равно нулю (точки из разных кластеров совпадают), что на практике встречается редко.

Критерий Данна не имеет фиксированного порога «хорошего» или «плохого» значения. Его основное применение — сравнение различных разбиений одного и того же набора данных (например, с разным числом кластеров или разными алгоритмами). Разбиение с большим значением DI считается предпочтительным.

История

Критерий был впервые описан Дж. К. Данном в статье «Well-Separated Clusters and Optimal Fuzzy Partitions» (1974), опубликованной в Journal of Cybernetics. Данн работал над задачами нечёткой кластеризации (fuzzy clustering), где объект может принадлежать нескольким кластерам с разной степенью. Однако предложенный им индекс оказался применим и для жёсткой (чёткой) кластеризации, где каждый объект принадлежит ровно одному кластеру. Впоследствии критерий Данна стал одной из базовых внутренних метрик оценки кластеризации, наряду с индексом силуэта и индексом Калинского-Харабаса.

Применение

Критерий Данна используется в следующих задачах:

1. Выбор оптимального числа кластеров. При запуске алгоритма кластеризации (например, k-средних) с разным количеством кластеров \(k\) вычисляют значение DI для каждого разбиения. Оптимальным считается \(k\), при котором DI достигает максимума.
2. Сравнение алгоритмов кластеризации. Для одного и того же набора данных можно применить разные алгоритмы (например, k-средних, DBSCAN, иерархическую кластеризацию) и сравнить их результаты по критерию Данна.
3. Оценка устойчивости кластеризации. Если при небольших изменениях параметров алгоритма значение DI резко меняется, это может указывать на неустойчивость разбиения.
4. Валидация результатов в биоинформатике, маркетинге, анализе текстов и других областях, где кластеризация используется для выявления скрытых структур в данных.

Пример использования

Предположим, имеется набор данных из 10 точек, которые нужно разбить на 2 кластера. После применения алгоритма k-средних получены два кластера:

• Кластер 1: точки A, B, C (расстояния между ними: AB=1, AC=1.5, BC=1.2 → максимальное = 1.5).
• Кластер 2: точки D, E, F (расстояния: DE=0.8, DF=1.1, EF=0.9 → максимальное = 1.1).
• Минимальное расстояние между точками из разных кластеров: между A и D = 3.0, между B и E = 2.5, между C и F = 2.8 → минимальное = 2.5.

Тогда:

• \(\max \Delta = \max(1.5, 1.1) = 1.5\)
• \(\min \delta = 2.5\)
• \(DI = 2.5 / 1.5 \approx 1.67\)

Это высокое значение, указывающее на хорошее разделение кластеров.

Ограничения и критика

Несмотря на широкое применение, критерий Данна имеет ряд недостатков:

1. Чувствительность к выбросам. Поскольку в числителе используется минимальное межкластерное расстояние, а в знаменателе — максимальный диаметр, даже одна точка-выброс может сильно исказить значение критерия. Например, если один кластер содержит точку, далеко отстоящую от остальных, диаметр резко возрастает, что снижает DI, даже если в целом кластеризация качественная.
2. Монотонная зависимость от числа кластеров. С увеличением числа кластеров диаметры кластеров обычно уменьшаются (кластеры становятся меньше), а межкластерные расстояния могут как увеличиваться, так и уменьшаться. Это может приводить к тому, что DI не всегда монотонно растёт с улучшением качества, а иногда даёт ложные пики.
3. Вычислительная сложность. Для вычисления DI необходимо найти все попарные расстояния между точками внутри каждого кластера и между кластерами. В худшем случае (при большом числе точек) сложность составляет \(O(n^2)\), что делает критерий затратным для больших наборов данных.
4. Зависимость от метрики. Значение DI сильно зависит от выбора функции расстояния \(d(x, y)\). Использование разных метрик (евклидовой, манхэттенской, косинусной) может давать разные результаты, что затрудняет сравнение.
5. Неприменимость для кластеров сложной формы. Критерий Данна предполагает, что кластеры имеют сферическую или компактную форму. Для кластеров вытянутой, спиралевидной или вложенной формы (например, в данных типа «луна» или «кольцо») критерий может давать заниженные оценки, даже если визуально кластеризация корректна.

Модификации

Для преодоления некоторых ограничений были предложены модификации критерия Данна:

• Обобщённый критерий Данна (Generalized Dunn Index). Вместо минимального межкластерного расстояния и максимального диаметра используются другие меры, например, среднее расстояние между центроидами или средний диаметр кластеров.
• Критерий Данна с использованием других метрик. Например, для кластеров неправильной формы применяют расстояние по кратчайшему пути в графе (graph distance) или меру, основанную на плотности.
• Нормализованный критерий Данна. Значение DI нормируется на число кластеров или размер данных, чтобы уменьшить зависимость от масштаба.

Сравнение с другими метриками

Критерий Данна часто сравнивают с индексом силуэта (Silhouette index) и индексом Калинского-Харабаса (Calinski-Harabasz index). Основные различия:

• Индекс силуэта учитывает не только расстояния между кластерами, но и расстояния до ближайшего соседнего кластера для каждой точки, что делает его более устойчивым к выбросам, но более затратным по времени.
• Индекс Калинского-Харабаса основан на дисперсионном анализе и оценивает отношение межкластерной дисперсии к внутрикластерной. Он менее чувствителен к форме кластеров, но может давать завышенные оценки при увеличении числа кластеров.
• Критерий Данна проще в вычислении и интерпретации, но более чувствителен к выбросам и форме кластеров.

На практике рекомендуется использовать несколько метрик одновременно для валидации кластеризации.

Источники

• Dunn, J. C. (1974). «Well-Separated Clusters and Optimal Fuzzy Partitions». Journal of Cybernetics, 4(1), 95–104.
• Halkidi, M., Batistakis, Y., & Vazirgiannis, M. (2001). «On Clustering Validation Techniques». Journal of Intelligent Information Systems, 17(2–3), 107–145.
• Bezdek, J. C., & Pal, N. R. (1998). «Some New Indexes of Cluster Validity». IEEE Transactions on Systems, Man, and Cybernetics, Part B, 28(3), 301–315.
• Jain, A. K., & Dubes, R. C. (1988). Algorithms for Clustering Data. Prentice-Hall.