臺灣博碩士論文加值系統

隨著科技日新月異，新的群集分析方法不斷地被提出，但大多分群方法需先設定分群之群數，因此本研究主要提出一自動分群之方法－Dynamic Clustering using Particle Swarm Optimization and Genetic Algorithm (DCPG)演算法，不需事先決定欲分群的數目，可藉由資料的特性自行群聚成適合的群集。
本研究先分別採用四組基準資料集Iris、Wine、Glass以及Vowel來進行實驗，
並與Dynamic Clustering using Particle Swarm Optimization (DCPSO) 和Dynamic Clustering using Genetic Algorithm (DCGA)進行比較，以驗證該方法之準確性及有效性。驗證得知，本研究所提DCPG此一動態分群的方法在分群結果上表現較為穩定且優異。最後再將此方法應用於研華科技新店單板廠所有機種與用料之Bill of Material (BOM)表中，利用DCPG自動分群法找出群數後，接著第二階段以林如梅(2008)所提出之Hybrid Particle Swarm Optimization (Hybrid PSO)找出最佳的分群結果。經過兩階段的群集分析後，找出相同群集的機種及其共用料，再透過產品族的概念將相同群集的機種安排一起生產，以其縮短SMT換線作業時間，以因應工業電腦產業多量少樣的生產模式。

With the advancement of technology, the methods of clustering analysis are continually proposed. Even though, most of the clustering methods still need to set the number of cluters. This study intends to propose a novel dynamic clustering technique - Dynamic Clustering using Particle Swarm Optimization and Genetic Algorithm (DCPG), which does not need to set the number of cluters in advance. By the features of data, the method could auomatically cluster together into a suitable cluster number.
This study employees four benchmark datasets, Iris, Wine, Glass and Vowel, to evaluate the accuracy and validity by comparing DCPG and other two methods, Dynamic Clustering using Particle Swarm Optimization (DCPSO) and Dynamic Clustering using Genetic Algorithm (DCGA). The experimental results indicate that DCPG outperforms other three methods in validity and stability. Finally, we apply a two-stage method, which includes DCPG to determine the number of cluters, and Hybrid Particle Swarm Optimization (Hybrid PSO) to find the final solution. This method is applied to cluster the Bill of Material (BOM) for Advantech Company. The clustering results can be used to categorize products into clusters which share the same materials. Moreover, through the concept of product family, machines in the same cluster are arranged to be manufactured together to reduce SMT setup time in response to the high-mix and low-volumn production pattern of industrial personal computers.

摘要 I
ABSTRACT II
誌謝 III
目錄 IV
表目錄 VI
圖目錄 VII
第一章 緒論 1
1.1 研究背景與動機 1
1.2 研究目的 2
1.3 研究範圍 2
1.4 研究流程 2
第二章 文獻探討 4
2.1 分群 4
2.1.1 分群的定義與應用 4
2.1.2 分群的程序 4
2.1.3 分群的方法 5
2.1.4 自動分群的方法 11
2.2 粒子群最佳化演算法 14
2.2.1 粒子群最佳化演算法發展背景 14
2.2.2 粒子群最佳化演算法之原理 15
2.2.3 粒子群最佳化演算法在分群的應用 19
2.2.4 粒子群最佳化演算法與遺傳演算法之結合 21
2.3 Dynamic Clustering using PSO (DCPSO) 23
2.3.1 DCPSO簡介 23
2.3.2 DCPSO演算流程 25
第三章 研究方法 26
3.1 研究架構 27
3.2 DCPG介紹 27
3.2.1 DCPG之架構 27
3.2.2 DCPG之演算流程 29
3.3 效能驗證 30
第四章 實驗分析 31
4.1 資料集介紹 31
4.2 資料前處理 33
4.3 實驗結果與分析 34
4.3.1 演算法評估準則 35
4.3.2 演算法結果分析 36
4.3.3 演算法收斂情形 39
4.4 演算法參數設定 42
第五章 實證分析 46
5.1 案例簡介 46
5.1.1 工業電腦的定義及特性 46
5.1.2 表面黏著技術 47
5.2實證分析流程 48
5.3 實證資料來源及前處理 50
5.4實證結果與分析 51
5.4.1 方法評估 51
5.4.2 實證結果 52
5.4.3 實證分析 54
5.5 換線效益評估 55
5.6 結語 60
第六章 結論與建議 62
6.1 研究結論 62
6.2 研究貢獻 63
6.3 未來研究方向 63
參考文獻 64
附錄A 實驗結果 72
附錄B DCGA之演算步驟 84
附錄C 實驗設計結果 85
附錄D 主成份分析結果 86
附錄E 研華科技三方法之數據 89

