基于密度方法的聚類全解課件

聚類分析宋宜飛聚類分析宋宜飛1主要內(nèi)容回顧密度聚類方法

DBSCAN算法OPTICS算法網(wǎng)格聚類方法

CLIQUE算法主要內(nèi)容回顧2回顧聚類聚類(clustering)也稱為聚類分析,指將樣本分到不同的組中使得同一組中的樣本差異盡可能的小，而不同組中的樣本差異盡可能的大。聚類得到的不同的組稱為簇(cluster)。一個好的聚類方法將產(chǎn)生以下的聚類最大化類中的相似性最小化類間的相似性回顧聚類3回顧聚類的分類：

劃分聚類方法層次聚類方法

密度聚類方法網(wǎng)格聚類方法

模型聚類方法回顧聚類的分類：4在基于劃分的聚類中，任務(wù)就是將數(shù)據(jù)劃分成K個不相交的點集，使每個子集中的點盡可能同質(zhì)。基于劃分的方法，其代表算法有k-means算法、K-medoids等劃分聚類方法在基于劃分的聚類中，任務(wù)就是將數(shù)據(jù)劃分成K個不相交的點集，使5k-means算法k-means算法基本步驟從n個數(shù)據(jù)對象任意選擇k個對象作為初始聚類中心；根據(jù)每個聚類對象的均值(中心對象)，計算每個對象與這些中心對象的距離；并根據(jù)最小距離重新對相應(yīng)對象進(jìn)行劃分；重新計算每個(有變化)聚類的均值(中心對象)；計算標(biāo)準(zhǔn)測度函數(shù)，當(dāng)滿足一定條件，如函數(shù)收斂時，則算法終止；如果條件不滿足則回到步驟2。k-means算法k-means算法基本步驟www.wo6k-means優(yōu)缺點主要優(yōu)點：是解決聚類問題的一種經(jīng)典算法，簡單、快速。對處理大數(shù)據(jù)集，該算法是相對可伸縮和高效率的。當(dāng)結(jié)果簇是密集的，它的效果較好。主要缺點在簇的平均值被定義的情況下才能使用。必須事先給出k（要生成的簇的數(shù)目），而且對初值敏感，對于不同的初始值，可能會導(dǎo)致不同結(jié)果。不適合于發(fā)現(xiàn)非凸面形狀的簇或者大小差別很大的簇。而且，它對于“躁聲”和孤立點數(shù)據(jù)是敏感的。k-means優(yōu)缺點主要優(yōu)點：www.wondershare7層次聚類方法層次聚類方法對給定的數(shù)據(jù)集進(jìn)行層次的分解，直到某種條件滿足為止。具體又可分為：

凝聚的層次聚類：一種自底向上的策略，首先將每個對象作為一個簇，然后合并這些原子簇為越來越大的簇，直到某個終結(jié)條件被滿足。

分裂的層次聚類：采用自頂向下的策略，它首先將所有對象置于一個簇中，然后逐漸細(xì)分為越來越小的簇，直到達(dá)到了某個終結(jié)條件。層次凝聚的代表是AGNES算法。層次分裂的代表是DIANA算法。層次聚類方法層次聚類方法對給定的數(shù)據(jù)集進(jìn)行層次的分解，直到某8層次聚類優(yōu)缺點層次聚類方法是不可逆的，也就是說，當(dāng)通過凝聚式的方法將兩組合并后，無法通過分裂式的辦法再將其分離到之前的狀態(tài)，反之亦然。另外，層次聚類過程中調(diào)查者必須決定聚類在什么時候停止，以得到某個數(shù)量的分類。在不必要的情況下應(yīng)該小心使用層次聚類方法。層次聚類優(yōu)缺點層次聚類方法是不可逆的，也就是說，當(dāng)通過凝聚式9劃分聚類方法層次聚類方法

密度聚類方法：基于密度的聚類方法以數(shù)據(jù)集在空間分布上的稠密程度為依據(jù)進(jìn)行聚類，無需預(yù)先設(shè)定簇的數(shù)量，因此特別適合對于未知內(nèi)容的數(shù)據(jù)集進(jìn)行聚類。網(wǎng)格聚類方法

模型聚類方法密度聚類方法密度聚類方法10基于密度方法的聚類密度聚類方法的指導(dǎo)思想是，只要一個區(qū)域中的點的密度大于某個域值，就把它加到與之相近的聚類中去。對于簇中每個對象，在給定的半徑ε的鄰域中至少要包含最小數(shù)數(shù)目（MinPts）個對象。這類算法能克服基于距離的算法只能發(fā)現(xiàn)“類圓形”的聚類的缺點，可發(fā)現(xiàn)任意形狀的聚類，且對噪聲數(shù)據(jù)不敏感。代表算法有：DBSCAN、OPTICS、DENCLUE算法等?；诿芏确椒ǖ木垲惷芏染垲惙椒ǖ闹笇?dǎo)思想是，只要一個區(qū)域中的11基于密度方法的聚類-DBSCANDBSCAN（Density-BasedSpatialClusteringofApplicationswithNoise）一個比較有代表性的基于密度的聚類算法。與層次聚類方法不同，它將簇定義為密度相連的點的最大集合，能夠把具有足夠高密度的區(qū)域劃分為簇，并可在有“噪聲”的空間數(shù)據(jù)庫中發(fā)現(xiàn)任意形狀的聚類。基于密度方法的聚類-DBSCANDBSCAN（Densit12傳統(tǒng)基于中心的密度定義為：數(shù)據(jù)集中特定點的密度通過該點ε半徑之內(nèi)的點計數(shù)(包括本身)來估計。顯然，密度依賴于半徑。傳統(tǒng)的密度定義：基于中心的方法傳統(tǒng)基于中心的密度定義為：傳統(tǒng)的密度定義：基于中心的方法ww13基于密度方法的聚類-DBSCAN所用到的基本術(shù)語定義對象的ε-鄰域：給定對象在半徑ε內(nèi)的區(qū)域。定義核心對象：如果一個對象的ε-鄰域至少包含最小數(shù)目MinPts個對象，則稱該對象為核心對象。

例下圖中，ε=1cm，MinPts=5，q是一個核心對象。定義直接密度可達(dá)：給定一個對象集合D，如果p是在q的ε-鄰域內(nèi)，而

q是一個核心對象，我們說對象p從對象q出發(fā)是直接密度可達(dá)的。

例在下圖中，ε=1cm，MinPts=5，q是一個核心對象，對象

p1從對象q出發(fā)是直接密度可達(dá)的。基于密度方法的聚類-DBSCAN所用到的基本術(shù)語www.14基于密度方法的聚類-DBSCAN所用到的基本術(shù)語密度可達(dá)定義密度可達(dá)的：如果存在一個對象鏈p1，p2，…，pn，p1=q，

pn=p，對pi∈D，（1<=i<=n），pi+1是從pi關(guān)于ε和MitPts直接密度可達(dá)的，則對象p是從對象q關(guān)于ε和MinPts密度可達(dá)的。例在下圖中，ε=1cm，MinPts=5，q是一個核心對象，p1是從q關(guān)于ε和MitPts直接密度可達(dá)，p是從p1關(guān)于ε和MitPts直接密度可達(dá)，則對象p從對象q關(guān)于ε和MinPts密度可達(dá)的基于密度方法的聚類-DBSCAN所用到的基本術(shù)語密度可達(dá)15基于密度方法的聚類-DBSCAN所用到的基本術(shù)語圖密度相連圖噪聲定義噪聲:一個基于密度的簇是基于密度可達(dá)性的最大的密度相連對象的集合。不包含在任何簇中的對象被認(rèn)為是“噪聲”。邊界點：邊界點不是核心點，但落在某個核心點的鄰域內(nèi)。噪聲就是那些既不是邊界點也不是核心點的對象定義

