Индекс Дэвиса-Булдина

Индекс Дэвиса-Булдина (DBI) , введенный Дэвидом Л. Дэвисом и Дональдом В. Боулдином в 1979 году, является метрикой для оценки алгоритмов кластеризации . Это схема внутренней оценки, в которой проверка того, насколько хорошо была выполнена кластеризация, осуществляется с использованием величин и функций, присущих набору данных. У этого метода есть недостаток: хорошее значение, полученное с помощью этого метода, не означает наилучшего извлечения информации.

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

Учитывая n мерных точек, пусть C _i будет кластером точек данных. Пусть X _j будет n -мерным вектором признаков, присвоенным кластеру C _i .

$S_{i}=\left({\frac {1}{T_{i}}}\sum _{j=1}^{T_{i}}{\left|\left|X_{j}-A_{i}\right|\right|_{p}^{q}}\right)^{1/q}$

Здесь $A_{i}$ — центр тяжести C i _, а Ti _— размер кластера i . $S_{i}$ — корень q -го момента из q -го момента точек в кластере i относительно среднего значения. Если $q=1$ затем $S_{i}$ — среднее расстояние между векторами признаков в кластере i и центроидом кластера. Обычно значение p равно 2, что делает расстояние евклидовой функцией расстояния . В случае многообразий и данных более высокой размерности можно использовать многие другие метрики расстояния, где евклидово расстояние может быть не лучшей мерой для определения кластеров. Важно отметить, что для получения значимых результатов эта метрика расстояния должна совпадать с метрикой, используемой в самой схеме кластеризации.

$M_{i,j}=\left|\left|A_{i}-A_{j}\right|\right|_{p}={\Bigl (}\displaystyle \sum _{k=1}^{n}\left|a_{k,i}-a_{k,j}\right|^{p}{\Bigr )}^{\frac {1}{p}}$

$M_{i,j}$ является мерой разделения между кластерами $C_{i}$ и кластер $C_{j}$.

$a_{k,i}$ является k- м элементом $A_{i}$, и таких элементов в A n , поскольку это n-мерный центроид.

Здесь k индексирует особенности данных, и это, по сути, евклидово расстояние между центрами кластеров i и j , когда p равно 2.

Определение

Пусть R _i,j будет мерой того, насколько хороша схема кластеризации. Эта мера по определению должна учитывать Mi _,j разделение между i ^й и Дж ^й кластер, который в идеале должен быть как можно большим, и Si _, разброс внутри кластера для кластера i, который должен быть как можно меньшим. Следовательно, индекс Дэвиса-Булдина определяется как отношение Si _{такое ,} и Mi _,j что эти свойства сохраняются:

1. $R_{i,j}\geqslant 0$.
2. $R_{i,j}=R_{j,i}$.
3. Когда $S_{j}\geqslant S_{k}$ и $M_{i,j}=M_{i,k}$ затем $R_{i,j}>R_{i,k}$.
4. Когда $S_{j}=S_{k}$ и $M_{i,j}\leqslant M_{i,k}$ затем $R_{i,j}>R_{i,k}$.

При такой формулировке, чем ниже значение, тем лучше разделение кластеров и «плотность» внутри кластеров.

Решение, удовлетворяющее этим свойствам:

$R_{i,j}={\frac {S_{i}+S_{j}}{M_{i,j}}}$

Это используется для определения D _i :

$D_{i}\equiv \max _{j\neq i}R_{i,j}$

Если N — количество кластеров:

${\mathit {DB}}\equiv {\frac {1}{N}}\displaystyle \sum _{i=1}^{N}D_{i}$

DB называется индексом Дэвиса-Булдина. Это зависит как от данных, так и от алгоритма. D _i выбирает наихудший сценарий, и это значение равно R _i,j для кластера, наиболее похожего на кластер i . У этой формулировки может быть множество вариаций, например, выбор среднего значения сходства кластера, средневзвешенного значения и т. д.

Объяснение

Более низкие значения индекса указывают на лучший результат кластеризации. Индекс улучшается (понижается) за счет увеличения разделения между кластерами и уменьшения вариаций внутри кластеров.

Эти условия ограничивают определенный таким образом индекс симметричным и неотрицательным. Из-за того, как оно определяется как функция отношения разброса внутри кластера к разделению между кластерами, более низкое значение будет означать, что кластеризация лучше. Это среднее сходство между каждым кластером и его наиболее похожим, усредненное по всем кластерам, где сходство определяется как S _i выше. Это подтверждает идею о том, что ни один кластер не должен быть похож на другой, и, следовательно, лучшая схема кластеризации по существу минимизирует индекс Дэвиса-Булдина. Определенный таким образом индекс представляет собой среднее значение по всем i кластерам, и, следовательно, хорошей мерой определения того, сколько кластеров на самом деле существует в данных, является отображение его в зависимости от количества кластеров, по которым он рассчитывается. Число i, для которого это значение является наименьшим, является хорошей мерой количества кластеров, на которые в идеале можно классифицировать данные. Это имеет применение при определении значения k в алгоритме kmeans , где значение k неизвестно априори.

Мягкая версия индекса Дэвиса-Булдина

Недавно индекс Дэвиса-Булдина был распространен на область категорий мягкой кластеризации. Это расширение основано на подходе кластеризации категорий в соответствии с рамками нечеткой логики . Отправной точкой для этой новой версии индекса проверки является результат данного алгоритма мягкой кластеризации (например, нечетких c-средних ), сформированный с помощью вычисленных разделов кластеризации и значений членства, связывающих элементы с кластерами. В мягкой области каждый элемент системы принадлежит каждому классу с учетом значений членства. Таким образом, эта мягкая версия индекса Дэвиса–Булдина способна учитывать, помимо стандартных мер проверки, таких как компактность и разделение кластеров, степень принадлежности элементов к классам.

Реализации

scikit -learn Библиотека Python с открытым исходным кодом предоставляет реализацию этой метрики в модуле sklearn.metrics.

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

Реализация Java находится в ELKI , и ее можно сравнить со многими другими индексами качества кластеризации.

См. также

• Оценка силуэта
• Индекс Данна
• Кластерный анализ
• Индекс Калинского-Харабаша
• Определение количества кластеров в наборе данных