密度不均衡数据分类算法

杜红乐，张 燕

(商洛学院数学与计算机应用学院，陕西 商洛 726000)

·计算机软件理论、技术与应用·

密度不均衡数据分类算法

杜红乐，张 燕

(商洛学院数学与计算机应用学院，陕西 商洛 726000)

针对不均衡数据下分类超平面偏移、少数类识别率较低的问题，提出一种基于样本密度的不均衡数据分类算法。该算法首先计算样本密度和类样本密度，依据类样本密度之间的关系确定聚类类数,然后利用K-means聚类算法对多数类样本进行聚类，用聚类所得类中心作为样本集取代原多数类样本集,最后对新构造的训练集进行训练得到最终决策函数。其实验结果表明，该算法能够提高SVM在不均衡数据下的分类性能，尤其是少数类的分类性能。

支持向量机；不均衡数据集；样本密度；欠取样；K-近邻

支持向量机(support vector machine， SVM)基于结构风险最小化原则，在解决小样本、非线性及高维属性等模式识别问题中表现出许多特有的优势，因此，SVM得到许多专家的关注，并在许多领域得到应用。

传统SVM在均衡训练样本下有较好的分类性能，然而，研究表明，在样本密度分布不均衡的情况下，SVM对少数类样本分类准确率远低于对多数类样本的分类准确率。因为传统SVM算法对多数类是过学习，而对少数类则是欠学习，从而导致对少数类样本的分类错误率较高。实际应用中对少数类样本的分类性能要求比对多数类样本的分类性能高得多。例如入侵检测中入侵行为样本较难收集，是少数样本，把一个入侵行为错分为正常行为要比把一个正常行为错分为入侵行为造成的危害大得多，因此为提高对不均衡数据的分类能力，学者们提出了相应的解决方法。这些方法大致可以分为2类：基于数据的和基于算法的。基于数据的方法主要是依据一定策略删除部分多数类的样本或者增加一些少数类的样本使数据集均衡化，进而提高分类器的分类性能，常用的方法有过取样[1-5]、欠取样[6-10]和混合取样[11-13]；基于算法的方法主要有代价敏感学习[14]、集成方法(如boosting[15])、单类学习法[16]等。

文献[6-11]都采用聚类算法对数据集进行相应处理。文献[7]利用K-means算法对多数类样本进行聚类并提取类中心，得到与少数类样本数量相同的样本，重构新的训练集，为避免少数类样本过少导致最终训练样本过度稀疏，对少数类样本采用SMOTE算法进行过取样。文献[8]为提高泛化能力，聚类在核空间中进行，并利用AdaBoost集成手段对该欠取样算法进行集成。文献[9]引入“聚类一致性系数”找出处于少数类边界区域和处于多数类中心区域的样本，然后用SMOTE对少数类样本进行过取样，用改进的随机欠取样对多数类样本进行处理。文献[10]利用谱聚类的优点对多数类样本在核空间中进行谱聚类，然后依据聚类大小和聚类中样本与少数类样本间的距离选择有代表性的信息点。

导致分类超平面偏移的本质是样本密度的不均衡。样本密度小，则该类样本出现的概率越小，分类超平面向该区域偏移时错分的可能性越小；因此，错分的总代价也越小(两类错分代价相同，但是错分的概率小；因此，平均出错就少，平均代价也就小)。如果超平面向密度大的区域偏移，样本出现在该区域的概率就大，造成错分的总代价就大，而支持向量机在保证分类间隔尽可能大的同时，错误分类代价尽可能的小；因此，分类超平面会向样本密度小的一方偏移。以上方法都是依据少数类样本数量和多数类样本数量之间的关系对多数类进行重取样，没有考虑实际的样本密度分布情况。

基于以上分析，结合聚类算法和K-近邻算法，本文给出一种基于样本密度的聚类算法以解决样本不均衡的问题。该算法依据类样本密度之间关系和少数类样本数量，计算多数类重取样后的样本数量k，然后用K-means聚类算法对多数类样本进行聚类，用所得的类中心作为样本取代原多数类样本集。该算法在重取样时既考虑了样本数量，又考虑样本密度的分布。其仿真实验结果表明，该方法较好地解决了不均衡数据集导致分类超平面偏移的问题，提高了支持向量机的泛化能力，提高了少数类样本的分类准确率。

1 支持向量机

1.1 支持向量机

SVM的训练过程实质是二次优化问题，既要保证分类错误代价最小，又要保证最大化分类间隔。给定一个样本集T={(x1,y1),(x2,y2),…,(x1,y1)},xi∈R″,yi∈{1,-1}。SVM的主要目的是构造一个超平面以分割2类样本，使得分类间隔最大，同时分类错误代价最小。通过求解下面二次优化问题，得到决策函数。

