柚子快報(bào)激活碼778899分享：算法 數(shù)據(jù)挖掘（六） 層次聚類(lèi)

http://yzkb.51969.com/

數(shù)據(jù)挖掘（六） 層次聚類(lèi)

1.層次聚類(lèi)簡(jiǎn)介

層次聚類(lèi)算法(Hierarchical Clustering)將數(shù)據(jù)集劃分為一層一層的clusters，后面一層生成的clusters基于前面一層的結(jié)果。層次聚類(lèi)算法一般分為兩類(lèi)：

Divisive 層次聚類(lèi)：又稱(chēng)自頂向下（top-down）的層次聚類(lèi)，最開(kāi)始所有的對(duì)象均屬于一個(gè)cluster，每次按一定的準(zhǔn)則將某個(gè)cluster 劃分為多個(gè)cluster，如此往復(fù)，直至每個(gè)對(duì)象均是一個(gè)cluster。Agglomerative 層次聚類(lèi)：又稱(chēng)自底向上（bottom-up）的層次聚類(lèi)，每一個(gè)對(duì)象最開(kāi)始都是一個(gè)cluster，每次按一定的準(zhǔn)則將最相近的兩個(gè)cluster合并生成一個(gè)新的cluster，如此往復(fù)，直至最終所有的對(duì)象都屬于一個(gè)cluster。

下圖直觀的給出了層次聚類(lèi)的思想以及以上兩種聚類(lèi)策略的異同：

;

層次聚類(lèi)算法是一種貪心算法（greedy algorithm），因其每一次合并或劃分都是基于某種局部最優(yōu)的選擇。

2. 自頂向下的層次聚類(lèi)算法(Divisive)

2.1 Hierarchical K-means算法

Hierarchical K-means算法是“自頂向下”的層次聚類(lèi)算法，用到了基于劃分的聚類(lèi)算法那K-means，算法思路如下：

首先，把原始數(shù)據(jù)集放到一個(gè)簇C，這個(gè)簇形成了層次結(jié)構(gòu)的最頂層 使用K-means算法把簇C劃分成指定的K個(gè)子簇，形成一個(gè)新的層 對(duì)于步驟2所生成的K個(gè)簇，遞歸使用K-means算法劃分成更小的子簇，直到每個(gè)簇不能再劃分（只包含一個(gè)數(shù)據(jù)對(duì)象）或者滿(mǎn)足設(shè)定的終止條件。

如下圖，展示了一組數(shù)據(jù)進(jìn)行了二次K-means算法的過(guò)程：

;

Hierarchical K-means算法一個(gè)很大的問(wèn)題是，一旦兩個(gè)點(diǎn)在最開(kāi)始被劃分到了不同的簇，即使這兩個(gè)點(diǎn)距離很近，在后面的過(guò)程中也不會(huì)被聚類(lèi)到一起。

;

對(duì)于以上的例子，紅色橢圓框中的對(duì)象聚類(lèi)成一個(gè)簇可能是更優(yōu)的聚類(lèi)結(jié)果，但是由于橙色對(duì)象和綠色對(duì)象在第一次K-means就被劃分到不同的簇，之后也不再可能被聚類(lèi)到同一個(gè)簇。

Bisecting k-means聚類(lèi)算法，即二分k均值算法，是分層聚類(lèi)（Hierarchical clustering）的一種。更多關(guān)于二分k均值法，可以查看聚類(lèi)算法之K-Means。

3. 自底向上的層次聚類(lèi)算法(Agglomerative)

層次聚類(lèi)的合并算法通過(guò)計(jì)算兩類(lèi)數(shù)據(jù)點(diǎn)間的相似性，對(duì)所有數(shù)據(jù)點(diǎn)中最為相似的兩個(gè)數(shù)據(jù)點(diǎn)進(jìn)行組合，并反復(fù)迭代這一過(guò)程。簡(jiǎn)單的說(shuō)層次聚類(lèi)的合并算法是通過(guò)計(jì)算每一個(gè)類(lèi)別的數(shù)據(jù)點(diǎn)與所有數(shù)據(jù)點(diǎn)之間的距離來(lái)確定它們之間的相似性，距離越小，相似度越高。并將距離最近的兩個(gè)數(shù)據(jù)點(diǎn)或類(lèi)別進(jìn)行組合，生成聚類(lèi)樹(shù)。

