浅谈特征选择的原理和实现

2024-03-27 20:27:22

0.引言

在现实世界中，我们总是倾向于收集尽可能多的特征来描述一个事物，以期能够更加全面准确的对其进行刻画。然而，我们了解事物的目的是变化着的，所以并非每一次对事物的刻画都需要所有特征。例如在机器学习领域众所周知的西瓜，描述西瓜的特征有很多，包括：大小、色泽、敲声、纹理、触感、根蒂等。了解西瓜的目的，即学习任务，也各不相同：好吃、好闻、好看等。显然，若学习任务是判断一个西瓜是否好看，则只需要大小、色泽、纹理等特征即可，这些特征即是“相关特征”。若需求为判断西瓜是否好吃，有经验的人只需要根蒂、敲声即可挑出好瓜，其他的特征则为“无关特征”。故对应于不同的学习任务，不同特征的重要性不同，从所有特征构成的特征集中选取对学习任务有用的相关特征的过程就称为特征选择。
如果我们不对特征进行选择，使用全部的特征，能否在只是付出更多的时间和资源代价的情况下完成学习任务呢？答案是不一定。特征选择是“数据预处理”过程的重要组成部分，其不仅筛选出完成学习任务所需的最少特征，还出于两个很重要的原因。其一是避免维度灾难，如果使用特征数量过多、样本数又不够，则可能带来过拟合等问题，所以需要构筑基于部分特征的模型。特征选择和降维在这一点上有相同的动机，使他们成为高维数据处理的两大主流技术。其二因为特征选择能够去除不相关特征，只留下关键因素，有利于我们在纷繁的因素中抽丝剥茧，看清事物的真相，例如房价和那些因素相关性最大。

1. 子集搜索

如想从初始的数据集中选取一个包含所有重要信息的特征子集，如果没有任何领域知识作为先验假设，则最好的办法就是遍历所有可能的特征子集，也称为暴力破解。显而易见，随着特征数量的增加，计算量终将无法招架，除非在量子计算机或其他非传统计算机领域有重大突破，在现实应用中很难使用这种方法。

相对而言，“贪心算法”则可操作性较强，基本流程如下所述。对于给定的特征集合 { a 1 , a 2 , . . . , a d } \{a_{\tiny 1},a_{\tiny 2},...,a_{\tiny d} \} {a1,a2,...,ad}，首先将每个特征看做一个候选子集，对这d个候选子集进行评价，即对比单个特征对数据的分类效果。以人体为例，包含有身高、体重、肤色、发色等诸多特征，若学习的目的是对人种进行分类，则利用每一个特征（身高、体重、肤色、发色等）对数据进行分类（不同的人种），在通过数据真实标签对比就可以选出分类效果最好或者说分类结果最纯的特征。假定特征 { a 2 } \{a_{\tiny 2}\} {a2}最优，将 { a 2 } \{a_{\tiny 2}\} {a2}作为第一轮的选定集；然后在此基础上加入另一个特征，构成包含两个特征的特征集合，按照同样的方法对特征集合进行评价，假设集合 { a 2 , a 4 } \{a_{\tiny 2},a_{\tiny 4}\} {a2,a4}为最优，其优于 { a 2 } \{a_{\tiny 2}\} {a2}，于是将 { a 2 , a 4 } \{a_{\tiny 2},a_{\tiny 4}\} {a2,a4}作为本轮的选定集。假设递归至k+1轮时，最优的候选 ( k + 1 ) (k+1) (k+1)特征子集不如上一轮的选定集，则停止生成候选子集，并将上一轮选定的包含k个特征的特征子集作为特征选择结果。这种从一个特征开始的策略称为“前向（forward）搜索”。相反，如果我们从整个特征集合出发，每一轮尝试筛选出一个无关特征，这样逐渐减少的策略称为“后向（backward）搜索”。又或者，还可以将前向和后向搜索结合起来，每一轮逐渐增加相关特征同时减少无关特征，称为“双向搜索”。

由于仅考虑了使本轮选定集最优而无法筛选出全局最优，此种策略故被称为贪心算法。贪心算法并不能涵盖所有可能的可能，只能保证当前利益的最大化，若要获得全局最优只能通过穷举遍历才可行。虽然不能获得绝对的最优解，但贪心算法能够得到解决大对数问题的次优解。类似的有序列向后选择算法（Sequential backward Selection，SBS），其大致流程是先用所有特征训练一个分类器并得到分类器的某种性能度量（MSE、准确度等），然后每次去掉一个特征再训练一个分类器，若去除的是无关特征，则性能变化不大甚至可能还会有所提升，反之可能使性能下降。

2.信息熵

2.1 定义

