《聚類分析》ppt課件

1、1,第7章 聚類分析,什么是聚類（Clustering）分析?聚類分析中的數(shù)據(jù)類型主要聚類方法分類劃分方法（Partitioning Methods）層次方法（Hierarchical Methods）基于密度的方法（Density-Based Methods）基于網(wǎng)格的方法（Grid-Based Methods）基于模型的聚類方法（Model-Based Clustering Methods）孤立點分析（Outlie

2、r Analysis）小結(jié),2,什么是聚類分析?,聚類: 數(shù)據(jù)對象的集合/簇 (cluster) 同一簇中的對象彼此相似不同簇中的對象彼此相異聚類分析將數(shù)據(jù)對象分組成為多個類或簇聚類是無指導(dǎo)的分類: 沒有預(yù)先定義的類典型應(yīng)用作為洞察數(shù)據(jù)內(nèi)部分布的獨一無二的工具 作為其它算法的預(yù)處理步驟,3,聚類的一般應(yīng)用,模式識別空間數(shù)據(jù)分析 聚類產(chǎn)生GIS(地理信息系統(tǒng))的專題地圖thematic maps 在空間數(shù)據(jù)挖掘中檢

3、測空間聚類并解釋它們圖象處理經(jīng)濟(jì)科學(xué) (特別是市場研究)WWW文本分類Web日志數(shù)據(jù)聚類，發(fā)現(xiàn)類似訪問模式群,4,聚類應(yīng)用的例子,市場營銷: 幫助市場營銷者發(fā)現(xiàn)他們的基本顧客的不同組群，然后利用這一知識制定有針對性的營銷計劃國土利用在地球觀測數(shù)據(jù)庫中識別類似的國土使用區(qū)域保險 對汽車保險持有者的分組 城市規(guī)劃根據(jù)房子的類型，價值，和地理位置對一個城市中房屋的分組 地震研究應(yīng)當(dāng)將觀測到的地震震中沿大陸

4、板塊斷裂進(jìn)行聚類,5,什么是好的聚類方法?,一個好的聚類方法應(yīng)當(dāng)產(chǎn)生高質(zhì)量的聚類類內(nèi)相似性高類間相似性低聚類結(jié)果的質(zhì)量依賴于方法所使用的相似性度量和它的實現(xiàn).聚類方法的質(zhì)量也用它發(fā)現(xiàn)某些或全部隱藏的模式的能力來度量,6,數(shù)據(jù)挖掘?qū)垲惖囊?可伸縮性有的算法當(dāng)數(shù)據(jù)對象少于200時處理很好, 但對大量數(shù)據(jù)對象偏差較大大型數(shù)據(jù)庫包含數(shù)百萬個對象處理不同屬性類型的能力許多算法專門用于數(shù)值類型的數(shù)據(jù)實際應(yīng)用涉及不同的數(shù)據(jù)類型,

5、i.e. 混合了數(shù)值和分類數(shù)據(jù)發(fā)現(xiàn)任意形狀的聚類基于距離的聚類趨向于發(fā)現(xiàn)具有相近尺度和密度的球狀簇 一個簇可能是任意形狀的,7,數(shù)據(jù)挖掘?qū)垲惖囊?續(xù)),用于決定輸入?yún)?shù)的領(lǐng)域知識最小化許多聚類算法要求用戶輸入一定的參數(shù), 如希望產(chǎn)生的簇的數(shù)目.聚類結(jié)果對于輸入?yún)?shù)十分敏感 參數(shù)難以確定, 增加了用戶的負(fù)擔(dān), 使聚類質(zhì)量難以控制處理噪聲數(shù)據(jù)和孤立點的能力 一些聚類算法對于噪音數(shù)據(jù)敏感, 可能導(dǎo)致低質(zhì)量的聚類結(jié)果現(xiàn)實世界

6、中的數(shù)據(jù)庫大都包含了孤立點, 空缺, 或者錯誤的數(shù)據(jù) 對于輸入記錄的順序不敏感 一些聚類算法對于輸入數(shù)據(jù)的順序是敏感的, 以不同的次序輸入會導(dǎo)致不同的聚類,8,數(shù)據(jù)挖掘?qū)垲惖囊?續(xù)),高維性（high dimensionality） 許多聚類算法擅長處理低維的數(shù)據(jù), 可能只涉及兩到三維 數(shù)據(jù)庫或者數(shù)據(jù)倉庫可能包含若干維或者屬性, 數(shù)據(jù)可能非常稀疏, 而且高度偏斜 整合用戶指定的約束現(xiàn)實世界的應(yīng)用可能需要在各種約束條件下進(jìn)

7、行聚類 要找到既滿足特定的約束, 又具有良好聚類特性的數(shù)據(jù)分組是一項具有挑戰(zhàn)性的任務(wù) 可解釋性和可用性 用戶希望聚類結(jié)果是可解釋的, 可理解的, 和可用的 聚類可能需要和特定的語義解釋和應(yīng)用相聯(lián)系,9,第7章. 聚類分析,什么是聚類（Clustering）分析?聚類分析中的數(shù)據(jù)類型主要聚類方法分類劃分方法（Partitioning Methods）層次方法（Hierarchical Methods）基于密度的方法（De

