聚類分析-K-meansandK-medoids聚類1

智能數(shù)據(jù)挖掘Topic3--聚類分析K-means&K-medoids

聚類2023/2/1主要內(nèi)容K-means算法Matlab程序?qū)崿F(xiàn)在圖像分割上的簡單應(yīng)用K-medoids算法k-中心點(diǎn)聚類算法--PAMK-medoids改進(jìn)算法2023/2/1基于劃分的聚類方法構(gòu)造n個(gè)對(duì)象數(shù)據(jù)庫D的劃分,將其劃分成k個(gè)聚類啟發(fā)式方法:k-平均值(k-

means)和k-中心點(diǎn)(k-

medoids)算法k-平均值(MacQueen’67):每個(gè)簇用該簇中對(duì)象的平均值來表示k-中心點(diǎn)或PAM(Partitionaroundmedoids)(Kaufman&Rousseeuw’87):每個(gè)簇用接近聚類中心的一個(gè)對(duì)象來表示這些啟發(fā)式算法適合發(fā)現(xiàn)中小規(guī)模數(shù)據(jù)庫中的球狀聚類對(duì)于大規(guī)模數(shù)據(jù)庫和處理任意形狀的聚類,這些算法需要進(jìn)一步擴(kuò)展2023/2/1K-means聚類算法算法描述為中心向量c1,c2,…,ck初始化k個(gè)種子分組:將樣本分配給距離其最近的中心向量由這些樣本構(gòu)造不相交（non-overlapping

）的聚類確定中心:用各個(gè)聚類的中心向量作為新的中心重復(fù)分組和確定中心的步驟，直至算法收斂2023/2/1K-means聚類算法（續(xù)）算法的具體過程從數(shù)據(jù)集中任意選取k個(gè)賦給初始的聚類中心c1,c2,…,ck；對(duì)數(shù)據(jù)集中的每個(gè)樣本點(diǎn)xi，計(jì)算其與各個(gè)聚類中心cj的歐氏距離并獲取其類別標(biāo)號(hào)：

按下式重新計(jì)算k個(gè)聚類中心；重復(fù)步驟2和步驟3，直到達(dá)到最大迭代次數(shù)、聚類目標(biāo)函數(shù)達(dá)到最優(yōu)值或者兩次迭代得到的目標(biāo)函數(shù)變化小于給定的為止。2023/2/1k-平均聚類算法(續(xù))例012345678910012345678910012345678910012345678910K=2任意選擇

K個(gè)對(duì)象作為初始聚類中心將每個(gè)對(duì)象賦給最類似的中心更新簇的平均值重新賦值更新簇的平均值重新賦值2023/2/1Matlab程序?qū)崿F(xiàn)function[M,j,e]=kmeans(X,K,Max_Its)[N,D]=size(X);I=randperm(N);M=X(I(1:K),:);Mo=M;forn=1:Max_Itsfork=1:K

Dist(:,k)=sum((X-repmat(M(k,:),N,1)).^2,2)';end

[i,j]=min(Dist,[],2);fork=1:Kifsize(find(j==k))>0

M(k,:)=mean(X(find(j==k),:));endend2023/2/1Matlab程序?qū)崿F(xiàn)（續(xù)）Z=zeros(N,K);form=1:N

Z(m,j(m))=1;end

e=sum(sum(Z.*Dist)./N);

fprintf('%dError=%f\n',n,e);Mo=M;end2023/2/1在圖像分割上的簡單應(yīng)用例1：圖片：一只遙望大海的小狗；此圖為100x100像素的JPG圖片，每個(gè)像素可以表示為三維向量（分別對(duì)應(yīng)JPEG圖像中的紅色、綠色和藍(lán)色通道）

；將圖片分割為合適的背景區(qū)域（三個(gè)）和前景區(qū)域（小狗）；使用K-means算法對(duì)圖像進(jìn)行分割。2023/2/1在圖像分割上的簡單應(yīng)用（續(xù)）分割后的效果注：最大迭代次數(shù)為20次，需運(yùn)行多次才有可能得到較好的效果。2023/2/1在圖像分割上的簡單應(yīng)用（續(xù)）例2：注：聚類中心個(gè)數(shù)為5，最大迭代次數(shù)為10。2023/2/1k-平均聚類算法(續(xù))優(yōu)點(diǎn):相對(duì)有效性:O(tkn),其中n

是對(duì)象數(shù)目,k

