Self-organizing map

※此筆記可能會有一些錯誤, 歡迎大家指正:)※
這學期似乎會被學長找去代課, 聽說是要上機器學習(machine learning, ML). 什麼!! 聽到的瞬間身體不自主的抖了兩下(還好沒有漏了幾滴東西…), 剛好最近看到一篇文獻是探討類神經網路(neural network)中的Self-organizing map(SOM)與複雜網路(complex network)之間的關係(究竟SOM跟網路拓樸會擦出什麼火花呢?! 有興趣可以參閱[1]), 為了能夠稍為進入代課的狀況, 就來複習一下SOM並且寫寫筆記[4] :).

I. Introduction
SOM的全名是Self-organizing map又或著是Self-organizing feature map(SOFM), 中文翻譯成"自我組織(特徵映射)圖"網路, 不管名稱為何所說的都是同一個東西. 此方法是由T. Kohonen在1980年代所提出, 因此SOM又被稱為Kohonen network[3][4][5].

(以下為小羊之不負責任解說)

SOM的概念來源為人類大腦網路或生物網路在處理資訊時, 處理相同資訊的神經元會聚集在一起的特性, 簡單來說就是會有一個個區域的樣子. 例如: 給一隻羊看草原的照片並且同時給牠照fMRI, 我們會發現其腦部有一些特定的區域會對草原有反應. 圖1與圖2為fMRI及SOM, 互相對照之下, 可以觀察看看兩者有何相似之處.


(以上為小羊之不負責任解說)

II. Self-organizing map
SOM有一個很重要的優點為, 將N維(N-dimension)的資料映射(mapping)到2維(2-dimension)的空間上(如圖3所示)並且維持資料中的拓撲(topology)特性.將資料映射到2 維空間時則可以使用視覺化(visualization)的方式呈現, 以方便後續的觀察及分析.



舉個例子, 假設我們想要了解全世界各地所有不同品種的羊之間的關係為何, 若總共有5個品種(a.亞洲, b.非洲, c.歐洲, d.美洲及e.大洋洲), 每一個品種都有5個屬性(5維). 對每一個品種收集100 隻羊的資料, 因此資料總數為500 筆. 接下來我們利用SOM 將5維的資料映射到2維的空間上, 以視覺化的方式來呈現這5個品種的羊之間的拓樸關係.

SOM 演算法(參考至[2]及[5]):
1. 初始化(initialization)
2. 輸入資料集(dataset)
3. 從資料集挑選一個pattern 並尋找距離最近的神經元為winner
4. 更新winner 神經元的權重及其鄰近神經元
5. 重複步驟3~4, 且迴圈步數 step=2 至結束

接下來我們定義 SOM 演算法中的必要元件(公式):
1.距離函數(distance function),
2.學習規則(learning rule),
3.核心函數(kernel function),
4.鄰近函數(neighborhood function),
5.學習率函數(learning-rate function),
6.函數及
7. 鄰近範圍的形狀(shape of neighborhood).

首先, 定義距離函數, 學習規則及核心函數.
1.距離函數(歐幾里德距離):


其中是目前的pattern i, 是2維Map上的神經元 j. 距離函數是用來找出距離目前patter最近的神經元並成為winner神經元, 隨後根據鄰近函數更新winner神經元的鄰近其他神經元.

2.學習規則:


其中為神經元 j 在時間 t 時的權重, 為神經元 j 在時間 t 時的核心函數, 為目前所選的 pattern, 為時間 t 時的鄰近範圍之大小.

3.核心函數:


包含了學習率函數及函數, 核心函數會隨著時間 t 變化, 參考常態分佈(Normal distribution)的在不同參數下的曲線變化之後[8], 則我們可以感覺一下是如何更新winner神經元的鄰近其他神經元之權重.

再者, 定義學習率函數, 函數及鄰近函數, 這三個函數通常都定義成單調的(monotonic)遞減的函數. 第一種定義的方式為參考相關文獻[3], 第二種定義的方式則是簡單的方式, 可以從下圖看出其中差異.



4.學習率函數:




其中 為學習率的初始值, 為總迴圈數.

5. 函數:




其中為的初始值, 為總迴圈數.

6.鄰近函數:




其中為鄰近函數的初始值, 為總迴圈數.

最後, 對於鄰近範圍的形狀可以定義成正方形(square)或六角形.

7.鄰近範圍的形狀:



III. Experiment
接下來我們來做點小實驗來體驗一下SOM :D. 首先, 從UCI Machine Learning Repository下載Iris資料集(http://archive.ics.uci.edu/ml/datasets/Iris, 簡單的介紹此資料集, 總共有150筆資料, 每一筆資料有4個屬性(包含sepal length, sepal width, petal length, petal width及class)及3種類別(Iris setosa, Iris versicolour及Iris virginica). 例如: 第35筆資料為4.9,3.1,1.5,0.2,"Iris-setosa".

當想要了解Iris資料集在2維平面上的樣子為何, 我們將屬性兩兩一組並且利用Excel畫出散佈來觀察. 例如: 圖6的x軸為sepal length為及y軸為sepal width.



但是, 當資料集的屬性變多時, 想要畫出所有的散佈圖是相當累人的工作. 此時, SOM就派上用場了, 我們僅需觀察SOM將多維資料映射到2維空間之後的結果就可以了(如圖7), 所以使用SOM是相當的方便.


--
參考文獻及資料
[1] F. Jiang, H. Berry, and M. Schoenauer, "The impact of network topology on self-organizing maps," Proceedings of the first ACM/SIGEVO Summit on Genetic and Evolutionary Computation, pp.247–254, 2009.
[2] K. A. Smith and A. Ng, "Web page clustering using a self-organizing map of user navigation patterns," Decision Support Systems, Vol. 35, pp. 245– 256, 2003.
[3] T. Kohonen, “The Self-organizing map,” Proceedings of the IEEE, Vol. 78, No. 9, pp.1464-1480, Sep. 1990.
[4] Lecture - Neural Network I: Fundamental Theory and Applications, The University of Aizu.
[5] Wikipedia - Self-organizing map,
http://en.wikipedia.org/wiki/Self-organizing_map
[6] Human brain,
http://en.wikipedia.org/wiki/Human_brain
[7] ai-junkie - Kohonen's Self Organizing Feature Map,
http://www.ai-junkie.com/ann/som/som1.html
[8] Wikipedia - Normal distribution, http://en.wikipedia.org/wiki/Gaussian_distribution