聚類分析Contents聚類分析介紹01層次聚類02密度聚類03譜聚類04聚類分析介紹什么是聚類？(cluster)聚類分析介紹什么是聚類？(cluster)聚類就是針對大量數據或者樣品根據數據本身的特性研究數據分類規則及方法（無監督方式），并遵循這個分類方法實現“同類相同、異類相異”。聚類分析介紹什么是聚類分析？

(clusteranalysis)把“對象”分成不同的類別這些類不是事先給定的，而是直接根據數據的特征確定的把相似的東西放在一起，從而使得類別內部的“差異”盡可能小，而類別之間的“差異”盡可能大聚類分析就是按照對象之間的“相似”程度把對象進行分類聚類分析介紹什么是聚類分析？(兩種分類方式)聚類分析的“對象”可以是所觀察的多個樣本，也可以是針對每個樣本測得的多個變量按照變量對所觀察的樣本進行分類稱為Q型聚類按照多項經濟指標(變量)對不同的地區(樣本)進行分類按照樣本對多個變量進行分類，則稱為R型聚類按照不同地區的樣本數據對多個經濟變量進行分類兩種聚類沒有什么本質區別，實際中人們更感興趣的通常是根據變量對樣本進行分類(Q型聚類)聚類分析介紹什么是聚類分析？(按什么分類)按對象的“相似”程度分類根據樣本的觀測數據測度變量之間的相似性程度可以使用夾角余弦、Pearson相關系數等工具，也稱為相似系數變量間的相似系數越大，說明它們越相近根據變量來測度樣本之間的相似程度則使用“距離”把離得比較近的歸為一類，而離得比較遠的放在不同的類聚類分析介紹相似性的度量

(樣本點間距離的計算方法)在對樣本進行分類時，度量樣本之間的相似性使用點間距離點間距離的計算方法主要有歐氏距離(Euclideandistance)平方歐氏距離(SquaredEuclideandistance)曼哈頓距離(Blockdistance)切比雪夫距離(Chebychevdistance)馬氏距離(Minkovskidistance)最常用的是平方歐氏距離聚類分析介紹保險業土地使用市場營銷城市規劃幫市場分析人員從客戶基本庫中發現不同的客戶群，從而可以對不同的客戶群采用不同營銷策略在地球監測數據庫中，發現相同的土地使用區域發現汽車保險中索賠率較高的客戶群根據房子的類型、價值和地理位置對其進行分組地震研究將觀測到的震中點沿板塊斷裂帶進行聚類最終可以得出地震高危區聚類分析的實際應用聚類分析介紹聚類分析的算法分類根據處理復雜分布的，高維的或者混合屬性的大規模數據方法進行大致分類基于網格(Grid-Based)STING算法、CLIQUE算法等圖論譜聚類基于劃分（Partitioning）K-均值聚類，K-中心聚類等基于層次(Hierarchical)BIRCH算法、CURE算法、CHAMELEON算法等基于密度(Density-Based)DBSCAN算法、OPTICS算法、DENCLUE算法等基于模型(Model-Based)統計學的COBWEB聚類和神經網絡的SOM聚類模糊理論相關領域結合的聚類技術FCM聚類自然計算相關領域結合的聚類技術遺傳聚類、克隆選擇聚類Contents聚類分析介紹01層次聚類02密度聚類03譜聚類04層次聚類層次的聚類方法將數據對象組成一棵聚類的樹根據層次分解是自底向上,還是自頂向下形成,層次的聚類方法可以進一步分為凝聚的(agglomerative)和分裂的(divisive)層次聚類

純粹的層次聚類方法的聚類質量受限于如下特點：一旦一個合并或分裂被執行，就不能修正最近的研究集中于凝聚層次聚類和迭代重定位方法的集成

使用距離矩陣作為聚類標準.該方法不需要輸入聚類數目k,但需要終止條件層次聚類凝聚的(agglomerative)和分裂的(divisive)層次聚類圖示Step0Step1Step2Step3Step4bdceaabdecdeabcdeStep4Step3Step2Step1Step0agglomerative(AGNES)divisive(DIANA)層次聚類四個廣泛采用的簇間距離度量方法

最小距離：dmin(Ci,Cj)=min

p∈Ci,p’∈Cj

|p-p’|

最大距離：dmax(Ci,Cj)=max

p∈Ci,p’∈Cj|p-p’|

平均值的距離：dmean(Ci,Cj)=|mi-mj|

平均距離(簇的直徑D)：davg(Ci,Cj)=∑p∈Ci∑p’∈Cj|p-p’|

/ninj其中,|p-p’|是兩個對象p和p’之間的距離

mi是簇Ci

的平均值，ni是簇Ci中對象的數目

層次聚類簇與簇之間鄰近度的定義:每個簇中的點數不一定相等，如何計算兩個不同簇之間的鄰近度呢？常用的有三種方法：單鏈（MIN準則），全鏈（MAX準則），組平均技術。單鏈（MIN）定義簇的鄰近度為不同簇的兩個最近的點之間的鄰近度。層次聚類全鏈（MAX）定義簇的鄰近度為不同簇中兩個最遠的點之間的鄰近度作為簇的鄰近度。組平均是一種基于圖的方法。它定義簇鄰近度為取自不同簇的所有點對鄰近度的平均值（平均長度）。層次聚類基于劃分的聚類方法構造n個對象數據庫D的劃分,將其劃分成k個聚類啟發式方法:k-平均值(k-

means)和k-中心點(k-

medoids)算法k-平均值(MacQueen’67):每個簇用該簇中對象的平均值來表示k-中心點或PAM(Partitionaroundmedoids)(Kaufman&Rousseeuw’87):每個簇用接近聚類中心的一個對象來表示這些啟發式算法適合發現中小規模數據庫中的球狀聚類對于大規模數據庫和處理任意形狀的聚類,這些算法需要進一步擴展層次聚類——K-means聚類算法描述為中心向量c1,c2,…,ck初始化k個種子分組:將樣本分配給距離其最近的中心向量由這些樣本構造不相交（non-overlapping

）的聚類確定中心:用各個聚類的中心向量作為新的中心重復分組和確定中心的步驟，直至算法收斂層次聚類——K-means聚類算法的具體過程從數據集中任意選取k個賦給初始的聚類中心c1,c2,…,ck；對數據集中的每個樣本點xi，計算其與各個聚類中心cj的歐氏距離并獲取其類別標號：

按下式重新計算k個聚類中心；重復步驟2和步驟3，直到達到最大迭代次數、聚類目標函數達到最優值或者兩次迭代得到的目標函數變化小于給定的

為止。層次聚類——K-means聚類例012345678910012345678910012345678910012345678910K=2任意選擇

