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

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

2、中對象的平均值來表示每個簇用該簇中對象的平均值來表示 nk-中心點(diǎn)或中心點(diǎn)或 PAM (Partition around medoids) (Kaufman & Rousseeuw87): 每個簇用接近聚類中心的一個對象來表示每個簇用接近聚類中心的一個對象來表示 n這些啟發(fā)式算法適合發(fā)現(xiàn)中小規(guī)模數(shù)據(jù)庫中的球狀聚類這些啟發(fā)式算法適合發(fā)現(xiàn)中小規(guī)模數(shù)據(jù)庫中的球狀聚類n對于大規(guī)模數(shù)據(jù)庫和處理任意形狀的聚類對于大規(guī)模數(shù)據(jù)庫和處理任意形狀的聚類,這些算法需要進(jìn)這些算法需要進(jìn)一步擴(kuò)展一步擴(kuò)展2022-6-26K-means聚類算法聚類算法n算法描述算法描述1. 為中心向量c1, c2, , ck初始

3、化k個種子2. 分組: 將樣本分配給距離其最近的中心向量 由這些樣本構(gòu)造不相交（ non-overlapping ）的聚類3. 確定中心: 用各個聚類的中心向量作為新的中心4. 重復(fù)分組和確定中心的步驟，直至算法收斂2022-6-26K-means聚類算法聚類算法（續(xù)）（續(xù)）n算法的具體過程算法的具體過程1.從數(shù)據(jù)集 中任意選取k個賦給初始的聚類中心c1, c2, , ck；2.對數(shù)據(jù)集中的每個樣本點(diǎn)xi，計算其與各個聚類中心cj的歐氏距離并獲取其類別標(biāo)號： 3.按下式重新計算k個聚類中心；4.重復(fù)步驟2和步驟3，直到達(dá)到最大迭代次數(shù)、聚類目標(biāo)函數(shù)達(dá)到最優(yōu)值或者兩次迭代得到的目標(biāo)函數(shù)變化小于給

4、定的為止。1Nnnx2( )argmin | ,1,.,1,.,ijjlabel iiN jkxc:( ),1,2,.,ss label sjjjcjkNx2022-6-26k-平均聚類算法平均聚類算法(續(xù)續(xù))n例例012345678910012345678910012345678910012345678910012345678910012345678910012345678910012345678910012345678910012345678910K=2任意選擇任意選擇 K個對個對象作為初始聚類象作為初始聚類中心中心將每個將每個對象賦對象賦給最類給最類似的中似的中心心更新簇更新簇的平均的平

5、均值值重新賦值重新賦值更新簇更新簇的平均的平均值值重新賦值重新賦值2022-6-26Matlab程序?qū)崿F(xiàn)程序?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;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), :);

