基于二阶段法的新型凸壳支持向量机研究

开篇：润墨网以专业的文秘视角，为您筛选了一篇基于二阶段法的新型凸壳支持向量机研究范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

［摘要］支持向量机由于引入了核函数，将线性划分推广到非线性划分问题，而且有效地克服了“维数灾难”，使得支持向量机成为了机器学习领域研究的热点。但其执行效率低也是普遍存在的问题。本文引入凸壳理论并运用二阶段法对凸壳进行必要的改进，从而提升支持向量机的执行效率。

［关键词］凸壳 二阶段法 支持向量机

［中图分类号］TH17 ［文献标识码］A ［文章编号］1009-5349（2012）11－0071－01

引言

支持向量机基于统计学习理论，最优化理论以及核函数等理论，将输入空间中的样本通过核函数映射到更高维的特征空间，在此特征空间求解出一个最优超平面对其进行类别划分。其对核函数的引进不仅可以将支持向量机由线性划分推广到非线性划分问题，而且有效地克服了“维数灾难”。由于以上优点，使得支持向量机成为了机器学习领域研究的热点。

但是支持向量机执行效率低也是普遍存在的问题，将其引入到服务器性能分析中来需要必要的改进。本文提出的一种基于二阶段法的凸壳算法正是在此背景下提出的一种快速算法。先将输入空间中的样本点通过核函数映射求出其凸壳，然后将凸壳通过支持向量机进行分类，从而达到减少输入样本点的目的，进而提高支持向量机的执行效率。实验结果表明，新算法是有效可行的。

一、支持向量机理论

支持向量机是模式识别中一种较新的方法，其核心理论是，对于输入训练样本点，分类超平面方程为，求解最优超平面的问题可化为如下二次规划问题：

可通过引入核函数的办法将其转化为高维特征空间的线性划分问题，由此可得非线性支持向量机的对偶问题为

由此，只要求出此问题的解，即可得到最优分类超平面。

由于训练样本点中起分类作用的只是支持向量，而支持向量又一定是凸壳的子集，因此可通过先求凸壳再分类的方法来降低训练样本数目，从而达到提高支持向量机执行效率的目的，下面给出求凸壳的一种方法。

二、基于二阶段法的凸壳支持向量机

（一）一种求凸壳的算法

STEP1.假设样本点是m维向量，则各维上具有最大值或最小值的样本点必是顶点。用这些样本点组成初始顶点集，，并令，；

STEP.2令，从中取，用D中的样本点表示该点；

STEP3.如果线性规划无解，则把加入D中；否则跳到STEP4；

STEP4.求D的顶点集，并赋给D；

STEP5.输出D为由G生成的凸壳S的顶点集，结束。

整个算法的关键在于线性规划是否有解的判定上来，由此通过线性规划中的二阶段法来进行判断。

（二）二阶段法判定方程组是否有非负解

对于STEP3的线性规划问题，单纯形法是求解的有效手段，而且不必将最后的解迭代求出，只需判断是否有初始解即可。由此引入二阶段法中的第一阶段来确定是否存在初始可行解。判定方法为首先构造一个新的辅助线性规划问题 然后判断此辅助线性规划问题是否有最小值0，如果有，则原问题有初始基可行解，否则无解。

至此，用此方法求出的凸壳可以直接在支持向量机中进行分类，由于训练样本的减少，必将提高分类的速度。

（三）Iris仿真结果

为验证上述算法，本文采用UCI数据库中的Iris标准数据集。该数据集包含三类鸢尾花：硬刺类（Iris-setosa），变色类（Iris-versicolor）和含羞类（Iris-virginica）。三种不同类型的花各有50组数据。每组数据包含鸢尾花的四个属性：萼片长度（sepal length）、萼片宽度（sepal width）、花瓣长度（petal length）和花瓣宽度（petal width）。为了直观起见，本文只采用花瓣长度和花瓣宽度两维数据，并对重复数据进行剔除。

具体实验数据结果见下表：

可以看出，在非线性情况下，凸壳的求解训练效果基本相同，而新型分类机要比原始分类机所耗费时间少22.29%。

三、结论与展望

根据对Iris仿真实验来看，本文提出的基于二阶段法的新型凸壳支持向量机是有效可行的，训练效果基本相同的情况下，训练时间有所减少。本文只是对基于二阶段法的新型凸壳支持向量机进行了初步探讨，而对于该新型支持向量机的进一步应用则是未来的研究方向。

【参考文献】

[1]基于支持向量机的故障智能诊断方法研究.

[2]凸壳顶点集在支持向量分类机中的应用研究.