1、第七章 聚類(lèi)分析,張靜 （Jingzhang）,主要內(nèi)容,ECUST-Jing Zhang,2,什么是聚類(lèi)分析? 聚類(lèi)分析中的數(shù)據(jù)類(lèi)型 主要的聚類(lèi)方法 劃分方法 層次方法 基于密度的方法 基于網(wǎng)格的方法 基于模型的方法 離群點(diǎn)分析 小結(jié),什么是聚類(lèi)分析？,3,簇: 一個(gè)數(shù)據(jù)對(duì)象的集合 在簇內(nèi)部，各個(gè)對(duì)象均極為相似 簇和簇之間，對(duì)象的差異明顯 聚類(lèi)分析 將物理或抽象對(duì)象的集合分組成為由類(lèi)似的對(duì)象組成的多個(gè)類(lèi)的過(guò)程被稱(chēng)為聚類(lèi)。 將一個(gè)對(duì)象集合劃分為多個(gè)類(lèi)或簇，在同一個(gè)簇中的對(duì)象之間具有較高的相似度，而不同簇中的對(duì)象差別較大。,ECUST-Jing Zhang,什么是聚類(lèi)分析？,聚類(lèi)是無(wú)監(jiān)督學(xué)習(xí)（u

2、nsupervised learning） 沒(méi)有預(yù)定義的類(lèi)別 觀察式學(xué)習(xí) 典型應(yīng)用 作為獨(dú)立工具（stand-alone tool），可表征數(shù)據(jù)分布 作為其他算法的預(yù)處理步驟（preprocessing step）,ECUST-Jing Zhang,4,5,聚類(lèi)的應(yīng)用場(chǎng)景,空間數(shù)據(jù)分析 在GIS中，通過(guò)對(duì)特征空間聚類(lèi)來(lái)創(chuàng)建主題地圖。 圖像處理 經(jīng)濟(jì)學(xué) (特別是市場(chǎng)研究) 城市規(guī)劃 氣候研究 WWW 文檔分類(lèi) 對(duì)Web日志進(jìn)行聚類(lèi)，從而發(fā)現(xiàn)相似的訪(fǎng)問(wèn)模式。 離群點(diǎn)檢測(cè) 信用卡欺詐檢測(cè)；監(jiān)控電子商務(wù)中的犯罪活動(dòng)等。,6,聚類(lèi)作為預(yù)處理工具,概括 可以作為回歸, PCA, 分類(lèi), 以及關(guān)聯(lián)分析的預(yù)處

3、理 壓縮 圖像處理: 矢量量化 找到K近鄰 局部搜索一個(gè)或少量的聚類(lèi),ECUST-Jing Zhang,什么是好的聚類(lèi)方法？,ECUST-Jing Zhang,7,一個(gè)好的聚類(lèi)方法將會(huì)產(chǎn)生高質(zhì)量的簇 高簇內(nèi)相似性：類(lèi)內(nèi)凝聚性 低簇間相似性：類(lèi)間區(qū)分性 判定一個(gè)聚類(lèi)方法質(zhì)量好壞依賴(lài)于 用于該聚類(lèi)方法的相似度度量 具體實(shí)現(xiàn)方法 能否發(fā)現(xiàn)部分或者所有隱藏的模式,數(shù)據(jù)挖掘?qū)垲?lèi)的要求,8,可伸縮性 處理不同類(lèi)型屬性的能力 數(shù)值型、二元類(lèi)型、分類(lèi)/標(biāo)稱(chēng)類(lèi)型、序數(shù)型。 發(fā)現(xiàn)任意形狀的聚類(lèi) 基于歐幾里德距離或曼哈頓距離，偏向于發(fā)現(xiàn)具有相近尺寸和密度的球狀簇 開(kāi)發(fā)其他類(lèi)型的其他度量 對(duì)于決定輸入?yún)?shù)的領(lǐng)域知識(shí)

4、需求最小 參數(shù)選擇,ECUST-Jing Zhang,數(shù)據(jù)挖掘?qū)垲?lèi)的要求,處理噪聲數(shù)據(jù)的能力 離群點(diǎn)、空缺值、未知數(shù)據(jù)、錯(cuò)誤數(shù)據(jù) 增量聚類(lèi)和對(duì)于輸入紀(jì)錄的順序不敏感 高維性 基于約束的聚類(lèi) 可解釋性和可用性,ECUST-Jing Zhang,9,10,聚類(lèi)方法研究的問(wèn)題,分割需求: 單層 vs. 多層 簇的分割: 排他的 vs. 非排他的 相似度度量: 距離 vs. 基于密度或區(qū)域的連通性 聚類(lèi)空間: 整個(gè)空間 vs. 子空間,主要內(nèi)容,ECUST-Jing Zhang,11,什么是聚類(lèi)分析? 聚類(lèi)分析中的數(shù)據(jù)類(lèi)型 主要的聚類(lèi)方法 劃分方法 層次方法 基于密度的方法 基于網(wǎng)格的方法 基于模型

5、的方法 離群點(diǎn)分析 小結(jié),不同數(shù)據(jù)類(lèi)型的距離度量,區(qū)間標(biāo)度變量: 粗略線(xiàn)性標(biāo)度的連續(xù)度量，如：重量，高度等 Minkowski Distance: Special cases: Euclidean (L2-norm), Manhattan (L1-norm),12,ECUST-Jing Zhang,不同數(shù)據(jù)類(lèi)型的距離度量,二元變量: 只有兩種狀態(tài)：0, 1 相異度計(jì)算：相異矩陣 對(duì)稱(chēng) vs. 非對(duì)稱(chēng) 對(duì)稱(chēng)二元變量：兩個(gè)狀態(tài)具有同等價(jià)值和相同的權(quán)重。 非對(duì)稱(chēng)二元變量：輸出的狀態(tài)不是同等重要的。 標(biāo)稱(chēng)變量（分類(lèi)變量）: 二元變量的推廣，可以取多個(gè)狀態(tài)值 相異度計(jì)算：不匹配變量的數(shù)目（或不匹配率）,

