基于密度方法的聚類PPT課件

1、2021/3/91聚 類 分 析宋宜飛2021/3/92主要內(nèi)容 回顧回顧 密度聚類方法密度聚類方法 DBSCAN算法 OPTICS 算法 網(wǎng)格聚類方法網(wǎng)格聚類方法 CLIQUE算法2021/3/93回顧回顧聚類 聚類(clustering)也稱為聚類分析,指將樣本分到不同的組中使得同一組中的樣本差異盡可能的小，而不同組中的樣本差異盡可能的大。聚類得到的不同的組稱為簇(cluster)。一個好的聚類方法將產(chǎn)生以下的聚類 最大化類中的相似性 最小化類間的相似性2021/3/94回顧聚類的分類： 劃分聚類方法劃分聚類方法 層次聚類方法層次聚類方法 密度聚類方法密度聚類方法 網(wǎng)格聚類方法網(wǎng)格聚類方法

2、 模型聚類方法模型聚類方法2021/3/95在基于劃分的聚類中，任務(wù)就是將數(shù)據(jù)劃分成K個不相交的點集，使每個子集中的點盡可能同質(zhì)。基于劃分的方法 ，其代表算法有 k-means算法、 K-medoids等劃分聚類方法2021/3/96k-means k-means 算法算法 k-means 算法基本步驟 從 n個數(shù)據(jù)對象任意選擇 k 個對象作為初始聚類中心； 根據(jù)每個聚類對象的均值(中心對象)，計算每個對象與這些中心對象的距離；并根據(jù)最小距離重新對相應(yīng)對象進行劃分； 重新計算每個(有變化)聚類的均值(中心對象)； 1. 計算標(biāo)準測度函數(shù)，當(dāng)滿足一定條件，如函數(shù)收斂時，則算法終止；如果條件不滿足

3、則回到步驟2。2021/3/97k-means優(yōu)缺點 主要優(yōu)點：是解決聚類問題的一種經(jīng)典算法，簡單、快速。對處理大數(shù)據(jù)集，該算法是相對可伸縮和高效率的。當(dāng)結(jié)果簇是密集的，它的效果較好。 主要缺點在簇的平均值被定義的情況下才能使用。必須事先給出k（要生成的簇的數(shù)目），而且對初值敏感，對于不同的初始值，可能會導(dǎo)致不同結(jié)果。不適合于發(fā)現(xiàn)非凸面形狀的簇或者大小差別很大的簇。而且，它對于“躁聲”和孤立點數(shù)據(jù)是敏感的。2021/3/98層次聚類方法層次聚類方法 層次聚類方法對給定的數(shù)據(jù)集進行層次的分解，直到某種條件滿足為止。具體又可分為： 凝聚的層次聚類：一種自底向上的策略，首先將每個對象作為一個簇，然后

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

5、密度聚類方法密度聚類方法 ：基于密度的聚類方法以數(shù)據(jù)集在空間分布上的稠密程度為依據(jù)進行聚類，無需預(yù)先設(shè)定簇的數(shù)量，因此特別適合對于未知內(nèi)容的數(shù)據(jù)集進行聚類。網(wǎng)格聚類方法網(wǎng)格聚類方法 模型聚類方法模型聚類方法密度聚類方法密度聚類方法2021/3/911基于密度方法的聚類 密度聚類方法的指導(dǎo)思想是，只要一個區(qū)域中的點的密度大于某個域值，就把它加到與之相近的聚類中去。對于簇中每個對象，在給定的半徑的鄰域中至少要包含最小數(shù)數(shù)目（MinPts）個對象。 這類算法能克服基于距離的算法只能發(fā)現(xiàn)“類圓形”的聚類的缺點，可發(fā)現(xiàn)任意形狀的聚類，且對噪聲數(shù)據(jù)不敏感。 代表算法有：DBSCAN、OPTICS、DENC

6、LUE算法等。2021/3/912基于密度方法的聚類- DBSCAN DBSCAN（Density-Based Spatial Clustering of Applications with Noise）一個比較有代表性的基于密度的聚類算法。與層次聚類方法不同，它將簇定義為密度相連的點的最大集合，能夠把具有足夠高密度的區(qū)域劃分為簇，并可在有“噪聲”的空間數(shù)據(jù)庫中發(fā)現(xiàn)任意形狀的聚類。2021/3/913傳統(tǒng)基于中心的密度定義為：數(shù)據(jù)集中特定點的密度通過該點半徑之內(nèi)的點計數(shù)(包括本身)來估計。顯然，密度依賴于半徑。傳統(tǒng)的密度定義：基于中心的方法2021/3/914基于密度方法的聚類- DBSCAN

