基于密度方法的聚類

1、聚 類 分 析宋宜飛主要內(nèi)容 回顧回顧 密度聚類方法密度聚類方法 DBSCAN算法 OPTICS 算法 網(wǎng)格聚類方法網(wǎng)格聚類方法 CLIQUE算法回顧回顧聚類 聚類(clustering)也稱為聚類分析,指將樣本分到不同的組中使得同一組中的樣本差異盡可能的小，而不同組中的樣本差異盡可能的大。聚類得到的不同的組稱為簇(cluster)。一個(gè)好的聚類方法將產(chǎn)生以下的聚類 最大化類中的相似性 最小化類間的相似性回顧聚類的分類： 劃分聚類方法劃分聚類方法 層次聚類方法層次聚類方法 密度聚類方法密度聚類方法 網(wǎng)格聚類方法網(wǎng)格聚類方法 模型聚類方法模型聚類方法在基于劃分的聚類中，任務(wù)就是將數(shù)據(jù)劃分成K個(gè)不

2、相交的點(diǎn)集，使每個(gè)子集中的點(diǎn)盡可能同質(zhì)?；趧澐值姆椒?，其代表算法有 k-means算法、 K-medoids等劃分聚類方法k-means k-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ì)象)； 1. 計(jì)算標(biāo)準(zhǔn)測(cè)度函數(shù)，當(dāng)滿足一定條件，如函數(shù)收斂時(shí)，則算法終止；如果條件不滿足則回到步驟2。k-means優(yōu)缺點(diǎn) 主要優(yōu)點(diǎn)：是解決聚類問題的一種經(jīng)典算法，簡(jiǎn)單、快速。對(duì)處理大數(shù)據(jù)集，該算

3、法是相對(duì)可伸縮和高效率的。當(dāng)結(jié)果簇是密集的，它的效果較好。 主要缺點(diǎn)在簇的平均值被定義的情況下才能使用。必須事先給出k（要生成的簇的數(shù)目），而且對(duì)初值敏感，對(duì)于不同的初始值，可能會(huì)導(dǎo)致不同結(jié)果。不適合于發(fā)現(xiàn)非凸面形狀的簇或者大小差別很大的簇。而且，它對(duì)于“躁聲”和孤立點(diǎn)數(shù)據(jù)是敏感的。層次聚類方法層次聚類方法 層次聚類方法對(duì)給定的數(shù)據(jù)集進(jìn)行層次的分解，直到某種條件滿足為止。具體又可分為： 凝聚的層次聚類：一種自底向上的策略，首先將每個(gè)對(duì)象作為一個(gè)簇，然后合并這些原子簇為越來越大的簇，直到某個(gè)終結(jié)條件被滿足。 分裂的層次聚類：采用自頂向下的策略，它首先將所有對(duì)象置于一個(gè)簇中，然后逐漸細(xì)分為越來越小

4、的簇，直到達(dá)到了某個(gè)終結(jié)條件。 層次凝聚的代表是AGNES算法。層次分裂的代表是DIANA算法。層次聚類優(yōu)缺點(diǎn)層次聚類優(yōu)缺點(diǎn) 層次聚類方法是不可逆的，也就是說，當(dāng)通過凝聚式的方法將兩組合并后，無法通過分裂式的辦法再將其分離到之前的狀態(tài)，反之亦然。 另外，層次聚類過程中調(diào)查者必須決定聚類在什么時(shí)候停止，以得到某個(gè)數(shù)量的分類。 在不必要的情況下應(yīng)該小心使用層次聚類方法。劃分聚類方法劃分聚類方法層次聚類方法層次聚類方法 密度聚類方法密度聚類方法 ：基于密度的聚類方法以數(shù)據(jù)集在空間分布上的稠密程度為依據(jù)進(jìn)行聚類，無需預(yù)先設(shè)定簇的數(shù)量，因此特別適合對(duì)于未知內(nèi)容的數(shù)據(jù)集進(jìn)行聚類。網(wǎng)格聚類方法網(wǎng)格聚類方法

