圖的聚類演算法

㈠ 聚類演算法有哪些分類

聚類演算法的分類有：

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

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

(1)圖的聚類演算法擴展閱讀：

聚類演算法的要求：

1、可伸縮性

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

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

2、不同屬性

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

3、任意形狀

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

4、領域最小化

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

5、處理「雜訊」

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

6、記錄順序

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

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

本文共計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、劃分法

劃分法(partitioning methods)，給定一個有N個元組或者紀錄的數據集，分裂法將構造K個分組，每一個分組就代表一個聚類，K<N。使用這個基本思想的演算法有：K-MEANS演算法、K-MEDOIDS演算法、CLARANS演算法。

2、層次法

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

3、密度演算法

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

4、圖論聚類法

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

5、網格演算法

基於網格的方法(grid-based methods)，這種方法首先將數據空間劃分成為有限個單元（cell）的網格結構,所有的處理都是以單個的單元為對象的。代表演算法有：STING演算法、CLIQUE演算法、WAVE-CLUSTER演算法。

6、模型演算法

基於模型的方法(model-based methods)，基於模型的方法給每一個聚類假定一個模型，然後去尋找能夠很好的滿足這個模型的數據集。通常有兩種嘗試方向：統計的方案和神經網路的方案。

(3)圖的聚類演算法擴展閱讀：

聚類分析起源於分類學，在古老的分類學中，人們主要依靠經驗和專業知識來實現分類，很少利用數學工具進行定量的分類。隨著人類科學技術的發展，對分類的要求越來越高，以致有時僅憑經驗和專業知識難以確切地進行分類，於是人們逐漸地把數學工具引用到了分類學中，形成了數值分類學，之後又將多元分析的技術引入到數值分類學形成了聚類分析。聚類分析內容非常豐富，有系統聚類法、有序樣品聚類法、動態聚類法、模糊聚類法、圖論聚類法、聚類預報法等。

在商業上，聚類可以幫助市場分析人員從消費者資料庫中區分出不同的消費群體來，並且概括出每一類消費者的消費模式或者說習慣。它作為數據挖掘中的一個模塊，可以作為一個單獨的工具以發現資料庫中分布的一些深層的信息，並且概括出每一類的特點，或者把注意力放在某一個特定的類上以作進一步的分析；並且，聚類分析也可以作為數據挖掘演算法中其他分析演算法的一個預處理步驟。

㈣ 各類聚類演算法的特點和優缺點

聚類演算法是數據分析和機器學習中的重要工具，它們能夠將相似的數據點分組在一起。在眾多聚類演算法中，K-means、均值漂移（MeanShift）、DBSCAN、高斯混合（Mixture-of-Gaussian）、層次聚類（Hierarchical clustering）以及圖團體檢測（Graph community Detection）是常見且具有代表性的方法。每種演算法都有其獨特的特點、優點與局限性。

在眾多聚類演算法中，K-means演算法以其快速的計算速度和簡單的實現方式而著稱。然而，K-means演算法依賴於隨機種子點的選取，不同種子點可能導致截然不同的結果，這增加了演算法的不確定性。

均值漂移（MeanShift）聚類是一種基於密度的演算法，與K-means相比，它更少受到均值的影響，更加穩健。但選擇合適的窗口半徑r仍然是一個挑戰。

DBSCAN演算法是一種著名的密度聚類方法，通過設置距離r和minPoints參數來定義密度的聚集。然而，選擇合適的這些參數是其實踐中的關鍵挑戰。

高斯混合（Mixture-of-Gaussian）聚類通過擬合數據為多個正態分布的混合模型，以實現聚類。它提供了強大的模型擬合能力，但缺乏直接的可視化結果和明確的聚類數量估計。

層次聚類演算法通過構建聚類樹（或稱為層次聚類樹）來顯示數據之間的關系。合並中止條件是區分不同層次聚類演算法的關鍵，而基於鏈接的聚類演算法則從細小的聚類逐步合並，形成樹狀結構。然而，該演算法的效率較低，且時間復雜度較高。

圖團體檢測（Graph community Detection）則關注於圖數據的聚類，通過識別圖中的緊密連接的子圖來實現聚類。聚類間的距離度量不同，如單鏈接、完全鏈接、中心鏈接、平均鏈接和組平均等，每種度量都有其優缺點，如敏感性、緊湊性等。

總的來說，每種聚類演算法都有其獨特的優勢和適用場景。選擇合適的演算法需要根據具體的數據特性和應用需求來決定，同時充分考慮演算法的局限性以避免潛在的誤判。

㈤ 多視圖譜聚類演算法介紹

假設給出了具有多個視圖的數據 。

視圖v的相似度矩陣：

視圖v的拉普拉斯矩陣：