7、 所用到的基本術(shù)語定義 對象的-鄰域：給定對象在半徑內(nèi)的區(qū)域。定義 核心對象：如果一個對象的-鄰域至少包含最小數(shù)目MinPts個 對象，則稱該對象為核心對象。 例 下圖中，=1cm，MinPts=5，q是一個核心對象。 定義 直接密度可達：給定一個對象集合D，如果p是在q的-鄰域內(nèi)，而 q是一個核心對象，我們說對象p從對象q出發(fā)是直接密度可達的。 例 在下圖中，=1cm，MinPts=5 ，q是一個核心對象，對象 p1從對象q出發(fā)是直接密度可達的。2021/3/915基于密度方法的聚類- DBSCAN 所用到的基本術(shù)語密度可達定義 密度可達的：如果存在一個對象鏈p1，p2，pn，p1=q， p

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

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

10、“密度可達”；但P從Q無法“密度可達”(非對稱)。類似地，S和R從O是“密度可達”的；O、R和S均是“密度相連”的。2021/3/918基于密度方法的聚類- DBSCAN DBSCAN 算法根據(jù)以上的定義在數(shù)據(jù)庫中發(fā)現(xiàn)簇和噪聲。簇可等價于集合D中，這個簇核心對象密度可達的所有對象的集合。 DBSCAN通過檢查數(shù)據(jù)集中每個對象的-鄰域來尋找聚類。如果一個點p的-鄰域包含多于MinPts個對象，則創(chuàng)建一個p作為核心對象的新簇C。然后，DBSCAN從C中尋找未被處理對象q的-鄰域，如果q的-鄰域包含多MinPts個對象，則還未包含在C中的q的鄰點被加入到簇中，并且這些點的-鄰域?qū)⒃谙乱徊街羞M行檢測。

11、這個過程反復(fù)執(zhí)行，當(dāng)沒有新的點可以被添加到任何簇時，該過程結(jié)束。具體如下：2021/3/919基于密度方法的聚類- DBSCANDBSCAN算法描述： 輸入：包含n個對象的數(shù)據(jù)庫，半徑，最少數(shù)目MinPts。 輸出：所有生成的簇，達到密度要求。 1. REPEAT 2. 從數(shù)據(jù)庫中抽取一個未處理過的點； 3. IF 抽出的點是核心點 THEN找出所有從該點密度可達的對象，形成一個簇 4. ELSE 抽出的點是邊緣點(非核心對象)，跳出本次循環(huán)，尋找下一點； 5. UNTIL 所有點都被處理；2021/3/920DBSCAN算法步驟 輸入：數(shù)據(jù)集D，參數(shù)MinPts, 輸出：簇集合(1) 首先將

12、數(shù)據(jù)集D中的所有對象標(biāo)記unvisited ；(2) do(3) 從D中隨機選取一個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 標(biāo)記p 為噪聲(15) Untill 沒有標(biāo)記

13、為unvisited 的對象2021/3/921基于密度方法的聚類- DBSCAN 下面給出一個樣本事務(wù)數(shù)據(jù)庫（見下表），對它實施DBSCAN算法。 根據(jù)所給的數(shù)據(jù)通過對其進行DBSCAN算法，以下為算法的步驟（設(shè)n=12，用戶輸入=1，MinPts=4） 序號屬性 1屬性 2121251312422532642752862913102311531224樣本事務(wù)數(shù)據(jù)庫2021/3/922DBSCAN聚類過程 第1步，在數(shù)據(jù)庫中選擇一點1，由于在以它為圓心的，以1為半徑的圓內(nèi)包含2個點（小于4），因此它不是核心點，選擇下一個點。 第2步，在數(shù)據(jù)庫中選擇一點2，由于在以它為圓心的，以1為半徑的圓內(nèi)

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

