局部几何保持的Laplacian代价敏感支持向量机

周国华,宋 洁,殷新春

(1. 常州轻工职业技术学院 信息工程系,江苏 常州 213164；2. 扬州大学 信息工程学院,江苏 扬州 225127)

0 引言

在现实世界中，人们采集的真实数据往往是不平衡的，比如癌症疾病诊断实例中，健康人的样本数目往往要远多于患病者的样本数目；诈骗短信分类中，正常短信的数目也远多于诈骗短信的数目。解决此类问题一般主要有三种方法： 一种方法是重采样来调整不同类别样本的比例，如在支持向量机技术中常用的过采样(over-sampling)和欠采样(under-sampling)方法[1-3]，但是这类方法的缺点是会改变样本的原始分布结构, 采取精确复制少数类样本的策略容易造成分类器的过拟合，而采取抽样多类样本的策略容易丢失部分样本信息。第二种方法是调整分类面的偏移[4]，让分类面尽可能地远离少数类，但是这种方法也易产生过拟合的问题。第三种方法是针对数据的不平衡性选取不同的代价参数[5]。这是因为样本的不平衡分类问题一般常涉及到代价敏感学习问题[6-8]，即错分代价。错分代价包括类依赖的代价和样本依赖的代价，其中类代价可以表示为错误分类两类样本的代价不同，样本的不平衡分类常可表示为类别的代价敏感问题。如Lo等[9]在2011年通过考虑噪声标注问题提出了用于自动音乐标注的代价敏感分类算法；万建武等[10]将错分代价融入局部保持降维的目标函数中, 提出了一种错分代价最小化的局部保持降维方法，并采用了加权策略, 将算法应用到不平衡人脸数据集上；Liu等[11]基于满足基本运算的不变性和各行间元素的大小差异性，并借鉴领域专家的先验知识，提出了容易定义成对代价的概念，运用于不平衡数据的分类。

但是代价敏感学习方法通常为有监督学习方法，其必须获取足够的训练数据。在实际应用中，由于标记样本的标签这一工作费时费力，人们更容易得到大量的无标记数据。因此在面对大量未知标签信息的不平衡数据分类问题中，文献[12]在代价敏感学习框架的基础上使用半监督学习来处理不平衡数据分类问题，将未标记样本纳入到分类器的求解过程中。文献[13]将半监督学习和代价敏感结合应用在microRNA的分类问题中。但是这两种方法均没有考虑数据的局部几何分布信息对分类性能的影响，其分类精度还有待提高。

鉴于上述分析，本文提出了一种新的局部几何保持的Laplacian代价敏感支持向量机(locality preserving cost sensitive laplacian support vector machine, LPCS-LapSVM)。该分类器为一种半监督分类方法，将针对不平衡数据的不同代价和样本的局部几何流形信息同时融入Laplacian支持向量机的架构中，从而更大程度地提高半监督学习中不平衡问题下分类器的分类精度。

1 相关工作

1.1 代价敏感支持向量机

(1)

其中ci为第i个样本的误分代价参数，其值可按照上段的描述设置。ciεi为第i个样本错分造成的损失，参数C则用于控制损失与模型复杂度的关系。CS-SVM是一种有监督学习模型，由于可以对不同类别的样本设置不同的代价参数，对比传统的支持向量机(support vector machine, SVM)，更能获得尽可能小的总体代价，从而可以在不平衡的数据分类问题中得到更加精确的分类效果。但CS-SVM的不足是无法利用无标记信息来训练模型，无法应用到半监督学习中。

1.2 Laplacian支持向量机

(2)

(3)

(4)

ξi>0,i=1,2,…,l

LapSVM的解的形式为式(5)。

f(x)=∑l+ui=1αiK(x,xi)

(5)

LapSVM作为一种成功的半监督学习方法，依然存在不足之处，其主要表现在： ①LapSVM认为如果两个数据的内在几何空间距离较近，则判定它们属于同一类，但在两类样本的边缘地带这种假设往往并不成立； ②LapSVM利用了数据的整体流形信息而忽略了已知样本的类别标签信息，其结果导致忽略了不同类别内部样本的局部分布信息。

2 局部几何保持的Laplacian代价敏感支持向量机

