A k-means based co-clustering (kCC) algorithm for sparse, high dimensional data. (15th March 2019)

• Record Type: Journal Article
• Authors: Hussain, Syed Fawad; Haris, Muhammad
• Is Part Of: Expert systems with applications. Volume 118(2019)
• Page Start: 20
• Page End: 34
• Publication Date: 2019-03-15
• Subjects: Clustering -- K-means -- Centroid initialization -- Co-clustering -- Semantic similarity; Expert systems (Computer science) -- Periodicals; Systèmes experts (Informatique) -- Périodiques; Electronic journals; 006.33
• DOI: 10.1016/j.eswa.2018.09.006
• Languages: English
• ISSNs: 0957-4174

Abstract

Highlights: A probabilistic random walk model for the 3 steps of the k -means algorithm. Mathematical foundation for efficacy and proofs for convergence is given. Clustering/co-clustering results show robustness, convergence and high accuracy. Abstract: The k -means algorithm is a widely used method that starts with an initial partitioning of the data and then iteratively converges towards the local solution by reducing the Sum of Squared Errors (SSE). It is known to suffer from the cluster center initialization problem and the iterative step simply (re-)labels the data points based on the initial partition. Most improvements to k -means proposed in the literature focus on the initialization step alone but make no attempt to guide the iterative convergence by exploiting statistical information from the data. Using higher order statistics (such as paths from random walks in a graph) and the duality in the data (as in co-clustering), for instance, are known ways to improve the clustering results. What is unique and significant in our proposed approach is that we embed these concepts into the k -means algorithm rather than just using them as an external distance measure and present a unified framework called the k -means based co-clustering ( k CC) Algorithm. The initialization step has been modified to include multiple points to represent each cluster center such that points within a cluster are close together but are far from points representing other clusters. Moreover, neighborhood walk statistics is proposed as a semantic similarity technique for both cluster assignment and center re-estimation in the iterative process. The effectiveness of the combined approach is evaluated on several standard data sets. Our results show that k CC performs better as compared to the baseline k-means and other state-of-the-art improvements.