6、ECUST-Jing Zhang,13,14,不同數(shù)據(jù)類(lèi)型的距離度量,序數(shù)變量: 相異度計(jì)算：處理方法同區(qū)間標(biāo)度變量 比例標(biāo)度變量: 在非線(xiàn)性的刻度（例如指數(shù)刻度）取正的度量值 相異度計(jì)算：首先進(jìn)行對(duì)數(shù)變換 矢量: 相異度計(jì)算： cosine measure 混合類(lèi)型變量: 相異度計(jì)算： 按類(lèi)型分組，對(duì)每種類(lèi)型的變量進(jìn)行單獨(dú)的聚類(lèi)分析 將所有類(lèi)型的變量一起處理，只進(jìn)行一次聚類(lèi)分析,15,簇之間的距離,Single link: 一個(gè)簇中的對(duì)象和另一個(gè)簇中對(duì)象的最小距離, i.e., dist(Ki, Kj) = min(tip, tjq) Complete link:一個(gè)簇中的對(duì)象和另一個(gè)簇中對(duì)

7、象的最大距離, i.e., dist(Ki, Kj) = max(tip, tjq) Average:一個(gè)簇中的對(duì)象和另一個(gè)簇中對(duì)象的平均距離, i.e., dist(Ki, Kj) = avg(tip, tjq) Centroid: 兩個(gè)簇質(zhì)心之間的距離, i.e., dist(Ki, Kj) = dist(Ci, Cj) Medoid:兩個(gè)簇中心點(diǎn)之間的距離, i.e., dist(Ki, Kj) = dist(Mi, Mj) Medoid: a chosen, centrally located object in the cluster,16,一個(gè)簇的質(zhì)心（Centroid）, 半徑（

8、Radius）和直徑（Diameter） (對(duì)于數(shù)值數(shù)據(jù)集合),Centroid: the “middle” of a cluster Radius: square root of average distance from any point of the cluster to its centroid Diameter: square root of average mean squared distance between all pairs of points in the cluster,主要內(nèi)容,ECUST-Jing Zhang,17,什么是聚類(lèi)分析? 聚類(lèi)分析中的數(shù)據(jù)類(lèi)型 主要的

9、聚類(lèi)方法 劃分方法 層次方法 基于密度的方法 基于網(wǎng)格的方法 基于模型的方法 離群點(diǎn)分析 小結(jié),主要聚類(lèi)方法的分類(lèi),ECUST-Jing Zhang,18,劃分算法 構(gòu)造各種各樣的劃分,并用一些標(biāo)準(zhǔn)來(lái)評(píng)估它們 給定初始劃分?jǐn)?shù)目k，產(chǎn)生一個(gè)初始劃分，然后采用迭代的重定位技術(shù)，直到找到一個(gè)好的劃分。 層次算法 使用一些策略來(lái)進(jìn)行數(shù)據(jù)(或?qū)ο?集的層次分解 凝聚的和分裂的 缺點(diǎn)：不能被撤銷(xiāo) 改進(jìn) 在每層劃分中，仔細(xì)分析對(duì)象間的“聯(lián)接” 綜合層次凝聚和迭代的重定位方法,主要聚類(lèi)方法的分類(lèi),ECUST-Jing Zhang,19,基于密度的方法 基于連續(xù)和密度函數(shù) 只要臨近區(qū)域的密度（對(duì)象或數(shù)據(jù)點(diǎn)的數(shù)目

10、）超過(guò)某個(gè)閾值，就繼續(xù)聚類(lèi) 基于網(wǎng)格的方法 基于多層粒度結(jié)構(gòu) 把對(duì)象量化為有限數(shù)目的單元，形成一個(gè)網(wǎng)格結(jié)構(gòu)。聚類(lèi)操作在網(wǎng)格結(jié)構(gòu)（即量化的空間）上進(jìn)行。 處理時(shí)間獨(dú)立于數(shù)據(jù)對(duì)象數(shù)目，只與量化空間中每一維的單元數(shù)目有關(guān)。 基于模型的方法 為每個(gè)簇假設(shè)一個(gè)模型,尋找數(shù)據(jù)對(duì)給定模型的最佳擬合,主要聚類(lèi)方法的分類(lèi),其他類(lèi)型的聚類(lèi) 聚類(lèi)高維數(shù)據(jù) 子空間聚類(lèi)方法 基于頻繁模式的聚類(lèi) 基于約束的聚類(lèi) 存在障礙物的空間聚類(lèi) 用戶(hù)指定約束下的聚類(lèi) 半監(jiān)督聚類(lèi),ECUST-Jing Zhang,20,主要內(nèi)容,ECUST-Jing Zhang,21,什么是聚類(lèi)分析? 聚類(lèi)分析中的數(shù)據(jù)類(lèi)型 主要的聚類(lèi)方法 劃分方法

11、層次方法 基于密度的方法 基于網(wǎng)格的方法 基于模型的方法 離群點(diǎn)分析 小結(jié),劃分方法：基本概念,22,劃分方法: 基于一個(gè)n個(gè)對(duì)象或元組的數(shù)據(jù)庫(kù)，構(gòu)建數(shù)據(jù)的k個(gè)劃分，每個(gè)劃分表示一個(gè)簇，k=n 給定一個(gè)k，找到一個(gè)劃分方法，含k個(gè)簇，并且這個(gè)劃分是最優(yōu)的。 全局最優(yōu): 需要窮舉所有可能的劃分 啟發(fā)式方法: k-means和k-medoids算法 k-means : 每個(gè)簇用該簇中對(duì)象的平均值來(lái)表示 k-medoids or PAM (Partition around medoids): 每個(gè)簇用接近聚類(lèi)中心的一個(gè)對(duì)象來(lái)表示,ECUST-Jing Zhang,22,K-Means聚類(lèi)方法,K均值