s.t.yi(+b)≥1-εi

(1)

εi≥0,i=1,2,…,l。

通过引入Lagrange算子，可以得到问题(1)的对偶问题：

(2)

其中K(xi,xj)为核函数，K(xi,xj)=〈φ(xi),φ(xj)〉，对于线性不可分问题，采用非线性映射φ:RkF将训练集从输入空间映射到某一特征空间上，在该特征空间上训练集是线性可分的。最后得到决策函数

(3)

由决策函数可以看出，决定支持向量机分类性能的是支持向量，即ai≠0的样本，而那些远离分类超平面的样本对分类结果影响较小可以忽略。

1.2 密度不均衡对SVM的影响

不均衡数据集指的是同一数据集中某类的样本数量比其他类的样本数量多得多，其中样本数量多的类称为多数类，样本数量少的类称为少数类。所谓不均衡分类问题是指基于这种不平衡数据集进行的分类。实际上，影响SVM分类性能的不仅是样本数量，还与样本空间分布有关，即受类样本密度的影响。

为观察类样本密度对分类超平面的影响，随机生成2类均匀分布的样本，数据集1的第1类样本为U([0,1]×[0,1])、第2类样本为U([1,2]×[0,1])，如图1(a)所示；数据集2的第1类样本为U([0,1]×[0,1])、第2类样本为U([1,1.3]×[0,1])，如图1(b)所示；数据集3的第1类样本为U([0,1]×[0,1])、第2类样本为U([1,1.1]×[0,1])，如图1(c)所示。图1中第1类样本数均为200，第2类样本数均为20，经支持向量机训练最终的分类超平面如图1(a)、(b)、(c)所示，其中细线为分类超平面。

由图1可以看出：在类样本密度不均衡的情况下，分类超平面会向少数类样本偏移，即对少数类的欠学习，如图1(a)所示；类样本密度相差较小的时候，分类超平面偏移也较小如图1(b)所示；当类样本密度相同时，分类超平面不偏移，如图1(c) 所示。换句话说，在样本密度不均衡时，分类超平面向类样本密度较小侧偏移，导致对样本密度大的类的过学习。这是因为传统支持向量机在训练的时候认为2类样本错分代价相同，而2个类(区域)样本密度不同，即出现在密度小的区域的概率小，大密度区域出现的概率大。SVM为了保证分类间隔尽可能的大，同时错分代价尽可能的小，因此分类超平面会向样本密度小的区域(少数类)偏移。针对此，文献[13]提出了对2个类采用不同的惩罚因子的方法，对少数类采用较大的惩罚因子，增加少数类样本的错分代价，而对多数类采用较小的惩罚因子；但是对于不同的训练数据惩罚因子确定困难。文献[7]对多数类样本采用聚类的方法，减少了多数类样本的数量，同时也减少了样本的密度。当多数类样本空间与少数类样本空间相同时，由于最后2类样本数量相等，因此样本密度也就均衡;但是如果2类样本空间大小不同则导致出现新的样本密度不均衡，其原因在于该方法只考虑样本的数量而没有考虑样本空间大小。为此，本文从样本集本身出发，结合样本数量和样本空间大小，即依据类样本密度之间的关系对多数类样本进行欠取样，从而使数据集均衡化。

2 重取样算法

2.1 样本密度

为了描述样本密度及类样本密度，本文采用欧式距离计算样本间的距离。

定义 1 样本间距离：样本x与样本y之间的距离d(x,y)为

d(x,y)=x-y。

(4)

式中：x、y为多维向量；x表示x的二阶范数，用于计算样本间的欧式距离。

在线性不可分情况下，支持向量机通过核函数将样本由输入空间映射到某一特征空间中，使得样本在该特征空间中可分，假设映射函数为φ:RkF，核函数为K(x,y)=〈φ(x),φ(y)〉，则在特征空间下2个样本间的距离为

假设核函数采用RBF，则K(x,y)=exp(-gx-y2)，g为一待定的常数，且g的值也将影响最终结果，g值一般取维数的倒数，由式(5)可得

(6)

定义2 样本密度：第i类样本集中任意样本x的样本密度D(x)定义为

D(x)=N(xij|d(x,xij)ar,j=1,2,…,ni)。

(7)

