View source for Davies–Bouldin index

{{short description|Metric for evaluating clustering algorithms}}
{{Primary sources|date=May 2010}}

The '''Davies&ndash;Bouldin index (DBI)''', introduced by David L. Davies and Donald W. Bouldin in 1979, is a metric for evaluating [[clustering algorithm]]s.<ref>{{Cite journal | last1 = Davies | first1 = David L. | last2 = Bouldin | first2 = Donald W. | doi = 10.1109/TPAMI.1979.4766909 | title = A Cluster Separation Measure | journal = IEEE Transactions on Pattern Analysis and Machine Intelligence | volume = PAMI-1| issue = 2 | pages = 224–227 | year = 1979 | s2cid = 13254783 }}</ref> This is an internal evaluation scheme, where the validation of how well the clustering has been done is made using quantities and features inherent to the dataset. This has a drawback that a good value reported by this method does not imply the best information retrieval.{{Citation needed|reason=No justification given.|date=September 2019}}

==Preliminaries==
Given ''n'' dimensional points, let ''C''<sub>''i''</sub> be a cluster of data points. Let ''X''<sub>''j''</sub> be an ''n''-dimensional feature vector assigned to cluster ''C''<sub>''i''</sub>.

: <math> 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}</math>

Here <math>A_i</math> is the [[centroid]] of ''C''<sub>''i''</sub> and ''T''<sub>''i''</sub> is the size of the cluster ''i''.  <math> S_i</math> is the ''q''th root of the ''q''th moment of the points in cluster ''i'' about the mean. If <math> q=1</math> then <math> S_i</math> is the average distance between the feature vectors in cluster ''i'' and the centroid of the cluster. Usually the value of ''p'' is 2, which makes the distance a [[Euclidean distance]] function. Many other distance metrics can be used, in the case of [[manifolds]] and higher dimensional data, where the euclidean distance may not be the best measure for determining the clusters. It is important to note that this distance metric has to match with the metric used in the clustering scheme itself for meaningful results.

: <math> 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} </math>

: <math> M_{i,j}</math> is a measure of separation between cluster <math>C_i</math> and cluster <math>C_j</math>.

: <math> a_{k,i} </math> is the ''k''th element of <math>A_i</math>, and there are n such elements in ''A'' for it is an n dimensional centroid.{{inconsistent|reason=a_ki not used in definition of S above}}

Here ''k'' indexes the features of the data, and this is essentially the [[Euclidean distance]] between the centers of clusters ''i'' and ''j'' when ''p'' equals 2.

==Definition==

Let ''R''<sub>''i,j''</sub> be a measure of how good the clustering scheme is. This measure, by definition has to account for ''M''<sub>''i,j''</sub> the separation between the ''i''<sup>''th''</sup> and the ''j''<sup>''th''</sup> cluster, which ideally has to be as large as possible, and ''S''<sub>''i''</sub>, the within cluster scatter for cluster i, which has to be as low as possible. Hence the Davies–Bouldin index is defined as the ratio of ''S''<sub>''i''</sub> and ''M''<sub>''i,j''</sub> such that these properties are conserved:

#  <math> R_{i,j} \geqslant 0 </math>.
#  <math> R_{i,j} = R_{j,i} </math>.
#  When <math> S_j \geqslant S_k </math> and <math> M_{i,j} = M_{i,k} </math> then <math> R_{i,j} > R_{i,k} </math>.
#  When <math> S_j = S_k </math> and <math> M_{i,j} \leqslant M_{i,k} </math> then <math> R_{i,j} > R_{i,k} </math>.
With this formulation, the lower the value, the better the separation of the clusters and the 'tightness' inside the clusters.

A solution that satisfies these properties is:
: <math> R_{i,j} = \frac{S_i + S_j}{M_{i,j}} </math>

This is used to define ''D''<sub>''i''</sub>:
: <math> D_i \equiv \max_{j \neq i} R_{i,j}</math>

