臺灣博碩士論文加值系統

至今越來越多研究加入群體智慧（Swarm Intelligence）概念應用於資料分群（Data Clustering）問題，協助截取資料隱含意義提供多樣資訊給管理者，文獻顯示可獲得不錯的效果。其中，粒子群演算法是模擬鳥群覓食的行為所衍生的最佳化搜尋技術，具備快速收斂、易實現和強健性（Robust）的優點，在解空間搜尋最佳解的精度和效率有不錯表現。

本研究針對分群問題，提出的四種研究架構：（1） DPSO Clustering； （2） SPSO Clustering ；（3） DSPSO Clustering；（4）SDPSO Clustering。透過實驗證明各有特色，DPSO Clustering增加粒子更多機會搜尋新空間，突破需要設定固定迭代才會擾動的模式，算法更自動和靈活。SPSO Clustering透過SWAP機制，提升最佳解的精度。DSPSO Clustering以SWAP局部搜尋，進而改變粒子的位置。SDPSO結合SWAP和DPSO，粒子在一定機率下隨機擾動粒子來跳出局部解，並以SWAP提升粒子的最佳解。

實驗結果顯示，本研究提出的概念應用於資料分群問題，確實優於原始粒子群演算法和基因演算法，此外，SPSO和SDPSO與差分演算法也不相上下。

Data Clustering can be implied the meaning of data, providing managers diverse information. Now more and more researches joining on the Swarm Intelligence concept get good results, for example, PSO algorithm. PSO is the simulation of bird populations to search for food with some characters, including rapid convergent and achieve easily, robust and so on. It is good performance in the accuracy and efficiency.

In this study, four framework of research include, DPSO Clustering, SPSO Clustering, DSPSO Clustering and SDPSO Clustering. Some characteristics were found though the experiment. DPSO Clustering being more automatic and flexible increase more opportunities to search new space for particle. SPSO use SWAP mechanism to enhance the accuracy of cluster’s center. DSPSO changes the particles’ location with disturbance strategy of SWAP. SDPSO is combined with SWAP and DPSO and helps particle jump out of local solution and enhance final result.

目錄
論文摘要 I
Abstract II
謝誌 III
目錄 IV
圖目錄 V
表目錄 VI
第一章 緒論 8
1.1 研究背景 8
1.2 研究動機 9
1.3 研究目的 10
1.4 章節概要 11
第二章 文獻探討 12
2.1 群集分析 12
2.1.1 分群問題定義 12
2.1.2 群集技術 13
2.1.3 PAM　Method 15
2.2 粒子群演算法 16
2.2.1 演算法 16
2.2.2 擾動式粒子群演算法 18
2.3 粒子群分群演算法 19
2.3.1 相關研究 19
2.3.2 基本PSO Clustering 20
2.4 基因演算法 22
2.5 差分演算法 23
第三章 研究方法 25
3.1 演算流程設計 26
3.1.1 初始化 26
3.1.2 成員矩陣建立 26
3.1.3 適應值計算 28
3.1.4 邊界處理 29
3.1.5 避免空值群集 30
3.2 演算法架構 31
3.2.1 DPSO Clustering 31
3.2.2 SPSO Clustering 35
3.2.3 DSPSO Clustering 38
3.2.4 SDPSO Clustering 41
第四章 實驗設計 44
4.1 測試集 45
4.1.1 Iris Data Set 46
4.1.2 Breast-cancer Data Set 47
4.1.3 Glass Data Set 48
4.1.4 Vowel Data Set 49
4.2 實驗環境和參數設定 50
4.3 實驗結果 51
4.3.1 DPSO Clustering 52
4.3.2 SPSO Clustering 54
4.3.3 DSPSO Clustering 56
4.3.4 SDPSO Clustering 58
4.3.5 綜合比較 60
4.4 結果分析 61
第五章 結論與未來研究 62
5.1 結論 62
5.2 未來研究 63
參考文獻 64

圖目錄
圖2. 1 階層式演算法示意圖 13
圖2. 2 粒子群演算法流程圖 17
圖2. 3 粒子群演算法應用於資料分群概念圖 20
圖2. 4 粒子群演算法應用於資料分群概念圖 22
圖3. 1 演算法應用於資料分群概念圖 25
圖3. 2 粒子編碼範例 26
圖3. 3 DPSO CLUSTERING概念圖 31
圖3. 4 DPSO分群演算流程圖 32
圖3. 5 改變粒子的位置 33
圖3. 6 SPSO CLUSTERING概念圖 35
圖3. 7 粒子的位置改變 35
圖3. 8 SPSO分群演算法流程圖 36
圖3. 9 DSPSO CLUSTERING概念圖 38
圖3. 10 DSPSO分群演算流程圖 39
圖3. 11 SDPSO CLUSTERING演算流程圖 41
圖3. 12 SDPSO 分群演算流程圖 42

表目錄
表4. 1 測試集簡介 45
表4. 2 IRIS 測試集的資料表 46
表4. 3 BREAST-CANCER測試集的資料表 47
表4. 4 GLASS 測試集的資料表 48
表4. 5 VOWEL測試集的資料表 49
表4. 6 參數的設定值 50
表4. 7 DPSO與各演算法之適應值 52
表4. 8 SPSO與各演算法之適應值 54
表4. 9 DSPSO與各演算法之適應值 56
表4. 10 SDPSO與各演算法之適應值 58
表4. 11 適應值綜合比較 60

