# \(K\)-Means Cloning: Adaptive Spherical \(K\)-Means Clustering
###### Abstract  
We propose a novel method for adaptive \(K\)-means clustering. The proposed method overcomes the problems of the traditional \(K\)-means algorithm. Specifically, the proposed method does not require prior knowledge of the number of clusters. Additionally, the initial identification of the cluster elements has no negative impact on the final generated clusters. Inspired by cell cloning in microorganism cultures, each added data sample causes the existing cluster 'colonies' to evaluate, with the other clusters, various merging or splitting actions in order for reaching the optimum cluster set. The proposed algorithm is adequate for clustering data in isolated or overlapped compact spherical clusters. Experimental results support the effectiveness of this clustering algorithm. Keywords:data mining; clustering analysis; adaptive \(K\)-means; simulated annealing +
Footnote †: journal:  
0000-0001-6000-0000  
0000-0001-6000-0000]J. A.  
local minimum solution. The \(K\)-means algorithm is well known for its efficiency and its ability to cluster large datasets. However, a major bottleneck in the operation of \(K\)-means is the requirement of predefinition of the clusters number [8]. From another side, the high dependence of the final clustering on the initial identification of clusters elements represents another difficulty to the operation of \(K\)-means [8]. Some research studies have approached the clustering problem from a meta-heuristic perspective. Meta-heuristics have a major advantage over other methods, which is the ability to avoid becoming trapped at local minima. Such algorithms exploit guided random search. Therefore, much better results have been obtained with meta-heuristics approaches, such as simulated annealing [9; 10; 11; 12; 13; 14], tabu search [15; 16], and genetic algorithms [17]. They combine techniques of local search and general strategies to escape from local optima leading to broadly searching the solution space. The objective of such combination is to obtain solutions that are closer to the global optima (centroids) of the clusters. Based on the tendency of the \(K\)-means algorithm to obtain local optima [18], this work investigates a new approach to solve clustering problem. Data clustering is known to be NP hard in finding groups in heterogeneous data [19]. It is the process of grouping similar data items together based on some measure of similarity (or dissimilarity) between items. A major difficulty that exists with \(K\)-means clustering, as one of the most well-known unsupervised clustering methods, is the requirement of prior knowledge about the number of clusters. This piece of information could be difficult to know in advance for many applications. Moreover, \(K\)-means has other well-known drawbacks, sensitivity to initial configuration and its convergence to local optima. These problems are raised in the literature, see [7; 20; 21; 22; 23; 24; 25] and reference therein. Different treatments have been discussed to find better tuning mechanisms of the number \(K\) including statistical tests, probabilistic models, incremental estimation process, or visualization schemes. In the following, we give a brief presents of some of those treatments. In [26], the authors built a powerful learning-based fuzzy \(C\)-means structure, so it turns out to be free of the fuzziness index \(m\) and initializations without parameter choice, and can likewise consequently locate the best number of clusters. They initially utilized entropy-type penalty terms for optimizing the fuzziness index, and afterward make a learning-based schema for finding the best number of clusters. That learning-based schema uses entropy terms contain the belonging probabilities of data points to clusters and the average of occurrence in those probabilities over fuzzy memberships to find the best number of clusters. [PERSON] et al. [27] proposed a new automatic clustering approach based on particle swarm optimization and genetic algorithm.