基於層次聚類演算法

⑴ 數據挖掘干貨總結（四）--聚類演算法

本文共計2680字，預計閱讀時長七分鍾

聚類演算法

 

一 、 本質

將數據劃分到不同的類里，使相似的數據在同一類里，不相似的數據在不同類里

 

二 、 分類演算法用來解決什麼問題

文本聚類、圖像聚類和商品聚類，便於發現規律，以解決數據稀疏問題

三 、 聚類演算法基礎知識

1. 層次聚類 vs 非層次聚類

– 不同類之間有無包含關系

2. 硬聚類 vs 軟聚類

– 硬聚類：每個對象只屬於一個類

– 軟聚類：每個對象以某個概率屬於每個類

3. 用向量表示對象

– 每個對象用一個向量表示，可以視為高維空間的一個點

– 所有對象形成數據空間（矩陣）

– 相似度計算：Cosine、點積、質心距離

4. 用矩陣列出對象之間的距離、相似度

5. 用字典保存上述矩陣（節省空間）

    D={(1,1):0,(1,2):2,(1,3):6...(5,5):0}

6. 評價方法

– 內部評價法（Internal Evalution）：

• 沒有外部標准，非監督式

• 同類是否相似，跨類是否相異

DB值越小聚類效果越好，反之，越不好

– 外部評價法（External Evalution）：

• 准確度（accuracy）: (C11+C22) / (C11 + C12 + C21 + C22)

• 精度（Precision）: C11 / (C11 + C21 )

• 召回（Recall）: C11 / (C11 + C12 )

• F值（F-measure）：

β表示對精度P的重視程度，越大越重視，默認設置為1，即變成了F值，F較高時則能說明聚類效果較好。

四 、 有哪些聚類演算法

主要分為 層次化聚類演算法 ， 劃分式聚類演算法 ， 基於密度的聚類演算法 ， 基於網格的聚類演算法 ， 基於模型的聚類演算法等 。

4.1 層次化聚類演算法

又稱樹聚類演算法，透過一種層次架構方式，反復將數據進行分裂或聚合。典型的有BIRCH演算法，CURE演算法，CHAMELEON演算法，Sequence data rough clustering演算法,Between groups average演算法,Furthest neighbor演算法,Neares neighbor演算法等。

凝聚型層次聚類 ：

先將每個對象作為一個簇，然後合並這些原子簇為越來越大的簇，直到所有對象都在一個簇中，或者某個終結條件被滿足。

演算法流程：

1. 將每個對象看作一類，計算兩兩之間的最小距離；

2. 將距離最小的兩個類合並成一個新類；

3. 重新計算新類與所有類之間的距離；

4. 重復2、3，直到所有類最後合並成一類。

特點：

1. 演算法簡單

2. 層次用於概念聚類（生成概念、文檔層次樹）

3. 聚類對象的兩種表示法都適用

4. 處理大小不同的簇

5. 簇選取步驟在樹狀圖生成之後

4.2 劃分式聚類演算法

預先指定聚類數目或聚類中心，反復迭代逐步降低目標函數誤差值直至收斂，得到最終結果。K-means,K-modes-Huang,K-means-CP,MDS_CLUSTER, Feature weighted fuzzy clustering，CLARANS等

經典K-means：

演算法流程：

1. 隨機地選擇k個對象，每個對象初始地代表了一個簇的中心；

2. 對剩餘的每個對象，根據其與各簇中心的距離，將它賦給最近的簇；

3. 重新計算每個簇的平均值，更新為新的簇中心；

4. 不斷重復2、3，直到准則函數收斂。

特點：

1.K的選擇

2.中心點的選擇

– 隨機

– 多輪隨機：選擇最小的WCSS

3.優點

– 演算法簡單、有效

– 時間復雜度：O(nkt)

4.缺點

– 不適於處理球面數據

– 密度、大小不同的聚類，受K的限制，難於發現自然的聚類

4.3 基於模型的聚類演算法

