蟻群尋優法(Ant colony optimization)是一種啟發式方法，已經成功地應用在求解複雜的最佳化問題。而該方法也適用於資料探勘中的集群分析。許多研究也使用螞蟻演算法來進行資料分群，分群結果也優於其他啟發式方法。為了增進螞蟻演算法的分群效果，我們使用人工免疫系統的概念來強化分群效果。因此本研究提出一個兩階段的集群分析方法：Immunity-based Ant Clustering Algorithm (IACA) 以及 Ant Colony System-Based K-means (ACSK)。第一階段的分群演算法IACA是一種自動分群方法結合螞蟻演算法和人工免疫系統的特點，可以決定分群結果的群數和各群的中心點。而第二階段的ACSK是一種結合蟻拓法(Ant Colony System)和傳統K-Means演算法的分群方法。
根據IACA產生的初始解再運用ACSK來進行最佳化，則為本研究提出的兩階段分群演算法。為了評估所提出的分群演算法的效果和驗證可行性，我們利用蒙地卡羅法模擬產生資料集以及利用一個真實案例來測試並與其他分群方法進行比較包括：Self-Organizing Map (SOM), SOM+GA-based clustering algorithm, Ant System-based Clustering Algorithm(ASCA), 以及Ant System-based Clustering Algorithm + Ant K-means Algorithm(ASCA+AK)。結果顯示了本文提出的方法的確有著更佳的分群結果和較小的總組內變異。

Ant colony optimization is a meta-heuristic approach successfully applied to solve hard combinatorial optimization problems. It is also feasible for clustering analysis in data mining. Many researches use ant algorithms for clustering analysis and the result is better than other heuristic methods. In order to improve the performance of the algorithm, we use the concept of artificial immune system to strengthen the ant algorithm for clustering analysis. This study proposes a two-stage method for clustering problem, the immunity-based Ant Clustering Algorithm (IACA) and the Ant Colony System-Based K-means (ACSK). IACA using the immune system and ant algorithm is an auto-clustering method which can decide the number of the clusters and its centroids. According to the initial solution of IACA, we utilize ACSK which combines the K-means algorithm with the Ant Colony System algorithm to optimize its performance.
The data sets generated using the Monte Carlo simulation and a real case data are used to evaluate the efficiency and validate the feasibility of the proposed algorithms and other clustering methods including Self-Organizing Map (SOM), SOM+GA-based clustering method, Ant System-based Clustering Algorithm (ASCA), and Ant System-based Clustering Algorithm +Ant K-means Algorithm(ASCA+AK). The proposed algorithm indeed has better clustering performances and smaller total within cluster variance according to the result of the experiment.

摘要 i
ABSTRACT ii
誌謝 iii
Content iv
List of Tables vi
List of Figures vii
Chapter 1 Introduction 1
1.1 Motivation and Background 1
1.2 The Objectives 2
1.3 The Scope and Constrains 2
1.4 Research Process 3
Chapter 2 Literature Review 4
2.1 DATA MINING 4
2.1.1 The knowledge Discovery Process 4
2.1.2 The methods of Data Mining 5
2.2 Clustering Analysis 6
2.2.1 The methods of Clustering Analysis 6
2.3 Ant Colony Optimization 8
2.3.1 Ant System 9
2.3.2 Ant Colony System 11
2.4 Artificial Immune System 13
2.4.1 Immune System 13
2.4.2 Immune-based Algorithm 15
Chapter 3 Methodology 16
3.1 Monte Carlo Study 18
3.2 Proposed Algorithm 20
3.2.1 The Notations and Definitions 20
3.2.2 The Immunity-based Ant Clustering Algorithm 22
3.2.3 The Ant Colony System-based K-means 28
3.3 Evaluation of six Clustering Algorithms 32
Chapter 4 Simulation 33
4.1 Verification of Random Number Generator 33
4.2 Generating simulation data sets 33
4.3 Experiment Results and analysis 36
4.3.1 The result of IACA 36
4.3.2 The result of IACA+ACSK 38
4.3.3 The comparison of six clustering algorithms 39
4.3.4 The Analysis of the Experiments 43
Chapter 5 Case Study and Discussion 45
5.1 The Structure of Sample 45
5.2 Clustering Analysis 46
5.3 Factors Analysis 47
5.3.1 The Mean Difference Analysis for Each Factor 47
5.3.2 The Analysis of Demographic Variables for Each Cluster 49
5.4 Summary 52
Chapter 6 Conclusions and Suggestions 53
6.1 Conclusions 53
6.2 Contribution 53
6.3 Future Research Issues 54
REFERENCE 55
Appendix: 59

