我又上線啦！前幾天收到簡信纺念，才知道小李在簡書耍了一年啦想括！承蒙各位厚愛瑟蜈，小李還能堅持更新 嘻嘻嘻铺根！感恩Ｎ挥亍！現(xiàn)在的更新就隨著組會的任務啦臣缀！
————————

特征選擇

特征選擇精置，從字面上來說就是選擇特征氯窍，特征其實就是樣本集的屬性狼讨。我們在做一個學習任務的時候政供，應該有類似“取其精華布隔，去其糟粕”的思想，也就是要選擇對我們當前學習任務有用的屬性留下來招刨，沒有用的屬性丟棄沉眶。這里將有用的屬性稱之為相關(guān)特征谎倔，沒有用的屬性稱之為無關(guān)特征片习。故藕咏，我們把從給定的特征集合中選擇出相關(guān)子集的過程侈离，稱為特征選擇筝蚕。

舉個例子：選擇西瓜的時候洲胖，我們?nèi)サ魺o關(guān)特征坯沪，只留下了有用的根蒂和聲音的特征腐晾。

特征選擇的優(yōu)點：
（1）減輕維數(shù)災難淹冰，在少數(shù)屬性上構(gòu)建模型
（2）降低學習難度樱拴，留下關(guān)鍵信息
需要注意的是，特征選擇的過程中必須確保不丟失重要特征珍坊。
這里還有一個其他特征“冗余特征”
定義：如果屬性Y=F(A,B,C,),且A,B,C屬于屬性集阵漏，那么Y是冗余特征履怯。
exp1：如果屬性4，可以用屬性1和屬性2綜合表示出來晾虑，那么屬性4為冗余特征帜篇。
exp2：體積V可以用長l,寬w,高h表示為V=F(l,w,h),那么V就是冗余特征
選擇的時候是否需要去除冗余特征笙隙？→考慮“中間概念”

就比如說竟痰，學習目標是估算立方體體積坏快，則“底面積”這個冗余特征的存在使得體積的估算更容易莽鸿，這時候就可不去除祥得。

子集搜索與評價

想從初始特征集合中選取一個包含了所有重要信息的特征子集级及，若沒有相關(guān)領(lǐng)域的知識作為 先驗假設(shè)创千，那就只好遍歷所有可能的子集了（窮舉）追驴；然而很明顯殿雪，這在計算上是不可行的丙曙，因為這樣做會組合爆炸亏镰，特征個數(shù)稍多一點就無法進行。因此钧忽，可行的做法是產(chǎn)生一個 候選子集耸黑，評價出它的好壞大刊，然后基于評價結(jié)果產(chǎn)生下一個 候選子集缺菌，再進行評價男翰，……以此類推蛾绎，這個過程持續(xù)進行下去租冠，直至無法找到更好的 候選子集 為止顽爹。

顯然镜粤，有兩個關(guān)鍵環(huán)節(jié)：
1.如何根據(jù)評價結(jié)果獲取下一個候選特征子集?
2.如何評價候選特征子集的好壞?
第一個環(huán)節(jié)肉渴，涉及的是子集搜索同规。有三種搜集方法：前向搜索、后向搜索绪钥、雙向搜索

給定一個特征集合 {a1，a2寸潦，...甸祭，ad} 將每個特征看成一個 候選子集 進行評價，假定a2 最優(yōu)凡怎，把它作為第一輪的選定集统倒；然后房匆，在上一輪的選定集中加入一個特征浴鸿，構(gòu)成包含兩個特征的候選子集岳链。假定在這中 {a2掸哑，a4}最優(yōu)苗分，且優(yōu)于 {a2}俭嘁，于是將 {a2供填，a4} 作為本輪的選定集近她。假定在第 k+1 輪時粘捎，最優(yōu)的候選 k+1特征子集不如上一輪的選定集攒磨，則停止生成候選子集灸撰，并將上一輪選定的 k 特征集合作為特征選擇結(jié)果浮毯，這樣逐漸增加相關(guān)特征 的策略稱為前向(fòrward) 搜索债蓝。
綜上可以發(fā)現(xiàn)：這三種其實都是基于貪心策略即僅考慮使本輪選定集最優(yōu)饰迹。

第二個環(huán)節(jié)即評價準則啊鸭，這邊采用信息增益。

信息增益越大憎妙，意味著特征子集包含的有助于分類的信息越多
信息熵來源于決策樹厘唾，故與決策時聯(lián)系：事實上抚垃，決策樹就可以用于特征選擇鹤树，樹節(jié)點的劃分屬性所組成的特征集合就是選擇出的特征子集罕伯。