為每簇假定了一個模型，尋找數據對給定模型的最佳擬合，同一」類「的數據屬於同一種概率分布，即假設數據是根據潛在的概率分布生成的。主要有基於統計學模型的方法和基於神經網路模型的方法，尤其以基於概率模型的方法居多。一個基於模型的演算法可能通過構建反應數據點空間分布的密度函數來定位聚類。基於模型的聚類試圖優化給定的數據和某些數據模型之間的適應性。

SOM 神經網路演算法 ：

該演算法假設在輸入對象中存在一些拓撲結構或順序，可以實現從輸入空間(n維)到輸出平面(2維)的降維映射，其映射具有拓撲特徵保持性質,與實際的大腦處理有很強的理論聯系。

SOM網路包含輸入層和輸出層。輸入層對應一個高維的輸入向量，輸出層由一系列組織在2維網格上的有序節點構成，輸入節點與輸出節點通過權重向量連接。學習過程中，找到與之距離最短的輸出層單元，即獲勝單元，對其更新。同時，將鄰近區域的權值更新，使輸出節點保持輸入向量的拓撲特徵。

演算法流程：

1. 網路初始化，對輸出層每個節點權重賦初值；

2. 將輸入樣本中隨機選取輸入向量，找到與輸入向量距離最小的權重向量；

3. 定義獲勝單元，在獲勝單元的鄰近區域調整權重使其向輸入向量靠攏；

4. 提供新樣本、進行訓練；

5. 收縮鄰域半徑、減小學習率、重復，直到小於允許值，輸出聚類結果。

4.4 基於密度聚類演算法

只要鄰近區域的密度（對象或數據點的數目）超過某個閾值，就繼續聚類，擅於解決不規則形狀的聚類問題，廣泛應用於空間信息處理,SGC,GCHL，DBSCAN演算法、OPTICS演算法、DENCLUE演算法。

DBSCAN：

對於集中區域效果較好，為了發現任意形狀的簇，這類方法將簇看做是數據空間中被低密度區域分割開的稠密對象區域；一種基於高密度連通區域的基於密度的聚類方法，該演算法將具有足夠高密度的區域劃分為簇，並在具有雜訊的空間數據中發現任意形狀的簇。

4.5 基於網格的聚類演算法

    基於網格的方法把對象空間量化為有限數目的單元，形成一個網格結構。所有的聚類操作都在這個網格結構（即量化空間）上進行。這種方法的主要優點是它的處理 速度很快，其處理速度獨立於數據對象的數目，只與量化空間中每一維的單元數目有關。但這種演算法效率的提高是以聚類結果的精確性為代價的。經常與基於密度的演算法結合使用。代表演算法有STING演算法、CLIQUE演算法、WAVE-CLUSTER演算法等。 

⑵ 常用的聚類方法有哪幾種

聚類分析的演算法可以分為劃分法、層次法、基於密度的方法、基於網格的方法、基於模型的方法。

1、劃分法，給定一個有N個元組或者紀錄的數據集，分裂法將構造K個分組，每一個分組就代表一個聚類，K<N。

2、層次法，這種方法對給定的數據集進行層次似的分解，直到某種條件滿足為止。

3、基於密度的方法，基於密度的方法與其它方法的一個根本區別是：它不是基於各種各樣的距離的，而是基於密度的。這樣就能克服基於距離的演算法只能發現「類圓形」的聚類的缺點。

4、圖論聚類方法解決的第一步是建立與問題相適應的圖，圖的節點對應於被分析數據的最小單元，圖的邊（或弧）對應於最小處理單元數據之間的相似性度量。

5、基於網格的方法，這種方法首先將數據空間劃分成為有限個單元的網格結構,所有的處理都是以單個的單元為對象的。

6、基於模型的方法，基於模型的方法給每一個聚類假定一個模型，然後去尋找能夠很好的滿足這個模型的數據集。

(2)基於層次聚類演算法擴展閱讀：

在商業上，聚類可以幫助市場分析人員從消費者資料庫中區分出不同的消費群體來，並且概括出每一類消費者的消費模式或者說習慣。

它作為數據挖掘中的一個模塊，可以作為一個單獨的工具以發現資料庫中分布的一些深層的信息，並且概括出每一類的特點，或者把注意力放在某一個特定的類上以作進一步的分析；並且，聚類分析也可以作為數據挖掘演算法中其他分析演算法的一個預處理步驟。

