模糊粒子最佳化分群演算法

在資料分群(Data Clustering)的問題中，資料群的分佈可能是任意大小、重疊，甚至有許多離異值，因此發展群聚演算法是資料探勘(Data Mining)重要的課題。本研究提出新的分群演算法，主要是結合粒子最佳化(Particle swarm optimization ,PSO)及模糊理論，針對資料分群問題進行求解。 PSO是群體生物行為的演算法，利用粒子自身所經歷最佳解及所有粒子到目前所發現最好的解來影響粒子下一代位置的移動，世代演進來尋求最佳解，解題過程可避開區域最小值，對最佳解問題可以提供良好的解決方案；但過去的研究指出(Y. Shi, Eberhart , 1999)，PSO常在演化初期收斂速度快，但在接近最佳解的時候，反而收斂速度會減慢因而陷入區域最佳解[14]。因此本研究提出結合模糊理論與粒子演算法(稱為Fuzzy PSO, FPSO)，在演化的過程中透過隸屬度取得各粒子經驗最佳解的影響性，作為影響PSO下一世代運行的另外資訊，目的在使PSO演算法的演化後期，可以進一步穩定且精確的探索最佳解。本研究將FPSO與其他各種演算法(如：PSO、FCM、PSOFCM[7])在數種不同類型的資料分別進行硬式分群與模糊分群的比較，最後的實驗結果均可得到較佳的求解品質，且其求解的穩定性也較其他方法優。

關鍵字

模糊粒子最佳化；資料分群；模糊理論；粒子演算法

並列摘要

This paper proposes a new data clustering algorithm which is based on fuzzy techniques and particle swarm optimization (PSO). As pointed out by some researchers: the standard PSO always converges very quickly towards the optimal positions but may slow its convergence speed when it is reaching a minimum [9]. This paper is trying to solve this problem by integrating a Fuzzy technique with PSO to allow each particle to update its new velocity and next position according to the current position of other better particles, in addition to gbest, pbest and itself. Not all of other particles are considered by a particle; only those particles which have higher degree of fuzzy membership with the current global best particle are taken into account. This provides more information to direct the particle to fly toward a better direction. Finally, the proposed algorithm was evaluated by testing a couple of hard and soft clustering problems, also compared to some famous clustering methods. The experimental results show that the proposed approach has better convergence ability than its original PSO algorithm.

並列關鍵字

Data Clustering ； Fuzzy ； Particle swarm optimization ； Fuzzy PSO

參考文獻

[1] Bandyopadhyay S. and Maulik U., “Genetic clustering for automatic evolution of clusters and application to image classification,” pattern recognition, vol. 35, no. 6, pp.1197-1208, 2002.

[2] Bezdek, J. C. and Hathaway, R. J., “Optimization of fuzzy clustering criteria using genetic algorithms,” in Proc. of IEEE Intl. Conf. on Evolutionary Computation, pp. 589–549, 1994

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

[7] Juang, C.F., "A Hybrid of Genetic Algorithm and Particle Swarm Optimization for Recurrent Network Design," IEEE Transactions On Systems, Man, and Cybernetics-part B: Cybernetics, Vol. 34, No. 2, pp. 997-1006, Apr 2004.

[9] Lucia, B., Leonardo B. and Carina, B. J. ,“Image segmentation by a genetic fuzzy c-means algorithm using color and spatial information,” EvoWorkshops LNCS 3005, pp. 260–269, 2004.

國際替代計量

模糊粒子最佳化分群演算法

未授權

主題瀏覽