6、end end2022-6-26Matlab程序?qū)崿F(xiàn)程序?qū)崿F(xiàn)（續(xù)）（續(xù)） Z = zeros(N,K); for m=1:N Z(m,j(m) = 1; end e = sum(sum(Z.*Dist)./N); fprintf(%d Error = %fn, n, e); Mo = M;end2022-6-26在圖像分割上的簡單應(yīng)用在圖像分割上的簡單應(yīng)用例例1：1. 圖片：一只遙望大海的小狗；2. 此圖為100 x 100像素的JPG圖片，每個像素可以表示為三維向量（分別對應(yīng)JPEG圖像中的紅色、綠色和藍(lán)色通道） ；3. 將圖片分割為合適的背景區(qū)域（三個）和前景區(qū)域（小狗）；4. 使用K-m

7、eans算法對圖像進(jìn)行分割。2022-6-26在圖像分割上的簡單應(yīng)用在圖像分割上的簡單應(yīng)用（續(xù)）（續(xù)）分割后的效果注：最大迭代次數(shù)為20次，需運(yùn)行多次才有可能得到較好的效果。2022-6-26在圖像分割上的簡單應(yīng)用在圖像分割上的簡單應(yīng)用（續(xù)）（續(xù)）例例2：注：聚類中心個數(shù)為5，最大迭代次數(shù)為10。2022-6-26k-平均聚類算法平均聚類算法(續(xù)續(xù))n優(yōu)點(diǎn)優(yōu)點(diǎn): 相對有效性相對有效性: O(tkn), 其中其中 n 是對象數(shù)目是對象數(shù)目, k 是簇數(shù)目是簇數(shù)目, t 是迭代次數(shù)是迭代次數(shù); 通常通常, k, t n.n當(dāng)結(jié)果簇是密集的，而簇與簇之間區(qū)別明顯時，它的效果當(dāng)結(jié)果簇是密集的，而簇與簇

8、之間區(qū)別明顯時，它的效果較好較好2022-6-26k-平均聚類算法平均聚類算法(續(xù)續(xù))n弱點(diǎn)弱點(diǎn)n只有在簇的平均值只有在簇的平均值(mean)被定義的情況下才能使用被定義的情況下才能使用.可能不適用于可能不適用于某些應(yīng)用某些應(yīng)用, 例如涉及有例如涉及有分類屬性分類屬性的數(shù)據(jù)的數(shù)據(jù)n需要預(yù)先指頂簇的數(shù)目需要預(yù)先指頂簇的數(shù)目k, n不能處理噪音數(shù)據(jù)和孤立點(diǎn)不能處理噪音數(shù)據(jù)和孤立點(diǎn)(outliers)n不適合用來發(fā)現(xiàn)具有非凸形狀不適合用來發(fā)現(xiàn)具有非凸形狀(non-convex shapes)的簇的簇2022-6-26k-中心點(diǎn)聚類方法中心點(diǎn)聚類方法nk-平均值算法對孤立點(diǎn)很敏感平均值算法對孤立點(diǎn)很敏

9、感!n因?yàn)榫哂刑貏e大的值的對象可能顯著地影響數(shù)據(jù)的分布因?yàn)榫哂刑貏e大的值的對象可能顯著地影響數(shù)據(jù)的分布.nk-中心點(diǎn)中心點(diǎn)(k-Medoids): 不采用簇中對象的平均值作為參照不采用簇中對象的平均值作為參照點(diǎn)點(diǎn), 而是而是選用簇中位置最中心的對象選用簇中位置最中心的對象, 即中心點(diǎn)即中心點(diǎn)(medoid)作作為參照點(diǎn)為參照點(diǎn). 0123456789100123456789100123456789100123456789100123456789100123456789102022-6-26k-中心點(diǎn)聚類方法中心點(diǎn)聚類方法(續(xù)續(xù))n找聚類中的代表對象找聚類中的代表對象(中心點(diǎn)中心點(diǎn))nPAM (

10、Partitioning Around Medoids, 1987)n首先為每個簇隨意選擇選擇一個代表對象首先為每個簇隨意選擇選擇一個代表對象, 剩余的對象根據(jù)剩余的對象根據(jù)其與代表對象的距離分配給最近的一個簇其與代表對象的距離分配給最近的一個簇; 然后反復(fù)地用然后反復(fù)地用非代表對象來替代代表對象，以改進(jìn)聚類的質(zhì)量非代表對象來替代代表對象，以改進(jìn)聚類的質(zhì)量 nPAM 對于較小的數(shù)據(jù)集非常有效對于較小的數(shù)據(jù)集非常有效, 但不能很好地擴(kuò)展到大但不能很好地擴(kuò)展到大型數(shù)據(jù)集型數(shù)據(jù)集2022-6-26k-中心點(diǎn)聚類方法中心點(diǎn)聚類方法(續(xù)續(xù))n基本思想：基本思想：n首先為每個簇隨意選擇選擇一個代表對象首先

11、為每個簇隨意選擇選擇一個代表對象; 剩余的對象剩余的對象根據(jù)其與代表對象的距離分配給最近的一個簇；根據(jù)其與代表對象的距離分配給最近的一個簇；n然后反復(fù)地用非代表對象來替代代表對象然后反復(fù)地用非代表對象來替代代表對象, 以改進(jìn)聚類以改進(jìn)聚類的質(zhì)量；的質(zhì)量；n聚類結(jié)果的質(zhì)量用一個代價函數(shù)來估算。聚類結(jié)果的質(zhì)量用一個代價函數(shù)來估算。 21|jkijp CEpo2022-6-26k-中心點(diǎn)聚類方法中心點(diǎn)聚類方法(續(xù)續(xù))n為了判定一個非代表對象為了判定一個非代表對象Orandom 是否是當(dāng)前一個代表對象是否是當(dāng)前一個代表對象Oj的好的替代的好的替代, 對于每一個非代表對象對于每一個非代表對象p,考慮下面

