聚類分析—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)在圖像分割上的簡單應用K-medoids算法k-中心點聚類算法中心點聚類算法-PAMK-medoids改進算法2022-6-26基于劃分的聚類方法基于劃分的聚類方法n構造構造n個對象數(shù)據(jù)庫個對象數(shù)據(jù)庫D的劃分的劃分, 將其劃分成將其劃分成k個聚類個聚類n啟發(fā)式方法啟發(fā)式方法: k-平均值平均值(k- means)和和 k-中心點中心點(k- medoids) 算算法法nk-平均值平均值(MacQueen67): 每個簇用該簇

2、中對象的平均值來表示每個簇用該簇中對象的平均值來表示 nk-中心點或中心點或 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ù)庫和處理任意形狀的聚類,這些算法需要進這些算法需要進一步擴展一步擴展2022-6-26K-means聚類算法聚類算法n算法描述算法描述1. 為中心向量c1, c2, , ck初始

3、化k個種子2. 分組: 將樣本分配給距離其最近的中心向量 由這些樣本構造不相交（ non-overlapping ）的聚類3. 確定中心: 用各個聚類的中心向量作為新的中心4. 重復分組和確定中心的步驟，直至算法收斂2022-6-26K-means聚類算法聚類算法（續(xù)）（續(xù)）n算法的具體過程算法的具體過程1.從數(shù)據(jù)集 中任意選取k個賦給初始的聚類中心c1, c2, , ck；2.對數(shù)據(jù)集中的每個樣本點xi，計算其與各個聚類中心cj的歐氏距離并獲取其類別標號： 3.按下式重新計算k個聚類中心；4.重復步驟2和步驟3，直到達到最大迭代次數(shù)、聚類目標函數(shù)達到最優(yōu)值或者兩次迭代得到的目標函數(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在圖像分割上的簡單應用在圖像分割上的簡單應用例例1：1. 圖片：一只遙望大海的小狗；2. 此圖為100 x 100像素的JPG圖片，每個像素可以表示為三維向量（分別對應JPEG圖像中的紅色、綠色和藍色通道） ；3. 將圖片分割為合適的背景區(qū)域（三個）和前景區(qū)域（小狗）；4. 使用K-m

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

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

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

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

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

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

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

14、個剩余的對象給離它最近的代表對象所代表的簇；指派每個剩余的對象給離它最近的代表對象所代表的簇；(4) 隨意地選擇一個非代表對象隨意地選擇一個非代表對象Orandom；(5) 計算用計算用Orandom代替代替Oj的總距離的總距離E, 如果如果E比取代前下降則則用比取代前下降則則用Orandom替替 換換Oj，形成新的形成新的k個代表對象的集合，返回（個代表對象的集合，返回（4）；）； (6) until 不發(fā)生變化不發(fā)生變化(7) 如果所有非代表對象都無法取代已存在的簇中心，則結束替代過程，并輸如果所有非代表對象都無法取代已存在的簇中心，則結束替代過程，并輸出結果出結果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當存在噪音和孤立點時當存在噪音和孤立點時, PAM 比比 k-平均方法更健壯平均方法更健壯. 這是因為中心點不象平均值那么容易被極端數(shù)據(jù)影這是因為中心點不象平均值那么容易被極端數(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)點優(yōu)點: 可以處理的數(shù)據(jù)集比可以處理的數(shù)據(jù)集比 PAM大大n缺點缺點:n有效性依賴于樣本集的大小有效性依賴于樣本集的大小n基于樣本的好的聚類并不一定是基

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

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

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

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

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

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

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