K個對象作為初始聚類中心將每個對象賦給最類似的中心更新簇的平均值重新賦值更新簇的平均值重新賦值層次聚類——K-means聚類Matlab程序實現function[M,j,e]=kmeans(X,K,Max_Its)[N,D]=size(X);I=randperm(N);M=X(I(1:K),:);Mo=M;forn=1:Max_Itsfork=1:KDist(:,k)=sum((X-repmat(M(k,:),N,1)).^2,2)';end

[i,j]=min(Dist,[],2);fork=1:Kifsize(find(j==k))>0

M(k,:)=mean(X(find(j==k),:));endend層次聚類——K-means聚類Matlab程序實現（續）Z=zeros(N,K);form=1:NZ(m,j(m))=1;end

e=sum(sum(Z.*Dist)./N);fprintf('%dError=%f\n',n,e);Mo=M;end層次聚類——K-means聚類在圖像分割上的簡單應用例1：圖片：一只遙望大海的小狗；此圖為100x100像素的JPG圖片，每個像素可以表示為三維向量（分別對應JPEG圖像中的紅色、綠色和藍色通道）

；將圖片分割為合適的背景區域（三個）和前景區域（小狗）；使用K-means算法對圖像進行分割。層次聚類——K-means聚類在圖像分割上的簡單應用分割后的效果注：最大迭代次數為20次，需運行多次才有可能得到較好的效果。層次聚類——K-means聚類在圖像分割上的簡單應用例2：注：聚類中心個數為5，最大迭代次數為10。層次聚類——K-means聚類優點:相對有效性:O(tkn),其中n

是對象數目,k

是簇數目,t是迭代次數;通常,k,t<<n.當結果簇是密集的，而簇與簇之間區別明顯時，它的效果較好弱點只有在簇的平均值(mean)被定義的情況下才能使用.可能不適用于某些應用,例如涉及有分類屬性的數據需要預先指頂簇的數目k,不能處理噪音數據和孤立點(outliers)不適合用來發現具有非凸形狀(non-convexshapes)的簇層次聚類——K-medoids聚類k-平均值算法對孤立點很敏感!因為具有特別大的值的對象可能顯著地影響數據的分布.k-中心點(k-Medoids):不采用簇中對象的平均值作為參照點,而是選用簇中位置最中心的對象,即中心點(medoid)作為參照點.012345678910012345678910012345678910012345678910012345678910012345678910層次聚類——K-medoids聚類找聚類中的代表對象(中心點)PAM(PartitioningAroundMedoids,1987)首先為每個簇隨意選擇選擇一個代表對象,剩余的對象根據其與代表對象的距離分配給最近的一個簇;然后反復地用非代表對象來替代代表對象，以改進聚類的質量

PAM

對于較小的數據集非常有效,但不能很好地擴展到大型數據集層次聚類——K-medoids聚類基本思想：首先為每個簇隨意選擇選擇一個代表對象;剩余的對象根據其與代表對象的距離分配給最近的一個簇；然后反復地用非代表對象來替代代表對象,以改進聚類的質量；聚類結果的質量用一個代價函數來估算。層次聚類——K-medoids聚類為了判定一個非代表對象Orandom是否是當前一個代表對象Oj的好的替代,對于每一個非代表對象p,考慮下面的四種情況：

第一種情況：p當前隸屬于代表對象Oj.如果Oj被Orandom所代替,且p離Oi最近,i≠j,那么p被重新分配給Oi

第二種情況：p當前隸屬于代表對象Oj.如果Oj被Orandom代替,且p離Orandom最近,那么p被重新分配給Orandom

1.重新分配給Oi 2.重新分配給Orandom層次聚類——K-medoids聚類第三種情況：p當前隸屬于Oi，i≠j。如果Oj被Orandom代替，而p仍然離Oi最近，那么對象的隸屬不發生變化

第四種情況：p當前隸屬于Oi，i≠j。如果Oj被Orandom代替，且p離Orandom最近，那么p被重新分配給Orandom

3.不發生變化4.重新分配給Orandom層次聚類——K-medoids聚類算法:k-中心點(1)隨機選擇k個對象作為初始的代表對象；(2)repeat (3)指派每個剩余的對象給離它最近的代表對象所代表的簇； (4)隨意地選擇一個非代表對象Orandom； (5)計算用Orandom代替Oj的總距離E,如果E比取代前下降則則用Orandom替換Oj，形成新的k個代表對象的集合，返回（4）；(6)until不發生變化(7)如果所有非代表對象都無法取代已存在的簇中心，則結束替代過程，并輸出結果層次聚類——K-medoids聚類PAM012345678910012345678910K=2ArbitrarychoosekobjectasinitialmedoidsAssigneachremainingobjecttonearestmedoidsRandomlyselectanonmedoidobject,OramdomComputetotalcostofswapping012345678910012345678910TotalCost=26SwappingOandOramdomIfqualityisimproved.DoloopUntilnochange012345678910012345678910TotalCost=20層次聚類——K-medoids聚類PAM當存在噪音和孤立點時,PAM比

k-平均方法更健壯.這是因為中心點不象平均值那么容易被極端數據影響

PAM對于小數據集工作得很好,但不能很好地用于大數據集

每次迭代O(k(n-k)2)

其中

n

是數據對象數目,

k是聚類數基于抽樣的方法, CLARA(ClusteringLARgeApplications)層次聚類——CLARACLARA(KaufmannandRousseeuwin1990)不考慮整個數據集,而是選擇數據的一小部分作為樣本它從數據集中抽取多個樣本集,對每個樣本集使用PAM,并以最好的聚類作為輸出優點:可以處理的數據集比PAM大缺點:有效性依賴于樣本集的大小基于樣本的好的聚類并不一定是整個數據集的好的聚類,樣本可能發生傾斜

例如,Oi是最佳的k個中心點之一,但它不包含在樣本中,CLARA將找不到最佳聚類層次聚類——CLARACLARA--效率由取樣大小決定PAM→利用完整資料集

CLARA→利用取樣資料集

盲點：取樣范圍不包含最佳解

sampledbestTrade-off層次聚類——CLARACLARA改良解決：CLARANS(ClusteringLargeApplicationbaseduponRANdomizedSearch)應用

