# Ellipsoidal K-Means: An Automatic Clustering Approach for Non-Uniform Data Distributions
###### Abstract  
Traditional \(K\)-means clustering assumes, to some extent, a uniform distribution of data around predefined centroids, which limits its effectiveness for many realistic datasets. In this paper, a new clustering technique, simulated-annealing-based ellipsoidal clustering (SAELLC), is proposed to automatically partition data into an optimal number of ellipsoidal clusters, a capability absent in traditional methods. SAELLC transforms each identified cluster into a hyperspherical cluster, where the diameter of the hypersphere equals the minor axis of the original ellipsoid, and the center is encoded to represent the entire cluster. During the assignment of points to clusters, local ellipsoidal properties are independently considered. For objective function evaluation, the method adaptively transforms these ellipsoidal clusters into a variable number of global clusters. Two objective functions are simultaneously optimized: one reflecting partition compactness using the silhouette function (SF) and Euclidean distance, and another addressing cluster connectedness through a nearest-neighbor algorithm. This optimization is achieved using a newly-developed multiobjective simulated annealing approach. SAELLC is designed to automatically determine the optimal number of clusters, achieve precise partitioning, and accommodate a wide range of cluster shapes, including spherical, ellipsoidal, and non-symmetric forms. Extensive experiments conducted on UCI datasets demonstrated SAELLC's superior performance compared to six well-known clustering algorithms. The results highlight its remarkable ability to handle diverse data distributions and automatically identify the optimal number of clusters, making it a robust choice for advanced clustering analysis. unsupervised learning, data clustering; simulated annealing silhouette function; adaptive ellipsoidal \(K\)-means; automatic clustering. +
Footnote †: journal: _Algorithms_  
0000-0001-9900-0001-9900-0001-9900-0001-9900-0001-9900-0001-9900-0001-9900-0001-99000-001-99000  
been devoted to it in recent decades. This renewed interest is evident in the wide range of applications covering a variety of fields, including data mining, statistical analysis, data compression, and vector quantization. The primary objective of clustering is to organize data into cohesive clusters, in which the data points in each cluster exhibit a significant degree of similarity, while retaining distinct differences from the data points in other clusters [1; 2]. For a comprehensive overview of clustering techniques, see [3]. Several types of clustering algorithms have been created, such as those mentioned in [4; 5; 6]. The main algorithms include partitional methods, hierarchical methods, and graph-theoretic methods. The success of a clustering method mainly depends on its ability to separate data points in a multi-dimensional space. This separation potential is generally defined by an objective function that the algorithm attempts to optimize. The most common type of clustering algorithm is the \(K\)-means algorithm. It is simple, fast, and works by grouping objects into a predetermined number of clusters, denoted \(K\). Each object is assigned to the cluster with the closest mean distance [7; 8]. However, in the real world, clusters often do not have clear boundaries. This means that data points may not belong entirely to a single cluster; in contrast, they may be shared between several clusters. Furthermore, the \(K\)-means algorithm is highly dependent on its initial conditions. It always approaches the nearest best local solution from where it begins its search. Researchers across various fields have applied different clustering techniques to address the local optima problem. These techniques include hierarchical clustering, partition-based clustering, density-based clustering, model-based clustering, grid-based clustering, and AI-driven clustering methods [9; 10].