8、nsity-Based Methods）基于網(wǎng)格的方法（Grid-Based Methods）基于模型的聚類方法（Model-Based Clustering Methods）孤立點分析（Outlier Analysis）小結(jié),10,數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)矩陣(two modes)相異度矩陣(Dissimilarity matrix)(one mode),11,評估聚類的質(zhì)量,有一個單獨的“質(zhì)量”函數(shù), 它度量聚類的“好

9、壞”.很難定義“足夠類似”或“足夠好” 對此問題是相當(dāng)主觀的.相異度/相似度矩陣相似性用距離函數(shù)表示, 通常記作 d(i, j)對于區(qū)間標(biāo)度變量, 二元變量, 標(biāo)稱變量, 序數(shù)和比例標(biāo)度變量, 距離函數(shù)的定義通常是很不相同的.根據(jù)應(yīng)用和數(shù)據(jù)語義, 不同的變量應(yīng)賦予不同的權(quán).,12,聚類分析的數(shù)據(jù)類型,區(qū)間標(biāo)度變量(Interval-scaled variables)二元變量(Binary variables)標(biāo)

10、稱(名詞性), 序數(shù), 和比例標(biāo)度變量(Nominal, ordinal, and ratio variables)混合類型變量(Variables of mixed types),13,區(qū)間標(biāo)度變量,區(qū)間標(biāo)度變量：一種粗略線形標(biāo)度的連續(xù)度量為了避免度量單位的影響，數(shù)據(jù)標(biāo)準(zhǔn)化(1)計算平均絕對偏差:其中(2)計算標(biāo)準(zhǔn)化的度量值 (z-score)使用平均絕對偏差比使用標(biāo)準(zhǔn)差更具有魯棒性,14,對象之間的相似性/相異

11、性,通常, 使用距離來度量兩個數(shù)據(jù)對象之間的相似性/相異性常用的距離包括:閔可夫斯基(Minkowski) 距離:其中 i = (xi1, xi2, …, xip)和 j = (xj1, xj2, …, xjp) 是兩個 p-維數(shù)據(jù)對象(q 正整數(shù))如果q = 1, d是曼哈坦 (Manhattan)距離,15,對象之間的相似性/相異性,如果 q = 2, d是歐幾里德(Euclidean)距離 :距離的性質(zhì)非負(fù)性:

12、 d(i,j) ? 0自身到自身的距離為0: d(i,i) = 0對稱性: d(i,j) = d(j,i)三角不等式: d(i,j) ? d(i,k) + d(k,j)也可以使用加權(quán)的距離, 如加權(quán)的歐幾里德距離,16,二元變量,二元變量(binary variable )只有兩個狀態(tài)0或1. 0表示該變量為空, 1表示該變量存在例如, 描述病人的變量smoker, 1表示病人抽煙, 而0表示病人不抽煙計算二元變量的相似度

13、假定所有二元變量具有相同的權(quán)重, 則得到一個兩行兩列的可能性表(contingency table),,,對象 i,對象 j,17,二元變量,對稱的: 二元變量的兩個狀態(tài)具有同等價值,并具有相同的權(quán)重例: 性別是對稱的二元變量恒定的相似度: 基于對稱的二元變量的相似度, 當(dāng)一些或全部二元變量編碼改變時, 計算結(jié)果不會發(fā)生變化對稱的二元變量的相異度計算----簡單匹配系數(shù)不對稱的: 二元變量的兩個狀態(tài)的輸出不是同樣重要例:

14、疾病檢查結(jié)果的肯定和否定.,18,二元變量(續(xù)),根據(jù)慣例, 比較重要的輸出結(jié)果是出現(xiàn)幾率較小的例: HIV陽性是比較重要的結(jié)果,出現(xiàn)幾率較小, 而HIV陰性(正常情況)出現(xiàn)幾率較大通常, 比較重要的輸出結(jié)果編碼為1, 另一種結(jié)果編碼為0兩個都取1的情況(正匹配)比兩個都取0的情況(負(fù)匹配)更有意義. ----非恒定的相似度對于非對稱的相似度, 負(fù)匹配數(shù)目t被忽略. 采用Jaccard系數(shù),19,二元變量之間的相異度,例

15、gender 是對稱的其余都不是對稱的Y和P的值設(shè)置為1, 而 N的值設(shè)置為 0,20,標(biāo)稱變量-分類變量，名義變量,標(biāo)稱變量(Nominal variable)是二元變量的拓廣, 它可以取多于兩種狀態(tài)值, 如, red, yellow, blue, green方法1: 簡單匹配m:狀態(tài)取值匹配的變量數(shù)目, p: 變量總數(shù)方法 2：（可以用非對稱的二元變量對標(biāo)稱變量編碼）使用大量二元變量，對M個標(biāo)稱狀態(tài)的每一個, 創(chuàng)

