特征選擇與提取.ppt

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