第2章 模式識別的基本理論(3)

1§2.4特征的選擇與提取如何確定合適的特征空間是設計模式識別系統(tǒng)另一個十分重要，甚至更為關鍵的問題。如果所選用的特征空間能使同類物體分布具有緊致性，即各類樣本能分布在該特征空間中彼此分割開的區(qū)域內，這就為分類器設計成功提供良好的基礎。反之，如果不同類別的樣本在該特征空間中混雜在一起，再好的設計方法也無法提高分類器的準確性。這一節(jié)要討論的問題就是特征空間如何設計的問題2

如何構造一個特征空間，即對要識別的事物用什么方法進行描述、分析的問題？1、物理量的獲取與轉換(原始測量）這是指用什么樣的傳感器獲取電信號，如攝取景物則要用攝像機?？梢苑Q之為原始信息(原始測量，得到測量空間)。2、描述事物方法的選擇與設計(特征形成)

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

設計所要信息的形式是十分關鍵的。3、特征空間的優(yōu)化這個層次的工作發(fā)生在已有了特征的描述方法之后，也就是已有了一個初始的特征空間，如何對它進行改造與優(yōu)化的問題。對初始的特征空間進行優(yōu)化是為了降維。即初始的特征空間維數較高。能否改成一個維數較低的空間，稱為優(yōu)化，優(yōu)化后的特征空間應該更有利于后續(xù)的分類計算。特征空間的優(yōu)化的兩種方法特征選擇已有D維特征向量空間，Y={y1,y2,…,yD}，從原有的D維特征空間，刪去一些特征描述量，從而得到精簡后的特征空間。在這個特征空間中，樣本由d維的特征向量描述：X={x1,x2,…,xd}，d＜D。X只是Y的一個子集，每個分量xi必然能在原特征集中找到其對應的描述量xi＝y(tǒng)j。特征提取找到一個映射關系：A:Y→X，使新樣本特征描述維數比原維數降低。

其中X的每個分量xi是原特征向量Y各分量的函數，即：xi=fi(y1,y2,…,yD)

這兩種降維的基本方法是不同的。在實際應用中可將兩者結合起來使用，比如先進特征提取，然后再進一步選擇其中一部分，或反過來。

342.4.1特征空間優(yōu)化結果的評價準則：類別可分離性判據

對原特征空間優(yōu)化，就要對優(yōu)化結果進行評價實際的評價方法：對系統(tǒng)性能進行測試，測試指標主要有正確率、計算速度、存儲容量等。本節(jié)討論的評價方法：找出對特征空間進行優(yōu)化的具體算法。對特征空間進行優(yōu)化是一種計算過程，它的基本方法仍然是模式識別的典型方法：找到一種準則(或稱判據，通常用一種式子表示），以及一種優(yōu)化計算方法，使這種準則達到一個極值。理想的情況：判據與計算錯誤率有關，但直接反映錯誤率的是貝葉斯公式，在實際中運用有困難。采用其他判據：類別可分離性判據

5可分性判據應滿足的要求（1）與錯誤率有單調關系，這使判據取最大值時錯誤率也較?。?）當特征獨立時

有可加性：

（Jij是第i類與第j類的可分性準則）

（3）度量特性：（4）單調性：加入新的特征時，判據不減小6幾種常用的可分性判據以計算樣本在特征空間離散程度為基礎的準則，稱為基于距離的可分性判據（重點）基于概率密度分布的可分性判據（不講）?；陟睾瘮档目煞中耘袚ú恢v）

7基于距離的可分性判據基于距離的度量：是用來進行分類的重要依據。原理：同類物體在特征空間呈聚類狀態(tài)，即從總體上說同類物體內各樣本由于具有共性，因此類內樣本間距離應比跨類樣本間距離小。例如：Fisher準則（也可看成是特征提取方法）正是以使類間距離盡可能大同時又保持類內距離較小這一種原理為基礎的。同樣在特征選擇與特征提取中也使用類似的原理，這一類被稱為基于距離的可分性判據。

C類：各類之間的平均距離式中：

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

j)的距離，可用不同距離度量方法，如歐氏距離等。Pi,Pj：分別表示第ωi類和第ωj類的先驗概率ni,nj：分別表示第ωi類和第ωj類的樣本數目

1、用于可分性判據的距離8令：總的類間離散度矩陣）

（總的類間離散度矩陣）則可得判據的矩陣形式：tr：跡92、歐氏距離下的可分性判據

歐氏距離：各類均值：所有樣本集的總均值：則平均距離為：上述公式是有限樣本集，是均值及散度的估計。對于無限樣本：

10113、類內類間歐氏距離的其它判據判據Jd(X)是計算特征向量的總平均距離，以下一些判據則基于使類間離散度盡量大，類內離散度盡量小的考慮而提出。12基于距離的可分性判據優(yōu)缺點距離準則：是樣本在特征空間的分布的距離作為特征提取的依據。優(yōu)點：直觀，計算簡便。缺點：沒有考慮概率分布，因此當不同類樣本中有部分在特征空間中交迭分布時，簡單地按距離劃分，無法表明與錯誤概率之間的聯系。132.4.2特征提取1、按距離度量的特征提取方法

Fisher準則的延伸，這種判據的優(yōu)化體現出降維后的特征空間較好地體現類內密集、類間分離的要求。特征優(yōu)化過程是通過一個線性變換實現的：設在原特征空間一個樣本向量表示成X(D維)，在優(yōu)化特征空間中，樣本向量表示成Y(d維)，X與Y之間的關系是：

Y=WTX，W：D×d維矩陣（d<D）按距離度量的特征提取就是：利用基于距離的判據(J1~J5)找出一種線性變換W，使得判據J達到極值。

（1）J2判據下的特征提取算法設X空間的類內離散度矩陣和類間離散度矩陣分別為SW,Sb；

則按J2判據得到的特征提取矩陣W是按如下方式構造的：若矩陣SW-1Sb

的本征值λi按大小順序列為則選擇前最大的d個本征值所對應的本征向量組成的變換矩陣WD*d，可使判據J2(W)在W是D*d維下達到最大值。1415證明：因為：Y=WTX，

設：X的類內和類間離散度矩陣分別為SW,Sb則：Y的類內和類間離散度矩陣分別為SW’,Sb’為SW’=WSW’WT,Sb’=WSb’WT（見第3章中，Fisher準則一節(jié)）在使用J2判據下，將其Y的可分性判據表示成變換W的函數：J2(Y)=tr[(SW’)-1Sb’]則：J2(Y)=tr[(WSWWT)-1(WSbWT)]=J2(W)可以證明：在不降維條件下，即，設W是D*D維的，則J2判據不變J2(Y)=

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

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

1617上式表明D維特征空間中，J2判據的值是矩陣的全部本征值之和。令上式中WT=Ud=[u1，u2,….,ud]則則：如果矩陣的本征值按大小順序列為那么由對應于d個最大的本征值的本征向量所組成的矩陣W(D×d)，就能使所得到的d維特征滿足J2判據最大的要求。此結論對J4判據也適用18例：給定先驗概率相等的兩類，其均值向量分別為：協(xié)方差矩陣是：

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

19解：應先求，再求此矩陣的本征矩陣。混合均值類間離散度矩陣：類內離散度矩陣20求

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

中只有一個是獨立的，因此

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

利用W向量對原始的兩類兩維樣本進行線性變換得到新的一維分布，特征空間從二維降到一維，并滿足J2判據。該特征空間實質上就是對應于Fisher準則求得的線性分類器的法向量。如果討論的是多類別C問題，則優(yōu)化后的維數至多為類別數減一(C-1)。21(2)J5判據下的特征提取由于和是對稱矩陣，因此，存在矩陣U使得：則：2223即：是的本征值矩陣或（兩邊同乘U）因此：由：可見，取使J5達最大的d個本征值對應的本征向量組成的W，可將X降到d維。24J5的另一種形式又設的本征值矩陣是則：取使J5達最大的d個本征值對應的本征向量組成的W，可將X降到d維。25§2.4.3特征選擇

特征選擇在概念上十分簡單，即對原有特征進行刪選優(yōu)化。通常，人們認為：只要逐個分析每個特征，判斷它對分類的價值，然后根據其優(yōu)值刪去或保留，這是一個為人們常采用方法，但是這種方法并不能保證特征空間的最優(yōu)組合優(yōu)化，因此本節(jié)討論了一些原理上更好的方法。26兩個問題一：選擇特征的標準：也就是選擇前面討論過的可分離性判據，以這些判據為準則，使所選擇的d維子空間具有最大的可分離性。二：是要找出較好的特征選擇方法，以在允許的時間內選擇出一組最優(yōu)的特征。所謂最優(yōu)的特征組，就是要找到合適的特征的組合。如果從逐個特征配組進行性能比較的話，即窮舉的算法，特征配組的數量可能極大，組合配置的數目按下式計算

27如果D＝100，d＝10，則q的數量級就是1013，即使D＝20，d＝10，則q也可達184756種。如果將所有可能的特征配組列舉出來，按某選定的可分離性判據進行計算，從中擇優(yōu)，其計算量之大是可想而知的。任何非窮舉的算法都不能確保所得結果是最優(yōu)的，因此要得最優(yōu)解，就必需采用窮舉法，只是在搜索技術上采用一些技巧，使計算量有可能降低。28“自上而下”與“自下而上”“自上而下”是指，從D維特征開始，逐步將其中某些特征刪除，直到剩下所要求的d維特征為止。而“自下而上”則是從零維特征空間開始，逐個地從D維持征中選擇特征，直至達到預定的維數指標為止。在選擇的過程中，“自上而下”算法做到篩選剩下的特征組在每一步上都是最優(yōu)的，而“自下而上”則在每一步都生成最優(yōu)的特征空間。

29

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

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

則有J(?i)≤J(?j)稱該判據具有單調性分支定界算法（略）302次優(yōu)搜索法

分支定界算法雖然比盲目窮舉法節(jié)省計算量，但計算量仍可能很大而無法實現，因此還是常用次優(yōu)搜索法。（1）

單獨最優(yōu)特征組合

是一種最簡單的方法，即將各特征按單獨使用計算其判據值，然后取其前d個判據值最大的特征作為最優(yōu)特征組合。J(x1)>J(x2)>J(x3)>…J(xd)>…J(xD)問題：即使各特征是獨立統(tǒng)計的，也不一定得到最優(yōu)結果。但如果：J(X)=∑J(xi)或J(X)=∏J(xi)

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

31（2）

順序前進法

(SequentialForwardSelection----SFS)

是最簡單的自下而上搜索方法。具體過程如下：首先計算每個特征單獨進行分類的判據值，并選擇其中判據值最大的特性，作為入選特征。然后每次從未入選的特征中選擇一個特征，使得它與已入選的特征組合在一起時所得的J值為最大，直到特征數增至d個為止。與單獨特征最優(yōu)化組合相比：考慮了特征之間的相關性，在選擇特征時計算并比較了組合特征的判據值，要比前者好些。主要缺點：一旦某一特征被選入，即使由于后加入的特征使它變?yōu)槎嘤?，也無法再把它剔除。推廣：每次入選r個特征，而不是一個，稱為廣義順序前進法(GeneralizedSequentialForwardSelection---GSFS)。與SFS相比，該法在每次入選r個特征時，考慮了他們之間的相關性。缺點是計算量大大增加.CD-kr。32（3）

