淡江大學覺生紀念圖書館 (TKU Library)
進階搜尋


下載電子全文限經由淡江IP使用) 
系統識別號 U0002-2206200921110600
中文論文名稱 以螞蟻、塔布基因為基礎的混合式雞尾酒分群法之探討
英文論文名稱 A Mix Cluster Method Based on Ant Genetic and Tabu Search
校院名稱 淡江大學
系所名稱(中) 資訊管理學系碩士班
系所名稱(英) Department of Information Management
學年度 97
學期 2
出版年 98
研究生中文姓名 朱芳儀
研究生英文姓名 Fang-Yi Chu
學號 696631505
學位類別 碩士
語文別 中文
口試日期 2009-06-07
論文頁數 53頁
口試委員 指導教授-李鴻璋
委員-翁頌舜
委員-趙涵捷
委員-侯永昌
中文關鍵字 螞蟻分群法  基因演算法  塔布搜尋法  k均值法  分群效度指標 
英文關鍵字 Ant Colony system  Genetic Algorithm  Tabu Search  K-means  Cluster validity index 
學科別分類 學科別社會科學管理學
學科別社會科學資訊科學
中文摘要 分群是將相似度高的物件分類成群,而分群有許多方法,從傳統的階層式分群法、分割式分群法、密度分群法到應用啟發式演算法在分群上。對於傳統的分群法,例如常見的K-means,使用者需先決定群數,才能進行分群。
本研究發展一個能自動決定適合群數的演算法,簡稱AGKT,混合了螞蟻分群、基因、K-means及塔布搜尋演算法之概念,並探討以不同分群效度指標做作目標函數之正確率差異。演算法分為兩階段:第一階段由螞蟻分群法(ASCA)產生初始群組;第二階段搭配基因遮罩及分群效度指標的K-means分群,找出最佳群數與分群結構。
在效能評估方面,我們使用UCI Machine Learning Repository[3]和Gerrild and Lantz[11]所提供的4個資料集,與其他七個分群方法進行比較與評估[2,15]。此外亦利用該資料集,來探討目前提出之分群效度指標,並提出一種新的分群效度指標PBM+ index。
實驗結果顯示,相較於其他七個分群方法,AGKT皆能非常快速且正確分群。相較於ESTA[15]分群法, AGKT平均約快40倍且分群效度表現上差不多。
探討分群效度指標方面,我們研究效度指標,分別為:Dunn’s index、Davies Boundin index、PBM index及我們提出的PBM+ index。而實驗證實,4種分群效度指標中,以PBM+ index進行分群得到了較好的分群數與分群結果。
英文摘要 Clustering is to collect those objects are high similarity into a group, there are many methods to clustering. The common methods of clustering include the traditional hierarchical clustering, partitional clustering, density-based clustering and and application of heuristic clustering algorithms on the cluster. K-means is a kind of traditional clustering methods, users need to decide the cluster number before clustering.
This research developed an algorithm that can automatically decides the cluster number, called AGKT. It mixed of ant clustering, Gene, K-means and the concept of tabu search algorithm, and explore Cluster validity indexes as to objective functions to compare the performance of the correct rate.
There are two stages of algorithm: the first stage generated the initial group by ASCA; The second stage find out the best structure and number of cluster with the mask of Gene and k-means, with Cluster validity index.
In the performance assessment, we compare and estimate with seven other clustering methods [2,15], and use four data sets provided from the UCI Machine Learning Repository[3] and Gerrild and Lantz[11]. In addition, we also make use of these data sets to explore the current cluster validity index, and propose a new index called PBM+ index.
The results showed that, AGKT can faster and accurate clustering than the seven other clustering methods. Compared to the ESTA [15], AGKT about 40 times faster in the performance of Cluster validity index.
Discussion on Cluster validity index, we use four Cluster validity index, including: Dunn's index, Davies Boundin index, PBM index and PBM+ index provided from us. The research confirmed that the four Cluster validity index to PBM+ index has better result.
論文目次 目錄
第一章 緒論 1
1.1. 研究背景 1
1.2. 研究動機與目的 2
第二章 文獻探討 3
2.1. 階層式分群法 3
2.2. K均值分群法 4
2.3. DBSCAN分群法 10
2.4. 蟻群系統 14
2.5. 基因演算法 19
2.6. 塔布搜尋法 27
2.7. 群間距離 28
第三章 研究方法 30
3.1. 演算法架構 30
3.2. ASCA 32
3.3. 基因遮罩 35
3.4. 分群效度指標 36
第四章 研究結果 38
4.1. 參數設定 39
4.2. 以PBM-index和其他演算法比較 41
4.3. 各分群效度指標之評比 47
第五章 結論 50

