Индекс Дэвиса – Боулдина - Davies–Bouldin index

В Индекс Дэвиса – Болдина (DBI), введенный Дэвидом Л. Дэвисом и Дональдом В. Боулдином в 1979 году, является метрикой для оценки алгоритмы кластеризации.^[1] Это внутренняя схема оценки, при которой проверка того, насколько хорошо была выполнена кластеризация, осуществляется с использованием количественных характеристик и характеристик, присущих набору данных. Это имеет недостаток, заключающийся в том, что хорошее значение, сообщаемое этим методом, не означает наилучшего поиска информации.^{[нужна цитата ]}

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

Данный п размерные точки, пусть C_я быть кластером точек данных. Позволять Икс_j быть п-мерный вектор признаков, присвоенный кластеру C_я.

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

Здесь ${\displaystyle A_{i}}$ это центроид из C_я и Т_я это размер кластера я. S_я - мера разброса внутри кластера. Обычно значение п равно 2, что делает это Евклидово расстояние функция между центроидом кластера и отдельными векторами признаков. Можно использовать многие другие метрики расстояния в случае коллекторы и данные более высокой размерности, где евклидово расстояние может быть не лучшим показателем для определения кластеров. Важно отметить, что эта метрика расстояния должна совпадать с метрикой, используемой в самой схеме кластеризации для получения значимых результатов.

${\displaystyle 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}}}$

${\displaystyle M_{i,j}}$ мера разделения кластера ${\displaystyle C_{i}}$ и кластер ${\displaystyle C_{j}}$.

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

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

Определение

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

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

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

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

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

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

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

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

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

БД называется индексом Дэвиса – Боулдина. Это зависит как от данных, так и от алгоритма. D_я выбирает наихудший сценарий, и это значение равно р_{я, j} для наиболее похожего кластера на кластер я. У этой формулировки может быть много вариаций, таких как выбор среднего значения кластерного сходства, средневзвешенного значения и так далее.

Объяснение

Эти условия ограничивают индекс, определенный таким образом, симметричным и неотрицательным. Из-за способа его определения как функции отношения разброса внутри кластера к расстоянию между кластерами меньшее значение будет означать, что кластеризация лучше. Это среднее сходство между каждым кластером и его наиболее похожим кластером, усредненное по всем кластерам, где сходство определяется как S_я над. Это подтверждает идею о том, что ни один кластер не должен быть похож на другой, и, следовательно, лучшая схема кластеризации по существу минимизирует индекс Дэвиса-Боулдина. Этот индекс, определенный таким образом, является средним по всем я кластеров, и, следовательно, хорошей мерой для определения того, сколько кластеров на самом деле существует в данных, является построение графика в сравнении с количеством кластеров, для которых они вычисляются. Номер я для которого это значение является наименьшим, является хорошей мерой количества кластеров, в которые можно идеально классифицировать данные. Это имеет применение при определении ценности k в kсредний алгоритм, где значение k неизвестно априори. Набор инструментов SOM содержит MATLAB выполнение.^[2] Реализация MATLAB также доступна через MATLAB Statistics and Machine Learning Toolbox, используя команду «evalclusters».^[3] А Ява реализация находится в ELKI, и его можно сравнить со многими другими индексами качества кластеризации.

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

• Силуэт (кластеризация)
• Индекс Данна

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

• http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.17.2072
• https://books.google.com/books?id=HY8gB2OIqSoC
• http://nl.mathworks.com/help/stats/clustering.evaluation.daviesbouldinevaluation-class.html

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

1. Дэвис, Дэвид Л .; Боулдин, Дональд В. (1979). «Мера разделения кластеров». IEEE Transactions по анализу шаблонов и машинному анализу. ПАМИ-1 (2): 224–227. Дои:10.1109 / TPAMI.1979.4766909.
2. «Реализация Matlab». Получено 12 ноября 2011.
3. «Оцените решения кластеризации - MATLAB evalclusters».