2.1.3 模式聚類

2.1.2節介紹的模式分類器在學習狀態時所利用的樣本必須是已知類別的，因此這種學習稱為有監督學習。在一些實際的應用中，往往沒有已知類別的樣本可供利用，甚至將提供的樣本應分成幾類都不知道。例如，衛星遙感照片上各像素點的分類問題，我們不知道各像素點屬于哪一類，甚至不知道應將照片上的像素點分成幾類。

本節要討論的內容就是將未知類別的樣本集劃分成若干子集（類），劃分的直接成果是完成了樣本的分類，可能的間接成果是確定了分類器的參數。由于所用樣本是沒有類別標志的，因此通常稱為無監督學習。

無監督學習以“物以類聚”為指導思想，對未知類別的樣本集根據樣本之間的相似程度分類，相似的歸為一類，不相似的歸為另一類，故這種模式聚類稱為聚類分析。

采用模式聚類，首先要解決兩個問題：一是如何衡量兩個樣本的相似程度；二是相似到什么程度歸為一類。這就涉及模式相似性的測度和聚類準則。

模式聚類是統計模式識別的另一重要工具，它把模式歸入到同樣的類或聚合類；同一個聚合類比不同聚合類中的模式更相近。已知若干模式和它們的特征，但不知道每個模式的類別，且事先也不知道究竟分成多少類，在此基礎上使用某種相似性度量的方法，即基于“物以類聚”的觀點，把特征相似的模式歸為一類的方法稱為模式聚類法。這種方法是一種非監督學習的方法。

1.模式相似性測度和聚類準則

（1）相似性測度

相似性測度用于衡量同類樣本的類似性和不同類樣本的差異性。常用的測度有：

1）歐氏距離（即歐幾里得距離，簡稱距離）

設Xi和X j為兩個樣本，其歐氏距離定義為

顯然，樣本Xi和X j間的距離越小，越相似。

2）街坊距離

街坊距離的表達式為

與歐氏距離相比，街坊距離減小了計算量。

3）角度相似性函數

角度相似性利用樣本Xi和X j間夾角的余弦來定義，即

距離和角度相似性函數作為相似性的測度各有其局限性。距離對于坐標系的旋轉和位移是不變的，而對于放大和縮小并不具有不變性的性質。角度相似性函數對于坐標系的旋轉、放大和縮小均具有不變性，但對于位移不具有不變性的性質。用角度相似性函數作為相似性的測度還有一個缺點，當本屬不同類的樣本分布在從模式空間原點出發的一條直線上時，所有樣本之間的角度相似性函數幾乎都等于1，這會造成將這些樣本全歸為一類的錯誤。

（2）聚類準則

為了評價聚類結果的好壞，必須定義準則函數。有了模式相似性測度和準則函數后，聚類就變成了使準則函數取極值的優化問題了。

常用的準則函數是誤差平方和準則。

若Ni是第i類ωi中的樣本數目，mi是這些樣本的均值，即

把ωi中的各樣本X與均值mi間的誤差平方和對所有類相加后為

式中，J 是誤差平方和聚類準則，它度量了用 c 個聚類中心m1,m2,…,mc代表 c 個樣本子集m1,m2,…,mc時所產生的總的誤差平方和。對于不同的聚類，J值當然是不同的，使J值極小的聚類是誤差平方和準則下的最優結果。這種類型的聚類通常稱為最小方差劃分。

2.層次聚類法

模式聚類的三要素為相似性測度、聚類準則和聚類算法。選定相似性測度和聚類準則后，下面的問題是用什么算法找出使準則函數取極值的最好聚類結果。現有的兩種聚類算法是非迭代的層次聚類算法和迭代的動態聚類算法。本節將討論層次聚類算法。

層次聚類算法又稱系統聚類法、分級聚類法，該方法先把所有樣本各自視為一類，然后計算類與類之間的相似性，選擇相似性最大的一對類別合并成一個新類，進而在新的類別劃分下重復合并操作，直到滿足停止條件。由此可見，層次聚類法具有如下性質：在某一級劃分時歸入同一類樣本，在此后的劃分中，它們永遠屬于同一類。

