柚子快報(bào)邀請(qǐng)碼778899分享：機(jī)器學(xué)習(xí) 算法 14-聚類方法

http://yzkb.51969.com/

14 聚類方法

1. 聚類的基本概念1.1 相似度或距離1.2 類或簇1.3 類之間的距離

2. 層次聚類3. K均值聚類3.1 模型3.2 策略3.3 算法3.4 算法特性3.5 實(shí)例解釋

導(dǎo)讀：

聚類：依據(jù)樣本特征的相似度或距離，將其歸并到若干個(gè)**“類”或“簇”**的數(shù)據(jù)分析問題目的：通過得到的類或簇來發(fā)現(xiàn)數(shù)據(jù)的特點(diǎn)或?qū)?shù)據(jù)進(jìn)行處理。聚類：屬于無監(jiān)督學(xué)習(xí)，因?yàn)橹皇歉鶕?jù)樣本的相似度或距離將其進(jìn)行歸類，而類或簇事先并不知道本章主要介紹：層次聚類hierarchical clustering，k均值聚類k-means clustering。

1. 聚類的基本概念

1.1 相似度或距離

聚類的核心概念就是相似度similarity或距離distance。有多種相似度和距離的定義，且相似度直接影響聚類結(jié)果。

閔可夫斯基距離 Minkowski distance：在聚類中，可將樣本集合看作向量空間中點(diǎn)的集合，以向量空間中的距離表示樣本之間的相似度。

相似度度量方法函數(shù)Minkowski distance

d

i

j

=

(

∑

k

=

1

N

∣

x

k

i

?

x

k

j

∣

p

)

1

p

d_{ij} = (\sum_{k=1}^N{ \vert x_{ki}-x_{kj} \vert }^p )^{\frac{1}{p}}

dij?=(∑k=1N?∣xki??xkj?∣p)p1?Euclidean distance

d

i

j

=

(

∑

k

=

1

N

∣

x

k

i

?

x

k

j

∣

2

)

1

2

d_{ij} = (\sum_{k=1}^N{ \vert x_{ki}-x_{kj} \vert }^2 )^{\frac{1}{2}}

dij?=(∑k=1N?∣xki??xkj?∣2)21?Manhattan distance

d

i

j

=

(

∑

k

=

1

N

∣

x

k

i

?

x

k

j

∣

)

d_{ij} = (\sum_{k=1}^N{ \vert x_{ki}-x_{kj} \vert } )

dij?=(∑k=1N?∣xki??xkj?∣)Chebyshev distance

d

i

j

=

(

m

a

x

k

∣

x

k

i

?

x

k

j

∣

)

d_{ij} = ( \underset{k}{max} \vert x_{ki}-x_{kj} \vert )

dij?=(kmax?∣xki??xkj?∣)

Minkowski距離就是

L

P

L_{P}

LP?范數(shù)

(

P

>

=

1

)

(P>=1)

(P>=1)，而 Manhattan 距離、Euclidean距離、Chebyshev距離分別對(duì)應(yīng)

P

=

1

,

2

,

+

∞

P=1,2,+\infty

P=1,2,+∞時(shí)的情形。

馬哈拉諾比斯距離 Mahalanobis distance:簡稱馬氏距離，考慮各個(gè)分量（特征）之間的相關(guān)性，與各個(gè)分量的尺度無關(guān)，距離越大，相似度越小。S為協(xié)方差矩陣。

d

i

j

=

[

(

x

i

?

x

j

)

T

S

?

1

(

x

i

?

x

j

)

]

1

2

d_{ij}=[(x_i-x_j)^TS^{-1}(x_i-x_j)]^{\frac{1}{2}}

dij?=[(xi??xj?)TS?1(xi??xj?)]21? 當(dāng)S為單位矩陣時(shí)，樣本數(shù)據(jù)各個(gè)分量互相獨(dú)立，且各個(gè)分量的方差為1。

相關(guān)系數(shù)correlation coefficient：可以表達(dá)樣本之間的相似度,相關(guān)系數(shù)的絕對(duì)值越接近1，表示樣本越相似。

r

i

j

=

∑

k

=

1

m

