特征选择

子集搜索与评价

给定属性集，其中有些属性可能很关键、很有用，另一些属性则可能没什么用。对当前学习任务有用的属性称为相关特征(relevant feature)，无用的属性称为无关特征(irrelevant feature)。**特征选择(feature selection)**是一个重要的数据预处理过程，指从给定的特征集合中选择出相关特征的子集的过程。特征选择能够减少维数灾难问题，同时降低学习任务的难度。

如果我们想从特征集合中选区一个包含了所有重要信息的特征子集，如果我们没有任何先验知识，那么就只能遍历可能的子集，这会带来很高的计算复杂度；可行的一种做法是先产生一个“候选子集"，评价它的好坏，然后在此基础之上产生下一个子集。这里涉及到两个关键环节，一是如何根据评价结果选择下一个候选子集，二是如何评价子集的好坏。

第一个环节是子集搜索(subset search)，给定特征集合${a_1,a_2,\cdots,a_d}$，可以将每个单独的特征看作一个候选子集，对这$d$个候选单特征子集进行评定，假如${a_2}$最优，那么我们就把${a_2}$作为第一轮的选定集；然后，在上一轮选定集中加入一个特征，构成两个特征的候选子集，我们假定${a_2,a_4}$最优且优于${a_2}$，那么我们就得到了新的候选子集，以此类推。这是一种前向搜索。我们也可以从完整的属性集合开始，每次去掉一个无关特征，这样的方法叫后向搜索。还可以将前向和后向搜索结合起来进行双向搜索。显然，该策略是贪心的。

$$ \operatorname{Gain}(A)=\operatorname{Ent}(D)-\sum_{v=1}^{V} \frac{\left|D^{v}\right|}{|D|} \operatorname{Ent}\left(D^{v}\right) $$$$ \operatorname{Ent}(D)=- \sum_{k=1}^{|\mathcal Y|}p_k\log_2p_k $$

信息增益越大，意味着特征子集$A$包含的有助于分类的信息更多。于是，对每个候选特征子集，我们可基于训练数据$D$来计算其信息增益，以此作为评价准则。

更一般地，特征子集$A$实际上确定了对数据集$D$的一个划分，每个划分区域对应着$A$上的一个取值，而样本标记信息$Y$则对应着对$D$的真实划分，通过估算这两个划分的差异，就能对$A$进行评价。与$Y$对应的划分的差异越小，则说明$A$越好。信息熵仅是判断这个差异的一种途径，其他能判断两个划分差异的机制都能用于特征子集评价。

将特征子集搜索机制与子集评价机制相结合，即可得到特征选择方法。例如，将前向搜索与信息熵相结合，这与决策树算法非常相似。事实上，决策树可用于特征选择，树结点的划分属性组成的集合就是选择出的特征子集。其他的特征选择方法未必像决策树特征选择这么明显，但其本质上都是显式或隐式地结合了子集搜索和子集评价机制。

常见的特征选择方法大致可分为三类：过滤式(filter)、包裹式(wrapper)和嵌入式(embedding)。

过滤式选择

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

Relief是一种著名的过滤式选择方法，该方法设计了一个“相关统计量”来度量特征的重要性。该统计量是一个向量，其每个分量分别对应于一个初始特征，而特征子集的重要性则是由子集中每个特征锁对应的相关统计量分量之和来决定。于是，最终只需指定一个阈值，然后选择比该阈值大的相关统计量分量对应的特征即可；也可指定欲选取的特征个数$k$，然后选择相关统计量分量最大的$k$个特征。

$$ \delta^j=\sum_i -\operatorname{diff}(x_i^j,x_{i,nh}^j)^2+\operatorname{diff}(x_i^j,x_{i,nm}^j)^2 $$

其中，diff体现了两个样本对应属性的差异性，对于离散属性，我们可以取0/1，对连续属性，我们可以作差取绝对值。我们可以看到，如果同类样本越近，异类样本越远，向量对应位置的值的统计量分量越大，也就是这个属性对分类越有用。

包裹式选择

与过滤特征选择不考虑后续学习器不同，包裹式特征选择直接把最终将要使用的学习器的性能作为特征子集的评价标准。一般而言，由于包裹式选择的直接性，它一般比过滤式的特征选择性能更好；但另一方面，由于在特征选择过程中需要多次训练学习器，因此包裹式特征选择的计算开销通常比过滤式特征选择大得多。

LVW(las vegas wrapper)算法是一个典型的包裹式特征选择算法。它在拉斯维加斯算法(las vegas method)框架下使用随机策略来进行子集搜索，并以最终分类器的误差作为特征子集评价准则。该算法的具体做法是：

(1) 设置初始最优误差$E$为无穷大，目前最优特征子集为属性全集$A$，重复次数$t=0$；

