最小二乘支持向量机的两点改进

王立国，赵亮，石瑶，路婷婷

（哈尔滨工程大学信息与通信工程学院，黑龙江哈尔滨150001）

最小二乘支持向量机的两点改进

王立国，赵亮，石瑶，路婷婷

（哈尔滨工程大学信息与通信工程学院，黑龙江哈尔滨150001）

最小二乘支持向量机以其较好的性能得到了广泛应用，但仍存在2点不足：一方面，最小二乘支持向量机将所有训练样本都作为支持向量参与未知样本的分类，导致该算法在泛化过程中处理速度较慢；另一方面，最小二乘支持向量机主要利用光谱数据进行训练和分类，忽略了对地物空间信息的挖掘，影响了分类精度。为此，提出一种基于库伦引力模型的样本缩减策略，在此基础上将分类结果与基于空间信息的分类器相融合，由此产生的新分类器可以有效解决以上两方面的问题。实验表明了新分类模型在分类精度与速度方面的优势。

高光谱；支持向量机；样本缩减；马尔科夫随机场；空间信息

高光谱遥感技术也已经成为矿产资源探测、环境监测、海洋调查、精细农业、植被研究、军事侦察与识别伪装等领域的有效技术手段。高光谱图像在实现监测、勘探等目标的重要前提是分类技术，其中从统计学习理论中发展起来的支持向量机，以结构风险最小化作为理论基础，避免了过学习造成分类器过于复杂，丧失泛化性的问题，尤其在有限样本的情况下仍然具有良好的分类性能［1⁃4］，因而受到国内外学者的广泛关注，其核函数的引入，也为解决线性不可分问题提供了最佳的解决途径。在文献［5］中，将支持向量机与最大似然分类器，神经网络分类器以及决策树分类器进行了对比，结果表明支持向量机相比其他几种分类器在分类精度上具有明显的优势。

随着支持向量机（support vector machine，SVM））的不断发展，产生了许多SVM的新类型，如球形SVM、单类SVM、最小二乘SVM（least squares SVM，LSSVM）、模糊SVM、粒度SVM、排序SVM、孪生SVM，等。在这些发展类型中，LSSVM因其高效的分类和回归功能而得到广泛的使用。更为主要的：LSSVM的数学模型是一个仅带有等式约束的误差代价函数平方和的优化问题，其求解可在线性系统中进行，学习过程得到大大简化。不足的是：LSS⁃VM将二次规划问题转化为方程组求解问题，但却丧失了支持向量的稀疏性，泛化模型的复杂所导致的应用效率较低影响了该方模型的广泛应用，特别是一些特定领域的应用中对实时性有较高的需求，这将严重影响该方法的实用价值。另一方面，LSS⁃VM主要利用光谱数据进行训练以及分类，忽略了对地物空间相关性的挖掘，造成信息获取不充分的缺陷。针对以上问题，本文在基本保持分类精度的前提下，引用物理学原理对SVM的训练样本进行精简以提高泛化效率，在此基础上，同时利用MRF（Markov random field，MRF）模型将原始分类结果进行与空间相关信息的融合，进一步提高分类精度。

1 库伦力缩减策略

在普通SVM中，只有数量较少的支持向量对最优分类超平面的确定起作用，而在LSSVM［6］中，由公式αi＝γei可以看出，支持值正比于这点的错误值，所有训练样本的α均不为零。为了让LSSVM重新获得稀疏性［8］，基于电子间库仑力（coulomb force）的物理模型思想提出一种筛选支持向量的样本缩减策略（CF⁃LSSVM），使得LSSVM具备一定的稀疏性。

1.1 基本原理

物理学中的电子之间有同号电荷相互排斥，异号电荷相互吸引的性质，作用力的方向在它们的连线上；本文则以两类别中心连线的中垂线作为分类超平面的近似，筛选出更靠近此中垂线的训练样本。

如图1所示，在库伦力模型中，由每个训练样本受到同类样本中心的斥力及异类样本中心的引力之和大小及方向的不同，即可筛选出那些对分类超平面的构建贡献度高的样本，即准支持向量。那些靠近分类超平面的训练样本将会受到同类样本中心的斥力，以及异类样本中心的引力，因而具有一个向分类超平面移动的趋势；而那些距离分类超平面很远的训练样本将会受到两类样本中心的库仑力之和使之远离分类超平面。

图1 库伦力筛选策略示意图Fig.1 Diagram of Coulomb Force screening strategy

