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

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

2、k-means算法、 K-medoids等,劃分聚類方法,k-means 算法,k-means 算法基本步驟 從 n個數(shù)據(jù)對象任意選擇 k 個對象作為初始聚類中心； 根據(jù)每個聚類對象的均值(中心對象)，計算每個對象與這些中心對象的距離；并根據(jù)最小距離重新對相應(yīng)對象進(jìn)行劃分； 重新計算每個(有變化)聚類的均值(中心對象)； 計算標(biāo)準(zhǔn)測度函數(shù)，當(dāng)滿足一定條件，如函數(shù)收斂時，則算法終止；如果條件不滿足則回到步驟2,k-means優(yōu)缺點,主要優(yōu)點： 是解決聚類問題的一種經(jīng)典算法，簡單、快速。 對處理大數(shù)據(jù)集，該算法是相對可伸縮和高效率的。 當(dāng)結(jié)果簇是密集的，它的效果較好。 主要缺點 在簇的平均值被定義

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

4、,層次聚類優(yōu)缺點,層次聚類方法是不可逆的，也就是說，當(dāng)通過凝聚式的方法將兩組合并后，無法通過分裂式的辦法再將其分離到之前的狀態(tài)，反之亦然。 另外，層次聚類過程中調(diào)查者必須決定聚類在什么時候停止，以得到某個數(shù)量的分類。 在不必要的情況下應(yīng)該小心使用層次聚類方法,劃分聚類方法 層次聚類方法 密度聚類方法 ：基于密度的聚類方法以數(shù)據(jù)集在空間分布上的稠密程度為依據(jù)進(jìn)行聚類，無需預(yù)先設(shè)定簇的數(shù)量，因此特別適合對于未知內(nèi)容的數(shù)據(jù)集進(jìn)行聚類。 網(wǎng)格聚類方法 模型聚類方法,密度聚類方法,基于密度方法的聚類,密度聚類方法的指導(dǎo)思想是，只要一個區(qū)域中的點的密度大于某個域值，就把它加到與之相近的聚類中去。對于簇中每

5、個對象，在給定的半徑的鄰域中至少要包含最小數(shù)數(shù)目（MinPts）個對象。 這類算法能克服基于距離的算法只能發(fā)現(xiàn)“類圓形”的聚類的缺點，可發(fā)現(xiàn)任意形狀的聚類，且對噪聲數(shù)據(jù)不敏感。 代表算法有：DBSCAN、OPTICS、DENCLUE算法等,基于密度方法的聚類- DBSCAN,DBSCAN（Density-Based Spatial Clustering of Applications with Noise）一個比較有代表性的基于密度的聚類算法。與層次聚類方法不同，它將簇定義為密度相連的點的最大集合，能夠把具有足夠高密度的區(qū)域劃分為簇，并可在有“噪聲”的空間數(shù)據(jù)庫中發(fā)現(xiàn)任意形狀的聚類,傳統(tǒng)基于中

6、心的密度定義為： 數(shù)據(jù)集中特定點的密度通過該點半徑之內(nèi)的點計數(shù)(包括本身)來估計。 顯然，密度依賴于半徑,傳統(tǒng)的密度定義：基于中心的方法,基于密度方法的聚類- 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從

7、對象q出發(fā)是直接密度可達(dá)的,基于密度方法的聚類- DBSCAN 所用到的基本術(shù)語,密度可達(dá),定義 密度可達(dá)的：如果存在一個對象鏈p1，p2，pn，p1=q， pn=p，對piD，（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ù)語,圖 密度相連,圖 噪聲,定義 噪聲: 一個基于密度的簇是

8、基于密度可達(dá)性的最大的密度相 連對象的集合。不包含在任何簇中的對象被認(rèn)為是“噪聲”。 邊界點：邊界點不是核心點，但落在某個核心點的鄰域內(nèi)。 噪聲就是那些既不是邊界點也不是核心點的對象,定義 密度相連的： 如果對象集合D中存在一個對象o，使得對象p 和q是從o關(guān)于和MinPts密度可達(dá)的，那么對象p和q是關(guān)于 和MinPts密度相連的,DBSCAN算法概念示例,如圖所示， 用一個相應(yīng)的半徑表示，設(shè)MinPts=3，請分析Q,M,P,S,O,R這5個樣本點之間的關(guān)系,直接密度可達(dá)”和“密度可達(dá)”概念示意描述,解答：根據(jù)以上概念知道：由于有標(biāo)記的各點M、P、O和R的 近鄰均包含3個以上的點，因此它們