graph考慮緊鄰節點不局限于區域性復雜度：O(n^2)→缺點層次聚類——CLARANSCLARANS(“Randomized”CLARA)(1994)CLARANS(AClusteringAlgorithmbasedonRandomizedSearch)(NgandHan’94)CLARANS將采樣技術和PAM結合起來CLARA在搜索的每個階段有一個固定的樣本CLARANS任何時候都不局限于固定樣本,而是在搜索的每一步帶一定隨機性地抽取一個樣本聚類過程可以被描述為對一個圖的搜索,圖中的每個節點是一個潛在的解,也就是說k-medoids相鄰節點：代表的集合只有一個對象不同在替換了一個代表對象后得到的聚類結果被稱為當前聚類結果的鄰居層次聚類——CLARANSCLARANS(“Randomized”CLARA)(1994)如果一個更好的鄰居被發現,CLARANS移到該鄰居節點,處理過程重新開始,否則當前的聚類達到了一個局部最優如果找到了一個局部最優,CLARANS從隨機選擇的節點開始尋找新的局部最優實驗顯示CLARANS比PAM和CLARA更有效CLARANS能夠探測孤立點聚焦技術和空間存取結構可以進一步改進它的性能(Esteretal.’95)層次聚類——CLARANSCLARANS(“Randomized”CLARA)(1994)1、輸入參數numlocal和maxneighbor。numlocal表示抽樣的次數，maxneighbor表示一個節點可以與任意特定鄰居進行比較的數目。令：i=1，i用來表示已經選樣的次數mincost為最小代價，初始時設為大數。

2、設置當前節點current為Gn中的任意一個節點。

3、令j=1。（j用來表示已經與current進行比較的鄰居的個數）

4、考慮當前點的一個隨機的鄰居S，并計算兩個節點的代價差。5、如果S的代價較低，則current:=S，轉到步驟3。

6、否則，令j=j+1。如果j<=maxneighbor,則轉到步驟4。

7、否則，當j>maxneighbor，當前節點為本次選樣最小代價節點.如果其代價小于mincost,令mincost為當前節點的代價，bestnode為當前的節點。

8、令i=i+1，如果i〉numlocal,輸出bestnode，運算中止.否則，轉到步驟2。算法步驟：層次聚類——CLARANSCLARANS(“Randomized”CLARA)(1994)1）代價值，主要描述一個對象被分到一個類別中的代價值，該代價值由每個對象與其簇中心點間的相異度（距離或者相似度）的總和來定義。代價差則是兩次隨機領域的代價差值。

（2）更新鄰接點，CLARANS不會把搜索限制在局部區域，如果發現一個更好的近鄰，CLARANS就移到該近鄰節點，處理過程從新開始；否則，當前的聚類則產生了一個局部最小。如果找到一個局部最小，CLARANS從隨機選擇的新節點開始，搜索新的局部最小。當搜索的局部最小解達到用戶指定的數目時，最好的局部最小作為算法的輸出。從上面的算法步驟也可以看出這一思想。在第5步中更新節點current。層次聚類綜合比較KmeansKmedoidsCLARACLARANS優點簡單不受極值影響可處理大數據找到最佳解缺點受極值影響無法處理大數據不一定是最佳解速度慢復雜度O(nkt)O(k(n-k)^2)O(ks^2+k(n-k))O(n^2)精確度速度層次聚類層次聚類的主要缺點不具有很好的可伸縮性:時間復雜性至少是O(n2),其中n

對象總數合并或分裂的決定需要檢查和估算大量的對象或簇不能撤消已做的處理,聚類之間不能交換對象.如果某一步沒有很好地選擇合并或分裂的決定,可能會導致低質量的聚類結果

層次聚類改進層次方法的聚類質量的方法:將層次聚類和其他的聚類技術進行集成,形成多階段聚類BIRCH(1996):使用CF-tree對對象進行層次劃分,然后采用其他的聚類算法對聚類結果進行求精ROCK1999：基于簇間的互聯性進行合并CHAMELEON(1999):使用動態模型進行層次聚類CURE(1998):采用固定數目的代表對象來表示每個簇，然后依據一個指定的收縮因子向著聚類中心對它們進行收縮層次聚類——BIRCHBirch(BalancedIterativeReducingandClusteringusingHierarchies):利用層次方法的平衡迭代歸約和聚類由Zhang,Ramakrishnan和Livny提出(SIGMOD’96),該算法的特點是能利用有限的內存資源完成對大數據集的高質量的聚類，同時通過單遍掃描數據集能最小化I/O代價。

兩個重要概念聚類特征(ClusteringFeature,CF)聚類特征樹(ClusteringFeatureTree,

CF樹)聚類特征聚類特征(CF)是一個三元組，給出對象子類的信息的匯總描述設某個子類中有N個d維的點或對象{oI}，則該子類的CF定義如下

層次聚類——BIRCH聚類特征ClusteringFeature:CF=(N,LS,SS)N:數據點數目LS:N個節點特征線性和

Ni=1XiSS:N個節點特征平方和

Ni=1Xi2CF=(5,(16,30),(54,190))(3,4)(2,6)(4,5)(4,7)(3,8)層次聚類——BIRCH聚類特征假定簇C1中有兩個點（1，2，3），（3，2，1），簇C2有三個點（1，1，2），（2，2，1），（2，1，2），簇3由C1和C2構成，則：CF1=（2，（1+3，2+2，3+1），（

））=（2，（4，4，4），（10，8，10））CF2=（3，（1+2+2，1+2+1，2+1+2），（

））=（3，（5，4，5），（9，6，9））因此得到CF3為：CF3=（2+3，（4+5，4+4，4+5），（10+9，8+6，10+9））=（5，（9，8，9），（19，14，19））層次聚類——BIRCH聚類特征

層次聚類——BIRCHBIRCH算法有意思的是簇中心、簇半徑、簇直徑以及兩簇之間的距離D0到D3都可以由CF來計算，比如簇直徑

簇間距離這里的N，LS和SS是指兩簇合并后大簇的N，LS和SS。所謂兩簇合并只需要兩個對應的CF相加那可層次聚類——BIRCHBIRCH的CF樹聚類特征從統計學的觀點來看，聚類特征是對給定子類統計匯總:子聚類的0階,1階和2階矩(moments)記錄了計算聚類和有效利用存儲的關鍵度量,并有效地利用了存儲,因為它匯總了關于子類的信息，而不是存儲所有的對象CF樹是高度平衡的樹，它存儲了層次聚類的聚類特征

樹中的非葉節點有后代或“孩子”

非葉節點存儲了其孩子的CF的總和，即匯總了關于其孩子的聚類信息

CF樹有兩個參數----影響CF樹的大小分支因子B:定義非樹葉節點的孩子的最大個數閾值T:給出了存儲在樹的葉子節點中的子類的最大直徑