是簇?cái)?shù)目,t是迭代次數(shù);通常,k,t<<n.當(dāng)結(jié)果簇是密集的，而簇與簇之間區(qū)別明顯時(shí)，它的效果較好2023/2/1k-平均聚類算法(續(xù))弱點(diǎn)只有在簇的平均值(mean)被定義的情況下才能使用.可能不適用于某些應(yīng)用,例如涉及有分類屬性的數(shù)據(jù)需要預(yù)先指頂簇的數(shù)目k,不能處理噪音數(shù)據(jù)和孤立點(diǎn)(outliers)不適合用來發(fā)現(xiàn)具有非凸形狀(non-convexshapes)的簇2023/2/1k-中心點(diǎn)聚類方法k-平均值算法對(duì)孤立點(diǎn)很敏感!因?yàn)榫哂刑貏e大的值的對(duì)象可能顯著地影響數(shù)據(jù)的分布.k-中心點(diǎn)(k-Medoids):不采用簇中對(duì)象的平均值作為參照點(diǎn),而是選用簇中位置最中心的對(duì)象,即中心點(diǎn)(medoid)作為參照點(diǎn).0123456789100123456789100123456789100123456789100123456789100123456789102023/2/1k-中心點(diǎn)聚類方法(續(xù))找聚類中的代表對(duì)象(中心點(diǎn))PAM(PartitioningAroundMedoids,1987)首先為每個(gè)簇隨意選擇選擇一個(gè)代表對(duì)象,剩余的對(duì)象根據(jù)其與代表對(duì)象的距離分配給最近的一個(gè)簇;然后反復(fù)地用非代表對(duì)象來替代代表對(duì)象，以改進(jìn)聚類的質(zhì)量

PAM

對(duì)于較小的數(shù)據(jù)集非常有效,但不能很好地?cái)U(kuò)展到大型數(shù)據(jù)集2023/2/1k-中心點(diǎn)聚類方法(續(xù))基本思想：首先為每個(gè)簇隨意選擇選擇一個(gè)代表對(duì)象;剩余的對(duì)象根據(jù)其與代表對(duì)象的距離分配給最近的一個(gè)簇；然后反復(fù)地用非代表對(duì)象來替代代表對(duì)象,以改進(jìn)聚類的質(zhì)量；聚類結(jié)果的質(zhì)量用一個(gè)代價(jià)函數(shù)來估算。2023/2/1k-中心點(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

第二種情況：p當(dāng)前隸屬于代表對(duì)象Oj.如果Oj

被Orandom代替,且p離Orandom最近,那么p被重新分配給Orandom

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

第四種情況：p當(dāng)前隸屬于Oi，i≠j。如果Oj被Orandom代替，且p離Orandom最近，那么p被重新分配給Orandom

3.不發(fā)生變化4.重新分配給Orandom2023/2/1k-中心點(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的總距離E,如果E比取代前下降則則用Orandom替換Oj，形成新的k個(gè)代表對(duì)象的集合，返回（4）；(6)until不發(fā)生變化(7)如果所有非代表對(duì)象都無法取代已存在的簇中心，則結(jié)束替代過程，并輸出結(jié)果2023/2/1PAM(續(xù))TotalCost=20012345678910012345678910K=2ArbitrarychoosekobjectasinitialmedoidsAssigneachremainingobjecttonearestmedoidsRandomlyselectanonmedoid

object,OramdomComputetotalcostofswapping012345678910012345678910TotalCost=26SwappingOandOramdom

Ifqualityisimproved.DoloopUntilnochange0123456789100123456789102023/2/1PAM(續(xù))當(dāng)存在噪音和孤立點(diǎn)時(shí),PAM比

k-平均方法更健壯.這是因?yàn)橹行狞c(diǎn)不象平均值那么容易被極端數(shù)據(jù)影響

PAM對(duì)于小數(shù)據(jù)集工作得很好,但不能很好地用于大數(shù)據(jù)集

每次迭代O(k(n-k)2)

其中

n

是數(shù)據(jù)對(duì)象數(shù)目,

k是聚類數(shù)基于抽樣的方法, CLARA(ClusteringLARgeApplications)2023/2/1CLARA

(ClusteringLargeApplications)

(1990)CLARA(KaufmannandRousseeuwin1990)不考慮整個(gè)數(shù)據(jù)集,而是選擇數(shù)據(jù)的一小部分作為樣本它從數(shù)據(jù)集中抽取多個(gè)樣本集,對(duì)每個(gè)樣本集使用PAM,并以最好的聚類作為輸出優(yōu)點(diǎn):可以處理的數(shù)據(jù)集比PAM大缺點(diǎn):有效性依賴于樣本集的大小基于樣本的好的聚類并不一定是整個(gè)數(shù)據(jù)集的好的聚類,樣本可能發(fā)生傾斜

例如,Oi是最佳的k個(gè)中心點(diǎn)之一,但它不包含在樣本中,CLARA將找不到最佳聚類2023/2/1CLARA--效率由取樣大小決定PAM→利用完整資料集

CLARA→利用取樣資料集

盲點(diǎn)：取樣范圍不包含最佳解

sampledbestTrade-off232023/2/1CLARA改良解決：CLARANS(ClusteringLargeApplicationbaseduponRANdomizedSearch)應(yīng)用

graph考慮緊鄰節(jié)點(diǎn)不局限于區(qū)域性復(fù)雜度：O(n^2)→缺點(diǎn)242023/2/1CLARA的有效性主要取決于樣本的大小。如果任何一個(gè)最佳抽樣中心點(diǎn)不在最佳的K個(gè)中心之中，則CLARA將永遠(yuǎn)不能找到數(shù)據(jù)集合的最佳聚類。同時(shí)這也是為了聚類效率做付出的代價(jià)。

CLARANS聚類則是將CLARA和PAM有效的結(jié)合起來，CLARANS在任何時(shí)候都不把自身局限于任何樣本，CLARANS在搜素的每一步都以某種隨機(jī)性選取樣本。算法步驟如下CLARANS(“Randomized”CLARA)(1994)2023/2/1CLARANS

(“Randomized”CLARA)(1994)CLARANS(AClusteringAlgorithmbasedonRandomizedSearch)(NgandHan’94)CLARANS將采樣技術(shù)和PAM結(jié)合起來CLARA在搜索的每個(gè)階段有一個(gè)固定的樣本CLARANS任何時(shí)候都不局限于固定樣本,而是在搜索的每一步帶一定隨機(jī)性地抽取一個(gè)樣本聚類過程可以被描述為對(duì)一個(gè)圖的搜索,圖中的每個(gè)節(jié)點(diǎn)是一個(gè)潛在的解,也就是說k-medoids相鄰節(jié)點(diǎn)：代表的集合只有一個(gè)對(duì)象不同在替換了一個(gè)代表對(duì)象后得到的聚類結(jié)果被稱為當(dāng)前聚類結(jié)果的鄰居2023/2/1CLARANS(續(xù))如果一個(gè)更好的鄰居被發(fā)現(xiàn),CLARANS移到該鄰居節(jié)點(diǎn),處理過程重新開始,否則當(dāng)前的聚類達(dá)到了一個(gè)局部最優(yōu)如果找到了一個(gè)局部最優(yōu),CLARANS從隨機(jī)選擇的節(jié)點(diǎn)開始尋找新的局部最優(yōu)實(shí)驗(yàn)顯示CLARANS比PAM和CLARA更有效CLARANS能夠探測孤立點(diǎn)聚焦技術(shù)和空間存取結(jié)構(gòu)可以進(jìn)一步改進(jìn)它的性能(Esteretal.’95)2023/2/11、輸入?yún)?shù)numlocal和maxneighbor。numlocal

