一文讀懂層次聚類(Python代碼)
本篇想和大家介紹下層次聚類，先通過一個(gè)簡單的例子介紹它的基本理論，然后再用一個(gè)實(shí)戰(zhàn)案例Python代碼實(shí)現(xiàn)聚類效果。
首先要說，聚類屬于機(jī)器學(xué)習(xí)的無監(jiān)督學(xué)習(xí)，而且也分很多種方法，比如大家熟知的有K-means。層次聚類也是聚類中的一種，也很常用。下面我先簡單回顧一下K-means的基本原理，然后慢慢引出層次聚類的定義和分層步驟，這樣更有助于大家理解。
層次聚類和K-means有什么不同？
K-means?工作原理可以簡要概述為：
- 決定簇?cái)?shù)（k）
- 從數(shù)據(jù)中隨機(jī)選取 k 個(gè)點(diǎn)作為質(zhì)心
- 將所有點(diǎn)分配到最近的聚類質(zhì)心
- 計(jì)算新形成的簇的質(zhì)心
- 重復(fù)步驟 3 和 4
這是一個(gè)迭代過程，直到新形成的簇的質(zhì)心不變，或者達(dá)到最大迭代次數(shù)。
但是?K-means?是存在一些缺點(diǎn)的，我們必須在算法開始前就決定簇?cái)?shù)?K?的數(shù)量，但實(shí)際我們并不知道應(yīng)該有多少個(gè)簇，所以一般都是根據(jù)自己的理解先設(shè)定一個(gè)值，這就可能導(dǎo)致我們的理解和實(shí)際情況存在一些偏差。
層次聚類完全不同，它不需要我們開始的時(shí)候指定簇?cái)?shù)，而是先完整的形成整個(gè)層次聚類后，通過決定合適的距離，自動(dòng)就可以找到對(duì)應(yīng)的簇?cái)?shù)和聚類。
什么是層次聚類？
下面我們由淺及深的介紹什么是層次聚類，先來一個(gè)簡單的例子。
假設(shè)我們有以下幾點(diǎn)，我們想將它們分組：
我們可以將這些點(diǎn)中的每一個(gè)分配給一個(gè)單獨(dú)的簇，就是4個(gè)簇（4種顏色）：
然后基于這些簇的相似性（距離），將最相似的（距離最近的）點(diǎn)組合在一起并重復(fù)這個(gè)過程，直到只剩下一個(gè)集群：
上面本質(zhì)上就是在構(gòu)建一個(gè)層次結(jié)構(gòu)。先了解到這里，后面我們?cè)敿?xì)介紹它的分層步驟。
層次聚類的類型
主要有兩種類型的層次聚類：
- 凝聚層次聚類
- 分裂層次聚類
凝聚層次聚類
先讓所有點(diǎn)分別成為一個(gè)單獨(dú)的簇，然后通過相似性不斷組合，直到最后只有一個(gè)簇為止，這就是凝聚層次聚類的過程，和我們上面剛剛說的一致。
分裂層次聚類
分裂層次聚類正好反過來，它是從單個(gè)集群開始逐步分裂，直到無法分裂，即每個(gè)點(diǎn)都是一個(gè)簇。
所以無論是 10、100、1000 個(gè)數(shù)據(jù)點(diǎn)都不重要，這些點(diǎn)在開始的時(shí)候都屬于同一個(gè)簇：
現(xiàn)在，在每次迭代中拆分簇中相隔最遠(yuǎn)的兩點(diǎn)，并重復(fù)這個(gè)過程，直到每個(gè)簇只包含一個(gè)點(diǎn)：
上面的過程就是分裂層次聚類。
執(zhí)行層次聚類的步驟
上面已經(jīng)說了層次聚類的大概過程，那關(guān)鍵的來了，如何確定點(diǎn)和點(diǎn)的相似性呢？
這是聚類中最重要的問題之一了，一般計(jì)算相似度的方法是：計(jì)算這些簇的質(zhì)心之間的距離。距離最小的點(diǎn)稱為相似點(diǎn)，我們可以合并它們，也可以將其稱為基于距離的算法。
另外在層次聚類中，還有一個(gè)稱為鄰近矩陣的概念，它存儲(chǔ)了每個(gè)點(diǎn)之間的距離。下面我們通過一個(gè)例子來理解如何計(jì)算相似度、鄰近矩陣、以及層次聚類的具體步驟。
案例介紹
假設(shè)一位老師想要將學(xué)生分成不同的組?，F(xiàn)在有每個(gè)學(xué)生在作業(yè)中的分?jǐn)?shù)，想根據(jù)這些分?jǐn)?shù)將他們分成幾組。關(guān)于擁有多少組，這里沒有固定的目標(biāo)。由于老師不知道應(yīng)該將哪種類型的學(xué)生分配到哪個(gè)組，因此不能作為監(jiān)督學(xué)習(xí)問題來解決。下面，我們將嘗試應(yīng)用層次聚類將學(xué)生分成不同的組。
下面是個(gè)5名學(xué)生的成績：
創(chuàng)建鄰近矩陣
首先，我們要?jiǎng)?chuàng)建一個(gè)鄰近矩陣，它儲(chǔ)存了每個(gè)點(diǎn)兩兩之間的距離，因此可以得到一個(gè)形狀為 n X n 的方陣。
這個(gè)案例中，可以得到以下 5 x 5 的鄰近矩陣：
矩陣?yán)镉袃牲c(diǎn)需要注意下：
- 矩陣的對(duì)角元素始終為 0，因?yàn)辄c(diǎn)與其自身的距離始終為 0
- 使用歐幾里得距離公式來計(jì)算非對(duì)角元素的距離
比如，我們要計(jì)算點(diǎn) 1 和 2 之間的距離，計(jì)算公式為：
同理，按此計(jì)算方法完成后填充鄰近矩陣其余元素。
執(zhí)行層次聚類
這里使用凝聚層次聚類來實(shí)現(xiàn)。
步驟 1：首先，我們將所有點(diǎn)分配成單個(gè)簇：
這里不同的顏色代表不同的簇，我們數(shù)據(jù)中的 5 個(gè)點(diǎn)，即有 5 個(gè)不同的簇。
步驟2：接下來，我們需要查找鄰近矩陣中的最小距離并合并距離最小的點(diǎn)。然后我們更新鄰近矩陣：
最小距離是 3，因此我們將合并點(diǎn) 1 和 2：
讓我們看看更新的集群并相應(yīng)地更新鄰近矩陣：
更新之后，我們?nèi)×?、2 兩個(gè)點(diǎn)中值 (7, 10) 最大的來替換這個(gè)簇的值。當(dāng)然除了最大值之外，我們還可以取最小值或平均值。然后，我們將再次計(jì)算這些簇的鄰近矩陣：
第 3 步：重復(fù)第 2 步，直到只剩下一個(gè)簇。
重復(fù)所有的步驟后，我們將得到如下所示的合并的聚類：
這就是凝聚層次聚類的工作原理。但問題是我們?nèi)匀徊恢涝摲謳捉M？是2、3、還是4組呢？
下面開始介紹如何選擇聚類數(shù)。
如何選擇聚類數(shù)？
為了獲得層次聚類的簇?cái)?shù)，我們使用了一個(gè)概念，叫作樹狀圖。
通過樹狀圖，我們可以更方便的選出聚類的簇?cái)?shù)。
回到上面的例子。當(dāng)我們合并兩個(gè)簇時(shí)，樹狀圖會(huì)相應(yīng)地記錄這些簇之間的距離并以圖形形式表示。下面這個(gè)是樹狀圖的原始狀態(tài)，橫坐標(biāo)記錄了每個(gè)點(diǎn)的標(biāo)記，縱軸記錄了點(diǎn)和點(diǎn)之間的距離：
當(dāng)合并兩個(gè)簇時(shí)，將會(huì)在樹狀圖中連接起來，連接的高度就是點(diǎn)之間的距離。下面是我們剛剛層次聚類的過程。
然后開始對(duì)上面的過程進(jìn)行樹狀圖的繪制。從合并樣本 1 和 2 開始，這兩個(gè)樣本之間的距離為 3。
可以看到已經(jīng)合并了 1 和 2。垂直線代表 1 和 2 的距離。同理，按照層次聚類過程繪制合并簇類的所有步驟，最后得到了這樣的樹狀圖：
通過樹狀圖，我們可以清楚地形象化層次聚類的步驟。樹狀圖中垂直線的距離越遠(yuǎn)代表簇之間的距離越大。
有了這個(gè)樹狀圖，我們決定簇類數(shù)就方便多了。
現(xiàn)在我們可以設(shè)置一個(gè)閾值距離，繪制一條水平線。比如我們將閾值設(shè)置為 12，并繪制一條水平線，如下：
從交點(diǎn)中可以看到，聚類的數(shù)量就是與閾值水平線與垂直線相交的數(shù)量（紅線與 2 條垂直線相交，我們將有 2 個(gè)簇）。與橫坐標(biāo)相對(duì)應(yīng)的，一個(gè)簇將有一個(gè)樣本集合為 (1,2,4)，另一個(gè)集群將有一個(gè)樣本集合 (3,5)。
這樣，我們就通過樹狀圖解決了分層聚類中要決定聚類的數(shù)量。
Python代碼實(shí)戰(zhàn)案例
上面是理論基礎(chǔ)，有點(diǎn)數(shù)學(xué)基礎(chǔ)都能看懂。下面介紹下在如何用代碼Python來實(shí)現(xiàn)這一過程。這里拿一個(gè)客戶細(xì)分的數(shù)據(jù)來展示一下。
數(shù)據(jù)集和代碼在我的GitHub里，歡迎star！
https://github.com/xiaoyusmd/PythonDataScience
這個(gè)數(shù)據(jù)來源于UCI 機(jī)器學(xué)習(xí)庫。我們的目的是根據(jù)批發(fā)分銷商的客戶在不同產(chǎn)品類別（如牛奶、雜貨、地區(qū)等）上的年度支出，對(duì)他們進(jìn)行細(xì)分。
首先對(duì)數(shù)據(jù)進(jìn)行一個(gè)標(biāo)準(zhǔn)化，為了讓所有數(shù)據(jù)在同一個(gè)維度便于計(jì)算，然后應(yīng)用層次聚類來細(xì)分客戶。
from?sklearn.preprocessing?import?normalize
data_scaled?=?normalize(data)
data_scaled?=?pd.DataFrame(data_scaled,?columns=data.columns)
import?scipy.cluster.hierarchy?as?shc
plt.figure(figsize=(10,?7))??
plt.title("Dendrograms")??
dend?=?shc.dendrogram(shc.linkage(data_scaled,?method='ward'))
x 軸包含了所有樣本，y 軸代表這些樣本之間的距離。距離最大的垂直線是藍(lán)線，假如我們決定要以閾值 6 切割樹狀圖：
plt.figure(figsize=(10,?7))??
plt.title("Dendrograms")??
dend?=?shc.dendrogram(shc.linkage(data_scaled,?method='ward'))
plt.axhline(y=6,?color='r',?linestyle='--')
現(xiàn)在我們有兩個(gè)簇了，我們要對(duì)這 2 個(gè)簇應(yīng)用層次聚類：
from?sklearn.cluster?import?AgglomerativeClustering
cluster?=?AgglomerativeClustering(n_clusters=2,?affinity='euclidean',?linkage='ward')??
cluster.fit_predict(data_scaled)
由于我們定義了 2 個(gè)簇，因此我們可以在輸出中看到 0 和 1 的值。0 代表屬于第一個(gè)簇的點(diǎn)，1 代表屬于第二個(gè)簇的點(diǎn)。
plt.figure(figsize=(10,?7))??
plt.scatter(data_scaled['Milk'],?data_scaled['Grocery'],?c=cluster.labels_)?
到這里我們就成功的完成了聚類。
參考：https://www.analyticsvidhya.com/blog/2019/05/beginners-guide-hierarchical-clustering/
- END -