9、都是核對象；M是從P“直接密度可達(dá)”；而Q則是從M“直接密度可達(dá)”；基于上述結(jié)果，Q是從P“密度可達(dá)”；但P從Q無法“密度可達(dá)”(非對稱)。類似地，S和R從O是“密度可達(dá)”的；O、R和S均是“密度相連”的,基于密度方法的聚類- DBSCAN,DBSCAN 算法根據(jù)以上的定義在數(shù)據(jù)庫中發(fā)現(xiàn)簇和噪聲。簇可等價于集合D中，這個簇核心對象密度可達(dá)的所有對象的集合。 DBSCAN通過檢查數(shù)據(jù)集中每個對象的-鄰域來尋找聚類。如果一個點p的-鄰域包含多于MinPts個對象，則創(chuàng)建一個p作為核心對象的新簇C。然后，DBSCAN從C中尋找未被處理對象q的-鄰域，如果q的-鄰域包含多MinPts個對象，則還未包含

10、在C中的q的鄰點被加入到簇中，并且這些點的-鄰域?qū)⒃谙乱徊街羞M(jìn)行檢測。這個過程反復(fù)執(zhí)行，當(dāng)沒有新的點可以被添加到任何簇時，該過程結(jié)束。具體如下,基于密度方法的聚類- DBSCAN,DBSCAN算法描述： 輸入：包含n個對象的數(shù)據(jù)庫，半徑，最少數(shù)目MinPts。 輸出：所有生成的簇，達(dá)到密度要求。 1. REPEAT 2. 從數(shù)據(jù)庫中抽取一個未處理過的點； 3. IF 抽出的點是核心點 THEN找出所有從該點密度可達(dá)的對象，形成一個簇 4. ELSE 抽出的點是邊緣點(非核心對象)，跳出本次循環(huán)，尋找下一點； 5. UNTIL 所有點都被處理,DBSCAN算法步驟,輸入：數(shù)據(jù)集D，參數(shù)MinPt

11、s, 輸出：簇集合 (1) 首先將數(shù)據(jù)集D中的所有對象標(biāo)記unvisited ； (2) do (3) 從D中隨機(jī)選取一個unvisited對象p，并將p標(biāo)記為visited ； if p的 鄰域 包含的對象數(shù)至少為MinPts個 創(chuàng)建新簇C ，并把p添加到c中； 令N為 p的 鄰域 中對象的集合； (7) for N 中每個點pi if pi 是unvisited 標(biāo)記pi 為visited； if pi 的 鄰域 至少有MinPts個 對象，把這些對象添加到N ； if pi 還不是任何簇的對象。將 pi 添加到 簇C中 ； (12) end for (13) 輸出C (14) Else

12、標(biāo)記p 為噪聲 (15) Untill 沒有標(biāo)記為unvisited 的對象,基于密度方法的聚類- DBSCAN,下面給出一個樣本事務(wù)數(shù)據(jù)庫（見下表），對它實施DBSCAN算法。 根據(jù)所給的數(shù)據(jù)通過對其進(jìn)行DBSCAN算法，以下為算法的步驟（設(shè)n=12，用戶輸入=1，MinPts=4,樣本事務(wù)數(shù)據(jù)庫,DBSCAN聚類過程,第1步，在數(shù)據(jù)庫中選擇一點1，由于在以它為圓心的，以1為半徑的圓內(nèi)包含2個點（小于4），因此它不是核心點，選擇下一個點。 第2步，在數(shù)據(jù)庫中選擇一點2，由于在以它為圓心的，以1為半徑的圓內(nèi)包含2個點，因此它不是核心點，選擇下一個點。 第3步，在數(shù)據(jù)庫中選擇一點3，由于在以它為

13、圓心的，以1為半徑的圓內(nèi)包含3個點，因此它不是核心點，選擇下一個點,DBSCAN聚類過程,第4步，在數(shù)據(jù)庫中選擇一點4，由于在以它為圓心的，以1為半徑的圓內(nèi)包含5個點，因此它是核心點，尋找從它出發(fā)可達(dá)的點（直接可達(dá)4個，間接可達(dá)3個），聚出的新類1，3，4，5，9，10，12，選擇下一個點,DBSCAN聚類過程,第5步，在數(shù)據(jù)庫中選擇一點5，已經(jīng)在簇1中，選擇下一個點。 第6步，在數(shù)據(jù)庫中選擇一點6，由于在以它為圓心的，以1為半徑的圓內(nèi)包含3個點，因此它不是核心點，選擇下一個點,DBSCAN聚類過程,第7步，在數(shù)據(jù)庫中選擇一點7，由于在以它為圓心的，以1為半徑的圓內(nèi)包含5個點，因此它是核心點，

