第七章-聚類分析

05二月2023DataMining:ConceptsandTechniques1第七章聚類分析什么是聚類分析？聚類分析中的數(shù)據(jù)類型聚類分析的主要方法分類劃分方法層次方法基于密度的方法基于網(wǎng)格的方法基于模型的方法聚類高維數(shù)據(jù)基于約束的聚類分析

離群點(diǎn)分析小結(jié)05二月2023DataMining:ConceptsandTechniques2什么是聚類分析聚類：將數(shù)據(jù)對(duì)象集合成簇簇內(nèi)相似最大化簇間相異最大化聚類分析將物理或抽象對(duì)象的集合分成相似的對(duì)象類的過(guò)程無(wú)監(jiān)督學(xué)習(xí):無(wú)欲先定義的類典型應(yīng)用作為獨(dú)立的工具來(lái)分析數(shù)據(jù)的分布情況作為其他程序的預(yù)處理過(guò)程05二月2023DataMining:ConceptsandTechniques3聚類在各學(xué)科間的應(yīng)用

模式識(shí)別空間數(shù)據(jù)分析CreatethematicmapsinGISbyclusteringfeaturespacesDetectspatialclustersorforotherspatialminingtasks圖像處理經(jīng)濟(jì)學(xué)(特別是市場(chǎng)分析)WWW文獻(xiàn)分類聚類網(wǎng)絡(luò)日志，ClusterWeblogdatatodiscovergroupsofsimilaraccesspatterns05二月2023DataMining:ConceptsandTechniques4聚類的應(yīng)用舉例市場(chǎng)學(xué):幫助營(yíng)銷人員將其客戶數(shù)據(jù)分成不同的組，以更好的開(kāi)拓目標(biāo)市場(chǎng)土地使用:對(duì)地球上相似地區(qū)土地的使用觀察數(shù)據(jù)保險(xiǎn)行業(yè):將汽車保險(xiǎn)分組從而使得投保人的平均花費(fèi)最高城市規(guī)劃:根據(jù)的房子類型，價(jià)值，和地理位置確定住房團(tuán)體地震研究:

根據(jù)大陸斷層的聚類觀測(cè)震中05二月2023DataMining:ConceptsandTechniques5什么是好的聚類？一個(gè)好的聚類方法使聚類結(jié)果簇內(nèi)相似最大化簇間相似最小化

好的聚類方法不僅取決于它產(chǎn)生結(jié)果的相似程度，而且還與其執(zhí)行有關(guān)聚類方法的好壞也與他發(fā)現(xiàn)部分或全部潛在模式的能力有關(guān)05二月2023DataMining:ConceptsandTechniques6衡量聚類的質(zhì)量相異/相似尺度:我們用距離函數(shù)d(i,j)來(lái)表示相似度。有獨(dú)立的“質(zhì)量”函數(shù)來(lái)衡量聚類的好壞對(duì)區(qū)間標(biāo)度變量，布爾變量，分類變量，序數(shù)變量，向量的距離函數(shù)的定義方式是不同的.不同的應(yīng)用或數(shù)據(jù)含義，其衡量方法應(yīng)該不同很難定義“足夠相似”或“足夠好”

結(jié)果往往是高度主觀的05二月2023DataMining:ConceptsandTechniques7數(shù)據(jù)挖掘中聚類的要求

可伸縮性具有處理不同類型屬性的能力具有處理動(dòng)態(tài)數(shù)據(jù)的能力發(fā)現(xiàn)任意形狀的聚類對(duì)于決定輸入的參數(shù)的領(lǐng)域知識(shí)需求最小可以處理噪聲和離群點(diǎn)不依賴于對(duì)象的輸入次序高維性基于約束的聚類可釋性和可用性05二月2023DataMining:ConceptsandTechniques8第七章聚類分析什么是聚類分析？聚類分析中的數(shù)據(jù)類型聚類分析的主要方法分類劃分方法層次方法基于密度的方法基于網(wǎng)格的方法基于模型的方法聚類高維數(shù)據(jù)基于約束的聚類分析

離群點(diǎn)分析小結(jié)05二月2023DataMining:ConceptsandTechniques9數(shù)據(jù)結(jié)果數(shù)據(jù)矩陣(二模)相異度矩陣(單模)05二月2023DataMining:ConceptsandTechniques10聚類分析中的數(shù)據(jù)類型區(qū)間標(biāo)度變量二元變量分類、序數(shù)、和比例表度變量混合類型的變量05二月2023DataMining:ConceptsandTechniques11區(qū)間標(biāo)度變量數(shù)據(jù)標(biāo)準(zhǔn)化計(jì)算均值絕對(duì)誤差其中計(jì)算標(biāo)準(zhǔn)度量值(z-score)使用均值絕對(duì)誤差比使用標(biāo)準(zhǔn)度量值穩(wěn)定05二月2023DataMining:ConceptsandTechniques12對(duì)象間的相似度和相異度通常用距離來(lái)描述對(duì)象間的相似度或相異度最常用的是閔可夫斯基距離其中i=(xi1,xi2,…,xip)和j=(xj1,xj2,…,xjp)是兩個(gè)p維數(shù)據(jù)，q是一個(gè)正整數(shù)。當(dāng)q=1時(shí)，d是曼哈頓距離05二月2023DataMining:ConceptsandTechniques13對(duì)象間的相似度和相異度當(dāng)q=2時(shí)，d為歐氏距離:d應(yīng)滿足的要求d(i,j)

0d(i,i)

=0d(i,j)

=d(j,i)d(i,j)

d(i,k)

+d(k,j)當(dāng)然，我們也可以用加權(quán)距離或是其他的相異度衡量方法05二月2023DataMining:ConceptsandTechniques14二元變量二元變量的相依表使用對(duì)稱二元變量描述對(duì)象間的距離：使用非對(duì)稱二元變量描述對(duì)象間的距離：Jaccard系數(shù)(非對(duì)稱二元變量相似度):ObjectiObjectj05二月2023DataMining:ConceptsandTechniques15二元變量間的相異度例：性別是對(duì)稱屬性剩下的屬性為非對(duì)稱二元變量令，Y=P=1,N=005二月2023DataMining:ConceptsandTechniques16分類變量一般的變量都不是二元變量，是可以取多于兩個(gè)狀態(tài)值的。如：紅色，黃色，藍(lán)色，綠色。方法1:不匹配率m:匹配的數(shù)目，p:全部變量的數(shù)目方法2:使用多個(gè)二元變量為每個(gè)分類變量的狀態(tài)創(chuàng)建一個(gè)新的二元變量05二月2023DataMining:ConceptsandTechniques17序數(shù)變量序數(shù)變量可以是離散的或是連續(xù)的序數(shù)是很重要的，如：等級(jí)。可以當(dāng)做是區(qū)間標(biāo)度變量來(lái)對(duì)待將

