《聚類分析》ppt課件

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

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

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

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

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

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

7、行聚類 要找到既滿足特定的約束, 又具有良好聚類特性的數(shù)據(jù)分組是一項(xiàng)具有挑戰(zhàn)性的任務(wù) 可解釋性和可用性 用戶希望聚類結(jié)果是可解釋的, 可理解的, 和可用的 聚類可能需要和特定的語(yǔ)義解釋和應(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）孤立點(diǎn)分析（Outlier Analysis）小結(jié),10,數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)矩陣(two modes)相異度矩陣(Dissimilarity matrix)(one mode),11,評(píng)估聚類的質(zhì)量,有一個(gè)單獨(dú)的“質(zhì)量”函數(shù), 它度量聚類的“好

9、壞”.很難定義“足夠類似”或“足夠好” 對(duì)此問(wèn)題是相當(dāng)主觀的.相異度/相似度矩陣相似性用距離函數(shù)表示, 通常記作 d(i, j)對(duì)于區(qū)間標(biāo)度變量, 二元變量, 標(biāo)稱變量, 序數(shù)和比例標(biāo)度變量, 距離函數(shù)的定義通常是很不相同的.根據(jù)應(yīng)用和數(shù)據(jù)語(yǔ)義, 不同的變量應(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)計(jì)算平均絕對(duì)偏差:其中(2)計(jì)算標(biāo)準(zhǔn)化的度量值 (z-score)使用平均絕對(duì)偏差比使用標(biāo)準(zhǔn)差更具有魯棒性,14,對(duì)象之間的相似性/相異

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

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

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

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

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

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

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

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

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

20、變量組合在單個(gè)相異度矩陣中, 把所有變量轉(zhuǎn)換到共同的值域區(qū)間[0.0, 1.0]上,25,混合類型變量(續(xù)),假設(shè)數(shù)據(jù)集包含p個(gè)不同類型的變量，對(duì)象i 和j 之間的相異度d(i,j)定義為 其中, 如果xif或xjf 缺失(即對(duì)象i 或?qū)ο骿 沒(méi)有變量f 的度量值)或者xif =xjf=0, 且變量f 是不對(duì)稱的二元變量, 則指示項(xiàng) ; 否則, 指示項(xiàng)變量f 對(duì)i 和j 之間相異度的計(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)度型變量計(jì)算秩rif 和 將 zif 作為區(qū)間標(biāo)度變量對(duì)待,27,向量對(duì)象,向量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）孤立點(diǎn)分析（Outlier Analysis）小結(jié),29,主要聚類方法的分類,劃分方法(Partition

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

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

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

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

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

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

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

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

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

32、(1) 任意選擇k個(gè)對(duì)象作為初始的簇中心；(2) repeat(3) 根據(jù)簇中對(duì)象的平均值, 將每個(gè)對(duì)象(重新)賦給最類似的簇；(4) 更新簇的平均值, 即重新計(jì)算每個(gè)簇中對(duì)象的平均值；(5) until 不再發(fā)生變化 通常, 采用平方誤差準(zhǔn)則作為收斂函數(shù), 其定義如下 其中, mi是簇Ci的平均值該準(zhǔn)則試圖使生成的結(jié)果簇盡可能緊湊, 獨(dú)立,,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個(gè)對(duì)象作為初始聚類中心,,,將每個(gè)對(duì)象賦給最類似的中心,更新簇的平均值,,,,,重新賦值,,更新簇的平均值,重新賦值,40,k-平均聚類算法(續(xù)),優(yōu)點(diǎn): 相對(duì)有效性: O(tkn), 其中 n 是對(duì)象數(shù)目, k 是簇?cái)?shù)目, t 是迭代次

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

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

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

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

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

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

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

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

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

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

44、rtitioning Around Medoids) (Kaufman and Rousseeuw, 1987)是最早提出的k-中心點(diǎn)聚類算法基本思想:隨機(jī)選擇k個(gè)代表對(duì)象反復(fù)地試圖找出更好的代表對(duì)象: 分析所有可能的對(duì)象對(duì)，每個(gè)對(duì)中的一個(gè)對(duì)象被看作是代表對(duì)象, 而另一個(gè)不是. 對(duì)可能的各種組合, 估算聚類結(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)存在噪音和孤立點(diǎn)時(shí), PAM 比 k-平均方法更健壯. 這是因?yàn)橹行狞c(diǎn)不象平均值那么容易被極端數(shù)據(jù)影響 PAM對(duì)于小數(shù)據(jù)集工作得很好, 但不能很好地用于大數(shù)據(jù)集 每次迭代O(

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

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

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

50、LARANS(續(xù)),如果一個(gè)更好的鄰居被發(fā)現(xiàn), CLARANS移到該鄰居節(jié)點(diǎn), 處理過(guò)程重新開(kāi)始, 否則當(dāng)前的聚類達(dá)到了一個(gè)局部最優(yōu)如果找到了一個(gè)局部最優(yōu), CLARANS從隨機(jī)選擇的節(jié)點(diǎn)開(kāi)始尋找新的局部最優(yōu)實(shí)驗(yàn)顯示CLARANS比PAM和CLARA更有效 CLARANS能夠探測(cè)孤立點(diǎn) 聚焦技術(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）孤立點(diǎn)分析（Outlier Analysis）小結(jié),57,層次方法,層次的聚類方法

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

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

54、和Rousseeuw提出 (1990)已在一些統(tǒng)計(jì)分析軟件包中實(shí)現(xiàn) . 如 Splus是 AGNES的逆最終每個(gè)節(jié)點(diǎn)自己形成一個(gè)簇,,,61,層次方法(續(xù)),四個(gè)廣泛采用的簇間距離度量方法 最小距離：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’|是兩個(gè)對(duì)象p和p’之間的距離mi是簇Ci 的平均值，ni是簇Ci中對(duì)象的數(shù)目,62,層次方法(續(xù)),層次聚類的主要缺點(diǎn)不具有很好的可伸縮性: 時(shí)間復(fù)雜性至少是 O(n2), 其中 n 對(duì)象總數(shù)合并或分裂的決定需要檢查和估算大量的對(duì)象或簇 不能撤消已做的處理, 聚類之間不能交換對(duì)象. 如果某一步?jīng)]有很好地選擇合并或分裂

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

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

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

59、ts ) 記錄了計(jì)算聚類和有效利用存儲(chǔ)的關(guān)鍵度量, 并有效地利用了存儲(chǔ),因?yàn)樗鼌R總了關(guān)于子類的信息，而不是存儲(chǔ)所有的對(duì)象 CF 樹(shù)是高度平衡的樹(shù)，它存儲(chǔ)了層次聚類的聚類特征 樹(shù)中的非葉節(jié)點(diǎn)有后代或“孩子” 非葉節(jié)點(diǎn)存儲(chǔ)了其孩子的CF的總和，即匯總了關(guān)于其孩子的聚類信息 CF樹(shù)有兩個(gè)參數(shù) ----影響CF樹(shù)的大小分支因子B: 定義非樹(shù)葉節(jié)點(diǎn)的孩子的最大個(gè)數(shù)閾值T: 給出了存儲(chǔ)在樹(shù)的葉子節(jié)點(diǎn)中的子類的最大直徑,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 樹(shù)(Clustering F

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

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

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

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

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

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

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

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