第八章-特征選擇與提取PPT課件.pptx

1、,特征選擇與特征提取,1,問(wèn)題,1、為什么要做特征選擇和特征提??？ 2、特征選擇和特征提取的區(qū)別在哪兒？ 3、怎么做特征選擇和特征提取？,2,目錄,背景 特征選擇簡(jiǎn)介 特征子集搜索與子集評(píng)估 特征提取 特征選擇與特征提取討論 總結(jié),3,背景,好瓜還是壞瓜?,分類任務(wù),原始特征: 西瓜顏色, 根蒂, 敲聲, 紋理, 觸感,以往研究，是特征固定，研究重點(diǎn)是分類器,4,背景,舉例: 對(duì)于一個(gè)有經(jīng)驗(yàn)的瓜農(nóng)，怎么判斷西瓜是好還是壞？,5, 相比 ，部分特征冗余，需要選擇特征,背景,特征: 根蒂，敲聲，紋理,注意：原始特征是已知的,6,特征: 西瓜顏色, 根蒂, 敲聲,紋理, 觸感,除此之外，還有一種處理

2、特征的方式，叫特征提取,從原始特征中選擇出部分和任務(wù)相關(guān)的特征，是特征選擇,特征選擇： 從原始特征中選擇出和任務(wù)相關(guān)的特征 特征提?。?將原始特征通過(guò)線性或者非線性組合的方式轉(zhuǎn)化為新的特征表示 For example:= =1 作用: 降維 特征優(yōu)化 提升分類性能,7,背景,目錄,背景 特征選擇簡(jiǎn)介 特征子集搜索與子集評(píng)估 特征提取 特征選擇與特征提取討論 總結(jié),8,特征選擇,特征：對(duì)象所具有的屬性 例如: 西瓜顏色, 根蒂, 敲聲, 紋理, 觸感,根蒂: 蜷縮 敲聲: 清脆 紋理: 清晰,恩，這是一個(gè)好瓜,9,有經(jīng)驗(yàn)瓜農(nóng)判斷：,特征選擇,相關(guān)特征: 和任務(wù)相關(guān)的屬性，且屬性之間互相不相關(guān),比

3、如：根蒂、敲聲、紋理,無(wú)關(guān)特征: 和任務(wù)不相關(guān)的屬性,比如：顏色、觸感,特征選擇：從所有的已知屬性中選擇出和任務(wù)相關(guān)，且相互之間不相關(guān)的屬性,10,好而不同,特征選擇,11,一般來(lái)說(shuō)，特征選擇步驟如下，主要包括子集搜索和子集評(píng)估,目錄,背景 特征選擇簡(jiǎn)介 特征子集搜索與子集評(píng)估 特征提取 特征選擇與特征提取討論 總結(jié),12,子集搜索,1) 前向搜索: 依次在候選集合中增加相關(guān)特征,2) 后向搜索: 在候選集合中，依次去除不相關(guān)特征,Question: How to evaluate the searched feature?, 2 2 , 4 .,Optimal feature:,Optima

4、l feature:,13,These strategies are greedy, only consider optimization of this round 這些方法是貪心的策略，因?yàn)槭窃谏弦惠喌幕A(chǔ)上考慮本輪最優(yōu)，所以不一定得到最優(yōu)特征組合,其他子集搜索方法：,子集評(píng)估,類可區(qū)分性判據(jù)(Separation Criterion) 用于評(píng)估特征子集的類別區(qū)分性的能力,基于距離的類可區(qū)分性判據(jù) Distance based separation criterion 基于概率分布的類可區(qū)分性判據(jù) Probability distributions based separation cri