[1]王志峯，整合增長式自組織映射圖與遺傳演算法之發展與應用，台北科技大學工業工程與管理研究所，碩士論文，台北，2008。
[2]林芳君，應用粒子群最佳化於群集分析以縮短SMT換線時間－以研華科技為例，台北科技大學工業工程與管理研究所，碩士論文，台北，2007。
[3]林如梅，整合遺傳演算法和粒子群最佳化演算法於分群分析之研究，台北科技大學工業工程與管理研究所，碩士論文，台北，2008。
[4]黃庭瑋，應用群集分析方法縮短SMT換線時間－以研華科技為例，台北科技大學工業工程與管理研究所，碩士論文，台北，2006。
[5]黃振倫，印刷電路板小元件裝配排程問題之研究─以Fuji CP機器為例，元智大學，工業工程與管理學系，碩士論文，桃園，2002。
[6]曾憲雄，蔡秀滿，蘇東興，曾秋蓉，王慶堯，資料探勘，台北：旗標出版股份有限公司，2005，第六章。
[7]葉俊吾，運用類神經網路建構SMT錫膏印刷製程品質管制系統，成功大學製造工程研究所，碩士論文，台南，2003。
[8]韓永祥，整合遺傳演算法與粒子群最佳化演算法於二階線性規劃問題之應用-以供應鍊之配銷模型為例，台北科技大學工業工程與管理研究所，碩士論文，台北，2008。
[9]魏建發，景氣復甦的工業電腦，元大京華，2003。
[10]蘇育霆，整合模糊理論與自適應共振理論Ⅱ神經網路於資料採礦之集群技術研究，台北科技大學生產系統工程與管理研究所大學製造工程研究所，碩士論文，台北，2002。
[11]鍾文杰，整合自組織映射圖網路與遺傳演算法為輔之K-means於顧客關係管理中，台北科技大學生產系統工程與管理研究所大學製造工程研究所，碩士論文，台北，2001。
[12]Alahakoon, D., Halgamuge, S.K. and Srinivasan, B., “Dynamic self-organizing maps with controlled growth for knowledge discovery,” IEEE Transaction on Neural Networks, vol. 11, no. 3, 2000, pp. 601-614.
[13]Al-Sultan K., “A Tabu search approach to the clustering problem,” Pattern Recognition, vol. 28, no. 9, 1995, pp. 1443-1451.
[14]Ankerst, M., Breunig, M., Kriegel, H. and Sander, J., “OPTICS: Ordering Points to Identify the Clustering Structure,” Proceedins ACM SIGMOD’99 International Conference. on Management of Data.1999.
[15]Arumugam, M.S. and Rao, M.V.C., “On the improved performances of the partical swarm optimization algorithms with adaptive parameters, cross-over operators and root mean square(RMS) vataiants for computing optimal control of a class of hybrid systems,” Applied Soft Computing, vol. 8, no. 1, 2008, pp. 324-336.
[16]Ball, G. and Hall, D., “A clustering technique for summarizing multivariate data,” Behav. Sci., vol. 12, 1967, pp. 153-155.
[17]Barbara, D. and Chen, P., “Using the fractal dimension to cluster datasets,” Proceedings 6th ACM SIGKDD International Conference Knowledge Discovery and Data Mining, 2000, pp. 260-264.
[18]Bauer, H.U. and Villmann, T., “Growing a hypercubical output space in a self-organizing feature map,” IEEE Transaction on Neural Networks, vol. 8, no. 2, 1997, pp. 218-226.
[19]Bergh, F.V.D. and Engelbrecht, A.P., “A new locally convergent particle swarm optimiser,” Proceedings of IEEE International Conference on Systems, Man and Cybernetics, vol. 3, 2002, pp. 96-101.
[20]Bezdek, J. and Hathaway, R., “Numerical convergence and interpretation of the fuzzy c-shells clustering algorithms,” IEEE Transactions on Neural Network, vol. 3, no. 5, 1992, pp. 787-793.
[21]Blackmore, J. and Miikkulainen, R., “Incremental grid growing: Encoding high-dimensional structure into a two-dimensional feature map,” Technique Report: AI92-192. Austin, TX: The University of Texas at Austin, 1992.
[22]Carpenter, G. and Grossberg, S., “A massively parallel architecture for a self-organizing neural pattern recognition machine,” Comput. Vis. Graph. Image Process, vol. 37, 1987, pp. 54-115.
[23]Carpenter, G. and Grossberg, S., “ART2: Self-organization of stable category recognition codes for analog input patterns,” Appl. Opt., vol. 26, no. 23, 1987, pp. 4919-4930.

