1、模式識別-總結(jié) Pattern Recognition,余莉 電話： 73478（O）,75420（H）E-mail：,課程內(nèi)容,第一章 引論 (2學(xué)時) 第二章 聚類分析 (4學(xué)時) 第三章 判別域代數(shù)界面方程法 (4學(xué)時) 第四章 統(tǒng)計判決與估計(4學(xué)時) 第五章 統(tǒng)計學(xué)習(xí)與估計(4學(xué)時) 第六章 最近鄰方法 (2學(xué)時) 第七章 特征提取與選擇(2學(xué)時) 復(fù)習(xí) (2學(xué)時) 實驗 上機實驗 (8學(xué)時) 作業(yè) 每次課后布置習(xí)題 考核 筆試(70%)+實驗(20%)+作業(yè)(10%),概 念,模式識別：確定一個樣本的類別屬性（模式類）的過程，即把某一樣本歸屬于多個類型中的某個類型。模式分類的過程。

2、 樣本（Sample)：一個具體的研究（客觀）對象。如患者，某人寫的一個漢字，一幅圖片等。 模式（Pattern）：對客體（研究對象）特征的描述（定量的或結(jié)構(gòu)的描述），是取自客觀世界的某一樣本的測量值的集合（或綜合）。 特征（Features）：能描述模式特性的量（測量值）。在統(tǒng)計模式識別方法中，通常用一個矢量表示，稱之為特征矢量，記為 模式類（Class）：具有某些共同特性的模式的集合。,1.1.3 模式識別系統(tǒng),圖1.2 模式識別系統(tǒng)框圖,判決過程,學(xué)習(xí)過程,分類器訓(xùn)練,分類器,特征提取選擇,預(yù)處理,模式采集,1.1.4 模式識別方法,統(tǒng)計判決 句法結(jié)構(gòu) 模糊判決 邏輯推理 神經(jīng)網(wǎng)絡(luò),第二

3、章 聚類分析,內(nèi)容： 聚類的基本概念； 相似性測度、類間距離 、聚類準(zhǔn)則； 簡單聚類、層次聚類 ； 動態(tài)聚類。 要求： 重點:相似性測度、K均值聚類和層次聚類算法。 難點:聚類準(zhǔn)則函數(shù)。,小結(jié),一、影響分類的因數(shù) （1）分類準(zhǔn)則；（2）特征量的選擇；（3）量綱。 二、模式相似性測度 （一） 距 離 測 度 (1) 歐氏距離 (2) 馬氏距離 對坐標(biāo)系平移、旋轉(zhuǎn)、比例不變。 （二） 相 似 測 度 相關(guān)系數(shù) （特征矢量的方向） 對坐標(biāo)系平移、旋轉(zhuǎn)、比例不變。,三、類間距離遞推公式,（其中l(wèi) =p q ）,四、 聚類準(zhǔn)則函數(shù),評估分類過程或分類結(jié)果優(yōu)劣的準(zhǔn)則函數(shù) （一）類內(nèi)距離準(zhǔn)則（誤差平方和準(zhǔn)則

4、）,式中，nj是j中的樣本個數(shù)，,適用于各類模式呈團(tuán)狀分布的情況。,四、聚類準(zhǔn)則函數(shù),（二）類間距離準(zhǔn)則,式中， 是總的樣本均值矢量，,加權(quán)類間距離準(zhǔn)則,對于兩類問題 ，可以定義,（三）基于類內(nèi)類間距離的準(zhǔn)則函數(shù),構(gòu)造能同時使Jwmin和JBmax的準(zhǔn)則函數(shù) 類內(nèi)離差矩陣（Scatter Matrix）,總的類內(nèi)離差矩陣,總的離差矩陣,類間離差矩陣,（三）基于類內(nèi)類間距離的準(zhǔn)則函數(shù),聚類的基本目標(biāo)是使 JWB=TrSBmax和JWW =TrSWmin 因此可定義如下聚類準(zhǔn)則函數(shù),Jimax，(i=1,2,3,4) 即，類內(nèi)越“緊”，類間越“開”，聚類效果越好。,2.3 聚類算法,（一）簡單聚類

