# Ellipsoidal K-Means: An Automatic Clustering Approach for Non-Uniform Data Distributions
## 2 Adaptive Ellipsoidal Clustering Technique
### Cluster Merging and Splitting  
A merging and splitting procedure is incorporated into the SAELLC algorithm to ensure a comprehensive exploration of all research areas and the discovery of new regions. This merging and splitting procedure aims for comprehensive exploration and diversity in solution identification, which is a common goal in multi-depth memory search algorithms [34]. This approach is crucial because the search begins with \(K\) centroids randomly chosen as initial centers, which requires a method that can effectively search and access diversity to identify the best solution.  
The cluster merging and splitting procedure described in [17] is explained in detail, including the method for selecting the cluster to which the procedure is applied and the implementation mechanism. Details of the cluster merging and splitting procedures are provided in Procedures 1 and 2.  
**Procedure 1**.: _Merging procedure_  
1. _Input the average silhouette width_ \(S_{av}(k)\) _for all clusters, where_ \(k=1,\ldots,K\)_, along with_ \(N_{k}\)_, the number of objects in each cluster, and their centers_ \(c_{k}\)Identify the two clusters with the minimum values of \(S_{av}(k)\), where \(S_{av}(i)<S_{av}(j)<\ldots<S_{av}(K)\), with \(i\) and \(j\) being indices in the range \([1,K]\).
3. Set a new center \(c_{new}\) as \(c_{new}=\frac{n_{i}c_{i}+n_{j}c_{j}}{n_{i}+n_{j}}\).
4. Replace the centers \(c_{i}\) and \(c_{j}\) with \(c_{new}\), and update \(K\gets K-1\).
5. Adjust the newly generated centers based on the \(K\)-means.  
Splitting procedure  
1. Input the average silhouette width \(S_{av}(k)\) for all clusters, where \(k=1,\ldots,K\), together with \(O(k)\), the objects in each cluster and their centers \(c_{k}\).
2. Identify the cluster with the minimum value \(S_{av}(i)\), \(i\in[1,K]\).
3. Subdivide cluster \(i\) into two sub-clusters, \(O_{1}(i)\) and \(O_{2}(i)\), by dividing the points along the longest coordinate of the cluster. The center \(c_{i}\) serves as the boundary between these sub-clusters.
4. Determine the number of objects in the subclusters, denoted \(N_{1}\) and \(N_{2}\).
5. Replace \(c_{i}\) with \((c_{i},c_{K+1})\), where \(c_{i}=\frac{\Sigma O_{1}(i)}{N_{1}}\) and \(c_{K+1}=\frac{\Sigma O_{2}(i)}{N_{2}}\), and update \(K\gets K+1\).
6. Adjust the newly-generated centers based on \(K\)-means.  
These procedures are fundamentally based on the silhouette function [26]. The overall average silhouette width for all clusters can be computed as follows:  
\[SF(K)=\frac{1}{K}\sum_{k=1}^{K}S_{av}(k), \tag{19}\]  
where \(S_{av}(k)\) is the average silhouette width for points in cluster \(k\) (\(k=1,\ldots,K\)), determined as follows:  
\[S_{av}(k)=\frac{1}{N_{k}}\sum_{i=1}^{N_{k}}cv(i), \tag{20}\]  
where \(cv(i)\) is a value associated with each object \(i\) in the dataset, based on the average dissimilarity of \(i\) with all other data within the same cluster and the minimum distance of \(i\)'s average dissimilarity to data from another cluster, as defined in Equation (3).  
\(S_{av}(k)\) measures the average homogeneity of the clusters and is used to efficiently identify the clusters that may need to be merged or split. Clusters are partitioned into two sub-clusters by splitting the points along the longest dimension, and adjacent clusters are merged based on the \(S_{av}(k)\) value.