1、聚類算法總結劃分方法每個數據被歸入相互不同重疊的k個cluster之一目標：cluster內距離最小、K-Means 算法：(1)算法思想：指定 cluster數目為k；隨機劃分數據到 k個子集；計算每個子集的 中心”數據；*計算所有數據到 k個 中心”距離；*將每個數據所屬類別調整到里數據最近中心”所代表的cluster/子集；重復上述兩個步驟，直至收斂。(2)算法優點：簡單，實現簡單；運行時間復雜度較低：0(元組數n * cluster數k *迭代次數t)。目標明確：最小化類內距離。(3)算法不足：易陷入局部最優解(和初始值密切相關)；中心”計算時，如何處理標稱數據？；需要預置k值；對噪聲

2、數據/孤立點敏感；非凸cluster的識別能力弱。(4)算法改進：K-Means算法的 中心”點是虛擬數據，不一定在數據集合中存在，改成某實際靠近中心點且存在的數 據，得到 &中心點”算法；降低了噪聲、離群點的影響，增加了時間代價；標稱屬性的 中心”用眾數代替均值，及改進的距離計算方法；改進初始時刻數據劃分方法或中心點選擇方法，如PAM算法。二、PAM算法(圍繞中心點劃分方法)(1)算法思想：隨機選擇k個種子為中心點，即 cluster的代表，將數據點劃歸到最近中心點/種子代表的cluster；對所有(種子，非種子)對，嘗試交換它們，檢查是否能提高聚類質量：所有元組到各自中心”的距離和