熵来自于物理学，被称为信息论之父的香农证明了熵与信息内容的不确定性有等价关系。熵是描述物质系统状态，即该状态可能出现的程度。简单的讲，熵用以描述事物无序的状态，越混乱无序的事物熵越大，越确定有序的事物熵越小。熵的一个重要作用就是度量系统的平均信息量，即传递该信息所用的代价。例如：太阳从东方升起，正是一个确定性事件，其熵为0，意味着若要传递该信息，无需进行任何编码。根据定义，若一个系统中存在多个事件 E 1 , E 2 , . . . , E n E_{\tiny 1},E_{\tiny 2},...,E_{\tiny n} E1,E2,...,En，每个事件出现的概率为 p 1 , p 2 , . . . , p n p_{\tiny 1},p_{\tiny 2},...,p_{\tiny n} p1,p2,...,pn，则系统的平均信息量为：
e n t r o p y ( p 1 , p 2 , . . . , p n ) = − p 1 l o g 2 p 1 − p 2 l o g 2 p 2 . . . − p n l o g 2 p n ( b i t s ) entropy(p_{\tiny 1},p_{\tiny 2},...,p_{\tiny n}) = -p_{\tiny1}log_{\tiny 2}{p_{\tiny 1}}-p_{\tiny2}log_{\tiny 2}{p_{\tiny 2}}...-p_{\tiny n}log_{\tiny 2}{p_{\tiny n}}^(bits) entropy(p1,p2,...,pn)=−p1log2p1−p2log2p2...−pnlog2pn(bits)

例如，某事件有四种可能{A，B，C，D}，其发生的概率分别为{1/2，1/4，1/8，1/8}，假设某一种可能发生视为随机变量 X ∈ { A , B , C , D } X\in\{A,B,C,D\} X∈{A,B,C,D}，利用信息熵额定义，得到该事件的信息熵为：
H ( x ) = 1 2 l o g ( 2 ) + 1 4 l o g ( 4 ) + 1 8 l o g ( 8 ) + 1 8 l o g ( 8 ) = 1 2 + 1 2 + 3 8 + 3 8 = 7 4 b i t H(x)=\frac{1}{2}log(2)+\frac{1}{4}log(4)+\frac{1}{8}log(8)+\frac{1}{8}log(8)=\frac{1}{2}+\frac{1}{2}+\frac{3}{8}+\frac{3}{8}=\frac{7}{4}bit H(x)=21log(2)+41log(4)+81log(8)+81log(8)=21+21+83+83=47bit
这也就意味着，在计算机中，若要对该事件进行二元（0/1）编码，所需要的平均码长即为1.75比特。

同时，信息熵也是度量集合纯度的一个指标。集合中数据的真实标签全为一个类别时纯度最高，相应的信息熵就越低。假设当前样本集合D中k类样本所占比例为 p k ( k = 1 , 2 , . . . , n ) p_k(k=1,2,...,n) pk(k=1,2,...,n)，则D的信息熵定义为：
E n t ( D ) = − ∑ k = 1 n p k l o g 2 p k Ent(D)=-\sum_{k=1}^{n}p_klog_2p_k Ent(D)=−k=1∑npklog2pk
Ent值越小，则集合D的纯度越高。

2.2 信息增益

就特征选择而言，如果按照某个特征（属性）对对数据集进行划分后，能够提高数据纯度，则可以认为该特征对分类任务是有意义的。由于信息熵反应了数据集合的混乱程度，通过比较数据划分后信息熵的变化，就得到了所谓的信息增益。

假设离散属性 a a a有 V V V个可能的取值 a 1 , a 2 , . . . , a V {a^1,a^2,...,a^V} a1,a2,...,aV，若使用 a a a对样本集合D进行划分，则会产生 V V V个分支节点， D v D^v Dv表示数据集D中所有在属性 a a a上取值为 a v a^v av的样本集合。我们可以按照前文所述的方法计算出 D v D^v Dv的信息熵。此外，考虑到不同 D v D^v Dv所包含的样本数量不同，对各个 D v D^v Dv的信息熵加权平均再与原有数据集D的信息熵相减便得到了用属性a对数据集D进行划分所获得的“信息增益”。
G a i n ( D , a ) = E n t ( D ) − ∑ v = 1 V ∣ D v ∣ ∣ D ∣ E n t ( D v ) Gain(D,a)=Ent(D)-\sum_{v=1}^{V}\frac{|D^v|}{|D|}Ent(D^v) Gain(D,a)=Ent(D)−v=1∑V∣D∣∣Dv∣Ent(Dv)
一般而言，信息增益越大，意味着按照属性a对数据集D进行划分对数据集“纯度”的提升越大，也就是该属性包含的有助于数据分类的信息越多、越值得保留。决策树等树的模型可利用信息增益对特征的重要性进行排序，进而达到特征选择的目的。

