臺灣博碩士論文加值系統

群集分析（Cluster Analysis）為資料探勘（Data Mining）領域中，最常被用以對大量資料進行預測、推估的應用技術，其主要的目標在於透過群集演算法區隔出不同且未知類別的資料，並將相似性較高的資料形成不同的群集，使決策者得以藉由群集分析應用的結果提供決策分析時所需的參考資訊，故分群演算法的發展及使用，實為相當重要且值得研究的一環。在群集問題分析之分群求解的應用上，基於群集演算法在使用上之便利性、時效性及易取得等方面的考量，K-Means演算法是最常被使用於分群的一種工具，然而，在實際的群集問題應用中，K-Means演算法卻也有其缺點。
本論文結合傳統群集演算法的觀念與啟發式方法之螞蟻理論的技術，發展一個能夠求得較佳全域解之群集結果的群集演算法，以跳脫K-Means演算法易於落入局部最佳化群集結果的窘境。為了驗證本研究所提出之方法為一有效之群集演算法，本研究透過數個範例資料的實驗驗證，探討在實際應用上所產生的群集結果之優劣程度，由此些應用中可知我們所提出的群集演算法確實能夠改善K-Means演算法的缺點，進而求得較佳之群集結果目標值與群集正確率。本研究並以一實際的PCB製造廠商之產品設計規格資料及品質缺陷資料，進行PCB新產品品質缺陷之預估，期望經由本研究所提出之群集演算法與群集分析應用，以有效且正確地分析出新產品在實際生產中可能會發生的品質缺陷，藉此提早預防以降低生產成本、提高新產品之生產良率。

Cluster analysis is a technique used to forecast and infer a great deal of data in the domain of data mining. Its major objective is to differentiate the data that have unknown categories. Decision manager can obtain the reference information through the result of cluster analysis. Therefore developing an efficient clustering algorithm is important for many applications. K-Means algorithm is commonly used to conduct clustering task since it can quickly cluster data. However, K-Means algorithm has many drawbacks when used to real world cluster problem.
This research combines the concept of traditional clustering algorithm and the technique of ant colony optimization to develop a clustering algorithm that can obtain the global optimization solution. The approach improves the drawback in which K-Means algorithm is easily fall into an awkward situation of the local optimization solution. To demonstrate the benefits of our method, this research experiments several sample data sets. These experiments show that the proposed cluster algorithm can improve the drawback of K-Means algorithm and obtain better cluster objective value and accurate rate. Furthermore, we use product specifications data and production defect data from a practical PCB manufacturer to forecast the defects for a new product. This can prevent and reduce the produce cost and raise the quality of the new product during production.

第一章 緒論 1
1.1 研究背景與動機 1
1.2 問題描述 3
1.3 研究目的 5
1.4 論文架構 5
第二章 文獻探討 7
2.1 資料探勘 7
2.1.1 資料探勘的意義 7
2.1.2 資料探勘的功能 8
2.2 群集分析 10
2.2.1 群集分析概述 10
2.2.2 資料群集演算法 13
2.2.3 K-Means演算法 17
2.3 啟發式方法-螞蟻演算法 20
2.3.1 螞蟻演算法簡介 20
2.3.2 結合群集分析與螞蟻演算法之研究探討 27
第三章 研究方法 32
3.1 研究流程架構 32
3.2 螞蟻群集演算法（ACOCA） 33
3.2.1 初始設定 36
3.2.2 蟻群建構解 39
3.2.3 建構解過程之抽樣策略 46
3.3 分群效度指標（The Validity Index of Clusters）46
第四章 演算法實作與結果討論 49
4.1 演算法實作與操作說明 49
4.1.1 演算法介面操作說明 50
4.2 參數設定與敏感度分析 54
4.2.1 蟻群大小與演算法循環次數分析 55
4.2.2 機率函數之選擇基準分析 57
4.2.3 控制費洛蒙與距離倒數相對重要性之參數分析 59
4.2.4 初始費洛蒙、費洛蒙濃度增加值與費洛蒙殘留係數分析 61
4.2.5 參數分析小結 63
4.3 研究目的之驗證 64
4.3.1 驗證方式說明 65
4.3.2 資料群集驗證結果與數據分析 66
4.3.2.1 IRIS群集驗證 66
4.3.2.2 SD1群集驗證 69
4.3.2.3 SD2群集驗證 71
4.3.2.4 SD3群集驗證 74
4.3.3 研究目的驗證小結 78
第五章 應用案例 80
5.1 應用案例之背景 80
5.2 案例資料說明 82
5.3 案例群集分析 84
5.3.1 新產品設計規格 84
5.3.2 現有產品設計規格資料之分群 85
5.3.3 品質缺陷資訊分析 87
第六章 結論與未來研究 92
6.1 結論 92
6.2 未來研究 94
參考文獻 96

