《模式識(shí)別與人工智能之五課件》由會(huì)員分享，可在線閱讀，更多相關(guān)《模式識(shí)別與人工智能之五課件（53頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、Click to edit Master title style,,Click to edit Master text styles,,Second level,,Third level,,Fourth level,,Fifth level,,*,,*,單擊此處編輯母版標(biāo)題樣式,,單擊此處編輯母版文本樣式,,第二級(jí),,第三級(jí),,第四級(jí),,第五級(jí),,*,,*,Pattern Recognition,&,artificial Intelligence,,L,ecture,,5:,聚類算法（一）,主要內(nèi)容,聚類的定義,聚類算法分類,典型聚類算法講解,,,聚類的定義,聚類的定義,典型的非監(jiān)督式機(jī)器學(xué)習(xí)

2、,數(shù)據(jù)類別不被事先標(biāo)識(shí),通過(guò)學(xué)習(xí)模型推斷出數(shù)據(jù)的一些內(nèi)在結(jié)構(gòu)，進(jìn)而進(jìn)行聚類。,,聚類算法分類,聚類算法分類,劃分方法,：首先得到初始的,K,個(gè)劃分的集合。如,K-,平均、,K-,中心點(diǎn)、,CLARANS,以及對(duì)它們的改進(jìn)。,層次方法,：創(chuàng)建給定數(shù)據(jù)對(duì)象集合的一個(gè)層次性的分解。根據(jù)層次分解的過(guò)程可以分為凝聚（自底向上）或分裂（自頂向下）。,基于密度的方法,：根據(jù)密度的概念來(lái)聚類對(duì)象，如,DBSCAN,、,DENCLUE,、,OPTICS,。,聚類算法分類,基于網(wǎng)格的方法,：首先將對(duì)象空間量化為有限數(shù)目的單元，形成網(wǎng)格結(jié)構(gòu)，然后在網(wǎng)格結(jié)構(gòu)上進(jìn)行聚類，如,STING,、,CLIQUE,、,WaveC

3、luster,。,基于模型的方法,：為每個(gè)簇假設(shè)一個(gè)模型，發(fā)現(xiàn)數(shù)據(jù)對(duì)模型的最好匹配，如,COBWEB,、,CLASSIT,，,GCM, AutoClass, SOM,。,基于降維的方法,：如,Spectral clustering,，,Ncut,等,,聚類算法分類,類別,算法,分裂,/,劃分方法,K-MEANS,（,K-,平均）、,K-MEDOIDS,算法（,K-,中心點(diǎn)）、,CLARANS,算法（基于選擇的方法）,層次法,BIRCH,算法（平衡迭代規(guī)約和聚類）、,CURE,算法（代表聚類）、,CHAMELEON,算法（動(dòng)態(tài)模型）,基于密度的方法,DBSCAN,算法（基于高密度連接區(qū)域）、,O

4、PTICS,算法（對(duì)象排序識(shí)別）、,DENCURE,算法（密度分布函數(shù)）,基于網(wǎng)格的方法,STING,算法（統(tǒng)計(jì)信息網(wǎng)格）、,CLIQUE,算法（聚類高維空間）、,WAVE-CLUSTER,算法（小波變換）,基于模型的方法,統(tǒng)計(jì)學(xué)方法、神經(jīng)網(wǎng)絡(luò)方法,基于降維的方法,Spectral clustering,，,Ncut,,典型聚類算法講解,,-----,基于劃分的聚類算法,,劃分聚類法,– K-means,,Summary,：,k-means,是采用均值算法把數(shù)據(jù)分成,K,個(gè)類的算法！,,Q1,：,k,是什么？,A1,：,k,是聚類算法當(dāng)中類的個(gè)數(shù)。,,,Q2,：,means,是什么？,A2,：

5、,means,是均值算法。,,k-means,算法，亦稱,k-,均值或,k-,平均，是一種基于質(zhì)心的,啟發(fā)式聚類算法,。,基本思想,：通過(guò)迭代把數(shù)據(jù)集劃分為不同的類別（或稱簇），使得,評(píng)價(jià)聚類性能的準(zhǔn)則函數(shù),達(dá)到最優(yōu)，使得每個(gè)聚類類內(nèi)緊湊，類間獨(dú)立。,對(duì)于,連續(xù)型屬性,具有較好的聚類效果，不適合處理離散型屬性。,,劃分聚類法,– K-means,算法概述,,平方誤差和準(zhǔn)則函數(shù),,即,SSE,（,sum of the squared error,）,,,,,SSE,是數(shù)據(jù)庫(kù)中所有對(duì)象的平方誤差總和，其中,,為數(shù)據(jù)對(duì)象； 為簇 的平均值。,,這個(gè)準(zhǔn)則函數(shù)使得生成的簇盡可能的緊湊和獨(dú)立,。,