为了能更精确地处理半监督场景下不平衡数据的分类问题，本文在LapSVM模型的基础上提出了一种新的局部几何保持的Laplacian代价敏感支持向量机LPCS-LapSVM。LPCS-LapSVM首先使用测地线距离构造一个新的局部几何保持连接图，提出类内局部保持散度矩阵，然后将基类内局部保持散度信息融入基于LapSVM的代价敏感学习框架中，得到一种新的Laplacian代价敏感支持向量机。因为LPCS-LapSVM中融入了类内局部保持散度信息，在解决半监督场景下不平衡分类问题时，能挖掘样本的局部几何结构特征和整体流形信息，从而提高半监督分类器的分类性能。LPCS-LapSVM算法构造原理如图1所示。

图1 局部几何保持的Laplacian代价 敏感支持向量机构造原理

2.1 类内局部保持散度矩阵

现有算法在构造连接图时，多采用欧氏距离，而本文方法为了利用数据在高维核空间下的局部内在几何信息，使用测地线距离[17]构造局部几何保持连接图Gw。这是因为高维数据在核空间往往呈现折叠、螺旋或曲面等分布，导致欧氏距离无法正确计算样本间的距离度量，而测地线距离能更好地根据样本的几何分布反映高维数据的流形信息。

定义1(局部几何保持连接图Gw)：Gw=(V,E),其中结点集V={x1,…,xl,xl+1,…,xl+u}，边集E可表示为一个邻接矩阵，基于高斯函数定义该邻接矩阵的元素如式(6)所示。

(6)

其中exp(-d2(xi,xj)/t)为热核函数，t为一个常数，KNN()表示K近邻函数。距离度量函数d(xi,xj)的值由式(7)、式(8)计算得到：

值得注意的是，与常规LapSVM中使用的邻接矩阵不同，dx(xi,xj)为图Gw中边长，dg(xi,xj)为同类别内结点xi和xj之间的测地线距离。初始化Gw时，如果xi和xj类别标签相同且相邻，则d(xi,xj)=dx(xi,xj)，否则d(xi,xj)设置为无穷大。

(9)

其中Dw为对角阵，Dw表示为Dw=∑l+uj=1Ww,ij，Lw=Dw-Ww为Gw的类内拉普拉斯矩阵。

2.2 LPCS-LapSVM

(10)

(11)

根据KKT条件，可得式(11)的对偶式为式(12)。

(12)

其中α是拉格朗日系数向量，Q=YJK(I+γILK+γGLwK)-1JTY，Y=diag(y1,y2,…,yl)，J=[I,0]l×(l+u)，I是l×l的单位阵。本文采用二次规划问题求解方法可得式(12)的最优解α*，如式(13)、式(14)所示。

由此可得非线性LPCS-LapSVM的目标决策函数如式(15)所示。

(15)

通过上面的分析，得到LPCS-LapSVM算法的执行步骤，如算法1所示。

算法1：LPCS-LapSVM算法

输入: l个已标记样本{(xi,yi)}li=1,u个未标记样本{(xj)}l+uj=l+1;输出: 目标决策函数f*(x). //构建未标记数据的类内局部保持散度矩阵步骤1: 根据文献[17]计算同类别内结点xi和xj之间的测地线距离dg(xi,xj);步骤2: 根据式(7)和式(8)计算xi和xj之间距离度量函数d(xi,xj);步骤3: 根据式(6)计算基于测地线距离的局部几何保持连接图矩阵Ww,ij;步骤4: 根据式(9)计算类内局部保持散度矩阵S^w;//使用全部训练数据完成分类器的训练步骤5: 对式(12)求解拉格朗日系数α*;

续表

LPCS-LapSVM算法在半监督学习框架的基础上，继承了半监督学习流形学习的特点，同时从考虑内在可分辨信息和样本的局部几何分布两方面来提高代价敏感支持向量机在标记信息有限的场景中的分类性能。LPCS-LapSVM算法的时间复杂度采用了LapSVM框架，而LapSVM的时空复杂度与传统的SVM相似，所以LPCS-LapSVM时间复杂度和空间复杂度分别是最差情况下为O((l+u)3)和O((l+u)2)，为了在一定程度上提高本文方法的执行效率, 可以采用SMO(sequential minimal optimization)等快速二次规划优化算法求解。

3 实验

3.1 实验设置

