聚類(lèi)分析基本概念和方法

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

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

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

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

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

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

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

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

BIRCH：使用聚類(lèi)特征樹(shù)的多階段聚類(lèi)

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

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

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

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

給定一個(gè)對(duì)象集D，我們可以識(shí)別關(guān)于參數(shù)和MinPts的所有核心對(duì)象。聚類(lèi)任務(wù)就歸結(jié)為使用核心對(duì)象和它們的鄰域形成稠密區(qū)域，這里稠密區(qū)域就是簇。對(duì)于核心對(duì)象q和對(duì)象p，我們說(shuō)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的鄰域中。10.4.1：DBSCAN：一種基于高密度連通區(qū)域的基于密度的聚類(lèi)第十八頁(yè)，共二十二頁(yè)，編輯于2023年，星期一“如何使用以核心對(duì)象為中心的小稠密區(qū)域來(lái)裝配一個(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ì)稱(chēng)的。如果o1和o2都是核心對(duì)象，并且o1是從o2密度可達(dá)的，則o2是從o1密度可達(dá)的。然而，如果o2是核心對(duì)象而o1不是，則o1可能是從o2密度可達(dá)的的，但反過(guò)來(lái)就不可以。10.4.1：DBSCAN：一種基于高密度連通區(qū)域的基于密度的聚類(lèi)第十九頁(yè)，共二十二頁(yè)，編輯于2023年，星期一為了把核心對(duì)象與它的近鄰連接成一個(gè)稠密區(qū)域，DBSCAN使用密度相連概念。兩個(gè)對(duì)象p1,p2

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

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

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

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

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