順序后退法

(SequentialBackwardSelection----SBS)

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

33（4）

增L減r法(L-r法)

SFS(GSFS)、SBS(GSBS)的缺點：即一旦特征入選(或剔除)，過程不可逆轉。解決辦法：采用將這兩種方法結合起來的方法，即增l減r法。L-r法原理：是對特征組在增加l個特征后，轉入一個局部回溯過程，又用順序后退法，剔除掉r個特征。這種方法既可能是“自上而下”方法，也可能是“自下而上”的，這取決于L與r的數據大小。當L>r時，入選特征數逐漸增加，屬“自下而上”型，反之屬“自上而下”型。

L-r法1）用SFS法在未入選特征中逐個入選L個特征2）用SBS法在已入選特征中逐個剔除r個特征。3）若特征數是d，則終止算法。否則，轉入（1）L>r時，是自下而上的算法，先執(zhí)行第1步，起始時，入選特征是空集ΦL<r時，是自上而下的算法，先執(zhí)行第2步，起始時，入選特征是原有特征集X={x1,x2,….,XD}3435（ZL,Zr）法此法也可推廣至用GSFS及GSBS代替SFS及SBS，并可在實現增加L特征時采用分幾步實現。(ZL,Zr)法：增L個特征用ZL步，每步可入選Li(i=1,2,…,ZL)個特征。ZL=（L1,L2,L3,……,LZL）；減r則用Zr步，每步可剔除ri(i=1,2,…,Zr)個特征。Zr=（r1,r2,r3,……,rZr）這種做法是為了既考慮入選(或剔除)特征之間的相關性，又不至因此引起計算量過大。合理地設置ZL與Zr，可以同時對兩者，即計算復雜性及特征選擇的合理性兼顧考慮。36前面的各種方法可看作是（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）372.4.4基于Karhunen-Loeve變換

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

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

