I-k-means−+: An iterative clustering algorithm based on an enhanced version of the k-means. (July 2018)

• Record Type: Journal Article
• Authors: Ismkhan, Hassan
• Is Part Of: Pattern recognition. Volume 79(2018:Jul.)
• Page Start: 402
• Page End: 413
• Publication Date: 2018-07
• Subjects: k-means -- Solution improving -- Accurate k-means -- Iterative improvement; Pattern perception -- Periodicals; Perception des structures -- Périodiques; Patroonherkenning; 006.4
• DOI: 10.1016/j.patcog.2018.02.015
• Languages: English
• ISSNs: 0031-3203

Abstract

Highlights: I-k-means−+ utilizes some heuristics and an enhanced version of the k -means. For all datasets, accuracy of I-k-means−+ is higher than k -means. For some datasets, I-k-means−+ is faster than the k -means. Except one dataset, for all datasets, accuracy of I-k-means−+ is higher than k-means++. For a dataset, I-k-means−+ is about 15 times faster than k-means++. Abstract: The k -means tries to minimize the sum of the squared Euclidean distance from the mean (SSEDM) of each cluster as its objective function. Although this algorithm is effective, it is too sensitive to initial centers. So, many approaches in the literature have focused on determining suitable initial centers. However, selecting suitable initial centers is not always possible, especially when the number of clusters is increased. This paper proposes an iterative approach to improve quality of the solution produced by the k -means. This approach tries to iteratively improve the quality of solution of the k -means by removing one cluster (minus), dividing another one (plus), and applying re-clustering again, in each iteration. This method called iterative k-means minus–plus (I-k-means−+). The I-k-means−+ is speeded up using some methods to determine which cluster should be removed, which one should be divided, and how to accelerate the re-clustering process. Results of experiments show that I-k-means−+ can outperform k-means++, to be known one of the accurate version of the k -means, in terms of minimizing SSEDM. For some instances, the accuracy of I-k-means−+ is about 2 times higher than both the k -means and k-means++, while it is faster than k-means++, and has the reasonable runtime, in comparison with the k -means. Graphical abstract: Image, graphical abstract