同样，对于包含一个或多个属性的属性子集 A A A，假定根据其取值将D分为V个子集 { D 1 , D 2 , . . . , D V } \{D^1,D^2,...,D^V\} {D1,D2,...,DV}，则属性子集 A A A的信息增益为
G a i n ( A ) = E n t ( D ) − ∑ v = 1 V ∣ D v ∣ D E n t ( D v ) Gain(A)=Ent(D)-\sum_{v=1}^{V}\frac{|D^v|}{D}Ent(D^v) Gain(A)=Ent(D)−v=1∑VD∣Dv∣Ent(Dv)
同理信息增益越大，则特征子集A包含的有助于分类的信息越多，可以作为评价特征子集的标准。

3.过滤式特征选择

对于每一个特征子集A，其都对应了对数据集D的一种划分，通过对比该划分和样本真实标记所对应的划分之间的差异，就能对A进行评价。前文所述的基于信息熵的方法仅是一种评价特征子集的方法。

过滤式方法是先对数据进行特征选择，然后再训练学习器，特征选择过程与后续学习器无关，相当于先用特征选择过程对初始特征进行“过滤”，再用过滤后的特征来训练模型。

相关特征（Relief）是一种早期常用的过滤式特征选择方法，该方法设计了一种相关统计量来度量特征的重要性。该统计量是一个向量，其每个分量分别对应一个初始特征，特征子集的重要性则是由子集中每个特征所对应的相关统计量之和来决定。对于二分类情况，训练集 { ( x 1 , y 1 ) , ( x 2 , y 2 ) , . . . , ( x m , y m ) } \{(x_1,y_1),(x_2,y_2),...,(x_m,y_m)\} {(x1,y1),(x2,y2),...,(xm,ym)}，对于样本 x i x_i xi，Relief算法先在其同类样本中寻找最近邻 x i , n h x_{i,nh} xi,nh，即“猜中（near-hit）近邻”，所使用的度量可以是欧氏距离、余弦相似度等。再从不同类样本中寻找最近邻 x i , n m x_{i,nm} xi,nm，即“猜错（near-miss）近邻”。则对应于属性 j j j的相关统计量为：
δ j = ∑ i [ − d i f f ( x i j , x i , n h ) 2 + d i f f ( x i j , x i , n m ) 2 ] \delta^j=\sum_{i}[-diff(x_i^j,x_{i,nh})^2+diff(x_i^j,x_{i,nm})^2] δj=i∑[−diff(xij,xi,nh)2+diff(xij,xi,nm)2]

其中 x i j x_i^j xij表示样本 x i x_i xi在属性 j j j上的取值， d i f f ( a j , b j ) diff(a^j,b^j) diff(aj,bj)可以理解为两个样本在属性 j j j上的距离，若属性 j j j为离散值，则当 a j = b j a^j=b^j aj=bj时，其值为0，否则为1。若属性 j j j为连续值，先将属性值规范到 [ 0 , 1 ] [0,1] [0,1]区间，则 d i f f ( a j , b j ) = ∣ a j − b j ∣ diff(a^j,b^j)=|a^j-b^j| diff(aj,bj)=∣aj−bj∣。

如果一个属性对数据分类效果较好，则会呈现类内距离小、类间距离大的态势，对应上式中则是与猜错近邻距离 d i f f ( x i j , x i , n m ) 2 diff(x_i^j,x_{i,nm})^2 diff(xij,xi,nm)2较大，与猜中近邻距离 d i f f ( x i j , x i , n h ) 2 diff(x_i^j,x_{i,nh})^2 diff(xij,xi,nh)2较小，故该属性的相关统计量 d e l t a delta delta也较大。反之，如果某个属性所包含的有助于分类的信息较少，则在该属性上与猜错近邻距离小于与猜中近邻的距离。通过比较不同属性所对应的相关统计量，即可实现对属性重要性的排名。

相关统计量（Relief）最早是针对二分类情况设计的，若扩展至多分类情况，假设数据集 D D D中的样本有 ∣ y ∣ |y| ∣y∣个类别。对于样本 x i x_i xi，若它属于第k类 ( k ∈ { 1 , 2 , . . . , ∣ y ∣ } ) (k\in\{1,2,...,|y|\}) (k∈{1,2,...,∣y∣})，则现在第 k k k类中寻找 x i x_i xi的最近邻 x i , n h x_{i,nh} xi,nh，并将其作为猜中近邻。然后在第k类之外的每一类中寻找一个 x i x_i xi的最近邻 x i , l , n m ( l = 1 , 2 , . . . , ∣ y ∣ ; l ≠ k ) x_{i,l,nm} (l=1,2,...,|y|;l\ne k) xi,l,nm(l=1,2,...,∣y∣;l=k)作为猜错近邻。此时对应于属性 j j j的相关统计量为：
δ j = ∑ i [ − d i f f ( x i j , x i , n h j ) 2 + ∑ l ≠ k ( p l × d i f f ( x i j , x i , l , n m j ) 2 ) ] \delta^j=\sum_i[-diff(x_i^j,x_{i,nh}^j)^2+\sum_{l\ne k}(p_l\times diff(x_i^j,x_{i,l,nm}^j)^2)] δj=i∑[−diff(xij,xi,nhj)2+l=k∑(pl×diff(xij,xi,l,nmj)2)]