[24]Carpenter, G., Grossberg, S., and Reynolds, J., “ARTMAP: a self-organizing neural network architecture for fast supervised learning and pattern recognition,” Neural Networks, vol. 1, 1991, pp. 863-868.
[25]Carpenter, G., Grossberg, S. and Rosen, D., “Fuzzy ART: Fast stable learning and categorization of analog patterns by an adaptive resonance system,” Neural Networks, vol. 4, 1991, pp. 759-771.
[26]Clerc M., “The swarm and the queen: towards a deterministic and adaptive particle swarm optimization,” Evolutionary Computation, 1999.
[27]Chen, C.Y. and Ye, F., “Particle swarm optimization algorithm and its application to clustering analysis,” 2004 IEEE International Conference on Networking, 2004, pp. 789-794.
[28]Cohen, S.C.M. and Castro, L.N.D., “Data clustering with particle swarms,” IEEE Congress on Evolutionary Computations, 2006, pp. 1792-1798.
[29]Cui, X., Potok, T.E. and Palathingal, P., “Document clustering using particle swarm optimization,” Swarm Intelligence Symposium, SIS 2005. Proceedings IEEE , 2005.
[30]Das, S., Abraham, A., and Konar, A., “Automatic kernel clustering with a multi-elitist particle swarm optimization algorithm,” Pattern Recognition Letters, vol. 29, no.5, 2008, pp. 688-699.
[31]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, 1996, pp. 1-13,.
[32]Du, S., Li, W. and Cao, K., “A Learning Algorithm of Artificial Neural Network Based on GA - PSO,” Proceedings of the 6th World Congress on Intelligent Control and Automation, Dalian, China, 2006.
[33]Eberhart, R. and Kennedy, J., “A new optimizer using particle swarm theory,” Proceedings qf the 6th International Symposium on Micro Machine and Human Science, 1995, pp. 39-43.
[34]Eberhart, R. and Shi, Y., “Tracking and optimizing dynamic systems with particle swarms,” IEEE International Conference on Neural Networks, 2001, pp. 1942-1948.
[35]Eberhart, R. and Shi, Y., “Particle swarm optimization: developments, applications and resources,” Proceedings of the 2001 Congress on Evolutionary Computation, 2001, pp. 81-86.
[36]Estivill-Castro, V. and Lee, I., “AMOEBA: hierarchical clustering based on spatial proximity using delaunay diagram,” Proceedings 9th International Spatial Data Handling (SDH2000) , 2000a, pp. 10-12.
[37]Estivill-Castro, V. and Lee, I., “AUTOCLUST: Automatic clustering via boundary extraction for massive point data sets,” Proceedings 5th International Conference Geo-Computation, 2000b, pp. 23-25.
[38]Ester M., Kriegel H., Sander J. and Xu X., “A density-based algorithm for discovering clusters in large spatial databases with noise,” Proceedings 2th International Conference Knowledge Discovery and Data Mining (KDD’96), 1996, pp. 226-231.
[39]Forgy, E., “Cluster analysis of multivariate data: efficiency vs. interpretability of classification,” Biometrics, vol. 21, 1965, pp. 768-780.
[40]Fritzke, B., “Growing cell structure: a self-organizing network for unsupervised and supervised learning,” Neural Networks, vol. 7, no, 9, 1990, pp. 1141-1160.
[41]Geva, A.B, “Hierarchical unsupervised fuzzy clustering,” IEEE Transactions on Fuzzy Systems, vol. 7, no. 6, 1999, pp. 723-733.
[42]Grossberg, S., “Adaptive pattern recognition and universal encoding II: Feedback, expectation, olfaction, and illusions,” Biol. Cybern., vol. 23, 1976, pp. 187-202.
[43]Guha, S., Rastogi, R. and Shim, K., “CURE: An efficient clustering algorithm for large databases,” Proceedings ACM SIGMOD Int. Conf. Management of Data, 1998, pp. 73-84.
[44]Guha, S., Rastogi, R. and Shim, K., “ROCK: A robust clustering algorithm for categorical attributes,” Inf. Syst., vol. 25, no. 5, 2000, pp. 345-366.
[45]Holland, J.H., Adaptation in Natural and Artificial Systems. Ann Arbor, MI: Univ. of Michigan Press, 1975.
[46]Jarboui, B., Cheikh, M., Siarry, P. and Rebai, A., “Combinatorial particle swarm optimization (CPSO) for partitional clustering problem,” Applied Mathematics and Computation, vol. 192, no. 2, 2007, pp. 337-345.
[47]Juang, C.F., “A hybrid of genetic algorithm and particle swarm optimization for recurrent network design,” Systems, Man and Cybernetics, Part B, IEEE Transactions, vol. 34, no. 2, 2004, pp. 997-1006.