381傅立葉級數展開周期平穩(wěn)隨機過程x(t)的Fourier展開則：周期平穩(wěn)過程的Fourier系數互不相關392K-L展開（1）連續(xù)情況：將一個非周期隨機過程x(t)在區(qū)間[a,b]展開為其中：40（2）離散情況用正交向量uj（X在D維空間K-L變換坐標系）表示D維向量X:X在K-L坐標系uj上的展開系數稱作X的K-L變換：其中：式中：41（3）K-L展開式的性質K-L變換的展開系數是互相無關的這表明經過K-L變換后，原向量各分量Ci之間存在的相關性已被消除。423、

使用K-L變換進行特征提取1）K-L坐標系的產生矩陣：產生K-L變換的K-L坐標系的矩陣Ψ稱為K-L坐標系的產生矩陣。如Ψ=E[XXT]實際上使用不同的向量作為產生矩陣，會得到不同的K-L坐標系，從而滿足不同的分類要求。一般，沒有類別標簽的樣本集的均值向量u常常沒有意義，因此，可用樣本數據的協(xié)方差矩陣

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

432）對分類問題，如何形成產生矩陣?當樣本集中個樣本的類別標簽已知時，可以得到不同的Σ，Σ有多個（不同類可有不同的Σ）,如何形成產生矩陣?設各類別先驗概率為Pi

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

