Code covered by the BSD License  

Highlights from
Modified & Generalized Dunn's index

Be the first to rate this file! 34 Downloads (last 30 days) File Size: 139 KB File ID: #42199
image thumbnail

Modified & Generalized Dunn's index

by

 

12 Jun 2013 (Updated )

An implementation of Modified and Generalized Dunn's index for internal cluster validation.

| Watch this File

File Information
Description

This package computes the modified Dunn's internal cluster validity index using the shortest paths in the neighbourhood graph (Ilc, 2012). It also includes an implementation of the original Dunn's index (Dunn, 1973), the generalized Dunn's index (Pal & Biswas, 1997), and a bunch of algorithms for building graphs on data.

Cluster validation index is a measure of quality of a data partition that is obtained from clustering algorithm. The internal indices evaluate the given partition of the data by measuring the compactness and the separation of the clusters on a basis of some objective criteria, without any information about how the true partition should look like. Original Dunn's index (Dunn, 1973) validates clusters of data by computing the compactness within clusters (maximum distance between any two points from the same cluster) and separation between clusters (minimal distance between two data points that belong to different clusters). Pal & Biswas proposed the generalization of Dunn's index using neighbourhood graph on data. Furthermore, Ilc proposed a modification of this approach based on the shortest paths in the graph. See references for additional explanation on this topic.

Supported neighbourhood graphs for cluster validation:
    - Gabriel graph
    - relative neighbourhood graph
    - epsilon-neighbourhood graph
    - Euclidean minimum spanning tree graph
    - directed kNN graph
    - mutual kNN graph
    - symmetric kNN graph

ACKNOWLEDGEMENTS
This package contains code contributed by the following authors, who made their work freely available:
    - Matthias Hein and Ulrike von Luxburg (http://www.ml.uni-saarland.de/GraphDemo/GraphDemo.html),
    - Richard E. Strauss (http://www.faculty.biol.ttu.edu/Strauss/Matlab/Matlab.htm),
    - Piotr Dollar (http://vision.ucsd.edu/~pdollar/toolbox/doc/),
    - Julian Ramos (http://www.mathworks.com/matlabcentral/fileexchange/27859)
Mentioned authors are greatly appreciated for their valuable contribution to this package.

REFERENCES
    Ilc, N. (2012). Modified Dunn’s cluster validity index based on graph theory. Przeglad Elektrotechniczny (Electrical Review), (2), 126-131.
    Pal, N. R., & Biswas, J. (1997). Cluster validation using graph theoretic concepts. Pattern Recognition, 30(6), 847-857.
    Dunn, J. C. (1973). A Fuzzy Relative of the ISODATA Process and Its Use in Detecting Compact Well-Separated Clusters. Journal of Cybernetics, 3(3), 32–57.

CURRENT VERSION: 1.1

Acknowledgements

Dunn's Index inspired this file.

MATLAB release MATLAB 7.14 (R2012a)
Tags for This File   Please login to tag files.
Please login to add a comment or rating.
Comments and Ratings (2)
02 Dec 2014 Nejc Ilc

Antonis, I can speculate that the problem lies in the input data you are using (too few unique data points). Can you send me your code and dataset, so I can do some debug?

17 Oct 2014 Antonis Alexiadis

the EMST option doesn't work(at least for me) i get the error Error using cgprechecks (line 41)
Not enough unique points specified.

Error in delaunayn (line 48)
cgprechecks(x, nargin, cg_opt);

Error in graph_EMST (line 38)
DT=delaunayn(data);

Error in graph_create (line 82)
[G,d] = graph_EMST(data,[]);

Error in indexDNg (line 66)
G=graph_create(data,labels,graph_type,options);

Updates
18 Jun 2013

version 1.1:
    - added original Dunn's index
    - updated demo.m
    - added new datasets: face, halfring, iris, wine

Contact us