跳到主要內容

臺灣博碩士論文加值系統

(44.201.97.224) 您好!臺灣時間:2024/04/18 01:56
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:黃信嘉
研究生(外文):Shin-chia Hunag
論文名稱:差分動態分群演算法
論文名稱(外文):Dynamic Clustering Using Differential Evolution
指導教授:林金城林金城引用關係
指導教授(外文):Prof. Jin-Cherng Lin
學位類別:碩士
校院名稱:大同大學
系所名稱:資訊工程學系(所)
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2008
畢業學年度:96
語文別:中文
論文頁數:68
中文關鍵詞:差分演算法資料分群動態分群分群效度指標
外文關鍵詞:differential evolutiondata clusteringdynami
相關次數:
  • 被引用被引用:4
  • 點閱點閱:433
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
資料分群為探勘技術重要研究課題之一,其過程需考慮分群組數與資料分群組
態之群中心。大部分資料分群演算法都是事先須給予固定的群數,而動態分群是指
在未給定組數下,透過演算法進行資料分群,自動找到最佳分群組數與資料分群組
態之群中心。本研究運用差分演化演算法 ( Differential evolution ) 演算法(以下簡稱
差分演算法),進行動態資料分群,稱為差分動態分群演算法( Dynamic clustering
using differential evolution, DCDE )。本演算法每個世代內,先使用常態分配抽樣決
定解向量的分群組數,接著使用差分演算法更新每個解向量的群中心值,再結合分
群效度指標 ( Cluster validity index ) 的衡量進行資料動態分群結果,使得各解向量
不斷地往最佳組數之子空間移動。本研究利用八個人工資料與四個UCI 資料集進行
測試,實驗結果顯示,DCDE 演算法在未知群數下,確實能有效的找到各組資料的
最佳群數,同時得到較佳且穩定的分群組態之群中心。
Data clustering is one of the important issues on the data mining techniques which is the process of considering as the number of cluster and the center of cluster. Most of data clustering algorithms are prior known of the number of cluster but dynamic clustering is able to find the optimal number of cluster and center of cluster dynamically by algorithms. This research is used differential evolution algorithm to perform data clustering which is called as dynamic clustering using differential evolution (DCDE). This algorithm is accessed the number of cluster of solution vectors first by normal distribution and then updating the center of cluster of every solution vectors by differential evolution. Finally, we combine cluster validity index to estimate the results of dynamic clustering to make the solution vectors move to the optimal number of cluster of the subspace constantly. This paper uses eight artificial data sets and four real-world data sets to test. The experimental results show that DCDE is able to find the accurate number of cluster and better and more stable center of cluster with unknown the accurate number of cluster.
目 錄
中文摘要ii
Abstarctiii
致謝 iv
目錄 v
圖目錄 vii
表目錄 viii
第一章 緒 論 9
1.1 研究背景與動機 9
1.2 研究目的 10
1.3 研究範圍與限制 11
1.4 研究流程 12
1.5 論文架構 14
第二章 文獻探討 16
2.1 資料分群 16
2.1.1 階層法 16
2.1.2 分割法 16
2.1.3 密度基準法 16
2.1.4 模式基準法 18
2.1.5 網格基準法 18
2.2 k-means演算法 18
2.3 粒子演算法 19
2.4 GCUK演算法 20
2.5 DCPSO演算法 20
2.6 差分演算法 21
2.6.1 DE演算法流程 23
2.7 分群效度演算法 23
第三章 研究方法 27
3.1 DCDE演算法模型 27
3.1.1 資料分群數學模式 28
3.1.2 常態分佈模型 28
3.2 DCDE演算法介紹 30
3.2.1 DCDE演算法簡介 30
3.2.2 參數初始 32
3.2.3 解的表達 33
3.2.4 演算法過程 33
3.2.5 演算法說明 34
3.3 避免不合理解( Infeasible solution )的處理 36
第四章 DCDE演算法範例說明 38
4.1 DCDE演算法流程圖 38
4.2 DCDE演算法範例說明 38
第五章 實驗結果與評估 46
5.1 測試環境與資料集 . 46
5.2 參數測試與實驗參數設定 48
5.3 DCDE演算法與GCUK,DCPSO演算法比較最佳群數 50
5.4 綜合演算法求解品質比較 51
5.5 綜合演算法收歛趨勢比較 54
5.6 問題大小對DCDE演算法之影響 57
第六章 結論與未來研究 58
6.1 結論 58
6.2 未來研究 58
參考文獻 60
附錄A人工資料實驗之資料集合及散佈圖 64
[1]
MacQueen., J. B., "Some Methods for classification and Analysis of Multivariate bservations, Proceedings of 5-th Berkeley Symposium on arithmetical Statistics and Probability", Berkeley, University of California Press, 1:281-297 Agrawal, R., Gehrke, J., Gunopulos, D. and Raghavan, P., “Automatic Subspace.
[2]
Bezdek, J. C., “Pattern recognition with fuzzy objective function algorithms”, New York, plenum plress 1983. 95-107.
[3]
Friedman, H. P. and Rubin, J. “On some invariant criteria for grouping data,” J. Amer. Statist. Ass. , Vol. 62, No. 320, pp.1159-1178, 1967.
[4]
Maulik, U., Bandyopadhyay, S., “Genetic algorithm-based clustering technique”, Pattern Recognition 33 (2000) 1455-1465.
[5]
DW van der Merwe, Y., Engelbrecht, A., “Data Clustering using Particle SwarmOptimization”, Evolutionary Computation, 2003. CEC '03. The 2003 Congress on.
[6]
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]
Paterlini, S. P., Thiemo, K., “Differential evolution and particleswarm optimisation in partitional clustering”, Computational Statistics& Data Analysis 50 (2006) 1220 – 1247.
[8]
Dunn J. C., “Well separated clusters and optimal fuzzy partitions”, J Cybern 4:95–104.
[9]
Bouldin, D., “A cluster separation measure”, IEEE Trans Pattern Anal Mach 6 0
Intell 1(2).
[10]
Ray, S., Turi, R. H., “Determination of number of clusters in K-means clustering and application in color image segmentation”, In: Proceedings of the 4th International Conference on Advances in Pattern Recognition and Digital Techniques, Calcutta, India, 27–29 December, 1999.
[11]
Shen, J., Chang, S. I., Lee, E. S., Deng, Y., and Brown, S. J., “Determination of cluster number in clustering microarray data”, Applied Mathematics and Computation 169, Issue 2, 15 October 2005, Pages 1172-1185.
[12]
Halkidi, M., Vazirgiannis, M., “Clustering validity assessment: finding the optimal partitioning of a data set”, In: Proceedings of ICDM conference, CA, USA., 2001.
[13]
Halkidi, M., Vazirgiannis, M., “Clustering validity assessment using multi representative”, In: Proceedings of SETN conference, Thessaloniki, Greece.
[14]
Hamerly, G., Elkan, C., “Learning the K in K-means”, In: 7th annual conference on neural information processing systems.
[15]
Lee, C.Y., Antonsson, E.K., “Dynamic partitional clustering using evolution strategies”, In: The third Asia-Pacific conference on simulated evolution and learning.
[16]
Roy, D,Y, and David J.G., ”Probability and Stochastic Processes”, 1999.
[17]
Han, J., and Kamber, M., “Data mining: Concepts and Techniques”, San Francisco:Morgan Kaufmann Publisher, 2001.
[18]
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.
[19]
Chandrasekharan, M. P., and Rajagopalan, R., “An ideal seed non-hierarchical
[20]
Agrawal, R., Gehrke, J., Gunopulos, D. and Raghavan, P., “Automatic SubspaceClustering of High Dimensional Data for Data Mining Applications”, Proc. of the ACM SIGMOD Conference on Management of Data, pp. 94-104, 1998.
[21]
Wang, W., Yang, J. and Muntz, R., “STING: A Statistical Information Grid Approach to Spatial Data Mining”, Proc. of the 23th VLDB Conference, pp. 186-195, 1997.
[22]
Sheikholeslami, G., Chatterjee, S., and Zhang, A., “WaveCluster: A Multiresolution.
[23]
Kennedy, J. and Eberhart, R.C., “Particle swarm optimization”, IEEE International Conference on Neural Networks, Vol. IV, 1995, pp. 1942-1948.
[24]
Shi,Y., and Eberhart, R., “ A Modified Particle Swarm Optimizer”, IEEE International Conference on Evolutionary Computation, May 1998, Anchorage,Alaska, USA.
[25]
Shi Y., Eberhart, R., “Empirical study of particle swarm optimization,”, IEEE International Conference of Evolutionary Computation”, Vol. 3, pp.101-106. 1999.
[26]
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.
[27]
Mahamed, G. H., Omran, Engelbrecht,A. P., and Salman, A., “Dynamic Clustering using Particle Swarm Optimization with Application in Unsupervised Image Classification”, Transactions On Engineering, Computing And Technology, 9,199-204, 2005.
[28]
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.
[29]
Storn, R., Price, K., “Differential evolution – A Simple and Efficient Heuristicfor Global Optimization over Continuous Spaces”, Journal of Global Optimization, 11(4) (1997) 341–359
[30]
Halkidi, M., Batistakis, Y., and Vazirgiannis, M., “On clustering validation techniques.”, Intell Inform Syst J 17(2–3):107–145
[31]
Zhang, D., Liu, X., Guan, Z., “A Dynamic Clustering Algorithm Based on PSOand Its Application in Fuzzy Identification”, Intelligent Information Hiding and Multimedia Signal Processing, 2006. IIH-MSP '06. International Conference on, 2006 Page(s):232 - 235
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top