一种不平衡数据的分类方法

李艳玲，郭文普，徐东辉

(第二炮兵工程大学，西安 710025)

0 引 言

分类的基本过程是首先将一些具有类别标记的样本作为训练数据，通过学习算法获得分类器，然后根据分类器判定待分类样本的类别。因此，训练数据的质量直接影响学习算法获得的分类器性能。基于机器学习的分类方法要求训练数据比较完整及数据分布相对均匀等，当样本分布出现不平衡时，分类性能会降低［1～3］。然而，最近的一些研究认为［1～5］，许多情况下，样本分布存在偏斜问题，尤其在两类分类中，不平衡问题更为多见。因此，对类别分布不平衡数据的学习已成为机器学习目前面临的一个挑战。目前对数据不平衡问题的解决方法主要集中在三个层次:一是数据集;二是分类方法;三是评估方法的优化。对于数据集，目前主要通过重取样，来构造分布均衡的训练数据集。对于分类方法则从采用新的分类策略、改进特征选择方法和权重润饰等角度进行改进。对于评估方法，如何根据评估结果来优化分类模型成为研究热点。但目前所有的方法都还不能对小类别的识别水平整体提高到实际可以接受的程度，相关的研究仍需进一步深入［4］。

已有的研究表明，将数据重取样与基于分类算法的改进二者结合起来的组合方法，效果要优于单纯使用一种类型的方法［6］，但目前对组合方法的研究较少。以两类文本分类为背景，从数据重取样与特征权重润饰结合的角度考虑，提出一种基于组合的不平衡数据分类方法，通过相关实验，验证了该方法可有效提高不平衡数据分类精度。

1 数据不平衡问题

训练数据的不平衡通常是指某些类拥有较多的样本，而某些类只有相对较少或很少的样本［1］。在这种情况下，标准的分类器会倾向于过分适应大类而忽略小类。在数据挖掘或机器学习的许多应用领域中，数据不平衡问题是普遍存在的［7］。比如，在舆论监控、信息安全监管、入侵检测、医疗诊断、风险管理及文本分类等应用中，都会遭遇数据不平衡的问题。目前常用的一些分类算法，例如决策树、支持向量机(SVM)、KNN、神经网络、Bayesian network、及关联规则挖掘等方法，当处理不平衡数据时，都表现出不适应［8～10］。文献［8］基于SVM，从理论和实验两个角度，验证了类分布对传统分类算法的影响，即算法对小类的分类和预测差于对大类的分类和预测。然而值得注意的是，实际应用中，通常对于小类别正确分类的要求更高。例如，在不良信息过滤中，不良信息数量远远小于正常的信息，而过滤的目标就是要识别出不良信息，将它们过滤。基于这些原因，数据不平衡在数据挖掘和机器学习领域是急需解决的问题。

1.1 数据的不平衡性

通常认为，数据的不平衡性主要体现在类别之间样本数量的差异。据统计，在实际应用中，小类和大类的样本数之比可以是1 ∶100、1 ∶1000，甚至是1 ∶10000。已有许多研究表明，如此大的样本数量差异会导致分类性能的降低。那么，当各类别样本数量大致相当时，是否还会存在类别不平衡性呢?文献［11，12］分别从理论和实验两个方面研究并验证了数据偏斜不是影响分类性能的唯一因素，小类别样本的规模大小、样本的独立性及类别中存在的子类等都会影响分类的性能。也就是说，数据的不平衡性不仅仅是表现在各类样本数量的差异上，也包括类别规模、子类和类别交迭等。

(1)数据分布的不平衡

数据分布的不平衡或者说数据偏斜主要指类别间样本数量的不同。已有的研究在进行数据不平衡对分类的影响分析时，多数集中在这个原因的研究上，一般用大类和小类的样本数量之比来表示类别分布的不平衡程度，大量的研究结果表明，现有的分类模型在类别分布均衡时能达到较好的分类效果，而当数据分布不均衡时，都会不同程度的受到影响。但是，类别分布不平衡的程度对分类的影响目前还没有明确的结论。文献［11］的研究结果显示，在某些应用中，当小类与大类样本数量的比率达1 ∶35时，才会影响分类效果，而在另一些应用中，比率为1 ∶10 时，已经明显影响了分类效果。

(2)类别的规模