由于库伦力是一个矢量，任意两点间的库伦力的方向在两点连线上，因此对于大量的训练样本会获得大量不同方向的库伦力，但是无法直接从这些带有方向的库仑力中比较出哪些训练样本是更靠近分类超平面的准支持向量，而更关心的是训练样本点受到的库伦力在垂直分类超平面方向上的分量。但分类超平面的法向量是未知的，因此利用两类样本的中心点连线近似为分类面的法线方向。求得训练样本所受斥力、引力之后，向两类样本中心点连线方向投影，得到该力的水平分量。在本文中将一个样本点的斥力水平分量与引力水平分量的加权和作为判断其是否能成为准支持向量的贡献值。贡献值越大的，就越具备成为准支持向量的条件，反之同理。根据贡献值确定出准支持向量集，从而训练最终的分类模型。

1.2 库仑力模型

以二分类［9⁃10］问题为例，对于在低维空间中线性不可分的问题，库伦力缩减策略中也相应采用核函数，经过非线性映射后正类和负类样本中心分别为

两类样本的基准特征方向的计算由式（1）和（2）得出：

式中的非线性映射函数的具体公式形式并不知道，因此无法直接获得类别中心以及基准特征方向的值。但由式（1）～（4）可知，利用贡献值可转换为向量内积表达式，故可通过核函数计算出最终结果。正类非线性斥力得分计算公式、负类非线性斥力得分计算公式、正类非线性引力得分计算公式、负类非线性引力得分计算公式依次为式（5）～（8）。

通过分别计算CV＝α·RFS+β·AFS便可以得到训练样本在LSSVM分类器分类过程中对于分类超平面的决策贡献度的排序，在应用过程中根据实际情况需要，可以对分类精度与分类时间进行权衡，选择针对不同情况下的最佳性能分类器。

2 结合空间信息的分类模型

支持向量机在高光谱遥感图像高维数据的分类中表现出良好的性能，然而常规的分类方法都主要关注单个像元光谱信息的挖掘，而没有最大限度结合空间相关信息以此提高分类器的可靠性。MRF是一种将空间相关性整合到图像分类中的概率模型［11］，早已在各个领域中得到广泛关注。大量文献中对MRF在图像分类中如何发挥最佳效果都进行了深入的研究，尤其在文献［12⁃14］中，将支持向量机技术与MRF框架结合，提高遥感图像分类精度。在这些文献中，都用支持向量机分类结果估计类条件概率密度函数，并用MRF根据空间相关性对类别先验概率做出估计，在最大后验概率准则（maximum a posterior，MAP）下进行判决，并获得良好的实验效果。本文将所提出的缩减分类器CF⁃LSSVM⁃MRF与基于MRF空谱分类模型结合，在提高分类速度的同时使分类精度得到显著提高。实验证明本文方法与未结合空间信息的模型相比，前者效果更理想。

MRF在图像分割［15］过程中，可以通过K均值距离分类法得到图像的一种分类结果，并由此结果得到条件概率与标号场所得X的联合概率分布的乘积，以最大后验概率准则作为判决标准，将最终概率乘积最大的类别作为未知样本的标号。借助MRF的原理，将样本缩减后的LSSVM一对一多类分类器所得的概率形式分类结果与MRF的标号场模型相结合，建立光谱信息与空间信息相结合的分类器模型，在缩短分类时间的基础上大大提高分类精度。

由MRF的性质可知，中心像元的类别标号只与其邻域系统中的像元类别标号有关，因此可以通过中心像元的邻域系统内各个像元的类别标号求出中心像元所属类别的先验概率P x()。由地物分布的相关特性，可以在原有分类器分类结果的基础上，通过对空间相关性进行计算，计算结果作为决定标号的重要参考。在大量文献中都对结合空间相关性的方法的分类效果进行论证，均对分类精度有改进的效果。本文根据MRF原理，利用MRF对标号场先验概率的估计模型，提出一种空谱结合的分类器模型。该模型主要分为两部分，首先通过CF⁃LSSVM⁃MRF对未知数据进行分类，通过1⁃a⁃1型多分类结构通过投票得到各个分类结果对应的概率。假设共有N类待分类地物，则应该建立N（N-1）／2个一对一分类器，得到后验概率的形式为

式中：Pij（i｜X）的取值为0或者1。