5、terion 基于熵的類可區(qū)分性判據(jù) Entropy based separation criterion,14,搜索一個(gè)特征子集，我們希望 : 樣本類內(nèi)的距離盡可能小 樣本類間距離盡可能大,基于距離的判據(jù),15,Far away,Far away,Class1,Class2,基于距離的判據(jù),樣本均值向量: 協(xié)方差矩陣: 類內(nèi)散度矩陣: 類間散度矩陣:,類可區(qū)分性判據(jù):, ( ) ( ),16,注：協(xié)方差矩陣的跡等同于方差,基于概率密度的判據(jù),17,Class1,Class2,類條件概率密度曲線,重疊,分離,x,x, 1, 2,根據(jù)搜索到的特征子集，分析一下兩個(gè)類的類條件概率密度曲線分布情況,

6、類條件概率密度,Class1,Class2, 1, 2,類條件概率密度,基于概率密度的判據(jù),= 1 , 2 , 1 , 2 ,18,重疊度 J：兩個(gè)概率密度分布曲線的重疊程度,類條件概率,先驗(yàn)概率,J 滿足的條件: 0 If 1 =0 ,19,滿足以上條件的任何函數(shù)都可以作為基于概率密度的類可區(qū)分性判據(jù)的距離度量! 概率密度距離的常用函數(shù): 巴氏距離（Bhattacharyya distance） Chernoff 界限（Chernoff bound ） 散度（Divergence） 參考書(shū): 邊肇祺模式識(shí)別第8章,基于概率密度的判據(jù),基于概率密度的判據(jù),巴氏距離 (Bhattacharyya

7、 distance) J= 1 2 1 2 對(duì)于高斯分布下： 1 = 1 (2) 2 |1| 1 2 exp 1 2 ( 1 ) 1 1 ( 1 ) 2 = 1 (2) 2 |2| 1 2 exp 1 2 ( 2 ) 2 1 ( 2 ),20,基于概率密度的判據(jù),巴氏距離 (Bhattacharyya distance) = 1 8 1 2 1 + 2 2 1 ( 1 2 ) + 1 2 | 1 2 1 + 2 | | 1 | 2 | 1 2,21,22,熵（Entropy）:,基于熵的判據(jù),熵值越大，說(shuō)明樣本的類別不確定性越大,23,貝葉斯分類器中，分類的結(jié)果由后驗(yàn)概率確定 對(duì)于一個(gè)樣本，如

8、果所有類的后驗(yàn)概率是相同的，則分類結(jié)果不可知 例如: = 1 , 分類錯(cuò)誤率: =1 1 = 1 =1 , =0, 分類錯(cuò)誤率: =0,基于熵的判據(jù),熵值可以度量后驗(yàn)概率的分布!,24,平方熵（Square Entropy）:,基于熵的判據(jù), 2 = 1 , 2 , =21 =1 2 ( |) ,后驗(yàn)概率分散性越大，熵值越大，分類錯(cuò)誤率越高,香農(nóng)熵（Shannon Entropy）:, = =1 ( |) log 2 ( |),特征選擇,過(guò)濾式 (Filter) 包裹式（Wrapper） 嵌入式（Embedding）,特征選擇策略: 特征子集搜索和子集評(píng)估組合起來(lái)的過(guò)程,25,特征選擇,過(guò)濾式

9、 ：特征選擇發(fā)生在訓(xùn)練過(guò)程之前 （無(wú)訓(xùn)練過(guò)程） 代表性方法: Relief 包裹式：直接將分類器的性能作為特征選擇中的子集評(píng)估方法（無(wú)訓(xùn)練過(guò)程） 代表性方法: LVW（拉斯維加斯算法） 嵌入式：特征選擇和學(xué)習(xí)器訓(xùn)練同時(shí)嵌入到一個(gè)優(yōu)化過(guò)程中，特征選擇在學(xué)習(xí)器訓(xùn)練過(guò)程中完成（有訓(xùn)練過(guò)程）,L1 norm,易獲得稀疏解，是一種嵌入式特征選擇方法,26,過(guò)濾式,過(guò)濾式 ：特征選擇發(fā)生在訓(xùn)練過(guò)程之前,Relief (Relevant Features) Kira and Rendell, 1992 給定相關(guān)統(tǒng)計(jì)量，度量特征的重要性 設(shè)置一個(gè)閾值t, 如果某一個(gè)特征的相關(guān)統(tǒng)計(jì)量大于閾值t, 那么就將其加入

