哈工大 模式識(shí)別第四章第五章

2023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林1第四章特征的選擇與提取2023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林2§4.1基本概念

如何確定合適的特征空間是設(shè)計(jì)模式識(shí)別系統(tǒng)另一個(gè)十分重要，甚至更為關(guān)鍵的問(wèn)題。如果所選用的特征空間能使同類物體分布具有緊致性，即各類樣本能分布在該特征空間中彼此分割開的區(qū)域內(nèi)，這就為分類器設(shè)計(jì)成功提供良好的基礎(chǔ)。反之，如果不同類別的樣本在該特征空間中混雜在一起，再好的設(shè)計(jì)方法也無(wú)法提高分類器的準(zhǔn)確性。這一章要討論的問(wèn)題就是特征空間如何設(shè)計(jì)的問(wèn)題2023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林3

如何構(gòu)造一個(gè)特征空間，即對(duì)要識(shí)別的事物用什么方法進(jìn)行描述、分析的問(wèn)題？1、物理量的獲取與轉(zhuǎn)換(原始測(cè)量）這是指用什么樣的傳感器獲取電信號(hào)，如攝取景物則要用攝像機(jī)。可以稱之為原始信息(原始測(cè)量，得到測(cè)量空間)。2、描述事物方法的選擇與設(shè)計(jì)(特征形成)

在得到了原始信息之后，要對(duì)它進(jìn)一步加工，以獲取對(duì)分類最有效的信息。

設(shè)計(jì)所要信息的形式是十分關(guān)鍵的。2023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林4例用RGB顏色空間和HSI顏色空間右邊是原始圖像，左邊是用HSI空間描述的同一圖像(但是為了顯示出來(lái)，用H對(duì)應(yīng)R，S對(duì)應(yīng)G，I對(duì)應(yīng)B，然后再以RGB的方式顯示出來(lái)3、特征空間的優(yōu)化這個(gè)層次的工作發(fā)生在已有了特征的描述方法之后，也就是已有了一個(gè)初始的特征空間，如何對(duì)它進(jìn)行改造與優(yōu)化的問(wèn)題。一般說(shuō)來(lái)要對(duì)初始的特征空間進(jìn)行優(yōu)化是為了降維。即初始的特征空間維數(shù)較高。能否改成一個(gè)維數(shù)較低的空間，稱為優(yōu)化，優(yōu)化后的特征空間應(yīng)該更有利于后續(xù)的分類計(jì)算，這就是本章著重討論的問(wèn)題。對(duì)特征空間進(jìn)行優(yōu)化有兩種基本方法：一種為特征選擇，一種為特征的組合優(yōu)化----特征的提取。2023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林52023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林6特征選擇已有D維特征向量空間，Y={y1,y2,…,yD}，從原有的D維特征空間，刪去一些特征描述量，從而得到精簡(jiǎn)后的特征空間。在這個(gè)特征空間中，樣本由d維的特征向量描述：X={x1,x2,…,xd}，d＜D。X只是Y的一個(gè)子集，每個(gè)分量xi必然能在原特征集中找到其對(duì)應(yīng)的描述量xi＝y(tǒng)j。

2023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林7特征提取找到一個(gè)映射關(guān)系：

A:Y→X

使新樣本特征描述維數(shù)比原維數(shù)降低。其中每個(gè)分量xi是原特征向量各分量的函數(shù)，即

Xi=fi(y1,y2,…,yD)

這兩種降維的基本方法是不同的。在實(shí)際應(yīng)用中可將兩者結(jié)合起來(lái)使用，比如先進(jìn)特征提取，然后再進(jìn)一步選擇其中一部分，或反過(guò)來(lái)。

2023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林8§4.2類別可分離性判據(jù)

對(duì)原特征空間優(yōu)化，就要對(duì)優(yōu)化結(jié)果進(jìn)行評(píng)價(jià)實(shí)際的評(píng)價(jià)方法，是對(duì)系統(tǒng)性能進(jìn)行測(cè)試，測(cè)試指標(biāo)主要有正確率、計(jì)算速度、存儲(chǔ)容量等。本章討論的評(píng)價(jià)方法：目的在于找出對(duì)特征空間進(jìn)行優(yōu)化的具體算法。對(duì)特征空間進(jìn)行優(yōu)化是一種計(jì)算過(guò)程，它的基本方法仍然是模式識(shí)別的典型方法：找到一種準(zhǔn)則(或稱判據(jù)，通常用一種式子表示），以及一種優(yōu)化計(jì)算方法，使這種準(zhǔn)則達(dá)到一個(gè)極值。

2023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林9判據(jù)理想的情況是與計(jì)算錯(cuò)誤率有關(guān)的判據(jù)直接反映錯(cuò)誤率的是貝葉斯公式，在實(shí)際中運(yùn)用有困難采用其他判據(jù)2023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林10可分性判據(jù)應(yīng)滿足的要求（1）與錯(cuò)誤率有單調(diào)關(guān)系，這使判據(jù)取最大值時(shí)錯(cuò)誤率也較小（2）當(dāng)特征獨(dú)立時(shí)

有可加性：

（Jij是第i類與第j類的可分性準(zhǔn)則）

（3）度量特性：（4）單調(diào)性：加入新的特征時(shí)，判據(jù)不減小2023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林11幾種常用的可分性判據(jù)以計(jì)算樣本在特征空間離散程度為基礎(chǔ)的準(zhǔn)則，稱為基于距離的可分性判據(jù)（重點(diǎn)）基于概率密度分布的可分性判據(jù)?；陟睾瘮?shù)的可分性判據(jù)（不講）

2023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林12一、基于距離的可分性判據(jù)基于距離的度量是用來(lái)進(jìn)行分類的重要依據(jù)。因?yàn)橐话闱闆r下同類物體在特征空間呈聚類狀態(tài)，即從總體上說(shuō)同類物體內(nèi)各樣本由于具有共性，因此類內(nèi)樣本間距離應(yīng)比跨類樣本間距離小。Fisher準(zhǔn)則(也可看成是特征提取方法)正是以使類間距離盡可能大同時(shí)又保持類內(nèi)距離較小這一種原理為基礎(chǔ)的。同樣在特征選擇與特征提取中也使用類似的原理，這一類被稱為基于距離的可分性判據(jù)。

2023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林13兩類之間的距離：ω1任一點(diǎn)與ω2中任一點(diǎn)的距離和的平均。多類：各類之間的平均距離

:ωi任一點(diǎn)xk(i)與ωj中任一點(diǎn)xj(

j)的距離Pi,Pj是第i類和第j類的先驗(yàn)概率度量類內(nèi)、類間的距離，可用不同方法，如歐氏距離等。

2023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林14歐氏距離下的可分性判據(jù)歐氏距離：每類均值：所有樣本集總均值：平均距離：（判據(jù)）令：則得判據(jù)的矩陣形式：上述公式是有限樣本集，是均值及散度的估計(jì)。對(duì)于無(wú)限樣本，

tr：跡2023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林152023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林16考慮類內(nèi)類間歐氏距離的其它判據(jù)判據(jù)Jd(X)是計(jì)算特征向量的總平均距離，以下一些判據(jù)則基于使類間離散度盡量大，類內(nèi)離散度盡量小的考慮而提出。2023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林17基于距離的可分性判據(jù)優(yōu)缺點(diǎn)距離準(zhǔn)則：是樣本在特征空間的分布的距離作為特征提取的依據(jù)。優(yōu)點(diǎn)：直觀，計(jì)算簡(jiǎn)便。缺點(diǎn)：沒有考慮概率分布，因此當(dāng)不同類樣本中有部分在特征空間中交迭分布時(shí)，簡(jiǎn)單地按距離劃分，無(wú)法表明與錯(cuò)誤概率之間的聯(lián)系。2023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林18基于概率分布的可分性判據(jù)：依據(jù)不同類別類分布概率密度函數(shù)來(lái)優(yōu)化特征空間不考慮各類的先驗(yàn)概率，或假設(shè)兩類樣本的先驗(yàn)概率相等（如下圖），可以看出：如果兩類條件概率分布互不交迭，則這兩類就完全可分；對(duì)所有X都有p(X|ω1)＝p(X|ω2)，則兩類就完全不可分。

完全可分重合，完全不可分二、基于概率分布的可分性判據(jù)通俗的講：若不同類別在特征空間的不同區(qū)域聚集，則分類就容易，它們重迭的程度越低，越有別于分類，因此這一類可分性判據(jù)就是用各種方式來(lái)度量它們之間重迭的程度。分布的交疊程度可用概率密度之間距離來(lái)描述2023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林192023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林20任何函數(shù)若滿足下列條件，則用于做判據(jù)：

1、Jp≥02、當(dāng)兩類完全不交疊時(shí)，Jp取最大值若對(duì)所有x有：p(X|ω2)≠0時(shí)，p(x|ω1)=0，則Jp=max3、當(dāng)兩類分布相同時(shí)，Jp=0

若：p(X|ω2)=p(x|ω1)，則Jp=0一種是用p(x|ω1)，p(x|ω2)之間的乘法來(lái)計(jì)算其重迭程度，像Bhattacharya距離、Chernoff界限等Bhattacharyya距離、Chernoff界限與錯(cuò)誤率的上界有直接關(guān)系（見第二章）。因此Bhattacharyya距離、Chernoff界限不僅用來(lái)對(duì)特征空間進(jìn)行降維優(yōu)化，而且也用來(lái)對(duì)分類器的錯(cuò)誤率作出估計(jì)。另一種用兩者間的比值，稱為散度。2023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林212023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林221、Bhattacharyya距離

和Chernoff界限Bhattacharyya距離顯然，當(dāng)p(X|ω1)＝p(X|ω2)時(shí)，JB＝0；而當(dāng)兩者完全不交迭時(shí)JB為無(wú)窮大Chernoff界限2023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林232、散度另一種常用的基于概率距離度量的判據(jù)是利用似然比或?qū)?shù)似然比。對(duì)兩類問(wèn)題，對(duì)數(shù)似然比為：