3、。選擇最好的能提升結果質量所對應的交換，實施交換，直至算法收斂。(2)算法評述：K-medoids算法的改進；可以用一些啟發式方法選擇交換的種子和非種子；易陷入局部最優。三、針對大規模數據集改進算法(1)主要解決問題：數據集無法一次載入內存；重復多次計算一個點/數據到其它數據的距離;(2) CLARA 算法：對數據集中的數據進行 采樣，在采樣得到的子集上尋找中心點，執行 PAM算法；(3) CLARANS 算法：執行PAM算法，其中沒有搜索所有可能的實施交換的對，僅僅執行L次(種子，非種子)對的交換;層次方法層次聚類:在不同概念層次上各自形成clusters,構成一棵樹狀圖(Dendrogra

4、m)重點考慮優化目標：cluster之間的距離最大化核心問題：兩個 cluster之間的距離如何計算的問題(最小、最大、平均距離、虛擬中心、Medoid距一、主要層次算法：(1) AGNES算法(凝聚思想)：自底向上，找兩個簇，它們中最相似兩個數據的距離最小，則合并這兩個簇；迭代該過程，直至所有 對象最終合并形成一個簇。(2) DIANA算法(分裂思想，計算量較大通常采用啟發式，為了效率通常不對已做出的劃分決策回溯) 自頂向下，找一個簇，簇中最近兩個數據的距離在所有簇中最大，分裂該簇；迭代該過程；(3)算法評估：聚合/分裂點的選擇，極大影響算法的性能；算法時間復雜度較高；二、針對大規模數據集改

5、進算法：BIRCH算法(利用層次結構的平衡迭代規約和聚類)(1)算法思想：利用統計信息表示一個簇，避免存儲簇中所有數據；實現簇信息的壓縮存儲。也可以認為是定義了一 個簇的特征描述。(2)算法步驟：掃描數據集，逐步構建一棵包括了簇統計信息/特征的樹(聚類特征向量 CF,包含聚類的特征，計算簡單)，非葉結點是統計信息；一個葉節點是一個簇，不同的數據歸入不同簇；若某個簇的數據太多，距離太大，考慮分裂該簇(及其父節點)；(3)算法特點：每個非葉結點的聚類特征向量 包括其所有“后代”葉子節點數據 的統計信息；新數據加入后，歸入某一類，更新其所有父節點的統計信息 /聚類特征向量；當葉結點的父節點特征向量

6、達到某個“臨界點”/滿足某些條件時，考慮分裂該節點；增量式算法；算法參數1:分支因子B,控制非葉結點的最大孩子數；算法參數2： cluster直徑最大彳I的界 T,超過就分裂此 cluster。(4)算法優點：時間復雜度O(n),只需要裝入一次數據集，適用于大型數據集；重點在CF和CF-Tree的設計和利用很巧妙，壓縮存儲數據集；動態調整參數，使得其和機器的內存配置相適應；對葉條目對應的 cluster可以繼續處理：采用其它技術(比如聚類)，刪除小的cluster (離群點)，合并稠密的cluster；（5）算法缺點：B, T和L的確定沒有標準和經驗，但它們顯著影響性能 對數據對象的輸入次序敏

7、感/次序相關的T的使用，使得 cluster形狀受約束Chameleon算法（使用動態建模的多階段層次聚類）（1）核心思想兩個cluster之間連邊很多，且距離近，則合并之。（2）算法步驟：從數據集開始，每個數據視為n-D空間中的一個點；計算每個點的k個最近鄰（構建 KNN圖），然后連接，并且每個連接賦予權值（距離）；劃分圖：使得分割邊（被切斷的邊）的權值之和最小，評估了簇之間的絕對互連性；合并RI （相對互連度：（最小二分）邊割和）和RC （相對接近度：（最小二分）平均權重）大于用戶指定 閾值的簇。（3）時間復雜度最壞是 O（n2）；概率層次聚類（使用概率模型度量簇之間的距離，使用生成模型，

8、找出擬合觀測數據的最佳參數值）（1）層次聚類方法的缺點：為層次聚類選擇一種好的距離度量常常是困難的；為了使用算法的方法，數據對象不能有缺失的屬性值，而實際中數據被部分觀測情況下很難計算距離；大部分算法的層次聚類方法都是啟發式的（每一步局部搜索號的合并 /劃分），因此聚類層次結果的優化目標可能不清晰；（2）算法核心思想：用概率模型來度量 cluster之間的距離，避免層次方法中最優距離定義問題；基于生成模型（一個聯合概率分布），例如每個 cluster來自一個高維高斯分布等；cluster是該生成模型的一個樣本集；生成模型的參數由cluster的樣本集估計出來；生成模型將對樣本集進行新的劃分；該

9、過程循環迭代直到收斂；算法基本過程就是 EM或K-Means。基于密度的方法DBSCAN算法（一個 cluster就是密度連通的最大點集）（1） 一些概念：q直接密度可達p： q是核心對象，q的領域中有p；q密度可達p：存在一條q到p的鏈路，前一個數據對象直接可達后一個數據對象；鏈上 前n-1個數 據對象都是核心對象；對直接密度可達概念的擴展密度連通：任意給定兩個數據對象p, q,稱p, q密度連通，當且僅當存在一個數據o,。分別密度可達 p,q。（2）算法步驟:初始時刻，所有點都標記為unvisited ,隨機選擇一個記為 p,并標記為visaed,檢查是否是核心對象，否則記為噪聲/非核心點

10、；若p是核心對象，則創建新簇 C,將N(p)(p的鄰域點集)添加到集合N;檢查N中的點，假設為q,加入C(必然是p簇中的一個)，檢查q的標記，若是unvisited ,則改為visited , 并檢查其鄰域大小|N(q)|,若q為核心對象，則 N(q) (q的鄰域點集)都加入 N;N為空時，找到一個簇 C;重復上述過程，得到其它的簇。(3)算法評估：使用空間索引可以使得時間復雜度為O(nlogn), n為數據庫對象數，其復雜度為O(n2)；若e和Minpts設置恰當，則該算法可以有效地發現任意形狀的簇。但是參數的設置難以確定，特別對于高維數據集，對參數值敏感；只有一組全局參數，使得基于密度的簇

11、關于鄰域的閾值是單調的。OPTICS算法(使用簇排序，不顯式產生數據集聚類)假定任何一個點的概率密度依賴該點(出現概率較大)到樣本的距離(1) 一些概念：核心距離：p核心距離是最小半徑使得至少包含 Minpts個對象，若p不是核心對象，則沒有定義。可達距離：q到p的可達距離是從 q密度可達p的最小半徑值(q必須是核心對象，p必須在q的鄰域 內)，可達距離為 max core-distance(q), dist(p, q),若q不是核心對象，則沒有定義。(2)算法步驟：開始用數據庫中的任意對象作為當前對象p,檢索p的e鄰域，確定核心距離并設置可達距離為未定義輸出當前對象p,若p不是核心對象，則轉

12、移到OrderSeeds表下一個(若 OrderSeeds表為空，則找數據庫中的下一個)；若p是核心對象，則對于 p的e鄰域中的每個對象 q,更新從p到q的可達距離，并且如果 q尚未處理 則加入到OrderSeeds表中不斷迭代知道輸入數據庫為空，并且 OrderSeeds為空。(3)算法評估：算法結構與DBSCAN相似，使用空間索引可以使得時間復雜度為O(nlogn),否則為O(n2)。以上兩種方法的密度估計方式對半徑值非常敏感，隨著半徑的稍微增加，密度顯著改變，需要使用核密度估計(非參數密度估計方法，減少參數值帶來的敏感性)。DENCLUE算法(基于密度分布函數的聚類)核心思想想象一個場/

13、平面，上面堆了很多沙堆，每個沙堆獨立看，是芷態分布”；平面上的每個點都是很多個沙堆“疊加”出來一個高度，高度代表密度，出現一個新樣本的概率；“正態”沙堆多了，彼此交疊，就成了 “綿延起伏”的沙漠；沙漠中存在一些沙丘的高點，高于周圍 的沙；形成一個局部最大值；正式的名稱是“局部吸引子”達到一定高度(h)的局部吸引子”可以被視為簇中心，用來把樣本數據劃歸到不同的簇中。用爬山式方法把樣本劃分給局部吸引子，因為“沙漠”是一個概率密度函數，存在梯度，沿梯度方向 讓每個樣本找到一個“山頂”。若一個樣本數據爬到了一個非局部吸引子的山頂(< h),那么這個數據就被認為“噪聲” ；DBSCAN的一般化，抗

14、噪聲。核密度估計通過把噪聲均勻分不到輸入數據，降低噪聲影響。基于網格的方法STING （統計信息網格網格）（1）方法介紹空間被劃分為多個超立方體的小格子，小格子具有不同的層次/分辨率，高層小格子被劃分為多個低層的小格子；每個小格子有統計信息 （計數/最大值/最小值/均值/標準差/服從分布等），高層格子的統計信息可由底層 的來計算；（2）方法評估：基于網格的計算獨立于查詢，不依賴于查詢（因為存儲在每個單元的統計信息提供了數據匯總信息）；網格結構利于并行處理與增量更新 ；主要優點：效率高（產生聚類的時間復雜度 O（n）, n是對象數；層次結構建立后，查詢時間為O（g）, g是最底層網格單元個數，通

15、常遠小于n）。主要缺點：由于未考慮子女單元和其相鄰單元之間的聯系，分類邊界都是水平或垂直的線，可能降低簇的質量和精確性。CLIQUE （類似于Apriori的基于網格的聚類，發現子空間基于密度的簇）如果在3-D空間中是稠密的，那么在其任何投影空間中都應該是稠密的，類似 Apriori思想，尋找高維 空間的稠密單元。 （1）算法步驟：第一階段：把 d-維數據空間劃分若干互不重疊的矩形單元，并且從中識別出稠密單元，迭代連接子空 間，并檢查連接后的子空間中的點數是否滿足密度閾值，直到都不稠密時終止。第二階段：使用每個子空間中的稠密單元來裝配可能具有任意形狀的簇（利用最小描述長度，使用最 大區域來覆蓋

16、連接的稠密單元。原問題是NP難的，因此采用貪心策略）。（2）方法評估自動識別高維數據空間中數據稠密的子空間不需要對數據分布做假設，數據輸入次序無關/不敏感輸入數據的多少和維度，對算法的時間復雜度影響是線性的缺點：聚類精度可能會降低聚類評估聚類評估分為三步：在聚類開始前，估計聚類趨勢（Hopkins統計量），判斷能否聚類均勻數據集不可以。判斷可以聚類后， 確定簇數（經驗方法、肘方法、交叉驗證法）；聚類完成后，度量聚類質量（給定標準-外在方法；沒有標準 -內在方法）；一、估計聚類趨勢每個均勻采樣得到的樣本都找一個離自己最近的數據集中的點，記為xi;均勻隨機從D中采樣n個點q1,q2,qn,并找出D

17、中離qi最近（不等于qi）的點，記為yi;Hopkins 統計量:i1n時，匯y會顯著小于 匯x，H接近0；不包含明顯的“自然簇”時（距離較遠）'=二弦簇（距離較近） ,H約為0.5。、確定簇數經驗方法：，（n/2由簇，每個簇«2n）個數據，總數據n個肘方法（增加簇數 k,檢查簇內方差 S隨著k降低的速度，找拐點）：給定k,采用一種聚類方法對數據集聚類，計算每個簇的簇內方差之和S;增加k, S會降低，因為簇多了，簇小了，簇內差異變小；檢查S隨k降低的速度，或者說找第一個“拐點”；交叉驗證法：將數據集劃分為近似相等的 m分；用其中m-1份構建聚類模型，剩下一份檢驗聚類質量（如：數據到最近“簇心”的距離平方和）對給定的k,重復上述過程 m次；比較不同的k；三、度量聚類質量（1）外在方法：給定一個標準，標準看成是“類標號”，故是有監督的（Bcubed精度和召回率）；rl 如果 = L（o ）qC（6） = C（o ）Correctnesses-,）其他一個對象的精度指：C給出的同一個簇中，多少個等于L給定的Precision BCubedn V Correctness(?in ill | 1% I i *= C(q) I II一個對象的召回率指：L給出的同一個簇白對象多少被 C正確給定了1 二Recall BC