柚子快報邀請碼778899分享：周志華機器學(xué)習(xí)——聚類算法。

http://yzkb.51969.com/

聚類算法

聚類算法是一種經(jīng)典的無監(jiān)督學(xué)習(xí)方法，無監(jiān)督學(xué)習(xí)的目標(biāo)是通過對無標(biāo)記訓(xùn)練樣本的學(xué)習(xí)，發(fā)掘和揭示數(shù)據(jù)集本身的潛在結(jié)構(gòu)與j規(guī)律，即不依賴于訓(xùn)練數(shù)據(jù)集的類標(biāo)記信息。聚類則試圖將數(shù)據(jù)集的樣本劃分為若干個互相相交的類簇，從而每個簇對應(yīng)一個潛在的類別。 聚類直觀上來說是將相似的樣本聚集在一起，從而形成一個類簇，（Cluster), 那首先的問題是如何度量相似性，這便是距離度量，在生活中，我們說差別小則相似，對應(yīng)多維樣本，每個樣本可以對應(yīng)高維空間中的一個數(shù)據(jù)點，若它們的距離相近，我們便可以稱其為相似，那接著如何來評價聚類結(jié)果的好壞呢？這便是性能度量，性能度量為評價聚類結(jié)果的好壞提供了一系列有效性指標(biāo)。

距離度量

談及距離度量，最熟悉的莫過于 歐式距離了，從年頭一直用到年尾的距離計算公式，即對應(yīng)屬性之間相減的平方和在開根號，度量距離還有很多其他經(jīng)典的度量方法，通常它們需要滿足以下基本性質(zhì)： 非負(fù)性

d

i

s

t

(

x

i

,

x

j

)

>

=

0

;

dist(x_i,x_j)>=0;

dist(xi?,xj?)>=0; 同一性

d

i

s

t

(

x

i

,

x

j

)

=

0

當(dāng)且僅當(dāng)

x

i

=

x

j

dist(x_i,x_j) = 0當(dāng)且僅當(dāng)x_i = x_j

dist(xi?,xj?)=0當(dāng)且僅當(dāng)xi?=xj? 對稱性

d

i

s

t

(

x

i

,

x

j

)

=

d

i

s

t

(

x

j

,

x

i

)

dist(x_i,x_j) = dist(x_j,x_i)

dist(xi?,xj?)=dist(xj?,xi?) 直遞性

d

i

s

t

(

x

i

,

x

j

)

<

=

d

i

s

t

(

x

i

,

x

k

)

+

d

i

s

t

(

x

k

,

x

j

)

dist(x_i,x_j)<=dist(x_i,x_k) + dist(x_k,x_j)

dist(xi?,xj?)<=dist(xi?,xk?)+dist(xk?,xj?) 即三角不等式，兩邊之和大于第三邊。 最常用的距離度量方法是閔可夫斯基距離：

d

i

s

t

m

k

(

x

i

,

x

j

)

=

(

∑

u

=

1

n

∣

x

i

u

?

x

j

u

∣

)

1

p

dist_{mk}(x_i,x_j) = (\sum^n_{u = 1}|x_{iu} - x_{ju}|)^{\frac{1}{p}}

distmk?(xi?,xj?)=(u=1∑n?∣xiu??xju?∣)p1? 當(dāng) p = 1時，該距離公式可以變?yōu)槁D距離：

d

s

i

t

m

a

n

(

x

i

,

x

j

)

=

∣

∣

x

i

?

x

j

∣

∣

1

=

∑

u

=

1

n

∣

x

i

u

?

x

j

u

∣

dsit_{man}(x_i,x_j) = ||x_i - x_j||_1 = \sum^n_{u = 1}|x_{iu} - x_{ju}|

dsitman?(xi?,xj?)=∣∣xi??xj?∣∣1?=u=1∑n?∣xiu??xju?∣ 當(dāng)p = 2時，該距離公式都是歐式距離公式，可以表示為：

d

i

s

t

e

d

(

x

i

,

x

j

)

=

∣

∣

x

i

?

x

j

∣

∣

2

=

∑

u

=

