局部支持向量机算法的研究与探讨

论文摘要

现有的各种支持向量机算法，原则上都可以归纳为凸二次规划问题直接求解。这些算法需要存储与训练集相应的核矩阵，很多学者针对如何提高训练速度和效率提出众多改进算法，比如选块算法、分解算法和序列最小最优化算法，其目的在于将大规模的原始问题分解成若干个小规模的子问题，按照某种迭代策略，反复求解子问题，构造出原始问题的近似解。但是当面对数据集为凹集时，SVM算法以及改进的算法都需要进一步完善来解决此类问题。支持向量机的学习效率与识别正确率依赖于边界的样本分布曲面的特性。本文基于样本空间稀疏化技术结合FCM算法建立了局部支持向量机算法（Local Support VectorMachine），试图通过局部化技术模拟或近似逼近样本的分布曲面。研究内容主要包含下述三个方面：(一)基于稀疏化技术利用Floyd算法与FCM算法对样本空间的分割。类与类之间的分离度直接影响SVM算法的分类有效性；样本数，分类数的大小直接关系到SVM算法的计算量。依据最大分离原则，利用Floyd（或者Dijkstra）算法合并分类样本空间，直至为两类（这样可能会导致非凸分类问题的产生）。为了达到FCM算法对样本空间的有效剖分，利用最邻近准则与距离或贴近度来删减样本从而达到稀疏化样本空间的目的。然后利用加权FCM算法完成对样本空间的第一次剖分。(二)利用贴近度分离两类间的中间带。为了解决两邻近剖分部分的样本归属问题，也为了保证识别过程的SVM算法的有效性，利用贴近度、贴近度之比作为新的特征，分离出两邻近剖分块的中间带，达到对样本空间的第二次剖分，粗划分到此结束。(三)对样本子集进行细剖分在上述剖分的基础上，考虑到除中间带剖分块外的样本空间部分，仍然可能较为复杂，例如有可能存在比较复杂的凹集。一直循环上面两个步骤继续对剖分块进行细剖分，提高训练效率。本文最后以UCI数据库中的waveform数据集为例来检验上述算法的有效性，现有最好的识别效果为86.1%，本文的结果为87.8%，当对样本进行三次剖分时计算量只有原来的1/18，如果继续剖分，训练效率与识别效果可能会更好。

论文目录

• 摘要
• ABSTRACT
• 第1章 绪论
• 1.1 支持向量机的研究现状
• 1.2 FCM 算法的研究现状
• 第2章 模糊聚类算法
• 2.1 传统的FCM 算法
• 2.2 带有权重的FCM 算法
• 2.3 PCM 算法
• 第3章 支持向量机算法
• 3.1 最优分类面
• 3.2 线性可分支持向量机
• 3.3 线性不可分支持向量机
• 3.4 非线性支持向量机
• 第4章 最短路径算法
• 4.1 单源最短路径：Dijkstra 算法
• 4.1.1 算法基本思想
• 4.1.2 算法的具体描述
• 4.2 任意一对顶点之间的最短路算法： Floyd 算法
• 4.2.1 算法的基本思想
• 4.2.2 算法基本原理
• 4.2.3 Floyd 算法实现的基本步骤
• 第5章 样本的稀疏化
• 5.1 基于贴近度的样本的稀疏化
• 5.1.1 贴近度的定义
• 5.1.2 样本的稀疏化
• 5.2 基于小球填充的样本的稀疏化
• 第6章 局部支持向量机
• 6.1 基于稀疏化技术的样本空间的粗划分
• 6.2 利用贴近度分离两类间的中间带
• 6.3 对样本子集进行细划分
• 6.4 局部支持向量机的实现步骤
• 6.5 实验结果
• 第7章 总结和展望
• 参考文献
• 致谢
• 附录A
• 攻读学位期间的研究成果