6、劃分聚類法,– K-means,準(zhǔn)則函數(shù),,1.,隨機(jī)抽取k個(gè)點(diǎn)作為初始聚類的中心，由,各,中心代表各聚類,,2.,計(jì)算所有點(diǎn)到這k個(gè),中心,的距離，,并,將點(diǎn)歸到離其最近的聚類,,,3.,調(diào)整聚類中心，即將聚類的中心移動(dòng)到聚類的幾何中心（即平均值）,,4.,重復(fù)第,2,、,3,步直到聚類的中心不再移動(dòng)，此時(shí)算法收斂,劃分聚類法,– K-means,算法流程,迭代計(jì)算,,中心點(diǎn),收斂！,選擇初始中心點(diǎn),,各點(diǎn)劃分進(jìn)最近聚類,,調(diào)整聚類中心,劃分聚類法,– K-means,Simple Example,Step 1,從數(shù)據(jù)集中任意選擇,k,個(gè)對(duì)象,C,1,,C,2,, …,C,k,作為初始的簇中

7、心；,Step2,把每個(gè)對(duì)象分配到與之最相似的聚合。每個(gè)聚合用其中所有對(duì)象的均值來(lái)代表，“最相似”就是指距離最小。對(duì)于每個(gè)點(diǎn),V,i,，找出一個(gè)質(zhì)心,C,j,，使它們之間的距離,d(,V,i,,,C,j,),最小，并把,V,i,分到第,j,組。,Step3,把所有的點(diǎn)分配到相應(yīng)的簇之后，重新計(jì)算每個(gè)組的質(zhì)心,C,j,,。,Step4,循環(huán)執(zhí)行,Step2,和,step3,，直到數(shù)據(jù)的劃分不再發(fā)生變化,,劃分聚類法,– K-means,算法實(shí)現(xiàn)的具體流程,,,,初始,中心點(diǎn),,,,輸入數(shù)據(jù)及,k,值的選擇,,,,距離,度量,,Factors,影響聚類,效果！,一般采用歐氏距離、曼哈頓距離或者名考

8、斯距離的一種，作為樣本間的相似性度量,劃分聚類法,– K-means,算法特點(diǎn)：影響主要因素,劃分聚類法,– K-means,不足：,k-means,算法只有在簇的平均值被定義的情況下才能使用。,k-means,算法的不足之處在于它要多次掃描數(shù)據(jù)庫(kù)。,k-means,算法只能找出球形的類，而不能發(fā)現(xiàn)任意形狀的類。,初始質(zhì)心的選擇對(duì)聚類結(jié)果有較大的影響。,k-means,算法對(duì)于噪聲和孤立點(diǎn)數(shù)據(jù)是敏感的，少量的該類數(shù)據(jù)能夠?qū)ζ骄诞a(chǎn)生極大的影響。,問(wèn)題描述：,,如圖所示，一只遙望大海的小狗。此圖為,100×100,像素的,JPG,圖片，每個(gè)像素可以表示為三維向量（分別對(duì)應(yīng)紅綠藍(lán)三基色）。,要求使

9、用,k-means,算法，將圖片分割為合適的背景區(qū)域（三個(gè)）和前景區(qū)域（小狗）。,,劃分聚類法,– K-means,應(yīng)用實(shí)例,Matlab,程序?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

10、==k))>0,,M(k, :) = mean(X(find(j==k), :));,end,end,劃分聚類法,– K-means,Z = zeros(N,K);,for m=1:N,Z(m,j(m)) = 1;,end,,e = sum(sum(Z.*Dist)./N);,fprintf('%d Error = %f\n', n, e);,Mo = M;,end,Matlab,程序?qū)崿F(xiàn)（續(xù)）,劃分聚類法,– K-means,close all;clear all; clc;,C_Segments=5;,img_original = imread('dog.png');,%,讀入圖像,fig

