一种改进的支持向量机及其在图像分割中的应用

刘 琦，赵彦晖

（西安建筑科技大学，陕西西安 710055）

一种改进的支持向量机及其在图像分割中的应用

刘 琦，赵彦晖

（西安建筑科技大学，陕西西安 710055）

支持向量机方法在解决小样本，非线性及高维模式识别中表现出许多特有的优势。目前主要用于二元分类问题中，而对于其在多类分类应用仍是一个值得研究的问题。在目前存在的各种多类支持向量机分类问题中，一对一方法是一种最符合实际的方法。文章提出了一种改进的支持向量机，并将其应用于图像分割。这种改进的支持向量机它对一对一方法进行了改进，实验表明，支持向量机的方法是一种很有潜力的图像分割技术。

支持向量机;距离;决策函数;一对一;分类器

1 前言

支持向量机是一种基于统计学理论的机器学习的新方法，它的理论基础是统计学理论的VC理论和结构风险的最小化准则，其是由 Corinne Cortes和Vapnik［1］等于1995年首先提出来的，它在解决小样本，非线性及高维模式识别中表现出许多特有的优势，并能够推广应用到函数拟合等其他机器学习问题中，相比较于传统的方法，支持向量机具有以下优点: （1）专门针对于有限样本的情况，（2）使用了核函数，将原问题通过隐形非线性变换转换到高维的特征空间，在高维空间中构造线性决策函数来实现原空间中的非线性决策函数，（3）SVM的解也具有稀疏性。

近年来，国内外对于SVM的研究发展迅速，以Suykell为代表的研究团队提出了用于分类的最小二乘支持向量机;用于支持向量机泛化能力的理论分析的概念——支持向量数据域描述（Support vector data，Discriptill，SVDD）思想，提出了只针对于某个单类问题进行学习的单分类支持向量机，这种方法使得训练样本大大的减少了，使得学习时间也随之减少，但它使得整体的泛化能力下降。

本文旨在构造一种改进的支持向量机，并将其应用到图像分割中，因而本文所研究的主要内容可分为两个板块:其一为对现有的支持向量机进行改进，提出一种改进的向量机;其二，利用改进的支持向量机进行图像分割。

2 改进的支持向量机

支持向量机在解决二元分类问题上具有很好的泛化能力，但是它在多类分类问题上的应用依然是一个值得研究的问题。很多应用支持向量机解决多类分类问题的方法被提出，例如:一对一方法，一对多方法，以及有向无环图方法。解决多类分类问题关键是要求分类的数目要与变量的数目相适应，因而在相同数据的计算上，较二元问题，它在时间上的花费要多得多。对于类的分类问题，一对多的方法构造了个分类器（这个分类器的构造是利用训练集的数据）。一对一方法构造了k（k－1）/2分类器（这些分类器的构造是通过使用从个分类中选出的两类的训练数据来构造的），虽然它需要构建的分类器数量较多，但他的训练时间大大低于其它的方法。有向无环图也利用了k（k－1）/2分类器。然而，它在训练时间上远不及一对一方法的。Hsn和Lin通过比较上述方法的的表现方式以及计算耗时，对上述方法进行了比较，他们认为在训练时间上没有任何方法能比得上一对一的方法，也没有任何方法比一对一的方法更具有泛化能力。因而，一对一方法相比较于其他方法更符合实际问题。近年来，Lee和Lin提出了一种多目标分类的支持向量机，该种支持向量机被认为是二元问题向多类问题应用的一个很好的推广。正如在二元问题中一样，他们在多类问题中应用了贝叶斯定理，但是它面临着使得数据的计算问题变得更为复杂。

一对一方法在类训练样本中构造所有可能的两类分类器，分类决策采用了投票策略（即“最大得分理论”），它每个分类器仅仅在类中的两类训练样本上训练，结果构造k（k－1）/2个分类器，虽然它需要构建的分类器数量较多，但在实际应用中使用最好，但该种方法最大的缺点就是它也存在不可分域，为此，Abel等人，对一对一方法进行了改进，提出了多类分类的模糊支持向量机，对于位于不可分域中的向量采用了最小算子其隶属度决定其类别。

图1 一对一不可分区域的解决策略

众所周知，在分类问题中，距离是一种最简单，最直观的分类测度，基于这样的考虑，提出了一种改进的一对一的方法，实现过程如下:

针对多类分割问题，当向量位于不可分割区域时，计算其到所有两类超平面的距离:

所对应的分类超平面为

决策函数为

