基于主动学习欠取样的不均衡数据SVM 分类算法

《基于主动学习欠取样的不均衡数据SVM 分类算法》由会员分享，可在线阅读，更多相关《基于主动学习欠取样的不均衡数据SVM 分类算法（7页珍藏版）》请在装配图网上搜索。

1、精品论文基于主动学习欠取样的不均衡数据 SVM 分类算法陶新民5（哈尔滨工程大学信息与通信工程学院） 摘要：传统的支持向量机(SVM)算法在数据不均衡的情况下，分类效果很不理想。为了提高 SVM 算法在不均衡数据集下的分类性能，本文提出一种基于主动学习欠取样不均衡 SVM 分类算法。该算法首先在核空间中选择一定比例的靠近不均衡分类界面近的多数类样本，然10后从中选择具有代表性和信息性的均衡多数类样本点，在实现减少多数类样本的同时将分 类界面向多数类方向偏移；在删除上一次支持向量的前提下，根据新的分类界面重新选择 多数类样本点，直到泛化性能达到最优。试验中将本文算法同其他不均衡数据预处理方法 进

2、行比较，结果表明该算法不仅能有效提高 SVM 算法在不均衡数据中少数类的分类性能， 而且总体分类性能及运行效率都有明显提高。15关键词：不均衡数据；SVM 算法；主动学习中图分类号：TP391The SVM Classifier For Unbalanced Data Based onSpectrum Cluster-based under-sampling approaches20Tao Xinmin(College of Information and Communication Engineering, Harbin Engineering University) Abstract: T

3、he classification result of classical support vector machine (SVM) algorithm in the case of unbalanced data set is not satisfactory. In order to improve the SVM algorithms classification performance under unbalanced data set, a novel under-sampling algorithm based on25active learning is presented. S

4、ome majority instances located near the classification interface are selected,then the representive and informative majortiy samples in the selected samples areused as the training majority samples,which can not only reduce the number of majority instances,but also make the SVM classification interf

5、ace bias toward the majority instances. Substantly the support vectors are deleted ,the training majority samples are iteratively reselected by the new30obtained classifcation intrerface until the general classifcation performance is the best. In the experiments, the proposed approach is compared wi

6、th other data-preprocess methods for unbalanced dataset classification,the experimental results demonstrate that the proposed method can not only improve classification performance of SVM in the minority class data, but also increase the overall classification performance and effectivity35Key words:

7、 Unbalanced Data; Support Vector Machine; Spectrum Cluster0引言支持向量机(SVM)是以统计学习理论为基础的一种新型机器学习方法1。它克服了神经 网络和传统分类器的过学习、局部极值点和维数灾难等诸多缺点，具备较强的泛化能力，现40已成为机器学习领域的一个新的研究热点。不过由于SVM方法属于有监督分类算法，因此需要数目相同的不同类别样本进行训练 才能获得较好的泛化能力。但是在现实生活中，很多数据样本都是不均衡的，针对不均衡数 据集进行分类时，由于各个类别的样本数目存在很大差异从而导致不同类别的样本对于训练算法提供的信息不对称，导致SVM算

8、法对少数类样本的错分率增大。因此，如何实现SVM基金项目：国家自然科学基金面上项目（61074076），中国博士点新教师基金（20092304120017）作者简介：陶新民（1973-），男，副教授，博士，从事模式识别、信号检测的研究. E-mail: taoxinmin- 7 -45算法在不均衡数据下的正确分类成为众多学者关注的重点1-3。 目前提高不均衡数据下SVM算法性能的研究主要集中在算法层面和数据层面。如文献4提出的代价敏感算法等。而数据层面有如文献5提出的基于随机过取样代价敏感SVM算法、 文献6提出的基于SMOTE(Synthetic Minority Over-Sampling

9、 Technique)代价敏感SVM算法以及基于边界BSMOTE过取样的SVM算法等。然而过取样算法需额外增加了很多新的训练50样本，因此导致SVM模型计算代价增大。欠取样算法则是一个与过取样相反的方法，其中 包括随机欠取样7，以及借鉴实例简约的DROP算法和CNN算法8，但是由于欠取样算法只随机选取了多数类的一个子集，而这些选取出来的子集对改善SVM分类界面是否有效却未 知，如选择不当可能会导致分类效果很不理想9。因此，如何在保证数据均衡的同时，使得保存的样本信息对决策界面的生成更有效是利用欠取样提高不均衡数据下SVM算法分类性55能的关键。因此本文提出一种基于主动学习的欠取样策略，即首先利