可提供ωi對(duì)ωj的可分性信息。如果對(duì)某個(gè)X，當(dāng)p(X|ω1)＝p(X|ω2)時(shí)，則lij=0,反之若兩者差異越大，則lij的絕對(duì)值也大。

2023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林24對(duì)整個(gè)特征空間概率分布的差異程度作出評(píng)價(jià)，可將對(duì)ωi類及對(duì)ωj

的平均可分性信息定義為

總的平均可分信息則可表示成散度

2023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林253、正態(tài)分布時(shí)可分性判據(jù)

若則一維：2023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林26若則2023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林274.3特征提取4.3.1按距離度量的特征提取方法

基于距離的可分性判據(jù)的實(shí)質(zhì)是Fisher準(zhǔn)則的延伸，即綜合考慮不同類樣本的類內(nèi)聚集程度與類間的離散程度這兩個(gè)因素。這種判據(jù)的優(yōu)化體現(xiàn)出降維后的特征空間較好地體現(xiàn)類內(nèi)密集、類間分離的要求。2023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林28按歐氏距離度量的特征提取方法基于距離可分性判據(jù)的特征優(yōu)化過(guò)程是通過(guò)一個(gè)線性變換實(shí)現(xiàn)的。設(shè)在原特征空間一個(gè)樣本向量表示成X(D維)而在優(yōu)化特征空間中，樣本向量表示成Y(d維)而X與Y之間的關(guān)系是：

Y=WTX其中W是一個(gè)D×d維矩陣（d<D）目的：利用判據(jù)找出一種線性變換W，它可實(shí)現(xiàn)這種判據(jù)J(Y)=J(W)的極值化。1、J2判據(jù)下的特征提取將原特征空間X(D維)通過(guò)線性映射Y=WTX降維到特征空間Y中，若X空間的類內(nèi)離散度矩陣和類間離散度矩陣分別為SW,Sb;則按J2判據(jù)的的最后特征提取矩陣W是按如下方式構(gòu)造的：若矩陣SW-1Sb

的本征值λi按大小順序列為則選擇前d個(gè)本征值所對(duì)應(yīng)的本征向量組成變換矩陣WD*d，都可使這些判據(jù)J2(W)達(dá)到最大值。2023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林292023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林30證明：因?yàn)椋篩=WTX，

設(shè)：X的類內(nèi)和類間離散度矩陣分別為SW,Sb則：Y的類內(nèi)和類間離散度矩陣分別為SW‘,Sb‘為SW’=WSW’WT,Sb’=WSb’WT

（見第3章中，F(xiàn)isher準(zhǔn)則一節(jié)）在使用J2判據(jù)下，將其Y的可分性判據(jù)表示成變換W的函數(shù)：

J2(Y)=tr[(SW’)-1Sb’]則：J2(Y)=tr[(WSWWT)-1(WSbWT)]=J2(W)可以證明：在不降維條件下，即，設(shè)W是D*D維的，則J2判據(jù)不變J2(Y)=

J2(X)。哈爾濱工業(yè)大學(xué)電信院宿富林30J2(W)=tr[(WSWWT)-1(WSbWT)]=tr[(WT)-1SW-1W-1WSbWT)]=tr[(WT)-1SW-1SbWT]=tr[SW-1SbWT(WT)-1]=tr[SW-1Sb]=J2(X)設(shè)SW-1Sb的本征值為λ1>λ2>λ3>……>λD

，對(duì)應(yīng)的本征向量矩陣為U=[u1，u2,….,uD]則UTSW-1SbU=Λ,其中：令W=UT=U-1則J2(W)=tr[UTSW-1SbU]

2023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林312023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林32上式表明D維特征空間中，J2判據(jù)的值是矩陣的全部本征值之和。令上式中WT=Ud=[u1，u2,….,ud]則則：如果矩陣的本征值按大小順序列為那么由對(duì)應(yīng)于d個(gè)最大的本征值的本征向量所組成的矩陣W(D×d)，就能使所得到的d維特征滿足J2判據(jù)最大的要求。此結(jié)論對(duì)J4判據(jù)也適用2023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林33例：給定先驗(yàn)概率相等的兩類，其均值向量分別為：協(xié)方差矩陣是：

求用J2判據(jù)的最優(yōu)特征提取。

2023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林34解：應(yīng)先求，再求此矩的特征矩陣。混合均值類間離散度矩陣：類內(nèi)離散度矩陣2023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林35求

的本征值矩陣。由于這是一個(gè)兩類別問(wèn)題，總均值向量μ值是兩個(gè)均值向量μ1和μ2的線性求和，則

中只有一個(gè)是獨(dú)立的，因此

的秩是一，換句話說(shuō)它只有一個(gè)非零本征值，W是D×1矩陣，是一個(gè)向量W，求該向量需解

利用W向量對(duì)原始的兩類兩維樣本進(jìn)行線性變換得到新的一維分布，特征空間從二維降到一維，并滿足J2判據(jù)。該特征空間實(shí)質(zhì)上就是對(duì)應(yīng)于Fisher準(zhǔn)則求得的線性分類器的法向量。如果討論的是多類別C問(wèn)題，則優(yōu)化后的維數(shù)至多為類別數(shù)減一(C-1)。2023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林362、J5判據(jù)下的特征提取由于和是對(duì)稱矩陣，因此，存在矩陣U使得：則：

2023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林372023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林38即：是的本征值矩陣或是對(duì)角陣的證明及計(jì)算方法：2023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林39J5的另一種形式（與J2比較）又設(shè)的本征值矩陣是則：2023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林404.3.2按概率距離判據(jù)提取特征

設(shè)原始特征為Y，而經(jīng)變換后的特征為X，兩者之間有映射關(guān)系

X=WTY

則原空間中一矩陣A經(jīng)映射后為：A*=WTAW映射后概率距離判據(jù)：

