臺灣博碩士論文加值系統

群居的昆蟲（或動物）提供了我們一個有效的概念，來建立可彼此互動的分散式代理人系統。研究這些昆蟲（或動物）的群體行為，提供了我們一個有效的方法來解決許多困難的問題，例如最佳化等。愈來愈多的研究者，對於完成所謂的“群體智慧”（由一群簡單的代理人集體突現出的智慧）感到越來越濃的興趣。目前，已有許多研究者設計出各種的電腦模擬，來解釋鳥群、魚群或蟻群等生物間的移動模式。
本篇論文的研究動機來自於鳥類的覓食行為模式，我們把資料當作食物，藉由不斷的拋置於地上給成群的鳥群覓食，此鳥群會隨之調整他們的彼此位置來獲得奪取食物的機會，每隻鳥會在搜尋食物的過程中，從其他的鳥獲得食物來源的資訊，因為每隻鳥都會受到對該食物具有最佳反應的鳥所影響，而企圖朝向它來搜尋食物。漸漸地，鳥類會被分成幾個不同的群聚，而這些形成的群聚則會反應出資料的潛藏結構特性。
然而，大多數的實際資料是屬於高維度的資料型態；要如何分析高維的資料特性是個相當迫切的挑戰。自我組織映射圖（SOM）擁有可透過自我組織的過程，將高維的資料映射到低維度的空間上的特性。所以，我們整合了自我組織映射圖以及上述的群體智慧的概念，提出了一個新的視覺化方法“以群體智慧為基礎的自我組織特徵映射圖”演算法。此演算法允許我們利用人類擅長於二維平面上的分群能力來判斷群聚的數目；此外，我們並可依據所決定的群聚數目，將資料予以分群處理。最後，我們以九個不同特性的資料集合來測試所提出方法之有效性。

Social insects (or animals) provide us with a powerful concept to create decentralized systems of simple interacting, and often mobile, agents (e.g. ants, birds, etc.) The study of their behaviors provides us with effective tools for solving many difficult problems such as optimization, etc. More and more researchers are interested in this exciting way of achieving a form of swarm intelligence (i.e. the emergent collective intelligence of groups of simple agents.) They have created computer simulations of various interpretations of the movement of organisms in a bird flock, fish school, or ant colonies.
In this paper, a new data visualization method, which was inspired by real birds behaviors, is proposed. In this method, each data pattern in the data set to be clustered is regarded as a piece of food and these data patterns will be sequentially tossed to a flock of birds on the ground. The flock of birds adjusts its physical movements to seek food. Individual members of the flock can profit from discoveries of all of other members of the flock during the search for food because an individual is influenced by the success of the best neighbor and tries to imitate the behavior of the best neighbor. Gradually, the flock of birds will be divided into several groups according to the distributions of the food. The formed groups will naturally correspond to the underlying data structures in the data set.
However many practical data sets are consisted of high-dimensional data points; therefore, how to generalize the aforementioned idea to cluster high-dimensional data sets is a very demanding challenge. Since the Self-Organizing Map (SOM) algorithm can project high-dimensional data points into a low-dimensional space through a self-organizing procedure we decide to integrate the SOM algorithm with the foregoing swarm intelligence to propose a new data visualization algorithm d. We then name the new data visualization algorithm as the Swarm Intelligence-based SOM (SISOM) algorithm. The algorithm allows us to use our visualization to decide the numbers of clusters and then cluster the data set based on the estimated cluster number. Nine data sets are used to demonstrate the effectiveness of the proposed algorithm.

