模式識(shí)別 課件 第7章 無監(jiān)督模式識(shí)別

第7章無監(jiān)督模式識(shí)別主要內(nèi)容7.1聚類的基本概念7.2相似性測度7.3動(dòng)態(tài)聚類7.4層次聚類7.5高斯混合聚類7.6其他聚類算法簡介7.8聚類性能度量7.9聚類分析的實(shí)例7.1聚類的基本概念事先不知道要?jiǎng)澐值氖鞘裁搭悇e，沒有類別已知的樣本用來訓(xùn)練，通過某種方法直接把數(shù)據(jù)劃分成若干類別，稱為無監(jiān)督模式識(shí)別、無監(jiān)督學(xué)習(xí)、聚類分析等（1）無監(jiān)督模式識(shí)別（2）聚類一般指將缺少先驗(yàn)知識(shí)的樣本集劃分為若干個(gè)不相交的子集，每個(gè)子集稱為一個(gè)“簇”（cluster）。7.1聚類的基本概念（3）聚類分析三要素聚類依據(jù)模式相似性測度，樣本之間的相似性的衡量聚類算法對(duì)應(yīng)聚類的思路、方法和過程聚類性能度量聚類準(zhǔn)則函數(shù)，用于衡量聚類結(jié)果的有效性（1）樣本相似性測度原理同類樣本特征相似，不同類樣本的特征顯著不同時(shí)；同類樣本會(huì)聚集在一個(gè)區(qū)域，不同類樣本相對(duì)遠(yuǎn)離。樣本點(diǎn)在特征空間距離的遠(yuǎn)近直接反映了相應(yīng)樣本所屬類別，可作為樣本相似性度量。距離越近，相似性越大，屬于同一類的可能性就越大；距離越遠(yuǎn)，相似性越小，屬于同一類的可能性就越小。距離測度7.2相似性測度距離的定義

7.2相似性測度常用距離7.2相似性測度歐氏距離Euclidean城市距離Manhattan切氏距離Chebyshev明氏距離Minkowski7.2相似性測度Canberra距離（Lance距離）（Williams距離）Jffreys&Matusita距離馬氏距離Mahalanobis相似測度余弦值越大，相似性越大，適于扇形分布的樣本余弦相似度函數(shù)7.2相似性測度

Pearson相關(guān)系數(shù)

7.2相似性測度指數(shù)相關(guān)系數(shù)Tanimoto測度其它相似測度7.2相似性測度匹配測度適用于二元向量

7.2相似性測度簡單匹配測度Jaccard系數(shù)（Tanimoto測度）Dice系數(shù)漢明距離Rao測度Kulzinsky系數(shù)

7.2相似性測度（2）點(diǎn)和集合之間的相似性測度衡量待測點(diǎn)與集合之間的相似性，以便將樣本歸入某一聚類。兩種情況根據(jù)待測樣本點(diǎn)和集合當(dāng)前所有點(diǎn)之間的相似度定義將集合用某種方式表達(dá)，待測樣本點(diǎn)和該表達(dá)之間的相似度定義7.2相似性測度最大相似測度最小相似測度平均相似測度7.2相似性測度聚類中心每類模式的聚集中心或具有代表性的模式將一個(gè)類用一個(gè)點(diǎn)表達(dá)，待測樣本和該點(diǎn)之間的相似度作為和類的相似度平均向量均值中心樣本集中和其他點(diǎn)相似度之和最大的樣本樣本集中和其他點(diǎn)相似度的中值最大的樣本點(diǎn)中值中心7.2相似性測度（3）集合和集合之間的相似性測度衡量集合與集合之間的相似性，以便將集合聚集兩種情況根據(jù)集合間所有點(diǎn)之間的相似度定義將集合用某種方式表達(dá)，根據(jù)集合表達(dá)之間的相似度定義7.2相似性測度最大相似測度最小相似測度平均相似測度均值測度其他測度采用距離度量樣本間的相似性；確定某個(gè)評(píng)價(jià)聚類結(jié)果質(zhì)量的準(zhǔn)則函數(shù)；給定某個(gè)初始分類，通過迭代算法找出使準(zhǔn)則函數(shù)取極值的最好聚類結(jié)果。7.3動(dòng)態(tài)聚類動(dòng)態(tài)聚類方法的關(guān)鍵點(diǎn)7.3動(dòng)態(tài)聚類（1）C均值算法首先確定c個(gè)初始聚類中心，然后根據(jù)各類樣本到聚類中心的距離平方和最小的準(zhǔn)則（最小誤差平方和準(zhǔn)則），不斷調(diào)整聚類中心，直到聚類合理。原理步驟7.3動(dòng)態(tài)聚類

