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

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

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

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

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

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

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

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

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

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

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

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

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

例在下圖中，ε=1cm，MinPts=5，q是一個(gè)核心對(duì)象，對(duì)象

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

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

密度相連的：如果對(duì)象集合D中存在一個(gè)對(duì)象o，使得對(duì)象p

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

ε和MinPts密度相連的。基于密度方法的聚類-DBSCAN所用到的基本術(shù)語(yǔ)圖密16DBSCAN算法概念示例如圖所示，ε

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

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

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

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

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

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

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

由于在DBSCAN算法中，變量ε，MinPts是全局惟一的，當(dāng)空間聚類的密度不均勻、聚類間距離相差很大時(shí)，聚類質(zhì)量較差。許多現(xiàn)實(shí)的數(shù)據(jù)集內(nèi)在的聚類結(jié)構(gòu)不能夠通過(guò)全局的密度參數(shù)來(lái)描述，數(shù)據(jù)空間中不同區(qū)域的聚類需要不同的局部密度。OPTICS算法由于在DBSCAN算法中，變量31OPTICS算法盡管dbscan能夠根據(jù)給定的輸入?yún)?shù)ε，和MinPts聚類對(duì)象，但是它把選擇能產(chǎn)生可接受的聚類結(jié)果的參數(shù)值的責(zé)任留給了用戶。這是許多其他算法都存在的問(wèn)題。但是對(duì)于高維數(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ù)集不能通過(guò)一個(gè)全局密度參數(shù)同時(shí)區(qū)分出簇A、B、C、C1、C2和C3，只能得到A、B、C或C1、C2和C3，對(duì)于C1、C2和C3而言A、B、C都是噪聲。對(duì)于固定的MinPts值，和兩個(gè)ε1＜

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

。兩個(gè)定義：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

例在下圖中，ε=1cm，MinPts=5，q是一個(gè)核心對(duì)象，對(duì)象

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

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

密度相連的：如果對(duì)象集合D中存在一個(gè)對(duì)象o，使得對(duì)象p

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

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

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

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

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

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

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

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

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

由于在DBSCAN算法中，變量ε，MinPts是全局惟一的，當(dāng)空間聚類的密度不均勻、聚類間距離相差很大時(shí)，聚類質(zhì)量較差。許多現(xiàn)實(shí)的數(shù)據(jù)集內(nèi)在的聚類結(jié)構(gòu)不能夠通過(guò)全局的密度參數(shù)來(lái)描述，數(shù)據(jù)空間中不同區(qū)域的聚類需要不同的局部密度。OPTICS算法由于在DBSCAN算法中，變量96OPTICS算法盡管dbscan能夠根據(jù)給定的輸入?yún)?shù)ε，和MinPts聚類對(duì)象，但是它把選擇能產(chǎn)生可接受的聚類結(jié)果的參數(shù)值的責(zé)任留給了用戶。這是許多其他算法都存在的問(wèn)題。但是對(duì)于高維數(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ù)集不能通過(guò)一個(gè)全局密度參數(shù)同時(shí)區(qū)分出簇A、B、C、C1、C2和C3，只能得到A、B、C或C1、C2和C3，對(duì)于C1、C2和C3而言A、B、C都是噪聲。對(duì)于固定的MinPts值，和兩個(gè)ε1＜

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

。兩個(gè)定義：

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

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

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

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

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

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

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

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

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

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