倾斜数据集的分界修剪支持向量机

周华平 张贝贝 刘光宗

摘 要：倾斜数据集在实际应用中具有很高的价值，同时也是数据挖掘中的难点和热点，因而得到越来越多的研究者的关注。通过给出的一种改进的支持向量机—DP-SVM，首先对数据集进行预处理、分类，再对它们采取相应的操作；
然后根据混叠数据集中样本的k个最近邻的类别，并结合波动大小与其相应类限定值的关系，对该样本点做相应的处理；
最后根据副类支持向量与主类样本数量之间的关系，决定对副类支持向量采取何种修剪策略，训练得到其分类器。提出的分界修剪支持向量机由消除分类边界混叠与支持向量修剪两个主要处理部件构成，并通过这两个处理部件实现对分类边界混叠数据的判别及两类支持向量的修剪。实验结果表明，DP-SVM是一种能够较好地解决倾斜数据集分类边界混叠问题的有效方法。

关键词：倾斜数据集；
混叠现象；
支持向量；
分界修剪支持向量机

中图分类号：
TP391 文献标志码：A

文章编号：1672-1098（2017）06-0008-07

Abstract：This paper was to present an improved Support Vector Machine-DP-SVM. Firstly data sets were preprocessed and classified， and then the corresponding operation were taken on them. Secondly， according to the category of the k nearest neighbors in aliasing data set and the relationship between the fluctuation and the corresponding category limited values， the sample point was processed correspondingly. Lastly， based on the relationship between the support vectors in negative category and the number of samples in major category， the pruning strategy was determined on the support vectors in negative category，as a result， the classifier was trained to be obtained. The proposed DP-SVM in this paper was composed of two main processing components， with one eliminating aliasing data at the classifying boundary and the other supporting the vectors pruning；

and the two components could be used to realize the judgement of the aliasing data at the classifying boundary and support the vectors prunning of the two categories. The results show that DP-SVM is an effective method that can better solve the aliasing problem of skewed data sets.

Key words：skewed data sets；

aliasing phenomenon；

support vector；

demarcation pruning-support vector machine

傾斜数据集在实际应用中具有很高的价值，同时也是数据挖掘中的难点和热点，因而得到越来越多的研究者的关注。对倾斜数据集的处理，文献[1-2]提出了许多处理效果较好的理论方法，但其主要是对分类边界混叠数据做了简单的删除或对支持向量做了简单修剪，而未考虑这些数据对数据集分类正确率及主类分类精度的影响；
因此对存在倾斜的数据集的分类正确率及主类的分类精度的处理效率尚有进一步提升的空间。为了降低数据集尤其是倾斜数据集分类边界混叠数据对分类正确率以及主类分类精度的影响，本文提出分界修剪支持向量机（Demarcation Pruning-Support Vector Machine， DP-SVM）。

DP-SVM的工作过程：首先，对分类边界混叠数据进行处理。计算每个分类边界混叠数据的k个最近邻，并判断该样本所属类型：（1）k个最近邻均属同一类，若为大类，判断其标准差与副类对应的边界限定值关系，然后对其采取相应的操作；
反之，则判断其标准差与主类对应边界限定值关系，并对其进行相应的处理。（2）k个最近邻属异类，若属于副类样本数量大于属于主类样本数量，舍弃该测试样本；
反之，对该测试样本做加权操作，使其脱离分类边界混叠区，进入主类区，使得主类样本数量得以增多。其次，判断分类边界线性关系，如果非线性可分，选择相应的核函数将其转换到高维线性空间；
反之，则无需转换。最后，对支持向量进行修剪。计算副类的支持向量并判断其代价敏感程度，同时根据其与主类样本数量的关系分别进行操作：（1）主类样本数量与副类支持向量数目基本均衡，求出这两部分数据的最优超平面，即该数据集的较适合的分类器；
（2）主类样本数量与副类支持向量数目相差较多，则需根据两类样本数量的大小情况分别进行处理，最后通过支持向量机训练出合适的分类器。

1 相关工作

支持向量机（Support Vector Machine， SVM）由Boser，Guyon和Vapnik在COLT-92上首次提出，是统计学习理论中提出较晚的内容，也是最实用的部分之一，目前仍处于不断发展阶段。