密度相連的：如果對象集合D中存在一個對象o，使得對象p

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

ε和MinPts密度相連的?；诿芏确椒ǖ木垲?DBSCAN所用到的基本術(shù)語圖密16DBSCAN算法概念示例如圖所示，ε

用一個相應(yīng)的半徑表示，設(shè)MinPts=3，請分析Q,M,P,S,O,R這5個樣本點之間的關(guān)系?！爸苯用芏瓤蛇_(dá)”和“密度可達(dá)”概念示意描述解答：根據(jù)以上概念知道：由于有標(biāo)記的各點-M、P、O和R的ε

近鄰均包含3個以上的點，因此它們都是核對象；M-是從P“直接密度可達(dá)”；而Q則是從-M“直接密度可達(dá)”；基于上述結(jié)果，Q是從P“密度可達(dá)”；但P從Q無法“密度可達(dá)”(非對稱)。類似地，S和R從O是“密度可達(dá)”的；O、R和S均是“密度相連”的。DBSCAN算法概念示例如圖所示，ε用一個相應(yīng)的半徑表示17基于密度方法的聚類-DBSCANDBSCAN算法根據(jù)以上的定義在數(shù)據(jù)庫中發(fā)現(xiàn)簇和噪聲。簇可等價于集合D中，這個簇核心對象密度可達(dá)的所有對象的集合。DBSCAN通過檢查數(shù)據(jù)集中每個對象的ε-鄰域來尋找聚類。如果一個點p的ε-鄰域包含多于MinPts個對象，則創(chuàng)建一個p作為核心對象的新簇C。然后，DBSCAN從C中尋找未被處理對象q的ε-鄰域，如果q的ε-鄰域包含多MinPts個對象，則還未包含在C中的q的鄰點被加入到簇中，并且這些點的ε-鄰域?qū)⒃谙乱徊街羞M(jìn)行檢測。這個過程反復(fù)執(zhí)行，當(dāng)沒有新的點可以被添加到任何簇時，該過程結(jié)束。具體如下：基于密度方法的聚類-DBSCANDBSCAN算法根據(jù)以上18基于密度方法的聚類-DBSCANDBSCAN算法描述：輸入：包含n個對象的數(shù)據(jù)庫，半徑ε，最少數(shù)目MinPts。輸出：所有生成的簇，達(dá)到密度要求。1.REPEAT2.從數(shù)據(jù)庫中抽取一個未處理過的點；3.IF抽出的點是核心點THEN找出所有從該點密度可達(dá)的對象，形成一個簇4.ELSE抽出的點是邊緣點(非核心對象)，跳出本次循環(huán)，尋找下一點；5.UNTIL所有點都被處理；基于密度方法的聚類-DBSCANDBSCAN算法描述：ww19DBSCAN算法步驟

輸入：數(shù)據(jù)集D，參數(shù)MinPts,ε輸出：簇集合(1)首先將數(shù)據(jù)集D中的所有對象標(biāo)記unvisited；(2)do(3)從D中隨機(jī)選取一個unvisited對象p，并將p標(biāo)記為visited；ifp的ε鄰域包含的對象數(shù)至少為MinPts個創(chuàng)建新簇C，并把p添加到c中；令N為p的ε鄰域中對象的集合；(7)forN中每個點piifpi是unvisited標(biāo)記pi為visited；ifpi的ε鄰域至少有MinPts個對象，把這些對象添加到N；ifpi還不是任何簇的對象。將pi添加到簇C中；(12)endfor(13)輸出C(14)Else標(biāo)記p為噪聲(15)Untill沒有標(biāo)記為unvisited的對象DBSCAN算法步驟輸入：數(shù)據(jù)集D，參數(shù)MinPts,ε20基于密度方法的聚類-DBSCAN

下面給出一個樣本事務(wù)數(shù)據(jù)庫（見下表），對它實施DBSCAN算法。根據(jù)所給的數(shù)據(jù)通過對其進(jìn)行DBSCAN算法，以下為算法的步驟（設(shè)n=12，用戶輸入ε=1，MinPts=4）

序號屬性1屬性2121251312422532642752862913102311531224樣本事務(wù)數(shù)據(jù)庫基于密度方法的聚類-DBSCAN下面給出一個樣本事務(wù)21DBSCAN聚類過程第1步，在數(shù)據(jù)庫中選擇一點1，由于在以它為圓心的，以1為半徑的圓內(nèi)包含2個點（小于4），因此它不是核心點，選擇下一個點。第2步，在數(shù)據(jù)庫中選擇一點2，由于在以它為圓心的，以1為半徑的圓內(nèi)包含2個點，因此它不是核心點，選擇下一個點。第3步，在數(shù)據(jù)庫中選擇一點3，由于在以它為圓心的，以1為半徑的圓內(nèi)包含3個點，因此它不是核心點，選擇下一個點。DBSCAN聚類過程第1步，在數(shù)據(jù)庫中選擇一點1，由于在以它22DBSCAN聚類過程第4步，在數(shù)據(jù)庫中選擇一點4，由于在以它為圓心的，以1為半徑的圓內(nèi)包含5個點，因此它是核心點，尋找從它出發(fā)可達(dá)的點（直接可達(dá)4個，間接可達(dá)3個），聚出的新類{1，3，4，5，9，10，12}，選擇下一個點。DBSCAN聚類過程第4步，在數(shù)據(jù)庫中選擇一點4，由于在以它23DBSCAN聚類過程第5步，在數(shù)據(jù)庫中選擇一點5，已經(jīng)在簇1中，選擇下一個點。第6步，在數(shù)據(jù)庫中選擇一點6，由于在以它為圓心的，以1為半徑的圓內(nèi)包含3個點，因此它不是核心點，選擇下一個點。DBSCAN聚類過程第5步，在數(shù)據(jù)庫中選擇一點5，已經(jīng)在簇124DBSCAN聚類過程第7步，在數(shù)據(jù)庫中選擇一點7，由于在以它為圓心的，以1為半徑的圓內(nèi)包含5個點，因此它是核心點，尋找從它出發(fā)可達(dá)的點，聚出的新類{2，6，7，8，11}，選擇下一個點。DBSCAN聚類過程第7步，在數(shù)據(jù)庫中選擇一點7，由于在以它25DBSCAN聚類過程第8步，在數(shù)據(jù)庫中選擇一點8，已經(jīng)在簇2中，選擇下一個點。第9步，在數(shù)據(jù)庫中選擇一點9，已經(jīng)在簇1中，選擇下一個點。第10步，在數(shù)據(jù)庫中選擇一點10，已經(jīng)在簇1中，選擇下一個點。第11步，在數(shù)據(jù)庫中選擇一點11，已經(jīng)在簇2中，選擇下一個點。第12步，選擇12點，已經(jīng)在簇1中，由于這已經(jīng)是最后一點所有點都以處理，程序終止。DBSCAN聚類過程第8步，在數(shù)據(jù)庫中選擇一點8，已經(jīng)在簇226基于密度方法的聚類-DBSCAN步驟選擇的點在ε中點的個數(shù)通過計算可達(dá)點而找到的新簇112無222無333無445簇C1：{1，3，4，5，9，10，12}553已在一個簇C1中663無775簇C2：{2，6，7，8，11}882已在一個簇C2中993已在一個簇C1中10104已在一個簇C1中，11112已在一個簇C2中12122已在一個簇C1中算法執(zhí)行過程：基于密度方法的聚類-DBSCAN步驟選擇的點在ε中點的個數(shù)27DBSCAN的時間復(fù)雜性時間復(fù)雜度DBSCAN算法要對每個數(shù)據(jù)對象進(jìn)行鄰域檢查時間性能較低。DBSCAN的基本時間復(fù)雜度是O(N*找出Eps領(lǐng)域中的點所需要的時間),N是點的個數(shù)。最壞情況下時間復(fù)雜度是O(N2)在低維空間數(shù)據(jù)中,有一些數(shù)據(jù)結(jié)構(gòu)如KD樹，使得可以有效的檢索特定點給定距離內(nèi)的所有點，時間復(fù)雜度可以降低到O(NlogN)DBSCAN的時間復(fù)雜性時間復(fù)雜度www.wondersha28DBSCAM的空間復(fù)雜性空間復(fù)雜度

