聚類分析—K-means and K-medoids聚類.ppt

1、數(shù)據(jù)挖掘,Topic3-聚類分析 K-means I=randperm(N); M=X(I(1:K),:); Mo = M; for n=1:Max_Its for k=1:K Dist(:,k) = sum(X - repmat(M(k,:),N,1).2,2); end i, j=min(Dist, , 2); for k=1:K if size(find(j=k)0 M(k, :) = mean(X(find(j=k), :); end end,2020/9/30,Matlab程序?qū)崿F(xiàn)（續(xù)）,Z = zeros(N,K); for m=1:N Z(m,j(m) = 1; end e =

2、sum(sum(Z.*Dist)./N); fprintf(%d Error = %fn, n, e); Mo = M; end,2020/9/30,k-平均聚類算法(續(xù)),例,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個對象作為初始聚類中心,將每個對象賦給最類似的中心,更新簇的平均值,重新賦值,更新簇的平均值,重新賦值,2020/9/30,在圖像分割上的簡單應(yīng)用,例1：,圖片：一只遙望大海的小狗； 此圖為100 x 100像素的JPG圖片，每個像素可以表示為三維向量（分別對應(yīng)JPEG圖像中的紅色、綠色和藍色通道） ； 將圖

3、片分割為合適的背景區(qū)域（三個）和前景區(qū)域（小狗）； 使用K-means算法對圖像進行分割。,2020/9/30,在圖像分割上的簡單應(yīng)用（續(xù)）,分割后的效果,注：最大迭代次數(shù)為20次，需運行多次才有可能得到較好的效果。,2020/9/30,在圖像分割上的簡單應(yīng)用（續(xù)）,例2：,注：聚類中心個數(shù)為5，最大迭代次數(shù)為10。,2020/9/30,k-平均聚類算法(續(xù)),優(yōu)點: 相對有效性: O(tkn), 其中 n 是對象數(shù)目, k 是簇數(shù)目, t 是迭代次數(shù); 通常, k, t n. 當(dāng)結(jié)果簇是密集的，而簇與簇之間區(qū)別明顯時，它的效果較好 Comment: 常常終止于局部最優(yōu). 全局最優(yōu) 可以使用諸

4、如確定性的退火(deterministic annealing)和遺傳算法(genetic algorithms)等技術(shù)得到,2020/9/30,k-平均聚類算法(續(xù)),弱點 只有在簇的平均值(mean)被定義的情況下才能使用.可能不適用于某些應(yīng)用, 例如涉及有分類屬性的數(shù)據(jù) 需要預(yù)先指頂簇的數(shù)目k, 不能處理噪音數(shù)據(jù)和孤立點(outliers) 不適合用來發(fā)現(xiàn)具有非凸形狀(non-convex shapes)的簇,2020/9/30,k-中心點聚類方法,k-平均值算法對孤立點很敏感! 因為具有特別大的值的對象可能顯著地影響數(shù)據(jù)的分布. k-中心點(k-Medoids): 不采用簇中對象的平均

5、值作為參照點, 而是選用簇中位置最中心的對象, 即中心點(medoid)作為參照點.,2020/9/30,k-中心點聚類方法(續(xù)),找聚類中的代表對象(中心點) PAM (Partitioning Around Medoids, 1987) 首先為每個簇隨意選擇選擇一個代表對象, 剩余的對象根據(jù)其與代表對象的距離分配給最近的一個簇; 然后反復(fù)地用非代表對象來替代代表對象，以改進聚類的質(zhì)量 PAM 對于較小的數(shù)據(jù)集非常有效, 但不能很好地擴展到大型數(shù)據(jù)集 CLARA (Kaufmann 剩余的對象根據(jù)其與代表對象的距離分配給最近的一個簇 然后反復(fù)地用非代表對象來替代代表對象, 以改進聚類的質(zhì)量

6、聚類結(jié)果的質(zhì)量用一個代價函數(shù)來估算, 該函數(shù)評估了對象與其參照對象之間的平均相異度,2020/9/30,k-中心點聚類方法(續(xù)),為了判定一個非代表對象Orandom 是否是當(dāng)前一個代表對象Oj的好的替代, 對于每一個非代表對象p,考慮下面的四種情況： 第一種情況：p當(dāng)前隸屬于代表對象 Oj. 如果Oj被Orandom所代替, 且p離Oi最近, ij, 那么p被重新分配給Oi 第二種情況：p當(dāng)前隸屬于代表對象 Oj. 如果Oj 被Orandom代替, 且p離Orandom最近, 那么p被重新分配給Orandom 第三種情況：p當(dāng)前隸屬于Oi，ij。如果Oj被Orandom代替，而p仍然離Oi最

7、近，那么對象的隸屬不發(fā)生變化 第四種情況：p當(dāng)前隸屬于Oi，ij。如果Oj被Orandom代替，且p離Orandom最近，那么p被重新分配給Orandom,2020/9/30,k-中心點聚類方法(續(xù)),1.重新分配給Oi 2. 重新分配給Orandom,3. 不發(fā)生變化 4.重新分配給Orandom,k-中心點聚類代價函數(shù)的四種情況,2020/9/30,k-中心點聚類方法(續(xù)),算法: k-中心點 (1) 隨機選擇k個對象作為初始的代表對象； (2) repeat (3) 指派每個剩余的對象給離它最近的代表對象所代表的簇； (4) 隨意地選擇一個非代表對象Orandom； (5) 計算用Ora

8、ndom代替Oj的總代價S； (6) 如果S0，則用Orandom替換Oj，形成新的k個代表對象的集合； (7) until 不發(fā)生變化,2020/9/30,PAM,PAM (Partitioning Around Medoids) (Kaufman and Rousseeuw, 1987) 是最早提出的k-中心點聚類算法 基本思想: 隨機選擇k個代表對象 反復(fù)地試圖找出更好的代表對象: 分析所有可能的對象對，每個對中的一個對象被看作是代表對象, 而另一個不是. 對可能的各種組合, 估算聚類結(jié)果的質(zhì)量,2020/9/30,PAM(續(xù)),Total Cost = 20,0,1,2,3,4,5,6

9、,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,Compute total cost of swapping,Total Cost = 26,Swapping O and Oramdom If quality is improved.,Do loop Until no change,2020/9/30

10、,PAM(續(xù)),當(dāng)存在噪音和孤立點時, PAM 比 k-平均方法更健壯. 這是因為中心點不象平均值那么容易被極端數(shù)據(jù)影響 PAM對于小數(shù)據(jù)集工作得很好, 但不能很好地用于大數(shù)據(jù)集 每次迭代O(k(n-k)2 ) 其中 n 是數(shù)據(jù)對象數(shù)目, k 是聚類數(shù) 基于抽樣的方法, CLARA(Clustering LARge Applications),2020/9/30,CLARA (Clustering Large Applications) (1990),CLARA (Kaufmann and Rousseeuw in 1990) 不考慮整個數(shù)據(jù)集, 而是選擇數(shù)據(jù)的一小部分作為樣本 它從數(shù)據(jù)集中抽

11、取多個樣本集, 對每個樣本集使用PAM, 并以最好的聚類作為輸出 優(yōu)點: 可以處理的數(shù)據(jù)集比 PAM大 缺點: 有效性依賴于樣本集的大小 基于樣本的好的聚類并不一定是 整個數(shù)據(jù)集的好的聚類, 樣本可能發(fā)生傾斜 例如, Oi是最佳的k個中心點之一, 但它不包含在樣本中, CLARA將找不到最佳聚類,2020/9/30,CLARA - 效率,由取樣大小決定 PAM 利用完整資料集CLARA 利用取樣資料集盲點：取樣范圍不包含最佳解,Trade-off,24,2020/9/30,CLARA 改良,解決：CLARANS (Clustering Large Application based upon

12、RANdomized Search) 應(yīng)用 graph 考慮緊鄰節(jié)點 不局限于區(qū)域性 負雜度：O(n2) 缺點,25,2020/9/30,CLARANS (“Randomized” CLARA) (1994),CLARANS (A Clustering Algorithm based on Randomized Search) (Ng and Han94) CLARANS將采樣技術(shù)和PAM結(jié)合起來 CLARA在搜索的每個階段有一個固定的樣本 CLARANS任何時候都不局限于固定樣本, 而是在搜索的每一步帶一定隨機性地抽取一個樣本 聚類過程可以被描述為對一個圖的搜索, 圖中的每個節(jié)點是一個潛在的

13、解, 也就是說 k -medoids 相鄰節(jié)點：代表的集合只有一個對象不同 在替換了一個代表對象后得到的聚類結(jié)果被稱為當(dāng)前聚類結(jié)果的鄰居,2020/9/30,CLARANS(續(xù)),如果一個更好的鄰居被發(fā)現(xiàn), CLARANS移到該鄰居節(jié)點, 處理過程重新開始, 否則當(dāng)前的聚類達到了一個局部最優(yōu) 如果找到了一個局部最優(yōu), CLARANS從隨機選擇的節(jié)點開始尋找新的局部最優(yōu) 實驗顯示CLARANS比PAM和CLARA更有效 CLARANS能夠探測孤立點 聚焦技術(shù)和空間存取結(jié)構(gòu)可以進一步改進它的性能 (Ester et al.95),2020/9/30,綜合比較,精確度,速度,28,2020/9/30,作業(yè),編程實現(xiàn)K-means算法針對UCI的waveform數(shù)據(jù)集中每類數(shù)據(jù)取100個；對一副無噪圖像進行分割； 編程實現(xiàn)PAM對部分waveform數(shù)據(jù)集加20%的高斯噪聲；同時對一副噪聲圖像進行分割； 編程實現(xiàn)CLARA在全部的waveform數(shù)據(jù)集上的聚類； due date：4月25日,2020/9/30,K-means聚類算法（續(xù)）,分組: 將樣本分配給距離它們最近的中心向量，并使目標(biāo)函數(shù)值減小 確定中心: 亦須有助于減小目標(biāo)函數(shù)值,2020/9/30,k-中心點聚類方