發展混合式最佳化演算法於模糊分群

The Development of Hybrid Optimization Algorithm for Fuzzy Clustering

陳攸伃(You-Yu Chen)

指導教授 ： 王河星

國立臺北科技大學/管理學院/工業工程與管理研究所/碩士(2009年)

摘要

模糊C-means分群演算法(FCM)由Dunn於1974年提出，是最常被使用的模糊分群方法，而FCM利用隨機選取初始重心進行資料分群，當資料數量多或屬性維度大時容易影響分群結果，且需要更多次的重複演算。為彌補FCM隨機初始重心對結果的影響，本研究發展出混合式演算法－基因免疫模糊分群演算法(Genetic Immune Fuzzy C-means Algorithm, GIFA)，此演算法執行時先求得較適當的初始重心再進行分群，以改善分群效率。將GIFA透過Teaching Assistant Evaluation、Ecoli與Glass Identification三個資料集進行測試，並與模糊C-means分群演算法(Fuzzy C-means Algorithm, FCM)、基因模糊分群演算法(Genetic Fuzzy C-means Algorithm, GFA)及免疫模糊分群演算法(Immune Fuzzy C-means Algorithm, IFA)的執行結果相互比較，以目標函數收斂值及收斂次數分析演算法的優劣，證實GIFA能獲得良好的分群結果。

關鍵字

模糊分群 ； 基因演算法 ； 免疫演算法

並列摘要

The Fuzzy C-means Algorithm as proposed by Dunn (1974) is a commonly used fuzzy clustering method which conducts data clustering by randomly selecting initial centroids. With larger data size or attribute dimensions, clustering results may be affected and more repetitive computations are required. To compensate the effect of random initial centroids on results, this study proposed a hybrid optimization algorithm－Genetic Immune Fuzzy C-means Algorithm (GIFA). This algorithm first obtains the proper initial cluster centroids and then cluster data to improve clustering efficiency. And tests GIFA through three data sets: Teaching Assistant Evaluation, Ecoli and Class Identification, and compares the results with the executed results of Fuzzy C-means Algorithm (FCM), Genetic Fuzzy C-means Algorithm (GFA), and Immune Fuzzy C-means Algorithm (IFA). Analyze the advantages and disadvantages of the algorithms by convergence value of objective function and convergence iterations. The results suggest that GIFA could achieve better clustering results.

並列關鍵字

Fuzzy Clustering ； Genetic Algorithm ； Immune Algorithm

參考文獻

[1] A. L. Chen, "Genetic Algorithm Solution for Partner Selection and Optimization in Virtual Enterprise," Journal of Jiangsu Polytechnic University, vol. 17, no. 3, 2005, pp. 49-52.

[2] A. Bouchachia, "An Immune Genetic Algorithm for Software Test Data Generation," 7th International Conference on Hybrid Intelligent Systems, 2007, pp. 84-89.

[3] B. M. Baker, and M. A. Ayechew, "A genetic algorithm for the vehicle routing problem," Computers & Operations Research, vol. 30, no. 5, April 2003, pp. 787-800.

[4] L. Cai, Y. Huang and J. Chen, "A Genetic-Based Fuzzy Clsutering Algorithm for Fault Diagnosis in Satellite Attitude Determination System," Proceedings of the 6th International Conference on Intelligent Systems Design and Appliications, vol. 1, 2006, 834-837.

[5] C. H. Wei and C. S. Fahn, "A Distributed Approach to Fuzzy Clustering by Genetic Algorithm," Asian Fuzzy Systems Symposium, 1996, pp. 350-357.