(2) 随机产生一组特征子集$A’$，计算使用该特征子集时分类器的误差$E’$；

(3) 如果$E’$比$E$小，则令$A’=A,E’=E$并重复(2)(3)步；否则$t++$，当$t$大于等于停止控制参数$T$时跳出循环。

LVW算法简单明了，但是由于是使用随机子集筛选，并且每次筛选都要重新计算学习器误差，若$A$和$T$很大时，算法可能会长时间都达不到停止条件。即若有运行时间限制，则可能会得不到解。

嵌入式选择与$\boldsymbol{L_1}$正则化

在过滤式和包裹式特征选择方法中，特征选择过程与学习器训练过程由明显的分别。与此不同的是，嵌入式特征选择是将特征选择的过程与学习器训练过程融为一体，两者在同一个优化过程中完成，即在学习器训练过程中自动地进行了特征选择。

常用的正则化方法如$L_1$范数(LASSO回归)和$L_2$范数(岭回归)都有助于降低过拟合风险，但$L_1$范数还会有一个额外的好处：它比$L_2$范数更易于获得稀疏解，即它求得的$w$会有更少的非零分量。

注意到$w$取得稀疏解意味着初始的$d$个特征中仅有对应着$w$的非零分量的特征才会出现在最终模型中，于是，求解$L_1$范数正则化的结果是得到了仅采用一部分初始特征的模型。换言之，基于$L_1$正则化的学习方法就是一种嵌入式特征选择方法，其特征选择过程与学习器训练过程融为一体，同时完成。

稀疏表示与字典学习

不妨把数据集$D$考虑为一个矩阵，其每一行对应一个样本，每一列对应一个特征。特征选择锁考虑的问题是特征具有稀疏性，即矩阵中的许多列与当前学习任务无关，通过特征选择去除这些列，则学习器训练过程仅需在较小的矩阵上进行，学习任务的难度可能有所降低，设计的计算和存储开销会减小，学得模型的可解释性也会提高。

考虑另一种稀疏性：$D$对应的矩阵中存在很多零元素，但这些零元素并不是以整行或整列的形式存在的。现实中有很多这种情况，比如文档分类任务中，若一个文档用词袋模型进行表示，矩阵的每一行都有大量的零元素，而对于不同的文档，这些零元素出现的列往往很不相同。

然而，当样本具有这样的稀疏表达形式时，对学习任务来说会有不少好处。例如线性支持向量机之所以能在文本数据上有很好的性能，恰是由于文本数据在使用上述字频表示后具有高度的稀疏性，使大多数问题变得线性可分。同时，稀疏性样本并不会造成存储上的负担，因为稀疏矩阵已经有很多高效的存储方法。

那么，若给定的数据集$D$是稠密的，可以将其转化为适度的**稀疏表示(sparse representation)**形式，从而享有稀疏性带来的好处。

显然，在一般的学习任务(例如图像分类)中并没有字典可用，我们需要学习出一个字典，为普通稠密表达的样本找到合适的字典，将样本转化为合适的稀疏表示形式，从而使学习任务得以简化，模型的复杂度得以降低，这个过程通常称为字典学习(dictionary learning)。

scikit-learn实现几种特征选择方法

# 1. 去除低方差特征
from sklearn.feature_selection import VarianceThreshold

X = [[0, 0, 1], [0, 1, 0], [1, 0, 0], [0, 1, 1], [0, 1, 0], [0, 1, 1]]
sel = VarianceThreshold(threshold=(.8 * (1 - .8)))
print(sel.fit_transform(X))

# 2. 单变量特征选择
from sklearn.datasets import load_iris
from sklearn.feature_selection import SelectKBest
from sklearn.feature_selection import chi2

X, y = load_iris(return_X_y=True)
print(X.shape)

X_new = SelectKBest(chi2, k=2).fit_transform(X, y)
print(X_new.shape)

# 3. 基于L1正则化的特征选择
from sklearn.svm import LinearSVC
from sklearn.datasets import load_iris
from sklearn.feature_selection import SelectFromModel

X, y = load_iris(return_X_y=True)
print(X.shape)

lsvc = LinearSVC(C=0.01, penalty="l1", dual=False).fit(X, y)
model = SelectFromModel(lsvc, prefit=True)
X_new = model.transform(X)
print(X_new.shape)

# 4. 基于树结构的特征选择
from sklearn.ensemble import ExtraTreesClassifier
from sklearn.datasets import load_iris
from sklearn.feature_selection import SelectFromModel

X, y = load_iris(return_X_y=True)
print(X.shape)

clf = ExtraTreesClassifier(n_estimators=50)
clf = clf.fit(X, y)
print(clf.feature_importances_)

model = SelectFromModel(clf, prefit=True)
X_new = model.transform(X)
print(X_new.shape)

参考资料

周志华. 机器学习. 北京: 清华大学出版社, 2016.