可以用總的類內離散矩陣SW=ΣPi

Σi作為產生矩陣，其效果相當于只按類內離散程度進行特征選取。如果只以某一類樣本集的協(xié)方差矩陣Σi作為產生矩陣，則效果是對該類樣本集有信息壓縮的最優(yōu)性。443）

利用類均值向量提取特征類條件均值ui包含大量的分類信息。為了降低維數，且盡可能地保持原有特征的分類信息，應選擇一種變換，是變換后的類條件均值向量的各分量比其他的變換保持更多的分類信息?；跉W氏距離特征提?。号袚菑氖诡悆缺M可能密集，類間盡可能分開的思想出發(fā)的。各類均值向量各分量的分類性能，不僅與取決于各均值向量各分量之間的距離，而且，還和其方差以及各分量的相關程度有關。如何在K-L變換方法中體現對這兩者的兼顧?具體算法1）按Sw=ΣPi

Σi作為產生矩陣產生相應的K-L坐標系統(tǒng)uj

（把包含在原向量中各分量的相關性消除）2）計算在新坐標系中各分量uj上的離散度。類內離散度其內間離散度3）計算樣本在各分量上的可分性：

（越大，表明該坐標可分性越好）4）將各分量按大小重新排列：J(X1)≥J(X2)≥….≥J(XD)

取前d個最大的J(Xi)值對應的本征向量uj構成變換矩陣：W=[u1,u2,…,ud]，則W可將原特征向量X降為d維特征向量：Y=WTX4546類內離散度：在ui軸上，原第i類特征向量Xik投影為：Xjkj=ujTXik，其類內離散度：新坐標系中各分量uj上的離散度計算47類間離散度：48

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

類協(xié)方差矩陣分別是：把維數從2壓縮為149解1）將SW作K-L變換的產生矩陣，求其本征矩陣得K-L變換的變換矩陣?？汕蟮帽菊髦稻仃嚭捅菊飨蛄糠謩e是：50又2）求得：3）514）包含在類平均向量中判別信息的最優(yōu)壓縮上面方法（利用類均值向量提取特征）為了兼顧類內離散度與類間離散度，包含在類均值向量內的分類信息并沒有全部利用。即：類平均向量的判別信息在K-L坐標系的各個分量中都有反映，并沒有得到最優(yōu)壓縮。