12、的處理流程如下： 隨機(jī)選擇k個(gè)對(duì)象，每個(gè)對(duì)象初始地代表了一個(gè)簇的平均值或中心 對(duì)剩余每個(gè)對(duì)象，根據(jù)其與各個(gè)簇中心的距離，將它賦給最近的簇。 重新計(jì)算每個(gè)簇的平均值。 這個(gè)過(guò)程不斷重復(fù)，直到簇不再發(fā)生變化或準(zhǔn)則函數(shù)收斂。 平方誤差準(zhǔn)則 P是空間中的點(diǎn)，mi是簇Ci的平均值,ECUST-Jing Zhang,23,24,K-Means聚類(lèi)方法,舉例,0,1,2,3,4,5,6,7,8,9,10,0,1,2,3,4,5,6,7,8,9,10,K=2 任意選擇K 個(gè)對(duì)象作為初始化類(lèi)中心,把每個(gè)對(duì)象歸為最相似的中心,更新簇的均值,更新簇的均值,重新指派,重新指派,K-Means聚類(lèi)方法,ECUST-Ji

13、ng Zhang,25,優(yōu)點(diǎn) 復(fù)雜度: O(nkt), 其中n 是對(duì)象的數(shù)目, k 是簇的數(shù)目, t 是迭代的次數(shù). 通常k, t n. 相對(duì)可伸縮和高效。 通常以局部最優(yōu)結(jié)束。 缺點(diǎn) 只有在簇的平均值被定義的情況下才能使用，當(dāng)涉及有分類(lèi)屬性的數(shù)據(jù)時(shí)無(wú)法處理 需要事先給出k，簇的數(shù)目 對(duì)噪聲和離群點(diǎn)數(shù)據(jù)敏感 不適合發(fā)現(xiàn)非凸形狀的簇，或者大小差別很大的簇,K-Means方法的變種,ECUST-Jing Zhang,26,有許多k-means算法的變種，區(qū)別在于 初始k個(gè)平均值的選擇 相異度的計(jì)算 計(jì)算聚類(lèi)平均值的策略 處理分類(lèi)數(shù)據(jù): k-眾數(shù)方法（k-modes (Huang98)） 用眾數(shù)代替

14、簇的平均值 采用新的相異度度量 采用基于頻率的方法更新簇眾數(shù) 混合處理分類(lèi)和數(shù)值數(shù)據(jù): k-原型方法（k-prototype） 將k-均值和k-眾數(shù)方法綜合起來(lái),27,K-Means 方法存在的問(wèn)題?,k-means 算法對(duì)離群點(diǎn)非常敏感! 因?yàn)閾碛袠O端值的對(duì)象將在很大程度上影響數(shù)據(jù)的分布。 K-Medoids: 用中心點(diǎn)（位于簇最中心位置的對(duì)象）而不是簇中對(duì)象的平均值作為參考點(diǎn)。,K-Medoids 聚類(lèi)算法,ECUST-Jing Zhang,28,在各個(gè)簇中找到最有代表性的對(duì)象，即中心點(diǎn)（medoids） 基本策略 為每個(gè)簇隨意選擇一個(gè)代表對(duì)象 剩余的對(duì)象按照它跟代表對(duì)象的距離分配給最近的

15、一個(gè)簇 然后反復(fù)地用非代表對(duì)象替代代表對(duì)象，以改進(jìn)聚類(lèi)質(zhì)量。 方法 PAM (Partitioning Around Medoids, 1987) 從一個(gè)初始的集合開(kāi)始，循環(huán)利用non-medoids替換medoids，看看是否能夠提高各個(gè)簇的性能 PAM 處理小數(shù)據(jù)集合時(shí)非常有效，但是處理大數(shù)據(jù)集合時(shí)卻并不很有效 CLARA (Kaufmann & Rousseeuw, 1990)：基于抽樣的PAM CLARANS (Ng & Han, 1994): 隨機(jī)的樣本,PAM (Partitioning Around Medoids),ECUST-Jing Zhang,29,PAM (Partit

16、ioning Around Medoids, Kaufman and Rousseeuw, 1987) 算法： 隨機(jī)選擇k個(gè)對(duì)象作為初始的中心點(diǎn) Repeat 指派每個(gè)剩余的對(duì)象給離它最近的中心點(diǎn)所代表的簇； 隨機(jī)地選擇一個(gè)非中心點(diǎn)對(duì)象Oh； 計(jì)算用Oh代替Oi的總代價(jià)(total swapping cost)TCih； If TCih0, then Oh替換Oi，形成新的k個(gè)中心點(diǎn)的集合； Until 不發(fā)生變化,k-Means與k-Medoids,ECUST-Jing Zhang,30,當(dāng)存在噪聲或離群點(diǎn)數(shù)據(jù)時(shí)，k-Medoids方法比k-Means方法更健壯，因?yàn)橹行狞c(diǎn)不象平均值那么容易

17、被極端數(shù)據(jù)影響 K-Medoids方法執(zhí)行代價(jià)比k-Means高 K-Medoids方法不具有良好的可伸縮性 二者均要求指定結(jié)果簇的數(shù)目k,CLARA(Clustering Large Applications),ECUST-Jing Zhang,31,基于抽樣的方法 抽取數(shù)據(jù)集合的多個(gè)樣本，對(duì)每個(gè)樣本應(yīng)用PAM算法，返回最好的聚類(lèi)結(jié)果作為輸出 優(yōu)點(diǎn) 能處理規(guī)模較大的數(shù)據(jù)集 缺點(diǎn) 有效性取決于樣本的大小 如果樣本發(fā)生偏斜，基于樣本的好的聚類(lèi)不一定代表了整個(gè)數(shù)據(jù)集合的一個(gè)好的聚類(lèi),CLARANS (Clustering Large Application based upon RANdomize

18、d Search),將采樣技術(shù)同PAM相結(jié)合，隨機(jī)化的“CLARA” CLARANS 動(dòng)態(tài)的從近鄰中抽取樣本 聚類(lèi)的過(guò)程可以被描述為對(duì)一個(gè)圖的搜索，圖中的每一個(gè)結(jié)點(diǎn)是一個(gè)潛在的解，也就是說(shuō)，k個(gè)中心點(diǎn)的集合 如果發(fā)現(xiàn)局部最優(yōu)，CLARANS從新的任意選擇的結(jié)點(diǎn)開(kāi)始尋找新的局部最優(yōu) CLARANS能夠探測(cè)離群點(diǎn)，聚類(lèi)質(zhì)量取決于抽樣算法 計(jì)算復(fù)雜度 利用空間數(shù)據(jù)結(jié)構(gòu)的聚焦技術(shù)可以進(jìn)一步改善CLARANS的性能,ECUST-Jing Zhang,32,主要內(nèi)容,ECUST-Jing Zhang,33,什么是聚類(lèi)分析? 聚類(lèi)分析中的數(shù)據(jù)類(lèi)型 主要的聚類(lèi)方法 劃分方法 層次方法 基于密度的方法 基于網(wǎng)格

