IT工程師數位筆記本

概述

SOM是芬蘭教授Teuvo Kohonen提出的一種神經網絡算法，它提供一種將高維數據在低維空間進行表示的方法(通常是一維或二維)。縮減向量維度的過程，叫做向量量化(vector quantisation)。此外，SOM網絡能保留原有數據的拓撲關系。

一個用來直觀感受SOM網絡規則的例子，是將3維顏色映射到二維空間，如圖所示。

圖1

左圖的顏色是按(r,g,b)組合形式表示的，SOM網絡經過學習后能他這些顏色在二維空間進行表示。如右圖所示：為了讓顏色聚類，相似的屬性通常被發現是相鄰的。這種特性被很好的使用，后面你還會看到的。

SOM最有趣的一個方面是，它是無監督學習的。你可能已經知道有監督訓練，比如BP神經網絡，它的訓練數據是由(input, target)向量元組組成的。用這種有監督的方法，當給定輸入向量到網絡中（典型的是一個多層前饋網絡），輸出會被用來和目標向量比較，如果它們不相同，則微調網絡中的權重以減小輸出誤差。這一過程重復多次，并且是對于所有(input,target)向量元組進行的，直到網絡給出想要的輸出。然而訓練一個SOM網絡，則不需要目標輸出向量target。SOM網絡學著對訓練數據進行分類而不需要任何外部監督。是不是很神奇？

在說出事實真相之前，你最好忘掉你對神經網絡的任何知識！如果你嘗試著用神經元、激活函數、前饋/反饋連接這些術語來思考SOM，你很可能很快就懵了。所以，把腦中那些知識先丟到一邊去吧！

樣例代碼下載（C++版）：http://www.ai-junkie.com/files/SOMDemo.zip

ZIP包中包括了可執行程序，沒有編譯器也可以玩的!

另外有人提供一個java版本的：http://www.ai-junkie.com/files/SOMDemo_java.zip

網絡架構

本教程使用2維的SOM網絡。網絡從2維網格節點創建，每個節點和輸入層是全連接的。（譯注：下述如未特別聲明，“節點”均表示“競爭層節點”）下圖是一個有4*4個節點、和輸入層全連接的網絡架構，表示了一個二維的SOM網絡:

圖2

每個節點都有一個拓撲位置，即節點中的(x,y)坐標，同時也包含一個和輸入向量同維度的權重向量。也就是說，如果訓練數據是由向量n維向量V組成的：

V1，V2，V3,…,V

那么每個節點都會包含一個相應的n維權重向量W：

W1，W2，W3，…Wn

上圖中連接節點的連線，僅僅是用來表示鄰接，并不意味著通常談論的神經網絡中的一個連接。網格中的節點之間沒有側連接（不懂！前面看到的教程都說是有的欸）。

圖1所示的SOM網絡有一個尺寸為40*40的默認網格，網格中的每個節點有三個權重，對應著輸入向量中的三個維度：red，green，blue（這里也不懂。為什么是3個權重連接，不應該是8個嘛？）。每個節點以長方形cell的形式表示。圖3顯示了將cell邊界渲染為黑色的cell們，這樣能看得更清楚些:

圖3

學習算法概覽

SOM網絡不需要目標輸出，這是它和其它種類網絡區別的地方。相應地，對于節點權重和輸入向量匹配的地方，被選擇性地優化為和輸入數據所屬類別更像。從初始時隨機權重分布，經過多次迭代，SOM網絡最終形成多個穩定的區域。每個區域都是一個有效的特征分類器，因此你可以把圖形輸出認為是輸入空間的一種特征映射(feature map)。如果你再看一眼圖1，會發現相似顏色的區塊代表了獨立的區域。任何新的、以前沒見過的輸入向量，一旦它輸入到了網絡中，將會刺激到具有相似權重向量的節點。

訓練在很多步驟中都出現并迭代多次：

1. 每個節點的權重被初始化
2. 輸入向量是從訓練數據中隨機選出的，然后被放到網格中
3. 每個節點都被檢查:用節點的權重和輸入向量進行比較，找到最相似的那一個。獲勝節點通常叫做最佳匹配單元（Best Matching Unit，BMU)。
4. BMU的鄰域的半徑被計算。這個值最開始很大，通常設定為和網格半徑相同（fuck，網格半徑是什么鬼，到底是多少？），隨著迭代次數增加會減小。此半徑內任何發現的節點被認為是術語BMU鄰域內的。
5. 每個鄰域內的節點的權重被調整，從而使得他們和輸入向量更像。距離BMU越近，權重改變就越大。
6. 回到步驟2，重復執行N次。
   
   

學習算法的細節

現在來詳細看看每一步是怎么做的。我會用適當的代碼片段補充我的描述。也希望這些代碼對于懂編程的讀者能增加理解。

1. 1.    初始化權重

訓練之前，每個節點的權重一定要被初始化。典型地，這些將被設定為小的歸一化的隨機值。下面的代碼片段中SOM的權值被初始化，因而有0<w<1。節點在CNode類中定義。相關的類為：

class CNode

{

private:

  //this node's weights

  vector<double>      m_dWeights;

  //its position within the lattice

  double              m_dX,

                      m_dY;

  //the edges of this node's cell. Each node, when draw to the client

  //area, is represented as a rectangular cell. The colour of the cell

  //is set to the RGB value its weights represent.

  int                 m_iLeft;

  int                 m_iTop;

  int                 m_iRight;

  int                 m_iBottom;

public:

  CNode(int lft, int rgt, int top, int bot, int NumWeights):m_iLeft(lft),

                                                            m_iRight(rgt),

                                                            m_iBottom(bot),

