A new separation measure for improving the effectiveness of validity indices

作者：Yue Shihong^*; Wang Jeen Shing; Wu Teresa; Wang Huaxiang

来源：Information Sciences, 2010, 180(5): 748-764.

DOI：10.1016/j.ins.2009.11.005

• Validity index
• Clustering
• Separation measure

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 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.

• 出版日期2010-3-1
• 单位天津大学