5、模型聚類方法模型聚類方法密度聚類方法密度聚類方法基于密度方法的聚類 密度聚類方法的指導(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算法等?；诿芏确椒ǖ木垲? DBSCAN DBSCAN（Density-Based Spatial Clustering of Applications with Noise）一個(gè)比較有代表性的

6、基于密度的聚類算法。與層次聚類方法不同，它將簇定義為密度相連的點(diǎn)的最大集合，能夠把具有足夠高密度的區(qū)域劃分為簇，并可在有“噪聲”的空間數(shù)據(jù)庫中發(fā)現(xiàn)任意形狀的聚類。傳統(tǒng)基于中心的密度定義為：數(shù)據(jù)集中特定點(diǎn)的密度通過該點(diǎn)半徑之內(nèi)的點(diǎn)計(jì)數(shù)(包括本身)來估計(jì)。顯然，密度依賴于半徑。傳統(tǒng)的密度定義：基于中心的方法基于密度方法的聚類- DBSCAN 所用到的基本術(shù)語定義 對(duì)象的-鄰域：給定對(duì)象在半徑內(nèi)的區(qū)域。定義 核心對(duì)象：如果一個(gè)對(duì)象的-鄰域至少包含最小數(shù)目MinPts個(gè) 對(duì)象，則稱該對(duì)象為核心對(duì)象。 例 下圖中，=1cm，MinPts=5，q是一個(gè)核心對(duì)象。 定義 直接密度可達(dá)：給定一個(gè)對(duì)象集合D，如

7、果p是在q的-鄰域內(nèi)，而 q是一個(gè)核心對(duì)象，我們說對(duì)象p從對(duì)象q出發(fā)是直接密度可達(dá)的。 例 在下圖中，=1cm，MinPts=5 ，q是一個(gè)核心對(duì)象，對(duì)象 p1從對(duì)象q出發(fā)是直接密度可達(dá)的?；诿芏确椒ǖ木垲? DBSCAN 所用到的基本術(shù)語密度可達(dá)定義 密度可達(dá)的：如果存在一個(gè)對(duì)象鏈p1，p2，pn，p1=q， pn=p，對(duì)piD，（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á)，

