A Formal Algorithm for Verifying the Validity of Clustering Results Based on Model Checking
Authors:
Open Access
- 7 March 2014
- journal article
- research article
- Published by Public Library of Science (PLoS) in PLOS ONE
- Vol. 9 (3) , e90109
Abstract
The limitations in general methods to evaluate clustering will remain difficult to overcome if verifying the clustering validity continues to be based on clustering results and evaluation index values. This study focuses on a clustering process to analyze crisp clustering validity. First, we define the properties that must be satisfied by valid clustering processes and model clustering processes based on program graphs and transition systems. We then recast the analysis of clustering validity as the problem of verifying whether the model of clustering processes satisfies the specified properties with model checking. That is, we try to build a bridge between clustering and model checking. Experiments on several datasets indicate the effectiveness and suitability of our algorithms. Compared with traditional evaluation indices, our formal method can not only indicate whether the clustering results are valid but, in the case the results are invalid, can also detect the objects that have led to the invalidity.Keywords
This publication has 25 references indexed in Scilit:
- A Survey on Internal Validity Measure for Cluster ValidationInternational Journal of Computer Science & Engineering Survey, 2010
- Relative clustering validity criteria: A comparative overviewStatistical Analysis and Data Mining: An ASA Data Science Journal, 2010
- Model checkingCommunications of the ACM, 2009
- The Transcriptome of the Intraerythrocytic Developmental Cycle of Plasmodium falciparumPLOS Biology, 2003
- Clustering validity checking methodsACM SIGMOD Record, 2002
- A new cluster-validity for fuzzy clusteringPattern Recognition, 1999
- BIRCHACM SIGMOD Record, 1996
- Verification of the Futurebus+ cache coherence protocolFormal Methods in System Design, 1995
- Automatic verification of finite-state concurrent systems using temporal logic specificationsACM Transactions on Programming Languages and Systems, 1986
- Using branching time temporal logic to synthesize synchronization skeletonsScience of Computer Programming, 1982