數(shù)據(jù)挖掘 課件 第六章 聚類分析

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

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

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

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

使用距離矩陣作為聚類標準.該方法不需要輸入聚類數(shù)目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中對象的數(shù)目

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

means)和k-中心點(k-

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

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

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

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

K個對象作為初始聚類中心將每個對象賦給最類似的中心更新簇的平均值重新賦值更新簇的平均值重新賦值層次聚類——K-means聚類Matlab程序?qū)崿F(xiàn)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程序?qū)崿F(xiàn)（續(xù)）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聚類在圖像分割上的簡單應(yīng)用例1：圖片：一只遙望大海的小狗；此圖為100x100像素的JPG圖片，每個像素可以表示為三維向量（分別對應(yīng)JPEG圖像中的紅色、綠色和藍色通道）

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

是對象數(shù)目,k

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

PAM

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

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

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

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

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

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

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

PAM對于小數(shù)據(jù)集工作得很好,但不能很好地用于大數(shù)據(jù)集

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

其中

n

是數(shù)據(jù)對象數(shù)目,

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

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

CLARA→利用取樣資料集

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

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

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

2、設(shè)置當(dāng)前節(jié)點current為Gn中的任意一個節(jié)點。

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

4、考慮當(dāng)前點的一個隨機的鄰居S，并計算兩個節(jié)點的代價差。5、如果S的代價較低，則current:=S，轉(zhuǎn)到步驟3。

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

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

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

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

對象總數(shù)合并或分裂的決定需要檢查和估算大量的對象或簇不能撤消已做的處理,聚類之間不能交換對象.如果某一步?jīng)]有很好地選擇合并或分裂的決定,可能會導(dǎo)致低質(zhì)量的聚類結(jié)果

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

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

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

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

Ni=1XiSS:N個節(jié)點特征平方和

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構(gòu)成，則：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。所謂兩簇合并只需要兩個對應(yīng)的CF相加那可層次聚類——BIRCHBIRCH的CF樹聚類特征從統(tǒng)計學(xué)的觀點來看，聚類特征是對給定子類統(tǒng)計匯總:子聚類的0階,1階和2階矩(moments)記錄了計算聚類和有效利用存儲的關(guān)鍵度量,并有效地利用了存儲,因為它匯總了關(guān)于子類的信息，而不是存儲所有的對象CF樹是高度平衡的樹，它存儲了層次聚類的聚類特征

樹中的非葉節(jié)點有后代或“孩子”

非葉節(jié)點存儲了其孩子的CF的總和，即匯總了關(guān)于其孩子的聚類信息

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

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

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

是，更新CF值

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

是，添加一個新的元組

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

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

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

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

階段一：掃描數(shù)據(jù)庫，構(gòu)造一顆CF樹，并定義相關(guān)閾值，把稠密數(shù)據(jù)分成簇。?

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

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

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

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

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

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

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

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

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

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

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

區(qū)域的密度作為邊的權(quán)重被記錄下來一個密集區(qū)域的邊趨向于比稀疏區(qū)域的邊有更大的權(quán)重

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

RI(Ci,Cj)定義為Ci和Cj之間的絕對互聯(lián)性關(guān)于兩個簇的內(nèi)部互連性的規(guī)范化

其中,EC{Ci，Cj}是包含Ci和Cj的簇分裂為Ci和Cj的割邊,ECCi（或ECCj）是它的最小截斷等分線的大?。磳D劃分為兩個大致相等的部分需要切斷的邊的加權(quán)和）

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

其中,是連接Ci和Cj頂點的邊的平均權(quán)重

是Ci的最小二等分的邊的平均權(quán)重

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

關(guān)于Eps,MinPts

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

1)p

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

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

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

–鄰域內(nèi),而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由一個核心對象和其密度可達的所有對象構(gòu)成一個聚類。密度聚類基于密度的聚類：背景Ⅱ密度可達:點p

關(guān)于Eps,MinPts

是從

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

使得pi+1

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

與點

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

和

q

都是關(guān)于Eps,MinPts

是從

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

假設(shè)半徑

Ε=3

，

MinPts=3

，點

p

的

領(lǐng)域中有點

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

點

m

的

領(lǐng)域中有點

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

點

q的

領(lǐng)域中有

{q,m},

點

o

的

領(lǐng)域中有點

{o,p,s},

點

s

的

領(lǐng)域中有點

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

p,m,o,s(q

不是核心對象，因為它對應(yīng)的

領(lǐng)域中點數(shù)量等于

2

，小于

MinPts=3)

；點

m

從點

p

直接密度可達，因為

m

在

p

的

領(lǐng)域內(nèi)，并且

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)一個基于密度的聚類算法可以在帶有“噪音”的空間數(shù)據(jù)庫中發(fā)現(xiàn)任意形狀的聚類CoreBorderOutlierEps=1cmMinPts=5密度聚類——DBSCAN

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

關(guān)于Eps

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

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

是一個邊界點,沒有從p

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

從任一對象p開始。a)

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

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

i++3.

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

DBSCAN輸入：

—

半徑

MinPts

—

給定點在

鄰域內(nèi)成為核心對象的最小領(lǐng)域點數(shù)

D

—

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

repeat1)

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

找出核心對象的

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

util

所有輸入點都判斷完畢