xif

替換成他的秩

將每個(gè)變量的值映射到區(qū)間[0,1]內(nèi)，這可以通過(guò)用代替第f個(gè)變量的第i個(gè)對(duì)象來(lái)實(shí)現(xiàn)利用求區(qū)間標(biāo)度變量相異度的方法來(lái)計(jì)算序數(shù)變量的相異度05二月2023DataMining:ConceptsandTechniques18比例標(biāo)度變量比例表度變量:在非線性的刻度（例如指數(shù)刻度）取正的度量值，近似的遵循下面的公式：

AeBt

或Ae-Bt

方法：采用處理區(qū)間標(biāo)度變量的方法——并不是一個(gè)好的方法（比例可能被扭曲了）對(duì)比例標(biāo)度進(jìn)行對(duì)數(shù)變化yif=log(xif)將其看做連續(xù)的序數(shù)數(shù)據(jù)，將其秩看做區(qū)間標(biāo)度變量05二月2023DataMining:ConceptsandTechniques19混合類型的變量一個(gè)數(shù)據(jù)庫(kù)可能含有所以以上六種類型的變量對(duì)稱二元變量，非對(duì)稱二元變量，分類變量，序數(shù)變量，區(qū)間標(biāo)度變量和比例標(biāo)度變量用有效的公式將他們一起處理f

是二元變量或分類變量:dij(f)=0ifxif=xjf,ordij(f)=1否則f

是區(qū)間標(biāo)度變量:使用標(biāo)準(zhǔn)距離f

是序數(shù)或比例標(biāo)度變量計(jì)算秩rif

和zif

并將zif看做區(qū)間標(biāo)度變量05二月2023DataMining:ConceptsandTechniques20向量對(duì)象向量對(duì)象:文獻(xiàn)中的關(guān)鍵詞，微陣列中的基因特征等。廣泛應(yīng)用:信息檢索,生物學(xué)分類等.余弦度量Tanimoto系數(shù)05二月2023DataMining:ConceptsandTechniques21第七章聚類分析什么是聚類分析？聚類分析中的數(shù)據(jù)類型聚類分析的主要方法分類劃分方法層次方法基于密度的方法基于網(wǎng)格的方法基于模型的方法聚類高維數(shù)據(jù)基于約束的聚類分析

離群點(diǎn)分析小結(jié)05二月2023DataMining:ConceptsandTechniques22主要的聚類分析方法（I）劃分法:將給定的數(shù)據(jù)，按照一定的標(biāo)準(zhǔn)構(gòu)建k劃分。典型的有：k均值法，k中心點(diǎn)算法，CLARA(聚類大型應(yīng)用)。層次方法：

按照一定的標(biāo)準(zhǔn)，創(chuàng)建給定數(shù)據(jù)對(duì)象集的層次分解。典型的有：Diana,Agnes,BIRCH,ROCK,CAMELEON基于密度的方法：

基于密度或鏈接函數(shù)典型的有：DBSACN,OPTICS,DenClue05二月2023DataMining:ConceptsandTechniques23主要的聚類分析方法(II)基于網(wǎng)格的方法：

基于多層粒度結(jié)構(gòu)經(jīng)典的方法:STING,WaveCluster,CLIQUE基于模型的方法:為每個(gè)簇假定一個(gè)模型，并尋找數(shù)據(jù)對(duì)給定模型的最佳擬合。經(jīng)典的有：

EM,SOM,COBWEB基于頻繁模式的方法:基于對(duì)頻繁模式的分析。經(jīng)典的方法:pCluster基于約束的方法:結(jié)合用戶給定或面向應(yīng)用的特殊約束進(jìn)行聚類經(jīng)典的方法:COD(含障礙物),基于約束的聚類05二月2023DataMining:ConceptsandTechniques24常用的計(jì)算簇間距離的方法單鏈接:使用兩個(gè)簇的元素間的最小距離作為簇間距離即：dis(Ki,Kj)=min(tip,tjq)完全鏈接:使用兩個(gè)簇間的元素的最大距離作為簇間距離即：dis(Ki,Kj)=max(tip,tjq)平均值:使用兩個(gè)簇的元素間距離的平均值作為簇間距離即：dis(Ki,Kj)=avg(tip,tjq)質(zhì)心:使用兩個(gè)簇的質(zhì)心的距離作為簇間距離即：dis(Ki,Kj)=dis(Ci,Cj)中心點(diǎn):使用兩個(gè)簇的中心點(diǎn)的距離作為簇間距離即：dis(Ki,Kj)=dis(Mi,Mj)05二月2023DataMining:ConceptsandTechniques25簇的質(zhì)心，半徑，直徑

(fornumericaldatasets)質(zhì)心:簇的“中央”半徑:簇中元素到其質(zhì)心的距離的平均值的平方根直徑:沒(méi)對(duì)元素的距離的平均值的平方根05二月2023DataMining:ConceptsandTechniques26第七章聚類分析什么是聚類分析？聚類分析中的數(shù)據(jù)類型聚類分析的主要方法分類劃分方法層次方法基于密度的方法基于網(wǎng)格的方法基于模型的方法聚類高維數(shù)據(jù)基于約束的聚類分析

離群點(diǎn)分析小結(jié)05二月2023DataMining:ConceptsandTechniques27劃分算法：基本概念劃分方法：

將給定n個(gè)對(duì)象的數(shù)據(jù)集D，劃分成k個(gè)簇，使得：平方距離和最小給定k，找到一個(gè)k劃分，找一個(gè)又劃分標(biāo)準(zhǔn)來(lái)判斷是最優(yōu)的k劃分全局最優(yōu):窮舉法啟發(fā)式的方法:k均值法和k中心點(diǎn)法K均值法

(MacQueen’67):每個(gè)簇由其中心來(lái)代替k-medoidsorPAM(Partitionaroundmedoids)(Kaufman&Rousseeuw’87):每個(gè)簇由其中的一個(gè)元素來(lái)代替05二月2023DataMining:ConceptsandTechniques28K均值聚類方法給定k，k均值算法的處理流程有以下四步組成：將數(shù)據(jù)集分成k個(gè)非空的子集計(jì)算當(dāng)前每個(gè)簇的質(zhì)心作為種子結(jié)點(diǎn)（質(zhì)心是簇的中心點(diǎn)，或是平均值點(diǎn)）將每個(gè)對(duì)象指派到離他最近的種子結(jié)點(diǎn)的簇回到第二步，知道指派結(jié)果不再變動(dòng)05二月2023DataMining:ConceptsandTechniques29K均值聚類方法例：012345678910012345678910012345678910012345678910K=2任意選擇k個(gè)對(duì)象作為最初的簇的質(zhì)心將每個(gè)對(duì)象指派到最相似的簇更新簇的質(zhì)心更新簇的質(zhì)心重新指派reassign05二月2023DataMining:ConceptsandTechniques30K均值法的優(yōu)缺點(diǎn)優(yōu)點(diǎn):

