Authors: Vasudha Bhatnagar; Sangeeta Ahuja; Sharanjit Kaur
Addresses: Department of Computer Science, Faculty of Mathematical Sciences, University of Delhi, Delhi – 110 007, India ' Divison of Computer Applications, IASRI (ICAR), New Delhi – 110012, India ' Department of Computer Science, Acharya Narendra Dev College, University of Delhi, Gobindpuri, Kalkaji, New Delhi – 110019, India
Abstract: The problem of instability and non-robustness in K-means clustering has been recognised as a serious problem in both scientific and business applications. Further, these problems get accentuated in the presence of outliers in data. Cluster ensemble technique has been recently developed to combat such problems and improve overall quality of clustering scheme. In this paper, we propose a cluster ensemble method based on discriminant analysis to obtain robust clustering and report noise to the user. Clustering schemes are generated by the partitional clustering algorithm (K-means) for constructing the ensemble. The proposed algorithm operates in three phases. During the first phase, input clustering schemes are reconciled by relabeling the clusters corresponding to an arbitrary reference scheme. This is accomplished using Hungarian algorithm, which is a well-known optimisation approach. The second phase uses discriminant analysis and constructs a label matrix that is used for generating consensus partition. In the final stage, clustering scheme is refined to deliver robust and stable clustering scheme. Empirical evaluation of the algorithm shows that the proposed method significantly improves the quality of resultant ensemble. Further, comparison with the cluster ensembles generated by package R for 20 public datasets demonstrated improved quality of ensembles generated by the proposed algorithm.
Keywords: k-means clustering; cluster ensembles; discriminant analysis; consistency; optimisation.
International Journal of Data Mining, Modelling and Management, 2015 Vol.7 No.2, pp.83 - 107
Published online: 06 May 2015 *Full-text access for editors Access for subscribers Purchase this article Comment on this article