19、的方法 基于模型的方法 離群點(diǎn)分析 小結(jié),層次聚類(lèi),ECUST-Jing Zhang,34,使用距離矩陣作為聚類(lèi)的標(biāo)準(zhǔn)。這種方法不需要簇的數(shù)目k作為輸入,但需要一個(gè)終止條件 兩種類(lèi)型的層次聚類(lèi)方法 凝聚的層次聚類(lèi) 自底向上 首先將每個(gè)對(duì)象作為一個(gè)簇，然后合并這些原子簇為越來(lái)越大的簇，直到所有對(duì)象都在一個(gè)簇中，或滿(mǎn)足終止條件。 分裂的層次聚類(lèi) 自頂向下 首先將所有對(duì)象置于一個(gè)簇中，然后逐漸細(xì)分，直到每個(gè)對(duì)象自成一簇，或達(dá)到某個(gè)終止條件。,層次聚類(lèi),ECUST-Jing Zhang,35,AGNES (Agglomerative Nesting),ECUST-Jing Zhang,36,凝聚層次聚

20、類(lèi) 使用單鏈接（ single-link ）方法和相異矩陣 合并最小相異的結(jié)點(diǎn) 以一個(gè)非下降的模式進(jìn)行 最終所有的結(jié)點(diǎn)屬于同一個(gè)簇,DIANA (Divisive Analysis),ECUST-Jing Zhang,37,分裂層次聚類(lèi) 與AGNES算法相反 最終每一個(gè)結(jié)點(diǎn)形成只包含它本身的簇,層次聚類(lèi),ECUST-Jing Zhang,38,四個(gè)廣泛采用的簇間距離度量 最小距離 最大距離 均值距離 平均距離,更多關(guān)于層次聚類(lèi)方法,凝聚的層次聚類(lèi)方法的主要缺點(diǎn) 伸縮性不夠好: 時(shí)間復(fù)雜度最小為 ，這里n是全體對(duì)象的數(shù)目 先前已做的處理不能被撤銷(xiāo) 層次聚類(lèi)和基于距離聚類(lèi)的集成 BIRCH (19

21、96): 使用CF樹(shù)，增量的調(diào)整子聚類(lèi)的質(zhì)量 ROCK (1998): 基于簇間的互聯(lián)性進(jìn)行合并 CHAMELEON (1999): 采用動(dòng)態(tài)模型的聚類(lèi)方法,ECUST-Jing Zhang,39,40,BIRCH,BIRCH: 利用層次方法的平衡迭代歸約和聚類(lèi) Zhang, Ramakrishnan, Livny(SIGMOD96) 綜合的層次聚類(lèi)方法 聚類(lèi)特征（CF）：三元組，給出對(duì)象子聚類(lèi)的信息的匯總描述。 假設(shè)某個(gè)子聚類(lèi)中有N個(gè)d維多點(diǎn)或?qū)ο?，則該子聚類(lèi)的CF定義如下： N是子類(lèi)中點(diǎn)的數(shù)目， 是N個(gè)點(diǎn)的線(xiàn)性和（即 ），ss是數(shù)據(jù)點(diǎn)的平方和（即 ） 聚類(lèi)特征樹(shù)（CF樹(shù)） 高度平衡的樹(shù)，

22、存儲(chǔ)了層次聚類(lèi)的聚類(lèi)特征 一個(gè)CF樹(shù)有兩個(gè)參數(shù)：分支因子B，和閾值T。分支因子定義了每個(gè)非葉節(jié)點(diǎn)孩子的最大數(shù)目，而閾值參數(shù)給出了存儲(chǔ)在樹(shù)的葉子節(jié)點(diǎn)中的子聚類(lèi)的最大直徑。,聚類(lèi)特征,ECUST-Jing Zhang,41,CF 樹(shù),ECUST-Jing Zhang,42,43,Birch 算法,簇的直徑 對(duì)于輸入的每一個(gè)點(diǎn) 找到距離其最近的葉子 增加該點(diǎn)到該葉子結(jié)點(diǎn)并更新CF 如果該葉子結(jié)點(diǎn)直徑大于最大直徑，則分裂該葉子結(jié)點(diǎn)。 算法的復(fù)雜度為O(n) 值得注意的幾個(gè)問(wèn)題 該算法對(duì)數(shù)據(jù)的插入順序敏感 因?yàn)楣潭巳~節(jié)點(diǎn)的大小，因此聚類(lèi)的結(jié)果可能會(huì)不太自然 因?yàn)榻o定了半徑和直徑的度量，形成的簇趨向于球

23、形,BIRCH,ECUST-Jing Zhang,44,增量的構(gòu)造CF（聚類(lèi)特征）樹(shù),CF樹(shù)是一個(gè)用于多階段聚類(lèi)的層次數(shù)據(jù)結(jié)構(gòu) 階段1: 掃描數(shù)據(jù)庫(kù)，建立一個(gè)初始存放于內(nèi)存的CF樹(shù)，它可以被看作數(shù)據(jù)的多層壓縮，試圖保留數(shù)據(jù)內(nèi)在的聚類(lèi)結(jié)構(gòu) 階段2: 使用某個(gè)聚類(lèi)算法對(duì)CF樹(shù)的葉結(jié)點(diǎn)進(jìn)行聚類(lèi) 優(yōu)點(diǎn) 線(xiàn)形伸縮性 支持增量聚類(lèi) 缺點(diǎn) 只能處理數(shù)值數(shù)據(jù)，對(duì)數(shù)據(jù)記錄的順序很敏感,聚類(lèi)分類(lèi)數(shù)據(jù):ROCK,ECUST-Jing Zhang,45,ROCK(Robust Clustering using linKs) 由S. Guha, R. Rastogi, K. Shim (ICDE99)提出，是一個(gè)凝聚的

