聚類分析-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-中心點聚類算法--PAMK-medoids改進(jìn)算法2023/2/1基于劃分的聚類方法構(gòu)造n個對象數(shù)據(jù)庫D的劃分,將其劃分成k個聚類啟發(fā)式方法:k-平均值(k-

means)和k-中心點(k-

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

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

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

K個對象作為初始聚類中心將每個對象賦給最類似的中心更新簇的平均值重新賦值更新簇的平均值重新賦值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圖片，每個像素可以表示為三維向量（分別對應(yīng)JPEG圖像中的紅色、綠色和藍(lán)色通道）

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

是對象數(shù)目,k

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

PAM

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

是否是當(dāng)前一個代表對象Oj的好的替代,對于每一個非代表對象p,考慮下面的四種情況：

第一種情況：p當(dāng)前隸屬于代表對象Oj.如果Oj被Orandom所代替,且p離Oi最近,i≠j,那么p被重新分配給Oi

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

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

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

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

3.不發(fā)生變化4.重新分配給Orandom2023/2/1k-中心點聚類方法(續(xù))算法:k-中心點(1)隨機選擇k個對象作為初始的代表對象；(2)repeat (3)指派每個剩余的對象給離它最近的代表對象所代表的簇； (4)隨意地選擇一個非代表對象Orandom； (5)計算用Orandom代替Oj的總距離E,如果E比取代前下降則則用Orandom替換Oj，形成新的k個代表對象的集合，返回（4）；(6)until不發(fā)生變化(7)如果所有非代表對象都無法取代已存在的簇中心，則結(jié)束替代過程，并輸出結(jié)果2023/2/1PAM(續(xù))TotalCost=20012345678910012345678910K=2ArbitrarychoosekobjectasinitialmedoidsAssigneachremainingobjecttonearestmedoidsRandomlyselectanonmedoid

object,OramdomComputetotalcostofswapping012345678910012345678910TotalCost=26SwappingOandOramdom

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

k-平均方法更健壯.這是因為中心點不象平均值那么容易被極端數(shù)據(jù)影響

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

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

其中

n

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

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

(ClusteringLargeApplications)

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

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

CLARA→利用取樣資料集

盲點：取樣范圍不包含最佳解

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

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

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

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

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

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

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

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

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

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

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

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

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