式中：C为类别标号，i为X邻域系统中的某像元，本文采用8-邻域系统，因此i＝1，2，…，8。由式（10）可以求得X的类别标号取遍所有类别的每个引力势能的值。在8-邻域系统中的8个像元，由于相对位置的关系不同，可以分为2类。分别是与中心像元直接相邻的4个像元，另一类是与中心像元对角相邻的4个像元。由于这2类像元相对中心像元空间位置关系的不同，对于中心像元标号的影响也是不同的，因此模型中引入各个像元与中心像元的欧式距离作为影响因子：

由支持向量机软分类结果得到fc（xi），与引力势能进行线性加权可以得到空间相关性的分类模型：

3 实验仿真

本文涉及的仿真实验的硬件运行环境是CPU为Intel Core 2，2.00GHz，内存2GB的PC机；软件环境是：Window 7操作系统，仿真平台为Matlab 2010a。实验中，原始的LSSVM，利用库仑力精简训练样本的CF⁃LSSVM，利用承载空谱间信息的MRF的LSSVM⁃MRF，以及同时利用库仑力和MRF的CF⁃LSSVM⁃MRF 4种方法来进行比较来验证所提出方法的有效性。

第1组实验采用Pavia大学高光谱数据中的2类进行二分类仿真。2类地物分别选取Asphalt、Bricks，由地物监督图可以看出，这2种地物分布覆盖范围比较广，且较为分散，并不是同类地物集中分布，各类别地物的细节信息较丰富，因此选择这2种地物进行分类实验，验证本文方法在这种特征的高光谱图像分类中的表现。各种分类模型所取得的分类精度如表1所示。CF⁃LSSVM分类模型的分类精度与LSSVM相差不大，而分类时间则由32.15 s降至1.61 s；CF⁃LSSVM⁃MRF分类模型较之LSSVM分类精度有较大提高，在分类时间上则与CF⁃LSSVM基本持平。可见，空谱结合模型CF⁃LSSVM⁃MRF较之基本的LSSVM模型不但提高了分类精度，也大量节省了推广阶段的分类时间。

表1 Pavia University二分类模型性能对比Table 1 Performance comparison of two⁃classification model for Pavia University data set

第2组实验采用印第安农林数据验证算法性能，在仿真实验中LSSVM采用性能较好的高斯径向基核函数进行非线性分类，其中核函数中σ取值0.9，γ为1 000。本章中均采用1⁃a⁃1型多分类结构。实验主要通过高光谱数据分类对比了原始LSSVM分类法，本文提出的CF⁃LSSVM⁃MRF分类法以及本章提出的空谱结合分类器在各类别分类精度，整体分类精度以及Kappa系数的对比，图2为经各方法分类后的地物分布效果图。

图2 4种分类方法效果图Fig.2 Classification results of four methods

由图2可以直观的看出，在融合空间信息后的分类器的分类效果得到明显提高，这种新型的分类模型有效避免类别内部像素点的错分情况，使分类结果具有更强的完整性，尤其适用于区域面积较大的地物目标。由表2的具体各类别分类精度可以看出，结合空间信息的分类模型具有更高的分类准确度；同时，分类时间统计表明，样本缩减模型较之未缩减模型所耗时间明显减少。

表2 India Pine 4种分类模型性能对比Table 2 Performance comparison of four kinds of classification models for India Pine data set

4 结束语

本文提出一种基于库仑力的LSSVM样本缩减策略，该方法将物理学中带电粒子间引力的模型引入到对于训练样本空间位置关系的计算当中，并通过设置标准特征方向，由矢量投影方式对计算进行简化，实验证明本方法可以在精度要求范围内提升判别新样本的速度，提高了LSSVM的推广能力。在样本缩减分类器模型的基础上，提出一种融合了光谱信息以及空间相关性的新型分类器，该分类器把样本缩减了的LSSVM与MRF理论相结合，显著提高了分类器分类精度。从理论分析和实验评价方面均显示出本文提出方法的可行性和有效性。

［1］BRUZZONE L，MARCONCINI M.Toward the automatic up⁃dating of land⁃cover maps by a domain⁃adaptation SVM clas⁃sifier and a circular validation strategy［J］.IEEE Trans Geosci Remote Sens，2009，47（4）：1108⁃1122.

［2］DEMIR B，ERTURK S.Clustering⁃based extraction of bor⁃der training patterns for accurate SVM classification of hy⁃perspectral images［J］.IEEE Geosci Remote Sens Lett，2009，6（4）：840⁃844.

［3］王立国，王群明，刘丹凤，等.基于几何估计的光谱解混方法［J］.红外与毫米波学报，2013，32（1）：56⁃61.WANG Liguo，WANG Qunming，LIU Danfeng，et al.Geo⁃metric estimation method of spectral unmixing［J］.Journal of Infrared and Millimeter Waves，2013，32（1）：56⁃61