24、層次聚類(lèi)算法，適用于分類(lèi)屬性。 通過(guò)將聚集的互連性與用戶(hù)定義的靜態(tài)互連性模型相比較來(lái)度量?jī)蓚€(gè)簇的相似度 鏈接-兩個(gè)對(duì)象間共同的近鄰數(shù)目。 簇間相似度用“鏈接”來(lái)描述，即來(lái)自于不同簇而有相同近鄰的點(diǎn)的數(shù)目。 思想 ROCK首先根據(jù)相似度閾值和共享近鄰的概念從給定的數(shù)據(jù)相似度矩陣構(gòu)建一個(gè)稀疏的圖，然后再這個(gè)稀疏圖上執(zhí)行一個(gè)層次聚類(lèi)算法,CHAMELEON,ECUST-Jing Zhang,46,CHAMELEON 由G. Karypis, E.H. Han和V. Kumar99 提出的，使用動(dòng)態(tài)模型的層次聚類(lèi) 在動(dòng)態(tài)模型的基礎(chǔ)上度量相似性 兩個(gè)簇被合并當(dāng)且僅當(dāng)簇間的互連性和近似度與簇內(nèi)部對(duì)象間的互

25、連性和近似度高度相關(guān) 既考慮了互連性，又考慮了簇間的近似度。 一個(gè)兩步的算法 使用一個(gè)圖劃分算法: 把對(duì)象聚類(lèi)到相對(duì)較小的子聚類(lèi) 使用一個(gè)凝聚的聚類(lèi)層次算法: 通過(guò)反復(fù)合并這些子聚類(lèi)來(lái)找到真正的聚類(lèi)簇,CHAMELEON的總體框架,ECUST-Jing Zhang,47,K-NN Graph P and q are connected if q is among the top k closest neighbors of p,Relative interconnectivity: connectivity of c1 and c2 over internal connectivity Rel

26、ative closeness: closeness of c1 and c2 over internal closeness,主要內(nèi)容,ECUST-Jing Zhang,48,什么是聚類(lèi)分析? 聚類(lèi)分析中的數(shù)據(jù)類(lèi)型 主要的聚類(lèi)方法 劃分方法 層次方法 基于密度的方法 基于網(wǎng)格的方法 基于模型的方法 離群點(diǎn)分析 小結(jié),基于密度的聚類(lèi)方法,ECUST-Jing Zhang,49,該類(lèi)方法把簇看作是數(shù)據(jù)空間中被低密度區(qū)域分割開(kāi)的高密度對(duì)象區(qū)域?；诿芏鹊拇厥敲芏认噙B的點(diǎn)的集合 主要特點(diǎn) 能夠發(fā)現(xiàn)任意形狀的簇 能處理噪聲 只需一次掃描 需要密度參數(shù)作為終結(jié)條件 研究成果 DBSCAN:Ester,

27、et al. (KDD96) OPTICS: Ankerst, et al (SIGMOD99). DENCLUE: Hinneburg& D. Keim (KDD98) CLIQUE: Agrawal, et al. (SIGMOD98),基于密度的聚類(lèi): 背景,ECUST-Jing Zhang,50,兩個(gè)參數(shù)： : 鄰域的最大半徑 MinPts: 一個(gè)對(duì)象的-鄰域至少包含的對(duì)象數(shù) N(p):q D | dist(p,q) = MinPts,基于密度的聚類(lèi): 背景(II),ECUST-Jing Zhang,51,密度可達(dá)的 一個(gè)對(duì)象p從對(duì)象q關(guān)于和MinPts是密度可達(dá)的，如果存在一個(gè)對(duì)象鏈

28、p1, , pn, p1= q, pn= p，pi+1是從pi關(guān)于和MinPts直接密度可達(dá)的 密度相連的 如果存在一個(gè)對(duì)象o，使得對(duì)象p和q是從o關(guān)于和MinPts密度可達(dá)的，那么對(duì)象關(guān)于p和q是關(guān)于和MinPts密度相連的,52,DBSCAN: 一個(gè)基于高密度連接區(qū)域的密度聚類(lèi)方法,（DBSCAND）ensity-Based Spatial Clustering of Applications with Noise 該算法將具有足夠高密度的區(qū)域劃分為簇，能夠在帶有“噪聲”的空間數(shù)據(jù)庫(kù)中發(fā)現(xiàn)任意形狀的聚類(lèi) 它定義簇為密度相連的點(diǎn)的最大集合,DBSCAN算法,ECUST-Jing Zhang,

29、53,算法 DBSCAN通過(guò)檢查數(shù)據(jù)庫(kù)中每個(gè)點(diǎn)的-鄰域來(lái)尋找聚類(lèi)。 如果一個(gè)點(diǎn)p的-鄰域包含多于MinPts個(gè)點(diǎn)，則創(chuàng)建一個(gè)以p作為核心對(duì)象的新簇。 DBSCAN反復(fù)尋找從這些核心對(duì)象直接密度可達(dá)的對(duì)象，并合并一些密度可達(dá)的簇。 當(dāng)沒(méi)有新的點(diǎn)可以被添加到任何簇時(shí)，結(jié)束。,54,DBSCAN: 對(duì)參數(shù)十分敏感,OPTICS: 簇次序方法(1999),ECUST-Jing Zhang,55,OPTICS(Order Points to Identify the Clustering Structure): 通過(guò)點(diǎn)排序識(shí)別聚類(lèi)結(jié)構(gòu) 不顯式地產(chǎn)生數(shù)據(jù)集聚類(lèi)，而是為自動(dòng)和交互的聚類(lèi)分析計(jì)算一個(gè)增廣的簇排