为了评价本文所提LPCS-LapSVM算法的有效性，本文选取了代价敏感支持向量机(CS-SVM)[14]、Laplacian支持向量机(LapSVM)[15]、代价敏感Laplacian支持向量机(CS-LapSVM)[13]、代价敏感半监督支持向量机(CS4VM)[18]半监督和加权支持向量机(SSWSVM)[21]共5种对比算法进行比较实验。实验选择12个UCI数据集[19]进行对比实验，详细的数据集描述见表1。所有样本的特征值都被规范化到[0,1]区间上。按照通用不平衡数据的实验设置，少数类样本设置为正类，多数类样本设置为负类，同时参照文献[18]的设置，负类样本的误分类代价为1，正类样本的误分类代价为{2, 5,10}。各SVM算法的正则化参数C取值为{10-3,10-2,…，103}，LPCS-LapSVM的正类样本的正则化参数是负类样本的10倍。核函数均采用高斯核, 核参数σ取值为{10-3,10-2,…,103}。LPCS-LapSVM中的k-近邻参数k取值范围为{1,3,5,7，9}，参数γI和γG的取值范围为{10-3,10-2,…,103}。对比算法的其他参数设置采取文献的默认设置。本文采用测试集上的整体错分损失[20]来评价算法的分类性能。本文实验依照表1中正负类标记样本的数目随机选取相应的样本，执行10次并记录了运行10次的整体错分损失的平均值和标准差。本文的实验在2.53GHz quad-core CPU, 8GB RAM, Windows 7 系统下执行, 所有算法均在 Matlab 2016b环境下实现。

表1 UCI数据集描述

3.2 实验结果

本文所提LPCS-LapSVM算法与5种对比算法的整体错分损失进行了比较，实验结果如表2～4所示，表2～4分别选取正类样本的误分类代价为2、5和10。本节中我们使用T检验[22]来判断所提算法与5种对比算法之间是否统计学显著性差异，并设置显著性水平α=0.05，受篇幅的限制，在检测的操作中，我们使用表中加注(*)的方式表示算法间存在显著性差异，即若LPCS-LapSVM取得的整体错分损失较小，且与对比算法的显著性水平<0.05，则在对比算法的性能旁加标注(*)；若LPCS-LapSVM取得的整体错分损失较大，或整体错分损失较小但与对比算法的显著性水平>0.05，则在对比算法的性能旁不加标注。另外，实验还对正类样本的误分类代价为5时LPCS-LapSVM算法与5种对比算法的训练时间进行了比较。根据表2～5的实验结果可以得到以下结论。

(1) 4种半监督代价敏感支持向量机(CS-LapSVM、CS4VM、LPCS-LapSVM和SSWSVM)在训练集标记信息不足的场景下处理不平衡数据的分类问题都有较好的学习能力。在正类样本的误分类代价为2、5和10时取得的实验结果在整体错分损失这一指标上具有相似性。但是本文所提的LPCS-LapSVM在整体错分损失上具有相当的优势，除了在两个数据集上分别略逊于CS4VM和CS-LapSVM算法，两个数据集上略逊于SSWSVM。这是因为： 第一，LPCS-LapSVM在LapSVM模型的框架基础上，考虑了不同类别数据的错分代价，能提高不平衡数据的分类精度，同时还融入了类内局部保持散度矩阵，保持同类别样本的鉴别信息，还可以体现不同样本之间的差异信息，即全局考虑了样本的内在结构信息，这充分说明了类内局部保持散度矩阵有助于提高分类器的性能。第二，在计算类内局部保持散度矩阵时，使用测地线距离代替欧氏距离来计算两个样本点之间距离的方法是合适的。LPCS-LapSVM是基于SVM框架的，SVM在处理线性不可分的数据分类问题上，通常使用核技术将原始样本通过各类核函数投影在核空间，在这种情况下，使用测地线距离更能表达样本间的距离关系。

(2) CS-SVM和LapSVM算法的整体错分损失明显高于另外3种对比算法和LPCS-LapSVM算法。这是因为CS-SVM基于标记样本充足的场景考虑不同类别数据的错分代价，在标记数据不足的场景下其整体错分损失上升迅速。LapSVM算法是一种优秀的半监督分类算法，但不适应于不平衡数据的分类问题，特别是两类样本不平衡比例较大时，LapSVM算法在正类上的分类精度较低，因而得到的整体错分损失在所有算法中是较低的。

(3) 表2～表4中参照显著性检验T检验的结果可知，所提LPCS-LapSVM在12个UCI数据集的大部分数据集上，与5种对比算法相比，均具有显著性差异。说明LPCS-LapSVM在代价敏感的不平衡分类问题上具有显著优势，与5种对比算法相比是具有竞争力的。进一步说明，LPCS-LapSVM非常适用于代价敏感不平衡分类场景的应用。

(4) 表5显示了LPCS-LapSVM算法与5种对比算法的训练时间，实验中比较的6种算法都是基于SVM的分类算法，训练问题都可以转换成QP(qualification programme)问题，时间复杂度为训练样本的3次方。CS-SVM的训练时间最短，LPCS-LapSVM与另4种半监督SVM算法的训练时间相当。其原因在于CS-SVM不是半监督SVM分类算法，而半监督SVM在训练过程中需构建保持数据分布的几何邻接图，因此CS-SVM相对时间复杂度较低，训练时间较短。如何提高所提LPCS-LapSVM的计算效率是下阶段的工作之一。

表2 各算法的整体错分损失比较(正类样本的误分类代价为2)

表3 各算法的整体错分损失比较(正类样本的误分类代价为5)

续表

表4 各算法的整体错分损失比较(正类样本的误分类代价为10)

表5 各算法的训练时间比较(正类样本的误分类代价为5，单位为s)

3.3 参数敏感性实验

LPCS-LapSVM中需要设定的参数有6个： 正类样本的误分类代价参数c，k-近邻参数，正则化参数C，高斯核核参σ，参数γI和γG。其中正则化参数C和高斯核核参σ是SVM模型中皆有的两个参数，其最优值通常情况下都在给定的范围内寻优获得，由于篇幅的限制，本节没有给出这两个参数的敏感性分析结果。误分类代价参数c对本文方法LPCS-LapSVM算法性能的影响如表2～4所示。表6显示了k-近邻参数k对本文方法LPCS-LapSVM在12个UCI数据集上的整体错分损失的影响，实验中固定误分类代价参数c=5，正则化参数C和高斯核核参σ分别是1和0.1，参数γI和γG均为1。另外，图2显示了参数γI在4个UCI数据集上的敏感性实验结果，实验中固定误分类代价参数c=5，正则化参数C和高斯核核参σ分别是1和0.1，k-近邻参数k=5，参数γG为1。图3显示γG在4个UCI数据集上的敏感性实验结果，实验中固定误分类代价参数c=5，正则化参数C和高斯核核参σ分别是1和0.1，k-近邻参数k=5，参数γI为1。分析表6和图2、图3可得到以下的结论。

表6 LPCS-LapSVM在k-近邻参数不同k值时的整体错分损失

图2 LPCS-LapSVM在不同参数γI下的G-mean值

图3 LPCS-LapSVM在不同参数γG下的G-mean值

(1) 从表6结果可知，LPCS-LapSVM的分类性能受k取值的变化很大，但是我们也注意到，LPCS-LapSVM在12个UCI数据集上的整体错分损失的最小值一般在k<7时获得，当k值大于7时，整体错分损失有所上升。因为在计算类内局部保持散度矩阵时使用的测地线距离是计算核空间中近邻点最短距离的累加，当k取大值时，无法准确地表达这一空间距离信息。

(2) 参数γI的作用是调节流形正则项，通过在范围{10-3，10-2，…，103}内寻优获得最佳值。从图2可知，各数据集上的整体错分损失对γI值很敏感，且不同数据集获得最佳分类效果时取得的γI值差异很大，因此参数γI适合在给定的数值范围内寻优得到。

(3) 参数γG的作用是调节类内局部保持散度项，类内局部保持散度矩阵的计算结果与数据集在核空间分布有直接关系。从图3结果可知，4个UCI数据集上的整体错分损失也对参数γG敏感，因此参数γG也适合在给定的数值范围内寻优得到。

4 结论

本文提出了局部几何保持的Laplacian代价敏感支持向量机LPCS-LapSVM，该算法在LapSVM框架的基础上融入了代价敏感学习的思想，还构造了一种新的类内局部保持散度矩阵，其使用测地线距离来计算核空间下结点间的距离，类内局部保持散度矩阵不仅能够表示样本的类别分布信息，还可以表示样本的局部几何结构特征，特别是保证两类样本的边缘地带的几何特征。通过12个UCI数据集上的对比实验，验证了LPCS-LapSVM算法的有效性。