11.1 子集搜索與評價

相關特征：對當前學習任務有用的屬性褥影。

無關特征：對當前學習任務沒用的屬性崭捍。

冗余特征：所包含的信息能從其他特征中推演出來的特征。

在很多時候不起作用蕾各，去除它們會減輕學習過程的負擔冶忱。
有時候恰好對應了完成學習任務所需的“中間概念”，會降低學習任務的難度登馒。

特征選擇：從給定的特征集合中選擇出相關特征子集的過程匙握。將特征子集搜索機制與子集評價機制相結合，即可得到特征選擇方法陈轿。

減輕維數災難問題圈纺。
降低學習任務的難度。

為簡化討論麦射，本章暫且假定數據中不涉及冗余特征蛾娶，并且假定初始的特征集合包含了所有的重要信息。

子集搜索：

前向搜索：從單個特征開始潜秋，每次嘗試增加一個相關特征蛔琅，這樣逐漸增加特征的策略。
1. 給定特征集合{a₁, a₂, ..., a_d}峻呛，我們可將每一個特征看做一個候選子集罗售，對這d個候選單特征子集進行評價，假定{a₂}最優(yōu)钩述，于是將{a₂}作為第一輪的選定集寨躁。
2. 在上一輪的選定集中加入一個特征，構成包含兩個特征的候選子集牙勘，假定在這d-1個候選兩特征子集中{a₂, a₄}最優(yōu)职恳，且優(yōu)于{a₂}，于是將{a₂, a₄}作為本輪的選定集方面。
3. 假定在第k+1輪時放钦，最優(yōu)的候選(k+1)特征子集不如上一輪的選定集，則停止生成候選子集葡幸，并將上一輪選定的k特征集合作為特征選擇結果最筒。
后向搜索：從完整的特征集合開始，每次嘗試去掉一個無關特征蔚叨，這樣逐漸減少特征的策略床蜘。
雙向搜素：每一輪逐漸增加選定相關特征（這些特征在后續(xù)輪中將確定不會被去除）、同時減少無關特征的策略蔑水。

上述策略都是貪心的邢锯，僅考慮了使本輪選定集最優(yōu)。但若不進行窮舉搜索搀别，則無法避免這樣的問題丹擎。

子集評價：特征子集A實際上確定了對數據集D的一個劃分，每個劃分區(qū)域對應著A上的一個取值，而樣本標記信息Y則對應著對D的真實劃分蒂培，通過估算這兩個劃分的差異再愈，就能對A進行評價。與Y對應的劃分的差異越小护戳，則說明A越好翎冲。信息熵是判斷這個差異的其中一種途徑：

給定數據集D，假定D中第i類樣本所占的比例為p_i （i = 1, 2, ..., |y|）媳荒。為便于討論抗悍，假定樣本屬性均為離散型。對屬性子集A钳枕，假定根據其取值將D分成了V個子集{D¹, D², ..., D^V}缴渊，每個子集中的樣本在A上取值相同，于是我們可計算屬性子集A的信息增益
$Gain(D, a) = Ent(D) - \displaystyle\sum_{v=1}^V\frac{|D^v|}{|D|}Ent(D^v)鱼炒，$
其中信息熵定義為
$Ent(D) = - \displaystyle\sum_{k=1}^{|y|}p_klog_2p_k衔沼，$
其中信息增益Gain(A)越大，意味著特征子集A包含的有助于分類的信息越多田柔。于是俐巴，對每一個候選特征子集，我們可基于訓練數據集D來計算其信息增益硬爆，以此作為評價準則欣舵。
信息熵的相關內容可參考http://www.reibang.com/p/ea115d94ba52

11.2 過濾式選擇

過濾式特征選擇：先對數據集進行特征選擇，然后再訓練學習器缀磕，特征選擇過程與后續(xù)學習器無關缘圈。這相當于先用特征選擇過程對初始特征進行“過濾”，再用過濾后的特征來訓練模型袜蚕。

Relief方法：一種為二分類問題設計的過濾式特征選擇方法糟把。只需在數據集的采樣上而不必在整個數據集上估計相關統計量，其時間開銷隨采樣次數以及原始特征線性增長牲剃，是一個運行效率很高的過濾式特征選擇算法遣疯。