10、特征子集 特征子集的重要性等于特征子集相關(guān)統(tǒng)計(jì)量的和,27,過(guò)濾式,特征j 的相關(guān)統(tǒng)計(jì)量：,猜中近鄰（near-hit instance） = similar class,猜錯(cuò)近鄰（near-miss instance ）= different class,instances belongs to similar class should stay closer together than those in a different class,越大，說(shuō)明特征j 的類別區(qū)分能力越強(qiáng),28,Relief-FKononenko, 1994,過(guò)濾式,Relief的擴(kuò)展，處理多分類問(wèn)題,數(shù)據(jù)集D中第L類

11、的比例,29,包裹式,包裹式：直接將分類器的性能作為特征選擇中的子集評(píng)估方法 LVW(Las Vegas Wrapper) 是一種典型的包裹式算法,1）在候選特征集中自由選擇特征子集 2）在特征子集表示的數(shù)據(jù)集上，運(yùn)行學(xué)習(xí)算法 3）用分類的錯(cuò)誤率來(lái)評(píng)估特征子集的好壞,30,包裹式,連續(xù)T次不更新，就停止,31,循環(huán)的條件,終止條件,分類錯(cuò)誤率比上一輪減小,分類錯(cuò)誤率跟上一輪相等，但特征維數(shù)減少,包裹式,LVW 可以減少特征的維數(shù)，并且提高分類的準(zhǔn)確率 由于每次都要運(yùn)行分類器，復(fù)雜性高 算法運(yùn)行速度慢,32,特點(diǎn)：,嵌入式,嵌入式：特征選擇和學(xué)習(xí)器訓(xùn)練同時(shí)嵌入到一個(gè)優(yōu)化過(guò)程中，特征選擇在學(xué)習(xí)器訓(xùn)

12、練過(guò)程中完成,目標(biāo)函數(shù),L2 norm,L1 norm,易獲得稀疏解，是一種嵌入式特征選擇方法,L1范數(shù)比L2范數(shù)更易獲得稀疏解,33,特征選擇+特征提取,并行的思路,嵌入式,34,總結(jié),背景 特征子集搜索方法 前向搜索，后向搜索，雙向搜索 特征子集評(píng)估方法 基于距離的判據(jù)，基于概率密度的判據(jù)，基于熵的判據(jù) 特征選擇的策略 過(guò)濾式，包裹式，嵌入式,35,目錄,背景 特征選擇介紹 特征子集搜索與子集評(píng)估 特征提取 特征選擇與特征提取討論 總結(jié),36,特征提取,特征提取不同于特征選擇 特征提取是將原始特征通過(guò)組合轉(zhuǎn)換到新的特征空間 特征提取是特征工程的一種,37,特征提取的方法,線性方法,Prin

13、cipal Component Analysis (PCA)Pearson , 1901 Linear Discriminant Analysis (LDA) Ronald Fisher , 1936 Belhumeur, 1996,非線性方法,Multidimensional Scaling (MDS) Torgerson, W.S. et al. ,1958 Kernel principal component analysis (KPCA) Scholkopf et al., 1998 Principal Curves Hastie, 1989 Self-Organizing Featu

14、re Map (SOM) Kohonen et al., 1995 Generative topographic map (GTM) Bishop et al., 1998 Manifold Learning：Isomap,LLE,LE. .,38,39,PCA,PCA:(主成分分析法),=11+22,x1,x2,Z 是1維的數(shù)值 W 是投影向量 x=(x1;x2) 是一個(gè)向量 w 未知 Question：如何求得最好的W,= ,線性組合就相當(dāng)于幾何中的投影,PCA,40, =(1;2;3;.;),= W T ,Z= 1;2; , ,=(1；2；3；. ；d),Question: W和Z如何計(jì)