12、的四種情況：考慮下面的四種情況： n第一種情況：第一種情況：p當(dāng)前隸屬于代表對象當(dāng)前隸屬于代表對象 Oj. 如果如果Oj被被Orandom所代替所代替, 且且p離離Oi最近最近, ij, 那么那么p被重新分配給被重新分配給Oi n第二種情況：第二種情況：p當(dāng)前隸屬于代表對象當(dāng)前隸屬于代表對象 Oj. 如果如果Oj 被被Orandom代替代替, 且且p離離Orandom最最近近, 那么那么p被重新分配給被重新分配給Orandom 1.重新分配給重新分配給Oi 2. 重新分配給重新分配給Orandom2022-6-26k-中心點(diǎn)聚類方法中心點(diǎn)聚類方法(續(xù)續(xù))n第三種情況：第三種情況：p當(dāng)前隸屬于當(dāng)

13、前隸屬于Oi，ij。如果如果Oj被被Orandom代替，而代替，而p仍然離仍然離Oi最近，最近，那么對象的隸屬不發(fā)生變化那么對象的隸屬不發(fā)生變化 n第四種情況：第四種情況：p當(dāng)前隸屬于當(dāng)前隸屬于Oi，ij。如果如果Oj被被Orandom代替，且代替，且p離離Orandom最近，最近，那么那么p被重新分配給被重新分配給Orandom 3. 不發(fā)生變化不發(fā)生變化 4.重新分配給重新分配給Orandom2022-6-26k-中心點(diǎn)聚類方法中心點(diǎn)聚類方法(續(xù)續(xù))n算法算法: k-中心點(diǎn)中心點(diǎn)(1) 隨機(jī)選擇隨機(jī)選擇k個對象作為初始的代表對象；個對象作為初始的代表對象；(2) repeat(3) 指派每

14、個剩余的對象給離它最近的代表對象所代表的簇；指派每個剩余的對象給離它最近的代表對象所代表的簇；(4) 隨意地選擇一個非代表對象隨意地選擇一個非代表對象Orandom；(5) 計算用計算用Orandom代替代替Oj的總距離的總距離E, 如果如果E比取代前下降則則用比取代前下降則則用Orandom替替 換換Oj，形成新的形成新的k個代表對象的集合，返回（個代表對象的集合，返回（4）；）； (6) until 不發(fā)生變化不發(fā)生變化(7) 如果所有非代表對象都無法取代已存在的簇中心，則結(jié)束替代過程，并輸如果所有非代表對象都無法取代已存在的簇中心，則結(jié)束替代過程，并輸出結(jié)果出結(jié)果2022-6-26PAM

15、(續(xù)續(xù))Total Cost = 20012345678910012345678910K=2Arbitrary choose k object as initial medoidsAssign each remaining object to nearest medoidsRandomly select a nonmedoid object,OramdomCompute total cost of swapping012345678910012345678910Total Cost = 26Swapping O and Oramdom If quality is improved.Do loo

16、pUntil no change0123456789100123456789102022-6-26PAM(續(xù)續(xù))n當(dāng)存在噪音和孤立點(diǎn)時當(dāng)存在噪音和孤立點(diǎn)時, PAM 比比 k-平均方法更健壯平均方法更健壯. 這是因?yàn)橹行狞c(diǎn)不象平均值那么容易被極端數(shù)據(jù)影這是因?yàn)橹行狞c(diǎn)不象平均值那么容易被極端數(shù)據(jù)影響響 nPAM對于小數(shù)據(jù)集工作得很好對于小數(shù)據(jù)集工作得很好, 但不能很好地用于但不能很好地用于大數(shù)據(jù)集大數(shù)據(jù)集 n每次迭代每次迭代O(k(n-k)2 )其中其中 n 是數(shù)據(jù)對象數(shù)目是數(shù)據(jù)對象數(shù)目, k 是聚類數(shù)是聚類數(shù)基于抽樣的方法基于抽樣的方法, CLARA(Clustering LARge Appl

17、ications)2022-6-26CLARA (Clustering Large Applications) (1990)nCLARA (Kaufmann and Rousseeuw in 1990)n不考慮整個數(shù)據(jù)集不考慮整個數(shù)據(jù)集, 而是選擇數(shù)據(jù)的一小部分作為樣本而是選擇數(shù)據(jù)的一小部分作為樣本n它從數(shù)據(jù)集中抽取多個樣本集它從數(shù)據(jù)集中抽取多個樣本集, 對每個樣本集使用對每個樣本集使用PAM, 并并以最好的聚類作為輸出以最好的聚類作為輸出n優(yōu)點(diǎn)優(yōu)點(diǎn): 可以處理的數(shù)據(jù)集比可以處理的數(shù)據(jù)集比 PAM大大n缺點(diǎn)缺點(diǎn):n有效性依賴于樣本集的大小有效性依賴于樣本集的大小n基于樣本的好的聚類并不一定是基