16、建一個新的二元變量. 對于一個有特定狀態(tài)值的對象, 對應(yīng)狀態(tài)值的二元變量值置1, 其余二元變量的值置0,21,序數(shù)型變量,序數(shù)型變量(ordinal variable)可以是離散的, 也可以是連續(xù)的離散的序數(shù)型變量類似于標(biāo)稱變量, 但序數(shù)型變量的M個狀態(tài)是以有意義的序列排序 連續(xù)的序數(shù)型變量看起來像一個未知刻度的連續(xù)數(shù)據(jù)的集合. 值的相對順序是必要的, 而其實際的大小則不重要 將區(qū)間標(biāo)度變量的值域劃分為有限個區(qū)間, 從而將其值

17、離散化, 也可以得到序數(shù)型變量序數(shù)型變量的值可以映射為秩(rank). 例如, 假設(shè)變量f有Mf個狀態(tài), 這些有序的狀態(tài)定義了一個排列1,…,Mf,22,序數(shù)型變量(續(xù)),相異度計算可以用類似于區(qū)間標(biāo)度變量的方法處理設(shè)第i 個對象f 的值為 xif , 用對應(yīng)的秩rif 替代xif, 其中 rif ∈{1,…,Mf }將每個變量的值域映射到[0, 1]區(qū)間, 以便每個變量都具有相同的權(quán)重: 用下式替換rif 使用區(qū)間標(biāo)度

18、變量計算距離的方法計算相異度, z if作為第i 個對象f 的值,23,比例標(biāo)度變量,比例標(biāo)度變量(Ratio-scaled variable)非線性的刻度上取正的度量值，例如指數(shù)標(biāo)度，近似地遵循如下的公式 AeBt 或Ae-Bt 相異度計算:采用與處理區(qū)間標(biāo)度變量同樣的方法 —不是好的選擇! (為什么?—標(biāo)度可能被扭曲)進(jìn)行對數(shù)變換 yif = log(xif)將xif看作連續(xù)的序數(shù)型數(shù)據(jù), 將其秩作為區(qū)間標(biāo)度

19、值方法的選取取決于應(yīng)用, 但后兩種方法比較有效,24,混合類型變量,數(shù)據(jù)庫可能包含所有六種類型對稱的二元變量, 不對稱的二元變量, 標(biāo)稱的, 序數(shù)的, 區(qū)間的, 比例標(biāo)度的如何計算混合類型變量描述的對象的相異度?方法1: 將變量按類型分組, 對每種類型的變量單獨進(jìn)行聚類分析如果這些分析得到兼容的結(jié)果, 這種方法是可行的在實際的應(yīng)用中, 這種方法行不通方法2:將所有的變量一起處理, 只進(jìn)行一次聚類分析. 將不同類型的

20、變量組合在單個相異度矩陣中, 把所有變量轉(zhuǎn)換到共同的值域區(qū)間[0.0, 1.0]上,25,混合類型變量(續(xù)),假設(shè)數(shù)據(jù)集包含p個不同類型的變量，對象i 和j 之間的相異度d(i,j)定義為 其中, 如果xif或xjf 缺失(即對象i 或?qū)ο骿 沒有變量f 的度量值)或者xif =xjf=0, 且變量f 是不對稱的二元變量, 則指示項 ; 否則, 指示項變量f 對i 和j 之間相異度的計算方式與其具體類型有關(guān)

21、 如果f 是二元或標(biāo)稱變量:如果 xif = xjf , dij(f) = 0; 否則 dij(f) = 1,26,混合類型變量(續(xù)),如果f 是區(qū)間標(biāo)度變量, 使用規(guī)格化的距離如果f 是序數(shù)型或比例標(biāo)度型變量計算秩rif 和 將 zif 作為區(qū)間標(biāo)度變量對待,27,向量對象,向量x和y余弦度量Tanimoto系數(shù),28,第8章. 聚類分析,什么是聚類（Clustering）分析?聚類分析中的數(shù)據(jù)類

22、型主要聚類方法分類劃分方法（Partitioning Methods）層次方法（Hierarchical Methods）基于密度的方法（Density-Based Methods）基于網(wǎng)格的方法（Grid-Based Methods）基于模型的聚類方法（Model-Based Clustering Methods）孤立點分析（Outlier Analysis）小結(jié),29,主要聚類方法的分類,劃分方法(Partition

23、ing method): 構(gòu)造n個對象數(shù)據(jù)庫D的劃分, 將其劃分成k個聚類滿足如下的要求：每個組至少包含一個對象每個對象必須屬于且只屬于一個組在某些模糊劃分技術(shù)中, 第二個要求可以放寬 基本方法: 首先創(chuàng)建一個初始劃分. 然后采用一種迭代的重定位技術(shù), 嘗試通過在劃分間移動對象來改進(jìn)劃分好的劃分的一般準(zhǔn)則: 在同一個類中的對象之間盡可能“接近”或相關(guān), 而不同類中的對象之間盡可能“遠(yuǎn)離”或不同,30,主要聚類方法的分類(續(xù)),

24、全局最優(yōu): 窮舉所有可能的劃分 啟發(fā)式方法: k-平均值(k- means)和 k-中心點(k- medoids) 算法k-平均值(MacQueen’67): 每個簇用該簇中對象的平均值來表示 k-中心點或 PAM (Partition around medoids) (Kaufman & Rousseeuw’87): 每個簇用接近聚類中心的一個對象來表示 這些啟發(fā)式算法適合發(fā)現(xiàn)中小規(guī)模數(shù)據(jù)庫中的球狀聚類對于大規(guī)模數(shù)

