A Wrap-arounded Self-Organizing Map Associated with a 2-Mean Method Based Automation Classification Mechanism

本研究開發超環面拓樸結構的自組織映射網路的物件分群技術，且提示一自動分析物件間鄰近程度且切斷網路拓樸的鏈結關係以產生子群的自動分群機制。該自動劃分群集演算法以拓樸映射和自動劃分群集兩階段的演算求解求解物件有屬性且無物件間互斥限制及群落的物件分群問題。第一階段的拓樸結構有：平面拓樸結構及超環面拓樸結構。第二階段的求算節線斷開門檻值演算法有：平面拓樸結構為基求算節線斷開門檻值演算法及超環面拓樸結構為基求算節線斷開門檻值演算法。上述兩種演算法各包含三種求算節線斷開門檻值演算法，分別是：網圖為基節線斷開演算法、最小間距樹為基節線斷開演算法、及完全網圖為基節線斷開演算法。並以三維空間中兩個彼此不相交環的範例資料進行自動劃分群集演算法演算。分析演算求解的分群結果推知，以超環面拓樸結構的自組織映射網路結合2–Mean方法為基的自動劃分群集演算法進行求解的分群結果是正確的，且具有自動決定節線斷開門檻值及不需事先設定群數的優點。因此，以本研究提示的自動劃分群集演算法可自動展示分群結果。This thesis presents a wrap-around Self-Organizing Map associated with an automatic classification mechanism for data clustering. The proposed data clustering method consists of two procedures. At first data are mapped onto topologically structured neural neurons, represented as either a traditional SOM or the proposed wrap-around SOM. Then, in the second stage, the topology of the structured neural neurons and associated characteristic vectors are used by an automation classification algorithm to divide the linked neurons into sub-graphs. These sub-graphs are then the results of data clustering. The classification algorithm uses 2-mean techniques to automatically find the threshold for link cutting between connected neurons. Three topology models are investigated and studied, including the original 2-D topology, a reduced spanning tree for the original topology, and a regenerated complete graph from all neurons. Several numerical examples are tested, including an example with data distributed as chained two rings. Results show that only the proposed wrap-around SOM associated with the 2-mean method based classification mechanism can produce a correct data clustering result. The main advantages of using the proposed method are that the number of groups of the clustered data is automatically determined and only wrap-around topology can deal with problems of mutual inclusive data distribution.目錄 第1章 緒論 1 1.1 研究背景 1 1.2 問題描述與研究動機 2 1.3 研究目的 3 1.4 研究範疇與架構 4 1.5 章節概要 5 第2章 文獻探討 6 2.1 物件分群問題 6 2.2 自組織映射網路 10 2.3 自組織映射網路的視覺化技術劃分群集演算法 18 2.4 2−Mean演算法 22 2.5 圖論和Prim演算法 24 2.6 文獻探討結語 25 第3章 超環面拓樸結構的自組織映射網路 26 3.1 自動劃分群集演算法求解架構 26 3.2 平面拓樸結構的自組織映射網路結合2–Mean方法為基的自動劃分群集演算法 29 3.2.1 自組織映射網路演算法 29 3.2.2 平面拓樸結構為基求算節線斷開門檻值演算法 43 3.3 超環面拓樸結構的自組織映射網路結合2–Mean方法為基的自動劃分群集演算法 68 3.3.1 超環面拓樸結構的自組織映射網路演算法 69 3.3.2 超環面拓樸結構為基求算節線斷開門檻值演算法 83 3.4 等高線視覺化劃分群集演算法和自動劃分群集演算法間優劣異同 107 3.5 小結 109 第4章 實例驗證及結果討論 110 4.1 實驗範例與討論 110 4.1.1 範例二：三維空間中三個常態分佈的資料集 110 4.1.2 範例三：三維空間中兩個彼此不相交的環 127 4.1.3 範例四：二維空間中六個彼此不相交的資料集 144 4.2 實驗結果分析 161 4.3 小結 167 第5章 結論與未來研究建議 168 5.1 結論 168 5.2 未來研究建議 16