分群是將相似度高的物件分類成群，而分群有許多方法，從傳統的階層式分群法、分割式分群法、密度分群法到應用啟發式演算法在分群上。對於傳統的分群法，例如常見的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.