效率很高:算法時(shí)間復(fù)雜度為O(tkn),其中，n為給定對(duì)象的數(shù)目，k是給定要?jiǎng)澐值拇氐膫€(gè)數(shù)，t是指反復(fù)迭代次數(shù)，通常k,t<<n.相比之下:PAM:O(k(n-k)2),CLARA:O(ks2+k(n-k))注:

常常會(huì)停留在局部最優(yōu)處，而達(dá)不到全局最優(yōu)。要找到全局最優(yōu)往往要使用確定的退火算法或是遺傳算法缺點(diǎn)：只適用于均值已被定義的情況，不能用于分類數(shù)據(jù)等。?需要預(yù)先指定要?jiǎng)澐值拇氐膫€(gè)數(shù)不能處理噪聲或離群點(diǎn)不適于尋找圖形不規(guī)則的簇05二月2023DataMining:ConceptsandTechniques31改進(jìn)k均值算法改進(jìn)的k均值算法的幾個(gè)不同之處：挑選最初的k個(gè)均值計(jì)算相異度計(jì)算簇均值的算法可以處理分類數(shù)據(jù)的算法:k眾數(shù)(Huang’98)用眾數(shù)替代簇的均值使用新的相異度衡量方法來(lái)處理分類數(shù)據(jù)使用基于頻率的方法來(lái)更新簇的眾數(shù)處理數(shù)值數(shù)據(jù)和分類數(shù)據(jù)的混合類型:k-原型算法05二月2023DataMining:ConceptsandTechniques32K均值算法的問(wèn)題Method?K均值算法對(duì)離群點(diǎn)非常敏感!因?yàn)橐粋€(gè)對(duì)象如果具有很大的值，會(huì)對(duì)均值產(chǎn)生很大的影響，明顯的扭曲數(shù)據(jù)的分布狀態(tài).K中心點(diǎn)法:用中心點(diǎn)來(lái)代替簇的均值，中心點(diǎn)就是簇的最中央的那個(gè)對(duì)象。01234567891001234567891001234567891001234567891005二月2023DataMining:ConceptsandTechniques33K中心點(diǎn)聚類算法找到簇的中心點(diǎn)作為簇的代表對(duì)象PAM(圍繞中心點(diǎn)的劃分，1987)在隨機(jī)的選取k個(gè)代表對(duì)象做為中心點(diǎn)后，反復(fù)選擇簇的更好的代表對(duì)象。當(dāng)數(shù)據(jù)集很小時(shí)，PAM的效率是很高的，但是不適用于大的數(shù)據(jù)集CLARA

（聚類大型應(yīng)用）(Kaufmann&Rousseeuw,1990)CLARANS

（基于隨機(jī)搜索的聚類大型應(yīng)用）(Ng&Han,1994):RandomizedsamplingFocusing+spatialdatastructure(Esteretal.,1995)05二月2023DataMining:ConceptsandTechniques34經(jīng)典的k中心算法

(PAM)TotalCost=20012345678910012345678910K=2隨機(jī)的選擇k個(gè)對(duì)象作為代表對(duì)象將剩余的對(duì)象指派給離其最近的那個(gè)對(duì)象的簇隨機(jī)的選取一個(gè)不是代表對(duì)象的對(duì)象Oramdom計(jì)算總的交換開(kāi)銷012345678910012345678910總開(kāi)銷

=26如果情況變好了就交換O和Oramdom循環(huán)，直至情況不再改變01234567891001234567891005二月2023DataMining:ConceptsandTechniques35PAM(圍繞中心點(diǎn)的劃分)(1987)PAM(KaufmanandRousseeuw,1987),builtinSplus使用實(shí)際的對(duì)象作為代表對(duì)象任選k個(gè)對(duì)象作為代表對(duì)象對(duì)任意一對(duì)沒(méi)被選中的對(duì)象h和被選中的對(duì)象i計(jì)算總的交換開(kāi)銷TCih對(duì)任意一對(duì)

i

和

h,如果

TCih<0,h則用h來(lái)代替i然后將每個(gè)沒(méi)被選中的對(duì)象指派到最近的代表對(duì)象的簇重復(fù)第2-3步，直至結(jié)果不在改變05二月2023DataMining:ConceptsandTechniques36PAM聚類:總的交換開(kāi)銷

