基于密度的聚類和基于網(wǎng)格的兩大聚類算法

數(shù)據(jù)挖掘

DataMining肖婷112090501

第十章聚類

2基于密度的聚類方法劃分和層次方法旨在發(fā)現(xiàn)球狀簇。他們很難發(fā)現(xiàn)任意形狀的簇。改進(jìn)思想，將簇看作數(shù)據(jù)空間中由低密度區(qū)域分隔開的高密度對(duì)象區(qū)域。這是基于密度的聚類方法的主要策略?；诿芏鹊木垲惙椒梢杂脕磉^濾噪聲孤立點(diǎn)數(shù)據(jù)，發(fā)現(xiàn)任意形狀的簇。DBSCAN：基于高密度連通區(qū)域聚類OPTICS：通過點(diǎn)排序識(shí)別聚類結(jié)構(gòu)DENCLUE:基于密度分布函數(shù)的聚類

3DBSCAN基于密度的簇是密度相連的點(diǎn)的集合主要思想尋找被低密度區(qū)域分離的高密度區(qū)域只要臨近區(qū)域的密度（單位大小上對(duì)象或數(shù)據(jù)點(diǎn)的數(shù)目）超過某個(gè)閾值，就繼續(xù)聚類

4DBSCAN兩個(gè)參數(shù)：Eps:鄰域的最大半徑MinPts:一個(gè)核心對(duì)象以Eps為半徑的鄰域內(nèi)的最小頂點(diǎn)數(shù)MinPts=5Eps=1cmpq5DBSCAN密度=制定半徑(Eps)內(nèi)點(diǎn)的個(gè)數(shù)如果一個(gè)對(duì)象的Eps鄰域至少包含最小數(shù)目MinPts個(gè)對(duì)象，則稱該對(duì)象為核心對(duì)象（Corepoint）如果一個(gè)對(duì)象是非核心對(duì)象,但它的鄰域中有核心對(duì)象，則稱該對(duì)象為邊界點(diǎn)（Borderpoint

）除核心對(duì)象和邊界點(diǎn)之外的點(diǎn)是噪聲點(diǎn)（Noisepoint

）6DBSCAN7DBSCAN密度可達(dá)的（Density-reachable）對(duì)于對(duì)象p和核心對(duì)象q(關(guān)于E和MinPts),我們稱p是從q(關(guān)于E和MinPts)直接密度可達(dá)，若對(duì)象p在對(duì)象q的E鄰域內(nèi)。如果存在一個(gè)對(duì)象鏈p1,…,pn,p1=q,pn=p

，pi+1是從pi關(guān)于Eps和MinPts

直接密度可達(dá)的，則對(duì)象p是從對(duì)象q關(guān)于Eps和MinPts

密度可達(dá)的。密度可達(dá)性是直接密度可達(dá)性的傳遞閉包，這種關(guān)系是非對(duì)稱的。只有核心對(duì)象之間是相互可達(dá)的。pqp18DBSCAN密度相連的（Density-connected）如果對(duì)象集合D中存在一個(gè)對(duì)象o，使得對(duì)象p和q是從o關(guān)于Eps

和MinPts密度可達(dá)的，那么對(duì)象p和q是關(guān)于Eps

和MinPts密度相連的。密度相連性是一個(gè)對(duì)稱的關(guān)系。pqo9DBSCAN:算法算法：DBSCAN輸入：D-數(shù)據(jù)對(duì)象集合；Eps-鄰域或稱為半徑；MinPts-密度閾值輸出：基于密度的簇的集合方法：Step1

讀取D中任意一個(gè)未分類的對(duì)象p；Step2

檢索出與p的距離不大于Eps的所有對(duì)象Neps(p)；Step3

如果|Neps(p)|<MinPts（即p為非核心對(duì)象），則將p標(biāo)記為噪聲，并執(zhí)行Step1；Step4

否則（即p為核心對(duì)象），給Neps(p)中的所有對(duì)象打上一個(gè)新的類標(biāo)簽newid，然后將這些對(duì)象壓入堆棧的Seeds中；Step5

讓CurrentObject=Seeds.top；然后檢索屬于Neps(CurrentObject)的所有對(duì)象；如果|Neps(CurrentObject)|>MinPts，則剔除已經(jīng)打上標(biāo)記的對(duì)象，將余下的未分類對(duì)象打上類標(biāo)簽newid，然后壓入堆棧；Step6

Seeds.pop，判斷Seeds是否為空，是，則執(zhí)行Step1