在聚類過程中，DBSCAN一旦找到一個核心對象，即以該核心對象為中心向外擴(kuò)展．此過程中核心對象將不斷增多，未處理的對象被保留在內(nèi)存中．若數(shù)據(jù)庫中存在龐大的聚類，將需要很大的存來存儲核心對象信息，其需求難以預(yù)料．當(dāng)數(shù)據(jù)量增大時，要求較大的內(nèi)存支持I/0消耗也很大;

低維或高維數(shù)據(jù)中，其空間都是O(N)DBSCAM的空間復(fù)雜性空間復(fù)雜度www.wondersha29基于密度方法的聚類優(yōu)點能克服基于距離的算法只能發(fā)現(xiàn)“類圓形”的聚類的缺點，可發(fā)現(xiàn)任意形狀的聚類，有效地處理數(shù)據(jù)集中的噪聲數(shù)據(jù)，數(shù)據(jù)輸入順序不敏感缺點輸入?yún)?shù)敏感．確定參數(shù)ε，MinPts困難，若選取不當(dāng)，將造成聚類質(zhì)量下降．由于在DBSCAN算法中，變量ε，MinPts是全局惟一的，當(dāng)空間聚類的密度不均勻、聚類間距離相差很大時，聚類質(zhì)量較差。計算密度單元的計算復(fù)雜度大，需要建立空間索引來降低計算量，且對數(shù)據(jù)維數(shù)的伸縮性較差。這類方法需要掃描整個數(shù)據(jù)庫，每個數(shù)據(jù)對象都可能引起一次查詢，因此當(dāng)數(shù)據(jù)量大時會造成頻繁的I/O操作。。基于密度方法的聚類優(yōu)點30OPTICS算法

由于在DBSCAN算法中，變量ε，MinPts是全局惟一的，當(dāng)空間聚類的密度不均勻、聚類間距離相差很大時，聚類質(zhì)量較差。許多現(xiàn)實的數(shù)據(jù)集內(nèi)在的聚類結(jié)構(gòu)不能夠通過全局的密度參數(shù)來描述，數(shù)據(jù)空間中不同區(qū)域的聚類需要不同的局部密度。OPTICS算法由于在DBSCAN算法中，變量31OPTICS算法盡管dbscan能夠根據(jù)給定的輸入?yún)?shù)ε，和MinPts聚類對象，但是它把選擇能產(chǎn)生可接受的聚類結(jié)果的參數(shù)值的責(zé)任留給了用戶。這是許多其他算法都存在的問題。但是對于高維數(shù)據(jù)而言設(shè)定準(zhǔn)確的參數(shù)非常困難。參數(shù)設(shè)置有細(xì)微的不同都可能導(dǎo)致差別很大的聚類結(jié)果。全局參數(shù)不能很好地刻畫其內(nèi)在的聚類結(jié)構(gòu)。OPTICS算法盡管dbscan能夠根據(jù)給定的輸入?yún)?shù)ε，32OPTICS算法下圖中所描述的數(shù)據(jù)集不能通過一個全局密度參數(shù)同時區(qū)分出簇A、B、C、C1、C2和C3，只能得到A、B、C或C1、C2和C3，對于C1、C2和C3而言A、B、C都是噪聲。對于固定的MinPts值，和兩個ε1＜

ε2，關(guān)于ε1的MinPts簇C一定是關(guān)于ε2和MinPts簇C’的子集，這就意味著。如果兩個對象在同一個基于密度的簇中，則它們也是在同一個具有較低密度要求的簇中。OPTICS算法下圖中所描述的數(shù)據(jù)集不能通過一個33OPTICS算法為了克服在聚類分析中使用一組全局參數(shù)的缺點，提出了OPTICS聚類分析方法。P為對象，數(shù)據(jù)集D，為距離值，N(q)為鄰域，MinPts

。兩個定義：

P的核心距離：使得P成為核心對象的最小‘，‘是使p稱為核心對象的最小半徑閾值。若|（N(q)MinPts，即P不是核心對象，核心距離則無定義。q關(guān)于對象P的可達(dá)距離：是使q從p密度可達(dá)的最小半徑。p的核心距離和p,q的歐幾里得距離之間的較大值，p必須是核心對象且q在p的鄰域內(nèi)。若|N(p)|MinPts，即P不是核心對象，則無定義否則，定義為Max（核心距離，|（p,q）|）OPTICS算法為了克服在聚類分析中使用一組全局參數(shù)的缺點34OPTICS算法例核心距離與可達(dá)距離,假設(shè)

=6mm，MinPts=5。P的核心距離是p于第四個最近的數(shù)據(jù)對象之間的距離‘，q1到p的可達(dá)距離是p的核心距離（‘=3mm），因為它比q1到p的歐氏距離大。q2關(guān)于p的科大距離是p到q2的歐氏距離，它大于p的核心距離。OPTICS算法例核心距35OPTICS算法OPTICS算法并不顯式的產(chǎn)生數(shù)據(jù)及聚類，而是輸出簇排序（clusterordering），這個排序是所有分析對象的線性表，并且代表數(shù)據(jù)基于密度的聚類結(jié)構(gòu)。較稠密簇中的對象在簇排序中相互靠近。這個排序等價于從較廣泛的參數(shù)設(shè)置中得到基于密度的聚類。這樣optics不需要用戶提供特定密度閾值。簇排列可以用來提取基本聚類信息，導(dǎo)出內(nèi)在的聚類結(jié)構(gòu)，也可以提供聚類的可視化。OPTICS算法OPTICS算法并不顯式的產(chǎn)生數(shù)據(jù)及聚類36OPTICS算法為了構(gòu)造不同的類，對象需要按特定的次序處理，這個次序選擇這樣的對象，及關(guān)于最小的值，它是密度可達(dá)的，以便較高密度（較低值）的簇先完成。optics算法計算給定數(shù)據(jù)庫中所有對象的排序，并且存儲每個對象核心距離和相應(yīng)的可達(dá)距離。optics維護(hù)一個稱作orderseeds的表來來產(chǎn)生輸出排列，orderseeds中的對象按到各自的最近核心對象的可達(dá)距離排序，及按每個對象的最小可達(dá)距離排序。OPTICS算法為了構(gòu)造不同的類，對象需要按特定的次序處理37OPTICS算法OPTICS算法38尋找簇Reachability-distanceundefined‘Cluster-orderoftheobjects尋找簇Reachability-distanceundefi39數(shù)據(jù)集的簇排序可以用圖形描述，這有助于可視化和理解數(shù)據(jù)集中聚類結(jié)構(gòu)。例如下圖是一個簡單的二維數(shù)據(jù)集的可達(dá)性圖?？蛇_(dá)距離未定義’數(shù)據(jù)集的簇排序可以用圖形描述，這有助于可視化和理解數(shù)據(jù)集中聚40OPTICS算法并不直接尋找各個簇,而是將基于密度查找簇所需要的信息記錄下來,這些信息反映了數(shù)據(jù)空間基于密度的簇結(jié)構(gòu)。同時從這些密度信息可以直接發(fā)現(xiàn)各個簇。OPTICS采取了兩個方法來達(dá)到目標(biāo)1)定義了對象的核心距離和可達(dá)距離,以反映對象附近的密度大小;2)在迭代查找可達(dá)對象時,對種子對象依可達(dá)距離進(jìn)行排序,從而在簇擴(kuò)展時優(yōu)先擴(kuò)展密度值較大區(qū)域的點。這樣,OPTICS算法實現(xiàn)了數(shù)據(jù)庫所有對象的排序,這一對象序列就可以反映出數(shù)據(jù)空間基于密度的簇結(jié)構(gòu)信息。基于這些信息可以容易地確定合適的ε值,并隨之發(fā)現(xiàn)各個簇。另外,OPTICS還提供了自動的簇發(fā)現(xiàn)方法。OPTICS算法較好地解決了DBSCAN算法的對輸入?yún)?shù)ε敏感的問題,但是由于采用了復(fù)雜的處理方法以及額外的磁盤IPO操作,使得OPTICS實際運(yùn)行的速度遠(yuǎn)遠(yuǎn)低于DBSCAN。OPTICS算法并不直接尋找各個簇www.wondersha41424344不同密度、形狀、大小的簇不同密度、形狀、大小的簇www.wondershare.co45參數(shù)的影響減小，則可達(dá)距離為無窮大的點增多；