25、據(jù)庫和處理任意形狀的聚類,這些算法需要進(jìn)一步擴(kuò)展,31,主要聚類方法的分類(續(xù)),層次方法(Hierarchy method): 對給定數(shù)據(jù)對象集合進(jìn)行層次的分解 兩種層次方法凝聚方法, 也稱為自底向上的方法: 開始將每個對象作為單獨的一個組; 然后繼續(xù)地合并相近的對象或組, 直到所有的組合并為一個(層次的最上層), 或者達(dá)到一個終止條件 分裂方法, 也稱為自頂向下的方法: 開始將所有的對象置于一個簇; 在迭代的每一步, 一個簇被

26、分裂為更小的簇, 直到最終每個對象在單獨的一個簇中, 或者達(dá)到一個終止條件,32,主要聚類方法的分類(續(xù)),層次方法的缺點: 一個步驟一旦完成便不能被撤消.該規(guī)定可以避免考慮選擇不同的組合, 減少計算代價問題: 不能更正錯誤的決定改進(jìn)層次聚類結(jié)果的措施在每層劃分中, 仔細(xì)分析對象間的“聯(lián)接”, 例如CURE和Chameleon中的做法 綜合層次凝聚和迭代的重定位方法。首先用自底向上的層次算法，然后用迭代的重定位來改進(jìn)結(jié)果。例如

27、在BIRCH中的方法,33,主要聚類方法的分類(續(xù)),基于密度的方法(Density-based method): 基于密度函數(shù)基本思想: 只要臨近區(qū)域的密度(對象或數(shù)據(jù)點的數(shù)目)超過某個閥值, 就繼續(xù)聚類. 也就是說, 對給定類中的每個數(shù)據(jù)點, 在一個給定范圍的區(qū)域中必須至少包含一定數(shù)目的點 該方法可以用來過濾“噪音”數(shù)據(jù)，發(fā)現(xiàn)任意形狀的簇 DBSCAN是一個有代表性的基于密度的方法, 它根據(jù)一個密度閥值來控制簇的增長OPTI

28、CS是另一個基于密度的方法, 它為自動的, 交互的聚類分析計算一個聚類順序,34,主要聚類方法的分類(續(xù)),基于網(wǎng)格的方法(Grid-based method): 把對象空間量化為有限數(shù)目的單元, 形成了一個網(wǎng)格結(jié)構(gòu). 所有的聚類操作都在這個網(wǎng)格結(jié)構(gòu)(即量化的空間)上進(jìn)行這種方法的主要優(yōu)點是它的處理速度很快, 其處理時間獨立于數(shù)據(jù)對象的數(shù)目, 只與量化空間中每一維的單元數(shù)目有關(guān) STING是基于網(wǎng)格方法的一個典型例子CLIQU

29、E和WaveCluster這兩種算法既是基于網(wǎng)格的, 又是基于密度的,35,主要聚類方法的分類(續(xù)),基于模型的方法(Model-based Method): 基于模型的方法為每個簇假定了一個模型, 尋找數(shù)據(jù)對給定模型的最佳擬合,36,第7章. 聚類分析,什么是聚類（Clustering）分析?聚類分析中的數(shù)據(jù)類型主要聚類方法分類劃分方法（Partitioning Methods）層次方法（Hierarchical Method

30、s）基于密度的方法（Density-Based Methods）基于網(wǎng)格的方法（Grid-Based Methods）基于模型的聚類方法（Model-Based Clustering Methods）孤立點分析（Outlier Analysis）小結(jié),37,劃分方法,劃分方法: 構(gòu)造n個對象數(shù)據(jù)庫D的劃分, 將其劃分成k個聚類給定 k, 找k 個clusters 對于選定的劃分標(biāo)準(zhǔn)它是最優(yōu)的全局最優(yōu)(Global opti

31、mal): 枚舉所有的劃分啟發(fā)式方法(Heuristic methods): k-平均(k-means)和k-中心點(k-medoids)算法k-平均(MacQueen’67): 每個簇用簇的重心( 簇的平均值) 表示k-中心點或PAM (Partition around medoids) (Kaufman & Rousseeuw’87): 每個簇用接近聚類中心的一個對象來表示,38,k-平均聚類算法,算法： k-平均

32、(1) 任意選擇k個對象作為初始的簇中心；(2) repeat(3) 根據(jù)簇中對象的平均值, 將每個對象(重新)賦給最類似的簇；(4) 更新簇的平均值, 即重新計算每個簇中對象的平均值；(5) until 不再發(fā)生變化 通常, 采用平方誤差準(zhǔn)則作為收斂函數(shù), 其定義如下 其中, mi是簇Ci的平均值該準(zhǔn)則試圖使生成的結(jié)果簇盡可能緊湊, 獨立,,39,k-平均聚類算法(續(xù)),例,,,,,,,,,,,,,,,,

