Индекс Дэвиса – Болдина

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

Содержание

• 1 Предварительные сведения
• 2 Определение
• 3 Пояснение
• 4 См. Также
• 5 Внешний ссылки
• 6 Примечания и ссылки

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

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

$S\; i\; =\; (1\; T\; i\; \sum \; j\; =\; 1\; T\; i\; |\; X\; j\; -\; A\; i\; |\; p)\; 1\; /\; p\; \{\backslash \; displaystyle\; S\_\; \{i\}\; =\; \backslash \; left\; (\{\backslash \; frac\; \{1\}\; \{T\_\; \{i\}\}\}\; \backslash \; sum\; \_\; \{j\; =\; 1\}\; ^\; \{T\_\; \{i\}\}\; \{\backslash \; left\; |\; X\_\; \{j\}\; -A\_\; \{i\})\; \backslash \; right\; |\; ^\; \{p\}\}\; \backslash \; right)\; ^\; \{1\; /\; p\}\}$

Здесь $A\; i\; \{\backslash \; displaystyle\; A\_\; \{i\}\}$- центроид из C i и T i - это размер кластера i. S i - это мера разброса внутри кластера. Обычно значение p равно 2, что делает эту функцию евклидовым расстоянием между центроидом кластера и отдельными векторами признаков. Можно использовать многие другие метрики расстояния, в случае многообразий и данных более высокой размерности, где евклидово расстояние может быть не лучшим показателем для определения кластеров. Важно отметить, что эта метрика расстояния должна совпадать с метрикой, используемой в самой схеме кластеризации для получения значимых результатов.

$M\; i,\; j\; =\; |\; |\; A\; i\; -\; A\; j\; |\; |\; п\; знак\; равно\; (\sum \; К\; =\; 1\; N\; |\; ак,\; я\; -\; ак,\; J\; |\; п)\; 1\; п\; \{\backslash \; Displaystyle\; M\_\; \{я,\; j\}\; =\; \backslash \; left\; |\; \backslash \; left\; |\; A\_\; \{i\}\; -A\_\; \{j\}\; \backslash \; right\; |\; \backslash \; справа\; |\; \_\; \{p\}\; =\; \{\backslash \; Bigl\; (\}\; \backslash \; displaystyle\; \backslash \; sum\; \_\; \{k\; =\; 1\}\; ^\; \{n\}\; \backslash \; left\; |\; a\_\; \{k,\; i\}\; -a\_\; \{k,\; j\}\; \backslash \; right\; |\; ^\; \{p\}\; \{\; \backslash \; Bigr)\}\; ^\; \{\backslash \; frac\; \{1\}\; \{p\}\}\}$

$M\; i,\; j\; \{\backslash \; displaystyle\; M\_\; \{i,\; j\}\}$- мера разделения между кластером $C\; я\; \{\backslash \; displaystyle\; C\_\; \{i\}\}$и кластер $C\; j\; \{\backslash \; displaystyle\; C\_\; \{j\}\}$.

$ak,\; i\; \{\backslash \; displaystyle\; a\_\; \{k,\; i\}\}$- k-й элемент в $A\; i\; \{\backslash \; displaystyle\; A\_\; \{i\}\}$, и в A n таких элементов, поскольку это n-мерный центроид.

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

Определение

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

1. $R\; i,\; j\; ⩾\; 0\; \{\backslash \; displaystyle\; R\_\; \{i,\; j\}\; \backslash \; geqslant\; 0\}$.
2. $R\; i,\; j\; =\; R\; j,\; i\; \{\backslash \; displaystyle\; R\_\; \{i,\; j\}\; =\; R\_\; \{j,\; i\}\}$.
3. Когда $S\; j\; ⩾\; S\; к\; \{\backslash \; displaystyle\; S\_\; \{j\}\; \backslash \; geqslant\; S\_\; \{k\}\}$и $M\; i,\; j\; =\; M\; i,\; k\; \{\backslash \; displaystyle\; M\_\; \{i,\; j\}\; =\; M\_\; \{i,\; k\}\; \}$, затем $R\; i,\; j>R\; i,\; k\; \{\backslash \; displaystyle\; R\_\; \{i,\; j\}>R\_\; \{i,\; k\}\}$.
4. Когда $S\; j\; =\; S\; К\; \{\backslash \; Displaystyle\; S\_\; \{j\}\; =\; S\_\; \{k\}\}$и $M\; i,\; j\; ⩽\; M\; i,\; k\; \{\backslash \; displaystyle\; M\_\; \{i,\; j\}\; \backslash \; leqslant\; M\_\; \{i,\; k\}\}$, затем $R\; i,\; j>R\; i,\; k\; \{\backslash \; displaystyle\; R\_\; \{i,\; j\}>R\_\; \{i,\; k\}\}$.

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

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

$R\; i,\; j\; =\; S\; i\; +\; S\; j\; M\; i,\; j\; \{\backslash \; displaystyle\; R\_\; \{i,\; j\}\; =\; \{\backslash \; frac\; \{S\_\; \{i\}\; +\; S\_\; \{j\}\}\; \{M\_\; \{i,\; j\}\}\}\}$

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

$D\; i\; \equiv \; max\; j\; \ne \; i\; R\; i,\; j\; \{\backslash \; displaystyle\; D\_\; \{i\}\; \backslash \; Equiv\; \backslash \; max\; \_\; \{j\; \backslash \; neq\; i\}\; R\_\; \{i,\; j\}\}$

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

$DB\; \equiv \; 1\; N\; \sum \; i\; =\; 1\; ND\; i\; \{\backslash \; displaystyle\; \{\backslash \; mathit\; \{DB\}\}\; \backslash \; Equiv\; \{\; \backslash \; frac\; \{1\}\; \{N\}\}\; \backslash \; displaystyle\; \backslash \; sum\; \_\; \{i\; =\; 1\}\; ^\; \{N\}\; D\_\; \{i\}\}$

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

Объяснение

Эти условия ограничивают индекс, определенный таким образом, симметричным и неотрицательным. Из-за способа его определения как функции отношения разброса внутри кластера к расстоянию между кластерами более низкое значение будет означать, что кластеризация лучше. Это среднее сходство между каждым кластером и его наиболее похожим кластером, усредненное по всем кластерам, где сходство определено как S i выше. Это подтверждает идею о том, что ни один кластер не должен быть похож на другой, и, следовательно, лучшая схема кластеризации по существу минимизирует индекс Дэвиса – Болдина. Этот определенный таким образом индекс представляет собой среднее значение по всем кластерам i, и, следовательно, хорошей мерой для определения того, сколько кластеров фактически существует в данных, является его построение в зависимости от количества кластеров, для которых он рассчитывается. Число i, для которого это значение является наименьшим, является хорошей мерой количества кластеров, в которые данные могут быть идеально классифицированы. Это имеет приложения при определении значения k в алгоритме kmeans, где значение k неизвестно априори. Набор инструментов SOM содержит реализацию MATLAB. Реализация MATLAB также доступна через MATLAB Statistics and Machine Learning Toolbox, используя команду «evalclusters». Реализация Java находится в ELKI, и ее можно сравнить со многими другими индексами качества кластеризации.

См. Также

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

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

• 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

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