(

x

k

i

?

x

ˉ

i

)

(

x

k

j

?

x

ˉ

j

)

[

∑

k

=

1

m

(

x

k

i

?

x

ˉ

i

)

2

∑

k

=

1

m

(

x

k

j

?

x

ˉ

j

)

2

]

1

2

r_{ij} = \frac{ \sum_{k=1}^m(x_{ki} - \bar{x}_i)(x_{kj} - \bar{x}_j) }{[ \sum_{k=1}^m(x_{ki} - \bar{x}_i)^2 \sum_{k=1}^m(x_{kj} - \bar{x}_j)^2 ]^\frac{1}{2} }

rij?=[∑k=1m?(xki??xˉi?)2∑k=1m?(xkj??xˉj?)2]21?∑k=1m?(xki??xˉi?)(xkj??xˉj?)?

夾角余弦 cosine：可以表達(dá)樣本相似度，夾角余弦越接近1，表示樣本越相似。

s

i

j

=

∑

k

=

1

m

x

k

i

x

k

j

[

∑

k

=

1

m

x

k

i

2

∑

k

=

1

m

x

k

j

2

]

1

2

s_{ij} = \frac{ \sum_{k=1}^m x_{ki}x_{kj} }{[ \sum_{k=1}^mx_{ki}^2 \sum_{k=1}^mx_{kj}^2]^\frac{1}{2}}

sij?=[∑k=1m?xki2?∑k=1m?xkj2?]21?∑k=1m?xki?xkj??

選取合適的相似度函數(shù)：如上圖所示：不同的函數(shù)，聚類的結(jié)果不同從距離的角度看，A和B比A和C更相似從相關(guān)系數(shù)的角度看，A和C比A和B更相似

1.2 類或簇

聚類得到的類或簇，本質(zhì)是樣本的子集。根據(jù)子集有無交集分為硬聚類（hard clustering）和軟聚類（soft clustering）。類的特征：

類的均值，中心

x

ˉ

G

\bar{x}_G

xˉG? ：

x

ˉ

G

=

1

n

G

∑

i

=

1

n

G

x

i

\bar{x}_G = \frac{1}{n_G} \sum_{i=1}^{n_G} x_i

xˉG?=nG?1?∑i=1nG??xi?類的直徑：

D

G

=

m

a

x

x

i

,

x

j

d

i

j

D_G = \underset{x_i,x_j}{max} d_{ij}

DG?=xi?,xj?max?dij?類的樣本散布矩陣scatter matrix：

A

G

=

∑

i

=

1

n

G

(

x

i

?

x

ˉ

G

)

(

x

i

?

x

ˉ

G

)

T

A_G = \sum_{i=1}^{n_G}(x_i- \bar{x}_G)(x_i - \bar{x}_G)^T

AG?=∑i=1nG??(xi??xˉG?)(xi??xˉG?)T樣本協(xié)方差矩陣

S

G

S_G

SG?:

S

G

=

1

m

?

1

A

G

=

1

m

?

1

∑

i

=

1

n

G

(

x

i

?

x

ˉ

G

)

(

x

i

?

x

ˉ

G

)

T

S_G = \frac{1}{m-1}A_G = \frac{1}{m-1} \sum_{i=1}^{n_G}(x_i- \bar{x}_G)(x_i - \bar{x}_G)^T

SG?=m?11?AG?=m?11?∑i=1nG??(xi??xˉG?)(xi??xˉG?)T

1.3 類之間的距離

最短距離或單連接single linkage:定義類

G

p

G_p

Gp?的樣本與

G

q

G_q

Gq?的樣本之間最短的距離為兩類的距離最長距離或完全連接complete linkage:定義最長距離為兩類的距離中心距離:定義類中心之間的距離為兩類距離平均距離:定義類

G

p

G_p

Gp?與類

G

q

G_q

Gq?任意兩樣本之間的距離平均值為兩類的距離

2. 層次聚類

層次聚類：假設(shè)類別之間 存在層次結(jié)構(gòu)，將樣本聚到層次化的類中。層次聚類屬于硬聚類，分為以下兩類：

聚合（agglomerative）或自下而上（bottom-up）聚類分裂（divisive）或自上而下（top-down）聚類 聚合聚類：