TCih=jCjihjihttihjhitjtihj05二月2023DataMining:ConceptsandTechniques37PAM算法的問(wèn)題在處理有離群點(diǎn)或噪聲的數(shù)據(jù)時(shí)PAM算法要比k均值算法穩(wěn)定，因?yàn)殡x群點(diǎn)或其他具有極端值的點(diǎn)對(duì)中心點(diǎn)的影響要小于對(duì)均值的影響PAM算法在處理小數(shù)據(jù)集的對(duì)象是效率很高的，但不適用于數(shù)據(jù)集很大的情況.每次迭代需要進(jìn)行O(k(n-k)2

步

其中，n是對(duì)象的個(gè)數(shù)，k是劃分成的簇的個(gè)數(shù)基于取樣的方法,

CLARA(聚類大型應(yīng)用)05二月2023DataMining:ConceptsandTechniques38CLARA(聚類大型應(yīng)用)(1990)CLARA(KaufmannandRousseeuwin1990)用于統(tǒng)計(jì)學(xué)數(shù)據(jù)包分析，如S+對(duì)數(shù)據(jù)進(jìn)行多重抽樣，對(duì)每個(gè)抽樣的樣本用PAM算法聚類優(yōu)點(diǎn):可以處理比PAM算法能處理的大的數(shù)據(jù)集缺陷:有效性取決于抽樣大小如果取樣偏執(zhí)了，那么對(duì)取樣的一個(gè)好的聚類并不能代表對(duì)整個(gè)數(shù)據(jù)的好的聚類05二月2023DataMining:ConceptsandTechniques39CLARANS(基于隨機(jī)搜索的CLARA)(1994)CLARANS(基于隨機(jī)搜索的聚類算法)(NgandHan’94)CLARANS動(dòng)態(tài)的抽取緊鄰的隨機(jī)樣本聚類的過(guò)程可以看做搜素一個(gè)圖，圖中的每個(gè)結(jié)點(diǎn)是一個(gè)潛在解。當(dāng)達(dá)到局部最優(yōu)時(shí)，CLARANS會(huì)隨機(jī)的選擇一個(gè)新的結(jié)點(diǎn)開(kāi)始，尋找新的局部最優(yōu)他比PAM和CLARA算法更有效。通過(guò)利用空間數(shù)據(jù)結(jié)構(gòu)的聚焦技術(shù)，可以進(jìn)一步提高該算法的能力(Esteretal.’95)05二月2023DataMining:ConceptsandTechniques40第七章聚類分析什么是聚類分析？聚類分析中的數(shù)據(jù)類型聚類分析的主要方法分類劃分方法層次方法基于密度的方法基于網(wǎng)格的方法基于模型的方法聚類高維數(shù)據(jù)基于約束的聚類分析

離群點(diǎn)分析小結(jié)05二月2023DataMining:ConceptsandTechniques41層次方法使用距離矩陣作為聚類標(biāo)準(zhǔn)。此方法不需要輸入簇的個(gè)數(shù)k，但是需要終止條件Step0Step1Step2Step3Step4bdceaabdecdeabcdeStep4Step3Step2Step1Step0凝聚層次聚類法(AGNES)分裂層次聚類法(DIANA)05二月2023DataMining:ConceptsandTechniques42AGNES(凝聚層次聚類法)IntroducedinKaufmannandRousseeuw(1990)執(zhí)行統(tǒng)計(jì)數(shù)據(jù)分析，

如：Splus使用單連接方法，和相異度矩陣

合并相異度最小的結(jié)點(diǎn)采用非遞減模式進(jìn)行最終，所有的結(jié)點(diǎn)都凝聚成一個(gè)簇05二月2023DataMining:ConceptsandTechniques43樹(shù)狀圖:

簇是如何合并的Decomposedataobjectsintoaseverallevelsofnestedpartitioning(treeofclusters),calledadendrogram.Aclusteringofthedataobjectsisobtainedbycuttingthedendrogramatthedesiredlevel,theneachconnectedcomponentformsacluster.05二月2023DataMining:ConceptsandTechniques44DIANA(分裂層次聚類)IntroducedinKaufmannandRousseeuw(1990)執(zhí)行統(tǒng)計(jì)數(shù)據(jù)分析如：SplusAGNES的逆序過(guò)程最終每個(gè)結(jié)點(diǎn)構(gòu)成一個(gè)簇05二月2023DataMining:ConceptsandTechniques45最新的層次聚類分析法凝聚算法的主要缺陷不可伸縮型:時(shí)間復(fù)雜度至少是O(n2)不能取消以前的工作結(jié)合層次法和基于距離的方法的聚類BIRCH(1996):使用CF樹(shù)，對(duì)對(duì)象的增量和動(dòng)態(tài)聚類也非常有效ROCK(1999):對(duì)分類屬性數(shù)據(jù)使用了鏈接，通過(guò)考慮成對(duì)點(diǎn)鄰域情況進(jìn)行聚類CHAMELEON(1999):使用動(dòng)態(tài)建模的層次聚類算法05二月2023DataMining:ConceptsandTechniques46BIRCH(1996)Birch:利用層次方法的平衡迭代規(guī)約和聚類IncrementallyconstructaCF(ClusteringFeature)tree,ahierarchicaldatastructureformultiphaseclustering階段1：掃描DB在內(nèi)存中創(chuàng)建初始的CFtree階段2：使用任意聚類算法聚類CFtree的葉節(jié)點(diǎn)

線性增長(zhǎng):掃描一次就可以的到較好的聚類，如果增加掃描次數(shù)就可以提高聚類質(zhì)量缺陷：

只能處理數(shù)值數(shù)據(jù),而且對(duì)數(shù)據(jù)的輸入次序敏感05二月2023DataMining:ConceptsandTechniques47用BIRCH聚類特征向量聚類特征:

CF=(N,LS,SS)N:數(shù)據(jù)點(diǎn)個(gè)數(shù)LS:Ni=1=XiSS:Ni=1=Xi2CF=(5,(16,30),(54,190))(3,4)(2,6)(4,5)(4,7)(3,8)05二月2023DataMining:ConceptsandTechniques48BIRCH中的CF-Tree聚類特征:給定簇的統(tǒng)計(jì)匯總，他是簇的0階矩，一階矩，二階矩匯總對(duì)象簇的主要信息，避免存儲(chǔ)所有對(duì)象，有效地利用了存儲(chǔ)空間CFtree是一個(gè)高度平衡樹(shù)，他儲(chǔ)存了層次聚類的聚類特征

非葉節(jié)點(diǎn)有子女或后裔非葉節(jié)點(diǎn)存儲(chǔ)其子女的CF總和CFtree有兩個(gè)參數(shù)分支因子：定義了每個(gè)非葉結(jié)點(diǎn)的子女的最大數(shù)目.閾值:存儲(chǔ)在樹(shù)的葉節(jié)點(diǎn)中子簇的最大直徑05二月2023DataMining:ConceptsandTechniques49CFTree的結(jié)構(gòu)CF1child1CF3child3CF2child2CF6child6CF1child1CF3child3CF2child2CF5child5CF1CF2CF6prevnextCF1CF2CF4prevnextB=7L=6RootNon-leafnodeLeafnodeLeafnode05二月2023DataMining:ConceptsandTechniques50聚類分類數(shù)據(jù):ROCK算法ROCK:RObustClusteringusinglinKsS.Guha,R.Rastogi&K.Shim,ICDE’99主要思想使用鏈接來(lái)衡量相似度/相異度不急于距離計(jì)算復(fù)雜度:算法:基于取樣的聚類隨機(jī)取樣采用鏈接聚類在磁盤中標(biāo)號(hào)數(shù)據(jù)實(shí)驗(yàn)議會(huì)選舉,迅速增長(zhǎng)的數(shù)據(jù)05二月2023DataMining:ConceptsandTechniques51ROCK中的相似度衡量傳統(tǒng)的方法無(wú)法很好的衡量分類數(shù)據(jù)的相似度，如，Jaccard系數(shù)例如：兩個(gè)事務(wù)簇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}Jaccard系數(shù)會(huì)得到錯(cuò)誤的聚類結(jié)果C1:0.2({a,b,c},{b,d,e}}to0.5({a,b,c},{a,b,d})C1&C2:couldbeashighas0.5({a,b,c},{a,b,f})基于Jaccard系數(shù)的相似度: 例.令

T1={a,b,c},T2={c,d,e}05二月2023DataMining:ConceptsandTechniques52ROCK中的鏈接方法鏈接：公共緊鄰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}LetT1={a,b,c},T2={c,d,e},T3={a,b,f}link(T1,T2)=4,因?yàn)樗麄冇兴膫€(gè)公共近鄰{a,c,d},{a,c,e},{b,c,d},{b,c,e}link(T1,T3)=3,他們有3個(gè)公共近鄰{a,b,d},{a,b,e},{a,b,g}所以鏈接法比Jaccard系數(shù)更為有效05二月2023DataMining:ConceptsandTechniques53CHAMELEON:利用動(dòng)態(tài)建模的層次聚類法CHAMELEON:byG.Karypis,E.H.Han,andV.Kumar’99基于動(dòng)態(tài)建模來(lái)衡量相似度如果兩個(gè)簇的互聯(lián)性都很高并且它們又靠的很近就將其合并