14、尋找從它出發(fā)可達(dá)的點，聚出的新類2，6，7，8，11，選擇下一個點,DBSCAN聚類過程,第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,算法執(zhí)行過程,DBSCAN的時間復(fù)雜性,時間復(fù)雜度 DBSCAN算法要對每個數(shù)據(jù)對象進(jìn)行鄰域檢查時間性能較低。 DBSCAN的基本時間復(fù)雜度是

15、O(N*找出Eps領(lǐng)域中的點所需要的時間), N是點的個數(shù)。最壞情況下時間復(fù)雜度是O(N2) 在低維空間數(shù)據(jù)中,有一些數(shù)據(jù)結(jié)構(gòu)如KD樹，使得可以有效的檢索特定點給定距離內(nèi)的所有點，時間復(fù)雜度可以降低到O(NlogN,DBSCAM的空間復(fù)雜性,空間復(fù)雜度 在聚類過程中，DBSCAN一旦找到一個核心對象，即以該核心對象為中心向外擴(kuò)展此過程中核心對象將不斷增多，未處理的對象被保留在內(nèi)存中若數(shù)據(jù)庫中存在龐大的聚類，將需要很大的存來存儲核心對象信息，其需求難以預(yù)料 當(dāng)數(shù)據(jù)量增大時，要求較大的內(nèi)存支持 I/0 消耗也很大; 低維或高維數(shù)據(jù)中，其空間都是O(N,基于密度方法的聚類,優(yōu)點 能克服基于距離的算法

16、只能發(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操作,OPTICS 算法,由于在DBSCAN算法中，變量，MinPts是全局惟一的， 當(dāng)空間聚類的密度不均勻、聚類間距

17、離相差很大時，聚類質(zhì)量較差。 許多現(xiàn)實的數(shù)據(jù)集內(nèi)在的聚類結(jié)構(gòu)不能夠通過全局的密度參數(shù)來描述，數(shù)據(jù)空間中不同區(qū)域的聚類需要不同的局部密度,OPTICS 算法,盡管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 算法,下圖中所描述的數(shù)據(jù)集不能通過一個全局密度參數(shù)同時區(qū)分出簇A 、B 、C、C1、C2和C3，只能得到A 、B 、C或C1、C2和C3，對于

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

19、使 q從p密度可達(dá)的最小半徑。p的核心距離和p,q的歐幾里得距離之間的較大值，p必須是核心對象且q在p的鄰域內(nèi)。 若|N(p)| MinPts，即P不是核心對象，則無定義 否則，定義為Max（核心距離，|（p,q）,OPTICS 算法,例 核心距離與可達(dá)距離,假設(shè) =6mm， MinPts =5 。P的核心距離是p于第四個最近的數(shù)據(jù)對象之間的距離，q1到p的可達(dá)距離是p的核心距離（ =3mm），因為它比q1到p的歐氏距離大。q2關(guān)于p的科大距離是p到q2的歐氏距離，它大于p的核心距離,OPTICS 算法,OPTICS 算法并不顯式的產(chǎn)生數(shù)據(jù)及聚類，而是輸出簇排序（cluster orderin

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

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

22、可達(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實際運行的速度遠(yuǎn)遠(yuǎn)低于DBSCAN,不同密度、形狀、大小的簇,參數(shù)的影響,減小，則可達(dá)距離為無窮大的點增多； MinPts減小，核心對象增多，圖象更尖銳,基于網(wǎng)格的方法（Grid-Based Me

23、thods,聚類高維數(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ǎng)格的方法（Grid-Based Methods） 將數(shù)據(jù)空間劃分成為有限個單元（cell）的網(wǎng)格結(jié)構(gòu)，所有的處理都是以單個單元為對象的。 這種方法的主要優(yōu)點是它的處理速度很快，處理時間獨立于數(shù)據(jù)對象的數(shù)目，只與每一維所劃分的單元數(shù)目有關(guān) 代表算法有：CLIQUE算法,

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

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

26、性一個間隔段組成的交集。形式為u1,u2,ud，其中ui=li,hi）是在Ai的劃分中的右邊界開放的間隔段,聚類在空間中的描述,一個點V屬于單元u=u1,u2,.ud,當(dāng)對所有的ui，有l(wèi)ivihi。 一個單元的選擇性（selectivity）：單元內(nèi)數(shù)據(jù)點的數(shù)量與單元的總數(shù)據(jù)點數(shù)量之比。 稱單元u是稠密的：若單元的選擇性大于密度閾值,聚類在空間中的描述,兩個k維單元u1，u2是連接的，即他們之間有一個公共面。 若存在k-1維，假設(shè)是維At1，At2，,Atk-1，單元u1 rt1,rt2,rtk 及u2=rt1， rt2，, rtk-1是相連的， 則有rtj= rtj，并且有htk ltk

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