0-1规划及其在特征提取中的应用

论文摘要

特征选择是模式识别以及数据挖掘中的一个重要组成部分。随着机器学习和数据挖掘在实际领域中的广泛应用,使得特征子集选择算法研究逐渐成为人工智能领域的一个研究热点。特征选择问题的主要目的是期望能够在不明显降低识别系统性能的基础上选择最小的特征子集。近几年,对特征选择领域的研究有很多新的成果,本文对部分新兴理论做了理论阐述和方法介绍。 0—1二次规划问题是一个已知的NP—hard问题,具有广泛的应用。本文对近年来0—1二次规划问题的研究成果进行了探讨,提出了用梯度法求解0—1二次规划问题,并在此基础上提出了基于0—1规划的特征选择梯度算法。 本文的主要工作如下:1、对特征选择进行了较全面的学习和研究,阐述了特征选择的组成部分和模式, 介绍了一些有代表性的特征选择方法,并从构成现有的特征选择算法的三个 重要的方面:评判特征子集优劣的指标、搜索策略和搜索方向对现有的特征 选择算法进行了分析。 2、研究了0—1二次规划的基本理论和近阶段的成果,提出了用梯度法求解O一1-- 次规划问题的新方法,该算法是一个基于按梯度方向搜索的启发式算法。算 法通过构造一个新的目标函数,然后根据某一点的梯度的方向是目标函数在 该点的函数值增长最快的方向这一原则,提出To一1二次规划的梯度算法,对 0一l二次规划问题求解,以达到加快求解速度的目的。并用实验加以验证该方 法的可行性。 3、从0—1二次规划问题的研究出发,结合“盒分类器’’的概念,将特征提取问题 归结为0—1规划问题。在此基础上,采用上述梯度法求解0—1规划问题。提出 了基于O一1规划的特征选择梯度算法,并用实验加以验证,分析表明:采用基 于0—1规划的特征选择梯度算法获得的特征具有较强的代表性,而且算法具有 较快的求解速度。

论文目录

• 第一章 引言
• 1.1 研究背景
• 1.2 特征选择的基本概念
• 1.3 本文的主要研究任务
• 第二章 0-1二次规划问题（BQP）综述
• 2.1 BQP问题简介
• 2.2 求解BQP问题的确定性算法
• 2.3 求解BQP问题的启发式算法
• 2.4 求解BQP问题的改进的贪心和局部搜索算法
• 第三章 0-1二次规划问题的梯度法
• 3.1 基本概念
• 3.2 0-1二次规划问题的梯度法
• 3.3 算法性能评估
• 第四章 特征选择方法概述
• 4.1 类别可分性判据
• 4.2 特征选择算法
• 4.2.1 特征子集生成
• 4.2.2 评估准则
• 第五章 基于0-1规划的特征选择方法
• 5.1 基本概念
• 5.2 基于0-1规划的特征选择算法
• 5.3 实验结果
• 第六章 总结和展望
• 参考文献
• 致谢