【周志华机器学习】十一、特征选择与稀疏学习

文章目录

• 参考资料
• 前言
• 1. 子集搜索与评价
• • 1.1 特 征 选 择
  • 1.2 特征选择原因
  • 1.3 子集搜索与子集评价
  • • 1.3.1 子集搜索
    • 1.3.2 子集评价
• 2. 过滤式选择（Relief）
• • 2.1 Relief算法核心
  • 2.2 拓展变体：Relief-F算法
• 3. 包裹式选择（LVW）
• 4. 嵌入式选择与正则化
• • 4.1 L1范数与L2范数理解
• 5. 稀疏表示与字典学习
• 6. 压缩感知

参考资料

1. Machine-learning-learning-notes
2. LeeML-Notes
3. ML-NLP

本博客是根据周志华的西瓜书和参考资料1、2、3所做的笔记，主要用于学习，非技术类博客，因此存在大量复制粘贴，请见谅。

如果本篇博客有后记部分，则该部分表示的是在书本原有的基础知识上，进行的知识点的扩充。

前言

对于数据集中的一个对象及组成对象的零件元素：

• 统计学家常称它们为观测（observation）和变量（variable）；
• 数据库分析师则称其为记录（record）和字段（field）；
• 数据挖掘/机器学习学科的研究者则习惯把它们叫做样本/示例（example/instance）和属性/特征（attribute/feature）。
  

  
  

机器学习中特征选择是一个重要的“数据预处理”（data preprocessing）过程，即试图从数据集的所有特征中挑选出与当前学习任务相关的特征子集，接着再利用数据子集来训练学习器；稀疏学习则是围绕着稀疏矩阵的优良性质，来完成相应的学习任务。

1. 子集搜索与评价 1.1 特 征 选 择

我 们 能 用 很 多 属 性 描 述 一 个 西 瓜 , 例 如 色 泽 、 根 蒂 、 敲 声 、 纹 理 、 触 感 等 , 但 有 经 验 的 人 往 往 只 需 看 看 根 蒂 、 听 听 敲 声 就 知 道 是 否 好 瓜 . 换 言 之 , 对 一 个 学 习 任 务 来 说 , 给 定 属 性 集 , 其 中 有 些 属 性 可 能 很 关 键 、 很 有 用 , 另 一 些 属 性 则 可 能 没 什 么 用 . 我 们 将 属 性 称 为 “ 特 征 “(feature), 对 当 前 学 习 任 务 有 用 的 属 性 称 为 “ 相 关 特 征 “(relevant feature)、 没 什 么 用 的 属 性 称 为 “ 无 关 特 征 “(irrelevant feature). 从 给 定 的 特 征 集 合 中 选 择 出 相 关 特 征 子 集 的 过 程 , 称
为 “ 特 征 选 择 “(feature selection),

1.2 特征选择原因

特 征 选 择 是 一 个 重 要 的 “ 数 据 预 处 理 “(data preprocessing) 过 程 , 在 现 实 机 器 学 习 任 务 中 , 获 得 数 据 之 后 通 常 先 进 行 特 征 选 择 , 此 后 再 训 练 学 习 器 . 那 么 , 为 什 么 要 进 行 特 征 选 择 呢 ?

首 先 , 我 们 在 现 实 任 务 中 经 常 会 遇 到 维 数 灾 难 问 题 , 这 是 由 于 属 性 过 多 而 造 成 的 , 若 能 从 中 选 择 出 重 要 的 特 征 , 使 得 后 续 学 习 过 程 仅 需 在 一 部 分 特 征 上 构 建 模 型 , 则 维 数 灾 难 问 题 会 大 为 减 轻 . 从 这 个 意 义 上 说 ,特 征 选 择 与 第 10 章 介 绍 的 降 维 有 相 似 的 动 机 ; 事 实 上 , 它 们 是 处 理 高 维 数 据 的两 大 主 流 技 术 .

第 二 个 原 因 是 , 去 除 不 相 关 特 征 往 往 会 降 低 学 习 任 务 的 难 度 , 这 就 像 侦 探 破 案 一 样 , 若 将 纷 繁 复 杂 的 因 素 抽 丝 剥 茧 , 只 留 下 关 键 因 素 , 则 真 相 往 往 更 易 看 清 .

1.3 子集搜索与子集评价

特征选择是直接剔除那些与学习任务无关的属性而选择出最佳特征子集。

若直接遍历所有特征子集，显然当维数过多时遭遇指数爆炸就行不通了；若采取从候选特征子集中不断迭代生成更优候选子集的方法，则时间复杂度大大减小。

这时就涉及到了两个关键环节：1.如何生成候选子集；2.如何评价候选子集的好坏

