【文章內(nèi)容簡介】 數(shù)或收縮因子向簇中心“收縮”或移動它們。在算法的每一步，有最近距離的代表點對 (每個點來自于一個不同的簇 )的兩個簇被合并。 CURE是一種自底向上的層次聚類算法，首先將輸入的每個點作為一個簇，然后合并相似的簇，直到簇的個數(shù)為 k 時停止。 算法描述如下： (1)從源數(shù)據(jù)對象中抽取一個隨機樣本 S； (2)將樣本 S劃分為一組分塊； (3)對每個劃分局部地聚類； (4)通過隨機取樣剔除孤立點。如果一個簇增長得太慢，就去掉它。 (5)對局部的簇進行聚類。 落在每個新形成的簇中的代表點根據(jù)用戶定義的一個收縮因子 a 收縮或向簇中心移動。這些點描述和捕捉到了簇的形狀。 (6)用相應的簇標簽來標記數(shù)據(jù)。 ROCK算法 ROCK采用一種比較全局的觀點，通過考慮成對點的鄰域情況進行聚類。如果兩個相似的點同時具有相似的鄰域，那么這兩個點可能屬于同一個簇而合并。 兩個 “點 ”即兩個事務 和 之間的相似度用 Jaccard系數(shù) 定義為： ||||),(jijiji TTTTTTs i m???例 44同時使用點間相似度和鄰域鏈接信息的影響分析示例 假定一個購物籃數(shù)據(jù)庫包含關(guān)于商品 a,b,…,g 的事務記錄。考慮這些事務的兩個簇 C1和 C2。 C1涉及商品 {a， b， c， d， e}，包含事務 {a， b， c}， {a， b， d}， {a， b， e}， {a， c， d}， {a， c，e}， {a， d， e}， {b， c， d}， {b， c， e}， {b， d， e}， {c， d， e}。C2涉及商品 {a， b， f， g}，包含事務 {a， b， f}， {a， b， g}， {a，f， g}， {b， f， g}。假設我們首先只考慮點間的相似度而忽略鄰域信息。 C1中事務 {a， b， c}和 {b， d， e}之間的 Jaccard系數(shù)為1/5=。事實上， C1中任意一對事務之間的 Jaccard系數(shù)都在 (如 {a， b， c}和 {a， b， d})。而屬于不同簇的兩個事務之間的 Jaccard系數(shù)也可能達到 (如 C1中的 {a， b， c}和C2中的 {a， b， f}或 {a， b， g})。很明顯，僅僅使用 Jaccard系數(shù)，無法得到所期望的簇。 ? ROCK基于鏈接的方法可以成功地把這些事務劃分到恰當?shù)拇刂?。直觀地看，對于每一個事務，與之鏈接最多的那個事務總是和它處于同一個簇中。例如，令，則 C2中的事務 {a， b， f}與同樣來自同一簇的事務 {a， b， g}之間的鏈接數(shù)為 5(因為它們有共同的近鄰 {a， b， c}， {a， b， d}， {a， b， e}， {a， f， g}和 {b，f， g})。然而， C2中的事務 {a， b， f}與 C1中事務 {a， b， c}之間的鏈接數(shù)僅為 3(其共同的鄰居為 {a， b， d}， {a， b， e}和 {a， b，g})。類似地， C2中的事務 {a， f， g}與 C2中其它每個事務之間的鏈接數(shù)均為 2，而與 C1中所有事務的鏈接數(shù)都為 0。因此，這種基于鏈接的方法能夠正確地區(qū)分出兩個不同的事務簇，因為它除了考慮對象間的相似度之外還考慮鄰近信息。 ROCK使用一個相似度閾值和共享近鄰的概念從一個給定的數(shù)據(jù)相似度矩陣中首先構(gòu)建一個稀疏圖。然后在這個稀疏圖上執(zhí)行凝聚層次聚類。使用一個優(yōu)度 (goodness measure)度量評價聚類，采用隨機抽樣處理大規(guī)模的數(shù)據(jù)集。 ROCK算法的聚類過程描述如下： (1) 隨機選擇一個樣本； (2) 在樣本上用凝聚算法進行聚類，簇的合并是基于簇間的相似度，即基于來自不同簇而有相同鄰居的樣本的數(shù)目； (3) 將其余每個數(shù)據(jù)根據(jù)它與每個簇之間的連接，判斷它應歸屬的簇。 基于密度的聚類算法 通常將簇看作是數(shù)據(jù)空間中被低密度區(qū)域 (代表噪聲 )分割開的稠密對象區(qū)域?；诿芏鹊姆椒ǖ湫偷陌? DBSCAN (DensityBased Spatial Clustering of Applications with Noise) OPTICS(Ordering Points to Identify the Clustering Structure) 圖 基于密度的聚類算法可聚類的形狀 DBSCAN算法 1 DBSCAN是一種基于高密度連通區(qū)域的聚類方法，該算法將具有足夠高密度的區(qū)域劃分為簇，并在具有噪聲的空間數(shù)據(jù)庫中發(fā)現(xiàn)任意形狀的簇，它將簇定義為密度相連的點的最大的集合。根據(jù)點的密度將點分為三類： (1) 稠密區(qū)域內(nèi)部的點 (核心點 )， (2) 稠密區(qū)域邊緣上的點 (邊界點 )， (3) 稀疏區(qū)域中的點 (噪聲或背景點 )。下面將介紹一些基本概念。 給定一個對象集合 D，對象之間的距離函數(shù)為 distance(*， *)，鄰域半徑為 Eps。 數(shù)據(jù)集中特定點的密度通過該點的 Eps半徑之內(nèi)包含的點數(shù) (包括點本身 )來估計。 DBSCAN算法 2 Eps鄰域： 給定對象半徑 Eps內(nèi)的鄰域稱為該對象的 Eps鄰域。我們用 表示點 p的 Eps半徑內(nèi)的點的集合，即 MinPts： 給定鄰域 包含的點的最小數(shù)目，用以決定點 p是簇的核心部分還是邊界點或噪聲。 核心對象： 如果對象的 Eps鄰域包含至少 MinPts個的對象，則稱該對象為核心對象。 邊界點： 邊界點不是核心點，但落在某個核心點的鄰域內(nèi)。 噪音點： 既不是核心點，也不是邊界點的任何點。 )( pNEpsE p s }q),d i s t a n c e ( pDq|{q)( ?? 中，在數(shù)據(jù)集pN E p s)( pN EpsDBSCAN算法 3 直接密度可達： 如果 p在 q的 Eps鄰域內(nèi)，而 q是一個核心對象，則稱對象 p 從對象 q出發(fā)時是直接密度可達的 (directly densityreachable)。 密度可達： 如果存在一個對象鏈 ，對于 ， 是 從關(guān)于 Eps和 MinPts直接密度可達的，則對象 p是從對象 q關(guān)于 Eps和 MinPts密度可達的 (densityreachable)。 密度相連： 如果存在對象 O∈ D，使對象 p和 q都是從 O關(guān)于 Eps和MinPts密度可達的，那么對象 p到 q是關(guān)于 Eps和 MinPts密度相連的 (densityconnected)。 ppqpppp nn ?? ,, 121 ?)1( niDp i ??? 1?ip ip算法具體描述 (1) 首先將數(shù)據(jù)集 D中的所有對象標記為未處理狀態(tài) (2) for 數(shù)據(jù)集 D中每個對象 p do (3) if p已經(jīng)歸入某個簇或標記為噪聲 then (4) continue。 (5) else (6) 檢查對象 p的 Eps鄰域 ； (7) if 包含的對象數(shù)小于 MinPts then (8) 標記對象 p為邊界點或噪聲點； (9) else (10) 標記對象 p為核心點，并建立新簇 C； (11) for 中所有尚未被處理的對象 q do (12) 檢查其 Eps鄰域 ，若 包含至少 MinPts個對象，則將 中未歸入任何一個簇的對象加入 C； (13) end for (14) end if (15) end if (16) end for (p) N Eps(p) NEps(p) NEps(p) NEps (p) NEps(q) NEps例 45 DBSCAN算法示例 1 ? 如圖 ， Eps用一個相應的半徑表示，設 MinPts=3。 圖 “直接密度可達”和“密度可達”概念示意描述 解答：根據(jù)以上概念知道：由于有標記的各點 M、 P、 O和 R的 Eps近鄰均包含 3個以上的點，因此它們都是核對象； M是從 P“直接密度可達”；而 Q則是從 M“直接密度可達”；基于上述結(jié)果， Q是從 P“密度可達”；但 P從 Q無法“密度可達” (非對稱 )。類似地， S和 R從 O是“密度可達”的； O、 R和 S均是“密度相連”的。 例 46 DBSCAN算法示例 2 對于表 43所示二維平面上的數(shù)據(jù)集，取 Eps=3， MinPts=3 來演示 DBSCAN算法的聚類過程 (使用 Mahattan距離公式 )。 表 43 聚類過程示例數(shù)據(jù)集 3 P1 P2 P3 P4 P5 P6 P7 P8 P9 P10 P11 P12 P13 1 2 2 4 5 6 6 7 9 1 3 5 3 2 1 4 3 8 7 9 9 5 12 12 12 3 DBSCAN算法示例 2 解答： (1) 隨機選擇一個點，如 P1(1， 2)，其 Eps鄰域中包含 {P1， P2，P3， P13}， P1是核心點，其鄰域中的點構(gòu)成簇 1的一部分，依次檢查 P2， P3， P13的 Eps鄰域，進行擴展，將點 P4并入， P4 為邊界點； (2) 檢查點 P5，其 Eps鄰域中包含 {P5， P6， P7， P8}， P5是核心點，其鄰域中的點構(gòu)成簇 2的一部分，依次檢查 P6， P7， P8的 Eps鄰域，進行擴展，每個點都是核心點，不能擴展； (3) 檢查點 P9，其 Eps鄰域中包含 {P9}， P9為噪聲點或邊界點； (4) 檢查點 P10，其 Eps鄰域中包含 {P10， P11}， P10為噪聲點或邊界點；檢查 P11，其 Eps鄰域中包含 {P10， P11， P12}， P11為核心點，其鄰域中的點構(gòu)成簇 3的一部分；進一步檢查， P P12為邊界點。 DBSCAN算法示例 2 所有點標記完畢， P9沒有落在任何核心點的鄰域內(nèi)，為噪聲點。 最終識別出三個簇， P9為噪聲點。簇 1包含 {P1， P2， P3， P4， P13}，P4為邊界點，其它點為核心點；簇 2包含 {P5， P6， P7， P8 }，其全部點均為核心點；簇 3包含 {P10， P11， P12}， P P12為邊界點， P11為核心點； 如果 MinPts=4，則簇 3中的點均被識別成噪聲點。 基于圖的聚類算法 基于圖的聚類算法需要用到一些重要方法 (1) 稀疏化鄰近度圖，只保留對象與其最近鄰之間的連接。這種稀疏化有利于降低噪聲和離群點的影響?？梢岳脼橄∈鑸D開發(fā)的有效圖劃分算法來進行稀疏化。 (2) 基于共享的最近鄰個數(shù)，定義兩個對象之間的相似性度量。該方法基于這樣的觀察，對象和它的最近鄰通常屬于同一個簇。該方法有助于克服高維和變密度簇的問題。 (3) 定義核心對象并構(gòu)建環(huán)繞它們的簇。與 DBSCAN一樣，圍繞核心對象構(gòu)建簇，設計可以發(fā)現(xiàn)不同形狀和大小的簇的聚類技術(shù)。 (4) 使用鄰近度圖中的信息，提供兩個簇是否應當合并的更復雜的評估。兩個簇合并僅當結(jié)果簇具有相似于原來的兩個簇的特性。 Chameleon聚類算法 利用動態(tài)模型的層次聚類算法 Chameleon算法是一種基于圖的層次聚類算法，該算法利用基于 圖 的方法得到的初始數(shù)據(jù)劃分與一種新穎的 層次聚類 方案相結(jié)合，使用簇間的接近性和互連性概念以及簇的局部建模來高質(zhì)量地發(fā)現(xiàn)具有 不同形狀、大小和密度 的簇。 Chameleon聚類算法 2 ? 確定合并哪些簇 ? Chameleon力求合并這樣的一對簇，合并后產(chǎn)生的簇，用互連性和緊密性來度量時，其與原來的一對簇最相似。為了理解互連性和緊密性概念，需要用鄰近圖的觀點，并且需要考慮簇內(nèi)和簇間點之間的邊數(shù)和這些邊的強度。 ? 相對互連度 (relative interconnectivity， RI)：簇 和 之間的絕對互連度是連接簇 和 中頂點的所有邊的權(quán)重之和，其本質(zhì)是同時包含簇 和 的邊割 (edge cut， EC)，用 表示。簇 的內(nèi)部互連度可以通過它的最小二分邊割 的大小 (即將圖劃分成兩個大致相等的部分的邊的加權(quán)和 )表示。簇 和 間的相對互連度 定義為用簇 和 的內(nèi)部互連度規(guī)格化簇 和 間的絕對互連度，計算公式如下： iC