# \(K\)-Means Cloning: Adaptive Spherical \(K\)-Means Clustering
## 2 K-Means Cluster Cloning
### K-Means Colony Growth
#### 2.3.3 How to Split or Merge  
_K_-means cloning is a continuous evolving process that is represented by split and merge of _K_-means clusters. Merging and Splitting Procedures 2, 3 show the cloning mechanism of merging two clusters into a larger one, and how a single cluster is split into two new clusters with new centers. When a cluster is split into two sub-clusters, new-alternative centers are generated.  
**Procedure 2**.: _Merging_  
1. _Input: clustering outputs with clusters_ \(C_{\kappa},\kappa=\{1,\ldots,K\}\)_, and for each cluster_ \(N_{\kappa}\) _is the number of objects in this cluster, and his center is_ \(c_{\kappa}\)_._
2. _Evaluate the cluster silhouettes_ \(S(\kappa),\kappa=\{1,\ldots,K\}\)_._
3. _Sort the cluster silhouettes to determine the two clusters with the minimum cluster silhouettes_ \(C_{i}\) _and_ \(C_{j}\)_._
4. _Set a new center_ \(c_{\mathrm{new}}\) _as,_ \[c_{\mathrm{new}}=\frac{n_{i}c_{i}+n_{j}c_{j}}{n_{i}+n_{j}}.\]
5. _Replace the centers_ \(c_{i}\) _and_ \(c_{j}\) _by_ \(c_{\mathrm{new}}\)_, set_ \(K:=K-1\)_._
6. _Adjust the new generated centers based on K-means, and return with the adjusted clusters._  
The splitting process is applied to the cluster with the minimum cluster silhouette value among all clusters. A hyperplane is generated to split this cluster objects in order to generate two new clusters. Coordinate-wise variances are computed over the data objects of the chosen cluster. Then, the separation hyperplane is generated passing through the cluster center and orthogonal to the coordinate axis corresponding to the highest variance component of the data objects. Figure 5 shows an example of cluster splitting in two dimensions. In this figure, it is clear that the data variance over \(x_{1}\)-axis is higher than that over \(x_{2}\)-axis. Therefore, the dashed hyperplane is generated passing through center \(c\) and orthogonal to \(x_{1}\)-axis in order to separate the data objects into two clusters along the both sides of the hyperplane. Data objects which are located on the hyperplane can be added to any of the two clusters since new centers will be computed and all data objects will be adjusted as in the case of _K_-means.  
Figure 4: The cluster silhouettes for Dataset 10-2 to determine clusters must be split or merge for Dataset 10-2.  
**Procedure 3**.: _Splitting_  
1. _Input: clustering outputs with clusters_ \(C_{\kappa},\kappa=\{1,\dots,K\}\)_, and for each cluster_ \(N_{\kappa}\) _is the number of objects in this cluster, and his center is_ \(c_{\kappa}\)_._
2. _Evaluate the cluster silhouettes_ \(S(\kappa),\kappa=\{1,\dots,K\}\)_._
3. _Sort the cluster silhouettes to determine the cluster_ \(C_{i}\) _with the minimum cluster silhouette._
4. _Divide cluster_ \(C_{i}\) _into two sub-clusters with objects_ \(C_{i}^{\prime}\) _and_ \(C_{i}^{\prime\prime}\) _by splitting the data objects in_ \(C_{i}\) _using a separation hyperplane passing through its center and orthogonal to the coordinate axis corresponding to the highest variance component of the data objects._
5. _Compute the centers_ \(c_{i}^{\prime}\) _and_ \(c_{i}^{\prime\prime}\) _of the new clusters_ \(C_{i}^{\prime}\) _and_ \(C_{i}^{\prime\prime}\)_, respectively._
6. _Replace_ \(C_{i}\) _with_ \(C_{i}^{\prime}\) _and_ \(C_{i}^{\prime\prime}\)_, set_ \(K:=K+1\)_._
7. _Adjust the new generated centers based on_ \(K\)_-means, and return with the adjusted clusters._