1.3.1 子集搜索

前向搜索：初始将每个特征当做一个候选特征子集，然后从当前所有的候选子集中选择出最佳的特征子集；接着在上一轮选出的特征子集中添加一个新的特征，同样地选出最佳特征子集；最后直至选不出比上一轮更好的特征子集。

后向搜索：初始将所有特征作为一个候选特征子集；接着尝试去掉上一轮特征子集中的一个特征并选出当前最优的特征子集；最后直到选不出比上一轮更好的特征子集。

双向搜索：将前向搜索与后向搜索结合起来，即在每一轮中既有添加 *** 作也有剔除 *** 作。

每 一 轮 逐 渐增 加 选 定 相 关 特 征 ( 这 些 特 征 在 后 续 轮 中 将 确 定 不 会 被 去 除 )、 同 时 减 少 无 关 特征 。

显 然 , 上 述 策 略 都 是 贪 心 的 , 因 为 它 们 仅 考 虑 了 使 本 轮 选 定 集 最 优 。

1.3.2 子集评价

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

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

2. 过滤式选择（Relief）

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

Relief (Relevant Features)是 一 种 著 名 的 过 滤 式特 征 选 择方法。

它使用一个“相关统计量”来度量特征的重要性，该统计量是一个向量，其中每个分量代表着相应特征的重要性，因此我们最终可以根据这个统计量各个分量的大小来选择出合适的特征子集。

2.1 Relief算法核心

Relief算法的核心在于如何计算出该相关统计量。

直观上理解：对于猜中近邻，两者 j j j属性的距离越小越好，对于猜错近邻， j j j属性距离越大越好。

更一般地，若 x i x_i xi​为离散属性， d i f f diff diff取汉明距离，即相同取0，不同取1；若 x i x_i xi​为连续属性，则 d i f f diff diff为曼哈顿距离，即取差的绝对值。

分别计算每个分量，最终取平均便得到了整个相关统计量。

2.2 拓展变体：Relief-F算法

标准的Relief算法只用于二分类问题，后续产生的拓展变体Relief-F则解决了多分类问题。

3. 包裹式选择（LVW）

与过滤式选择不同的是，包裹式选择将后续的学习器也考虑进来作为特征选择的评价准则。

因此包裹式选择可以看作是为某种学习器量身定做的特征选择方法，由于在每一轮迭代中，包裹式选择都需要训练学习器，因此在获得较好性能的同时也产生了较大的开销。

LVW（Las Vegas Wrapper）是一种经典的包裹式特征选择方法。

它 在 拉 斯 维 加 斯 方 法 (Las Vegas method) 框 架 下 使 用 随 机 策 略来 进 行 子 集 搜 索 , 并 以 最 终 分 类 器 的 误 差 为 特 征 子 集 评 价 准 则 . 算 法 描 述 如图 11.1 所 示 .

图 11.1 算 法 第 8 行 是 通 过 在 数 据 集 D 上 , 使 用 交 叉 验 证 法 来 估计 学 习 器（学习算法）的 误 差 , 注 意 这 个 误 差 是 在 仅 考 虑 特 征 子 集 A’ 时 得 到 的 , 即 特 征 子 集 A’ 上的 误 差 , 若 它 比 当 前 特 征 子 集 A 上 的 误 差 更 小 , 或 误 差 相 当 但 A’ 中 包 含 的 特 征数 更 少 , 则 将 A’ 保 留 下 来 .

注 意 , 由 于 LVW 算 法 中 特 征 子 集 搜 索 采 用 了 随 机 策 略 , 而 每 次 特 征子 集 评 价 都 需 训 练 学 习 器 , 计 算 开 销 很 大 , 因 此 算 法 设 置 了 停 止 条 件 控 制 参 数T. 然 而 , 整 个 LVW 算 法 是 基 于 拉 斯 维 加 斯 方 法 框 架 , 若 初 始 特 征 数 很 多 ( 即|A| 很 大 )、 T 设 置 较 大 , 则 算 法 可 能 运 行 很 长 时 间都 达 不 到 停 止 条 件 . 换 言 之 , 若有运行时间限制，则有可能给不出解。

蒙特卡罗算法：采样越多，越近似最优解，一定会给出解，但给出的解不一定是正确解；
拉斯维加斯算法：采样越多，越有机会找到最优解，不一定会给出解，且给出的解一定是正确解。

举个例子，假如筐里有100个苹果，让我每次闭眼拿1个，挑出最大的。

于是我随机拿1个，再随机拿1个跟它比，留下大的，再随机拿1个……我每拿一次，留下的苹果都至少不比上次的小。

拿的次数越多，挑出的苹果就越大，但我除非拿100次，否则无法肯定挑出了最大的。