11、ure,imshow(img_original),title(',原始圖像,');,%,顯示原圖像,[m,n,depth]=size(img_original );,%,獲取圖像的長(zhǎng)寬,,%,將圖像進(jìn)行,RGB——3,通道分解,%,將,RGB,分量各轉(zhuǎn)為,kmeans,使用的數(shù)據(jù)格式,n,行，一樣本,A = reshape(img_original(:, :, 1), m*n, 1);,B = reshape(img_original(:, :, 2), m*n, 1);,C = reshape(img_original(:, :, 3), m*n, 1);,dat = [A B C];,%

12、r g b,分量組成樣本的特征，每個(gè)樣本有三個(gè)屬性值，共,width*height,個(gè)樣本,cRGB =,kmeans,(double(dat), C_Segments, 20);,rRGB = reshape(cRGB, m, n);,%,反向轉(zhuǎn)化為圖片形式,figure, imshow(label2rgb(rRGB),[]),title(',分類結(jié)果,');,%,顯示分割結(jié)果,劃分聚類法,– K-means,分割后的效果,應(yīng)用實(shí)例,劃分聚類法,– K-means,,,,,,,,劃分聚類法,– K-means,應(yīng)用實(shí)例,注：聚類中心個(gè)數(shù)為,5,，最大迭代次數(shù)為,10,。,思路,將聚類問(wèn)題中的

13、,類定義為模糊集合,，用模糊集的,隸屬度,函數(shù)定量描述樣本點(diǎn)與類之間的從屬關(guān)系，并通過(guò)尋找使,目標(biāo)函數(shù)最小化,的隸屬度函數(shù)，實(shí)現(xiàn)聚類。,,算法關(guān)鍵點(diǎn),隸屬度函數(shù)的數(shù)學(xué)定義,模糊類中心的更新,,,,,,,劃分聚類法,–,模糊,C,均值聚類,fuzzy c-means,變量定義,數(shù)據(jù)集,X,=,{,x,1,,,,x,2,,,,…,,,,,x,n,},c,個(gè)模糊類,樣本,x,k,對(duì)第,i,類的模糊隸屬度為,u,ik,，,滿足條件,隸屬度矩陣,U,={,u,ik,},,第,i,類的類中心為,v,i,聚類中心矩陣為,V,={,v,1,,,,v,2,,,,…,,,v,c,},建立基于隸屬度矩陣,U,和聚類

14、中心矩陣,V,的目標(biāo)函數(shù),J,m,(,U,,,V,),,,,,,,,劃分聚類法,–,模糊,C,均值聚類,fuzzy c means,目標(biāo)函數(shù)最小化求解,,,,,劃分聚類法,–,模糊,C,均值聚類,fuzzy c means,這里,m>1,,是隸屬度的加權(quán)指數(shù),;,,為第,i,個(gè)聚類中心與第,k,個(gè)數(shù)據(jù)樣本之間的歐幾里得距離,;,限定條件：,最小化上述函數(shù)可以用拉格朗日乘子法求解,目標(biāo)函數(shù)最小化求解,對(duì)上式進(jìn)行求導(dǎo)，使其達(dá)到最小的必要條件為：,,,,劃分聚類法,–,模糊,C,均值聚類,fuzzy c means,公式（,1,）,公式（,2,）,模糊,C,均值聚類算法具體步驟,劃分聚類法,–,模糊

15、,C,均值聚類,fuzzy c-means (FCM),確定聚類類別數(shù)目,c,、加權(quán)指標(biāo),m,，用,0~1,的隨機(jī)值初始化隸屬矩陣,U,(0),,，并滿足,令迭代次數(shù)為,b,，,b=0,1,2…bmax,根據(jù)公式（,2,）計(jì)算各個(gè)類的中心,V,i,(b),;,根據(jù)公式（,1,）更新,U,(b),為,U,(b+1),；,比較,U,(b),和,U,(b+1),之間的差別，如果 或者迭代達(dá)到最大次數(shù)，則聚類結(jié)束；否則，置,b=b+1,并返回第,3,步。,,,,,,,,劃分聚類法,–,模糊,C,均值聚類,fuzzy c means,MATLAB,中提供

16、了,FCM,函數(shù)：,[center, U, obj_fcn] = fcm(data, cluster_n, options);,,%,輸入：,% data ---- nxm,矩陣,,,表示,n,個(gè)樣本,,,每個(gè)樣本具有,m,的維特征值,% N_cluster ----,標(biāo)量,,,表示聚合中心數(shù)目,,,即類別數(shù),% options ---- 4x1,矩陣，其中,% options(1):,隸屬度矩陣,U,的指數(shù)，,>1 (,缺省值,: 2.0),% options(2):,最大迭代次數(shù),(,缺省值,: 100),% op