如圖，如僅從類均值向量所包含的分類判別信息全部被利用出發(fā)，應選擇包含兩均值向量連線方向在內的坐標系。但是簡單地從類均值向量來確定特征子空間，雖然實現很容易，但一般不能滿足各分量間互不相關的要求。52例外情況：如果類內離散度矩陣Sw是一個單位矩陣，即它在特征空間中以超球體分布，從類均值向量來確定特征子空間就可做到既保持各分量的不相關性，同時又能充分利用包含在類均值向量內的差別信息。從這種特殊情況得到啟發(fā)，一種充分利用類均值向量所包含的判別信息的方法因此而產生。具體說來這種方法分成兩步：1）白化處理2）特征提取53第一步：白化處理1、先用原坐標系中Sw作為產生矩陣，實行K-L變換，將原有數據的相關性消除掉。(

Y1=UTX)所得到的K-L坐標系中的S’w=Λ是一個對角矩陣，其相應的K-L坐標系為U，由原Sw本征值對應的本征向量組成。

即：

UTSw=ΛU，或UTSwU=Λ2、進一步實行變換：Y2=Λ-1/2Y1，使S’w矩陣變?yōu)閱挝痪仃嚕害?1/2UTSwUΛ-1/2=Λ-1/2ΛΛ-1/2=I即(UΛ-1/2)

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

此時，Y2=Λ-1/2Y1=Λ-1/2UTX=(UΛ-1/2)TX=BTX經過B變換后的類間離散度矩陣S’b應有：S’b=BTSbB54第二步:特征提取1）采用上節(jié)方法求最佳的變換。因S’W

=I則，Λ=I而且，U可以是任何正交矩陣。即UTIU=UTU=I則判據：由于U可以上任何正交矩陣，因此，可以以S’b作為產生矩陣，作第二次K-L變換，得到正交矩陣VTSb’=Λ’V則判據因此，按判據最大選擇uj，就是按Sb’正交分解的本征值λ’j最大選擇。由于S’b的秩最多是c-1，所以最多只有c-1個非零本征值。選擇最大的d（≤c-1）個非零本征值，則該d個非零本征值就可表示類均值向量所包含的全部信息。設這d個本征向量系統(tǒng)用V’表示，即

V’=[v1,v2,….,vd]（d≤c-1）則變換為:Y=V’TY22）將第一步得到的結果代入，整個變換為：Y=VTY2=VTBTX=(BV)TX=WTX因此變換矩陣為：W=BV=UΛ-1/2V55具體算法1）先用原坐標系中Sw作為產生矩陣：UTSwU=Λ2）令:B=UΛ-1/23）計算經過B變換后的類間離散度矩陣S’b：S’b=BTSbB4）以S’b作為產生矩陣，作第二次K-L變換VTSb’=Λ’V5）選擇最大d個本征值對應的d（≤c-1）個本征向量

V’=[v1,v2,….,vd]6）計算最終的變換矩陣：W=BV’=UΛ-1/2V’（前3步是白化過程）56572024/1/23哈爾濱工業(yè)大學電信院宿富林57

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

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

類協(xié)方差矩陣分別是：58解：59下圖給出了兩次變換步驟