[48]Juha V. and Esa A., “Clustering of the Self-Organizing Map,” IEEE Transactions on Neural Networks, vol. 11, no. 3, 2000, pp. 586-600.
[49]Hinneburg, A. and Keim, D. "An efficient approach to clustering in large multimedia databases with noise," in Proceeding 4th International Conference Knowledge Discovery and Data Mining (KDD''98), 1998, pp. 58-65.
[50]Huston, s., "Surface mount technology market forecasting," Journal of Industrial Technology, vol. 17, no. 1, 2000, pp. 2-7.
[51]Kao, Y.T. and Zahara, E., “A hybrid genetic algorithm and particle swarm
optimization for multimodal functions,” Applied Soft Computing, 2007.
[52]Karypis, G., Han, E. and Kumar V., “Chameleon: Hierarchical clustering using dynamic modeling,” IEEE Computer, vol. 32, no. 8, 1999, pp. 68-75.
[53]Kaufman, L. and Rousseeuw, P.J., “Finding groups in data: an introduction to cluster analysis.” John Wiley & Sons, 1990.
[54]Kennedy, J. and Eberhart, R., “A discrete binary version of the particle swarm algorithm,” Proceeding of IEEE International Conference on Neural Networks, vol. no. 4, 1997, PP. 4104-4108.
[55]Kohonen, T., “The self-organizing map,” Proceeding of IEEE, vol. 78, no. 9,1990, pp. 1464-1480.
[56]Kotsiantis, S. and Pintelas, P., "Recent advances in clustering: a brief survey,” WSEAS Trans. Information Science & Applications, vol. 1, no. 1, 2004, pp. 73-81.
[57]Krishna, K.and Murty, M.N., “Genetic K-means algorithm,” IEEE Transactions on Systems, vol. 29, no. 3, 1999, pp. 433-439.
[58]Krishnapuram, R. and Keller, J., “A possibilistic approach to clustering,” IEEE Transactions Fuzzy Systems, vol. 1, no. 2, 1993, pp. 98-110.
[59]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, 2000b, pp. 509-513.
[60]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, 2002a, pp. 1475-1493.
[61]Kuo, R.J., Hu, T.L. and Chen, Z.Y., “Application of Radial Basis Function Neural Network for Sales Forecasting,” Informatics in Control, Automation and Robotics, 2009. CAR ''09. , 2009, pp. 325 – 328.
[62]Kuo, R.J., Liao, J.L. and Tu, C., “Integration of ART2 neural network and genetic K-means algorithm for analyzing Web browsing paths in electronic commerce,” Decision Support Systems, vol. 40, no. 2, 2005, pp. 355-374.
[63]Kuo, R.J., Wang, H.S., Hu, T.L. and Chou, S.H. , “Application of ant K-means on clustering analysis” Computers & Mathematics with Applications, vol. 50, 2005, pp. 1709-1724.
[64]Liu, B., Wang, L. and Jin, Y.H., “An effective hybrid PSO-based algorithm for flow shop scheduling with limited buffers,” Computers & Operations Research, 2007.
[65]Lumer, E. and Faieta, B., “Diversity and adaptation in populations of clustering ants,“ Proceedings of the 3th International Conference onSimulation of Adaptive Behavior: From Animals to Animats, vol. 3, 1994, pp. 501–508.
[66]Merwe, D.W.V.D. and Engelbrecht, A.P., “Data clustering using particle swarm optimization,” The 2003 Congress on Evolutionary Computation, 2003, pp. 215-220.
[67]Monmarché, N., Slimane, M. and Venturini, G., “Antclass: discovery of clusters in numeric data by an hybridization of an ant colony with the kmeans algorithm”, 1999.
[68]Omran, M.G.H., Salman A. and Engelbrecht A.P., “Dynamic clustering using particle swarm optimization with application in image segmentation,” Pattern Analysis & Applications, vol. 8, no. 4, 2006, pp. 332-344.
[69]Ratnaweera, A. and Halgamuge, K.S., “Self organizing hierarchical particle swarm optimizer with time-varying acceleration coefficients,” IEEE Transactions on Evolutionary Computation, vol. 8, no. 3, 2004, pp. 240–254.
[70]Ressom, H., Wang, D. and Natarajan P., “Adaptive double self-organizing maps for clustering gene expression profiles,” Neural Networks, vol. 16, 2003, pp. 633-640.
[71]Robinson, J., Sinton, S. and Yahya, R.S., “Particle swarm, genetic algorithm, and their hybrids: Optimization of a profiled corrugated horn antenna,” IEEE Antennas and Propagation Society International Symposium, San Antonio, vol. 1, 2002, pp. 314–317.
[72]Selim, S. and Alsultan, K., “A simulated annealing algorithm for the clustering problems,” Pattern Recognition, vol. 24, no. 10, 1991, pp. 1003-1008.

