機器學習與數(shù)據(jù)挖掘_特征選擇與降維

1、機器學習與數(shù)據(jù)挖掘特征選擇與特征降維維數(shù)災難nCurse of Dimensionality隨著維數(shù)的增加，特征空間的體積指數(shù)增加，從而導致各方面的成本指數(shù)增加n樣本數(shù)量n存儲空間n計算量nn圖靈可計算問題：多項式復雜度涉及高維空間的算法是不可計算的?。烤S數(shù)災難n維數(shù)災難的幾個表現(xiàn)空間采樣011維：42維：4*4=1610維：410=1048576Monte Carlo: 4016010M維數(shù)災難n維數(shù)災難的幾個表現(xiàn)索引困難0111立方體體積球體積1比例100%/478.5%11055 . 0! 50.25%維數(shù)災難n維數(shù)災難的幾個表現(xiàn)樣本稀疏n總樣本：1000n每維劃分：41維：1000/4

2、 = 250 樣本/區(qū)間2維：1000/(4*4)= 62.5 樣本/區(qū)間10維：1000/(410)= 0.001 樣本/區(qū)間維數(shù)災難n維數(shù)災難的幾個表現(xiàn)噪聲影響n特征空間：101維n正負樣本在第一維的距離：1n樣本在其余維的噪聲：10%n“噪聲距離”：n即使噪聲只有10%，高維空間的“噪聲距離”足以掩蓋正負樣本的本質區(qū)別11 . 01002維數(shù)災難n高維空間的奇異特性克萊因瓶Klein bottle莫比烏斯帶Mbius stripN維單位超球的表面積(http:/ Yang and Jan Pedersen“A comparative study on feature selection

3、in text categorization”.維數(shù)災難n特征降維的途徑去除無用特征n特征的必要性：不必要的特征對訓練無用n特征選擇去除相關分量n特征的相關性：相關的多個特征可以變換成較少的不相關分量n特征變換/特征降維特征選擇n從整個特征集中選擇最有效的子集如何評價特征“有效性”？n互信息量， 測試，如何決定閾值？n指定維數(shù)n指定“有效性”指標n指定性能n增量式、減量式性能評價2x特征選擇n特征有效性評價從概率論的角度n協(xié)方差兩個隨機變量不相關：協(xié)方差為0隨機變量相關度與協(xié)方差正相關問題：協(xié)方差是兩個變量的總方差n如果某變量方差大，則協(xié)方差也大 YEYXEXEYXiii,cov特征目標函數(shù)特

4、征選擇n特征有效性評價從概率論的角度n相關系數(shù)（歸一化協(xié)方差）值域范圍：-1, +1絕對值越大，相關性越大n一般使用其平方作為特征選擇指標 YXYXiii,cov標準差特征選擇n特征有效性評價從數(shù)理統(tǒng)計的角度（假設檢驗）n 測試nT測試n自己翻課本查公式n與相關系數(shù)在理論上非常接近，但更偏重于有限樣本下的估計2x特征選擇n特征有效性評價從信息論角度n把機器學習過程看做通信特征是編碼目標函數(shù)是信息特征包含的有關目標函數(shù)的信息越多，則從特征解出的信息就越多完全編碼目標函數(shù)需要的額外特征就越少各種信息量/熵衡量指標特征選擇n特征有效性評價從信息論角度n條件熵與“相關性”負相關n信息增益n相對信息增益

5、n/tutorials/infogain.htmliXYH| iiXYHYHXYIG| YHXYHYHXYRIGii/|特征選擇n特征有效性評價從信息論角度n互信息量(Mutual Information)KL-距離 YPXPYXPKLdYdXYPXPYXPYXPiMIiiiiii|,log,特征選擇n特征有效性評價IR領域的度量n（逆）文檔詞頻(inverse document frequency)ttDDidflog總文檔數(shù)總文檔數(shù)包含詞包含詞(特征特征)t的文檔數(shù)的文檔數(shù)所有文檔都出現(xiàn)的詞(如“的”)：D=Dt idft = log(1) =

6、0在1%文檔中出現(xiàn)的詞：D/Dt = 100 idft = log(100) 0特征選擇n特征有效性評價IR領域的度量n詞強度(term strength)已知一個詞(特征)在某文檔(實例)中出現(xiàn)，該詞在同類(目標函數(shù)值相同)文檔中出現(xiàn)的概率為詞強度 jyYiyYdtdtPts|特征選擇n特征有效性評價學習相關的度量n分類準確率用單一維特征進行分類訓練，某種分類準確率指標作為特征的有效性度量復雜度較大不一定有合適的準確率指標特征選擇n選擇方法獨立選擇n指定維數(shù)如何確定？n指定閾值如何確定？n特征的組合可能比單個的特征有效聯(lián)合選擇Guyon-Elisseeff, JMLR 2004; Sprin

7、ger 2006特征選擇n聯(lián)合選擇減量法nF =全體特征n計算在F上的分類性能nF = F -ff可以用評價準則選擇，也可以遍歷所有特征n計算在F 上的分類性能n如果分類性能不降低： F=F ，循環(huán)否則結束特征選擇n聯(lián)合選擇增量法nF =f1n計算在F上的分類性能nF = F +f 2f1、 f2可以用評價準則選擇，也可以遍歷所有特征n計算在F 上的分類性能n如果分類性能增加： F=F ，循環(huán)否則結束特征選擇n聯(lián)合選擇增/減量法優(yōu)缺點n復雜度關于維數(shù)為 或選單個特征采用評價準則排序的方式為一次選單個特征采用測試全部特征的方式為二次n本質上是貪心算法某些組合無法遍歷可能陷入局部極值 NO2NO特

8、征選擇n聯(lián)合選擇全組合遍歷nNP難NO 2Kohavi-John, 1997特征選擇n聯(lián)合選擇模擬退火/遺傳算法（通用的優(yōu)化算法）n隨機生成一批解可以用梯度下降法迭代到局部極值n用現(xiàn)有解通過操作合成新的解不要求合成操作具有任何理論依據(jù)好的合成操作將極大提高解題效率n對新生成的解進行生存選擇同上，并可用梯度下降法迭代到局部極值n迭代直到收斂或已支付預期的計算量特征選擇n模擬退火/遺傳算法理論依據(jù)n梯度下降法（爬山法）往往陷入局部極值n非梯度下降手段使解“跳”到爬山法可求解范圍不同的非梯度下降手段產(chǎn)生不同的算法梯度下降法可求解的范圍局部極值特征選擇n模擬退火/遺傳算法應用實例nN皇后問題求解n旅行

9、商(TSP)問題求解n很多類似NP完全和NP難問題n適合于解可能有大量解，但解的比例很小，而整個解空間巨大的問題特征選擇n特征的相關性問題例：直方圖通過特征選擇算法不可能消除相關特征的相關性Guyon-Elisseeff, JMLR 2004; Springer 2006iiH1niHHHH,.,.,1niinHH11Hn可以由前n-1維完全預測出Hn不能告訴我們任何額外信息可預測則不攜帶信息特征選擇n相關特征的選擇把所有特征的各種可能變換、組合加入特征矢量在這個巨大的特征矢量上進行特征選擇n比NP難還難的問題特征的函數(shù)組合是無限的核函數(shù)（kernel functions）類似于利用原有特征構

10、造各種新特征n僅哲學上類似，并無數(shù)學依據(jù)變換降維特征降維n主分量分析(PCA: Principle Component Analysis)在特征空間，如果特征維之間有相關性，則樣本將分布在較低維的(高維)(曲)面上特征降維n主分量分析線性變換iiiTHaHaz111niHHHH,.,.,1原始特征矢量：主分量：11111,.,.,niaaaa “軸”： 11varmaxarg1zaa111aaTHazTkk kakzakvarmaxargak垂直于所有前面的“軸”特征降維n主分量分析 11,11,11,11,1121211varSaaSaaHHHHaaHHaaHHaazzzTjiijjijij

11、ijijijijijijijiji協(xié)方差矩陣如何求極值： 111varSaazT111aaT約束條件：特征降維n主分量分析Lagrange乘數(shù)法11111aaSaaTT目標函數(shù)約束條件求導，導數(shù)為0處為極值011 aSa01aISa1是S的最大特征值對應的特征矢量特征降維n主分量分析同理可證：所有主分量對應的“軸”都是S的特征矢量，相應的特征值為其方差HAzT正交陣A可通過KL變換從協(xié)方差矩陣S求特征降維n主分量分析如果H是線性相關的：S是降秩的n特征矢量個數(shù)小于維數(shù)降維無信息損失如果H各維相關性大，但沒有達到完全相關n有很小的特征值對應的特征矢量可以去除n降維，有信息損失n相關但非線性相關？目前還沒有好的方法特征降維n多模特征的降維同質特征可以方便地使用PCAn同質特征內部是已經(jīng)歸一化的n例：直方圖，像素值，等等異質特征不能簡單地進行PCAn不同的歸一化導致不同的主分量n異質特征之間沒有歸一化例：顏色直方圖和“粗糙度”如何歸一化？特征降維n多模特征的降維分組降維，組