哈爾濱工業(yè)大學(xué)-模式識別課程-6．特征的提取與選擇4學(xué)時

1、哈爾濱工業(yè)大學(xué)哈爾濱工業(yè)大學(xué) 主講人：李君寶主講人：李君寶 1.引言引言 2 類別可分離性判據(jù)類別可分離性判據(jù) 3 特征選擇特征選擇 4.特征提取特征提取 1.引言引言 對特征空間的改造、優(yōu)化、主要的目的是降維，即把維數(shù)對特征空間的改造、優(yōu)化、主要的目的是降維，即把維數(shù) 高的特征空間改成維數(shù)低的特征空間。高的特征空間改成維數(shù)低的特征空間。 降維主要有兩種途徑。一種是刪選掉一些次要的特征，問降維主要有兩種途徑。一種是刪選掉一些次要的特征，問 題在于如何確定特征的重要性，以及如何刪選。另一種方題在于如何確定特征的重要性，以及如何刪選。另一種方 法是使用變換的手段，在這里主要限定在線性變換的方法法是

2、使用變換的手段，在這里主要限定在線性變換的方法 上，通過變換來實(shí)現(xiàn)降維，這兩種方法的區(qū)分要弄清楚。上，通過變換來實(shí)現(xiàn)降維，這兩種方法的區(qū)分要弄清楚。 【問題的提出】 1什么叫特征空間？如果我們用顏色、尺寸、重量來衡什么叫特征空間？如果我們用顏色、尺寸、重量來衡 量水果的構(gòu)造的特特空間是幾維空間？量水果的構(gòu)造的特特空間是幾維空間？ 2如果用顏色、尺寸與重量組成的特征空間來區(qū)分蘋果與如果用顏色、尺寸與重量組成的特征空間來區(qū)分蘋果與 梨，這三種度量中的哪種最有效？梨，這三種度量中的哪種最有效？ 為什么？為什么？ 能否想像這兩種水果在這個三維空間的分布？如果用能否想像這兩種水果在這個三維空間的分布？如

3、果用 這個特征空間來區(qū)分紅蘋果與櫻桃，你想像一下這兩這個特征空間來區(qū)分紅蘋果與櫻桃，你想像一下這兩 類水果在特征空間如何分布？類水果在特征空間如何分布？ 能否對這兩種情況設(shè)計(jì)更經(jīng)濟(jì)有效的特征空間？能否對這兩種情況設(shè)計(jì)更經(jīng)濟(jì)有效的特征空間？ 【問題的提出】 3如果兩類物體在一個二如果兩類物體在一個二 維特征空間如圖分布維特征空間如圖分布,能能 否用刪除其中任一維來否用刪除其中任一維來 優(yōu)化特征空間？有沒有優(yōu)化特征空間？有沒有 什么方法能得到一個對什么方法能得到一個對 分類很有利的一維特征分類很有利的一維特征 空間？空間？ 【問題的提出】 4上題的答案可用右圖上題的答案可用右圖Y1 與與Y2組成的

4、空間表示？你組成的空間表示？你 認(rèn)為哪個分量可以刪掉？認(rèn)為哪個分量可以刪掉？ 5將原在將原在X1、X2空間表示的數(shù)改成用空間表示的數(shù)改成用Y1、Y2空間表示？空間表示？ 【問題的提出】 1描述事物方法的選擇與設(shè)計(jì)描述事物方法的選擇與設(shè)計(jì) 方案方案1.從框架的左邊框到數(shù)字之間的距離變化反映從框架的左邊框到數(shù)字之間的距離變化反映 了不同數(shù)字的不同形狀，這可以用來作為數(shù)字分類了不同數(shù)字的不同形狀，這可以用來作為數(shù)字分類 的依據(jù)。的依據(jù)。 方案方案2.強(qiáng)調(diào)分析不同截面的信號，如在框架的強(qiáng)調(diào)分析不同截面的信號，如在框架的 若干部位沿不同方向截取截面分析從背景到字若干部位沿不同方向截取截面分析從背景到字