以及變換對數據產生的作用由圖中看出，樣本原為橢圓形分布，經白化處理后轉化為圓形分布，此時S’w為單位矩陣。均值向量也隨之變化，最后得到的均值向量作為降維后的一維坐標。這種方法主要用在類別數C比原特征向量的維數D小得多的情況，由于Sb的秩最多為C-1，因此可使特征維數降至C維以下。60§2.5非監(jiān)督學習法以前討論的分類器設計方法都是在樣本集中的類別標簽已知的條件下進行的，這些樣本稱為訓練樣本。在樣本類別標簽已知的情況下，可以統(tǒng)計出各類訓練樣本不同的描述量，如其概率分布，或在特征空間分布的區(qū)域等，利用這些參數進行分類器設計，稱為有監(jiān)督的學習方法。然而在實際應用中，不少情況下無法預先知道樣本的標簽，也就是說沒有訓練樣本，因而只能從沒有樣本標簽的樣本集進行分類器設計，這就是非監(jiān)督學習方法。61一幅道路圖像按路面與非路面分類其中左圖是在圖像中路面區(qū)與非路面中各找一個窗口，將其中每個象素分別作為這兩類的訓練樣本集，用這兩個樣本集在特征空間的分布參數進行設計（有監(jiān)督的學習）。右圖，無法預先選擇不同類別的樣本集，而是將整幅圖的像素都作為待分類樣本集，通過它們在特征空間中表現出來的聚類現象，把不同類別劃分開。（非監(jiān)督學習）62有監(jiān)督學習中，樣本集分布呈現交迭情況，而無監(jiān)督學習方法由于沒有類別樣本指導，無法確定它們的交迭情況，只能按分布的聚類情況進行劃分。在類似于該例的實際應用問題中，預先選定不同類別的樣本往往不可能，如時間不允許，或無法用人工干予等因素。

另外在某些有監(jiān)督學習方法中，也往往需要利用聚類方法將樣本按其分布劃分成若干子類等。聚類方法就是無監(jiān)督學習方法的一個內容，它是經常應用的一門技術。非監(jiān)督學習方法要解決的問題：觀察事物與分析事物，從中尋找其規(guī)律性，這就是非監(jiān)督學習方法要解決的問題。63非監(jiān)督學習與有監(jiān)督學習的不同點1．有監(jiān)督學習方法必須要有訓練集與測試樣本。在訓練集中找規(guī)律，而對測試樣本使用這種規(guī)律；而非監(jiān)督學習沒有訓練集，只有一組數據，在該組數據集內尋找規(guī)律。

2．有監(jiān)督學習方法的目的就是識別事物。

識別的結果表現在給待識別數據加上了標號，因此訓練樣本集必須由帶標號的樣本組成。非監(jiān)督學習方法的目的是尋找數據集中的規(guī)律性。不一定要達到劃分數據集的目的，也就是說不一定要“分類”。

只有要分析的數據集本身，預先沒有什么標號。如果發(fā)現數據集呈現某種聚集性，則可按自然的聚集性分類，但不以與某種預先的分類標號對上號為目的。64非監(jiān)督學習分類非監(jiān)督學習方法可以分成兩大類基于概率密度函數估計的直接方法：指設法找到各類別在特征空間的分布參數再進行分類。包括單峰子類的分離方法等?；跇颖鹃g相似性度量的間接聚類方法：其原理是設法定出不同類別的核心或初始類核，然后依據樣本與這些核心之間的相似性度量將樣本聚集成不同類別。如：K均值聚類，ISODATA法、分級聚類等65§2.5.1單峰子類的分離方法

樣本概率密度分布在特征空間的分布是多峰的。每個單峰區(qū)域則被看作不同的決策域。落在同一單峰區(qū)域的待分類樣本就被劃分成同一類，稱為單峰子類。該類算法也很多，典型的有：投影法投影法高維空間尋找概率密度的“峰”是困難的,一維空間尋找概率密度的“峰”較容易。將高維空間樣本投影到不同的一維空間ui上，xi=uiTY；在此一維空間上估計邊緣概率密度p(xi)在此概率密度上尋找各個峰，并確定每個峰的范圍（即每個聚類），各個聚類的分解面與該坐標軸ui垂直，交點則是兩個峰值之間的最小點。投影法的主要問題：一：如何設計合適的坐標系統(tǒng)（即投影方向）二、如何設計直方圖（計算邊緣概率密度）66直方圖和坐標系統(tǒng)設計一、設計直方圖1）將數據xi(k)=uiTY(k)按大小排列2）確定直方圖上的單位間隔長度L3）根據L將數據xi(k)分成不同區(qū)間，統(tǒng)計；落在每個區(qū)間內的樣本數：K。