從上面的討論也可發現，層次聚類法需要解決兩方面的問題：一是如何衡量類別的相似性；二是聚類操作應停止在哪一級上。

通常不同類別的相似性通過類間距離來度量，設類ωi和類ωj之間的距離用Δ(ωi,ωj)表示，最常用的類間距離定義有以下幾種。

（1）最近距離

類ωi和類ωj之間的最近距離Δ(ωi,ωj)為ωi類中所有樣本與ωj類中所有樣本間的最小距離，即

（2）最遠距離

類ωi和類ωj之間的最遠距離Δ(ωi,ωj)為ωi類中所有樣本與ωj類中所有樣本間的最大距離，即。

（3）均值距離

類ωi和類ωj之間的最近距離Δ(ωi,ωj)為ωi類的均值mi與ωj類的均值m j之間的距離，即Δ(ωi,ωj)=d(mi,m j)。

三種距離的表達式中d( )可以是任何一種模式相似性測度。

由于定義類間距離的方法不同，故得到的聚類結果可能不一致。

聚類可能以3種方式終止：所有的樣本合并為一類；達到所規定的類別數；所有的類別相似性測度大于給定的相似性閾值。

已知樣本集為{X1,X2,…,XN}，下面給出層次聚類的具體步驟：

（a）以N個樣本作為N個類別，計算每類間的相似度，形成相似度矩陣；

（b）在相似度矩陣中尋找最相似的兩個類別，將這兩個類別合并；

（c）重新計算各類別間的相似度，獲得新的相似度矩陣；

（d）判斷是否達到聚類終止的條件，如達到，則聚類終止，否則轉到步驟（b）。

3.c-均值算法

c-均值算法是動態聚類法的一種。動態聚類法的特點在于聚類過程通過不斷的迭代來完成，且在迭代中通常容許樣本從一個聚合類中轉移到另一個聚合類中。動態聚類過程如圖2-2所示。

c-均值算法的指導思想是假定樣本集中的全體樣本可分為c類，并選定c個初始聚類中心，然后根據最小距離原則將每個樣本分配到某一類中，之后不斷迭代計算各類的聚類中心并依新的聚類中心調整聚類情況，直到迭代收斂。

設樣本集為{X1,X2,…,X N}，聚合的 c 個類別用ω1,ω2,…,ωc表示，各類的中心分別為m1,m2,…,mc，則c-均值算法采用的準則函數為

在進行聚類之前，還必須預先確定類別數c和初始聚類中心。

類別數c如果不能通過先驗知識確定，則可采用作圖法近似求出。對c從小到大應用c-均值算法進行聚類，在不同的c值下取得不同的J值，分別用Jc表示，顯然準則函數Jc隨著c的增加而減小，這樣就可作出一條Jc-c 曲線。若曲線上存在一個拐點，則拐點對應的類別數即為欲求的最佳類別數；若拐點不明顯，則該方法失效。

初始聚類中心的選擇與聚類結果直接相關，選擇不同的初始聚類中心會產生不同的聚類結果。初始聚類中心的選擇方法較多，例如：

·根據問題的性質，憑經驗選擇。

·用前c個樣本作為初始聚類中心。

·將全部樣本隨機地分為c類，以每類的均值作為初始聚類中心。

·當樣本數N較大時，先隨機從中選擇一部分樣本采用層次聚類法將其聚成c類，以每類的均值作為初始聚類中心。

c-均值算法可描述如下：

（a）選擇c個初始聚類中心m1(1),m2(1),…,mc(1), k=1。

（b）計算所有樣本與各聚類中心的距離

按最小距離原則將樣本X進行聚類，即若

則X∈ωj。

（c）重新計算聚類中心

式中，Ni為當前ωi類中的樣本數目。

（d）若存在任一i∈{1,2,…,c}，有mi(k+1)≠mi(k)，則 k=k+1，轉向步驟（b）；若任意i∈{1,2,…,c}，都有mi(k+1)=mi(k)，則聚類結束。