臺灣博碩士論文加值系統

本研究主要是結合ACO (Ant Colony Optimization)演算法和禁忌搜尋法(Tabu Search，TS)，發展出新的資料分群演算法，我們將之命名為HACOC(Hybrid Ant Colony Optimization for Clustering)。當求解資料分群問題時，如果群組數變大以及資料點變多，ACO資料分群演算法的求解效率變差。原因是螞蟻在求解的過程中，所需嘗試的解相對變多，導致螞蟻沒有辦法在演算法演化早期儘快地將費洛蒙留在不錯的節點上，導致求解的品質及收斂速度受到影響。所以我們將ACOC演算法在每一回合螞蟻找出來的最佳解後，加入禁忌搜尋法進行區域搜索，以找尋更佳的解。利用螞蟻演算法全域搜索求解的特性，結合禁忌搜尋法區域搜索求解的特性，可以有效改善ACOC演算法求解的品質及收斂速度。本演算法已經開發成系統，針對五個資料分群問題進行實驗，結果顯示HACOC確實能夠有效改善ACOC資料分群的績效。我們也將HACOC與其他分群方法進行比較，例如k-means、Tabu Search、GA、SACO及ACO等，發現HACOC分群能力優於其他方法。

This research mainly focuses on integrating the Tabu search method with the ACO (Ant Colony Optimization) method for developing a new data clustering algorithm. When the ACO algorithm is applied to solve clustering problems, it is found that the solution quality may get worse if the number of data items or the group number becomes large. In a large solution space, it is difficult for ants to lay pheromone on better routes in the early stage of evolution, so the calculation process needs much more time to reach a high-quality solution. To find out a better clustering solution, in each ACO iteration, the tabu search method is used to improve the best solution found by ants before they update the pheromone trails. In other words, Tabu search performs the local search while ACO carries out the global search. The proposed algorithm has been named as HACOC (Hybrid Ant Colony Optimization for Clustering) and implemented into a software system in C++. Five clustering problems are generated or collected for the numerical experiment. The experimental results show that HACOC can effectively improve the weakness of ACO-based clustering methods and outperforms other methods, such as K-means, Tabu Search, genetic algorithm, and pure ACO.

第1章 緒論 1
1.1 研究背景與動機 1
1.2 研究目的 2
1.3 研究範圍及限制 3
1.4 研究流程 4
1.5 論文架構 6
第2章 文獻探討 7
2.1 資料分群方法 7
2.1.1 分割法 8
2.1.2 階層法 8
2.1.3 密度為基法 9
2.1.4 網格為基法 10
2.1.5 模式為基法 10
2.2 禁忌搜尋法 10
2.3 基因演算法 12
2.4 螞蟻演算法 14
第3章 HACOC演算法 18
3.1 分群問題 18
3.2 螞蟻演算法 20
3.3 禁忌搜尋法 22
3.4 演算流程架構 25
3.5 實例說明 29
第四章 數値與實驗比較 36
4.1 演算法綜合比較 36
4.2 收斂趨勢之比較 43
4.3 HACOC和ACOC演算法參數之分析 45
4.4 改善HACOC CPU Time 51
4.5 問題大小對HACOC之影響分析 54
5.1 結論 56
5.2未來研究 57
中文參考文獻 59
附錄A 演算法之整體收斂圖 60
附錄B不同螞蟻數之收斂比較 62
附錄C 問題大小對HACOC影響之資料集合 64