式中：N(·)是统计满足条件的样本数；xij表示第i类样本中第j个样本；ni表示第i类样本的数量；d(x,xij)表示第i类样本x与第i类样本中的第j个样本间的距离，是欧氏距离，也可以是特征空间中的距离；r表示超球的半径(阈值)。阈值的选择对样本密度的计算有很大的影响，选择过大，所有样本都被包含进去即样本密度为ni，选择过小，每个样本的密度都为1。a为控制系数，可以进一步调整阈值，使样本密度能够反映实际的样本分布。本文将对多数类样本中每个样本包含K个样本的最小超半径的平均值作为r。

定义3 类样本密度：第i类样本的类样本密度D(Ci)为

(8)

确保经聚类后各类样本密度的均衡的关键在于K-means中K值的确定。本文依据样本数量与样本密度之间的关系来确定K值，D(x)实质上就是指定半径的超球内的样本数量，D(Ci)为平均值，因此ni/D(Ci)表示ni个样本可以用多个这样的超球容纳。为使各类之间最终形成的超球数量相同，则应满足

n1/D(C1)=n2/D(C2)=…=ni/D(Ci)。

(9)

对于2类分类，假设n1表示多数类样本数量，n2表示少数类样本数量，设对多数类样本经过聚类处理后的样本数量为n，则

n/D(C1)=n2/D(C2)。

变形可得

n=D(C1)·n2/D(C2)。

(10)

2.2 重取样算法描述

基于样本密度的聚类算法具体描述如下。

输入：多数类样本集bdata，少数类样本集sbata。

输出：对多数类样本重取样的样本集bdata’，少数类样本集sdata。

Step1对于多数类样本集，计算每个样本K-近邻中相距最远的样本距离di。

Step3对于每类中的样本，利用公式(7)计算每个样本的密度D(x)，并用公式(8)计算类样本密度D(Ci)。

Step4利用公式(10)计算多数类样本聚类后的类别数。

Step5调用K-means聚类算法对多数类样本进行聚类，以聚类所得类中心为新的样本，与原有少数类样本共同构成新的训练集。

3 实验及数据分析

为验证本文算法的有效性，该节用人工数据集和UCI数据集对本文算法进行验证。实验设计思路如下：首先选择二维人工不均衡数据，可以看到分类超平面的偏移情况，并与聚类方法和不使用降维处理的SVM算法进行对比，来验证本文算法的性能；然后用不均衡的UCI数据集进行相同的验证；最后对分类器训练的时间复杂度进行分析，并比较在UCI数据集上的训练时间，对比分类时间及总体分类性能上的效果。

本文所做实验是在Matlab 7.11.0环境中结合了台湾林智仁老师的LIBSVM[17]，主机为Intel Core i7 2.3GHz，8G内存，操作系统为Win7的PC机上完成的。

3.1 性能评价

对于均衡数据的分类方法，常用分类精度作为评价指标，该评价指标基于错分代价相同，因此这个评价指标用在不均衡数据集则不合理。有学者给出了针对不均衡数据的评价指标，TP为正类样本被分为正类的数量，FP为正类样本被分为负类的数量，FN为负类样本被分为正类的样本数量，TN为负类样本被分为负类的数量[18]。假设正类为多数类，由此得少数类正确分类率为

Se=TN/(TN+FN) ，

(11)

多数类样本正确率为

Re=TP/(TP+FP)，

(12)

少数类查准率为

Pr=TN/(FP+TN)，

(13)

则Fv和Gm定义如下：

(14)

(15)

其中λ为Pr与Re的相对重要性。Fv综合考虑少数类样本的准确率和查准率，因此能够更准确地反映对少数类样本的分类性能。Gm综合考虑多数类和少数类样本的分类准确率，因此能够衡量分类器的整体分类性能。本文实验使用这2个评价指标，且取λ=1。

3.2 人工数据集

3.2.1 线性可分数据

为简化过程，本文实验数据采用人工生成方式。为观察不均衡数据对分类决策面的影响，随机产生2类均匀分布的不均衡样本，第1类样本为U([0,1]×[0,1])，第2类样本为U([1,1.4]×[0,1])，第1类样本数为300，第2类样本数为50。测试集同样采用均衡分布的人工数据，第1类样本为U([0,1.05]×[0,1])，第2类样本为U([0.95,1.35]×[0,1])，2类样本各100个样本，如图2所示。