17、tions(3):,隸屬度最小變化量,,,迭代終止條件,(,缺省值,: 1e-5),% options(4):,每次迭代是否輸出信息標(biāo)志,(,缺省值,: 1),,%,輸出：,% center ----,聚類中心,% U ----,隸屬度矩陣,% obj_fcn ----,目標(biāo)函數(shù)值,,,,,,劃分聚類法,–,模糊,C,均值聚類,fuzzy c means,應(yīng)用實(shí)例,,close all;clear all; clc;,C_Segments=4;,img_original = imread('pepper.png');%,讀入圖像,fi

18、gure,imshow(img_original),title(',原始圖像,'); %,顯示原圖像,[m,n,p]=size(img_original ); %,獲取圖像的長(zhǎng)寬,,%,將圖像進(jìn)行,RGB——3,通道分解,%,將,RGB,分量各轉(zhuǎn)為,kmeans,使用的數(shù)據(jù)格式,n,行，一樣本,A = reshape(img_original(:, :, 1), m*n, 1);,B = reshape(img_original(:, :, 2), m*n, 1);,C = reshape(img_original(:, :, 3), m*n, 1);,dat = [A B C]; %

19、 r g b,分量組成樣本的特征，每個(gè)樣本有三個(gè)屬性值，共,width*height,個(gè)樣本,,,,,聚類法,–,模糊,C,均值聚類,fuzzy c means,應(yīng)用實(shí)例,[center,U,fct] = fcm (double(dat),C_Segments);,[~, label] = max(U, [],1);,figure; LAB = reshape(label,m,n);,imshow(LAB,[]),,figure; map = [0 0 0; center(1,1)/255, center(1,2)/255,center(1,3)/255];,imshow(LAB==1),co

20、lormap(map),,figure; map = [0 0 0; center(2,1)/255, center(2,2)/255,center(2,3)/255];,imshow(LAB==2),colormap(map),,figure; map = [0 0 0; center(3,1)/255, center(3,2)/255,center(3,3)/255];,imshow(LAB==3),colormap(map),,figure; map = [0 0 0; center(4,1)/255, center(4,2)/255,center(4,3)/255];,imshow(L

21、AB==4),colormap(map),,,,,聚類法,–,模糊,C,均值聚類,fuzzy c means,應(yīng)用實(shí)例,分割結(jié)果,,,,,劃分聚類法,– K-medoids,k-,中心點(diǎn),(,k,-Medoids):,不采用簇中對(duì)象的平均值作為參照點(diǎn), 而是,選用簇中位置最中心的對(duì)象,, 即中心點(diǎn)(,medoid),作為參照點(diǎn),.,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,0,1,2,3,4,5,6,7,8,9,10,0,1,2,3,4,5,6,7,8,9,10,,,,,,,,,,,,,,,,,,,,,,,,,,,,,

22、,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,0,1,2,3,4,5,6,7,8,9,10,0,1,2,3,4,5,6,7,8,9,10,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,0,1,2,3,4,5,6,7,8,9,10,0,1,2,3,4,5,6,7,8,9,10,,,,,,,,劃分聚類法,– K-medoids,基本思想,:,,找聚類中的代表對(duì)象(中心點(diǎn)),PAM,(Partitioning Around Medoids),首先為每個(gè)簇隨意選擇一個(gè)代表對(duì)象, 剩余的對(duì)象根據(jù)其與代表對(duì)象

23、的距離分配給最近的一個(gè)簇; 然后反復(fù)地用,非代表對(duì)象來(lái)替代代表對(duì)象,，以改進(jìn)聚類的質(zhì)量,PAM,,對(duì)于較小的數(shù)據(jù)集非常有效, 但不能很好地?cái)U(kuò)展到大型數(shù)據(jù)集。,劃分聚類法,– K-medoids,為了判定一個(gè)非代表對(duì)象,O,random,是否是當(dāng)前一個(gè)代表對(duì)象,O,j,的好的替代, 對(duì)于每一個(gè)非代表對(duì)象,p,,考慮下面的四種情況：,,第一種情況,：,p,當(dāng)前隸屬于代表對(duì)象,O,j,.,如果,O,j,被,O,random,所代替, 且,p,離,O,i,最近,,i≠j,,那么,p,被重新分配給,O,i,,第二種情況,：,p,當(dāng)前隸屬于代表對(duì)象,O,j,.,如果,O,j,被,O,random,代替,