層次聚類——BIRCHBIRCH的CF樹CFtree的結構類似于一棵B-樹，它有3個參數：內部節點平衡因子B，葉節點平衡因子L，簇直徑閾值T。樹中每個Nlonleaf節點最多包含B個孩子節點，Leaf最多只能有L個MinCluster（初始劃分子簇），而一個MinCluster的直徑不能超過T。例如，一棵高度為3，B為5，L為6的一棵CF樹的例子如圖所示：層次聚類——BIRCHBIRCH的CF樹層次聚類——BIRCHBIRCH的CF樹B=5L=6CF1child1CF3child3CF2child2CF6child5CF1child1CF3child3CF2child2CF5child5CF1CF2CF6prevnextCF1CF2CF4prevnextRootNon-leafnodeLeafnodeLeafnode層次聚類——BIRCHCF樹構造過程(1)從根節點開始，自上而下選擇最近的孩子節點

(2)到達葉子節點后，檢查最近的元組CFi能否吸收此數據點

是，更新CF值

否，是否可以添加一個新的元組

是，添加一個新的元組

否則，分裂最遠的一對元組，作為種子，按最近距離重新分配其它元組

(3)更新每個非葉節點的CF信息，如果分裂節點，在父節點中插入新的元組，檢查分裂，直到root

層次聚類——BIRCHCF樹構造過程生成CF樹層次聚類——BIRCH構造CF樹算法起初，我們掃描數據庫，拿到第一個datapointinstance--（1,2,3）,我們創建一個空的Leaf和MinCluster，把點（1,2,3）的id值放入Mincluster，更新MinCluster的CF值為（1,（1,2,3），（1,4,9）），把MinCluster作為Leaf的一個孩子，更新Leaf的CF值為（1,（1,2,3），（1,4,9））。實際上只要往樹中放入一個CF（這里我們用CF作為Nonleaf、Leaf、MinCluster的統稱），就要更新從Root到該葉子節點的路徑上所有節點的CF值。層次聚類——BIRCH插入一個節點當又有一個數據點要插入樹中時，把這個點封裝為一個MinCluster（這樣它就有了一個CF值），把新到的數據點記為CF_new，我們拿到樹的根節點的各個孩子節點的CF值，根據D2來找到CF_new與哪個節點最近，就把CF_new加入那個子樹上面去。這是一個遞歸的過程。遞歸的終止點是要把CF_new加入到一個MinCluster中，如果加入之后MinCluster的直徑沒有超過T，則直接加入，否則譔CF_new要單獨作為一個簇，成為MinCluster的兄弟結點。插入之后注意更新該節點及其所有祖先節點的CF值。層次聚類——BIRCH生成CF樹1.從訓練集讀入第一個樣本點，將它放入一個新的CF三元組A，這個三元組的N=1，將這個新的CF放入根節點。2.讀入第二個樣本點，該點和樣本點A同在半徑為T的超球體內，因此將該點加入CFA,此時需更新A的三元組值，A的三元組中N=2。3.第三個樣本點不能融入之前兩個節點形成的超球體內，需要生成一個新的CF三元組B。此時根節點有兩個CF三元組A和B4.第四個樣本點和第三個樣本點在半徑小于T的超球體內，因此將該點加入CFB。層次聚類——BIRCH節點分裂插入新節點后，可能有些節點的孩子數大于了B（或L），此時該節點要分裂。對于Leaf，它現在有L+1個MinCluster，我們要新創建一個Leaf，使它作為原Leaf的兄弟結點，同時注意每新創建一個Leaf都要把它插入到雙向鏈表中。L+1個MinCluster要分到這兩個Leaf中，怎么分呢？找出這L+1個MinCluster中距離最遠的兩個Cluster（根據D2），剩下的Cluster看離哪個近就跟誰站在一起。分好后更新兩個Leaf的CF值，其祖先節點的CF值沒有變化，不需要更新。這可能導致祖先節點的遞歸分裂，因為Leaf分裂后恰好其父節點的孩子數超過了B。Nonleaf的分裂方法與Leaf的相似，只不過產生新的Nonleaf后不需要把它放入一個雙向鏈表中。如果是樹的根節點要分裂，則樹的高度加1。層次聚類——BIRCH節點分裂1.一個新的樣本點讀入，發現它離LN1節點最近，判斷是否在sc1,sc2,sc3這3個CF對應的超球體之內，否，因此建立一個新的CF

sc8來容納它。但是此時LN1的CF個數已經達到最大值了，不能再創建新的CF了，就要將LN1葉子節點一分為二了。2.將LN1里所有CF元組中，最遠的兩個CF做新葉子節點的種子CF，然后將LN1節點里所有CFsc1,sc2,sc3，以及新樣本點的新元組sc8劃分到兩個新的葉子節點上。3.如果內部節點的最大CF數B=3，則此時葉子節點一分為二會導致根節點的最大CF數超了，此時根節點也要分裂，分裂的方法和葉子節點分裂一樣。層次聚類——BIRCHBrich算法的階段?

階段一：掃描數據庫，構造一顆CF樹，并定義相關閾值，把稠密數據分成簇。?

階段二：對CF樹進行壓縮，通過改變T值，將部分簇進行壓縮合并，建立一個更小的CF樹。?

階段三：采用其他的聚類算法對其葉節點進行聚類，將稀疏的簇當作離群值進行刪除，補救由于輸入順序和頁面大小帶來的分裂。?

階段四：通過上階段得出聚類質心，將其作為種子節點，將其他對象分配給質心，構成新的聚類。層次聚類——BIRCHBrich算法流程層次聚類——BIRCH重建過程從舊樹的葉子節點建造一個新樹。這樣，重建樹的過程不需要重讀所有的對象----建樹只需讀一次數據在階段三和四采用任何聚類算法，例如典型的劃分方法BIRCH的性能支持增量聚類：因為它對每一個數據點的聚類的決策都是基于當前已經處理過的數據點，而不是基于全局的數據點。

線性可伸縮性:計算復雜性O(n),單遍掃描,附加的掃描可以改善聚類質量較好的聚類質量缺點只能處理數值數據對數據的輸入次序敏感CF樹結點不總是對應于[用戶考慮的]自然簇(參數B和T)簇非球形時效果不好(使用半徑/直徑控制簇邊界)層次聚類——CURE“單鏈”簇的鄰近度為不同簇的兩個最近的點之間的鄰近度。會將由低密度帶連接的兩個簇錯誤的合并為一個簇。“組平均”簇鄰近度為取自不同簇的所有點對鄰近度的平均值（平均長度）。得到的簇偏向于球形，因此會將圖中瘦長的簇拆散。層次聚類——CURECURE(ClusteringUsingREpresentatives):由Guha,Rastogi和Shim提出(1998)絕大多數聚類算法或者擅長處理球形和相似大小的聚類，或者在存在孤立點時變得比較脆弱CURE解決了偏好球形的問題，在處理孤立點上也更加健壯CURE采用了一種新的層次聚類算法選擇基于質心和基于代表對象方法之間的中間策略.它不用單個質心或對象來代表一個簇,而是選擇了數據空間中固定數目的具有代表性的點（采用的方法介于“單鏈”和“組平均”之間，克服了這兩種層次聚類算法的不足之處。）首先選擇簇中分散的對象,然后根據一個特定的收縮因子向簇中心“收縮”，距離質心越遠的點（例如離群點）的收縮程度越大。層次聚類——CURE每個簇有多于一個的代表點使得CURE可以適應非球形的任意形狀的聚類簇的收縮或凝聚可以有助于控制孤立點的影響CURE的優點CURE對孤立點的處理更加健壯能夠識別非球形和大小變化較大的簇對于大規模數據庫,它也具有良好的伸縮性,而且沒有犧牲聚類質量