單視圖聚類演算法解決了歸一化圖拉普拉斯運算元 如下的優化問題：

其中的tr代表求矩陣的跡。

矩陣 的行是數據點的嵌入，就是說一行對應一個數據，一共有n行，然後用k均值演算法進行聚類。

作者的多視圖譜聚類框架建立在標准譜聚類基礎上，增加了半監督學習中的共正則化框架增加單一視圖。

半監督學習中的共正則化基本上是通過使不同數據視圖中的學習的假設在未標記數據上一致。

框架成功採用了兩個主要假設：(a)每個視圖中的真實目標函數應該就未標記數據的標簽(兼容性)達成一致;(b)視圖在類標簽(條件獨立性)下是獨立的。

兼容性假設允許我們通過進搜索通過僅搜索兼容的函數來縮小可能的目標假設的空間。

作者提出了兩種基於共正則化的方法，使得不同視圖的聚類假設彼此一致。同時作者構建包含所有數據視圖的拉普拉斯運算元，同時在拉普拉斯運算元的基礎上進行了規范化，使得每個拉普拉斯運算元得到的聚類結構在每個視圖中一致。

第一個共正則化強制一個視圖對 的特徵向量應該具有高度的成對相似性(使用成對的正則化標准)。第二個共正則化方案是通過將他們規范化為共同的共識(基於中心的共正則化)來強制使視圖特定的特徵向量看起來相似。

在多視圖的情況下，我們希望每個視圖的特徵向量矩陣是相似的。相當於在強制使所有視圖中的譜聚類假設相同。

先討論雙視圖情況。

提出以下損失函數作為兩個視圖之間聚類結果是否一致性的度量。

其中的 是 的相似矩陣。

進行除法的意義在於進行歸一化使得兩個視圖具有可比較性。

然後作者選擇了線性核作為相似性的度量方式。

從而得出：

選擇線性核的原因：

因為 對上面的代價函數進行化簡最終的到

然後我們在其中增加各個視圖之間的譜聚類目標函數，得到以下的最大化問題：

然後我們可以通過不斷的進行迭代去最大化上面的式子。

例如當給定 時，上式的優化目標就變成了：

這時候就化簡成了普通的單視圖的優化目標函數的形式。它的拉普拉斯矩陣為 。

上面的拉普拉斯矩陣是一種自適應(隨著每次迭代，拉普拉斯運算元會改變)的，結合內核和拉普拉斯運算元的方法。

然後我們可以交替最大化使得演算法得到最大值。但是同時要注意選擇合適的初始化值從而避免陷入局部最大值。迭代開始時，可以選擇最具有信息性的視圖開始進行迭代。

對固定的 和 ，可以保證演算法收斂。實踐中通過觀察連續迭代之間的目標值的差值來監視是否收斂，當低於某一閾值時，停止迭代。

我們擴展上一節中提出的共正則化譜聚類。對於m個視圖，我們有：

在這里，對所有的共正則化部分使用了共同的 進行平衡。然後優化方法和雙視圖情況類似。

給定一個視圖的 ，優化目標如下所示：

然後我們可以通過迭代對它進行不斷優化。

這里提出的正則化方案是對上面的正則化方案的一種替代。將所有視圖的特徵向量 朝向共同的中心 (類似一組共同的特徵向量)。這樣可以減少正則化項的對數(m對)。

目標函數可以寫為：

這個目標函數平衡各個譜聚類目標與每個視圖特定特徵向量 和共有特徵向量 之間的折中。同時與第一種共正則化方法不同的是，我們可以對每一個正則化項設置一個參數來反映它的重要性。

這里的優化方法和上面的還是一樣的，通過固定其他特徵向量對單個特徵向量進行優化。不同的地方在於需要對 進行優化，我們可以固定其他變數，然後對他進行優化。

只有對 進行優化時，和第一種共正則化方法不同，需要優化以下式子：

然後由矩陣的跡的性質tr(AB)=tr(BA)和tr(mA+nB)=mtr(A)+ntr(B)可以得到：

然後就又將這個問題轉化成了單視圖譜聚類的目標函數形式。對應的拉普拉斯矩陣為：

使用第二種基於中心的共正則化和第一種共正則化的另一個差別在於這種方法可以直接得到最終的特徵向量集合 ，然後可以直接對他應用k均值等聚類演算法進行聚類。而第一種共正則化方法需要對得出的所有特徵向量集合進行拼接等處理步驟。

基於中心的共正則化方法一個缺點是容易受到有雜訊的視圖的影響，為了解決這個問題，需要仔細的選擇每個視圖對應的權重 。

參考論文：Co-regularized Spectral Clustering，Abhishek Kumar∗，Piyush Rai∗，Hal Daum ́e III.