則pi(k)=K/NN:總的樣本數二、設計合適的坐標系統(tǒng)目前還沒有合適的準則用于確定坐標系。一種啟發(fā)式的辦法是使待分類的樣本在某個坐標軸方向具有最大的分散性，可以采用K-L變換方法。具體算法：用混合樣本協(xié)方差矩陣作為K-L變換的產生矩陣，找到其本征值，并按大小排序。對此混合樣本來說，對應最大本征值的本征向量，離散程度最大，預期能發(fā)現明顯的峰值?？勺鳛樽鴺讼到y(tǒng)但是，即使在這些方向的投影，并不能保證分出各個聚類。6768可以分出各個聚類不能分出各個聚類69投影法的具體算法步驟1：計算樣本協(xié)方差矩陣具有最大本征值的本征向量Uj，把數據投影到Uj軸上。步驟2：用直方圖方法求數據的邊緣概率密度函數。步驟3：在直方圖的峰值間求最小值，在這些最小點作垂直于Uj的超平面把數據劃分為若干個聚類。步驟4：如果在這個軸上沒有這樣的最小值，則用下一個最大本征值對應的本征向量重復以上過程。步驟5：對每個得到的子集(聚類)重復上述過程，直到每個集不能再分(為單峰)為止。702.5.2類別分離的間接方法

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

如何聚類取決于聚類準則，以使某種聚類準則達到極值為最佳。兩類對數據集進行聚類的方法：迭代的動態(tài)聚類算法非迭代的分級聚類算法712.5.2.1動態(tài)聚類方法

動態(tài)聚類方法的任務是將數據集劃分成一定數量的子集，子集數目在理想情況現能體現數據集比較合理的劃分。問題:

（1）怎樣才能知道該數據集應該劃分的子集數目

（2）如果劃分數目已定，則又如何找到最佳劃分

由于優(yōu)化過程是從不甚合理的劃分到“最佳”劃分，是一個動態(tài)的過程，故這種方法稱為動態(tài)聚類方法。主要方法：K均值算法ISODATA算法72動態(tài)聚類方法3個要點（1）選定某種距離度量作為樣本間的相似性度量；

（2）確定樣本合理的初始分類，包括代表點的選擇，初始分類的方法選擇等。（3）確定某種評價聚類結果質量的準則函數，用以調整初始分類直至達到該準則函數的極值。

731、K-均值算法

也叫C-均值算法（1）準則函數—誤差平方和準則這個準則函數是以計算各類樣本到其所屬類均值點誤差平方和為準則。若各類均值表示成

誤差平方和準則可表示成

最佳的聚類是使Jc為最小的分類。這種類型的聚類通常稱為最小方差劃分。74（2）樣本集初始劃分初始劃分的一般作法是先選擇一些代表點作為聚類的核心把其余的樣本按某種方法分到各類中去

75代表點的幾種選擇方法(a)憑經驗選擇代表點。根據問題的性質，用經驗的辦法確定類別數，從數據中找出從直觀上看來是比較合適的代表點。(b)將全部數據隨機地分為C類計算各類重心，將這些重心作為每類的代表點。（c）用前C個樣本作為代表點

76(d)“密度”法選擇代表點?！懊芏取保簩γ總€樣本確定大小相等的鄰域（如同樣半徑的超球體），統(tǒng)計落在其鄰域的樣本數，稱為該點“密度”。確定一個距離d選“密度”為最大的樣本點作為第一個代表點；然后，找次高“密度”的樣本點作為第二個代表點；第2個代表點離第1個代表點的距離需大于d。依次選擇其它代表點。其離選定的代表點的距離應大于d。使用這種方法的目的是避免代表點過分集中在一起。

77(e)從c-1個聚類劃分問題的解中產生C聚類劃分問題的代表點首先，將所有樣本集看作一個聚類，計算其總均值，然后找與該均值相距最遠的點，由該點及原均值點構成2聚類的代表點。其次，依同樣方法，對已有(c-1)個聚類代表點(由(c-1)個類均值點組成)找一樣本點，使該樣本點距所有這些均值點的最小距離為最大，這樣就得到了第c個代表點。代表點的選擇會影響迭代結果。因為迭代得到的結果往往是局部最優(yōu)而非全局最優(yōu)。78初始分類方法(a)對選定的代表點按距離最近的原則將樣本劃屬各代表點代表的類別。(b)在選擇樣本的點集后，將樣本按順序劃歸距離最近的代表點所屬類，并立即修改代表點參數，用樣本歸入后的重心代替原代表點。因此代表點在初始劃分過程中作了修改。