表示抽樣的次數(shù)，maxneighbor

表示一個(gè)節(jié)點(diǎn)可以與任意特定鄰居進(jìn)行比較的數(shù)目。令：i=1，i用來表示已經(jīng)選樣的次數(shù)mincost為最小代價(jià)，初始時(shí)設(shè)為大數(shù)。

2、設(shè)置當(dāng)前節(jié)點(diǎn)current為Gn中的任意一個(gè)節(jié)點(diǎn)。

3、令j=1。（j用來表示已經(jīng)與current進(jìn)行比較的鄰居的個(gè)數(shù)）

4、考慮當(dāng)前點(diǎn)的一個(gè)隨機(jī)的鄰居S，并計(jì)算兩個(gè)節(jié)點(diǎn)的代價(jià)差。5、如果S的代價(jià)較低，則current:=S，轉(zhuǎn)到步驟3。

6、否則，令j=j+1。如果j<=maxneighbor,則轉(zhuǎn)到步驟4。

7、否則，當(dāng)j>maxneighbor，當(dāng)前節(jié)點(diǎn)為本次選樣最小代價(jià)節(jié)點(diǎn).如果其代價(jià)小于mincost,令mincost為當(dāng)前節(jié)點(diǎn)的代價(jià)，bestnode為當(dāng)前的節(jié)點(diǎn)。

8、令i=i+1，如果i〉numlocal,輸出bestnode，運(yùn)算中止.否則，轉(zhuǎn)到步驟2。CLARANS(“Randomized”CLARA)(1994)2023/2/11）代價(jià)值，主要描述一個(gè)對(duì)象被分到一個(gè)類別中的代價(jià)值，該代價(jià)值由每個(gè)對(duì)象與其簇中心點(diǎn)間的相異度（距離或者相似度）的總和來定義。代價(jià)差則是兩次隨機(jī)領(lǐng)域的代價(jià)差值。

（2）更新鄰接點(diǎn)，CLARANS不會(huì)把搜索限制在局部區(qū)域，如果發(fā)現(xiàn)一個(gè)更好的近鄰，CLARANS就移到該近鄰節(jié)點(diǎn)，處理過程從新開始；否則，當(dāng)前的聚類則產(chǎn)生了一個(gè)局部最小。如果找到一個(gè)局部最小，CLARANS從隨機(jī)選擇的新節(jié)點(diǎn)開始，搜索新的局部最小。當(dāng)搜索的局部最小解達(dá)到用戶指定的數(shù)目時(shí)，最好的局部最小作為算法的輸出。從上面的算法步驟也可以看出這一思想。在第5步中更新節(jié)點(diǎn)current。CLARANS(“Randomized”CLARA)(1994)2023/2/1綜合比較KmeansKmedoidsCLARACLARANS優(yōu)點(diǎn)簡單不受極值影響可處理大數(shù)據(jù)找到最佳解缺點(diǎn)受極值影響無法