，否則執(zhí)行Step5。10DBSCANOriginalPointsClusters特點(diǎn)：抗噪聲能處理任意形狀聚類11OPTICS：通過點(diǎn)排序識(shí)別聚類結(jié)構(gòu)對(duì)于真實(shí)的，高維的數(shù)據(jù)集合而言，參數(shù)的設(shè)置通常是依靠經(jīng)驗(yàn)，難以確定。絕大多數(shù)算法對(duì)參數(shù)值是非常敏感的：設(shè)置的細(xì)微不同可能導(dǎo)致差別很大的聚類結(jié)果。OPTICS算法通過對(duì)象排序識(shí)別聚類結(jié)構(gòu)。OPTICS沒有顯式地產(chǎn)生一個(gè)數(shù)據(jù)集合簇，它為自動(dòng)和交互的聚類分析計(jì)算一個(gè)簇排序。這個(gè)次序代表了數(shù)據(jù)的基于密度的聚類結(jié)構(gòu)。較稠密中的對(duì)象在簇排序中相互靠近。12OPTICS簇排序選擇這樣的對(duì)象：即關(guān)于最小的E值，它是密度可達(dá)的，以便較高密度（較低E值）的簇先完成。對(duì)象p的核心距離：使p成為核心對(duì)象的最小?’。如果p不是核心對(duì)象，那么p的核心距離沒有任何意義?？蛇_(dá)距離：對(duì)象q到對(duì)象p的可達(dá)距離是指p的核心距離和p與q之間歐幾里得距離之間的較大值。如果p不是核心對(duì)象，p和q之間的可達(dá)距離沒有意義。13OPTICS：通過點(diǎn)排序識(shí)別聚類結(jié)構(gòu)算法思路首先檢查數(shù)據(jù)對(duì)象集合D中任一個(gè)對(duì)象的E—鄰域。設(shè)定其可達(dá)距離為“未定義”，并確定其核心距離，然后將對(duì)象及其核心距離和可達(dá)距離寫入文件。如果P是核心對(duì)象，則將對(duì)象P的E—鄰域內(nèi)的對(duì)象N(P)插入到一個(gè)種子隊(duì)列中，包含在種子隊(duì)列中的對(duì)象p’按到其直接密度可達(dá)的最近的核心對(duì)象q的可達(dá)距離排序。種子隊(duì)列中具有最小可達(dá)距離的對(duì)象被首先挑選出來，確定該對(duì)象的E一鄰域和核心距離，然后將其該對(duì)象及其核心距離和可達(dá)距離寫入文件中，如果當(dāng)前對(duì)象是核心對(duì)象，則更多的用于擴(kuò)展的后選對(duì)象被插入到種子隊(duì)列中。這個(gè)處理一直重復(fù)到再?zèng)]有一個(gè)新的對(duì)象被加入到當(dāng)前的種子隊(duì)列

中。OPTICS：通過點(diǎn)排序識(shí)別聚類結(jié)構(gòu)數(shù)據(jù)集的排序可以用圖形描述，有助于可視化和理解數(shù)據(jù)集中聚類結(jié)構(gòu)，例如下圖是一個(gè)簡(jiǎn)單的二維數(shù)據(jù)集的可達(dá)圖。其中三個(gè)高斯“凸起”反映數(shù)據(jù)集中比較稠密的部分。1415OPTICS：通過點(diǎn)排序識(shí)別聚類結(jié)構(gòu)Step1：有序種子隊(duì)列初始為空．結(jié)果隊(duì)列初始為空；Step2：如果所有點(diǎn)處理完畢．算法結(jié)束；否則選擇一個(gè)未處理對(duì)象（即不在結(jié)果隊(duì)列中）放人有序種子隊(duì)列：Step3：如果有序種子隊(duì)列為空，返回Step2，否則選擇種子隊(duì)列中的第一個(gè)對(duì)象P進(jìn)行擴(kuò)張：Step3.1：如果P不是核心節(jié)點(diǎn)．轉(zhuǎn)Step4；否則，對(duì)P的E鄰域內(nèi)任一未擴(kuò)張的鄰居q進(jìn)行如下處理Step3.1.1：如果q已在有序種子隊(duì)列中且從P到q的可達(dá)距離小于舊值，則更新q的可達(dá)距離，并調(diào)整q到相應(yīng)位置以保證隊(duì)列的有序性；Step3.1.2：如果q不在有序種f隊(duì)列中，則根據(jù)P到q的可達(dá)距離將其插入有序隊(duì)列；Step4：從有序種子隊(duì)列中刪除P．并將P寫入結(jié)果隊(duì)列中，返回Step3DENCLUE—基于密度分布函數(shù)的聚類DENCLUE是一種基于一組密度分布函數(shù)的聚類算法。該算法的原理是：每個(gè)數(shù)據(jù)點(diǎn)的影響可以用一個(gè)數(shù)學(xué)函數(shù)來形式化地模擬，它描述了一個(gè)數(shù)據(jù)點(diǎn)在鄰域內(nèi)的影響，被稱為影響函數(shù)。數(shù)據(jù)空間的整體密度(全局密度函數(shù))可以被模擬為所有數(shù)據(jù)點(diǎn)的影響函數(shù)的

