第八章無監(jiān)督學(xué)習(xí)

（聚類分析,Clustering

）1

以前討論的分類方法都是在已知訓(xùn)練樣本類別的基礎(chǔ)上進行的。8.1引言在實際應(yīng)用中，有時我們只能用沒有類別標(biāo)簽的樣本集來進行分類工作。稱為無監(jiān)督學(xué)習(xí)，無教師學(xué)習(xí)，聚類分析。2有哪些類（組）?類的定義？多少類？都不知道。此時需要研究模式分布的內(nèi)在結(jié)構(gòu)、組織。目標(biāo)是根據(jù)模式間的相似性把它們分成一些類（組）。3例如

相似的緊湊性定義緊湊型聚類直線（平面）型聚類451．聚類的定義

不好定義。大多數(shù)基于“相似”、“相象”，或面向某一特定的類型。

如果特征是d維特征空間的一個向量（一個點），那么聚類可以描述為：含有相對較高密度點的一個連續(xù)區(qū)域，這個區(qū)域和其它高密度點的區(qū)域分開，而中間是低密度點的區(qū)域。這種聚類的定義和二維、三維時的視覺效果一致。

6生命科學(xué)

動物學(xué)植物學(xué)

醫(yī)學(xué)精神病學(xué)病理學(xué)

社會科學(xué)考古學(xué)

社會學(xué)

地球科學(xué)地質(zhì)學(xué)

地理學(xué)

許多科學(xué)領(lǐng)域都使用了聚類分析的方法：

7聚類分析是人類的一種最基本的智能活動。是從個體到類別的一個概括，是進行抽象的基礎(chǔ)。單獨處理各個模式（個體）有時是不可能的。人們傾向于將它們分類，每類有共同的屬性。82．聚類分析的應(yīng)用1）數(shù)據(jù)挖掘、信息恢復(fù)、信號壓縮與編碼、機器學(xué)習(xí)N個數(shù)據(jù)，→m（<<N）個聚類，每個聚類中的樣本都用一個代表性的量表示。

2）圖象分割。比如從遙感圖像中分割田野和森林區(qū)。3）預(yù)測；產(chǎn)生假設(shè)，檢驗假設(shè)未知的物體∈某一聚類，聚類中各個模式具有這一類的共性=>預(yù)測未知物體的特性。

93.聚類的一般步驟

1）特征的提取和選擇特征應(yīng)充分反映模式的信息，同時盡量減少冗余。

2）確定proximity度量（相近性）

用來刻畫兩個模式的相似性（similarity）或不相似性（dissimilarity）。103）聚類的準(zhǔn)則

取決于問題本身，和專家的意見。如有時認(rèn)為緊湊的合理，有時認(rèn)為線型的合理.聚類準(zhǔn)則一般用目標(biāo)函數(shù)或某些規(guī)則表示。

4）聚類算法

在定義了Proximity度量和聚類準(zhǔn)則后，要設(shè)計一個好的算法，得到好的聚類。

115）聚類結(jié)果的驗證

檢驗聚類結(jié)果的合理性，一般由領(lǐng)域的專家來判定。

除了上述步驟外，有時還要做“是否有聚類傾向（趨勢）”分析，作各種實驗，分析數(shù)據(jù)是否有聚類的結(jié)構(gòu)，還是隨機的數(shù)據(jù)。12不同的特征，不同的相似性度量，不同的聚類準(zhǔn)則，不同的算法，對同樣的數(shù)據(jù)可能會得出完全不同的結(jié)果。

134.兩種聚類問題及解決的方法：1.基于概率密度函數(shù)估計的方法2.基于樣本間相似性程度的聚類法14

