聚類分析基本概念和方法演示文稿

聚類分析基本概念和方法演示文稿當前第1頁\共有20頁\編于星期三\13點（優(yōu)選）聚類分析基本概念和方法當前第2頁\共有20頁\編于星期三\13點凝聚的層次聚類方法使用自底向上的策略。分裂的層次聚類方法使用自頂向下的策略。：凝聚的與分裂的層次聚類層次聚類方法可以是凝聚的或分裂的，取決于層次分解是自底向上（合并）還是以自頂向下（分裂）方式形成。在凝聚或分裂聚類中，用戶都可以指定期望的簇個數(shù)作為終止條件。當前第3頁\共有20頁\編于星期三\13點：凝聚的與分裂的層次聚類凝聚的層次聚類算法AGNES(AgglomerativeNESting)；分裂的層次聚類算法DIANA(DivisiveANAlysis)；單鏈接(single-linkoge)方法；樹狀圖的樹形結(jié)構(gòu)來表示層次聚類的過程。詳情見例10.3當前第4頁\共有20頁\編于星期三\13點：算法方法的距離度量

無論使用凝聚方法還是只用分類方法，一個核心問題是度量兩個簇之間的距離，其中每個簇一般是一個對象集。4個廣泛采用的簇間距離，也稱鏈接度量(linkagemeasure)：最小距離：最大距離：均值距離：平均距離：當前第5頁\共有20頁\編于星期三\13點最近鄰聚類算法(nearest-neighborclusteringalgorithm)單鏈接算法(single-linkagealgorithm)最小生成樹算法(minimalspanningtreealgorithm)最遠鄰聚類算法(farthest-neighborclusteringalgorithm)全連接算法(complete-linkagealgorithm)例10.4：算法方法的距離度量當前第6頁\共有20頁\編于星期三\13點

BIRCH：使用聚類特征樹的多階段聚類平衡迭代歸約和聚類(BalancedIterativeReducingandClusteringusingHierarchies,BIRCH):是為大量數(shù)值數(shù)據(jù)聚類設(shè)計的將層次聚類(在初始微聚類階段)與諸如迭代地劃分這樣的其他聚類算法(在其后的宏聚類階段)集成在一起克服了凝聚聚類方法所面臨的兩個困難可伸縮性不能撤銷先前步驟所做的工作

當前第7頁\共有20頁\編于星期三\13點

BIRCH：使用聚類特征樹的多階段聚類BIRCH使用聚類特征來概括一個簇使用聚類特征樹(CF-樹)來表示聚類的層次結(jié)構(gòu)這些結(jié)構(gòu)幫助聚類方法在大型數(shù)據(jù)庫甚至在流數(shù)據(jù)庫中取得好的速度和伸縮性這些結(jié)構(gòu)使得BIRCH方法對新對象增量或動態(tài)聚類也非常有效當前第8頁\共有20頁\編于星期三\13點

BIRCH：使用聚類特征樹的多階段聚類考慮一個n個d維的數(shù)據(jù)對象或點的簇。聚的聚類特征(ClusteringFeature,CF)是一個3維向量，匯總了對象簇的信息，定義如下：其中，LS是n個點的線性和(即)，而SS是數(shù)據(jù)點的平方和(即)。

聚類特征本質(zhì)上是給定簇的統(tǒng)計匯總。使用聚類特征，我們可以很容易地推導(dǎo)出簇的許多有用的統(tǒng)計量。例如，簇的型心X0、半徑R和直徑D。

例10.5當前第9頁\共有20頁\編于星期三\13點

BIRCH：使用聚類特征樹的多階段聚類

BIRCH采用了一種多階段聚類技術(shù)：數(shù)據(jù)集的單編掃描產(chǎn)生一個基本的好聚類，而一或多遍的額外掃描可以進一步地改進聚類質(zhì)量。它主要包括兩個階段:階段一：BIRCH掃描數(shù)據(jù)庫，建立一棵存放于內(nèi)存的初始CF-樹，它可以被看做數(shù)據(jù)的多層壓縮，試圖保留數(shù)據(jù)的內(nèi)在聚類結(jié)構(gòu)。階段二：BIRCH采用某個(選定的)聚類算法對CF樹的葉節(jié)點進行聚類，把稀疏的簇當做離群點刪除，而把稠密的簇合并為更大的簇。