10、用 SVM 进行分类然后选择距 离分类边界近具有代表性的多数类样本，并同少数类样本组合共同构成训练样本集对 SVM 算法进行训练。然后删除支持向量后，根据新得到的分类界面重新从剩余的多数类样本中选 择，重复上述步骤直到性能达到最优。实验部分将建议的基于主动学习欠取样的 SVM 算法60同其他取样与 SVM 相结合的算法进行比较，结果表明建议的算法在数据不均衡情况下分类 性能较其他算法有较大幅度提高。1SVM 算法及其不均衡数据分类问题分析传统的SVM算法都是基于数据集中各类样本数目基本均衡的假设，显然，这一假设在 现实应用领域中多数时候并不成立。实际上，在大多数的应用领域中往往很多类别并不均衡

11、，65数据集中某个类别的样本数可能会远多于其他类别；另外不同类别的分类错误带来的损失也 不尽相同，这就引出了不均衡数据集的分类问题。为了测试数据不均衡对SVM分类器的影响，选用高斯函数生成的数据集作为测试样本 集，其中一类样本中心为(0.3,0.5)，另一类样本中心是(-0.3,-0.5)，方差定为0.5。SVM算法的 参数设置如下：选择高斯核函数，核宽度为10，惩罚常数选择为C=10，两类样本数目比例70为100：1，其中少数类样本数为5，SVM算法的分类情况如图1所示。从图1的结果我们清楚 地看到SVM分类边界向着少数类方向进行了偏移，这是由于SVM 算法本身的优化函数对不 同类别的错误分

12、类采用了相同的惩罚系数，在这种条件设置下，由于少数类样本密度小，训 练后得到的总体训练误差也小，因此为了能使间隔尽可能大的同时尽量降低错分经验风险， 算法学习得到的分类超平面就会向样本数量小的类别移动。这样一来，势必会导致最终的75SVM 分类器对小数量的样本类别产生较大的测试误差，因此，为了提高SVM分类器的分类 性能，必须解决SVM算法在不均衡数据下分类边界偏向于少数类样本的问题。3多数类210-1少数类-2分类边界-3-3 -2 -1 0 1 2 3图 1 数据样本比例为 100:1 时 SVM 算法的分类边界Fig.1 Interface of SVM under 100:1802基于

13、主动学习欠取样不均衡 SVM 分类算法8590951002.1 传统欠取样算法分析由于在多数类样本中存在大量的重复信息，这些冗余信息会导致多数类与少数类样本的 数目不均衡从而严重影响 SVM 分类器的界面生成，因此传统的欠取样算法通过剔除这些远 离边界的冗余多数类样本并保留有效多数类边界样本的方式来实现数目间的均衡。这种方法 包括：DROP 和 CNN 以及 ODR3等算法。然而这些减少多数类样本数目的欠取样数据预处 理方法并不适合于 SVM 算法，这是因为 SVM 算法的分类边界只与支持向量有关，因此通 过删除远离边界的多数类冗余样本来减少多数类样本，即使实现了多数类和少数类样本数目 间的均

14、衡，但仍不能改变 SVM 分类边界的位置，即无法实现分类边界向多数类样本偏移。 这由 SVM 判别公式不难发现，分类边界的形成只与支持向量有关，因此均衡前后分类边界 没有发生任何变化，这个示例说明传统欠取样算法减少多数类样本的方式并不适合于改善不 均衡数据下 SVM 算法的分类性能。2.2 基于主动学习的欠取样由 SVM 的原理可以看出：决策面是只与 SV 有关的超平面，SVM 通过使分类间隙最 大来设计决策超平面，以获得最好的推广能力。为了能最大限度地保留有用的多数类样本点， 就要设计一个既能代表多数类分布特征，又能对分类界面有一定影响程度的欠取样方法。我 们知道样本点到决策超平面的距离是判