將每個(gè)樣本各自分到一個(gè)類之后將相距最近的兩類合并，建立一個(gè)新的類，重復(fù)此操作直到滿足停止條件得到層次化的類別 分裂聚類：

將所有樣本分到一個(gè)類將已有類中相距最遠(yuǎn)的樣本分到兩個(gè)新的類，重復(fù)上一步直到滿足停止條件得到層次化的類別 聚合聚類的步驟：

對(duì)給定的樣本集合，開始將每個(gè)樣本分到一個(gè)類按照一定規(guī)則，例如 類間距離最小，將最滿足規(guī)則條件的兩個(gè)類進(jìn)行合并反復(fù)上一步，每次減少一個(gè)類，直到滿足停止條件，如所有樣本聚為一類 聚合聚類三要素：

距離或相似度（閔可夫斯基距離、馬哈拉諾比斯距離、相關(guān)系數(shù)、夾角余弦）合并規(guī)則（類間距離最小，可以是最短距離、最長距離、中心距離、平均距離）停止條件（類的個(gè)數(shù)達(dá)到閾值（極端情況類的個(gè)數(shù)是1）、類的直徑超過閾值） 算法14.1： 輸入：

n

n

n個(gè)樣本組成的集合

X

X

X 輸出：對(duì)樣本的一個(gè)層次化聚類

C

C

C

計(jì)算

n

n

n個(gè)樣本兩兩之間的歐氏距離

d

i

j

{d_{ij}}

dij?，記作矩陣

D

=

[

d

i

j

]

n

×

n

D=[d_{ij}]_{n\times n}

D=[dij?]n×n?構(gòu)造

n

n

n個(gè)類，每個(gè)類只包含一個(gè)樣本合并類間距離最小的兩個(gè)類，其中最短距離為類間距離，構(gòu)建一個(gè)新類。計(jì)算新類與當(dāng)前各類之間的距離。如果類的個(gè)數(shù)是1， 終止計(jì)算，否則回到步驟3。 算法復(fù)雜度比較為

O

(

n

3

m

)

O(n^3m)

O(n3m)

3. K均值聚類

k均值聚類：是基于樣本集合劃分的聚類算法

將樣本集合劃分為 k 個(gè)子集，構(gòu)成 k 個(gè)類將 n 個(gè)樣本分到 k 個(gè)類中，每個(gè)樣本到其所屬類的中心的距離最小每個(gè)樣本只能屬于一個(gè)類，是硬聚類

3.1 模型

K均值聚類的目標(biāo)：是將n個(gè)樣本分到k個(gè)不同的類或簇中

3.2 策略

策略：通過損失函數(shù)的最小化選取最優(yōu)的劃分或函數(shù)C*

樣本距離：歐式距離平方

d

(

x

i

,

x

j

)

=

∑

k

=

1

m

(

x

k

i

?

x

k

j

)

2

d(x_i,x_j) = \sum_{k=1}^m (x_{ki} - x_{kj} )^2

d(xi?,xj?)=∑k=1m?(xki??xkj?)2損失函數(shù)：樣本與所屬類的中心之間的距離的總和：

W

(

C

)

=

∑

l

=

1

k

∑

C

(

i

)

=

l

∥

x

i

?

x

ˉ

l

∥

2

W(C) = \sum_{l=1}^k \sum_{C(i)=l} \left \| x_i - \bar{x}_l \right \|^2

W(C)=∑l=1k?∑C(i)=l?∥xi??xˉl?∥2K均值聚類就是求解最優(yōu)化問題：

C

?

=

a

r

g

m

i

n

C

W

(

C

)

=

a

r

g

m

i

n

C

∑

l

=

1

k

∑

C

(

i

)

=

l

∥

x

i

?

x

ˉ

l

∥

2

C^* = \underset{C}{argmin} W(C) = \underset{C}{argmin} \sum_{l=1}^k \sum_{C(i)=l} \left \| x_i - \bar{x}_l \right \|^2

C?=Cargmin?W(C)=Cargmin?∑l=1k?∑C(i)=l?∥xi??xˉl?∥2

3.3 算法