設計了一個“相關統計量”來度量特征的重要性。該統計量是一個向量凿傅，其每個分量分別對應于一個初始特征缠犀，而特征子集的重要性則是由子集中每個特征所對應的相關統計量分量之和來決定。
1. 給定訓練集 {(x₁, y₁), (x₂, y₂), ..., (x_m, y_m)}聪舒，對每個示例x_i辨液，先在x_i的同類樣本中尋找其最近鄰x_i,nh，稱為猜中近鄰near-hit箱残。（選中樣本中的一個好瓜滔迈，則離此好瓜最近的另一個好瓜則為猜中近鄰止吁，下標nh為near-hit簡寫）
2. 從x_i的異類樣本中尋找其最近鄰x_i,nh，稱為猜錯近鄰near-hit（離第一步選中的好瓜最近的壞瓜則為猜錯近鄰）
3. 若x_i與其猜中近鄰x_i,nh在屬性j上的距離小于x_i與其猜錯近鄰x_i,nm的距離燎悍，則說明屬性j對區(qū)分同類與異類樣本是有益的敬惦，于是增大屬性j所對應的統計量分量，反之亦然间涵。按此規(guī)律可計算相關統計量對應于屬性j的分量：其中表示在屬性j上的取值仁热，取決于屬性j的類型：
  - 若屬性j為離散型，則 $x^j_a = x^j_b$ 時 $diff(x^j_a, x^j_b) = 0$ 勾哩，否則為1。
  - 若屬性j為連續(xù)型举哟，則 $diff(x^j_a, x^j_b) = |x^j_a - x^j_b|$ 思劳，注意 $x^j_a, x^j_b$ 已規(guī)范化到[0, 1]區(qū)間。
4. 對基于不同樣本得到的估計結果進行平均妨猩，就得到各屬性的相關統計量分量潜叛，分量值越大，則對應屬性的分類能力就越強壶硅。
指定一個閾值τ威兜，選擇比τ大的相關統計量分量所對應的特征；也可指定欲選取的特征個數k庐椒，然后選擇相關統計分量最大的k個特征椒舵。

Relief算法：

輸入：訓練集D;
??????樣本抽樣次數m;
??????特征權重閾值τ.
過程：
1. T = ?;
2. for i = 1 to m do
3. ??隨機選擇一個樣本R;
4. ??從同類樣本集中找到R的最近鄰樣本H;
5. ??從不同樣本集中找到最近鄰樣本M;
6. ??for A = 1 to N do
7. ????W(A) = W(A) - diff(A, R, H)/m + diff(A, R, M)/m
8. ??end for
9. end for
10. for A = 1 to N do
11. ??if W(A) ≥ τ
12. ????把第A個特征添加到T中
13. ??end if
14. end for
輸出：特征子集T

Relief-F方法：Relief的拓展變體，能處理多分類問題约谈。

假定數據集D中的樣本來自|y|個類別笔宿。對示例x_i，若它屬于第k類(k∈{1, 2, ..., |y|})棱诱，則先在第k類的樣本中尋找x_i的最近鄰示例x_i,nh并將其作為猜中近鄰泼橘。
在第k類之外的每個類中找到一個x_i的最近鄰示例作為猜錯近鄰，記為x_i,l,nh(l = 1, 2, ..., |y|; l ≠ k)迈勋。
相關統計量對應于屬性j的分量為
$\delta^{j}=\sum_{i}-\operatorname{diff}\left(x_{i}^{j}, x_{i, \mathrm{nh}}^{j}\right)^{2}+\sum_{l \neq k}\left(p_{l} \times \operatorname{diff}\left(x_{i}^{j}, x_{i, l, \mathrm{nm}}^{j}\right)^{2}\right),$ 其中p_l為第l類樣本在數據集D中所占的比例炬灭。

11.3 包裹式選擇

包裹式特征選擇：直接把最終將要使用的學習器的性能作為特征子集的評價準則，目的是為給定學習器選擇最有利于其性能靡菇、“量身定做”的特征子集重归。

從最終學習器性能來看，包裹式特征選擇比過濾式特征選擇更好镰官。
但包裹式特征選擇的計算開銷通常比過濾式特征選擇大得多提前。

拉斯維加斯方法：若有時間限制，給出滿足要求的解或不給出解泳唠；若無時間限制狈网，給出滿足要求的解。

LVW算法：典型的包裹式特征選擇方法。在拉斯維加斯方法框架下使用隨機策略來進行子集搜索拓哺，并以最終分類器的誤差為特征子集評價準則勇垛。

