Dunn index

The Dunn index (DI) (introduced by J. C. Dunn in 1974) is a metric for evaluating clustering algorithms.^[1]^[2] This is part of a group of validity indices including the Davies–Bouldin index or Silhouette index, in that it is an internal evaluation scheme, where the result is based on the clustered data itself. As do all other such indices, the aim is to identify sets of clusters that are compact, with a small variance between members of the cluster, and well separated, where the means of different clusters are sufficiently far apart, as compared to the within cluster variance. For a given assignment of clusters, a higher Dunn index indicates better clustering. One of the drawbacks of using this is the computational cost as the number of clusters and dimensionality of the data increase.

Preliminaries

There are many ways to define the size or diameter of a cluster. It could be the distance between the farthest two points inside a cluster, it could be the mean of all the pairwise distances between data points inside the cluster, or it could as well be the distance of each data point from the cluster centroid. Each of these formulations are mathematically shown below:

Let C_i be a cluster of vectors. Let x and y be any two n dimensional feature vectors assigned to the same cluster C_i.

\Delta _{i}={\underset {x,y\in C_{i}}{{\text{max}}}}d(x,y)

, which calculates the maximum distance.

\Delta _{i}={\dfrac {1}{|C_{i}|(|C_{i}|-1)}}{\underset {x,y\in C_{i},x\neq y}{\sum }}d(x,y)

, which calculates the mean distance between all pairs.

\Delta _{i}={\dfrac {{\underset {x\in C_{i}}{\sum }}d(x,\mu )}{|C_{i}|}},\mu ={\dfrac {{\underset {x\in C_{i}}{\sum }}x}{|C_{i}|}}

, calculates distance of all the points from the mean.

This can also be said about the intercluster distance, where similar formulations can be made, using either the closest two data points, one in each cluster, or the farthest two, or the distance between the centroids and so on. The definition of the index includes any such formulation, and the family of indices so formed are called Dunn-like Indices. Let

\delta (C_{i},C_{j})

be this intercluster distance metric, between clusters C_i and C_j.

Definition

With the above notation, if there are m clusters, then the Dunn Index for the set is defined as:

\mathit{DI}_m = \frac{ \underset{ 1 \leqslant i < j \leqslant m}{\text{min}} \left.\delta(C_i,C_j)\right.}{ \underset{ 1 \leqslant k \leqslant m}{\text{max}} \left.\Delta_k\right.}

Explanation

Being defined in this way, the DI depends on m, the number of clusters in the set. If the number of clusters is not known apriori, the m for which the DI is the highest can be chosen as the number of clusters. There is also some flexibility when it comes to the definition of d(x,y) where any of the well known metrics can be used, like Manhattan distance or Euclidean distance based on the geometry of the clustering problem. This formulation has a peculiar problem, in that if one of the clusters is badly behaved, where the others are tightly packed, since the denominator contains a 'max' term instead of an average term, the Dunn Index for that set of clusters will be uncharacteristically low. This is thus a worst case indicator, and has to be kept in mind. There are ready implementations of the Dunn index in some vector based programming languages like MATLAB, R and Apache Mahout.^[3]^[4]^[5]

Notes and references

↑ Dunn, J. C. (1973-09-17). "A Fuzzy Relative of the ISODATA Process and Its Use in Detecting Compact Well-Separated Clusters". Journal of Cybernetics. 3 (3): 32–57. doi:10.1080/01969727308546046. CS1 maint: Date and year (link)
↑ Dunn, J. C. (1973-09-01). "Well-Separated Clusters and Optimal Fuzzy Partitions". Journal of Cybernetics (published 1974). 4 (1): 95–104. ISSN 0022-0280. doi:10.1080/01969727408546059.
↑ "MATLAB implementation of the Dunn Index". Retrieved 5 December 2011.
↑ Lukasz, Nieweglowski. "Package ‘clv’" (PDF). R project. CRAN. Retrieved 2 April 2013.
↑ "Apache Mahout". Apache Software Foundation. Retrieved 9 May 2013.

External links

"Validity index for crisp and fuzzy clusters". Pattern Recognition. 37: 487–501. doi:10.1016/j.patcog.2003.06.005.
http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=499469
http://machaon.karanagai.com/validation_algorithms.html

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.