結合FCM 及PSO 處理動態模糊分群問題

Combining FCM and PSO for Dynamic Fuzzy Clustering Problems

謝凱明(Kai Ming Hsieh)

指導教授 ： 高有成

大同大學/經營設計學院/資訊經營學系所/碩士(2009年)

摘要

資料分群在資料探勘技術中運用相當廣泛，傳統的模糊分群演算法都需要預先設定組數才能進行資料分群。本研究結合Fuzzy C-means分群演算法及粒子群最佳化演算法(PSO)發展出一套動態分群演算法，能夠自動找出最適當的分群數，避免傳統Fuzzy C-means 需要預先設定組數才能進行分群演算的問題。本演算法我們稱之為FCPSO( Fuzzy C-means with Combinatorial Particle Swarm Optimization )。本演算法在初始階段會依據資料集決定可能最大分群組數，演算法並會在此範圍內隨機產生各粒子的分群組數，接著使用fuzzy C-means 調整群中心位置。透過分群效度指標衡量各粒子之分群結果，接下來重新調整粒子的的分群數，亦即粒子之間透過資訊分享使得分群數朝向最佳群數解搜尋，直到取得最適當的分群組數，從實驗結果顯示，FCPSO確實可以有效的找出最適合的分群組數與較佳的分群結果。

關鍵字

資料分群 ； Fuzzy C-means ； 粒子演算法 ； 動態分群

並列摘要

This paper proposes a dynamic data clustering algorithm which combines the fuzzy c-means clustering method and Particle Swarm Optimization. The disadvantage of fuzzy c-means is that it requires a given number of clusters, thus this paper tries to overcome this shortcoming. The proposed approach, called fuzzy c-means with Particle Swarm Optimization (FCPSO), can automatically determine the proper number of clusters during the data clustering process. In the initial phase of FCPSO, a maximum possible cluster number is predefined. Each particle then selects its own cluster number less than the maximum number and generates cluster centers randomly. In the following iterations, a particle uses fuzzy c-means to modify its own cluster centers, to evaluate the result by using a clustering validity index, and to adjust its own cluster number according the clustering result. That is, FCPSO performs a global search iteratively to find a optional number of clusters. For each of 6 test cases, the experimental results showed that FCPSO can effectively find the best clustering configuration including the number of clusters and cluster centers.

並列關鍵字

Data Clustering ； Fuzzy c-means ； Particle Swarm Optimization ； Dynamic

參考文獻

[2] Welch, W.J., “Algorithmic complexity: Three NP-hard problems in computational statistics.” J.Statist. Comput. Simulation, vol. 15, pp.17–25, 1982.

[3] Das, S., Konar, A., Chakraborty, U. K., “Automatic Fuzzy Segmentation of Images with Differential Evolution”, 2006 IEEE Congress on Evolutionary Computation Sheraton Vancouver Wall Centre Hotel, Vancouver, BC, Canada July 16-21, 2006.

[7] Bezdek, J. C., (1981), Pattern Recognition with Fuzzy Objective Function Algorithms, Plenum, NY, 1981.

[8] Martin, E. Kriegel, H. Sander, J. and Xu, X., “A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise.” Proc. of KDD96:pp. 226-231, 1996.

[9] Chandrasekharan, M. P., and Rajagopalan, R., “An ideal seed non-hierarchical clustering algorithm for cellular manufacturing.” International Journal of Production Research, Vol. 24, pp. 451-464, 1986.