33、,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,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個對象作為初始聚類中心,,,將每個對象賦給最類似的中心,更新簇的平均值,,,,,重新賦值,,更新簇的平均值,重新賦值,40,k-平均聚類算法(續(xù)),優(yōu)點: 相對有效性: O(tkn), 其中 n 是對象數(shù)目, k 是簇數(shù)目, t 是迭代次

34、數(shù); 通常, k, t << n.比較: PAM: O(k(n-k)2 ), CLARA: O(ks2 + k(n-k))當(dāng)結(jié)果簇是密集的，而簇與簇之間區(qū)別明顯時，它的效果較好Comment: 常常終止于局部最優(yōu). 全局最優(yōu) 可以使用諸如確定性的退火(deterministic annealing)和遺傳算法(genetic algorithms)等技術(shù)得到,41,k-平均聚類算法(續(xù)),弱點只有在簇的平均值(m

35、ean)被定義的情況下才能使用.可能不適用于某些應(yīng)用, 例如涉及有分類屬性的數(shù)據(jù)需要預(yù)先指頂簇的數(shù)目k, 不能處理噪音數(shù)據(jù)和孤立點(outliers)不適合用來發(fā)現(xiàn)具有非凸形狀(non-convex shapes)的簇,42,k-平均方法的變種,k-平均方法的變種, 它們在以下方面有所不同初始k個平均值的選擇相異度的計算計算聚類平均值的策略 較好的策略: 先用層次凝聚算法決定簇的數(shù)目, 并產(chǎn)生初始聚類, 然后用迭代重定位改

36、進(jìn)聚類結(jié)果處理分類屬性: k- 模(k-modes) 方法(Huang’98)用模(modes眾數(shù))替代聚類的平均值使用新的相異性度量方法來處理分類對象 用基于頻率的方法來修改聚類的模 k-原型(k-prototype)方法: k-平均和k-模的結(jié)合, 處理具有數(shù)值和分類屬性的數(shù)據(jù),43,k-平均方法的變種(續(xù)),EM(Expectation Maximization, 期望最大)算法以另一種方式對k-means方法進(jìn)行了擴(kuò)

37、展: 不把對象分配給一個確定的簇, 而是根據(jù)對象與簇之間隸屬關(guān)系發(fā)生的概率來分派對象 怎樣增強(qiáng)k-means算法的可擴(kuò)展性？ 數(shù)據(jù)分成三種區(qū)域： 可廢棄的: 一個對象與某個簇的隸屬關(guān)系是確定的可壓縮的: 一個對象不是可廢棄的,但屬于某個緊密的子簇必須在主存: 既不是可廢棄的, 又不是可壓縮的迭代的算法只包含可壓縮的對象和必須在主存中的對象的聚類特征, 從而將一個基于二級存儲的算法變成了基于主存的算法,44,k-中心點聚類方

38、法,k-平均值算法對孤立點很敏感!因為具有特別大的值的對象可能顯著地影響數(shù)據(jù)的分布.k-中心點(k-Medoids): 不采用簇中對象的平均值作為參照點, 而是選用簇中位置最中心的對象, 即中心點(medoid)作為參照點.,45,k-中心點聚類方法(續(xù)),找聚類中的代表對象(中心點)PAM (Partitioning Around Medoids, 1987)首先為每個簇隨意選擇選擇一個代表對象, 剩余的對象根據(jù)其與代表對

39、象的距離分配給最近的一個簇; 然后反復(fù)地用非代表對象來替代代表對象，以改進(jìn)聚類的質(zhì)量 PAM 對于較小的數(shù)據(jù)集非常有效, 但不能很好地擴(kuò)展到大型數(shù)據(jù)集CLARA (Kaufmann & Rousseeuw, 1990)抽樣CLARANS (Ng & Han, 1994): 隨機(jī)選樣,46,k-中心點聚類方法(續(xù)),基本思想：首先為每個簇隨意選擇選擇一個代表對象; 剩余的對象根據(jù)其與代表對象的距離分配給最近的一個簇

40、然后反復(fù)地用非代表對象來替代代表對象, 以改進(jìn)聚類的質(zhì)量聚類結(jié)果的質(zhì)量用一個代價函數(shù)來估算, 該函數(shù)評估了對象與其參照對象之間的平均相異度,47,k-中心點聚類方法(續(xù)),為了判定一個非代表對象Orandom 是否是當(dāng)前一個代表對象Oj的好的替代, 對于每一個非代表對象p,考慮下面的四種情況： 第一種情況：p當(dāng)前隸屬于代表對象 Oj. 如果Oj被Orandom所代替, 且p離Oi最近, i≠j, 那么p被重新分配給Oi 第二種情

41、況：p當(dāng)前隸屬于代表對象 Oj. 如果Oj 被Orandom代替, 且p離Orandom最近, 那么p被重新分配給Orandom 第三種情況：p當(dāng)前隸屬于Oi，i≠j。如果Oj被Orandom代替，而p仍然離Oi最近，那么對象的隸屬不發(fā)生變化 第四種情況：p當(dāng)前隸屬于Oi，i≠j。如果Oj被Orandom代替，且p離Orandom最近，那么p被重新分配給Orandom,48,k-中心點聚類方法(續(xù)),重新分配給Oi 2. 重新