表1中的面积比值是多数类样本分布区域与少数类样本分布区域的面积比，依据这个区域及样本数量可以粗略估计样本密度。当面积为1∶3时，经过聚类算法后密度比约为1∶3，出现新的不均衡；当面积接近1∶1时，即聚类后样本密度接近1∶1时，聚类算法效果较好；当面积比例接近样本数量比时(样本数300∶50，面积比1∶0.2)，聚类算法与本文算法都比直接支持向量机算法的效果要差。本文算法差的原因在于，本文算法只用于改变原多数类样本的密度，而没有改变少数类样本的密度。当面积为1∶0.1时，实际多数类样本密度要比少数类样本密度小，因此无法调整密度使2类样本密度接近，从而导致其结果不如直接SVM算法的结果。

从图2可以看到，传统支持向量机分类超平面会向少数类方向偏移，使得对少数类欠学习，如图(a)所示。经聚类处理[8]后，分类超平面向多数类偏移，其原因在于对原多数类样本重取样后数量与原少数类样本数量相同；但从图2(b)中可以看出，原多数类样本空间大小是少数类样本空间大小2.5倍，也就是说聚类结束后，原少数类样本密度与多数类样本密度之比为2.5，形成了新的密度不均衡，原来的多数类变为密度小的类，分类超平面向新的少数类偏移。图2(c)是本文算法处理后的结果，可以看到分类超平面能很好地分离2个类。

由于上面数据集是随机生成的，具有一定的偶然性，因此实验给出5次测试结果和平均值。表2给出了5次随机数据的实验结果，其中训练集第1类样本为U([0,1]×[0,1])，第2类样本为U([1,1.4]×[0,1])，第1类样本数为300，第2类样本数为50，核函数采用径向基核函数。

从表2可以看到，在2个类样本空间不同的情况下，本文算法的性能比聚类算法和直接SVM算法要好。对比图2可以看出，本文算法的分类超平面能更准确地把2个类区分开。

3.2.2 线性不可分数据集

从表3可以看到，5次实验结果中本文算法都优于聚类算法和直接SVM算法。对比图3，也可以看到本文算法的分类超平面既不向多数类偏移，也不向少数类偏移，能更准确区分2类样本，因此有较高的分类准确率。

3.3 UCI数据集

本实验数据集选取contraceptive method choice(Cmc)、haberman′s survival、ionosphere、letter recognition和pima indians diabetes 5组UCI数据，这5组实验数据属性都为实数，并且类样本间有不同程度的不均衡性。本实验中多数类样本为正类，少数类样本为负类。表4给出了各组实验数据集中属性、样本数量等特点。数据集Cmc和letter是多类数据集，该实验把其转换为2类数据。数据集Cmc把B类作为少数类，其他R和L类作为多数类；数据集letter把A类作为少数类，其他B-Z类作为多数类。

表5给出了在数据集contraceptive method choice(Cmc)、haberman’s survival、ionosphere、letter recognition和pima上的实验结果。由于聚类算法初始K个样本是随机选择的，具有一定的随机性，因此表5中的数据均为进行5次实验后，取的最优结果。从表5中可以看到，本文算法比采用聚类算法的结果要优，另外，最终对多数类样本进行欠取样的结果也是相等的。

3.4 K值对算法的影响

本文算法需要计算每个样本的K-近邻，利用包含K个近邻样本的最小距离的平均值作为阈值计算每个样本的密度，然后再用每个样本密度的平均值作为类密度；因此K值对计算最终的类密度有很大的影响。如果K=1，则每个样本的密度都为1，类的密度必定相同，若K值过大，则把整个类的样本都包含进去，类的样本密度仍然相等；因此K值决定样本的缩减规模和增加规模。为了更直观地看到K值的影响，该节选用3.2.1节中的数据集进行分析，其不同K值对应的结果如表6所示。由表6可以看出，随着K值的变化，分类性能在不断波动，随着K值的增加，对多数类样本进行重取样的数目就比较少，准确率在不断的波动，但整体是降低的。

4 结论

由于实际应用中训练样本不均衡的问题主要表现为样本密度分布不均衡，因此，本文结合聚类算法和K-近邻算法，提出一种基于样本密度的不均衡数据分类算法。该算法利用类样本密度之间的关系确定最终多数类样本数量，然后用聚类对多数类样本进行欠取样。该方法进行重取样后能够保持2类样本密度的均衡化，使得分类超平面不向任何一方偏移。最后用人工数据集和UCI数据集验证该方法的有效性。通过与聚类算法和直接SVM算法进行比较的结果表明：在不同的数据集及不同的不均衡化程度下，该方法有较好的实验效果；然而如果少数类样本数量很少，且样本密度与多数类样本密度相差不大的时候分类性能仍然会下降。如何对这样的少数类样本进行过取样将是下阶段的主要工作。