1

n

∣

x

i

u

?

x

j

u

∣

2

dist_{ed}(x_i,x_j) = ||x_i - x_j||_2 = \sqrt{\sum^n_{u =1}|x_{iu} - x_{ju}|^2}

disted?(xi?,xj?)=∣∣xi??xj?∣∣2?=u=1∑n?∣xiu??xju?∣2

?

我們清楚屬性劃分有兩種連續(xù)屬性和離散屬性，（有限個取值），對于連續(xù)屬性的取值，一般都可以被學(xué)習(xí)器取用，有時會根據(jù)具體的情形做相應(yīng)的預(yù)處理，例如：歸一化等，對于離散值的屬性，需要做下一步處理： 若屬性值之間存在序關(guān)系，可以將其轉(zhuǎn)化為連續(xù)值：身高屬性“高”“中等”“矮”，可轉(zhuǎn)化為

1

,

0.5

,

0

{1, 0.5, 0}

1,0.5,0。 若屬性間不存在序關(guān)系，可以將其轉(zhuǎn)化為向量的形式，例如：性別屬性男女：可轉(zhuǎn)化為

（

1

,

0

），（

0

,

1

）

{（1,0），（0,1）}

（1,0），（0,1） 在進行距離度量時，容易知道連續(xù)屬性和存在序關(guān)系的離散屬性都可以直接參與計算，因為它們都可以反應(yīng)一種程度，我們稱之為有序?qū)傩?，而對于不存在序關(guān)系的離散屬性，我們稱之為無序?qū)傩裕@然無序?qū)傩栽偈褂瞄h可夫斯基距離就行不通了。 對于無序?qū)傩?，我們一般采用VDM進行距離的計算，例如：對于離散屬性的兩個取值

a

a

a和

b

b

b,定義為：

V

D

M

p

(

a

,

b

)

=

∑

i

=

1

k

∣

m

u

,

a

,

i

m

u

,

a

?

m

u

,

b

,

i

m

u

,

b

∣

p

VDM_p(a,b) = \sum^k_{i = 1}|\frac{m_{u,a,i}}{m_{u,a}} - \frac{m_{u,b,i}}{m_{u,b}}|^p

VDMp?(a,b)=i=1∑k?∣mu,a?mu,a,i???mu,b?mu,b,i??∣p 于是在計算兩個樣本之間的距離時，我們可以將閔可夫斯基距離和VDM混合在一起進行計算： 我們定義的距離度量方式是用來計算相似性的，例如下面將要討論聚類問題，即距離越小，相似性越大，反之，距離越大，相似性越小。這時的距離度量方法并不一定需要滿足前面所說的四個基本性質(zhì)。這種方法稱為非度量距離。

性能度量

由于聚類方法不依賴于樣本的真實類標(biāo)，就不能像監(jiān)督學(xué)習(xí)的分類那般，通過計算分對錯（即精確度和錯誤率）來評價學(xué)習(xí)器的好壞或者做為學(xué)習(xí)過程的優(yōu)化目標(biāo)，一般聚類有兩類性能優(yōu)化目標(biāo)，外部指標(biāo)和內(nèi)部指標(biāo)。

外部指標(biāo)

即將聚類的結(jié)果與單個參考模型的結(jié)果進行比較，以參考模型的輸出作為標(biāo)準(zhǔn)，來評價聚類好壞，假設(shè)聚類給出的結(jié)果為

λ

\lambda

λ 參考模型給出的結(jié)果為

λ

?

\lambda^*

λ?,則我們將樣本進行兩兩配對，定義為：

雖然

a

a

a和

b

b

b代表著聚類結(jié)果好壞的正能量，

b

b

b和

c

c

c則表示參考結(jié)果和聚類結(jié)果相矛盾，基于這四個值可以導(dǎo)出以下常用的外R部指標(biāo)：

Jaccard系數(shù)

J

C

=

a

a

+

b

+

c

JC = \frac{a}{a + b + c}

JC=a+b+ca?FM指數(shù)

F

M

I

=

a

a

+

b

×

a

a

+

c