30、序（cluster ordering）。 簇排序包含的信息，等同于從一個(gè)廣泛的參數(shù)設(shè)置所獲得的基于密度的聚類(lèi)。 簇排序可以用來(lái)提取基本的聚類(lèi)信息（如簇中心，任意形狀的簇），也可以提供內(nèi)在的聚類(lèi)結(jié)構(gòu)。 該算法對(duì)自動(dòng)的和交互式聚類(lèi)分析（包括找出內(nèi)在的聚類(lèi)結(jié)構(gòu)）很有用 可以用圖形或使用可視化技術(shù)表示,56,OPTICS: 對(duì)DBSCAN的擴(kuò)展,在OPTICS中，每個(gè)對(duì)象需要存儲(chǔ)兩個(gè)值核心距離和可達(dá)距離。 核心距離: 使p成為核心對(duì)象的最小eps距離 可達(dá)距離： 對(duì)象p關(guān)于對(duì)象o的可達(dá)距離是o的核心距離和p與o之間的歐幾里得距離的較大值,D,p2,MinPts = 5 e = 3 cm,Max (co

31、re-distance (o), d (o, p) r(p1, o) = 2.8cm. r(p2,o) = 4cm,o,o,p1,OPTICS: 對(duì)DBSCAN的擴(kuò)展,OPTICS算法創(chuàng)建了數(shù)據(jù)庫(kù)中對(duì)象的排序，額外存儲(chǔ)了每個(gè)對(duì)象的核心距離和相應(yīng)的可達(dá)距離。 已經(jīng)提出了一種算法，基于OPTICS產(chǎn)生的排序信息來(lái)提取簇。 對(duì)于小于用于生成該排序的距離的距離，提取所有基于密度的聚類(lèi)，這些信息是足夠的。 OPTICS與DBSCAN具有相同的時(shí)間復(fù)雜度。,ECUST-Jing Zhang,57,主要內(nèi)容,ECUST-Jing Zhang,58,什么是聚類(lèi)分析? 聚類(lèi)分析中的數(shù)據(jù)類(lèi)型 主要的聚類(lèi)方法 劃分

32、方法 層次方法 基于密度的方法 基于網(wǎng)格的方法 基于模型的方法 離群點(diǎn)分析 小結(jié),59,基于網(wǎng)格的聚類(lèi)方法,使用一個(gè)多分辨率的網(wǎng)格數(shù)據(jù)結(jié)構(gòu) 將空間量化為有限數(shù)目的單元，這些單元形成了網(wǎng)格結(jié)構(gòu)，所有的聚類(lèi)操作都在網(wǎng)格上進(jìn)行。 優(yōu)點(diǎn) 處理速度快，處理速度獨(dú)立于對(duì)象數(shù)目，僅依賴(lài)于量化空間中每一維上的單元數(shù)目。 幾種代表性的方法 STING (a STatisticalINformationGrid approach)由Wang, Yang 和Muntz在1997年提出 基于網(wǎng)格的多分辨率聚類(lèi)技術(shù) WaveCluster：Sheikholeslami,Chatterjee(VLDB98) 一個(gè)采用小波

33、變換方法的多分辨率聚類(lèi)算法 CLIQUE: Agrawal, et al. (SIGMOD98) 綜合了基于密度和基于網(wǎng)格的聚類(lèi)方法,STING: 統(tǒng)計(jì)信息網(wǎng)格方法,ECUST-Jing Zhang,60,(STING)STatistical INformation Grid, 由Wang, Yang 和Muntz提出(VLDB97) 基于網(wǎng)格的多分辨率聚類(lèi)技術(shù) 將空間區(qū)域劃分成矩形單元 針對(duì)不同級(jí)別的分辨率，通常存在不同級(jí)別的矩形單元,STING:統(tǒng)計(jì)信息網(wǎng)格方法,ECUST-Jing Zhang,61,高層的每個(gè)單元被劃分成多個(gè)低一層的單元 每個(gè)單元屬性的統(tǒng)計(jì)信息被預(yù)先計(jì)算和存儲(chǔ)，這對(duì)查詢(xún)

34、處理是有用的 高層單元的統(tǒng)計(jì)參數(shù)很容易從低層單元的計(jì)算得到，這些參數(shù)包括： Count（計(jì)數(shù)）, mean（平均值）, s（標(biāo)準(zhǔn)差）, min（最小值）, max（最大值） 分布類(lèi)型: 正態(tài)分布，均勻分布，指數(shù)分布等等,STING:統(tǒng)計(jì)信息網(wǎng)格方法,ECUST-Jing Zhang,62,使用自頂向下的方法回答空間數(shù)據(jù)的查詢(xún) 從一個(gè)預(yù)先選擇的層次開(kāi)始-通常包含少量的單元 為當(dāng)前層的每個(gè)單元計(jì)算置信區(qū)間 不相關(guān)的單元不再考慮 當(dāng)檢查完當(dāng)前層，接著檢查下一個(gè)低層次 重復(fù)這個(gè)過(guò)程直到達(dá)到底層 優(yōu)點(diǎn) 獨(dú)立于查詢(xún)，易于并行處理和增量更新 查詢(xún)處理時(shí)間O(k),其中k是最底層網(wǎng)格單元的數(shù)目 缺點(diǎn) 所有的聚

35、類(lèi)邊界或者是水平的，或者是垂直的，沒(méi)有對(duì)角的邊界,63,WaveCluster: 利用小波變換聚類(lèi),Sheikholeslami, Chatterjee, and Zhang (VLDB98) 將小波變換應(yīng)用到特征空間，基于網(wǎng)格和基于密度的聚類(lèi)算法。 小波變換：一種信號(hào)處理技術(shù)，它將一個(gè)信號(hào)分解為不同頻率的子波段。 數(shù)據(jù)被轉(zhuǎn)換后，在不同的分辨率水平依然保持對(duì)象間的相對(duì)距離 使得數(shù)據(jù)的自然簇變得更加容易區(qū)分,64,The WaveCluster Algorithm,如何利用小波變換找到聚類(lèi) 在數(shù)據(jù)空間用多維網(wǎng)格結(jié)構(gòu)概括數(shù)據(jù) 多維的空間數(shù)據(jù)對(duì)象被表示成n維特征空間 在特征空間上運(yùn)用小波變換找到密度

36、區(qū)域 多次運(yùn)用小波變換在不同尺度上進(jìn)行數(shù)據(jù)聚類(lèi) 主要特征 計(jì)算復(fù)雜度 O(N) 能夠在不同尺度上找到任意形狀的聚類(lèi) 對(duì)噪音不敏感，對(duì)輸入順序也不敏感 僅應(yīng)用于低維數(shù)據(jù),CLIQUE ：聚類(lèi)高維空間,ECUST-Jing Zhang,65,CLIQUE（CLustering In QUEst） 高維空間中維增長(zhǎng)子空間聚類(lèi)算法 綜合了基于密度和基于網(wǎng)格的聚類(lèi)方法 通過(guò)自動(dòng)識(shí)別高維數(shù)據(jù)空間的子空間，來(lái)達(dá)到比在原空間更好聚類(lèi)的目的 CLIQUE的中心思想 區(qū)分空間中稀疏的和“擁擠的”區(qū)域（或單元），以發(fā)現(xiàn)數(shù)據(jù)集合的全局分布模式 簇定義為互連的稠密單元的最大集合。,CLIQUE ：聚類(lèi)高維空間,CLIQ

37、UE 分兩步進(jìn)行多維聚類(lèi) 把一個(gè)n維的數(shù)據(jù)空間劃分為互不相交的矩形單元，識(shí)別其中的稠密單元。 一個(gè)單元是稠密的，如果包含在這個(gè)單元的數(shù)據(jù)點(diǎn)的總數(shù)超過(guò)了某個(gè)輸入的模型參數(shù)值 如果一個(gè)k維單元是稠密的，則該單元在k-1維子空間的投影也是稠密的。 為每個(gè)簇生成一個(gè)最小描述。 對(duì)每個(gè)簇，確定覆蓋連通稠密單元簇的最大區(qū)域 然后為每個(gè)簇確定一個(gè)最小覆蓋,ECUST-Jing Zhang,66,ECUST-Jing Zhang,67,CLIQUE的優(yōu)缺點(diǎn),ECUST-Jing Zhang,68,優(yōu)點(diǎn) 自動(dòng)的發(fā)現(xiàn)最高維的子空間，高密度聚類(lèi)存在于這些子空間中 對(duì)元組的輸入順序不敏感，無(wú)需假設(shè)任何規(guī)范的數(shù)據(jù)分布

38、它隨輸入數(shù)據(jù)的大小線(xiàn)性地?cái)U(kuò)展，當(dāng)數(shù)據(jù)的維增加時(shí)具有很好的可伸縮性 缺點(diǎn) 由于方法大大簡(jiǎn)化，聚類(lèi)結(jié)果的精確性可能會(huì)降低,主要內(nèi)容,ECUST-Jing Zhang,69,什么是聚類(lèi)分析? 聚類(lèi)分析中的數(shù)據(jù)類(lèi)型 主要的聚類(lèi)方法 劃分方法 層次方法 基于密度的方法 基于網(wǎng)格的方法 基于模型的方法 離群點(diǎn)分析 小結(jié),基于模型的方法,ECUST-Jing Zhang,70,基于模型的聚類(lèi)方法通常假定數(shù)據(jù)具備一定的概率分布，并通過(guò)優(yōu)化給定的數(shù)據(jù)，使其適應(yīng)某些數(shù)學(xué)模型，并基于此產(chǎn)生聚類(lèi)。 基于模型的方法主要有兩類(lèi) 統(tǒng)計(jì)學(xué)方法 期望最大化方法EM (Expectation maximization) 神經(jīng)網(wǎng)絡(luò)