类别的规模就是指类别中样本的数量。Yanmin Sun 等人认为［7］，当类别不平衡的程度一定时，类别的规模就成为影响分类效果的主要因素了。主要原因是类别的规模受到限制时，分类规则不能覆盖小类别中固有的一些性质，因而是不可靠的。G.E.A.P.A.Batista［9］等人通过实验观察指出:随着类别规模的增长，由类别分布不平衡所造成的错误分类将减少;若有足够的数据集，并且假定学习时间可接受的话，类别分布不平衡将不再是分类的障碍。

(3)类别的交迭

类别的交迭就是指类别概念间有相互重合的部分。文献［13］通过实验得到结论:类别分布不平衡本身不是个问题，当类别间交迭较多时，类别分布不均才会降低小类别的正确分类率。文献［9］也得到了类似的结论:线性分类模型对类别分布不均并不敏感，但是随着类别交迭程度的增加，分类系统对类别分布不平衡的敏感度也会增加。

(4)子类问题

在许多实际的分类问题中，某个类别中可能会存在几个子类的现象。通常，子类的样本数量也常常不一样，这就构成了类别中的不平衡问题。另外，子类间的区别一般不明显，也就是会存在类别交迭。文献［7］认为，以上原因会增加分类模型训练的复杂度。

1.2 对数据不平衡问题的解决策略

Yanmin Sun 等人总结了目前对不平衡数据问题研究的三个方面:(1)类别不平衡问题的本质研究，例如在什么领域中，数据不平衡最影响标准分类器的性能?(2)对不平衡数据问题的解决方法。(3)在面临不平衡数据时，对分类性能合适的评估方法。在三个研究方面中，多数的研究集中于第(2)、(3)个方面，提出的解决方法可归纳为三种策略。

(1)训练集重构

训练集重构的主要思路是通过某种方法重新构造训练集，使其达到类别平衡。目前主要是通过重取样方法，来构造类别分布均衡的训练数据集。重取样的方法有多种，在不同的重取样方法中主要体现了两种思路［1］:对小类别进行向上取样;对大类别进行向下取样。向上取样指通过增加小类别的样本，来平衡大类别与小类别的样本数量，降低分类器对大类别的偏好;而向下取样则是通过减少大类别的样本数量，来达到类别分布平衡。向上或向下取样时，既有随机方式也有选择方式，还有上述方法的组合方式。不管是哪种重取样方法，其追求的目标都是要达到各类别的样本数量的大致相当。虽然重取样方法在不平衡数据集的分类中经常使用，而且被证实是比较有效的方法，但也还存在一些明显的缺陷，例如，当类别间分布很不均衡时，向上取样增加小类别的样本数较大，这会增加训练时间，还可能会造成过适应性;但当小类别样本数量过少时，一味的删除大类别中的样本，也可能会删除对分类有重要贡献的样本，损失不少信息，降低分类性能。另外，重取样方法显然着重考虑的是样本数量的差异，因而对于类别规模、类别交迭和子类问题等影响分类性能的因素，重取样方法是不能很好解决的。

(2)分类方法的改进

一般地，凡是不是对训练集本身进行重构的方法，都可归为分类方法的改进，其主要思路是通过调整分类策略，使训练算法对小类别重视起来。由于各种分类方法其分类原理有所不同，在面对不平衡数据时，其表现也会有所不同，因此，相应的改进策略也有多种。

①改进或优化特征选择方法

一般的学习算法处理的基本对象就是特征，因此，特征的选取对分类精度有重要的影响。文献［14 ～16］通过改进或优化特征选择方法，获得分类器对小类别的特征重视，从而提高分类精度。

②权重润饰

权重润饰的主要思想是通过引入权系数，调整样本的权重或者特征的权重，获得分类器对小样本的重视，从而寻求达到类别的平衡状态，提高分类精度。样本权重的调整有多种方法，例如，针对SVM相对于不平衡数据，分类性能下降的问题，Veropoulos 在文献［17］中提出了对两个类别施加不同的惩罚系数的方法，较好地降低了样本分布不均对整体分类性能的影响。陈晓云等提出的基于规则权重调整的关联规则文本分类算法，使得分类质量显著提高［18］。

③基于一类的分类

基于一类的分类方法，一般将目标类样本定义为正例，而将其他样本统统定义为反例，其主要思路是仅基于正例样本来训练分类模型，这类方法不是试图在特征空间中，划分正例和反例样本的界限，而是努力划清目标类的边界。对于待分类样本，通常度量其与目标类的相似性，当相似度超过一定阈值时，则认为其属于目标类。神经网络、SVM 方法可以采用基于单类的学习，而决策树、Bayes、关联规则分类方法则不适宜用单类分类方法［7］。

④基于集成学习的分类

集成学习，也称为多重学习或分类器组合，主要通过决策优化(Dicision Optimization)或覆盖优化(Coverage Optimization)两种手段将若干弱分类器的能力进行综合，以优化分类系统的总体性能［4］。Yanmin Sun 等人［7］，通过为不同类设置不同的错误代价，提出了三种改进的AdaBoost 算法，获得了对不平衡数据较好的分类效果。

(3)优化评估方法

常用的评估方法，例如查准率、查全率和F1测试值，在面对不平衡数据时不能做出准确的评估［19，20］。于是，如何准确的评估分类器的分类效果，以及如何依据评估结果来优化分类模型，成为一个研究热点。但是，数据不平衡会对分类模型产生影响，所以只从公平的评估角度考虑改进评估方法本身意义不大，应着重考虑对分类模型的改进。目前的研究，主要集中在第二个侧面，即结合评估结果来优化分类模型，例如，基于错误代价的分类方法［21］，其基本思想是采用某种评估方法计算出上一轮分类的错误代价，从而调整权重或者说惩罚系数、阈值等，从而使分类器对小类别重视起来。可见，评估方法对于错误代价的计算有重要的影响，而错误代价常被引用到分类模型中，以修正模型参数等。

2 基于组合的分类方法基本思路

综上所述，各种数据不平衡问题的解决策略实际上是从不同角度改进分类模型，降低分类器对大类别的偏好，究竟哪种方法好，并没有公认的结论，但从相关文献的研究结果不难看出，数据集本身的特点及所用分类方法的原理是应首要考虑的两个因素。

采用文献［22］提出的基于类别空间模型的分类方法，其基本思想是基于词的类别权重为待分类文本打分，根据文本相对于每个类别的分值大小，将文本归入到分值高的一类。其中，第i 个词对第j 个类别的权重Wij为

Ni，j是第i 个特征词在j 类文本中出现的文本数，Nti是整个训练文本集中出现特征词ti的文本数，fij是第i 个词语在第j 类出现的频率。一篇待分类文档相对于每一类别分值的计算公式如式(2)

式中，j 是类别编号;T 是总特征词数;Scorej就是该文档相对于类别j 的分值。

特征选择与词的类别权重计算是影响该分类方法的两个关键因素，而特征选择与类别权重计算都是基于词频、词的文本频和词的分布等统计特征，这些统计特征显然会直接受到数据分布的平衡与否的影响。考虑到数据重取样能很好地解决数据分布的不平衡问题，但不能有效解决类别规模、类别交迭和子类等问题，因此，提出了基于组合的不平衡数据分类方法，其基本思路如下。

第一，采取合适的数据重取样方法构造分布大致均衡的训练集;

第二，采用权重润饰方法弥补数据重取样不能很好解决类别规模、类别交迭和子类等问题。

随机取样是目前常用的数据重取样方法，但相关文献的研究表明:随机向上取样不仅会增加训练时间，而且可能造成分类器的过适应问题;而随机向下取样可能造成信息损失。哪种取样方法更好，目前并没有统一的结论，这与实验所用的数据及分类方法有关。鉴于此，在后续的实验中，分别采用了随机向上、随机向下，以及随机向上与随机向下取样组合三种方式。

权重润饰的关键是计算出合适的加权系数，从现有的研究看，加权系数的计算一般有两类方法:一是根据数据集的分布情况计算，称为预先计算;另一种则是根据分类结果的反馈信息计算。基于以往的研究发现，预先计算中有许多不确定性，因此，下面所用加权系数计算方法，其基本思路是根据上一轮分类结果的反馈信息来计算加权系数，通过几轮迭代，达到较高的分类精度。加权系数的计算为［23］

式中，N1、N2分别是C1 和C2 类的训练文本数;R1(k)、R2(k)分别是第i 轮分类后C1 和C2 类中被正确分类的文本数;Ej(k)是j 类中错分为其他类的文本数。

3 基于组合的分类算法主要步骤

基于上述的组合分类方法的基本思路，本文提出的基于组合的不平衡数据分类算法主要步骤是

①训练文本预处理。

②特征提取［22］，得到一个总的特征词表。

③按式(1)计算每个词对各类别的类别权重Wij。

④将待分类的文档进行分词等预处理。

⑤按式(2)计算待分类文档的类别权值Scorej。

⑥比较Scorej的值，若Scorek为最大值，则输出该文档为类别k。

⑦根据分类结果判断:若达到满意的分类正确率或最大迭代次数(预先设定的)，则算法结束;否则，按式(4)计算第k+1 轮加权系数，则得特征词第k +1 轮的类别权重如式(5)，返回⑤。

4 实验及结果分析

4.1 实验数据集

所用数据集是从网上下载的关于讨论“房价”的帖子，根据帖子所表达的观点将其分成两类:C1、C2，经整理得到初始数据集见表1。

表1 初始数据集

从表1 可得该数据集有两个明显特点:(1)两类文本数相差悬殊，C1 类与C2 类文本数比值约为6.46 ∶1，即数据分布明显不平衡;(2)初始训练集总词数为8986 个，其中C1 类有8854 个，C2 类有1033 个，两类相同的词有901 个，占C2 类的87.22%，即类别交迭较多。

4.2 分类性能测试指标

实验中，测试指标采用常用的查准率(P)、查全率(R)，F1测试值。对于全局的分类结果，采用宏平均方式，即Macro-P、Macro-R 和Macro-F1［23］。

4.3 相关实验和分析

(1)实验1

首先基于数据重取样方法来构造分布均衡的训练集:第1 组，对大类别C1 随机向下取样，C1、C2 各111 篇;第2 组，对小类别采用随机复制的方法进行向上取样，C1、C2 各718 篇;第3 组，采用组合取样，即对大类别随机向下取样，对小类别随机向上取样，C1、C2 各360 篇。此外，为了比较重取样方法对分类精度提高的效果，第4 组实验基于分布不平衡的初始训练集。实验中，为了克服结果的随机性，每组实验都做了三、四次，结果取几次实验的平均值。基于构造的均衡训练集的分类结果与基于初始分布不平衡数据集的结果对比如图1 所示。

图1 基于重取样方法的分类结果

①由图1 可见，不管哪种重取样方法，都明显地提高了分类精度，表明重取样方法较好地解决了类别间样本数量差异对分类的影响。

②第3 组，即组合取样的分类精度最高，第2组，即单纯对小类别采取随机复制向上取样，分类效果最差。但不管哪种重取样方法，当两类文本数量大致相当时，分类精度不再提高。以随机向上取样为例，做了五次实验，每次随机复制的样本数不同，分别是222、360、700、718、730，分类结果如图2 所示。由图2 可见，随机复制小类别样本，对分类精度的提高有一定的效果，但当小类别样本数量增加到一定程度时，分类精度不再提高。这表明重取样方法着力解决的是样本数量差异对分类的影响，当类别间样本数量大致相当时，重取样方法对类别间数据其他的不平衡性没有明显作用。

图2 基于随机向上取样方法的分类结果

③对比两类的分类效果发现仍有较大的差别，如图3 所示，C1 类的查全率普遍高于C2 类的，说明分类器仍偏好大类别C1。分析其原因发现，由于C1 类的文本长度普遍大于C2 类的，因而经过特征选择后，两类的特征词数仍然相差悬殊;此外，类别间相同词语较多，即类别交迭较多，见表2。可见，虽然此时两类的文本分布大致均衡，但仍存在特征词数的差异、类别交迭等其他不平衡问题，因此按照所采用的分类方法，建立的分类器仍然偏好于大类别C1。

图3 两类分类结果对比

表2 两类特征词数对比

④综合②与③中的分析结果，表明数据重取样方法能很好地解决样本数量分布不均的问题，但对文本长度差异造成的特征词数的差异、类别交迭等其他不平衡问题，不能有效解决，应考虑结合其他方法解决类别交迭等不平衡问题。

(2)实验2

基于重取样和权重润饰组合的分类结果如图4所示，组合后的分类效果优于单纯使用重取样的效果，两类分类结果对比情况如图5 所示，此时两类的分类效果大致相当，即分类器不再偏好大类别。可见，权重润饰较好的弥补了重取样方法对特征词数差异、类别交迭等问题不能有效解决的不足。

5 结 语

对数据挖掘与机器学习领域中常遇到的数据不平衡问题进行了研究，在对数据不平衡性及目前解决策略的分析基础上，提出了将数据重取样与权重润饰组合的分类方法，以降低分类模型对大类别的偏重，由相关实验的结果可见，权重润饰能较好地弥补重取样方法对类别交迭等问题处理不理想的不足，组合方法有效地提高了不平衡数据的分类精度。

［1］CHAWLA N V，JAPKOWICZ N，KOTCZ A. Editorial:Special Issue on Learning from Imbalanced Data Sets［J］.Sigkdd Explorations Newsletters，2004，6(1):1-6.

［2］叶志飞，文益民，吕宝粮. 不平衡分类问题研究综述［J］.智能系统学报，2009，4(2):148-156.

［3］林智勇，郝志峰，杨晓伟.不平衡数据分类的研究现状［J］.计算机应用研究，2008，25(2):332-336.

［4］苏金树，张博锋，徐昕.基于机器学习的文本分类技术研究进展［J］.软件学报，2006，17(9):1848-1859.

［5］SEBASTIANI F.Machine Learning in Automated Text Categorization［J］.ACM Computing Surveys，2002，34(1):1-47.

［6］王和勇，樊泓坤，姚正安，等. 不平衡数据集的分类研究［J］.计算机应用研究，2008，25(5):1301-1304.

［7］YANMIN SUN，MOHAMED S，KAMEL，et al.Cost-Sensitive Boosting for Classification of Imbalanced Data［J］.Pattern Recognition，2007(40):3358-3378.

［8］郑恩辉，许宏，李平，等.基于v-SVM 的不平衡数据挖掘研究［J］. 浙江大学学报:工学版，2006，40(10):1682-1687.

［9］BATISTA G E A P A，PRATI R C，MONARD M C. A Study of the Behavior of Several Methods for Balancing Machine Learning Training Data［J］. SIGKDD Explorations Special Issue on Learning from Imbalanced Datasets，2004，6(1):20-29.

［10］RASKUTTI B，KOWALCZYK A.Extreme Rebalancing for SVMs:A Case Study［C］//Proceedings of European Conference on Machine learning，Pisa，Italy，2004:60-69.

［11］ JOSHI M V. Learning Classifier Models for Predicting Rare Phenomena［D］. Twin Cites，MN，USA:University of Minnesota，2002.

［12］LI YANLING，SUN GUOSHE，ZHU YEHANG. Data Imbalance Problem in Text Classification［C］//Third International Symposium on Information Processing，QingDao，2010:301-305.

［13］PRATI R C，BATISTA G E A P A.Class Imbalances Versus Class Overlapping:An Analysis of a Learning System Behavior［C］//In Proceedings of the Mexican International Conference on Artificial Intelligence(MICAI)，Mexico CityMexico，2004:312-321.

［14］ FORMAN G. An Extensive Empirical Study of Feature Selection Metrics for Text Classification［J］. Journal of Machine Learning Research，2003，3(1):1533-7928.

［15］M DOLORES DEL CASTILLO，SERRANO J I. A Multistrategy Approach for Digital Text Categorization from Imbalanced Documents［J］. SIGKDD.Explorations Newsletter，2004，6(1):70-79.

［16］ZHENG Z，WU X，SRIHARI R.Feature Selection for Text Categorization on Imbalanced Data［J］.SIGKDD Explorations，2004，6(1):80-89.

［17］VEROPOULOS K，CAMBELL C，CRISRIANINI N.Controlling the Sensitivity of Support Vector Machine［C］//Proceedings of the International Joint Conference on AI，1999:55-60.

［18］陈晓云，胡运发. 规则加权的文本关联分类［J］.中文信息学报，2005，19(4):52-59.

［19］ WEISS G. Mining with Rarity:A Unifying Framework［J］.SIGKDD Explorations Special Issue on Learning from Imbalanced Datasets，2004，6(1):7-19.

［20］ HAPKOWICZ N. Concept-Learning in the Presence of Between-Class and Within-Class Imbalances［C］//In Proceedings of the fourteenth Conference of the Canadian Society for Computational Studies of Intelligence，Ottawa，Canada，2001:67-77.

［21］LIN Y，LEE Y，WAHBA G. Support Vector Machines for Classification in Nonstandard Situations［J］.March.Learn，2002，46:191-202.

［22］李艳玲，戴冠中，朱烨行.基于类别空间模型的文本倾向性分类方法［J］.计算机应用，2007，27(9):2194-2196.

［23］李艳玲，戴冠中，余梅. 基于反馈信息的特征权重调整方法［J］.计算机工程，2009，35(2):206-208.