聚類分析基本概念和方法

聚類分析基本概念和方法第一頁，共二十二頁，編輯于2023年，星期一10.3：層次方法層次聚類方法(hierarchicalclusteringmethod):將數(shù)據(jù)對象組成層次結(jié)構(gòu)或簇的“樹”。對組織在層次結(jié)構(gòu)中的數(shù)據(jù)進(jìn)行匯總或特征化。層次劃分可以遞歸繼續(xù)，直到達(dá)到期望的粒度。層次結(jié)構(gòu)對于數(shù)據(jù)可視化特別有用。一種提高層次方法聚類質(zhì)量的有希望的方向是集成層次聚類與其他聚類技術(shù)，形成多階段聚類。第二頁，共二十二頁，編輯于2023年，星期一凝聚的層次聚類方法使用自底向上的策略。分裂的層次聚類方法使用自頂向下的策略。10.3.1：凝聚的與分裂的層次聚類層次聚類方法可以是凝聚的或分裂的，取決于層次分解是自底向上（合并）還是以自頂向下（分裂）方式形成。在凝聚或分裂聚類中，用戶都可以指定期望的簇個(gè)數(shù)作為終止條件。第三頁，共二十二頁，編輯于2023年，星期一10.3.1：凝聚的與分裂的層次聚類凝聚的層次聚類算法AGNES(AgglomerativeNESting)；分裂的層次聚類算法DIANA(DivisiveANAlysis)；單鏈接(single-linkoge)方法；樹狀圖的樹形結(jié)構(gòu)來表示層次聚類的過程。詳情見例10.3第四頁，共二十二頁，編輯于2023年，星期一10.3.2：算法方法的距離度量

無論使用凝聚方法還是只用分類方法，一個(gè)核心問題是度量兩個(gè)簇之間的距離，其中每個(gè)簇一般是一個(gè)對象集。4個(gè)廣泛采用的簇間距離，也稱鏈接度量(linkagemeasure)：最小距離：最大距離：均值距離：平均距離：第五頁，共二十二頁，編輯于2023年，星期一最近鄰聚類算法(nearest-neighborclusteringalgorithm)單鏈接算法(single-linkagealgorithm)最小生成樹算法(minimalspanningtreealgorithm)最遠(yuǎn)鄰聚類算法(farthest-neighborclusteringalgorithm)全連接算法(complete-linkagealgorithm)例10.410.3.2：算法方法的距離度量第六頁，共二十二頁，編輯于2023年，星期一10.3.3

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

第七頁，共二十二頁，編輯于2023年，星期一10.3.3

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

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

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

例10.5第九頁，共二十二頁，編輯于2023年，星期一10.3.3

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è)(選定的)聚類算法對CF樹的葉節(jié)點(diǎn)進(jìn)行聚類，把稀疏的簇當(dāng)做離群點(diǎn)刪除，而把稠密的簇合并為更大的簇。

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

例10.6.第十四頁，共二十二頁，編輯于2023年，星期一10.3.5：概率層次聚類概率的層次聚類的一個(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)模型來處理這些問題。第十五頁，共二十二頁，編輯于2023年，星期一劃分和層次方法旨在發(fā)現(xiàn)球狀簇，為了發(fā)現(xiàn)任意形狀的簇，作為選擇，我們可以把簇看做數(shù)據(jù)空間中被稀疏區(qū)域分開的稠密區(qū)域。這是基于密度的聚類方法的主要策略，該方法可以發(fā)現(xiàn)非球狀的簇?；诿芏染垲惖幕炯夹g(shù)-三種代表性的方法：DBSCANOPTICSDENCLUE10.4基于密度的方法第十六頁，共二十二頁，編輯于2023年，星期一10.4.1：DBSCAN：一種基于高密度連通區(qū)域的基于密度的聚類

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

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

pn=p，并且對于pi

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

D是關(guān)于和MinPts密度相連的(density-connected),如果存在一個(gè)對象q

D,使得對象p1和p2都是從q關(guān)于和MinPts密度可達(dá)。不像密度可達(dá)，密度相連是等價(jià)關(guān)系。容易證明，對于對象o1、o2和o3，如果o1和o2是密度相連的，并且o2和o3是密度相連的，則o1和o2也是密度相連的。例10.7。10.4.1：DBSCAN：一種基于高密度連通區(qū)域的基于密度的聚類第二十頁，共二十二頁，編輯于2023年，星期一

我們可以使用密度相連的閉包來發(fā)現(xiàn)連通的稠密區(qū)域作為簇。每個(gè)閉集都是一個(gè)基于密度的簇。子集CD是一個(gè)簇，如果（1）對于任意兩個(gè)對象o1、o2C,o1、o2是密度相連的，并且（2）不存在對象oC和另一個(gè)對象o’(D-C),使得o和o’是密度相連的。

“DBSCAN如何發(fā)現(xiàn)簇？”…

如果使用空間索引，則DBSCAN計(jì)算復(fù)雜度為O(nlogn)，其中n是數(shù)據(jù)庫對象數(shù)，其復(fù)雜度為O(n2)。如果用戶定義的參數(shù)和MinPts設(shè)置恰當(dāng)，則該算法可以有效地發(fā)現(xiàn)任意形狀的簇。10.4.1：DBSCAN：一種基于高密度連通區(qū)域的基于密度的聚類第二十一頁，共二十二頁，編輯于2023年，星期一10.4.2：OPTICS