为了验证改进方法的有效性，该方法在UCI标准数据库［8］的iris以及vehicle以及wine数据上进行了实验，并将是分类性能与一对一方法以及Abe等人改进的方法进行了比较，试验中，将样本一分为二，一半用于训练，一半用于测试，核函数采用了二阶的多项式核函数

此时的支持向量机是一个含有阶多项式的分类器。

表1为几种方法的分类性能比较结果，从表1中可以知道，本文改进的方法可以获得与Abe等人改进方法相比较，此法比较简单实用。同时本文的方法还是不可分区域进行了划分，如图2。

图2 一对一方法对不可分区域的划分

表1 几种一对一方法分类性能的比较

3 图像分割实验

为了评价SVM方法对于图像分割的性能，本文以2010年研究生建模竞赛A题的中瘤基因癌变图为例，进行了分割实验。该图像具有边界模糊，目标灰度不明确以及不连续的特点，选择它主要是为了增加分割的全面性和客观性。

实验过程步骤如下:

（1）对所有数据进行提取，然后对其进行归一化处理形成SVM的输入向量。

（2）将实验数据一分为二，一部分作为训练数集，一部分作为测试数集。

（3）将训练数据分到所有的二元子集中，利用前面所给出的距离计算所有的分类间的距离。

（4）构造第i个分类的界，实现过程如下:让j作为第i个分类的有序元素，如果j是第i个分类的第一个元素，且对于第i个分类来讲，没有一个分类器被它所构造，则应用SVM去分类与j。如果j不是第个i分类的第一个元素，且对于第i个分类来讲，没有一个分类器被i与j所构造，且分类i与其它分类所构造分类器不能把i与j区分出来，则应用SVM去分类i与j。检查第个分类所有的以及在需要的情况下应用SVM去分类i与j。

（5）对于所有的分类应用上述的第3步的方法，进而得到分类方式。

（6）将所得结果应用在测试数集上。

实验中，选择核函数为k（x，xi）=［（x*xi）+ 1］d，其中d=3。

如图3，图像被成功的分割。因而对于一些目标边界模糊，目标灰度不明确的图形分割，SVM是一种很好的选择。

图3 实验前后的图像对比

4 结语

本文提出了一种改进的支持向量机，这种支持向量机是建立在对于多类分类支持向量机方法的研究上的。通过大量的实验将其和一对一方法，还有Abel等人提出的方法进行了比较。同时还其应用于图像分割中。实验的结果表明，本文提出的改进的支持向量机具有很好的实际效用，同时对于图像分割的处理SVM是一种很好的方法，它有着较好的前景。

［1］ V.N.Vapnik.统计学习理论的本质［M］.张学工，译.北京:清华大学出版社，2000.

［2］ Welcome to the UC Irvine Machine Learning Repository!［EB/OL］.www.ics.uci.edu/～mlearn/MLRepostitory.html.

［3］ 岳振军，邱望成，刘春林.一种自适应的多目标图像分割方法［J］.中国图像图形学报，2004，9（6）:674－678.

［4］ C.W.Hsu，C.J.Lin.A comparison of methods for multiclass support vector machines［J］.IEEE Transactions on Neural Network，2002，13（2）:415－425.

［5］ J.Weston，C.Watkins.Multi-class support vector machines［R］.CSD-TR-98-04，1998:1－9.

［6］ J.C.Platt，N.Cristianini，T.J.Shawe.Largemargin DAGs for Multiclass classification［J］.In advances in Neural Information Processing Systems，MIT Press，2000（12）: 547－553.

［7］ Hsu C-W，Lin C-J.A comparison of methods for Multiclass support vector machines.IEEE Trans Networks［J］.2002（13）:415－425.

An Im proved Support Vector Machine and Its Application in Image Segmentation

LIU Qi，ZHAO Yan－hui
（Xi’anUniversityofArchitectureandTechnology，Xi’an710055，China）

Support vector machine is a statistical theory based on the new machine learning method;it addresses the Small Sample，Nonlinear and High Dimensional Pattern Recognition performance of the many unique advantages.At present it is mainly used for binary classification problems，and for its application in multi-class classification is still a problem worthy of study.In a variety of existing multi-class support vector machine classification problem，one-against-one is one of the most realistic approaches.This paper presents an improved support vector machines and applied it to image segmentation.This improved method of support vector machines is one of the improvements of one-against－one，experiments show that support vector machine approach is a promising image segmentation technique.

support vector machine;distance;decision function;one-against-one;classifier

G43

A

1671－1491（2012）02－0015－03

2012－01－04

刘 琦（1986－），男，陕西西安人，西安建筑科技大学在读硕士研究生，从事概率统计应用研究。

（责编:王玉琴）