42、分配給Orandom 3. 不發(fā)生變化 4.重新分配給Orandom● 數(shù)據(jù)對象+ 簇中心 替代前 替代后圖8-3 k-中心點聚類代價函數(shù)的四種情況,,+,+,+,●,Orandom,Oi,Oj,p,,+,+,+,●,Orandom,Oi,Oj,p,,+,+,+,●,Orandom,Oi,Oj,p,,,+,+,+,●,Orandom,Oi,Oj,p,,,,,,,,

43、,49,k-中心點聚類方法(續(xù)),算法: k-中心點(1) 隨機(jī)選擇k個對象作為初始的代表對象；(2) repeat(3) 指派每個剩余的對象給離它最近的代表對象所代表的簇；(4) 隨意地選擇一個非代表對象Orandom；(5) 計算用Orandom代替Oj的總代價S；(6) 如果S<0，則用Orandom替換Oj，形成新的k個代表對象的集合；(7) until 不發(fā)生變化,50,PAM,PAM (Pa

44、rtitioning Around Medoids) (Kaufman and Rousseeuw, 1987)是最早提出的k-中心點聚類算法基本思想:隨機(jī)選擇k個代表對象反復(fù)地試圖找出更好的代表對象: 分析所有可能的對象對，每個對中的一個對象被看作是代表對象, 而另一個不是. 對可能的各種組合, 估算聚類結(jié)果的質(zhì)量,51,PAM(續(xù)),Total Cost = 20,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,

45、,,,,,,,,,,,,,,,,,,,,,,,,,,0,1,2,3,4,5,6,7,8,9,10,0,1,2,3,4,5,6,7,8,9,10,,,,K=2,,Arbitrary choose k object as initial medoids,,,Assign each remaining object to nearest medoids,,Randomly select a nonmedoid object,Oramdom,,

46、Compute total cost of swapping,Total Cost = 26,,Swapping O and Oramdom If quality is improved.,Do loopUntil no change,52,PAM(續(xù)),當(dāng)存在噪音和孤立點時, PAM 比 k-平均方法更健壯. 這是因為中心點不象平均值那么容易被極端數(shù)據(jù)影響 PAM對于小數(shù)據(jù)集工作得很好, 但不能很好地用于大數(shù)據(jù)集 每次迭代O(

47、k(n-k)2 )其中 n 是數(shù)據(jù)對象數(shù)目, k 是聚類數(shù)基于抽樣的方法, CLARA(Clustering LARge Applications),53,CLARA (Clustering Large Applications) (1990),CLARA (Kaufmann and Rousseeuw in 1990)不考慮整個數(shù)據(jù)集, 而是選擇數(shù)據(jù)的一小部分作為樣本它從數(shù)據(jù)集中抽取多個樣本集, 對每個樣本集使用PAM

48、, 并以最好的聚類作為輸出優(yōu)點: 可以處理的數(shù)據(jù)集比 PAM大缺點:有效性依賴于樣本集的大小基于樣本的好的聚類并不一定是 整個數(shù)據(jù)集的好的聚類, 樣本可能發(fā)生傾斜 例如, Oi是最佳的k個中心點之一, 但它不包含在樣本中, CLARA將找不到最佳聚類,54,CLARANS (“Randomized” CLARA) (1994),CLARANS (A Clustering Algorithm based on Randomize

49、d Search) (Ng and Han’94)CLARANS將采樣技術(shù)和PAM結(jié)合起來CLARA在搜索的每個階段有一個固定的樣本CLARANS任何時候都不局限于固定樣本, 而是在搜索的每一步帶一定隨機(jī)性地抽取一個樣本 聚類過程可以被描述為對一個圖的搜索, 圖中的每個節(jié)點是一個潛在的解, 也就是說 k medoids相鄰節(jié)點：代表的集合只有一個對象不同在替換了一個代表對象后得到的聚類結(jié)果被稱為當(dāng)前聚類結(jié)果的鄰居,55,C

50、LARANS(續(xù)),如果一個更好的鄰居被發(fā)現(xiàn), CLARANS移到該鄰居節(jié)點, 處理過程重新開始, 否則當(dāng)前的聚類達(dá)到了一個局部最優(yōu)如果找到了一個局部最優(yōu), CLARANS從隨機(jī)選擇的節(jié)點開始尋找新的局部最優(yōu)實驗顯示CLARANS比PAM和CLARA更有效 CLARANS能夠探測孤立點 聚焦技術(shù)和空間存取結(jié)構(gòu)可以進(jìn)一步改進(jìn)它的性能 (Ester et al.’95),56,第7章. 聚類分析,什么是聚類（Clustering）分

51、析?聚類分析中的數(shù)據(jù)類型主要聚類方法分類劃分方法（Partitioning Methods）層次方法（Hierarchical Methods）基于密度的方法（Density-Based Methods）基于網(wǎng)格的方法（Grid-Based Methods）基于模型的聚類方法（Model-Based Clustering Methods）孤立點分析（Outlier Analysis）小結(jié),57,層次方法,層次的聚類方法