Cure

忽略了簇的互聯(lián)性，Rock

忽略了關(guān)于簇的鄰近度信息算法分為兩個(gè)階段使用圖劃分算法：將對(duì)象劃分為相對(duì)較小的字簇使用凝聚層次聚類算法：通過(guò)反復(fù)合并子簇來(lái)找到最終的簇05二月2023DataMining:ConceptsandTechniques54CHAMELEON的工作框架構(gòu)造稀疏圖劃分圖合并劃分最終的簇?cái)?shù)據(jù)集05二月2023DataMining:ConceptsandTechniques55CHAMELEON(聚類復(fù)雜對(duì)象)05二月2023DataMining:ConceptsandTechniques56第七章聚類分析什么是聚類分析？聚類分析中的數(shù)據(jù)類型聚類分析的主要方法分類劃分方法層次方法基于密度的方法基于網(wǎng)格的方法基于模型的方法聚類高維數(shù)據(jù)基于約束的聚類分析

離群點(diǎn)分析小結(jié)05二月2023DataMining:ConceptsandTechniques57基于密度的聚類方法Clusteringbasedondensity(localclustercriterion),suchasdensity-connectedpoints主要特征:可以發(fā)現(xiàn)任意形狀的簇可以處理喊噪聲的數(shù)據(jù)一次掃描需要給出密度參數(shù)的終止條件典型算法DBSCAN:Ester,etal.(KDD’96)OPTICS:Ankerst,etal(SIGMOD’99).DENCLUE:Hinneburg&D.Keim(KDD’98)CLIQUE:Agrawal,etal.(SIGMOD’98)(moregrid-based)05二月2023DataMining:ConceptsandTechniques58基于密度聚類的基本概念兩個(gè)參數(shù):Eps:鄰域的最大半徑MinPts:對(duì)象鄰域內(nèi)最少點(diǎn)數(shù)NEps(p): {q屬于D|dist(p,q)<=Eps}直接密度可達(dá):對(duì)象p從對(duì)象q出發(fā)時(shí)直接密度可達(dá)的，如果

P屬于

NEps(q)核心對(duì)象條件:|NEps(q)|>=MinPts

pqMinPts=5Eps=1cm05二月2023DataMining:ConceptsandTechniques59密度可達(dá)和密度相連密度可達(dá):P是從q密度可達(dá)的，如果存在一連串的對(duì)象p1,…,pn,p1=q,pn=p

使得pi+1從

pi

出發(fā)直接密度可達(dá)密度相連P和q是密度互連的，如果存在o使得p和q都是從o出發(fā)密度可達(dá)的pqp1pqo05二月2023DataMining:ConceptsandTechniques60DBSCAN:基于高密度連同區(qū)域的基于密度的聚類方法依賴基于密度理論的分類：密度互連的對(duì)象組成的最大集合為一個(gè)簇在有噪聲的空間數(shù)據(jù)庫(kù)中可以發(fā)現(xiàn)任意形狀的簇CoreBorderOutlierEps=1cmMinPts=505二月2023DataMining:ConceptsandTechniques61DBSCAN:算法任選一個(gè)對(duì)象p找到所有從p出發(fā)密度可達(dá)的對(duì)象（給定Eps和MinPts）如果p是核心對(duì)象，則形成一個(gè)簇如果p是邊界對(duì)象，則沒(méi)有對(duì)象從p出發(fā)直接密度可達(dá)，DBSCAN則會(huì)選擇數(shù)據(jù)庫(kù)中的另外一個(gè)對(duì)象重復(fù)上述步驟，直至所有的對(duì)象都被處理過(guò)05二月2023DataMining:ConceptsandTechniques62DBSCAN:對(duì)參數(shù)的敏感性05二月2023DataMining:ConceptsandTechniques63CHAMELEON(聚類復(fù)雜對(duì)象)05二月2023DataMining:ConceptsandTechniques64OPTICS:排序聚類方法(1999)OPTICS:通過(guò)點(diǎn)排序識(shí)別聚類結(jié)構(gòu)Ankerst,Breunig,Kriegel,andSander(SIGMOD’99)根據(jù)基于密度的分類結(jié)構(gòu)產(chǎn)生簇排序

該簇排序包含的信息等價(jià)于從一個(gè)廣泛的參數(shù)設(shè)置所獲得的基于密度的聚類有利于自動(dòng)或交互式聚類分析，并能提供內(nèi)在的聚類結(jié)構(gòu)可以用圖表示，或者其他的可視化工具05二月2023DataMining:ConceptsandTechniques65OPTICS:對(duì)DBSCAN一些擴(kuò)展基于索引:

k=維數(shù)N=20p=75%M=N(1-p)=5Complexity:O(kN2)核心距離可達(dá)距離Dp2MinPts=5e=3cmMax(core-distance(o),d(o,p))r(p1,o)=2.8cm.r(p2,o)=4cmoop105二月2023DataMining:ConceptsandTechniques66可達(dá)距離Cluster-orderoftheobjects無(wú)定義‘05二月2023DataMining:ConceptsandTechniques67基于密度聚類:OPTICS及其應(yīng)用05二月2023DataMining:ConceptsandTechniques68DENCLUE:使用密度分布函數(shù)DENsity-basedCLUstEringbyHinneburg&Keim(KDD’98)使用密度分布函數(shù):主要特征固定的數(shù)學(xué)基礎(chǔ)可以處理含有大量噪聲的數(shù)據(jù)可以對(duì)高維數(shù)據(jù)集中任意形狀的簇做簡(jiǎn)潔的數(shù)學(xué)描述比現(xiàn)有的其他算法要快得多(e.g.,DBSCAN)但是需要大量的參數(shù)05二月2023DataMining:ConceptsandTechniques69使用網(wǎng)格單元，但是只保存網(wǎng)格單元中實(shí)際包含的數(shù)據(jù)點(diǎn)的個(gè)數(shù)信息，并用樹(shù)結(jié)構(gòu)來(lái)管理這些網(wǎng)格影響函數(shù):描述數(shù)據(jù)點(diǎn)在其鄰域內(nèi)的影響數(shù)據(jù)空間的整體密度可以用所有數(shù)據(jù)點(diǎn)的影響函數(shù)計(jì)算出簇可以通過(guò)識(shí)別密度吸引點(diǎn)數(shù)學(xué)確定密度吸引點(diǎn)是全局密度函數(shù)的局部極大值Denclue:基本技術(shù)05二月2023DataMining:ConceptsandTechniques70密度吸引點(diǎn)05二月2023DataMining:ConceptsandTechniques71Center-DefinedandArbitrary05二月2023DataMining:ConceptsandTechniques72第七章聚類分析什么是聚類分析？聚類分析中的數(shù)據(jù)類型聚類分析的主要方法分類劃分方法層次方法基于密度的方法基于網(wǎng)格的方法基于模型的方法聚類高維數(shù)據(jù)基于約束的聚類分析