摘要 I
Abstract III
誌謝 V
目錄 VI
表目錄 VIII
圖目錄 X
第一章 緒論 1
1.1 群聚分析 1
1.2 自我組織映射圖 4
1.3 群體智慧 5
1.4 研究動機 6
1.5 論文架構 8
第二章 群聚分析文獻回顧 9
2.1 傳統群聚演算法 9
2.1.1 K-means 和 模糊K-means 9
2.1.2 適應共振理論（ART） 12
2.1.3 最大最小演算法（Maximin Algorithm） 14
2.1.4 傳統群聚演算法之比較 17
2.2 自我組織特徵映射圖 18
2.3 基於SOM的視覺化群聚演算法 23
2.3.1 The Kohonen Topology Preserving Mapping 25
2.3.2 Double SOM 27
2.3.3 Visualization-induced SOM 30
2.4 其他視覺化群聚演算法 34
2.4.1 主成分分析 35
2.4.2 賽門非線性投影 35
2.4.3 Lumer Faieta演算法 37
第三章 研究方法與步驟 42
3.1 蟻群最佳化 43
3.2 粒子群體最佳化 45
3.3 代表點初始化 47
3.4 訓練階段 54
3.5 分類階段 57
第四章 模擬結果與比較 60
4.1 二維資料集1之測試與比較 60
4.2 二維資料集2測試之測試與比較 65
4.3 三維資料集測試與比較 69
4.4 十維資料集測試與比較 72
4.5 染色體資料集測試與比較 77
4.6 工業元件資料集測試與比較 81
4.7 鳶尾花資料集測試與比較 85
4.8 衛星資料集測試與比較 89
4.9 三維腦波資料集測試與比較 95
第五章 結論與展望 97
5.1 結論 97
5.2 未來研究方向 98
參考文獻 99

