(3.238.99.243) 您好!臺灣時間:2021/05/16 22:54
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:李賜遠
研究生(外文):Szu-yuan Lee
論文名稱:結合K-means及粒子演算法進行動態資料分群
論文名稱(外文):Combining K-means and Particle Swarm Optimization for Dynamic Data Clustering Problems
指導教授:高有成高有成引用關係
指導教授(外文):Yu-cheng Kao
學位類別:碩士
校院名稱:大同大學
系所名稱:資訊經營學系(所)
學門:商業及管理學門
學類:一般商業學類
論文種類:學術論文
論文出版年:2008
畢業學年度:96
語文別:中文
論文頁數:72
中文關鍵詞:動態分群粒子最佳化演算法K-means資料分群
外文關鍵詞:K-meansParticle Swarm OptimizationDynamic clusteringData clustering
相關次數:
  • 被引用被引用:4
  • 點閱點閱:471
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
傳統K-means方法需要預先設定組數才能進行資料分群,為解決此問題,本研究以粒子最佳化演算法(Particle Swarm Optimization)為基礎,發展出一套動態資料分群方法,用以處理無法預先知道組數之分群問題。本研究提出之方法,結合了K-means及組合式粒子最佳化演算法,我們稱之為K-means with Combinatorial Particle Swarm Optimization (KCPSO),在演算法開始前,先給予一個最大分群組數之參數,使用組合式粒子最佳化演算法在此最大分群組數下,透過分群效度指標(Cluster Validity Index)的衡量,調整各粒子的分群組數,接著利用粒子最佳化演算法之記憶與分享資訊的能力來選取群中心,並利用K-means調整群中心的位置,如此能改善初始群中心對K-means的影響,並找出適當的分群組數與分群結果。本演算法已被開發成系統,並透過數種資料分群題目進行驗證,實驗結果顯示,相較於其他類似演算法,KCPSO能更快速且有效的分群。
This paper presents a dynamic data clustering algorithm named K-means with Combinatorial Particle Swarm Optimization (KCPSO). Unlike the K-means method, KCPSO does not need a specific number of clusters before clustering is performed and is able to find the proper number of clusters automatically. A predefined parameter of maximum cluster number is given, and a cluster validity index is employed to evaluate the clustering results in order to adjust the cluster number of each particle. Then, the cluster center among particles is adjusted by using K-means. KCPSO is able not only to avoid the drawback of K-means but also to determine the proper number of cluster. KCPSO has been developed into a system and evaluated by testing some datasets. Results show that KCPSO is an effective algorithm in providing the optimal number of clusters.
第1章 緒論 1
1.1 研究背景與動機 1
1.2 研究目的 2
1.3 研究範圍及限制 3
1.4 研究流程 4
1.5 論文架構 6
第2章 文獻探討 7
2.1分群問題 7
2.2 K-means分群演算法 8
2.3 基因演算法 9
2.4 粒子最佳化演算法 11
2.5 動態資料分群 13
2.5.1 GCUK-clustering分群演算法 13
2.5.2 DCPSO分群演算法 14
2.6 分群效度指標 16
2.6.1 Dunn’s Index 16
2.6.2 DB Index 18
2.6.3 SD Index 19
第3章 KCPSO演算法 21
3.1 KCPSO演算法 21
3.1.1 解的表達 24
3.1.2 初始階段 25
3.1.3 演化階段 25
3.1.4 參數調整說明 29
3.2 實例說明 29
3.2.1 分群實例介紹 30
3.2.2 初始階段 30
3.2.3 演化階段 32
第4章 數值與實驗比較 35
4.1 測試環境及題庫說明 35
4.2 演算法求解效率分析 38
4.3 演算法求解品質分析 41
4.4 重疊問題之比較 42
4.5 問題大小之比較 45
第5章 結論與未來研究 48
5.1 結論 48
5.2未來研究 48
參考文獻 50
附錄A GCUK演算法收歛說明 53
附錄B 問題大小實驗之資料集散佈圖 57
[1] Welch, W.J., “Algorithmic complexity: Three NP-hard problems in computational statistics.” J.Statist. Comput. Simulation, vol. 15, pp.17–25, 1982.
[2] Han, J. and Kamber, M., “Data mining: Concepts and Techniques.” San Francisco: Morgan Kaufmann Publisher, 2001.
[3] Halkidi, M. Batistakis, Y. and Vazirgiannis, M. “Clustering validitychecking methods: Part II.”, ACM SIGMOD Record, 31(3):19–27,2002.
[4] MacQueen, J. B. "Some Methods for classification and Analysis of Multivariate Observations.", Proceedings of 5-th Berkeley Symposium on Mathematical Statistics and Probability, Berkeley, University of California Press, 1:281-297, 1967.
[5] Peña, J. M., Lozano, J. A., and Larrañaga, P.,” An empirical comparison of four initialization methods for the K-Means algorithm.” Pattern Recognition Letters 20 1027-1040,1999.
[6] Goldberg, D.E., “Genetic Algorithm in Search.” Optimization and Machine Learning.”, Addision-Wesley, New York, 1989.
[7] Davis, L., “Handbook of Genetic Algorithm.” Van Nostrand Reinhold, New York, 1991.
[8] Tseng, L.Y., ”Genetic algorithm for clustering, feature selection and Classification.” 1997 IEEE International Conference on Neural Networks, vol, 3, pp. 1612-1616 1997.
[9] Maulik, U. and Bandyopadhyay, S., “Genetic algorithm-based clustering technique.” Pattern Recognition vol. 33, pp.1455-1465, 2000.
[10] Eberhart, R.C. and Kennedy, J. “A new optimizer using particle swarm theory.” Proc. Sixth International Symposium on Micro Machine and Human Science, Nagoya, Japan, pp.39-43, 1995.
[11] Eberhart, R.C. and Shi, Y. “Particle swarm optimization: developments, applications and resources” Proc. IEEE Int. Conf. On Evolutionary Computation, pp.81-86, 2001.
[12] Shi, Y. Eberhart, R. “A Modified Particle Swarm Optimizer”, Proceedings of the IEEE International Conference on Evolutionary Computation, Piscataway, NJ, 69-73, 1998.
[13] van der Merwe, D.W. and Engelbrecht, A.P. “Data clustering using particle swarm optimization.” Proceedings of IEEE Congress on Evolutionary Computation 2003 (CEC 2003), pp. 215-220, 2003.
[14] Kennedy, J. and Eberhart, R. C. “A discrete binary version of the particle swarm algorithm.” Proceedings of the World Multiconference on Systemics,Cybernetics and Informatics 1997, Piscataway, NJ. pp. 4104-4109, 1997.
[15] Mahamed G.H. Omran, Andries P Engelbrecht, and Ayed Salman. “Dynamic Clustering using Particle Swarm Optimization with Application in Unsupervised Image Classification.”, TRANSACTIONS ON ENGINEERING, COMPUTING AND TECHNOLOGY, 9,199-204, 2005.
[16] Jarboui, B. Cheikh, M. Siarry, P. and Rebai, A. “Combinatorial particle swarm optimization (CPSO) for partitional clustering problem.”, Applied Mathematics and Computation, vol. 192, pp. 337-345, 2007.
[17] Bandyopadhyay, S., and Maulik, U. “Genetic Clustering for Automatic Evolution of Clusters and Application to Image Classification.”, Journal of the Pattern Recognition, vol. 35, no. 6, pp.1197-1208, 2002.
[18] Turi, R.H. “Clustering-Based Colour Image Segmentation.”, PhD Thesis,Monash University, Australia, 2001.
[19] Halkidi, M. Batistakis, Y. and Vazirgiannis, M. “Clustering validitychecking methods: Part I.”, ACM SIGMOD Record, 31(2):40–45,2002.
[20] Dunn, J. C.. "Well separated clusters and optimal fuzzy pardtions.", J. Cybern. vol.4, pp. 95-104, 1974.
[21] Davies, D.L., Bouldin, D.W. "A cluster separation measure.", IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 1, No2, 1979.
[22] Halkidi, M., Vazirgiannis, M., Badstakis, I.. "Quality scheme assessment in the clustering process.", Proceedings of PKDD, Lyon, France, 2000.
[23] Yang S.L., Li Y.S. and Hu X.X., PAN Ruo-yu. “Optimization study on k value of K-means algorithm.Systems”, Engineering-Theory & Practice,26(2):97-101, 2006.
[24] Van den Bergh, F. “An Analysis of Particle Swarm Optimizers.”, PhD Thesis, Department of Computer Science, University of Pretoria, 2002.
[25] 黃若蘋,”啟發式演算法於資料分群問題之比較”,大同大學資訊經營所,研究所碩士論文,2007。
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
無相關期刊