數據挖掘入門筆記——層次聚類 ( 浮光掠影)

寫在前面:健忘星人自學筆記,僅供參考

簡單易懂的閱讀資料

前面的文章我們分別介紹瞭 K-means , 密度聚類,譜聚類,其中譜聚類的難度比較大,要求有一定的矩陣學習基礎,今天不妨輕松一下,學習一個較為簡單的“層次聚類”。

正文:

一、層次聚類基本原理

層次的聚類方法(Hierarchical Clustering),從字面上理解,其是層次化的聚類,最終得出來的是樹形結構。專業一點來說,層次聚類通過 計算不同類別數據點間的相似度 來創建一棵有層次的嵌套聚類樹。

層次聚類的好處是不需要指定具體類別數目的,其得到的是一顆樹,聚類完成之後,可在任意層次橫切一刀,得到指定數目的簇。

聚類數示例

按照 層次分解是自下而上,還是自頂向下,層次的聚類方法可以進一步分為以下兩種:

AGNES 算法步驟:

(1) 初始化,每個樣本當做一個簇

(2) 計算任意兩簇距離,找出 距離最近的兩個簇,合並這兩簇

(3) 重復步驟 2……

直到,最遠兩簇距離超過閾值,或者簇的個數達到指定值,終止算法

DIANA 算法步驟:

(1) 初始化,所有樣本集中歸為一個簇

(2) 在同一個簇中,計算任意兩個樣本之間的距離,找到 距離最遠 的兩個樣本點a,b,將 a,b 作為兩個簇的中心;

(3) 計算原來簇中剩餘樣本點距離 a,b 的距離,距離哪個中心近,分配到哪個簇中

(4) 重復步驟2、3 ……

直到,最遠兩簇距離不足閾值,或者簇的個數達到指定值,終止算法

二、距離度量

在上面說的 AGNES 提到瞭 合並距離最近的兩簇,這裡的距離是如何度量的呢?

簇間距離的計算方法有許多,包括:

最小距離,最大距離,均值距離,(類)平均距離,中間距離,重心距離

(1)最小距離,取兩個類中距離最近的兩個樣本的距離作為這兩個簇的距離

(2)最大距離,取兩個類中距離最遠的兩個樣本的距離作為這兩個簇的距離

補充:

當算法選擇“最小距離”作為簇間距離時,有時稱之為 最近鄰聚類算法。並且,當最近兩個簇之間的距離超過閾值時,算法終止,則稱其為單連接算法

當算法選擇“最大距離”作為簇間距離時,有時稱之為 最遠鄰聚類算法。並且,當最近兩個簇之間的最大距離超過閾值時,算法終止,則稱其為全連接算法

(3)均值距離,兩個簇的平均值作為中心點,取這兩個均值之間的距離作為兩個簇的距離

(4)(類)平均距離,兩個簇任意兩點距離加總後,取平均值 作為兩個簇的距離

(5)中間距離,介於最短距離和最長距離之間,相當於初等幾何中三角形的中線

假設 p 點 是最長距離點,q 點是最短距離點,則中間距離為:

D_lr = sqrt{frac{1}{2}D_{lp}^2 +frac{1}{2}D_{lq}^2-frac{1}{4}D_{pq}^2 }

(6)重心距離,將每類中包含的樣本數考慮進去。

若 I 類中有 n I 個樣本, J 類中有 n J 個樣本

還有其他距離計算方法,這裡省略

有興趣繼續瞭解的可參考:

距離度量的選擇

三、優缺點

優點:

缺點:

層次聚類的改進:

一個有希望的方向是集成層次聚類和其他的聚類技術,形成多階段聚類。

上面四種衍生算法的參考資料:

預計在後面文章中詳細介紹。

今天的內容就到這裡,總體而言,層次聚類還是比較簡單的

赞(0)