離群點(diǎn)分析小結(jié)05二月2023DataMining:ConceptsandTechniques73基于網(wǎng)格的聚類方法使用多分辨率的網(wǎng)格數(shù)據(jù)結(jié)構(gòu)相關(guān)的方法STING(aSTatisticalINformationGridapproach)byWang,YangandMuntz(1997)WaveClusterbySheikholeslami,Chatterjee,andZhang(VLDB’98)利用小波變換的多分辨率聚類方法CLIQUE:Agrawal,etal.(SIGMOD’98)處理高維數(shù)據(jù)05二月2023DataMining:ConceptsandTechniques74STING:統(tǒng)計(jì)信息網(wǎng)格法Wang,YangandMuntz(VLDB’97)將空間區(qū)域分成矩形單元存在多級(jí)矩形單元對(duì)應(yīng)不同級(jí)別的分辨率05二月2023DataMining:ConceptsandTechniques75STING聚類方法每個(gè)高層單元?jiǎng)澐殖啥鄠€(gè)低一層的單元將每個(gè)單元的統(tǒng)計(jì)信息都計(jì)算并存儲(chǔ)起來(lái)，用于查詢處理高層單元的統(tǒng)計(jì)參數(shù)可以很容易的從低層單元的參數(shù)計(jì)算得到計(jì)數(shù)，均值，標(biāo)準(zhǔn)差，最大值，最小值分布類型—正態(tài)的，均勻的等.使用從頂向下方法回答空間數(shù)據(jù)查詢從預(yù)先選定的一層開(kāi)始，通常該層含有較少量的單元對(duì)當(dāng)前層的每個(gè)單元計(jì)算器相關(guān)的置信度區(qū)間

05二月2023DataMining:ConceptsandTechniques76STING刪除不相關(guān)的單元，不再進(jìn)一步考慮處理完當(dāng)前層后處理下一個(gè)較低層

重復(fù)此過(guò)程，直至達(dá)到最低層優(yōu)點(diǎn):不依賴于查詢信息，有利于并行處理和增量更新時(shí)間復(fù)雜度為：O(K),其中k是最低層網(wǎng)格單元的數(shù)量缺點(diǎn):所有簇的邊界不是水平的就是豎直的，沒(méi)有斜的分界線05二月2023DataMining:ConceptsandTechniques77WaveCluster:利用小波分析聚類(1998)Sheikholeslami,Chatterjee,andZhang(VLDB’98)對(duì)特征空間進(jìn)行小波變換的多分辨率聚類方法如何應(yīng)用小波變換來(lái)找到簇通過(guò)在數(shù)據(jù)空間強(qiáng)加一個(gè)多維網(wǎng)格結(jié)構(gòu)來(lái)匯總數(shù)據(jù)用一個(gè)n為特征空間來(lái)代替這些多維空間數(shù)據(jù)對(duì)特征空間進(jìn)行小波變換，在變換后的空間中發(fā)現(xiàn)密集區(qū)域多次應(yīng)用小波變換05二月2023DataMining:ConceptsandTechniques78小波變換小波變換:一種信號(hào)處理技術(shù)，它將一個(gè)信號(hào)分解成不同頻率的子波段數(shù)據(jù)變換，以便在不同的分辨率水平保留對(duì)象間的相對(duì)距離使得數(shù)據(jù)的自然簇變得更加容易分辨05二月2023DataMining:ConceptsandTechniques79WaveCluster算法輸入?yún)?shù)#ofgridcellsforeachdimensionthewavelet,andthe#ofapplicationsofwavelettransform在聚類中為什么可以用小波變換?使用帽子形狀的過(guò)濾器來(lái)強(qiáng)調(diào)尖端簇區(qū)域，同時(shí)弱化其邊界的信息

有效地去除離群點(diǎn)，多分辨率，開(kāi)銷低主要特征:復(fù)雜度O(N)可以發(fā)現(xiàn)任意形狀的簇對(duì)噪聲和數(shù)據(jù)的輸入順序不敏感僅適用于低維數(shù)據(jù)基于網(wǎng)格與基于密度相結(jié)合05二月2023DataMining:ConceptsandTechniques80分層與變換首先將數(shù)據(jù)分成m維網(wǎng)格結(jié)構(gòu)，然后應(yīng)用小波變換a)scale1:高分辨率b)scale2:中等分辨率c)scale3:低分辨率05二月2023DataMining:ConceptsandTechniques81第七章聚類分析什么是聚類分析？聚類分析中的數(shù)據(jù)類型聚類分析的主要方法分類劃分方法層次方法基于密度的方法基于網(wǎng)格的方法基于模型的方法聚類高維數(shù)據(jù)基于約束的聚類分析

離群點(diǎn)分析小結(jié)05二月2023DataMining:ConceptsandTechniques82基于模型的聚類什么是基于模型的聚類?優(yōu)化給定數(shù)據(jù)與某個(gè)數(shù)學(xué)模型間的擬合

基于這個(gè)假設(shè)，數(shù)據(jù)根據(jù)潛在的混合概率分布生成典型方法統(tǒng)計(jì)方法EM(Expectationmaximization),AutoClass機(jī)器學(xué)習(xí)法MachinelearningapproachCOBWEB,CLASSIT神經(jīng)網(wǎng)絡(luò)法NeuralnetworkapproachSOM(Self-OrganizingFeatureMap)05二月2023DataMining:ConceptsandTechniques83EM—期望最大化EM—一種流行的迭代求精算法可以看做是k均值法的擴(kuò)展根據(jù)一個(gè)代表隸屬度概率的權(quán)重將對(duì)象指派到簇(prob.distribution)新的均值基于加權(quán)的重量來(lái)計(jì)算主要思想對(duì)參數(shù)進(jìn)行初始猜測(cè)反復(fù)估計(jì)參數(shù)來(lái)產(chǎn)生的混合密度對(duì)每個(gè)對(duì)象重新打分重新打分后的對(duì)象又用來(lái)更新參數(shù)估計(jì)每個(gè)對(duì)象賦予一個(gè)概率，假定它是給定簇的成員，具有一定屬性值集合的可能性。算法收斂很快，但可能達(dá)不到全局最優(yōu)05二月2023DataMining:ConceptsandTechniques84EM算法隨機(jī)的選取k個(gè)對(duì)象代表簇的均值或中心按如下兩個(gè)步驟反復(fù)求精參數(shù)

