一种基于支持向量机中分离超平面求取的算法*

易校石， 刘 念

(1.重庆师范大学 数学科学学院，重庆 401331； 2.重庆大学 数学科学学院， 重庆 401331)

0 引 言

支持向量机(Support Vector Machines， SVM)是由Vapnik等人提出的一种分类算法。此算法在解决小样本、高维、非线性的模型中起到关键作用，且这种学习算法在许多领域的分类问题中获得了成功的应用[1-6]，成为浅层统计学习算法的优秀代表。有很多学者将支持向量机进行多方面的改进，作为深度机器学习的算法[7-11]。它归结于求解凸二次规划问题，虽然该凸二次规划问题有唯一的最优解，但随着训练样本容量的增加，算法变得比较低效，如何快速高效学习支持向量机就变为一个重要的且需要解决的问题。有很多的文献直接调用数学软件或统计软件进行计算，但对算法本身不了解，更不用说创新。本文对支持向量机分离超平面的求解算法采用迭代算法，充分利用支持向量机的特点，分离超平面首先要将样本训练数据集完全分开，其次是正类支持向量和负类支持向量到分离超平面的距离相等。将感知机算法获得的完全分离训练数据集的超平面进行旋转和平移，直到几何间隔达到最大且完全分离训练集。此时的分离超平面就是支持向量机的分离超平面。

1 问题的表述

假设给定一个训练数据集：

T={(x1,y1)，(x2,y2)，…，(xN,yN)}

其中xi∈X=Rn,yi∈{+1,-1}，1≤i≤N，xi为第i个特征向量，也称为第i个实例，yi为xi的类标记，当yi=+1时，称xi为正实例，当yi=-1时，称xi为负实例 ，(xi,yi)称为训练样本点。

感知机是一个二分类器，目标是在特征空间上学习一个分离超平面ωx+b=0，分离超平面由法向量ω和截距b决定，可用(ω,b)来表示。但感知机的分离超平面学习时误分类点达到最少，因而学习的分离超平面是不唯一的，如图1所示，x1,x2是正类点，x3是负类点，存在无穷多个超平面将正类点和负类点完全分开，但对测试集就有可能存在误分类点，因此对测试集和待预测分类集的分类效果不理想。

支持向量机是在感知机的思想上发展起来的，在特征空间上学习一个分离超平面，但有别于感知机的分离超平面，它引入了函数间隔和几何间隔的概念，寻找几何间隔最大的分离超平面，这个分离超平面是唯一的，并将求解间隔最大的分离超平面问题转化成如下的凸二次规划(Convex Quadratic Programming)问题。

求得最优解ω*,b*，但求解这个凸二次规划算法很多，需要较好的基础，很多文献是调用软件进行计算。此处不去解凸二次规划，直接采用迭代方法。

图1 感知机的分离超平面

图2 支持向量机的分离超平面

对于给定的数据集T和超平面(ω,b)，(xi,yi)为T中的一个实例，则(xi,yi)与超平面的几何间隔为

定义超平面(ω,b)与数据集T的几何间隔为T中所有实例与超平面(ω,b)的几何间隔的最小值，即

实例点(xi,yi)与超平面(ω,b)的几何间隔一般是实例点到超平面的带符号的距离(Signed Distance)，当实例点被超平面正确分类时就是实例点到超平面的距离。

支持向量机的分离超平面就是求得一个几何间隔最大的分离超平面。具体地，这个问题可以表示为下面的约束最优化问题：

2 迭代算法

由于支持向量机是从感知机发展而来，由感知机的迭代算法可知：当一个实例点被误分类，即位于分离超平面的错误一侧时，则调整w和b的值，使分离超平面向该误分类点的一侧移动，以减少该误分类点与超平面间的距离，直至超平面越过该误分类点使其被正确分类。迭代出的分离超平面依赖于初值的选择和迭代过程中误分类点的选择顺序，选取不同的初始值和误分类点的不同顺序，将得到不同的分离超平面。为了得到唯一的分离超平面，需要增加约束条件，由感知机发展为支持向量机，那么可以由感知机的迭代思想迭代出支持向量机的分离超平面。采用两个阶段进行迭代：第一阶段用感知机迭代算法迭代出一个能将训练数据集完全正确分开的超平面作为支持向量机分离超平面的初始值；将初始分离超平面进行旋转和平移，直到几何间隔达到最大。

支持向量机新算法如下：

线性可分数据集：

T={(x1,y1)，(x2,y2)，…，(xN,yN)}

xi∈X⊆Rn,yi∈Y={+1,-1}

i=1,2,…,N

学习率：η(0<η≤1).

输出：ω和b；

支持向量机模型y=f(x)=sing (ω·x+b)。

阶段1 获取支持向量机的初始超平面。

步骤1 设置初值ω=ω0和b=b0

步骤2 在数据集中选取数据(xi,yi),i=1,2,…,N。

步骤3 如果yi(ω·xi+b)≤0，则更新ω和b：

ω←ω+ηyixi

b←b+ηyi

步骤4 转至步骤2，直到训练集中没有误分类点，得到支持向量机的初始分离超平面：