为了提高倾斜数据集的分类正确率，已提出了许多优秀的相关研究方法。又因SVM主要用于二分类问题，且SVM可通过边界宽度保证其泛化能力，故有许多研究方法依据于此。KE Hai-xin等提出ESVM数据集的重采样方法，使用SVM算法在数据集上训练得到决策边界，并根据SVM的决策边界删除数据集中数据混叠部分和被错误分类的抽样样本，但该方法直接对决策边界的混叠数据进行了删除。文献[3]提出的NN-SVM方法，根据测试样本与其最近邻的类别标识的异同，决定该测试样本的取舍，但对边界混叠数据类别标识只做了简单的处理。文献[4]在NN-SVM基础上提出了KCNN-SVM，判断测试样本与其最近的训练样本的类别的异同，同类不做处理，反之则分别对其k个近邻做均值比较，并删除均值大者对应的样本点，该方法忽略了边界点对主类分类精度的影响。文献[5]在其论文中提出通过软间隔支持向量机与Boosting算法相结合的方式对倾斜数据集进行处理，该方法在平衡支持向量的同时，又防止了过拟合的产生，但未考虑到分类边界混叠数据对分类正确率以及主类分类精度的影响。

SVM的构建主要从两个方面：最优超平面和核函数。最优超平面作为SVM分类时的最优决策面，根据决策面是否线性可分，又分为线性最优超平面和非线性最优超平面，且可通过将非线性最优超平面转化为线性最优超平面来求出其最优决策面；
核函数主要是解决低维空间向量难分的问题，通过将低维空间向量映射到高维空间的方式来解决[6-11]。

上述方法对分类边界混叠数据只进行了简单处理或只考虑到对分类器的修正，而忽视了该数据点与分类器的共同作用对分类正确率的影响，尤其是对倾斜数据集中主类分类精度的影响。鉴于此，本文针对倾斜数据集，提出了一种改进的支持向量机——分界修剪支持向量机。该方法通过将对分类边界混叠数据的处理与对支持向量的修剪相结合的方式，来实现对倾斜数据集的处理，从而进一步提升分类正确率以及主类的分类精度。

2 DP-SVM

SVM在对数据集分类时会受到类间样本分布不均衡的影响，造成分类决策面的偏移，导致最优分类超平面向主类倾斜，从而使得主类的分类误差率增加。然而，主类的分类精度对一些实际应用的影响又比较大，如医疗诊断、信用卡入侵检测、电信客户流失、垃圾邮件过滤及设备故障预测[12-18]等研究领域，因此不断地提高倾斜数据集的分类正确率以及主类的分类精度就显得尤为迫切。鉴于此，本文结合数据处理与支持向量数目修剪，提出了DP-SVM方法。

3）上述策略的实现算法

（4）实际分类中，尤其是倾斜数据集分类时两类之间样本数量的极大差异，必然会导致两类支持向量数目的不平衡，而给分类正确率带来极大的影响，为降低其负面作用，特通过引入松弛变量ξi与惩罚因子C来允许实际分类中存在一定的不准确性以及放弃一些重要的数据来减小分类器分类正确率的损失；

（5）为减少两类之间的倾斜程度，比较NS支持向量数目与MS中样本数量的关系，从而决定对NS的支持向量是否修剪。

本文基于（4）、（5）两点，通过对NS使用支持向量修剪策略以及对MS采取相应操作方式来训练分类器。

1）MS样本数量与NS支持向量数目均衡

MS样本数量与NS支持向量数目相差较小，故而MS支持向量数目稀少，因此引入软间隔来允许MS中一些点到分类平面的距离可以不满足必须大于某个值的要求，尋求出的这两部分数据集的最优超平面即是整个数据集的最优超平面。本文使用的数据集属此类情况，由抽取的随机样本组合而成。

2）MS样本数量与NS支持向量数目相差较多

① MS样本数量远小于NS支持向量数目（此种情形多出现于MS样本数量绝对稀少或数据集较小），该类情况根据具体实验数据，从以下两种方法中选择一个较适合的方法，对数据集进行处理。

a. 在MS数据集上使用SMOTE算法[20]，以增加MS样本数量。但此过程中，需即刻验证新生成点是否可被正确分类，若不可，删除该点，反之则保留，直至MS样本数量与NS支持向量数目大致均衡为止，再求出这两部分数据的最优分类器。

b. 仿照主成分分析方法，通过构建NS分类器来判断NS每个支持向量的重要程度，并为其赋予相应的权值，从中抽取权值较大者，并保持其数目与MS样本数量大致相同，然后再根据两者求出其最优超平面。

② MS样本数量多于NS支持向量数目且MS支持向量数目远少于NS支持向量数目，此情形较常出现于大型或超大型倾斜数据集（倾斜比相对较小）。先对MS中除其支持向量外的数据判断其权重，再根据NS支持向量的数目，从MS中抽取出其支持向量及权重较大的样本，并使之与NS支持向量数目尽量达到平衡，然后再根据这两个修剪后的数据集求出最优超平面。