If N is the number of clusters:

: <math> \mathit{DB} \equiv \frac{1}{N}\displaystyle\sum_{i=1}^N D_i</math>

''DB'' is called the Davies–Bouldin index. This is dependent both on the data as well as the algorithm. ''D''<sub>''i''</sub> chooses the worst-case scenario, and this value is equal to ''R''<sub>''i,j''</sub> for the most similar cluster to cluster ''i''. There could be many variations to this formulation, like choosing the average of the cluster similarity, weighted average and so on.

==Explanation==
Lower index values indicate a better clustering result. The index is improved (lowered) by increased separation between clusters and decreased variation within clusters.

These conditions constrain the index so defined to be symmetric and non-negative. Due to the way it is defined, as a function of the ratio of the within cluster scatter, to the between cluster separation, a lower value will mean that the clustering is better. It happens to be the average similarity between each cluster and its most similar one, averaged over all the clusters, where the similarity is defined as ''S''<sub>''i''</sub> above. This affirms the idea that no cluster has to be similar to another, and hence the best clustering scheme essentially minimizes the Davies–Bouldin index. This index thus defined is an average over all the ''i'' clusters, and hence a good measure of deciding how many clusters actually exists in the data is to plot it against the number of clusters it is calculated over. The number ''i'' for which this value is the lowest is a good measure of the number of clusters the data could be ideally classified into. This has applications in deciding the value of ''k'' in the [[kmeans]] algorithm, where the value of k is not known apriori.

== Soft version of Davies-Bouldin index ==
Recently, the Davies–Bouldin index has been extended to the domain of soft clustering categories.<ref>{{Cite book |last1=Vergani |first1=Alberto A. |last2=Binaghi |first2=Elisabetta |date=July 2018 |title=A Soft Davies-Bouldin Separation Measure |url=https://ieeexplore.ieee.org/document/8491581 |publisher=IEEE |pages=1–8 |doi=10.1109/FUZZ-IEEE.2018.8491581 |isbn=978-1-5090-6020-7}}</ref> This extension is based on the category clustering approach according to the framework of [[fuzzy logic]]. The starting point for this new version of the validation index is the result of a given soft clustering algorithm (e.g. [[Fuzzy C-means clustering|fuzzy c-means]]), shaped with the computed clustering partitions and membership values associating the elements with the clusters. In the soft domain, each element of the system belongs to every classes, given the membership values. Therefore, this soft version of the Davies–Bouldin index is able to take into account, in addition to standard validation measures such as [[Compactness measure|compactness]] and separation of clusters, the degree to which elements belong to classes.

== Implementations ==

The [[scikit-learn]] Python [[open source]] library provides an implementation of this metric in the sklearn.metrics module.<ref>{{Cite web |title=sklearn.metrics.davies_bouldin_score |url=https://scikit-learn.org/stable/modules/generated/sklearn.metrics.davies_bouldin_score.html |access-date=2023-11-22 |website=scikit-learn |language=en}}</ref>

[[R (programming language)|R]] provides a similar implementation in its ''clusterSim'' package.<ref>{{Cite web |title=R: Davies-Bouldin index |url=https://search.r-project.org/CRAN/refmans/clusterSim/html/index.DB.html |access-date=2023-11-22 |website=search.r-project.org}}</ref>

A [[Java (programming language)|Java]] implementation is found in [[ELKI]], and can be compared to many other clustering quality indexes.

== See also ==
* [[Silhouette (clustering)|Silhouette score]]
* [[Dunn index]]
* [[Cluster analysis#Evaluation and assessment|Cluster analysis]]
* [[Calinski-Harabasz index]]
* [[Determining the number of clusters in a data set]]

== Notes and references ==
{{Reflist}}

{{Machine learning evaluation metrics}}

{{DEFAULTSORT:Davies-Bouldin index}}
[[Category:Clustering criteria]]