MinPts減小，核心對象增多，圖象更尖銳參數(shù)的影響減小，則可達(dá)距離為無窮大的點增多；www.won46

基于網(wǎng)格的方法（Grid-BasedMethods）

聚類高維數(shù)據(jù)是聚類分析中一個非常重要的任務(wù)，而一般聚類方法無法處理這些數(shù)據(jù)。用戶感興趣的通常是某個高維數(shù)據(jù)空間的若干個子空間，對該空間內(nèi)數(shù)據(jù)點的聚類要比原始空間更好一些。高維數(shù)據(jù)中，通常只有少數(shù)幾維與某些簇相關(guān)，其他不相關(guān)的維數(shù)據(jù)可能會產(chǎn)生大量的噪聲而屏蔽真實的簇。

為聚類高維數(shù)據(jù)集便提出了基于網(wǎng)格的方法的聚類?；诰W(wǎng)格的方法（Grid-BasedMethods）ww47

基于網(wǎng)格的方法（Grid-BasedMethods）

將數(shù)據(jù)空間劃分成為有限個單元（cell）的網(wǎng)格結(jié)構(gòu)，所有的處理都是以單個單元為對象的。這種方法的主要優(yōu)點是它的處理速度很快，處理時間獨立于數(shù)據(jù)對象的數(shù)目，只與每一維所劃分的單元數(shù)目有關(guān)代表算法有：CLIQUE算法?；诰W(wǎng)格的方法（Grid-BasedMethods）48CLQUE是一個綜合了基于密度和基于網(wǎng)格方法的聚類算法，對于大型數(shù)據(jù)庫中的高維數(shù)據(jù)的聚類比較有效,在高維數(shù)據(jù)的子空間中識別稠密的聚類，所產(chǎn)生的理解結(jié)果與所給的輸入數(shù)據(jù)無關(guān)。CLIQUE：高維度數(shù)據(jù)的自動子空間聚類算法CLQUE是一個綜合了基于密度和基于網(wǎng)格方法的聚類算法，對于49CLIQUE：聚類高維空間CLIQUE的中心思想如下：給定一個多維數(shù)據(jù)點的大集合，數(shù)據(jù)點在數(shù)據(jù)空間中通常不是均衡分布的。CLIQUE區(qū)分空間中稀疏的和“擁擠的”區(qū)域，以發(fā)現(xiàn)數(shù)據(jù)集合全局分布模式。

將數(shù)據(jù)空間中的每個維劃分成等長且數(shù)量相等的間隔段，即單元。如果一個單元中的包含數(shù)據(jù)點超過了某個輸入模型參數(shù)，則該單元是密集的。在CLIQUE中，一個聚類被定義為相連的密集單元的最大集合。CLIQUE：聚類高維空間CLIQUE的中心思想如下：www50問題描述