k均值聚類的算法是迭代的過程，每次迭代包括兩個(gè)步驟：

首先隨機(jī)選擇 k 個(gè)類的中心（選 k 個(gè)樣本），將其余樣本逐個(gè)指派到與其最近的中心的類中，得到一個(gè)聚類結(jié)果 然后更新每個(gè)類的樣本的均值，作為類的新的中心 重復(fù)以上步驟，直到收斂 算法14.2： 輸入：

n

n

n個(gè)樣本的集合

X

X

X 輸出：樣本集合的聚類

C

?

C^*

C?

初始化。對(duì)樣本進(jìn)行聚類。計(jì)算類的中心。如果迭代收斂或符合停止條件，輸出

C

?

=

C

(

t

)

C^*=C^{(t)}

C?=C(t)

3.4 算法特性

1，總體特點(diǎn)

基于劃分的聚類方法類別數(shù) k 事先指定以歐氏距離平方表示樣本之間的距離以中心或樣本的均值表示類別以 樣本和其所屬類的中心 之間的 距離的總和 為最優(yōu)化目標(biāo)函數(shù)得到的類別是平坦的、非層次化的是迭代算法，不能保證得到全局最優(yōu) 2，收斂性

k均值聚類屬于啟發(fā)式方法，不能保證收斂到全局最優(yōu)初始中心的選擇會(huì)直接影響聚類結(jié)果類中心在聚類的過程中會(huì)發(fā)生移動(dòng)，但是往往不會(huì)移動(dòng)太大，因?yàn)樵诿恳徊剑瑯颖颈环值脚c其最近的中心的類中 3，初始類的選擇

選擇不同的初始中心，會(huì)得到不同的聚類結(jié)果初始中心的選擇，比如 可以用層次聚類對(duì)樣本進(jìn)行聚類，得到k個(gè)類時(shí)停止。然后從每個(gè)類中選取一個(gè)與中心距離最近的點(diǎn) 4， 類別數(shù)k的選擇 k 值需要預(yù)先指定，而在實(shí)際應(yīng)用中最優(yōu)k值是不知道的 解決方法：嘗試不同的k值，檢驗(yàn)聚類的質(zhì)量，推測(cè)最優(yōu)的k值 聚類結(jié)果的質(zhì)量：可以用類的平均直徑來衡量 一般地，類別數(shù)變小時(shí)，平均直徑會(huì)增加；類別數(shù)變大超過某個(gè)值以后，平均直徑會(huì)不變；而這個(gè)值正是最優(yōu)的k值 可以采用二分查找，快速找最優(yōu)的k值

3.5 實(shí)例解釋

k-means，下左圖是原始數(shù)據(jù)集，通過觀察發(fā)現(xiàn)大致可以分為4類，所以取k=4，測(cè)試數(shù)據(jù)效果如下右圖所示。 當(dāng)時(shí)初始質(zhì)心點(diǎn)取值不同的時(shí)候，最終的聚類效果也不一樣，接下來我們看一個(gè)具體的實(shí)例： 這個(gè)例子當(dāng)中，下方的數(shù)據(jù)應(yīng)該歸為一類，而上方的數(shù)據(jù)應(yīng)該歸為兩類，這是由于初始質(zhì)心點(diǎn)選取的不合理造成的誤分。而k值的選取對(duì)結(jié)果的影響也非常大，同樣取上圖中數(shù)據(jù)集，取k=2,3,4，可以得到下面的聚類結(jié)果：

因此，k-means算法：

需要提前確定值對(duì)初始質(zhì)心點(diǎn)敏感對(duì)異常數(shù)據(jù)敏感

更多聚類方法可參考： 參考： 李航，統(tǒng)計(jì)學(xué)習(xí)方法第二版 常用聚類算法：https://zhuanlan.zhihu.com/p/104355127 層次聚類算法：https://zhuanlan.zhihu.com/p/363879425 sklearn介紹的10中聚類算法：https://scikit-learn.org/stable/modules/clustering.html

柚子快報(bào)邀請(qǐng)碼778899分享：機(jī)器學(xué)習(xí) 算法 14-聚類方法

http://yzkb.51969.com/

文章鏈接