非监督特征约简算法的研究与应用

论文摘要

在机器学习、模式识别、信息检索和生物信息等很多领域人们都面临海量的高维数据,由此引发维数灾难问题。特征约简旨在解决上述难题,其任务是将原始特征空间映射到一个低维空间,以期在降低维数的同时,保持原空间的重要信息。特征约简可大致分为特征抽取和特征选择两部分。特征抽取试图获得原始特征的线性或非线性组合,以期去除特征间的冗余性;特征选择试图选择与学习任务最相关的特征,以期去除噪声特征。由于在非监督背景下缺少类别信息,使得特征约简尤其是特征选择任务,变得异常困难。流形学习是特征抽取的一个重要分支。本文提出了一种局部线性镶嵌(Locally Linear Inlaying, LLI)方法。LLI是一种流形学习方法,该类方法假设原始高维空间分布在或近似分布在一个低维非线性流形之上。LLI利用分而治之的策略,将高维空间中的各个线性区域进行局部嵌入和全局拼接。该算法可以在很大程度上改善流形学习算法的时间复杂度和鲁棒性,具体表现在:第一,LLI的时间复杂度与样本点数目成线性关系;第二,LLI可以适用于任何非凸的数据集;第三,LLI有很高的鲁棒性,能够很好的工作于存在异质噪声或同质噪声的数据集。基于仿真数据和真实人脸数据的实验证实了LLI的上述特点。针对特征选择任务,因为原特征集中存在大量噪声特征,这些特征会严重干扰合理的测度(即中肯的测度),使得特征空间变得不中肯。当前大部分非监督特征选择算法因为缺少测度不变的性质,在强非中肯空间中其效果会很差。本文提出了一种处理非中肯空间的测度不变性模型,该模型基于以下重要观察:如果指导非监督特征选择的统计量在测度缩放时保持不变,那么特征选择模型的解也将是不变的;如果这个模型在一个中肯的特征空间中可行,它也将在由于测度缩放后得到的非中肯空间中可行。本文从理论上证明了该模型的测度不变性,基于仿真数据和真实文本数据的实验结果证实了该模型的有效性。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 研究背景和目的
• 1.2 研究现状
• 1.2.1 特征抽取研究现状
• 1.2.2 特征选择研究现状
• 1.3 本文结构
• 第二章 相关工作
• 2.1 特征抽取相关工作
• 2.1.1 线性方法
• 2.1.2 非线性流形学习方法
• 2.2 特征选择相关工作
• 2.2.1 包装器方法
• 2.2.2 过滤器方法
• 第三章 局部线性镶嵌特征抽取算法
• 3.1 局部线性镶嵌算法（LLI）
• 3.1.1 算法框架
• 3.1.2 分片
• 3.1.3 片的嵌入
• 3.1.4 近似最优拼接顺序
• 3.1.5 拼接过程的形式化
• 3.1.6 近似最优拼接顺序的解析分析
• 3.2 算法时间复杂性分析
• 3.3 实验
• 3.3.1 时间效率分析
• 3.3.2 空洞Swiss roll 数据集
• 3.3.3 噪声Swiss roll 数据集
• 3.3.4 同心圆数据集
• 3.3.5 真实数据集二维嵌入
• 3.3.6 三维嵌入
• 3.4 算法小结与讨论
• 第四章 测度不变性特征选择方法
• 4.1 符号和定义
• 4.2 研究动机
• 4.3 测度不变性模型形式化
• 4.4 测度不变性证明
• 4.5 基于测度不变性模型的特征选择算法及实现
• 4.6 实验
• 4.6.1 实验设置
• 4.6.2 实验数据
• 4.6.3 聚类效果实验
• 4.6.4 特征空间分布实验
• 4.7 算法小结与讨论
• 第五章 总结与展望
• 5.1 特征抽取算法总结与展望
• 5.2 特征选择算法总结与展望
• 参考文献
• 发表论文和参加科研情况说明
• 致谢