5、 最鄰近規(guī)則試探法給定閥值T，聚類到zl （二）層次聚類初始每個樣本點為一類（N類），將類間距離最小者合并為一類，逐級進(jìn)行。類間距離可用：最小、最大、中間、重心、平均距離等。,（三）動態(tài)聚類算法,C-均值算法（適用于團(tuán)狀分布的情況）重新聚類 ISODATA算法c（預(yù)期類數(shù)），Nc（初始類心個數(shù)），N（各類最小樣本數(shù)）， s（類中樣本特征分量標(biāo)準(zhǔn)差上限）， jmax， D（聚合中心最小間距），L，I,C-均值算法性能,算法簡單，收斂。如模式呈現(xiàn)類內(nèi)團(tuán)狀分布，效果很好，故應(yīng)用較多。 能使各模式到其所判屬類別中心距離平方之和為最小。,第三章 類域界面方程法 總結(jié),分類特征空間的分劃子空間的界面：判別

6、函數(shù) 求解 32 線性判別函數(shù) 式中 ,稱為權(quán)矢量或系數(shù)矢量。寫成矢量形式 這里， ， ，稱為增廣特征矢量和增廣權(quán)矢量。增廣特征矢量的全體稱為增廣特征空間。,判別規(guī)則：,解多類問題的兩分法: 兩分法 有不確定區(qū)域 兩分法 沒有不確定區(qū)的 兩分法 令,33 判別函數(shù)值的鑒別意義、權(quán)空間及解空間,（1）系數(shù)矢量 是超平面 的法矢量； （2） 的絕對值 正比于 到超平面的距離； （3） 的正（負(fù)）反映 在超平面 的正（負(fù)）側(cè)。,34 Fisher線性判別,多維 Fisher變換 利于分類的一維 （1）Fisher準(zhǔn)則函數(shù) 對兩類問題 作變換，n維矢量 在矢量 方向軸上的投影 Fisher準(zhǔn)則函數(shù),（

7、2）Fisher變換,對于兩類問題, 它所對應(yīng)的本征矢量 稱為Fisher最佳鑒別矢量。 Fisher變換函數(shù) ： （3）Fisher判別規(guī)則,3.5 一次準(zhǔn)則函數(shù)及梯度下降法,如果訓(xùn)練模式已經(jīng)符號規(guī)范化，即 已乘以1（包括增廣分量1），則,收斂定理 解多類問題,36 二次準(zhǔn)則函數(shù)及其算法,式中 是 矩陣。,將上面的不等式組寫成矩陣方程形式，并引入N 維余量矢量 ，于是不等式方程組變?yōu)?最小方差準(zhǔn)則及W-H算法 針對方程組 ,構(gòu)造方差準(zhǔn)則函數(shù) 對于 ,此時的 , 而對于 ,此時的 。如果方程組有唯一解,說 明訓(xùn)練模式集是線性可分的,如果方程組無解,極小點值是最小二乘解。一般情況下使 極小等價于

8、誤分模式數(shù)目最少。, 偽逆法 求 對 的梯度并令其為零，有 可得 (3-6-12) 當(dāng)(X X)-1存在時， X +=(X X)-1X 稱為X的偽逆(也稱廣義逆或M-P逆)， 稱為 的偽逆解。 X X是(n+1)(n+1)矩陣，一般是非奇異的。 當(dāng)(X X)-1不存在時，可用廣義逆法解 這里(X X)+為X X的廣義逆矩陣。,求解最佳權(quán)矢量的方法：, 梯度法,由前述知， 的梯度為,梯度下降算法迭代公式為,Step1. 任取 Step2.,(3-6-13),可以證明，當(dāng) 為任意正的常數(shù)，則該算法使權(quán)矢量序列 收斂于 ; 滿足 ， 也稱為MSE解。,Step1. 任取 Step2. 此算法通常稱為