8、則對(duì)象p從對(duì)象q關(guān)于和MinPts密度可達(dá)的基于密度方法的聚類- DBSCAN 所用到的基本術(shù)語圖 密度相連圖 噪聲定義 噪聲: 一個(gè)基于密度的簇是基于密度可達(dá)性的最大的密度相 連對(duì)象的集合。不包含在任何簇中的對(duì)象被認(rèn)為是“噪聲”。邊界點(diǎn)：邊界點(diǎn)不是核心點(diǎn)，但落在某個(gè)核心點(diǎn)的鄰域內(nèi)。邊界點(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算法概念示例 如圖所示， 用一個(gè)相應(yīng)的半徑表示，設(shè)MinPts=3

9、，請(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無法“密度可達(dá)”(非對(duì)稱)。類似地，S和R從O是“密度可達(dá)”的；O、R和S均是“密度相連”的。基于密度方法的聚類- DBSCAN DBSCAN 算法根據(jù)以上的定義在數(shù)據(jù)庫中發(fā)現(xiàn)簇和噪聲。簇可等價(jià)于集合D中，這個(gè)簇核心對(duì)象密度可達(dá)的所有對(duì)象的集合。 DBSCAN通過檢查數(shù)據(jù)集中每個(gè)對(duì)象的-鄰域來尋找聚

10、類。如果一個(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è)過程反復(fù)執(zhí)行，當(dāng)沒有新的點(diǎn)可以被添加到任何簇時(shí)，該過程結(jié)束。具體如下：基于密度方法的聚類- DBSCANDBSCAN算法描述： 輸入：包含n個(gè)對(duì)象的數(shù)據(jù)庫，半徑，最少數(shù)目MinPts。 輸出：所有生成的簇，達(dá)到密度要求。 1. REPEAT 2. 從數(shù)據(jù)庫中抽取一個(gè)未處理過的點(diǎn)； 3. IF 抽出的點(diǎn)是核心點(diǎn) THEN找出所有從該點(diǎn)密度

11、可達(dá)的對(duì)象，形成一個(gè)簇 4. ELSE 抽出的點(diǎn)是邊緣點(diǎn)(非核心對(duì)象)，跳出本次循環(huán)，尋找下一點(diǎn)； 5. UNTIL 所有點(diǎn)都被處理；DBSCAN算法步驟 輸入：數(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 ； if p的 鄰域 包含的對(duì)象數(shù)至少為MinPts個(gè) 創(chuàng)建新簇C ，并把p添加到c中； 令N為 p的 鄰域 中對(duì)象的集合；(7) for N 中每個(gè)點(diǎn)pi if pi 是unvisited 標(biāo)記pi 為visited； if pi 的 鄰域

12、至少有MinPts個(gè) 對(duì)象，把這些對(duì)象添加到N ； if pi 還不是任何簇的對(duì)象。將 pi 添加到 簇C中 ；(12) end for(13) 輸出C(14) Else 標(biāo)記p 為噪聲(15) Untill 沒有標(biāo)記為unvisited 的對(duì)象基于密度方法的聚類- DBSCAN 下面給出一個(gè)樣本事務(wù)數(shù)據(jù)庫（見下表），對(duì)它實(shí)施DBSCAN算法。 根據(jù)所給的數(shù)據(jù)通過對(duì)其進(jìn)行DBSCAN算法，以下為算法的步驟（設(shè)n=12，用戶輸入=1，MinPts=4） 序號(hào)屬性 1屬性 2121251312422532642752862913102311531224樣本事務(wù)數(shù)據(jù)庫DBSCAN聚類過程 第1步，在

13、數(shù)據(jù)庫中選擇一點(diǎn)1，由于在以它為圓心的，以1為半徑的圓內(nèi)包含2個(gè)點(diǎn)（小于4），因此它不是核心點(diǎn)，選擇下一個(gè)點(diǎn)。 第2步，在數(shù)據(jù)庫中選擇一點(diǎn)2，由于在以它為圓心的，以1為半徑的圓內(nèi)包含2個(gè)點(diǎn)，因此它不是核心點(diǎn)，選擇下一個(gè)點(diǎn)。 第3步，在數(shù)據(jù)庫中選擇一點(diǎn)3，由于在以它為圓心的，以1為半徑的圓內(nèi)包含3個(gè)點(diǎn)，因此它不是核心點(diǎn)，選擇下一個(gè)點(diǎn)。DBSCAN聚類過程 第4步，在數(shù)據(jù)庫中選擇一點(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聚類過程 第5步，在數(shù)據(jù)庫中選

14、擇一點(diǎn)5，已經(jīng)在簇1中，選擇下一個(gè)點(diǎn)。 第6步，在數(shù)據(jù)庫中選擇一點(diǎn)6，由于在以它為圓心的，以1為半徑的圓內(nèi)包含3個(gè)點(diǎn)，因此它不是核心點(diǎn)，選擇下一個(gè)點(diǎn)。DBSCAN聚類過程 第7步，在數(shù)據(jù)庫中選擇一點(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聚類過程 第8步，在數(shù)據(jù)庫中選擇一點(diǎn)8，已經(jīng)在簇2中，選擇下一個(gè)點(diǎn)。 第9步，在數(shù)據(jù)庫中選擇一點(diǎn)9，已經(jīng)在簇1中，選擇下一個(gè)點(diǎn)。 第10步，在數(shù)據(jù)庫中選擇一點(diǎn)10，已經(jīng)在簇1中，選擇下一個(gè)點(diǎn)。 第11步，在數(shù)據(jù)庫中選擇一點(diǎn)11，已經(jīng)在簇2中，選擇下一個(gè)點(diǎn)

15、。 第12步，選擇12點(diǎn)，已經(jīng)在簇1中，由于這已經(jīng)是最后一點(diǎn)所有點(diǎn)都以處理，程序終止?；诿芏确椒ǖ木垲? DBSCAN步驟選擇的點(diǎn)在中點(diǎn)的個(gè)數(shù)通過計(jì)算可達(dá)點(diǎn)而找到的新簇112無222無333無445簇C1：1，3，4，5，9，10，12553已在一個(gè)簇C1中663無775簇C2：2，6，7，8，11882已在一個(gè)簇C2中993已在一個(gè)簇C1中10104已在一個(gè)簇C1中，11112已在一個(gè)簇C2中 12122已在一個(gè)簇C1中算法執(zhí)行過程：DBSCAN的時(shí)間復(fù)雜性 時(shí)間復(fù)雜度DBSCAN算法要對(duì)每個(gè)數(shù)據(jù)對(duì)象進(jìn)行鄰域檢查時(shí)間性能較低。DBSCAN的基本時(shí)間復(fù)雜度是 O(N*找出Eps領(lǐng)域中的點(diǎn)所需

16、要的時(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)DBSCAM的空間復(fù)雜性 空間復(fù)雜度 在聚類過程中，DBSCAN一旦找到一個(gè)核心對(duì)象，即以該核心對(duì)象為中心向外擴(kuò)展此過程中核心對(duì)象將不斷增多，未處理的對(duì)象被保留在內(nèi)存中若數(shù)據(jù)庫中存在龐大的聚類，將需要很大的存來存儲(chǔ)核心對(duì)象信息，其需求難以預(yù)料 當(dāng)數(shù)據(jù)量增大時(shí)，要求較大的內(nèi)存支持 I/0 消耗也很大; 低維或高維數(shù)據(jù)中，其空間都是O(N)基于密度方法的聚類 優(yōu)點(diǎn)能克服基于距離的算法只能發(fā)現(xiàn)“類圓形”的聚類的缺點(diǎn)，可發(fā)

17、現(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ù)雜度大，需要建立空間索引來降低計(jì)算量，且對(duì)數(shù)據(jù)維數(shù)的伸縮性較差。這類方法需要掃描整個(gè)數(shù)據(jù)庫，每個(gè)數(shù)據(jù)對(duì)象都可能引起一次查詢，因此當(dāng)數(shù)據(jù)量大時(shí)會(huì)造成頻繁的I/O操作。OPTICS 算法 由于在DBSCAN算法中，變量，MinPts是全局惟一的， 當(dāng)空間聚類的密度不均勻、聚類間距離相差很大時(shí)，聚類質(zhì)量較差。 許多現(xiàn)實(shí)的

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

19、聲。 對(duì)于固定的MinPts 值，和兩個(gè) 1 2，關(guān)于1的MinPts簇C一定是關(guān)于2和MinPts簇C的子集，這就意味著。如果兩個(gè)對(duì)象在同一個(gè)基于密度的簇中，則它們也是在同一個(gè)具有較低密度要求的簇中。OPTICS 算法 為了克服在聚類分析中使用一組全局參數(shù)的缺點(diǎn)，提出了 OPTICS 聚類分析方法。 P 為對(duì)象，數(shù)據(jù)集D，為距離值，N(q)為鄰域，MinPts 。 兩個(gè)定義： P 的核心距離：使得P成為核心對(duì)象的最小， 是使p 稱為核心對(duì)象的最小半徑閾值。若|（ N(q) MinPts，即P不是核心對(duì)象，核心距離則無定義。 q關(guān)于對(duì)象P的可達(dá)距離：是使 q從p密度可達(dá)的最小半徑。p的核心距離

20、和p,q的歐幾里得距離之間的較大值，p必須是核心對(duì)象且q在p的鄰域內(nèi)。 若|N(p)| MinPts，即P不是核心對(duì)象，則無定義 否則，定義為Max（核心距離，|（p,q）|）OPTICS 算法 例 核心距離與可達(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 算法 OPTICS 算法并不顯式的產(chǎn)生數(shù)據(jù)及聚類，而是輸出簇排序（cluster ordering），這個(gè)排序是所有分析對(duì)象的線性表，并

21、且代表數(shù)據(jù)基于密度的聚類結(jié)構(gòu)。 較稠密簇中的對(duì)象在簇排序中相互靠近。這個(gè)排序等價(jià)于從較廣泛的參數(shù)設(shè)置中得到基于密度的聚類。這樣optics不需要用戶提供特定密度閾值。 簇排列可以用來提取基本聚類信息，導(dǎo)出內(nèi)在的聚類結(jié)構(gòu)，也可以提供聚類的可視化。OPTICS 算法 為了構(gòu)造不同的類，對(duì)象需要按特定的次序處理，這個(gè)次序選擇這樣的對(duì)象，及關(guān)于最小的值，它是密度可達(dá)的，以便較高密度（較低 值）的簇先完成。 optics 算法計(jì)算給定數(shù)據(jù)庫中所有對(duì)象的排序，并且存儲(chǔ)每個(gè)對(duì)象核心距離和相應(yīng)的可達(dá)距離。 optics 維護(hù)一個(gè)稱作order seeds 的表來來產(chǎn)生輸出排列，orderseeds 中的對(duì)象按

22、到各自的最近核心對(duì)象的可達(dá)距離排序，及按每個(gè)對(duì)象的最小可達(dá)距離排序。OPTICS 算法尋找簇Reachability-distanceundefinedCluster-orderof the 數(shù)據(jù)集的簇排序可以用圖形描述，這有助于可視化和理解數(shù)據(jù)集中聚類結(jié)構(gòu)。例如下圖是一個(gè)簡(jiǎn)單的二維數(shù)據(jù)集的可達(dá)性圖?？蛇_(dá)距離可達(dá)距離未定義未定義OPTICS算法并不直接尋找各個(gè)簇,而是將基于密度查找簇所需要的信息記錄下來,這些信息反映了數(shù)據(jù)空間基于密度的簇結(jié)構(gòu)。同時(shí)從這些密度信息可以直接發(fā)現(xiàn)各個(gè)簇。OPTICS采取了兩個(gè)方法來達(dá)到目標(biāo)1)定義了對(duì)象的核心距離和可達(dá)距離,以反映對(duì)象附近的密度大小;2)在迭代查找可

23、達(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ù)庫所有對(duì)象的排序,這一對(duì)象序列就可以反映出數(shù)據(jù)空間基于密度的簇結(jié)構(gòu)信息?；谶@些信息可以容易地確定合適的值,并隨之發(fā)現(xiàn)各個(gè)簇。另外,OPTICS還提供了自動(dòng)的簇發(fā)現(xiàn)方法。OPTICS算法較好地解決了DBSCAN算法的對(duì)輸入?yún)?shù)敏感的問題,但是由于采用了復(fù)雜的處理方法以及額外的磁盤IPO操作,使得OPTICS實(shí)際運(yùn)行的速度遠(yuǎn)遠(yuǎn)低于DBSCAN。不同密度、形狀、大小的簇參數(shù)的影響 減小，則可達(dá)距離為無窮大的點(diǎn)增多； MinPts減小，核心對(duì)象增多，圖象更尖銳 基于網(wǎng)格的方法（Grid-

24、Based Methods） 聚類高維數(shù)據(jù)是聚類分析中一個(gè)非常重要的任務(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ǎng)格的方法（基于網(wǎng)格的方法（Grid-Based MethodsGrid-Based Methods） 將數(shù)據(jù)空間劃分成為有限個(gè)單元（cell）的網(wǎng)格結(jié)構(gòu)，所有的處理都是以單個(gè)單元為對(duì)象的。 這種方法的主要優(yōu)點(diǎn)是它的處理速度很快，處理時(shí)間獨(dú)立于數(shù)據(jù)對(duì)

25、象的數(shù)目，只與每一維所劃分的單元數(shù)目有關(guān) 代表算法有：CLIQUE算法。CLQUE是一個(gè)綜合了基于密度和基于網(wǎng)格方法的聚類算法，對(duì)于大型數(shù)據(jù)庫中的高維數(shù)據(jù)的聚類比較有效,在高維數(shù)據(jù)的子空間中識(shí)別稠密的聚類，所產(chǎn)生的理解結(jié)果與所給的輸入數(shù)據(jù)無關(guān)。CLIQUE：高維度數(shù)據(jù)的自動(dòng)子空間聚類算法CLIQUE：聚類高維空間CLIQUE的中心思想如下： 給定一個(gè)多維數(shù)據(jù)點(diǎn)的大集合，數(shù)據(jù)點(diǎn)在數(shù)據(jù)空間中通常不是均衡分布的。CLIQUE區(qū)分空間中稀疏的和“擁擠的”區(qū)域，以發(fā)現(xiàn)數(shù)據(jù)集合全局分布模式。 將數(shù)據(jù)空間中的每個(gè)維劃分成等長且數(shù)量相等的間隔段，即單元。如果一個(gè)單元中的包含數(shù)據(jù)點(diǎn)超過了某個(gè)輸入模型參數(shù)，則該單

26、元是密集的。在CLIQUE中，一個(gè)聚類被定義為相連的密集單元的最大集合。問題描述 要能自動(dòng)地識(shí)別一個(gè)高維數(shù)據(jù)的子空間限制在只對(duì)原始空間的子空間的搜索而不是使用一個(gè)新的維度為了識(shí)別數(shù)據(jù)點(diǎn)的密度，將數(shù)據(jù)空間劃分并找出在每個(gè)單元中數(shù)據(jù)點(diǎn)的數(shù)量。聚類是子空間中相連的高密度單元的并集，即將聚類映射到軸對(duì)稱的超矩形中。聚類在空間中的描述 設(shè)AA1,A2,Ad是一個(gè)有界的、全部有序的域的集合。而SA1A2Ad是一個(gè)d維的數(shù)字空間，A1，A2，Ad定義為S的維。 輸入是由d維點(diǎn)集Vv1,v2,vm組成的，其中Vi=,Vi的第j個(gè)元素來自域Aj。 將數(shù)據(jù)空間S劃分成非重疊矩形單元。單元的劃分方法是在每一個(gè)維上將

27、維分割成個(gè)等長的間隔段，是輸入?yún)?shù)。 每一個(gè)單元u是由每一個(gè)屬性一個(gè)間隔段組成的交集。形式為u1,u2,ud，其中ui=li,hi）是在Ai的劃分中的右邊界開放的間隔段。聚類在空間中的描述聚類在空間中的描述 一個(gè)點(diǎn)V屬于單元u=u1,u2,.ud,當(dāng)對(duì)所有的ui，有l(wèi)ivihi。 一個(gè)單元的選擇性（selectivity）：?jiǎn)卧獌?nèi)數(shù)據(jù)點(diǎn)的數(shù)量與單元的總數(shù)據(jù)點(diǎn)數(shù)量之比。 稱單元u是稠密的：若單元的選擇性大于密度閾值。聚類在空間中的描述聚類在空間中的描述 兩個(gè)k維單元u1，u2是連接的，即他們之間有一個(gè)公共面。 若存在k-1維，假設(shè)是維At1，At2，,Atk-1，單元u1rt1,rt2,rtk