[1] Tseng, L. Y. and Yang S. B., “A genetic approach to the automatic clustering problem,” Pattern Recognition 34, pp.415-424, 2001.
[2] Kanungo, T., Mount, D., Netanyahu, N., Piatko, C., Silverman, R. and Wu, A., ”A local search approximation algorithm for k-means clustering,” 18th Annual ACM Symposium on Computational Geometry, pages 10-18, 2002.
[3] Labroche, N., Monmarché, N. and Venturini, G., ”A new clustering algorithm based on the chemical recognition system of ants,” 15th European Conference on Artificial Intelligence, 2002.
[4] Vinokourov, A. and Girolami, M., “A Probabilistic Hierarchical Clustering Method for Organising Collections of Text Documents,” Department of Computing and Information Systems University of Paisley, 2000.
[5] Freitas, A. A., “A Survey of Evolutionary Algorithms for Data Mining and Knowledge Discovery,” Advances in Evolutionary Computation, Springer-Verlag, 2002.
[6] Sung, C. S.and Jin, H. W., “A tabu-search-based heuristic for clustering,” Pattern Recognition 33, pp.849-858, 2000.
[7] Jain, A. K., Murty, M. N. and Flynn, P. J., “Data Clustering: A Review,” ACM Computing Surveys, Vol. 31, No. 3, September, 1999.
[8] Tsai, C. F., Wu, H. C. and Tsai, C. W., “A New Clustering Approach for Data Mining in Large Databases,” Proceedings of the international Symposium on Parallel Architectures, Algorithms and Networks (ISPAN’02), IEEE Computer Society, pp.1087-4089, 2002.
[9] Ding, C. and He, X., “Cluster merging and splitting in hierarchical clustering algorithms,” IEEE International Conference on , 9-12 Dec. 2002, Page(s): 139 —146, 2002.
[10] Hinneburg, A. and Keim, D. A., “An Efficient Approach to Clustering in Large Multimedia Databases with Noise,” Knowledge Discovery and Data Mining, 1998.
[11] Parpinelli, R. S., Lopes, H. S. and Freitas, A. A., “Data Mining With an Ant Colony Optimization Algorithm,” IEEE Trans on Evolutionary Computation, special issue on Ant Colony Algorithms, 6(4), August, 2002.
[12] Monmarché, N., “On data clustering with artificial ants,” Data Mining with Evolutionary Algorithms: Research Directions, 1999.
[13] Monmarché, N., Slimane, M. and Venturini, G., “On Improving Clustering in Numerical Databases with Artificial Ants,” In D. Floreano, J.D. Nicoud, and F. Mondala, editors, Lecture Notes in Artificial Intelligence, pages 626-635, Swiss Federal Institute of Technology, Lausanne, Switzerland, 13-17 September 1999.
[14] Dorigo, M. and Caro, G. Di., “The Ant Colony Optimization Meta-Heuristic,” In Corne, D., Dorigo, M. and Glover, F., editors, New Ideas in Optimization, McGraw-Hill, 11-32, 1999.
[15] Bonabeau E., Dorigo, M. and Theraulaz, T., “From Natural to Artificial Swarm Intelligence,” New York: Oxford University Press, 1999.
[16] 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.1, pp.1-13, 1996.
[17] Dorigo, M. and Gambardella, L. M., “Ant Colonies for the Traveling Salesman Problem,” BioSystems, 43 , pp.73-81, 1997.
[18] 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, April, 1997.
[19] Dorigo, M., Caro, G. Di. and Gambardella, L. M., ”Ant Algorithms for Discrete Optimization,” Artificial Life, 5(2):137-172, 1999.
[20] Colorni A., M. Dorigo , V. Maniezzo, ”Distributed Optimization by Ant Colonies,” Proceedings of the First European Conference on Artificial Life, Elsevier Publishing, pp.134-142, 1992.
[21] Stützle T. and M. Dorigo, ”ACO Algorithms for the Traveling Salesman Problem,” Evolutionary Algorithms in Engineering and Computer Science, Wiley, 1999.
[22] M. Dorigo, V. Maniezzo, A. Colorni, “Positive Feedback as a Search Strategy,” Technical Report No. 91-016, Politecnico di Milano, Italy, 1991.
[23] Dorigo, M., G. Di Caro, L. M. Gambardella, “Ant algorithms and stigmergy,” Future Generation Computer Systems 16, p.851-871, 2000.
[24] Dorigo, M. and Stützle, T., ”The Ant Colony Optimization Metaheuristic: Algorithms, Applications, and Advances,” Technical Report IRIDIA, 2000.
[25] Dorigo, M., Gambardella, L. M., Middendorf, M. and Stützle, T., “Guest Editorial Special Section on Ant Colony Optimization,” IEEE Transactions on Evolutionary Computation, Vol.6, No.4, August, 2002.
[26] Dasgupta, D. and Attoh-Okine, N., “Immunity-Based Systems： A Survey,” Proceeding of the IEEE Transactions on Systems, Man and Cybernetics, Vol. 1, pp. 369 —374, 1997.
[27] Dote, Y., “Soft Computing (Immune Networks) in Artificial Intelligence,” Proceeding of the IEEE Transactions on Systems, Man and Cybernetics, Vol. 2, pp.1382 —1387, 1998.
[28] Hajela, P., Yoo, J. and Lee, J., “GA based simulation of immune networks applications in structural optimization,” Engineering Optimization, 22, 131-149, 1997.
[29] Krishnaiyer, K. and Cheraghi, S. H.; "Ant Algorithms: Review and Future Applications", IERC’02, Industrial Engineering Research Conference, Orlando, Florida, USA, May 2002.
[30] De Castro, L. N. and Von Zuben, F. J., “Artificial Immune System: Part I —Basic Theory and Applications”, Technical Report RT-DCA 01/99, 1999.
[31] Wang, L. and Jiao, L., “A novel genetic algorithm based on immunity,” 2000 IEEE International Symposium on Circuits and Systems, pp. 385-388, 2000.
[32] Lee, Z. J., Lee, C. Y. and Su, S. F., "An immunity-based ant colony optimization algorithm for solving weapon—target assignment problem," Applied Soft Computing Journal Volume: 2, Issue: 1, August, pp. 39-47, 2002.
[33] Ester, M., Kriegel, H. P., Sander, J.and Xu, X., “A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise,” Proceedings of 2nd International Conference on Knowledge Discovery and Data Mining (KDD-96), 1996.
[34] Kuo, R. J., Ho, L. M. and Hu, C. M., “Integration of Self-Organizing Feature Map and K-Means Algorithm for Market Segmentation,” International Journal of Computers and Operations Research, 29, pp. 1475-1493, 2002a.
[35] Kuo, R. J. and Chung, W. J., “Integration of Self-Organizing Map and Genetic K-Means Algorithm for Data Mining”, Proceedings of 30th International Conference of Computer and Industrial Engineering, Tinos Island, Aggean, Sea, Greece, Jun. 29 — Jul. 2, 2002b.
[36] Kuo, R. J., Chang, K. and Chien, S.Y., “Integration of Self-Organizing Feature Map and Genetic Algorithm Based Clustering Method for Market Segmentation,” Journal of Organizational Computing and Electronic Commerce, 2002c.
[37] Chien, S. Y., “Integration of Self-Organizing Feature Maps and GA-Based clustering Method for Market Segmentation in Data Mining,” Master thesis, National Taipei University of Technology, 2001.
[38] Kuo, R. J., Chiu, C. Y., Wang, H. S. and Chio, S. H.,”Application of Ant System on Clustering Analysis in Data Mining,” submitted to IEEE Transactions on Evolutionary Computing.
[39] Fayyad, U., “Data Mining and Knowledge Discovery in Databases: Implications for Scientific Databases,” Scientific and Statistical Database Management, 1997. Proceedings., Ninth International Conference, pp.2-11, 1997.
[40] Berkhin, P., “Survey of Clustering Data Mining Techniques,” Accrue Software, Inc. http://www.accrue.com/products/researchpapers.html , 2002.
[41] Sethi, I. K., “Data Mining: An Introduction,” Data Mining For Design and Manufacturing, Kluwer Academic Publishers, 2001.
[42] Chen, M., Han, J. and Yu, P. S., “Data Mining: An overview from a Database Perspective,” IEEE Transactions on Knowledge and Data Engineering, Vol. 8, No.6, December, 1996.
[43] Krishna, K. and Murty, M., “Genetic K-Means Algorithm,” IEEE Transactions on Systems, Man, and Cybernetics-Part B: CYBERNETICS, Vol.29, No.3, pp. 433-439, 1999.
[44] Caro, G. D. and Dorigo, M., “AntNet: Distributed Stigmergetic Control for Communications Networks,” Journal of Artificial Intelligence Research 9, pp.317-365,1998.