期望步：用以下概率將每個(gè)對(duì)象XiXi

指派到簇Ck最大化步:估計(jì)模型參數(shù)05二月2023DataMining:ConceptsandTechniques85給定一些觀察數(shù)據(jù)x，假設(shè)x符合如下高斯分布：求混合高斯分布的三組參數(shù)05二月2023DataMining:ConceptsandTechniques86該混合高斯分布一共有K個(gè)分布，并且對(duì)于每個(gè)觀察

到的x，如果我們同時(shí)還知道它屬于K中的哪一個(gè)分布，則我們可以根據(jù)最大似然估計(jì)求出每個(gè)參數(shù)。結(jié)論：特別注意是個(gè)向量，而是個(gè)數(shù)值。表示屬于第k個(gè)高斯分布的觀察數(shù)據(jù)x。05二月2023DataMining:ConceptsandTechniques87實(shí)際問(wèn)題觀察數(shù)據(jù)x屬于哪個(gè)高斯分布是未知的，所以要用

EM算法來(lái)解決這種實(shí)際問(wèn)題。05二月2023DataMining:ConceptsandTechniques88EM算法過(guò)程：1、用隨機(jī)函數(shù)初始化K個(gè)高斯分布的參數(shù)，同時(shí)保證Expectation2、依次取觀察數(shù)據(jù)x，比較x在K個(gè)高斯函數(shù)中概率的大小，把x歸類到這K個(gè)高斯中概率最大的一個(gè)。05二月2023DataMining:ConceptsandTechniques89Maximum3、用最大似然估計(jì)，使觀察數(shù)據(jù)是x的概率最大，因?yàn)橐呀?jīng)在第2步中分好類了，所以，即簡(jiǎn)單問(wèn)題的求法。4、返回第2步用第3步新得到的參數(shù)來(lái)對(duì)觀察數(shù)據(jù)x

重新分類。直到下式概率（最大似然函數(shù)）達(dá)到最大。05二月2023DataMining:ConceptsandTechniques90問(wèn)題求解過(guò)程：05二月2023DataMining:ConceptsandTechniques91概念分類概念分類一種機(jī)器學(xué)習(xí)聚類方法給定一組為標(biāo)記的對(duì)象，產(chǎn)生對(duì)象的模式分類找出每組對(duì)象的特征描述，其中每組對(duì)象代表一個(gè)概念或類COBWEB(Fisher’87)

一種流行的、簡(jiǎn)單的、增量概念分類以分類樹(shù)的形式創(chuàng)建層次聚類每個(gè)結(jié)點(diǎn)代表一個(gè)概念，包含對(duì)該概念的概率描述05二月2023DataMining:ConceptsandTechniques92COBWEB聚類方法分類樹(shù)05二月2023DataMining:ConceptsandTechniques93概念分類COBWEB的缺陷它基于這樣一個(gè)假設(shè)，各個(gè)屬性的概念分布是彼此統(tǒng)計(jì)獨(dú)立的。但屬性之間常常存在相關(guān)不適用于聚類大型的數(shù)據(jù)庫(kù)Notsuitableforclusteringlargedatabasedata–skewedtreeandexpensiveprobabilitydistributionsCLASSIT是對(duì)COBWEB的擴(kuò)展，用以處理連續(xù)性數(shù)據(jù)的增量聚類與COBWEB算法存在類似的問(wèn)題

AutoClass(CheesemanandStutz,1996)使用貝葉斯統(tǒng)計(jì)分析法來(lái)估計(jì)簇的數(shù)目在工業(yè)中非常流行05二月2023DataMining:ConceptsandTechniques94神經(jīng)網(wǎng)絡(luò)方法神經(jīng)網(wǎng)絡(luò)方法將每個(gè)簇看成是一個(gè)標(biāo)本，作為簇的原型新的對(duì)象可以根據(jù)某種距離度量分布到其標(biāo)本最相似的簇經(jīng)典的方法SOM(自組織特征映射)競(jìng)爭(zhēng)學(xué)習(xí)法Involvesahierarchicalarchitectureofseveralunits(neurons)神經(jīng)元按照Neuronscompeteina“winner-takes-all”fashionfortheobjectcurrentlybeingpresented05二月2023DataMining:ConceptsandTechniques95自組織特征映射(SOM)SOMs,也稱之為拓?fù)溆行蛴成浠騅ohonen自組織特征映射(KSOMs)目標(biāo)是用低維（通常是2維到3維）目標(biāo)空間的點(diǎn)來(lái)表示高維源空間中的所有點(diǎn)，盡可能的保持點(diǎn)見(jiàn)得距離和鄰近關(guān)系類似于k均值算法:簇的中心往往處于特征或?qū)傩钥臻g的一個(gè)低維流形中聚類通過(guò)若干單元競(jìng)爭(zhēng)當(dāng)前對(duì)象來(lái)進(jìn)行權(quán)重向量最接近當(dāng)前對(duì)象的單元成為贏家或活躍點(diǎn)調(diào)整獲勝單元及其最近鄰的權(quán)重SOM被認(rèn)為類似于大腦的處理過(guò)程對(duì)用2維或3維的方式觀察高維數(shù)據(jù)時(shí)很有效的05二月2023DataMining:ConceptsandTechniques96使用SOM聚類的web文檔用SOM算法對(duì)12088篇web、文章聚類的結(jié)果右邊的圖片：對(duì)關(guān)鍵詞“mining”進(jìn)行下鉆的結(jié)果05二月2023DataMining:ConceptsandTechniques97第七章聚類分析什么是聚類分析？聚類分析中的數(shù)據(jù)類型聚類分析的主要方法分類劃分方法層次方法基于密度的方法基于網(wǎng)格的方法基于模型的方法聚類高維數(shù)據(jù)基于約束的聚類分析

離群點(diǎn)分析小結(jié)05二月2023DataMining:ConceptsandTechniques98聚類高維數(shù)據(jù)聚類高維數(shù)據(jù)應(yīng)用：文本文檔，DNA微序列數(shù)據(jù)主要挑戰(zhàn):很多不相關(guān)的維可能屏蔽真實(shí)的簇距離度量變得無(wú)意義了——數(shù)據(jù)特別稀疏時(shí)位于不同維的數(shù)據(jù)點(diǎn)可以認(rèn)為是等距的簇可能僅存在于某些子空間內(nèi)方法特征變換:僅適用于大部分維都是相關(guān)的情況下如：PCA（主成分分析）和SVD（支撐向量機(jī)）僅適用于特征是高度相關(guān)的/冗余的特征選擇:wrapperorfilterapproachesusefultofindasubspacewherethedatahaveniceclusters子空間聚類：