15、擇下一個點。2021/3/925DBSCAN聚類過程 第7步，在數(shù)據(jù)庫中選擇一點7，由于在以它為圓心的，以1為半徑的圓內(nèi)包含5個點，因此它是核心點，尋找從它出發(fā)可達的點，聚出的新類2，6，7，8，11，選擇下一個點。2021/3/926DBSCAN聚類過程 第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)是最后一點所有點都以處理，程序終止。2021/3

16、/927基于密度方法的聚類- DBSCAN步驟選擇的點在中點的個數(shù)通過計算可達點而找到的新簇112無222無333無445簇C1：1，3，4，5，9，10，12553已在一個簇C1中663無775簇C2：2，6，7，8，11882已在一個簇C2中993已在一個簇C1中10104已在一個簇C1中，11112已在一個簇C2中 12122已在一個簇C1中算法執(zhí)行過程：2021/3/928DBSCAN的時間復(fù)雜性 時間復(fù)雜度DBSCAN算法要對每個數(shù)據(jù)對象進行鄰域檢查時間性能較低。DBSCAN的基本時間復(fù)雜度是 O(N*找出Eps領(lǐng)域中的點所需要的時間), N是點的個數(shù)。最壞情況下時間復(fù)雜度是O(N2

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

18、有效地處理數(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操作。2021/3/931OPTICS 算法 由于在DBSCAN算法中，變量，MinPts是全局惟一的， 當(dāng)空間聚類的密度不均勻、聚類間距離相差很大時，聚類質(zhì)量較差。 許多現(xiàn)實

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

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

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

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

23、相應(yīng)的可達距離。 optics 維護一個稱作order seeds 的表來來產(chǎn)生輸出排列，orderseeds 中的對象按到各自的最近核心對象的可達距離排序，及按每個對象的最小可達距離排序。2021/3/938OPTICS 算法2021/3/939尋找簇Reachability-distanceundefinedCluster-orderof the objects2021/3/940 數(shù)據(jù)集的簇排序可以用圖形描述，這有助于可視化和理解數(shù)據(jù)集中聚類結(jié)構(gòu)。例如下圖是一個簡單的二維數(shù)據(jù)集的可達性圖?？蛇_距離可達距離未定義未定義2021/3/941OPTICS算法并不直接尋找各個簇,而是將基于密度查

24、找簇所需要的信息記錄下來,這些信息反映了數(shù)據(jù)空間基于密度的簇結(jié)構(gòu)。同時從這些密度信息可以直接發(fā)現(xiàn)各個簇。OPTICS采取了兩個方法來達到目標(biāo)1)定義了對象的核心距離和可達距離,以反映對象附近的密度大小;2)在迭代查找可達對象時,對種子對象依可達距離進行排序,從而在簇擴展時優(yōu)先擴展密度值較大區(qū)域的點。這樣,OPTICS算法實現(xiàn)了數(shù)據(jù)庫所有對象的排序,這一對象序列就可以反映出數(shù)據(jù)空間基于密度的簇結(jié)構(gòu)信息?；谶@些信息可以容易地確定合適的值,并隨之發(fā)現(xiàn)各個簇。另外,OPTICS還提供了自動的簇發(fā)現(xiàn)方法。OPTICS算法較好地解決了DBSCAN算法的對輸入?yún)?shù)敏感的問題,但是由于采用了復(fù)雜的處理方法以

25、及額外的磁盤IPO操作,使得OPTICS實際運行的速度遠遠低于DBSCAN。2021/3/9422021/3/9432021/3/9442021/3/945不同密度、形狀、大小的簇2021/3/946參數(shù)的影響 減小，則可達距離為無窮大的點增多； MinPts減小，核心對象增多，圖象更尖銳2021/3/947 基于網(wǎng)格的方法（Grid-Based Methods） 聚類高維數(shù)據(jù)是聚類分析中一個非常重要的任務(wù)，而一般聚類方法無法處理這些數(shù)據(jù)。用戶感興趣的通常是某個高維數(shù)據(jù)空間的若干個子空間，對該空間內(nèi)數(shù)據(jù)點的聚類要比原始空間更好一些。高維數(shù)據(jù)中，通常只有少數(shù)幾維與某些簇相關(guān)，其他不相關(guān)的維數(shù)據(jù)可