本部分内容主要是先对数据集进行初步分类，利用最远距离，找出AS，并利用最近邻、标准差、类限定值对AS进行训练，得到处理后的训练集TA。然后对其进行分类边界判定并对非线性边界进行转换；
最后再对支持向量进行修剪，最大程度上保证NS分类正确率的同时又提高了MS的分类精度。上述获得分类器的方法称为DP-SVM。

相对于SVM，DP-SVM具有以下优点：

（1）分类正确率的提高

应用SVM之前对数据集A处理，得到训练集TA，再对训练集TA进行分类，从而使分类边界的混叠现象得到很大的改观；
其次，将非线性可分的边界通过核函数转换为高维线性可分情况；
最后，先对NS的支持向量加权，再根据MS样本数量与NS支持向量数目的关系，分情况构建相应的支持向量机，从而得到最优超平面。DP-SVM使分类边界得以简化，泛化能力得到提升，同时分类正确率也得到提高，第四部分对此做了验证。由实验结果可知，DP-SVM是一种能够解决倾斜数据集分类边界混叠问题较为有效的方法。

（2）主類分类精度的提高

MS分类的精度与该类样本数量及新增样本数量有很大关系，一定程度上受到NS支持向量数目的影响。数据集A处理后，一定程度上增加了MS的样本数量，使MS中样本信息得到丰富。MS精度的提升幅度大于分类正确率的提升幅度。倾斜比越大，混叠现象越严重，MS精度提升的越多，因此有较高的应用参考价值。

当然，DP-SVM的上述优点是以增加额外修剪处理时间为代价的，而此代价与分类正确率及MS分类精度的提高相比是可以接受的。当前计算机的处理速度很快，即使面对较大的倾斜数据集也能够快速地对其做出处理。

3 实验与分析

3.1 实验环境

选择使用的是HP型号机（Intel 340G，40G内存），使用的软件是Matlab71版本以及自己编制的数据集处理及支持向量修剪程序。数据集是Stat log（德国信用数据）1 000个、Stat log（澳大利亚信用批准）690个、信用筛选数据集690个，数据集来自数据堂，所用五维数据均已经过脱敏处理。本文实验数据是由数据集中的数据处理后组合而成。且本文的对比实验，未考虑维度的这一因素，是鉴于维度在Boosting-SVM、DP-SVM、KCNN-SVM方法中更多的是增加了计算的复杂度，而对分类准确率、MS分类精度影响相对较小的原因。

3.2 实验结果与分析

θ-、θ+是实验时推导出来的修订值，随着样本集以及样本数量的不同，θ-、θ+取值也会不同。实验结果如图4～图5。由于所采用样本集样本数量有限，故实验结果难免会有一定的偏差。图4是在倾斜比、混叠程度一定时，样本量对分类正确率及MS分类精度的影响。一定程度上样本量越多，可获取的样本信息越丰富，分类的正确率也会越高，根据其趋势图可预测当样本量达到一定程度时，其对分类正确率及MS分类精度的影响将趋于平缓。由图4左图可知，样本量对分类正确率及MS分类精度在三种方法下，均有提高；
但当样本量不足（小于300）时，DP-SVM方法的分类正确率略优于其他两种方法，样本量稍多（300～600）时，Boosting-SVM的分类正确率高于DP-SVM方法，主要受到DP-SVM中参数对混叠边界的处理时的影响，以及支持向量在修剪时对其数目的影响，随着样本数量的增加，这一影响逐渐减小，DP-SVM方法分类正确率的优势逐渐凸显。图4右图所示，是在样本量不足（小于300）时，KCNN方法的分类精度高于其他两种方法，源于其对样本的简单的k近邻处理，随着样本量的增加，其优势逐渐减弱，同时DP-SVM对MS分类精度的提升明显优于该方法，在一定范围内Boosting-SVM方法对MS分类精度的提升优于DP-SVM，但随样本量的增多，样本信息的丰富，DP-SVM对MS分类精度的提升幅度更为显著。图5呈现出在样本量、倾斜比一定时，混叠程度对分类正确率、MS分类精度的影响。假设无混叠时，样本的分类正确率及MS分类精度均是最优的。混叠程度较小时，Boosting-SVM方法较DP-SVM方法优良，主要是可处理的边界混叠数据的数量有限，无法呈现出DP-SVM方法的优势。随着混叠程度的加深，三种方法的分类正确率及MS分类精度均有所下降，但DP-SVM曲线较平稳，对混叠状况表现出较强的健壮性，在分类正确率及MS分类精度的下降程度上明显低于另外两种方法。