要能自動地識別一個高維數(shù)據(jù)的子空間限制在只對原始空間的子空間的搜索而不是使用一個新的維度為了識別數(shù)據(jù)點的密度，將數(shù)據(jù)空間劃分并找出在每個單元中數(shù)據(jù)點的數(shù)量。聚類是子空間中相連的高密度單元的并集，即將聚類映射到軸對稱的超矩形中。問題描述要能自動地識別一個高維數(shù)據(jù)的子空間www.wond51聚類在空間中的描述設(shè)A＝{A1,A2,…,Ad}是一個有界的、全部有序的域的集合。而S＝A1×A2×…×Ad是一個d維的數(shù)字空間，A1，A2，…，Ad定義為S的維。輸入是由d維點集V＝{v1,v2,…,vm}組成的，其中Vi=<Vi1,Vi2,…,Vid>,Vi的第j個元素來自域Aj。將數(shù)據(jù)空間S劃分成非重疊矩形單元。單元的劃分方法是在每一個維上將維分割成ξ個等長的間隔段，ξ是輸入?yún)?shù)。每一個單元u是由每一個屬性一個間隔段組成的交集。形式為{u1,u2,…,ud}，其中ui=[li,hi）是在Ai的劃分中的右邊界開放的間隔段。聚類在空間中的描述設(shè)A＝{A1,A2,…,Ad}是一個有界的52聚類在空間中的描述一個點V＝<v1,v2,…,vd>屬于單元u={u1,u2,..ud},當(dāng)對所有的ui，有l(wèi)i≤vi<hi。一個單元的選擇性（selectivity）：單元內(nèi)數(shù)據(jù)點的數(shù)量與單元的總數(shù)據(jù)點數(shù)量之比。稱單元u是稠密的：若單元的選擇性大于密度閾值τ。聚類在空間中的描述一個點V＝<v1,v2,…,vd>屬于單元53聚類在空間中的描述兩個k維單元u1，u2是連接的，即他們之間有一個公共面。若存在k-1維，假設(shè)是維At1，At2，…,Atk-1，單元u1＝{rt1,rt2,…,rtk}及u2={rt1’，rt2’，…,rtk-1’}是相連的，則有rtj=rtj’，并且有htk＝ltk’

或者h(yuǎn)tk’＝ltk。若R∩C＝R，則稱一個區(qū)域R包含于一個聚類C中。若沒有其他R的超集包含于聚類C中，則稱區(qū)域R是最大的。一個聚類的最小描述是具有最大區(qū)域的聚類的非冗余的覆蓋。

聚類在空間中的描述54例子（一）

在下圖中，二維空間（age,salary）劃分成10×10格一個單元是間隔段的交集；例如單元u＝（30≤age<35）∧（1≤salary<2）。一個區(qū)域是單元的矩形的并集。A與B是兩個區(qū)域：A＝（30≤age<50）∧（4≤salary<8）,B=（40≤age<60）∧（2≤salary<6）。假設(shè)陰影部分是稠密的單元，A∪B是一個聚類。該聚類的最小描述為：（（30≤age<50）∧（4≤salary<8））∨（（40≤age<60）∧（2≤salary<6））。例子（一）在下圖中，二維空間（age,salary）劃55例子（二）：圖二：原始數(shù)據(jù)空間的子空間中的聚類在圖二中，假設(shè)τ＝20％，沒有2-維單元是稠密的，在原始數(shù)據(jù)空間中就沒有聚類。但將數(shù)據(jù)點投影到維salary上，就有三個1維密度單元，其中兩個是相連的，因此，在1維salary子空間上就有兩個聚類：C’＝5≤salary<7及D’＝2≤salary<3.由于在age子空間中沒有密度單元，故在該子空間中就沒有聚類。例子（二）：圖二：原始數(shù)據(jù)空間的子空間中的聚類在圖二中，假設(shè)56CLIQUE算法由以下幾部分組成：1）含有聚類子空間的識別。2）聚類的識別。3）對聚類產(chǎn)生最小的描述。CLIQUE算法由以下幾部分組成：www.wondersha57含有聚類子空間的識別自下而上算法定理（單調(diào)性）若在k維數(shù)據(jù)空間的點集S是一個聚類，則S也是在這個數(shù)據(jù)空間的任意（k-1）維投影中一個聚類的一部分。該算法利用聚類針對維度的單調(diào)性的準(zhǔn)則減少搜索空間含有聚類子空間的識別自下而上算法www.wondershar58算法步驟1.遍歷一遍數(shù)據(jù)庫確定1維的密度單元，即將n維數(shù)據(jù)空間劃分為不重疊的矩形單元。2.利用單調(diào)性定理：在確定了k-1維密度單元之后，確定候選的k維密度單元3.直到不再有候選單元產(chǎn)生，算法結(jié)束算法步驟1.遍歷一遍數(shù)據(jù)庫確定1維的密度單元，即將n維數(shù)據(jù)空59聚類的識別輸入：密度單元的集合D輸出：D的劃分問題就變成在下面定義的圖中發(fā)現(xiàn)連通圖：圖的頂點對應(yīng)著密度單元，當(dāng)且僅當(dāng)兩個密度單元有公共面時對應(yīng)的頂點之間有一條邊利用度優(yōu)先深搜索算法發(fā)現(xiàn)圖中的連通圖，即從D中的某個密度單元u開始，將第一個聚類的編號賦予給該單元，再去發(fā)現(xiàn)與它相連的單元，之后，若在圖中還存在沒有被訪問的單元，重復(fù)此過程。聚類的識別輸入：密度單元的集合Dwww.wondershar60生成最小的聚類描述步驟：1、使用貪心算法由若干最大矩形來覆蓋聚類即對每個聚類，確定覆蓋連接密集單元聚類的最大區(qū)域。2、去掉多余的矩形從而產(chǎn)生最小的覆蓋生成最小的聚類描述步驟：www.wondershare.co61貪心增長算法從任意的一個密度單元u1開始用貪心法尋找覆蓋u1的最大區(qū)域R1，將R1加到R中找另一個單元u2，但在R中沒有任何最大區(qū)域覆蓋u2，找出其最大區(qū)域R2直到任何單元都有R中的某個最大區(qū)域所覆蓋。為了得到覆蓋密度單元的一個最大區(qū)域，從u開始沿著維a1，從單元的兩個方向增長，通過使用包含在C中相連的密度單元，增長u，得到一個矩形區(qū)域。再沿著維a2增長此區(qū)域，得到一個盡可能較大的矩形區(qū)域。沿著所有的維重復(fù)此過程，就產(chǎn)生覆蓋u的最大區(qū)域。貪心增長算法從任意的一個密度單元u1開始www.wonder6263最小覆蓋從覆蓋中移走最小的大區(qū)域，該大區(qū)域是冗余的，即其中的每個單元都包含在其他的大區(qū)域中。重復(fù)上述過程，直到在沒有可移走的大區(qū)域為止。最小覆蓋從覆蓋中移走最小的大區(qū)域，該大區(qū)域是冗余的，即其中的64CLIQUE的有效性

CLIQUE自動地發(fā)現(xiàn)最高維的子空間，高密度聚類存在于這些子空間中。

CLIQUE對元組的輸入順序不敏感，無需假設(shè)任何規(guī)范的數(shù)據(jù)分布。

CLIQUE隨輸入數(shù)據(jù)的大小線性地擴(kuò)展，當(dāng)數(shù)據(jù)的維數(shù)增加時具有良好的可伸縮性。但是，由于方法大大簡化，聚類的精確性可能會降低。CLIQUE的有效性CLIQUE自動地發(fā)現(xiàn)最高維的子空間65聚類分析宋宜飛聚類分析宋宜飛66主要內(nèi)容回顧密度聚類方法

DBSCAN算法OPTICS算法網(wǎng)格聚類方法

CLIQUE算法主要內(nèi)容回顧67回顧聚類聚類(clustering)也稱為聚類分析,指將樣本分到不同的組中使得同一組中的樣本差異盡可能的小，而不同組中的樣本差異盡可能的大。聚類得到的不同的組稱為簇(cluster)。一個好的聚類方法將產(chǎn)生以下的聚類最大化類中的相似性最小化類間的相似性回顧聚類68回顧聚類的分類：

劃分聚類方法層次聚類方法

密度聚類方法網(wǎng)格聚類方法

模型聚類方法回顧聚類的分類：69在基于劃分的聚類中，任務(wù)就是將數(shù)據(jù)劃分成K個不相交的點集，使每個子集中的點盡可能同質(zhì)?；趧澐值姆椒?，其代表算法有k-means算法、K-medoids等劃分聚類方法在基于劃分的聚類中，任務(wù)就是將數(shù)據(jù)劃分成K個不相交的點集，使70k-means算法k-means算法基本步驟從n個數(shù)據(jù)對象任意選擇k個對象作為初始聚類中心；根據(jù)每個聚類對象的均值(中心對象)，計算每個對象與這些中心對象的距離；并根據(jù)最小距離重新對相應(yīng)對象進(jìn)行劃分；重新計算每個(有變化)聚類的均值(中心對象)；計算標(biāo)準(zhǔn)測度函數(shù)，當(dāng)滿足一定條件，如函數(shù)收斂時，則算法終止；如果條件不滿足則回到步驟2。k-means算法k-means算法基本步驟www.wo71k-means優(yōu)缺點主要優(yōu)點：是解決聚類問題的一種經(jīng)典算法，簡單、快速。對處理大數(shù)據(jù)集，該算法是相對可伸縮和高效率的。當(dāng)結(jié)果簇是密集的，它的效果較好。主要缺點在簇的平均值被定義的情況下才能使用。必須事先給出k（要生成的簇的數(shù)目），而且對初值敏感，對于不同的初始值，可能會導(dǎo)致不同結(jié)果。不適合于發(fā)現(xiàn)非凸面形狀的簇或者大小差別很大的簇。而且，它對于“躁聲”和孤立點數(shù)據(jù)是敏感的。k-means優(yōu)缺點主要優(yōu)點：www.wondershare72層次聚類方法層次聚類方法對給定的數(shù)據(jù)集進(jìn)行層次的分解，直到某種條件滿足為止。具體又可分為：

凝聚的層次聚類：一種自底向上的策略，首先將每個對象作為一個簇，然后合并這些原子簇為越來越大的簇，直到某個終結(jié)條件被滿足。

分裂的層次聚類：采用自頂向下的策略，它首先將所有對象置于一個簇中，然后逐漸細(xì)分為越來越小的簇，直到達(dá)到了某個終結(jié)條件。層次凝聚的代表是AGNES算法。層次分裂的代表是DIANA算法。層次聚類方法層次聚類方法對給定的數(shù)據(jù)集進(jìn)行層次的分解，直到某73層次聚類優(yōu)缺點層次聚類方法是不可逆的，也就是說，當(dāng)通過凝聚式的方法將兩組合并后，無法通過分裂式的辦法再將其分離到之前的狀態(tài)，反之亦然。另外，層次聚類過程中調(diào)查者必須決定聚類在什么時候停止，以得到某個數(shù)量的分類。在不必要的情況下應(yīng)該小心使用層次聚類方法。層次聚類優(yōu)缺點層次聚類方法是不可逆的，也就是說，當(dāng)通過凝聚式74劃分聚類方法層次聚類方法

密度聚類方法：基于密度的聚類方法以數(shù)據(jù)集在空間分布上的稠密程度為依據(jù)進(jìn)行聚類，無需預(yù)先設(shè)定簇的數(shù)量，因此特別適合對于未知內(nèi)容的數(shù)據(jù)集進(jìn)行聚類。網(wǎng)格聚類方法

模型聚類方法密度聚類方法密度聚類方法75基于密度方法的聚類密度聚類方法的指導(dǎo)思想是，只要一個區(qū)域中的點的密度大于某個域值，就把它加到與之相近的聚類中去。對于簇中每個對象，在給定的半徑ε的鄰域中至少要包含最小數(shù)數(shù)目（MinPts）個對象。這類算法能克服基于距離的算法只能發(fā)現(xiàn)“類圓形”的聚類的缺點，可發(fā)現(xiàn)任意形狀的聚類，且對噪聲數(shù)據(jù)不敏感。代表算法有：DBSCAN、OPTICS、DENCLUE算法等。基于密度方法的聚類密度聚類方法的指導(dǎo)思想是，只要一個區(qū)域中的76基于密度方法的聚類-DBSCANDBSCAN（Density-BasedSpatialClusteringofApplicationswithNoise）一個比較有代表性的基于密度的聚類算法。與層次聚類方法不同，它將簇定義為密度相連的點的最大集合，能夠把具有足夠高密度的區(qū)域劃分為簇，并可在有“噪聲”的空間數(shù)據(jù)庫中發(fā)現(xiàn)任意形狀的聚類。基于密度方法的聚類-DBSCANDBSCAN（Densit77傳統(tǒng)基于中心的密度定義為：數(shù)據(jù)集中特定點的密度通過該點ε半徑之內(nèi)的點計數(shù)(包括本身)來估計。顯然，密度依賴于半徑。傳統(tǒng)的密度定義：基于中心的方法傳統(tǒng)基于中心的密度定義為：傳統(tǒng)的密度定義：基于中心的方法ww78基于密度方法的聚類-DBSCAN所用到的基本術(shù)語定義對象的ε-鄰域：給定對象在半徑ε內(nèi)的區(qū)域。定義核心對象：如果一個對象的ε-鄰域至少包含最小數(shù)目MinPts個對象，則稱該對象為核心對象。

例下圖中，ε=1cm，MinPts=5，q是一個核心對象。定義直接密度可達(dá)：給定一個對象集合D，如果p是在q的ε-鄰域內(nèi)，而

q是一個核心對象，我們說對象p從對象q出發(fā)是直接密度可達(dá)的。

例在下圖中，ε=1cm，MinPts=5，q是一個核心對象，對象

p1從對象q出發(fā)是直接密度可達(dá)的?；诿芏确椒ǖ木垲?DBSCAN所用到的基本術(shù)語www.79基于密度方法的聚類-DBSCAN所用到的基本術(shù)語密度可達(dá)定義密度可達(dá)的：如果存在一個對象鏈p1，p2，…，pn，p1=q，

pn=p，對pi∈D，（1<=i<=n），pi+1是從pi關(guān)于ε和MitPts直接密度可達(dá)的，則對象p是從對象q關(guān)于ε和MinPts密度可達(dá)的。例在下圖中，ε=1cm，MinPts=5，q是一個核心對象，p1是從q關(guān)于ε和MitPts直接密度可達(dá)，p是從p1關(guān)于ε和MitPts直接密度可達(dá)，則對象p從對象q關(guān)于ε和MinPts密度可達(dá)的基于密度方法的聚類-DBSCAN所用到的基本術(shù)語密度可達(dá)80基于密度方法的聚類-DBSCAN所用到的基本術(shù)語圖密度相連圖噪聲定義噪聲:一個基于密度的簇是基于密度可達(dá)性的最大的密度相連對象的集合。不包含在任何簇中的對象被認(rèn)為是“噪聲”。邊界點：邊界點不是核心點，但落在某個核心點的鄰域內(nèi)。噪聲就是那些既不是邊界點也不是核心點的對象定義

密度相連的：如果對象集合D中存在一個對象o，使得對象p

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

ε和MinPts密度相連的?；诿芏确椒ǖ木垲?DBSCAN所用到的基本術(shù)語圖密81DBSCAN算法概念示例如圖所示，ε

用一個相應(yīng)的半徑表示，設(shè)MinPts=3，請分析Q,M,P,S,O,R這5個樣本點之間的關(guān)系?！爸苯用芏瓤蛇_(dá)”和“密度可達(dá)”概念示意描述解答：根據(jù)以上概念知道：由于有標(biāo)記的各點-M、P、O和R的ε

近鄰均包含3個以上的點，因此它們都是核對象；M-是從P“直接密度可達(dá)”；而Q則是從-M“直接密度可達(dá)”；基于上述結(jié)果，Q是從P“密度可達(dá)”；但P從Q無法“密度可達(dá)”(非對稱)。類似地，S和R從O是“密度可達(dá)”的；O、R和S均是“密度相連”的。DBSCAN算法概念示例如圖所示，ε用一個相應(yīng)的半徑表示82基于密度方法的聚類-DBSCANDBSCAN算法根據(jù)以上的定義在數(shù)據(jù)庫中發(fā)現(xiàn)簇和噪聲。簇可等價于集合D中，這個簇核心對象密度可達(dá)的所有對象的集合。DBSCAN通過檢查數(shù)據(jù)集中每個對象的ε-鄰域來尋找聚類。如果一個點p的ε-鄰域包含多于MinPts個對象，則創(chuàng)建一個p作為核心對象的新簇C。然后，DBSCAN從C中尋找未被處理對象q的ε-鄰域，如果q的ε-鄰域包含多MinPts個對象，則還未包含在C中的q的鄰點被加入到簇中，并且這些點的ε-鄰域?qū)⒃谙乱徊街羞M(jìn)行檢測。這個過程反復(fù)執(zhí)行，當(dāng)沒有新的點可以被添加到任何簇時，該過程結(jié)束。具體如下：基于密度方法的聚類-DBSCANDBSCAN算法根據(jù)以上83基于密度方法的聚類-DBSCANDBSCAN算法描述：輸入：包含n個對象的數(shù)據(jù)庫，半徑ε，最少數(shù)目MinPts。輸出：所有生成的簇，達(dá)到密度要求。1.REPEAT2.從數(shù)據(jù)庫中抽取一個未處理過的點；3.IF抽出的點是核心點THEN找出所有從該點密度可達(dá)的對象，形成一個簇4.ELSE抽出的點是邊緣點(非核心對象)，跳出本次循環(huán)，尋找下一點；5.UNTIL所有點都被處理；基于密度方法的聚類-DBSCANDBSCAN算法描述：ww84DBSCAN算法步驟