15、算呢?,Where， Z= 1;2; 是主成分, zi 是個(gè)標(biāo)量 wj=(wj1,wj2,.,wjn) 是個(gè)向量 W 是d*n的矩陣,注： 每個(gè)主成分都是原始特征的線性組合 主成分的數(shù)量小于原始特征維數(shù) 主成分可以保留原始特征的最大信息量 主成分之間互相不相關(guān),41,目標(biāo)函數(shù)：,目標(biāo)： 最大可分性,特征值分解,PCA,求解： 特征值分解,=(1；2；3；. ；d),前d個(gè)最大的特征值對(duì)應(yīng)的特征向量組成W,方差最大化,拉格朗日乘子法,min +( ),(可理解成向量)對(duì)應(yīng)的是信息量的大小，w對(duì)應(yīng)的是投影方向,PCA,Algorithm,Let be the mean vector (taking

16、 the mean of all rows),Adjust the original data by the mean X = X ,Compute the covariance matrix XXT of adjusted X,Find the eigenvectors and eigenvalues of XXT,Get a matrix W consisted of d ordered eigenvectors,= T is the result that want to get,42,去中心化,中心化,PCA,以2維的數(shù)據(jù)集為例：,43,PCA,PCA保證新空間中特征之間不相關(guān)的情況下

17、，使變換后的特征維數(shù)更少，實(shí)現(xiàn)降維和特征提取.(不包含類別區(qū)分性) 局限： 無(wú)監(jiān)督 被忽略掉的成分可能也包含一些相對(duì)獨(dú)立的信息,44,優(yōu)點(diǎn):,LDA（線性判別分析） LDA是Fisher線性判別分析的一般形式，通過(guò)特征的線性組合實(shí)現(xiàn)兩類或者多類數(shù)據(jù)的分離。LDA在統(tǒng)計(jì)、模式識(shí)別和機(jī)器學(xué)習(xí)中具有廣泛應(yīng)用,線性判別分析,45,46,線性判別分析,2維映射到1維,2維映射到1維,線性判別分析,數(shù)據(jù)集: ：第一類數(shù)據(jù)樣本集 ：第一類數(shù)據(jù)樣本個(gè)數(shù) ：第二類數(shù)據(jù)樣本集 ：第二類數(shù)據(jù)樣本個(gè)數(shù),47,N 2,N 1,LDA 就是FLD (Fisher 線性判別),如果特征是從n維映射到1維:,以二分類為例：,

18、48,線性判別分析,均值向量: 協(xié)方差矩陣: 類內(nèi)散度矩陣: 類間散度矩陣:,原始特征空間（n維特征）,線性判別分析,49,新的特征空間（1維）,均值： = 1 , (=1,2) 方差： S = ( i ) 2 , =1,2 類內(nèi)散度： S w = S 1 + S 2 類間散度： S b = ( 1 2 ) 2,目標(biāo)函數(shù): max = ( 1 2 ) 2 S 1 + S 2,其中： i = 1 = 1 = 1 = ( 1 2 ) 2 = ( 1 2 ) 2 = 1 2 1 2 = ,Linear Discriminant Analysis,廣義瑞利商:,類間散度,類內(nèi)散度,50,W如何求解?,

19、S = ( ) 2 = ( ) 2 = = S 1 + S 2 = ( 1 + 2 )= ,線性判別分析,拉格朗日乘子法,51,min +( ),求導(dǎo) (Derivative) 使導(dǎo)數(shù)為0, = , 1 = ,特征值分解（eigenvalue decomposition）, ,最大的特征值對(duì)應(yīng)的特征向量就是 ,注: 1） 需要可逆 2）如果 不可逆, 那么先 PCA 再 LDA,不可逆出現(xiàn)在維數(shù)高，樣本量少的情況，這時(shí)可先做PCA，然后LDA,如果特征從n維映射到d維: 原始特征: n 維 新的維數(shù): 1(維度上限) 映射的維數(shù)和類別數(shù)C有關(guān),52,線性判別分析,注: 如果特征由n維映射到1維