图4 样本数量对分类正确率及主类分类精度影响

图5 混叠程度对分类正确率及主类分类精度影响

4 结论

DP-SVM是一种能够解决倾斜数据集分类边界混叠问题较为有效的方法，一定程度上解决了SVM由于类间数据分布不均衡造成的过学习和泛化能力弱的问题。

随着数据量的增多，当倾斜比、混叠情况一定时，分类正确率提升缓慢，本文提到的方法略显不足。鉴于分类正确率与抽样方法关系更为密切，后续工作是探索选取何种抽样方法，以便可以更有效地提高分类正确率以及MS的分类精度。

参考文献：

[1] KE HAI-XIN，ZHANG XUE-GONG. Editing support vector machines[C]//Neural Networks， 2001 Proceedings， IJCNN01， International Joint Conference on IEEE，2001：

1 464-1 467.

[2] 黄久玲. 面向失衡数据集的集成学习分类方法及其应用研究[D].哈尔滨：哈尔滨理工大学，2015.

[3] 李红莲，王春花，袁保宗.一种改进的支持向量机NN-SVM[J].计算机学报，2003，26（8）：1 015-1 020.

[4] ZHANG SHI-RONG，ZHOU KUAN-JIU，TIAN YUAN.An improved NN-SVM based on k congener nearest neighbors classification Algorithm[C]//Knowledge Science， Engineering and Management. Springer Berlin Heidelberg，2007：550-555.

[5] BENJAMIN X WANG，NATHALIE JAPKOWICZ.Boosting support vector machines for imbalanced data sets[J]. Knowledge and Information Systems，2010，25（1）：1-20.

[6] 张学工.关于统计学习理论与支持向量机[J].自动化学报，2000，26（1）：
32-42.

[7] BURGES C J C.A tutorial on support vector machines for pattern recognition[J]. Data Mining and Knowledge Discovery，1998，2（2）：121-167.

[8] VAPNIK V N.An overview of statistical learning theory[J]. IEEE Transactions on Neural Networks，1999，10（5）：
988-999.

[9] Vapnik V N. Statistical learning theory[M]. New York：
Wiley-Interscience，1998：2-200.

[10] KLAUS-ROBERT MULLER，SEBASTIAN MIKA，GUNNAR RTSCH，et al. An introduction to kernel-based learning algorithms[J]. IEEE Transaction on Neural Networks，2001，12（2）：181-201.

[11] XU JIE，TANG YUAN-YAN，ZOU BIN，et al. The generalization ability of SVM classification based on Markov sampling[J]. IEEE Trans. Cybem.，2015，45（6）：1 169-1 179.

[12] 吴庆忠，车峰远，薛付忠.基于非平衡数据的癫痫发作预警模型研究[J].山东大学学报（医学版），2012， 50（2）：141-148.

[13] MAJID A， ALIS S， IQBAL M. Prediction of human breast and colon cancers from imbalanced data using nearest neighbor and support vector machines[J]. Computer methods and programs in biomedicine， 2014， 113（2）：792-808.

[14] CHEN WEI-MIN，MA CHAO-QUN，MA LIN.Mining the customer credit using hybrid support vector machine technique[J]. Expert Systems with Applications，2009，36（4）：7 611-7 616.

[15] WEI WEI，LI JIN-JIU，CAO LONG-BING. Effective detection of sophisticated online banking fraud on extremely imbalanced data[J]. World Wide Web，2013，16（4）：449-475.

[16] 王春玉.非平衡数据集分类方法研究及其在电信行业中的应用[D].杭州：浙江大学，2011.

[17] DIAO LI-LI，YANG CHENG-ZHONG，WANG HAO. Training SVM email classifiers using very large imbalanced dataset[J]. Journal of experimental and theoretical artificial intelligence， 2012，24（2）：193-210.

[18] LIAO T Warren1. Classification of weld flaws with imbalanced class data[J]. Expert Systems with Applications，2008，35（3）：1 041-1 052.

[19] CHEN XUE-WEN，BYRON GERLACH，DAVID CASA-SENT.Pruning support vectors for imbalanced data classification[C]//2005 IEEE International Joint Conference on Neural Networks. Montreal，Quebec，Canada， 2005：1 883-1 888.

[20] JOSEY MATHEW，LUO MING，CHEE KHIANG PANG，et al. Kernel-based SMOTE for SVM classification of imbalanced datasets[C]// Industrial Electronics Society， IECON 2015-41st Annual Conference of the IEEE. Yokohama， 2015：001 127-001 132.

（責任编辑：李 丽）