在所有可能的子空間中尋找簇CLIQUE,ProClus,基于頻繁模式的聚類05二月2023DataMining:ConceptsandTechniques99維災(zāi)難

(graphsadaptedfromParsonsetal.KDDExplorations2004)一維的數(shù)據(jù)通常是在一個(gè)相關(guān)的區(qū)域內(nèi)的增加一個(gè)維，是數(shù)據(jù)點(diǎn)沿這個(gè)維延伸，則會(huì)使數(shù)據(jù)變得分離增加更多的維，會(huì)使得數(shù)據(jù)點(diǎn)之間更加分離，高維數(shù)據(jù)是極端稀疏的數(shù)據(jù)度量變得沒(méi)有意義了—當(dāng)數(shù)據(jù)特別稀疏時(shí)我們可以認(rèn)為位于不同維的數(shù)據(jù)點(diǎn)是距離相等的05二月2023DataMining:ConceptsandTechniques100為什么要對(duì)子空間聚類?

(adaptedfromParsonsetal.SIGKDDExplorations2004)簇可能僅僅是存在于某個(gè)子空間中子空間聚類:找出所有可能的子空間內(nèi)的簇05二月2023DataMining:ConceptsandTechniques101CLIQUE(維增長(zhǎng)子空間聚類方法)

Agrawal,Gehrke,Gunopulos,Raghavan(SIGMOD’98)自動(dòng)的將高維數(shù)據(jù)空間劃分成子空間以便更好的聚類

CLIQUE可以看做是基于密度的也可以看做是基于網(wǎng)格的他將每一維劃分成相同數(shù)目的等距的區(qū)域?qū)⒁粋€(gè)m維的數(shù)據(jù)空間劃分成互不重疊的矩形單元如果一個(gè)單元中包含的數(shù)據(jù)點(diǎn)的個(gè)數(shù)超過(guò)了輸入的參數(shù)則這個(gè)單元為稠密單元同一子空間中彼此相連的稠密單元構(gòu)成的最大集合為一個(gè)簇05二月2023DataMining:ConceptsandTechniques102CLIQUE:主要步驟將數(shù)據(jù)空間劃分，并找到每個(gè)劃分單元中的數(shù)據(jù)點(diǎn)的個(gè)數(shù).找出含有簇的子空間，使用Apriori規(guī)則剪枝確定簇找出所有相關(guān)子空間中的稠密單元找出相關(guān)子空間中的所有相連的稠密單元.生成簇的最小覆蓋（邏輯描述）為每個(gè)簇確定覆蓋所有相連的稠密單元的最大區(qū)域?yàn)槊總€(gè)簇確定一個(gè)最小覆蓋05二月2023DataMining:ConceptsandTechniques103Salary(10,000)2030405060age543126702030405060age54312670Vacation(week)ageVacationSalary3050

=305二月2023DataMining:ConceptsandTechniques104CLIQUE的優(yōu)缺點(diǎn)優(yōu)點(diǎn)自動(dòng)的找出高維數(shù)據(jù)的簇存在的子空間對(duì)數(shù)據(jù)的輸入順序不敏感，不需要假定數(shù)據(jù)的規(guī)范分布

它隨著輸入規(guī)模線性的伸縮，當(dāng)數(shù)據(jù)維數(shù)增加時(shí)具有良好的伸縮性缺點(diǎn)作為算法簡(jiǎn)潔的代價(jià)，聚類結(jié)果的精度可能會(huì)降低05二月2023DataMining:ConceptsandTechniques105基于頻繁模式的方法適合用于高維數(shù)據(jù)(如：聚類文本文檔，微陣列數(shù)據(jù))Projectedsubspace-clustering:whichdimensionstobeprojectedon?CLIQUE,ProClusFeatureextraction:開(kāi)銷大，效率低？使用頻繁模式是因?yàn)槠渚哂邢铝行再|(zhì)頻繁度是固有的性質(zhì)挖掘頻繁模式的開(kāi)銷不是很大經(jīng)典方法基于頻繁項(xiàng)的文件聚類通過(guò)微陣列數(shù)據(jù)分析中的模式相似性聚類(pClustering)05二月2023DataMining:ConceptsandTechniques106基于相似模式的聚類(p-Clustering)右圖：只包含3個(gè)對(duì)象的多維微陣列原始數(shù)據(jù)很難發(fā)現(xiàn)其中的模式下圖：選擇屬性的子集后的平移和縮放模式05二月2023DataMining:ConceptsandTechniques107p-Clustering產(chǎn)生的原因?微陣列數(shù)據(jù)分析需要聚類具有上千屬性的數(shù)據(jù)發(fā)現(xiàn)平移和縮放模式使用歐氏距離聚類？——不能發(fā)現(xiàn)平移模式

對(duì)數(shù)據(jù)變換后得到新的屬性如Aij=ai–aj再對(duì)其聚類?—將引入

N(N-1)個(gè)屬性Bi-cluster使用均方差得分矩陣變換matrix(I,J)其中子矩陣稱為稱為δ-雙簇，如果對(duì)于某個(gè)δ>0有H(I,J)≤δδ雙簇的問(wèn)題δ雙簇的子矩陣不一定是δ雙簇由于取平均的影響，雙簇可能包含一些不符合要求的離群點(diǎn)，但仍滿足一個(gè)非常小的

δ閾值05二月2023DataMining:ConceptsandTechniques108p-Clustering:基于相似模式的聚類給定對(duì)象x,y屬于O，屬性a,b屬于T,pScore（X）是一個(gè)2*2階矩陣如果（O,T）中任意的2*2階矩陣X都有pScore(X)≤δ（δ>0）則（O,T）對(duì)形成pclusterδ-pCluster的性質(zhì)向下閉包性產(chǎn)生的簇比雙簇方法產(chǎn)生的更同源(thusthename:pair-wiseCluster)為了有效的挖掘引入模式增長(zhǎng)算法

用比例模式，取對(duì)數(shù)可以得到pScore的形式為05二月2023DataMining:ConceptsandTechniques109第七章聚類分析什么是聚類分析？聚類分析中的數(shù)據(jù)類型聚類分析的主要方法分類劃分方法層次方法基于密度的方法基于網(wǎng)格的方法基于模型的方法聚類高維數(shù)據(jù)基于約束的聚類分析

離群點(diǎn)分析小結(jié)05二月2023DataMining:ConceptsandTechniques110為什么要有機(jī)遇約束的聚類分析?需要用戶反饋:用戶最了解他們的需求參數(shù)少，但是用戶定義的約束多，05二月2023DataMining:ConceptsandTechniques111基于約束聚類分析的分類聚類應(yīng)用:設(shè)計(jì)有用戶知道的聚類分析聚類分析中的不同約束:對(duì)個(gè)體對(duì)象的約束(應(yīng)首先選擇)聚類價(jià)值在