24、且,p,離,O,random,最近, 那么,p,被重新分配給,O,random,,劃分聚類法,– K-medoids,第三種情況：,p,當(dāng)前隸屬于,O,i,，i≠j。,如果,O,j,被,O,random,代替，而,p,仍然離,O,i,最近，那么對(duì)象的隸屬不發(fā)生變化,,第四種情況：,p,當(dāng)前隸屬于,O,i,，i≠j。,如果,O,j,被,O,random,代替，且,p,離,O,random,最近，那么,p,被重新分配給,O,random,,劃分聚類法,– K-medoids,算法:,k-,中心點(diǎn),(1) 隨機(jī)選擇,k,個(gè)對(duì)象作為初始的代表對(duì)象；,(2),repeat,(3) 指派每個(gè)剩余的對(duì)象給

25、離它最近的代表對(duì)象所代表的簇；,(4) 隨意地選擇一個(gè)非代表對(duì)象,O,random,；,(5),計(jì)算用,O,random,代替,O,j,的總距離,E,,如果,E,比取代前下降則則用,O,random,替 換,O,j,，,形成新的,k,個(gè)代表對(duì)象的集合，返回（,4,）；,(,6),until,不發(fā)生變化,(7),如果所有非代表對(duì)象都無(wú)法取代已存在的簇中心，則結(jié)束替代過(guò)程，并輸出結(jié)果,劃分聚類法,– K-medoids,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,0,1,2,3,4,5,6,7,8,9,10,0,1,2,3

26、,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,O,ramdom,,Compute total cost of swapping,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,0,1,2,3,4,5,6,7,8,9,10,0,1,2,3,4,5,6,7,8,9,10,,,,

27、,Total Cost = 26,,Swapping O and O,ramdom,If quality is improved.,Do loop,Until no change,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,0,1,2,3,4,5,6,7,8,9,10,0,1,2,3,4,5,6,7,8,9,10,,,,劃分聚類法,– K-medoids,當(dāng)存在噪音和孤立點(diǎn)時(shí),,PAM,比,,k-,平均方法更健壯. 這是因?yàn)橹行狞c(diǎn)不象平均值那么容易被極端數(shù)據(jù)影響,,PAM,對(duì)于小數(shù)據(jù)集工作得很好, 但不能很好地用于大數(shù)據(jù)集,,

28、每次迭代,O,(,k,(,n-k,),2,),,其中,,n,,是數(shù)據(jù)對(duì)象數(shù)目,,,,k,是聚類數(shù),CLARA,,(Clustering LARge Applications),Improvement over PAM,Finds medoids in a,sample,from the dataset,[Idea],:,,If the samples are sufficiently random, the medoids of the sample approximate the medoids of the dataset,[Heuristics],:,,5 samples of size

29、 40+2k gives satisfactory results,Works well for large datasets (n=1000, k=10),劃分聚類法,– K-medoids,CLARA,,(Clustering LARge Applications),劃分聚類法,– K-medoids,Draw multiple samples of the dataset,Sample should be able to represent the dataset,Apply PAM to each sample,Return the best clustering,Set,mincos

30、t,to MAXIMUM;,Repeat,q,times // draws,q,samples,Create,S,by drawing,s,objects randomly from,D,;,Generate the set of medoids,M,from,S,by applying the PAM algorithm;,Compute cost(M,D),If cost(M,D)< mincost,Mincost = cost(M, D);,Bestset = M;,End if;,End repeat;,Return Bestset;,Algorithms:,CLARA,,(Clust

31、ering LARge Applications),劃分聚類法,– K-medoids,s: the size of the sample,k: number of clusters,n:number of objects,Complexity of each iteration is: O(ks,2,+k(n-k)),CLARA,,(Clustering LARge Applications),劃分聚類法,– K-medoids,PAM,find the best K medoids from a given dataset;,CLARA,,finds the best kMedoids f

32、rom several selected samples.,Problems:,The best k-medoids may not be selected during the sampling Process, in this case, CLARA will never find the best clustering,If the sampling is biased, we can not have a good clustering.,Trade off-of efficiency.,CLARANS,,(Clustering Large Applications based on

33、Randomized Search),劃分聚類法,– K-medoids,It was proposed to improve the quality and scalability of CLARA,It combines sampling techniques with PAM,It does not confine itself to any sample at a given time,It draws a sample with some randomness in each step of the search,CLARANS draws sample in,solution sp