[73]Sheikholeslami, G., Chatterjee, S., and Zhang, A., “WaveCluster: A multi-resolution clustering approach for very large spatial databases,” Proceedings 1998 International Conference Very Large Databases (VLDB’98), 1998, pp. 428-439.
[74]Shi, Y. and Eberhart, R., “A modified particle swarm optimizer,” Proceedings of the IEEE International Conference on Evolutionary Computation, 1998a, pp. 69-73.
[75]Shi, X.H., Liang, Y.C., Lee, H.P., Lu, C. and Wang, L.M., “An improved GA and a novel PSO-GA-based hybrid algorithm,” Information Processing Letters, vol. 93, no. 5, 2005, pp. 255-261.
[76]Wu, S. and Chow, T.W.S., “PRSOM a new visualization method by hybridizing multidimensional scaling and self-organizing map,” IEEE Transaction on Neural Network, vol. 16, no. 6, 2005, pp. 1362-1380.
[77]Srinoy, S. and Kurutach, W., “Combination artificial ant clustering and K-PSO clustering approach to network security model,” International Conference Hybrid Information Technology, vol. 2, 2006, pp. 128 –134.
[78]Su, M.C. and Chang, H.T., “Fast self-organizing feature map algorithm,” IEEE Transactions on neural networks, vol. 11, no. 3, 2000, pp. 721-733.
[79]Suganthan, P.N., “Particle swarm optimizer with neighbourhood operator,” Proceedings of the Conference on Evolutionary Computation, 1999, pp. 1958-1961.
[80]Tsai, C.F., Tsai, C.W., Wu, H.C. and Yang, T. “ACODF: A Novel Data Clustering Approach for Data Mining in Large Databases,” Journal of Systems and Software, vol. 73, 2004, pp. 133–145.
[81]Turi, R.H., “Clustering-based colour image segmentation,” PhD Thesis, Monash University, Australia, 2001.
[82]Xiao, X., Dow, E.R., Eberhart, R., Miled, Z.B. and Oppelt, R.J., “Gene clustering using self-organizing maps and particle swarm optimization,” Proceedings of the International Parallel and Distributed Processing Symposium, 2003, pp. 22-28.
[83]Xie X.F., Zhang W.J. and Yang Z.L., “A dissipative paticle swarm optimization,” Proceedings of the IEEE Congress on Evolutionary Computing (CEC 2002), 2002, pp. 1666-1670.

[84]Xu, R. and Wunsch, D., “Survey of clustering algorithm,” IEEE Transactions on Neural Networks, vol.16, no. 3, 2005, pp. 645-678.
[85]Yin, H., “ViSOM-A novel method for multivariate data projection and structure visualization,” IEEE Transactions on Neural Networks, vol. 13, no. 1, 2002, pp. 135-144.
[86]Zhang, T., Ramakrishnan, R. amd Livny, M., “BIRCH: An efficient data clustering method for very large databases,” Proceedings ACM SIGMOD Conf. Management of Data, 1996, pp. 103-114.
[87]Zhang, D., Liu, X. and Guan, Z., “A dynamic clustering algorithm based on PSO and Its application in fuzzy identification,” Proceedings of the 2006 International Conference on Intelligent Information Hiding and Multimedia Signal Processing (IIH-MSP''06), 2006, pp. 232 – 235.
[88]Zhao, B., Guo, C.X., Bai, B.R. and Cao, Y.J., “An improved particle swarm optimization algorithm for unit commitment,” International Journal of Electrical Power & Energy Systems, vol. 28, no.7, 2006, pp. 482-490.