15、断该点分类性质的主要因素，距离越近则对分类界面 的影响就越大；另外，所选择的样本是否具有一定的空间代表性也是欠取样算法的成功关键 所在。为了能选择具有空间代表性以及信息性的样本点，本文提出一种新的方法。该方法是首 先根据信息密度值对多数类样本进行排序，然后选择排在前面的那些多数类样本点，具体公式如下所示：b 1 Uf ID ( x) = f ME ( x) sim( x, x (u ) ) (1) U u =1 f ME ( x) 是信息量的度量，可以采用信息熵或者距离边界的距离等公式，后一项则考虑的是 该样本的密度，即考虑该样本的代表性， b 用来控制代表性影响的强度。r r105sim(

16、x, x (u ) ) =x x(u)或c osr rx x(u)rrsimxGauss( r,x (u ) ) =Uu =1exp( -x - x (u )2d 2(2)d 是高斯核半径参数，该参数对该项的影响很大，过大则太过泛化，太小则局部化太强。 因此本课题拟采用一种所有样本最小距离中的最大距离的倍数：22d = gD = g maxmin( xk - xl)x(3)110其中g 是个固定数值。kxl为了考虑选出来的样本彼此之间的相关性，即考虑选出的样本之间的差异性。本课题拟 采用考虑样本集合间差异性的信息量评测标准，如下：f MID (x) = f ( Z ) (x) 1 Ub1 Q(

17、4) l sim(x, x (u ) ) + (1 - l) dif f (x, x ( q ) ) 其中115 U u =1Q q=1diff ( x, x ( q ) ) = 1 - sim( x, x ( q ) )(5)1201251301352.3 基于主动学习欠取样不均衡 SVM 分类算法为了减少训练时的计算量以及不均衡数据给 SVM 分类界面带来的偏移影响，本文提出 一种具有主动学习欠取样策略的不均衡 SVM 分类算法，算法首先利用原有数据训练得到了 分类界面(不均衡分类界面)，然后选取一定数量距离边界前 L MI (少数类样本)近的多数 类样本，然后利用公式(5)对多数类样本点

18、进行排序，保留具有大信息量且具有代表性的 MI 个多数类样本作为新的训练样本进行学习；得到新的分类界面并计算该分类器的训练错误 率；随后删除这些样本重新进行训练，再利用新得到的分类界面重新选择多数类样本，循环 直到多数类样本用尽为止。注意，这些保留的样本有可能是噪声样本也有可能是有用的样本， 如果是有用的样本，那么由此训练形成的分类界面的精度就会很大，这样就可有效避免欠取 样算法导致的有用信息的删除；相反如果是噪声样本，则由此形成的分类决策权重就会减少， 而删除后接下来形成的分类器的权重就会增大，最终通过权重投票机制就可以防止噪声对算 法性能的影响。同样这种采样方法也可以有效避免孤立样本对分类

19、边界的影响，最终使得那 些密度大且距离边界近的多数类样本被选择作为多数类训练样本集合。重复训练直到得到一 定数量的分类假设，并计算得到的分类假设的训练错误率，作为集成分类的基分类器集合以 及权重计算的依据。3实验分析及对比3.1 实验数据本文选用来源于国际机器学习标准数据库 UCI 中的 3 组不同的数据集对算法进行实验，数 据特征信息见表 1：其中类别表示选择出来作为少数类和多数类样本的代表类别。表 1 实验数据集描述Tab.1 Data Description数据集属性少数类/多数类类别haberman4126 /2252:1german25300/700B/Apima9268/5001:

20、01401451503.2 不同算法的分类性能比较为了比较本文算法在不均衡数据下的分类性能，试验中应用本文算法(ALU-SVM)对上 述数据集进行分类，并与基于随机欠取样的 SVM 算法(RU)、基于 SMOTE 过取样的 SVM 算法、基于 BSMOTE 过取样的 SVM 算法的结果进行比较。对于每一个数据集，采用 10 次 交叉验证的方法进行实验，对于每次交叉实验运行 10 次以防止随机影响，最后计算这些实 验的 F-MEASURE、G-MEAN 和 AUC 性能评测指标的统计平均值。对于本次实验我们选取1:10 的比例进行随机选择，以考察不均衡数据下算法的分类性能。其中分类器 SVM 参

21、数设 置为：核函数为高斯函数，核宽度数为 10，惩罚因子 C = 1000 ，SMOTE、BSMOTE 算法 中最近邻算法参数 k 选择为 6，其他欠取样算法保留着与少数类样本数目相同的多数类样本。 代价敏感 SVM 算法的多数类的代价与少数类的代价比值设置为 CMI / CMA = 10 ，本文算法 中 L = 5 * ML，l = 0.5 ，为了能和 SVM 算法很好地融合，本文算法中d 的值设置为与 SVM 算法核宽度相同。实验结果如表 2 所示，对不同数据集的 F-MEASURE、G-MEAN 和 AUC 性能指标的实验对比结果。表 2 10:1 不均衡数据下数据集 F-MEASURE

22、、G-MEAN 和 AUC 性能比较Tab.2 F-MEASURE、G-MEAN and AUC peformance comparison under 10:1DatasetMethodsG-MeanF-measureAUCSVMALU1.000.823.1060.0.00.460.0730.0.00.612.061habermanRU0.961.0630.128.1060.281.211Smote0.769.1610.469.0820.588.057BSMote0.769.1710.469.0920.590.062SVMALU0.998.0040.776.0980.035.0050.604

23、.0920.039.0460.679.026germanRU0.856.0370.482.0530.641.034Smote0.824.0290.481.0320.629.024BSMote0.831.0360.472.0310.626.0251.0.00.718.1340.0.00.767.1140.0.00.733.0430.0.00.833.068pima0.898.0750.521.0460.682.0380.673.0380.768.0730.687.0450.725.0340.789.0290.772.0760.685.0410.726.0350.788.027155从上面的结果我

24、们可以看出，SVM 算法针对不均衡数据集分类而言，出现来严重向多数类样本方向偏移的问题，其中针对大部分数据集，其 SVM 算法的 Specificity 性能指标多 为 1，而 Sensitivity 性能指标基本为零，而其他不均衡数据分类算法在二者指标上都有明显 的性能提高。其中本文算法的 G - mean 性能在各个数据集分类上都优于其他的不均衡数据 SVM 分类算法。由于 G - mean 性能既考虑了多数类的样本分类性能也考虑的少数类样本 的分类性能，因此可以说本文算法在整体性能上最优。观察另一个 AUC 性能评测指标，我160165170们发现本文算法和 SVM-Weight 算法在

25、该性能指标上表现较好。而同样是欠取样算法的随机欠取样算法 RU，由于对多数类采样的盲目性使得该算法对不均衡数据分类性能的改善不如 本文算法显著。3.3 高斯核半径对算法性能的影响为了测试高斯核半径参数对本文算法分类性能的影响，我们选用 haberman、german 数 据集作为测试数据，多数类样本数目和少数类样本按 20：1 的比例选取，利用 10 次交叉验 证法测试，参数选定在(0.5,4.5)区间，其他参数设置同上，其中本文中的相似度计算以及 SVM 算法的计算都在同一个参数的特征空间进行，测试结果如图 2、3 所示。从图中的结果可以得出：本文算法随着参数的增大，算法性能呈明显的上升趋势

26、，这说 明针对欠取样算法而言高斯核半经参数越大则分类性能越好。这是由于本文主动学习欠取样 算法选取的多数类样本点都具有一定的空间代表性，因此为了能在算法中发挥代表作用，需 要将自身的邻域半径进行扩大以便使受其影响的面积增多。然而随着参数的进一步增大，分 类性能开始出现下降趋势，这是由于随着参数的增大，每个样本的影响区域不断增大导致学 习能力降低，因此选择一个合适的参数对于本文算法的性能提升具有一定的帮助，从本文实验结果可以看出参数在2,4区间性能最优。0.850.8haberman german0.750.7Fmeasure0.650.60.550.50.5 0.8 1 1.1 1.5 2 2

27、.5 3 3.5 4 4.5belta value175图 2 不同参数下本文算法 F-MEASURE 性能比较Fig.2 F-MEASURE of different parameters0.750.7AUC0.650.60.55haberman german0.5 0.8 1 1.1 1.5 2 2.5 3 3.5 4 4.5belta value图 3 不同参数下本文算法 G-MEAN 性能比较Fig.3 G-MEAN of different parameters1801851901952004结论针对 SVM 算法在不均衡数据下分类性能差的问题，提出一种基于主动学习欠取样的 SVM

28、分类算法。算法首先在 SVM 特征空间中通过选择具有代表性同时具有一定信息性的 多数类样本点，实现 SVM 分类界面向着多数类样本方向逐渐偏移的目的。实验部分将本文 算法同其他不均衡数据分类算法进行了比较，结果表明：本文算法在不同数据集分类性能都 优于其他算法。实验最后，为了考察高斯核半径参数对算法性能的影响，本文利用不同参数 值对不同数据集进行实验，结果发现本文算法在参数设置较大时分类性能较好，这一现象也 同样符合本文基于欠取样算法的机理。参考文献 (References)1 Haibo H,Edwardo A.Learning from Imbalanced DataJ.IEEE Tran

29、saction on Knowledge and DataEngineering,2009,21(9):1263-12842 Liu X.Y.,Zhou Z.H. Exploratory Under-Sampling for Class-Imbalance LearingJ.IEEE Transactions onSystems,Man and Cybernetics.2009,39(2):539-5503 Liu X.Y.,Zhou Z.H.Training Cost-Sensitive Neural Networks with Methods Addressing the Class Im

30、balanceProblemJ. IEEE Transactions on Knowledage and Data Engineering, 2006,18(1)：63-77.4 陶新民,徐晶,童稚靖.不均衡数据下基于阴性免疫的过抽样算法,控制与决策,2010,25(6):867-873 5 毕华,梁洪力,王珏.重采样方法与机器学习J . 计算机学报,2009, 32( 5) : 862-8776 Sun,Y.,Kamel M.S. and Wong A.K.C. Cost-Sensitive Boosting for Classification of ImbalancedDataJ.Pat

31、tern Recognition,2007,40(12):3358-3378.7 曾志强,吴群,廖备水,高济.一种基于核 SMOTE 的非平衡数据集分类方法J.电子学报,2009,39(11)：2489-2495.8 Y.Liu,X.H. Yu.Combining integrated sampling with SVM ensembles for learning from imbalanced datasetsJ.Information Processing & Management,2010,12:409-4399 王 玲, 薄列峰, 焦李成.密度敏感的半监督谱聚类J. 软件学报,2007,18(10):2412-2422