基于随机森林的特征选择算法.docx

基于随机森林的特征选择算法姚登举，杨静，詹晓娟（哈尔滨工程大 学 计算机科学与技术学 院 ，哈 尔 滨 ；哈尔滨理工大 学 软件学院 ，哈 尔 滨 ；黑龙江工程学 院 计算机科学与技术学院 ，哈 尔 滨 ）摘 要：提出了一种基 于随 机 森 林的 封装式特征选择算法 ，以随机 森林算法为基本工 具，以分类精度作为准则函数 ，采用序列后向选择和广义序列后向选择方法进行特征选择 。在 数据集上的对比实验结果 表 明 ， 算 法 在 分 类 性 能 和 特 征 子 集 选 择 两 方 面 具 有 较 好 的性能。关键词：人工智能；随机森林；特征选择；封装式中图分类号： 文献标志码： 文章编号：（）： ， （，； ，； ，）： （） ， ：；引言图像处理、信 息 检 索 以 及 生 物 信 息 学 等 技 术 的发展，产生了 以超大规模特征 为特点的高维数 据集。如何有效地从高维数据中提取或选择出有用的特征信息 或 规 律 ，并 将其分类识别已成为当 今信息科学与技术所面临的基本问题。特 征 选 择是指从原始特征集中选择使某种评估标准最优 的特征子集，以 使在该最优特征子集上所构建 的 分类或回归模型达到与特征选择前近似甚至更好收 稿 日 期 ：基 金 项 目 ：国家自然科学基金项目（，）；黑龙江省自然科学基金项目 （，）；哈 尔 滨 市 科 技 创 新 人 才研究专项项目 （，）；高 等 学 校 博 士 学 科 点专项科研基金项目（）作 者 简 介 ：姚 登 举（），男 ，博 士 研 究 生 ，讲 师 研 究 方 向 ：人 工 智 能 ，数 据 挖 掘 ，模 式 识 别 ：吉 林 大 学 学 报 （工 学 版 ）第卷的预测 精 度。 证 明 寻找满足要求的最小 特征子集 是 完 全 问 题。 在 实 际 应 用 中，通 常是通过采用 启 发 式 搜 索 算 法 ，在运算效率和特 征子集质量间 找 到 一 个 好 的 平 衡 点 ，即 近 似 最 优 解。随 机 森 林 （，）是 一 种 集 成 机 器 学 习 方 法，它利用随机重采样技术 和节点随机分裂技 术 构 建 多 棵 决 策 树 ， 通过投票得到最 终 分 类 结 果 。 具 有 分 析 复 杂 相互作用分类 特 征 的 能 力 ，对于 噪声数据和存在 缺失值的数据 具 有 很 好 的 鲁 棒 性 ，并 且 具 有 较 快 的学习速度，其 变量重要性度量 可以作为高维数 据的特征选择 工 具，近年来已经被广泛应用于各 种分 类、预 测、特 征选 择 以及异常点检测问题 中。特征选择算法根据所采用的特征评价策略可器，如果把决策树看成分类任务中的一个专家 ，随 机森林就 是 许 多 专 家 在 一 起 对 某 种 任 务 进 行 分 类。生成随机森林的步骤如下 ：（）从 原始训练数据集中 ，应 用 方 法有放回地 随 机 抽 取 个 新 的 自 助 样 本 集 ，并 由 此构建 棵 分 类 回 归 树，每 次 未 被 抽 到 的 样 本 组 成了 个袋外数据（，）。（）设有 个特征，则在每一棵树的每个节点处 随机抽取 个特征（ ），通过计算每个 特征蕴含的信息量 ，在 个特征中选择一个最 具有分类能力的特征进行节点分裂 。（）每棵树最大限度地生长 ，不做任何剪裁。（）将生成的多棵树组成随机森林 ，用随机森 林对新的数据 进 行 分 类 ，分类结果按树分类器 的 投票多少而定。以分为 和 两 大 类。方 法定义 给定一组分类 器 （ ），（ ）， 独立于后续采 取 的 机 器 学 习 算 法 ，可 以 较 快 地 排除一部分非关 键 性 的 噪 声 特 征 ，缩小优化特征子 集搜索范围，但 它并不能保证选 择出一个规模较 小的优化特征子集。 方法在筛选特 征 的 过程中直接用 所选特征子 集来训练分类器 ，根 据 分类器在测试集的性能表现来评价该特征子集的（），每 个 分 类 器 的 训 练 集 都 是 从 原 始 的 服 从随机分布的数据集 （，）中 随 机 抽 样 所 得，余 量函数（）定义为（，） （） ） （）优劣，该方法在计算效率上不 如 方 法，但 其 所选的优化特征子集的规模相对要小一些 。式中：（）是示性函数。（）本 文 以 随 机 森 林 算 法 为 基 本 工 具 研 究 特征选择 方 法，利 用 随 机 森 林 分 类 器 的 分类准确率作 为 特 征 可 分 性 判 据 ，基 于 随 机 森 林 算法本身 的 变 量 重要性度量进行特征重要性排 余量函数用于度量平均正确分类数超过平均错 误 分 类 数 的 程 度 ，余 量 值 越 大，分 类 预 测 越 可 靠。定义 泛化误差定义为序，利用序列后向 选 择 方 法 （ ， （，）（），）和 广 义 序 列 后 向 选 择 方 法（ ， ）选取特 征 子 集。 实 验 结 果 表 明，相 比 于 文 献中已 有 的 特 征 选 择 算 法，本 文 的 算 法 在 性能上有较大的提高。随机森林定义 随机森林是 一 个 由 一 组 决 策 树 分 类器 （，）， ，组成的集 成 分 类 器，其中是服从独立同分布的随机向量 ， 表 示随机 森 林 中决策树的个数，在 给 定 自 变 量 下，每个决策树 分类器通过投票 来决定最优的分 类结果。随机森 林 是 许 多 决 策 树 集 成在一起的分类 式中：下标 、 表示概率 覆盖 、 空间。在随 机 森 林 中，当 决 策 树分类器足够 多 ，（）（，）服从强大数定律。定理随着随机森林中决策树数量的增 加，所有序列， 几乎处处收敛于 ， （，） ） （，）（）定理表明随机森林不会随着决策树的增加而产生过拟合 问 题，但可 能会产生一定限度内的 泛化误差。变量重要性评估是随机森林算法的一个重要 特点。随机森林程序通常提供 种变量重要性度 量。本文采用基于袋外数据分类准确率的变量重 要性度量。第期姚登举，等：基于随机森林的特征选择算法定义 基于袋外数据 分 类 准 确 率 的 变 量 重 要性度量定义为袋外数据自变量值发生轻 微 扰 动后的分类正确率与扰动前分类正确率的平均减 少量。假 设有样本， 表示 训 练样本个数，特征 的基于分类准确率的变量 重要性度量 按照下面的步骤计算 ：（）设置 ，在 训 练 样 本 上 创 建 决 策 树，并将袋外数据标记为 。（）在袋外数据上使用 对 数据进行分轮迭代的分类精度 。具体过程如算法所示。 算 法 基于随机森林的特征选 择 算 法输入：原始数据集 输 出：验证集上的最大 分 类 正 确 率及其对应的特征集合 步骤：初 始 化读入原始数据集 设 置 （） 。类，统计正确分类的个数 ，记为 （）对于特征 ，对 中的 特征 的 值 进 行 扰 动，扰 动后的数据集记为 ，使用 对 数据进行分类，统计正确分类 将 数 据 集 随 机 划 分 成 等 份 设置局部最大分类准确率 设置局部平均分类准确率 初 始 化 折 交叉验证中每次迭代的分类准确 的个数，记为 率 。（）对于，重复步骤（）（）。（）特 征 的 变 量 重 要 性 度 量 通 过 下 面 的公式进行计算： （） 在 上 运 行创 建 分 类 器 在测试集上执行 进 行 分 类 （） （ ） 比较分类结果与观测值 ，计 算 计 算 定义 随机森林算法的分类准确率定义为 （） （ ） 则 式中：（）代 表 正 确 的 肯 定；（ ）代 表 正 确 的 否 定； （ ）代表 错 误 的 肯 定；（）代 表错误的否定。 本文算法 算法描述本 文 提 出 了 一 种 基 于 随 机 森 林 的 特征选择 方 法 ，利用随 机 森林算法的变量 重要性度量对 特 征 进 行 排 序 ，然 后采用序列后向 搜索方法，每次 从特征集合中去 掉一个最不重要 （重要性得分最小）的特征，逐次进行迭代，并计算 分类正确率，最终得到变量个数最少 、分类正确率 最高的特征集合作为特征选择结果 。为了保证实 验结 果 的 稳 定 性，本 文 采 用 了 折 交 叉 验 证 方 法，在每一次迭代中，将数据集划分成等份，利 用其中的份作为训练集用于构建随机森林分类 器，剩余的份作为验 证 集 数 据 进 行 验 证。 在 折交叉验证过 程 中，选择测试集上分类准确率最 高的一次迭代产生的变量重要性排序作为删除特 征的依据，将次迭代的平均分类准确率作为该对特征按变量重要性排序并存为 （ ）则 从 中 去掉重要性得分最低的一个特征 ， 得到新的数据集 输 出 结 果输出全局最高分类准确率 输出全局最高分类准确率对应的特征集合 注 ：代 表 循 环 变 量 ， 代表数据集中所有特征个数 。 时间复杂度分析本文所提出的随机森林特征选择方法中基分 类器选择 算 法。 假 设 训 练 数 据 集 的 特 征维 数为 ，训练样本个数为， 算法的时间复 杂 度 为 （ （）。 随机森林在构建 树的过程中，从 个 特 征 中 随 机 选 择 个特征计算信 息 增 益 ，并 且对树的生长不进行剪 枝，故 训 练每一个 基 分类器的计算时 间小 于（ （），假设随 机森林中基分类器的个 数为 个，则随 机森林算法的时间复杂度可以 近 似为 （ （）。在 本 实 验 中，采 用 序 列 后吉 林 大 学 学 报 （工 学 版 ）第卷向选择策略进行特征选择需要循 环 次，每 一轮循环中采用折交叉验证，需运行随机森林 算法 次，每 轮 循 环 需 对 特 征 子 集 进 行 排 序 ，采用 快 速 排 序 算 法 的 平 均 时 间 复 杂 度 为（），根据 排 序 后的 特征集合生成新的训 练数据集需要进行 次，每 次计算时间为常 数，故本算法总的时间复杂度可以近似表示为）（ ） （ （ ）（） ） （ （ ）（）由式（）可见， 算 法 的 时 间 复 杂 度 与 特 征维数 成近似平 方 关 系，与数据集样本个数 成近似立方关系，对于高维小样本数据 ，运算时间是可以接受的，算法具有较好的扩展性 。 实验结果及分析 实验数据与方法为便于比较，从 数 据 集 中 选 取 了 、 、 和 个 数 据 集 进 行 测 试。 表 列 出 了这些数据集 的 特 征 ，数据集维数从几个到数十 个不等。表 取 自 的 数 据 集 和冗余特征的 消除提高了分类器性能 ；当 分 类 准 确率到 达 最 高 值 后又开始呈现下降趋 势，则是因为有用的特征被消除 ，降低了分类器的 性能。这说明了本文算法能够有效地识别并消除 冗余特征和不 相 关 特 征 ，从而提高分类器的分 类 性能。图 分类精度与特征个数之间的关系 表 列 出 了 算 法 和 算 法、 算法在不同实验数据集上的性 能 比 较 ，其 中 列 表 示选出的最优特征子集中的特征个 数，列表示算法在实验数据 集 上 的 分 类 性 能 。 算法、 算法 在相应数据集上的实验 数据分别来自文献和文献，“”表示该算 法在相应数据集上没有进行实验 。表 不同算法的性能比较 序 号数 据 集维 数样 本 个 数分 类 数 目 本文算法采用 语 言 进 行 实 现，随 机 森 林 核心算 法 采 用 软 件 中 的 程 序 包，其中 参数 取 建 议 的 默 认 值 槡（ 为数 据 集训练 数 据 集中特征的个数 ）， 参 数 设 置 为 。实验的硬件环境为（） ， 的 内 存，操 作 系统 为 ，绘 图 软 件 采 用。 实验结果分析本文算法 在搜索实现最大分类准确率 的特征子集时 采用的是序 列后向搜索策略 ，特 征 选择 过 程 和 结 果 如 图 所 示。 从 图 可 以 看 出， 随着不重要特征 （在随机森林变 量重要性排序中 排在最后的特征）的依次删除，分类准确率整体上 呈现逐步提高 的 趋 势 ，这主要是因为不相关特征 从 表 可 以 看 出， 算 法 在 、 、和 数 据 集 上的分类正确率分别 为、，选 择 出 的 特 征 个 数 分 别为、。与 算法相比，算 法 在 特 征个数基本相 等或者更少的情况下 ，分 类 性 能 明 显优于 。 算 法 在 数 据 集 上 选 择的特征 个 数 与 算 法 相 等，分 类 性 能 略 低于 算 法；在 数 据 集 上， 算法选择 的 特 征 个 数 与 算 法 相 等，分 类 性能 略 高 于 算 法；在 数 据 集 上，第期姚登举，等：基于随机森林的特征选择算法 算 法 比 算 法 选 择 了 更 少 的 特 征 数 目，却获得了更高的分类精度 。从整体上看，本文 方法优于文献和 文 献 中 的 方 法。 实 验 结 果表明， 算法不 仅 能够 选择出较优的特征 子集，而且能够获得较高的分类性能 。另外，本文算 法 也 可 以 容 易 地 扩 展 为 使 用 广 义后向搜索策 略 进 行 最 优 子 集 搜 索 ，为 了 获 得 最 好的分类效果，本 文 对 删 除 “最 不 重 要 特 征 ”时 采 用 的 不 同 步 长 进 行 了 实 验 ，结 果 如 表 所 示。 从 表可以看出，在所有组实验中（依次删除个 到个特征），最高的分类性能是在每次删除一个 特征时获得。 需 要 说 明 的 是，每 次删除一个特征 并不是在所有 数 据 集 上 的 最 优 选 择 ，由 于 本 文 所 涉及的数据集 特 征 数 目 还