JC(X)=JC(WTY)=JC(W)JD(X)=JD(WTY)=JD(W)2023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林412023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林41一、正態(tài)分布下基于Jc的特征提取當(dāng)兩類都是正態(tài)分布時(shí)：2023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林422023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林432023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林44由于Jc在任何非奇異變換下具有不變性，因此，WU=VU-1U=V也是最優(yōu)變換陣，是Σ-1M的本征向量。而M的秩是1，故只有一個(gè)非零本征值，此時(shí)：2023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林45可證，只有一個(gè)非零本征值，此時(shí)，W是一維的：是的本征值矩陣W是其本征向量2023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林462023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林472023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林48根據(jù)Jc對(duì)非奇異變換的不變性，W即是Σ2-1Σ1的本征向量。此時(shí)：2023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林49為使Jc最大，應(yīng)選擇滿足如下關(guān)系的d個(gè)本征值對(duì)應(yīng)的本征向量組成的矩陣。2023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林502023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林50步驟不同s，結(jié)果不同。1、s=0.5，得：Vi,i=1,2,…,d。2、根據(jù)Vi,i=1,2,…,d,求最優(yōu)S(使Jc最大)3、求最佳Vi,i=1,2,…,d4、用新的S重復(fù)1，2、3直至獲得一組穩(wěn)定Vi二、用散度準(zhǔn)則JD的特征提取2023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林51只有兩類時(shí)：2023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林52最佳W是對(duì)應(yīng)下列次序的本征值對(duì)應(yīng)的本征向量例：有兩類樣本：

W1:x11=(0,0,0)T,X12=(1,0,0)T,X13=(1,0,1)T,X14=(1,1,0)T

W2:x21=(0,0,1)T,X22=(0,1,0)T,X23=(0,1,1)T,X24=(11,1)T

試?yán)蒙⒍菾D降低維數(shù)。2023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林53特征提取結(jié)果：Y=WTXW1:y11=0,y12=-1,y13=0,y14=0W2:y21=1,y22=1,y23=2,y24=12023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林54-1012*00*2023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林55§4.4特征選擇

特征選擇在概念上十分簡(jiǎn)單，即對(duì)原有特征進(jìn)行刪選優(yōu)化。通常，人們認(rèn)為：只要逐個(gè)分析每個(gè)特征，判斷它對(duì)分類的價(jià)值，然后根據(jù)其優(yōu)值刪去或保留，這是一個(gè)為人們常采用方法，但是這種方法并不能保證特征空間的最優(yōu)組合優(yōu)化，因此本節(jié)討論了一些原理上更好的方法。2023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林56兩個(gè)問(wèn)題一：選擇特征的標(biāo)準(zhǔn)：也就是選擇前面討論過(guò)的可分離性判據(jù)，以這些判據(jù)為準(zhǔn)則，使所選擇的d維子空間具有最大的可分離性。二：是要找出較好的特征選擇方法，以在允許的時(shí)間內(nèi)選擇出一組最優(yōu)的特征。所謂最優(yōu)的特征組，就是要找到合適的特征的組合。如果從逐個(gè)特征配組進(jìn)行性能比較的話，即窮舉的算法，特征配組的數(shù)量可能極大，組合配置的數(shù)目按下式計(jì)算

2023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林57如果D＝100，d＝10，則q的數(shù)量級(jí)就是1013，即使D＝20，d＝10，則q也可達(dá)184756種。如果將所有可能的特征配組列舉出來(lái)，按某選定的可分離性判據(jù)進(jìn)行計(jì)算，從中擇優(yōu)，其計(jì)算量之大是可想而知的。任何非窮舉的算法都不能確保所得結(jié)果是最優(yōu)的，因此要得最優(yōu)解，就必需采用窮舉法，只是在搜索技術(shù)上采用一些技巧，使計(jì)算量有可能降低。2023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林58“自上而下”與“自下而上”“自上而下”是指，從D維特征開始，逐步將其中某些特征刪除，直到剩下所要求的d維特征為止。而“自下而上”則是從零維特征空間開始，逐個(gè)地從D維持征中選擇特征，直至達(dá)到預(yù)定的維數(shù)指標(biāo)為止。在選擇的過(guò)程中，“自上而下”算法做到篩選剩下的特征組在每一步上都是最優(yōu)的，而“自下而上”則在每一步都生成最優(yōu)的特征空間。

2023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林59

4.4.1最優(yōu)搜索算法

“分支定界”算法：至今能得到最優(yōu)解的唯一快速算法屬于“自上而下”算法，但是具有回溯功能，可使所有可能的特征組合都被考慮到。其核心問(wèn)題是通過(guò)合理組合搜索過(guò)程，可以避免一些計(jì)算而仍能得到最優(yōu)的結(jié)果。關(guān)鍵是利用了判據(jù)的單調(diào)性。如果特征存在包含關(guān)系：?i是?j的子集

則有J(?i)≤J(?j)稱該判據(jù)具有單調(diào)性分支定界算法（略）2023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林604.4.2次優(yōu)搜索法

上述分支定界算法雖然比盲目窮舉法節(jié)省計(jì)算量，但計(jì)算量仍可能很大而無(wú)法實(shí)現(xiàn)，因此人們還是常用次優(yōu)搜索法。4.4.2.1單獨(dú)最優(yōu)特征組合

這是一種最簡(jiǎn)單的方法，即將各特征按單獨(dú)使用計(jì)算其判據(jù)值，然后取其前d個(gè)判據(jù)值最大的特征作為最優(yōu)特征組合。這種做法的問(wèn)題在于即使各特征是獨(dú)立統(tǒng)計(jì)的，也不一定得到最優(yōu)結(jié)果。

2023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林61但如果可分性判據(jù)可寫成如下形式

或

則用這種方法可以選出一組最優(yōu)的特征來(lái)。例如當(dāng)兩類都是正態(tài)分布，各特征統(tǒng)計(jì)獨(dú)立時(shí)，用Mahalanobis距離作為可分性判據(jù)，上述條件可以滿足。

2023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林62

4.4.2.2順序前進(jìn)法

(SequentialForwardSelection----SFS)

這是最簡(jiǎn)單的自下而上搜索方法。首先計(jì)算每個(gè)特征單獨(dú)進(jìn)行分類的判據(jù)值，并選擇其中判據(jù)值最大的特性，作為入選特征。然后每次從未入選的特征中選擇一個(gè)特征，使得它與已入選的特征組合在一起時(shí)所得的J值為最大，直到特征數(shù)增至d個(gè)為止。

2023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林63廣義順序前進(jìn)法

(GeneralizedSequentialForwardSelection----GSFS)順序前進(jìn)法與前一小節(jié)的單獨(dú)特征最優(yōu)化組合相比，一般說(shuō)來(lái)，由于考慮了特征之間的相關(guān)性，在選擇特征時(shí)計(jì)算與比較了組合特征的判據(jù)值，要比前者好些。其主要缺點(diǎn)是，一旦某一特征被選入，即使由于后加入的特征使它變?yōu)槎嘤?，也無(wú)法再把它剔除。推廣至每次入選

r個(gè)特征，而不是一個(gè)，稱為廣義順序前進(jìn)法(GSFS)。與SFS相比，該法在每次入選r個(gè)特征時(shí)，考慮了他們之間的相關(guān)性。缺點(diǎn)是計(jì)算量大大增加.CD-kr。2023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林644.4.2.3順序后退法

(SequentialBackwardSelection----SBS)

這是一種自上而下的方法。做法也很簡(jiǎn)單，從現(xiàn)有的特征組中每次減去一個(gè)不同的特征并計(jì)算其判據(jù)，找出這些判據(jù)值中之最大值，如此重復(fù)下去直到特征數(shù)達(dá)到予定數(shù)值d為止。與SFS相比，此法計(jì)算判據(jù)值是在高維特征空間進(jìn)行的，因此計(jì)算量比較大。此法也可推廣至每次剔除r個(gè)，稱為廣義順序后退法(GeneralizedSequentialBackwardSelection----GSBS)。

2023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林65

4.4.2.4增l減r法(l-r法)