52、將數(shù)據(jù)對象組成一棵聚類的樹根據(jù)層次分解是自底向上, 還是自頂向下形成, 層次的聚類方法可以進(jìn)一步分為凝聚的(agglomerative)和分裂的(divisive)層次聚類 純粹的層次聚類方法的聚類質(zhì)量受限于如下特點：一旦一個合并或分裂被執(zhí)行，就不能修正 最近的研究集中于凝聚層次聚類和迭代重定位方法的集成 使用距離矩陣作為聚類標(biāo)準(zhǔn). 該方法不需要輸入聚類數(shù)目 k, 但需要終止條件,58,層次方法(續(xù)),凝聚的(agglomer

53、ative)和分裂的(divisive)層次聚類圖示,59,AGNES (Agglomerative Nesting),由 Kaufmann和Rousseeuw提出(1990)已在一些統(tǒng)計分析軟件包中實現(xiàn) . 如 Splus使用單鏈接(Single-Link)方法和相異度矩陣 合并具有最小相異度的節(jié)點以非遞減的方式繼續(xù)最終所有的節(jié)點屬于同一個簇,,,60,DIANA (Divisive Analysis),由 Kaufmann

54、和Rousseeuw提出 (1990)已在一些統(tǒng)計分析軟件包中實現(xiàn) . 如 Splus是 AGNES的逆最終每個節(jié)點自己形成一個簇,,,61,層次方法(續(xù)),四個廣泛采用的簇間距離度量方法 最小距離：dmin(Ci,Cj) = min p∈Ci, p’∈Cj |p-p’| 最大距離：dmax(Ci,Cj) = max p∈Ci, p’∈Cj |p-p’| 平均值的距離：dmean(Ci,Cj) = | mi - mj |

55、平均距離：davg(Ci,Cj) =∑ p∈Ci ∑p’∈Cj |p-p’| /ninj其中, |p-p’|是兩個對象p和p’之間的距離mi是簇Ci 的平均值，ni是簇Ci中對象的數(shù)目,62,層次方法(續(xù)),層次聚類的主要缺點不具有很好的可伸縮性: 時間復(fù)雜性至少是 O(n2), 其中 n 對象總數(shù)合并或分裂的決定需要檢查和估算大量的對象或簇 不能撤消已做的處理, 聚類之間不能交換對象. 如果某一步?jīng)]有很好地選擇合并或分裂

56、的決定, 可能會導(dǎo)致低質(zhì)量的聚類結(jié)果,63,層次方法(續(xù)),改進(jìn)層次方法的聚類質(zhì)量的方法: 將層次聚類和其他的聚類技術(shù)進(jìn)行集成, 形成多階段聚類 BIRCH (1996): 使用 CF-tree對對象進(jìn)行層次劃分, 然后采用其他的聚類算法對聚類結(jié)果進(jìn)行求精 ROCK1999：基于簇間的互聯(lián)性進(jìn)行合并CHAMELEON (1999): 使用動態(tài)模型進(jìn)行層次聚類CURE (1998):采用固定數(shù)目的代表對象來表示每個簇，然后依據(jù)一

57、個指定的收縮因子向著聚類中心對它們進(jìn)行收縮,64,BIRCH (1996),Birch (Balanced Iterative Reducing and Clustering using Hierarchies): 利用層次方法的平衡迭代歸約和聚類由Zhang, Ramakrishnan和Livny 提出(SIGMOD’96)兩個重要概念聚類特征(Clustering Feature, CF)聚類特征樹(Clustering Fe

58、ature Tree, CF樹)聚類特征聚類特征(CF)是一個三元組，給出對象子類的信息的匯總描述 設(shè)某個子類中有N個d維的點或?qū)ο髙oI}，則該子類的CF定義如下,65,聚類特征,,,CF = (5, (16,30),(54,190)),(3,4)(2,6)(4,5)(4,7)(3,8),66,BIRCH的CF樹,聚類特征 從統(tǒng)計學(xué)的觀點來看，聚類特征是對給定子類統(tǒng)計匯總: 子聚類的0階, 1階和 2階矩( momen

59、ts ) 記錄了計算聚類和有效利用存儲的關(guān)鍵度量, 并有效地利用了存儲,因為它匯總了關(guān)于子類的信息，而不是存儲所有的對象 CF 樹是高度平衡的樹，它存儲了層次聚類的聚類特征 樹中的非葉節(jié)點有后代或“孩子” 非葉節(jié)點存儲了其孩子的CF的總和，即匯總了關(guān)于其孩子的聚類信息 CF樹有兩個參數(shù) ----影響CF樹的大小分支因子B: 定義非樹葉節(jié)點的孩子的最大個數(shù)閾值T: 給出了存儲在樹的葉子節(jié)點中的子類的最大直徑,67,CF T

