特征選擇與稀疏學習

1、徐淼p 特征l 描述物體的屬性p 特征的分類l 相關特征: 對當前學習任務當前學習任務有用的屬性l 無關特征: 與當前學習任務當前學習任務無關的屬性西瓜的特征特征顏色紋理觸感根蒂聲音相關相關特征特征無關特征無關特征好瓜壞瓜當前任務當前任務：西瓜是否是好瓜p 特征選擇l 從給定的特征集合中選出任務相關任務相關特征子集l 必須確保不丟失重要特征p 原因l 減輕維度災難：在少量屬性上構建模型l 降低學習難度：留下關鍵信息西瓜的特征特征顏色紋理觸感根蒂聲音相關相關特征特征無關特征無關特征好瓜壞瓜當前任務當前任務：西瓜是否是好瓜特征選擇：選擇當前任務相關特征p 遍歷所有可能的子集l 計算上遭遇組合爆炸，

2、不可行不可行p 可行方法產生初始候選子集評價候選子集的好壞基于評價結果產生下一個候選子集兩個關鍵環(huán)節(jié)：子集搜索和子集評價p 前向搜索：最優(yōu)子集初始為空集，逐漸增加相關特征 p 后向搜索：從完整的特征集合開始，逐漸減少特征p 雙向搜索：每一輪逐漸增加相關特征，同時減少無關特征用貪心策略選擇包含重要信息的特征子集特征集合當前最優(yōu)子集優(yōu)于上一輪最優(yōu)子集？YN結束p 特征子集A 確定了對數(shù)據(jù)集D的一個劃分l 每個劃分區(qū)域對應著特征子集A的某種取值p 樣本標記Y對應著對數(shù)據(jù)集的真實劃分p 通過估算這兩個劃分的差異，就能對特征子集進行評價；與樣本標記對應的劃分的差異越小，則說明當前特征子集越好p 信息熵是

3、判斷這種差異的一種方式常見的特征選擇方法大致分為如下三類：p 過濾式p 包裹式p 嵌入式將特征子集搜索機制與子集評價機制相結合，即可得到特征選擇方法常見的特征選擇方法大致分為如下三類：p 過濾式先對數(shù)據(jù)集進行特征選擇，然后再訓練學習器，特征選擇過程與后續(xù)學習器無關。先用特征選擇過程過濾原始數(shù)據(jù)，再用過濾后的特征來訓練模型。p 包裹式p 嵌入式將特征子集搜索機制與子集評價機制相結合，即可得到特征選擇方法p Relief (Relevant Features) 方法是一種著名的過濾式特征選擇方法。l Relief算法最早由Kira提出，最初局限于兩類數(shù)據(jù)的分類問題。l Relief算法是一種特征權

4、重算法(Feature weighting algorithms)，根據(jù)各個特征和類別的相關性賦予特征不同的權重（相關統(tǒng)計量），權重小于某個閾值的特征將被移除。l Relief算法中特征和類別的相關性是基于特征對近距離樣本的區(qū)分能力。l Relief的關鍵是如何確定權重（相關統(tǒng)計量）？pp選用的數(shù)據(jù)：威斯康星州乳腺癌數(shù)據(jù)集，數(shù)據(jù)來源美國威斯康星大學醫(yī)院的臨床病例報告，每條數(shù)據(jù)具有9個屬性。p數(shù)據(jù)處理思路：先采用ReliefF特征提取算法計算各個屬性的權重，剔除相關性最小的屬性，然后采用K-means聚類算法對剩下的屬性進行聚類分析。p乳腺癌數(shù)據(jù)集特征提取采用ReliefF算法來計算各個特征的權

5、重，權重小于某個閾值的特征將被移除，針對乳腺癌的實際情況，將對權重最小的2-3種剔除。將ReliefF算法運行20次，得到了各個特征屬性的權重趨勢圖p按照從小到大順序排列，可知，各個屬性的權重關系如下：屬性9屬性5屬性7屬性4屬性2屬性3屬性8屬性1屬性6我們選定權重閥值為0.02，則屬性9、屬性4和屬性5剔除。p乳腺癌數(shù)據(jù)特征分析從上面的特征權重可以看出，屬性6裸核大小是最主要的影響因素，說明乳腺癌患者的癥狀最先表現(xiàn)了裸核大小上，將直接導致裸核大小的變化，其次是屬性1和屬性8等，后幾個屬性權重大小接近。幾個重要的屬性進行分析：塊厚度屬性的特征權重在0.19-25左右變動，也是權重極高的一個，

