Search

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. [ABSTRACT FROM AUTHOR]

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.ejor.2004.05.033 Byline: Abdel-Rahman Hedar, Masao Fukushima Keywords: Global optimization; Metaheuristics; Tabu Search; Nelder-Mead method; Adaptive pattern search Abstract: In recent years, there has been a great deal of interest in metaheuristics in the optimization community. Tabu Search (TS) represents a popular class of metaheuristics. However, compared with other metaheuristics like genetic algorithm and simulated annealing, contributions of TS that deals with continuous problems are still very limited. In this paper, we introduce a continuous TS called Directed Tabu Search (DTS) method. In the DTS method, direct-search-based strategies are used to direct a tabu search. These strategies are based on the well-known Nelder-Mead method and a new pattern search procedure called adaptive pattern search. Moreover, we introduce a new tabu list conception with anti-cycling rules called Tabu Regions and Semi-Tabu Regions. In addition, Diversification and Intensification Search schemes are employed. Numerical results show that the proposed method is promising and produces high quality solutions. Author Affiliation: Department of Applied Mathematics and Physics, Graduate School of Informatics, Kyoto University, Kyoto 606-8501, Japan Article History: Received 2 July 2003; Accepted 13 May 2004 Article Note: (footnote) [star] This research was supported in part by a Grant-in-Aid for Scientific Research from the Ministry of Education, Science, Sports and Culture of Japan.