［4］MATHUR A，FOOFY G M.Crop classification by a SVM with intelligently selected training data for an operational ap⁃plication［J］.International Journal of Remote Sensing，2008，29（8）：2227⁃2240.

［5］HUANG C，DAVIS L S，TOWNSHEND J R G.An assess⁃ment of support vector machines for land cover classification［J］.Int J Remote Sens，2002，23（4）：725⁃749.

［6］SUYKENS J A K，BRABANTER J D，LUKAS L，et al.Weighted least squares support vector machines［J］.Neuro⁃computing，2002，48（1／4）：85⁃105.

［7］SUYKENS J A K，LUKAS L，VANDEWALLE J.Sparse ap⁃proximation using least squares support vector machines［J］.IEEE International Symposium on Circuits and Systems，2000，2：757⁃760.

［8］吴宗亮，窦衡.一种新的最小二乘支持向量机稀疏化算法［J］.计算机应用，2009，29（6）：1559⁃1562.WU Zongliang，DOU Heng.New sparse least squares sup⁃port vector machine algorithm［J］.Journal of Computer Ap⁃plications，2009，29（6）：1559⁃1562.

［9］HSU C W，LIN C J.A comparison of methods for multi⁃class support vector machines［J］.IEEE Trans Neural Netw，2002，13（2）：415⁃425.

［10］PLATT J C，CRISTIANINI N，SHAWE-TAYLOR J.Large margin DAGs for multiclass classification［J］.Proc Adv Neural Inf Process Syst，2000，12（6）：547⁃553.

［11］VERHOEYE J，de WULF R R.Land⁃cover mapping at sub⁃pixel scales using linear optimization techniques［J］.Remote Sensing of Environment，2002，79（1）：96⁃104.

［12］FARAG A A，MOHAMED R M，EL-BAZ A.A unified framework for map estimation in remote sensing image seg⁃mentation［J］.IEEE Trans Geosci Remote Sensing，2005，43（7）：1617⁃1634.

［13］BOVOLO F，BRUZZONE L.A context⁃sensitive technique based on support vector machines for image classification［M］.Berlin：Pattern Recognition and Machine Intelli⁃gence，2005：260⁃265.

［14］GONG Peng，KELLY M，LIU Desheng.A spatial⁃temporal approach to monitoring forest disease spread using multi⁃temporal high spatial resolution imagery［J］.Remote Se⁃ning of Environment，2006，101（2）：167⁃180.

［15］郑玮.基于模糊马尔科夫随机场的遥感图像分割算法研究［D］.成都：电子科技大学，2007：28⁃35.ZHENG Wei.Research on remote sensing image segmenta⁃tion algorithms based on fuzzy Markov random field［D］.Chengdu：University of Electronic Science and Technology of China，2007：28⁃35.

Two improvements for least squares support vector machines

WANG Liguo，ZHAO Liang，SHI Yao，LU Tingting

（College of Information and Communication Engineering，Harbin Engineering University，Harbin 150001，China）

The least squares support vector machine（LSSVM）has been widely used due to its better performance.However，LSSVM still has two deficiencies.On the one hand，it sacrifices the speed in the generalization process because it treats all the training samples as the support vector set to participate in classification of unknown samples.On the other hand，LSSVM mainly uses spectral data for training and classification，and it ignores mining on the spatial information of a terrestrial object，which influences classification precision.Therefore，a sample reduction strategy based on the Coulomb gravity model is proposed.And on this basis，a new classifier model which merges the above classification result with the classifier based on spatial information can solve the two problems mentioned above.Experimental results indicate that this new classifier performs better than the standard LSSVM both in classi⁃fication accuracy and speed.

hyperspectral；support vector machine（SVM）；sample reduction；Markov random field（MRF）；spa⁃tial information

10.3969／j.issn.1006⁃7043.201404078

TP753

：A

：1006⁃7043（2015）06⁃0847⁃05

http：／／www.cnki.net／kcms／detail／23.1390.u.20150428.1118.022.html

2014⁃04⁃25.网络出版时间：2015⁃04⁃28.

国家自然科学基金资助项目（61275010）；国家教育部博士点基金资助项目（20132304110007）；黑龙江省自然科学基金资助项目（F201409）；中央高校基本科研业务费重大资助项目（HEUCFD1410）.

王立国（1974⁃），男，教授，博士生导师.

王立国，E⁃mail：wangliguo＠hrbeu.edu.cn.