3）計(jì)算新的聚類中心

2）逐個(gè)將每一樣本按最小距離原則分配給c個(gè)聚類中心例題例7-4：有10個(gè)二維樣本，用C均值算法聚類。

7.3動(dòng)態(tài)聚類序號(hào)取值序號(hào)取值

7.3動(dòng)態(tài)聚類2）樣本歸類

3）計(jì)算新的聚類中心7.3動(dòng)態(tài)聚類4）判斷算法是否收斂2）重新按最小距離分配樣本

3）計(jì)算新的聚類中心7.3動(dòng)態(tài)聚類4）判斷算法是否收斂

3）計(jì)算新的聚類中心7.3動(dòng)態(tài)聚類4）判斷算法是否收斂

3）計(jì)算新的聚類中心4）判斷算法是否收斂7.3動(dòng)態(tài)聚類仿真實(shí)現(xiàn)clc,clear,closeall;X=[00;10;22;11;01;

53;63;54;64;75];[N,n]=size(X);c=2;label=zeros(1,N);mv=randperm(N,c);%mv=[1,2];oldmu=X(mv,:);newmu=zeros(c,n);while1d=pdist2(X,oldmu);[~,label]=min(d,[],2);fori=1:cnewmu(i,:)=mean(X(label==i,:));endifabs(oldmu-newmu)<0.00001break;elseoldmu=newmu;endendfigure,plot(X(:,1),X(:,2),'k*','MarkerSize',5);holdongscatter(X(:,1),X(:,2),label,'rg','o>',8);plot(newmu(:,1),newmu(:,2),'kx',

'MarkerSize',10,'LineWidth',2);legend('原始數(shù)據(jù)','聚類1','聚類2','聚類中心',

'Location','NW');title('C均值聚類');xlabel('x1');ylabel('x2');holdoff7.3動(dòng)態(tài)聚類7.3動(dòng)態(tài)聚類C均值聚類結(jié)果圖7.3動(dòng)態(tài)聚類例7-5：對(duì)fisheriris數(shù)據(jù)集，進(jìn)行C均值聚類。clc,clear,closeall;loadfisheririsX=meas;[idx,C]=kmeans(X,3,'Start',[X(1,:);X(2,:);X(3,:)]);plot3(X(idx==1,1),X(idx==1,2),X(idx==1,3),'r+','MarkerSize',5);holdonplot3(X(idx==2,1),X(idx==2,2),X(idx==2,3),'gx','MarkerSize',5);plot3(X(idx==3,1),X(idx==3,2),X(idx==3,3),'b.','MarkerSize',5);plot3(C(:,1),C(:,2),C(:,3),'kx','MarkerSize',8,'LineWidth',3);xlabel('花萼長(cm)');ylabel('花萼寬(cm)');zlabel('花瓣長(cm)');legend('聚類1','聚類2','聚類3','聚類中心','Location','NW');holdoff7.3動(dòng)態(tài)聚類fisheriris數(shù)據(jù)集3均值聚類7.3動(dòng)態(tài)聚類算法分析需要預(yù)先確定聚類數(shù)c。如果c值估計(jì)不準(zhǔn)確，聚類結(jié)果不能合理地反應(yīng)數(shù)據(jù)的分布結(jié)構(gòu)。初始聚類中心的選擇對(duì)聚類結(jié)果有較大影響。C均值算法對(duì)噪聲和異常點(diǎn)較為敏感。即使某些點(diǎn)是噪聲或孤立的異常點(diǎn)，也會(huì)按距離分配給某一個(gè)聚類，影響到聚類中心的計(jì)算，進(jìn)而影響最終的聚類結(jié)果。7.3動(dòng)態(tài)聚類（2）ISODATA算法IterativeSelf-OrganizingDataAnalysisTechniquesA：迭代自組織數(shù)據(jù)分析技術(shù)原理與C均值算法相似，以均值迭代確定聚類中心可以調(diào)整參數(shù)，引入分裂與合并機(jī)制某兩類中心間距小于某一閾值時(shí)，合并兩類在某類樣本標(biāo)準(zhǔn)差大于某一閾值時(shí)，或樣本數(shù)目超過某一閾值時(shí)，分裂為兩類類別數(shù)目少于某一閾值時(shí)，也實(shí)行分裂在類的樣本數(shù)目少于某閾值時(shí)，可消除類7.3動(dòng)態(tài)聚類