1.吳旭志、賴淑貞譯，「資料採礦理論與實務」，維科圖書有限公司，2001年。
2.邱創政，「以消費表現為基礎之顧客群集分析」，碩士論文，元智大學工業工程與管理研究所，民國92年6月。
3.周仕雄，「應用螞蟻系統於資料挖礦之集群分析」，碩士論文，國立台北科技大學生產系統工程與管理研究所，民國91年6月。
4.黃志雄，「應用資料採礦分析線上拍賣市場之模式」，碩士論文，朝陽科技大學工業工程與管理所，民國91年6月。
5.陳麗君，「應用資料探勘技術於信用卡黃金級客戶之顧客關係管理」，碩士論文，元智大學工業工程與管理研究所，民國92年6月。
6.蘇育霆，「整合模糊理論與自適應共振理論II神經網路於資料採礦之集群技術」，碩士論文，國立台北科技大學生產系統工程與管理研究所，民國90年6月。
7.Ankerst M., M. M. Breunig, H-P. Kriegel and J. Sander, “OPTICS: Ordering Points to Identify the Clustering Structure,” SIGMOD, 1999.
8.Agrawal R., J. Gehrke, D. Gunopulos and P. Raghavan, “Automatic Subspace Clustering of High Dimensional Data for Data Mining Applications,” SIGMOD, 1998, pp.94-105.
9.Berry M.J.A. and G. Linoff, Data Mining Technique for Marketing, Sale, and Customer Support, Wiley Computer, 1997.
10.Cabena P., P. O. Hadjinaian, D. R. J. Stadler, J. Verhees and A. Zanasi, Discovering Data Mining from Concept to Implementation, Prentice Hall, 1997.
11.Chinrungrueng C. and C. H. Sequin, “Optimal Adaptive K-Means Algorithm with Dynamic Adjustment of Learning Rate,” IEEE Transactions on Neural Networks, Vol. 6, No. 1, 1995, pp.157-169.
12.Dorigo M., V. Maniezzo and A. Colorni, “The Ant System: Optimization by a Colony of Cooperating Agents,” IEEE Transactions on Systems, Man, and Cybernetics-Part B, Vol. 26, No. 1, 1996, pp.29-41.
13.Di Caro, G. and M. Dorigo, “AntNet: Distributed Stigmergetic Control for Communications Networks”, Journal of Artificial Intelligence Research 9, 1998, pp.317-365.
14.Duda R. O. and P. E. Hart, Pattern Classification and Scene Analysis, John Wiley & Sons, NY, USA, 1973.
15.Ester M., H. Kriegel, J. Sander and X. Xu, “A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise,” Proc. of the 2nd Int''l Conf. on Knowledge Discovery in Databases, Menlo Park, CA., 1996, pp.226-231.
16.Fayyad U., G. Piatetsky and P. Smyth, “From Data Mining to Knowledge Discovery in Databases,” AI Magazine, 1996, pp.37-54.
17.Freisleben B. and P. Merz, “A Genetic Local Search Algorithm for Solving Symmetric and Asymmetric Traveling Salesman Problems,” Proc. of the IEEE International Conference on Evolutionary Computation, 1996, pp.616-621.
18.Gambardella L.M., E. D. Taillard and G. Agazzi, “MACS-VRPTW: a Multipleant Colony System for Vehicle Routing Problems with Time Windows,” D. Corne, M. Dorigo, F. Glover (Eds.), New Ideas in Optimization, McGraw-Hill, London, 1999, pp.63-76.
19.Gambardella L.M. and M. Dorigo, “HAS-SOP: Hybrid Ant System for the Sequential Ordering Problem,” Technical Report IDSIA, IDSIA, Lugano, Switzerland, 1997, pp.11-97.
20.Grupe G. H. and M. M. Owrang, “Database Mining Discovering New Knowledge and Cooperative Advantage,” Information Systems Management, Vol. 12, No. 4, 1995, pp.26-31.
21.Guha S., R. Rastogi and K. Shim, “CURE: An Efficient Clustering Algorithm for Large Databases,” Proc. of the ACM SIGMOD Int''l Conf. on Management of Data, Seattle, WA., 1998, pp.73-84.
22.Han J. and M. Kamber, Data Mining : Concepts and Techniques, Morgan Kaufmann Publisher, San Francisco, 2001.
23.Hinneburg A. and D. A. Keim, “An Efficient Approach to Clustering in Multimedia Databases with Noise,” Proc. 4th Int’l Conf. on Knowledge Discovery and Data Mining, New York, AAAI Press, 1998.
24.Hall L. O., I. B. Ozyurt and J. C. Bezdek, “Clustering with a Genetically Optimized Approach,” IEEE Transactions on Evolutionary Computation, Vol. 3, No. 2, 1999, pp.103-112.
25.Huang Z., “Extensions to the k-Means Algorithm for Clustering Large Data Sets with Categorical Values,” Data Mining and Knowledge Discovery 2, 1998, pp.283-304.
26.Jain A. K. and R. C. Dubes, Algorithms for Clustering Data, Advanced reference series. Prentice-Hall, Upper Saddle River, New York, 1998.
27.Kaufman L. and P. J. Rousseeuw, Finding Groups in Data : An Introduction to Cluster Analysis, Wiley, New York, 1990.
28.Krishna K. and M. N. Murty, “Genetic K-Means Algorithm,” IEEE Transactions on Systems, Man, and Cybernetics-Part B, Vol. 29, No. 3, 1999, pp.433-439.
29.Kanungo T., D. M. Mount, N. S. Netanyahu, C. D. Piatko, R. Silverman and A. Y. Wu, “An Efficient K-Means Clustering Algorithm : Analysis and Implementation,” IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 24, No. 7, 2002, pp.881-892.
30.MacQueen J., “Some Methods for Classification and Analysis of Multivariate Observations,” Proc. 5th Berkeley Symposium on Mathematical Statistics and Probability, 1967, pp. 281-297.
31.Maniezzo V., “Exact and Approximate Nondeterministic Tree-Search Procedures for the Quadratic Assignment Problem,” INFORMS Journal on Computing, 1999, pp.358-369.
32.Michel R. and M. Middendorf, “An Island Based Ant System with Lookahead for the Shortest Common Supersequence Problem,” Proc. of the Fifth International Conference on Parallel Problem Solving from Nature, Lecture Notes in Computer Science, Vol. 1498, 1998, pp.692-708.
33.McMullen P. R., “An Ant Colony Optimization Approach to Addressing a JIT Sequencing Problem with Multiple Objectives,” Artificial Intelligence in Engineering, Vol. 15, 2001, pp.309-317.
34.Rosenkrantz D. J., R. E. Stearns and P. M. Lewis, “An Analysis of Several Heuristics for the Traveling Salesman Problem,” SIAM J. Comput., Vol. 6, 1977, pp. 563-581.
35.Sarafis I., A. M. S. Zalzala and P. W. Trinder, “A Genetic Rule-Based Data Clustering Toolkit,” Proc. of the 2002 Congress on Evolutionary Computation CEC2002, pp.1238-1243.
36.Sheikholeslami G., S. Chatterjee and A. Zhang, “WaveCluster: A Multi-Resolution Clustering Approach for Very Large Spatial Databases,” VLDB''98, Proc. of 24th International Conference on Very Large Data Bases, New York, USA, 1998, pp.428-439.
37.Shaw M. J., C. Subramaniam and G. W. Tan, “Knowledge management and data mining for marketing,” Decision Support Systems, 31, 2001, pp.127-137.
38.Su M. C. and H. T. Chang, “Fast Self-Organizing Feature Map Algorithm,” IEEE Transactions on Neural Networks, Vol. 11, No. 3, 2000, pp.721-731.
39.Stutzle T. and H. H. Hoos, “The MAX — MIN Ant System and Local Search for the Traveling Salesman Problem,” Proc. of the IEEE International Conference on Evolutionary Computation, 1997, pp.309-314.
40.Stutzle T. and M. Dorigo, “ACO Algorithms for the Quadratic Assignment Problem,” D. Corne, M. Dorigo, F. Glover (Eds.), New Ideas in Optimization, Mc-Graw Hill, 1999, pp.33-50.
41.Tsai C. F., H. C. Wu and C. W. Tsai, “A New Data Clustering Approach for Data Mining in Large Databases,” Proc. of the International Symposium on Parallel Architectures, Algorithms and Networks, 2002.
42.Tsai C. F., Z. C. Chen and C. W. Tsai, “MSGKA : An Efficient Clustering Algorithm for Large Databases,” Systems, Man and Cybernetics, 2002 IEEE International Conference on , Vol.5 , pp.6-9.
43.Vesanto J. and E. Alhoniemi, “Clustering of the Self-Organizing Map,” IEEE Transactions on Neural Networks, Vol. 11, No. 3, 2000, pp.586-600.
44.Wang W., J. Yang and R. Munts, “STING: A Statistical Information Grid Approach to Spatial Data Mining,” Proc. of the 23rd conf. on Very Large Data Bases, Athens, Greece, 1997, pp.186-195.
45.Wang X. R. and T. J. Wu, “Ant Colony Optimization for Intelligent Scheduling,” Proc. of the 4th World Congress on Intelligent Control and Automation, 2002, pp.66-70.
46.Yang X. B., J. G. Sun and D. Huang, “A New Clustering Method Based on Ant Colony Algorithm,” Proc. of the 4th World Congress on Intelligent Control and Automation, Vol. 3, 2002, pp.2222 -2226.
47.Zhang T., R. Ramakrishnan and M. Livny, “BIRCH: An Efficient Data Clustering Method for Very Large Databases,” Proc. of the ACM SIGMOD Int''l Conf. on Management of Data, Montreal, Canada, 1996, pp.103-114.
48.Zhang R. and A. I. Rudnicky, “A Large Scale Clustering Scheme for Kernel K-Means,” Pattern Recognition, 2002. Proc. 16th International Conference on, Vol. 4, 2002, pp.289-292.