FMI = \sqrt{\frac{a}{a + b}\times\frac{a}{a+c}}

FMI=a+ba?×a+ca?

?Rand指數(shù)

R

I

=

2

(

a

+

d

)

m

(

m

?

1

)

RI = \frac{2(a+d)}{m(m - 1)}

RI=m(m?1)2(a+d)?

內(nèi)部指標(biāo)

內(nèi)部指標(biāo)即不依賴于任何外部模型，直接對聚類結(jié)果進行評估，聚類的目的是想將那些相似的樣本盡可能聚在一起，不相似的樣本盡可能的分開，直觀來說：簇內(nèi)高內(nèi)聚緊緊抱團，簇間低耦合老死不相往來。定義：

基于上面這四個距離，可以導(dǎo)出上面常用的評價指標(biāo)：

原型聚類

原型聚類即基于原型的聚類，原型表示模板的意思，就是通過參考一個模板向量或模板分布的方式，來完成聚類的過程。常見的K-means聚類便是基于簇中心實現(xiàn)的聚類。

K-means聚類

思想十分簡單，首先隨機指定類中心，根據(jù)樣本與類中心的遠近劃分類簇，接著重新計算類中心，迭代直至收斂。但是其中迭代的過程并不是主觀想象得出的，事實上，若將樣本的類別看作是隱變量，類中心看作樣本的分布參數(shù)，這一過程正是通過EM算法的兩步驟策略而計算出的，其根本目的是為了最小化平方誤差函數(shù)E：

E

=

∑

i

=

1

k

∑

x

∈

C

i

∣

∣

x

?

μ

i

∣

∣

2

2

E = \sum^k_{i = 1}\sum_{x\in C_i}||x - \mu_i||^2_2

E=i=1∑k?x∈Ci?∑?∣∣x?μi?∣∣22?

K-means算法的流程如下：

學(xué)習(xí)向量量化（LVQ）

LVQ也是基于原型的聚類算法，與K-means不同的是，LVQ使用樣本真實類標(biāo)記輔助聚類，首先LVQ根據(jù)樣本的類標(biāo)記，從各類中分別隨機選出一個樣本作為該類簇的原型，從而組成了一個原型向量組，接著從樣本集中隨機挑選出一個樣本，計算其與原型向量組中每個向量的距離，并選取距離最小的原型向量所在的類簇作為其的劃分結(jié)果，在與真實類標(biāo)比較：

若劃分結(jié)果正確，則對應(yīng)原型向量向這個樣本靠近一些。若劃分結(jié)果不正確，則對應(yīng)原型向量向這個樣本遠離一些。 LVQ算法流程如下：

高斯混合聚類

現(xiàn)在可以看出K-Means與LVQ都試圖以類中心作為原型指導(dǎo)聚類，高斯混合聚類則采用高斯分布來描述原型。現(xiàn)假設(shè)每個類簇中的樣本都服從一個多維高斯分布，那么空間中的樣本可以看作由

k

k

k個多維高斯分布混合而成。

對于多維高斯分布函數(shù)，其概率密度函數(shù)如下所示：

p

(

x

)

=

1

(

2

π

)

n

2

∣

∑

∣

1

2

e

?

1

2

(

x

?

μ

)

T

∑

?

1

(

x

?

μ

)

p(x) = \frac{1}{(2\pi)^\frac{n}{2}|\sum|^\frac{1}{2}}e^-\frac{1}{2}(x - \mu)^T\sum^{-1}(x - \mu)

p(x)=(2π)2n?∣∑∣21?1?e?21?(x?μ)T∑?1?(x?μ)

其中

μ

\mu

μ為高斯分布,

∑

\sum

∑ 表示協(xié)方差矩陣。可以看出一個多維高斯分布完全有這兩個參數(shù)所決定，接著定義高斯混合分布為：

α

\alpha

α稱為混合系數(shù)，這樣空間中樣本采集過程可以抽象為：先選擇一個類簇（高斯分布），在根據(jù)對應(yīng)的高斯分布的密度函數(shù)進行采樣，這時候貝葉斯公式，又能大展伸手了：