;

相比于Hierarchical K-means算法存在的問(wèn)題，Agglomerative Clustering算法能夠保證距離近的對(duì)象能夠被聚類(lèi)到一個(gè)簇中，該算法采用的“自底向上”聚類(lèi)的思路。

3.1 Agglomerative算法示例

對(duì)于如下數(shù)據(jù)：

;

1、 將A到F六個(gè)點(diǎn)，分別生成6個(gè)簇 2、 找到當(dāng)前簇中距離最短的兩個(gè)點(diǎn)，這里我們使用單連鎖的方式來(lái)計(jì)算距離，發(fā)現(xiàn)A點(diǎn)和B點(diǎn)距離最短，將A和B組成一個(gè)新的簇，此時(shí)簇列表中包含五個(gè)簇，分別是{A，B}，{C}，{D}，{E}，{F}，如下圖所示：

;

3、重復(fù)步驟2、發(fā)現(xiàn){C}和{D}的距離最短，連接之，然后是簇{C,D}和簇{E}距離最短，依次類(lèi)推，直到最后只剩下一個(gè)簇，得到如下所示的示意圖：

;

4、此時(shí)原始數(shù)據(jù)的聚類(lèi)關(guān)系是按照層次來(lái)組織的，選取一個(gè)簇間距離的閾值，可以得到一個(gè)聚類(lèi)結(jié)果，比如在如下紅色虛線的閾值下，數(shù)據(jù)被劃分為兩個(gè)簇：簇{A，B，C，D，E}和簇{F}

;

Agglomerative聚類(lèi)算法的優(yōu)點(diǎn)是能夠根據(jù)需要在不同的尺度上展示對(duì)應(yīng)的聚類(lèi)結(jié)果，缺點(diǎn)同Hierarchical K-means算法一樣，一旦兩個(gè)距離相近的點(diǎn)被劃分到不同的簇，之后也不再可能被聚類(lèi)到同一個(gè)簇，即無(wú)法撤銷(xiāo)先前步驟的工作。另外，Agglomerative性能較低，并且因?yàn)榫垲?lèi)層次信息需要存儲(chǔ)在內(nèi)存中，內(nèi)存消耗大，不適用于大量級(jí)的數(shù)據(jù)聚類(lèi)。

3.2 對(duì)象之間的距離衡量

衡量?jī)蓚€(gè)對(duì)象之間的距離的方式有多種，對(duì)于數(shù)值類(lèi)型（Numerical）的數(shù)據(jù)，常用的距離衡量準(zhǔn)則有 Euclidean 距離、Manhattan 距離、Chebyshev 距離、Minkowski 距離等等。

3.3 Cluster 之間的距離衡量

除了需要衡量對(duì)象之間的距離之外，層次聚類(lèi)算法還需要衡量cluster之間的距離，常見(jiàn)的cluster之間的衡量方法有 Single-link 方法、Complete-link 方法、UPGMA（Unweighted Pair Group Method using arithmetic Averages）方法、WPGMA（Weighted Pair Group Method using arithmetic Averages）方法、Centroid 方法（又稱(chēng) UPGMC，Unweighted Pair Group Method using Centroids）、Median 方法（又稱(chēng) WPGMC，weighted Pair Group Method using Centroids）、Ward 方法。前面四種方法是基于圖的，因?yàn)樵谶@些方法里面，cluster是由樣本點(diǎn)或一些子cluster（這些樣本點(diǎn)或子cluster之間的距離關(guān)系被記錄下來(lái)，可認(rèn)為是圖的連通邊）所表示的；后三種方法是基于幾何方法的（因而其對(duì)象間的距離計(jì)算方式一般選用 Euclidean 距離），因?yàn)樗鼈兌际怯靡粋€(gè)中心點(diǎn)來(lái)代表一個(gè)cluster。

假設(shè)Ci和Cj為兩個(gè)cluster，則前四種方法定義的Ci和Cj之間的距離如下表所示：

;

簡(jiǎn)單的理解：