9、WH(WidrowHoff)算法,仿前采用單樣本修正法，則式(3-6-13)可以修改為,為了減少計算量和存儲量，由于,(3-6-14),312 勢函數(shù)分類法,概念：1：q+； 2 ：q- 定義點 處的位勢函數(shù) ，它應(yīng)滿足： ； 是連續(xù)光滑函數(shù)； 是 與 間距離的單值單調(diào)下降函數(shù);當(dāng)且僅當(dāng) 時，達(dá)其最大值;,第一類位勢函數(shù) 設(shè) 是 定義域中的完備正交函數(shù)集，位勢函數(shù)取為 第二類位勢函數(shù)取關(guān)于 和 的距離的對稱函數(shù)作位勢函數(shù)，例如,兩類位勢函數(shù),第四章統(tǒng)計判決 總結(jié),概念: 后驗概率： 類概密： 先驗概率：,41最小誤判概率準(zhǔn)則判決,總的誤判概率,多類問題，最小誤判概率準(zhǔn)則有如下幾種等價的判決規(guī)則

10、,(1),(2),(3),(4),42 最小損失準(zhǔn)則判決,對一個實屬i 類的模式采用了決策j 所造成損失記為損失函數(shù) 條件平均損失 （總的）平均損失 定理：使條件平均損失最小的判決也必然使總的平均損失最小。 最小損失準(zhǔn)則判決： 兩類問題,含拒判決策的最小損失判決規(guī)則為,如果 ，則對 拒判； 如果 ，則判 。 當(dāng) 即 時，不存在拒判。,對于兩類問題，存在拒判決策的條件是,判決規(guī)則： 如果 ，則判 ； 如果 ，則判 ； 如果 ，則對 拒判。,適用于P(i)未知或是變動的情況。 當(dāng)類概密已知，損失函數(shù)ij、類域i取定后，平均損失R是P(i)的線性函數(shù) 方法：按最小損失準(zhǔn)則，對P(i)(0,1)，計算

11、RP(i)曲線，找出使R取最大值的P*(i) ，然后最小損失準(zhǔn)則對具體的模式分類識別。最小最大損失判決規(guī)則為,43 最小最大損失準(zhǔn)則,44 N-P(NeymanPearson)判決,由 確定判決似然比門限,第五章 統(tǒng)計估計 概述,本章目的： 已知類別的樣本（訓(xùn)練樣本）學(xué)習(xí)或訓(xùn)練類概密,51 統(tǒng)計推斷概述,參數(shù)估計 如果已知i類的概密 的函數(shù)類型，但不知道其中的參數(shù)或參數(shù)集可采用參數(shù)估計確定未知參數(shù) (1)將參數(shù)作為非隨機量處理，如矩法估計、最大似然估計； (2)將參數(shù)作為隨機變量，如貝葉斯估計。 非參數(shù)估計當(dāng)不知道類的概型時，可采用非參數(shù)估計方法，也稱為總體推斷，這類方法有 (1) p-窗法；

12、 (2) 有限項正交函數(shù)級數(shù)逼近法。,設(shè)模式 ,i類總體 概密為,5.2.1 均值矢量和協(xié)方差陣的矩法估計,總體 的均矢 的無偏估計為,的無偏估計為,若用 近似 ,則,5.2.2 最大似然估計(Maximum Likelihood Estimate),似然函數(shù)稱為相對于 的 的似然函數(shù)。如果各個 是獨立抽取的，則有 最大似然估計 取 的 作為未知參數(shù)集的估計值。 根據(jù)已知樣本X(N)和下列似然方程組或?qū)?shù)似然方程組,可得,5.2.3貝葉斯估計,（1）確定未知參數(shù)集 的先驗概密 ； （2）由樣本集X(N) 求這里類 的概型是已知的； （3）計算 （4）計算,(5-2-17),(5-2-19),(5-2-16),53 貝葉斯學(xué)習(xí),貝葉斯學(xué)習(xí)與貝葉斯估計前提條件是相同的，不同的是，貝葉斯學(xué)習(xí)不是進(jìn)行概密的參數(shù)估計，而是進(jìn)行總體概密的估計以獲得 。 在前一節(jié)貝葉斯估計的四個步驟中，貝葉斯學(xué)習(xí)在執(zhí)行完了前三個步驟得到未知參數(shù)的 后驗概密 之后不是去求 ，而是直接求總體的后驗概密 。,第七章 特征提取與選擇,類別可分性判據(jù) 特征選擇中的直接挑選法,目的：,7.1 概 述,類別可分性判據(jù)小結(jié),幾何可分性判據(jù) 類概率密度可分性判據(jù)(一)Bhattacharyya判據(jù)(JB) (二)Cher