其中 p l p_l pl为第 l l l类样本在数据集D中所占的比例。随机森林（RF）、梯度提升树（GBDT）和Xgboost也都可以进行特征选择，利用各自的特征排序算法对所有特征进行排序。用户可以根据阈值进行选择，也可以根据数量选择部分进行测试分类或回归的具体性能。

4.包裹式特征选择

过滤式特征选择使用一定的规则来度量每一个特征的重要性，以不同特征对数据分割结果与数据真实分类相似程度为依据对特征进行排序，再选择所需的特征子集对数据进行分类或回归。不同于过滤式选择不考虑后续学习器，包裹式选择直接把最终将要使用的学习器性能作为特征子集的评价标准，即包裹式特征选择的目的就是为给定学习器选择最有利于其性能的特征子集，所以相较过滤式特征选择方法具有更好的效果。

当然，任何事物都都逃不开两面性法则，虽然包裹式方法能获得较好的特征选择效果，但由于需要多次训练学习器，包裹式特征选择的计算开销也远高于滤式特征选择。

LVW（Las Vegas Wrapper）是一种典型的包裹式特征选择方法，它在拉斯维加斯方法框架下使用随机策略进行子集搜索，并以最终分类器的误差作为特征子集的评价标准。分类器的误差可以使用准确率（accuracy）或是交叉熵。需要注意的是，准确率并不总能很好的度量分类效果，例如过拟合情况下，验证集的准确率就相当高。算法描述伪代码如下：

输入：数据集 D 数据集D 数据集D
   特征集 A \qquad\space\space特征集A   特征集A
   学习算法 ξ \qquad\space\space学习算法\xi   学习算法ξ
   停止条件控制参数 T \qquad\space\space停止条件控制参数T   停止条件控制参数T