39、方法 自組織特征映射SOM（ Self-Organizing Feature Map ）,71,混合密度模型（Mixture Models）,每個(gè)簇都可以用概率分布模型來(lái)描述 實(shí)際上，假定任何一個(gè)分布都可以用多參數(shù)正態(tài)分布來(lái)很好的近似 多個(gè)簇是不同概率分布的混合。 整個(gè)數(shù)據(jù)集就是這些模型的混合。,72,對(duì)象概率,假定有k個(gè)聚類(lèi)和一個(gè)有m個(gè)對(duì)象的集合X 令第j個(gè)聚類(lèi)包含參數(shù)j = (j, j) 一個(gè)點(diǎn)在第j個(gè)聚類(lèi)中的概率是wj, 其中 w1 + + wk = 1 對(duì)象x的概率為,73,例子,74,最大似然估計(jì)（Maximal Likelihood Estimation）,最大似然定律: 如果知道

40、一組對(duì)象來(lái)自一個(gè)分布，但是不知道其中的參數(shù)，可以選擇參數(shù)最大化這個(gè)概率。 最大化 等同于最大化,75,The EM (Expectation Maximization) Algorithm,期望最大化算法 選擇模型參數(shù)的一個(gè)初始化集合 Repeat 期望步: 對(duì)每一個(gè)對(duì)象，計(jì)算對(duì)象xi隸屬于每一個(gè)分布概率i的概率，即, prob(xi|i) 最大化步: 利用前面得到的概率估計(jì)重新估計(jì)模型參數(shù)，對(duì)給定數(shù)據(jù)的分布似然“最大化” Until 參數(shù)趨于穩(wěn)定,76,優(yōu)缺點(diǎn),優(yōu)點(diǎn) 混合模型比k-means更通用 簇能夠被極少的幾個(gè)參數(shù)刻畫(huà) 缺點(diǎn) 計(jì)算代價(jià)高 需要大的數(shù)據(jù)集合 很難估計(jì)簇的數(shù)目,77,神經(jīng)網(wǎng)

41、絡(luò)方法,神經(jīng)網(wǎng)絡(luò)方法 將每個(gè)簇描述成一個(gè)標(biāo)本，充當(dāng)簇的“原型”。 根據(jù)某種距離度量，新對(duì)象被分配到其標(biāo)本最相似的簇。 典型方法 SOM (Soft-Organizing feature Map)自組織特征映射,78,自組織特征映射(SOM),SOM, 也稱(chēng)作拓?fù)溆行蛴成?或 Kohonen 自組織特征映射 (KSOM) 它將所有高維空間的點(diǎn)映射至2到3維的目標(biāo)空間，并盡可能保留其距離和近似關(guān)系（即拓?fù)洌?類(lèi)似于 k-means: 聚類(lèi)中心趨向于位于特征空間的低維流形中。 聚類(lèi)通過(guò)若干單元競(jìng)爭(zhēng)當(dāng)前對(duì)象來(lái)進(jìn)行 權(quán)重向量最接近當(dāng)前對(duì)象的單元成為贏家或活躍單元 為了更接近輸入對(duì)象，調(diào)整獲勝單元及其最近