特征選擇的方法

將特征子集搜索 機制與 子集評價 機制相結(jié)合追他，即可得到特征選擇方法邑狸。
常見的方法大致可分為三類：
過濾式(fiter)单雾、包裹式(wrapper)铁坎、嵌入式(embedding)

1.過濾式

過濾式：先對數(shù)據(jù)集進行特征選擇，然后再訓練學習器朴乖，特征選擇過程與后續(xù)學習器無關(guān)买羞。先用特征選擇過程過濾原始數(shù)據(jù)畜普，再用過濾后的特征來訓練模型吃挑。

經(jīng)典算法是：Relief
Relief的核心：引入“相關(guān)統(tǒng)計量”---度量特征重要性的向量埠通，其中每個分量代表著相應特征的重要性端辱，故我們可根據(jù)這個統(tǒng)計量各個分量的大小來選擇出合適的特征子集舞蔽。
具體：對于數(shù)據(jù)集中的每個樣例xi，先找出與xi同類別的最近鄰與不同類別的最近鄰,稱為猜中近鄰(near-hit)與猜錯近鄰(near-miss),便可以分別計算出相關(guān)統(tǒng)計量中的每個分量码撰。相關(guān)統(tǒng)計量對應于屬性 j 的分量為:

實際上 Relief 是一個運行效率很高的過濾式特征選擇算法喷鸽。是專門為二分類問題設(shè)計的。其擴展變體 Relie-F 能處理多分類問題灸拍。

其中pl表示第l類樣本在數(shù)據(jù)集中所占的比例做祝，易知兩者的不同之處在于：標準Relief 只有一個猜錯近鄰，而Relief-F有多個猜錯近鄰混槐。
注：Relief只需在數(shù)據(jù)集的采樣上而不必在這個數(shù)據(jù)集上估計相關(guān)統(tǒng)計量，且屬于高效的過濾式特征選擇算法轩性。

2.包裹式

與過濾式特征選擇不考慮后續(xù)學習器不同声登，包裹式特征選擇直接把最終將要使用的學習器的性能作為特征子集的評價準則。換句話說揣苏，包裹式特征選擇的目的就是為給定學習器選擇最有利于其性能悯嗓、"量身走做"的特征子集。
一般而言卸察，由于包裹式特征選擇方法直接針對給定學習器進行優(yōu)化脯厨，因此從最終學習器性能來看，包裹式特征選擇比過濾式特征選擇更好坑质；但另一方面合武，由于在特征選擇過程中需多次訓練學習器，因此包裹式特征選擇的計算開銷通常比過濾式特征邊擇大得多涡扼。
LVW (Las Vegas Wrapper) 是一個典型的包裹式特征選擇方法稼跳。
它在拉斯維加斯方法(Las Vegas method) 框架下使用隨機策略來進行子集搜索，并以最終分類器的誤差為特征子集評價準則吃沪。
拉斯維加斯:采樣越多汤善，越有機會找到最優(yōu)解，不一定會給出解，且給出的解一定是正確解红淡。
exp: 有一把鎖卸伞，100把鑰匙，只有1把是對的锉屈。每次隨機拿1把試荤傲，打不開就再換1把。試的次數(shù)越多颈渊，打開的機會就越大遂黍，但在打開之前，那些錯的鑰匙都是沒有用的俊嗽。
找鑰匙—盡量找最好的雾家，但不保證能找到。
具體：1.在循環(huán)的每一輪隨機產(chǎn)生一個特征子集
2.在隨機產(chǎn)生的特征子集通過交叉驗證推斷當前特征子集的誤差
3.進行多次循環(huán)绍豁，在多個隨機產(chǎn)生的特征子集中選擇誤差最小的特征子集作為最終解

3.嵌入式

在過濾式和包裹式特征選擇方法中芯咧，特征選擇過程與學習器訓練過程有明顯的分別；與此不同竹揍，嵌入式特征選擇是將特征選擇過程與學習器訓練過程融為一體敬飒，兩者在同一個優(yōu)化過程中完成，即在學習器訓練過程中自動地進行了特征選擇芬位。
以均方誤差為損失函數(shù),優(yōu)化目標為:

樣本特征很多,而樣本數(shù)相對少无拗，容易過擬合--------引入正則化項。

分析：L1范數(shù)是向量中每個元素的絕對值之和,在優(yōu)化目標函數(shù)的過程中.會使w盡可能地小,起到了防止過擬合的作用,同時與L2范數(shù)不同的是,L1范數(shù)會使得部分w變?yōu)?,達到特征選擇的效果昧碉。
對比：