[1]J. Bezdek, Pattern Recognition with Fuzzy Objective Function Algorithms, New York: Plenum, 1981.
[2]E. Bonabeau, M. Dorigo, and G. Theraulaz, “Inspiration for optimization form social insect behaviour,” Nature, vol. 406, 6 July 2000.
[3]E. Bonabeau, M. Dorigo and G. Theraulaz, Swarm Intelligence: From Natural to Artificial Systems, Oxford University Press, New York. 1999.
[4]P. Cheeseman and J. Stutz, “Bayesian classification (autoclass): theory and results,” in Proceedings of Advances in Knowledge Discovery and Data Mining, 1996.
[5]G. A. Carpenter and S. Grossberg, “A massively parallel architecture for a self-organizing neural pattern recognition machine,” Computer Vision, Graphics, and Image Proc, vol. 37, pp. 54-115, 1987.
[6]G. A. Carpenter and S. Grossberg, “ART2: self-organizing of stable category recognition codes for analog input pattern,” Appl. Optics, vol. 26, no. 23, pp. 4919-4930, Dec. 1987.
[7]G. A. Carpenter, S. Grossberg, and D. B. Rosen, “Fuzzy ART: Fast Stable Learning and Categorization of Analog Patterns by an Adaptive Resonance System,” Neural Networks, vol. 4, pp. 759-771, 1991.
[8]G. A. Carpenter, S. Grossberg, and J. H. Reynolds, “ARPMAP: supervised real-time learning and classification of nonstationary Data by a self-organizing neural networks,” Neural Networks, vol. 4, pp. 565-558, 1991.
[9]A. Colorni, M. Dorigo, and V. Maniezzo, “An investigation of some properties of an ant algorithm,” Proceedings of the Parallel Problem Solving From Nature, vol. 2, pp.509-520, 1992.
[10]R. O. Duda and P. E. Hart, Pattern Classification and Scene Analysis, New York: Wiley, 1973.
[11]D. L. Davies and D. W. Bouldin, “A cluster separation measure,” IEEE Trans. on Pattern Anal. Machine Intell, vol. PAMI-1, pp. 224-227, 1979.
[12]D. L. Davies and D. W. Bouldin, “A cluster separation measure,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 1, no. 4, pp. 224-227, 1979.
[13]M. Dorigo, E. Bonabeau, and G. Theralulaz, “Ant algorithm and stigmergy,” Future Generation Computer Systems, vol-16, pp. 851-871, 2000.
[14]J. L. Denebourg, S. Goss, N. Frankes, A. SendovaFranks, C. Detrain and L. Chretien, “The dynamic of collective sorting robot-like ants and ant-like robots,” in J. A. Meyer and S. W. Wilson (Eds.), Procs. of SAB’90 – 1st Conf. on Simulation of Adaptive Behavior：Form Animal to Animates, Cambridge, MA：MIT Press, pp.356-365, 1991.
[15]J. Han and M. Kamber, Data mining: Concepts and Techniques, Morgan Kaufmann, 2000.
[16]F. Heppner and U. Grenander, “A stochastic nonlinear model for coordinated bird flocks,” in S. Krasner, Ed., The Ubiquity of Chaos. AAAS Publications, Washington, DC, 1990.
[17]A. K. Jain and R. C. Dubes, Algorithm for Clustering Data, Prentic Hall, New Jersey, 1988.
[18]T. Kohonen, S. Kaski, K. Lagus, and T. Honkela, “Very large two-level SOM for the browsing of newsgroups,” in Proceedings of ICANN96, International Conference on Artificial Neural Networks, 1996.
[19]T. Kohonen, “Self-organized formation of topologically correct feature maps,” Biological Cybernetics, vol. 43, pp. 59-69, 1982.
[20]B. Kleiner, and J. A. Hartigan. “Representing points in many dimensions by trees and castles.” Journal of the American Statistical Association, vol. 76, pp. 260-269, 1981.
[21]M. A. Kraaijveld, J. Mao, and A. K. Jain, “A nonlinear projection method based on Kohonen’s topology preserving maps,” IEEE Trans. on Neural Network, vol. 6, pp. 548-559, 1995.
[22]M. A. Kraaijveld, J. Mao, and A. K. Jain, “A non-linear projection method based on Kohonen’s topology preserving maps,” Proc. 11th Int’l. Conference on Pattern Recognition, The Hague, pp. 41-45, August 1992.M. Dorigo, E. Bonabeau, G. Theralulaz, “Ant algorithm and stigmergy,” Future Generation Computer Systems, vol-16, pp. 851-871, 2000.
[23]E. D. Lumer and B.Faieta, “Diversity and adaptation in population of cluster ants,” in D. Cliff, P. Husbands, J. Meyer, and S. Wilson (Eds.), Procs. of SAB’64-3rd Conf. on Simulation of Adaptive Behavior：Form Animal to Animates, Cambridge, MA：The MIT Press/Bradford Books, 1994.
[24]C. W. Reynolds, “Flocks, herds and schools: a distributed behavioral model”, Computer Graphics, vol. 21, no. 4, pp.25-34, 1987.
[25]M. C. Su and H. T. Chang, “A new model of self-organizing neural networks and its application in data projection,” IEEE Trans. on Neural Networks, vol. 12, no. 1, pp. 153-158, 2000.
[26]J. W. Sammon, “A nonlinear mapping for data structure analysis,” IEEE Trans. on Comput., C-18, pp. 401-409, 1969.
[27]T. Stutzle and H. Hoos, “MAX-MIN ant system,” Future Generation Computer Systems, vol-16, pp. 889-914, 2000.
[28]M. C. Su and H. T. Chang, “Fast self-organizing feature map algorithm,” IEEE Trans. on Neural Networks, vol. 11, no. 3, pp. 721-733, 2000.
[29]J. T. Tou and R. C. Gonzalez, Pattern Recognition Principles, Addison-Wesley, 1974.
[30]A. Ultsch, “Self-organizing neural networks for visualization and classification,” Inform. Classification, pp. 864-869, 1993.
[31]H. Yin, “ViSOM-a novel method for multivariate data projection and structure visualization,” IEEE Trans. on Neural Networks, vol. 13, no. 1, pp. 237-243, 2002.
[32]H. Yin, “Data visualization and manifold mapping using the ViSOM,” Neural Networks, vol. 15, no. 8-9, pp. 1005-1016, 2002.
[33]I. K. Yu, C. S. Chou, and Y. H. Song, “Application of the ant colony search algorithm m to short-term generation scheduling problem of thermal units,” International Conference on Power System Technology, vol. 1, pp.552-556, 1998.