許多聚類演算法在小於 200 個數據對象的小數據集合上工作得很好；但是，一個大規模資料庫可能包含幾百萬個對象，在這樣的大數據集合樣本上進行聚類可能會導致有偏的結果。

許多聚類演算法在聚類分析中要求用戶輸入一定的參數，例如希望產生的簇的數目。聚類結果對於輸入參數十分敏感。參數通常很難確定，特別是對於包含高維對象的數據集來說。這樣不僅加重了用戶的負擔，也使得聚類的質量難以控制。

⑶ 聚類演算法 - 凝聚層次聚類

層次聚類 就是通過對數據集按照某種方法進行層次分解，直到滿足某種條件為止。按照分類原理的不同，可以分為凝聚和分裂兩種方法。

層次聚類方法對給定的數據集進行層次的分解，直到某種條件滿足為止。具體又可分為 凝聚 和 分裂 的兩種方案：

凝聚的層次聚類是一種自底向上的策略，首先將每個對象作為一個簇，然後合並這些原子簇為越來越大的簇，直到所有的對象都在一個簇中，或者某個終結條件被滿足，絕大多數層次聚類方法屬於這一類，它們只是在簇間相似度的定義上有所不同。.

分裂的層次聚類與凝聚的層次聚類相反，採用自頂向下的策略，它首先將所有對象置於同一個簇中，然後逐漸細分為越來越小的簇，直到每個對象自成一簇，或者達到了某個終止條件。

本篇主要討論凝聚的層次聚類。

第一步 ，將訓練樣本集中的每個數據點都當做一個聚類
第二步 ，計算每兩個聚類之間的距離，將距離最近的或最相似的兩個聚類進行合並，如同下圖中的p1和p2、p5和p6
第三步 ，重復上述步驟，依舊計算每個聚類的距離，當然這次因為已經有聚合起來的簇了因此距離的計算方式有多種： 【單鏈】簇內的最近的點的距離、【全鏈】簇內的最遠的點的距離、【組平均】簇的平均距離、簇的相似度等
第四步 ，直到得到的當前聚類數是合並前聚類數的10%，即90%的聚類都被合並了；當然還可以設置其他終止條件，這樣設置是為了防止過度合並，此時需要幾個簇，那麼就可以用一條橫線去截取分出的簇，如下圖分出3類、4類、5類的橫線截止

ps：距離在通常的情況下可以計算歐幾里得距離，就是普通的直線距離，還可以計算餘弦相似度
具體的動畫效果可以參考視頻，這是----> 傳送門

1）距離和規則的相似度容易定義，限制少
2）不像kmeans，不需要預先制定聚類數
3）可以發現類的層次關系

1）計算復雜度太高
2）奇異值也能產生很大影響
3）由於根據距離來聚合數據，演算法很可能聚類成鏈狀

⑷ 什麼叫層次聚類分析

一個層次的聚類方法將數據對象組成一棵聚類的樹。根據層次分解是自底向上的還是自頂向下形成的，層次的聚類方法可以進一步分為凝聚的（agglomerative）和分裂的（divisive）層次聚類。

（1）凝聚的層次聚類：這種自底向上的策略首先將每個對象作為單獨的一個簇，然後和並這些原子簇為越來越大的簇，直到所有的對像都在一個簇中，或者達到某個終止條件。

（2）分裂的層次聚類：這種自頂向下的策略與凝聚的層次聚類相反，它首先將所有的對象置於一個簇中。然後逐漸細分為越來越小的簇，直到每個對象在單獨的一個簇中，或者達到一個終止條件，例如打到了某個希望的簇數目後者兩個簇之間的距離超過了某個閥值。

例2 圖2－3描述了一個凝聚的層次聚類方法AGNES（Agglomerative NESting）和一個分裂的層次聚類方法DIANA（Divisive Analysis）在一個包含五個對象的數據集合{a,b,c,d,e}上的處理過程。最初,AGNES將每個對象作為一個簇，然後這些簇根據某些准則一步步合並。例如，如果簇C1中的一個對象和簇 C2中的一個對象之間的距離使所有屬於不同簇的對象間歐式距離最小的，C1和C2可能被合並。其每個簇可以被簇中所有對象代表，兩個簇間的相似度由兩個不同簇中距離最近的數據點對的相似度來確定。聚類的合並過程反復進行直到所有對象最終合並為一個簇。