A. Abraham, C. Grosan and V. Ramos, “Swarm Intelligence and Data Mining”, Studies in Computational Intelligence, Springer Verlag, Germany, pages 270, ISBN： 3-540-34955-3, 2006.

C. L. Blake and C. J. Merz. Uci repository of machine learning databases. http：//www.ics.uci.edu/, 1998.

C.Y. Chen and F. Ye ,“Particle Swarm Optimization Algorithm and Its Application to Clustering Analysis,” IEEE ICNSC 2004, Taipei, Taiwan,2004

D. W. V. D. Merwe and A. P. Engelbrecht, “Data clustering using particle swarm optimization.” Proceedings of the 2003 IEEE Congress on Evolutionary Computation,Piscataway, NJ： IEEE Service Center, 2003.

D. Satchidananda, G. Ashish and M. Rajib, “Particles with Age for Data Clustering “ 9th International Conference on Information Technology, 2006.

F. Ye and C. Y. Chen ,“Alternative KPSO-Clustering Algorithm,” Tamkang Journal of Science and Engineering, Vol.8, No.2. ,2005.

H.X. Long, W.B. Xu and J. Sun ,“Data Clustering Based on Quantum-behaved Particle Optimization,” College of Information Technology , Southern Yangtze University , Wuxi Jiangsu, China, 2006.

H.P. Friedman and J. Rubin, ”On some invariant criterion for grouping data.” J. Amer. Statist. Assoc. 63,pp.1159–1178, 1967.


J.T. Tou and R.C. Gonzalez, “Pattern Recognition Principles”, Addison-Wesley, Reading , 1974.

J. Kennedy and R. C. Eberhart , “Particle swarm optimization,” Proceedings of the IEEE International Joint Conference on Neural Networks, 4：1942–1948, 1995.

J. Kennedy and R. C. Eberhart , and Y. Shi, “Swarm Intelligence,” Morgan Kaufmann Publishers, San Francisco, 2001.

J. Holland, “Genetic Algorithms”, Scientific American, 1992, pp.44-50.

K. Krishna and M.N. Murty, “Genetic K-means algorithm,” IEEE Trans. Systems Man Cybernet. 29, 433–439,1999.

L. Kaufman and P.J. Rousseeuw ,“Finding Groups in Data： an Introduction to Cluster Analysis,” John Wiley & Sons, 1990.

M. Clerc and J. Kennedy,“The particle swarm-explosion, stability and convergence in a multidimensional complex space,” IEEE Transactions on Evolutionary Computation, Vol.6, no.2, 2002, pp.58-73,2002.

M. Jiawei and K. Micheline, “Data Mining Concepts and Techniques,” Morgan Kaufmann Publishers,2Ed, 2006.

M. Omran, A. Salman and A.P. Engelbrecht “Image classification using particle swarm optimization,” Proceedings of the 4th Asia-Pacific Conference on Simulated Evolution and Learning 2002 ,Singapore, 2002.

R.C. Eberhart, and Y. Shi, “A Modified Particle Swarm Optimizer,” Proceedings of IEEE World Congress Computation Intelligence, pp.69-73, 1998.

R. Storm and K. Price, “Minimizing the Real Function of the ICEC’96 Contest by Differential Evolution,” IEEE Conference on Evolutionary Computation, Nagoya, Japan, pp. 842-844, May, 1996.

R. Storm and K. Price, DE homepage [EB/OL]. （1997-02-11）
http：//www.icsi.berkeley.edu/~storn/code.html

S. Paterlini and T. Krink, “Differential Evolution and Particle Swarm Optimization in Partitional Clustering.”,Computational Statistics and Data Analysis, 2006.

X. Cui, T.E.Potok and P. Palathingal, “Document Clustering using Particle Swarm Optimization,” IEEE Swarm Intelligence Symposium,2005.

X.F. Xie , W.J. Zhang and Z.L. Yang ,“A dissipative particle swarm optimization,” Congress on Evolutionary Computation （CEC） , Hawaii , USA ,pp. 1456-1461, 2002.

Y. Shi and R.C. Eberhart ,“ A modified particle swarm optimizer,” In Proceedings of the IEEE Congress on Evolutionary Computation （CEC）, Piscataway, 1998.

Y. Shi and R.C. Eberhart “Empirical study of particle swarm optimization.” International Conference on Evolutionary Computation, Washington, USA： IEEE, pp. 1945-1950, 1999.

陳慶逸，“分群驗證及其在群聚分析演算法的應用”，Journal of China College of Marine Technology and Commerce，2007.

陳慶逸，余繁“應用於資料探勘之演化式群聚分析技術”，2004智慧型知識經濟暨第二屆演化代計算應用研討會，真理大學，pp.153-161, 2004.

曾憲雄，蔡秀滿，蘇東興，曾秋蓉，王慶堯，”資料探勘”，旗標出版社，2006.

丁一賢，陳牧言，”資料探勘”，滄海書局，2006.

張智星，"資料群聚與樣式辨認"，網路線上課程，可由作者之網頁http：//www.cs.nthu.edu.tw/~jang 連結到此線上課程