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

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

無論使用凝聚方法還是只用分類方法，一個(gè)核心問題是度量兩個(gè)簇之間的距離，其中每個(gè)簇一般是一個(gè)對(duì)象集。4個(gè)廣泛采用的簇間距離，也稱鏈接度量(linkagemeasure)：最小距離：最大距離：均值距離：平均距離：當(dāng)前5頁，總共20頁。最近鄰聚類算法(nearest-neighborclusteringalgorithm)單鏈接算法(single-linkagealgorithm)最小生成樹算法(minimalspanningtreealgorithm)最遠(yuǎn)鄰聚類算法(farthest-neighborclusteringalgorithm)全連接算法(complete-linkagealgorithm)例10.4：算法方法的距離度量當(dāng)前6頁，總共20頁。

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

當(dāng)前7頁，總共20頁。

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

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

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

例10.5當(dāng)前9頁，總共20頁。

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

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

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

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

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

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

pn=p，并且對(duì)于pi

D(1≤i≤n),pi+1是從pi關(guān)于和MinPts直接密度可達(dá)的。注意，密度可達(dá)不是等價(jià)關(guān)系，因?yàn)樗皇菍?duì)稱的。如果o1和o2都是核心對(duì)象，并且o1是從o2密度可達(dá)的，則o2是從o1密度可達(dá)的。然而，如果o2是核心對(duì)象而o1不是，則o1可能是從o2密度可達(dá)的的，但反過來就不可以。：DBSCAN：一種基于高密度連通區(qū)域的基于密度的聚類當(dāng)前19頁，總共20頁。為了把核心對(duì)象與它的近鄰連接成一個(gè)稠密區(qū)域，DBSCAN使用密度相連概念。兩個(gè)對(duì)象p1,p2

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