18、于樣本的好的聚類并不一定是 整個數(shù)據(jù)集的好的聚類整個數(shù)據(jù)集的好的聚類, 樣本可能發(fā)生傾斜樣本可能發(fā)生傾斜n 例如例如, Oi是最佳的是最佳的k個中心點(diǎn)之一個中心點(diǎn)之一, 但它不包含在樣本中但它不包含在樣本中, CLARA將找不到將找不到最佳聚類最佳聚類2022-6-26CLARA - 效率n由取樣大小決定nPAM 利用完整資料集CLARA 利用取樣資料集盲點(diǎn)：取樣范圍不包含最佳解 sampledbestTrade-off232022-6-26CLARA 改良n解決：CLARANS (Clustering Large Application based upon RANdomized Searc

19、h)n應(yīng)用 graphn考慮緊鄰節(jié)點(diǎn)n不局限于區(qū)域性n復(fù)雜度：O(n2) 缺點(diǎn)242022-6-26nCLARA的有效性主要取決于樣本的大小。如果任何一個最佳抽樣中心點(diǎn)不在最佳的K個中心之中，則CLARA將永遠(yuǎn)不能找到數(shù)據(jù)集合的最佳聚類。同時這也是為了聚類效率做付出的代價。 n CLARANS聚類則是將CLARA和PAM有效的結(jié)合起來，CLARANS在任何時候都不把自身局限于任何樣本，CLARANS在搜素的每一步都以某種隨機(jī)性選取樣本。算法步驟如下 CLARANS (“Randomized” CLARA) (1994)2022-6-26CLARANS (“Randomized” CLARA)

20、(1994)nCLARANS (A Clustering Algorithm based on Randomized Search) (Ng and Han94)nCLARANS將采樣技術(shù)和將采樣技術(shù)和PAM結(jié)合起來結(jié)合起來nCLARA在搜索的每個階段有一個固定的樣本在搜索的每個階段有一個固定的樣本nCLARANS任何時候都不局限于固定樣本任何時候都不局限于固定樣本, 而是在搜索的每一步帶一而是在搜索的每一步帶一定隨機(jī)性地抽取一個樣本定隨機(jī)性地抽取一個樣本 n聚類過程可以被描述為聚類過程可以被描述為對一個圖的搜索對一個圖的搜索, 圖中的每個節(jié)點(diǎn)圖中的每個節(jié)點(diǎn)是一個潛在的解是一個潛在的解, 也就

21、是說也就是說 k -medoidsn相鄰節(jié)點(diǎn)：代表的集合只有一個對象不同相鄰節(jié)點(diǎn)：代表的集合只有一個對象不同n在替換了一個代表對象后得到的聚類結(jié)果被稱為當(dāng)前聚類在替換了一個代表對象后得到的聚類結(jié)果被稱為當(dāng)前聚類結(jié)果的鄰居結(jié)果的鄰居 2022-6-26CLARANS(續(xù)續(xù))n如果一個更好的鄰居被發(fā)現(xiàn)如果一個更好的鄰居被發(fā)現(xiàn), CLARANS移到該鄰居節(jié)點(diǎn)移到該鄰居節(jié)點(diǎn), 處處理過程重新開始理過程重新開始, 否則當(dāng)前的聚類達(dá)到了一個局部最優(yōu)否則當(dāng)前的聚類達(dá)到了一個局部最優(yōu)n如果找到了一個局部最優(yōu)如果找到了一個局部最優(yōu), CLARANS從隨機(jī)選擇的節(jié)點(diǎn)開從隨機(jī)選擇的節(jié)點(diǎn)開始尋找新的局部最優(yōu)始尋找新的

