پديد آورندگان :
مهدي زاده، اسماعيل دانشگاه آزاد اسلامي قزوين - دانشكده مهندسي صنايع و مكانيك , تيموري، محمد دانشگاه آزاد اسلامي قزوين - دانشكده مهندسي صنايع و مكانيك , زارع طلب، آرش دانشگاه آزاد اسلامي قزوين - دانشكده مهندسي صنايع و مكانيك
چكيده فارسي :
خوشه‌بندي يكي از روش‌هاي پركاربرد در بسياري از زمينه‌هاي علمي است كه در آن تلاش مي‌شود داده‌ها داخل گروه‌ها براساس درجه‌ي شباهت قرار گيرند. الگوريتم‌هاي ابتكاري و فراابتكاري زيادي براي حل مسئله‌ي خوشه‌بندي ارائه شده است. يكي از روش‌هاي ابتكاري پركاربرد، K-means است. اين روش، به‌دليل وابستگي به حالت اوليه، معمولاً به بهينه‌يمحلي همگرا مي‌شود. در اين مقاله به‌منظور فرار از بهينه‌ي محلي، الگوريتم K-means با الگوريتم فراابتكاري الكترومغناطيس تركيب شده و الگوريتم جديدي با عنوان الگوريتم K-EM براي حل مسئله‌ي خوشه‌بندي ارائه مي‌شود. به‌منظور بررسي كارايي الگوريتم پيشنهادي، پنج مجموعه داده انتخاب و حل شده و نهايتاً جواب‌هاي حاصله با جواب‌هاي حاصل از الگوريتم‌هاي مطرح در ادبيات خوشه‌بندي مقايسه مي‌شود. نتايج محاسباتينشان مي‌دهد كه الگوريتم پيشنهادي در دست‌يابي به جواب‌هاي مطلوب از كارايي مناسبي برخوردار است.
چكيده لاتين :
Clustering is one of the useful methods in many scientific fields. It is a classification process for putting data in specific groups or clusters based on the similarities between them. In literature, many algorithms, such as heuristic and meta-heuristic, have been successfully applied to solve clustering problems. Among them, the K-means is well-known due to its simplicity and computational efficiency, although it suffers from several drawbacks due to its initial state and may be trapped in local optima.
Electromagnetism-like Mechanism (EM) algorithm is a new population-based meta-heuristic to tackle complex optimization problems. It imitates the attraction- repulsion of the electromagnetic theory that is based on Coulombs law for obtaining the optimal solution.
Unlike some meta-heuristic algorithms such as Genetic Algorithm (GA) and Tabu search (TS), in EM, each particle is influenced by all other particles within its population.In this paper, to skip the local optimum, the K-means method is combined with the Electromagnetism-like Mechanism (EM) algorithm, and a new algorithm, called K-EM, is presented to solve clustering problems. In K-EM, there are two main
phases. In the first phase, K-EM executes the K-means algorithm within the population size and tries to produce favorable centroids for desired clusters, which terminates when there is no change in centroid. In the second phase, the fitness value of each particle is computed and the particle that has the best fitness value is stored. Then, the particles are fed into the improved local search procedure. Then, the total force exerted on each particle is computed. In the move procedure, the particle position is moved according to the resultant force exerted on them. The search process of finding the best results continues until the stop criterion is met.
In order to evaluate the performance of the proposed algorithm, five distinguished and standard datasets are chosen from the UCI Machine Learning repository. These datasets are solved and the results are compared with the results of those of K-means, GA, Simulated Annealing (SA), Ant Colony Optimization (ACO), Particle Swarm Optimization (PSO), and EM. The results illustrate that the proposed K-EM algorithm has good proficiency in obtaining desired results.