60、ree,,,,,,,,CF1,child1,CF3,child3,CF2,child2,CF5,child5,,,,,CF1,,CF2,,CF6,,,,,prev,next,,,CF1,,CF2,,CF4,,,,,prev,next,,,,,,B = 7T = 6,,,,Root,Non-leaf node,Leaf node,Leaf node,,68,BIRCH (續(xù)),BIRCH增量地構(gòu)造一棵 CF 樹(Clustering F

61、eature Tree) , CF樹是一個層次數(shù)據(jù)結(jié)構(gòu), 用于多階段聚類階段 1: 掃描 DB , 建立一棵初始的存放在內(nèi)存的 CF樹(數(shù)據(jù)的多層壓縮, 試圖保留數(shù)據(jù)內(nèi)在的聚類結(jié)構(gòu) )階段 2: 使用某種聚類算法對CF樹的葉節(jié)點進(jìn)行聚類. 在階段一，隨著對象被插入, CF樹被動態(tài)地構(gòu)造. 一個對象被插入到最近的葉子條目(子聚類). 如果在插入后存儲在葉子節(jié)點中的子類的直徑大于閥值, 那么該葉子節(jié)點(可能還有其他節(jié)點)被分裂.

62、 新對象插入后. 關(guān)于該對象的信息向著樹根傳遞----類似于B+樹構(gòu)建中的插入和節(jié)點分裂 通過修改閥值，CF樹的大小可以改變,69,BIRCH (續(xù)),重建過程從舊樹的葉子節(jié)點建造一個新樹。這樣，重建樹的過程不需要重讀所有的對象 ----建樹只需讀一次數(shù)據(jù) 在階段二被采用任何聚類算法，例如典型的劃分方法BIRCH的性能支持增量聚類線性可伸縮性: 計算復(fù)雜性O(shè)(n), 單遍掃描, 附加的掃描可以改善聚類質(zhì)量較好的聚類質(zhì)量缺

63、點只能處理數(shù)值數(shù)據(jù)對數(shù)據(jù)的輸入次序敏感Cf樹結(jié)點不總是對應(yīng)于[用戶考慮的]自然簇(參數(shù)B和T)簇非球形時效果不好(使用半徑/直徑控制簇邊界),70,CURE(1998),CURE (Clustering Using REpresentatives ) : 由 Guha, Rastogi 和 Shim提出(1998)絕大多數(shù)聚類算法或者擅長處理球形和相似大小的聚類，或者在存在孤立點時變得比較脆弱 CURE解決了偏好球形的問題，

64、在處理孤立點上也更加健壯 CURE采用了一種新的層次聚類算法選擇基于質(zhì)心和基于代表對象方法之間的中間策略. 它不用單個質(zhì)心或?qū)ο髞泶硪粋€簇, 而是選擇了數(shù)據(jù)空間中固定數(shù)目的具有代表性的點 首先選擇簇中分散的對象, 然后根據(jù)一個特定的收縮因子向簇中心“收縮”,71,CURE(續(xù)),每個簇有多于一個的代表點使得CURE可以適應(yīng)非球形的任意形狀的聚類簇的收縮或凝聚可以有助于控制孤立點的影響 CURE的優(yōu)點CURE對孤立點的處理更

65、加健壯能夠識別非球形和大小變化較大的簇對于大規(guī)模數(shù)據(jù)庫, 它也具有良好的伸縮性, 而且沒有犧牲聚類質(zhì)量 針對大型數(shù)據(jù)庫, CURE采用了隨機(jī)取樣和劃分兩種方法的組合首先劃分一個隨機(jī)樣本,每個劃分被部分聚類然后對這些結(jié)果簇聚類, 產(chǎn)生希望的結(jié)果,72,Cure(續(xù)),CURE算法核心:從源數(shù)據(jù)對象中抽取一個隨機(jī)樣本S .將樣本S分割為p個劃分, 每個的大小為 s/p將每個劃分局部地聚類成 s/pq 個簇刪除孤立點通過

66、隨機(jī)選樣如果一個簇增長太慢, 就刪除它.對局部聚類進(jìn)行聚類.用相應(yīng)的簇標(biāo)簽來標(biāo)記數(shù)據(jù),73,CURE: 例,s = 50p = 2s/p = 25,x,x,s/pq = 5,74,CURE: 例(續(xù)),多個代表點向重心 以因子?移動, 進(jìn)行收縮或凝聚多個代表點描述了每個簇的形狀,,75,對分類數(shù)據(jù)聚類: ROCK,ROCK(RObust Clustering using linKs) 由S. Guha, R. Rasto

67、gi, K. Shim提出 (ICDE’99). 使用鏈接(link)度量相似性/接近性鏈接：兩個對象間共同的近鄰的數(shù)目不是基于距離的計算復(fù)雜性:基本思想:相似性函數(shù):Jaccard系數(shù)設(shè) T1 = {1,2,3}, T2={3,4,5},76,Rock(續(xù)),兩個點pi和pj是近鄰，如果sim(pi,pj)>=用戶指定閾值link(pi,pj)是兩個點pi和pj共同的近鄰的數(shù)目兩個簇Ci和Cj的互連性被定義

68、為兩個簇間交叉鏈（cross link）的數(shù)目 ROCK首先根據(jù)相似度閥值和共享近鄰的概念，從給定的數(shù)據(jù)相似度矩陣構(gòu)建一個稀疏的圖，然后在這個稀疏圖上運行一個層次聚類算法,,77,CHAMELEON,CHAMELEON :一個利用動態(tài)模型的層次聚類算法 (Hierarchical clustering using dynamic modeling) 由G. Karypis, E.H. Han, and V. Kumar’99 提出