22、局部最優(yōu)n實(shí)驗(yàn)顯示實(shí)驗(yàn)顯示CLARANS比比PAM和和CLARA更有效更有效 nCLARANS能夠探測孤立點(diǎn)能夠探測孤立點(diǎn) n聚焦技術(shù)和空間存取結(jié)構(gòu)可以進(jìn)一步改進(jìn)它的性能聚焦技術(shù)和空間存取結(jié)構(gòu)可以進(jìn)一步改進(jìn)它的性能 (Ester et al.95)2022-6-26n1、輸入?yún)?shù)numlocal和maxneighbor。numlocal 表示抽樣的次數(shù)， maxneighbor 表示一個節(jié)點(diǎn)可以與任意特定鄰居進(jìn)行比較的數(shù)目。 令：i=1，i用來表示已經(jīng)選樣的次數(shù) mincost為最小代價，初始時設(shè)為大數(shù)。 n2、設(shè)置當(dāng)前節(jié)點(diǎn)current為Gn中的任意一個節(jié)點(diǎn)。 n3、令j =1。（j用來表示

23、已經(jīng)與current進(jìn)行比較的鄰居的個數(shù)） n4、考慮當(dāng)前點(diǎn)的一個隨機(jī)的鄰居S，并計算兩個節(jié)點(diǎn)的代價差。n5、如果S的代價較低，則current:=S，轉(zhuǎn)到步驟3。 n6、否則，令j=j+1。如果jmaxneighbor，當(dāng)前節(jié)點(diǎn)為本次選樣最小代價節(jié)點(diǎn). 如果其代價小于mincost,令mincost為當(dāng)前節(jié)點(diǎn)的代價，bestnode為當(dāng)前的節(jié)點(diǎn)。 n8、令 i= i+1，如果inumlocal,輸出bestnode，運(yùn)算中止.否則，轉(zhuǎn)到步驟2。 CLARANS (“Randomized” CLARA) (1994)2022-6-26n1）代價值，主要描述一個對象被分到一個類別中的代價值，該代

24、價值由每個對象與其簇中心點(diǎn)間的相異度（距離或者相似度）的總和來定義。代價差則是兩次隨機(jī)領(lǐng)域的代價差值。 n （2）更新鄰接點(diǎn)，CLARANS不會把搜索限制在局部區(qū)域，如果發(fā)現(xiàn)一個更好的近鄰，CLARANS就移到該近鄰節(jié)點(diǎn)，處理過程從新開始；否則，當(dāng)前的聚類則產(chǎn)生了一個局部最小。如果找到一個局部最小，CLARANS從隨機(jī)選擇的新節(jié)點(diǎn)開始，搜索新的局部最小。當(dāng)搜索的局部最小解達(dá)到用戶指定的數(shù)目時，最好的局部最小作為算法的輸出。從上面的算法步驟也可以看出這一思想。在第5步中更新節(jié)點(diǎn)current。CLARANS (“Randomized” CLARA) (1994)2022-6-26綜合比較K meansK medoidsCLARACLARANS優(yōu)點(diǎn)優(yōu)點(diǎn)簡單簡單不受不受極值影響極值影響可可處理大數(shù)據(jù)處理大數(shù)據(jù)找到最佳解找到最佳解缺缺點(diǎn)點(diǎn)受極值影響受極值影響無法處理大數(shù)據(jù)無法處理大數(shù)據(jù)不一定不一定是是最佳解最佳解速度慢速度慢復(fù)雜復(fù)雜度度O(nkt)O(k(n-k)2)O(ks2+k(n-k)O(n2)精確度精確度速度速度302022-6-26作業(yè)作業(yè)n編程實(shí)現(xiàn)編程實(shí)現(xiàn)K-means算法針對算法針對UCI的的waveform數(shù)數(shù)據(jù)集中每類數(shù)據(jù)取據(jù)集中每類數(shù)據(jù)取100個；對一副無噪圖像進(jìn)行個；對一副無