輸入：數(shù)據(jù)集D，參數(shù)MinPts,ε輸出：簇集合(1)首先將數(shù)據(jù)集D中的所有對象標(biāo)記unvisited；(2)do(3)從D中隨機(jī)選取一個unvisited對象p，并將p標(biāo)記為visited；ifp的ε鄰域包含的對象數(shù)至少為MinPts個創(chuàng)建新簇C，并把p添加到c中；令N為p的ε鄰域中對象的集合；(7)forN中每個點piifpi是unvisited標(biāo)記pi為visited；ifpi的ε鄰域至少有MinPts個對象，把這些對象添加到N；ifpi還不是任何簇的對象。將pi添加到簇C中；(12)endfor(13)輸出C(14)Else標(biāo)記p為噪聲(15)Untill沒有標(biāo)記為unvisited的對象DBSCAN算法步驟輸入：數(shù)據(jù)集D，參數(shù)MinPts,ε85基于密度方法的聚類-DBSCAN

下面給出一個樣本事務(wù)數(shù)據(jù)庫（見下表），對它實施DBSCAN算法。根據(jù)所給的數(shù)據(jù)通過對其進(jìn)行DBSCAN算法，以下為算法的步驟（設(shè)n=12，用戶輸入ε=1，MinPts=4）

序號屬性1屬性2121251312422532642752862913102311531224樣本事務(wù)數(shù)據(jù)庫基于密度方法的聚類-DBSCAN下面給出一個樣本事務(wù)86DBSCAN聚類過程第1步，在數(shù)據(jù)庫中選擇一點1，由于在以它為圓心的，以1為半徑的圓內(nèi)包含2個點（小于4），因此它不是核心點，選擇下一個點。第2步，在數(shù)據(jù)庫中選擇一點2，由于在以它為圓心的，以1為半徑的圓內(nèi)包含2個點，因此它不是核心點，選擇下一個點。第3步，在數(shù)據(jù)庫中選擇一點3，由于在以它為圓心的，以1為半徑的圓內(nèi)包含3個點，因此它不是核心點，選擇下一個點。DBSCAN聚類過程第1步，在數(shù)據(jù)庫中選擇一點1，由于在以它87DBSCAN聚類過程第4步，在數(shù)據(jù)庫中選擇一點4，由于在以它為圓心的，以1為半徑的圓內(nèi)包含5個點，因此它是核心點，尋找從它出發(fā)可達(dá)的點（直接可達(dá)4個，間接可達(dá)3個），聚出的新類{1，3，4，5，9，10，12}，選擇下一個點。DBSCAN聚類過程第4步，在數(shù)據(jù)庫中選擇一點4，由于在以它88DBSCAN聚類過程第5步，在數(shù)據(jù)庫中選擇一點5，已經(jīng)在簇1中，選擇下一個點。第6步，在數(shù)據(jù)庫中選擇一點6，由于在以它為圓心的，以1為半徑的圓內(nèi)包含3個點，因此它不是核心點，選擇下一個點。DBSCAN聚類過程第5步，在數(shù)據(jù)庫中選擇一點5，已經(jīng)在簇189DBSCAN聚類過程第7步，在數(shù)據(jù)庫中選擇一點7，由于在以它為圓心的，以1為半徑的圓內(nèi)包含5個點，因此它是核心點，尋找從它出發(fā)可達(dá)的點，聚出的新類{2，6，7，8，11}，選擇下一個點。DBSCAN聚類過程第7步，在數(shù)據(jù)庫中選擇一點7，由于在以它90DBSCAN聚類過程第8步，在數(shù)據(jù)庫中選擇一點8，已經(jīng)在簇2中，選擇下一個點。第9步，在數(shù)據(jù)庫中選擇一點9，已經(jīng)在簇1中，選擇下一個點。第10步，在數(shù)據(jù)庫中選擇一點10，已經(jīng)在簇1中，選擇下一個點。第11步，在數(shù)據(jù)庫中選擇一點11，已經(jīng)在簇2中，選擇下一個點。第12步，選擇12點，已經(jīng)在簇1中，由于這已經(jīng)是最后一點所有點都以處理，程序終止。DBSCAN聚類過程第8步，在數(shù)據(jù)庫中選擇一點8，已經(jīng)在簇291基于密度方法的聚類-DBSCAN步驟選擇的點在ε中點的個數(shù)通過計算可達(dá)點而找到的新簇112無222無333無445簇C1：{1，3，4，5，9，10，12}553已在一個簇C1中663無775簇C2：{2，6，7，8，11}882已在一個簇C2中993已在一個簇C1中10104已在一個簇C1中，11112已在一個簇C2中12122已在一個簇C1中算法執(zhí)行過程：基于密度方法的聚類-DBSCAN步驟選擇的點在ε中點的個數(shù)92DBSCAN的時間復(fù)雜性時間復(fù)雜度DBSCAN算法要對每個數(shù)據(jù)對象進(jìn)行鄰域檢查時間性能較低。DBSCAN的基本時間復(fù)雜度是O(N*找出Eps領(lǐng)域中的點所需要的時間),N是點的個數(shù)。最壞情況下時間復(fù)雜度是O(N2)在低維空間數(shù)據(jù)中,有一些數(shù)據(jù)結(jié)構(gòu)如KD樹，使得可以有效的檢索特定點給定距離內(nèi)的所有點，時間復(fù)雜度可以降低到O(NlogN)DBSCAN的時間復(fù)雜性時間復(fù)雜度www.wondersha93DBSCAM的空間復(fù)雜性空間復(fù)雜度