42、鄰的權(quán)重 SOM 被認(rèn)為類(lèi)似于大腦的處理過(guò)程 對(duì)在二維或三維空間中可視化高維數(shù)據(jù)是有用的,79,利用SOM的Web文檔挖掘,用SOM對(duì)12088篇網(wǎng)絡(luò)文章聚類(lèi)的結(jié)果 右圖: 關(guān)鍵詞“mining”進(jìn)行下鉆挖掘的結(jié)果 數(shù)據(jù)來(lái)源websom.hut.fi Web page,主要內(nèi)容,ECUST-Jing Zhang,80,什么是聚類(lèi)分析? 聚類(lèi)分析中的數(shù)據(jù)類(lèi)型 主要的聚類(lèi)方法 劃分方法 層次方法 基于密度的方法 基于網(wǎng)格的方法 基于模型的方法 離群點(diǎn)分析 小結(jié),81,什么是離群點(diǎn)發(fā)現(xiàn)?,什么是離群點(diǎn)? 和其它數(shù)據(jù)不同或不一致的對(duì)象集 問(wèn)題 找出n個(gè)離群點(diǎn) 方法 統(tǒng)計(jì)學(xué)方法 基于距離的方法 基于偏移

43、的方法 應(yīng)用 信用卡的欺詐監(jiān)測(cè) 電信的欺詐監(jiān)測(cè) 顧客分類(lèi) 醫(yī)療分析,基于統(tǒng)計(jì)的離群點(diǎn) 檢測(cè),ECUST-Jing Zhang,82,對(duì)給定的數(shù)據(jù)集合假設(shè)了一個(gè)分布或概率模型（例如一個(gè)正態(tài)分布） 使用不和諧檢驗(yàn)（discordancy test）識(shí)別離群點(diǎn)。 需要的知識(shí)包括： 數(shù)據(jù)集參數(shù)知識(shí)（例如數(shù)據(jù)分布） 分布參數(shù)(例如平均值和方差) 預(yù)期的離群點(diǎn)的數(shù)目 缺點(diǎn) 大部分的檢驗(yàn)都是對(duì)單個(gè)屬性的 在很多情況下，數(shù)據(jù)分布是未知的,基于距離的離群點(diǎn)檢測(cè),ECUST-Jing Zhang,83,為了解決統(tǒng)計(jì)學(xué)方法帶來(lái)的一些限制，引入了基于距離的離群點(diǎn)的概念 需要在不知道數(shù)據(jù)分布的情況下進(jìn)行多維分析 將離群

44、點(diǎn)看作是那些沒(méi)有足夠多“鄰居”的對(duì)象 基于距離的離群點(diǎn): 基于距離的離群點(diǎn)，即DB(p, D)，是指數(shù)據(jù)集T中的一個(gè)對(duì)象O，使得T中對(duì)象至少有p部分與對(duì)象O的距離大于D 基于距離離群點(diǎn)的挖掘算法 基于索引的算法 嵌套循環(huán)算法 基于單元的算法,基于偏差的離群點(diǎn)檢測(cè),ECUST-Jing Zhang,84,通過(guò)檢查一組對(duì)象的主要特征來(lái)確定離群點(diǎn) 與給出的描述“偏離”的對(duì)象稱(chēng)為離群點(diǎn) 兩種技術(shù) 順序異常技術(shù) 模仿了人類(lèi)從一系列推測(cè)類(lèi)似的對(duì)象中識(shí)別異常對(duì)象的方式 OLAP 數(shù)據(jù)立方體技術(shù) 使用數(shù)據(jù)立方體來(lái)確定大規(guī)模的多維數(shù)據(jù)中的反常區(qū)域,主要內(nèi)容,ECUST-Jing Zhang,85,什么是聚類(lèi)分析

45、? 聚類(lèi)分析中的數(shù)據(jù)類(lèi)型 主要的聚類(lèi)方法 劃分方法 層次方法 基于密度的方法 基于網(wǎng)格的方法 基于模型的方法 離群點(diǎn)分析 小結(jié),小結(jié),ECUST-Jing Zhang,86,主要的聚類(lèi)方法 劃分方法:k-means,k-mediods,CLARA，CLARANS 層次方法: BIRCH,ROCK 基于密度的方法: DBSCAN, OPTICS 基于網(wǎng)格的方法: STING, CLIQUE 基于模型的方法：EM，SOM,小結(jié),ECUST-Jing Zhang,87,聚類(lèi)分析組合而成的對(duì)象基于它們的相似性有很廣泛的應(yīng)用 相異度可以用多種類(lèi)型的數(shù)據(jù)來(lái)計(jì)算 聚類(lèi)算法可以分為劃分方法,層次方法,基于密度

46、的方法,基于方格的方法和基于模型的方法 離群點(diǎn)探測(cè)和分析對(duì)于欺詐探測(cè)等非常有用,可以用統(tǒng)計(jì)學(xué)方法,基于距離的方法和基于偏差的方法來(lái)實(shí)現(xiàn) 在聚類(lèi)分析上仍舊存在許多研究問(wèn)題,如基于約束的聚類(lèi),參考文獻(xiàn)（1）,ECUST-Jing Zhang,88,R. Agrawal, J. Gehrke, D. Gunopulos, and P. Raghavan. Automatic subspace clustering of high dimensional data for data mining applications. SIGMOD98 M. R. Anderberg. Cluster Analy

47、sis for Applications. Academic Press, 1973. M. Ankerst, M. Breunig, H.-P. Kriegel, and J. Sander. Optics: Ordering points to identify the clustering structure, SIGMOD99. P. Arabie, L. J. Hubert, and G. De Soete. Clustering and Classification. World Scietific, 1996 M. Ester, H.-P. Kriegel, J. Sander,

48、 and X. Xu. A density-based algorithm for discovering clusters in large spatial databases. KDD96. M. Ester, H.-P. Kriegel, and X. Xu. Knowledge discovery in large spatial databases: Focusing techniques for efficient class identification. SSD95. D. Fisher. Knowledge acquisition via incremental conceptual clustering. Machine Lear