[1]李雄飞,李军,董元方，等.一种新的不平衡数据学习算法PCBoost[J]. 计算机学报，2012, 35(2):202-209.

[2]曾志强,吴群,廖备水.一种基于核SMOTE的非平衡数据集分类方法[J].电子学报，2009,37(11):2489-2495.

[3]CHEN B, MA L, HU J. An Improved Multi-label Classification Method Based on SVM with Delicate Decision Boundary [J]. International Journal of Innovative Computing, Information and Control, 2010, 6(4):1605-1614.

[4]楼晓俊,孙雨轩,刘海涛.聚类边界过采样不平衡数据分类方法[J]. 浙江大学学报:工学版,2013,47(6):944-950.

[5]林舒杨,李翠华,江弋,等.不平衡数据的降维采用方法研究[J].计算机研究与发展,2011,48(增刊3):47-53.

[6]陶新民,郝思媛,张冬雪.核聚类集成失衡数据SVM算法[J].哈尔滨工程大学学报,2013，34(3):381-388.

[7]陈思,郭躬德,陈黎飞.基于聚类融合的不平衡数据分类方法[J].模式识别与人工智能, 2010,23(6):772-780.

[8]陶新民,张冬梅,郝思媛,等.基于谱聚类欠取样的不均衡数据SVM算法[J].控制与决策,2012,27(12): 1761-1768.

[9]杨智明,彭宇,彭喜元.基于支持向量机的不平衡数据集分类方法研究[J].仪器仪表学报,2009, 30(5):1094-1099.

[10]陶新民,童智靖,刘玉.基于ODR和BSMOTE结合的不均衡数据SVM分类算法[J].控制与决策,2011,26(10):1535-1541.

[11]曹鹏,李博,栗伟,等.基于概率分布估计的混合采样算法[J].控制与决策,2014,29(5):815-820.

[12]夏战国,夏士雄,蔡世玉,等.类不均衡的半监督高斯过程分类算法[J].通信学报,2013,34(5):42-51.

[13]蔡艳艳,宋晓东.针对非平衡数据分类的新型模糊SVM模型[J].西安电子科技大学学报:自然科学版,2015,42(5):140-145.

[14]SUN Y M, KAMEL M S, ANDREW W, et al. Cost-sensitiveBoosting for Classification of Imbalanced Data[J]. Pattern Recognition, 2007,40(12):3358-3378.

[15]XIAO J, XIE L, HE C Z, et al.Dynamic Classifier Ensemble Model for Customer Classification with Imbalanced Class Distribution[J]. Expert Systems with Applications, 2012,39(3):3668-3675.

[16]WANG S J,XI L F. ConditionMonitoring System Design with One-class and Imbalanced Data Classifier[C]//Proceedings of the 16thInternational Conference on Industrial Engineering and Engineering Management(IE&EM’09).Beijing:IEEE,2009:779-783.

[17]CHANG C C, LIN C J. LIBSVM: a Library for Support Vector Machines[EB/OL].[2014-10-15]. http://www.csie.ntu.tw/～cjlin/libsvm.

[18]SUC T,CHEN L S. Knowledge Acquisition through Information Granulation for Imbalanced Data [J]. Expert Systems with Applications, 2006,31(3):531-541.

(编校：饶莉)

A Classification Algorithm for Imbalanced Dataset of Sample Density

DU Hong-le, ZAHGN Yan

(SchoolofMathematicsandComputerApplication,ShangluoUniversity,Shangluo726000China)

In order to resolve the classifiers’ over fitting phenomenon to enhance classification performance, a new algorithm based on sample density is proposed for imbalanced data classification. Firstly, it computes the density of samples and the density of every class. Then it works out the number of class with cluster algorithm according to the relation of sample density of every class. Then it clusters the samples of majority class usingK-means algorithm with above class number. The cluster centers are treated as the new samples and then a new training dataset is constructed with the new samples and minority dataset. According to the new training dataset, we can get the decision function. The method may resolve the problem of imbalanced dataset and improve the classification performance of SVM. Results of experiments with artificial dataset and six groups of UCI dataset show that the algorithm is effective for imbalanced dataset, especially for the minority class samples.

support vector machine; imbalanced dataset; sample density; under-sampling;K-nearest neighbor

2015-01-18

陕西省自然科学基金项目(2014JM2-6122)；陕西省教育厅科技计划项目(12JK0748)；商洛学院科学与技术研究项目(13sky024)。

杜红乐(1979—)，男，硕士，讲师，主要研究方向为网络安全、机器学习。

TP181

A

1673-159X(2015)05-0016-08

10.3969/j.issn.1673-159X.2015.05.003