圖目錄
圖 1:K均值法原始資料 5
圖 2:K均值演算法步驟1 6
圖 3:K均值演算法步驟2 7
圖 4:K均值演算法步驟3 7
圖 5:K均值演算法步驟4 8
圖 6:K均值演算法步驟5 8
圖 7:K均值演算法步驟6 9
圖 8:K均值演算法步驟7 9
圖 9:DBSCAN密度可達(DENSITY REACHABLE)示意圖 11
圖 10:DBSCAN密度可連接(DENSITY-CONNECTED)示意圖 12
圖 11:真實螞蟻案例 15
圖 12:蟻群演算法流程圖 18
圖 13:基因演算法流程圖 20
圖 14:基因演算法編碼型態 21
圖 15:輪盤法 22
圖 16:單點交配 23
圖 17:雙點交配 24
圖 18:順序交配 25
圖 19:字罩交配 26
圖 20:二元編碼突變 27
圖 21:實數編碼突變 27
圖 22:研究架構圖 31
圖 23:ASCA流程圖 34
圖 24:基因遮罩 35

表目錄
表 1:DBSCAN主程式演算法 12
表 2:DBSCAN EXPANDCLUSTER演算法 13
表 3:不同方法距離計算公式 29
表 4:資料集分群數、維度及資料量 38
表 5:第一階段Theta參數設定及分群結果 39
表 6:AGKT與TAC分群效度指標PBM INDEX與時間之比較 40
表 7:CPU與其MFLOPS 41
表 8:各演算法執行環境 42
表 9:CPU與其MFLOPS 43
表 10: IRIS分群結果比較 44
表 11:BREAST CANCER WISCONSIN分群結果比較 45
表 12:CRUDE-OIL分群結果比較 46
表 13:WINE分群結果比較 47
表 14:不同分群效度指標之正確率比較 48
表 15:AGKT與TAC之正確率比較 49
參考文獻 參考文獻
中文文獻:
1.周仕雄, 應用螞蟻系統於資料挖礦之集群分析,國立臺北科技大學生產系統工程與管理研究所碩士論文,2003。
2.曾偉哲,以塔布基因為基礎的兩階段碼以分群方法,淡江大學資訊管理學系碩士班碩士論文,2009。
英文文獻:
3.A. Asuncion and D.J. Newman, “UCI machine learning repository,” 2007, url: www.ics.uci.edu/mlearn/MLRepository.html.
4.D. L. Davies and D. W. Bouldin,” A cluster separation measure,” IEEE Trans. Pattern Anal. Mach. Intell 1(2), 1979,pp. 224-227.
5.M. Dorigo and L. Gambardella, “Ant colony system: A cooperative learning approach to the traveling salesman problem,” IEEE Transactions on Evolutionary Computation 1(1), 1997, pp. 53-66.
6.M. Dorigo, V. Maniezzo and A. Colorni, ”Ant system: Optimization by a colony of cooperating agents,” IEEE Transactions on Systems, Man, and Cybernetics, Part B 26(1), 1996, pp. 29-41.
7.J. Dunn, “Well-separated clusters and optimal fuzzy partitions,” Cybern. Syst. 4(1), 1974, pp. 95-104.
8.M. Ester, H. P. Kriegel, J. Sander and X. Xu, ”A density-based algorithm for discovering clusters in large spatial databases with noise,” Presented at Proc. 2nd Int. Conf. on Knowledge Discovery and Data Mining, Portland, OR, AAAI Press.
9.F. Glover, “Tabu search-part I,” ORSA Journal on Computing 1(3), 1989, pp. 190-206.
10.J. H. Holland, Adaptation in Natural and Artificial Systems,1992.
11.R. A. Johnson and D. W. Wichern, Applied Multivariate Statistical Analysis,1998.
12.J. MacQueen, ” Some methods for classification and analysis of multivariate data,” Presented at 5th Berkeley Symposium, 1967: pp. 281-297.
13.C. D. Manning, P. Raghavan and H. Schtze, Introduction to Information Retrieval, 2008.
14.M. K. Pakhira, S. Bandyopadhyay and U. Maulik, “Validity index for crisp and fuzzy clusters,” Pattern Recognit 37(3), 2004, pp. 487-501.
15.S. M. Pan and K. S. Cheng, “Evolution-based tabu search approach to automatic clustering,” IEEE Transactions on Systems, Man, and Cybernetics, Part C: Applications and Reviews 37(5), 2007, pp. 827-838.
論文使用權限
  • 同意紙本無償授權給館內讀者為學術之目的重製使用,於2010-06-24公開。
  • 同意授權瀏覽/列印電子全文服務,於2010-06-24起公開。


  • 若您有任何疑問,請與我們聯絡!
    圖書館: 請來電 (02)2621-5656 轉 2281 或 來信