阶段2：获取支持向量机的分离超平面。

步骤6：在正例数据集和负例数据集中分别寻找到分离超平面距离最近的点，设正例集和负例集分别为T1和T2，计算

步骤7：若|d1-d2|<ε，选取距离d1和d2中任意一对应点(x,y)：

ω*=ω*+εy·x

b*=b*+ε·y，转至步骤6；

若d1,d2同时增大，转至步骤8；

若d1,d2一个增大，一个减小，转至步骤9。

ω*=ω*+η1y·x

b*=b*+η1·y

步骤9：输出支持向量机的分离超平面

ω*=ω*-εy·x

b*=b*-ε·y

ω*·x+b*=0

3 算法检验

为了检验算法的有效性，选取鸢花数据中setosa和versicolor作为样本数据集，将setosa作为负类(记为-1)，versicolor作为正类(记为+1)，每个鸢花数据包含Sepal.Length ，Sepal.Width 两个特征。记第i个样本点为xi=(xi1,xi2)，其中xij表示第i个样本点的j个特征，样本容量取100。选取了感知机迭代算法分离超平面的3个，包括任取误分类点、取误分类点与分离超平面最近点和最远点进行迭代与本文算法迭代的分离超平面进行比较。迭代算法的分离超平面和线条颜色如表1所示，绘出的图形如图3所示。

表1 迭代算法及线条颜色Table 1 The iteration algorithms and line colors

图3不同算法的分离超平面

Fig.3Theseparatinghyperplanebydifferentalgorithms

从图3可以看出，本文算法的分离超平面接近支持向量机的分离超平面，分离的效果最好。

4 结束语

针对支持向量机的分离超平面有各种不同的优化算法，搜索的近优解往往不是实质上的最优解，本文构建的算法是依据正类支持向量和负类支持向量到支持向量机分离超平面的距离相等，避免参数的优化选择，其思想和原理非常简单，当然本文的算法是针对线性可分的支持向量机分离超平面的算法，对于线性不可分的训练数据集，通过核技巧，将输入空间对应于一个特征空间(希尔伯特空间)，使得在输入空间中的超曲面模型对应于特征空间中的超平面模型，分类问题的学习任务通过在特征空间中求解线性支持向量机就可以完成，使得本文构建的新算法具有广阔的应用前景。

参考文献(References)：

[1] 李天宏，张洁，魏江月.基于Bootstrapping支持向量机算法的森林干扰遥感监测[J].应用基础与工程科学学报，2015，23(2)： 308-317

LI T H， ZHANG J， WEI J Y.Monitoring Forest Disturbances with Bootstrapping Support Vector Machine Algorithm[J].Journal of Basic Science and Engineering，2015,23(2)： 308-317

[2] ZHANG Z， GUO H. Research on Fault Diagnosis of Diesel Engine Based on PSO-SVM [C]∥Proceedings of the 6th International Asia Conference on Industrial Engineering and Management Innovation. Atlantis Press， 2016： 509-517

[3] HUANG J，HU X G， YANG F. Support Vector Machine with Genetic Algorithm for Machinery Fault Diagnosis of High Voltage Circuit Breaker [J]. Measurement， 2011 (44) ： 1018-1027

[4] LONG B， TIAN S L， MIAO Q， et al. Research on Features for Diagnostics of Filtered Analog Circuits Based on LS-SVM [J]. IEEE Autotestcon， Baltimore， MD， 2011(9)：360-366

[5] LONG B， TIAN S L， WANG H J. Diagnostics of Filtered Analog Circuits with Tolerance Based on LS-SVM Using Frequency Features[J]. Journal of Electronic Testing， 2012(28)： 291-300

[6] 顾彬，郑关胜，王建东.增量和减量式标准支持向量机的分析[J].软件学报，2013，24(7)：1601-1613

GU B， ZHENG G S， WANG J D. Analysis of Incremental and Decrement Standard Support Vector Machines[J]. Journal of Software， 2013，24 (7)： 1601-1613

[7] 尹传环，牟少敏，田盛丰，等. 局部支持向量机的研究进展[J].计算机科学，2012，39(1)：170-174

YIN C H， MOU S M， TIAN S F，et al. Advances in Research on Local Support Vector Machines[J]. Computer Science， 2012，39(1)： 170-174

[8] 鞠哲，曹隽喆，顾宏.用于不平衡数据分类的模糊支持向量机算法[J].大连理工大学学报，2016，56(5)： 525-531

JU Z， CAO J Z， GU H.Fuzzy Support Vector Machines Algorithm for Imbalanced Data Classification [J]. Journal of Dalian University of Technology，2016，56(5)： 525-531

[9] HUANG Y H.Deep Understanding of Big Data：Big Data Processing and Programming Practice[M].Beijing：China Machine Press，2014

[10] GUO X X. SVM Algorithm Optimization Based on

Distributed Computing[D].Xi’an：Xidian University，2014

[11] ZHAO Q.Efficient Algorithm of Canopy K-means Based on Hadoop Platform[J].Electronic Science and Technology，2014，27(2)：2-3