參考網站：https://www.jamleecute.com/hierarchical-clustering-%E9%9A%8E%E5%B1%A4%E5%BC%8F%E5%88%86%E7%BE%A4/

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]，擅於處理與識別大規模群聚。

  • 階層分群可被用運用數值與類別資料。

    聚合式階層群聚法（AGNES, bottom-up）

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

  • d : 由dist()函數計算出來資料兩兩間的相異度矩陣(dissimilarity matrix)，即兩兩資料間的距離矩陣。

  • method: 群(clusters)聚合或連結的方式。包括：single(單一）、complete（完整）、average（平均）、Ward’s（華德）和 centroid（中心）等法。其中又以average(平均)聚合方法被認為是最適合的。不同方法對階層分群結果亦有極大影響。

R語言hclust()套件中提供群聚距離演算法來衡量兩群聚的不相似度，最常見的幾種演算法有：

  • 單一連結聚合演算法(single-linkage agglomerative algorithm): 群與群的距離定義為不同群聚中最近的兩個點的距離。傾向產生較於緊緻(compact)的群聚。
  • 完整連結聚合演算法(complete-linkage agglomerative algorithm): 群與群的距離定義為不同群聚中最遠的兩個點的距離。傾向產生較於長(long)、鬆散(loose)的群聚。
  • 平均連結聚合演算法(average-linkage agglomerative algorithm): 群與群的距離定義為不同群聚中各點與各點距離總和的平均。
  • 中心連結聚合演算法(centroid-linkage agglomerative algorithm): 群與群的距離定義為不同群聚中心點之間的距離。


2. K-means

原理

K-means演算法其實算是分群中最簡單也最常被使用的演算法之一，他的原理如下圖(取自stack overflow):

  1. 由User事先指定分群數目k。
  2. 演算法隨機從資料集中挑選k個資料點當作初始中心點(initial centers)。
  3. 各資料點將依據距離初始中心的的歐式距離遠近分派指定給最近的群聚CkCk(cluster assignment)。
  4. 各群聚CkCk重新計算所有群聚中資料點的平均值作為新的中心點（centroid update)。並重新檢測所有資料點是否位在與其最近的中心點的群聚中。
  5. 重複第3~4步驟，來最小化各群聚的變異總和，直到各群聚組合趨於穩定與收斂（不再變動）(reach convergence)，或已達最大迭代次數（R的kmeans函數預設為最大迭代次數為10）才停止。

    設定參數

    | 參數 | 意義 | | :—-: | :—-: | | n_cluster | 要分成幾個群 | | random_state | 決定初始點的隨機seed |
  • 特性：一開始需要決定要分成幾個群

3. 密度聚類演算法（DBSCAN）

原理

這個算法是以密度為本的：給定某空間裡的一個點集合，這算法能把附近的點分成一組（有很多相鄰點的點），並標記出位於低密度區域的局外點（最接近它的點也十分遠）。
https://www.biaodianfu.com/dbscan.html