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

智能數據挖掘Topic3--聚類分析K-means&K-medoids

聚類2023/2/1主要內容K-means算法Matlab程序實現在圖像分割上的簡單應用K-medoids算法k-中心點聚類算法--PAMK-medoids改進算法2023/2/1基于劃分的聚類方法構造n個對象數據庫D的劃分,將其劃分成k個聚類啟發式方法:k-平均值(k-

means)和k-中心點(k-

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

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

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

K個對象作為初始聚類中心將每個對象賦給最類似的中心更新簇的平均值重新賦值更新簇的平均值重新賦值2023/2/1Matlab程序實現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程序實現（續）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在圖像分割上的簡單應用例1：圖片：一只遙望大海的小狗；此圖為100x100像素的JPG圖片，每個像素可以表示為三維向量（分別對應JPEG圖像中的紅色、綠色和藍色通道）

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

是對象數目,k

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

PAM

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

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

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

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

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

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

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

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

object,OramdomComputetotalcostofswapping012345678910012345678910TotalCost=26SwappingOandOramdom

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

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

PAM對于小數據集工作得很好,但不能很好地用于大數據集

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

其中

n

是數據對象數目,

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

(ClusteringLargeApplications)

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

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

CLARA→利用取樣資料集

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

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

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

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

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

表示抽樣的次數，maxneighbor

表示一個節點可以與任意特定鄰居進行比較的數目。令：i=1，i用來表示已經選樣的次數mincost為最小代價，初始時設為大數。

2、設置當前節點current為Gn中的任意一個節點。

3、令j=1。（j用來表示已經與current進行比較的鄰居的個數）

4、考慮當前點的一個隨機的鄰居S，并計算兩個節點的代價差。5、如果S的代價較低，則current:=S，轉到步驟3。

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

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

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

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