在聚類過程中，DBSCAN一旦找到一個核心對象，即以該核心對象為中心向外擴(kuò)展．此過程中核心對象將不斷增多，未處理的對象被保留在內(nèi)存中．若數(shù)據(jù)庫中存在龐大的聚類，將需要很大的存來存儲核心對象信息，其需求難以預(yù)料．當(dāng)數(shù)據(jù)量增大時，要求較大的內(nèi)存支持I/0消耗也很大;

低維或高維數(shù)據(jù)中，其空間都是O(N)DBSCAM的空間復(fù)雜性空間復(fù)雜度www.wondersha94基于密度方法的聚類優(yōu)點能克服基于距離的算法只能發(fā)現(xiàn)“類圓形”的聚類的缺點，可發(fā)現(xiàn)任意形狀的聚類，有效地處理數(shù)據(jù)集中的噪聲數(shù)據(jù)，數(shù)據(jù)輸入順序不敏感缺點輸入?yún)?shù)敏感．確定參數(shù)ε，MinPts困難，若選取不當(dāng)，將造成聚類質(zhì)量下降．由于在DBSCAN算法中，變量ε，MinPts是全局惟一的，當(dāng)空間聚類的密度不均勻、聚類間距離相差很大時，聚類質(zhì)量較差。計算密度單元的計算復(fù)雜度大，需要建立空間索引來降低計算量，且對數(shù)據(jù)維數(shù)的伸縮性較差。這類方法需要掃描整個數(shù)據(jù)庫，每個數(shù)據(jù)對象都可能引起一次查詢，因此當(dāng)數(shù)據(jù)量大時會造成頻繁的I/O操作。?；诿芏确椒ǖ木垲悆?yōu)點95OPTICS算法

由于在DBSCAN算法中，變量ε，MinPts是全局惟一的，當(dāng)空間聚類的密度不均勻、聚類間距離相差很大時，聚類質(zhì)量較差。許多現(xiàn)實的數(shù)據(jù)集內(nèi)在的聚類結(jié)構(gòu)不能夠通過全局的密度參數(shù)來描述，數(shù)據(jù)空間中不同區(qū)域的聚類需要不同的局部密度。OPTICS算法由于在DBSCAN算法中，變量96OPTICS算法盡管dbscan能夠根據(jù)給定的輸入?yún)?shù)ε，和MinPts聚類對象，但是它把選擇能產(chǎn)生可接受的聚類結(jié)果的參數(shù)值的責(zé)任留給了用戶。這是許多其他算法都存在的問題。但是對于高維數(shù)據(jù)而言設(shè)定準(zhǔn)確的參數(shù)非常困難。參數(shù)設(shè)置有細(xì)微的不同都可能導(dǎo)致差別很大的聚類結(jié)果。全局參數(shù)不能很好地刻畫其內(nèi)在的聚類結(jié)構(gòu)。OPTICS算法盡管dbscan能夠根據(jù)給定的輸入?yún)?shù)ε，97OPTICS算法下圖中所描述的數(shù)據(jù)集不能通過一個全局密度參數(shù)同時區(qū)分出簇A、B、C、C1、C2和C3，只能得到A、B、C或C1、C2和C3，對于C1、C2和C3而言A、B、C都是噪聲。對于固定的MinPts值，和兩個ε1＜

ε2，關(guān)于ε1的MinPts簇C一定是關(guān)于ε2和MinPts簇C’的子集，這就意味著。如果兩個對象在同一個基于密度的簇中，則它們也是在同一個具有較低密度要求的簇中。OPTICS算法下圖中所描述的數(shù)據(jù)集不能通過一個98OPTICS算法為了克服在聚類分析中使用一組全局參數(shù)的缺點，提出了OPTICS聚類分析方法。P為對象，數(shù)據(jù)集D，為距離值，N(q)為鄰域，MinPts

。兩個定義：