[1] Agrawal, R., Gehrke, J., Gunopulos, D. and Raghavan, P., “Automatic Subspace
Clustering of High Dimensional Data for Data Mining Applications.” Proc. of
the ACM SIGMOD Conference on Management of Data, pp. 94-104, 1998.
[2] Al-Sultan, K. S., “A tabu search approach to the clustering problem.” Pattern
Recognition 28 (1995) 1443-1451.
[3] Bandyopadhyay, S.,“Genetic clustering for automatic evolution of clusters and
application to image classification,” pattern recognition,35, pp. 1197-1208, 2002
[4] Chandrasekharan, M. P., and Rajagopalan, R., “An ideal seed non-hierarchical
clustering algorithm for cellular manufacturing.” International Journal of
Production Research, Vol. 24, pp. 451-464, 1986.
[5] Delgado, M.,“A tabu search approach to the fuzzy clustering problem.” CICYT
project TIC95-1019,IEEE 1997.
[6] Deneubourg, J., Goss, S., Franks, N., Sendova-Franks, A., Detrain, C. and
Chretien, L., “The dynamics of collective sorting robot-like ants and ant-like
robots.” Proc. Of the 1st Conf. on Sim. of Adaptive Behavior, pp. 356-363, 1991.
[7] Dorigo, M., and Gambardella, L. M., “Ant Colony System: A Cooperative Learning
Approach to the Traveling Salesman Problem.” IEEE Transactions on Evolutionary Computation, Vol.1, No.1, pp.53-66, 1997.
[8] Dorigo, M., Maniezzo, V., and Colorni, A., “The ant system: optimization by a
colony of cooperating agents.” IEEE Transactions on Systems, Man, and Cybernetics--Part B , Vol. 26, No. 2, pp. 29-41, 1996.
[9] Dorigo, M., Stützle, T., “Ant Colony Optimization.” Cambridge, MA:
MIT Press, 2004.
[10] Glover, F., “Tabu Search, part i.” ORSA Journal Of Computing, vol 1, no.3
pp. 190-206, 1989.
[11] Goldberg, D.E., “Genetic Algorithm in Search.” Optimization and Machine
Learning, Addision-Wesley, New York, 1989
[12] Han, J. and Kamber, M., “Data mining: Concepts and Techniques.” San
Francisco: Morgan Kaufmann Publisher, 2001.
[13] Xu, H., “Fuzzy tabu search method for the clustering problem.”
Proceedings of the first international conference on machine learning and cybernetics, Beijing, IEEE 2002,
[14] Kao Y. and Cheng K., ”An ACO-Based Clustering Algorithm.” ANTS
2006, LNCS 4150 ,pp.340-347, 2006
[15] Lumer, E. and Faieta, B., “Diversity and adaptation in populations of clustering
ants.” Proc. Of the 3rd International Conference on Simulation of Adaptive Behavior：From Animals to Animats. Eds.: Cliff et al., Cambridge, MA: MIT Press, pp. 501-508, 1994.
[16] Davis, L., “Handbook of Genetic Algorithm.” Van Nostrand Reinhold,
New York, 1991
[17] Maulik, U. amd Bandyopadhyay, S., “Genetic algorithm-based clustering
technique.” Pattern Recognition Vol. 33, pp.1455-1465, 2000
[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] Saha, S. Bandyopadhyay, S.,“A fuzzy genetic clustering technique using a new
symmetry based distance for automatic evolution of clusters.” Theory and
Application ICCTA’07, International Conference
[20] Sheikholeslami, G., Chatterjee, S., and Zhang, A., “WaveCluster: A Multiresolution
Clustering Approach for Very Large Spatial Databases.” Proc. On the 24th VLDB Conference, pp. 428-439, Aug 1998.
[21] Shelokar, P. S., Jayaraman, V. K. and Kulkarni, B. D., “An ant colony
approach for clustering.” Analytica Chimica Acta Vol. 509, No.2, pp. 187-195, 2004.
[22] Tseng, L.Y., ”Genetic algorithm for clustering, feature selection and
Classification.” 1997 IEEE International Conference on Neural
Networks,vol, 3, pp. 1612-1616 1997
[23] UCI Repository of Machine Learning Databases, from website:
http://www.ics.uci.edu/~mlearn/MLRepository.html, 1998.
[24] 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.
[25] Welch, W.J., “Algorithmic complexity: Three NP-hard problems in computationalstatistics.” J.Statist. Comput. Simulation, Vol. 15, pp.17–25, 1982.
.
中文參考文獻

[26] 丁淯淨，改良式螞蟻分群演算法，大同大學資訊經營，研究所碩士論文，
2006。