7.3動(dòng)態(tài)聚類例題

2）逐個(gè)將N個(gè)樣本按最小距離分類

7.3動(dòng)態(tài)聚類

4）修正各聚類中心5）參數(shù)計(jì)算。對(duì)每一聚類域，計(jì)算其所有樣本到其聚類中心的距離的平均值；所有樣本到其相應(yīng)聚類中心的距離的平均值。

7.3動(dòng)態(tài)聚類

7.3動(dòng)態(tài)聚類7）分裂

①計(jì)算每一類別中樣本與聚類中心距離的標(biāo)準(zhǔn)差向量：

7.3動(dòng)態(tài)聚類7）分裂

7.3動(dòng)態(tài)聚類2）逐個(gè)將N個(gè)樣本按最小距離分類3）判斷是否要消除類

4）修正各聚類中心5）參數(shù)計(jì)算

7.3動(dòng)態(tài)聚類6）判斷偶次迭代，跳到第8步，進(jìn)行合并。8）合并①計(jì)算每兩聚類中心間的距離

無可合并的類。7.3動(dòng)態(tài)聚類9）判斷如果是最后一次迭代計(jì)算（即第Iter次），算法結(jié)束。否則，如需要改變參數(shù)，則轉(zhuǎn)入第1步，不需要改變參數(shù)轉(zhuǎn)入第2步。不是最后一次迭代，算法繼續(xù)；需要判斷是否需要修改給定的參數(shù)：

①已獲得所要求的聚類數(shù)目；②聚類之間的分離度（兩聚類中心之間的距離）大于類別之間樣本分離的標(biāo)準(zhǔn)差；

