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

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

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

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

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

5、n/tutorials/infogain.htmliXYH| iiXYHYHXYIG| YHXYHYHXYRIGii/|特征選擇n特征有效性評(píng)價(jià)從信息論角度n互信息量(Mutual Information)KL-距離 YPXPYXPKLdYdXYPXPYXPYXPiMIiiiiii|,log,特征選擇n特征有效性評(píng)價(jià)IR領(lǐng)域的度量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特征有效性評(píng)價(jià)IR領(lǐng)域的度量n詞強(qiáng)度(term strength)已知一個(gè)詞(特征)在某文檔(實(shí)例)中出現(xiàn)，該詞在同類(目標(biāo)函數(shù)值相同)文檔中出現(xiàn)的概率為詞強(qiáng)度 jyYiyYdtdtPts|特征選擇n特征有效性評(píng)價(jià)學(xué)習(xí)相關(guān)的度量n分類準(zhǔn)確率用單一維特征進(jìn)行分類訓(xùn)練，某種分類準(zhǔn)確率指標(biāo)作為特征的有效性度量復(fù)雜度較大不一定有合適的準(zhǔn)確率指標(biāo)特征選擇n選擇方法獨(dú)立選擇n指定維數(shù)如何確定？n指定閾值如何確定？n特征的組合可能比單個(gè)的特征有效聯(lián)合選擇Guyon-Elisseeff, JMLR 2004; Sprin

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

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

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

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

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