前面兩種方法都有一個(gè)缺點(diǎn)，即一旦特征入選(或剔除)，過(guò)程不可逆轉(zhuǎn)。為了克服這種缺點(diǎn)，可采用將這兩種方法結(jié)合起來(lái)的方法，即增l減r法。其原理是對(duì)特征組在增加l個(gè)特征后，轉(zhuǎn)入一個(gè)局部回溯過(guò)程，又用順序后退法，剔除掉r個(gè)特征。這種方法既可能是“自上而下”方法，也可能是“自下而上”的，這取決于l與r的數(shù)據(jù)大小。當(dāng)l>r時(shí)，入選特征數(shù)逐漸增加，屬“自下而上”型，反之屬“自上而下”型。

l-r法1）用SFS法在未入選特征中逐個(gè)入選l個(gè)特征2）用SBS法在已入選特征中逐個(gè)剔除r個(gè)特征。3）若特征數(shù)是d，則終止算法。否則，轉(zhuǎn)入（1）L>r時(shí)，是自下而上的算法，先執(zhí)行第1步，起始時(shí)，入選特征是空集ΦL<r時(shí)，是自上而下的算法，先執(zhí)行第2步，起始時(shí)，入選特征是原有特征集X={x1,x2,….,XD}2023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林662023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林67（ZL,Zr）法此法也可推廣至用GSFS及GSBS代替SFS及SBS，并可在實(shí)現(xiàn)增加l特征時(shí)采用分幾步實(shí)現(xiàn)。(ZL,Zr)法：增L個(gè)特征用ZL步，每步可入選li(i=1,2,…,ZL)個(gè)特征。ZL=（l1,l2,l3,……,lZL）；減r則用Zr步，每步可剔除ri(i=1,2,…,Zr)個(gè)特征。Zr=（r1,r2,r3,……,rZr）這種做法是為了既考慮入選(或剔除)特征之間的相關(guān)性，又不至因此引起計(jì)算量過(guò)大。合理地設(shè)置ZL與Zr，可以同時(shí)對(duì)兩者，即計(jì)算復(fù)雜性及特征選擇的合理性兼顧考慮。2023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林68前面的各種方法可看作是（ZL,Zr）法的特例(ZL,Zr)法等效算法ZL=（1）Zr=（0）SFSZL=（0）Zr=（1）SBSZL=（d）Zr=（0）窮舉法ZL=（L）Zr=（0）GSFSZL=（0）Zr=（r）GSBSZL=(1,1,1,…,1)Zr=(1,1,….,1)（l，r）2023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林694.5基于Karhunen-Loeve變換

（K-L變換）的特征提取

K-L變換又稱主分量分析，是一種正交變換，常用來(lái)作為數(shù)據(jù)壓縮。這里我們用它作降維