                                                            m_iTop(top)

  {

    //initialize the weights to small random variables

    for (int w=0; w<NumWeights; ++w)

    {

      m_dWeights.push_back(RandFloat());

    }

    //calculate the node's center

    m_dX = m_iLeft + (double)(m_iRight - m_iLeft)/2;

    m_dY = m_iTop  + (double)(m_iBottom - m_iTop)/2;

  }

  ...

};

可以看出，當創建一個CNode對象時候，權值在構造函數中被自動地初始化。成員變量m_iLeft，m_iRight，m_iTop和m_iBottom僅僅被用來渲染網絡到輸出區域——每個節點以矩形cell的形式顯示，這個矩形cell是由這些值來描述的。如圖3所示。

1. 2.    計算最佳匹配單元BMU

為了算出BMU，一個方法是遍歷所有節點并計算節點的權重向量和當前輸入向量的歐氏距離。如果一個節點的權值向量和輸入向量最接近，那么這個節點就被標記為BMU。

歐氏距離計算式為：

公式1

其中V表示當前輸入向量，W表示節點的權重向量。在代碼中，這個等式被翻譯為：

double CNode::GetDistance(const vector<double> &InputVector)

{

  double distance = 0;

  for (int i=0; i<m_dWeights.size(); ++i)

  {

    distance += (InputVector[i] - m_dWeights[i]) * (InputVector[i] - m_dWeights[i]);

  }

  return sqrt(distance);

}

例如，計算紅色向量(1,0,0)到一個隨機權重向量(0.1,0.4,0.5)的距離：

distance = sqrt( (1 - 0.1)² + (0 - 0.4)²+ (0 - 0.5)² )

               = sqrt( (0.9)² + (-0.4)²+ (-0.5)² )

               = sqrt( 0.81 + 0.16+ 0.25 )

                = sqrt(1.22)

distance  = 1.106

1. 3.    計算BMU的局部鄰域

從這里開始，事情變得有趣了！每次迭代，只要BMU被算出了，那么下一步就是計算出哪些其他節點是在BMU的鄰域內。所有這些節點在下一步都會更新其權值。那么，怎樣做到呢？其實不難…首先算出鄰域應當具備的半徑，然后就是勾股定理的簡單使用，來算出每個節點是否屬于這個鄰域。圖4是簡單示例：

圖4

可以看到，鄰域是以BMU為中心（黃色圓球）的圓形區域。綠色箭頭表示半徑。

Kohonen學習算法的一個獨特特征是，隨著迭代次數的增加，鄰域會變小，這通過縮減半徑做到，比如：

公式2

其中希臘字母s₀表示t₀時間的網格寬度，而希臘字母l表示時間常量。t表示當前時間步驟（迭代次數）。我的代碼中把s命名為m_dMapRadius，它在訓練結束的時候等于s₀。我計算s₀的方式為：

m_dMapRadius = max(constWindowWidth, constWindowHeight)/2;

l的值依賴于s的取值和算法迭代次數的取值。我把l命名為m_dTimeConstant，計算代碼為：

m_dTimeConstant = m_iNumIterations/log(m_dMapRadius);

其中m_iNumIterations表示迭代次數。在constants.h中用戶可進行修改。

我們可以使用m_dTimeContant和m_dMapRadius在每次迭代中使用公式2計算鄰域半徑：

m_dNeighbourhoodRadius = m_dMapRadius * exp(-(double)m_iIterationCount/m_dTimeConstant);

圖5顯示了圖4中鄰域是如何隨著迭代次數的增加而縮減的(假設BMU不變)：

圖5

隨著時間推移，鄰域會縮減為只剩BMU本身。

現在我們知道了半徑和鄰域的變化情況，鄰域覆蓋到的節點需要調整其權值，調整規則如下所示。

1. 4.    調整權值

BMU鄰域內的每個節點，包括BMU在內，都要根據下式調整權值向量：

公式3

其中t表示迭代次數，L是一個小變量，稱為學習率，會隨著時間推移而減小。這個調整公式的意思是，新的權值，是在老的權值基礎上，加上學習率乘以老的權值向量與輸入向量的差值。

學習率的衰減，通過如下公式計算：

公式4

其實很容易發現公式4和公式2是相同的形式。對應的代碼為：

m_dLearningRate = constStartLearningRate * exp(-(double)m_iIterationCount/m_iNumIterations);

訓練一開始時的學習率，constStartLearningRate，在constant.h文件中進行設定了為0.1。然后隨著時間遞減最終接近0。

注意！公式3其實是不完全正確的！因為沒有考慮到節點到BMU的距離。距離的影響可以認為是符合高斯分布的:

對此，我們改進公式3，得到:

公式5

其中q表示節點到BMU距離的影響力度：

公式6

SOM的應用

SOM常常被用來做可視化的助手，能幫助人類更容易地看到大數據之間的關系。我舉個栗子：

世界貧困圖

SOM被用來為統計數據做分類，包括關于生活質量的種種數據，比如健康狀態、營養狀態、教育服務程度等。具備相似的生活質量的國家被聚集在一起。左上方的國家是生活質量高的國家，而最窮的國家在圖中右下方。六邊形網格是一個統一距離矩陣，通常叫做u-matrix。每個六邊形代表SOM網絡中的一個節點。

接下來可以把顏色信息繪制到地圖上，比如:

這使得我們對于貧困數據的理解更容易了。

其他應用

SOM在許多其他方面被應用。比如：

書目分類

圖像瀏覽系統

醫學診斷

解釋地震活動

語音識別（Kohonen最初就是要做這個的）

數據壓縮

分離聲源

環境模型

甚至是吸血鬼分類！