R語言的層次聚類方法是什么

這篇文章主要介紹了R語言的層次聚類方法是什么的相關知識，內容詳細易懂，操作簡單快捷，具有一定借鑒價值，相信大家閱讀完這篇R語言的層次聚類方法是什么文章都會有所收獲，下面我們一起來看看吧。

聚類算法綜述

聚類分析（clustering analysis）是將一組對象根據其特征分成不同的 cluster，使得同一 cluster 內的對象在某種意義上比不同的 cluster 之間的對象更為相似。

由于 “cluster” 沒有一個明確的定義，因而會有基于不同的模型的聚類算法，其中被廣泛運用的聚類算法有以下幾類：

• 基于連通模型（connectivity-based）的聚類算法： 即本文將要講述的層次聚類算法，其核心思想是按照對象之間的距離來聚類，兩個離的近的對象要比兩個離的遠的對象更有可能屬于同一 cluster。

• 基于中心點模型（centroid-based）的聚類算法： 在此類算法中，每個 cluster 都維持一個中心點（centorid），該中心點不一定屬于給定的數據集。當預先指定聚類數目 k 時，此類算法需要解決一個優化問題，目標函數為所有的對象距其所屬的 cluster 的中心點的距離的平方和，優化變量為每個 cluster 的中心點以及每個對象屬于哪個 cluster；此優化問題被證明是 NP-hard 的，但有一些迭代算法可以找到近似解，k-means 算法 即是其中的一種。

• 基于分布模型（distribution-based）的聚類算法： 此類算法認為數據集中的數據是由一種混合概率模型所采樣得到的，因而只要將可能屬于同一概率分布所產生的數據歸為同一 cluster 即可，最常被使用的此類算法為 高斯混合模型（GMM）聚類。

• 基于密度（density-based）的聚類算法： 在此類算法中，密度高的區域被歸為一個 cluster，cluster 之間由密度低的區域隔開，密度低的區域中的點被認為是噪聲 （noise），常用的密度聚類算法為 DBSCAN 和 OPTICS。

層次聚類綜述

層次聚類算法 (hierarchical clustering) 將數據集劃分為一層一層的 clusters，后面一層生成的 clusters 基于前面一層的結果。層次聚類算法一般分為兩類：

• Agglomerative 層次聚類：又稱自底向上（bottom-up）的層次聚類，每一個對象最開始都是一個 cluster，每次按一定的準則將最相近的兩個 cluster 合并生成一個新的 cluster，如此往復，直至最終所有的對象都屬于一個 cluster。本文主要關注此類算法。

• Divisive 層次聚類： 又稱自頂向下（top-down）的層次聚類，最開始所有的對象均屬于一個 cluster，每次按一定的準則將某個 cluster 劃分為多個 cluster，如此往復，直至每個對象均是一個 cluster。

下圖直觀的給出了層次聚類的思想以及以上兩種聚類策略的異同。

另外，需指出的是，層次聚類算法是一種貪心算法（greedy algorithm），因其每一次合并或劃分都是基于某種局部最優的選擇。

樹形圖

樹形圖 （dendrogram）可以用來直觀地表示層次聚類的成果。一個有 5 個點的樹形圖如下圖所示，其中縱坐標高度表示不同的 cluster 之間的距離（“距離”的衡量準則可以多種多樣，詳見本文后面的定義），可以從這張圖看到，x1x1 和 x2x2 的距離最近（為 1），因此將 x1x1 和 x2x2 合并為一個 cluster (x1,x2)(x1,x2)，所以在樹形圖中首先將節點 x1x1 和 x2x2 連接，使其成為一個新的節點 (x1,x2)(x1,x2) 的子節點，并將這個新的節點的高度置為 1；之后再在剩下的 4 個 cluster (x1,x2)(x1,x2)， x3x3， x4x4 和 x5x5 中選取距離最近的兩個 cluster 合并，x4x4 和 x5x5 的距離最近（為 2），因此將 x4x4 和 x5x5 合并為一個 cluster (x4,x5)(x4,x5)，體現在樹形圖上，是將節點 x4x4 和 x5x5 連接，使其成為一個新的節點 (x4,x5)(x4,x5) 的子節點，并將此新節點的高度置為 2；….依此模式進行樹形圖的生成，直至最終只剩下一個 cluster ((x1,x2),x3),(x4,x5))((x1,x2),x3),(x4,x5))。

可以直觀地看到，如果我們想得到一個聚類結果，使任意的兩個 cluster 之間的距離都不大于 hh，我們只要在樹形圖上作一條水平的直線對其進行切割，使其縱坐標等于 hh，即可獲得對應的聚類結果。例如，在下面的樹形圖中，設 h=2.5h=2.5，即可得到 3 個 cluster (x1,x2)(x1,x2)， x3x3 和 (x4,x5)(x4,x5)。

對象之間的距離衡量

衡量兩個對象之間的距離的方式有多種，對于數值類型（Numerical）的數據，常用的距離衡量準則有 Euclidean 距離、Manhattan 距離、Chebyshev 距離、Minkowski 距離等等。對于 dd 維空間的兩個對象 x=[x1,x2,…,xd]Tx=[x1,x2,…,xd]T 和 y=[y1,y2,…,yd]Ty=[y1,y2,…,yd]T，其在不同距離準則下的距離計算方法如下表所示:

