K-means** – a fast and efficient K-means algorithms. (2018)

• Record Type: Journal Article
• Authors: Nguyen, Cuong Duc; Duong, Trong Hai
• Is Part Of: International journal of intelligent information and database systems. Volume 11:Number 1(2018)
• Page Start: 27
• Page End: 45
• Publication Date: 2018
• Subjects: data clustering -- K-means -- k-means++ -- incremental K-means -- IKM -- data mining; Database management -- Computer programs -- Periodicals; Information retrieval -- Computer programs -- Periodicals; Information storage and retrieval systems -- Computer programs -- Periodicals; Artificial intelligence -- Periodicals; Expert systems (Computer science) -- Periodicals; Intelligent agents (Computer software) -- Periodicals; 006.33
• Languages: English
• ISSNs: 1751-5858

Abstract

K-means often converges to a local optimum. In improved versions of K-means, k-means++ is well-known for achieving a rather optimum solution with its cluster initialisation strategy and high computational efficiency. Incremental K-means is recognised for its converging to the empirically global optimum but having a high complexity due to its stepping of the number of clusters K . The paper introduces K-means** with a doubling strategy on K . Additional techniques, including only doubling big enough clusters, stepping K for the last few values and searching on other candidates for the last K, are used to help K-means** have a complexity of O ( K logK ), which is lower than the complexity of incremental K-means, and still converge to empirically global optimum. On a set of synthesis and real datasets, K-means** archive the minimum results in almost of test cases. K-means** is much faster than incremental K-means and comparable with the speed of k-means++.