Single Linkage：方法是將兩個(gè)組合數(shù)據(jù)點(diǎn)中距離最近的兩個(gè)數(shù)據(jù)點(diǎn)間的距離作為這兩個(gè)組合數(shù)據(jù)點(diǎn)的距離。這種方法容易受到極端值的影響。兩個(gè)很相似的組合數(shù)據(jù)點(diǎn)可能由于其中的某個(gè)極端的數(shù)據(jù)點(diǎn)距離較近而組合在一起。Complete Linkage：Complete Linkage的計(jì)算方法與Single Linkage相反，將兩個(gè)組合數(shù)據(jù)點(diǎn)中距離最遠(yuǎn)的兩個(gè)數(shù)據(jù)點(diǎn)間的距離作為這兩個(gè)組合數(shù)據(jù)點(diǎn)的距離。Complete Linkage的問(wèn)題也與Single Linkage相反，兩個(gè)不相似的組合數(shù)據(jù)點(diǎn)可能由于其中的極端值距離較遠(yuǎn)而無(wú)法組合在一起。Average Linkage：Average Linkage的計(jì)算方法是計(jì)算兩個(gè)組合數(shù)據(jù)點(diǎn)中的每個(gè)數(shù)據(jù)點(diǎn)與其他所有數(shù)據(jù)點(diǎn)的距離。將所有距離的均值作為兩個(gè)組合數(shù)據(jù)點(diǎn)間的距離。這種方法計(jì)算量比較大，但結(jié)果比前兩種方法更合理。

;

其中 Single-link 定義兩個(gè) cluster 之間的距離為兩個(gè) cluster 之間距離最近的兩個(gè)對(duì)象間的距離，這樣在聚類(lèi)的過(guò)程中就可能出現(xiàn)鏈?zhǔn)叫?yīng)，即有可能聚出長(zhǎng)條形狀的 cluster；而 Complete-link 則定義兩個(gè) cluster 之間的距離為兩個(gè) cluster 之間距離最遠(yuǎn)的兩個(gè)對(duì)象間的距離，這樣雖然避免了鏈?zhǔn)叫?yīng)，但其對(duì)異常樣本點(diǎn)（不符合數(shù)據(jù)集的整體分布的噪聲點(diǎn)）卻非常敏感，容易產(chǎn)生不合理的聚類(lèi)；UPGMA 正好是 Single-link 和 Complete-link 的一個(gè)折中，其定義兩個(gè) cluster 之間的距離為兩個(gè) cluster 之間兩個(gè)對(duì)象間的距離的平均值；而 WPGMA 則計(jì)算的是兩個(gè) cluster 之間兩個(gè)對(duì)象之間的距離的加權(quán)平均值，加權(quán)的目的是為了使兩個(gè) cluster 對(duì)距離的計(jì)算的影響在同一層次上，而不受 cluster 大小的影響（其計(jì)算方法這里沒(méi)有給出，因?yàn)樵谶\(yùn)行層次聚類(lèi)算法時(shí)，我們并不會(huì)直接通過(guò)樣本點(diǎn)之間的距離之間計(jì)算兩個(gè) cluster 之間的距離，而是通過(guò)已有的 cluster 之間的距離來(lái)計(jì)算合并后的新的 cluster 和剩余cluster 之間的距離，這種計(jì)算方法將由下一部分中的 Lance-Williams 方法給出）。

4.實(shí)驗(yàn)：BIRCH算法聚類(lèi)

import numpy as np

import matplotlib.pyplot as plt

from sklearn.datasets import make_blobs

from sklearn.cluster import Birch

# X為樣本特征，Y為樣本簇類(lèi)別，共1000個(gè)樣本，每個(gè)樣本2個(gè)特征，共4個(gè)簇，簇中心在[-1,-1], [0,0],[1,1], [2,2]

X, y = make_blobs(n_samples=1000, n_features=2,

centers=[[-1,-1], [0,0], [1,1], [2,2]],

cluster_std=[0.4, 0.3, 0.4, 0.3],

random_state =9)

plt.scatter(X[:, 0], X[:, 1])

birch = Birch(n_clusters = None)#設(shè)置birch函數(shù),n_clusters取值分別為None和4

y_pred = birch.fit_predict(X)##訓(xùn)練數(shù)據(jù)

plt.scatter(X[:, 0], X[:, 1], c=y_pred)

plt.show()

柚子快報(bào)激活碼778899分享：算法 數(shù)據(jù)挖掘（六） 層次聚類(lèi)

http://yzkb.51969.com/

參考鏈接