5、，以及從字到背景轉(zhuǎn)換的情況，以及從字到背景轉(zhuǎn)換的情況,如如AB截面切割截面切割 字符三次，字符三次，CD截面切割字符一次等。截面切割字符一次等。 【問題的提出】 2特征空間的優(yōu)化特征空間的優(yōu)化 這個層次的工作發(fā)生在已有了特征的描述方法之后，也就是已這個層次的工作發(fā)生在已有了特征的描述方法之后，也就是已 有了一個初始的特征空間，如何對它進(jìn)行改造與優(yōu)化的問題。一有了一個初始的特征空間，如何對它進(jìn)行改造與優(yōu)化的問題。一 般說來要對初始的特征空間進(jìn)行優(yōu)化是為了降維。即初始的特征般說來要對初始的特征空間進(jìn)行優(yōu)化是為了降維。即初始的特征 空間維數(shù)較高。能否改成一個維數(shù)較低的空間，稱為優(yōu)化，優(yōu)化空間維數(shù)較高

6、。能否改成一個維數(shù)較低的空間，稱為優(yōu)化，優(yōu)化 后的特征空間應(yīng)該更有利于后續(xù)的分類計(jì)算后的特征空間應(yīng)該更有利于后續(xù)的分類計(jì)算 例例 用用RGB顏色空間和顏色空間和HSI顏色空間顏色空間 【問題的提出】 【問題的提出】 【問題的提出】 【概念】 【概念】 【概念】 2 類別可分離性判據(jù)類別可分離性判據(jù) 【概念】 特征選擇與提取的任務(wù)是找出一組對分類最有效的特征，特征選擇與提取的任務(wù)是找出一組對分類最有效的特征， 因此需一準(zhǔn)則。因此需一準(zhǔn)則。 概念：數(shù)學(xué)上定義的用以衡量特征對分類的效果的準(zhǔn)概念：數(shù)學(xué)上定義的用以衡量特征對分類的效果的準(zhǔn) 則實(shí)際問題中需根據(jù)實(shí)際情況人為確定。則實(shí)際問題中需根據(jù)實(shí)際情況人

7、為確定。 誤識率判據(jù)：理論上的目標(biāo)，實(shí)際采用困難（密度未誤識率判據(jù)：理論上的目標(biāo)，實(shí)際采用困難（密度未 知，形式復(fù)雜，樣本不充分，知，形式復(fù)雜，樣本不充分，） 可分性判據(jù)：實(shí)用的可計(jì)算的判據(jù)可分性判據(jù)：實(shí)用的可計(jì)算的判據(jù) 【概念】 【用于可分性判據(jù)的類內(nèi)類間距離】 【用于可分性判據(jù)的類內(nèi)類間距離】 定義定義 【用于可分性判據(jù)的類內(nèi)類間距離】 常用的基于類內(nèi)類間距離的可分性判據(jù)：常用的基于類內(nèi)類間距離的可分性判據(jù)： 特點(diǎn)：特點(diǎn)： 直觀，易于實(shí)現(xiàn)（用樣本計(jì)算），較常用。直觀，易于實(shí)現(xiàn)（用樣本計(jì)算），較常用。 不能確切表明各類分布重疊情況，與錯誤率無直接聯(lián)系。不能確切表明各類分布重疊情況，與錯誤率無

8、直接聯(lián)系。 當(dāng)各類協(xié)差相差不大時，用此種判據(jù)較好。當(dāng)各類協(xié)差相差不大時，用此種判據(jù)較好。 【用于可分性判據(jù)的類內(nèi)類間距離】 幾種常見的距離度量幾種常見的距離度量 （1）Minkovski Metric (of order s) （2）城市塊（）城市塊（City Block） （3）歐氏距離（）歐氏距離（Euclidean） Chobychev 距離距離 平方距離平方距離 非線性距離度量非線性距離度量 【用于可分性判據(jù)的類內(nèi)類間距離】 選擇原則：選擇原則： ii. 計(jì)算簡單，易于實(shí)現(xiàn)。計(jì)算簡單，易于實(shí)現(xiàn)。 iii. 數(shù)學(xué)上容易處理。數(shù)學(xué)上容易處理。 準(zhǔn)則函數(shù)的遞推計(jì)算問題準(zhǔn)則函數(shù)的遞推計(jì)算問題:

