基于分类噪声检测的支持向量机算法研究

摘要

支持向量机(Support Vector Machine, SVM)是基于统计学习理论的一种优秀的机器学习方法。它在最基本的线性可分问题中，采用与结构风险最小化理论一致的间隔最大化原理产生原始凸规划问题模型，使得基本问题模型具有良好的泛化能力。并且由于模型是凸规划模型，所以能够获得全局最优解。在获得这些良好特性的基础上，通过引入惩罚系数和惩罚因子来获得线性不可分问题的问题模型。并通过进一步使用核函数理论来解决非线性问题，从而避免了维数灾难。由于其优异的性能，已经广泛应用于模式分类，密度估计和函数逼近等领域，成为机器学习中的研究热点。
　　本文围绕支持向量机在分类问题中的训练过程和过学习现象，瞄准高维数据中的相对密度计算及与支持向量机的结合为关键问题，以提高支持向量机的训练速度为主要目的，其具体的研究成果主要包括以下几个内容：
　　①通过分析分类问题中噪声数据的特点，引入分类噪声的概念，提出了相对密度模型对其进行检测。分类问题中的噪声数据会明显减弱决策曲线的平滑度，降低决策函数的泛化能力，从而引起过拟合，因而挖掘这些噪声数据具有重要意义。本文针对现有算法无法有效检测分类问题中的噪声数据的问题，基于噪声数据在同类样本集合中的样本密度要小于在异类样本集合中的样本密度，引入了分类噪声的概念，进一步提出了相对密度模型来对分类噪声进行快速有效地检测。仿真实验表明相对密度模型能够很好的识别分类噪声。
　　②通过排除分类噪声将不可分问题转化为可分问题，简化了支持向量机模型和训练过程，并结合序列最小优化（Sequential Minimal Optimization, SMO）算法，提出了基于分类噪声检测的序列最小优化算法（Classification Noises Detection based Sequential Minimal Optimization, CNSMO）。针对现有的支持向量机在训练过程中依赖交叉验证会大幅增加训练时间的问题，CNSMO算法通过排除分类噪声后平滑了决策函数，避免了分类噪声产生的过学习现象，因此在训练过程中不需要使用交叉验证也能够获得良好的预测精度。同时，由于排除分类噪声将不可分问题转化为可分问题，不需要对惩罚系数进行寻优，简化了拉格朗日参数迭代模型。仿真结果表明改进算法能够在不牺牲算法预测精度的前提下，大幅缩短了支持向量机的训练时间，算法具有良好的稳定性。
　　③通过计算到某些固定参考点的度量来衡量不同样本之间的位置差异，以避免直接计算样本之间的欧式距离，提出了基于位置差异的近邻搜索算法(Location Difference based Algorithm，LDBA)。针对在相对密度计算中使用的现有近邻算法在高维数据集中性能下降的问题，LDBA算法使用参考点与样本所构成的角度和距离来度量不同样本点之间的位置差异，避免对样本之间的欧式距离直接进行计算，因此具有较低的算法时间复杂度。另外，LDBA算法不依赖索引树结构，因此在高维数据集中仍然能够保持良好的算法效率。仿真结果表明LDBA算法具有和基本算法接近的预测精度，但比同类算法在高维数据集中表现出了更好的算法效率。
　　④通过将LDBA算法结合到CNSMO算法中，提出了基于位置差异和分类噪声的最小序列化支持向量机算法(Location Difference and Classification Noise based Sequential Minimal Optimization,LD-CNSMO)。针对CNSMO算法在高维数据集中性能下降的问题，将LDBA算法结合到相对密度的计算过程中以检测和消除分类噪声，提出了LD-CNSMO算法。由于LDBA算法不依赖树索引结构，因此LD-CNSMO算法能够在高维数据集中保持良好的算法效率。仿真结果表明LD_CNSMO算法在高维数据集中能够获得比CNSMO和其他算法更好的算法效率。
　　本论文引入分类噪声后，通过使用基于LDBA的相对密度模型进行检测和排除分类噪声，并结合到SMO支持向量机中，避免了在支持向量机训练过程中使用交叉验证。在不影响算法泛化能力的情况下，大幅度提高了算法在低维和高维数据集中的训练效率，并增强了算法稳定性，有效地提高了支持向量机的算法性能。

目录

封面

中文摘要

英文摘要

目录

主要符号对照表

1 绪 论

1.1 研究背景

1.2 支持向量机的研究现状

1.3 论文的研究意义和主要内容

1.4 本文的结构安排

2 支持向量机理论基础

2.1 统计学习理论

2.2 最优化理论

2.3 支持向量机

2.4 序列最小优化算法

2.5 本章小结

3 基于分类噪声检测的低维支持向量机

3.1 研究背景与问题分析

3.2 分类噪声

3.3 使用相对密度检测分类噪声

3.4 基于分类噪声检测的序列最小优化算法

3.5 仿真实验分析

3.6 本章小结

4 基于位置差异的高维相对密度算法

4.1 基于位置差异的近邻搜索算法

4.2 仿真实验分析

4.3 基于位置差异的高维相对密度算法

4.4 本章小结

5 基于位置差异和分类噪声检测的支持向量机

5.1 基于位置差异和分类噪声检测的支持向量机

5.2仿真实验分析

5.3 本章小结

6 总结和展望

6.1 取得的成果和创新点

6.2 未来的工作展望

致谢

参考文献

附录

A. 作者在攻读学位期间以第一作者发表的相关论文目录：

B. 作者在攻读学位期间参加的相关科研项目：