28、及u2=rt1， rt2，, rtk-1是相連的， 則有rtj= rtj，并且有htk ltk 或者h(yuǎn)tk ltk。 若RCR，則稱一個(gè)區(qū)域R包含于一個(gè)聚類C中。若沒有其他R的超集包含于聚類C中，則稱區(qū)域R是最大的。 一個(gè)聚類的最小描述是具有最大區(qū)域的聚類的非冗余的覆蓋。例子（一）例子（一） 在下圖中，二維空間（age,salary）劃分成1010格一個(gè)單元是間隔段的交集；例如單元u（30 age35）（1salary2）。 一個(gè)區(qū)域是單元的矩形的并集。A與B是兩個(gè)區(qū)域：A（30 age50） （4 salary8）,B=（40 age60）（2 salary6）。 假設(shè) 陰影部分是稠密的單元，A B是一個(gè)聚類。該聚類的最小描述為：（30 age50）（4 salary8） （40 age60）（2 salary6）。例子（二）：圖二：原始數(shù)據(jù)空間的子空間中的聚類在圖二中，假設(shè)20，沒有2-維單元是稠密的，在原始數(shù)據(jù)空間中就沒有聚類。但將數(shù)據(jù)點(diǎn)投影到維salary上，就有三個(gè)1維密度單元，其中兩個(gè)是相連的，因此，在1維salary子空間上就有兩個(gè)聚類：C5salary7及D2 salary3.由于在age子空間中沒有密度單元，故在該子空間中就沒有聚類。CLIQUE算法由以下幾部分組