79(c)一種既選擇代表點又同時確定初始分類的方法規(guī)定一閾值d，選w1={y1}計算樣本y2與y1的距離D(y2,y1)，如其小于d，則y2歸入w1；否則建立新的類別w2={y2}。當輪到樣本yj時，已有了K類即，而每類第一個入類樣本分別為y1,y2,…,yk（作為每類的代表點），則計算D(yi,yj),i=1,2,…,k；若有D(yi,yj)>d（對所有的i，i＝1,…，k），則建立新類。否則將yj歸入與y1,y2,…,yk距離最近的類別中。重復上一步，直至所有樣本分類

80(d)標準化特征求和量化方法：i)先將數據標準化ii)若yij

表示標準化后第i個樣本的第j個特征量，令：iii)求出SUM(i)的最大值與最小值

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

v)如所得結果非整數，則找到其最近整數K，將第i個樣本歸入第K類

81（3）迭代計算K-均值算法的迭代計算過程在原理上與梯度下降法是一樣的，即以使準則函數值下降為準則。但是由于K-均值算法的準則函數值由數據劃分的調整所決定，因此只能通過逐個數據從某個子集轉移到另一子集計算準則函數值是否降低為準則。

82對劃分的修改規(guī)則如果原屬Гk

中的一個樣本y從Гk

移入Гj

時，則新的Гk類和樣本y新加盟的Гj

集合均值分別為：

由于y的移動只影響到k與j這兩類的參數改動，因此，計算Jc值的變動只要計算相應兩類誤差平方和的變動即可，此時

總誤差變化：如果:則：

即：將樣本y從Гk

移入至Гj

就會使誤差平方總和Jc減小，它表明樣本變動是合乎準則要求的83算法

選擇某種方法把樣本分成C個聚類的初始劃分，計算每個聚類的均值m1,…,mc和Jc。

選擇一個備選樣本y，設其在ωi中。

若Ni=1，則轉②(樣本只有1個，不移出)；否則繼續(xù)下一步。

計算

對于所有的j，若ek≤ej（表明ek<ei）則將y從ωi移到ωk中（否則，ei<ej,不用移）

重新計算mi和mk，并修改Jc。

若連續(xù)迭代N次(即所有樣本都運算過)Jc不變，則停止，否則轉到②。

84（4）確定類別數的實驗方法上述K—均值算法都是在類別c已知條件下進行的。在類別數未知情況下，可以假設類別數是逐步增加的，準則函數隨c的增加而單調地減小?？蛇x擇平緩時轉折處的C值。852、ISODATA算法

K—均值算法：

優(yōu)點：比較簡單

缺點：自我調整能力也比較差。這主要表現在類別數不能改變，受代表點初始選擇的影響也比較大。ISODATA算法：全稱‘迭代自組織數據分析技術’（IterativeSelf-OrganizingDataAnalysisTechniqueAlgorithm）。ISODATA算法與K—均值算法相比的改進:

1.不是每調整一個樣本的類別就重新計算一次各類均值（逐個樣本修正），而是每次把全部樣本都調整完畢后再重新計算樣本均值（成批樣本修正）。2.考慮了類別的合并與分裂，因而有了自我調整類別數的能力。從而可以得到較為合理的類別數。862.5.2.1分級聚類方法分級聚類方法的目的并不把N個樣本分成某一個預定的類別數C，而是把樣本集按不同的相似程度要求分成不同類別的聚類。最極端的情況:(1)每個樣本各自為一類.相似性最大

(2)將所有樣本歸一類。相似性最小在這兩個極端之間的是：類別數從N逐漸減少，每類的數量相應增加，而類內樣本的相似程度也隨之下降。分級聚類的兩種途徑分級聚類可通過兩種途徑實現：合并、分裂合并：開始時，每個樣本自成一類，然后通過合并類別減少類分裂：開始時，所有樣本是一類，然后通過分裂類別樣本增加類合并方法較簡單，后續(xù)重點介紹87基于合并的分級聚類1）第一次劃分（稱為1水平），每個樣本各自為一類，N個樣本，共N類；總的相似性最大2）第2次劃分（稱為2水平），按類別相似