當前第10頁\共有20頁\編于星期三\13點Chameleon(變色龍)是一種層次聚類算法，它采用動態(tài)建模來確定一對簇之間的相似度。在Chameleon中，簇的相似度依據(jù)如下兩點評估：簇中對象的連接情況簇的鄰近性圖10.10解釋Chameleon如何運作。：Chameleon：使用動態(tài)的建模的多階段層次聚類當前第11頁\共有20頁\編于星期三\13點Chameleon根據(jù)兩個簇Ci和Cj的相對互連度RI(Ci,Cj)和相對接近度RC(Ci,Cj)來決定它們的相似度：兩個簇Ci和Cj的相對互連度RI(Ci,Cj)定義為Ci和Cj之間的絕對互連度關(guān)于兩個簇Ci和Cj的內(nèi)部互連度的規(guī)范化，即兩個簇Ci和Cj的相對接近度RC(Ci,Cj)定義為Ci和Cj之間的絕對接近度關(guān)于兩個簇Ci和Cj的內(nèi)部互連度的規(guī)范化，定義如下：：Chameleon：使用動態(tài)的建模的多階段層次聚類當前第12頁\共有20頁\編于星期三\13點：概率層次聚類算法的層次聚類方法使用連接度量，往往使得聚類容易理解并且有效。它們廣泛用在許多聚類分析應(yīng)用中。然而，算法的層次聚類方法也有一些缺點。為層次聚類選擇一種好的距離度量常常是困難的為了使用算法的方法，數(shù)據(jù)對象不能有缺失的屬性值大部分算法的層次聚類方法都是啟發(fā)式的，在每一步局部地搜索好的合并/劃分。因此，結(jié)果聚類層次結(jié)構(gòu)的優(yōu)化目標可能不清晰。當前第13頁\共有20頁\編于星期三\13點：概率層次聚類概率層次聚類(probabilistichierarchicalclustering)旨在通過使用概率模型度量簇之間的距離，克服以上某些缺點。一種看待聚類問題的方法是，把待聚類的數(shù)據(jù)對象集看做要分析的基礎(chǔ)數(shù)據(jù)生成機制的一個樣本，或生成模型(generativemodel)。實踐中，我們可以假定該數(shù)據(jù)的生成模型采用常見的分布函數(shù)，如高斯分布或伯努利分布，它們由參數(shù)確定。于是，學(xué)習(xí)生成模型的任務(wù)就歸結(jié)為找出使得模型最佳擬合觀測數(shù)據(jù)集的參數(shù)值。

例10.6.當前第14頁\共有20頁\編于星期三\13點：概率層次聚類概率的層次聚類的一個缺點是，它只輸出一個關(guān)于選取的概率模型的層次結(jié)構(gòu)。它不能處理聚類層次結(jié)構(gòu)的不確定性。給出一個數(shù)據(jù)集，可能存在多個擬合觀測數(shù)據(jù)的層次結(jié)構(gòu)。算法的方法和概率的方法都不能發(fā)現(xiàn)這些層次結(jié)構(gòu)分布。最近，已經(jīng)開發(fā)了貝葉斯樹結(jié)構(gòu)模型來處理這些問題。當前第15頁\共有20頁\編于星期三\13點劃分和層次方法旨在發(fā)現(xiàn)球狀簇，為了發(fā)現(xiàn)任意形狀的簇，作為選擇，我們可以把簇看做數(shù)據(jù)空間中被稀疏區(qū)域分開的稠密區(qū)域。這是基于密度的聚類方法的主要策略，該方法可以發(fā)現(xiàn)非球狀的簇?；诿芏染垲惖幕炯夹g(shù)-三種代表性的方法：DBSCANOPTICSDENCLUE10.4基于密度的方法當前第16頁\共有20頁\編于星期三\13點：DBSCAN：一種基于高密度連通區(qū)域的基于密度的聚類

“如何在基于密度的聚類中發(fā)現(xiàn)稠密區(qū)域？”對象O密度可以用靠近O的對象數(shù)度量。DBSCAN(Density-BasedSpatialClusteringofApplicationswithNoise，具有噪聲應(yīng)用的基于密度的空間聚類)找出核心對象，即其鄰域稠密的對象。它連接核心對象和它們的鄰域，形成稠密區(qū)域作為簇。“DBSCAN如何確定對象鄰域？”一個用戶指定的參數(shù)用來指定每個對象的鄰域半徑。對象O的鄰域是以O(shè)為中心、以為半徑的空間。當前第17頁\共有20頁\編于星期三\13點由于鄰域大小由參數(shù)確定，因此，鄰域的密度可以簡單地用鄰域內(nèi)的對象數(shù)度量。為了確定一個鄰域是否稠密，DBSCAN使用另一個用戶指定的參數(shù)MinPts,指定稠密區(qū)域的密度閾值。如果一個對象的鄰域至少包含MinPts個對象，則該對象是核心對象(coreobject)。核心對象是稠密區(qū)域的支柱。

給定一個對象集D，我們可以識別關(guān)于參數(shù)和MinPts的所有核心對象。聚類任務(wù)就歸結(jié)為使用核心對象和它們的鄰域形成稠密區(qū)域，這里稠密區(qū)域就是簇。對于核心對象q和對象p，我們說p是從q(關(guān)于和MinPts)直接密度可達的(directlydensity-reachable),如果p在q的鄰域內(nèi)。顯然，對象p是從另一個對象q直接密度可達的，當且僅當q是核心對象，并且p在q的鄰域中。：DBSCAN：一種基于高密度連通區(qū)域的基于密度的聚類當前第18頁\共有20頁\編于星期三\13點“如何使用以核心對象為中心的小稠密區(qū)域來裝配一個大稠密區(qū)域？”在DBSCAN中，p是從q（關(guān)于和MinPts）密度可達的(density-reachable),如果存在一個對象鏈p1，p2，…，pn，使得p1=q，

pn=p，并且對于pi

D(1≤i≤n),pi+1是從pi關(guān)于和MinPts直接密度可達的。注意，密度可達不是等價關(guān)系，因為它不是對稱的。如果o1和o2都是核心對象，并且o1是從o2密度可達的，則o2是從o1密度可達的。然而，如果o2是核心對象而o1不是，則o1可能是從o2密度可達的的，但反過來就不可以。：DBSCAN：一種基于高密度連通區(qū)域的基于密度的聚類當前第19頁\共有20頁\編于星期三\13點為了把核心對象與它的近鄰連接成一個稠密區(qū)域，DBSCAN使用密度相連概念。兩個對象p1,p2

D是關(guān)于和MinPts密度相連的(density-connec