圖2-3 在對象集合(a,b,c,d)上的凝聚與分裂層次聚類

在DIANA方法處理過程中，所有的對象都放在一個簇中。根據一些原則（如簇中最鄰近的對象的最大歐氏距離），將該簇分裂。簇的分裂過程反復進行，直到最終每個新的簇只包含一個對象。

層次聚類方法盡管簡單，但經常會遇到合並或分裂點選擇的困難。這樣的選擇是非常關鍵的，因為一旦一組對象（合並或分裂）完成，它就不能被撤銷，下一步的處理將在新完成的簇上進行。這個嚴格規定是有用的，由於不用擔心組合數目的不同選擇，計算代價會比較小。但是，已做的處理不能被撤消，聚類之間也不能交換對象。如果在某一步沒有很好的選擇合並或分裂的決定，可能會導致低質量的聚類結果。而且，這種聚類不具有很好的可伸縮性。因為合並或分裂的決定需要檢查和估算大量的對象或結果。

改進層次方法的聚類質量的一個有希望的方向是將層次聚類和其他聚類技術集成。有兩種方法可以改進層次聚類的結果：

（i） 在每層劃分中，仔細分析對象間的「聯接」，例如CURE和Chameleon中的做法。

（ii）綜合層次凝聚和迭代的重定位方法。首先用自底向上的層次演算法，然後用迭代的重定位來改進結果。例如BIRCH中的方法。

⑸ 聚類演算法有哪幾種

聚類分析計算方法主要有： 層次的方法(hierarchical method)、劃分方法(partitioning method)、基於密度的方法(density-based method)、基於網格的方法(grid-based method)、基於模型的方法(model-based method)等。其中，前兩種演算法是利用統計學定義的距離進行度量。
k-means 演算法的工作過程說明如下：首先從n個數據對象任意選擇 k 個對象作為初始聚類中心;而對於所剩下其它對象，則根據它們與這些聚類中心的相似度(距離)，分別將它們分配給與其最相似的(聚類中心所代表的)聚類;然 後再計算每個所獲新聚類的聚類中心(該聚類中所有對象的均值);不斷重復這一過程直到標准測度函數開始收斂為止。一般都採用均方差作為標准測度函數. k個聚類具有以下特點：各聚類本身盡可能的緊湊，而各聚類之間盡可能的分開。
其流程如下：
(1)從 n個數據對象任意選擇 k 個對象作為初始聚類中心;
(2)根據每個聚類對象的均值(中心對象)，計算每個對象與這些中心對象的距離;並根據最小距離重新對相應對象進行劃分;
(3)重新計算每個(有變化)聚類的均值(中心對象);
(4)循環(2)、(3)直到每個聚類不再發生變化為止(標准測量函數收斂)。
優點： 本演算法確定的K個劃分到達平方誤差最小。當聚類是密集的，且類與類之間區別明顯時，效果較好。對於處理大數據集，這個演算法是相對可伸縮和高效的，計算的復雜度為 O(NKt)，其中N是數據對象的數目，t是迭代的次數。
缺點：
1. K 是事先給定的，但非常難以選定;
2. 初始聚類中心的選擇對聚類結果有較大的影響。

⑹ 層次聚類演算法是降維還是升維

層次聚類演算法是降維。

層次聚類演算法通過計算不同類別數據點間的相似度來創建一棵有層次的嵌套聚類樹。 在聚類樹中，不同類別的原始數據點是樹的最低層，樹的頂層是一個聚類的根節點。 創建聚類樹有自下而上合並和自上而下分裂兩種方法，本篇文章介紹合並方法。

層次聚類演算法原理：

層次聚類的合並演算法通過計算兩類數據點間的相似性，對所有數據點中最為相似的兩個數據點進行組合，並反復迭代這一過程。簡單的說層次聚類的合並演算法是通過計算每一個類別的數據點與所有數據點之間的距離來確定它們之間的相似性，距離越小，相似度越高。

⑺ 聚類演算法有哪些分類