③每一聚類之間的樣本數(shù)目都具有樣本總數(shù)中的足夠大的百分比。認(rèn)為兩聚類中心能代表各子集樣本，不需要修改參數(shù)，返回第2步。7.3動(dòng)態(tài)聚類2）～5）：與前一次迭代計(jì)算結(jié)果相同7）分裂8）與前一次迭代結(jié)果相同，不合并不滿足分裂條件，執(zhí)行下一步6）條件均不滿足，繼續(xù)下一步9）無新的分類變更，返回第2步2）～5）與前一次迭代計(jì)算結(jié)果相同6）最后一次迭代，算法結(jié)束7.4層次聚類層次聚類：HierarchicalClustering，HC，在不同層次（尺度）上進(jìn)行聚類，源自于社會(huì)科學(xué)和生物學(xué)分類，可以生成樣本的不同聚類，可以生成一個(gè)完整的樣本分級(jí)分類體系。層次聚類結(jié)果可以樹形圖表示。（1）基本概念聚類方法分裂方法：自上而下，將所有的數(shù)據(jù)作為一簇，采用合適的方法分為較小的簇，對(duì)于每一簇再分，直到滿足要求聚合方法：自下而上，將每個(gè)樣本看作一簇，采用合適的方法聚合較小的簇，對(duì)于聚合后的簇再次聚合，直到滿足要求7.4層次聚類終止算法條件7.4層次聚類最終類別數(shù)類間最小距離類內(nèi)方差……（2）分裂層次聚類分裂策略采用C均值聚類，將一簇分為c簇設(shè)定一致性準(zhǔn)則，將滿足的數(shù)據(jù)分裂出去分裂簇的選擇分散性大的簇樣本數(shù)多的簇……關(guān)鍵技術(shù)7.4層次聚類例7-7：有10個(gè)二維樣本，用分裂法分為3個(gè)聚類。7.4層次聚類例題分裂思路采用C均值聚類，將一簇分為2簇每次分裂樣本數(shù)最多的子簇序號(hào)取值序號(hào)取值7.4層次聚類采用C均值聚類，將一簇分為2簇分裂過程

分裂樹形圖

（3）合并層次聚類

關(guān)鍵技術(shù)7.4層次聚類例7-8：有10個(gè)二維樣本，用聚合法分為3個(gè)聚類。7.4層次聚類例題聚合思路類間距離采用兩類樣本間最近距離采用簇間最小距離，合并子簇序號(hào)取值序號(hào)取值7.4層次聚類聚合過程

計(jì)算10個(gè)類別樣本彼此間的距離7.4層次聚類

合并具有最小距離的類計(jì)算6個(gè)類別間的距離，單連接7.4層次聚類

合并具有最小距離的類聚合樹形圖7.4層次聚類（4）仿真實(shí)現(xiàn)設(shè)計(jì)思路linkage函數(shù)：生成二分層次聚類樹cluster函數(shù)：根據(jù)層次聚類樹實(shí)現(xiàn)聚類例7-9：有10個(gè)二維樣本，進(jìn)行分層聚類。序號(hào)取值序號(hào)取值7.4層次聚類程序clc,clear,closeall;X=[00;11;22;38;48;53;54;63;64;75];Z=linkage(X);dendrogram(Z,0),title('層次聚類樹');T1=cluster(Z,‘Cutoff’,1.15);T2=cluster(Z,‘MaxClust’,3);figure,gscatter(X(:,1),X(:,2),T2,‘rgb’,‘o+x’,8)；title('例題數(shù)據(jù)層次聚類結(jié)果');7.4層次聚類程序111213141516171819層次聚類樹聚類結(jié)果（4）分析7.4層次聚類單向性：分裂方法中，一旦在某一步被分開，即使距離很近，也不能再聚集。聚合方法中，一旦在某一步被合并，即使距離較遠(yuǎn)，也不能再分裂。解決辦法：分裂合并結(jié)合，如圖像處理中的區(qū)域分裂合并7.5高斯混合聚類（1）基本概念多元高斯分布

7.5高斯混合聚類高斯混合分布

7.5高斯混合聚類

高斯混合聚類

7.5高斯混合聚類（2）參數(shù)求解最大似然估計(jì)

可分為有監(jiān)督和無監(jiān)督兩種情況7.5高斯混合聚類求最優(yōu)有約束條件，采用拉格朗日函數(shù)法7.5高斯混合聚類EM算法

7.5高斯混合聚類（3）樣本歸類

例7-10：有10個(gè)二維樣本，進(jìn)行高斯混合聚類。7.5高斯混合聚類（4）例題

序號(hào)取值序號(hào)取值7.5高斯混合聚類

7.5高斯混合聚類

最終的后驗(yàn)概率為：

歸類：