針對大型數據庫,CURE采用了隨機取樣和劃分兩種方法的組合首先劃分一個隨機樣本,每個劃分被部分聚類然后對這些結果簇聚類,產生希望的結果

層次聚類——CURECURE算法核心:從源數據對象中抽取一個隨機樣本集S.將樣本S分割為p個劃分,每個的大小為

s/p將每個劃分局部地聚類成s/pq

個簇刪除孤立點通過隨機選樣如果一個簇增長太慢,就刪除它.對局部聚類進行聚類.用相應的簇標簽來標記數據層次聚類——CURExyyyyxyxs=50p=2s/p=25s/pq=5層次聚類——CURExyxy多個代表點向重心以因子

移動,進行收縮或凝聚多個代表點描述了每個簇的形狀層次聚類——ROCKROCK(RObustClusteringusinglinKs)由S.Guha,R.Rastogi,K.Shim提出(ICDE’99).使用鏈接(link)度量相似性/接近性鏈接：兩個對象間共同的近鄰的數目不是基于距離的計算復雜性:基本思想:相似性函數:Jaccard系數

設T1={1,2,3},T2={3,4,5}層次聚類——ROCK兩個點pi和pj是近鄰，如果sim(pi,pj)>=用戶指定閾值link(pi,pj)是兩個點pi和pj共同的近鄰的數目兩個簇Ci和Cj的互連性被定義為兩個簇間交叉鏈（crosslink）的數目ROCK首先根據相似度閥值和共享近鄰的概念，從給定的數據相似度矩陣構建一個稀疏的圖，然后在這個稀疏圖上運行一個層次聚類算法層次聚類——CHAMELEONCHAMELEON:一個利用動態模型的層次聚類算法(Hierarchicalclusteringusingdynamicmodeling)由G.Karypis,E.H.Han,andV.Kumar’99提出對CURE和ROCK缺點的觀察:Cure忽略了關于兩個不同簇中對象的聚集互連性的信息Rock強調對象間互連性,卻忽略了關于對象間近似度的信息CHAMELEON基于動態模型度量相似性如果兩個簇間的互連性和近似度與簇內部對象間的互連性和近似度高度相關,則合并這兩個簇層次聚類——CHAMELEON兩階段算法使用圖劃分算法:將數據對象聚類為大量相對較小的子類逐步用圖劃分算法把k近鄰圖分成相對較小的子簇，最小化割邊。使用凝聚的層次聚類算法：通過反復地合并子類來找到真正的結果簇既考慮互連性,又考慮簇間的近似度,特別是簇內部的特征,來確定最相似的子類.這樣,它不依賴于靜態的用戶提供的模型,能夠自動地適應被合并的簇的內部特征割邊最小化——簇c劃分為兩個子簇Ci和Cj時需要割斷的邊的加權和最小。割邊用EC{Ci，Cj}表示，評估Ci和Cj的簇間的絕對互聯性。層次聚類——CHAMELEON構造稀疏圖劃分圖合并劃分最終的簇DataSetK-最近鄰居圖層次聚類——CHAMELEONk-最近鄰圖Gk:圖中的每個點代表一個數據對象,如果一個對象是另一個對象的k個最類似的對象之一,在這兩個點之間存在一條邊

k-最近鄰圖Gk動態地捕捉鄰域的概念：一個對象的鄰域半徑由對象所在區域的密度所決定在一個密集區域,鄰域的定義范圍相對狹窄;在一個稀疏區域,它的定義范圍相對較寬

區域的密度作為邊的權重被記錄下來一個密集區域的邊趨向于比稀疏區域的邊有更大的權重

層次聚類——CHAMELEONChameleon通過兩個簇的相對互連性RI(Ci,Cj)和相對接近度RC(Ci,Cj)來決定簇間的相似度

RI(Ci,Cj)定義為Ci和Cj之間的絕對互聯性關于兩個簇的內部互連性的規范化

其中,EC{Ci，Cj}是包含Ci和Cj的簇分裂為Ci和Cj的割邊,ECCi（或ECCj）是它的最小截斷等分線的大小（即將圖劃分為兩個大致相等的部分需要切斷的邊的加權和）

層次聚類——CHAMELEONRC(Ci,Cj)定義為Ci和Cj之間的絕對接近度關于兩個簇的內部接近度的規范化

其中,是連接Ci和Cj頂點的邊的平均權重

是Ci的最小二等分的邊的平均權重

Contents聚類分析介紹01層次聚類02密度聚類03譜聚類04密度聚類基于密度的方法基于密度聚類(Density-BasedClustering)主要特點:發現任意形狀的聚類處理噪音一遍掃描需要密度參數作為終止條件一些有趣的研究:DBSCAN:Ester,etal.(KDD’96)OPTICS:Ankerst,etal(SIGMOD’99).DENCLUE:Hinneburg&D.Keim(KDD’98)CLIQUE:Agrawal,etal.(SIGMOD’98)密度聚類基于密度的聚類：背景Ⅰ兩個參數:Eps:鄰域的最大半徑MinPts:在Eps-鄰域中的最少點數NEps(p): {qbelongstop|dist(p,q)<=Eps}直接密度可達的:點p

關于Eps,MinPts

是從點q直接密度可達的,如果

1)p

屬于NEps(q)2)核心點條件:|NEps(q)|>=MinPts

pqMinPts=5Eps=1cm密度聚類密度概念核心對象(Coreobject):一個對象的

–鄰域至少包含最小數目MinPts個對象,不是核心點,但落在某個核心點的Eps鄰域內的對象稱為邊界點,不屬于任何簇的對象為噪聲.對于空間中的一個對象，如果它在給定半徑e的鄰域中的對象個數大于密度閾值MinPts，則該對象被稱為核心對象，否則稱為邊界對象。CoreBorderOutlierEps=1cmMinPts=5密度聚類密度概念直接密度可達的(Directlydensityreachable,DDR):給定對象集合D,如果p是在q的