總和；聚類可以通過確定密度吸引點(diǎn)(density

attractor)來得到，這里的密度吸引點(diǎn)是全局密度函數(shù)的局部最大值。一個(gè)點(diǎn)

x

是被一個(gè)密度吸引點(diǎn)

x*密度吸引的，如果存在一組點(diǎn)

x0，x1，…,xk，使得x0=x，xk=x*，對(duì)

0<i<k，xi-1

的梯度是在

xi的方向上，也就是說xi-1在xi的方向上變化最快。

使用一個(gè)步進(jìn)式爬山過程，把待分析的數(shù)據(jù)分配到密度吸引點(diǎn)

x*所代表的簇中。16DENCLUE—基于密度分布函數(shù)的聚類17DENCLUE—基于密度分布函數(shù)的聚類算法步驟：（1）對(duì)數(shù)據(jù)點(diǎn)占據(jù)的空間推導(dǎo)密度函數(shù)；（2）通過沿密度增長最大的方向(即梯度方向)移動(dòng)，識(shí)別密度函數(shù)的局

部最大點(diǎn)（這是局部吸引點(diǎn)），將每個(gè)點(diǎn)關(guān)聯(lián)到一個(gè)密度吸引點(diǎn)；（3）定義與特定的密度吸引點(diǎn)相關(guān)聯(lián)的點(diǎn)構(gòu)成的簇；（4）丟棄與非平凡密度吸引點(diǎn)相關(guān)聯(lián)的簇（密度吸引點(diǎn)x’稱為非平凡密

度吸引點(diǎn)，如果f*(x’)<η(其中f*是密度函數(shù),η是指定的閥值)；（5）若兩個(gè)密度吸引點(diǎn)之間存在密度大于或等于η的路徑，則合并他們

所代表的簇。對(duì)所有的密度吸引點(diǎn)重復(fù)此過程，直到不再改變時(shí)

算法中止。1819基于密度的聚類方法主要特征：發(fā)現(xiàn)任意形狀的聚類處理噪聲（孤立點(diǎn)數(shù)據(jù)）一次掃描需要密度參數(shù)作為終止條件基于網(wǎng)格的聚類聚類分析的算法有很多，其中一大類的傳統(tǒng)算法是基于距離的，這種基于距離的缺點(diǎn)在于只能發(fā)現(xiàn)球狀的簇、處理大數(shù)據(jù)集和高維數(shù)據(jù)集時(shí)不夠有效，另一方面它能發(fā)現(xiàn)的聚類個(gè)數(shù)常常依賴于用戶參數(shù)的指定，這對(duì)用戶來說經(jīng)常是很困難的?；诰W(wǎng)格(dding-based)指將對(duì)象空間量化為有限數(shù)目的單元，形成一個(gè)網(wǎng)格結(jié)構(gòu)，所有聚類都在這個(gè)網(wǎng)格結(jié)構(gòu)上進(jìn)行。20基于網(wǎng)格的聚類基本思想是將每個(gè)屬性的可能值分割成許多相鄰的區(qū)間，創(chuàng)建網(wǎng)格單元的集合（對(duì)于的討論我們假設(shè)屬性值是序數(shù)的、區(qū)間的或者連續(xù)的）。每個(gè)對(duì)象落入一個(gè)網(wǎng)格單元，網(wǎng)格單元對(duì)應(yīng)的屬性區(qū)間包含該對(duì)象的值。優(yōu)點(diǎn)是它的處理速度很快，其處理時(shí)間獨(dú)立于數(shù)據(jù)對(duì)象的數(shù)目，只與量化空間中每一維的單元數(shù)目有關(guān)。21STING:統(tǒng)計(jì)信息網(wǎng)格STING是一種基于網(wǎng)格的多分辨率聚類技術(shù)，它將空間區(qū)域劃分為矩形單元。針對(duì)不同級(jí)別的分辨率，通常存在多個(gè)級(jí)別的矩形單元，這些單元形成了一個(gè)層次結(jié)構(gòu)：高層的每個(gè)單元被劃分為多個(gè)低一層的單元。關(guān)于每個(gè)網(wǎng)格單元屬性的統(tǒng)計(jì)信息（例如平均值、最大值和最小值）被預(yù)先計(jì)算和存儲(chǔ)。這些統(tǒng)計(jì)信息用于回答查詢。22STING:統(tǒng)計(jì)信息網(wǎng)格網(wǎng)格中常用參數(shù)count-網(wǎng)格中對(duì)象數(shù)目mean-網(wǎng)格中所有值的平均值stdev-網(wǎng)格中屬性值的標(biāo)準(zhǔn)偏差min-網(wǎng)格中屬性值的最小值max-網(wǎng)格中屬性值的最大值distribution-網(wǎng)格中屬性值符合的分布類型。如正態(tài)分布、均勻分布、指數(shù)分布或者none（分布類型未知）23STING:統(tǒng)計(jì)信息網(wǎng)格24STING聚類的層次結(jié)構(gòu)STING:統(tǒng)計(jì)信息網(wǎng)格25levelileveli+1leveli+2