P的核心距離：使得P成為核心對象的最小‘，‘是使p稱為核心對象的最小半徑閾值。若|（N(q)MinPts，即P不是核心對象，核心距離則無定義。q關(guān)于對象P的可達(dá)距離：是使q從p密度可達(dá)的最小半徑。p的核心距離和p,q的歐幾里得距離之間的較大值，p必須是核心對象且q在p的鄰域內(nèi)。若|N(p)|MinPts，即P不是核心對象，則無定義否則，定義為Max（核心距離，|（p,q）|）OPTICS算法為了克服在聚類分析中使用一組全局參數(shù)的缺點99OPTICS算法例核心距離與可達(dá)距離,假設(shè)

=6mm，MinPts=5。P的核心距離是p于第四個最近的數(shù)據(jù)對象之間的距離‘，q1到p的可達(dá)距離是p的核心距離（‘=3mm），因為它比q1到p的歐氏距離大。q2關(guān)于p的科大距離是p到q2的歐氏距離，它大于p的核心距離。OPTICS算法例核心距100OPTICS算法OPTICS算法并不顯式的產(chǎn)生數(shù)據(jù)及聚類，而是輸出簇排序（clusterordering），這個排序是所有分析對象的線性表，并且代表數(shù)據(jù)基于密度的聚類結(jié)構(gòu)。較稠密簇中的對象在簇排序中相互靠近。這個排序等價于從較廣泛的參數(shù)設(shè)置中得到基于密度的聚類。這樣optics不需要用戶提供特定密度閾值。簇排列可以用來提取基本聚類信息，導(dǎo)出內(nèi)在的聚類結(jié)構(gòu)，也可以提供聚類的可視化。OPTICS算法OPTICS算法并不顯式的產(chǎn)生數(shù)據(jù)及聚類101OPTICS算法為了構(gòu)造不同的類，對象需要按特定的次序處理，這個次序選擇這樣的對象，及關(guān)于最小的值，它是密度可達(dá)的，以便較高密度（較低值）的簇先完成。optics算法計算給定數(shù)據(jù)庫中所有對象的排序，并且存儲每個對象核心距離和相應(yīng)的可達(dá)距離。optics維護(hù)一個稱作orderseeds的表來來產(chǎn)生輸出排列，orderseeds中的對象按到各自的最近核心對象的可達(dá)距離排序，及按每個對象的最小可達(dá)距離排序。OPTICS算法為了構(gòu)造不同的類，對象需要按特定的次序處理102OPTICS算法OPTICS算法103尋找簇Reachability-distanceundefined‘Cluster-orderoftheobjects尋找簇Reachability-distanceundefi104數(shù)據(jù)集的簇排序可以用圖形描述，這有助于可視化和理解數(shù)據(jù)集中聚類結(jié)構(gòu)。例如下圖是一個簡單的二維數(shù)據(jù)集的可達(dá)性圖。可達(dá)距離未定義’數(shù)據(jù)集的簇排序可以用圖形描述，這有助于可視化和理解數(shù)據(jù)集中聚105OPTICS算法并不直接尋找各個簇,而是將基于密度查找簇所需要的信息記錄下來,這些信息反映了數(shù)據(jù)空間基于密度的簇結(jié)構(gòu)。同時從這些密度信息可以直接發(fā)現(xiàn)各個簇。OPTICS采取了兩個方法來達(dá)到目標(biāo)1)定義了對象的核心距離和可達(dá)距離,以反映對象附近的密度大小;2)在迭代查找可達(dá)對象時,對種子對象依可達(dá)距離進(jìn)行排序,從而在簇擴(kuò)展時優(yōu)先擴(kuò)展密度值較大區(qū)域的點。這樣,OPTICS算法實現(xiàn)了數(shù)據(jù)庫所有對象的排序,這一對象序列就可以反映出數(shù)據(jù)空間基于密度的簇結(jié)構(gòu)信息?；谶@些信息可以容易地確定合適的ε值,并隨之發(fā)現(xiàn)各個簇。另外,OPTICS還提供了自動的簇發(fā)現(xiàn)方法。OPTICS算法較好地解決了DBSCAN算法的對輸入?yún)?shù)ε敏感的問題,但是由于采用了復(fù)雜的處理方法以及額外的磁盤IPO操作,使得OPTICS實際運(yùn)行的速度遠(yuǎn)遠(yuǎn)低于DBSCAN。OPTICS算法并不直接尋找各個簇www.wondersha106107108109不同密度、形狀、大小的簇不同密度、形狀、大小的簇www.wondershare.co110參數(shù)的影響減小，則可達(dá)距離為無窮大的點增多；

MinPts減小，核心對象增多，圖象更尖銳參數(shù)的影響減小，則可達(dá)距離為無窮大的點增多；www.won111

基于網(wǎng)格的方法（Grid-BasedMethods）

聚類高維數(shù)據(jù)是聚類分析中一個非常重要的任務(wù)，而一般聚類方法無法處理這些數(shù)據(jù)。用戶感興趣的通常是某個高維數(shù)據(jù)空間的若干個子空間，對該空間內(nèi)數(shù)據(jù)點的聚類要比原始空間更好一些。高維數(shù)據(jù)中，通常只有少數(shù)幾維與某些簇相關(guān)，其他不相關(guān)的維數(shù)據(jù)可能會產(chǎn)生大量的噪聲而屏蔽真實的簇。

為聚類高維數(shù)據(jù)集便提出了基于網(wǎng)格的方法的聚類?；诰W(wǎng)格的方法（Grid-BasedMethods）ww112

基于網(wǎng)格的方法（Grid-BasedMethods）

將數(shù)據(jù)空間劃分成為有限個單元（cell）的網(wǎng)格結(jié)構(gòu)，所有的處理都是以單個單元為對象的。這種方法的主要優(yōu)點是它的處理速度很快，處理時間獨立于數(shù)據(jù)對象的數(shù)目，只與每一維所劃分的單元數(shù)目有關(guān)代表算法有：CLIQUE算法?；诰W(wǎng)格的方法（Grid-BasedMethods）113CLQUE是一個綜合了基于密度和基于網(wǎng)格方法的聚類算法，對于大型數(shù)據(jù)庫中的高維數(shù)據(jù)的聚類比較有效,在高維數(shù)據(jù)的子空間中識別稠密的聚類，所產(chǎn)生的理解結(jié)果與所給的輸入數(shù)據(jù)無關(guān)。CLIQUE：高維度數(shù)據(jù)的自動子空間聚類算法CLQUE是一個綜合了基于密度和基于網(wǎng)格方法的聚類算法，對于114CLIQUE：聚類高維空間CLIQUE的中心思想如下：給定一個多維數(shù)據(jù)點的大集合，數(shù)據(jù)點在數(shù)據(jù)空間中通常不是均衡分布的。CLIQUE區(qū)分空間中稀疏的和“擁擠的”區(qū)域，以發(fā)現(xiàn)數(shù)據(jù)集合全局分布模式。

將數(shù)據(jù)空間中的每個維劃分成等長且數(shù)量相等的間隔段，即單元。如果一個單元中的包含數(shù)據(jù)點超過了某個輸入模型參數(shù)，則該單元是密集的。在CLIQUE中，一個聚類被定義為相連的密集單元的最大集合。CLIQUE：聚類高維空間CLIQUE的中心思想如下：www115問題描述

要能自動地識別一個高維數(shù)據(jù)的子空間限制在只對原始空間的子空間的搜索而不是使用一個新的維度為了識別數(shù)據(jù)點的密度，將數(shù)據(jù)空間劃分并找出在每個單元中數(shù)據(jù)點的數(shù)量。聚類是子空間中相連的高密度單元的并集，即將聚類映射到軸對稱的超矩形中。問題描述要能自動地識別一個高維數(shù)據(jù)的子空間www.wond116聚類在空間中的描述設(shè)A＝{A1,A2,…,Ad}是一個有界的、全部有序的域的集合。而S＝A1×A2×…×Ad是一個d維的數(shù)字空間，A1，A2，…，Ad定義為S的維。輸入是由d