基于支持向量机不平衡数据集分类算法地研究

《基于支持向量机不平衡数据集分类算法地研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

摹丁支持向避机的不平衡数据集分类研究摘要现代计算机技术的高速发展，使得在科学研究和社会生活的各个领域中积累了大量的数据，为将这些数据转换成有用的信息和知识，数据挖掘技术应运而生并得以迅速发展。但是存在一类数据集称为不平衡数据集，这种数据集中一类数据的数目远远大于另一类数据的数目，而且往往少数类提供的信息更加重要，所以不平衡数据集的分类问题成为现在数据挖掘领域研究的一个热点。支持向量机是一种建立在统计学习理论基础上的分类方法，具有坚实的理论基础，对于普通数据集有比其他分类算法好的分类效果，但是对于不平衡数据集的分类效果并不是很好。本文的研究内容首先从不平衡数据集的特点入手，提出基于聚簇的下采样方法，通过分析得到支持向量机在不平衡数据集分类时失效的原因，采用提出的下采样方法，对多数类的支持向量进行下采样，目的是删除一部分多数类样本，以降低多数类与少数类的不平衡程度，然后利用不同类惩罚支持向量机对新样本集进行训练，达到提高分类精度的目的。现今流行的处理不平衡数据集分类的方法之一是代价敏感学习，但是支持向量机本身并不具有代价敏感性，所以并不适用于代价敏感数据挖掘，本文提出基于数据集分解的代价敏感支持向量机，通过输出后验概率和元学习过程，重构一个集成了误分类代价的新样本集，使用代价敏感支持向量机对重构的新样本集进行训练，以使分类的误分类代价最小。对每一个算法都进行了仿真实验，使用不同的评价准则，通过实验结果和对实验结果的分析表明两个算法分别从提高分类精度，使误分类代价最小方面达到了很好的效果。关键词：数据挖掘；不平衡数据集；SVM；代价敏感 基于支持向鼍机的不平衡数据集分类研究AbstractTherapiddevelopmentofmodemcomputertechnology,makingtheresearchandallareasofsociallifehaveaccumulatedlargeamountsofdata，inordertoconvertthesedataintousefulinformationandknowledge，dataminingtechniquesemergedanddevelopedrapidly．Butthereisaclassofdatasetknownastheimbalanceddataset，thisdatasetthenumberofaclassofdataisfargreaterthanthenumberofanothertypeofdataandinformationprovidedbytheminorityclassisoftenmoreimportant，SOtheclassificationofimbalanceddatasetsDataminingisbecomingahotresearchfield．Supportvectormachineisbuiltbasedonstatisticallearningtheoryofclassification,hasasolidtheoreticalbasisforcommondatasetthanotherclassificationalgorithmsachievethebestperformance，butfortheimbalanceddatasetisnotverygoodclassificationresults．Thispaperwillfirstofallthecharacteristicsofimbalanceddatasetsfromtheunevenstart，Thenextproposedunder-samplingbasedonclustermethods,Byanalyzingtheobtainedsupportvectormachineclassificationintheimbalanceddatasetcausesthefailure，undertheproposedsamplingmethodusedformajorityclasssupportvectorfortheunder-sampling,thepurposeistoremovepartofthemajorityclasssamplestoreducetheimbalanceddegreeofmajorityclassandminorityclass，andthenuseSVMtotrainthellewsampleset,toimprovetheclassificationaccuracypurposes．Currentpopularclassificationofimbalanceddatasetsdealingwithoneofthemethodsiscost—sensitivelearning，butthesupportvectormachineitselfdoesnothavethecostofsensitivity,itdoesnotapplytoconsiderationofcost-sensitivedatamining，datasetsbasedondecompositionoftheproposedcost—sensitivesupportvectormachine，throughtheoutputaposterioriprobabilityandmeta-learningprocess，allintegratedreconstructionofmisclassificationcostofthenewsampleset，usingthesupportvectormachineonthereconstructionofthenewtrainingsampleset，SOthattheminimummisclassificationcostclassification．Havecarriedoutailalgorithmforeachsimulationexperiment，usingdifferentevaluationcriteria,theexperimentresultsandanalysisofexperimentalresultsshowsthatthetwoalgorithmsarefromimprovingtheaccuracyandtomaketheminimummisclassificationcost havereachedgoodresults．哈尔滨_r程大学硕十学位论文Keywords：datamining；imbalanceddataset；SVM；cost—sensitive 第1帝绪论第1章绪论1．1论文研究的目的和意义随着科学进步，计算机技术的高速发展，以及人们获取大量数据信息能力的提高，在各个领域中都积累了大量的数据。面对数量巨大并且不断增长的数据，人们迫切需要将这些数据转换成有用的信息和知识，数据挖掘技术从而得到了迅速的发展。获取有效、新颖、隐含有用的信息，并且最终可被理解的不平凡过程u1就是数据挖掘。所谓不平凡过程就是它已经不只是一般的数量计算，还包括对结构、模式、搜索参数等过程。数据挖掘的目标是为了找到数据间隐含的关联、特征、趋势等信息，从而可以发现从前未知，而且容易理解、有价值的知识，这些知识对趋势进行预测和决策是非常有用的。在人们日常数据收集过程中，虽然收集的数据量很大，但对于用户真正有用的信息通常非常的有限，大多数情况下只是全部数据中的-d,部分。对于上述问题，提出了不平衡数据集，不平衡数据集是指某类样本数量明显少于其他类样本数量的一类数据集。在不平衡数据集中，假设可以把样本分为两类，一类是指样本数目较多但价值很小的样本，称为多数类。另一类样本是指在数据集中数量很小但通常具有巨大的影响力和价值，称为少数类，这类样本是我们主要关心和研究的对象，并且两类样本在数量上相差极大。在传统的分类方法中，分类器的设计一般将测试样本全部判别为大类而忽视小类，这样就会产生小类分类效果差的问题，但是，在实际的应用中，对少数类的正确预测往往比正确预测出多数类具有更大的价值。所以以类分布基本平衡为假设前提，在此基础上，以分类精度最大化为分类目标，倾向于对多数类有较高的识别率，对于少数类的识别率却很低的方法并不适用于人们实际处理数据信息。在理论研究中，传统的分类方法存在认为不同的分类错误会带来相同分类损失的问题，而现实的数据提取中，错分不同的数据集合往往会带来不同的损失。特别在不平衡数据集中，拥有更大价值的少数类要比多数类更加重要，少数类的分类错误会带来更大的损失。所以，需要为不平衡数据集分类寻求新的分类方法和判别准则，同时在不平衡数据集分类的研究中代价敏感学习越来越引起人们的重视。当今对于不平衡数据集的主要研究内容为：一是研究不平衡数据集类分布对传统分类算法的影响。二是对不平衡数据集重构训练样本集或直接改进传统算法，提高少数类的分类和预测性能指标。不平衡数据集分类的应用很广泛，在人们的日常工作和学习中经常存在，并且在很1 哈尔滨一r：稃大学硕十掌何论文II多领域具有重要的商业价值和意义‘21。例如不平衡数据集分类可以应用于欺骗信用卡检测、疾病诊断叫、文本分类闱、信息检索啊等。综上所述，对不平衡数据集分类算法的研究，主要集中于提高少数类的识别率，满足分类的错分代价最小。不平衡数据集分类算法是未来研究的一个新的发展方向，对数据挖掘技术提出了新的挑战。1．2国内外研究现状1．2．1支持向量机的发展与研究支持向量机(supportvectormachine，SVM)的相关技术将在2．1．4节详细介绍。支持向量机的理论发展经历了一个不断完善的过程，统计学习理论的研究最早在60年代就由V．Vapnik开始研究，他可以称为是SVM的奠基人。1971年，在“TheNecessaryandSufficientConditionsfortheUniformsConvergenceofAveragestoExpectedValues”一文中，V．Vapnik和A．Chervonenkis提出了VC维理论，它是SVM的重要理论基础。V．Vapnik在1982年的“EstimationofDependencesBasedonEmpiricalData”一书中提出了结构风险最小化理论，这一理论的提出是具有划时代的意义的，也是SVM算法的奠基石。Boser,GuyonandVapnik在1992年提出了最优分类器。Cortes和Vapnik在1993年更进一步的讨论了非线性最优边界的分类问题。V．Vapnik在1995年出版的“ThenatureofstatisticalLearningTheory”一书中，完整地提出了SVM理论。支持向量机的核心内容1992年提出，1995年正式提出了SVM算法，SVM是到目前为止统计学习理论最成功的实现，目前仍处于不断发展阶段。支持向量机的发展过程历时很短，但是它却拥有着坚实的理论基础，因为它是基于统计学习理论的，而且近年又出现了很多理论研究成果，也为应用研究打下了坚实的基础。支持向量机发展的这些年来，对它的研究主要在对其自身性质及对其完善方面。支持向量机是在结构风险最小的原则上，在以统计学习为理论的基础上，很有效的避免了许多学习算法中维数灾难、局部极小等传统分类方法会出现的问题，因此受到了广泛的关注，成功的应用在了文本分类、语音识别、计算机入侵检测等多个应用领域。我国在支持向量机的发展上暂时落后于国外，但随着近几年对支持向量机的研究发展的加快，我国的研究人员做了很多研究工作并取得了大量的成果，对于推动我国支持向量机的发展发挥着巨大的作用和具有重大的意义。2 第1章绪论1．2．2支持向量机对不平衡数据集分类在不平衡数据集中，多数类与少数类这两类样本数目相差极大，而且不平衡数据集中，通常少数类样本具有比多数类样本更大的影响和价值，所以少数类才是我们所要关心的，在通常情况下，分类算法会将训练样本全部分类为多数类，对于少数类却忽略不计，从而使得对少数类的分类效果非常差，然而这并不适用于很多实际应用中，因为在好多情况下把少数类正确预测出来更有实际意义，需要提出新的分类算法来完善机器学习理论体系来解决这一实际问题，所以目前不平衡数据集的分类问题成为机器学习领域中新的研究热点，对于不平衡数据集的分类是对传统分类方法的一个重大挑战。目前传统的分类算法的最高目标是使总体分类精度最高，为了达到这个目标，算法因为提高了多数类的分类精度，这也就导致忽视了少数类的分类精度。不平衡数据集分类时使用传统的机器学习分类算法性能下降的原因有很多，例如性能评价准则选取的不合适、归纳偏置不恰当、由于某类样本数目过少产生的样本绝对稀少问题和各类样本数目相差悬殊产生的相对稀少问题以及数据碎片问题和嗓音等。针对上述问题现有的对策大致包括选择合适的性能评价准则、设置恰当的归纳偏置、分解数据集以及通过采样方法改变数据的原始分布以降低数据的不平衡性、进行单类学习、利用代价敏感学习方法来解决不平衡问题等。这些策略在一定程度上解决了不平衡数据集的分类问题。由Vapnik等人创立的支持向量机网，在实际生活中得到了广泛的应用。在假设类别均衡，样本数量大致相等的前提下具有较高的分类精度。然而当支持向量机应用于不平衡数据集时就会使分类器分类的性能大大下降‘7·蝎毡拍蚓。针对SVM应用于不平衡数据集的学习问题，对此的研究主要包括三个方面：第一，为了验证有偏性的存在Ⅲq，研究各种传统分类算法结果由类分布不同产生的影响；第二，通常采用合适的方法来重构训练样本集，以提高分类性能因御n；第三，为达到平衡的目的研究算法模型协加’271。文献[401提出给每一个训练样本通过后验概率赋予一个数量指标，根据得到的指标来建立优化算法，以此改善不平衡数据集的分类精度的后验概率支持向量机。文献[111提出一种模糊支持向量机，该支持向量机是通过赋予一个权重给每个样本的惩罚因子，以此达到使样本类别平衡的目的，确定处罚权重是使用该模糊支持向量机的关键。以上这些改进的方法都在一定程度上提高了在不平衡数据集中应用SVM的分类精度。文献【12]将代价敏感因子与支持向量机结合，为正类和负类分配不同的误分类代价。李正欣等提出SMOTEBoostSVM¨叫是利用SMOTE方法人造正类样本，3 哈尔溟T程大学硕十号：位论文将SVM作为弱分类器，用来构建分类器时使用AdaBoost方法。文献[141提出了一种自调节分类面的支持向量机，对分类面进行调整时是根据训练错分情况，以控制多数类和少数类样本的错分率来使样本达到平衡。1．3论文主要工作内容和组织结构1．3．1论文的主要研究内容本文对基于支持向量机在不平衡数据集分类展开研究，通过分析不平衡数据集中数据类别分布的特点，对支持向量机在不平衡数据集分类失效原因的研究，结合数据处理的采样技术与代价敏感学习对标准支持向量机进行改进，以使支持向量机能适用于不平衡数据集分类，本课题主要从以下几个方面展开研究：(1)对支持向量机进行研究。在了解支持向量机原理的基础上研究其分类的主要过程及方法。这里重点研究的内容是支持向量机在不平衡数据集中分类的失效的原因，在了解失效的原因后，深入研究如何对支持向量机进行改进使其能适用于不平衡数据集的分类。(2)对采样方法进行研究，包括使用采样方法的目的及采样的常用技术。在此基础上，重点研究下采样方法，提出把训练样本集分成若干子集，分别在每个子集中进行下采样的新方法，并研究把这种下采样的方法应用于使用支持向量机对不平衡数据集分类时多数类的支持向量。(3)对代价敏感学习展开研究，研究代价敏感学习的基本原理及实现方式。并由分析贝叶斯决策理论及最小化风险理论得到的启示，与代价敏感的误分类代价结合对不平衡样本集进行重构，使新样本集中的样本集成误分类代价，提出一种新的代价敏感支持向量机。1．3．2论文的组织结构第1章分析了本课题的研究的目的和意义以及到目前为止一些国内外相关的研究现状，最后介绍了本文研究的主要内容和文章的组织结构。第2章首先对数据挖掘分类技术进行研究，包括传统分类技术及相关分类算法，重点研究了支持向量机这种分类效果很好的分类算法，其次对不平衡数据集分类的相关技术及难点进行了分析，最后研究了常用的用于不平衡数据集分类时采用的相关技术。第3章首先提出一种基于聚簇的下采样方法，并把这种新的下采样方法应用于多数类的支持向量，以降低多数类与少数类的不平衡度，然后与支持向量机相结合，提出4 第1章绪论一种把基于聚簇的下采样方法和支持向量机相结合的能适用于不平衡数据集分类的新的支持向量机。并通过选取数据集进行仿真实验，以验证该分类器能有效提高不平衡数据集中对少数类的分类精度和总体分类精度。第4章本章是基于数据集分解对样本空间重构提出一种新的代价敏感支持向量机。由贝叶斯决策理论及最小化风险得到启示，结合代价敏感和元学习过程重构样本集，使样本集成误分类代价，最后利用代价敏感支持向量机对重构的数据集进行训练，得到一个新的代价敏感支持向量机。并通过选取合适的数据集对分类器进行仿真实验，以表明该方法能使不平衡数据集的误分类代价最小。最后对全文进行总结，总结文中工作，指出不足，并对今后的工作进一步展望。5 哈尔滨T程大学硕十学何论文第2章不平衡数据集分类2．1数据挖掘分类2．1．1数据挖掘现代数据库技术的飞速发展加上能够获得数据的方式多样化，使得现在人类所得到的数据数量非常巨大，但是面对这种信息膨胀的境况能够对这些数据进行处理的工具却非常有限。数据库系统仅仅是对数据库中已有的数据进行存取等简单的操作，通过这种方式从数据中获得的信息仅占大量数据的一小部分，那些隐藏在大量数据之后的能对数据进行整体特征描述以及对发展趋势的预测更加重要，通常在制定决策时这些信息具有非常重要的价值。数据挖掘是运用技术把信息和知识从大量数据库或数据仓库的数据中提取出来，被定义为找出数据中的模式的过程，这个过程必须是自动的或半自动的。数据的总量总是相当可观的，但从中发现的模式必须是有意义的，并能产生一些效益，通常是经济上的效益。在数据挖掘中，计算机以电子化的形式存储数据，并且能自动地查询数据，或至少扩增数据。经济学家、统计学家、预测家和信息工程师长久以来相信，存在于数据中的模式能够被自动地找到、识别、确认并能用于预测。该理论的最新发展使得由数据中找出模式的机遇剧增。在最近几年，随着数据量的膨胀，以及利用机器承担数据搜索工作已变得普通，数据挖掘的机会正在增长。世界正越来越丰富多彩，数据挖掘技术成为我们洞察构成数据模式的唯一希望，被充分研究过的数据是宝贵的资源，它能够引导人们去获得新的洞察力，用商业语言讲是获得竞争优势。数据挖掘是数据库、人工智能、机器学习、统计学等多个领域的理论和技术的一个有效综合，是为了发现大规模数据中的模型和数据间的关系，并把这些模型和关系用于预测需要使用各种分析工具的一个过程。数据挖掘过程简单分为问题定义、数据收集和预处理、数据挖掘算法执行、结果的解释和评估。图2．1表示的是数据挖掘过程。数据挖掘已经经历了十几年的发展，国外已经在这项技术上获得了大量的经验。在研究方面不仅把各个学科的经验集中，在商业上也涌现出了大量的软件产品，应用在社会大量领域并取得了很好的效果。数据挖掘在国内的发展近年也从单纯的研究向产品的开发应用转变，随着国内经济的飞速发展，经济制度的完善，市场对于数据挖掘的需求也在高速增长。如果不了解原6 第2辛不平衡数据集分类i一——II—IIIiiiiiiiiiiiiiiiiiiiiiii葺iiiiiiiiiii理或是缺乏核心技术，因为需要多次的实验与验证，应用效果的表现将会差强人意，这点与传统的软件是不同的。虽然数据挖掘的国产软件刚刚开始发展，但是速度是很快的，相信随着市场不断增大的需求与应用技术水平的不断提高，会出现大量优秀的国产数据挖掘软件。2．1．2分类技术图2．1数据挖掘过程分类技术是对具有类别标记的数据进行训练，从而得到一个模型能够预测新样本的类别。数学描述如下：给定一个有限训练样本集，寻找一个分类映射，，使得F能够在训练集合上拟合，即：F0；)；Ci，其中，，称为分类函数或分类模型，分类器的性能可以用预测的准确程度来评价。两类问题的预测问题都可以归结为，分类和回归。分类和回归的结构基本相同，输出取值范围不同是它们的区别，分类的输出是有限的离散类别值，而回归的输出则是无限的连续值。分类算法的目标是建立具有良好泛化能力的模型，即建立能够准确预测位置样本类标号的模型。分类问题的基本框架如图2．2所示，分类有两个步骤实现：建立模型和使用模型预测。第一步，对一个类别已经确定的数据集由属性描述的数据元组来建立模型，用来描述预定的数据类集。经过分析的数据元组形成训练集用来建立模型，单个元组称为训练样本。训练集中的每一个元组都属于一个确定的类别，类别用类标号标示，也称为有指7 哈尔滨’1：程大学硕十学1：c7：论文导的学习，就是模型的学习在知道每个训练样本属于哪个类的指导下进行，因为提供了每个训练样本的类标号。第二步，把创建好的模型将类别未知的元组归入到某类或者某几个类中，评估的方法很多，通常使用创建的模型在一个测试集进行预测，并将结果和实际值进行比较，得出预测准确率，测试集是随机选取的样本集，并独立于训练集。’2．1．3传统分类算法图2．2分类基本框架(1)决策树算法从机器学习中引出的决策树方法是一种较为通用并被深入研究的分类函数逼近方法，目前已形成了多种决策树算法，如CLS，ID3，CHAID，CART,FACT等。作为分类器，决策树是一棵有向无环树。核心思想是采用自上而下递归的方式构造决策树。创建决策树的问题可以用递归形式表示。绝大多数决策树分类方法分两步构造分类器：树的生成与树的剪枝。在树的生成阶段，决策树是通过反复地拆分训练集来生成。首先，选择一个属性放置在根节点，在每一次分拆时，都是利用某种分拆准则选择一个属性。这将使样本集分裂成多个子集，一个子集对应于一个属性值。然后在每一个分支上递归地重复这个过程，仅使用真正到达这个分支的实例。如果在一个节点上的所有实例拥有相同的类别，即停止该部分树的扩展。对已经生成的决策树进行树剪枝是为了处理过度拟合的问题，选择好的剪枝方法是就是为了消除训练集中异常和噪声，这样才能避免数据过适应的问题并能使训练时间减少。因为数据的表示不当，噪声或者生成了重复的子树等多种原因，使生成的决策树规模过大，降低了决策树的可理解性和可用性，所以对决策树的简化问题就是要从中寻求一棵最优的决策树，这是必不可少的环节。8 第2章不3F，衡数据集分类iiiiiiiiiii'I'?umrmllnnljIIII'Ii(2)K近邻算法K近邻算法是有监督的学习方法，规则的描述并不需要额外的数据，数据就是它的规则。它与归纳学习最大的区别就是用已经存在的数据来解决问题，而不是间接的通过推导的规则来解决，当有一个新的样本加入时，它并不需要之前构造一个分类器，而是用基于某个距离的算法，在训练集中找到与这个新样本点最近的七个样本，则与这个新样本最近的七个样本中的大多数样本的类别既为新样本所属的类别，它可以存在噪声，就是不要求～致性，并且对样本的修改也不是全部的，不需要重新来进行组织。K近邻算法在训练之前不需要建立模型，只要之前把训练样本存储在数据库中，通过最近的K个相邻样本的类别来预测未知样本的类别，所以计算开销几乎为零。如果样本不能在训练开始前全部得到，而需要以后更新补充，K近邻算法非常适合这种情况，由于样本是随时添加的，所以该算法的时效性是很强的。不足是由于训练之前没有对训练点的信息进行压缩，每添加一个新样本点都要与样本集中的全部已知样本计算距离，每个新样本都要对所有数据进行一次遍历，所以必须考虑时间和空间的复杂性问题，这就使得工作量很大，所以当已知样本集的规模很大时，计算的开销是很高的，导致使用上的不便。(3)人工神经网络：人工神经网络能够分析大量复杂的数据，它是建立在自学能力的数学模型基础上的，模拟的是人类大脑的组织和功能，运用多种学习方法对样本集进行学习从而获得知识，将得到的知识储存在网络各个单元之间的连接权上。神经网络是一组连接的单元即4输入和输出的连接，都有一个权与各个连接相连。在学习阶段，为了能够预测输入样本的准确类标号，可以通过调整神经网络的权来实现。神经网络通常是由隐蔽层、输入层、输出层三层组成。人工神经网络可以根据所在的环境去改变它的行为。也就是说，人工神经网络可以接受用户提交的样本集合，依照系统给定的算法，不断地修正用来确定系统行为的神经元之间连接的强度，而且在网络的基本构成确定之后，这种改变是根据其接受的样本集合自然地进行的。用户不需要再根据所遇到的样本集合去对网络的学习算法做相应的调整。因此，人工神经网络具有良好的学习能力。但是人工神经网络算法是基于经验风险的最小化原理的，不仅具有结构复杂，神经网络的层数和所用的神经元个数难以确定的缺点，而且还容易陷入局部极小的问题中，发生过学习现象，而这些缺点在支持向量机分类算法中能够得到很好的解决。(4)朴素贝叶斯分类器9 哈尔滨下稃大学硕十学何论文朴素贝叶斯分类器是产生概率估计来替代类预测的，对于每个类值，都是估计某个实例属于这个类的概率。基于一定的假设，在有确定的概率分布的前提下，根据条件概率分布和已知数据来进行推理，以最优的预测来进行决策。朴素贝叶斯分类法给出了一个简单且概念清晰的方法，来表达、使用和学习概率的知识。使用它能够达到很好的预测结果。在许多数据集上，朴素贝叶斯的性能能与一些更加成熟的分类相媲美，甚至会有更出色的表现。但是朴素贝叶斯法在很多数据集上的表现差强人意，因为朴素贝叶斯处理属性的时候，认为属性之间是完全独立的，所以一些冗余的属性会破坏机器学习过程。对于数值属性，正态分布的假设是朴素贝叶斯的另一个限制，因为许多属性值并不呈正态分布。然而对于数值属性，可以采用其他分布形式，如果知道一个特定的属性可能遵循其它的分布形式，可以使用那种分布形式的标准估计过程。如果怀疑数值分布不是正态分布，以不知道真正的分布形式，可以使用“核密度估计”过程，核密度估计并不把属性值的分布假设成任何特定形式的分布，另一种可行的处理方法是将数据离散。2．1．4支持向量机统计学习理论是目前针对小样本统计估计和预测学习的最佳理论，它从理论上系统地研究了经验风险最小化原则成立地条件、有限样本下经验风险与期望风险的关系及如何利用这些理论找到新的学习原则和方法等问题，在很大程度上解决了模型选择与过学习问题、非线性和维数灾难、局部极小点问题等，因此成为研究的热点。支持向量机(SupportVectorMachine，SVM)是Vapnik根据统计学理论提出的有监督机器学习方法，在统计学习理论的VC维理论和结构风险最小化原理基础上，根据有限的样本信息在模型的复杂性和学习能力之间寻求最佳折衷，以获得最好的推广能力。它脱离传统方法中降维的定式，利用反转技术有目的增加问题空间的维数，使得分类问题变得相对容易。SVM是基于寻找一种特别的线性模型：最优超平面的算法。处理两分类问题时，把用内积函数定义的非线性变换将样本空间变换成一个高维空间，然后在所变换的高维空间上寻找一个(广义)最优分类面作为两类的分割，就是说在实例空间上存在一个超平面能对所有的训练实例进行正确分类，最优超平面是一个能使两个类之间达到最大限度分离的超平面，它对两个类都是尽可能地不靠近，以保证最小的分类错误率。如图2．3，两个类分别用空心圈和实心圈来表示，从技术上说，一系列点的凸包即最紧凑的凸多边形，它的轮廓是通过将每个点与其他所有的点连接而形成的。假设这两10 第2章不平衡数据集分类个类是线性分隔的，它们的凸包不能重叠。在所有能分隔这两个类的超平面中，最大边际超平面是其中离两个凸包距离尽可能远的那个，它垂直于两个凸包间距离最短的线段(图中虚线)。竣优超甲丽图2．3支持向量机分类不意图最简单的情况是样本空间是线性可分的。‘(1)线性可分情况设线性超平面f(x)一wx+6a0能将正负样本分开，且对正样本有f(x)一wx+6≥0，对负样本有f(x)。wx+bs1。令超平面，0)11／F1]／(x)=一12_间的距离为2△，则称距离△为分类间隔。已知线性分类方程为舭+6=0，对它归一化，使对线性可分样本集；O；，Y。)，i；1,2，．．．，Z，y∈伯一U满足Yf【(w茗f)+6】-120,i=1,2，⋯，Z这样分类间隔A=I／IIW《，因此使分类间隔最大就等价于最小化llW0。线性可分支持向量机可归结为如下的二次规划：mm吾llwll2sJ'．Yj【(w’‘)+6卜1之0，ft1,2，⋯，Z利用拉格朗日优化方法，根据对偶理论可以把上述分类问题转化为它的对偶问题：max形(a)2荟口z一圭磊。yry，口r口，(x，，x，)珐∑y忍-0口j苫0,i=1,2，．．√这是一个有不等式约束的二次规划问题，因此存在唯一解。求解得到的最优分类函数为： 哈尔滨T程大学硕十学位论文，(x)=sgn(wx+6)=sgll{罗afyf“·z)+6}舒(2)非线性不可分情况当出现非线性且不可分的情况时，针对这种情况，SVM算法使用一个非线性变换将其映射到一个线性可分的高维空间中，最优的线性分类超平面就在这个变换空间中求得。因为涉及训练样本的内积运算，最优分类超平面的点积就可以通过礅)，)核函数来代替，这样做的好处就是避免了在高维特征空间内进行复杂运算，从而得到非线性不可分情况下最优分类函数的表达式。核函数代替对偶问题中的内积形式，从而得到非线性的分类支持向量机：一吣)。酗一言篇yiyja—ajk(x,,xj)sj。善ytaros口tsc，flL2，⋯：2相应的非线性支持向量机的判别函数为：f(x)一sgn{(w·x)+b}---sgIl{罗qYf七瓴·z)+6】．—■一2．2不平衡数据集分类难点分类是机器学习领域中重要的研究内容之一，普通的数据集使用现在一些已经成熟的分类算法进行分类时都能取得比较好的分类效果，但是当把这些分类算法应用于不平衡数据集中时其分类性能大大下降，因为不平衡数据集的数据特点与普通数据集非常不同，传统的分类算法并没有考虑到不平衡数据集中数据的特点。不平衡数据集分类的难点主要有以下几个方面：(1)少数类样本比例小少数类样本与多数类样本相比在数量上的稀少是数据集不平衡的根本原因。少数类样本数量稀少可分为两种情况，第一种情况是少数类样本数量的绝对稀少，是指少数类样本的实际数量少，处于这种情况时，由于少数类能提供的分类信息少，想要发现少数类内在的规律非常困难，就这造成了少数类样本很难被识别出来；第二种情况是少数类的相对稀少，是指少数类样本的实际数量并不少，而是与其他类别的样本相比，在数量上相对较少。当少数类样本处于相对稀少的情况时，表面看来少数类样本的数量并不少，12 第2章不平衡数据集分类但是由于多数类样本把少数类样本包围，使得多数类与少数类的分类边界变得不清晰。综上所述由于少数类样本占整个数据集的比例很小，导致少数类所提供的分类信息并不充分，分类器想在有限的样本中找到规律很难，这也就造成了对少数类的识别率很低的情况。(2)性能评价准则不恰当性能评价准则是用来指导数据挖掘算法的设计和评估算法性能的，所以在数据挖掘中的作用是勿庸置疑的。分类算法性能评价的最基本的指标是分类准确率。准确率只对平衡数据集是一个很好的评价指标，但是用它来评价不平衡数据集的分类结果是不恰当的，原因是由于少数类样本的数量很少，所以少数类对总体的分类精度的影响并不大，把全部样本都视为多数类，仍能得到很高的分类正确率。因为少数类被正确识别很重要，但是少数类却全部被错分，这时的分类模型就是毫无意义和价值的。举个例子来说，在现实应用中，如果一个数据集中的少数类样本表示一种罕见的疾病，并且这个少数类正是人们所关心的类别，那么使用上面的分类器并不能把人们所关注的少数类识别出来，那么这样的分类器就是毫无意义和价值的。综上可知，面对不平衡数据集的分类问题时，能够把少数类正确的识别出来是特别重要的，所以有时需要在一定程度上牺牲多数类的分类准确率来提高少数的分类准确率，是想要获得较好的总体分类精度，选择好恰当的评价指标是非常关键的。(3)噪声与少数类样本混淆噪声样本经常出现在数据集中，会影响数据集的分类性能。而且在不平衡数据集中，噪声对少数类的影响要比对多数类更严重，一种情况就是两类样本的分布出现重叠和交叉，分类边界模糊，这种情况对于少数类样本的分类来说困难更大。在对不平衡数据集进行识别并去除噪声的处理时，过滤器很难准确的识别出噪声数据和少数类样本，将少数类样本判为噪声数据而被删除，这样会影响分类的精度，所以说处理噪声是不平衡数据集分类中的一项重要任务。(4)阈值设置不合理很多分类算法，如神经网络、决策树等，为使分类能够实现，样本的类别确定就需要一个适当的阈值。往往一些算法阈值的设定是以牺牲少数类样本的正确率为代价的，这种情况不利于对少数类样本的分类，这都是为了获得较好的分类准确率或者避免过拟合，从而将少数类样本误判为多数类。所以合理的设置阈值对算法的性能有着很大的影响。13 哈尔滨T程大学硕十学何论文2．3不平衡数据集分类相关技术所谓不平衡数据集p卯，是指一个数据集中某类的样本数量比其他类的样本数量多的多，其中样本多的一类一般称为多数类，样本少的类称为少数类，而且往往少数类包含的信息是最重要的，但是以前的分类方法更关注于多数类较高的误别率，但是少数类的识别率却非常低。所以对不平衡数据集的分类研究得到越来越广泛的关注。因此需要研究新的分类方法和判别准则以适合于不平衡数据集的分类问题。目前对不平衡数据集分类的研究主要关注以下两个层面：一是数据采样方法即数据层面上，二是对传统分类算法的改进是即算法层面上，最后是对评价准则的研究。2．3．1数据层面为了使不平衡数据集中样本的类别平衡来解决原来类别不平衡的问题，从数据层面来看通常使用采样方法，采样方法是在并不改变现有的算法的基础上，为了消除数据集中两类数据不平衡的现象通过减少多数类样本或者增加少数类样本来实现。采样技术主要的作用是在原始训练数据集中进行一些数据预处理，以形成新的训练集来使用学习算法进行训练。在原始数据集中缓解数据集类别不平衡的最重要手段之一就是进行重采样，其主要思想是通过增加或者减少数据样本使得训练集变得更加均衡，以此降低在分类器构建时由于数据分布不平衡带来的不良影响。从采样所采用的策略来看，主要有两种：一种是简单随机采样；另一种是启发式采样。简单随机采样并不利用数据的特定的分类信息，而仅仅是随机地增加(主要通过复制)或删除样本，启发式抽样则不同，它实施相应的采样时是要充分利用数据信息的。重采样技术主要包括上采样和下采样两种。上采样试图增加少数类的训练样本，而下采样就是试图减少多数类的训练样本。下面分别详细介绍两种采样方法。(1)上采样上采样方法是处理不平衡数据的常用方法，文献[16．21]提出了增加样本的一些方法来重新增加少数类样本数量，目的是为了弥补少数类与多数类样本数目的差距，以起到平衡的作用。该方法增加了原有信息，能有效的解决类别失衡的现象，但有时无法保证与原来的样本分布是一样的，很可能发生过学习的情况。简单的复制少数类样本是最简单的办法，但是因为引入了额外的训练数据，会增加构建分类器的时间，增大了开销，而且并没有为少数类增加任何新的有价值的信息，可能会导致过学习。所以如何增加样本数量就很值得研究，如果仅仅是简单的硬塞进一些人为添加的样本到数据集中去，则14 第2章不平衡数据集分类训练集数据原有的随机性分布特点就有可能被破坏，进而待训练样本的分布规律也被破坏，这样即使能得到分类性能较好的分类器但也不能很好的用于测试样本的分类识别中去。为此，为解决上述问题，对上采样方法进行改进，通常采用加入随机噪声或合成新的样本的办法，在一定程度上取得了一定的成效，上采样技术中最有代表性的是Chawla等人在2002年提出来的SMOTEtl81技术。SMOTE算法主要思想是为了生成新的少数类样本，在相距较近的小类样本之间进行线性插值，目的是通过合成新的少数类样本来减轻类别的不平衡问题，能够使扩展的少数类的决策边界进一步向多数类方向移动。Han等人对SMOTE提出了改良的方法，即“Borderline．SMOTE”技术吲，这种技术是进行插值时只选择在合适的区域内插值，这样做可以保证新增加的样本能提供有价值的分类信息，文献[23．24]也在SMOTE基础上进行了改进。另外，文献【25】提出了基于初分类的上采样算法，这个算法是有一个多数类样本，如果它在数据集中的k个近邻都属于多数类，则由七近邻的思想则该样本被认为离分类边界较远，则对这个样本分类是相对保险的，然后在多数类中把满足以上k近邻思想的所有多数类选择出来放入到一个集合中，再将少数类与选取出来的多数类样本集合合并为一个训练集，在新的训练集中对多数类样本进行最近邻分类，将选取出来的多数类样本和少数类样本合并为第二个新的训练集。一，(2)下采样通过某种方法来减少多数类样本以提高少数类的分类精度是采用下采样方法的目的，文献[22][24][2511261研究了“减样法’’，即通过为了使数据集里样本类平衡而通过一些方法来减少多数类样本的数量。虽然这些方法能去掉一些相邻边界点，但是也必然会失去一些具有分类信息的有价值的样本点，随机性也无法得到保证。一种最基本的方法就是随机去掉多数类的样本以平衡数据集中的类分布，但是这种方法虽然简单但是会导致一些能提供重要信息的多数类样本丢失，已有一些信息不能够被充分利用阳，因此一些对下采样方法进行改进的算法相继被提出。Kubat和Matwin提出的单边选择处理法嘲(one．sidedselection)是一种具有代表性的下采样方法，尽可能地不删除有用的样本，通过减少分类超平面附近的样本、噪声数据和离分类超平面较远的冗余样本等办法来尽量减少数据集中多数类样本，以实现多数类和少数类样本数目相对的平衡。也可以把对少数类的上采样与对多数类的下采样两者结合起来㈣。文献[301提出了一种基于遗传的方式来对多数类进行抽样的算法，通过这种方法能找出噪音样本并将它们从数据集中删除。与上采样相比，下采样似乎有更多的策略可行。下采样方法是通过减少多数类样本】5 哈尔滨T程大学硕十学何论文的数量来缓解数据集的不平衡度。一般来说，上采样方法的效果不如下采样方法的效果。常用的技术基本利用欧氏距离以及K近邻规则启发式地识别可以合理删除的样本。基于距离的下采样方法使用距离模型，即多数类样本和少数类样本最近距离，最远距离，平均最近距离，平均最远距离四个指标去重新从多数类样本中选取样本。最近距离方法是对于数据集中的每一个少数类样本，首先计算与所有多数类样本和所有少数类样本的距离，然后选择出k个与其距离最近的多数类样本。如果在数据集中有n个少数类样本，则最近距离方法最终会选择kxn个多数类样本。然而，一些被选择出来的多数类样本有可能是复制的。和最近距离方法相似，使用最远距离方法选择出多数类样本，是计算与每一个少数类样本的最远距离。对于每一个在数据集中的多数类样本，平均最近距离指标计算一个多数类样本与所有少数类的平均距离。这个方法是选取最小平均距离的多数类样本。平均最远距离方法类似于平均最近距离方法，该方法是选取与所有少数类样本平均距离最远的多数类样本。以上基于距离的下采样方法，在大规模数据集中选择多数类样本会花费大量的时间，因此它们在现实的应用中效率并不高。重采样技术，从表面看是将数据集从数量上进行平衡，而从学习角度看，可将其视为一种正则化手段，是为了避免过学习，尤其是对多数类来说。还有一个问题是，为使样本数量平衡采用简单的重采样不一定是最好的办法，为确定最优的样本容量，Chawla等利用Wrapper方法m1，Garciat等把它看作为一个组合优化问题，使用优化算法求解阎。从理论上来说，在处理不平衡数据集分类时，两种采样方法都存在一些优点和缺点，没有哪一种方法是有绝对优势的弦蚓。为了能达到更好的效果可以将两种采样技术混合起来使用。2．3．2算法层面现在从算法层面对不平衡数据集的研究主要集中在代价敏感学习、集成学习、单类学习等以下几个方面。(1)代价敏感学习关注正确率或错误率往往是标准的机器学习算法最关注的，认为只要算法预测的正确率提高了就意味着分类性能也提高了，这其中是在传统的机器学习分类研究中隐含着一个假设，即所有的分类错误带来的错误代价是相同的。随着实现应用研究的深入，发现有一些分类问题很难用传统的分类方法来加以解决，如信用欺诈识别，癌症诊断等等，在这些问题不同类别样本被错分所产生的错分代价是相差非常大的，如信用的欺诈者、16 第2章不平衡数据集分类癌症患者数量很少，在所有数据中所占的比例很小，但是如果把这些少数类的样本错分，所带来的错分代价是相当大的。由于少数类所占的比例很小，所以基于传统分类算法的应用于这些问题时通常会得到较高的正确率，但这是相对于多数类样本来说的，少数类样本并没有被正确的识别出来。为摆脱这种拥有大量数据但是所需要的分类信息匮乏的境地，代价敏感学习得到越来越多的关注和应用。代价敏感学习是关注类错分代价的的机器学习算法。与非代价敏感学习的最大差别是对类错分代价处理的方式和目的不同。代价敏感学习考虑分类代价，以取得最小的误分类代价为目的。而非代价敏感学习并不考虑类错分代价，以取得最大的分类精度为最终目的。从统计学的角度来看，代价敏感学习要能训练出逼近样本代价分布的分类器，而传统的分类方法是训练出逼近样本的类分布的分类器，并不是代价分布。代价敏感学习就是要设计出能逼近代价分布的新的算法，也可以在传统分类器算法的基础上进行改造，使结果最终也逼近代价分布。，，在代价敏感学习中对不同类的分类错误赋予的代价是不同的，采取将较高的代价赋予少数类样本，把较小的代价赋予多数类样本的策略，是为了达到使样本之间的数目平衡的目的pq。文献【37】改进了Veropoulos的代价敏感支持向量机，但基本思想都是为了使SVM的超平面获得代价敏感把代价与松弛变量相关联。为了能使用SVM处理多类问题Lee等人设计了把采样偏置考虑进去的代价敏感的支持向量机㈣。文献[391提出了对正负两类的类内离散度矩阵分别进行加权的加权Fisher线性判别模型(WFLD)。上面提到的代价敏感学习方法的改进都是以全局模型为前提来改进的。文献【40】就提出把代价敏感应用在局部的算法，使用该算法预测一个新样本时，选择恰当的距离度量方法是第一步，得到新样本的k个近邻，接着使用加权的方式对选择出的这k个近邻进行训练，这样就得一个分类器，可以用这个分类器来进行预测。代价敏感学习方法存在一些不足，各类的错误代价信息不好确定，通常需要多次实验或是根据专家或经验来确定。当前对代价敏感学习的研究主要从两个方面展开：1)在不改变以前算法的基础上，根据样本不同的错分代价来重构数据集。使用这种思想对数据集进行重构是使用每一个样本的错分代价为数据集中的每一个样本加权，根据权重重构原始数据集，得到一个新的数据集。这里重构数据集主要是采用采样方法，有上采样和下采样两种方式。上采样方法为反映代价信息来改变数据集中的类别分布，通过复制代价高的样本，使类别的分布与代价成正比。下采样方法与上采样方法同理，17 哈尔滨T程大学硕士学何论文也是要使样本数量与代价成正比，不同的是下采样是减少代价小的类别的样本的数目。2)将代价因子引入到传统的分类算法中去，得到基于代价敏感的分类算法。在代价敏感学习中对多数类样本给予较小的错分代价，对少数类样本给予较高的错分代价，这样做的目的是为了平衡两类样本间数目的差异。在代价敏感学习方面，假设是二分类问题，是把给少数类样本被错分为多数类赋予比把多数类样本被错分为少数类更大的代价来实现的。因为能够正确识别出少数类样本所获得的价值会大大超过能够正确识别多数类样本所获得的价值，所以分别为多数类被误分为少数类和少数类被误分为多数类样本的这两种分类错误指定不同的误分类代价，这样就可以使分类器向有利于少数类样本正确分类的方向偏移p11。(2)集成学习方法对不平衡数据集分类使用AdaBoo“421可取得较好的分类效果，但是也有实验结果表明在提高少数类样本的识别率方面AdaBoost的能力很有限㈣，原因是提高整体分类精度是AdaBoost的目标，多数类样本对精度的贡献大是因为该类样本的数目多，同理由于少数类样本数目很少所以对精度的贡献也就小，所以这种分类决策是不利于少数类的分类的。为此，相继提出了一些改进方法，如以为了使分类错误的少数类样本比多数类样本有更高的权值而改变权值更新规则为主要策略的AdaCostM、RareBoostM。此外还有将集成方法与采样方法相结合的改进方法，文献【46】【47】是采用的方法是为了使分类器能够更好地提高少数类的分类性能，利用过抽样的优点是既能增加少数类样本的数量，又能利用能提高不平衡数据集的整体分类性能的集成方法，将过抽样与集成方法进行融合的方法，将过抽样和集成方法结合的成功例子有如文献[481提出的C．SMOTE算法。(3)单类分类器方法想要获取两类或是多类的样本在实际应用中是比较困难的，就是获取得到了也是以付出很高的成本为代价的，所以一般只能获取单类样本。所以在这种情形下，对单类样本进行训练成为解决的办法。单分类器是用来只对训练集中的一种类别数据进行分类训练，这是一种能有效解决不平衡数据集分类问题的方法阳1。如文献【50】就是用SVM对少数类样本进行训练，而且通过实验表明这种方法还是取得了一定的效果的。单类分类器因为只用数据集中的某类样本进行训练，这必然导致训练的数据量较少，这也就能减少构建分类器需要的时间，而且节约了开销，单类分类器在很多应用方面都有着很好的前景。2．3．3评价准则在一般情况下，人们评价机器学习的精确度是使用如下公式：】8 第2章不平衡数据集分类即+TNaccuracy2—=—_以+n式中：开——验证时正类的正确样本个数TN——验证时负类的正确样本个数n+——正类样本数量n‘——负类样本数量但在对待不平衡数据集的分类问题时，这种评价方法是不合适的。举个简单的例子，若数据集仅有3％是少数，那么分类器只需把所有测试样本分类多数类，这样就可以获得9r7％这样一个很高的准确率，但这样的分类器是没有实际意义的。因此对于不平衡数据集分类就要采用一种新的评价准则，应考虑使用更加合适的评价方法。(1)不平衡数据集的分类精度评价准则针对不平衡数据，需提出更为合理的评价标准，常用的标准有：召回率recall、准确率precision、F—value值、g—mean值。少数类的recaH、precision、F—value、g—mean值计算方法分别如下：．recalltTP{qP+FN)precision=TP|QP+FP’F-value：f一(1+／82),recall*precision1l∥2率recall+precisionfJTPJTN，g—me口忍。、fTP+FN。宰、『TN+FP’不平衡数据集学习常用的评价准则g—mean，是一种几何平均方法，它是少数类的精确度印／(卯+FN)与多数类的精确度TN／(TN+即)的乘积的平方根，二者的值都大时，g—mean才会大，且尽量保持两者平衡。如果仅仅负类的精确率大，而正类的精确率小，那么g值仍会比较小，反之亦然，正是几何平均这种特性才被许多研究人员所采用，因此g—mean能合理地评价不平衡数据集的总体分类性能。还有一个不平衡数据集学习中少数类的F—value也是有效的评价准则，它是recall和precision的组合，其中卢的是取值是可以调整的，通常取值为1，但是只有当少数类的recall和precision的值都很大时，它的F—value才会大，因此它能正确地反映少数类的分类性能。(2)代价敏感分类评价准则除了分类精度和二分类评价指标之外，代价敏感学习有其代价相关的评价指标，常19 哈尔滨T稃大学硕十学何论文用的代价敏感评价指标有：分类时产生的总的错误代价(TotalCosts)，平均误分类代价(AverageCosts)。根据二分类的混淆矩阵和代价矩阵，TotalCosts和AverageCosts分别为：TotalCosts=FPxcost(N，P)+FN×cost(p，Ⅳ)Aw阳geCos跆。—FPxcost(N,P)+—FN×cost(P,N)2．4本章小结本章首先对数据挖掘分类方法进行了介绍，并对传统分类的相关算法进行了简要分析和介绍，重点介绍了支持向量机这种分类算法。在对传统分类方法有了了解的基础上，对不平衡数据集的分类进行了介绍，主要介绍了不平衡数据集的相关概念，并分析了不平衡数据集分类中存在的难点问题。然后介绍了现在对于不平衡数据集分类都采用了哪些相关技术，都进行了哪些改进，最后介绍了不平衡数据集分类效果的评价准则。20 第3章基于下采样的支持向晕机第3章基于下采样的支持向量机前面内容介绍过类别不平衡是指数据集中某类数据的数量远远大于其他类的数据数量，将数量多的一类称为多数类，数量少的一类称为少数类，在这里假设少数类为正类，多数类为负类。在目前对不平衡数据集中数据的处理的众多方法中上采样和下采样技术成为解决不平衡数据集分类问题中重构数据集的流行方式。本章提出一种基于聚簇的下采样方法，并通过分析得出支持向量机分类是Eh支持向量起决定作用，在不平衡数据集中多数类的支持向量数量远远多于少数类的支持向量，使用该下采样方法对支持向量机的多数类的支持向量进行下采样，然后再利用不同类惩罚支持向量机训练新数据集，以提高分类的精度。3．1不同类惩罚支持向量机支持向量机(SVM)与其他分类算法相比，对于普通数据集有较好的分类准确率。然而，SVM对于不平衡数据集分类效果却很差，会导致对正类分类的准确率降低，它更倾向于对负类的分类，导致大量的数据被错分。导致SVM对不平衡数据集失效原因之一是由于软间隔SVM自身存在的缺陷。软间隔SVM的数学形式：s伊{，@)。善yt口rK@，墨)+6}(3-1’式(3．1)是软间隔SVM的判别函数式，口；为拉格朗日系数。软间隔SVM中最优分类面问题可根据拉格朗日系数法转化为下式的最小化拉格朗日鞍点问题：。t扣M112+C套袅一塞吼[)，；(w。t)+b-1+￡]一善l‘参(3-2)式(3—2)中，口；芑0，‘20，C为惩罚常数。为满足KKT条件，口；的值需满足下面的条件：∑ai)，i-oandO0，有非零松驰变量的少数类对应的呸比有非零松驰变量的多数类的对应的口；大，这样就会将分类面推向负类。求解此对偶问题最优解口’后，可得支持向量机的决策函数为：f(x)；s印(罗a；y；七O，鼍))+6’筒为便于理解将上面这种不同类惩罚支持向量机称为C．SVM。3．2基于聚簇的下采样方法3．2．1设计思想在不平衡数据集的分类中，采样方法通过对少数类进行向上采样或者通过对多数类进行向下采样来平衡数据集。向下采样删除多数类样本，向上采样增加少数类样本。有人把训练集分成若干个子集，在每个子集里对样本进行采样，这里把每一个子集称为一 第3章基丁．F采样的支持向带机i宣iiiiiiiiiii宣iiii宣i宣iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii个聚簇，如果一个聚簇中有比较多的负类样本和比较少的正类样本，这个聚簇就可近似的看作为全是负类样本。另外，如果一个聚簇中有比较多的正类样本，比较少的负类样本，那么这个聚簇中负类样本的特征就基本不起作用，该聚簇就可近似的看作为全是正类样本。因些就需要选择一种合适的方法对样本集进行划分，因此这里考虑使用一个正类样本与负类样本数目的比率使得在每一个聚簇里有合适数量的负类样本。3．2．2算法描述基于聚簇的下采样方法(SBC)，该方法是首先把整个样本集分成若干个聚簇，这些不同的聚簇在同一个样本集中，而且每个聚簇都不相交。假设～个不平衡数据集的样本数量为Ⅳ，包括正类(少数类)样本集Ⅳ．，负类(多数类)样本集Ⅳ一，可表示为Ⅳ一Ⅳ．UⅣ一，样本集的规模用该类样本在数据集中的样本数量来决定，则正类样本集的规模即为正类样本在数据集中的数量，用S．表示，同理，负类样本集的规模即为负类样本在数据集中的数量，用S一来表示，则整个数据集S可表示为S—S．+S一。在类别不平衡的数据集中，S一远远大于S．，对负类采用下采样方法，使得数据集重构，达到训练样本集中正负类数目相对均衡的目的。该算法首先计算，．=S一／s．，在正类样本集中随机抽取正类的样本，正类样本的数目数量用s：表示，然后根据比率，．在负类数据集中随机抽取负类样本，负类样本的数量用S!表示，如此循环直到把整个样本集分成k个聚簇。聚簇Ki0墨fsk)中，在该聚簇中负类样本数量与正类样本数量的比例为s!／s：。假设需要重构的样本集中S一／s+一m(m芑1)，则在每一个聚簇中选择的负类样本数量SS!可用下式表示：SS‘。彻xs．)×攀(3．4SS)：一彻xs+)×苹生(3·)SSi|Sit智k在式(3-4)中，m×S．表示在最终训练样本集中所选择的负类的样本ussL，罗s!／s：表示在所有聚簇中负类样本与正类样本数量比率的和。舒使用式(3．4)，可以得到在每个聚簇中需要选取的多数类的样本数量，根据一定的取样规则，如根据距离，属性等加权规则等在每一个聚簇中选择出负类样本后，把所有在聚簇中选择出的负类样本合并在一起，数量基本等于m×S．，例如要求在样本集中正 类样本的数目基本均衡，就可以设为m：1t1：1，则经过该方法下采样后正负类样本的数量是基本一致的。最后，把所有的正类样本和选择出的负类样本合并成一个新的训练样本集。该下采样方法可以根据所需要的样本集的正负比例来选择多数类的数量，有比较强的灵活性，在每个聚簇中选择多数类可以根据实际情况如属性加权，距离加权等来选择。SBC算法步骤描述：输入：数据集S’输出：新数据集S’方法：(1)根据给定的样本集中正类样本与负类样本数量确定，．一S一／S+(2)根据比率厂将样本集随机分成k个聚簇，使得每个聚簇中正负样本的比率也为，．(3)根据需要重构的样本集正负类样本数目的比率m，使用公式‘躞嘶姆卜苁，计算应从每个聚二中选取的负类样本的数量豁：(4)在每个聚簇中根据一定的样本选取算法，取出相应数量的负类样本(5)每个聚簇中选取出的所有负类样本和所有正类样本合成一个新样本集S‘3．3基于下采样的支持向量机3．3．1设计思想SVM在不平衡数据集上由于训练样本数量不平衡所引起的支持向量数量不平衡和分布的不平衡是使正类样本分类准确率下降的原因。在标准数据集中SVM的最优分类超平面，两类支持向量的分布情况，如图3．1所示H为在普通数据集中SVM的最优分类面，图中的方形和圆形代表参与训练的两类样本，H为将两类样本正确分开的分类平面，在二维线性可分的分类模式中，分类平面表示为分类线。H1,H2之间的距离为分类间隔，用Margin表示。依据结构最小化风险的原则，为满足经验风险最小，要求分类线能够正确将两类样本分开，为满足实际风险最小，要求分类间隔最大。满足上述两种要求的分类线，称为最优分类线。在高维空间中，最优分类线表现为最优分类超平面。 第3章基丁下采样的支持向帚机口DH2’、图3．1标准数据集SVM的最优分类面在不平衡数据集中SVM的分类面会发生偏移，如图3．2所示。方形的点是正类。日，日，，日：是根据样本算出来的分类面，由于正类的样本很少很少，所以有一些本来是正类的样本点没有提供信息，比如图中两个空心的方形点，如果这两个点有提供信息，那算出来的分类面应该是日’，日：和H，，他们显然和之前的结果有出入，实际上正类的样本点越多，就越容易出现在空心方形点附近的点，得到的结果也就越接近于真实的分类面。但现在由于偏斜的现象存在，使得数量多的负类可以把分类面向正类的方向“推"，因而影响了结果的准确性。oO．Oo’ol-12rl图oO图3．2不平衡数据集SVM的分类面由SVM的Ⅺ灯条件，存在∑口，一∑口f。然而由于与正类样本相对应的口+在数H。＼且，m．、。。Ⅳ＼ 哈尔滨丁稃大学硕十学何论文量上远少于与负类样本相对应的a一，因此每一个a?的值一定要远大于每一个af的值。在式(3．2)所示的决策函数中，一定程度来说，正类样本相对应的口，比负类样本相对应的口f能有更大的权重影响，这也就是在数据集不平衡数据类别不均衡情况不很严重的情况下，SVM比其它分类算法在解决不平衡数据集学习问题上取得相对较好的效果。同时wh和Chang研究指出，训练集中正、负两类样本数目的不平衡比例越高，相应的正、负类的支持向量的数目不平衡比例也越高，就是在训练集中正负两类样本的数目差距越大，则正负类的支持向量的数量也相差越多p习。进一步假设：对于某个靠近分类面的测试样本(又称为边界点样本)，在其领域范围内可能会分布有更多的负类样本，因此最后得到的决策函数会把边界点附近的样本识别为负类样本。如图3．3所示为样本数量不均衡时分类面及样本分布情况。乞妒O图3．3类别不均衡分类面及样本分布情况而且通过大量研究和实验，发现在设计SVM分类器时结合下采样技术主要有以下几个优点：(1)SVM具有坚实的理论基础，分类的效果较好。(2)SVM中核矩阵求解复杂，需要计算的复杂度高，而下采样方法能够有效减少样本集中样本的数量，因此能够大大减少系统响应时间。(3)SVM物理含义较为明确，非常便于理解和用编程来实现。图3．4所示为对数据集使用下采样技术后SVM分类面及样本分布情况。当今有很多研究把SVM应用在不平衡数据集分类中以提高分类的准确率，而且采用数据采样和分类算法相融合的综合方法不仅能够充分发挥两种方法各自的优点，还能同时避免各自的缺点。 图3．4使用下采样后SVM分类效果综上所述本算法是使用SBC与SVM相结合的方法，即首先在分类算法上使用SVM对初始样本集进行训练，然后采用SBC对负类的支持向量下采样，最后利用Vcropoulos等人提出的C．SVM方法利用不同的惩罚常数将实际分类从“正样本附近"偏移一定距离使得实际分类面的形状更加接近于“理想分类面’’。使用基于聚簇的下采样方法对负类样本进行下采样，删除一部分负类样本，以达到支持向量数目的平衡，由于样本数目减少了，还能降低系统的响应速度。3．3．2算法描述由于SVM学习得到的分类面完全由支持向量所决定，使用SVM对不平衡数据集进行分类时，正类支持向量的数量远少于负类支持向量的数量，使用基于聚簇的下采样方法对负类的支持向量下采样，目的是删除一部分负类样本，减少数据集的规模，并且使数据集中正负类样本的数量相对均衡，即可减弱样本类别不平衡对分类超平面产生的影响。该算法首先给定一个不平衡数据集S，利用SVM对数据集S进行训练，得到正负类的支持向量集口=缸．，口：，．．．，口。)，正类的支持向量集a+t缸。，a：，．．．，口，)，负类的支持向量集口。=仁州，．．．，口。}。使用SBC下采样算法对负类的支持向量集中的支持向量进行下采样，由式(3．4)确定每个聚簇中选取的负类的支持向量的数目豁：，1sisk。在每一个聚簇中利用公式选取距离最优分类面最远的船!个支持向量。把所有选取出来的负类的支持向量和所有的正类支持向量，合成一个新的训练样本集S’。再利用C．SVM训练新样本集S’。算法流程图如图3．5所示。 哈尔滨T程大学硕十学位论文图3．5SBC-SVM算法SBC．SVM算法步骤：输入：数据集S输出：SBC．SVM方法：(1)输入数据集S(2)SVM对数据集s进行训练，正负类的支持向量集口一{口。，口：，．．．，口。)，正类的支持向量集口+=仁，，口：，．．．，口，}，负类的支持向量集口’一仁“，．．．，口。)(3)SBC算法对负类的支持向量集中的支持向量进行下采样，得到驱：，1sfsk(4)在每一个聚簇中利用SVM的软间隔数学形式选取距离最优分类面最远的船：个支持向量(5)把所有选取出来的负类的支持向量和所有的正类支持向量，合成一个新的支持向量集S’(6)利用C．SVM训练新样本集s’ 第3章基于’f=采样的支持向帚机3．4仿真实验3．4．1实验数据本章算法实验所用的数据集是在研究不平衡数据分类时常用的5个公开数据集，都是从http：／／www．ics．uci．edu／mleam／MLRepository．htm标准数据集中获得的，分别是abalone，glass，letter,segment，sick数据集，这五个数据集原来为多类问题，考虑计算的方便性，本实验对这五个数据集首先转换为两类问题。对于数据集的处理如下：abalone数据集选取类标号为5的一类数据作为正类，将其余的类合并为多数类，对glass数据集选取类标号为7的一类数据作为正类，其余的类合并为负类。对letter数据集选取类标号为17的一类数据作为正类，其余的类合并为负类。对segment数据集选取类标号为7的一类数据作为正类，其余的类合并为负类。对sick数据集选取类标号为2的一类数据作为正类，其余的类合并为负类。各个数据集的正负类样本不平衡率也不尽相同。具体实验数据如下表3．1所示。表3．1实验数据集；N?总样本数正样本数负样本数不平衡率abalone4177324145129．53#ass214291856．38letter200007341926626．25seqment231033019806sick3772231354115．333．4．2实验结果与分析将数据集随机的拆分成训练集和测试集，采用交叉验证的方法，将全部样本随机分为lO份，并使每份样本的不平衡率保持与整体不平衡率相等。然后每次取其中7份作为训练集，剩下的3份作为测试集。使用标准SVM，C．SVM，US．SVM以及SBC．SVM四种方法进行比较。关于如何选择正、负类样本的惩罚常数C+和C一，需要根据大量的实验数据和经验探索发现它们之间的比率。通常情况下这个比率定为训练集中样本不平衡率的倒数，即罟t矿--(Ⅳ+，N一为训练集中正负类样本的数量)，本实验即采用这一原则来确定c+和 哈尔滨T程大学硕十学何论文i宣ii宣iiii宣ii萱iiiIll．．．————．．IiiiiiiiiiiiC一的值。评价SVM分类器处理不平衡数据集问题的性能，用分类准确率作为评价指标没有实际意义，因为对于高度不平衡的数据集，比如不平衡率达到99：1或更高的时候，分类器能够将把多数类(负类)样本的分类达到99％准确程度，但这对一个处理不平衡问题的分类器来说可能完全没有意义，因为正类样本数本来就很少，99％的分类准确率，也可能意味着对正类样本的分类是100％错误。这里用召回率recall和准确率precision两个指标作为实验的评价指标，其数学形式为：recall—zP／(卵+FN)precision=TP|qP+Fn其中：砰，即，TN，FN由混淆矩阵所得，混淆矩阵如表3．2所示。表3．2混淆矩阵—、＼预测类别正类样本负类样本真实共别、、＼正类样本砰FN负类样本FP刃V以recall和precision性能为分类器评价指标的实验结果，如表3．3所示。表3．3各种分类算法评价指标(％)分类器SVMC．SVM涂芝recallprecisionrecallpreclsmn、、～abalone010088．773．Oglass74．810087．796．5letter67．O10097．3segment98．810098．9100sick010086．786．4分类器US．SVMSBC-SVM＼指标recallpreclsmnrecallprecision数据卜abalone77．553．O81．068．8glass87．788．380．8100letter99．391．999．596．3segment98．999．095．699．5sick73．575．586．287．2 第3章基丁下采样的支持向量机图3．6不同分类器在各数据集中召回率和准确率比较从图3．6中可以看出，标准的SVM在处理不平衡问题上其实已有很好的precision性能，但其recall性能表现较差，是由于SVM分类器几乎把所有样本都分为负类样本的缘故。从以上图中还可以看出无论是什么算法，在提高recall性能的同时都不可避免地牺牲了一些precision性能。因此这里引进g—mean度量准则，其数学形式为：厂了歹一厂iiF—g一7"e口n。、fTP+FN。幸VTN+FP’该度量准则将recall和precision结合在一起进行了综合考虑，比单独用recall和precision指标来评价更合理。下表是使用g—mean度量准则所得的实验结果，如表3．4所示。表3．4各分类器的g—mean实验指标(％)—、～～分类嚣SVMC．SVMUS．SVMSBC．SVM数据集—、＼abaloneO80．664．389．5glass86．692．O88．O94．1letter81．898．795．698．2segment99．599．399．197．8sick086．376．487．Omean53．5891．3884．8693．3231 哈尔滨‘I：程人学硕士学位论文10080孚6040200广————————————一———————————————]曩匿萋一蓁l匿l，歹爹≯萝≯数据集囹SVM●C—SVM口US-SⅧ口SBC—SVM图3．7各分类器在不l司数据集的分类精度比较如图3．7所示，本章提出的SBC．SVM算法和其它三种算法相比较在分类性能上有明显的优势，在五个实验数据集中提出的算法在其中的四个上取得最高的g平均测度，在剩余一个数据集中它的g值也并不逊色。3．5本章小结本章通过分析支持向量机在不平衡数据集分类中失效的原因，而且已有研究表明支持向量机分类完全是由支持向量来起作用的，通过分析得出不平衡数据集中多数类与少数类的样本数量相差很大，则支持向量的数量也相差很多，这种情况导致了分类超平面发生偏移，为了使分类超平面向最优分类面靠近，减少数据不平衡带来的影响，提出一种基于聚簇的下采样方法(SBC)，使用该下采样方法对多数类的支持向量进行下采样，删除部分多数类靠近超平面的样本，以达到两类的支持向量的数目相对均衡，然后再使用C。SVM对新样本集进行训练。该方法通过实验采用g．mean度量准则表明有较好的分类性能。32 第4章摹于数据集分解的代价敏感支持向蛩机iiiiiiiiiiiiiiiiii■ii‘——IIII—II——I—II一--一iiIIIIi第4章基于数据集分解的代价敏感支持向量机为了能有效解决不平衡数据集分类问题，机器学习领域提出了很多有效的算法。按照Estabrooksp川的观点，现在解决类不平衡问题分类的方法可大致分为两类，一类就是根据类不平衡的特点创造新方法或者对已有的方法进行改进。另一类就是通过重采样技术降低类不平衡的影响再利用现有的方法，但是重采样方法也存在一些缺陷，对样本集上采样可能会导致过学习，进行下采样可能会导致训练集中的信息丢失M。因此通过对训练集进行划分这种既不会增加训练样本的数量，也不会损失样本中的有用信息而获得一定平衡度的子集的问题，成为解决类不平衡问题的另外一种方法。综上所述本章提出一个基于训练集分解的代价敏感支持向量机分类算法。该算法首先对训练样本集进行分解，在每个子集上训练出能输出后验概率的支持向量机．对训练样本通过训练出的支持向量机得到的后验概率使用元学习过程和代价矩阵，得到样本的真实类标号，从而实现．对样本的重构，蕴含了样本的误分类代价信息，利用代价敏感支持向量机，使得对不平衡数据集进行分类，使误分类代价最小。4．1贝叶斯决策理论及启示4．1．1贝叶斯决策理论贝叶斯决策理论是主观贝叶斯派归纳理论的重要组成部分，它是由英国数学家贝叶斯创立的。在数据信息不完全的情况下，贝叶斯决策能够对未知的部分使用主观概率来估计，最后使用贝叶斯概率公式去修正已经发生的概率，最终最优的决策同期望值和修正的概率一起做出。贝叶斯决策理论的基本思想可描述为：首先是在已经知道类条件概率密度参数表达式和先验概率的前提下，使用贝叶斯概率公式将其转换为后验概率，最后利用得到的后验概率的大小来进行最优预测决策。贝叶斯使用了逆概率并把它作为一种普遍的推理方法是对统计推理的重大贡献。贝叶斯公式是对贝叶斯定理的一个数学公式表达。假定皿，B：，．．．是某个过程可能的前提条件，则P(B。)是先验概率，为对各前提条件出现可能性大小的估计。这个过程得到了一个结果A，那么贝叶斯公式提供了前提条件做出新评价的方法而根据A的出现，是对在A的前提下B的出现概率的重新估计33 哈尔滨T程大学硕十学位论文P(B，14)为后验概率。现在由贝叶斯公式及以它为基础发展起来了一整套方法和理论，在现实生活中都有着非常广泛的应用。下面是对贝叶斯公式的一个数学公式表达：贝叶斯公式：设D1，D：，．．．，峨为样本空间S的一个划分，如果P(Di)表示事件D。发生的概率，且P(B)>0，f—L2，．．．，n。对于任一事件x，P@)>0，则有：P(D小)；≠监2盟罗pOlD；)p(B)4．1．2贝叶斯决策理论分析对贝叶斯决策理论从下面几个方面进行分析：(1)训练样本集合在已知被分类类别概率分布和已经标记了类别的前提下，这时要估计概率分布的参数就需要从训练样本集合中来估计。(2)如果没有任何有关被分类类别概率分布的相关信息，但是已经知道标记了类别的训练样本集合和判别函数的形式，这时想要估计判别式函数的参数就要从样本集合中来估计。(3)在不知道任何有关被分类类别概率分布的信息，但也不知道送别函数的形式，仅仅有已经标记类别的训练样本集合，那么概率分布函数的参数就要从训练样本集合中来估计。(4)如果其它信息都没有，仅有没有被标记类别的样本集合，这时为了估计概率分布的参数，就需要对样本集合进行聚类操作。(5)一种最好的情况是，在已经知道被分类类别的概率分布时，这时不需要训练样本集合，直接使用贝叶斯决策理论就可以得到最优分类器。4．1．3启示设任一样本X属于类_『的概率为P(jlz)，贝叶斯决策论把该样本分类为i需最小化条件风险尺ol石)一∑P(小)c(f，j『)(4-1)J最小化后的条件风险称为贝叶斯风险。其中f，j『∈{c。，c：，．．．，C。)，m表示类别数；C(i，j『)表示把一个．『类样本分类为f的风险，f=．j『表示正确的分类，i乒，表示错误的分类。对基于精度是“0-1”的损失分类器，f一_『时，C(i，j『)=0，f≠．j『时，C(i，j『)=1，分 第4罩翠】‘数据集分解的代价敏感支持向苗机类的任务是寻找z的极大后验概率。在解决代价敏感数据挖掘的问题时，i≠j『时，C(i，j『)≠C(_『，D，只依靠z的后验概率来确定样本的类别是不可取的。如果给定一类样本的错分代价，就可以把代价矩阵进行重新构造。基于式(4-1)就可以来解决数据挖掘的问题，并且能使误分类的代价最小，基于以上分析说明可以使用贝叶斯决策论来实现嵌入不同类别样本有不同错分代价的代价敏感数据挖掘。4．2概率估计利用式(4．1)来实现代价敏感首先需要能估计出一个样本属于各类的概率，概率分布已知是使用贝叶斯理论的前提，就是在已知概率密度后，就可以解决所有关于统计推理的问题，但是在实际应用中，概率分布在大多数情况下是未知的，所以贝叶斯理论被直接运用是不恰当的，原因就是不确定的类条件假设和概率数据的不充分，这就导致对贝叶斯理论在实际应用中的效果影响很大。由于SVM具有坚实的理论基础和很好的泛化能力，将SVM的输出变为不再是类标号而是后验概率P(jIx)，就是将SVM确定性分类转化为不确定性分类。但是标准SVM是不输出后验概率的，Platt嘲提出了利用SVM后验概率建模的方法对已知类别样本进行SVM训练。该方法能输出后验概率还能保持支持向量稀疏性，可以利用Sigmoid函数将标准SVM的输出值映射为目标的后验P(y；=1lz)，Sigmoid函数的转换形式如下：P(Y=1lfO))=1／(1+exp(AfO)+B))其中：f(x)为标准SVM的输出结果；e(y=1I，O”表示在输出值f(x)的条件下分类正确的概率；A和B是函数中的参数，由最小化下面的对数型函数Z似，B)得到：l(A，B)--一罗(fj，log(pf)+(1一tf)log(1一Pf))筒其中，屯=丝笋，￡=五i辜历1丽，五通过交叉验证得到a同理P(Y=-1l厂O))；1／(1一exp(Af@)+B))。4．3代价最小化Domingo归q提出了一种能够将分类模型转化为代价敏感模型的新方法，称为元代价，它是一个在经过元学习过程，在已经估计出样本的类概率e(jlX)后，然后由最小期望代价来修改样本的类别标记。35 哈尔滨’T：稃大学硕十学位论文其中元学习过程是指在全局范围内，经过对局部学习所获得到的知识二次学习。对于每个独立的分散数据使用相应的学习程序是元学习的目标，并且这些程序是一起执行，最后产生相对独立的分类器，把那些分类器都合并到一起形成一个新的数据集，然后再使用一个新的学习程序对新的数据集进行运算，最后产生元知识。元学习最大的特点就是在训练阶段可以采用任何合适的算法来产生相对独立的分类器。因为使用元学习方法，在最初阶段可以采用多种集成方法，所以最后生成的元分类器能进行较高精度的预测。元学习流程图如图4．1所示：图4．1元学习元代价是一种基于Bayes决策理论的分类学习算法。算法过程为首先多次从训练集中取样，得到多个模型，再从多个模型中得到训练集中每个样本属于每个类的后验概率P(YlX)后，再计算出每个样本属于每个类别的期望代价R(jlX)，最后根据得到的最小期望代价来修改类别标记，得到一个新的数据集，从而得到新的模型，最小期望代价由，R(iIz)。P(JIX)COst(i，-『)(4．2)7训练集中的每个样本X，先得到后验概率e(jIX)，然后根据式(4．2)计算其属于每一类i的代价，进而重构x的类标记为： 第4罩基I4数据集分解的代价敏感支持向节机一r+1，矿尺(，+lM4(-1M炉1—1，D砌P刑觇该类标记带有样本的误分类代价信息，被称为样本的“真实"类标号。4．4代价敏感支持向量机由于不同的样本具有不同的误分类代价，代价敏感支持向量机【121(CS．SVM)是将不同样本的误分类代价集成到SVM的设计中，考虑每个样本都有不同的误分类代价，将原样本集：“，Y1)，02，Y2)，．．．，G。，y。)，毛ER，)，f∈{+1，一1’，i=1,2，⋯，露(4．3)重构为：xl一,Y。l，COt)，@：，y：，∞z)，．．’，Ot，)，z，cDi)，．．。，O一，yn，CO．)，(4-4)鼍∈R，yfEl+l,-1}，COf≥0,i一1,29,o．9，l其中COf为第i个样本Xi的误分类代价，为正常数，它依赖于Xl或yz。设样本集能被超平面(W·工)+6；0分类，那么基于SVM的数据不平衡问题为最小化目标函数：跏澍=扣2+c(砉c啮)(4_5)&友yf(w。赡+6)≥l一言i，舅≥O，i=1，2，⋯，刀(4-6)其中：llw28为结构代价：善cD；轰为经验代价；c为松驰因子，作用是控制结构代价和经验代价之间的平衡，为求解优化问题，构造如下拉格朗日方程：￡，=三w。w+c砉cq舅一辜：；{yzot‘w+6)一1+参卜搴三，虽‘4-7)其中：p，芝0和a；≥0为拉格朗日系数最小化式(4．7)。CS．SVM使分类面向错误分类代价相对较小的一类偏移，这样就使错分代价高的样本能被正确分类进而减小总体误分类代价。4．5基于数据集分解的代价敏感支持向量机4．5．1设计思想在使用采样的方法对数据进行处理以解决不平衡数据集分类问题时，有可能会存在在对数据集进行上采样时会由于训练样本的增加而导致过学习，而进行下采样时因为训37 哈尔溟r样大学硕十学何论文iiiiii宣iiiiiiiiiiiiiiiiiiiii宣iiii。I'1''111iiiiiiiiii宣iiiiiiiiiiiiiiiiiiiiiiiiii宣iiii宣iiiiiiiiiiiiiiiii练样本数量的减少而损失样本的分类信息。为避免上述情况，有一种方法就是对训练集进行划分，将训练集分成若干个有一定平衡度的子集，在每个子集中利用机器学习方法进行训练，然后再集成学习，这种方法既不会增：J[1{Jll练样本，也不会损失样本中有用的分类信息。当解决代价敏感数据挖掘问题时，当i-_『，co，_『)乒c(j，f)时，如果只依靠X的极大后验概率并不能确定样本的类别，当给定样本的误分类代价后，可以把代价矩阵进行重新构造，贝叶斯决策理论为实现嵌入不同误分类代价的代价敏感问题提供了一种实现的框架，就可以基于贝叶斯决策理论来实现代价敏感，使得全局的误分类代价最小。利用贝叶斯决策理论处理代价敏感问题是将数据集划分成i个子类，类别f为是子类i中得到的最小期望代价，如果相对于其他子类来说，误分类类别i的样本的代价更高的话，那么就将原来不属于子类i但在f上获得最小期望代价的一部分样本划分给予类i，这也就是修改样本的类标记来重构样本集的原因。综上分析，提出一种基于数据集分解的代价敏感支持向量机(KCS—SVM)。4．5．2算法描述设有训练集L一{@。，Y。)，．．．，O。，Y。)，Y；∈{一1，+U)，1墨i墨所，L=L+UL一，其中：正类样本集，负类样本集L一一缸州，一1)⋯．，O历，一1)}，鼍∈x∈R“，表示一个样本，n表示训练集中正类样本的数量，m一万表示训练集中负类样本的数量。在本算法中，首先把负类样本集任意分解成七：I—m-—rl1个子集。然后将分解得到的【刀J每个负类的子集L一。与正类样本集合上+合并到一起，合并得到七个训练集L；，1sfsk。训练集的正负类样本数量比例可以通过调整来控制，在每个子集上训练出来的支持向量机是能输出后验概率的。取训练样本集中的每一个样本z；∈上，，在每一个子分类器中分别得到后验概率P／(+IIz)，￡(一1Iz)，根据设定的代价矩阵利用元学习，得到训练样本的误分类代价Ri(+llx)=∑置(一xlx)‘cost(一1，+1)，R(一llx)=∑只(+1Ix)’cost(+l,一1)，取最小误分类代价min(R)，根据条件判断得到该样本的真实类标号，这样就使得该样本集成了误分类代价，采用上述方式对样本集中的每一个样本都重新获得类标号，进而重构样本集L’，因为重构的样本集集成了误分类代价，所以可以利用代价敏感支持向量机，得到一个带有误分类代价的决策函数，使得分类的总体误分类代价最小。算法流程图如图4．238 第4章基于数据集分解的代价敏感支持向镶机所示。图4．2KCS．SVM算法KCS．SVM算法步骤描述：输入：样本集L，sigrnoid函数，核函数K，代价矩阵C，负类训练集划分度k输出：代价敏感支持向量机(KcS．SVM)方法：划分：训练集三一随机分解成k个独立且规模大小相等的子集，也就是有女k罗￡．，一L一和n￡一；；妒，驴表示空集臼‘f11‘‘生成训练集：Lj；三+UL一；，l