acellof(i-1)thlevelcorrespondsto4cellsof(i)thlevelSTING:統(tǒng)計(jì)信息網(wǎng)格26假設(shè)當(dāng)前層的屬性x的統(tǒng)計(jì)信息記為n,m,s,min,max,dist,而ni,mi,si,mini,maxi是相對(duì)于當(dāng)前層來說，對(duì)應(yīng)于更低一層的統(tǒng)計(jì)參數(shù)。那么n,m,s,min,max,dist可以用以下方法計(jì)算:

distSTING:統(tǒng)計(jì)信息網(wǎng)格27STING:

統(tǒng)計(jì)信息網(wǎng)格當(dāng)數(shù)據(jù)加載到數(shù)據(jù)庫時(shí)。最底層的單元參數(shù)直接由數(shù)據(jù)計(jì)算，若分布類型事先知道，可以用戶直接指定，而較高層的分布類型可以基于它對(duì)應(yīng)的低層單元多數(shù)的分布類型，用一個(gè)閾值過濾過程的合取來計(jì)算，若低層分布彼此不同，則高層分布設(shè)置為none。高層單元的統(tǒng)計(jì)參數(shù)可以很容易的從低層單元的參數(shù)計(jì)算得到。28STING:統(tǒng)計(jì)信息網(wǎng)格統(tǒng)計(jì)處理思想：使用自頂向下的方法回答空間數(shù)據(jù)的查詢從一個(gè)預(yù)先選擇的層次開始－通常包含少量的單元，為當(dāng)前層的每個(gè)單元計(jì)算置信區(qū)間不相關(guān)的單元不再考慮當(dāng)檢查完當(dāng)前層，接著檢查下一個(gè)低層次重復(fù)這個(gè)過程直到達(dá)到底層29STING:統(tǒng)計(jì)信息網(wǎng)格算法步驟：1從一個(gè)層次開始2對(duì)于這一層次的每個(gè)單元格，我們計(jì)算查詢相關(guān)的屬性值3從計(jì)算的屬性值及其約束條件中，我們將每一個(gè)單元格標(biāo)注成相關(guān)或者不相關(guān)4如果這一層是底層，則轉(zhuǎn)到步驟6，否則就行步驟55我們由層次結(jié)構(gòu)轉(zhuǎn)到下一層依照步驟2進(jìn)行計(jì)算6查詢結(jié)果滿足，轉(zhuǎn)到步驟8，否則轉(zhuǎn)到步驟77恢復(fù)數(shù)據(jù)到相關(guān)的單元格進(jìn)一步處理以得到滿意結(jié)果，轉(zhuǎn)到步驟88停止30STING:統(tǒng)計(jì)信息網(wǎng)格——應(yīng)用STING能夠用來幫助各種不同的空間查詢。這最常見的請(qǐng)求查詢是區(qū)域查詢。例如查詢滿足一定條件的區(qū)域。查找加利福尼亞州地區(qū)的房屋以得到房屋所在區(qū)域相關(guān)方面數(shù)據(jù)。查詢的對(duì)象是房屋，價(jià)格是其中的一個(gè)屬性。區(qū)域須滿足約束條件：哪些區(qū)域面積至少是A,單元地區(qū)至少有c棟房屋,至少d%的房屋其價(jià)格在a到b之間的置信度為1-t.且m<n,.