20、，不能滿足多分類任務(wù) 那么需要映射到d維,53,線性判別分析,= 1 , 2 ,., ,= 1 , 2 ,., ,= , 是n維向量, 是 d*n 的矩陣, 是d維向量,均值向量: 協(xié)方差矩陣: 類內(nèi)散度矩陣: 類間散度矩陣:,線性判別分析,新空間（d維）：,54,= = ,目標(biāo)函數(shù):,求解: 1 = ,= 1 , 2 ,., ,注: 不是正交的,為什么維度上限是C-1？,55,線性判別分析,存在這種情況,( 1 )min 1 ,( ), = =1 ( ) =1 )( ) = =1 / )( ) = =1 =,=1 =0, 1, 1 1,特點(diǎn)： 監(jiān)督的方法，可提取出具有判別性的特征 LDA最多

21、只能將特征降低到C-1維 LDA方法需要數(shù)據(jù)服從高斯分布 容易出現(xiàn)過(guò)擬合,線性判別分析,56,57,Kernel-PCA,低維空間中線性不可分,高維空間中線性可分,Kernel-PCA,本真二維結(jié)構(gòu),PCA降維后的數(shù)據(jù)分布,三維空間中的數(shù)據(jù)分布,58,59,Kernel-PCA,PCA 目標(biāo)函數(shù)：,Kernel PCA 目標(biāo)函數(shù)：,max . =,max (,) . =,低維空間上的Kernel變換代替高維空間上的內(nèi)積,Kernel trick：,Kernel-PCA,對(duì)于一個(gè)新樣本x, 映射后的第j維表示如下 ,特征值分解,此時(shí)，W沒(méi)法求解。但是可以證明，W是新的特征空間中樣本的線性組合,

22、通過(guò)求得的a 和核函數(shù)求解,推導(dǎo)：,60,Kernel-PCA,常用的核函數(shù) 線性核 多項(xiàng)式核 高斯核 指數(shù)核 .,61,Kernel-PCA,Kernel PCA是PCA的擴(kuò)展，可有效解決低維空間中數(shù)據(jù)無(wú)法準(zhǔn)確線性映射的問(wèn)題 核技巧可以很巧妙地將低維空間上的PCA擴(kuò)展到高維空間上，實(shí)現(xiàn)數(shù)據(jù)的非線性映射，不會(huì)增加計(jì)算復(fù)雜度 沒(méi)有固定的選擇核函數(shù)的方法,62,Isomap,Isomap （ 等距離映射） 目標(biāo)是通過(guò)保持?jǐn)?shù)據(jù)點(diǎn)對(duì)之間的測(cè)地距離，來(lái)保持?jǐn)?shù)據(jù)的全局結(jié)構(gòu),測(cè)地距離,Joshua B. Tenenbaum, Vin de Silva, John C. Langford. A Global Geometric Framework for Nonlinear Dimensionality Reduction. Science, 2000,63,歐氏距離,64,Isomap,65,最短路徑近似原始空間測(cè)地距離,映射空間的歐氏距離,測(cè)地距離,Isomap,優(yōu)點(diǎn)： 對(duì)于流形分布的數(shù)據(jù)，在低維空間中保留了數(shù)據(jù) 之間的本質(zhì)距離，全局結(jié)構(gòu)得以保持 缺點(diǎn)： 降維過(guò)程沒(méi)有考慮類別區(qū)分性保持 現(xiàn)實(shí)的測(cè)地距離較難計(jì)算,66,Isomap,LLE,LLE (局部線性嵌入) Roweis et al., 2000,Sam T. Roweis, Lawrence K.Saul. Nonlonea