过程：
\space 1： E = ∞ ; E=\infty; E=∞;
\space 2： d = ∣ A ∣ ; d=|A|; d=∣A∣;
\space 3： A ∗ = A ; A^*=A; A∗=A;
\space 4： t = 0 ; t=0; t=0;
\space 5： w h i l e t < T d o while \space { t<T} \space do while t<T do
\space 6：随机产生特征子集 A ′ \qquad随机产生特征子集A' 随机产生特征子集A′;
\space 7： d ′ = ∣ A ∣ ; \qquad d'=|A|; d′=∣A∣;
\space 8： E ′ = C r o s s V a l i d a t i o n ( ξ ( D A ′ ) ) \qquad E'=CrossValidation(\xi(D^{A'})) E′=CrossValidation(ξ(DA′))
\space 9： i f ( E ′ < E ) ⋁ ( ( E ′ = E ) ⋀ ( d ′ < d ) ) t h e n \qquad if(E'<E)\bigvee ((E'=E)\bigwedge(d'<d)) \space then if(E′<E)⋁((E′=E)⋀(d′<d)) then
10： t = 0 ; \qquad\qquad t=0; t=0;
11： E = E ′ ; \qquad\qquad E=E'; E=E′;
12： d = d ′ ; \qquad\qquad d=d'; d=d′;
13： A ∗ = A \qquad\qquad A^*=A A∗=A
14： e l s e \qquad else else
15： t = t + 1 \qquad\qquad t=t+1 t=t+1
16： e n d i f \qquad end \space if end if
17： e n d w h i l e end \space while end while
输出：特征子集 A ∗ A^* A∗

伪代码第8行表示通过在数据集D上，使用特征子集 A ′ A' A′和交叉验证法来估计学习器 ξ \xi ξ的误差，若其比当前特征子集 A A A的误差更小或误差相同但所包含的特征数量更少，则将 A ′ A' A′保留并进入下一次循环，直到满足设定的循环次数。

LVW算法每次特征子集的评价都需要训练学习器，计算开销大、耗时较长。此外，算法的特征搜索采用随机策略，如果初始特征数量较多（即 ∣ A ∣ |A| ∣A∣很大）、停止条件T设置较大，则可能在有限时间内无法得出结果。

5. 嵌入式特征选择

过滤式特征选择是利用某种统计方法对特征进行排序，选择所需的特征子集，再进行训练和测试。包裹式特征选择采用暴力随机的方式，用选择的特征子集训练学习器并评价其性能，最后选取性能较好的一个子集，从而实现特征选择。两者的共同之处在于特征选择过程与学习器训练过程有明显分别，而嵌入式特征选择是将特征选择过程与学习器训练过程融为一体，即在学习器训练过程中完成对特征子集的优化。

对于给定的数据集 D = { ( x 1 , y 1 ) , ( x 2 , y 2 ) , . . . , ( x m , y m ) } D=\{(x_1,y_1),(x_2,y_2),...,(x_m,y_m)\} D={(x1,y1),(x2,y2),...,(xm,ym)},其中 x ∈ R d x\in R^d x∈Rd，考虑最简单的线性回归模型，以平方误差为损失函数，则优化目标为：
m i n ω ∑ i = 1 m ( y i − ω T x i ) 2 \underset{\omega}{min}\sum_{i=1}^m(y_i-\omega^Tx_i)^2 ωmini=1∑m(yi−ωTxi)2

当特征数量较多而样本数量较少时，很容易出现过拟合。为了避免此类情况，可以使用正则化方法。在线性回归中，通过正则化可以有效限制权重。使用 L 1 L_1 L1范数正则化时，为一阶正则化，又称“lasso回归”，优化目标为：
m i n ω ∑ i = 1 m ( y i − ω T x i ) 2 + λ ∣ ∣ ω ∣ ∣ 1 \underset{\omega}{min}\sum_{i=1}^m(y_i-\omega^Tx_i)^2+\lambda||\omega||_1 ωmini=1∑m(yi−ωTxi)2+λ∣∣ω∣∣1
其中正则化参数 λ > 0 \lambda>0 λ>0。使用 L 2 L_2 L2范数正则化时，为二阶正则化，又称“岭回归”，优化目标为：
m i n ω ∑ i = 1 m ( y i − ω T x i ) 2 + λ ∣ ∣ ω ∣ ∣ 2 2 \underset{\omega}{min}\sum_{i=1}^m(y_i-\omega^Tx_i)^2+\lambda||\omega||_2^2 ωmini=1∑m(yi−ωTxi)2+λ∣∣ω∣∣22
同样，其中 λ > 0 \lambda>0 λ>0。使用Lasso回归和岭回归都可以有效的降低过拟合的风险，其中Lasso回归更为常用。

除了可以防止过拟合， L 1 L_1 L1相较 L 2 L_2 L2范数正则化力度更大，可以将权重各分量降到很小甚至是0，从而更容易获得“稀疏解”，即它求得的 ω \omega ω（向量）中会有更多的0或接近0的分量。

为何 L 1 L_1 L1较 L 2 L_2 L2范数更易得到稀疏解呢？以 ω \omega ω为2维向量为例， L 1 L_1 L1和 L 2 L_2 L2正则化求解的问题可以表述为：
L 1 R e g u l a t i o n : m i n ω E i n ; s . t . ∑ i ∣ ω i ∣ < C L 2 R e g u l a t i o n : m i n ω E i n ; s . t . ω T ω < C L_1Regulation:\underset{\omega}{min}E_{in};s.t.\sum_i|\omega_i|<C \newline L_2Regulation:\underset{\omega}{min}E_{in};s.t.\omega^T\omega<C \space\space\space\space\space L1Regulation:ωminEin;s.t.i∑∣ωi∣<CL2Regulation:ωminEin;s.t.ωTω<C
将其表示成图则如下：

左右两图中原点周围的黄色圆形和菱形区域就对应了 L 2 L_2 L2和 L 1 L_1 L1范数的约束空间，需要在这个区域内寻找最优解。在约束空间上方的同心圆为不同损失函数在权值二维空间的投影而形成的等高线，其中心点即为代价函数最小处。从图中可看出，损失函数最小时，权值可能远离原点，若推广至多维空间则可能是过拟合的情况。范数正则化的使用使得只能在约束空间中寻找使代价函数最小的点。相对于圆形，菱形约束区域的优势在于最先和等高线接触的大概率是位于数轴的顶点（也可能出现相切的情况），使得部分权值为0，从而达到使损失函数尽量小同时稀疏化的目的。

6. 稀疏表示与字典学习

通过上文我们知道，过滤式特征选择是同一些度量手段来衡量特征的重要性，从而对特征进行取舍；包裹式特征选择实质一种通过暴力搜索方式，利用穷举方法来寻找最佳的特征组合；而嵌入式特征选择是利用在机器学习方法本身中加入一些稀疏化技术，使得一些特征无效。

如果把数据集D考虑为一个矩阵，其中每行对应一个样本，每列对应一个特征。在实际应用中，矩阵中许多列可能与当前学习任务无关，如能通过相关的方法去除这些列，实现矩阵“稀疏化”（即与学习任务无关的数据用0表示），则可降低学习任务的难度，减少计算和存储的开销，并使学得模型的可解释性提高。例如如下矩阵：
[ 1 0 1 2.3 0 1.01 5 0 0.09 ] \begin{bmatrix} 1 & 0 & 1\\ 2.3 & 0 & 1.01 \\ 5& 0 & 0.09 \\ \end{bmatrix} ⎣⎡12.3500011.010.09⎦⎤
其中第二列所代表的的属性值全为0（或者是几乎全为0），对于样本的分类或回归没有意义。第三列数据虽然不为0，但相当于其均值而言方差太小，无法度量差异性，也认为没有意义。

然而在现实世界中更常出现的情况是：数据集D所对应的矩阵中存在很多0元素，但是这些0元素并不是以整列、整行的形式存在的。例如在自然语言编码任务中频繁采用的词袋模型，通常将每个文档看做一个样本，每个字（或词）作为一个特征，每个字在文档中出现的频率或次数作为特征的取值。此时，矩阵的行数就是文档的数量，而列数则是“词典”（包含所有可能出现的字或词）的大小，行、列交汇处则是某字在某个文档中出现的频率或次数。以汉语为例，《康熙词典》中有4万多个汉字，《现代汉语常用字表》中有3500多个常用字。然而，在特定文档中，相当多的字是不会出现的，若使用词袋模型对文档进行处理，则会得到一个列数至少3500以上、每一行还在不同位置包含有大量0元素的矩阵。

例如对《红楼梦》120回文档进行分析，首先使用分词工具（例如jieba）对120回全文进行分词，得到长度为4万多、一个包含文中所有出现过的字或词的“字典”。若将每一回看做一个特征向量，则该向量的长度也是4万多，最终得到矩阵非常稀疏。

当样本具有这样的稀疏表示时，对学习任务来说有不少好处，例如在深度学习出现之前，线性支持向量机（SVM）之所有能够在文本数据上有较好的性能，就是因为文本数据在使用上述词袋模型之类统计模型后具有高度的稀疏性，使大多数问题变得线性可分，同时，稀疏样本由于存在许多高效的存储方法，因此并不会造成存储上的巨大负担。

若给定的数据集D是普通的非稀疏数据，能否将其转化为恰当的稀疏表示呢？首先需要获得一个适当的“字典”。还是以汉语为例，假设文档中的词汇都是常见字，使用《现代汉语常用词表》即可覆盖，从而得到一个尺寸和稀疏程度适中的矩阵，那就没有必要使用《康熙字典》获取一个大得多也稀疏得多矩阵，过度稀疏对学习任务并无更多好处。此外，在一般学习任务中（例如图像学习），并没有现成的“字典”可用，需要为普通稠密编码找到合适的字典，得到用以转化的矩阵，称为“字典学习”。如上文中所述使用分词工具对《红楼梦》全文分词获得其中所有出现的字和词的过程。利用“字典”转化样本获得稀疏表示的过程就称为“稀疏编码”，反推可知，使用稀疏矩阵乘以字典矩阵即可还原稠密矩阵。

对于给定的数据集 { x 1 , x 2 , . . . , x m } \{x_1,x_2,...,x_m\} {x1,x2,...,xm}，字典学习最简单的形式为：
m i n B , α i ( ∑ i = 1 m ∣ ∣ x i − B α i ∣ ∣ 2 2 + λ ∑ i = 1 m ∣ ∣ a i ∣ ∣ 1 ) \underset{B,\alpha_i}{min}\left( \sum_{i=1}^m||x_i-B\alpha_i||_2^2+\lambda\sum_{i=1}^m||a_i||_1\right) B,αimin(i=1∑m∣∣xi−Bαi∣∣22+λi=1∑m∣∣ai∣∣1)

其中样本为 x i ∈ R d x_i\in R^d xi∈Rd， B ∈ R d × k B\in R^{d \times k} B∈Rd×k为字典矩阵，其列数 k k k即为字典矩阵的词汇量， α i ∈ R k \alpha_i\in R^k αi∈Rk则是样本 x i x_i xi的稀疏表示。明显可知，式子第一项是希望得到一个能够很好重构 x i x_i xi的 α i \alpha_i αi，第二项是希望 α i \alpha_i αi足够稀疏，其中各分量足够小。字典学习是有损失的学习，希望得到的差值越小越好。与一阶正则化类似，其中的Lasso范式会导致大量的参数接近于0。一般来说，稀疏表示之后特征数量会增加。

7.代码实例：Python库特征选择方法

7.1 过滤式特征选择

7.1.1 方差选择法

Pyhton库中自带方差选择法，其基本原理就是通过各个特征的方差来筛选特征，剔除波动值较小的特征。实际情景中，进行实现特征选择。

以葡萄酒数据为例，首先从文件中读取数据，将数据保存在功能强大的dataframe表格结构中（其中封装了常用的mean()、shape()、info()等方法），并设置属性名：

import pandas as pd

wine_data = 'd:/data/wine.data'
df_wine = pd.read_csv(wine_data, header=None)
df_wine.columns = ['Class label', 'Alcohol', 'Malic acid', 'Ash',
    'Alcalinity of ash', 'Magnesium', 'Total phenols',
    'Flavanoids', 'Nonflavanoid phenols', 'Proanthocyanins',
    'Color intensity', 'Hue', 'OD280/OD315 of diluted wines',
    'Proline']
df_wine.info()

其中的info()方法可以对数据进行初步统计，返回属性数据类型、数量、是否为空值等信息。

from sklearn.feature_selection import VarianceThreshold
var = VarianceThreshold(threshold=1)
var.fit_transform(df_wine)
var.get_support(True)

s k l e a r n sklearn sklearn库中的方差选择方法使用如上述代面所示，导入后直接调用即可，其中参数threshold为阈值，即获取方差大于该值的属性。 g e t _ s u p p o r t ( ) get\_support() get_support()方法用于获取满足阈值条件的属性值，且使用方式灵活，当参数设置为True时，返回方差大于1的属性值；参数设置为False时，返回方差小于1的属性值。

7.1.2 相关系数法

相关系数的定义如下：
ρ = C o v ( X , Y ) δ X δ Y \rho=\frac{Cov(X,Y)}{\delta_X\delta_Y} ρ=δXδYCov(X,Y)
相关系数可以认为是一种剔除了两个变量量纲影响，标准化之后的特殊协方差，其可以反映两个变量变化时时同向还是反向的，以及消除变量变化幅度后（标准化后），每单位变量变化的相似程度。

皮尔森（pearson）相关系数衡量的是变量之间的线性相关性，取值范围为[-1,1]，1表示完全正相关，-1表示完全负相关，0表示线性无关。使用scipy中的pearson()方法就可以计算pearson相关系数。皮尔森相关系数的缺点在于只能衡量线性相关，即使两个变量之间有很明显的非线性关系（幂次关系等），其皮尔森系数也是0。

在dataframe数据结构中已经包含了corr()方法用以获取pearson相关系数，直接调用即可：

df_wine.corr()

其返回值是一个属性相关系数的矩阵，一般认为相关系数超过0.5相关性就比较大。

#                               Class label    ...      Proline
# Class label                      1.000000    ...    -0.633717
# Alcohol                         -0.328222    ...     0.643720
# Malic acid                       0.437776    ...    -0.192011
# Ash                             -0.049643    ...     0.223626
# Alcalinity of ash                0.517859    ...    -0.440597
# Magnesium                       -0.209179    ...     0.393351
# Total phenols                   -0.719163    ...     0.498115
# Flavanoids                      -0.847498    ...     0.494193
# Nonflavanoid phenols             0.489109    ...    -0.311385
# Proanthocyanins                 -0.499130    ...     0.330417
# Color intensity                  0.265668    ...     0.316100
# Hue                             -0.617369    ...     0.236183
# OD280/OD315 of diluted wines    -0.788230    ...     0.312761
# Proline                         -0.633717    ...     1.000000

除了pearson相关系数外，还有spearman和kendall相关系数较为常用。其中kendall相关系数能够处理离散型的特征。使用时，在corr()方法中加入参数‘spearman’和‘kendall’即可。

7.1.3 卡方检验法

卡方检验是一种用途很广的计数资料的假设检验方法。它属于非参数检验的范畴，主要是比较两个及两个以上样本率( 构成比）以及两个分类变量的关联性分析。其根本思想就是在于比较理论频数和实际频数的吻合程度或拟合优度问题。具体原理可参见：卡方检验和卡方分布。

利用卡方检验方法可以在特征集中筛选出没有相关性的特征。同样，在sklearn中集成有该方法。以鸢尾花数据为例，按照惯例，首先读取并观察数据：

from sklearn.feature_selection import chi2
from sklearn.feature_selection import SelectKBest
from sklearn.datasets import load_iris

idata= load_iris()
idata.data.shape

运行结果如下，数据集有150组数据，每组数据有4个特征。

(150, 4)

通过SelectKBest()方法对样本进行卡方检验。

model = SelectKBest(chi2, k=2)
model.fit_transform(idata.data, idata.target)
model.get_support(True)

按照官方注释，SelectKBest()方法用于获取按照某种规则打分后，得分最高的k个属性值，上述代码中第一个参数“chi2”表示使用卡方检验方法对数据属性进行打分排名，第二个参数k=2即表示需要返回得分最高的两个属性。同7.1.1中的描述类似，get_support(True)方法用以返回所筛选出的属性序号。程序运行后返回值为：

[2 3]

意味着原数据集中的4个特征，经过卡方检验排序、去掉相关性最强的两个属性后，得到了序号为2和3的两个属性。再以葡萄酒数据为例，由于fit_transform()方法中要求输入参数为数组类型，需要对数据类型进行转换：

cols = list(df_wine.columns)
cols.remove('Class label')
X = df_wine[cols].values
y = df_wine['Class label'].values
# 使用卡方检验的方法筛选3个属性
model2 = SelectKBest(chi2, k=3)
model2.fit_transform(X,y)
model2.get_support(True)

输出为：

[ 6  9 12]

7.1.4 互信息法和最大信息系数

互信息法是评价定性自变量对定性应变量的相关性的，但是并不方便用于特征选择，一是应为它不属于度量方法，也没有办法进行归一化，在不同数据上无法做比较；二是因为对于连续变量的计算不是很方便，通常需要将变量离散化，而互信息的结果对于离散化的方法很敏感；因此引入了最大信息系数。最大信息系数首先要寻找一种最优的离散方式，然后把互信息取值转换为一种度量方式，取值区间在[0,1]，minepy是一个用于数据挖掘的模块，其中提供了最大信息系数（MIC）方法。

minepy包无法在线安装，需要下载后再安装。下载地址为：https://www.lfd.uci.edu/~gohlke/pythonlibs/，下载64位版本的文件minepy-1.2.3-cp36-cp36m-win_amd64.whl，利用命令pip install *.whl安装即可。示例代码如下：

from scipy.stats import pearsonr
from minepy import MINE   
import numpy as np 

x = np.random.normal(0,10,300)
z = x * x
print(pearsonr(x,z))

首先产生一个由300个均值为1、标准差为10的正态分布随机随机数组成的数组x，再生成一个与其成平方关系的数组z。运行输出如下：

(0.0290666676712168, 0.6160518667315499)

第一个数字即为两个数组的相关系数，其远小于1，再一次说明相关系数并不能度量非线性相关性。使用最大信息系数方法：

m = MINE()    
m.compute_score(x, z)
print(m.mic())

运行输出如下，说明两组数据100%相关。

1.0000000000000002

7.2 包裹式特征选择

sklearn中集成了一种名为递归特征消除（RFE）的特征选择方法，其通过对特征子集的暴力网格搜索，结合特定的学习器，寻找最好的子集。代码如下：

from sklearn.feature_selection import RFE
from sklearn.linear_model import LogisticRegression

#使用逻辑回归的方法作为选择标准
model = LogisticRegression() 
# 遍历3个特征的组合，选择评价最高的3个特征的组合
rfe = RFE(model, 3)
rfe = rfe.fit(X,y)
# 表示选择的特征，True表示选择的特征
rfe.support_
# 重要性排序
rfe.ranking_

运行结果如下，其中为True的位置表示对应特征所构成的特征子集为采用逻辑回归方法作为选择标准时的最佳组合。

[False False False False False False  True False False  True  True False
 False]
 [ 9  5  2  4 10  8  1  7  6  1  1  3 11]

7.3 嵌入式特征选择

L1、L2正则化时典型的嵌入式特征选择方法，sklearn中的使用方法如下，以前文中数组化的葡萄酒数据为例，首先对Label进行编码，使其从0开始索引：

from sklearn.preprocessing import LabelEncoder
le = LabelEncoder()
y = le.fit_transform(y)

然后在数据进行标准化操作：

from sklearn.preprocessing import StandardScaler
# 数据标准化
scaler = StandardScaler()
X = scaler.fit_transform(X)

以Lasso回归（即L1）为例，新建Lasso对像所设置的参数即为惩罚系数，值越大惩罚力度越大，意味特征权重中出现更多的0：

from sklearn.linear_model import Lasso
lasso = Lasso(0.2)
lasso.fit(X,y)
# 显示特征的权重系数，0的位置表示特征可以去除
lasso.coef_

运行结果为：

[-0.          0.          0.          0.01520731 -0.         -0.
 -0.27723978  0.         -0.          0.         -0.0161898  -0.14752854
 -0.09609586]

若采用岭回归（即L2）：

from sklearn.linear_model import Ridge
ridge = Ridge(0.2) 
ridge.fit(X,y)
ridge.coef_