查詢語言（sql語言）SELECTREGIONFROMhouse-mapWHEREDENSITYin[c,∞)ANDPRICErange[a,b]WITHpercent[d%,l]ANDAREA(A,+)ANDLOCATIONCalifornia

31STING:統(tǒng)計(jì)信息網(wǎng)格假設(shè)選擇第一層作為查詢過程的開始點(diǎn)(也可以選擇包含少量單元網(wǎng)格的其他層)并假設(shè)最底層的網(wǎng)格的屬性price近似服從標(biāo)準(zhǔn)分布，高層網(wǎng)格的price屬性的分布可能是NONE。假設(shè)houses的price在[a,b]的概率p，我們可以求得p置信區(qū)間(或者估計(jì)其概率范圍)[p1,p2],可以檢查每個(gè)網(wǎng)格單元是否與給定查詢相關(guān)(p2*n>A*C*d%成立?)，若相關(guān)，則標(biāo)記該網(wǎng)格為relevant否則標(biāo)記為not-relevant

.處理層次結(jié)構(gòu)中的下一層。這個(gè)處理過程反復(fù)進(jìn)行。直

到到達(dá)最底層。最后返回滿足查詢要求的相關(guān)單元的區(qū)域。

查找結(jié)束。

32STING:統(tǒng)計(jì)信息網(wǎng)格優(yōu)點(diǎn)如下：計(jì)算是獨(dú)立于查詢的；有利于并行處理和增量更新；效率很高。STING算法掃描數(shù)據(jù)庫一次來計(jì)算單元的統(tǒng)計(jì)信息，因此產(chǎn)生聚類的時(shí)間復(fù)雜度是o(n)，其中n是對(duì)象的數(shù)目。在層次結(jié)構(gòu)建立后，查詢處理時(shí)間是，這里g是最低層網(wǎng)格單元的數(shù)目o(g)，通常遠(yuǎn)小于n。33STING:統(tǒng)計(jì)信息網(wǎng)格缺點(diǎn)如下：如果粒度比較細(xì)，處理的代價(jià)會(huì)顯著增加；但是，如果網(wǎng)格結(jié)構(gòu)最低層的粒度太粗，將會(huì)降低聚類分析的質(zhì)量；在構(gòu)建一個(gè)父親單元時(shí)沒有考慮孩子單元和其相鄰單元之間的關(guān)系，因此，結(jié)果簇的形狀是isothetic，即所有的聚類邊界或者是水平的，或者是豎直的，沒有斜的分界線。盡管該技術(shù)有快速的處理速度，但可能降低簇的質(zhì)量和精確性34CLIQUE:一種類似于Apriori的子空間聚類方法CLICQUE算法是基于網(wǎng)格的空間聚類算法，但它同時(shí)非常好地結(jié)合了基于密度的聚類算法思想，因此既可以像基于密度的方法發(fā)現(xiàn)任意形狀的簇，又可以像基于網(wǎng)格的方法處理較大的多維數(shù)據(jù)集。CLIQUE把每個(gè)維劃分成不重疊的區(qū)間，從而把數(shù)據(jù)對(duì)象的整個(gè)嵌入空間劃分成單元。它使用一個(gè)密度閥值識(shí)別稠密單元，一個(gè)單元是稠密的，如果映射到它的對(duì)象超過該密度閥值35CLIQUE:一種類似于Apriori的子空間聚類方法算法概述：算法需要兩個(gè)參數(shù)值，一個(gè)是網(wǎng)格的步長，一具是密度閾值。

網(wǎng)格步長決定了空間的劃分，而密度閾值用來定義密集網(wǎng)格。

聚類思想：算法首先掃描所有網(wǎng)格，當(dāng)發(fā)現(xiàn)第一個(gè)密集網(wǎng)格時(shí)，便以該網(wǎng)格開始擴(kuò)展，擴(kuò)展原則是若一個(gè)網(wǎng)格與已知密集區(qū)域內(nèi)的網(wǎng)格鄰接并且其自身也是密集的，則將該網(wǎng)格加入到該密集區(qū)域中、直到不再有這樣的網(wǎng)格被發(fā)現(xiàn)為止。算法再繼續(xù)掃描網(wǎng)