各類樣本混合起來，要把屬于各類的樣本分開。第一種方法：S1S2這時，可以把特征空間（混合密度函數(shù)）分解為若干子集，對每個子集來說，其混合概率密度函數(shù)都是單峰的，這樣的每個單峰區(qū)域都對應(yīng)一個類。但估計概率密度函數(shù)需要大量樣本，比較困難。15第二種方法：（聚類，clustering）按照樣本間的相似性把樣本集劃分成若干組。劃分的結(jié)果應(yīng)使某種表示聚類質(zhì)量的準(zhǔn)則函數(shù)最大或最小。相似性一般是用距離表示的。16θ2θ1樣本間的相似性，一般用距離，但有時要用方向或其它度量。17迭代的動態(tài)聚類算法

兩種主要的聚類算法非迭代的分級聚類算法188.2動態(tài)聚類算法的一般步驟令Y表示樣本的集合{y(i)}(其中i為樣本序號)，Ω是有序的類別標(biāo)簽集合，每一標(biāo)簽和一個樣本相對應(yīng)，如果在Y中有N個樣本，則Ω中有N個標(biāo)簽和它對應(yīng)，每一個是ω1，ω2，…，ωc

之一。由于過程是迭代的，記Ω(r)是第r次迭代時的標(biāo)簽。19一般步驟如下1．選定某種距離度量作為樣本間相似性的度量。2．確定評價聚類結(jié)果質(zhì)量的準(zhǔn)則函數(shù)J（Y，Ω）,假定J最小時，最優(yōu)。3．選擇（確定）一個初始劃分Ω(0),計算J4．改變聚類的劃分，從而使J減小。5．如果J不能再減小，停止。否則轉(zhuǎn)4。208.3C－均值聚類（K－均值聚類）算法

C均值算法采用歐式距離作為樣本間相似性的度量。準(zhǔn)則函數(shù)J是誤差平方和準(zhǔn)則。并假定要分C類，事先定好了。設(shè)第i個聚類Γi中的樣本數(shù)為Ni，mi是第i類樣本的均值：21

J度量了用C個聚類中心m1，m2，…，mc來代表C個樣本子集時，所產(chǎn)生的總的誤差平方和。準(zhǔn)則函數(shù):

對不同的聚類，J的值不同，使J最小的分類是誤差平方和準(zhǔn)則下最優(yōu)的。

22C均值算法：

1、選擇任意一個初始劃分（把N個樣本分為C類），或任意選擇C個初始聚類中心，然后把N個樣本按照距離分到最近的聚類中心去。

2、計算每類的樣本均值m1，m1，…，mc

3、重新把每個樣本分到最近的均值所屬的類（調(diào)整）。

4、如果樣本的分類結(jié)果不再改變，停止。否則轉(zhuǎn)2

23C-均值聚類算法的兩種類型另一種方法是一次只調(diào)整一個樣本的類別，并計算該樣本所進入類和離開類的均值，這稱為單樣本法。上述算法中，將所有樣本按最小距離原則分類之后，再計算各類的均值，這稱為成批法。這兩種算法的收斂性都得到了嚴(yán)格證明。

24C-均值聚類算法的收斂性分析準(zhǔn)則函數(shù)值為（第s步）：

25

設(shè)某樣本yi從聚類

j移至聚類k中，

j移出yi后的集合記為，

k移入yi后的集合記為。

設(shè)

j和

k中所含的樣本數(shù)分別為nj和nk，聚類

j、、

k和的均值矢量分別為mj、、mk和。

存在下列關(guān)系：26

兩個新聚類和的類內(nèi)歐氏距離平方和與原來的兩個聚類

j和k的類內(nèi)歐氏距離平方Jj和Jk的關(guān)系是27當(dāng)yi距mk比距mj更近時，就有：

從而，即將yi分劃給

k類可使J變小。這說明在分類問題中不斷地計算新劃分的各類的均值，并按最小距離原則對各個樣本歸類，可使J值減至極小值。

28C-均值聚類算法的性能

C-均值算法是以確定的類數(shù)及選定的初始聚類中心為前提，使各模式到其所屬類別中心距離