[ SOM: SOM ]
Introducing the Self-Organizing Map (SOM)

為了以SOM為主題寫的國科會計畫的內容,往後在這裡記下一些技術性的細節--而且是中文的[1]!

SOM,自我組織映射

SOM主要的好處就是可以保持高維資料的特性,用二維平面來呈現分類結果--聽起來多美滿!至於其他好處就先不提囉。

會使用SOM應該就是要去操弄或分析包含高維向量的資料集吧,所以理論上你手上應該會有一個要給SOM訓練的input data,且這些data中會有一堆同維度的向量;我們底下就用V1、V2 …Vi …代表input data裡面的向量。

舉例來說,假設我手上有班上30位學生的資料,其中包括姓名、學號、身高、體重。這就代表我的input data有30個4維的向量:

Vi = (姓名i, 學號i, 身高i, 體重i)

如果手上沒有資料也沒關係,我只是要說明SOM訓練的過程中,會需要先知道input data中向量的維度

以上例而言就是 4 。


簡單說明演算法的五個步驟:

接著就是整個演算法究竟是怎麼運作的啦!

總共有五個步驟,我們先簡單瀏覽:

STEP 1 : 創造隨機節點(nodes)
STEP 2: 隨機選擇輸入向量找到最好的節點(Best Matching Unit, BMU)
STEP 3: 決定該節點的鄰居範圍
STEP 4: 學習,也就是去更新鄰居範圍內的權重(Weight)
STEP 5: 每學習一次,範圍與學習率都會衰減,重複step2–5直到範圍只剩自己

STEP 1:

我們先自己定義出MxN大小的矩陣(註1),也可以是方陣,每一個節點都含有一個與輸入向量 (V) 同維度的向量,其各值隨機地介於0-1之間,我們稱這些節點上攜帶的向量叫做W。

以上述學生為例,每一個位置i,j都會有一個四維、介於0-1之間的隨機單位向量(Wi,j),可參考圖一。

※注意是要與V同維度隨機值(0–1)、且是單位向量才行。

圖一:input data & nodes

註1:
雖然說是用矩陣、或是矩形,但實際上用六角型蜂窩狀的會更加理想(WHY?),不過我當初寫的程式還是在用矩形跑,所以這裡介紹就以矩形為例。


STEP 2:

隨機從V中選擇一個向量V1當作input vector,將V1與所有的nodes逐一歐式距離公式(圖二)計算彼此距離。

圖二:距離公式

計算過所有的nodes後,找出所有距離的最小值,則該節點就是Best Matching Unit, BMU了(圖三)。

圖三:BMU

STEP 3:

要決定BMU的鄰居範圍--因為只有屬於BMU的鄰居才會調整權重。

我們令一個範圍函數sigma(t)

sigma(t)的公式內容稍後介紹,我們先看t:

t是當前的迴圈數--畢竟學習總要多跑個幾圈才行,整個學習過程會跑迴圈很多次,偷偷看上面的step5就知道了。所以第一次迴圈進來的時候,t = 1,第二次:t = 2 ……簡單吧。

而sigma(t)會輸出一個距離值,我們就依照這個值來決定誰是鄰居(距離內),而誰不是(距離外)。

BUT!

正常情況下sigma(t)會輸出一個非整數的值;我們產生的方陣彼此不連續,而是一個一個 (i , j)的。那麼如果sigma(t) = 1.45763的時候怎麼辦呢?

這時候看各位的定義(反正只要交代清楚就沒問題了),小數部分我是以0.5為界,小數部分只要 >0.5 就進位;=0.5 & < 0.5 就退位。也就是說當sigma(t) = 1.45763的時候,就把它當作1處理。

以圖四為例,假如sigma(t) = 1.61803……,我們就當2處理。所以對於這個BMU而言,只有離它2以內的node才會是它的鄰居。(邊界就是邊界了)

圖四:BMU & sigma(t)圖示

至於sigma(t)到底長什麼樣子呢?

圖五:鄰居函數 sigma(t)

解釋一下:

sigma 0 代表初始的範圍,可以取全部的矩陣範圍(我是取方陣的一半當作sigma 0),例如是一個20 x 20的矩陣,你可以令它 = 20。

我們希望鄰居的範圍越來越小,所以使用了指數衰減(其他方式也可以,交代清楚就好啦~)。注意括號裡面是負號,所以當迴圈進來越多次,也就是t越來越大的時候,範圍就會越來越小。

lambda則是時間常數,其值是總迴圈數(需要預先決定)除上初始範圍取對數值。由於我是用筆電跑、又因為指數衰減速度快,所以我的迴圈數並沒有設定太多(N = 200)。


STEP 4:

接下來就是更新權重,也就是改變step3中屬於鄰居的nodes的權重(weight),或者說是改變其向量W的值;這就是學習阿!

不過,更新的依據是什麼?

我們先引入一個函數, 稱做學習率函數 L(t)

L(t)長的跟sigma(t)一模一樣:

圖六:學習率函數 L(t)

