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

本资料包含pdf文件1个，下载需要1积分

支持向量机基于统计学习理论，最优化理论以及核函数等理论，将输入空间中的样本通过核函数映射到更高维的特征空间，在此特征空间求解出-个最优超平面对其进行类别划分。

其对核函数的引进不仅可以将支持向量机由线性划分推广到非线性划分问题，而且有效地克服了 维数灾难”。由于以上优点，使得支持向量机成为了机器学习领域研究的热点。

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

-、 支持向量机理论支持向量机是模式识别中-种较新的方法，其核心理论是，对于输入训练样本点(xi，Yi)，i1n， ∈ ，Y∈-l，l1分类超平面方程为(W· )60，求解最优超平面的问题可化为如下二次规划问题：可通过引入核函数K(x· ) )· (J，)的办法将其转化为高维特征空间的线性划分问题，由此可得非线性支持向量机的对偶问题为maxL(a)-Za，-。ZXYiYJafa， ( · )i1 i1 Jl-t∑y，a o，O

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

二、基于二阶段法的凸壳支持向量机(-)-种求凸壳的算法STEP1.假设样本点是m维向量，则各维上具有最大值或最小值的样本点必是顶点。用这些样本点组成初始顶点集D ， ，， )，， 2m，并令k，，J，1；STEP.2令G G-Dt -， )，从G 中取 ，用D中的样本点表示该点；STEP3.如果线性规划无解，则把 加入D中；否则跳到STEP4：STEP4.求D的顶点集D，，并赋给D；STEP5.输出D为由G生成的凸壳s的顶点集，结束。

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

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

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

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

具体实验数据结果见下表：所有样本点 凸壳顶点lWl 2 287458478O8 27014441991Margin 0.000012 O.Oo0012Sum alpha 28757987121 27039937355消耗时间 18.5780O0 14.437000可以看出，在非线性情况下，凸壳的求解训练效果基本相同，而新型分类机要比原始分类机所耗费时间少22.29%。

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