26、能會產(chǎn)生大量的噪聲而屏蔽真實的簇。 為聚類高維數(shù)據(jù)集便提出了基于網(wǎng)格的方法的聚類。2021/3/948 基于網(wǎng)格的方法（基于網(wǎng)格的方法（Grid-Based MethodsGrid-Based Methods） 將數(shù)據(jù)空間劃分成為有限個單元（cell）的網(wǎng)格結(jié)構(gòu)，所有的處理都是以單個單元為對象的。 這種方法的主要優(yōu)點是它的處理速度很快，處理時間獨立于數(shù)據(jù)對象的數(shù)目，只與每一維所劃分的單元數(shù)目有關(guān) 代表算法有：CLIQUE算法。2021/3/949CLQUE是一個綜合了基于密度和基于網(wǎng)格方法的聚類算法，對于大型數(shù)據(jù)庫中的高維數(shù)據(jù)的聚類比較有效,在高維數(shù)據(jù)的子空間中識別稠密的聚類，所產(chǎn)生的理解結(jié)果

27、與所給的輸入數(shù)據(jù)無關(guān)。CLIQUE：高維度數(shù)據(jù)的自動子空間聚類算法2021/3/950CLIQUE：聚類高維空間CLIQUE的中心思想如下： 給定一個多維數(shù)據(jù)點的大集合，數(shù)據(jù)點在數(shù)據(jù)空間中通常不是均衡分布的。CLIQUE區(qū)分空間中稀疏的和“擁擠的”區(qū)域，以發(fā)現(xiàn)數(shù)據(jù)集合全局分布模式。 將數(shù)據(jù)空間中的每個維劃分成等長且數(shù)量相等的間隔段，即單元。如果一個單元中的包含數(shù)據(jù)點超過了某個輸入模型參數(shù)，則該單元是密集的。在CLIQUE中，一個聚類被定義為相連的密集單元的最大集合。2021/3/951問題描述 要能自動地識別一個高維數(shù)據(jù)的子空間限制在只對原始空間的子空間的搜索而不是使用一個新的維度為了識別數(shù)據(jù)

28、點的密度，將數(shù)據(jù)空間劃分并找出在每個單元中數(shù)據(jù)點的數(shù)量。聚類是子空間中相連的高密度單元的并集，即將聚類映射到軸對稱的超矩形中。2021/3/952聚類在空間中的描述 設(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是由每一個屬性一個間隔段組成的交集。形式為u1,u2,ud，其中ui=li,hi）是在Ai的劃分中的右邊界開放的

29、間隔段。2021/3/953聚類在空間中的描述聚類在空間中的描述 一個點V屬于單元u=u1,u2,.ud,當(dāng)對所有的ui，有l(wèi)ivihi。 一個單元的選擇性（selectivity）：單元內(nèi)數(shù)據(jù)點的數(shù)量與單元的總數(shù)據(jù)點數(shù)量之比。 稱單元u是稠密的：若單元的選擇性大于密度閾值。2021/3/954聚類在空間中的描述聚類在空間中的描述 兩個k維單元u1，u2是連接的，即他們之間有一個公共面。 若存在k-1維，假設(shè)是維At1，At2，,Atk-1，單元u1rt1,rt2,rtk 及u2=rt1， rt2，, rtk-1是相連的， 則有rtj= rtj，并且有htk ltk 或者htk ltk。 若R

30、CR，則稱一個區(qū)域R包含于一個聚類C中。若沒有其他R的超集包含于聚類C中，則稱區(qū)域R是最大的。 一個聚類的最小描述是具有最大區(qū)域的聚類的非冗余的覆蓋。2021/3/955例子（一）例子（一） 在下圖中，二維空間（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）。2021/3/956例子（二）：圖二：原始數(shù)據(jù)空間的子空間中的聚類在圖二中，假設(shè)20，沒有2-維單元是稠密的，在原始數(shù)據(jù)空間中就沒有聚類。但將數(shù)據(jù)點投影到維salary上，就有三個1維密度單元，其中兩個是相連的，因此，在1維salary子空間上就有兩個聚類：C5salary7及D2 salary3.由于在age子空間中沒有密度單元，故在該子空間中就沒有聚類。2021/3/957CLIQUE算法由以下幾部分組成：1）含有聚類子空間的識別。2）聚類的識別。3）對聚類產(chǎn)生最小的描述。2021/3/958含有聚類子空