34、ace,dynamically,A solution is a set of,k,medoids,The solutions space contains C,n,k,solutions in total,The solution space can be represented by a graph where every node is a potential solution, i.e., a set of,k,medoids,CLARANS,,劃分聚類法,– K-medoids,Every node is a potential solution (k-medoid),Every no

35、de is associated with a squared error,Two nodes are adjacent if they differ by one medoid,Every node has,k,(,n,?,k,) adjacent nodes,,,{,O,1,,,O,2,,…,O,k,},,{,O,k+1,,,O,2,,…,O,k,},,{,O,k+n,,,O,2,,…,O,k,},,,…,,n-k,,neighbors for one medoid,,k,(,n,?,,k,),neighbors for one node,…,,劃分聚類法,– K-medoids:,CLA

36、RANS,Start with a randomly selected node, check,at most,m,neighbors,randomly,If a better adjacent node is found, moves to node and continue; otherwise, current node is local optimum; re-starts with another randomly selected node to search for another local optimum,When,h,local optimum,have been foun

37、d, returns best result as overall result,劃分聚類法,– K-medoids:,CLARANS,N,N,N,C,,,,,,,,,C,,N,,,N,N,,,,<,,Local minimum,…,,Compare no more than,maxneighbor,,times,,numlocal,,Best Node,,Local minimum,…,,Local minimum,…,,Local minimum,…,劃分聚類法,– K-medoids:,CLARANS,Algorithms:,Set mincost to MAXIMUM;,For i=1

38、 to,h,do // find h local optimum,Randomly select a node as the current node C in the graph;,J = 1; // counter of neighbors,Repeat,Randomly select a neighbor N of C;,If Cost(N,D) m,Update mincost with Cost(C,D) if appli

39、cable End for;,End For,Return bestnode;,劃分聚類法,– K-medoids:,CLARANS,Algorithms:,Notes:,Each vertex is a set of,k,-representative objects (means, modes, medoids),Each iteration produces a new set of,k,-representative objects with lower overall dissimilarity,Iterations correspond to a,hill descent,proc

40、ess in a landscape (graph) of vertices,劃分聚類法,– K-medoids:,CLARANS,Advantages:,CLARANS is more effective than both PAM and CLARA,Handles outliers,,Disadvantages:,Computational complexity of CLARANS is O(N,2,).,The clustering quality depends on the sampling method,小 結(jié),掌握劃分聚類算法的基本思想和局限性,掌握常用的劃分聚類的思想和優(yōu)缺

41、點(diǎn)以及適用范圍,,k-means, FCM, k-medoids (PAM, CLARA, CLARANS),能夠利用代碼實(shí)現(xiàn)上述方法，并且結(jié)合實(shí)際應(yīng)用設(shè)計(jì)相應(yīng)的輸入輸出,內(nèi)容總結(jié),Pattern Recognition。統(tǒng)計(jì)學(xué)方法、神經(jīng)網(wǎng)絡(luò)方法。對(duì)于連續(xù)型屬性具有較好的聚類效果，不適合處理離散型屬性。1. 隨機(jī)抽取k個(gè)點(diǎn)作為初始聚類的中心，由各中心代表各聚類。對(duì)于每個(gè)點(diǎn)Vi，找出一個(gè)質(zhì)心Cj，使它們之間的距離d(Vi, Cj)最小，并把Vi分到第j組。此圖為100×100像素的JPG圖片，每個(gè)像素可以表示為三維向量（分別對(duì)應(yīng)紅綠藍(lán)三基色）。% 將圖像進(jìn)行RGB——3通道分解。注：聚類中心個(gè)數(shù)為5，最大迭代次數(shù)為10。第i類的類中心為vi。建立基于隸屬度矩陣U和聚類中心矩陣V的目標(biāo)函數(shù)Jm(U,V)。為第i個(gè)聚類中心與第k個(gè)數(shù)據(jù)樣本之間的歐幾里得距離。確定聚類類別數(shù)目c、加權(quán)指標(biāo)m，用0~1的隨機(jī)值初始化隸屬矩陣U(0) ，并滿足。否則，置b=b+1并返回第3步。然后反復(fù)地用非代表對(duì)象來(lái)替代代表對(duì)象，以改進(jìn)聚類的質(zhì)量。如果Oj被Orandom代替，而p仍然離Oi最近，那么對(duì)象的隸屬不發(fā)生變化,