Minkowski 距離就是 LpLp 范數（p≥1p≥1)，而 Manhattan 距離、Euclidean 距離、Chebyshev 距離分別對應 p=1,2,∞p=1,2,∞ 時的情形。

另一種常用的距離是 Maholanobis 距離，其定義如下：

dmah(x,y)=(x?y)TΣ?1(x?y)????????????????√dmah(x,y)=(x?y)TΣ?1(x?y)

其中 ΣΣ 為數據集的協方差矩陣，為給出協方差矩陣的定義，我們先給出數據集的一些設定，假設數據集為 X=(x1,x2,…,xn)∈Rd×nX=(x1,x2,…,xn)∈Rd×n，xi∈Rdxi∈Rd 為第 ii 個樣本點，每個樣本點的維度為 dd，樣本點的總數為 nn 個；再假設樣本點的平均值 mx=1n∑ni=1ximx=1n∑i=1nxi 為 00 向量（若不為 00，我們總可以將每個樣本都減去數據集的平均值以得到符合要求的數據集），則協方差矩陣 Σ∈Rd×dΣ∈Rd×d 可被定義為

Σ=1nXXTΣ=1nXXT

Maholanobis 距離不同于 Minkowski 距離，后者衡量的是兩個對象之間的絕對距離，其值不受數據集的整體分布情況的影響；而 Maholanobis 距離則衡量的是將兩個對象置于整個數據集這個大環境中的一個相異程度，兩個絕對距離較大的對象在一個分布比較分散的數據集中的 Maholanobis 距離有可能會比兩個絕對距離較小的對象在一個分布比較密集的數據集中的 Maholanobis 距離更小。更細致地來講，Maholanobis 距離是這樣計算得出的：先對數據進行主成分分析，提取出互不相干的特征，然后再將要計算的對象在這些特征上進行投影得到一個新的數據，再在這些新的數據之間計算一個加權的 Euclidean 距離，每個特征上的權重與該特征在數據集上的方差成反比。由這些去相干以及歸一化的操作，我們可以看到，對數據進行任意的可逆變換，Maholanobis 距離都保持不變。

Cluster 之間的距離衡量

除了需要衡量對象之間的距離之外，層次聚類算法還需要衡量 cluster 之間的距離，常見的 cluster 之間的衡量方法有 Single-link 方法、Complete-link 方法、UPGMA（Unweighted Pair Group Method using arithmetic Averages）方法、WPGMA（Weighted Pair Group Method using arithmetic Averages）方法、Centroid 方法（又稱 UPGMC，Unweighted Pair Group Method using Centroids）、Median 方法（又稱 WPGMC，weighted Pair Group Method using Centroids）、Ward 方法。前面四種方法是基于圖的，因為在這些方法里面，cluster 是由樣本點或一些子 cluster （這些樣本點或子 cluster 之間的距離關系被記錄下來，可認為是圖的連通邊）所表示的；后三種方法是基于幾何方法的（因而其對象間的距離計算方式一般選用 Euclidean 距離），因為它們都是用一個中心點來代表一個 cluster 。假設 CiCi 和 CjCj 為兩個 cluster，則前四種方法定義的 CiCi 和 CjCj 之間的距離如下表所示：

其中 Single-link 定義兩個 cluster 之間的距離為兩個 cluster 之間距離最近的兩個對象間的距離，這樣在聚類的過程中就可能出現鏈式效應，即有可能聚出長條形狀的 cluster；而 Complete-link 則定義兩個 cluster 之間的距離為兩個 cluster 之間距離最遠的兩個對象間的距離，這樣雖然避免了鏈式效應，但其對異常樣本點（不符合數據集的整體分布的噪聲點）卻非常敏感，容易產生不合理的聚類；UPGMA 正好是 Single-link 和 Complete-link 的一個折中，其定義兩個 cluster 之間的距離為兩個 cluster 之間兩個對象間的距離的平均值；而 WPGMA 則計算的是兩個 cluster 之間兩個對象之間的距離的加權平均值，加權的目的是為了使兩個 cluster 對距離的計算的影響在同一層次上，而不受 cluster 大小的影響（其計算方法這里沒有給出，因為在運行層次聚類算法時，我們并不會直接通過樣本點之間的距離之間計算兩個 cluster 之間的距離，而是通過已有的 cluster 之間的距離來計算合并后的新的 cluster 和剩余 cluster 之間的距離，這種計算方法將由下一部分中的 Lance-Williams 方法給出）。

Centroid/UPGMC 方法給每一個 cluster 計算一個質心，兩個 cluster 之間的距離即為對應的兩個質心之間的距離，一般計算方法如下：

DUPGMC(Ci,Cj)=1∣Ci∣∣Cj∣∑x∈Ci,y∈Cjd(x,y)?12∣Ci∣2∑x,<

關于“R語言的層次聚類方法是什么”這篇文章的內容就介紹到這里，感謝各位的閱讀！相信大家對“R語言的層次聚類方法是什么”知識都有一定的了解，大家如果還想學習更多知識，歡迎關注億速云行業資訊頻道。