6、說明該特征屬性在乳腺癌患者檢測指標中是相當重要的一個判斷依據(jù)。進一步分析顯示，在單獨對屬性6，和屬性1進行聚類分析，其成功率就可以達到91.8%。常見的特征選擇方法大致分為如下三類：p 過濾式p 包裹式直接把最終將要使用的學習器的性能作為特征子集的評價準則p 嵌入式將特征子集搜索機制與子集評價機制相結合，即可得到特征選擇方法p 包裹式特征選擇的目的就是為給定學習器選擇最有利于其性能、“量身定做”的特征子集p 包裹式選擇方法直接針對給定學習器進行優(yōu)化，因此從最終學習器性能來看，包裹式特征選擇比過濾式特征選擇更好p 包裹式特征選擇過程中需多次訓練學習器，計算開銷通常比過濾式特征選擇大得多p LVW

7、（Las Vegas Wrapper）是一個典型的包裹式特征選擇方法， LVW在拉斯維加斯方法框架下使用隨機策略來進行子集搜索，并以最終分類器的誤差作為特征子集評價準則p LVW基本步驟在循環(huán)的每一輪隨機產生一個特征子集在隨機產生的特征子集上通過交叉驗證推斷當前特征子集的誤差進行多次循環(huán)，在多個隨機產生的特征子集中選擇誤差最小的特征子集作為最終解p 采用隨機策略搜索特征子集，而每次特征子集的評價都需要訓練學習器，開銷很大。常見的特征選擇方法大致分為如下三類：p 過濾式 特征選擇過程與學習器訓練過程有明顯的分別p 包裹式p 嵌入式將特征選擇過程與學習器訓練過程融為一體，兩者在同一個優(yōu)化過程中完成

8、，在學習器訓練過程中自動地進行特征選擇將特征子集搜索機制與子集評價機制相結合，即可得到特征選擇方法p嶺回歸嶺回歸 (ridge regression) Tikhonov and Arsenin, 1977p 將數(shù)據(jù)集D考慮成一個矩陣，每行對應一個樣本，每列對應一個特征。特征選擇說考慮的問題是特征具有稀疏性，即矩陣中的許多列與當前學習任務無關，通過特征選擇去除這些列，則學習器訓練過程僅需在較小的矩陣上進行，學習任務的難度可能有所降低，設計的計算和存儲開銷會減少，學得模型的可解釋性也會提高。p 矩陣中有很多零元素，且非整行整列出現(xiàn)。p 稀疏表達的優(yōu)勢：l 數(shù)據(jù)具有稀疏性，使得大多數(shù)問題變得線性可分

9、l 稀疏矩陣已有很多高效的存儲方法p 在一般的學習任務中，數(shù)據(jù)集（如圖像）往往是非稀疏的，能否將稠密表示的數(shù)據(jù)集轉化為“稀疏表示”，使其享受稀疏表達的優(yōu)勢？p 為普通稠密表達的樣本找到 合適的字典字典ppp 壓縮壓縮感知感知是由美國學者E. Candes和T. Tao于2004年首先提出的。“壓縮感知”顧名思義是直接感知壓縮后的信息，其目的是從盡量少的數(shù)據(jù)中提取盡量多的信息。CS 理論證明了如果信號在正交空間具有稀疏性（即可壓縮性），就能以遠低于Nyquist采樣頻率的速率采樣該信號，最后通過優(yōu)化算法高概率重建出原信號。其基本思想是一種基于稀疏表示的信號壓縮和重構技術，也可以稱為壓縮采樣或稀疏采樣。p 壓縮壓縮感知感知是由美國學者E. Candes和T. Tao于2004年首先提出的。“壓縮感知”顧名思義是直接感知壓縮后的信息，其目的是從盡量少的數(shù)據(jù)中提取盡量多的信息。CS 理論證明了如果信號在正交空間具有稀疏性（即可壓縮性），就能以遠低于Nyquist采樣頻率的速率采樣該信號，最后通過優(yōu)化算法高概率重建出原信號。其基本思想是一種基于稀疏表示的信號壓縮和重構技術，也可以稱為壓縮采樣或稀疏采樣。p 壓縮感知引起了信號采樣及相應重構方式的本質性變化，即：數(shù)據(jù)的采樣和壓縮是以低速率同步進行的，這對于降低信息獲取系統(tǒng)