kyle-glenn-686350-unsplash
 程式與統計統計模型

Hierarchical Clustering 階層式分群 | Clustering 資料分群 | R 統計

Hierarchical Clustering, 屬於資料分群的一種方法。資料分群屬於非監督式學習,處理的資料是沒有正確答案/標籤/目標變數可參考的。常見的分群方法包括著名的kmeans, hierarchical clustering,分別使用不同分群演算邏輯。本篇將介紹階層式分群的實作與特色。

資料分群簡介

  • 資料分群是一個將資料分割成數個子集合的方法,主要目的包括:
    • 找出資料中相近的群聚(clusters)
    • 找出各群的代表點。代表點可以是群聚中的中心點(centroids)或是原型(prototypes)
  • 透過各群的代表點,可以達到幾個目標:
    • 資料壓縮
    • 降低雜訊
    • 降低計算量
  •  資料分群將依據資料自身屬性計算彼此間的相似度(物以類聚),而「相似度」主要有兩種型態:
    • 「Compactness」:目標是讓子集合間差異最大化,子集合內差異最小化。如階層式分群和K-means分群。
    • 「Connectedness」:目標是將可串連在一起的個體分成一群。如譜分群(Spectral Clustering)。
  • 資料分群屬於非監督式學習法(Unsupervised Learning),即資料沒有標籤(unlabeled data)或沒有標準答案,無法透過所謂的目標變數(response variable)來做分類之訓練。也因為資料沒有標籤之緣故,與監督式學習法和強化式學習法不同,非監督式學習法無法衡量演算法的正確率

資料分群系列文章會依序介紹以下幾種常見的分群方法:

  1. 階層式分群(hierarchical clustering)
    1. 聚合式階層分群法 Agglomerative Hierarchical Clustering
    2. 分裂式階層分群法 Divisive Hierarchical Clustering
    3. 最佳分群群數(Determining Optimal Clusters)
  2. 切割式分群(partitional clustering)
    1. K-means
    2. K-medoid
    3. 最佳分群群數(Determining Optimal Clusters)
  3. 譜分群(Spectral Clustering)

1. 階層式分群(Hierarchical clustering)

  • 階層分群法的概念是在分群中建立分群,並不需要預先設定分群數。
  • 產生的分群結果為一目瞭然的樹狀結構圖(又稱作dendrogram)。
  • 群數(number of clusters)可由大變小(divisive hierarchical clustering),或是由小變大(agglomerative hierarchical clustering),透過群聚反覆的分裂和合併後,在選取最佳的群聚數。
  • 階層式分群兩種演算法:
    • 當採行聚合法,又稱作AGNES(Agglomerative Nesting),資料會由樹狀結構的底部開始開始逐次合併 (bottom-up),在R語言中所使用的函數為hclust()[in stat package]或agnes[in cluster package]擅於處理與識別小規模群聚
    • 當採行分裂法,又稱作DIANA(Divisive Analysis),資料則會由樹狀結構的頂部開始逐次分裂(top-down),在R語言中使用的套件為diana()[in cluster package]擅於處理與識別大規模群聚
  • 階層分群可被用運用數值與類別資料。

1-1. 聚合式階層群聚法(AGNES, bottom-up)

我們使用Iris資料集-經典的鳶尾花資料來進行聚合式階層群聚法之說明。(*注意,資料必須先預處理遺失值的部分,比如說使用na.omit(data)。)

因為分群法為非監督式學習法,專處理無標籤(un-labeled)無標準答案的資料分群,故我們將分類結果欄位Species從我們的inputData刪除。

在進行聚合式群聚法前,我們先簡單介紹幾個hclust()函數中的重要參數:

  • d : 由dist()函數計算出來資料兩兩間的相異度矩陣(dissimilarity matrix),即兩兩資料間的距離矩陣。
  • method: 群(clusters)聚合連結的方式。包括:single(單一)、complete(完整)、average(平均)、Ward’s(華德)和 centroid(中心)等法。其中又以average(平均)聚合方法被認為是最適合的。不同方法對階層分群結果亦有極大影響。

