Cluster validation using graph theoretic concepts

Pattern RecognitionPublished 1 June 1997

Nikhil R. Pal, Jayabrata Biswas

DOI10.1016/s0031-3203(96)00127-6

Source URL

Citations165

SJR quartileQ1

SJR score2.06

SNIP2.67

TL;DR

The generalized Dunn's index and the Davies-Bouldin index for cluster validation using graph structures, such as GG, RNG and MST are generalized and superiority over some existing cluster validity indices is established.

Abstract

In this article we have generalized Dunn's index and the Davies-Bouldin index for cluster validation using graph structures, such as GG, RNG and MST. Unlike Dunn's index and the Davies-Bouldin index, the proposed indices are not sensitive to noisy points and are applicable to hyperspherical and structural clusters as well. The relationships between various indices have also been established. The effectiveness of the generalized indices and superiority over some existing cluster validity indices are established using eight data sets.

Keywords

Computer ScienceDecision Sciences

Pattern classification and scene analysis

12,643 Citations1973Richard O. Duda, Peter E. Hart

BiometricsApplied Multivariate Statistical Analysis.

11,424 Citations1988Andrea Johnson, Dean W. Wichern

IEEE Transactions on Pattern Analysis and Machine IntelligenceA Cluster Separation Measure

8,543 Citations1979David L. Davies, Donald W. Bouldin

A measure is presented which indicates the similarity of clusters which are assumed to have a data density which is a decreasing function of distance from a vector characteristic of the cluster which can be used to infer the appropriateness of data partitions.

IEEE Transactions on Fuzzy SystemsOn cluster validity for the fuzzy c-means model

1,839 Citations1995Nikhil R. Pal, James C. Bezdek

Limitation analysis indicates, and numerical experiments confirm, that the Fukuyama-Sugeno index is sensitive to both high and low values of m and may be unreliable because of this, and calculations suggest that the best choice for m is probably in the interval [1.5, 2.5], whose mean and midpoint, m=2, have often been the preferred choice for many users of FCM.

IEEE Transactions on ComputersGraph-Theoretical Methods for Detecting and Describing Gestalt Clusters

1,741 Citations1971C. T. Zahn

A family of graph-theoretical algorithms based on the minimal spanning tree are capable of detecting several kinds of cluster structure in arbitrary point sets; description of the detected clusters is possible in some cases by extensions of the method.

IEEE Transactions on Systems Man and Cybernetics Part B (Cybernetics)Some new indexes of cluster validity

1,142 Citations1998James C. Bezdek, Nikhil R. Pal

Pattern RecognitionThe relative neighbourhood graph of a finite planar set

988 Citations1980Godfried T. Toussaint

The ability of the RNG to extract a perceptually meaningful structure from the set of points is briefly discussed and compared to that of two other graph structures: the minimal spanning tree and the Delaunay (Voronoi) triangulation.

Pattern RecognitionValidity studies in clustering methodologies

300 Citations1979Richard C. Dubes, Anil K. Jain

This paper provides a semi-tutorial review of the state-of-the-art in cluster validity, or the verification of results from clustering algorithms, and covers ways of measuring clustering tendency, the fit of hierarchical and partitional structures and indices of compactness and isolation for individual clusters.

Pattern RecognitionGraph theoretical clustering based on limited neighbourhood sets

173 Citations1982R.B. Urquhart

The method is locally sensitive, hierarchic and based on the concept of limited neighbourhood sets, which means clusters that are either disjoint or homogeneous and separable by sharp changes in point density may be detected.