聚類演算法的分類有：

1、劃分法

劃分法(partitioning methods)，給定一個有N個元組或者紀錄的數據集，分裂法將構造K個分組，每一個分組就代表一個聚類，K小於N。而且這K個分組滿足下列條件：

（1） 每一個分組至少包含一個數據紀錄；

（2）每一個數據紀錄屬於且僅屬於一個分組（注意：這個要求在某些模糊聚類演算法中可以放寬）；

2、層次法

層次法(hierarchical methods)，這種方法對給定的數據集進行層次似的分解，直到某種條件滿足為止。具體又可分為「自底向上」和「自頂向下」兩種方案。

例如，在「自底向上」方案中，初始時每一個數據紀錄都組成一個單獨的組，在接下來的迭代中，它把那些相互鄰近的組合並成一個組，直到所有的記錄組成一個分組或者某個條件滿足為止。

3、密度演算法

基於密度的方法(density-based methods)，基於密度的方法與其它方法的一個根本區別是：它不是基於各種各樣的距離的，而是基於密度的。這樣就能克服基於距離的演算法只能發現「類圓形」的聚類的缺點。

4、圖論聚類法

圖論聚類方法解決的第一步是建立與問題相適應的圖，圖的節點對應於被分析數據的最小單元，圖的邊（或弧）對應於最小處理單元數據之間的相似性度量。因此，每一個最小處理單元數據之間都會有一個度量表達，這就確保了數據的局部特性比較易於處理。圖論聚類法是以樣本數據的局域連接特徵作為聚類的主要信息源，因而其主要優點是易於處理局部數據的特性。

5、網格演算法

基於網格的方法(grid-based methods)，這種方法首先將數據空間劃分成為有限個單元（cell）的網格結構,所有的處理都是以單個的單元為對象的。這么處理的一個突出的優點就是處理速度很快，通常這是與目標資料庫中記錄的個數無關的，它只與把數據空間分為多少個單元有關。

代表演算法有：STING演算法、CLIQUE演算法、WAVE-CLUSTER演算法；

6、模型演算法

基於模型的方法(model-based methods)，基於模型的方法給每一個聚類假定一個模型，然後去尋找能夠很好的滿足這個模型的數據集。這樣一個模型可能是數據點在空間中的密度分布函數或者其它。它的一個潛在的假定就是：目標數據集是由一系列的概率分布所決定的。

通常有兩種嘗試方向：統計的方案和神經網路的方案。

(7)基於層次聚類演算法擴展閱讀：

聚類演算法的要求：

1、可伸縮性

許多聚類演算法在小於 200 個數據對象的小數據集合上工作得很好；但是，一個大規模資料庫可能包含幾百萬個對象，在這樣的大數據集合樣本上進行聚類可能會導致有偏的結果。

我們需要具有高度可伸縮性的聚類演算法。

2、不同屬性

許多演算法被設計用來聚類數值類型的數據。但是，應用可能要求聚類其他類型的數據，如二元類型(binary)，分類/標稱類型（categorical/nominal），序數型（ordinal）數據，或者這些數據類型的混合。

3、任意形狀

許多聚類演算法基於歐幾里得或者曼哈頓距離度量來決定聚類。基於這樣的距離度量的演算法趨向於發現具有相近尺度和密度的球狀簇。但是，一個簇可能是任意形狀的。提出能發現任意形狀簇的演算法是很重要的。

4、領域最小化

許多聚類演算法在聚類分析中要求用戶輸入一定的參數，例如希望產生的簇的數目。聚類結果對於輸入參數十分敏感。參數通常很難確定，特別是對於包含高維對象的數據集來說。這樣不僅加重了用戶的負擔，也使得聚類的質量難以控制。

5、處理「雜訊」

絕大多數現實中的資料庫都包含了孤立點，缺失，或者錯誤的數據。一些聚類演算法對於這樣的數據敏感，可能導致低質量的聚類結果。

6、記錄順序

一些聚類演算法對於輸入數據的順序是敏感的。例如，同一個數據集合，當以不同的順序交給同一個演算法時，可能生成差別很大的聚類結果。開發對數據輸入順序不敏感的演算法具有重要的意義。