特征選擇與提取.ppt

第5章特征選擇與特征提取 5 1基本概念5 2類別可分性測度5 3基于類內(nèi)散布矩陣的單類模式特征提取5 4基于K L變換的多類模式特征提取 第5章特征選擇與特征提取 5 1基本概念 由于測量上可實現(xiàn)性的限制或經(jīng)濟上的考慮 所獲得的測量值為數(shù)不多 能獲得的性質(zhì)測量值很多 如果全部直接作為分類特征 耗費機時 且分類效果不一定好 有人稱之為 特征維數(shù)災(zāi)難 特征選擇和提取的目的 經(jīng)過選擇或變換 組成識別特征 盡可能保留分類信息 在保證一定分類精度的前提下 減少特征維數(shù) 使分類器的工作即快又準(zhǔn)確 1 兩種數(shù)據(jù)測量情況 1 具有很大的識別信息量 即應(yīng)具有很好的可分性 2 具有可靠性 模棱兩可 似是而非 時是時非等不易判別的特征應(yīng)丟掉 3 盡可能強的獨立性 重復(fù)的 相關(guān)性強的特征只選一個 4 數(shù)量盡量少 同時損失的信息盡量小 2 對特征的要求 3 特征選擇和特征提取的異同 1 特征選擇 從L個度量值集合中按一定準(zhǔn)則選出供分類用的子集 作為降維 m維 m L 的分類特征 2 特征提取 使一組度量值通過某種變換產(chǎn)生新的m個特征 作為降維的分類特征 其中 c 是具有分類能力的特征 故選 c 扔掉 a b 解 法1 特征抽取 測量三個結(jié)構(gòu)特征 a 周長 b 面積 c 兩個互相垂直的內(nèi)徑比 特征選擇 一般根據(jù)物理特征或結(jié)構(gòu)特征進行壓縮 分析 例 特征選擇與特征提取的區(qū)別 對一個條形和圓進行識別 當(dāng)模式在空間中發(fā)生移動 旋轉(zhuǎn) 縮放時 特征值應(yīng)保持不變 保證仍可得到同樣的識別效果 法2 特征抽取 測量物體向兩個坐標(biāo)軸的投影值 則A B各有2個值域區(qū)間 可以看出 兩個物體的投影有重疊 直接使用投影值無法將兩者區(qū)分開 分析 將坐標(biāo)系按逆時針方向做一旋轉(zhuǎn)變化 或物體按順時針方向變 并適當(dāng)平移等 根據(jù)物體在軸上投影的坐標(biāo)值的正負(fù)可區(qū)分兩個物體 特征提取 一般用數(shù)學(xué)的方法進行壓縮 5 2類別可分性測度 5 2 1基于距離的可分性測度 類別可分性測度 衡量類別間可分性的尺度 相似性測度 衡量模式之間相似性的一種尺度 類內(nèi)距離和類間距離 類概率密度函數(shù) 1 類內(nèi)距離和類內(nèi)散布矩陣 1 類內(nèi)距離 同一類模式點集內(nèi) 各樣本間的均方距離 平方形式 Xi Xj n維模式點集 X 中的任意兩個樣本 特征選擇和提取的結(jié)果應(yīng)使類內(nèi)散布矩陣的跡愈 愈好 特征選擇和提取的結(jié)果應(yīng)使類內(nèi)散布矩陣的跡愈小愈好 若 X 中的樣本相互獨立 有 式中 R 該類模式分布的自相關(guān)矩陣 M 均值向量 C 協(xié)方差矩陣 C主對角線上的元素 表示模式向量第k個分量的方差 tr 矩陣的跡 方陣主對角線上各元素之和 2 類內(nèi)散布矩陣 表示各樣本點圍繞均值的散布情況 該類分布的協(xié)方差矩陣 類間散布矩陣的跡愈大愈有利于分類 2 類間距離和類間散布矩陣 1 類間距離 模式類之間的距離 記為 每類模式均值向量與模式總體均值向量之間平方距離的先驗概率加權(quán)和 2 類間散布矩陣 表示c類模式在空間的散布情況 記為Sb 類間散布矩陣的跡愈 愈有利于分類 3 類間距離與類間散布矩陣的關(guān)系 注意 與類間距離的轉(zhuǎn)置位置不同 3 多類模式向量間的距離和總體散布矩陣 1 兩類情況的距離 q個 p個 共p q個距離 兩個類區(qū)之間的距離 p q個距離的平均距離 5 8 2 多類情況的距離 2 Jd的另一種形式 將以下3式代入 5 8 式 1 多類模式向量間的平均平方距離Jd 任意類的組合 特定兩類間任意樣本的組合 得 某類類內(nèi)平方距離平均值 某類類間平方距離 多類模式向量之間的平方距離 各類平方距離的先驗概率加權(quán)和 3 多類情況的散布矩陣 多類類間散布矩陣 4 多類模式平均平方距離與總體散布矩陣的關(guān)系 多類類內(nèi)散布矩陣 各類模式協(xié)方差矩陣的先驗概率加權(quán)平均值 多類模式的總體散布矩陣 得 距離與散布矩陣作為可分性測度的特點 計算方便 概念直觀 反映模式的空間分布情況 與分類錯誤率沒有直接的聯(lián)系 5 2 2基于概率分布的可分性測度 1 散度 出發(fā)點 對數(shù)似然比含有類別的可分性信息 1 散度的定義 對不同的X 似然函數(shù)不同 對數(shù)似然比體現(xiàn)的可分性不同 通常采用平均可分性信息 對數(shù)似然比的期望值 類對數(shù)似然比的期望值 類對數(shù)似然比的期望值 散度等于兩類的對數(shù)似然比期望值之和 散度表示了區(qū)分 i類和 j類的總的平均信息 2 散度的性質(zhì) 1 特征選擇和特征提取應(yīng)使散度盡可能的 特征選擇和特征提取應(yīng)使散度盡可能的大 3 錯誤率分析中 兩類概率密度曲線交疊越少 錯誤率越小 由散度的定義式 可知 散度愈大 兩類概率密度函數(shù)曲線相差愈大 交疊愈少 分類錯誤率愈小 據(jù)此可估計每一個特征在分類中的重要性 散度較大的特征含有較大的可分信息 保留 5 可加性表明 加入新的特征 不會使散度減小 即 3 兩個正態(tài)分布模式類的散度 設(shè) i類和 j類的概率密度函數(shù)分別為 兩類模式之間馬氏距離的平方 一維正態(tài)分布時 兩類均值向量距離越遠(yuǎn) 散度愈大 每類自身分布愈集中 兩類間的散度愈大 5 3基于類內(nèi)散布矩陣的單類模式特征提取 對某類模式 壓縮模式向量的維數(shù) 對多類分類 壓縮維數(shù) 保留類別間的鑒別信息 突出可分性 特征提取的目的 特征提取操作方法 注意 維數(shù)降低后 在新的m維空間里各模式類之間的分布規(guī)律應(yīng)至少保持不變或更優(yōu)化 討論內(nèi)容 根據(jù)類內(nèi)散布矩陣如何確定變換矩陣A 通過A如何進行特征提取 1 根據(jù)類內(nèi)散布矩陣確定變換矩陣 式中 X為n維向量 C為n n的實對稱矩陣 n個特征向量相互正交 若選n個歸一化特征向量作為A的行 則A為歸一化正交矩陣 1 2 An n 3 變換后的類內(nèi)距離 變換后 類內(nèi)距離保持不變 根據(jù)以上特點得到構(gòu)造變換矩陣的方法 思路 目標(biāo) 構(gòu)造一變換矩陣 可以將n維向量X變換成m維 m n 將變換前的C的n個特征值從小到大排隊 選擇前m個小的特征值對應(yīng)的特征向量作為矩陣A的行 m n 對X進行A變換 優(yōu)點 壓縮了維數(shù) 類內(nèi)距離減小 樣本更密集 相當(dāng)去掉了方差大的特征分量 后續(xù) 2 特征提取的方法 其中 第二步 計算C的特征值 對特征值從小到大進行排隊 選擇前m個 第四步 利用A對樣本集 X 進行變換 則m維 m n 模式向量X 就是作為分類用的模式向量 解 1 求樣本均值向量和協(xié)方差矩陣 由 得 由歸一化特征向量u1構(gòu)成變換矩陣A 變換前 變換后 5 4基于K L變換的多類模式特征提取 對一類模式 維數(shù)壓縮 對多類模式 維數(shù)壓縮 突出類別的可分性 特征提取的目的 卡洛南 洛伊 Karhunen Loeve 變換 K L變換 一種常用的特征提取方法 最小均方誤差意義下的最優(yōu)正交變換 適用于任意的概率密度函數(shù) 在消除模式特征之間的相關(guān)性 突出差異性方面有最優(yōu)的效果 離散K L變換 連續(xù)K L變換 分為 1 K L展開式 aj 隨機系數(shù) 用有限項估計X時 引起的均方誤差 uj為確定性向量 R 自相關(guān)矩陣 拉格朗日乘數(shù) 說明 當(dāng)用X的自相關(guān)矩陣R的特征值對應(yīng)的特征向量展開X時 截斷誤差最小 選前d項估計X時引起的均方誤差為 因此 當(dāng)用X的正交展開式中前d項估計X時 展開式中的uj應(yīng)當(dāng)是前d個較大的特征值對應(yīng)的特征向量 K L變換方法 對R的特征值由大到小進行排隊 均方誤差最小的X的近似式 矩陣形式 式中 其中 5 49 K L展開式 系數(shù)向量a就是變換后的模式向量 2 利用自相關(guān)矩陣的K L變換進行特征提取 第一步 求樣本集 X 的總體自相關(guān)矩陣R 決定壓縮后的維數(shù) 3 不同散布矩陣的K L變換 根據(jù)不同的散布矩陣進行K L變換 對保留分類鑒別信息的效果不同 多類類內(nèi)散布矩陣 若要突出各類模式的主要特征分量 選用對應(yīng)于大特征值的特征向量組成變換矩陣 若要使同一類模式聚集于最小的特征空間范圍 選用對應(yīng)于小特征值的特征向量組成變換矩陣 類間散布矩陣 適用于類間距離比類內(nèi)距離大得多的多類問題 選擇與大特征值對應(yīng)的特征向量組成變換矩陣 總體散布矩陣 把多類模式合并起來看成一個總體分布 適合于多類模式在總體分布上具有良好的可分性的情況 采用大特征值對應(yīng)的特征向量組成變換矩陣 能夠保留模式原有分布的主要結(jié)構(gòu) 1 變換在均方誤差最小的意義下使新樣本集 X 逼近原樣本集 X 的分布 既壓縮了維數(shù)又保留了類別鑒別信息 利用K L變換進行特征提取的優(yōu)點 2 變換后的新模式向量各分量相對總體均值的方差等于原樣本集總體自相關(guān)矩陣的大特征值 表明變換突出了模式類之間的差異性 3 C 為對角矩陣說明了變換后樣本各分量互不相關(guān) 亦即消除了原來特征之間的相關(guān)性 便于進一步進行特征的選擇 K L變換的不足之處 1 對兩類問題容易得到較滿意的結(jié)果 類別愈多 效果愈差 2 需要通過足夠多的樣本估計樣本集的協(xié)方差矩陣或其它類型的散布矩陣 當(dāng)樣本數(shù)不足時 矩陣的估計會變得十分粗略 變換的優(yōu)越性也就不能充分的地顯示出來 3 計算矩陣的本征值和本征向量缺乏統(tǒng)一的快速算法 給計算帶來困難 例5 3兩個模式類的樣本分別為 利用自相關(guān)矩陣R作K L變換 把原樣本集壓縮成一維樣本集 解 第一步 計算總體自相關(guān)矩陣R 第二步 計算R的本征值 并選擇較大者 由得 多類類內(nèi)散布矩陣Sw 5 5特征選擇 從n個特征中選擇d個 d n 最優(yōu)特征構(gòu)成分類用特征向量 5 5 1特征選取擇的準(zhǔn)則 1 散布矩陣準(zhǔn)則 類別可分性測度 類間散布矩陣Sb 多類總體散布矩陣St 特征選擇準(zhǔn)則 使tr Sw 最小 使tr Sb 最大 使J1 J4最大 2 散度準(zhǔn)則 用于正態(tài)分布的模式類 兩類的散度表達(dá)式 平均散度 選擇使J最大的特征子集 變換散度 平均變換散度 5 5 2特征選擇的方法 從n個特征中挑選d個特征 所有可能的特征子集數(shù)為 組合數(shù)很大 窮舉法 計算出各種可能特征組合的某個測度值 加以比較 選擇最優(yōu)特征組 特點 計算量大 難實現(xiàn) 采取搜索技術(shù)可降低計算量 可以得到最優(yōu)特征組 1 最優(yōu)搜索算法 分支定界算法 唯一能獲得最優(yōu)結(jié)果的搜索方法 自上而下 具有回溯功能 使用條件 可分性測度J對維數(shù)單調(diào) 方法 待選擇的n個原特征為根 將可能的特征組構(gòu)成樹結(jié)構(gòu) 子結(jié)點的特征組元素個數(shù)逐級下降 葉結(jié)點按照規(guī)定的特征數(shù)構(gòu)成特征組合 從最右邊的葉結(jié)點開始 根據(jù)選擇的測度回溯搜索 找到最優(yōu)特征組 結(jié)束 例 從5個特征中選出2個特征作為模式向量 2 次優(yōu)搜索算法 雖然不能得到最優(yōu)解 但可減少計算量 1 單獨最優(yōu)特征組合 2 順序前進法 Sequent