【正文】 Eps, MinPts 是從點(diǎn) q直接密度可達(dá)的 , 如果 ? 1) p 屬于 NEps(q) ? 2) 核心點(diǎn)條件 : |NEps (q)| = MinPts p q MinPts = 5 Eps = 1 cm 87 基于密度的聚類 : 背景 II ? 密度可達(dá) : ? 點(diǎn) p 關(guān)于 Eps, MinPts 是從 q密度可達(dá)的 , 如果 存在一個節(jié)點(diǎn)鏈 p1, …, pn, p1 = q, pn = p 使得 pi+1 是從 pi直接密度可達(dá)的 ? 密度相連的 : ? 點(diǎn) p關(guān)于 Eps, MinPts 與點(diǎn) q是密度相連的 , 如果 存在點(diǎn) o 使得 , p 和 q 都是關(guān)于 Eps, MinPts 是從 o 密度可達(dá)的 p q p1 p q o 88 例子 ? MinPts=3 ? q是從 p密度可達(dá)； p不是從 q密度可達(dá)（ q非核心） ? S和 r從 o密度可達(dá)； o從 r密度可達(dá)； ? r, s, o密度相連 89 DBSCAN(1996) ? DBSCAN(Density Based Spatial Clustering of Applications with Noise) 一個基于密度的聚類算法 ? 可以在帶有“噪音”的空間數(shù)據(jù)庫中發(fā)現(xiàn)任意形狀的聚類 Core Border Outlier Eps = 1cm MinPts = 5 90 DBSCAN(續(xù) ) ? 算法 ? 任意選取一個點(diǎn) p ? 得到所有從 p 關(guān)于 Eps 和 MinPts密度可達(dá)的點(diǎn) . ? 如果 p 是一個核心點(diǎn) , 則找到一個聚類 . ? 如果 p 是一個邊界點(diǎn) , 沒有從 p 密度可達(dá)的點(diǎn) , DBSCAN 將訪問數(shù)據(jù)庫中的下一個點(diǎn) . ? 繼續(xù)這一過程 , 直到數(shù)據(jù)庫中的所有點(diǎn)都被處理 . ? DBSCAN的復(fù)雜度 ? 采用空間索引 , 復(fù)雜度為 O(nlog n), 否則為 O(n2) ? DBSCAN的缺點(diǎn) : ? 對用戶定義的參數(shù)是敏感的 , 參數(shù)難以確定 (特別是對于高維數(shù)據(jù) ), 設(shè)置的細(xì)微不同可能導(dǎo)致差別很大的聚類 . （數(shù)據(jù)傾斜分布）全局密度參數(shù)不能刻畫內(nèi)在的聚類結(jié)構(gòu) 91 OPTICS (1999) ? OPTICS(Ordering Points To Identify the Clustering Structure) ? Ankerst, Breunig, Kriegel, 和 Sander 提出 (SIGMOD’99) ? 為自動和交互的聚類分析計(jì)算一個簇次序 (cluster ordering ). ? 這個次序代表了數(shù)據(jù)的基于密度的聚類結(jié)構(gòu)。它包含了信息 , 等同于從一個廣域的參數(shù)設(shè)置所獲得的基于密度的聚類 ? 可用于自動和交互聚類分析 , 包括發(fā)現(xiàn)內(nèi)在聚類結(jié)構(gòu) ? 可以使用圖形或可視化技術(shù)表示 92 OPTICS(續(xù) ) ? 考慮 DBSCAN, 對一個恒定的 MinPts值 , 關(guān)于高密度的 (即較小的 ?值 )的聚類結(jié)果被完全包含在根據(jù)較低密度所獲得的密度相連的集合中 ? 擴(kuò)展 DBSCAN算法來同時(shí)處理一組距離參數(shù)值 ? 為了同時(shí)構(gòu)建不同的聚類 , 應(yīng)當(dāng)以特定的順序來處理對象 . 優(yōu)先選擇最小的 ?值密度可達(dá)的對象 , 以便高密度的聚類能被首先完成 ? 每個對象需要存儲兩個值 ? 對象 p的 核心距離 (coredistance)是使得 p成為核心對象的最小 ?。如果 p不是核心對象 , p的核心距離沒有定義 ? 對象 q關(guān)于另一個對象 p的 可達(dá)距離 (reachabilitydistance )是 p的核心距離和 p與 q的歐幾里得距離 之間的較大值 . 如果 p不是一個核心對象 , p和 q之間的可達(dá)距離沒有定義 93 OPTICS(續(xù) ) ? 例 : 設(shè) ?=6(mm), MinPts=5. ? p的核心距離是 p與第四個最近的數(shù)據(jù)對象之間的距離 ?’ . ? q1關(guān)于 p的可達(dá)距離是 p的核心距離 (即 ?’ =3mm), 因?yàn)樗葟?p到 q1的歐幾里得距離要大 . ? q2關(guān)于 p的可達(dá)距離是從 p到 q2的歐幾里得距離 , 它大于 p的核心距離 ?=6mm ?’ =3mm ?=6mm ?’ =3mm p p q1 q2 P的核心距離 可達(dá)距離 (p,q1)=?’=3mm 可達(dá)距離 (p,q2)=d(p,q2) 94 OPTICS(續(xù) ) ? 這些值怎樣使用？ ? OPTICS算法創(chuàng)建了數(shù)據(jù)庫中對象的一個次序 , 額外存儲了每個對象的核心距離和一個適當(dāng)?shù)目蛇_(dá)距離 ? 已經(jīng)提出了一種算法 , 基于 OPTICS產(chǎn)生的次序信息來抽取聚類 . 對于小于在生成該次序中采用的距離 ?的任何距離 ?’ , 為提取所有基于密度的聚類 , 這些信息是足夠的 ? 一個數(shù)據(jù)集合的聚類次序可以被圖形化地描述，以助于理解 ? ? 由于 OPTICS算法與 DBSCAN在結(jié)構(gòu)上的等價(jià)性 , 它具有和DBSCAN相同的時(shí)間復(fù)雜度 , 即當(dāng)使用空間索引時(shí) , 復(fù)雜度為 O(nlog n) 95 ??可達(dá)距離 對象的簇次序 無定義 ?‘ 96 DENCLUE(1998) ? DENCLUE(DENsitybased CLUstEring) 由 Hinneburg 和Keim (KDD’98)提出 , 是基于密度分布函數(shù)的聚類方法 ? 主要特點(diǎn) ? 堅(jiān)實(shí)的數(shù)學(xué)基礎(chǔ) , 概括了其他的聚類方法 , 包括基于劃分的 , 層次的 , 及基于位置的方法 ? 適用于具有大量噪音的數(shù)據(jù)集 ? 可用于高維數(shù)據(jù)集任意形狀的聚類 , 它給出了簡潔的數(shù)學(xué)描述 ? 明顯快于現(xiàn)有算法 (比 DBSCAN 快 45倍 ) ? 但是 , 需要大量參數(shù) ,要求對密度參數(shù) σ和噪音閥值 ξ進(jìn)行仔細(xì)的選擇 97 ? 使用柵格單元 , 但只保存實(shí)際存放數(shù)據(jù)點(diǎn)的柵格單元信息 , 并且在一個基于樹的存取結(jié)構(gòu)中管理這些單元 . ? 影響函數(shù) (Influence function): 描述數(shù)據(jù)點(diǎn)在其鄰域的影響 . ? 數(shù)據(jù)空間的整體密度可以被模擬為所有數(shù)據(jù)點(diǎn)的影響函數(shù)的總和 ? 聚類可以通過確定 密度吸引點(diǎn) (density attractor)來得到 . ? 密度吸引點(diǎn)是全局密度函數(shù)的局部最大值 . Denclue: 技術(shù)要點(diǎn) 98 DENCLUE(續(xù) ) ? 設(shè) x和 y是 d維特征空間 Fd中的對象 . 數(shù)據(jù)對象 y對 x的影響函數(shù) 是一個函數(shù) f yB： Fd → R+0, 它是根據(jù)一個基本的影響函數(shù) fB來定義的 f yB(x)= fB(x, y) ? 原則上 , 影響函數(shù)可以是一個任意的函數(shù) , 它由某個鄰域內(nèi)的兩個對象之間的距離來決定 ? 例如歐幾里得距離函數(shù) , 用來計(jì)算一個方波影響函數(shù) (square wave influence function)： 其它如果1),(0{),( ??? yxdyxfSqua r e99 DENCLUE(續(xù) ) ? 高斯影響函數(shù) ? 一個對象 x∈ Fd的密度函數(shù)被定義為所有數(shù)據(jù)點(diǎn)的影響函數(shù)的和 . 給定 n個對象 , D={x1,… ,xn}? Fd, 在 x上的密度函數(shù)定義如下 222),(),( ?yxdG au s s eyxf??)()(1xfxfnixBDBi???100 DENCLUE(續(xù) ) ? 例如 , 根據(jù)高斯影響函數(shù)得出的密度函數(shù)是 ? 根據(jù)密度函數(shù) , 我們能夠定義該 函數(shù)的梯度 和 密度吸引點(diǎn)(全局密度函數(shù)的局部最大 ) ? 一個點(diǎn) x是被一個 密度吸引點(diǎn) x*密度吸引的 , 如果存在一組點(diǎn) x0, x1, …,x k, x0=x, xk=x*, 對 0ik， xi1的梯度是在 xi的方向上 ? 對一個連續(xù)的 , 可微的影響函數(shù) , 用梯度指導(dǎo)的爬山算法能用來計(jì)算一組數(shù)據(jù)點(diǎn)的密度吸引點(diǎn) ? ? ?? NixxdDG au s siexf 1 2),(22)( ?101 密度吸引點(diǎn) 102 密度吸引點(diǎn) 103 中心定義的簇和任意形狀的簇 ? 密度吸引點(diǎn) x*的 中心定義的簇 (centerdefined cluster)是一個被 x*密度吸引的子集 C, 在 x*的密度函數(shù)不小于一個閥值 ξ。 否則 (即如果它的密度函數(shù)值小于 ξ), 它被認(rèn)為是孤立點(diǎn) ? 一個 任意形狀的簇 (arbitraryshape cluster)是子集 C的集合 , 每一個是各自密度吸引子密度吸引的 ,有不小于閥值 ξ的密度函數(shù)值 , 從每個區(qū)域到另一個都存在一條路徑 P, 該路徑上每個點(diǎn)的密度函數(shù)值都不小于 ξ 104 中心定義的簇和任意形狀的簇 105 第 8章 . 聚類分析 ? 什么是聚類（ Clustering） 分析 ? ? 聚類分析中的數(shù)據(jù)類型 ? 主要聚類方法分類 ? 劃分方法（ Partitioning Methods） ? 層次方法（ Hierarchical Methods） ? 基于密度的方法（ DensityBased Methods） ? 基于網(wǎng)格的方法（ GridBased Methods） ? 基于模型的聚類方法 （ ModelBased Clustering Methods） ? 孤立點(diǎn)分析（ Outlier Analysis） ? 小結(jié) 106 基于網(wǎng)格的聚類方法 ? 使用多分辨率的網(wǎng)格數(shù)據(jù)結(jié)構(gòu) ? 一些有趣的方法 ? STING (a STatistical INformation Grid approach) 由 Wang, Yang 和 Muntz 提出 (1997) ? WaveCluster 由 Sheikholeslami, Chatterjee, 和 Zhang 提出 (VLDB’98) ? 采用小波方法的多分辨率的聚類方法 ? CLIQUE: Agrawal, et al. 提出 (SIGMOD’98) 107 STING: 統(tǒng)計(jì)信息網(wǎng)格 ? STING( STatistical INformation Grid)是一個基于網(wǎng)格的多分辨率聚類技術(shù) , 由 Wang, Yang 和 Muntz 提出(VLDB’97) ? 空間區(qū)域劃分為矩形單元 ? 多個級別的矩形單元 , 對應(yīng)不同級別的分辨率 . 這些單元形成了一個層次結(jié)構(gòu) : 每個高層單元被劃分為多個低一層的單元 ? 預(yù)先計(jì)算和存儲關(guān)于每個網(wǎng)格單元屬性的統(tǒng)計(jì)信息 (如平均值 , 最大值 , 和最小值 ), 用于回答查詢 108 STING(續(xù) ) STING聚類的層次結(jié)構(gòu) 109 STING(續(xù) ) ? 高層單元的統(tǒng)計(jì)參數(shù)可以很容易地從低層單元的計(jì)算得到 . 這些統(tǒng)計(jì)參數(shù)包括： ? 屬性無關(guān)的參數(shù) count； 屬性相關(guān)的參數(shù) m(平均值 ), s(標(biāo)準(zhǔn)偏差 ), min(最小值 ), max(最大值 ) ? 該單元中屬性值遵循的分布類型 : 正態(tài)的 , 一致的 , 指數(shù)的 , 無 (分布未知 ) ? 分布的值可以由用戶指定 , 也可以通過假設(shè)檢驗(yàn) (如 ?2檢驗(yàn) )來獲得 ? 最底層單元的參數(shù) count, m, s, min, 和 max直接進(jìn)行計(jì)算 110 STING(續(xù) ) ? 使用自頂向下的方法回答空間數(shù)據(jù)查詢 ? 在層次結(jié)構(gòu)中選定一層作為查詢處理的開始點(diǎn) ——通常 ,該層包含少量的單元 ? 對當(dāng)前層次的每個單元 , 計(jì)算置信度區(qū)間 (或者估算其概率 ), 用以反映該單元與給定查詢的關(guān)聯(lián)程度 ? 刪除不相關(guān)的單元 , 進(jìn)一步處理不考慮它們 ? 結(jié)束當(dāng)前層的考查后 , 就處理下一層 ? 重復(fù)這一過程 , 直到最低層 111 STING(續(xù) ) ? 優(yōu)點(diǎn) : ? 基于網(wǎng)格的計(jì)算是獨(dú)立于查詢的 : 存儲在每個單元中的統(tǒng)計(jì)信息是不依賴于查詢的匯總信息 ? 網(wǎng)格結(jié)構(gòu)有利于并行處理和增量更新 ? 效率很高： STING掃描數(shù)據(jù)庫一次來計(jì)算單元的統(tǒng)計(jì)信息 , 因此產(chǎn)生聚類的時(shí)間復(fù)雜度是 O(n), 其中 , n是對象的數(shù)目 層次結(jié)構(gòu)建立后 , 查詢處理時(shí)間是 O(K), K是最底層網(wǎng)格單元的數(shù)目 , 通常遠(yuǎn)遠(yuǎn)小于 n ? 缺點(diǎn) : ? 所有的聚類邊界或者是水平的 , 或者是豎直的 , 沒有斜的分界線 . 盡管該技術(shù)有快速的處理速度 , 但可能降低簇的質(zhì)量和精確性 112 WaveCluster (1998) ? 由 Sheikholeslami, Chatterjee, 和 Zhang (VLDB’98) 提出 ? 采用小波變換聚類 : 是一種多分辨率的聚類算法 , 對特征空間采用小波變換 (wa