Cost-sensitive分类算法

Cost-sensitive分类算法——综述与实验秦逸(南京大学计算机科学与技术系,南京210093)Cost-sensitiveclassification:surveyandexperimentsQinYi*(DepartmentofComputerScienceandTechnology,NanjingUniversity,Nanjing210093,China)Abstract:Cost-sensitiveclassificationisahotspotinmachinelearning.Cost-sensitiveclassificationaimstogetaminimalcostclassifyresultonaclassunbalancedataset.Duetoitspotentialapplicationoriental,machinelearningcommunitypayslotsattentiononthisproblem.Thispapergivesabriefintroductionofcost-sensitiveclassification.Wereviewthestateoftheart,dividingmajorworksintotwocategories:rescalingandreweighted,accordingtotheirmethodology.Aftergivingthemainideasandprocessesofsixinfluentialcost-sensitiveclassificationalgorithms,weshowourexperimentresultofthesealgorithmsonthreedatasets.Wealsopresentsomeanalysisofourexperimentresults,notifyingsomefactorsthatmayaffectalgorithms’performance.Keywords:machinelearning;classification;cost-sensitive;survey;categorytheory摘要:Cost-sensitive分类是近年来机器学习的热点问题之一。Cost-sensitive分类面向的是类型比例不平衡的数据集上的分类问题，其主要目的是使分类器的分类结果对应的cost值最低。由于cost-sensitive在实际问题中有着比较大的应用潜力，众多机器学习研究者提出了各种解决cost-sensitive分类问题的算法。本文简介了cost-sensitive分类问题的定义和研究动机。根据实现cost-sensitive分类的具体技术手段，我们将现有方法分为了两大类，rescaling和reweighted。在简述6种具体的cost-sensitive分类算法的主要思想和过程之后，我们给出了不同算法在3个实验数据集上的实验结果，并分析了可能影响算法性能的一些原因关键词:机器学习;分类器;cost-sensitive;综述中图法分类号:TP301文献标识码:A1简介机器学习研究者的一个重要任务是以面向算法研究的原型系统为基础，设计并实现出可用的实际系统。不幸的是，许多在算法层面性能十分优异的数据挖掘或机器学习原型系统并不能很好地完成这一步骤。造成这一现象的原因在于现实可用的机器学习系统受到比原型系统更多的内外部因素的影响。在现阶段，我们对于这些影响机器学习系统的外部因素的研究程度还处远远不及我们对于算法本身的研究程度。有一些工作已经开始关注如何完成从算法到实际系统的转换。总的来说，这些研究者希望在考察外部因素的基础上，对机器学习算法的结果给出额外的评价指标，从而使得算法能够被应用于实际应用的系统中去。Cost-sensitive的分类算法就是这样的一类方法。这类方法通过引入现实世界中实际存在的不同误判结果间代价的不平衡性，秦逸，南京大学硕博连读研究生，研究兴趣包括软件方法学，分布式算法等:2使得原有的机器学习算法能够在一定程度上适应现实世界应用的需要。本文简述了cost-sensitive分类问题的定义和研究动机。在介绍了本领域的研究现状之后，本文简述6种具体的cost-sensitive分类算法的主要思想和过程。随后我们给出了不同算法在3个实验数据集上的实验结果，并分析了一些可能影响算法性能的原因1.1Cost-sensitive分类的研究动机一般来说，机器学习领域的分类算法所关注的仅仅是如何得到最高的正确率。而cost-sensitive分类的主要目标是使得分类结果的cost值最小。以2-class分类为例，我们可以使用一个二维矩阵来描述分类算法的预测结果，如Figure1所示。predictnegativeFP(falsepositive)TN(truenegative)predictpositiveTP(truepositive)FN(falsenegative)actualpositiveactualnegativeFigure1分类算法预测结果predictnegativec01c00predictpositivec11c10actualpositiveactualnegativeFigure2银行借贷问题的costmatrix表中的列表示实际数据所属类别，行表示分类算法的预测类别。算法的预测错误的即是FP和FN两部分所表示。可以看到，传统意义下的分类算法所关心的是如何使得FP+FN的值尽可能的小，从而获得较高的分类准确率。对于FP、FN两部分各自在错误实例中所占的比例，传统分类问题并没有加以任何的考虑和限制。传统分类问题实际上是建立在下述假设的基础之上的，即分类算法做出FN判断和做出FP判断对于实际结果的影响因子是完全相同的。所以我们可以不对两种误判所占的比例加以约束。然而在现实世界中，这一假设往往是并不成立的。一个被广为接受的上述假设的反例就是银行借贷问题。通常情况下，银行会通过一些机器学习算法去判断是否应该接受贷款申请人的贷款申请。显然，这是一个2-class的分类问题。从机器挖掘算法的角度考虑，算法的分类结果应该是的错误分类率降到最低（a）。而在实际应用中，算法的分类结果应该保证分类结果给银行造成的损失较小（b）。在所有错误给银行造成的代价都相等的前提假设下，（a）和（b）显而易见是相等的。但是在实际情况中，银行做出FP判断，即没有将贷款贷给符合条件的申请人，所造成的损失无疑是要远小于其做出FN判断，即将贷款贷给不符合条件的申请人所造成的损失的。如果我们用Figure2来描述银行做出不同决定所造成的不同的代价的话，那么分类算法导致的实际损失等于|FP|∗c10+|FN|∗c01。假设现在有两个分类已训练好的算法A和B，对于10个贷款申请人进行分类。我们令c10=1，c01=10。若A/B算法的分类结果为Figure3。虽然A算法的分类正确性要优于B算法（80%60%）,但是从银行损失的角度来看，A算法的性能却不如B算法（204）。相同的例子还会出现在危险行为识别，恶性疾病诊断等诸多分类算法的应用问题上。这就要求我们的分类算法不仅仅能够较为准确地对数据集进行分类，还要能够尽可能的控制由分类错误造成的损失。这就是cost-sensitive分类算法所研究的问题。Figure3A/B算法对于银行借贷问题分类结果算法B0451算法A2035FNFPTNTP1.2Cost-sensitive中cost的定义与表示Cost-sensitive分类实际研究的是在具有不同cost值的数据集上的分类问题。由于这类问题需要在既有的数据集上添加了cost信息，因此我们要给出cost的定义和具体描述方法。通常情况下，我们使用costmatrix描述待分类数据集上的cost信息。CostmatrixC是一个N×N的矩阵，其中N代表待分类数据集中的类别的数量。C中的条目c(i,j)表示分类算法将实际属于j类得到实例分为i类所造成的cost。易见当i=j时代表分3类算法正确预测了实例的类别，而i≠j的条目对应于不正确的分类结果。利用costmatrix，我们就可以通过为其中的每一项赋值来定义待分类数据集上的cost。一般情况下，需要进行cost-sensitive分类的数据集会提供一个costmatrix供分类算法使用。由于现实世界中的cost信息很难准确获取，同时又不可能保证其在不同实例间的平均分布，因此costmatrix往往是由数据集提供者通过自己的经验给出c(i,j)的值。在对c(i,j)进行赋值的过程中，一般会遵循合理性原则[1]。该原则是在建立下述判断的基础上，即错误分类的造成的cost肯定要大于正确分类造成的cost。因此我们要求对c(i,j)的赋值应该满足c10c00andc01c11。Cost的实际意义是分类算法的分类结果相对于真实分类给被分类数据造成的影响。可以看出，这种影响可以是负面的损失，也可以使正面的收益。在考虑损失的情况下，我们认为只有错误的分类结果会造成损失。也就是说在costmatrix中的c(i,j)=0,wheni=j,而对于其他c的值，即错误的分类结果对应的条目c(i,j)，我们赋其值为正数，用于表示其代价。同时我们应该保证cFNcFP，即做出FN判断的代价要高于做出FP的代价。在考虑收益的情况下，正确的分类结果会给使用者带来一定的收益。所以我们一般将c(i,j)wheni=j，的值赋为正值，而将其他的条目，即错误的判断的cost条目赋值为负值。1.3Cost-sensitive分类的目标利用costmatrix，我们可以将cost-sensitive分类问题转化一个优化问题，即对于分类算法A，为实例x寻找到一个类别i，使得(1)中的L(x,i)达到最小值：L(x,i)=∑P(j|x)c(i,j)j(1)其中x是一个实例，(x,i)表示将其分为i类，P(j|x)表示在算法A中获得的x属于类别j的概率。对于每个类别i,L(x,i)都是x所有可能的类别的cost值的概率和。这样的目标使得我们不再关注如何获得P(j|x)的最大值，而是要关注何种分类能够最小化分类结果对应的cost值。这就使得cost-sensitive分类算法在追寻cost最优的前提下，可能会放弃可能性最大的分类结果。这种判断虽然有一定的反直觉成分，但是在1.1中所列举的实际应用中却有比较重要的现实意义。在2-class分类中，从(1)中可以知道，cost-sensitive分类算法将实例x分为1类的条件是当且仅当将x分为1类所造成的预期cost要不大于将x分为0类的损失。即P(j=0|x)c10+P(j=1|x)c11≤P(j=0|x)c00+P(j=1|x)c01我们令p=P(j=1|x)可以得到1(p)c10+pc11≤(1−p)c00+pc01(2)(2)即我们在2-class分类中所需要考虑具体问题。当式子取等号时，也就是说分类算法使得class1和class0的分类结果达到平衡时，即为我们需要的最优分类决定。2Cost-sensitive分类算法的研究现状机器学习研究者通常根据问题的难易程度，将cost-sensitive分类算法分为2-class分类和multi-class分类两个大类[15]。由于我们获得的实验数据中没有包含multi-class的数据集，所以本文没有从这一角度入手对现有工作进行分类。注意到已有工作中提出的cost-sensitive分类算法基本上都是从非cost-sensitive分类算法出发加以转换得到的，我们希望能够从转化采用的手段出发对cost-sensitive分类算法的研究现状进行一些介绍和分类。在1.3中我们说明了解决cost-sensitive分类问题的核心在于解决(1)的优化问题，即如何使得分类算法的结果能够获得尽可能小得L(x,i)值。从(1)中我们可以看出，通过调整分类算法对于不同cost的分类的倾向，即P的