此時只需要選擇PM最大時的類簇，并將該樣本劃分到其中，看到這里，很容易發(fā)現(xiàn)，這和那個傳說中的貝葉斯分類很相似，都是通過貝葉斯公式展開的，然后計算類先驗概率和類條件概率，但遺憾的是，這里沒有真實的類標(biāo)信息，對于類條件概率，并不能像貝葉斯分類那樣通過最大似然法美好的計算出來，這里的樣本可能屬于所有類簇，這里的似然函數(shù)變?yōu)椋?/p>

可以看出，簡單的最大似然法根本無法求出所有參數(shù)，這樣PM也就沒噶法計算啦，這里就要召喚出之前的EM大算法，首先對高斯分布的參數(shù)及混合系數(shù)進行隨機初始化，計算出各個PM（即γji，第i個樣本屬于j類），再最大化似然函數(shù)（即LL（D）分別對α、u和∑求偏導(dǎo) ），對參數(shù)進行迭代更新

高斯混合聚類的算法流程如下：

密度聚類

密度聚類則是基于密度的聚類，它從樣本分布的角度來考察樣本之間的可連接性，并基于可連接性（密度可達）不斷拓展疆域（類簇）。其中最著名的便是DBSCAN算法，首先定義以下概念：

簡單來理解DBSCAN便是：找出一個核心對象所有密度可達的樣本集合形成簇。首先從數(shù)據(jù)集中任選一個核心對象A，找出所有A密度可達的樣本集合，將這些樣本形成一個密度相連的類簇，直到所有的核心對象都遍歷完。DBSCAN算法的流程如下圖所示：

層次聚類

層次聚類是一種基于樹形結(jié)構(gòu)的聚類方法，常用的是自底向上的結(jié)合策略（AGNES算法）。假設(shè)有

N

N

N個待聚類的樣本，其基本步驟是：

初始化->把每個樣本歸為一類，計算每兩個了類之間的距離，也就是樣本與樣本之間的相似度。 尋找各個類之間的最近兩個類，把它們歸為一類（這樣類的總數(shù)就少了一個） 重新計算新生成的這個類與各個舊類之間的相似度。 重復(fù)2到3直至所有樣本點都?xì)w為一類，結(jié)束。

可以看出，其中最關(guān)鍵的一步就是計算兩個類簇的相似度，這里有多種度量方法：

單鏈接：取類間最小距離。

最小距離：

d

m

i

n

(

C

i

,

C

j

)

=

m

i

n

x

∈

C

i

,

z

∈

C

j

d

i

s

t

(

x

,

z

)

最小距離：d_{min}(C_i,C_j) = min_{x\in C_i,z\in C_j}dist(x,z)

最小距離：dmin?(Ci?,Cj?)=minx∈Ci?,z∈Cj??dist(x,z) 全鏈接：取類間最大距離

最大距離：

d

m

a

x

(

C

i

,

C

j

)

=

m

a

x

x

∈

C

i

,

z

∈

C

j

d

i

s

t

(

x

,

z

)

最大距離：d_{max}(C_i,C_j) = max_{x\in C_i,z\in C_j}dist(x,z)

最大距離：dmax?(Ci?,Cj?)=maxx∈Ci?,z∈Cj??dist(x,z) 均鏈接：取類間兩兩的平均距離。

很容易，看出，單鏈接包容性極強，稍微有點曖昧都當(dāng)做是自己人啦，全連接則是堅持到底，只要存在缺點都堅決不合并，均連接則是從全局出發(fā)顧全大局，層次聚類法算法流程如下所示：

學(xué)習(xí)心得

會自己根據(jù)項目，將各種聚類算法學(xué)一學(xué)，全部將其搞定都行啦的理由與打算。 慢慢地將各種聚類算法，各種聚類度量都給其搞定，全部都給其研究透徹都行啦的理由與打算，慢慢地自己琢磨，自己斟酌好好都行啦的樣子與度量。全部將其搞定。

柚子快報邀請碼778899分享：周志華機器學(xué)習(xí)——聚類算法。

http://yzkb.51969.com/

文章鏈接