–鄰域內,而q是核心對象,我們說對象p是從對象q直接密度可達的(如果q是一個核心對象，p屬于q的鄰域，那么稱q直接密度可達p。)密度可達的(densityreachable):存在一個從q到p的DDR對象鏈(如果存在一條鏈<p1,p2,…..,pi>，滿足p1=p，pi=q，pi+1直接密度可達pi，則稱q密度可達p)pqMinPts=5Eps=1cm由一個核心對象和其密度可達的所有對象構成一個聚類。密度聚類基于密度的聚類：背景Ⅱ密度可達:點p

關于Eps,MinPts

是從

q密度可達的,如果存在一個節點鏈p1,…,pn,p1=q,pn=p

使得pi+1

是從pi直接密度可達的密度相連的:點p關于Eps,MinPts

與點

q是密度相連的,如果存在點o使得,p

和

q

都是關于Eps,MinPts

是從

o密度可達的(如果存在o，o密度可達q和p，則稱p和q是密度連通的)pqopqp1密度聚類密度概念Eg:

假設半徑

Ε=3

，

MinPts=3

，點

p

的

領域中有點

{m,p,p1,p2,o},

點

m

的

領域中有點

{m,q,p,m1,m2},

點

q的

領域中有

{q,m},

點

o

的

領域中有點

{o,p,s},

點

s

的

領域中有點

{o,s,s1}.那么核心對象有

p,m,o,s(q

不是核心對象，因為它對應的

領域中點數量等于

2

，小于

MinPts=3)

；點

m

從點

p

直接密度可達，因為

m

在

p

的

領域內，并且

p

為核心對象；點

q

從點

p

密度可達，因為點

q

從點

m

直接密度可達，并且點

m

從點

p

直接密度可達；點

q

到點

s

密度相連，因為點

q

從點

p

密度可達，并且

s

從點

p

密度可達。密度聚類例子：MinPts=3q是從p密度可達；p不是從q密度可達（q非核心）S和r從o密度可達；o從r密度可達；r,s密度相連密度聚類例子：a為核心對象，b為邊界對象，且a直接密度可達b，但b不直接密度可達a,因為b不是一個核心對象密度聚類例子：c直接密度可達a,a直接密度可達b,所以c密度可達b，同理b不密度可達c，但b和c密度相連密度聚類——DBSCANDBSCAN(DensityBasedSpatialClusteringofApplicationswithNoise)一個基于密度的聚類算法可以在帶有“噪音”的空間數據庫中發現任意形狀的聚類CoreBorderOutlierEps=1cmMinPts=5密度聚類——DBSCAN

DBSCAN：一種基于高密度連通區域的基于密度的聚類方法，該算法將具有足夠高密度的區域劃分為簇，并在具有噪聲的空間數據庫中發現任意形狀的簇。它將簇定義為密度相連的點的最大集合；算法任意選取一個點p得到所有從p

關于Eps

和MinPts密度可達的點.如果p

是一個核心點,則找到一個聚類.如果p

是一個邊界點,沒有從p

密度可達的點,DBSCAN將訪問數據庫中的下一個點.繼續這一過程,直到數據庫中的所有點都被處理.DBSCAN的復雜度采用空間索引,復雜度為O(nlogn),否則為O(n2)DBSCAN的缺點:對用戶定義的參數是敏感的,參數難以確定(特別是對于高維數據),設置的細微不同可能導致差別很大的聚類.（數據傾斜分布）全局密度參數不能刻畫內在的聚類結構密度聚類——DBSCANDBSCAN從任一對象p開始，根據參數e和MinPts提取所有從p密度可達對象，得到一個聚類。1.

從任一對象p開始。a)

如果p是核心對象，則p和p直接密度可達的所有對象被標記為類i。遞歸p直接密度可達的所有對象qi（即用qi代替p回到第一步）。b)

如果p是一個邊界對象，那么p被標記為噪聲。2.

i++3.

如果還有沒被標記的對象，則從中任選一個作為p，回到第一步。密度聚類——DBSCAN算法：

DBSCAN輸入：

—

半徑

MinPts

—

給定點在

鄰域內成為核心對象的最小領域點數

D

—

集合輸出：目標類簇集合方法：

repeat1)

判斷輸入點是否為核心對象2)

找出核心對象的

鄰域中的所有直接密度可達點

util

所有輸入點都判斷完畢

repeat

針對所有核心對象的

鄰域所有直接密度可達點找到最大密度相連對象集合，

中間涉及到一些密度可達對象的合并。

Util

所有核心對象的

鄰域都遍歷完畢密度聚類——DBSCAN密度聚類——DBSCAN密度聚類——DBSCAN密度聚類——DBSCAN密度聚類——DBSCAN密度聚類——OPTICS在前面介紹的DBSCAN算法中，有兩個初始參數

（鄰域半徑）和minPts(

鄰域最小點數)需要用戶手動設置輸入，并且聚類的類簇結果對這兩個參數的取值非常敏感，不同的取值將產生不同的聚類結果，其實這也是大多數其他需要初始化參數聚類算法的弊端。OPTICS(OrderingPointsToIdentifytheClusteringStructure)Ankerst,Breunig,Kriegel,和Sander提出(SIGMOD’99)為自動和交互的聚類分析計算一個簇次序(clusterordering).OPTICS并不顯式的產生結果類簇，而是為聚類分析生成一個增廣的簇排序（比如，以可達距離為縱軸，樣本點輸出次序為橫軸的坐標圖），這個排序代表了各樣本點基于密度的聚類結構。它包含的信息等價于從一個廣泛的參數設置所獲得的基于密度的聚類，換句話說，從這個排序中可以得到基于任何參數E和minPts的DBSCAN算法的聚類結果。密度聚類——OPTICS這個次序代表了數據的基于密度的聚類結構。它包含了信息,等同于從一個廣域的參數設置所獲得的基于密度的聚類可用于自動和交互聚類分析,包括發現內在聚類結構可以使用圖形或可視化技術表示考慮DBSCAN,對一個恒定的MinPts值,關于高密度的(即較小的

值)的聚類結果被完全包含在根據較低密度所獲得的密度相連的集合中

擴展DBSCAN算法來同時處理一組距離參數值密度聚類——OPTICS為了同時構建不同的聚類,應當以特定的順序來處理對象.優先選擇最小的

值密度可達的對象,以便高密度的聚類能被首先完成

每個對象需要存儲兩個值對象p的核心距離(core-distance)是使得p成為核心對象的最小

。如果p不是核心對象,p的核心距離沒有定義

對象q關于另一個對象p的可達距離(reachability-distance)是p的核心距離和p與q的歐幾里得距離之間的較大值.如果p不是一個核心對象,p和q之間的可達距離沒有定義

