柚子快報邀請碼778899分享：機器學習 算法 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 實例解釋

導讀：

聚類：依據(jù)樣本特征的相似度或距離，將其歸并到若干個**“類”或“簇”**的數(shù)據(jù)分析問題目的：通過得到的類或簇來發(fā)現(xiàn)數(shù)據(jù)的特點或對數(shù)據(jù)進行處理。聚類：屬于無監(jiān)督學習，因為只是根據(jù)樣本的相似度或距離將其進行歸類，而類或簇事先并不知道本章主要介紹：層次聚類hierarchical clustering，k均值聚類k-means clustering。

1. 聚類的基本概念

1.1 相似度或距離

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

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

相似度度量方法函數(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距離分別對應

P

=

1

,

2

,

+

∞

P=1,2,+\infty

P=1,2,+∞時的情形。

馬哈拉諾比斯距離 Mahalanobis distance:簡稱馬氏距離，考慮各個分量（特征）之間的相關性，與各個分量的尺度無關，距離越大，相似度越小。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? 當S為單位矩陣時，樣本數(shù)據(jù)各個分量互相獨立，且各個分量的方差為1。

相關系數(shù)correlation coefficient：可以表達樣本之間的相似度,相關系數(shù)的絕對值越接近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：可以表達樣本相似度，夾角余弦越接近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ù)，聚類的結果不同從距離的角度看，A和B比A和C更相似從相關系數(shù)的角度看，A和C比A和B更相似

1.2 類或簇

聚類得到的類或簇，本質是樣本的子集。根據(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. 層次聚類

層次聚類：假設類別之間 存在層次結構，將樣本聚到層次化的類中。層次聚類屬于硬聚類，分為以下兩類：

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

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

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

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

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

n

n

n個樣本組成的集合

X

X

X 輸出：對樣本的一個層次化聚類

C

C

C

計算

n

n

n個樣本兩兩之間的歐氏距離

d

i

j

{d_{ij}}

dij?，記作矩陣

D

=

[

d

i

j

]

n

×

n

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

D=[dij?]n×n?構造

n

n

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

O

(

n

3

m

)

O(n^3m)

O(n3m)

3. K均值聚類

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

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

3.1 模型

K均值聚類的目標：是將n個樣本分到k個不同的類或簇中

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均值聚類的算法是迭代的過程，每次迭代包括兩個步驟：

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

n

n

n個樣本的集合

X

X

X 輸出：樣本集合的聚類

C

?

C^*

C?

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

C

?

=

C

(

t

)

C^*=C^{(t)}

C?=C(t)

3.4 算法特性

1，總體特點

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

k均值聚類屬于啟發(fā)式方法，不能保證收斂到全局最優(yōu)初始中心的選擇會直接影響聚類結果類中心在聚類的過程中會發(fā)生移動，但是往往不會移動太大，因為在每一步，樣本被分到與其最近的中心的類中 3，初始類的選擇

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

3.5 實例解釋

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

因此，k-means算法：

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

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

柚子快報邀請碼778899分享：機器學習 算法 14-聚類方法

http://yzkb.51969.com/

文章鏈接