輸入：數據集D;
??????特征集A;
??????學習算法 $\mathfrak{L}$ ;
??????停止條件控制參數T.
過程：
1. E = ∞;
2. d = |A|;
3. A^* = A;
4. t = 0;
5. while t < T do
6. ??隨機產生特征子集A^';
7. ??d^' = |A^'|;
8. ??E^' = CrossValidation( $\mathfrak{L}$ (D^A'));
9. ??if (E^' < E) ∨ ((E^' = E) ∧ (d^' < d)) then
10. ????t = 0;
11. ????E = E^';
12. ????d = d^';
13. ????A^* = A^';
14. ??else
15. ????t = t +1
16. ??end if
17. end while
輸出：特征子集A^*

第1-4行：初始誤差E為無窮大；目前最優(yōu)特征子集A^*為全集A士鸥；目前特征子集內特征數量d為全集A內特征數量闲孤；重復次數t為0。
第5行：當重復次數t小于設定的停止條件控制參數T時烤礁，開始循環(huán)讼积。
第6-7行：隨機產生一個特征子集A^'，目前特征子集內特征數量更新為d^'脚仔。
第8行：使用交叉驗證估計使用特征子集A^'來訓練學習器所產生的誤差E^'勤众。
第9行：如果使用征子集A^'來訓練學習器所產生的誤差E^'小于當前誤差E；或者兩個誤差相同E^' = E鲤脏，但目前特征子集內的特征數量d^'小于當前特征數量d们颜。
第10-13行：則重復次數重置為0，將誤差上限E設置為本輪誤差E^'猎醇，將特征子集內特征數量上限設置為本輪特征數量d^'窥突，將特征子集A^'保留。
第14-16行：若不滿足第9行條件硫嘶，即隨機選擇出的特征子集A^'無法減少誤差阻问，則重復次數t+1。
第17行：當t大于T時音半，即連續(xù)T輪未更新時则拷，算法停止。

11.4 嵌入式選擇與L₁正則化

嵌入式特征選擇：將特征選擇過程與學習期訓練過程融為一體曹鸠，兩者在同一個優(yōu)化過程中完成煌茬，即在學習器訓練過程中自動地進行了特征選擇。

L₁正則化：在損失函數中引入范數可降低過擬合的風險彻桃，而引入L₁范數相比L₂范數更易于獲得“稀疏”解坛善，即它所求得的w會有更少的非零分量。稀疏解意味著初始的d個特征中僅有對應著w的非零分量的特征才會出現在最終模型中邻眷，于是眠屎，求解L₁范數正則化的結果是得到了僅采用一部分初始化特征的模型，同時完成了特征選擇與學習器訓練肆饶，是一種嵌入式特征選擇方法改衩。

正則化原理可參考知乎https://www.zhihu.com/question/20924039
L₁正則化問題的求解過程可參考書本以及南瓜書https://datawhalechina.github.io/pumpkin-book/#/chapter11/chapter11

11.5稀疏表示與字典學習

稀疏表示：若將數據集D考慮成一個矩陣，其每行對應一個樣本驯镊，每列對應于一個特征葫督，則特征選擇所考慮的問題是特征具有稀疏性竭鞍。

矩陣中的許多列與當前學習任務無關。通過特征選擇去除這些列橄镜，則學習器訓練過程僅需在較小的矩陣上進行偎快，學習任務的難度可能有所降低，設計的計算和存儲開銷會減少洽胶，學的模型的可解釋性也會提高晒夹。
矩陣中中存在很多零元素，這些零元素并不是以整列姊氓、整行形式存在丐怯。當樣本具有這樣的稀疏表達形式時，對學習任務來說會有不少好處他膳。如大多數問題變得線性可分响逢，且洗漱樣本不會造成存儲上的巨大負擔，因為稀疏矩陣已有很多高校的存儲方式棕孙。

字典學習/稀疏編碼：將給定的普通非稀疏的稠密數據集轉化為合適的稀疏表達形式，從而使學習任務得以簡化些膨，模型復雜度得以降低蟀俊。

字典學習的過程可參考書本以及南瓜書https://datawhalechina.github.io/pumpkin-book/#/chapter11/chapter11

11.6 壓縮感知

奈奎斯特采樣定理：令采樣頻率達到模擬信號最高頻率的兩倍，則采樣后的數字信號就保留了模擬信號的全部信息订雾；換言之肢预，由此獲得的數字信號能精確重構原模擬信號。

壓縮感知：接收方基于收到的損失了部分信息的信號洼哎，重構出原信號烫映。

感知測量：對原始信號進行處理，以獲得稀疏樣本表示噩峦，這方面的內容涉及傅里葉變換锭沟、小波變換以及字典學習、稀疏編碼等识补。
重構恢復：基于稀疏性從少量觀測中恢復原信號族淮。

壓縮感知的過程可參考書本

第十一章特征選擇與稀疏學習

第十一章特征選擇與稀疏學習

11.1 子集搜索與評價

11.2 過濾式選擇

11.3 包裹式選擇

11.4 嵌入式選擇與L₁正則化

11.5稀疏表示與字典學習

11.6 壓縮感知

第十一章 特征選擇與稀疏學習

11.1 子集搜索與評價

11.2 過濾式選擇

11.3 包裹式選擇

11.4 嵌入式選擇與L1正則化

11.5稀疏表示與字典學習

11.6 壓縮感知

第十一章特征選擇與稀疏學習

11.4 嵌入式選擇與L₁正則化