9、每增每增/減一個特征，只影響向量減一個特征，只影響向量 中的一個元素，矩陣的一行和一列。中的一個元素，矩陣的一行和一列。 【用于可分性判據(jù)的類內(nèi)類間距離】 i. 實(shí)際分類問題需要，找與分類性能關(guān)系密切者。實(shí)際分類問題需要，找與分類性能關(guān)系密切者。 【基于概率分布的可分性判據(jù)】 考查兩類分布密度之間的交疊程度考查兩類分布密度之間的交疊程度 【基于概率分布的可分性判據(jù)】 定義：兩個密度函數(shù)之間的距離：定義：兩個密度函數(shù)之間的距離： 它必須滿足三個條件：它必須滿足三個條件： 【基于概率分布的可分性判據(jù)】 具體定義有多種：具體定義有多種： Bhattacharyya 距離距離 Chernoff 界界

10、散度散度 【基于概率分布的可分性判據(jù)】 正態(tài)分布情況下：正態(tài)分布情況下： 【基于概率分布的可分性判據(jù)】 幾種常見的概率距離準(zhǔn)則幾種常見的概率距離準(zhǔn)則(J ) 和概率相關(guān)性準(zhǔn)則和概率相關(guān)性準(zhǔn)則(I ) 【熵可分性判據(jù)】 熵：事件不確定性的度量熵：事件不確定性的度量 A事件的不確定性大（熵大），則對事件的不確定性大（熵大），則對A 事件的觀察所提供的信事件的觀察所提供的信 息量大。息量大。 思路：思路： 【熵可分性判據(jù)】 定義熵函數(shù)定義熵函數(shù) 滿足如下條件 規(guī)一化規(guī)一化 對稱性對稱性 確定性確定性 擴(kuò)張性擴(kuò)張性 連續(xù)性連續(xù)性 分枝性分枝性 【熵可分性判據(jù)】 常用的熵函數(shù)常用的熵函數(shù) Shannon

11、 熵：熵： 平方熵：平方熵： 廣義熵：廣義熵： 【熵可分性判據(jù)】 結(jié)論結(jié)論 【熵可分性判據(jù)】 舉例：圖像分割舉例：圖像分割 3.特征選擇特征選擇 問題：問題： 從從D維特征中選取維特征中選取d 維（維（ d D ），）， 使分類性能最佳（使分類性能最佳（ J 最大）。最大）。 【問題的提出】 一、窮舉算法：一、窮舉算法： 計(jì)算每一可能的組合，逐一比較準(zhǔn)則函數(shù)。計(jì)算每一可能的組合，逐一比較準(zhǔn)則函數(shù)。 適用于：適用于： d 或或D d 很?。ńM合數(shù)較少）的情況。很?。ńM合數(shù)較少）的情況。 二、分支定界算法：二、分支定界算法： 從頂向下，有回溯從頂向下，有回溯 應(yīng)用條件：準(zhǔn)則函數(shù)單調(diào)性應(yīng)用條件：準(zhǔn)則

12、函數(shù)單調(diào)性 基本思想：基本思想： 按照一定的順序?qū)⑺锌赡艿慕M合排成一棵樹，沿樹進(jìn)行搜索，避免一些不必要的按照一定的順序?qū)⑺锌赡艿慕M合排成一棵樹，沿樹進(jìn)行搜索，避免一些不必要的 計(jì)算，使找到最優(yōu)解的機(jī)會最早。計(jì)算，使找到最優(yōu)解的機(jī)會最早。 【最優(yōu)搜索方法】 算法要點(diǎn)：算法要點(diǎn)： 根結(jié)點(diǎn)為全體特征（第根結(jié)點(diǎn)為全體特征（第0 級）級） 每個結(jié)點(diǎn)上舍棄一個特征，各個葉結(jié)點(diǎn)代表選擇的各種組合每個結(jié)點(diǎn)上舍棄一個特征，各個葉結(jié)點(diǎn)代表選擇的各種組合 避免在整個樹中出現(xiàn)相同組合的樹枝和葉結(jié)點(diǎn)避免在整個樹中出現(xiàn)相同組合的樹枝和葉結(jié)點(diǎn) 記錄當(dāng)前搜索到的葉結(jié)點(diǎn)的最大準(zhǔn)則函數(shù)值（界限記錄當(dāng)前搜索到的葉結(jié)點(diǎn)的最大準(zhǔn)則