2023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林704.5.1傅立葉級(jí)數(shù)展開周期平穩(wěn)隨機(jī)過(guò)程x(t)的Fourier展開則：周期平穩(wěn)過(guò)程的Fourier系數(shù)互不相關(guān)2023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林71(X(t)周期------R(t)周期,周期也為T）2023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林724.5.2K-L展開將一個(gè)非周期隨機(jī)過(guò)程x(t)在區(qū)間[a,b]展開為其中：2023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林73本征值本征函數(shù)則：兩邊同乘并積分，則：2023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林74離散情況用完備正交向量(基)uj(j=1,2,…)展開若用有限項(xiàng)估計(jì)：則展開x’是x的一個(gè)近似均方誤差為：2023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林75本征分解2023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林76誤差因此，可對(duì)X的自相關(guān)做本征分解，若取前d個(gè)最大本征值對(duì)應(yīng)的本征向量來(lái)展開X時(shí)，截?cái)嗟木秸`差最小(實(shí)際展開時(shí)，因?yàn)閄的維數(shù)是D,只能求得D個(gè)本征值和本征向量)。這d個(gè)本征向量所組成的正交坐標(biāo)系稱為X在D維空間的d維K-L變換系。X在K-L坐標(biāo)系uj上的展開系數(shù)稱作X的K-L變換。2023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林774.5.3K-L展開式的性質(zhì)(1)K-L變換的展開系數(shù)是互相無(wú)關(guān)的。2023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林78(2)K-L變換后的協(xié)方差陣為對(duì)角陣令K-L變換后的D維坐標(biāo)系統(tǒng)中樣本向量為

X’=(c1,c2,…,cD)T則：或：這表明經(jīng)過(guò)K-L變換后，原向量各分量之間存在的相關(guān)性已被消除。2023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林794.5.4K-L變換的一些典型應(yīng)用

1．降維與壓縮

例如：一幅人臉圖象，大小為：M×N。

K-L變換后只用到30個(gè)基，那么維數(shù)就降至30?？梢娊稻S的效果是極其明顯的。另一方面降維與數(shù)據(jù)壓縮又是緊密聯(lián)系在一起的。譬如原訓(xùn)練樣本集的數(shù)量為V，現(xiàn)采用30個(gè)基，每個(gè)基實(shí)質(zhì)上是一幅圖象，再加上每幅圖象的描述參數(shù)，數(shù)據(jù)量是大大降低。基圖像Ui，i=1，…,d是通用的

=(c1,c2,……)T

2023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林802．構(gòu)造參數(shù)模型使用K-L變換不僅僅起到降維與壓縮數(shù)據(jù)的作用，更重要的是每個(gè)描述量都有明確的意義，因而改變某一個(gè)參數(shù)就可讓圖象按所需要的方向變化。在沒有使用K-L變換的原數(shù)據(jù)集中對(duì)圖象的描述量是每個(gè)象素的灰度值，而弧立地改變某個(gè)象素的灰度值是沒有意義的。

而在使用K-L變換后，每個(gè)描述量都有其各自的作用。因此通過(guò)改變這些參數(shù)的值就可實(shí)現(xiàn)對(duì)模型的有效描述，這在圖象生成中是很有用的。因此利用K-L變換構(gòu)造出可控制的，連續(xù)可調(diào)的參數(shù)模型在人臉識(shí)別與人臉圖象重構(gòu)采方面的應(yīng)用是十分有效的。

2023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林813．人臉識(shí)別利用K-L變換進(jìn)行人臉圖象識(shí)別是一個(gè)著名的方法。首先搜集要識(shí)別的人的人臉圖象，建立人臉圖象庫(kù)。然后利用K-L變換確定相應(yīng)的人臉基圖象(特征臉)，再反過(guò)來(lái)用這些基圖象對(duì)人臉圖象庫(kù)中的所有人臉圖象進(jìn)行K-L變換，從而得到每幅圖象的參數(shù)向量并將每幅圖的參數(shù)向量存起來(lái)。在識(shí)別時(shí)，先對(duì)一張所輸入的臉圖象進(jìn)行必要的規(guī)范化，再進(jìn)行K-L變換分析，得到其參數(shù)向量。將這個(gè)參數(shù)向量與庫(kù)中每幅圖的參數(shù)向量進(jìn)行比較，找到最相似的參數(shù)向量，也就等于找到最相似的人臉，從而認(rèn)為所輸入的人臉圖象就是庫(kù)內(nèi)該人的一張人臉,完成了識(shí)別過(guò)程。

2023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林824．人臉圖象合成用K-L變換構(gòu)造參數(shù)模型的另一種典型用途是人臉圖象合成。有目的的控制各個(gè)分量的比例，也就是通過(guò)調(diào)整參數(shù)向量?？梢詫⒁环粠П砬閳D象改變成帶各種表情的圖象，稱為人臉表情圖象合成。2023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林832023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林844.5.5使用K-L變換進(jìn)行特征提取上面討論K-L變換時(shí)得出K-L坐標(biāo)系是由E[XXT]的本征值對(duì)應(yīng)的本征向量產(chǎn)生，因而被稱為K-L坐標(biāo)系的產(chǎn)生矩陣。實(shí)際上使用不同的向量作為產(chǎn)生矩陣，會(huì)得到不同的K-L坐標(biāo)系，從而滿足不同的分類要求。一般，沒有類別標(biāo)簽的樣本集的均值向量u常常沒有意義，因此，可用樣本數(shù)據(jù)的協(xié)方差矩陣

E[(X-u)(X-u)T]作為產(chǎn)生矩陣。

2023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林85對(duì)分類問(wèn)題，如何形成產(chǎn)生矩陣?當(dāng)樣本集中各樣本的類別標(biāo)簽已知時(shí)，可以得到不同的Σ，Σ有多個(gè)（不同類可有不同的Σ）,如何形成產(chǎn)生矩陣?1）如各類別先驗(yàn)概率為Pi

，均值為i，協(xié)方差矩陣為Σi=E[(X-ui)(X-ui)T]

則可以用類內(nèi)離散矩陣SW=ΣPi

Σi作為產(chǎn)生矩陣，其效果相當(dāng)于只按類內(nèi)離散程度進(jìn)行特征選取。2）如果只以某一類樣本集的協(xié)方差矩陣Σi作為產(chǎn)生矩陣，則效果是對(duì)該類樣本集有信息壓縮的最優(yōu)性。2023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林861利用類均值向量提取特征類條件均值ui包含大量的分類信息。為了降低維數(shù)，且盡可能地保持原有特征的分類信息，應(yīng)選擇一種變換，是變換后的類條件均值向量的給分量比其他的變換保持更多的分類信息?；跉W氏距離特征提?。号袚?jù)是從使類內(nèi)盡可能密集，類間盡可能分開的思想出發(fā)的。但是，各類均值向量各分量的分類性能，不僅與取決于各均值向量各分量之間的距離，而且，還和其方差以及各分量的相關(guān)程度有關(guān)。如何在K-L變換方法中體現(xiàn)對(duì)這兩者的兼顧?具體算法1）為了估計(jì)各分量（特征）對(duì)于分類的單獨(dú)作用，先按類內(nèi)離散度矩陣Sw作為產(chǎn)生矩陣產(chǎn)生相應(yīng)的K-L坐標(biāo)系統(tǒng)，從而把包含在原向量中各分量的相關(guān)性消除，并得到在新坐標(biāo)系中各分量離散的程度。2）然后對(duì)均值向量在這些新坐標(biāo)中分離的程度作出判斷，決定在各坐標(biāo)軸分量均值向量所能提供的相對(duì)可分性信息。據(jù)此選取K-L變換的基向量作為特征提取變換矩陣。2023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林872023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林88在uj軸上，原第i類特征向量Xik投影為：Xikj=ujTXik其類內(nèi)離散度：其類間離散度2023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林892023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林90可設(shè)判據(jù)J(Xi)為類間離散度與類內(nèi)離散度在uj坐標(biāo)的分量之比:

其中:J(Xi)越大，表明在新坐標(biāo)系中該坐標(biāo)抽包含較多可分性信息。2023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林913）為了降低特征空間的維數(shù)，可以將各分量按大小重新排列，使

J(X1)≥J(X2)≥J(X3)….≥J(XD)

取與前面d個(gè)最大的J(Xi)≥值相對(duì)應(yīng)的本征向量uj，j=1,...,d;作為特征空間的基向量。W=[u1,u2,…,ud]

2023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林92

例:設(shè)有兩類問(wèn)題，其先驗(yàn)概率相等，即:P(w1)=P(w2)=0.5，設(shè)樣本的類均值向量分別為：

類協(xié)方差矩陣分別是：把維數(shù)從2壓縮為12023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林93解1）將SW作K-L變換的產(chǎn)生矩陣，求其本征矩陣得K-L變換的變換矩陣?？汕蟮帽菊髦稻仃嚭捅菊飨蛄糠謩e是：2023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林94又2）求得：3）2023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林952、包含在類平均向量中判別信息的最優(yōu)壓縮上面方法（利用類均值向量提取特征）為了兼顧類內(nèi)離散度與類間離散度，包含在類均值向量?jī)?nèi)的分類信息并沒有全部利用。即：類平均向量的判別信息在K-L坐標(biāo)系的各個(gè)分量中都有反映，并沒有得到最優(yōu)壓縮。

如圖，如僅從類均值向量所包含的分類判別信息全部被利用出發(fā)，應(yīng)選擇包含兩均值向量連線方向在內(nèi)的坐標(biāo)系。但是簡(jiǎn)單地從類均值向量來(lái)確定特征子空間，雖然實(shí)現(xiàn)很容易，但一般不能滿足各分量間互不相關(guān)的要求。2023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林96例外情況：如果類內(nèi)離散度矩陣Sw是一個(gè)單位矩陣，即它在特征空間中以超球體分布，從類均值向量來(lái)確定特征子空間就可做到既保持各分量的不相關(guān)性，同時(shí)又能充分利用包含在類均值向量?jī)?nèi)的差別信息。從這種特殊情況得到啟發(fā)，一種充分利用類均值向量所包含的判別信息的方法因此而產(chǎn)生。具體說(shuō)來(lái)這種方法分成兩步：1）白化處理2）特征提取2023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林97第一步：白化處理1、先用原坐標(biāo)系中Sw作為產(chǎn)生矩陣，實(shí)行K-L變換，將原有數(shù)據(jù)的相關(guān)性消除掉。

UTSw=ΛU，或UTSwU=Λ在K-L坐標(biāo)系U上，新的特征向量為：Y1=UTX

Y1的類內(nèi)離散度矩陣S’w=Λ是一個(gè)對(duì)角矩陣。2、進(jìn)一步實(shí)行變換：Y2=Λ-1/2Y1，則Y2的類內(nèi)離散度矩陣變?yōu)椋害?1/2

UTSwUΛ-1/2=Λ-1/2ΛΛ-1/2=I

即：(UΛ-1/2)

Sw(UΛ-1/2)=I3、令:B=UΛ-1/2（白化矩陣），則：BTSwB=I（白化）

此時(shí)，

Y2=Λ-1/2Y1=Λ-1/2UTX=(UΛ-1/2)TX=BTX經(jīng)過(guò)B變換后（Y2）的類間離散度矩陣S’b應(yīng)有：S’b=BTSbB2023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林98第二步:特征提取1）采用上節(jié)方法求最佳的變換。因S’W

=I則，Λ=I而且，U可以是任何正交矩陣。即UTIU=UTU=I則判據(jù)：由于U可以上任何正交矩陣，因此，可以以S’b作為產(chǎn)生矩陣，作第二次K-L變換，得到正交矩陣VTSb’=Λ’V則判據(jù)因此，按判據(jù)最大選擇uj，就是按Sb’正交分解的本征值λ’j最大選擇。由于S’b的秩最多是c-1，所以最多只有c-1個(gè)非零本征值。選擇最大的d（≤c-1）個(gè)非零本征值

，則該d個(gè)非零本征值就可表示類均值向量所包含的全部信息。設(shè)這d個(gè)本征向量系統(tǒng)用V’表示，即

V’=[v1,v2,….,vd]（d≤c-1）則變換為:Y=V’TY22）將第一步得到的結(jié)果代入，整個(gè)變換為：Y=VTY2=VTBTX=(BV)TX=WTX因此變換矩陣為：W=BV=UΛ-1/2V2023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林99具體算法1）對(duì)原特征向量計(jì)算類內(nèi)離散度矩陣Sw和類間離散度矩陣Sb2）用Sw作為產(chǎn)生矩陣做KL變換求坐標(biāo)系U及Λ：UTSwU=Λ3）計(jì)算變換矩陣:B=UΛ-1/24）計(jì)算經(jīng)過(guò)B變換后的類間離散度矩陣S’b：S’b=BTSbB5）以S’b作為產(chǎn)生矩陣，作第二次K-L變換VTSb’=Λ’V6）選擇Λ’中最大d個(gè)本征值對(duì)應(yīng)的d（≤c-1）個(gè)本征向量

V’=[v1,v2,….,vd]7）計(jì)算最終的變換矩陣：W=BV’=UΛ-1/2V’W即是降維的變換矩陣。可將D維特征向量降維d維（前3步是白化過(guò)程）2023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林1002023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林1012023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林101

例:數(shù)據(jù)同上例，求保持類均值向量中全部分類信息條件下壓縮為一維特征空間的坐標(biāo)軸。

設(shè)有兩類問(wèn)題，其先驗(yàn)概率相等，即:P(w1)=P(w2)=0.5，設(shè)樣本的類均值向量分別為：

類協(xié)方差矩陣分別是：2023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林102解：2023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林103下圖給出了兩次變換步驟

以及變換對(duì)數(shù)據(jù)產(chǎn)生的作用由圖中看出，樣本原為橢圓形分布，經(jīng)白化處理后轉(zhuǎn)化為圓形分布，此時(shí)S’w為單位矩陣。均值向量也隨之變化，最后得到的均值向量作為降維后的一維坐標(biāo)。這種方法主要用在類別數(shù)C比原特征向量的維數(shù)D小得多的情況，由于Sb的秩最多為C-1，因此可使特征維數(shù)降至C維以下。2023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林104第五章非監(jiān)督學(xué)習(xí)法2023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林105本章重點(diǎn)1.什么叫非監(jiān)督學(xué)習(xí)方法，什么叫有監(jiān)督學(xué)習(xí)方法？

2.非監(jiān)督學(xué)習(xí)方法主要的用途

3.非監(jiān)督學(xué)習(xí)方法的兩種基本處理方法：按分布密集程度劃分，與按相似度聚類劃分

4.按分布密度程度劃分的基本方法

5.動(dòng)態(tài)聚類方法與分級(jí)聚類方法的概念

6.典型的動(dòng)態(tài)聚類方法C-均值算法與ISODATA算法

7.使用非歐氏距離計(jì)算相似度的動(dòng)態(tài)聚類方法

8.分級(jí)聚類方法2023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林106本章難點(diǎn)

1.非監(jiān)督學(xué)習(xí)方法與監(jiān)督學(xué)習(xí)方法概念的區(qū)別

2.按分布密集程度劃分的基本方法

3.動(dòng)態(tài)聚類方法-迭代修正的概念

4.分級(jí)聚類方法2023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林107本章學(xué)習(xí)目標(biāo)

1.掌握非監(jiān)督學(xué)習(xí)方法的概念、用途

2.了解非監(jiān)督學(xué)習(xí)方法對(duì)數(shù)據(jù)劃分有兩種基本方法

3.掌握以c-均值算法，ISODATA算法為代表的動(dòng)態(tài)聚類方法

2023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林108§5.1引言以前討論的分類器設(shè)計(jì)方法都是在樣本集中的類別標(biāo)簽已知的條件下進(jìn)行的，這些樣本稱為訓(xùn)練樣本。在樣本類別標(biāo)簽已知的情況下，可以統(tǒng)計(jì)出各類訓(xùn)練樣本不同的描述量，如其概率分布，或在特征空間分布的區(qū)域等，利用這些參數(shù)進(jìn)行分類器設(shè)計(jì)，稱為有監(jiān)督的學(xué)習(xí)方法。然而在實(shí)際應(yīng)用中，不少情況下無(wú)法預(yù)先知道樣本的標(biāo)簽，也就是說(shuō)沒有訓(xùn)練樣本，因而只能從沒有樣本標(biāo)簽的樣本集進(jìn)行分類器設(shè)計(jì)，這就是非監(jiān)督學(xué)習(xí)方法。2023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林109一幅道路圖像按路面與非路面分類其中左圖是在圖像中路面區(qū)與非路面中各找一個(gè)窗口，將其中每個(gè)象素分別作為這兩類的訓(xùn)練樣本集，用這兩個(gè)樣本集在特征空間的分布參數(shù)進(jìn)行設(shè)計(jì)（有監(jiān)督的學(xué)習(xí)）。右圖，無(wú)法預(yù)先選擇不同類別的樣本集，而是將整幅圖的像素都作為待分類樣本集，通過(guò)它們?cè)谔卣骺臻g中表現(xiàn)出來(lái)的聚類現(xiàn)象，把不同類別劃分開。（非監(jiān)督學(xué)習(xí)）2023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林110

有監(jiān)督學(xué)習(xí)中，樣本集分布呈現(xiàn)交迭情況，而無(wú)監(jiān)督學(xué)習(xí)方法由于沒有類別樣本指導(dǎo)，無(wú)法確定它們的交迭情況，只能按分布的聚類情況進(jìn)行劃分。在類似于該例的實(shí)際應(yīng)用問(wèn)題中，預(yù)先選定不同類別的樣本往往不可能，如時(shí)間不允許，或無(wú)法用人工干予等因素。

另外在某些有監(jiān)督學(xué)習(xí)方法中（例如，局部訓(xùn)練法），也往往需要利用聚類方法將樣本按其分布劃分成若干子類等。聚類方法就是無(wú)監(jiān)督學(xué)習(xí)方法的一個(gè)內(nèi)容，它是經(jīng)常應(yīng)用的一門技術(shù)。非監(jiān)督學(xué)習(xí)方法要解決的問(wèn)題觀察事物與分析事物，從中尋找其規(guī)律性，這就是非監(jiān)督學(xué)習(xí)方法要解決的問(wèn)題。2023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林1112023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林112非監(jiān)督學(xué)習(xí)與有監(jiān)督學(xué)習(xí)的不同點(diǎn)1．?dāng)?shù)據(jù)集不同：

有監(jiān)督學(xué)習(xí)方法必須要有訓(xùn)練集與測(cè)試樣本。在訓(xùn)練集中找規(guī)律，而對(duì)測(cè)試樣本使用這種規(guī)律；

非監(jiān)督學(xué)習(xí)沒有訓(xùn)練集，只有一組數(shù)據(jù)，在該組數(shù)據(jù)集內(nèi)尋找規(guī)規(guī)律2．目的不同有監(jiān)督學(xué)習(xí)方法的目的就是識(shí)別事物。識(shí)別的結(jié)果表現(xiàn)在給待識(shí)別數(shù)據(jù)加上了標(biāo)號(hào)，因此訓(xùn)練樣本集必須由帶標(biāo)號(hào)的樣本組成。非監(jiān)督學(xué)習(xí)方法的目的是尋找數(shù)據(jù)集中的規(guī)律性。只有要分析的數(shù)據(jù)集本身，預(yù)先沒有什么標(biāo)號(hào)。如果發(fā)現(xiàn)數(shù)據(jù)集呈現(xiàn)某種聚集性，則可按自然的聚集性分類，但不以與某種預(yù)先的分類標(biāo)號(hào)對(duì)上號(hào)為目的。3.算法不同2023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林113無(wú)監(jiān)督學(xué)習(xí)算法分類兩大類：基于概率密度函數(shù)估計(jì)的直接方法：指設(shè)法找到各類別在特征空間的分布參數(shù)再進(jìn)行分類。如：?jiǎn)畏遄宇惖姆蛛x方法（投影法等），基于樣本間相似性度量的間接聚類方法：其原理是設(shè)法定出不同類別的核心或初始類核，然后依據(jù)樣本與這些核心之間的相似性度量將樣本聚集成不同類別。迭代的動(dòng)態(tài)聚類算法（K均值聚類，ISODATA算法），非迭代的分級(jí)聚類算法

2023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林114§5.2單峰子類的分離方法

樣本概率密度分布在特征空間的分布是多峰的。每個(gè)單峰區(qū)域則被看作不同的決策域。落在同一單峰區(qū)域的待分類樣本就被劃分成同一類，稱為單峰子類。5.2.1投影法高維空間尋找概率密度的“峰”是困難的。一維空間尋找概率密度的“峰”較容易。因此，可通過(guò)將高維空間樣本投影到不同的一維空間ui上，xi=uiTY；然后，在此一維空間上估計(jì)邊緣概率密度p(xi)，并在此概率密度上尋找各個(gè)峰，并確定每個(gè)峰的范圍（即每個(gè)聚類），各個(gè)聚類的分解面與該坐標(biāo)軸ui垂直，交點(diǎn)則是兩個(gè)峰值之間的最小點(diǎn)。稱為投影法。投影法的主要問(wèn)題：一：如何設(shè)計(jì)合適的坐標(biāo)系統(tǒng)（即投影方向）二、如何設(shè)計(jì)直方圖（計(jì)算邊緣概率密度）2023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林115一、如何設(shè)計(jì)直方圖1）將數(shù)據(jù)xi(k)=uiTY(k)按大小排列2）確定直方圖上的單位間隔長(zhǎng)度L3）根據(jù)L將數(shù)據(jù)xi(k)分成不同區(qū)間，統(tǒng)計(jì)；落在每個(gè)區(qū)間內(nèi)的樣本數(shù)。K

則pi(k)=K/NN:總的樣本數(shù)2023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林1162023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林117二：如何設(shè)計(jì)合適的坐標(biāo)系統(tǒng)目前還沒有合適的準(zhǔn)則用于確定坐標(biāo)系。一種啟發(fā)式的辦法是使待分類的樣本在某個(gè)坐標(biāo)軸方向具有最大的分散性，可以采用K-L變換方法。具體說(shuō)來(lái)是用混合樣本協(xié)方差矩陣作為K-L變換的產(chǎn)生矩陣，找到其本征值，并按大小排序。對(duì)此混合樣本來(lái)說(shuō)，對(duì)應(yīng)最大本征值的本征向量，離散程度最大，預(yù)期能發(fā)現(xiàn)明顯的峰值。但是，在這些方向的投影，并不能保證分出各個(gè)聚類。2023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林118可以分出各個(gè)聚類不能分出各個(gè)聚類2023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林119投影法的具體算法步驟1：計(jì)算樣本協(xié)方差矩陣具有最大本征值的本征向量Uj，把數(shù)據(jù)投影到Uj軸上。步驟2：用直方圖方法求數(shù)據(jù)的邊緣概率密度函數(shù)。步驟3：在直方圖的峰值間求最小值，在這些最小點(diǎn)作垂直于Uj的超平面把數(shù)據(jù)劃分為若干個(gè)聚類。步驟4：如果在這個(gè)軸上沒有這樣的最小值，則用下一個(gè)最大本征值對(duì)應(yīng)的本征向量重復(fù)以上過(guò)程。步驟5：對(duì)每個(gè)得到的子集(聚類)重復(fù)上述過(guò)程，直到每個(gè)集不能再分(為單峰)為止。2023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林1205.2.2單峰子集分離的其它方法基于對(duì)稱集性質(zhì)的單峰子集分離法單峰子集分離的迭代算法（略）2023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林1215.3類別分離的間接方法

----聚類方法聚類方法：不通過(guò)對(duì)概率密度函數(shù)作出估計(jì)而直接按樣本間的相似性，或彼此間在特征空間中的距離遠(yuǎn)近進(jìn)行分類。

如何聚類取決于聚類準(zhǔn)則，以使某種聚類準(zhǔn)則達(dá)到極值為最佳。兩類對(duì)數(shù)據(jù)集進(jìn)行聚類的方法：迭代的動(dòng)態(tài)聚類算法非迭代的分級(jí)聚類算法2023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林1225.3.1動(dòng)態(tài)聚類方法動(dòng)態(tài)聚類方法的任務(wù)是將數(shù)據(jù)集劃分成一定數(shù)量的子集，子集數(shù)目在理想情況現(xiàn)能體現(xiàn)數(shù)據(jù)集比較合理的劃分。問(wèn)題:

1．怎樣才能知道該數(shù)據(jù)集應(yīng)該劃分的子集數(shù)目

2．如果劃分?jǐn)?shù)目已定，則又如何找到最佳劃分

由于優(yōu)化過(guò)程是從不甚合理的劃分到“最佳”劃分，是一個(gè)動(dòng)態(tài)的過(guò)程，故這種方法稱為動(dòng)態(tài)聚類方法。2023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林1235.3.1.1動(dòng)態(tài)聚類方法3個(gè)要點(diǎn)1.選定某種距離度量作為樣本間的相似性度量；

2.確定樣本合理的初始分類，包括代表點(diǎn)的選擇，初始分類的方法選擇等。3.確定某種評(píng)價(jià)聚類結(jié)果質(zhì)量的準(zhǔn)則函數(shù)，用以調(diào)整初始分類直至達(dá)到該準(zhǔn)則函數(shù)的極值。

2023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林1245.3.1.2C-均值算法

也叫K-均值算法1.準(zhǔn)則函數(shù)—誤差平方和準(zhǔn)則這個(gè)準(zhǔn)則函數(shù)是以計(jì)算各類樣本到其所屬類均值點(diǎn)誤差平方和為準(zhǔn)則。若各類均值表示成

誤差平方和準(zhǔn)則可表示成

最佳的聚類是使Jc為最小的分類。這種類型的聚類通常稱為最小方差劃分。2023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林1252.樣本集初始劃分初始劃分的一般作法是（1）先選擇一些代表點(diǎn)作為聚類的核心（2）把其余的樣本按某種方法分到各類中去

2023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林126（1）代表點(diǎn)的幾種選擇方法(a)憑經(jīng)驗(yàn)選擇代表點(diǎn)。根據(jù)問(wèn)題的性質(zhì)，用經(jīng)驗(yàn)的辦法確定類別數(shù)，從數(shù)據(jù)中找出從直觀上看來(lái)是比較合適的代表點(diǎn)。(b)將全部數(shù)據(jù)隨機(jī)地分為C類計(jì)算各類重心，將這些重心作為每類的代表點(diǎn)。（c）用前C個(gè)樣本作為代表點(diǎn)

2023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林127(d)“密度”法選擇代表點(diǎn)。“密度”：對(duì)每個(gè)樣本確定大小相等的鄰域（如同樣半徑的超球體），統(tǒng)計(jì)落在其鄰域的樣本數(shù)，稱為該點(diǎn)“密度”。確定一個(gè)距離d選“密度”為最大的樣本點(diǎn)作為第一個(gè)代表點(diǎn)；然后，找次高“密度”的樣本點(diǎn)作為第二個(gè)代表點(diǎn)；第2個(gè)代表點(diǎn)離第1個(gè)代表點(diǎn)的距離需大于d。依次選擇其它代表點(diǎn)。其離選定的代表點(diǎn)的距離應(yīng)大于d。使用這種方法的目的是避免代表點(diǎn)過(guò)分集中在一起。

2023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林128(e)從c-1個(gè)聚類劃分問(wèn)題的解中產(chǎn)生C聚類劃分問(wèn)題的代表點(diǎn)首先，將所有樣本集看作一個(gè)聚類，計(jì)算其總均值，然后找與該均值相距最遠(yuǎn)的點(diǎn)，由該點(diǎn)及原均值點(diǎn)構(gòu)成2聚類的代表點(diǎn)。其次，依同樣方法，對(duì)已有(c-1)個(gè)聚類代表點(diǎn)(由(c-1)個(gè)類均值點(diǎn)組成)找一樣本點(diǎn)，使該樣本點(diǎn)距所有這些均值點(diǎn)的最小距離為最大，這樣就得到了第c個(gè)代表點(diǎn)。代表點(diǎn)的選擇會(huì)影響迭代結(jié)果。因?yàn)榈玫降慕Y(jié)果往往是局部最優(yōu)而非全局最優(yōu)。2023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林129(2)初始分類方法(a)對(duì)選定的代表點(diǎn)按距離最近的原則將樣本劃屬各代表點(diǎn)代表的類別。(b)在選擇樣本的點(diǎn)集后，將樣本按順序劃歸距離最近的代表點(diǎn)所屬類，并立即修改代表點(diǎn)參數(shù)，用樣本歸入后的重心代替原代表點(diǎn)。因此代表點(diǎn)在初始劃分過(guò)程中作了修改。

2023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林130(c)一種既選擇代表點(diǎn)又同時(shí)確定初始分類的方法規(guī)定一閾值d，選w1={y1}計(jì)算樣本y2與y1的距離D(y2,y1)，如其小于d，則y2歸入w1；否則建立新的類別w2={y2}。當(dāng)輪到樣本yj時(shí)，已有了K類即，而每類第一個(gè)入類樣本分別為y1,y2,…,yk（作為每類的代表點(diǎn)），則計(jì)算D(yi,yj),i=1,2,…,k；若有D(yi,yj)>d（對(duì)所有的i，i＝1,…，k），則建立新類。否則將yj歸入與y1,y2,…,yk距離最近的類別中。重復(fù)上一步，直至所有樣本分類

2023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林131(d)標(biāo)準(zhǔn)化特征求和量化方法：i)先將數(shù)據(jù)標(biāo)準(zhǔn)化ii)若yij

表示標(biāo)準(zhǔn)化后第i個(gè)樣本的第j個(gè)特征量，令：iii)求出SUM(i)的最大值與最小值

MA=max{SUM(i)},MI=min{SUM(i)}iv）如果欲將樣本劃分為c類，則對(duì)每個(gè)i計(jì)算

v)如所得結(jié)果非整數(shù)，則找到其最近整數(shù)K，將第i個(gè)樣本歸入第K類

2023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林1323.迭代計(jì)算c-均值算法的迭代計(jì)算過(guò)程在原理上與梯度下降法是一樣的，即以使準(zhǔn)則函數(shù)值下降為準(zhǔn)則。但是由于c-均值算法的準(zhǔn)則函數(shù)值由數(shù)據(jù)劃分的調(diào)整所決定，因此只能通過(guò)逐個(gè)數(shù)據(jù)從某個(gè)子集轉(zhuǎn)移到另一子集計(jì)算準(zhǔn)則函數(shù)值是否降低為準(zhǔn)則。

2023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林133對(duì)劃分的修改規(guī)則如果原屬Гk

中的一個(gè)樣本y從Гk

移入Гj

時(shí)，它會(huì)對(duì)誤差平方和產(chǎn)生影響,Гk類在抽出樣本y后其相應(yīng)均值為而樣本y新加盟的Гj

集合均值

2023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林134由于y的移動(dòng)只影響到k與j這兩類的參數(shù)改動(dòng)，因此，計(jì)算Jc值的變動(dòng)只要計(jì)算相應(yīng)兩類誤差平方和的變動(dòng)即可，此時(shí)

總誤差變化：如果則即將樣本y從Гk

移入至Гj

就會(huì)使誤差平方總和Jc減小，它表明樣本變動(dòng)是合乎準(zhǔn)則要求的2023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林135算法(1)選擇某種方法把樣本分成C個(gè)聚類的初始劃分，計(jì)算每個(gè)聚類的均值m1,…,mc和Jc(2)選擇一個(gè)備選樣本y，設(shè)其在wi中(3)若Ni=1，則轉(zhuǎn)(2)（樣本只有1個(gè)，不移出），否則繼續(xù)下一步。(4)計(jì)算

2023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林136(5)對(duì)于所有的j，若ek≤ej（表明ek<ei）則將y從wi移到wk中（否則，ei<ei,不用移）(6)重新計(jì)算mi和mk，并修改Jc。(7)若連續(xù)迭代N次(即所有樣本都運(yùn)算過(guò))Jc不變，則停止，否則轉(zhuǎn)到2。

2023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林137確定類別數(shù)的實(shí)驗(yàn)方法上述C—均值算法都是在類別c已知條件下進(jìn)行的。在類別數(shù)未知情況下，可以假設(shè)類別數(shù)是逐步增加的，準(zhǔn)則函數(shù)隨c的增加而單調(diào)地減小。可選擇平緩時(shí)轉(zhuǎn)折處的C值。2023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林1385.3.1.3ISODATA算法

C—均值算法比較簡(jiǎn)單，但它的自我調(diào)整能力也比較差。這主要表現(xiàn)在類別數(shù)不能改變，受代表點(diǎn)初始選擇的影響也比較大。全稱‘迭代自組織數(shù)據(jù)分析技術(shù)’（IterativeSelf-OrganizingData

AnalysisTechniqueAlgorithm）。ISODATA算法的功能與C—均值算法相比的改進(jìn)。

1.不是每調(diào)整一個(gè)樣本的類別就重新計(jì)算一次各類均值（逐個(gè)樣本修正），而是每次把全部樣本都調(diào)整完畢后再重新計(jì)算樣本均值（成批樣本修正）。2.考慮了類別的合并與分裂，因而有了自我調(diào)整類別數(shù)的能力。從而可以得到較為合理的類別數(shù)。2023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林139合并主要發(fā)生在某一類內(nèi)樣本個(gè)數(shù)太少的情況，或兩類聚類中心之間距離太小的情況。為此設(shè)有最小類內(nèi)樣本數(shù)限制N，以及類間中心距離參數(shù)L。若出現(xiàn)兩類聚類中心距離小于L或樣本數(shù)小于N的情況，可將此兩類合并分裂則主要發(fā)生在某一類別的某分量出現(xiàn)類內(nèi)方差過(guò)大的現(xiàn)象，因而宜分裂成兩個(gè)類別，以維持合理的類內(nèi)方差。

給出一個(gè)對(duì)類內(nèi)分量方差的限制參數(shù)S，用以決定是否需要將某一類分裂成兩類。2023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林140ISODATA算法的步驟步驟1：確定控制參數(shù)及設(shè)置代表點(diǎn)由于算法有自我調(diào)整的能力，因而需要設(shè)置若干個(gè)控制用參數(shù)。需確定的控制參數(shù)為：

K：聚類期望數(shù)；

QN：一個(gè)聚類中的最少樣本數(shù)；

θs：標(biāo)準(zhǔn)偏差控制參數(shù)，用于控制分裂；

θc

：類間距離控制參數(shù)，用于控制合并；

L：每次迭代允許合并的最大聚類對(duì)數(shù)；

I：允許迭代的次數(shù)。

設(shè)初始聚類數(shù)為c及聚類中心mi,i=1,2,…,C。

2023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林141步驟2(分類)

對(duì)所有樣本，按給定的c個(gè)聚類中心，以最小距離進(jìn)行分類，即

若

步驟3(撤消類內(nèi)樣本數(shù)過(guò)小類別)

若有任何一個(gè)類，其樣本數(shù)，則舍去該類，令c＝c-1，將該類中原樣本分配至其它類；步驟4（重新計(jì)算均值向量）

2023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林142步驟5(計(jì)算類內(nèi)平均距離)

每類各樣本離開均值的平均距離

步驟6(計(jì)算整個(gè)樣本集偏離均值的平均距離)

j2023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林143步驟7(入口選擇)

如這是最后一次迭代(取決于I)，則轉(zhuǎn)步驟11，并設(shè)置θc=0，防止合并發(fā)生。

如果c<K/2，則轉(zhuǎn)向步驟8，執(zhí)行分裂步驟；

如果c≥2K或是偶數(shù)次迭代，則轉(zhuǎn)向步驟11，執(zhí)行合并步驟步驟8(求各類內(nèi)各分類標(biāo)準(zhǔn)偏差)

對(duì)每個(gè)聚類j，求其標(biāo)準(zhǔn)偏差

2023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林144步驟9(求每類具有最大標(biāo)準(zhǔn)偏差的分量)

步驟10(分裂計(jì)算步驟)

若對(duì)任一個(gè)有，并且有

(a)且，或有(b)C<k/2則把wj分裂成兩個(gè)聚類，其中心相應(yīng)為M+

j與M-

j

，把原來(lái)的Mj取消，且令c＝c+1，由于M+

j與M-

j設(shè)置不當(dāng)將會(huì)導(dǎo)致影響到其它類別，可按以下步驟計(jì)算：

2023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林145(a)給定一k值，0＜k＜1；

(b)令

(c)其中k值應(yīng)使wj中的樣本到M+

j與M-

j的距離不同，但又應(yīng)使wj中的樣本仍然在分裂后的新樣本類中。步驟11(計(jì)算類間聚類中心距離)

i類與j類的類間距離

2023/2/1哈爾濱工業(yè)大學(xué)電信院宿富林146步驟12(列出類間距離過(guò)近者)

比較Dij

與θc

并將小于θc

的Dij按上升次序排列

該隊(duì)列最大個(gè)數(shù)是控制合并對(duì)數(shù)的參數(shù)L步驟13(執(zhí)行合并)

從類間距離最小的兩類開始執(zhí)行合并過(guò)程，此時(shí)需將miL與miL合并，得

2023/2/1哈爾濱工業(yè)大學(xué)