密度聚類——OPTICS例:設

=6(mm),MinPts=5.p的核心距離是p與四個最近的數據對象之間的距離

’.q1關于p的可達距離是p的核心距離(即

’=3mm),因為它比從p到q1的歐幾里得距離要大.q2關于p的可達距離是從p到q2的歐幾里得距離,它大于p的核心距離

=6mm

’=3mm=6mm

’=3mmppq1q2P的核心距離可達距離(p,q1)=’=3mm可達距離(p,q2)=d(p,q2)密度聚類——OPTICS例如：假設鄰域半徑E=2,minPts=3，存在點A(2,3),B(2,4),C(1,4),D(1,3),E(2,2),F(3,2)點A為核心對象，在A的E領域中有點{A,B,C,D,E,F}，其中A的核心距離為E’=1，因為在點A的E’鄰域中有點{A,B,D,E}>3;點F到核心對象點A的可達距離為

，因為A到F的歐幾里得距離

大于點A的核心距離1.OPTICS算法額外存儲了每個對象的核心距離和可達距離。基于OPTICS產生的排序信息來提取類簇。密度聚類——OPTICS算法：OPTICS輸入：樣本集D,鄰域半徑E,給定點在E領域內成為核心對象的最小領域點數MinPts輸出：具有可達距離信息的樣本點輸出排序方法：1、創建兩個隊列，有序隊列和結果隊列。（有序隊列用來存儲核心對象及其該核心對象的直接可達對象，并按可達距離升序排列；結果隊列用來存儲樣本點的輸出次序。你可以把有序隊列里面放的理解為待處理的數據，而結果隊列里放的是已經處理完的數據）；2、如果所有樣本集D中所有點都處理完畢，則算法結束。否則，選擇一個未處理（即不在結果隊列中）且為核心對象的樣本點，找到其所有直接密度可達樣本點，如果該樣本點不存在于結果隊列中，則將其放入有序隊列中，并按可達距離排序；3、如果有序隊列為空，則跳至步驟2（重新選取處理數據）。否則，從有序隊列中取出第一個樣本點（即可達距離最小的樣本點）進行拓展，并將取出的樣本點保存至結果隊列中(如果它不存在結果隊列當中的話)。然后進行下面的處理。3.1.判斷該拓展點是否是核心對象，如果不是，回到步驟3（因為它不是核心對象，所以無法進行擴展了。那么就回到步驟3里面，取最小的。這里要注意，第二次取不是取第二小的，因為第一小的已經放到了結果隊列中了，所以第二小的就變成第一小的了。）。如果該點是核心對象，則找到該拓展點所有的直接密度可達點；3.2.判斷該直接密度可達樣本點是否已經存在結果隊列，是則不處理，否則下一步；3.3.如果有序隊列中已經存在該直接密度可達點，如果此時新的可達距離小于舊的可達距離，則用新可達距離取代舊可達距離，有序隊列重新排序(因為一個對象可能直接由多個核心對象可達，因此，可達距離近的肯定是更好的選擇)；3.4.如果有序隊列中不存在該直接密度可達樣本點，則插入該點，并對有序隊列重新排序；4、迭代2，3。5、算法結束，輸出結果隊列中的有序樣本點。密度聚類——OPTICS大家或許會很疑惑，這里不也有輸入參數E和MinPts嗎？其實這里的E和MinPts只是起到算法輔助作用，也就是說E和MinPts的細微變化并不會影響到樣本點的相對輸出順序，這對我們分析聚類結果是沒有任何影響。我們采用與先前DBSCAN相同的樣本點集合，對于樣本點a={2,3};b={2,4};c={1,4};d={1,3};e={2,2};f={3,2};g={8,7};h={8,6};i={7,7};j={7,6};k={9,5};l={100,2};//孤立點m={8,20};n={8,19};o={7,18};p={7,17};q={8,21};并且使用相同的E=2

MinPts=4時，輸出具有可達距離信息的樣本點輸出排序密度聚類——OPTICS1->a:1.02->e:1.03->b:1.04->d:1.05->c:1.41421356237309516->f:1.4142135623730951------7->g:1.41421356237309518->j:1.41421356237309519->k:1.414213562373095110->i:1.414213562373095111->h:1.4142135623730951------12->n:2.013->q:2.014->o:2.015->m:2.0密度聚類——OPTICS如圖，按照算法，分三個階段輸出了三波值,{a,e,b,d,},{c,f,g,j,k,I,h},{n,q,o,m}

這和DBSCAN的類簇結果是一樣的。不僅如此，我們通過分析有序圖還能直接得到當參數E=1.5,minPts=4時DBSCAN的類簇結果，只要在坐標圖中找到Y值小于1.5的樣本點即可，只有兩類{a,e,b,d,c,f},{g,j,k,I,h},其他點被認為是孤立點，和DBSCAN聚類算法取E=1.5,minPts=4時的結果一致。所以說，這個OPTICS聚類算法所得的簇排序信息等價于一個廣泛的參數設置所獲得的基于密度的聚類結果。密度聚類——OPTICS這些值怎樣使用？OPTICS算法創建了數據庫中對象的一個次序,額外存儲了每個對象的核心距離和一個適當的可達距離已經提出了一種算法,基于OPTICS產生的次序信息來抽取聚類.對于小于在生成該次序中采用的距離

的任何距離

’,為提取所有基于密度的聚類,這些信息是足夠的

一個數據集合的聚類次序可以被圖形化地描述，以助于理解

由于OPTICS算法與DBSCAN在結構上的等價性,它具有和DBSCAN相同的時間復雜度,即當使用空間索引時,復雜度為O(nlogn)

密度聚類——OPTICS可達距離‘密度聚類——OPTICS密度聚類——OPTICS密度聚類——OPTICS密度聚類——DENCLUEDENCLUE(DENsity-basedCLUstEring)由Hinneburg和Keim(KDD’98)提出,是基于密度分布函數的聚類方法主要特點堅實的數學基礎,概括了其他的聚類方法,包括基于劃分的,層次的,及基于位置的方法適用于具有大量噪音的數據集可用于高維數據集任意形狀的聚類,它給出了簡潔的數學描述明顯快于現有算法(比DBSCAN快45倍)但是,需要大量參數,要求對密度參數σ和噪音閥值ξ進行仔細的選擇密度聚類——DENCLUE使用柵格單元,但只保存實際存放數據點的柵格單元信息,并且在一個基于樹的存取結構中管理這些單元.影響函數(Influencefunction):描述數據點在其鄰域的影響.數據空間的整體密度可以被模擬為所有數據點的影響函數的總和聚類可以通過確定密度吸引點(densityattractor)來得到.密度吸引點是全局密度函數的局部最大值.密度聚類——DENCLUE設x和y是d維特征空間Fd中的對象.數據對象y對x的影響函數是一個函數fyB：Fd→R+0,它是根據一個基本的影響函數fB來定義的