13、函數(shù)值（界限B），初值置），初值置0 每級中將最不可能被舍棄（舍棄后每級中將最不可能被舍棄（舍棄后J 值最小）的特征放在最左側(cè)值最?。┑奶卣鞣旁谧钭髠?cè) 從右側(cè)開始搜索從右側(cè)開始搜索 【最優(yōu)搜索方法】 從左側(cè)同級中將舍棄的特征不在本結(jié)點(diǎn)以下各級中舍棄從左側(cè)同級中將舍棄的特征不在本結(jié)點(diǎn)以下各級中舍棄 搜索到葉結(jié)點(diǎn)后，更新搜索到葉結(jié)點(diǎn)后，更新B 值，然后回溯到上一分支處值，然后回溯到上一分支處 如果結(jié)點(diǎn)上如果結(jié)點(diǎn)上J Tmin 1) for j = 1k 2) 對當(dāng)前最優(yōu)解對當(dāng)前最優(yōu)解xbest按照某一鄰域函數(shù)，按照某一鄰域函數(shù)， 產(chǎn)生一新的解產(chǎn)生一新的解xnew。計(jì)算新的目。計(jì)算新的目 標(biāo)函數(shù)值標(biāo)

14、函數(shù)值E(xnew) ，并計(jì)算目標(biāo)函數(shù)值，并計(jì)算目標(biāo)函數(shù)值 的增量的增量E = E(xnew) - E(xbest) 。 3) 如果如果E 0，則，則xbest = xnew； 4) 如果如果E 0，則，則p = exp(- E /T(i); 1) 如果如果c = random0,1 p， xbest = xnew; 否則否則xbest = xbest。 5) End for 4) i = i 1； 5) End Do 6) 輸出當(dāng)前最優(yōu)點(diǎn)，計(jì)算結(jié)束輸出當(dāng)前最優(yōu)點(diǎn)，計(jì)算結(jié)束 【模擬退火算法】 3.特征選擇特征選擇(續(xù)續(xù)) 【復(fù)習(xí)】 問題：問題： 從從D維特征中選取維特征中選取d 維（維（ d

15、D ），）， 使分類性能最佳（使分類性能最佳（ J 最大）。最大）。 【復(fù)習(xí)】 【基本遺傳算法】 【基本遺傳算法】 v基因型： 1000101110110101000111 編碼解碼 個體（染色體） 基因 【基本遺傳算法】 【基本遺傳算法】 【基本遺傳算法】 交叉點(diǎn)交叉點(diǎn) 【基本遺傳算法】 【基本遺傳算法】 變異點(diǎn)變異點(diǎn) 【基本遺傳算法】 產(chǎn)生初始群體產(chǎn)生初始群體 是否滿足停止準(zhǔn)則是否滿足停止準(zhǔn)則 是是 輸出結(jié)果并結(jié)束輸出結(jié)果并結(jié)束 計(jì)算個體適應(yīng)度值計(jì)算個體適應(yīng)度值 比例選擇運(yùn)算比例選擇運(yùn)算 單點(diǎn)交叉運(yùn)算單點(diǎn)交叉運(yùn)算 基本位變異運(yùn)算基本位變異運(yùn)算 否否 產(chǎn)生新一代群體產(chǎn)生新一代群體 執(zhí)行執(zhí)行M

16、/2次次 【基本遺傳算法】 4 特征提取特征提取 特征提?。喊烟卣魈崛。喊袲個特征變?yōu)閭€特征變?yōu)閐 個新特征個新特征 目的：更好分類和目的：更好分類和/或減少計(jì)算量或減少計(jì)算量 【概念】 【概念】 【概念】 準(zhǔn)則函數(shù)準(zhǔn)則函數(shù)J (w) ： 【歐氏距離準(zhǔn)則下的特征提取】 【歐氏距離準(zhǔn)則下的特征提取】 【歐氏距離準(zhǔn)則下的特征提取】 【歐氏距離準(zhǔn)則下的特征提取】 【歐氏距離準(zhǔn)則下的特征提取】 1. Chernoff 概率距離概率距離 【概率距離判據(jù)下的特征提取方法】 【概率距離判據(jù)下的特征提取方法】 【概率距離判據(jù)下的特征提取方法】 【概率距離判據(jù)下的特征提取方法】 【概率距離判據(jù)下的特征提取方法】 【概率距離判