这个挑苹果的算法，就属于蒙特卡罗算法——尽量找较好的，但不保证是最好的。

而拉斯维加斯算法，则是另一种情况。

假如有一把锁，给我100把钥匙，只有1把是对的。

于是我每次随机拿1把钥匙去试，打不开就再换1把。

我试的次数越多，打开（正确解）的机会就越大，但在打开之前，那些错的钥匙都是没有用的。

这个试钥匙的算法，就是拉斯维加斯的——尽量找最好的，但不保证能找到。

4. 嵌入式选择与正则化

过滤式中特征选择与后续学习器完全分离，包裹式则是使用学习器作为特征选择的评价准则；

嵌入式是一种将特征选择与学习器训练完全融合的特征选择方法，即将特征选择融入学习器的优化过程中。

经验风险指的是模型与训练数据的契合度，结构风险则是模型的复杂程度
机器学习的核心任务就是：在模型简单的基础上保证模型的契合度。

4.1 L1范数与L2范数理解

L1 范 数 和 L2 范 数 正 则 化 都 有 助 于 降 低 过 拟 合 风 险 , 但 前 者 还 会 带 来 一 个 额 外 的 好 处 : 它 比 后 者 更 易 于 获 得 “ 稀 疏 “(sparse) 解 , 即 它 求 得 的 w 会 有 更少 的 非 零 分 量 .

总的来说：L1范数会趋向产生少量的特征，其他特征的权值都是0；L2会选择更多的特征，这些特征的权值都会接近于0。

这样L1范数在特征选择上就十分有用，而L2范数则具备较强的控制过拟合能力。

可以从下面两个方面来理解：

（2）空间限制：L1范数与L2范数都试图在最小化损失函数的同时，让权值W也尽可能地小。

我们可以将原优化问题看做为下面的问题，即让后面的规则则都小于某个阈值。

这样从图中可以看出：采 用 L1 范 数 时 平 方 误 差 项 等 值 线 与 正 则 化 项 等 值 线 的交 点 常 出 现 在 坐 标 轻 上 , 即 w1或w2 为 0, 而 在 采 用 L2 范 数 时 , 两 者 的 交 点 常出 现 在 某 个 象 限 中 , 即w1或w2 均 非 0; 换 言 之 , 采 用 L1 范 数 比 L2 范 数 更 易 于得 到 稀 疏 解 .

5. 稀疏表示与字典学习

当样本数据是一个稀疏矩阵时，对学习任务来说会有不少的好处，例如很多问题变得线性可分，储存更为高效等。

这便是稀疏表示与字典学习的基本出发点。

稀疏矩阵即矩阵的每一行/列中都包含了大量的零元素，且这些零元素没有出现在同一行/列，对于一个给定的稠密矩阵，若我们能通过某种方法找到其合适的稀疏表示，则可以使得学习任务更加简单高效，我们称之为稀疏编码（sparse coding）或字典学习（dictionary learning）。

可参用变量交替优化的策略来求解上式。

6. 压缩感知

在 现 实 任 务 中 , 我 们 常 希 望 根 据 部 分 信 息 来 恢 复 全 部 信 息 . 例 如 在 数 据 通讯 中 要 将 模 拟 信 号 转 换 为 数 字 信 号 , 根 据 奈 奎 斯 特 (Nyquist) 采 样 定 理 , 令 采样 频 率 达 到 模 拟 信 号 最 高 频 率 的 两 倍 , 则 采 样 后 的 数 字 信 号 就 保 留 了 模 拟 信 号的 全 部 信 息 ; 换 言 之 , 由 此 获 得 的 数 字 信 号 能 精 确 重 构 原 模 拟 信 号 . 然 而 , 为了便 于 传 输 、 存 储 , 在 实 践 中 人 们 通 常 对 采 样 的 数 字 信 号 进 行 压 缩 , 这 有 可 能 损失 一 些 信 息 , 而 在 信 号 传 输 过 程 中 , 由 于 信 道 出 现 丢 包 等 问 题 , 又 可 能 损 失 部分 信 息 . 那 么 , 接 收 方 基 于 收 到 的 信 号 , 能 否 精 确 地 重 构 出 原 信 号 呢 ? 压 缩 感知 (compressed sensing) 为 解 决 此 类 问 题 提供 了 新 的 思 路 .

压缩感知与特征选择、稀疏表示不同的是：它关注的是通过欠采样信息来恢复全部信息。

在实际问题中，为了方便传输和存储，我们一般将数字信息进行压缩，这样就有可能损失部分信息，如何根据已有的信息来重构出全部信号，这便是压缩感知的来历，压缩感知的前提是已知的信息具有稀疏表示。