fyB(x)=fB(x,y)原則上,影響函數可以是一個任意的函數,它由某個鄰域內的兩個對象之間的距離來決定

例如歐幾里得距離函數,用來計算一個方波影響函數(squarewaveinfluencefunction)：

密度聚類——DENCLUE高斯影響函數一個對象x∈Fd的密度函數被定義為所有數據點的影響函數的和.給定n個對象,D={x1,…,xn}

Fd,在x上的密度函數定義如下

密度聚類——DENCLUE例如,根據高斯影響函數得出的密度函數是

根據密度函數,我們能夠定義該函數的梯度和密度吸引點(全局密度函數的局部最大)一個點x是被一個密度吸引點

x*密度吸引的,如果存在一組點x0,x1,…,xk,x0=x,xk=x*,對0<i<k，xi-1的梯度是在xi的方向上對一個連續的,可微的影響函數,用梯度指導的爬山算法能用來計算一組數據點的密度吸引點密度聚類——DENCLUE密度吸引點密度聚類——DENCLUE密度吸引點密度聚類——DENCLUE中心定義的簇和任意形狀的簇密度吸引點x*的中心定義的簇(center-definedcluster)是一個被x*密度吸引的子集C,在x*的密度函數不小于一個閾值ξ;否則(即如果它的密度函數值小于ξ),它被認為是孤立點

一個任意形狀的簇(arbitrary-shapecluster)是子集C的集合,每一個是各自密度吸引子密度吸引的,有不小于閥值ξ的密度函數值,從每個區域到另一個都存在一條路徑P,該路徑上每個點的密度函數值都不小于ξ

密度聚類——DENCLUE中心定義的簇和任意形狀的簇密度聚類References[DBSCAN]EsterM.,KriegelH.-P.,SanderJ.,XuX.:“ADensityBasedAlgorithmforDiscoveringClustersinLargeSpatialDatabaseswithNoise”,Proc.2ndInt.Conf.onKnowledgeDiscoveryandDataMining,Portland,OR,AAAIPress,1996,pp.226-231.[OPTICS]Ankerst,M.,Breunig,M.,Kreigel,H.-P.,andSander,J.1999.OPTICS:Orderingpointstoidentifyclusteringstructure.InProceedingsoftheACMSIGMODConference,49-60,Philadelphia,PA.Contents聚類分析介紹01層次聚類02密度聚類03譜聚類04譜聚類譜聚類是一個流行的源于譜圖劃分理論的高性能計算方法。通過使用對無向圖多路劃分方法來解決數據聚類問題。每個無向圖

的頂點V看作是一個數據點，基于某種相似性度量準則獲得的兩點間的相似性作為邊權重的集合

，無向圖的鄰接矩陣W包含了聚類所需的所有信息，且表示待聚類數據點間的相似性。通過優化劃分準則來達到類內相似性最大類間相似性最小的目的。

譜聚類對于最小化

向量p的尋找等價于尋找最優的最小切。把整數規劃問題轉化成一個二次規劃

可通過將p放松到連續值來實現，其中D表示對角矩陣，D-P表示拉普拉斯矩陣L，

表示對角元素。從而L的第二個最小特征值λ2對應的特征向量成為此問題的最優解Fiedler向量p。通過選擇合適的值對p進行兩類劃分來得到圖的最終劃分。最小切準則譜聚類簡單的最小切準則由于沒有考慮每個聚類內部的密度而僅僅只是關注聚類的外部關聯，從而沒有對類規模進行限制最終容易產生歪斜劃分的情況。為了避免上述歪斜劃分的情況，通過引入不同的平衡條件來解決這一問題，從而獲得性能更優的聚類準則，這在后來提出的各種準則中得到了體現：率切(ratiocut)準則中最小化類間相似性的目的通過采取類規模平衡項這一策略來實現；規范切(normalizedcut)準則通過引入容量的概念來規范化類間相關，從而兼顧了類內關聯強度和類間關聯強度的平衡；最小最大切(minmaxcut)準則采取同時最小化類間關聯強度和最大化類內關聯強度的方法。譜聚類譜聚類方法最早被提出來是解決兩類劃分問題的，當涉及到多類劃分時則需要遞歸調用兩類劃分方法來實現。然而，由于沒有對其它包含有效劃分信息的特征向量進行充分利用，兩類劃分方法不穩定且計算效率低。由于信息損失而造成的不穩定性可以采用同時使用多個特征向量來避免的論斷在相關文獻中已經得到證明。譜聚類所以，率切(Ratio-cut)準則、規范切(Normalized-cut)準則和最小最大切(Min-Max-cut)準則被分別被推廣到多路的情況下來求解多類劃分問題：多路率切：多路規范切：多路最小最大切：譜聚類最小化多路切劃分準則是一個NP難問題，其近似解只能在放松后的實數域內求得。相關文獻中已經證明，由前k個特征向量組成的子空間構成了劃分準則的譜放松逼近解。然而，為了從特征向量中獲得離散解，通常需要在這個k維子空間中，將特征向量看作是一個點集的幾何坐標，然后利用如k-means、窮舉搜索法或動態規劃等各種啟發式聚類方法在這個新的坐標點集上找到原始數據樣本集最終的劃分結果。通過對經典譜算法原理的深入了解，發現它們都包含預處理、譜映射和后處理三個部分。而它們彼此之間的差異之處在于：如何構造相似性矩陣、選擇什么樣的譜放松方法、使用哪些矩陣特征向量和怎樣利用特征向量求得聚類的最終劃分。譜聚類基于歐氏距離的相似性度量方法和譜聚類算法的一般步驟：輸入：樣本集

；聚類簇數k

過程：1：計算數據樣本集D的相似度矩陣W:

2：計算拉普拉斯矩陣L：

(S為度矩陣)3：求解拉普拉斯矩陣L的特征值和特征向量4：選擇前k個特征向量形成矩陣U

5：對U的行進行歸一化得到U’6：對歸一化的U’進行K-means聚類輸出：簇劃分譜聚類譜聚類算法聚類結果ThankYou!高級數據挖掘Contents圖數據挖掘01時間序列數據挖掘02大數據與分布式數據挖掘03圖數據圖是由頂點和邊構成的抽象數據結構，圖數據通過圖結構表示實體及其相互之間的復雜關聯關系，廣泛存在于各類應用中：化學信息學：原子可視為圖中的節點，節點可附帶原子的種類、電荷等關鍵信息；邊則代表了原子之間的化學鍵，用于表示原子之間的連接方式和相互作用，是理解分子