只有L0需要再特別解釋:L0就是初始學習率,也是需要預先決定的參數之一,介於0-1之間,通常會設定的靠近1一點(WHY?)。(我是設定過0.7 - 0.9都有,可以自己斟酌,用1也沒關係)

當然,如果你不要用指數衰減也是可以的,想辦法衰減就對了。

有了L(t)之後,我們就能夠更新nodes的權重了!

依據下列方程式調整:

圖七:更新的依據

上式的意思是說,屬於鄰居節點上的向量(Wi,j),更新後會等於原本的值加上學習率乘上它們之間的差值,也就是我們希望它從原本隨機的狀態,更像input vector一點

或者說使當前的BMU與它的鄰居更像V1 (input vector) 一點。

BUT!!

我們又希望它能夠滿足一個條件:當更新的時候,希望離BMU越近的node調整的權重越多,所以需要再引入一個參數--theta(t)。

圖八:又來一個參數theta(t)

這一坨看起來有點嚇人,不過仔細看看,括號內分母其實是sigma(t),代表在同一次迴圈之內,它其實是一個常數;而分子是該node與BMU的距離平方。

所以,theta(t)其實就是高斯函數的一種,即它長的樣子就是鐘型曲線(的一種):

圖九:theta(t)長的樣子就是鐘型曲線啦

其中,x軸就是dist,該node與BMU的距離,y軸就是它對應輸出的值。

可以注意到當距離是0、也就是BMU自己的時候,y值是1;離BMU越遠,y值越低--這項特性就是我們要的!

不過免不了再說一次,如果你想要其他種的調整函數也是可以,原則上都是越靠近BMU,調整的越多就好啦。

所以我們修正一下權重調整的依據(方程式):

圖十:最終調整的公式,不會再變了

如此一來,就滿足了:

一、在同一個迴圈之內只有鄰居會被調整。

二、在這些被調整的鄰居之中,離BMU越的node會被調整地越多。

三、隨著迴圈的增加,調整的量會越來越

也就是說只有BMU附近的node會與input vector越來越像,並且BMU會是最像的。


STEP 5:

複雜的上面都說完了,最後一步是要強調上述過程都只是一個迴圈內一個向量(input vector)要做的事情,實際上所有的向量要做幾百、幾千、幾萬個迴圈。

上述必須強調一下,做完一個向量的調整並不是馬上跳到 t = 2,而是要隨機地抽下一個向量(不重複),必須做完所有的input vector才會進入 t = 2!

而在整個過程中,所有的參數都會依照當前迴圈數t衰減,意即:一開始調整地多,慢慢的調整的越來越微弱,不僅是在範圍、學習率亦同。

我們稱一開始調整較多的階段叫做排列階段;後期調整量衰減許多的階段叫做收斂階段


呼,終於結束了!

附上一個用IRIS資料集[2](105個4維向量)做出來的結果:

圖十一:Iris資料集測試;左:訓練前、中:訓練結果、右:丟入原始資料繪圖

重要的是中間深藍色、經訓練過的矩陣。(原本應該是灰階的、我也認為灰階比較好,但在meeting的前一天突然變成彩色,我也不知道為什麼)

右邊的圖是把原始資料丟進中間輸出的結果,只是用原始資料來參考訓練出來的矩陣而已;由這個結果看來,SOM的分類效果還不錯!

事實上,若不知道原始的資料分類--一般而言你應該是不知道輸入資料的分類的--是無法自動切出1、2、或 3 的,只能藉由其他方式(未來搞懂了再補上!)大致分類--SOM最重要的結果就是能將一坨高維的資料,放在二維平面上呈現,你要分類再分類!

至於究竟要怎麼分類之後再說吧!


細心的同學會說:"WAIT!"

如果仔細看,會發現中間那張圖中的每個格子只攜帶了一個值,所以能用一個顏色表示[3]。可是iris資料集裡面明明就是4維向量阿?

那麼要如何把高維向量用一個顏色標示呢?

在訓練完 SOM 的網路後, 將每一個神經元與上下左右四個鄰居的神經元鍵結值計算距離取最大值當作該神經元的強度, 最後將所有神經元的強度正規化成[0,255]。 而該神經元強度值就是灰階影像的灰階值。[4]

也就是一個node如果周遭的鄰居都長的跟它很像,那麼它們的距離就會很小,導致畫出來的灰階值就會很黑;反之如果周遭只要有一個跟它長的很不一樣,就會比較白!

所以這個方法期望得到的結果,就是一張圖,用比較淺色的方式盡量分隔了深色的SOM訓練結果。

--如果是用灰階畫圖的話。


註解 & 參考資料(非正式學術格式):

[1]:由衷感謝這個網站
[2]:http://archive.ics.uci.edu/ml/datasets/Iris
[3]:實際上三維的資料也可以用RGB來表示,但我說過了,原本它是灰階的Q_Q

[4]:蘇軾詠(2004):結合群體智慧與自我組織映射圖的資料視覺化研究,p25。

One clap, two clap, three clap, forty?

By clapping more or less, you can signal to us which stories really stand out.