A new separation measure for improving the effectiveness of validity indices

Shihong Yue, Jeen Shing Wang, Teresa Wu, Huaxiang Wang

Research output: Contribution to journalArticlepeer-review

30 Scopus citations


Many validity indices have been proposed for quantitatively assessing the performance of clustering algorithms. One limitation of existing indices is their lack of generalizability, due to their dependence on the specific algorithms and structures of the data space. To handle large-scale datasets with arbitrary structures, this research study proposes a new cluster separation measure for improving the effectiveness of existing validity indices. This is achieved by partitioning the original data space into a grid-based structure which allows the introduction of a new measurement for assessing the true data distribution between any two clusters instead of the distance between the two cluster prototypes. To validate the effectiveness of the proposed separation measure, we adopt two commonly used validity indices, the Davies-Bouldin's function (DB) and Tibshirani's Gap statistic (GS). These indices are denoted as R-DB-1 and R-GS-1 for clusters with sphere-shaped structures and R-DB-2 and R-GS-2 for irregular-shaped structures. This integration enables the indices to evaluate both partitional algorithms and hierarchical algorithms. Partitional algorithms including C-Means (CM), Fuzzy C-Means (FCM), and hierarchical algorithms, including DBSCAN and CLIQUE, are used to test the performance of the new indices. Two synthetic datasets with spherical structures and four synthetic datasets with irregular shapes are first compared. Five real datasets from the UCI machine learning repository are then used to further test the measure's performance. The experimental results provide evidence that the new indices outperform the original indices.

Original languageEnglish (US)
Pages (from-to)748-764
Number of pages17
JournalInformation Sciences
Issue number5
StatePublished - Mar 1 2010


  • Clustering
  • Separation measure
  • Validity index

ASJC Scopus subject areas

  • Software
  • Control and Systems Engineering
  • Theoretical Computer Science
  • Computer Science Applications
  • Information Systems and Management
  • Artificial Intelligence


Dive into the research topics of 'A new separation measure for improving the effectiveness of validity indices'. Together they form a unique fingerprint.

Cite this