在0附近,L1的下降速度大于L2,L1能很快地下降到0,
L2在0附近的下降速度慢英染，因此較大可能收斂在0的附近。

L1正則化更易于得到稀疏(多數(shù)為零)解被饿，w有更少的非0的分量四康，達到了特征選擇的效果。
求解L1范數(shù)正則化的結(jié)果是得到了僅采用一部分初始特征的模型狭握。
（PGD ：近端梯段下降）：

轉(zhuǎn)化為最小值求解：

稀疏學習

稀疏表示與字典學習

特征選擇考慮的是特征具有稀疏性
(矩陣中許多列與當前學習任務無關(guān)闪金，通過特征選擇去除）
另一種稀疏性：
D所對應的矩陣中存在很多零元素，但這些零元素不是以整列哥牍、整行的形式存在的毕泌。
故稀疏表示其實就是用盡可能少的資源表示盡可能多的有用的知識
優(yōu)勢：數(shù)據(jù)具有稀疏性喝检，使得問題變?yōu)榫€性可分嗅辣。
問題來了-----若給定數(shù)據(jù)集是稠密的，即普通非稀疏數(shù)據(jù)挠说，能否轉(zhuǎn)化為“稀疏表示”的形式澡谭？（稀疏為恰當稀疏）
這個時候我們尋找一個合適的字典，也就是采用字典學習。

求解：借鑒LASSO→交替優(yōu)化的策略

經(jīng)典算法：K-SVD
核心思想：最大不同在字典更新蛙奖，K-SVD對誤差矩陣進行奇異值分解潘酗，取最大奇異值對應的正交向量更新字典的一個原子，同時并更新其稀疏系數(shù)雁仲，直到所有原子更新完畢仔夺，重復迭代幾次即可得到優(yōu)化的字典和稀疏系數(shù)≡茏【總結(jié)：K次迭代缸兔，且每一次迭代都要使用SVD分解】

具體流程：

壓縮感知

在現(xiàn)實任務中，我們常希望根據(jù)部分信息來恢復全部信息吹艇。然而在現(xiàn)實中惰蜜，總有各種信息的損失存在。那么基于收到的信號受神，能否精確地重構(gòu)出原信號呢抛猖？壓縮感知(compressed sensing) 為解決此類問題提供了新的思路。
與特征選擇鼻听、稀疏表示 不同财著，壓縮感知關(guān)注的是如何利用信號本身所具有的稀疏性，從部分觀測樣本中恢復原信號撑碴。
通常認為瓢宦，壓縮感知分為感知測量 和 重構(gòu)恢復這兩個階段。
感知測量：關(guān)注如何對原始信號進行處理以獲得稀疏樣本表示灰羽；
重構(gòu)恢復：關(guān)注的是如何基于稀疏性從少量觀測中恢復原信號驮履，這是壓縮感知的精髓。

數(shù)學表達：

舉個例子：【A為原圖廉嚼，D為從C重構(gòu)的】

求解：
y=ΦΨs玫镐，把ΦΨ合并成一個矩陣，稱之為傳感矩陣怠噪。
即令Θ=ΦΨ 恐似，則y=ΘS。
問題即為：已知y和Θ傍念，求解S矫夷。
求解S后：由x=Ψs即可得到恢復出的原信號x。
然而在正常情況下憋槐，方程的個數(shù)遠小于未知數(shù)的個數(shù)双藕，方程是沒有確定解的，無法重構(gòu)信號阳仔。但是忧陪，由于信號是K稀疏，若Φ滿足有限等距性質(zhì)(RIP)，則K個系數(shù)就能夠從M個測量值準確重構(gòu)（得到一個最優(yōu)解）嘶摊。

總結(jié)

特征選擇是一個重要的“數(shù)據(jù)預處理”（data preprocessing）過程延蟹，即試圖從數(shù)據(jù)集的所有特征中挑選出與當前學習任務相關(guān)的特征子集，接著再利用數(shù)據(jù)子集來訓練學習器叶堆；稀疏學習則是圍繞著稀疏矩陣的優(yōu)良性質(zhì)阱飘，來完成相應的學習任務。
————————
參考：《機器學習》周志華西瓜書學習筆記（十一）：特征選擇與稀疏學習
代碼分享：
淺談SVD原理以及python實現(xiàn)小demo
K-SVD字典學習及其實現(xiàn)（Python）
壓縮感知重構(gòu)算法之IRLS算法python實現(xiàn)
《機器學習（周志華）》習題11.1 參考答案

希望一切順心笆拧８┟取！上枕！