1 1 特征抽 取
特征抽 取也 被 称为 特征 重 参数 化 ( feature repa rame teriza
tion) [ 1] 。由于自然语言中存在大量 的多义 词、同 义词现 象, 特
征集无法生成一 个最优的特 征空间 对数据 内容进行 描述。特
征抽取通过将 原始 特征 空间 进行 变换, 重 新生 成一 个维 数更
K ira和 R endell提出的 R elief算法 [8] 是一个比较著名的特 征权重类方法, 主要根据特征值在同类实例中以及相近的不同 类实例中的区分能力 来评价 特征的 相关度。首 先从训 练集中 随机抽取 m 个实例, 再根据被选实例与两个最 近实例 ( 一个同 类最近实例, 一个相反类最近实例 )的差 异来更 新每个 特征的 相关度评价, 依赖相 关度评 价进 行特征 选择。其 对于 含 M 个 实例、N 个特征的数据集 R e lie f的时间复杂度为 O ( mMN )。因 此, 该算法很适合于处理 具有大 量实例 的高维 数据集。但 是, R e lief不 能消除冗余特征, 只要特 征被认 为与类 概念相 关即被 选中, 即使这些特征之间 相互高 度关联。 近几年, 许多 学者纷
Ab stract: F ea ture dmi ension reduction is effective in mi p rov ing m achine learn ing, the po int is how to search the subset and selection cr iter ia. T h is paper defined genera lm ode ls for dmi ension reduction, com pared d ifferent appro aches, and discussed the un reso lv ed topics and deve lopm en t trends. K ey words: dmi ension reduction; m ach ine learning; feature selection; feature abstraction; se lection cr iter ia
小、各维之间更独立的特征空间。可以按照表 1对特征抽取算
法进行分类。
表 1 特征抽取方法分类
有无指导 无 无 无 有
线性
主成分分析 ( PCA ) 独立成分分析 ( ICA)
投影追踪 线性区别分析
非线性
K oh onen 匹配 非线性 PCA 网络
Samm on投影 非线性区别分析
1 2 特征选 择
纷就 R elie f的改进提出了各种建 议, 如 Sun Y i jun最新 提出的 I R elie f算法 [ 9] 通过探索期望最大化算法的框架, 认为迭代 R e lie f算法能够减轻 R e lief的不 足, 并使 用新的 多类 别边缘 定义 将 I R elief扩展至多类别设置, 同时减少计算开销、发展在线学 习算法。
特征权重算法为 每个特征指定一个权值, 并按照它与目标 概念的相关度对其进 行排序, 如果一个特征的相关度权值大于 某个阈值, 则认为该特征 优秀, 并且 选择该特 征。特征 权重算 法的缺点在于: 它们可以捕 获特征 与目标 概念间的 相关性, 却 不能发现特征间的冗 余性。经验 证明除 了无关 特征对 学习任 务的影响, 冗余特征同样影 响学习 算法的 速度和准 确性, 也应 尽可能消除冗余特征 。
摘 要: 特征降维能够有效地提高机器学习的效率, 特征子集的搜索过程以及特征评价标准是特征降维的两个
核心问题。综述国际上关于特征降维的研究成果, 总结并提出了较完备的特征降维模型定义; 通过列举解决特
征降维上重要问题的各种方案来比较各种算法的特点以及优劣, 并讨论了该方向上尚未解决的问题和发展
趋势。
HU J ie ( a. L abora tory of M ach in e P erception, b. D ept. of M ach in e In te llig ence, School of E lectron ics E ng ineering & Compu ter S cience, c. Institu te of D ig ital L ibra ry, P eking Un iversity, Be ijing 100871, Ch ina )
2 特征降维模型
特征降维是一个 从初始高维 特征集 合中选 出低维 特征集 合, 以便根据一定的评估准则最优化缩小特征空间的过程。综 合国际上现有 的特 征降 维模 型, 可以 将特 征降 维模 型作 如下 定义。
定义 1 特征降维模型是一 个四元 组 { F, S, P, R ( si, fj ) }。 其中:
2 1 2 子集搜索算法 子集搜索算 法通过在一定 的度量标 准指导 下遍历 候选特
征子集, 对每个子集进行优 劣评价, 当搜 索停止 时即可 选出最 优 (或近似最优 )的特征子集。现 有子集搜索 算法的时 间复杂 度至少为维度的 平方, 所以在处理高维数据时不具有强可量测 性。 N akariyaku i和 C asasent最新提出的 分支跳 跃算法 [ 10] 通过 避免对解决方案 树中某些节点 不必要的 评价函 数计算 来提高
特征降维 ( feature d im ension reduction) 是一 个从初始 高维 特征集合中选出低维 特征集合, 以便根据一定的评估准则最优 化缩小特征空间的过 程, 通常作为机器学习的预处理步骤。特 征降维自 20世纪 70年代 以来就 获得了 广泛的 研究。近 几年 以来, 在许多应 用 ( 如基 因 染色 体 组 工程、文 本 分 类、图 像检 索、消费者关系管理 )中, 数 据的 实例 数目 和特 征数 目都 急剧 增加, 这种数据的海量性使得大量机器学习算法在可测量性和 学习性能方面产生严 重问题。例如, 高维数据即具有成百上千 特征的数据集, 会包含大量 的无关 信息和 冗余信息, 这 些信息 可能极大地降低学 习算法 的性能。因 此, 当面临高 维数据 时, 特征降维对于机器学 习任务 显得十 分必要。大 量研究 实践证 明, 特征降维能够有效地消 除无关 和冗余 特征, 提高挖 掘任务 的效率, 改善预测精确性等 学习性 能, 增 强学习 结果的 易理解 性。然而, 数据在数量和维度上的剧增趋势也对特征降维算法 提出了更加严峻的挑 战。本文给 出了特 征降维 的相关 概念介 绍, 概括了目前国际上常用 的特征 降维模 型、特 征降维 领域的 重要问题 特征选 取的评价标准, 并且通过列举不同的解决 方案, 比较这些方案的特点。
L i等人 [11]提出 的多层 过滤模 型中 首先使 用 R elie fF[ 12] 通 过为每个特征指 定相关权重来 移除无关 特征。 R e liefF 算法是 针对 R elie f的改进算法, 它具有鲁棒性, 能够 处理不完整 数据、 噪声数据以及多 重类别问题, 然而在移除冗余数据方面效率较 差。因此, L i等人又在 系统 中使 用特 征聚 类算 法 KNNC[ 13] 来 消除冗余特征。假设训练样 本数为 s, 原始 特征数 为 n, 则 R e lie fF 和 KNN C的 时间复 杂度 分别为 O ( s2 n )和 O ( n2 s) 。使用 多层过滤模型对 海量特征进行特征选择时, 应当将时间复杂度 低的 算法 先于 其他 算法 运行。 如果 n > > s, 则 KNNC 应 当在 R e lie fF 之后 运行 (记 为 R + K ) , 以 R elie fF 的 输出 作为 KNNC 的输入; 如果 s > > n, 则 KNN C 应先 于 R e lie fF 运 行 ( 记为 K + R ), 并将 KNN C的输出作为 Re lie fF 的输入。因为 R + K 时 R e lie fF 过滤 得到的 特征 具有权 重, 所以 在 KNNC 进 行特征 选择 后, 应当再对余下的未选中 特征进 行逐个 检查, 以确定 该特征 是否基于局部有 效而非基于 全局判 断。如果某 特征权 重大于
a) F 是特征集合中的一组特征逻辑视图, 称为特征的表示; b) S 是一组目标特征需求的逻辑视图, 称为降维目标; c)P 是一种机制, 用 于构建特 征表 示、降 维目 标及它 们之 间关系的模式; d) R ( si, fj ) 是排 序函数, 该函 数输出 一个与 降维 si ∀ S 和 特征表示 fj∀ F 有关的实数, 这样就在 特征之间 根据降 维目标 si 定义了一个顺序。 可以将现有的特 征降维模型大致分为过滤模型、包裹模型 及其他改进模型。
特征选择就 是从特征集 T = { t1, , ts } 中选择一 个真子集 T!= { t1, , ts! }, 满足 ( s!< < s )。其中: s 为原始特征集的大小; s!为选 择后的特征 集大小。 特征选 择不 改变原 始特 征空 间的 性质, 只是从原始特征空间 中选择 一部分 重要的特 征, 组成一 个新的低维空间 。
2 2 多层过 滤模型
考虑到各种 过滤方法各有优劣, 可以使用多层过滤模型分 别消除无关特征 和冗余特征。 多层过滤 模型不 仅能够 保留各
种过滤算法的优 点, 而且该模型易于理解和执行。对于消除无 关特征和冗余特征的次 序, 模型中 没有明 确限定, 可以 根据数 据集合的特点 以及 应用 特性, 选 择适 合的 过滤 算法 及过 滤步 骤。多层过滤模型的框架 如图 1所示。
关键词: 降维; 机器学习; 特征选择; 特征抽取; 评估准则
中图分类号: TP181
文献标志码: A
文章编号: 1001 3695( 2008) 09 2601 06
Survey on feature dim ens ion reduction for h igh dim ensiona l data