# Ellipsoidal K-Means: An Automatic Clustering Approach for Non-Uniform Data Distributions
###### Abstract
Several methods have been proposed to improve the efficiency of the \(K\)-means algorithm, leading to the development of many improved \(K\)-means algorithms in recent years. For example, SMCK-means was proposed for the circular invariant clustering of vectors using \(K\)-means [11]. Another method, the fuzzy spherical \(c\)-means clustering technique [12; 13], is well known for detecting and representing hyperspherical (in particular ellipsoidal) clusters. In [14], a method was developed using three similarity measures to identify groups of similar ellipsoids in \(p\)-space. Obtaining the best (optimal) clusters using the \(K\)-means algorithm is a real challenge, especially when it comes to detecting and representing hyperspherical clusters. Typically, many clustering methods are based on a single optimization criterion. However, this approach may not accurately identify the underlying clusters within a dataset. To address this issue, clustering tasks are often defined as multi-objective problems. This means that several optimization criteria can be established and evaluated simultaneously to improve the accuracy [15; 16]. In this paper, we propose a new clustering method specifically designed to identify ellipsoidal clusters. Our approach consists of incorporating the width of the silhouette, based on the criterion of the silhouette function (\(SF\)), into the nearest-neighbor algorithm in order to improve the performance of the objective function. This provides a more comprehensive means of determining the optimal number of ellipsoidal clusters. The SF method has shown particular effectiveness in identifying the optimal number of circular or spherical clusters [17]. However, it struggles to determine the appropriate cluster centers and their corresponding partitioning for datasets containing ellipsoidal clusters. Therefore, this study focuses on improving the efficiency of \(SF\)to encompass spherical clusters as well as ellipsoidal clusters. [PERSON] introduced the simulated annealing optimization algorithm, which is an iterative search method inspired by the annealing process in metals, to solve numerical optimization problems [18]. We adapted this algorithm to solve clustering problems, naming the proposed version simulated annealing for ellipsoidal clustering (SAELLC). The performance of the SAELLC algorithm is evaluated by applying it to 14 standard test databases used for benchmark clustering problems. Then, its results are compared with those obtained by the AMOSA algorithm (simulated annealing-based multiobjective optimization technique) combined with the stability-induced symmetry-based clustering technique (SSym-AMOSA) on the same datasets as presented in [19]. In addition to comparing the SAELLC algorithm with the SSym-AMOSA algorithm, we also evaluate the performance of the SAELLC algorithm against the wide range of clustering techniques listed in [19]. These include two multi-objective clustering techniques: Pareto envelope-based selection Algorithm-II (SSym-PESAII) [20], and multiobjective clustering with known Pareto fronts (MOCK) [21]. Moreover, we consider two automatic clustering techniques based on single-objective genetic algorithms: VGAPS clustering [22], and genetic clustering for unknown \(K\) (GCUK clustering) [23]. The performance of SAELLC, which incorporates SA as an inherent optimization technique in the proposed clustering algorithm, is then compared to \(K\)-means cloning (KMC) [17]. The KMC algorithm is another unique optimization technique that uses pure \(SF\) without any improvement, as described in [17]. The remainder of this paper is structured as follows: Section 2 reviews the adaptive ellipsoidal clustering technique. In Section 3, we examine the combination of the adaptive ellipsoidal clustering technique with the simulated annealing heuristic, which presents the main algorithm for automatic data clustering. The results of the numerical experiments and their analysis are presented in Section 4, as well as the deployment of the proposed methods on the IoV.