repeat

針對所有核心對象的

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

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

Util

所有核心對象的

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

（鄰域半徑）和minPts(

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

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

擴展DBSCAN算法來同時處理一組距離參數(shù)值密度聚類——OPTICS為了同時構(gòu)建不同的聚類,應(yīng)當(dāng)以特定的順序來處理對象.優(yōu)先選擇最小的

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

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

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

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

密度聚類——OPTICS例:設(shè)

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

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

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

=6mm

’=3mm=6mm

’=3mmppq1q2P的核心距離可達距離(p,q1)=’=3mm可達距離(p,q2)=d(p,q2)密度聚類——OPTICS例如：假設(shè)鄰域半徑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領(lǐng)域中有點{A,B,C,D,E,F}，其中A的核心距離為E’=1，因為在點A的E’鄰域中有點{A,B,D,E}>3;點F到核心對象點A的可達距離為

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

大于點A的核心距離1.OPTICS算法額外存儲了每個對象的核心距離和可達距離?；贠PTICS產(chǎn)生的排序信息來提取類簇。密度聚類——OPTICS算法：OPTICS輸入：樣本集D,鄰域半徑E,給定點在E領(lǐng)域內(nèi)成為核心對象的最小領(lǐng)域點數(shù)MinPts輸出：具有可達距離信息的樣本點輸出排序方法：1、創(chuàng)建兩個隊列，有序隊列和結(jié)果隊列。（有序隊列用來存儲核心對象及其該核心對象的直接可達對象，并按可達距離升序排列；結(jié)果隊列用來存儲樣本點的輸出次序。你可以把有序隊列里面放的理解為待處理的數(shù)據(jù)，而結(jié)果隊列里放的是已經(jīng)處理完的數(shù)據(jù)）；2、如果所有樣本集D中所有點都處理完畢，則算法結(jié)束。否則，選擇一個未處理（即不在結(jié)果隊列中）且為核心對象的樣本點，找到其所有直接密度可達樣本點，如果該樣本點不存在于結(jié)果隊列中，則將其放入有序隊列中，并按可達距離排序；3、如果有序隊列為空，則跳至步驟2（重新選取處理數(shù)據(jù)）。否則，從有序隊列中取出第一個樣本點（即可達距離最小的樣本點）進行拓展，并將取出的樣本點保存至結(jié)果隊列中(如果它不存在結(jié)果隊列當(dāng)中的話)。然后進行下面的處理。3.1.判斷該拓展點是否是核心對象，如果不是，回到步驟3（因為它不是核心對象，所以無法進行擴展了。那么就回到步驟3里面，取最小的。這里要注意，第二次取不是取第二小的，因為第一小的已經(jīng)放到了結(jié)果隊列中了，所以第二小的就變成第一小的了。）。如果該點是核心對象，則找到該拓展點所有的直接密度可達點；3.2.判斷該直接密度可達樣本點是否已經(jīng)存在結(jié)果隊列，是則不處理，否則下一步；3.3.如果有序隊列中已經(jīng)存在該直接密度可達點，如果此時新的可達距離小于舊的可達距離，則用新可達距離取代舊可達距離，有序隊列重新排序(因為一個對象可能直接由多個核心對象可達，因此，可達距離近的肯定是更好的選擇)；3.4.如果有序隊列中不存在該直接密度可達樣本點，則插入該點，并對有序隊列重新排序；4、迭代2，3。5、算法結(jié)束，輸出結(jié)果隊列中的有序樣本點。密度聚類——OPTICS大家或許會很疑惑，這里不也有輸入?yún)?shù)E和MinPts嗎？其實這里的E和MinPts只是起到算法輔助作用，也就是說E和MinPts的細微變化并不會影響到樣本點的相對輸出順序，這對我們分析聚類結(jié)果是沒有任何影響。我們采用與先前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的類簇結(jié)果是一樣的。不僅如此，我們通過分析有序圖還能直接得到當(dāng)參數(shù)E=1.5,minPts=4時DBSCAN的類簇結(jié)果，只要在坐標圖中找到Y(jié)值小于1.5的樣本點即可，只有兩類{a,e,b,d,c,f},{g,j,k,I,h},其他點被認為是孤立點，和DBSCAN聚類算法取E=1.5,minPts=4時的結(jié)果一致。所以說，這個OPTICS聚類算法所得的簇排序信息等價于一個廣泛的參數(shù)設(shè)置所獲得的基于密度的聚類結(jié)果。密度聚類——OPTICS這些值怎樣使用？OPTICS算法創(chuàng)建了數(shù)據(jù)庫中對象的一個次序,額外存儲了每個對象的核心距離和一個適當(dāng)?shù)目蛇_距離已經(jīng)提出了一種算法,基于OPTICS產(chǎn)生的次序信息來抽取聚類.對于小于在生成該次序中采用的距離

的任何距離

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

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

由于OPTICS算法與DBSCAN在結(jié)構(gòu)上的等價性,它具有和DBSCAN相同的時間復(fù)雜度,即當(dāng)使用空間索引時,復(fù)雜度為O(nlogn)

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

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

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

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

Fd,在x上的密度函數(shù)定義如下

密度聚類——DENCLUE例如,根據(jù)高斯影響函數(shù)得出的密度