（5）仿真實(shí)現(xiàn)7.5高斯混合聚類例7-11：設(shè)定均值和方差，生成二元高斯混合分布數(shù)據(jù)，并對(duì)數(shù)據(jù)進(jìn)行高斯混合聚類。生成數(shù)據(jù)，根據(jù)EM算法實(shí)現(xiàn)采用封裝好的函數(shù)gmdistribution模型：高斯混合分布，生成函數(shù)為gmdistributionfitgmdist函數(shù)：采用EM算法，通過求解最大似然函數(shù)，對(duì)數(shù)據(jù)擬合高斯混合分布模型cluster函數(shù)：實(shí)現(xiàn)聚類設(shè)計(jì)思路7.5高斯混合聚類程序clc,clear,closeall;mu1=[11];mu2=[55];mu3=[91];Sigma1=[10.4;0.41];Sigma2=[1-0.6;-0.61];Sigma3=[10;01];c=3;N=50;rng(1);X=[mvnrnd(mu1,Sigma1,N);mvnrnd(mu2,Sigma2,N);

mvnrnd(mu3,Sigma3,N)];label=ones(N,1);label=[label;label*2;label*3];GMModel=fitgmdist(X,c);Mu=GMModel.mu

subplot(121),gscatter(X(:,1),X(:,2),label,'rgb','*+.');h=gca;holdongmPDF=@(x1,x2)

reshape(pdf(GMModel,[x1(:)x2(:)]),size(x1));fcontour(gmPDF,[h.XLimh.YLim])legendoffholdoffidx=cluster(GMModel,X);subplot(122),gscatter(X(:,1),X(:,2),idx,'rgb','*+.');legend('第1類','第2類','第3類','Location','best');7.5高斯混合聚類7.5高斯混合聚類數(shù)據(jù)及概率密度函數(shù)等高線高斯混合聚類結(jié)果仿真結(jié)果7.6其他聚類算法簡介將模糊理論和聚類方法結(jié)合，實(shí)現(xiàn)不分明的劃分，以起到更好的聚類效果。代表性方法：模糊C均值算法（FCM）采用加權(quán)的誤差平方和函數(shù)作為隸屬度函數(shù)，通過迭代運(yùn)算，獲取模糊分類矩陣和聚類中心，進(jìn)而獲取最終的分類結(jié)果。仿真函數(shù)：fcm（1）模糊聚類7.6其他聚類算法簡介假設(shè)聚類結(jié)構(gòu)能通過樣本分布的緊密程度確定，從樣本密度的角度考察樣本間的可連接性，并基于可連接樣本不斷擴(kuò)展聚類簇獲得最終聚類結(jié)果。代表性方法：DBSCAN采用樣本點(diǎn)周圍鄰域內(nèi)的最少鄰點(diǎn)數(shù)描述樣本分布的緊密程度。仿真函數(shù)：dbscan（2）密度聚類7.8聚類性能度量對(duì)聚類算法的結(jié)果進(jìn)行評(píng)價(jià)（1）外部準(zhǔn)則對(duì)數(shù)據(jù)集的劃分有一個(gè)先驗(yàn)?zāi)Ｐ停ɑ騾⒖寄Ｐ停?，將聚類結(jié)果和先驗(yàn)?zāi)Ｐ瓦M(jìn)行比較

基本思路7.8聚類性能度量

歸類對(duì)比相關(guān)指標(biāo)Rand指標(biāo)Jaccard系數(shù)FMI7.8聚類性能度量（2）內(nèi)部準(zhǔn)則用數(shù)據(jù)集自身包含的向量驗(yàn)證聚類結(jié)果是否適合數(shù)據(jù)CH指標(biāo)方差比準(zhǔn)則DB指標(biāo)7.8聚類性能度量輪廓指標(biāo)

全局輪廓7.8聚類性能度量（3）相對(duì)準(zhǔn)則把當(dāng)前的聚類結(jié)果與不同