R語言hclust()套件中提供群聚距離演算法衡量兩群聚的不相似度,最常見的幾種演算法如下:

  • 單一連結聚合演算法(single-linkage agglomerative algorithm): 群與群的距離定義為不同群聚中最近的兩個點的距離。傾向產生較於緊緻(compact)的群聚。
    $$d(C_{i},C_{j})=\min_{a\in C_{i},b\in C_{j}}d(a,b)$$
  • 完整連結聚合演算法(complete-linkage agglomerative algorithm): 群與群的距離定義為不同群聚中最遠的兩個點的距離。傾向產生較於長(long)、鬆散(loose)的群聚。
    $$d(C_{i},C_{j})=\max_{a\in C_{i},b\in C_{j}}d(a,b)$$
  • 平均連結聚合演算法(average-linkage agglomerative algorithm): 群與群的距離定義為不同群聚中各點與各點距離總和的平均
    $$d(C_{i},C_{j})=\sum_{a\in C_{i},b\in C_{j}}\frac{d(a,b)}{|C_{i}||C_{j}|}$$
    其中,\(|C_{i}|\)和\(|C_{j}|\)分別為群聚\(C_{i}\)和\(C_{j}\)的大小。
  • 中心連結聚合演算法(centroid-linkage agglomerative algorithm): 群與群的距離定義為不同群聚中心點之間的距離
    $$d(A,B)= d(\bar{X}_{A},\bar{X}_{B})=\|\bar{X}_{A}-\bar{X}_{B}\|^2$$
  • 華德最小變異法(Ward’s Minimum Variance): 最小化各群聚內變異加總(minimize the total within-cluster variance)。主要用來尋找緊湊球型的群聚。反覆比較每對資料合併後的群內總變異數的增量,並找增量最小的組別優先合併。越早合併的子集表示其間的相似度越高。而使用華德最小變異法的前提為,初始各點資料距離必須是歐式距離的平方和(Squared Euclidean Distance)。在R套件hclust將參數設為method = “ward.D2″(不是”ward.D”)。(華德法參考文獻

我們先來試試,不同的資料點間距離矩陣計算之效果。即調整dist()中參數method

  • 歐式距離(以二維空間為例):最常用也是最重要的距離計算法
    $$d(P_{1},P_{2})=\sqrt{(x_{1}-x_{2})^2+(y_{1}-y_{2})^2}$$
  • 曼哈頓距離(以二維空間為例):
    $$d(P_{1},P_{2})=|x_{1}-x_{2}|+|y_{1}-y_{2}|$$

可發現不同資料距離計算會有不同分群結果。

  • Height表示n-1組實數值。各值為使用特定聚合方法計算出來的標準數值

hierarchical clustering

比較不同歐式距離搭配不同聚合演算法的分群結果。

從下圖可以發現群聚數結構的幾個特徵:

  • Single-linkage法具有「大者恆大」之效果。
  • 而 complete linkage 和 average linkage 比較具有「齊頭並進」之效果。

hierarchical clustering




接著,我們聚焦在採用歐式距離搭配華德最小變異聚合演算法。可透過設定hclust()參數method=”ward.D2″

hierarchical clustering

以上結果也可以使用anges()函數來執行。此函數跟hclust()很類似,不同之處是該函數能另外計算聚合係數(agglomerative coefficient)聚合係數是衡量群聚結構被辨識的程度,聚合係數越接近1代表有堅固的群聚結構(strong clustering structure)。在這個使用歐式距離搭配華德連結演算法的群聚係數有高達99%的表現。

我們可以用聚合係數來比較多組分群連結演算法的效果。此範例中又以華德法表現最好。

若遇將agnes()產生的樹狀圖繪出可使用函數pltree()。可以發現結果大致上與hclust()結果差不多。

hierarchical clustering

對階層分群結果產生的樹狀結構進行截枝可以將觀測值分成數群截肢方法有兩種:

  1. 指定所要的分群數: rect.hclust(k=…)、cutree(k=…)
  2. 指定截枝的位置: rect.hclust(h=…)

比如說,指定將資料分成3群與13群。

hierarchical clustering

比如說,指定截枝高度分別為4和10,可分別將資料分成5組跟3組。

hierarchical clustering

如果要將資料標記上分群結果,可使用cutree(),並指定參數k為所欲截枝群樹。

分群結果和實際結果比較。

將資料分群的混淆矩陣視覺化。

可以發現,屬於setosa種類的都被很好的分到第一群,屬於versicolor主要被分到第二群,但virginica似乎沒有分得很好。

hierarchical clustering

如果回頭看一下原始資料分佈長相,可以發現versicolor和virginica其實部分資料靠得很近,因此兩種Species被分到第二和第三群也是合理的。

hierarchical clustering




1-2. 分裂式階層群聚法(DIANA, top-down)

我們使用R內建的USArrests資料集來進行說明。進行分群前,我們先將資料預處理,包括遺失值忽略以及標準化(0~1)

diana()函數運作方式很類似agnes(),只差diana沒有method參數

由分裂式階層分群演算法產出的樹狀圖結果如下:

  • 葉節點(末梢節點)代表個別資料點。
  • 垂直座標軸的Height代表群聚間的(不)相似度((dis)similarity), 群聚的高度(height)越高,代表觀測值間越不相似(組內變異越大)。需要注意的是,要總結兩個觀測值的相似度,只能用兩觀測值何時被第一次合併的群聚高度來做判斷,而不能以水平軸的距離來評估

hierarchical clustering

另外,我們可以透過縱軸的群聚高度來決定分群數目。我們可以使用cutree()函數來得到各觀測值被分類到的群。

我們使用factoextra套件中的fviz_clusterc函數來將分群結果視覺化。

hierarchical clustering

1-3. 決定階層式分群最佳群聚數

1-3-1. Elbow Method

使用函數fviz_nbclust(),並將參數FUN指定為hcut(表階層式分群法)。wss代表組內平方誤差。

由結果圖可知根據Elbow法,最佳分群數目為4群。

hierarchical clustering

1-3-2. Average Silhouette Method

將method參數改為silhouette。

根據Average Silhouette Width,最佳分群數目為2 群。

hierarchical clustering

1-3-3. Gap Statistic Method

使用clusGap()函數。

根據Gap(k)統計量,最佳分群數為3群。(*\(Gap(k)\geq Gap(k+1) – s_{k+1}\))

hierarchical clustering

總結

  • 階層分群主要受:資料個體兩兩間距離矩陣衡量方法群與群連結方法所影響
  •  階層分群優點包括:
    • 概念簡單且樹狀圖(dendrogram)結果一目瞭然。
    • 只需要資料點間距離即可產出分群結果。
    • 可以應用在數值或類別資料。
  • 但缺點就是運算速度,以及不適用處理大量資料。運算速度方面,可以考慮其他R套件如fastcluster中的hclust函數,執行上會比一般hclust更有效率。

更多統計模型筆記連結:

  1. Linear Regression | 線性迴歸模型 | using AirQuality Dataset
  2. Regularized Regression | 正規化迴歸 – Ridge, Lasso, Elastic Net | R語言
  3. Logistic Regression 羅吉斯迴歸 | part1 – 資料探勘與處理 | 統計 R語言
  4. Logistic Regression 羅吉斯迴歸 | part2 – 模型建置、診斷與比較 | R語言
  5. Decision Tree 決策樹 | CART, Conditional Inference Tree, Random Forest
  6. Regression Tree | 迴歸樹, Bagging, Bootstrap Aggregation | R語言
  7. Random Forests 隨機森林 | randomForest, ranger, h2o | R語言
  8. Gradient Boosting Machines GBM | gbm, xgboost, h2o | R語言
  9. Hierarchical Clustering 階層式分群 | Clustering 資料分群 | R統計
  10. Partitional Clustering | 切割式分群 | Kmeans, Kmedoid | Clustering 資料分群
  11. Principal Components Analysis (PCA) | 主成份分析 | R 統計

參考:

  1. 歐萊禮  R資料科學

在《Hierarchical Clustering 階層式分群 | Clustering 資料分群 | R 統計》中有 6 則留言

  1. 請問文中提及階層分群可被用運用數值與類別資料,但如果是類別資料,我應該要如何定義變項的數值及如何計算其距離??

    1. 如遇類別型資料,在計算dissimilarity matrix 使用的距離計算方式是Gower distance(而非傳統的Eucledian distances),可以使用cluster package中的daisy()函數處理,可以處理混合形態的變數。
      R函數計算方式為 gower.dist https://www.rdocumentation.org/packages/cluster/versions/2.0.6/topics/daisy
      希望有回答到你的問題^^

  2. 最近才發現大大的網站,相見恨晚><
    超級厲害!受用無窮呀!
    非常感謝Orz

  3. 打擾囉!針對您所提供的daisy()函數,來處理資料中有連續型態,和類別型態變數使用,
    想請問,這樣我資料需要預處理,使其標準化後,再套用該函數嗎?
    亦或直接將所分析之資料變數放進去即可呢?

  4. 放進去即可呢?打擾囉!針對您所提供的daisy()函數,來處理資料中有連續型態,和類別型態變數使用,
    想請問,這樣我資料需要預處理,使其標準化後,再套用該函數嗎?
    亦或直接將所分析之資料變數

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *