消除随机一致性的支持向量机分类方法

王婕婷 钱宇华 李飞江 刘郭庆

(山西大学大数据科学与产业研究院 太原 030006)(计算智能与中文信息处理教育部重点实验室(山西大学) 太原 030006)(山西大学计算机与信息技术学院 太原 030006)(jietingwang@email.sxu.edu.cn)

在决策过程中,当人类缺乏足够的证据或详细的知识时,可能会进行逻辑欠缺的随机猜测[1-6].例如学生在面对困难的多项选择题时喜欢选择自己幸运的选项.有时,这些随机猜测可能与实际情况形成一致性,我们称这种一致性为随机一致性.随机一致性的存在会误导逻辑形成方向,导致决策结果无意义、信息含量少、扩展能力差.在随机猜测与真实情况的分布相同时,这些缺点尤为明显.

基于智能算法的机器学习系统本质上是一种由数学表达与逻辑运算构成的决策函数,被认为具有较强的客观性与确定性,不像人类容易受外部因素的影响,出现主观臆断的现象.然而,1)智能学习算法是数据驱动的.机器学习算法面对的历史数据通常具有数量有限、类别分布不平衡、含噪音等特质[7-9],这使得学习机所面对的学习证据缺乏完备性、充分性与准确性.那么,基于历史数据所得的决策知识与数据蕴涵的潜在模式可能会出现偏差;2)智能学习算法是目标导向的[10-11].智能算法的设计目的、数据运用、结果表征等都是开发者、设计者的主观价值选择,算法设计者在把算法逻辑输入机器的同时,也将具有随机性的判断方式带到了学习机中.基于上述分析,智能算法也会呈现随机一致性,并且在自我提升的反馈循环中又可能会把随机一致性带来的后果进一步放大或者固化,严重影响到自身泛化性能的提升.

目前,大多数机器学习算法以准确度为目标导向.例如,决策树所采用的信息熵,k近邻算法中所采用的投票准则,以及支持向量机,Adaboost等经典学习算法所使用的损失函数都与准确度有着密切的关系[12-13].然而,简单的准确度指标作为反馈或启发准则包含了由于偏差所导致的随机一致性,这对于学习机泛化性能的评价是不合理的.

因此,研究如何消除学习过程中的随机一致性,从而建立基于纯一致性度量(消除随机一致性的一致性度量)的机器学习算法与理论体系已成为人工智能研究领域的一个重要科学问题[14-17].

支持向量机(support vector machine, SVM)是传统机器学习中泛化能力较强、理论保障较为完善的方法之一,被广泛应用在故障诊断、文本分类等各个领域.本文首先给出纯准确度的定义,然后提出基于纯准确度的支持向量机分类方法PASVM,并通过KEEL数据集验证PASVM的泛化性能.

1 纯准确度指标

Table 1 Confusion Matrix表1 混淆矩阵

TP(true positive)表示正类样本被分为正类的比例;

FN(false negative)表示正类样本被分为负类的比例;

FP(false positive)表示负类样本被分为正类的比例;

TN(true negative)表示负类样本被分为负类的比例;

p表示真实类别中正类的比例;

q(h)表示分类器输出正类的比例.

基于混淆矩阵,准确度A和错误率L的定义分别为

A(h)=TP(h)+TN(h),

(1)

L(h)=FN(h)+FP(h).

(2)

1.1 随机准确度指标和纯准确度指标的定义

如引言所述,分类器构建过程中存在着不可避免的随机因素.本文引入置换划分集来刻画随机因素对分类结果的影响.

定义1.置换划分集Hq(h)为类别分布与待评估分类器h(X)相同的所有可能的二值划分组成的集合:

Hq(h)={h′:P(h′(X)=+1)=
q(h)，h′(X)=±1}.

(3)

例1.对于只包含3个样本的数据集,假设待评估分类器的类别分布为q(h)=2/3,那么置换划分集为包含3种二值划分的集合:

Hq(h)={h1=(-1,+1,+1),h2=(+1,-1,+1),
h3=(+1,+1,-1)}.

当分类器视被视为一个随机变量时,其分类结果的随机性可以通过类别分布来体现.置换划分集包含了与当前分类器输出分布相同的所有可能的划分结果.基于此,置换划分集的某些数字特征可用来刻画随机性导致的一致性.本文使用置换划分集中所有划分的平均准确度来衡量随机一致性,并且因缺乏划分对数据偏好信息的先验(倾向划分哪些样本为正类),我们假设所有的划分以相同的概率出现.

引理1.当置换划分集中的所有划分是均匀分布的,其平均准确度为

Eh′:h′∈Hq(h)(A(h′))=pq(h)+
(1-p)(1-q(h)).

(4)

当置换划分集中的划分服从均匀分布时,TP(h)服从参数为(N,Np,Nq(h))的超几何分布,即从N个样本中(其中包含Np个正类样本)中不放回地抽出Nq(h)个样本,TP(h)表示其中包含正类样本的个数.于是,我们有:

其中j=0,1,…,Nq(h).进一步基于超几何分布的2个重要公式:

(6)

我们有:

(7)

证毕.

定义2.分类器h(X)的随机准确度定义为

RA(h)=pq(h)+(1-p)(1-q(h)).

(8)

定义3.分类器h(X)的纯准确度定义为

需要指出的是,纯准确度与统计学中的κ指标形式相同,不同的是κ指标从评估者独立时的一致性来刻画随机一致程度[16].随机准确度的定义更具有启发意义,可指导其他指标中随机一致程度的定义,也可以扩展置换划分集的定义形式和概率分布来定义新的形式.

纯准确度从准确度中减去随机一致的部分,再除以上界使得最大值归一化,其定义框架与聚类中的调整兰德指数[4-5,7-8]相同.图1展示了纯准确度指标以随机准确度值为基准线(零值线);准确度指标以绝对零值为基准线.纯准确度指标是相对指标,衡量算法优于随机划分的程度,而准确度指标是绝对指标,衡量算法取得的分数.在机器学习中,不同任务的数据集,不同类型的运行环境,不同的算法,导致分类器产生程度不同的随机一致性.因此纯准确度指标作为评价指标更为合理客观,具有更多的信息量.

Fig. 1 The diagram of the baseline图1 基准线示意图

定义4.分类器h(X)的纯错误率定义为

进一步，纯错误率还可以表示为

纯准确度指标和纯错误率指标属于线性分式指标.线性分式指标是指形式如(13)的指标:

其中,ai,bi(i=0,1,2)是不为零的常数.类似指标还包括F1-measure和精确率Precision等.

1.2 随机准确度的进一步分析

本节进一步分析随机准确度在评价过程中的作用及意义.图2展示了随机准确度值RA与真实标签的类别分布p及输出标签的类别分布q之间的曲线图.可以看到,(0.5,0.5)是纯准确度曲面的鞍点:在p=q方向,0.5是曲面的最小值点;在p+q=1方向,0.5是曲面的最大值点.

Fig. 2 The relationship between the random accuracy and the class distribution图2 随机准确度与类别分布的关系

准确度指导的分类器往往过度拟合大类样本.纯准确度值随着准确度的增加而增加,随着随机准确度的减少而增加.在纯准确度指导下,为了保证较高的准确度,分类器与真实标签类别分布趋势应该相同(同时小于或大于0.5);为了保证达到较低的随机准确度,分类器应该趋近于无偏的(输出分布接近于0.5),进而有望更加接近于真实分布.基于上述分析,可以看到随机准确度使得纯准确度追求完全的输出随机性(输出概率为0.5),而不是依赖于经验数据的有偏差的随机性.

在实际任务场景中,机器学习算法面对的数据越复杂,所得到的分类模型与真实模式之间的偏差越大,相对于真实模式的随机性越强,从而产生更高的随机一致性.表2展示了10种不同任务的数据集.我们通过改变数据的不平衡度和噪音水平来验证随机准确度是否能捕捉到偏差造成的随机一致性.具体地，通过对每个数据集的小类样本欠抽样,得到不同IR(imbalance ratio)的数据集.IR表示大类与小类样本的数量比例.通过数据的标签加入单边噪音,得到不同噪音水平的数据集.这里,单边噪音是指小类样本的标签随机均匀地被污染为大类.在人工标注中,这种单边噪音相较于另一侧的单边噪音(大类标注为小类)更为常见.

然后,每个数据集按照7∶3的比例划分为训练集和测试集,使用训练集建立SVM分类器.实验进行30次,图3和图4的记录了测试随机准确度值(箱线)及其平均值(紫色圈),从图3和图4可以看到,随着IR和噪音水平的升高,随机准确度的值升高,这说明随机准确度的定义是有意义的.

Fig. 3 The random accuracy increases with the increase of imbalance degree图3 随机准确度随着不平衡程度的增加而增加

Fig. 4 The random accuracy increases with the increase of the one-size noise level图4 随机准确度随着单边标签噪音水平的增加而增加

2 基于纯准确度的支持向量机模型

为了消除SVM模型的随机一致性,本文提出优化纯准确度的SVM模型.首先,简要回顾SVM模型,可用来优化纯准确度指标的SVMperf(support vector machine for multivariate performance measures)模型及梯度下降法.然后,给出基于纯准确度指标的SVM模型PASVM及其求解过程.

2.1 SVM、SVMperf及梯度下降法回顾

SVM模型是传统机器学习中泛化能力较强的分类方法之一,该方法的基本思想是样本点不仅能够正确分类并且所有样本点到分类器界面的距离要尽可能大.

SVM模型为

s.t. ∀i:ξi≥0,yi(wTxi)≥1-ξi,

(15)

其中,ξi是错误率的上界.参数C为错误率和权重项的折中参数.SVM模型也可以等价表示为

为了构建优化F1-measure,Precision等多元复杂指标的SVM模型,文献[18]提出SVMperf模型.SVMperf模型可以用来优化纯准确度.其基本思想是将所有训练数据看作一个整体,然后要求真实标签向量与其他所有可能标签向量之间的间隔要超过它们之间的评价指标值.

其中ξ可证明是目标度量Ψ的上界.参数C为错误率和权重项的折中参数.

与传统的SVM模型相比,SVMperf的待解变量减少,然而约束条件的个数为2N-1个,与样本数量呈现指数增长关系.

其中ε为折中参数.在二类分类问题中,线性分式指标Ψ的梯度定义为

据此,模型参数w的更新公式为

其中λ为更新步长.

2.2 PASVM模型

构建基于纯准确度指标的支持向量机模型最直观的方法之一是使用纯错误率指标替代传统SVM模型中的错误率指标:

其中,L=EX,YI[Yh(X)<0],q=EYI[Y>0],I[·]为示性函数.

这个目标函数的难点在于纯错误率指标呈分式形式,并且L和q中存在不连续的非凸的示性函数.L中的示性函数表征样本是否被错误分类,q中的示性函数表征样本是否属于正类.在本文所采用的优化方法中L出现在目标函数中,q出现在约束条件中.因此,本文使用连续的凸的hinge函数和有界的sigmoid函数分别近似L和q中的示性函数:

(19)

那么,基于纯准确度指标的SVM模型为

(20)

称之为PASVM模型.

定理1.表示定理[20].设Ω是一个严格单调递增函数,c是任意损失函数.则每一个正则化风险

(21)

的最优解满足:

(22)

易知,PASVM模型满足表示定理.对于PASVM所使用的线性分类器,模型参数w的最优值满足:

(23)

即最优值由训练数据X张成.此时,模型的决策函数为

(24)

由表示定理可得，PASVM的核函数形式为

(25)

PASVM的求解问题属于带有正则项的分式规划问题:

其中,g2(z)≥0,g3(z)>0.令

此类问题的解可以等价转换求解z(r*),其中,

(28)

可以看到,上述过程将分式规划问题式(26)转换为一个带有约束的规划问题式(27)和一个一维优化问题式(28)[21].

然而,对于PASVM模型而言,在训练集上,分母的最优值为p+(1-2p)p.因此,可以省去r*的寻找.基于此,PASVM模型的最优解可以通过以下带有约束的规划问题求得:

(1-2p)p.

与传统SVM模型相比,PASVM模型多了一个约束条件.与SVMperf模型相比,借助分式规划问题,PASVM只需要一个约束条件实现求解,这得益于纯准确度的分母形式可以表示为真实标签和预测标签类别分布的函数.对于F1-measure,Precision而言,使用上述分式规划式(26)求解可能需要寻求最优的r*.

为了进一步提高PASVM模型的泛化能力,我们将半监督学习的思想融入到模型求解过程中.半监督学习使用大量的未标记数据,以及同时使用标记数据进行机器学习.从式(19)中可以看到,q的计算未使用样本的标签.因此,规划问题式(29)约束条件的可以使用未标记数据.具体地,规划问题式(29)可以扩展为

其中,样本xi,xj属于同一集合并且都是标记数据:xi,xj∈D1;xk属于另外一个集合,是标记数据或者未标记数据:xk∈D2.Nt为数据集Dt的样本数量,t=1,2.算法1给出PASVM的分类方法.

算法1.基于纯准确度的支持向量机PASVM.

输入:标记数据集D1、数据集D2、参数C、待分类样本x;

输出:预测结果.

1) 初始化αj为[0,1]区间的任意值;

2) 计算核相似度矩阵K(xi,xj),xi,xj∈D1,K(xk,xj),xj∈D1,xk∈D2,计算

3) 使用内点法求解问题式(30),得到模型参数αj,j=1,2,…,N1;

4) 预测结果

3 实验分析

为了验证基于纯准确度的SVM方法具有更加优异的性能,本文将PASVM方法与传统的SVM方法、SVMperf[18]、梯度下降法[19]及优化纯准确度的Plug-in[22]和Bisection[22]方法进行比较.

Plug-in方法的决策函数形式为

其中，η(x)=P(Y=1|X=x)为后验类属概率,δ为决策阈值.Plug-in方法是二步法,首先根据已有成熟的概率估计的方法得到后验类属概率,再按照某种搜索方法得到使得目标度量最大的决策阈值.Bisection方法归属于Plug-in这一类方法,不同的是Bisection方法按照二分法搜索δ.

3.1 数据集及设置

本文在KEEL[23]的10种基准数据集上测试PASVM的有效性.10种数据集详细信息描述如表2所示:

Table 2 Description of the Data Set表2 实验数据集描述

因对比算法未使用测试集进行学习,为了保证比较的公平性,在实现算法1的过程中,我们不使用测试数据集计算约束条件,而是将训练集的样本按照7∶3的比例划分为D1和D2,p的计算按照D2中属于正类的比例计算.

在每个数据集上,进行50次实验对比,以此考察算法的平均性能.每一次对比在相同的划分下进行.另外,为了创造更加复杂的数据环境,本文对数据集依次加入3%,5%的随机均匀分布的标签噪音.

3.2 实验结果及分析

表3～5分别列出了标签噪音为0%,3%,5%这3种情况时,6种算法在10个数据集上的准确度的平均值和标准差.表6～8分别列出了标签噪音为0%,3%,5%这3种情况时,6种算法在10个数据集上的纯准确度的平均值和标准差.黑体表示算法在该行数据集上取得了最高的性能值.每个数据集上,性能值最高的算法排序为1,性能值第二高的算法排序为2,以此顺推.算法的性能值越高,序值越小.表格最后一行的Average Rank表示每列方法在所有数据集上序值的平均值,越小说明算法取得的性能值越好.表格中的黑色圆点表示PASVM显著好于该方法.显著性检验方法为配对t检验,显著性水平为0.01.

Table 3 Comparison of Accuracy on Data Sets with 0% Noise (Mean±Standard Deviation)表3 无噪音时不同算法的准确度比较(均值±标准差)

Table 4 Comparison of Accuracy on Data Sets with 3% Noise (Mean±Standard Deviation)表4 噪音水平为3%时不同算法的准确度比较(均值±标准差)

Table 5 Comparison of Accuracy on Data Sets with 5% Noise (Mean±Standard Deviation)表5 噪音水平为5%时不同算法的准确度比较(均值±标准差)

Table 6 Comparison of Pure Accuracy on Data Sets with 0% Noise (Mean±Standard Deviation)表6 无噪音时不同算法的纯准确度比较 (均值±标准差)

Table 7 Comparison of Pure Accuracy on Data Sets with 3% Noise (Mean±Standard Deviation)表7 噪音水平为3%时不同算法的纯准确度比较(均值±标准差)

Table 8 Comparison of Pure Accuracy on Data Sets with 5% Noise (Mean±Standard Deviation)表8 噪音水平为5%时不同算法的纯准确度比较(均值±标准差)

表3～8的数据表明,整体而言,PASVM取得了较高的准确度和纯准确度值.相较于其他优化准确度的方法,PASVM能够更好地优化纯准确度.

为进一步分析表3～8的实验结果,在95%置信水平下统计每种方法比其他方法统计性好的次数与统计性差的次数之间的差值.具体地,对于数据集的集合S,算法a比算法a′统计性好的次数为

(31)

算法a比算法a′统计性差的次数为

(32)

图5与图6展示了在准确度和纯准确度意义下,每种算法的Ba-Wa值.图5与图6显示,在不同噪音水平下,PASVM取得了较高的差值,这说明PASVM算法显著性好于其他算法.

Fig. 5 Significant difference comparison of accuracy图5 准确度显著性差异比较

Fig. 6 Significant difference comparison of pure accuracy图6 纯准确度显著性差异比较

接下来,对PASVM的参数进行分析.图7～9展示了不同噪音水平下,PASVM在验证集上的纯准确度值.可以看到,核函数参数对PASVM的影响比较大,不同数据集上不同核窗宽参数的最优值差异较大.同一核参数下,不同的折中参数得到的验证值基本保持在同一水平.

Fig. 7 The impact of parameters on validation sets with 0% noise图7 无噪音时参数的影响

Fig. 8 The impact of parameters on validation sets with 3% noise图8 噪音含量为3%时参数的影响

Fig. 9 The impact of parameters on validation sets with 5% noise图9 噪音含量为5%时参数的影响

4 总 结

为了消除传统支持向量机中的随机一致性,本文给出了纯准确度的定义框架,提出了基于纯准确度的支持向量机模型PASVM.该方法不仅提升了传统SVM的性能,相比于其他优化纯准确度的方法,明显提升了纯准确度值.在未来的工作中,进一步考虑更具与普遍意义的置换划分集的分布来定义其他形式的随机准确度,这将有助于提高分类器对于其他类型的随机性的区分程度.另外,构建消除随机一致性的深度学习模型,以此进一步提高深度学习的性能,也是未来值得关注的研究方向.