運用粒子群演算法以求解分群問題

Particle Swarm Optimization for Sloving Clustering Problem

陳昱丞(Yu-Cheng Chen)

指導教授 ： 李維平

中原大學/商學院/資訊管理研究所/碩士(2009年)

https://doi.org/10.6840/CYCU.2009.00789

摘要

資料分群在資料探勘中，是一門常見與重要的技術，它可以從龐大的資料中，找出資料的分佈狀況並找出其隱藏的意義。而隨著群體智慧的興起，相關學者紛紛將群體智慧技術應用在資料分群研究上，也獲得良好的分群效果。而在相關研究中，粒子群演算法在資料分群上亦獲得良好的效果。粒子群演算法乃模擬鳥群覓食的行為所衍生的最佳化搜尋演算法，具備穩健性，快速收斂與易實現的特性，在解空間中充分展現極佳的搜尋能力。

針對資料分群問題，為求得最佳分群結果，本研究提出RDPSO演算法，主要運用粒子群演算法的區域搜尋與快速收斂能力於資料分群上，同時為加強群集中心分群時的正確性，加入群中心點置換策略，以改善隨機選擇的問題。另外粒子群的快速收斂易導致粒子陷入區域最佳解問題，於演算法中加入擾動因子，讓粒子可以跳脫區域最佳解的問題。因此本研究所提之RDPSO的優點有
A.在一定的機率下加入擾動因子增加搜尋空間，讓粒子可以跳脫區域最佳解的困境，以提高分群的結果；另外因加入機率因素於演算法中，使得粒子不會侷現在固定迭代數的問題，使得粒子的迭代運算更加靈活。
B.群集中心點的選擇，運用群中心點置換策略，讓中心點與各個粒子運用歐幾里得距離向量演算來決定中心點的最適性，取代以往採用隨機方式選擇中心點作為群集中心點。

關鍵字

粒子群演算法 ； 置換 ； 群集分析 ； 分群 ； 擾動因子

並列摘要

Data Clustering in Data Mining is the common and important technology. It can find out the data distribution and meaning in the huge data.By the Swarm Intelligence rising, more researchers use this technology of the Swarm Intelligence on data clustering, also get better effect.However,in these researches, Particle Swarm Optimization Algorithm(PSO) also has good effect on data clustering. PSO is a population-based stochastic search process, modeled after the social behavior of a bird flock, has the character of robust、quick converges and easy accomplish,and in space it shows the best search process.

For the problem of data clustering to have the best clustering result, in this study, the research suggest RDPSO Algorithm, and the primary in data clustering, perform the PSO local search and quick converges ability, simultaneously to enhance choose the cluster center correctness in clustering, I recommand the concept of K Nearest Neighbor algorithm to impove the random choose problem.Beside it, the quick converges of PSO will result to get into local optima problem. I add the chaos factor in the algorithm to let particle escape the local optima problem.Therefore, the advantage of RDPSO in the reasearch is:
A. In the certain probability to add chaos factor to increase particle search space, let particle escape local optima problem to enhance the clustering result; and by add probability factor in the algorithm, make particle to being more automatic and flexible increase more opportunities to search new space.
B.The clustering central point's choice, replaces the strategy using the group central point, lets the central point with each granule using Euclidean from the vector calculus decide that the central point most suitable, the substitution formerly used the stochastic mode selection central point to take the clustering central point.

並列關鍵字

PSO ； Cluster ； Replace ； Dissipative

參考文獻

[1] Han J. and Kamber M., “Data Mining: Concepts and Techniques,” Morgan Kaufmann, 2000.

[4] Kaufman L. and Rousseeuw PJ, “Finding Groups in Data: an Introduction to Cluster Analysis,” John Wiley & Sons, 1990.

[6] Jain A. K., Murty M. N., and Flynn P. J., “Data clustering: A review,”ACM Comput.

[10] Karypis G., Han E.H. and Kumar V., “CHAMELEON: Hierarchical Clustering Using Dynamic Modeling,” IEEE Computer, Vol. 32, No. 8, pp. 68-75, (1999).

[15] Wang W., Yang and Muntz R., “STING: A Statistical Information grid Approach to Spatial Data Mining,” In Proc. 1997 Int. Conf. Very Large Data Bases(VLDB’97), pp. 186-195, Athens, Greece, Aug. 1997.