降维与特征选择
1. 导论
2. 特征选择技术
2.1 特征过滤器
2.1.1 FOCUS 算法
2.1.2 LVF 算法
一个数据集的不一致率计算方法：
- 对于两个实例，如果它们是匹配的（即除标签外的所有特征都一样），但是标签不同，我们认为这两个实例是不一致的。
-
考虑一个匹配组（不考虑其类别标签）： 不一致计数 $=$ 实例数量 $-$ 类标签实例的最大数量 例如：有 $n$ 个匹配实例，有 $c_1$ 个实例属于标签 1，$c_2$ 个实例属于标签 2，$c_3$ 个实例属于标签 3，并且 $c_1+c_2+c_3=n$. 如果 $c_3$ 是这三者中最大的，那么不一致计数为 $n-c_3$.
- 不一致率 $=$ 所有不一致计数之和 / 数据集实例总数。
2.1.3 基于离散化的特征过滤
2.1.4 使用一种学习算法作为另一种算法的特征过滤器
2.1.5 基于互信息理论的特征过滤器
令 $C$ 表示类别集合，$V$ 表示特征集合，$X$ 为 $V$ 的一个子集，$v=(v_1,\dots,v_n)$ 是 $V$ 的一个特征值分配，$v_x$ 是 $v$ 在 $X$ 中的特征上的投影。特征选择器的目标是选择特征子集 $X$ 使得 $P(C\mid X=v_x)$ 尽可能接近 $P(C\mid V=v)$。
为了达到该目标，该算法从所有原始特征开始，在每个阶段，采用向后消除搜索，移除使得 (在移除前后) 两个分布之间变化最小的特征。由于从有限的数据估计高阶概率分布并不可靠，因此给出了一种使用特征对组合的近似算法。使用交叉熵衡量两个分布之间的差异，并且用户需要指定需要移除的特征数。
对于每个特征 $i$，该算法会从剩余特征中选择 $K$ 个属性得到一个集合 $M_i$，其中很可能包含了特征 $i$ 具有的关于类别值的信息。$M_i$ 包含了剩余的特征中的 $K$ 个特征，使得公式 5.2 的值最小。对于每个特征 $i$，计算给定 $M_i, V_i$ 时的类别值分布与给定 $M_i$ 时的类别值分布之间的期望交叉熵。将具有最小值的特征 $i$ 从特征集合中删除。重复此过程，直到原始特征集合中剩余特征数达到用户指定的特征数。
使用 C4.5 和朴素贝叶斯作为最终归纳算法的自然域和两个人工域实验表明，当条件集 $M$ 的大小 $K=2$ 时，特征选择器的表现最好。
该算法的一个问题是，它需要将具有两个以上值的特征编码为二进制，以避免熵度量偏向于具有多个值的特征。这可能导致原始数据中的特征数大大增加，并引入更多的依赖关系。此外，原始属性的含义不明确，使得 C4.5 等算法的输出难以解释。
2.1.6 基于实例的特征选择方法：RELIEF
Kira 和 Rendell（1992）描述了一种称为 RELIEF 的算法，该算法使用基于实例的学习为每个特征分配相关权重。每个特征的权重反映了其区分类别值的能力。按权重对特征进行排序，并选择那些超过用户指定阈值的特征来构建最终特征子集。该算法通过从训练数据中随机采样实例来工作。对于每个采样的实例，找到与之类别相同 (最近命中) 和相反 (最近未命中) 的最近实例。一个属性的权重将根据其值将采样实例与其最近命中和最近未命中区分开来的程度进行更新。如果一个属性能够区分不同类别的实例，并且对于相同类别的实例具有相同的值，那么算法将给予该属性很高的权重。公式（5.3）显示了 RELIEF 使用的权重更新公式：
\[W_X=W_X-\dfrac{\mathrm{diff} (X,R,H)^2}{m}+\dfrac{\mathrm{diff} (X,R,H)^2}{m}\]其中，$W_X$ 是属性 $X$ 的权重，$R$ 是一个随机采样实例，$H$ 是最近命中，$M$ 是最近未命中，$m$ 是最近采样实例的数量。
函数 $\mathrm{diff}$ 计算了对于一个给定属性，两个实例之间的差异。对于名义属性，$\mathrm{diff}$ 函数被定义为 $1$ (两个实例在该属性上的值不同) 或者 $0$ (两个实例在该属性上的值相同)。而对于连续属性，$\mathrm{diff}$ 函数为两个实例在该属性上的值的实际差异归一化到 $[0, 1]$ 区间的值。除以 $m$ 则保证了所有权重都落在区间 $[-1, 1]$ 内。
RELIEF 算法用于二分类域。Kononenko（1994）提出了一种 RELIEF 的改进版，使其能够处理多分类、带噪声和不完整的域。Kira 和 Rendell 提供的实验证据表明：即使在存在交互的情况下，RELIEF 也能有效识别相关特征。交互特征是指那些其值取决于其他特征以及类别的特征，因此这类特征可以提供有关该类别的更多信息。另一方面，冗余要素是那些其值取决于其他要素的值而与类别无关的特征，因此，这类特征无法提供有关该类别的更多信息。（例如，在奇偶校验块问题中）。但是，RELIEF 不会处理冗余特征。作者指出：“如果大多数给定特征与该概念相关，那么（RELIEF）会选择大多数给定特征，即使这些特征中只有少数是对于概念描述必需的。”
Scherf和Brauer（1997）描述了一种类似的基于实例的方法（EUBAFES），用于分配特征权重，该算法是独立于 RELIEF 开发的。像 RELIEF 一样，EUBAFES 试图增强同一类实例之间的相似性，同时降低不同类实例之间的相似性。相对于此目标，采用梯度下降方法来优化特征权重。
2.2 特征包装器
特征包装器用于特征选择，它使用归纳算法来估计特征子集的价值。包装方法的基本原理是，最终使用特征子集的归纳方法在准确性方面，应比具有完全不同归纳偏差的单独测量方法提供更好的估计 (Langley 和 Sage, 1994)。
特征包装器通常会比过滤器获得更好的结果，这是因为它们已针对归纳算法与其训练数据之间的特定交互进行了调优。但是，它们往往比特征过滤器慢得多，因为它们必须重复调用归纳算法，并且在使用其他归纳算法时必须重新运行。
由于包装器是一个良定义过程，因此其应用中的大部分方差都归因于用于估计目标归纳算法的样本外准确性所采用的方法、目标归纳算法本身、以及搜索结构。本节回顾了一些先前的工作，主要专注于包装方法和减少其计算成本的方法。
2.2.1 用于决策树学习器的包装器
John，Kohavi 和 Pfleger (1994) 首次主张将包装器 (Allen, 1974) 作为机器学习中特征选择的一个通用框架。他们提出了两种程度的特征相关性的形式定义，并声称包装器能够发现相关特征。如果在给定完整特征集的情况下，类别值的概率分布在移除特征 $X_i$ 时会发生变化，则可以认为特征 $X_i$ 与目标概念强相关。如果特征 $X_i$ 不是强相关的，并且在给定完整特征集的某些子集 $S$ (包含 $X_i$) 的情况下，类别值的概率分布在移除 $X_i$ 时会发生变化，则可以认为特征 $X_i$ 与目标概念弱相关。所有既非强相关又非弱相关的特征被称为不相关特征。
使用 ID3 和 C4.5 (Quinlan, 1993; Quinlan, 1986) 作为归纳算法，对三个人工域和三个自然域进行了实验。通过在训练数据上使用 25 折交叉验证来评估准确率；一个不相交测试集用于报告最终准确率。使用前向选择和后向消除搜索。除一个人工域外，结果表明，特征选择并没有显着改变 ID3 或 C4.5 的泛化性能。特征选择的主要作用是减小树的大小。与 John 等人一样，Caruana 和 Freitag (1994) 在两个日程调度域上使用 ID3 测试了多种贪婪搜索方法。除了后向消除和前向选择之外，它们还测试了逐步双向搜索的两种变体，一种是从特征全集开始，另一种是从空集开始。
结果表明，尽管双向搜索略胜于前向和后向搜索，但总体而言，除计算时间外，各种搜索策略之间的差异非常小。特征选择能够提升 ID3 在两个日程调度域上的表现。
Vafaie 和 De Jong (1995) 以及 Cherkauer 和 Shavlik (1996) 都尝试将遗传搜索策略用于包装器框架中，以提高决策树学习器的表现。Vafaie 和 De Jong (1995) 描述了一个系统，该系统包含两个由遗传算法驱动的模块：第一个用于特征选择，第二个用于构造归纳 (构造归纳是通过将逻辑和数学算子应用于原始特征来创建新属性的过程 (Michalski, 1983))。这两个模块都能够显着提升 ID3 在纹理分类问题上的表现。
Cherkauer 和 Shavlik (1996) 提出了一种名为 SET-Gen 的算法，该算法致力于提高决策树的可理解性及其准确性。为了实现这一目标，SET-Gen 的遗传搜索使用了一个适应度函数，该函数是准确率项和简明性项的一个线性组合：
\[\mathrm{Fitness}(X)=\dfrac{3}{4}A+\dfrac{1}{4}\left(1-\dfrac{S+F}{2} \right)\]其中，$X$ 是一个特征子集，$A$ 是 C4.5 的平均交叉验证准确率，$S$ 是由 C4.5 生成的树的平均大小 (通过训练样本数进行归一化)，$F$ 是子集 $X$ 中的特征数 (通过可选特征的总数进行归一化)。等式 (5.4) 保证了适应度最高的种群成员是那些导致 C4.5 归纳出小而准确的决策树的特征子集。
2.2.2 用于基于实例学习的包装器
除了 John 等人之外，Langley 和 Sage (1994) 也在大约在同一时期，在研究简单最近邻算法对于不相关属性的敏感度时，独立提出了包装器方法。缩放实验表明，最近邻的样本复杂度 (达到给定准确率所需的训练样本数) 会随数据中不相关属性的数量呈指数增加 (Aha 等人, 1991; Langley 和 Sage, 1994)。他们提出了一种称为 OBLIVION 的算法，该算法使用遗忘决策树进行特征的后向消除作为归纳算法 (当所有原始特征都包含在树中，并且在分类时给定很多假设时，Langley 和 Sage 注意到该结构在功能上等价于简单的最近邻算法；实际上，这正是其在 OBLIVION 中的实现方式)。对于 OBLIVION 在多个人工域上使用 $k$ 折交叉验证的实验表明，它能够移除冗余特征，并且在特征相互作用的域上比 C4.5 学习速度更快。
Moore 和 Lee (1994) 采取了类似的方法来增强最近邻算法，但是他们的系统使用了留一法代替 $k$ 折交叉验证，并且着重于改进数值预测而非离散分类。Aha 和 Blankert (1994) 也使用留一法交叉验证，但将其与集束搜索配对使用来代替爬山算法 (集束搜索是最佳优先搜索的受限版本，只能记住一部分用于回溯的搜索路径)。他们的结果表明，在一个稀疏的 (实例数很少) 具有许多特征的云模式域上，特征选择可以提升 IB1 (一种最近邻分类器) 的性能。Moore, Hill 和 Johnson (1992) 不仅涵盖了包装过程中的特征选择，还涵盖了预测中使用的最近邻数量和组合函数的空间。使用留一法交叉验证，他们在几个涉及连续类别预测的控制问题上取得了显着改进。
同样，Skalak (1994) 将特征选择和原型选择结合到一个包装程序中，使用随机突变爬山算法作为搜索策略。实验结果表明，在两个自然域上最近邻的准确率有了显着提高，并且算法的存储需求 (训练期间保留的实例数) 大大减少。
Domingos (1997) 描述了一种上下文敏感的包装器方法，用于基于实例的学习器的特征选择。该方法的动机是可能存在一些特征，这些特征要么仅在实例空间中的有限区域内是相关的，而在其他地方是不相关的；要么仅在其他特征为某些特定值的情况下相关 (弱交互)，否则是不相关的。在这两种情况下，当对特征进行全局 (在实例空间上) 估计时，此类特征的不相关方面可能会淹没它们对于基于实例的学习器的整个有用方面。即使在包装器中使用后向搜索策略时也是如此。对于包装器方法，在具有特征交互作用的域中，后向搜索策略通常比前向搜索策略更有效。因为后向搜索通常是从所有特征开始，所以如果移除了一个强交互特征，通常可以通过交叉验证期间准确率的下降检测出来。
Domingos 提出了一种称为 RC 的算法，该算法可以检测和利用上下文敏感特征。RC 通过为训练集中的每个实例选择一个 (潜在的) 不同特征集来工作。这是通过使用搜索策略和交叉验证来评估准确性实现的。对于后向训练集中的每个实例，RC 会找到与其标签类别相同的最近邻，并移除两者之间不同的那些特征。然后，通过交叉验证估来计整个训练数据集的准确率。如果准确率未降低，则接受修改后的实例；否则，实例将恢复到其原始状态并释放 (不再对其尝试进一步特征选择)。特征选择过程将继续进行，直到所有实例都达到释放状态为止。
通过对机器学习数据集进行选择的实验表明，RC 的表现要优于 (使用基于实例学习器的前向和后向搜索策略的) 标准包装器特征选择器。上下文敏感方法对于 (经过设计的) 有限特征依赖的人工域依然有效。当特征是全局相关或不相关时，RC 与标准包装器相比，在特征选择上并无优势。此外，当可用样本非常少或者数据嘈杂时，与 RC 相比，标准包装器方法可以更容易地检测出全局无关特征。
Domingos 还指出，使用基于实例学习器的包装器 (包括RC) 不适合在包含大量实例的数据库上使用，因为它们的 N 值 (实例数) 是平方的。
Kohavi (1995) 使用包装器特征选择来探索决策表多数 (DTM) 分类器的潜力。适当的数据结构允许对 DTM 分类器使用快速增量交叉验证。实验表明，使用适当特征子集的 DTM 分类器与 C4.5 等复杂算法相比非常有利。
2.2.3 用于贝叶斯分类器的包装器
由于朴素的贝叶斯分类器的假设，即在每个类中，属性的概率分布彼此独立。Langley 和 Sage (1994) 指出，对于具有冗余特征的域，可以通过删除此类特征来提升分类器的性能。相比于决策树算法和基于实例的学习器最常用的后向策略，朴素贝叶斯分类器通常采用前向搜索策略来选择特征。使用前向搜索的理由是，当一个有害的冗余属性被添加时，它可以即检测依赖关系。实验表明，在六个自然域中，有三个在总体上改进并提高了学习率，其余三个则没有变化。
Pazzani (1995) 在包装器框架中结合了特征选择和简单的构造性归纳，以提升朴素贝叶斯的性能。作者比较了前向和后向爬山搜索策略。对于前者，该算法不仅考虑将单个特征添加到当前子集中，还考虑通过将尚未选择的特征之一与子集中的每个选定特征相结合来创建新属性。对于后者，该算法既考虑删除单个特征，还考虑用一个联合特征来替换特征对。在机器学习数据集上的选择结果表明，这两种方法均可以提高朴素贝叶斯的性能。
在移除冗余属性方面，前向策略要比后向策略做得更好。而在识别特征交互方面，由于后向策略是从完整的特征集开始，并考虑了所有可能的联合特征对，因此它要比前向策略更有效。另外，其他一些研究也显示了使用基于包装器的特征选择能够提升朴素贝叶斯的性能 (Kohavi 和 Sommerfield, 1995; Kohavi 和 John, 1996)。
Provan 和 Singh (1996) 使用包装器来选择用于构建贝叶斯网络的特征。结果表明，虽然特征选择并不能在由完整特征集构成的网络上提升其准确率，但是经过特征选择后创建的网络却要小得多，学习起来也更快。
3. 变量选择
本节旨在提供对于变量选择的调研。假设 $Y$ 是一个我们感兴趣的变量，而 $X_1,\dots, X_p$ 是一组潜在的解释变量或预测变量，是由 $n$ 个观测值组成的向量。当我们想要对 $Y$ 和 $X_1,\dots, X_p$ 的一个子集之间的关系进行建模时，就会出现变量选择 (或者通常称为子集选择) 的问题，但是对于使用哪个子集存在不确定性。当 $p$ 很大并且 $X_1,\dots, X_p$ 被认为包含许多冗余或不相关的变量时，这种情况尤为令人关注。变量选择问题在线性回归上下文中的正态线性模型中最为常见。令 $q_\gamma$ 索引 $X_1,\dots, X_p$ 的子集，令 $q$ 为第 $\gamma$ 个子集的大小，问题在于选择并拟合一个以下形式的模型：
\[Y=X_{\gamma}\beta_{\gamma} + \boldsymbol \varepsilon\]其中，$X_\gamma$ 是一个 $n\times q_\gamma$ 矩阵，其列对应于第 $\gamma$ 个子集，$\beta_\gamma$ 是一个 $q_\gamma \times 1$ 的回归系数向量，并且 $\boldsymbol \varepsilon \approx \mathcal N(\mathbf 0, \sigma^2 \boldsymbol I)$。更一般地，变量选择问题是模型选择问题的一个特例，其中所考虑的每个模型对应于 $X_1,\dots, X_p$ 的不同子集。通常，将单个模型类简单地应用于所有可能的子集。
3.1 Mallows Cp (Mallows, 1973)
该方法最小化了预测值的均方误差：
\[C_p = \dfrac{\mathrm{RSS}_\gamma}{\hat \sigma^2_{\mathrm{FULL}}}+2q_\gamma - n\]其中，$\mathrm{RSS}\gamma$ 是第 $\gamma$ 个模型的残差平方和，$\hat \sigma^2{\mathrm{FULL}}$ 是基于完整模型的 $\sigma^2$ 的通常无偏估计。
目的是获得具有最小 $C_p$ 的模型。可以通过找到具有最小 $C_p$ 的最小子集来实现降维。
3.2 AIC, BIC 和 F ratio
从非常不同的观点出发，另外两个最受欢迎的标准是 AIC (针对 Akaike 信息标准) 和 BIC (针对贝叶斯信息标准)。令 $\hat l_\gamma$ 表示第 $\gamma$ 个模型的最大对数似然，AIC 选择能够最大化 $(\hat l_\gamma - q_\gamma)$ 的模型，而 BIC 选择能够最大化 $(\hat l_\gamma - (\log n) q_\gamma / 2)$ 的模型。
对于线性模型，许多流行的选择标准都是一个带惩罚项的平方和标准的特例，这为比较提供了一个统一的框架。为了避免复杂性，假设 $\sigma^2$ 是已知的，则此通用准则选择的子集模型将能够最小化：
\[\mathrm{RSS}_\gamma / \hat \sigma^2 + F q_\gamma\]其中，$F$ 是一个预设的 “维度惩罚项”。从直觉上，上式通过 $F$ 乘以 $q_\gamma$ (第 $\gamma$ 个模型的维度) 对 $\mathrm{RSS}_\gamma / \hat \sigma^2$ 项施加惩罚。AIC 和最小 $C_p$ 本质上是等价的，对应于 $F = 2$ 的情况；而 BIC 则对应于 $F = \log n$ 的情况。通过施加一个较小的惩罚项，AIC 和最小 $C_p$ 将选择比 BIC 更大的模型 (除非 $n$ 非常小)。
3.3 主成分分析 (PCA)
对于均方误差，主成分分析 (PCA) 是最好的线性降维技术 (Jackson, 1991; Jolliffe, 1986)。作为基于变量的协方差矩阵，它是一种二阶方法。在各个领域中，它也被称为奇异值分解 (SVD)、Karhunen-Loeve 变换、Hotelling 变换和经验正交函数 (EOF) 方法。从本质上讲，PCA 试图通过以下方法来实现数据降维：寻找具有最大方差的原始变量的一些正交线性组合 (PCs，即主成分)。第一个 PC, $s_1$, 是具有最大方差的线性组合。我们有 $s_1 = \mathbf x^{\mathrm T}\mathbf w_1$，其中 $p$ 维系数向量 $\mathbf w_1 =(w_{1,1},\dots,w_{1,p})^{\mathrm T}$。求解：
\[\mathbf w_1 = \mathop{\operatorname {arg\,max}}\limits_{\|w=1\|}\mathrm{Var}(\mathbf x^{\mathrm T}\mathbf w)\]第二个 PC 是具有第二大方差且与第一个 PC 正交的线性组合，依此类推。PCs 的数量与原始变量的数量一样多。对于许多数据集，前几个 PCs 解释了大部分方差，因此可以在忽略其余 PCs 的情况下将信息损失降至最低。
3.4 因子分析 (FA)
像 PCA 一样，因子分析 (FA) 也是基于二阶数据摘要的一种线性方法。该方法首先由心理学家提出，FA 假设测得的变量依赖于一些未知且通常无法测量的常见因子。典型例子包括定义为各种个人测试分数的变量，因为这些分数被认为与常见的 “智力” 因素有关。FA 的目标是发现这种关系，因此可以用来对遵循该因子模型的数据集进行降维。
3.5 投影追踪
投影追踪 (PP) 是一种线性方法，与 PCA 和 FA 不同，它可以包含高于二阶的信息，因此对于非高斯数据集很有用。该方法的计算量要比二阶方法更大。给定一个定义了某个方向的 “兴趣度” 的投影索引，PP 将寻找能够优化该索引的方向。由于高斯分布是兴趣度最低的分布 (结构最少)，因此投影索引通常用于衡量非高斯性的某些方面。然而，如果使用二阶最大方差 (投影是正交的) 作为投影指数，那么 PP 会转变为我们所熟悉的 PCA。
3.6 变量选择的高级方法
Chizi 和 Maimon (2002) 在他们的工作中描述了一些新的变量选择方法。这些方法基于简单的算法，并使用已知的评估器，例如：信息增益、逻辑回归系数和随机选择。所有方法都给出了在基准数据集上的经验结果和每种方法的理论边界。通过对降维问题的分解，可以发现对于变量选择的更广泛研究。
总而言之，特征选择对于许多应用领域都非常有用，例如：制造、安全和医学，以及许多数据挖掘技术，例如：决策树、聚类、集成方法和遗传算法。
本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。 欢迎转载，并请注明来自：YEY 的博客 同时保持文章内容的完整和以上声明信息！