基于改进支持向量机的数据挖掘分类算法研究

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

学校代号10731学号132081102009分类号TP274密级公开硕士学位论文基于改进支持向量机的数据挖掘分类算法研究学位申请人姓名张露培养单位电气工程与信息工程学院导师姓名及职称赵小强教授学科专业检测技术与自动化装置研究方向数据挖掘论文提交日期2016年6月7日 学校代号：10731学号：132081102009密级：公开兰州理工大学硕士学位论文基于改进支持向量机的数据挖掘分类算法研究学位申请人姓名：张露导师姓名及职称：赵小强教授培养单位：电气工程与信息工程学院专业名称：检测技术与自动化装置论文提交日期：2016年6月7日论文答辩日期：2016年5月24日答辩委员会主席：董海鹰教授 ResearchonClassificationAlgorithmofDataMiningBasedonImprovedSupportVectorMachinebyZHANGLuB.E.(ChinaJiliangUniversity)2013AthesissubmittedinpartialsatisfactionoftheRequirementsforthedegreeofMasterofEngineeringinDetectionTechniqueandAutomationDeviceintheGraduateSchoolofLanzhouUniversityofTechnologySupervisorProfessorZhaoXiaoqiangMay,2016 兰州理工大学＜学位论文原创性声明本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研巧所ｊ取得的研巧成果ｌ。除了文中特别加ｙ标注引用的内容外，本论文不包含任何其他个人或集体己经发表或撰写的成果作品。对本文的研巧做出重要贡献的个人和集体，均己在文中Ｗ明确方式标明。本人完全意识到本声明的法律后果由本人承担。如＾作者签名：＾长曰期：年／月／曰学位论文版权使用授权书ｉ本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留并向国家有关部口或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权兰州理工大学可Ｗ将本学位论文的全部或部分内容编入有关数据洁进行检索，可Ｗ采用影印、缩印或扫描等复制手段保存和汇编本学位论文。本学位论文属于１、保密□，在年解密后适用本授权书。２、不保密囚。＂＂（请在上相应方框内打Ｖ）作者签名：円期：年＾月／Ｈ导师签名策曰期；＞，／年／月曰／， 硕士学位论文目录摘要....................................................................................................................................................IAbstract.........................................................................................................................................III插图索引.........................................................................................................................................V附表索引........................................................................................................................................VI第1章绪论.....................................................................................................................................11.1研究背景和意义................................................................................................................11.2数据挖掘的研究概况.......................................................................................................21.3数据挖掘中分类算法的发展.........................................................................................21.3.1数据挖掘分类算法....................................................................................................21.3.2新型支持向量机........................................................................................................31.4本文研究主要内容............................................................................................................41.5本文组织结构.....................................................................................................................5第2章支持向量机及模糊支持向量机...................................................................................62.1支持向量机.........................................................................................................................62.1.1统计学习理论.............................................................................................................62.1.2SVM理论......................................................................................................................72.2模糊支持向量机................................................................................................................92.3本章小结...........................................................................................................................10第3章基于改进FSVM的数据挖掘分类算法.....................................................................113.1引言.......................................................................................................................................113.2基于改进FSVM的数据挖掘分类算法.........................................................................123.2.1预选有效的候选支持向量....................................................................................123.2.2一种新的模糊隶属度函数....................................................................................133.2.3基于近邻样本密度的模糊隶属度函数设计....................................................143.2.4算法步骤....................................................................................................................153.3一种改进的数据挖掘FSVM分类算法......................................................................163.3.1基本思想....................................................................................................................163.3.2粒子群优化算法......................................................................................................163.3.3编码方式....................................................................................................................163.3.4适应度函数...............................................................................................................173.3.5算法步骤....................................................................................................................173.4仿真实验和结果分析.....................................................................................................18I 基于改进支持向量机的数据挖掘分类算法研究3.4.1基于改进FSVM的数据挖掘分类算法的测试.................................................183.4.2一种改进的数据挖掘FSVM分类算法的测试.................................................203.5本章小结...........................................................................................................................22第4章基于改进球向量机的不平衡数据集分类算法......................................................234.1引言.....................................................................................................................................234.2球向量机（BVM）........................................................................................................244.2.1相关概念....................................................................................................................244.2.2球向量机实现原理..................................................................................................254.2.3BVM基本算法步骤................................................................................................254.3旋转森林算法..................................................................................................................264.4基于改进BVM的不平衡数据集分类算法...............................................................274.4.1基于改进BVM的不平衡数据集分类算法基本思想.....................................274.4.2基于改进BVM的不平衡数据集分类算法基本步骤.....................................274.5仿真实验及结果分析.....................................................................................................294.5.1评价标准....................................................................................................................294.5.2仿真实验结果及分析.............................................................................................304.6本章小结...........................................................................................................................32第5章基于SVM的高维不平衡数据集分类算法..............................................................335.1引言.....................................................................................................................................335.2改进的核SMOTE算法...................................................................................................345.3核稀疏表示特征选择算法............................................................................................355.4寻找合成样本原像.........................................................................................................365.5基于SVM的高维不平衡数据集分类算法基本步骤..............................................385.6仿真实验和结果分析.....................................................................................................405.7本章小结...........................................................................................................................42第6章结论与展望......................................................................................................................436.1结论.....................................................................................................................................436.2展望.....................................................................................................................................44参考文献........................................................................................................................................45致谢...............................................................................................................................................51附录攻读学位期间所发表的学术论文.............................................................................52II 硕士学位论文摘要随着信息技术与计算机技术的飞速发展，数据出现爆炸式增长。而这些海量的数据中隐藏着丰富的深具价值的信息和知识，如何对这些信息和知识进行有效的提取并加以利用，成为研究的重点。近年来不断发展的数据挖掘技术就是一种能够帮助人们发掘潜在有用信息的重要手段。支持向量机（SVM）作为一种有效的数据挖掘分类算法，它以统计学习理论为基础引入结构风险最小化，通过在属性空间中构建最优分类超平面获得分类器实现对未知样本的分类，具有泛化能力强，较好的非线性数据处理等优点，但也存在一些不足。本文主要围绕SVM算法展开分析与研究，主要研究成果如下：1.针对FSVM应用于数据挖掘分类中存在对大样本集训练速度慢及对噪声点敏感影响分类正确率的问题，提出了一种基于改进FSVM的数据挖掘分类算法，该算法首先利用预选候选支持向量的方法减少训练样本数目；其次定义一种新的隶属度函数增强支持向量作用，并将近邻样本密度运用于隶属度函数设计中，降低噪声点对分类的影响。试验通过与FSVM和基于类向心度的模糊支持向量机（CCD-FSVM）算法的结果对比，验证提出算法的有效性。此外针对FSVM算法进行数据挖掘分类时分类速度慢的问题，在保证分类正确率的前提下，提出了一种改进的数据挖掘FSVM分类算法。该算法使用预选候选支持向量的方法减少训练样本数目，并训练FSVM得到支持向量集；其次将粒子群优化运用到选择最优支持向量子集中，减少支持向量数目从而提高分类速度。仿真结果表明该算法在保证分类正确率的前提下，相比SVM和FSVM训练速度和分类速度更快。2.针对球向量机（BVM）虽然相较SVM具有较快的训练速度，但是当样本数目不均衡时存在分类性能较差的问题，提出了一种基于改进BVM的不平衡数据集分类算法。该算法先利用训练集分解思想对负类样本进行分解，并分别与正类样本组成平衡训练样本集，然后用旋转森林算法对得到的平衡训练样本集进行预处理并训练基分类器，最后利用集成技术对基分类器的分类结果进行集成，提高BVM的分类性能。试验通过对UCI数据集进行测试，与BVM、EStSVM、AdaBoost-SVM-OBMS和EnSVM算法进行对比，表明该算法对于不同的不平衡数据集分类结果相对稳定分类性能较高，验证了其有效性。3.针对现实生活中存在大量高维不平衡数据，但传统数据挖掘分类算法处理该分类问题时由于受到样本分布和维数的影响导致分类性能不高的问题，提出了一种基于SVM的高维不平衡数据集分类算法。该算法利用改进的核SMOTE算法合成正类样本解决样本分布不均衡的问题，然后在特征空间中运用稀疏表示的特征I 基于改进支持向量机的数据挖掘分类算法研究选择算法对高维数据集进行降维，最后寻找合成样本在输入空间的原像，运用SVM进行分类。对UCI数据集的测试结果表明，该算法能有效提高对高维不平衡数据集的分类性能。关键词：数据挖掘；分类；支持向量机；隶属度函数；不平衡数据集；旋转森林算法；核SMOTE方法II 硕士学位论文AbstractWiththerapiddevelopmentofinformationandcomputertechnology,Accumulationofdatahastakenplaceatanexplosiverate.Theremustbeabundantlatentknowledgeandinformationinthesedata,howtoextractinformationanduseinformationeffectivelybecomesthefocusofresearchers.Recently,continuallydevelopingtechnologynamedDataMiningjustcanbehelppeoplefindlatentknowledgeandinformationfromdata.AsaneffectiveDataMiningclassificationmethod,SupportVectorMachine(SVM)basedonstatisticallearningtheoryandstructuralriskminimizationcanachieveclassificationofunknownsamplesbyconstructingtheoptimalclassificationhyperplaneinattributespace.Ithasstronggeneralizationabilityandbetternonlineardataprocessingability,butitstillhassomeshortcomings.SVMisdeeplyresearchedandanalyzed,themainresearchresultsareasfollowing:1.Aimedattheproblemsofslowtrainingspeedforbigsampledata-setsandsensitivitytonoisesindataminingclassificationwithfuzzysupportvectormachine(FSVM),animprovedFSVM-basedalgorithmfordataminingclassificationisproposed.First,thisalgorithmusespreselectedcandidatesupportvectorstoreducethenumberoftrainingsamplestoimprovetrainingspeed.Second,anovelmembershipfunctionisdefinedtoenhancethefunctionofsupportvectorsinconstructionofFSVM.Finally,theneighborhoodsampledensityisappliedtothedesignofmembershipfunctiontoreducetheinfluenceofnoisesoroutliersontheclassificationtoimproveclassificationvalidity.Experimentalresultsshowthattheproposedalgorithmcanimprovetrainingspeedandclassificationaccuracy.ToovercomethedisadvantageoftestingspeedofFSVMforbigdatasetindataminingclassification,animprovedfuzzysupportvectormachineclassificationalgorithmispresented.Thealgorithmpreselectseffectivecandidatesettoreducethenumberoftrainingsamplestoimprovethetrainingspeed.Particleswarmoptimizationalgorithmisusedtooptimizesupportvectorset,averageclassificationerrorisusedasthefitnessfunction.Finally,comparethemembershipofsampleswiththethresholdvalueandselectlargemembershipofsamplesassupportvectorstoachieveimprovedthetestingspeed.Experimentalresultsshowthatthepresentedalgorithmimprovesthetrainingspeedandtestingspeedoffuzzysupportvectormachineinpremiseofguaranteeinggoodclassificationaccuracy.III 基于改进支持向量机的数据挖掘分类算法研究2.Ballvectormachine(BVM)hasfastertrainingspeedthanstandardsupportvectormachine(SVM).Butitsclassificationperformanceisbadforimbalanceddataset.Tosolvethisproblem,aclassificationalgorithmforimbalanceddatasetbasedonimprovedBVMisproposed.Theproposedalgorithmdecomposesanimbalancedtrainingdatasetandthesetisrandomlydividedthesamenumberofpositivekindofsamplesandthepositivesamplesubsets,theycomposebalancedtrainingsampleset.Thenrotationforestmethodisappliedtopreprocessnewbalancedsetandtrainthebaseclassifiers.Finally,integratedtechnologyisappliedtobaseclassifierstogetclassifiersofimbalanceddataset.BytestingandanalyzingUCIdatasets,comparingwithBVM、EStSVM、AdaBoost-SVM-OBMSandEnSVM,theproposedalgorithmcaneffectivelyimprovetheclassificationperformanceforimbalanceddataset.3.Therearealotofhigh-dimensionalandimbalancedatainreallife,butduetotheimpactofthesampledistributionanddimensions,classificationperformanceoftraditionaldataminingclassificationalgorithmsisnothigh.Tosolvethisproblem,ahigh-dimensionalandimbalanceddataclassificationalgorithmbasedonSVMisproposed.ThealgorithmfirstusesimprovedKSMOTE(KernelSyntheticMinorityOver-samplingTechnique)tocombinepositiveclasssamples.Thenfeatureselectionbasedonsparserepresentationisappliedtoselectfeatureinthefeaturespace.Finally,thesepre-imagesofthesyntheticinstancesarefoundbasedonadistancerelationininputspaceandSVMisusedtoclass.ExperimentsshowsthatproposedalgorithmcanimprovetheSVMclassificationperformanceofhigh-dimensionalandimbalanceddataset.Keywords:datamining;classification;supportvectormachine;membershipfunction;imbalanceddataset;rotationforestalgorithm;kernelSMOTEIV 硕士学位论文插图索引图2.1线性可分情况示意图.....................................................................................7图3.1预选有效的候选支持向量.........................................................................13图3.2基于类中心的隶属度函数.........................................................................13图3.3噪声点与正常样本近邻样本密度对比...................................................14图3.4FSVM的分类结果........................................................................................18图3.5CCD-FSVM的分类结果..............................................................................18图3.6本章算法的分类结果..................................................................................18图3.7SVM分类.........................................................................................................20图3.8FSVM分类......................................................................................................20图3.9本章算法分类................................................................................................21图4.1最小包围球、近似包围球、核心集图示..............................................24图4.2基于改进BVM的不平衡数据集分类算法流程图...............................28图4.3F-measure指标下的算法实验结果...........................................................31图4.4AUC指标下的算法实验结果....................................................................32图5.1KSMOTE合成样本示意图.........................................................................35图5.2三种算法的F-measure值对比....................................................................41V 基于改进支持向量机的数据挖掘分类算法研究附表索引表3.1三种算法对人工数据集的分类结果.......................................................19表3.2UCI数据集数据信息....................................................................................19表3.3三种算法对UCI数据集的分类结果........................................................19表3.4三种算法对人工数据集的分类结果.......................................................21表3.5三种算法对实际数据集的分类结果.......................................................22表4.1混淆矩阵.........................................................................................................30表4.2数据集信息.....................................................................................................31表4.3G-mean指标下的算法实验结果...............................................................31表5.1数据集信息.....................................................................................................40表5.2三种算法的G-mean值对比........................................................................41VI 硕士学位论文第1章绪论1.1研究背景和意义现今由于大量数据的累积,对于数据的有效利用已经成为我们面临的重要问题。近年来，随着人们对数据获取能力的不断提升，数据挖掘技术成为研究的重点。由于计算机技术和自动化技术的引入，工业生产中产生了大量的检测数据，复杂工业生产过程表现为多变量、非线性系统、变量间相互耦合，致使各变量间相互影响、相互制约，难以用精确的数学公式表达[1]，因此，为了从大量数据中获取有效信息，数据挖掘技术应运而生[2]。数据挖掘（DataMining）是一门交叉性的学科，融合了人工智能数据库技术、模式识别、机器学习、统计学和数据可视化等多个领域的理论和技术[3]。它的定义就是从有噪声的、随机的、不完全的、大量的数据中，提取人们事先未知的、但是有具有潜在价值的知识的过程[4]。简而言之，数据挖掘就是能够从海量数据中“挖掘”知识的技术[5,6]。描述和预测是数据挖掘的两个高层目标[7]，但是，数据挖掘仍没有统一的理论框架，目前为止，被大家公认的方法大致有以下三种[8]：统计学习理论、验证非线性方法、传统参数统计估计方法。相较于传统参数统计学理论，统计学习理论是一种关于小样本问题的数据挖掘理论框架[9]，它解决关于小样本的问题时，考虑传统参数统计估计方法的要求的同时，还建立了VC维理论体系，保证在有限信息的条件下能够寻找到最优结果，并得出了例如推广性能、一致性和收敛速度的一系列结论。Vapnik等人在上个世纪六十年代就开始对该方面进行研究[10]。直至上个世纪末，统计学习理论框架趋于成熟，但是关于经验非线性学习方法的研究仍存在理论论证不完整的问题，因此统计学习理论受到了广泛重视。数据挖掘的主要技术有：分类、聚类、关联分析、序列模式挖掘、空间数据挖掘、文本数据挖掘等。分类作为一种重要的数据挖掘算法，它的目的就是依据数据集的属性或特点构造出一个能够将未知类别的样本映射到给定类别中的某一种的分类模型或者分类函数，它在提取重要数据的类模型和预测数据中起到重要作用。由于统计学习理论已经具有较完善的理论基础和理论框架，所以许多难以解决的有限样本学习问题都迎刃而解。支持向量机(SupportVectorMachine,SVM)是Vapnik等人以统计学习理论为基础，结合结构风险最小化原则[11-15]提出来的一种有监督的学习方法，由于SVM算法在很多方面表现出的良好性能，已经得到很多人的认可，成为一种通用的方法，推动数据挖掘技术的发展。综上所述，对数据挖掘分类算法进一步研究具有重要的实际应用意义和理论1 基于改进支持向量机的数据挖掘分类算法研究价值。由于SVM泛化能力强，具有较好的非线性处理能力，所以应用广泛，但该算法存在训练速度慢、抗噪性差导致分类精度不高及分类速度慢和对不平衡数据集分类性能不高的问题，所以在有大量需要处理数据的背景下，本课题的研究具有十分重要的意义。1.2数据挖掘的研究概况数据挖掘就是对大量数据进行分析提取后挖掘出其中有意义的内在联系，1989年8月，知识发现（KnowledgeDiscoveryinDatabases,KDD）概念在第11届人工智能联合会议(ACM)上首次提出，KDD概念就是数据挖掘概念的前身[16]。首届KDD&DataMining会议于1995年在加拿大蒙特利尔召开，该会议将数据挖掘分为工程领域的数据挖掘和科研领域的知识发现，之后，每年都举行专门研究数据挖掘的KKD[17]会议。数据挖掘是一个融合了数据库技术[18]、机器学习[19]、信息检索、人工智能等多个最新技术的多学科领域，其广泛应用于各个领域，例如，银行以及保险公司对客户信息建立分类模型以此预测诈骗行为；生物学家采用数据挖掘对DNA进行分析；工程师用数据挖掘技术对故障进行分类及预测等。目前，国外数据挖掘技术的研究重点主要集中在发现知识的方法上，如对贝叶斯(Bayes)[20]、Boosting[21-22]等算法的研究和改进；传统的统计学在数据挖掘中的应用以及数据挖掘技术如何在实际问题中应用等。被应用最为广泛的数据挖掘软件有KnowledgeStudio、SPSS、SAS，主要应用于银行、电信、医药工程、保险等领域。国内数据挖掘研究相较于国外起步较晚，还处于发展阶段，最新发展主要集中在对聚类算法、分类算法和关联规则的研究，试图对海量数据进行分析处理；构造智能专家系统；研究文本挖掘理论模型等。同时也开发出了一些数据挖掘软件，例如：MSMiner、DMiner、ScopeMiner和iDMiner等。1.3数据挖掘中分类算法的发展1.3.1数据挖掘分类算法现有的分类算法有决策树、贝叶斯分类、支持向量机、基于关联规则的分类算法、神经网络算法、遗传算法、类比学习和案例学习等。决策树[23-25](decisiontree)分类算法，是一种以决策树形式表示的分类规则，该分类规则是从一组无次序、无规则的元组中推理出来的。决策树算法能够根据一定的规则将众多数据分类，并从中挖掘出那些有价值的、潜在的信息。决策树主要优点是处理大数据集的能力强，适合分类和预测型的任务，结果易于解释且2 硕士学位论文易于实施。现有的决策树分类算法有：ID3、C4.5、SLIQ(supervisedlearninginquest)、SPRINT(scalableparallelizableinductionofdecisiontrees)等。贝叶斯[26](Bayes)分类算法以概率统计知识为基础进行分类的算法。该算法简单、速度快、分类精度高，可以运用于大型数据库。因此，在很多应用中贝叶斯分类算法的分类性能与神经网络和决策树相当。现有的贝叶斯分类算法有：朴素贝叶斯(NaïveBayes，NB)算法、贝叶斯信念网络等。支持向量机算法是一种能够有效解决回归、概率密度估计、分类等问题的重要工具，它以统计学习理论为基础，具有较好的泛化能力和直观的几何解释，在图像识别、时间序列动作预测等一些实际应用中获得了较好的效果。基于关联规则分析的分类(associationclassification)算法搜索频繁模式与类标号之间的强关联，有效避免了决策树归纳一次只考虑一个属性的限制，使其比一些传统分类算法更为准确。目前主要的研究方法有三种：CBA[27](ClassificationbasedAssociation)、CMAR(ClassificationbasedonMultipleAssociationRules)和CPAR(ClassificationbasedonPredictiveAssociationRules)。神经网络[28](NeuralNetwork)算法是受神经网络和生物神经元特性的启示得到的算法，它模仿神经网络表达输入和输出的关联知识，经过非线性映射对数据进行归纳、提炼，最后并行处理为一类。它具有高度的抗干扰能力，所以在各个领域内应用广泛。遗传算法(GeneticAlgorithm)是基于进化理论的机器学习方法，它采用交叉、变异、选择等操作，实现规则的生成，已经在分类和其它一些优化问题和评估其它算法拟合度中得到了广泛应用。类比学习和案例学习，k-最近邻分类[29](k-NearestNeighborClassification)是最典型的类比学习算法，具有训练速度快但分类慢的特点。基于案例学习(Case-BasedLearning)的分类算法是对一个新案例进行分类时，通过检查已有的训练案例找出相同或最相近的案例，根据这些案例得出新案例的可能解。其它算法：粗糙集方法是对给定训练数据内部建立等价类，可以用于分类，发现噪声数据或不准确数据的结构联系；模糊集方法也称可能性理论，是传统的二值逻辑和概率论的一种替代，提供了一种处理数据的不精确测量手段。1.3.2新型支持向量机由于支持向量机具有对复杂的非线性决策边界建模能力的高度准确，以及不容易过分拟合的优点，近年来，支持向量机算法得到了长足的发展,出现了一些新型的支持向量机。-SVM是针对标准支持向量机(C-SVM)中参数C选取比较困难的问题，提出的一种用代替原来的参数C的方法，其中代表间隔错误样本的个数占总样本个3 基于改进支持向量机的数据挖掘分类算法研究数份额的上界或者下界。最小二乘支持向量机[30,31](LeastSquaresSupportVectorMachines,LS-SVM)是标准支持向量机的一种扩展，它在利用结构风险原则时，通过对优化目标选择不同损失函数使得其具有收敛速度快的优点，但当数据量较大时，求解过程所需计算资源很大。拉格朗日支持向量机[32](LSVM)是于2001年由Mangasarion等人提出来的，主要对对偶问题进行分析，先得到对偶问题的解，再由对偶问题的解求出原问题的解。该算法在线性分类的应用中，对于大样本集的分类处理相比其它算法收敛速度更快，也相对简单，但是推广到非线性问题中时，就只能处理中等规模的样本集。粒度支持向量机[33](GranularSupportVectorMachines,GSVM)的主要思想是通过粒度划分方法构建粒度空间获得一系列信息粒，然后在对每个信息粒学习后聚合其上的信息获得支持向量机。TangYC[34]等人在此基础上提出了基于关联规则的GSVM，通过径向基核函数映射原空间样本到特征空间并展开为麦克劳林级数，分析展开式中起重要作用的关联规则，并以此划分粒度，学习出关联规则分类器；张鑫[35]等人提出了基于聚类的GSVM，主要思想是运用聚类的方法划分原始数据为若干粒，选择其中信息量较多的粒参与SVM的分类。孪生支持向量机[36](TwinSupportVectorMachines，TWSVM)，又称双分界面支持向量机，具有更为快速的训练速度，使得其能够更好的处理大规模数据，但是由于TWSVM不具有标准SVM的特性，因此，对于孪生模型还需进一步的改进。排序支持向量机[37](RankingSupportVectorMachines,RSVM)对检索问题建立适用于具体应用的损伤函数。可以与标准SVM一样，两类样本使用相同的代价函数，也可以建立不同的代价函数，对一些应用的排序精度大大提高。模糊支持向量机[38,39](FuzzySupportVectorMachines,FSVM)是为了克服噪声点或野值点对SVM的影响而提出的一种将模糊数学和支持向量机结合的方法，主要是对训练样本集中存在的噪声数据，根据模糊思想对其赋于较小的权值，降低对构建最优超平面的影响。1.4本文研究主要内容本文的研究工作主要有以下几个方面：1.针对FSVM算法应用于数据挖分类中存在对大样本及训练速度慢以及对噪声点敏感影响分类正确率的问题，提出了一种基于改进FSVM的数据挖掘分类算法。该算法通过预选候选支持向量及根据近邻样本密度定义新的模糊隶属度函数，从而有效克服FSVM的缺点，通过与其它改进算法进行对比，验证了所提算法的有效性；并针对FSVM算法进行分类时存在分类速度慢的问题，提出了一种改进的数据挖掘模糊支持向量机算法。该算法先利用预选候选支持向量提高训练速度；4 硕士学位论文其次将粒子群优化算法运用到选择支持向量子集中，缩减支持向量数目，提高分类速度，通过在人工数据集和UCI数据集上验证了算法的有效性。2.针对BVM算法虽然相对标准SVM具有较快的训练速度，但是当样本集数目不均衡时分类性能较差的缺点，提出了基于改进BVM的不平衡数据集分类算法，该算法利用分解训练集的方法将负类样本集分解，并与正类样本集组成多个平衡的训练样本子集，再用旋转森林方法对各个子集进行预处理后训练基分类器，最后对基分类器分类结果进行集成，从而提高分类性能。3.针对传统数据挖掘算法对高维不平衡数据集分类时受到样本分布和维数影响导致分类性能不高的问题，提出了基于改进SVM的高维不平衡数据集分类算法，利用核SMOTE方法合成少数类样本平衡样本集，并运用稀疏表示的方法对样本进行降维处理，最终提高SVM对高维不平衡数据集的分类性能。1.5本文组织结构论文结构安排如下：第1章内容是绪论。介绍了本文的研究背景和意义，简要概述数据挖掘的研究现状，提出了本文研究的主要内容，并对本文结构安排进行了简介。第2章详细介绍了支持向量机和模糊支持向量机的相关理论。第3章详细介绍了基于改进模糊支持向量机的数据挖掘分类算法，并在人工数据集和UCI数据集上验证了改进模糊支持向量机算法比FSVM和基于类向心度的FSVM算法的优越性，加快了FSVM的训练时间，提高了分类准确率，同时经过粒子群优化算法改进后的FSVM进一步提高了其训练时间及分类时间。第4章主要针对现实生活中存在大量不平衡数据集，而传统的分类算法难以获得较高的分类精确度，提出改进BVM的不平衡数据集分类算法，结合旋转森林算法对分类结果进行投票，在UCI数据集上验证了算法的优越性。第5章提出了改进SVM的高维不平衡数据集分类算法，通过使用改进的核SMOTE合成少数类样本使两类样本数达到平衡，运用稀疏表示方法进行降维，在UCI数据集上进行测试验证了该算法的有效性。第6章对本论文的总结和今后工作的展望。5 基于改进支持向量机的数据挖掘分类算法研究第2章支持向量机及模糊支持向量机支持向量机(SVM)是于1995年由Vapnik等人提出的，它以统计学习理论为基础引入结构风险最小化，通过在属性空间中构建最优分类超平面获得分类器实现对未知样本的分类。SVM对于不是线性可分的问题，将样本通过某种变换映射到高维特征空间，并在高维空间中求取最优分类面，具有泛化能力强，较好的非线性数据处理能力等优点，在许多实际问题中应用广泛。2.1支持向量机2.1.1统计学习理论统计学习理论是一种针对小样本的统计问题所建立的理论体系，主要研究小样本条件下的机器学习规律。它的一个核心概念就是VC维，VC维是函数集学习能力的指标，VC维越大说明函数的学习能力越强。统计学习理论研究推广性的界，即训练误差与期望风险的关系，即各个函数集的经验风险及实际风险。关于两类分类问题有以下结论：对指示函数集中的所有函数，经验风险和实际风险之间至少以概率1-η满足下列关系：hln2l1lnh4R(a)＜R(a)(2.1)empl其中，h是函数集的VC维；l是样本数。该结论表明学习机器的实际风险是由两部分组成：经验风险和置信范围，可以看出过学习的原因就是：在训练样本集有限的条件下，VC维越高，复杂度度也越高，置信范围越大，实际风险与经验风险的差别也就可能越大。因此机器学习的过程在保证经验风险最小的情况下，还要尽可能的使VC维小，从而缩小置信范围，这样才可以得到比较小的期望风险，获得良好的推广性。由式(2.1)可知，只有在经验风险和置信范围都足够小的情况下，学习机器才能够具有较好的泛化能力。而对置信范围起控制作用的变量是VC维h，因此结构风险最小化原则被提出。假设函数集：SS...S...(2.2)12n其中，SQz,a,aA，在每个S中找出使得经验风险最小的假设s，得到如kknn下假设：ss...s...(2.3)12n6 硕士学位论文考察随着n的变化相应结构风险的变化情况可以得到：1）置信区间随着n的增加而增大，因为VC维是递增的。...hhh...(2.4)n1nn12）经验风险随着n的增加而减小。...Rempsn1RempsnRempsn1...(2.5)因此，结构风险最小化原则就是选择能够使置信区间与经验风险之和达到最小的n。2.1.2SVM理论支持向量机是一种以统计学习理论为基础具有较好的分类能力和泛化能力的分类算法。SVM主要有以下三种情况：(1)线性可分情况ln设训练集T=xy,...,xyxy，其中，xxR，yy1,1，11lliini1,2,...,l，如果存在wR，bR和正数，使得对于所有使y1的下标i，都有iwxib。而对于所有使yi1的下标i，都有wxib，那么称该训练集T是线性可分的，其对应的分类问题也是线性可分的，如图2.1所示。图2.1线性可分情况示意图1图2.1中的圈和叉代表待分类的两类样本，H就是要求的最优分类超平面，H1和H2是与最优分类面平行的直线且分别通过这两类样本里距离H最近的样本点。从图2.1可以看出，在H1和H2之间可以有很多条直线与它们平行，但是能够保证两类样本之间的最近距离最大的却只有最优分类超平面。SVM是一种有监督的机器学习算法，即需要通过对训练样本进行训练得到SVM获得最优分类超平面，然后根据训练结果进行分类。由图2.1可知，有分类能力的平面表述如下：wxb0s.t.wxib0yi1wxib0yi1(2.6)7 基于改进支持向量机的数据挖掘分类算法研究2可以看出，分类间隔是，要使得分类间隔最大，那么需要w尽可能小，w因此最优分类超平面可以通过求解下式得到：12minw2s.t.yiwxib1i1,2,...,l(2.7)将其转化成对偶形式：lll1minyiyjaiaj(xixj)aj2i1j1j1ls.t.yiai0i1a0,i1,2,...,l(2.8)il求解式(2.8)，得到拉格朗日系数的值a,则wyiaixi，选取a的一个正分i1l量aj,并据此计算byjyiai(xixj)，此时的分类函数为：i1fxsgnwxb(2.9)(2)线性不可分情况线性可分就是在样本存在的空间中，可以找到可能正确划分训练样本的最优分类超平面。但在现实世界中得到的样本所组成的训练样本集往往都无法找到这样一个使得所有训练样本关于分类超平面的间隔都是正值的分类超平面。然而仍然希望找到一个超平面，那么就必须适当软化条件，允许存在不满足约束条件yiwxib1的样本。因此，最优分类超平面的求解就表述为：l12minwci2i1s.t.yiwxib1-i0,i1,2,...,l(2.10)i将其转化为对偶形式为：lll1yiyjaiajxixjaj2i1j1j1ls.t.yiai0i10ac,i1,2,...,l(2.11)il求解式(2.11)，得到拉格朗日系数的值a，则wyiaixi，选取a的一个小i1l于c的正分量aj，并据此计算byjyiaixixj,此时的分类函数为：i1fxsgnwxb(2.12)对于那些需要软化的条件，将它们分为两类：一类是虽不满足KKT条件但是8 硕士学位论文可以被正确划分的点；另外一类是不满足KKT条件也不能被正确划分的点。对于第一类点，通过调整惩罚参数C来使松弛变量不取太大的值；对于第二类点，i由于该类点往往无法对提高分类器性能提供任何帮助，还会使得分类器的计算负担大大增加造成过学习现象，因此应该剔除掉。(3)非线性可分情况即便是引入了松弛变量，用直线划分有些问题还是存在很大误差，即输入空间中不存在该问题的线性分类超平面，这种问题叫非线性可分问题。处理这类问题时，通过某种映射使得训练样本线性可分，即将输入空间映射到高维空间中后，通过训练支持向量机得到该问题在高维空间中的最优分类超平面，解决该类分类问题。n设原问题对应输入空间R的训练集为：T=x1,y1,...,xi,yi(2.13)则对应的高维空间的新训练集为：Tx1y1,...,xlyl(2.14)于是相应特征空间的原始问题为：l12minwci2i1s.t.yiwxib1i0,i1,2,...,l(2.15)i转化为对偶问题为：lll1minyiyjaiajKxi,xjaj2i1j1j1ls.t.yiai0i10ac,i1,2,...,l(2.16)i其中，Kx,x=xx。ijijl对式(2.16)求解得到拉格朗日系数的值a，则wyiaixi，选取a的一个正i1l分量aj(支持向量)，并据此计算byjyiaiKxixj。i12.2模糊支持向量机模糊支持向量机[40,41]根据不同训练样本对分类贡献的不同而对其赋予不同的隶属度，从而将噪声点或野值点与有效样本区分开来。设每个样本关于其所在类的隶属度为s，则模糊化后的输入样本为：iSx1,y1,s1,x2,y2,s2,xn,yn,sn(2.17)n其中，xR为训练样本，y1,1为训练样本类别，0s1为样本的隶属度。iii9 基于改进支持向量机的数据挖掘分类算法研究因此SVM的最优超平面的求解问题就可转化为：n12minwCsii2i1s.t.y[w(x)b]10,(0,i1,2,...,n)(2.18)iiii其中，w为权值，b为偏移量，C为惩罚因子，为松弛变量。i构造拉格朗日函数求解上述优化问题，即：nnn12L(w,b,,)wCsiiiyiwxib1iii(2.19)2i1i1i1其中，,0为拉格朗日乘子。令L对变量w、b、的偏导数为零，则iiinL(w,b,,)wiyixi0(2.20)wi1nL(w,b,,)iyi0(2.21)bi1L(w,b,,)sC0(2.22)iiii将式(2.20)、(2.21)、(2.22)带入式(2.19)，求解式(2.18)的优化问题就转化为求解如下的二次规划问题，即：nnn1maxW()iijyiyjKxi,xji12i1j1ns.t.yii0(0isiC,i1,2,...,n)(2.23)i1其中，Kx,xxx为核函数。考虑KKT条件：ijijiyiwxib1i0，i1,2,...,n(2.24)siCii0,i1,2,..,n(2.25)求得决策函数为：nfxsgnwxbsgniyixi,xb(2.26)i12.3本章小结本章主要介绍了SVM以及FSVM算法的基本原理，SVM算法是一种二次规划的方法，具有泛化能力强、较好的非线性数据处理能力等优点，FSVM融合了模糊数学的思想，根据各个训练样本对分类所起作用的不同而赋予不同的隶属度，将噪声点或野值点与有效样本区分开，提高了SVM算法的抗噪性。10 硕士学位论文第3章基于改进FSVM的数据挖掘分类算法3.1引言模糊支持向量机具有泛化能力强，较好的非线性数据处理能力等优点，所以在很多应用中表现出了良好的性能，但是它也同样存在现有数据挖掘分类算法的缺点，比如对噪声点或野值点比较敏感所导致的抗噪性差，以及样本数目较大时，训练速度和分类速度较慢等。许翠云[42]等人提出了一种基于类向心度的模糊支持向量机，该方法在考虑样本与其类中心关系的同时，还考虑了各个样本之间的关系，并将类向心度与基于类中心的模糊隶属度函数结合确定新的隶属度函数，将有效点与噪声点或野值点区分开来，使得支持向量机具有较好的抗噪性能和分类能力，但该方法未能解决支持向量机训练速度慢的问题且忽略了对支持向量机构建最优分类面起重要作用的支持向量同样位于距离本类中心较远的位置，导致在降低噪声点或野值点的影响的同时，也削弱了支持向量对最优分类面构造的作用；张恒[43]等人提出了一种基于密度聚类的模糊支持向量机，该方法通过DBSCAN密度聚类对原数据集进行预处理，剔除对分类贡献较小的中心样本，用剩余的样本作为支持向量对模糊支持向量机进行训练，从而优化支持向量机，但是该方法在保留除中心样本以外的样本时，易加入噪声点或野值点容易对支持向量机的泛化能力造成影响；翟俊海[44]等人提出一种基于概率神经网络和K-L散度的样例选择，该算法将训练集进行分解为N+1个子集，并对这些子集训练概率神经网络；选择其中N个概率神经网络组成委员会，对剩余子集进行判别，通过多次迭代对所有样本都进行分类；最终运用K-L散度选择出不确定性较高的样本作为支持向量实现了对训练样本的缩减，用选择出的样本训练FSVM，提高了训练速度；此外，针对SVM分类速度慢的问题，张战成[45]等人提出了一种支持向量机的快速分类算法，该算法首先对训练标准SVM后得到的支持向量集进行模糊C均值聚类选取聚类中心作为新的支持向量集实现对支持向量的约简，并通过最小化损失函数实现在提高分类速度的同时保证分类精度；王宇[46]等人提出了一种基于卫向量的简化支持向量机模型，该算法运用几何对偶变换思想和线性规划方法提取卫向量(guard-vector)缩减训练集规模；并用缩减后的训练集训练支持向量机得到支持向量集；最后对支持向量集中的冗余支持向量进行删除，实现加快分类速度的同时不影响分类精度的目的。因此，本章针对模糊支持向量机应用于数据挖掘分类中存在对大样本集训练速度慢以及对噪声点敏感影响分类正确率的问题，提出了一种基于改进FSVM的数据挖掘分类算法，通过对数据集测试，验证该算法的有效性；并在此基础上针对模糊支持向量机存在分类速度慢的问题，提出了一种改进的数据挖掘模糊支持向量11 基于改进支持向量机的数据挖掘分类算法研究机分类算法，将粒子群优化算法运用到选择最优支持向量子集中，提高其分类速度。3.2基于改进FSVM的数据挖掘分类算法3.2.1预选有效的候选支持向量不失一般性，本章采用两类分类问题来进行说明，即训练样本为正类和负类。由于支持向量机的训练速度与训练样本集的大小相关，分布在类边界的样本即支持向量在决策中起决定作用，因此本章通过预选有效的候选支持向量来减小训练样本的数目，提高训练速度。预选有效的候选支持向量的主要是依据支持向量通常位于类边界，相对于本类其它样本来说，距离本类中心较远、异类中心较近，因此，选择互中心距离(样本与异类中心的距离)小于两类样本中心距离的样本作为有效的候选支持向量。1)线性可分情形。已知样本集为x,x,...,x，则该类样本的平均特征称为中心m，那么其中心12n为：n1mxi(3.1)ni12)非线性可分情形。已知两个向量x和y，经过非线性函数映射到特征空间H，那么这两个向量在特征空间的欧氏距离为：Hdx,yKx,x2Kx,yKy,y(3.2)其中，K()为核函数。那么特征空间样本的中心向量m为：n1mxi(3.3)ni1根据式(3.1)或(3.3)求出两类的类中心：正类中心m和负类中心m，并据此计算两类类中心的距离：D=mm(3.4)按照下式分别计算两类样本集中所有样本到异类中心m的距离，将该距离小于D的样本作为有效的候选支持向量：D'=xm(3.5)i即保留满足D'D的样本作为有效的候选支持向量，如图3.1中弧形部分的样本点。对样本进行预处理后，达到减小训练样本数目的目的，提高训练速度。12 硕士学位论文图3.1预选有效的候选支持向量13.2.2一种新的模糊隶属度函数为了减小噪声点对构建支持向量机的影响，Lin等人提出基于类中心的模糊隶属度函数[47]，该隶属度函数考虑噪声点或野值点通常位于距离类中心较远的位置，因此通过对距离类中心较远的样本赋予较小隶属度来减小噪声点或野值点的影响，但是该隶属度函数设计忽略了对支持向量机训练起重要作用的支持向量也同样位于距离类中心较远的位置，因此该隶属度函数在减小噪声点或野值点的同时也减小了支持向量的作用。如图3.2所示，传统隶属度函数使样本的隶属度随着与类中心距离的增大而减小，支持向量即图中加粗样本由于距离类中心较远而获得较小的隶属度，容易导致分类超平面偏离最优分类面。因此，本章定义了一种新的隶属度函数，使得样本的隶属度随着与类中心距离的增大而增大，即增大距离类中心较远样本对分类所起的作用，那么支持向量将会获得较大的隶属度。图3.2基于类中心的隶属度函数1由式(3.1)或式(3.3)可得正类中心m和负类中心m，每个正类样本到正类中心的距离为dxm；每个负类样本到负类中心的距离为dxm。假设经iiii过预选支持向量后正类样本集为X，负类样本集为X，则设计隶属度函数如下：di,y1,xXimaxdis(3.6)i1di,y1,xXimaxdi其中，为足够小的正数，避免出现sx0的情况。i13 基于改进支持向量机的数据挖掘分类算法研究该隶属度函数是以类中心最远的距离作为度量，使得距离类中心远的样本获得较大的隶属度，从而保证了支持向量在构建最优分类面时的作用。但是噪声点也位于距离类中心较远的区域，在增强支持向量对分类的作用的同时也有可能增强噪声点或野值点的影响。3.2.3基于近邻样本密度的模糊隶属度函数设计为了将噪声点与正常样本有效的区分开来利用近邻样本密度对隶属度函数进行加权。如图3.3所示，正常样本x在近邻范围e内样本数目多即近邻样本密度1大，而噪声点x在其近邻范围e内样本数目少即近邻样本密度小，因此可以利用2近邻样本密度对隶属度函数进行加权，在不削弱正常样本作用的同时减小噪声点的影响。图3.3噪声点与正常样本近邻样本密度对比1在本章中通过计算每个样本的近邻样本密度函数来量化其近邻样本密度[48]。对每个样本x在样本集中计算与其距离满足式(3.7)的样本x，形成样本集X中第iij个样本的近邻样本子集X。ide;i,j1,2,...,numX;ji(3.7)ij1xx,线性可分ji其中，dKx,x2Kx,xKx,x，d为两个样本x和x之间的距离，eijiiijjjijji1，非线性可分是样本近邻域范围，取min(d)emax(d)，numX为样本集中样本个数。样本ij1ij密度可以用样本近邻点之间的距离定义，假设样本的近邻样本子集X中有k个近i邻样本，则近邻样本密度函数如下：k1zi,dije1,i1,2,...,numX(3.8)ij,j1dija其中，a是很小的惩罚常量以便处理同值样本。对近邻样本密度z归一化：iziw(3.9)inumXzii1其中，z为样本集中第i个样本x的近邻样本密度，由上述内容可知，样本x在近iii14 硕士学位论文邻范围内的样本越多，w越大。i由于样本的近邻样本点的类别对该样本的所属类别所造成的影响是不同的，因此可以对近邻样本密度进行调整。若样本的近邻样本子集中全部为本类样本，则该样本与异类样本无混淆，则该近邻样本密度保持不变；当样本的近邻样本子集中包含有与样本不同类的样本时，说明该样本与异类样本有混淆，因此应根据其混淆程度对其隶属度适当减小；若样本的近邻样本都为异类样本时，则说明该样本是噪声点赋隶属度为0，减小其对构建支持向量机的作用。因此考虑近邻样本本身的类别信息，得到以下近邻样本密度：w,当近邻样本与样本x均属于同一类时；iilwiwi,当k个近邻样本中有l个样本与wik(3.10)样本x属于不同类时；i0，当近邻样本与样本xi均属于不同类时；用式(3.10)求出的近邻样本密度对新的模糊隶属度进行加权，得到最终的隶属度函数：ssw(3.11)ii1i1该隶属度函数将新的基于类中心的隶属度函数与近邻样本密度相结合，在增强支持向量作用的同时减小了噪声点对分类的影响，最终用式(3.11)得到的隶属度函数训练模糊支持向量机来对数据进行分类。3.2.4算法步骤基于改进模糊支持向量机的数据挖掘分类算法步骤如下：Step1：计算两类样本类中心点的距离D；Step2：分别计算两类样本集中每个样本与异类中心的距离D，保留距离满足DD的样本，构成预选支持向量后的样本集X(包含X和X)；Step3：对样本集X中的样本按式(3.6)分别计算其隶属度s；i1Step4：计算样本的近邻样本密度，假设经过预选后的样本数量为L，令i1；Step4.1：对X中的第i个样本按式(3.7)计算其近邻范围内的样本形成该样本的近邻子集X，并按式(3.8)求出该样本近邻范围内的样本密度z；iiStep4.2：ii1，返回Step4.1，当iL时，终止迭代，并对求得的X中所有样本的近邻样本密度按式(3.9)进行归一化得到归一化近邻样本密度w；iStep5：根据样本在近邻样本点所属的类别的不同，对w按式(3.10)进行调整i得到w；i1Step6：用近邻样本密度w对Step3中所得隶属度s进行加权得到最终隶属度i1i1s，用该隶属度训练FSVM并进行分类。i15 基于改进支持向量机的数据挖掘分类算法研究3.3一种改进的数据挖掘FSVM分类算法3.3.1基本思想目前，训练速度和分类速度较慢是限制SVM应用的主要因素，因此在3.2的基础上本节提出了一种改进的数据挖掘FSVM分类算法，运用3.2.1和3.2.2的方法对FSVM训练集进行预处理达到提高训练速度的目的，并训练FSVM得到决策函数，可以看出FSVM分类过程中，不是全部的训练样本都起作用，而是只有对偶问题的非零解对应的训练样本也即支持向量对决策函数起作用[49]。换句话说，FSVMi决策一个未知样本的复杂度为O(|l|)，当|l|即支持向量数目很大时，则计量很大，导致分类速度较慢。基于此，运用粒子群优化算法(PSO)对支持向量进行缩减，在不影响分类精度的同时提高分类速度，将训练FSVM后得到的支持向量集的模糊隶属度向量作为粒子群中的粒子，以测试集的平均分类误差作为适应度函数，选择出最优支持向量子集来缩减支持向量，从而提高分类速度。3.3.2粒子群优化算法[50]粒子群优化算法(ParticleSwarmOptimization,PSO)是于1995年由Eberhart和Kennedy提出的一种智能优化算法，该算法由于其收敛快、简单易实现、精度高等优点广泛应用于实际中。PSO算法是通过不断调整粒子的位置来搜索解的，假设D维搜索空间中，由n个粒子构成种群Xx,x,...,x，则第i个粒子的当前位置为Xx,x,...,x，粒12nii1i2in子当前的飞行速度为Vv,v,...,v，粒子i所经过的最好位置为ii1i2inPipi1,pi2,...,pin，所有粒子经过的最好位置为Pgpg1,pg2,...,pgn。则第i个粒子在t1时刻为：t1tttttvidvidc1r1pidxidc2r2pgdxid(3.12)t1tt1xxv(3.13)ididid其中，1dD；1in；r和r为均匀分布在0,1区间上的随机数；c和c称为1212学习因子，通常取cc2。123.3.3编码方式粒子群优化算法中，每个粒子代表一个解，将粒子群优化算法应用到模糊支持向量机精简支持向量中，经过训练FSVM得到的支持向量个数l为粒子的维数，按照式(3.6)对这些样本计算其隶属度，假设这些样本隶属度的范围为u,u，minmax选择该范围为初始化粒子的位置范围，将计算得到的l个样本的权重向量看成初始化粒子群空间中的一个粒子，每个粒子都有位置和速度，用位置表示样本的隶属度，速度改变隶属度值，设定一个阈值，粒子输出时，当样本隶属度值大于该阈值，让其隶属度保持原值，表示该样本被选择，否则其隶属度值赋为0，表示该16 硕士学位论文样本不被选择，因此，选择支持向量的问题就转化为选择最优粒子的PSO优化问题。3.3.4适应度函数训练集分为两部分：一部分(样本总数的70%)作为训练集，另一部分(样本总数的30%)作为测试集，对训练样本集进行处理并训练FSVM得到支持向量集，用测试集的平均分类误差作为粒子的适应值。定义适应度函数为：M12Fitnessfiyi(3.14)Mi1其中，M为测试集中的样本数目，f为预测值,y为实际值，由上式可知，粒子ii适应值越小越优。3.3.5算法步骤一种改进的数据挖掘模糊支持向量机分类算法步骤如下：输入：训练样本集S{(x,y),(x,y),...,(x,y)}1122nn输出：FSVM决策函数Step1：根据式(3.1)或式(3.2)计算正类类中心和负类类中心，并由式(3.4)求得两类类中心距离；Step2：根据式(3.5)分别计算两类样本到其类中心的距离，并选择该距离小于两类类中心距离的样本作为候选支持向量形成候选支持向量集；Step3：根据式(3.6)计算样本隶属度，得到模糊化的候选支持向量集；Step4：对模糊化的候选支持向量集训练FSVM，得到支持向量集；Step5:初始化粒子群X,其中计算得到的l个支持向量的权重向量为初始化粒子群中的一个粒子；Step6:保留粒子群中所有粒子的位置；Step7:依次判断保留的粒子位置，如果该位置大于阈值p时，则保持该位置不变，否则该位置的值改为0，选择出支持向量子集；Step8:对每个粒子选择出的支持向量子集训练FSVM，得到判决函数；Step9:根据判决函数对测试集进行测试，并按照式(3.14)计算粒子的适应度值，根据所获得的粒子适应度函数值调整粒子的个体最优位置和全局最优位置；Step10:按照式(3.12)、(3.13)更新粒子群算法，获得一组新的隶属度值；Step11:判断是否满足循环停止条件，当适应值不再变化时则结束，输出结果，否则转Step2；Step12:用输出的结果训练FSVM，得到约简支持向量后的决策函数并用该决策函数进行分类。17 基于改进支持向量机的数据挖掘分类算法研究3.4仿真实验和结果分析3.4.1基于改进FSVM的数据挖掘分类算法的测试对本章所提出的基于改进FSVM的数据挖掘分类算法进行仿真实验，并与模糊支持向量机(FSVM)以及基于类向心度的FSVM(CCD-FSVM)进行对比分析。实验中对4个人工数据集以及5个UCI数据集进行分类，实验环境为CPUInteli52.60GHz、RAM4.00GB、64位Windows8、MATLAB7.13。1）人工数据集分类不失一般性，本章用二维两类数据集对算法进行验证。本实验的训练样本集为随机产生的服从正态分布的两类二维样本，设为正类样本和负类样本，并在其中随机地加入2%的噪声数据；用随机二维样本作为测试样本，并加入1%的噪声数据。三种算法的参数选择一致(C=100)，e的选取根据样本的不同而不同，本1章选择min(d)的3~5倍。实验中随着数据集逐渐增大，三种算法的分类结果(以正ij类样本和负类样本数分别为200为例)如图3.4~3.6所示，图中“+”表示正类样本，“*”表示负类样本，由“□”标出的样本为预选候选支持向量后所要删减的样本。比较三种算法的训练速度和分类正确率(取10次实验的平均值作为结果)如表3.1所示。12121010886644YY2200-2-2-4正类样本-4正类样本负类样本负类样本-6-6-4-20246810-4-20246810XX图3.4FSVM的分类结果1图3.5CCD-FSVM的分类结果1210864Y20-2正类样本-4负类样本删减样本-6-4-20246810X图3.6本章算法的分类结果118 硕士学位论文表3.1三种算法对人工数据集的分类结果1训练时间/s准确率/%训练测试本章本章样本样本FSVMCCD-FSVMFSVMCCD-FSVM算法算法2002003.374.123.2792.1492.8793.1340030035.5445.7631.7593.2593.8694.7660040054.3769.5042.5394.5794.9795.63800500149.35179.8793.7596.2596.3396.82结合图3.4~3.6及表3.1可知，随着训练样本数目逐渐增大本章算法相比其它两种算法在训练时间和分类正确率上都有所提高，支持向量机训练时要进行大量的核矩阵运算及存储使得训练速度缓慢，而该矩阵大小与训练样本数目相关，FSVM和CCD-FSVM由于未对样本数目进行缩减所以其训练时间较长，且CCD-FSVM在算法中加入类向心度计算进行隶属度设置导致其训练速度更为缓慢，而本章算法进行了预选取候选支持向量删除了部分作用较小的样本减小训练样本数目，试验证明本章算法在隶属度设置过程的时间代价小于对删减样本进行训练的时间代价，因此预选候选支持向量有效的提高了训练时间；此外本章算法对支持向量赋予了较大隶属度增强其作用，并考虑噪声点或野值点的近邻样本密度小，对隶属度进行加权，有效的减小了噪声点或野值点的影响，达到了提高分类准确率的目的。2）UCI数据集分类本实验的数据集是来自UCI数据库中的5个UCI数据集。为了便于比较，三种算法采用相同参数(C=100)，其中数据集的数据信息如表3.2。三种算法的分类结果对比如表3.3所示。表3.2UCI数据集数据信息1数据集训练样本数测试样本数属性个数SPECT8018722Breastcancer200779Diabetes4003688Pima5682008Splice7677688由表3.3可知，随着训练样本数目逐渐增大，本章算法相比其它两种算法其训练时间有明显的缩短，在分类正确率上都有所提高。这是由于本文算法对训练样本进行了预选有效的候选支持向量处理，并结合新的隶属度函数在提高支持向量作用的同时减小了噪声点的影响，提高了训练速度和分类精确度。19 基于改进支持向量机的数据挖掘分类算法研究表3.3三种算法对UCI数据集的分类结果1训练时间/s正确率/%训练集FSVMCCD-FSVM本章算法FSVMCCD-FSVM本章算法SPECT3.193.833.0974.6775.3275.96Breastcancer4.236.174.1275.3175.5476.12Diabetes45.3271.6136.6778.8378.8579.23Pima64.6791.5349.3279.4679.4979.98Splice136.56178.4295.3783.5683.7984.413.4.2一种改进的数据挖掘FSVM分类算法的测试为验证算法的性能，对本章所提出的一种改进数据挖掘FSVM分类算法进行仿真实验，并与SVM和FSVM进行比较。实验中用1个人工数据集以及5个UCI数据集进行验证。1）人工数据分类不失一般性，本章用两类二维数据集对算法进行验证：训练样本集为随机产生的两类二维样本；测试样本同样为随机的两类二维样本。由于核函数参数的多少直接影响函数的复杂程度，而高斯函数需要确定的参数相对较少，因此，三种2算法的核函数选择均为高斯核函数(kx,xexpxx)，其中算法中的核ijij函数参数以及惩罚参数采用5折交叉验证求取最佳参数C和γ，采用网格搜索法，lui搜索范围为C25,23,...,215，=2-15，2-13,...,23。本章算法阈值i1，粒子群参pl数为cc2，r和r为均匀分布在(0,1)区间上的随机数，粒子群种群规模为20。1212三种算法的分类结果如图3.7~3.9所示(以正类样本数和负类样本数分别为200为例)，图中“+”表示正类样本，“*”表示负类样本，由“□”标出的样本为预选候选支持向量后所要删减的样本。比较三种算法的训练速度和分类正确率(取10次实验的平均值作为结果)如表3.4。1414正类样本正类样本12负类样本12负类样本10108866442200-2-2-4-4-2024681012-2024681012图3.7SVM分类1图3.8FSVM分类120 硕士学位论文14正类样本12负类样本删减样本1086420-2-4-2024681012图3.9本章算法分类1表3.4三种算法对人工数据集的分类结果1训练时间/s分类时间/s准确率/%训练测试本章本章本章样本样本SVMFSVMSVMFSVMSVMFSVM算法算法算法2002003.43.372.7319.2619.2617.4391.5692.1492.1450030043.443.3135.6746.2346.2237.6894.5194.5594.53800400150.51149.3591.24103.42103.4185.8996.2596.2596.29结合图3.7~3.9及表3.4可知，随着训练样本数目逐渐增大，本章算法相比其它两种算法在训练速度和分类速度上都有所提高且保证了其分类精度。由于支持向量机和模糊支持向量机训练时，需要多次计算及存储整个核函数矩阵，其元素个22数是n(n是样本数)，其计算复杂度是O(n)，因此，当训练样本数目较大时，它们的训练速度较慢。由表1可以看出随着训练样本数目的增加，本文算法的训练时间明显少于SVM和FSVM的训练时间，尤其是当训练样本数目为800时，本文算法的训练时间相较于SVM算法减少了59.27s，相比FSVM算法减少了58.11s，且保证了分类精度。另外可以看出，进行分类时，本文算法的分类时间明显少于SVM和FSVM，在测试样本数为400时，本文算法相比SVM和FSVM算法分类时间分别减少了17.53s和17.52s。这是因为本文算法在训练FSVM之前对训练样本进行预处理，缩减训练样本数目，从而提高了训练速度，另外由于本文算法对训练FSVM后得到的支持向量集运用粒子群优化算法对样本的隶属度进行寻优，选择使得平均分类误差较小的支持向量子集对模糊支持向量机进训练实现了对支持向量的约减，从而保证分类精确度并提高分类速度。2）UCI数据分类本实验采用UCI数据库中的3个两类数据集。为了便于比较，三种算法参数选择方法与1）一致，对3个数据集均采用10次5折交叉验证训练时间、分类时间及分类精度。表3.5中给出本章算法与其它两种算法的分类结果。21 基于改进支持向量机的数据挖掘分类算法研究表3.5三种算法对实际数据集的分类结果1训练时间/s分类时间/s准确率/%样本数据集本章本章本章数SVMFSVMSVMFSVMSVMFSVM算法算法算法Thyroid2171.941.921.8510.9810.988.1595.1795.1795.17Breast2772.132.141.9613.3313.3210.3173.6774.2374.21cancerPD66829.7429.9620.7353.9653.9749.5175.7675.7675.69Diabetes76839.5239.4927.2077.3577.3367.6878.8378.7378.75Splice1535136.56137.4283.42326.34326.34271.983.5283.5283.50由表3.5可以看出，对于数据集Thyroid、Breastcancer本文算法相比SVM和FSVM算法训练时间和分类时间基本一致，但是对于样本数较多的数据集PD、Diabetes和Splice，本文算法的训练时间和分类时间明显提高，尤其是数据集Splice，本文算法的训练时间相比SVM和FSVM分别提高了54.13s和54s，而分类时间提高了54.44s，可以看出本文算法通过预选候选支持向量缩减训练样本数目达到了提高训练速度的目的，而运用PSO对支持向量进行缩减，提高了分类速度。对于不同的数据集因为阈值的不同，选择的支持向量比率也不同，这由数据集的性质决定，有些数据集用较少的支持向量就能够达到最好的分类效果，而有些数据集则需要较多的支持向量才能够达到最好的分类效果，但其共同点是，只需要选择部分而不是全部支持向量就可以达到不损失分类准确率的目的，数据集PD相对来说精度损失了0.07%，这可能是由于数据集训练FSVM后得到的支持向量集本身就已经很稀疏，不需要再进行约减，但总体来说，本章算法在保证分类正确率基本一致的情况下，提高了训练速度和分类速度。3.5本章小结本章主要针对模糊支持向量机应用于数据挖掘分类中存在对大样本数据集训练速度及对噪声点敏感影响分类正确率的问题，提出了基于改进FSVM的数据挖掘算法，通过在人工数据集和UCI数据集上对算法进行测试，验证了算法的有效性。针对FSVM分类速度较慢的缺点，提出了一种改进的数据挖掘模糊支持向量机分类算法，将粒子群优化算法运用到选择最优支持向量子集中，缩减支持向量数目，提高分类速度，通过在数据集上验证表明，改进后的FSVM明显提高分类速度。22 硕士学位论文第4章基于改进球向量机的不平衡数据集分类算法4.1引言不平衡数据集是指样本空间中各类样本的数量分布存在不平衡的情况，即样本集中某一类或某几类样本的数目远远小于其它类样本的数目。在以往的研究中大多假设各类样本数目是均衡的，但是现实世界中，大部分领域的数据集都是不平衡数据集，例如疾病诊断[51]、故障诊断[52]、信用卡欺诈[53]和垃圾邮件检测[54]等，以疾病诊断为例，虽然只有很少一部分是病患，但我们关注的重点往往就是这部分信息，利用传统的数据挖掘分类算法会使分类性能大大降低，因此如何提高数据挖掘分类算法对不平衡数据集的分类性能具有重要的研究意义。目前对于不平衡样本集分类的主要方法有两个层面：数据层面和算法层面。数据层面，即对样本进行预处理使得其变为平衡数据集后再进行训练，主要有欠采样方法[55](under-sampling)、过采样方法[56](over-sampling)和混合采样方法[57]等，其中，欠采样方法是对多数类进行欠采样使得其与少数类样本数目基本相当组成平衡样本集；过采样方法是对少数类样本进行合成新样本以使其样本数目与多数类基本一致；混合采样是对过采样方法和欠采样方法的结合，即对少数类样本集过采样，对多数类样本集欠采样，从而得到平衡数据集。但是欠采样方法可能会丢失样本集中与分类相关的信息，过采样方法易导致过拟合现象；算法层面即调整算法使其适应不平衡数据集并得到较好的分类效果，主要有：代价敏感学习方法[58]、支持向量机算法[59]、Boosting算法[60]、Fisher线性判别分析方法[61]和Bagging算法[62]等。针对不平衡数据集的分类问题，研究者们提出了一些改进的支持向量机算法用于不平衡数据集分类，如王春玉[63]等人提出了一种基于过抽样的非平衡数据集分类方法(AdaBoost-SVM-OBMS)，该方法以SVM为基分类器，在每次Boosting迭代中标记错分样本并在错分样本与其近邻间随机产生一些新的样本点，这些新样本点与错分样本同类，并将它们加入到原训练样本集中重新学习以提高对困难样本的识别性能，但是该算法会同时生成两类错误分类样本的合成样本且没有对错误添加的合成样本进行处理，最终会导致迭代过程出现含有过多训练样本的问题；袁兴梅[64]等人提出了一种面向不平衡数据的结构化SVM集成算法(EStSVM)，该算法首先采用欠采样方法使得不平衡样本集达到平衡状态并训练结构化不平衡SVM作为基分类器，最终对基分类器进行集成来实现对不平衡样本集的分类，但是该算法中采用欠采样方法会导致多数类样本信息的丢失；TIANJ[65]等人提出了一种基于集成SVM的不平衡数据集分类算法(EnSVM)，该算法对少数类样本进行过采样处理，对多数类样本进行聚类并计算与合成少数类样本的距离，移除距离最远和最近的两个聚类，将得到的聚类分别与过采样后的少数类样本合23 基于改进支持向量机的数据挖掘分类算法研究并成为训练集训练多个SVM，最后将多个SVM进行集成得到决策函数，提高了SVM的不平衡分类性能，但是该算法采用SMOTE技术对少数类进行过采样，没有对少数类样本的分布进行考虑，直接将参数k设定为固定值，对于SMOTE近邻样本选择具有一定的盲目性。由于球向量机(BVM)可以将SVM二次规划问题转化为最小包围球问题并使用快速近似算法寻找近似最优解，因此，相比标准SVM在计算效率上得到了大大提高，可以快速的完成大数据的分类训练且可以保证分类准确率，但是，对不平衡数据集分类，BVM同样存在由于受到样本分布的影响导致分类性能较差的问题，因此本章提出了一种基于改进BVM的不平衡数据集分类算法，该算法结合分解不平衡数据集思想、旋转森林算法以及集成的思想对BVM进行改进，使得在保证两类样本信息完整性的前提下，通过旋转森林算法对构造的平衡样本集进行预处理并训练得到差异性较大的基分类器，最终对基分类器进行集成以提高BVM的不平衡数据集分类性能。4.2球向量机（BVM）球向量机[66](BVM)是由W.Tsang等人提出的一种基于最小包围球求解SVM最优化模型的近似算法，该算法将支持向量机训练算法和几何学进行结合，使得SVM的二次优化问题转化为求解最小包裹球的问题，并通过在特征空间中寻找核心向量[67](corevector)快速建立最优分类超平面。4.2.1相关概念定义4-1(包围球)：包围球问题(EnclosingBall,EB)表述为求解一个以c为球心、r为半径的球Bc,r，可以包含给定样本集S中所有的样本点，记为EBS。定义4-2(最小包围球)：对给定样本集S，可以包含样本集S中所有样本点的最小球为最小包围球(MinimumEnclosingBall,MEB)，记为MEBS。定义4-3(近似包围球)：以c为球心、r为半径的球Bc,r，若rr且MEBSSBc,1r，则球Bc,1+r为样本集S的近似包围球，记为近似MEBS。定义4-4(核心集)：对于QS，Bc,r为样本集S子集Q的最小包围球MEBQ，如果SBc,1r，则Q为S的核心集(CoreSet)。最小包围球、近似包围球、核心集如图4.1所示：图4.1最小包围球、近似包围球、核心集图示124 硕士学位论文其中，被矩形包围的样本为核心集，外球是包围所有样本的最小球，内球是包围核心集的最小包围球，外球是内球的1近似。4.2.2球向量机实现原理d给定训练集Sx,x,...,x，xR，k(x,x)((x),(x))为核函数，则求12niijij解MEB(S)表述为下面的优化问题：2B(c,r)argminr22s.t.c(x)ri(4.1)i它的对偶是一个QP问题：nnmaxt0ikiiijkiji1i,j1ns.t.i1(4.2)i1当满足式(4.3)时，对于任意一个QP问题可以看作MEB问题：k(x,x)(4.3)式(4.3)是一个常数。这样式(4.2)可以写为：nmaxt0ijkiji,j1ns.t.i1(4.4)i1同样地，两类SVM的对偶问题为：nijminij(yiyjk(xi,xj)yiyj)Ci,j1ns.t.i1,i0,i(4.5)i11,ij其中，，C是惩罚因子。对比式(4.4)和式(4.5)可知两类SVM问题与MEBij0,ij问题等价，并且MEB球心与SVM参数(权系数w，偏移量b，松弛变量)存在以下关系：c[wbC](4.6)通过式(4.6)可以由最小包围球MEB(S)的解得到SVM的解。4.2.3BVM基本算法步骤由于求解标准SVM问题等价于求解最小包围球问题，BVM是一种基于最小包围球求解SVM最优化模型的近似算法，首先将支持向量机等价为最小包围球问题，然后再将最小包围球问题转换为1近似包围球问题进行求解。BVM算法步骤如下：Step1:令S{(z)}即选择训练集S中的任一点作为初始核心集，c(z)，0000rr，t0；025 基于改进支持向量机的数据挖掘分类算法研究Step2:如果没有(z)落在B(c,(1)r)之外，则终止迭代，否则转Step3；tStep3:找到球B(c,(1)r)(0)外的任意一点(z)，生成新的核心集ttSS{(z)}；t1ttStep4:根据球心更新公式(4.7)，更新核心集S(t1)的球心c(t1)：c(z)(c(z))(4.7)t1ttttStep5:令tt1，返回Step2；利用(1)近似最小包围球思想，用上述算法求得最小包围球后根据式(4.6)反求出SVM参数。4.3旋转森林算法旋转森林(RotationForest)算法是由JuanJ.Rodriguez和LudmilaI.Kuncheva基于特征变换思想提出的集成算法[68]，由于多样性是决定集成算法分类精确度的重要属性，而旋转森林算法通过对原始样本进行一定的特征变换得到新样本，在保证分类正确率的情况下，增加基分类器之间的差异性，其基本思想如下：假设给定训练样本集X(Nn)，其中，N为样本个数，用以表示样本集中有NTT个样本x[x,x,...,x]，n为样本的特征数。Y[y,y,...,y]表示样本集X(Nn)12n12N对应的类标号，基分类器为D,...,D，F为特征集，基分类器的个数L需要预先设1L定，构建旋转森林模型步骤如下：Step1:将训练样本的特征集F无重复抽取的随机划分为K个特征子集，即每n个特征子集的特征数为M(若无法整除，则将剩余特征加入第K组)；KStep2:F表示用来训练分类器D的第j个特征子集，X表示数据集X在i,jiij'F对应的特征子集中的样本，对X进行75%的自助采样得到样本子集X，并用i,jijij该样本子集对F中的M个特征用主成分分析（PCA）进行特征变换，得到M个i,jj(1)Mj主成分：a,...,a；i,ji,jStep3:重复Step2，将得到的K个主成分存入矩阵R：ia1,a2,,aM100i,1i,1i,10a1,a2,,aM20Ri,2i,2i,2(4.8)i00a1,a2,...,aMKi,Ki,Ki,K根据原始数据特征集F的排列顺序将旋转矩阵R重排得到R(大小为Nn)，ii那么基分类器D的训练集变换为XR，并用该训练集训练基分类器D；iiiStep4:根据以上步骤训练得到L个基分类器，对于样本x，d(xR)表示基i,ji分类器D预测该样本属于类y的可能性，假设有a类，则样本x属于类y的置信ijj度(x)为：jL1j(x)di,j(xRi),j1,...,a(4.9)Li126 硕士学位论文Step5:以最大的置信度(x)来决定样本x的类别。max本章对旋转森林算法做了一些改进，将BVM作为基分类器，旨在利用旋转森林算法对训练样本进行处理并用得到的新样本训练基分类器，从而保证集成算法中基分类器具有差异性，最终得到具有较高准确率的集成分类器。由于BVM输出的决策为待测样本的类别而不是属于某一类的概率，因此本章中集成分类器的最终决策采用多数投票法，即：对于样本x，将L个基分类器投票数最多的类作为其类别，假设共有p个类标签，则决策函数如下：h(x)argmax(Counter(x))(4.10)ii1,2.,...,p其中，Counter(x)表示第i类得到的L个基分类器的票数，以得到最大投票数的类i作为样本x的类别，本章中p2。4.4基于改进BVM的不平衡数据集分类算法4.4.1基于改进BVM的不平衡数据集分类算法基本思想由于球向量机将支持向量机求解二次优化问题转化为求解最小包裹球的问题，可以高效而快速的确定一个SVM，克服SVM求解二次优化问题而导致的训练速度慢的问题，能够大大提高海量样本集下的SVM训练效率，但是在样本集分布不均衡的情况下，BVM所得到的SVM仍然会向多数类偏移，对少数类分类精度差，分类性能不高。因此，本章结合训练样本集分解思想、旋转森林算法和集成思想对其进行改进。给定两类不平衡数据集，假设正类样本集样本数目为q，负类样本集样本数目为l，将负类样本集随机分为T个子集，取Tl(如果不能整除则q将剩余样本加入第T组)，并复制T个正类样本集分别与T个负类样本子集形成T个平衡样本集，将平衡样本集作为输入样本集训练L个基分类器，由于每个平衡训练集中包含负类样本集的部分信息，为了使得负类样本信息更加全面，对T个平衡样本集都进行L个基分类器的训练，并对最终得到的TL个基分类器用多数投票法进行集成，使得集成模型的性能更优。4.4.2基于改进BVM的不平衡数据集分类算法基本步骤基于改进BVM的不平衡数据集分类算法流程图如4.2所示：27 基于改进支持向量机的数据挖掘分类算法研究图4.2基于改进BVM的不平衡数据集分类算法流程图1输入：训练集X{(x,y),...,(x,y)}，其中，x为训练样本，y(1,1)为训练11nnii样本的类标签。输出：集成分类器EnBVM。Step1：按照正负类样本集内样本数目之比确定T并将负类样本集随机分为T个子集；Step2：复制T个正类样本集分别与T个负类样本子集组合成为平衡样本集X(m1,2,...,T)；mStep3：m=1，对第m个平衡样本集X训练L个基分类器：mStep3.1：给定基分类器个数L，将样本集X的特征集F划分为K个特征子m28 硕士学位论文集；Step3.2：i=1，对第i个基分类器进行训练；Step3.3：对特征子集F(j1,...,K)对应的样本子集X进行75%的重采样得i,ji,j'到X，并用该样本子集对F进行特征变换得到M个主成分；iji,jjStep3.4：重复Step3.3K次得到旋转矩阵R，并根据原始数据特征对旋转矩i阵进行重排得到R，据此得到第i个基分类器D的训练集XR并训练基分类器iiiD：iStep3.4.1：核函数选取高斯核函数，令XR{(z)},c(z),rr,t0；i0000Step3.4.2：如果没有z落在B(c,(1)r)之外，则终止迭代转Step3.4.5，t否则，(XR)(XR){(z)}，其中，(z)为球B(c,(1)r)外的任意一点；it1ittttStep3.4.3：根据式(4.7)更新球心；Step3.4.4：tt1，转Step3.4.2；Step3.4.5：得到包围球后根据式(4.6)得到SVM的解，输出第i个基分类器BVM；Step3.5：ii1，返回Step3.3，当iL时，则终止迭代，输出L个基分类器；Step4：mm1，返回Step3，当mT时终止迭代输出TL个基分类器并对这些基分类器进行集成，按照式(4.10)得出决策函数。4.5仿真实验及结果分析为了验证本章算法的有效性，对本章所提出的算法进行仿真实验，实验中对5个UCI数据集进行分类。实验环境为CPUInteli52.60GHz、RAM4.00GB、64位Windows8、MATLAB7.13。4.5.1评价标准由于传统分类算法假设数据样本分布平衡，因此通常用分类正确率或错误率作为评估分类器性能的指标，但对于不平衡数据集来说，当样本集严重不平衡时，即使少数类样本全部错分也可以得到较高的分类正确率，因此对于不平衡样本分类器不能选择正确率来评估其性能。目前对于不平衡数据分类算法的评价方法有：基于混淆矩阵的正确率、精确度、召回率、F-Measure、G-mean、AUC、ROC曲线等。混淆矩阵(ConfusionMatrix)如表4.1所示，其中TP(TruePositives)表示正类样本判别为正类的个数，TN(TrueNegatives)表示负类样本判别为负类的个数，FN(FalseNegatives)表示误判的负类样本数目，FP(FalsePositives)表示误判的正类样本数目。几何平均准则(G-mean)[69]是常用的评价不平衡数据集分类算法的性能指标，它表明分类算法对不平衡数据集分类性能的均衡程度，可以全面体现算法的性能。利用混淆矩阵定义真正率(TPR)和真负率(TNR)，并据此得到G-mean：29 基于改进支持向量机的数据挖掘分类算法研究TPTPR(4.11)TPFNTNTNR(4.12)TNFPGmeanTPRTNR(4.13)表4.1混淆矩阵1预测正类预测负类实际正类TPFN实际负类FPTNF-Measure[70]是查全率和查准率的组合，也是评价非平衡数据集分类算法的有效指标，它体现了分类器对正类(少数类)样本的分类性能，少数类的查全率和查准率：TPrecall(4.14)TPFNTPprecision(4.15)TPFP少数类的F-Measure：2(1)recallprecisionFMeasure(4.16)2recallprecision其中，=1。ROC曲线表示分类器的真正率TPR与假正率FPR之间关系的曲线图，ROC曲线越靠近左上方且越凸则分类器性能越好。通常用ROC曲线下方的面积AUC(AreaUnderROCCurve)来表征分类器性能，AUC越大，则分类性能越强。TPTPR(4.17)TPFNFPFPR(4.18)FPTN4.5.2仿真实验结果及分析本章的实验数据为来自UCI数据库的5个数据集：Pima、Segmentation、Glass、Satimage和Yeast。表4.2给出了这5个不平衡数据集中的正负类样本数目、特征个数以及不平衡比，实验中对本章算法与BVM、AdaBoost-SVM-OBMS、EStSVM、EnSVM分别在G-mean、F-Measure、AUC三种评价指标下进行对比。为了使实验结果更有效，本实验对数据集进行10次5折交叉验证，并记录每个数据集的G-mean、F-value、AUC均值用于比较，实验结果如表4.3、图4.3及图4.4所示。本章采用的对比算法及参数设置如下：BVM(球向量机)、AdaBoost-SVM-OBMS、EStSVM、EnSVM和本章算法均采用全部训练样本集进行训练，核函数选择高斯核函数，其中，EnSVM的参数k为30 硕士学位论文不平衡比，本章算法中参数T为不平衡比，基分类器个数L10，参数K依照样本集特征个数进行设置，一般使得每个特征子集包含3个特征。上述算法中核参数和惩罚因子C的选取均采用网格搜索方法，以G-mean最大化为目标选择参数。表4.2数据集信息1数据集特征个数正类样本数目负类样本数目不平衡比Pima82685001:2Segmentation1933019801:6Glass10291851:7Satimage3653145731:9Yeast85114331:28表4.3G-mean指标下的算法实验结果1DatasetBVMAdaBoost-SVM-OBMSEStSVMEnSVM本章算法Pima0.68130.56530.62520.67620.7193Segmentation0.97310.93680.91340.98240.9756Glass0.86130.88130.90630.91670.9233Satimage0.86730.90650.84730.92450.9343Yeast0.3360.74930.65570.83560.8483由于G-mean值是衡量不平衡数据集分类算法的分类性能均衡程度的指标，由表4.3可以看出，虽然对于不同数据集各个算法的G-mean值都有较大的波动，但是对不平衡数据集Pima、Glass、Satimage和Yeast，本章算法的G-mean值明显好于其它4种算法，而对于数据集Segmentation，本章算法的G-mean值相对于G-mean值最高的EnSVM算法仅低0.0068。10.90.80.70.60.5F-M0.4easu0.3reBVM0.2AdaBoost-SVM-OBMSEStSVM0.1EnSVMOuralgorithm0PimaSegmentationGlassSatimageYeastDataSets图4.3F-Measure指标下的算法实验结果1F-Measure值是衡量分类器对正类样本分类性能的指标，由图4.3可以看出，在不同数据集上BVM对正类样本的分类性能相对较差，对于不平衡数据集Pima、Segmentation、Glass和Satimage本文算法的F-Measure值高于其它4种对比算法的31 基于改进支持向量机的数据挖掘分类算法研究F-Measure值，对于不平衡数据集Yeast，本章算法的F-Measure值稍小于F-Measure值最高的EnSVM算法。10.90.80.70.60.5AU0.4CAre0.3aBVM0.2AdaBoost-SVM-OBMSEStSVM0.1EnSVMOuralgorithm0PimaSegmentationGlassSatimageYeastDataSets图4.4AUC指标下的算法实验结果1AUC面积是表征分类器分类性能好坏的指标，AUC越大说明分类器的性能越好，由图4.4可以看出，本章算法对不平衡数据集Pima、Glass、Satimage和Yeast本章算法的AUC值明显好于其它4种算法，而对于数据集Segmentation，本章算法的AUC值稍小于具有最高AUC值的EnSVM。综上所述，本章算法对于不同不平衡数据集分类具有较好的分类性能，这是由于本章算法首先采用训练样本集分解的思想对负类样本随机划分为与正类样本数目相当的子集后分别和正类样本集组成平衡样本集，避免了AdaBoost-SVM-OBMS、EStSVM、EnSVM这三种算法采用的欠采样以及过采样技术导致的样本信息丢失或者存在过学习的问题；其次考虑集成学习中，基分类器的差异性和多样性对最终集成分类器的性能具有重要影响，选择旋转森林算法对平衡样本集进行预处理得到差异性较大的基分类器BVM；最终将多个基分类器进行集成，在保证负类样本信息完整性的前提下，形成强分类器使得BVM的不平衡分类性能得到提高。4.6本章小结本章主要介绍了球向量机的实现原理及算法步骤。针对球向量机虽然相对标准SVM具有较快的训练速度，但是当训练样本分布不均衡时存在分类性能较差的问题，提出了基于改进BVM的不平衡数据集分类算法，先对不平衡训练集进行分解，其次运用旋转森林算法对分解得到的平衡训练集进行预处理并训练基分类器，最终运用集成技术集成得到不平衡数据集分类器。通过UCI数据集验证了算法的有效性。32 硕士学位论文第5章基于SVM的高维不平衡数据集分类算法5.1引言高维不平衡数据集是指样本空间中各类样本的数量存在不平衡分布且样本具有大量属性。2005年的数据挖掘国际会议(ICDM)上，一批知名数据挖掘专家在关于未来数据挖掘研究面临的挑战性问题中指出，由于在实际中应用普遍具有大量属性的高维数据和类别分布不均匀的不平衡数据是未来数据挖掘研究的热点[71,72]。诸如网络流量监测[73]、入侵检测[74]、生物信息挖掘[75]、Web文本分类[76]以及异常检测[77]等现实数据都展现出了高维性和不平衡性双重特性，目前对于高维不平衡数据集的分类算法主要有：预处理后分类和直接分类，预处理后分类是对高维不平衡数据集进行预处理后再运用分类算法进行分类；直接分类为了避免丢失数据信息而不对数据集进行预处理直接进行分类，但当分类问题较为复杂时，建立的分类器模型也就越复杂，而要找到这样的分类器非常困难，因此如何有效提高数据挖掘分类算法对高维不平衡数据集的分类性能具有重要的研究意义。针对高维不平衡数据集的分类问题，研究者提出了一些改进的算法，如DeepaT[78]等人提出了一种基于新采样技术的高维不平衡数据集SVM分类算法，该算法分别采用改进的欠采样方法和过采样方法对多数类样本集和少数类样本集进行处理，得到平衡样本集后运用遗传算法进行特征选择实现降维，最后用处理后的样本集训练SVM并进行分类，但是由于SVM将数据样本映射到特征空间进行训练，而该算法欠采样或过采样在输入空间中进行，在不同空间处理训练样本的不一致性会影响分类性能；尹华[79]等人提出了一种基于随机森林的高维不平衡数据集分类算法，该算法通过Bagging抽样建立平衡数据集，并构建多个决策树获取各属性的重要性度量实现特征选择后训练分类器，最终对各个分类器集成进行分类，但是该算法没有对集成算法分类精度起重要作用的个体分类器之间的差异性进行考虑，有可能影响分类性能；YuH[80]等人提出了一种基于蚁群优化欠采样方法的不平衡DNA微阵列数据分类算法，该算法针对DNA微阵列数据集的高维不平衡特性，采用改进的蚁群优化算法对多数类样本进行欠采样后与少数类样本构建平衡样本集，并采用SNR(SignalNoiseRatio)实现特征选择，最后对降维后的平衡样本集进行训练SVM并分类，但是该算法采用的欠采样方法有可能导致样本信息的丢失；杨二伟[81]提出了一种基于改进过抽样算法的不平衡数据分类算法，该算法通过对SMOTE算法中的近邻样本进行划分降低噪声样本对合成样本的影响后对数据样本降维，并对平衡后的训练集训练SVM，但是该算法未考虑在不同空间处理训练样本的不一致性。支持向量机(SVM)具有坚实的理论基础和良好的推广性能，因此在很多领域33 基于改进支持向量机的数据挖掘分类算法研究中应用广泛，但是在解决不平衡数据集分类问题时，SVM由于受到样本分布的影响，导致最优分类面向少数类样本偏移，对少数类样本分类精度很低，而对多数类样本分类精度较高。此外，虽然之前的研究认为SVM对数据维数不敏感，但Pal[82]等人经过大量实验验证，SVM在高维特征空间中，其性能也会受到干扰，因此仅仅依靠SVM算法来解决高维特征空间的分类问题是不够的，还需要借助特征选择手段选择出最具代表性且最为有效的特征来实现降维。针对上述问题，本章提出一种基于SVM的高维不平衡数据集分类算法，该算法将原始数据集通过核函数映射到特征空间中，采用改进的核SMOTE算法对少数类样本进行过采样使得数据集达到平衡，并在特征空间中采用稀疏表示的方法进行特征选择实现降维，最终在输入空间中寻找合成样本的原像，训练SVM，提高其对于高维不平衡数据集的分类性能。5.2改进的核SMOTE算法对于高维不平衡数据集分类通常采用预处理方法，即对数据集进行降维和采样(欠采样或过采样)的处理，由于先进行采样可以消除不平衡，使得特征选择算法发挥正常作用[83]，因此本文对数据集采用先过采样后特征选择的过程。由于不平衡样本集中正类样本数目往往远小于负类样本数目且分布较为稀疏，数据范围较小，使得训练得到的分类超平面产生偏移，因此通常采用过采样或欠采样的方法使得两类样本数目达到平衡，曾志强[84]等人提出一种基于核SMOTE的非平衡数据集分类算法，该算法针对SVM工作在特征空间，但传统的SMOTE方法合成新样本是在输入空间，所以得到的合成样本不一定最佳的问题，在特征空间中合成正类样本使得两类样本达到平衡，该算法首先将正类样本映射到特征空间中；其次在特征空间中寻找各个正类样本的K-近邻，并运用SMOTE正类样本合成策略合成正类样本使得两类样本达到平衡；最终寻找合成样本在输入空间的原像，对预处理后得到的平衡训练集训练并进行分类。虽然核SMOTE方法考虑了SVM工作在特征空间中，解决了在不同空间处理训练样本的不一致性问题，但是该算法将正类样本K-近邻固定为K个同类近邻，没有考虑特征空间中正类样本以及其附近负类样本的分布情况，存在一定的盲目性，例如图5.1，以正类样本x为例，KSMOTE方法会求得其同类K-近邻(假设K5)1为样本x、x、x、x、x，并利用这些近邻进行合成新样本，即图5.1中的小‘○’，23456从图中可以看出核SMOTE方法合成的新样本一直处于原始正类样本所形成的范围内，无法扩展其样本数据边界，由SVM的几何解释可知，样本数据范围越小，则训练所得的分类超平面就会向正类样本偏移，易将正类样本错分为负类样本。此外，由于对SVM构建最优分类面起重要作用的是位于类边界的样本即支持向量，而在图5.1中可以看出，由x和距离其较远的近邻x合成的样本距离类边界较16远，因此对构建最优分类面的作用较小。基于此，本文提出改进的核SMOTE方法，考虑映射后样本内部的分布特性，设置近邻阈值如式(5.1)，自适应地调整核34 硕士学位论文SMOTE的近邻选择策略，提高合成正类样本的质量，即当近邻距离大于该阈值时，则用正类样本的负类近邻代替该同类近邻合成新样本，例如图5.1中以负类样本x代替正类样本x大于近邻阈值的同类近邻来合成样本，可以看到该合成样本在原1始正类样本所形成的数据范围之外，扩展正类样本数据边界，提高了新样本的质量。改进的核SMOTE采样方法首先通过核函数将所有样本映射到特征空间；其次在特征空间中寻找正类样本的同类K-近邻和异类K-近邻，根据样本内部的分布特性设置自适应近邻阈值，得到最终的K-近邻集合；最后运用SMOTE方法合成新样本。不同于核SMOTE方法，本章设定自适应近邻阈值如式(5.1)，且允许负类样本参与新正类样本的合成过程中，用于控制正类样本近邻区域并且提高合成样本的质量。Kdi,kikthreshold(5.1)K其中，K为正类样本x的近邻数目，di,k为正类样本x与其同类K-近邻p之间iiik的距离。图5.1KSMOTE合成样本示意图15.3核稀疏表示特征选择算法Pal[82]等人经过大量实验验证，在高维特征空间中SVM的性能也会受到干扰，且存在较多属性会导致数据存储及计算机处理代价较大，一些“不好”的属性会导致分类准确率下降，因此仅依靠SVM解决高维空间中的分类问题是不够的，还需要借助特征选择手段来实现降维，GiduduA[85]等人证明了特征选择对SVM分类的积极作用。此外由于SVM对于非线性可分问题，借助核技巧将样本映射到特征空间解决特征的非线性相似问题，因此本章通过对特征空间中的数据集进行稀疏重构，得到稀疏表示并构建评分机制，选择出最优特征子集，因为稀疏学习具有自然判别能力，能选择出保持原数据结构特性的“好”特征。基于稀疏分数(SparseScore)的特征选择算法[86]由于没有利用训练样本的类别信息因此其本质是一种过滤型的无监督特征选择算法，在特征空间中对数据样本进行稀疏表示，称为经验核稀疏表示(EmpiricalKernelSparseRepresentation,35 基于改进支持向量机的数据挖掘分类算法研究EKSR)，主要思想是对训练样本的d维特征通过计算得到相应的稀疏分数，并按照大小进行排列，选择前hhd个特征从而实现特征选择的目的。由GaoS[87]等人的研究可知，经验核映射与隐形核映射相比，更易分析处理核对输入空间的适宜度，因此本章在5.2中选择经验核映射方法对数据集进行映射与该步骤并不冲突。d首先，假设过采样处理后的样本集为Xx,x,...,x，其中，xR。对5.212MiM中特征空间中的新样本x进行稀疏表示，即有：ii1minSis2Ms.t.xiSixii1(5.2)Td其中，SS,...,S,0,S,...,SR是一个M维系数向量，针对每个样本向ii1ii1ii1iM量x，根据公式(5.2)得到其稀疏表示的重构系数S，即得到稀疏重构系数矩阵iiTSS1,S2,....,SM，为最大错误容忍变量，减小重构误差，Sijji表示样本集中第j个样本向量x对重构x的贡献，则样本x重构如下：jiixSxSxSxSx(5.3)ii11ii1i1ii1i1iMM其次，计算样本各个特征与稀疏表示得到的重构特征的误差情况。将此特征在所有样本上所对应的重构误差进行累加，得到它在整个样本集上各个特征的稀疏表示保留能力，若某个特征与得到的重构特征之间的误差较小，则认为该特征在整个样本集上具有比较好的稀疏表示保留能力，定义稀疏分数目标函数Sr进行计算：2MMxirSijxiri1r1Sr(5.4)M2xirri12MMM其中，xirSijxir为计算整个样本集第r维特征xij与第r维重构特征Sijxiri1i1r1M2的累积误差，xirr表示样本集第r维特征的方差情况。i1最后，根据样本集各个特征稀疏分数Sr的大小，对它们的稀疏表示保留能力进行从小到大的排序，选取Sr中较小的特征子集，达到特征选择的目的。5.4寻找合成样本原像特征空间中合成的样本表现为特征空间中原始样本的线性组合，但是由于映射未知，因此合成样本不能直接用来训练SVM，需寻找到在输入空间中使得uijOij的原像uij。由于非线性映射是未知的，因此不可能在输入空间中寻找到合成样本的精确原像u1O，只能得到其近似解。本章采用KwokJT[88]等人ijij所提的策略，利用核空间和输入空间的距离关系来寻找合成样本的原像u。ij36 硕士学位论文首先，建立输入空间与特征空间的距离关系，本章选取应用广泛的高斯核函数kx,yKxy，在特征空间中，原始正类样本集中的任一样本x到合成样l本O的距离为：ijd2O,xd2xxx,xlijlliijjil2xiijxjxixl(5.5)kxl,xl2ij1kxl,xi2ijkxl,xj22ij1kxi,xi2ij1ijkxi,xjijkxj,xj2对高斯核函数来说，x与O的原像u在特征空间中的距离du,x与lijijlijl2在输入空间的距离du,x维持以下关系：lijl2d2u,xuxlijlijlkuij,uij2kuij,xlkxl,xl22(5.6)uijxldluij,xl22exp()22exp()22222212dluij,xl2ln1dluij,xl222由于dO,xdu,x则根据式(5.5)、式(5.6)可得输入空间中样lijllijl2本点x与O原像u的距离du,x。通常确定样本点位置的过程中，样本点与其lijijlijl近邻的距离起着重要的作用，考虑核空间中合成样本O与其t个近邻ijijijijx1,x2,...,xt在输入空间中的距离。定义向量：T2222dd,d,...,d(5.7)12tij其中，dl1,2,...,t为O的原像u和其近邻x在输入空间的距离。借鉴文献[89]lijijlijijij的思想寻找O的原像u，对O的在核空间中的t个近邻x,x,...,x，ijijij12ttijijijd1ij确定它们在输入空间的原像x1,x2,...,xtR的均值xxl，并构建一个新的tl1ijijij坐标系，首先创建一个dt的矩阵Xxxx和一个tt的中心矩阵12t1TDILL(5.8)tT其中，I是一个tt的单位矩阵，L1,1,...,1为tL的向量，则矩阵XD是以x为中心的dt中心矩阵：ijijijXDxxxxxx(5.9)12t假设矩阵XD的秩为q，对其进行奇异值分解：TOV11TXDE1,E2TE11V1E1(5.10)OOV237 基于改进支持向量机的数据挖掘分类算法研究其中，Ee,e,...,e为一组标准正交列向量e组成的dq矩阵；112qiTij1V1c1,c2,...,ct为一qt矩阵，列向量cl为向量xlx在E1上的投影，此时2ij22222Tcxx,l1,2,...,t，定义一个t1的向量dc,c,...,c。为了获得ll012t2ij比较准确的原像u，距离du,x,l1,2,...,t应尽可能与式(5.7)的值相等，即：ijijl2ij2duij,xldl,l1,2,...,t(5.11)q1定义cR，并且Ecux，则1ij222ijijdluijxluijxxlx(5.12)22Tijccl2uijxxlx,l1,2,...,t将式(5.12)从1累加到t，由于XD为中心矩阵，则式(5.12)中内积项的累加和为零，累加完的等式如下：ttt2222122dltcclcdlcl，l1,2,...,t(5.13)l1l1tl12将式(5.13)中的c的表达式代入式(5.12)并重新排列可得:tijT221222xlxuijxcldlcldl，l1,2,..,t(5.14)tl1用矩阵形式表达式(5.14)得：T221T222cd0dLLd0d(5.15)tT由于为中心矩阵，因此LL0。对式(5.15)进行适当变换可得：1T12211T22cd0d1V1d0d(5.16)22最后，将c转换到输入空间的原始坐标系，可得合成样本O在输入空间的原ij像近似值：11T22uijE11V1d0dx(5.17)2获得在特征空间中合成样本的原像后，将其加入原始数据集中，增大正类样本数量，减小失衡程度。5.5基于SVM的高维不平衡数据集分类算法基本步骤本章针对传统数据挖掘分类算法对高维不平衡数据集分类性能不高的问题，提出了基于SVM的高维不平衡数据集分类算法。首先针对核SMOTE未考虑特征空间中正类样本以及其附近负类样本的分布情况，对核SMOTE方法进行改进，通过设置自适应阈值调整正类样本K近邻，允许负类近邻参与合成样本的过程，提高合成样本质量；其次考虑对于非线性可分问题，SVM会将数据样本映射到特征空间进行处理，在特征空间对高维数据集进行特征选择，选择出对分类起关键作用的特征；最后对特征空间的合成样本在输入空间中寻找原像，与原始不平衡样本38 硕士学位论文组成平衡样本，并对降维后的平衡样本训练SVM并进行分类。算法步骤：初始化：高维不平衡样本集，最近邻数目K，待合成正类样本与原正类样本数目之比N；Step1：将原始数据集通过核函数映射到特征空间中；Step2：运用改进的KSMOTE算法合成正类样本，使两类样本数目达到平衡；Step2.1：给定原始样本集中正类样本数目为TX，X；sStep2.2：若N1，则令TNT，N1，否则TT，NN；Step2.3：将原始样本集映射到特征空间中；Step2.4：令i1，在正类样本集中随机取一个正类样本x，并求其K个近邻；iStep2.4.1：对正类样本点x先求取其同类K-近邻p，再求其异类K-近邻n，iikik通常，在SMOTE算法中K5；Step2.4.2：设定近邻阈值如式(5.1)；Step2.4.3：根据式(5.18)确定正类样本x的候选近邻集合cand：iikpikifdi,kthresholdcand(5.18)iknikelse式(5.18)表示只有当di,k比近邻阈值threshold小时，正类样本近邻p才会进ik入其候选近邻集合cand，否则，为了保证cand内的数目一定且充分利用负类样ikik本信息，被排除的样本近邻将会被样本x的负类近邻n中随机采样得到的负类样iik本点代替。Step2.4.4：ii1，转到Step2.4.1，当iT时停止迭代，输出各个正类样本x的K-近邻集合D。iiStep2.5：合成新样本；Step2.5.1：i1；Step2.5.2：取第i个正类样本点x；iStep2.5.3：j=1；Step2.5.4：从正类样本点x的K-近邻集合D中随机取近邻点x，且得随机iij数random(0,1)，若同类近邻点被异类近邻点代替，则取random(0,0.5)；ijijStep2.5.5：在特征空间中合成新样本：Oijxiijxjxi(5.19)Step2.5.6：jj1，转到Step2.5.4，当jN时，停止迭代，输出合成样本集合O；ijStep2.5.7：XXO；ssijStep2.5.8：ii1，转到Step2.5.2，当iT时，停止迭代，输出所有合成样本X；sStep3：在特征空间中运用稀疏表示特征选择算法进行特征选择；39 基于改进支持向量机的数据挖掘分类算法研究Step3.1：对训练样本的d维特征通过计算得到相应的稀疏表示的重构系数；Step3.2：按式(5.6)计算样本的各个特征与利用稀疏表示重构系数得到的重构特征之间的误差情况；Step3.3：对样本的稀疏表示能力按照从小到大的顺序进行排列，选择前h个特征，实现降维；Step4：对合成样本寻找输入空间中的原像，并与原始样本集组成平衡训练集；Step5：对降维后的平衡训练集训练SVM并进行分类。算法中所涉及的核空间中样本点距离运算公式为：xixkxi,xi2kxi,xkx,x(5.20)其中，x、x为核空间中的任意两点。i5.6仿真实验和结果分析为了验证本章算法的有效性，对本章所提出的算法进行仿真实验，实验中对7个UCI数据集进行分类，实验环境为CPUInteli52.60GHz、RAM4.00GB、64位Windows8、MATLAB7.13。采用7个高维不平衡UCI数据集进行实验，表5.1中给出这7个数据集的正负类样本数目、属性个数以及不平衡比。实验对本章算法与文献[78]算法和文献[81]的算法分别在G-mean和F-measure两种指标下进行对比。为了使得实验结果更为有效，本实验对各个数据集进行10次10折交叉验证取平均值用于比较，实验结果如表5.2和图5.2所示。表5.1数据集信息1数据集属性个数正类样本数负类样本数不平衡比Segmentation1933019801:6Staimage3662558101:9SPECTFHeart45552121:4HandwrittenDigits6556250581:9HeartDisease-475132901:22Musk168101758101:6Dna-118076724191:3本章算法及各个对比算法的参数选择如下：文献[78]算法：核函数选择高斯核函数，适应度函数中N为被选中的特征数，P为总的特征数；文献[81]算法：核函数选择高斯核函数，SMOTE算法中参数K=5；本章算法：核函数选择高斯核函数，改进的KSMOTE算法中的参数K=5，N为需合成的正类样本数与原始正类样本数量之比，稀疏表示错误容忍量0.001。40 硕士学位论文对于上述算法中的惩罚参数和核函数参数都采用网格法搜索最优参数。表5.2三种算法的G-mean值对比1G-mean数据集文献[78]算法文献[81]算法本章算法Segmentation0.98110.98070.9887Satimage0.94110.93950.9559SPECTFHeart0.73870.76870.7932HandwrittenDigits0.97590.98100.9812HeartDisease-40.69890.72140.7873Musk0.76230.78420.8121Dna-10.86490.87710.8917平均值0.85180.86470.88710.90.80.70.60.5F-0.4meas0.3ure0.2文献[78]算法0.1文献[81]算法本章算法0SegSatimMuskDna-1平均值mentaageSPECTHandwHearttionFHeartrittenDiseaDigDataSetsse-4its图5.2三种算法的F-measure值对比1由表5.2及图5.2可知，文献[78]算法的平均G-means值和平均F-measure值最低，而本章算法的平均G-means值和平均F-measure值最高，本章算法仅在数据集Segmentation上的F-measure值略低于文献[81]算法，在其它数据集上都显示了其优越性，这说明本章通过在核空间中对少数类进行过采样，解决了原SMOTE方法存在由于SVM工作在特征空间而过采样在输入空间导致的过采样得到的最优不一定是最优的问题，使得合成样本更为符合原始样本在特征空间中的分布性状，另外由于本章改进KSMOTE算法考虑了核空间中正类样本和负类样本的分布情况通过自适应的调节近邻选择阈值，使得负类样本参与合成正类样本的过程，扩展了正类样本数据的边界，对因两类样本不平衡导致的使得最优分类面向正类样本偏移的问题得到纠正，使得分类器具有更高的泛化能力。另外，考虑样本属性较多导致SVM性能受到干扰，在特征空间中采用基于稀疏表示的特征选择算法对其进行降维，选择出“好”的特征参与训练和分类过程，最终提高算法对高维不平41 基于改进支持向量机的数据挖掘分类算法研究衡数据集的分类性能。5.7本章小结针对SVM对于高维不平衡数据集分类性能不高的问题，提出了一种基于SVM的高维不平衡数据分类算法，该算法首先在特征空间中采用改进的核SMOTE方法对正类样本进行合成，使得两类样本数目达到平衡；其次考虑样本属性较多对SVM会造成干扰，在特征空间中采用基于稀疏表示的特征选择算法进行特征选择实现降维；最终通过输入空间和特征空间的距离关系来寻找合成样本在输入空间的原像，并对预处理后的数据集进行训练SVM。在UCI数据集上验证了算法对高维不平衡数据集分类问题的有效性。42 硕士学位论文第6章结论与展望6.1结论随着信息技术以及计算机技术的不断发展，大量的数据信息充斥于人们生活的方方面面，而如何有效提取出这些信息并对其加以利用至关重要。分类算法作为一种重要而有效的数据挖掘方法，成为了研究的重点，并在各个领域里得到广泛应用。本文主要研究了支持向量机、模糊支持向量机和球向量机这三种分类算法，针对它们的不足，进行讨论、研究以及改进，进一步完善算法，主要取得了以下成果：1.有效克服了FSVM运用于大样本数据集进行分类时训练速度慢和分类精确度不高的不足。FSVM算法虽然具有泛化能力强、较好的非线性数据处理能力等优点，但存在应用于数据挖掘分类中存在对大样本集训练速度慢以及对噪声点敏感影响分类正确率的问题，针对上述问题，提出了一种基于改进FSVM的数据挖掘分类算法。该算法首先预选有效的候选支持向量，减小训练样本数目，提高训练速度；其次定义了一种新的隶属度函数，增强支持向量对构建模糊支持向量机的作用；最后将近邻样本密度应用于隶属度函数设计，降低噪声点或野值点对分类的影响提高分类正确率。通过与FSVM和CCD-FSVM算法进行对比，仿真实验结果表明，本文提出的算法在训练样本数目较大时训练速度和分类正确率都有提高，另外，对经过预选的训练样本集进行训练FSVM得到支持向量集，运用粒子群优化算法选择最优支持向量子集，使用平均分类误差作为适应度函数，最终粒子输出时，将样本隶属度与设定阈值相比较，选择出支持向量集中相对较大隶属度的样本作为新的支持向量，提高分类速度。实验结果表明，本文提出的算法在不损失分类精度的情况下，提高了模糊支持向量机的训练速度和分类速度。2.改善了BVM算法对不平衡数据集的分类性能不高的问题。球向量机(BVM)虽然相对标准SVM具有较快的训练速度，但是当训练集样本分布不平衡时存在分类性能较差的问题，针对该问题，提出了一种基于改进BVM的不平衡数据集分类算法。该算法首先对不平衡训练集进行分解，将负类样本集随机划分为与正类样本集样本数目相等的T个子集，复制T个正类样本集分别与T个负类样本子集组成平衡训练样本集；其次运用旋转森林算法对得到的平衡训练样本集进行预处理并用该样本集训练L个基分类器(BVM)；对所有平衡子集进43 基于改进支持向量机的数据挖掘分类算法研究行训练并利用集成技术对得到的TL个基分类器进行集成得到不平衡数据集分类器。通过对UCI数据集测试以及理论分析，本文算法可有效地提高BVM对于不平衡数据集的分类性能。3.改善了SVM对高维不平衡数据集分类时分类性能不高的问题针对SVM对高维不平衡数据集分类时分类性能不高的问题，提出了基于SVM的高维不平衡数据集分类算法，该算法首先将原始不平衡数据集通过核函数映射到特征空间中，运用改进的核SMOTE(SyntheticMinorityOver-samplingTechnique)算法在特征空间中合成正类样本使得两类样本数目达到平衡；其次在特征空间中运用稀疏表示的特征选择算法对高维数据集进行降维；最后通过输入空间和特征空间的距离关系来寻找合成样本在输入空间的原像，并对处理后的平衡样本集训练SVM，从而提高SVM对高维不平衡数据集的分类性能，实验证明，本文算法提高了SVM对高维不平衡数据集的分类性能。6.2展望目前，SVM具有泛化能力强，较好的非线性处理能力，得到了诸多学者的关注，成为数据挖掘分类算法研究的热点之一，并在很多领域里得到广泛应用。但对SVM算法的研究远未达到成熟的阶段，还有许多方面值得深入研究和讨论。可从以下几个方面作进一步讨论和研究。1.加深算法理论方面的研究。分析与探讨支持向量机是否存在进一步加强其分类精度的可能；2.对具有快速的训练速度的孪生支持向量机的孪生模型进行进一步的研究和改进；3.尝试对新型SVM进行改进使其能够更好的运用于不平衡数据集分类中；4.分类高维数据集时，由于特征空间大，产生的分类器复杂，数据容易过度拟合；分类不平衡数据集时，基于假设类别平衡的分类算法容易忽略被关注的少数类，导致少数类分类精度不高；对高维不平衡数据集分类时，高维和不平衡展现了两种不同的特性，应该先处理哪种特性，会不会对分类性能造成影响，另外，预处理后，将损失一定的属性和实例信息，如果这些信息是有用的，那么分类性能将会受到怎样的影响，这都是需要进一步研究的问题。5.加强算法的应用研究。将SVM算法应用于更多的实际工程领域。44 硕士学位论文参考文献[1]田志强,黄孝彬.工业生产过程的数据挖掘[J].控制工程,2009,16(S0):120-123[2]LiHC,WuXP,ChenY.K-meansclusteringmethodpreservingdifferentialprivacyinMapReduceframework[J].JournalonCommunications,2016,37(2):124-130[3]王继娜.浅谈数据挖掘与知识发现[J].内蒙古科技与经济,2013,11:104-105[4]毛国君.数据挖掘原理与算法[M].北京:清华大学出版社,2005[5]HanJW,MachelineK.Dataminingconceptsandtechniques[M].范明,孟小峰译.北京:机械出版社,2006[6]王梦雪.数据挖掘综述[J].软件导刊,2013,12(10):135-137[7]钟晓,马少平,张钹等.数据挖掘综述[J].统计与信息论坛,2007,22(5):105-112[8]FilipM,VapnikC.LearningTheoryanditsapplications[J].IEEEtransactiononNeuralNetworks,1999,10(5):985-987[9]ZhuF,ShiWB,WeiJF.OptimizationofSVMparametersbasedonartificialimmunealgorithm[J].InternationalJournalofDigitalControlTechnologyanditsApplications,2012,6(22):392-399[10]ZhangX.Introductiontostatisticallearningtheoryandsupportvectormachines[J].ActaAutomaticaSinica,2000,26(1):32-42[11]VladimrV.Thenatureofstatisticallearningtheory[M].张学工译.北京:清华大学出版社,2004[12]翟俊海,王婷婷,王熙照.样例约简支持向量机[J].计算机科学与探索,2011,5(12):1131-1138[13]丁世飞,齐丙娟,谭红艳.支持向量机理论与算法研究综述[J].电子科技大学学报,2011,1:2-4[14]郭明玮,赵宇宙,项俊平等.基于支持向量机的目标检测算法综述[J].控制与决策,2014,29(2):193-200[15]陈凯,朱钰.机器学习及其相关算法综述[J].统计与信息论坛,2007,22(5):105-112[16]VladimirVN.Estimationofdependencebasedonempirical[M].NewYork:Springe-Verlag,2006[17]梁循.数据挖掘算法与应用[M].北京:北京大学出版社,2006[18]杨晓君.数据库技术发展概述[J].科技情报开发与经济,2011,21(3):152-154[19]何清,李宁,罗文娟等.大数据下的机器学习算法综述[J].模式识别与人工智45 基于改进支持向量机的数据挖掘分类算法研究能,2014,27(4):327-336[20]高晓光,陈海洋,史建国.变结构动态贝叶斯网络的机制研究[J].自动化学报,2011,37(12):1435-1444[21]张超,宗光华.一种基于SVM-Boosting分类器的颜色识别方法[J].计算机与现代化,2013,9:98-101[22]赵晨阳,佀洁.一种半监督的多标签Boosting分类算法[J].计算机应用研究,2012,29(9):3266-3268[23]刘晓娜,封志明,姜鲁光.基于决策树分类的橡胶林地遥感识别[J].农业工程学报,2013,29(24):163-173[24]饶萍,王建力,王勇.基于多特征决策树的建设用地信息提取[J].农业工程学报,2014,30(12):233-240[25]杨静,张楠男,李建等.决策树算法的研究与应用[J].计算机技术与发展,2010,20(2):114-117[26]王国才.朴素贝叶斯分类器的研究与应用[D].重庆交通大学,2010[27]毛宇星,陈彤兵,施伯乐.一种高效的多层和概化关联规则挖掘方法[J].软件学报,2011,22(12):2965-2980[28]TezelG.Anewapproachforepilepticseizuredetectionusingadaptiveneuralnetwork[J].ExpertSystemswithApplications,2009,36(1):172-180[29]张晓燕,张化祥,计华.用于不平衡数据集分类的KNN算法[J].计算机工程与应用,2011,47(28):143-145[30]DengSG,YehTH.Usingleastsquaressupportvectormachinestotheproductcostestimation[J].JournalofChungChengInstituteofTechnology,2011,40(1):1-16[31]万辉,魏延.一种改进的最小二乘支持向量机算法[J].重庆师范大学学报,2010,27(4):69-72[32]汪海燕,黎建辉,杨风雷.支持向量机理论及其算法研究综述[J].计算机应用研究,2014,31(5):1281-1286[33]RuanJH,WangXP,ShiY.Developingfastpredictorsforlarge-scaletimeseriesusingfuzzygranularsupportvectormachines[J].AppliedSoftComputingJournal,2013,13(9):3981-4000[34]TangYC,JinB,ZhangYQ.Granularsupportvectormachineswithassociationrulesminingforproteinhomologyprediction[J].ArtificialIntelligenceinMedicine,2005,35(1):121-134[35]张鑫,王文剑.一种基于粒度的支持向量机学习策略[J].计算机科学,2008,35(8a):101-10346 硕士学位论文[36]ChenSG,XuJ.Leastsquarestwinsupportvectormachineformulti-classclassification[J].InternationalJournalofDatabaseTheoryandApplication,2015,8(5):65-76[37]ThuyNTT,VinhNTN,VienNA.Nomogramvisualizationforrankingsupportvectormachine[J].LectureNotesinComputerScience,2011,6676(2):94-102[38]ZhangJH,MaWP,MaL,etal.Faultdiagnosismodelbasedonfuzzysupporvectormachinecombinedwithweightedfuzzyclustering[J].TransactionsofTianjinUniversity,2013,19(3):174-181[39]TangH,LiaoYH,SunF,etal.Fuzzysupportvectormachinewithanewfuzzymembershipfunction[J].JournalofXi’anJiaotongUniversity,2009,43(7):40-43[40]LiK,LuXX.Aroughmarginbasedfuzzysupportvectormachine[J].ActaElectronicaSinica,2013,41(6):1183-1187[41]ZhangGQ,XuWH,YangZY.Anewfuzzysupportvectormachinealgorithm[J].SoftwareSpace,2010,26(10):217-218[42]许翠云,业宁.基于类向心度的模糊支持向量机[J].计算机工程与科学,2014,36(8):1623-1628[43]张恒,邹开其,崔杰等.一种改进的基于密度聚类模糊支持向量机[J].计算机工程,2009,35(5):194-196[44]翟俊海,李畅,李塔等.基于概率神经网络和K-L散度的样例选择[J].计算机应用研究,2014,31(1):63-65[45]张战成,王士同,邓赵红等.一种支持向量机的快速分类算法[J].控制与决策,2012,27(3):459-463[46]王宇,毛玉欣.一种基于卫向量的简化支持向量机模型[J].大连理工大学学报,2008,48(3):446-450[47]QiangY,PeiB,ZhaoJJ,etal.Classificationonpulmonarynodulesbasedonafuzzysupportvectormachine[J].JournalofTsinghuaUniversity,2014,54(3):354-359[48]LiuXF,HeBB.RemotesensingimageclassificationbasedonneighborsampledensityandmembershipweightedFCMalgorithm[J].JournalofScientificInstrument,2011,32(10):2242-2247[49]邓乃扬,田英杰.支持向量机理论、算法与拓展[M].北京:科学出版社,2009[50]KennedyJ,EberhartR.Particleswarmoptimization[J].SwarmIntelligence,2007,1:33-57[51]FidaB,NazirM,NaveedN,etal.Heartdiseaseclassificationensembleoptimizationusinggeneticalgorithm[C].In:Proceedingsofthe14thIEEE47 基于改进支持向量机的数据挖掘分类算法研究InternationalMultitopicConference.Karachi:IEEEPress,2011:19-24[52]高志勇,霍伟汉,高建民等.化工系统海量数据的扩散映射和异常辨识[J].计算机集成制造系统,2014,20(12):3091-3096[53]NaderM,EkremD.Detectingcreditcardfraudbymodifiedfisherdiscriminantanalysis[J].ExpertSystemswithApplications,2015,42(5):2510-2516[54]TsengCY,ChenMY.IncrementalSVMmodelforspamdetectionindynamicemailsocialnetworks[C].In:Proceedings12thIEEEInternationalConferenceonComputationalScienceandEngineering.Vancouver:IEEEPress,2009,4:128-135[55]JaneYS,ShiLY.Cluster-basedunder-samplingapproachesforimbalanceddatadistributions[J].ExpertSystemwithApplications,2009,36(3):5718-5727[56]楼晓俊,孙雨轩,刘海涛.聚类边界过采样不平衡数据分类方法[J].浙江大学学报,2013,47(6):944-950[57]古平,欧阳源遊.基于混合采样的非平衡数据集分类研究[J].计算机研究应用,2015,32(2):379-381[58]FuZL.Cost-sensitiveensemblelearningalgorithmformulti-labelclassificationproblem[J].ZidonghuaXuebao,2014,40(6):1075-1085[59]LiQ,YangB,DengNY,etal.Constructingsupportvectormachineensemblewithsegmentationforimbalanceddatasets[J].NeuralComputer&Application,2013,22(1):S249-S256[60]WuFJ.Comparingboostingandcost-sensitiveboostingwithimbalanceddata[J].JournalofConvergenceInformationTechnology,2012,7(21):1-8[61]尹军梅,杨明,万建武.一种面向不平衡数据集的核Fisher线性判别分析方法[J].模式识别与人工智能,2010,23(3):414-419[62]秦娇龙,王蔚.Bagging组合的不平衡数据分类方法[J].计算机工程,2011,37(14):178-180[63]王春玉,苏宏业,渠瑜等.一种基于过抽样技术的非平衡数据集分类方法[J].计算机工程与应用,2011,47(1):139-143[64]袁兴梅,杨明.一种面向不平衡数据的结构化SVM集成算法[J].南京师大学报,2010,33(4):123-127[65]TianJ,GuH,LiuWQ.Imbalancedclassificationusingsupportvectormachineensemble[J].NeuralComputer&Application,2011,20(2):203-209[66]TsangIW,KocsorA,KwokJT.Simplercorevectormachinewithenclosingballs[C].In:Proceedingsof24thInternationalConferenceonMachineLearning,Corvallis.NewYork:IEEEPress,2007:911-91848 硕士学位论文[67]TsangIW,KwokJT,ChengPM.Corevectormachine:fastSVMtrainingonverylargedatasets[J].JournalofMachineLearningResearch,2005,6:363-392[68]JodriguezJJ,KunchevaIL.RotationForest:anewclassifierensemblemethod[J].IEEETransactionsonPatternAnalysisandMachineIntelligence,2006,28(10):1619-1630[69]KubatM,HolteR,MatwinS.Learningwhennegativeexamplesabound[C].In:Proceedingsof9thEuropeanConferenceonMachineLearning.London:IEEEPress,1997:146-153[70]JesseD,MarkG.Therelationshipbetweenprecision-recallandROCcurve[C].In:Proceedingofthe23rdInternationalConferenceonMachineLearning.NewYork:IEEEPress,2006:233-240[71]YangQ.10challengingproblemsindataminingresearch[J].InternationalJournalofInformationTechnology&DecisionMaking,2006,5(4):597-604[72]MoD.Robustandefficientfeatureselectionforhighdimensionaldataset[D].UniversityofCincinnati,2010[73]吴旗,刘健男,寇文等.改进的单类支持向量机的网络流量检测[J].吉林大学学报(工学版),2013,43(S1):123-126[74]KuangFJ,ZhangSY,JinZ,etal.AnovelSVMbycombiningkernelprincipalcomponentanalysisandimprovedchaiticswarmoptimizationforintrusiondetection[J].SoftComputing,2015,19(5):1187-1199[75]BoazL,JosephaY,LevK.Ontheclassificationofasmallimbalancedcytogeneticimagedatabase[J].ACMTransactionsonComputationalBiologyandBioinformatics,2007,4(2):204-215[76]王平,吴剑.基于模糊加权近似支持向量机的web文本分类[J].计算机应用与软件,2015,32(5):54-58[77]刘凯伟,张冬梅.基于流形学习的异常检测算法研究[J].计算机工程与应用,2013,49(13):105-109[78]DeepaT,PunithavalliM.AnewsamplingtechniqueandSVMclassificationforfeatureselectioninhighdimensionalimbalanceddataset[C].In:34thInternationalConferenceonElectronicsComputerTechnology.Kanyakumari:IEEEPress,2011,5:395-398[79]尹华,胡玉平.基于随机森林的不平衡特征选择算法[J].中山大学学报(自然科学版),2014,53(5):59-65[80]YuHL,NiJ,ZhaoJ.ACOSampling:Anantcolonyoptimization-basedundersamplingmethodforclassifyingimbalancedDNAmicroarraydata[J].49 基于改进支持向量机的数据挖掘分类算法研究Neurocomputing,2013,101(2):309-318[81]杨二伟.基于改进非平衡策略的入侵检测系统研究[D].郑州大学,2014[82]PalM,FoodyGM.FeatureselectionforclassificationofhyperspectraldatabySVM[J].IEEETransactionsonGeoscienceandRemoteSensing,2010,48(5):2297-2307[83]ShanabAA,KhoshgoftaarTM,WaldR,etal.Comparisonofapproachestoalleviateproblemswithhigh-dimensionalandclass-imbalanceddata[C].In:IEEEInternationalConferenceonInformationReuseandIntegration.NewYork:IEEEPress,2011:234-239[84]曾志强,吴群,廖备水等.一种基于核SMOTE的非平衡数据集分类方法[J].电子学报,2009,37(11):2489-2495[85]GiduduA,RutherH.ComparisonoffeatureselectiontechniquesforSVMclassification[C].In:10thInternationalSymposiumonPhysicalMeasurementsandSignaturesinRemoteSensing.Switzerland:IEEEPress,2007:258-263[86]朱林.基于特征加权与特征选择的数据挖掘算法研究[D].上海交通大学,2013[87]GaoSH,TsangIWH,ChiaLT.Kernelsparserepresentationforimageclassificationandfacerecognition[C].In:Processofthe11thEuropeanConferenceonComputerVision.BerlinHeidelberg:IEEEPress,2010:1-14[88]KwokJT,TsangIW.Thepre-imageprobleminkernelmethod[J].IEEETransactionsonNeuralNetworks,2004,15(6):1517-1525[89]LoweDG.Distinctiveimagefeaturesfromscale-invariantkeypoints[J].InternationalJournalofComputerVision,2004,60(2):91-11050 硕士学位论文致谢时间如白驹过隙，还来不及细细品味其中美妙，匆匆已过三年。转眼间，在兰州理工大学的三年硕士学习生活即将结束，迎来人生的新起点。这三年，是努力充实自己的三年，也是收获成长果实的三年，更是人生中最为难忘最为珍贵的三年。这三年，我在学术专业和生活中都有很多收获，这些收获和进步，离不开所有关心，帮助和支持我的人，离不开兰州理工大学这片沃土。首先我要非常感谢我的研究生导师赵小强教授，这三年，赵老师为我提供了良好的科研环境，在我疑惑的时候，如一盏明灯，为我指明前行的道路，在我遇到困难的时候，鼓励我，帮助我。赵老师严谨的科研态度和工作作风给我树立了很好的榜样，在课题完成的每一个细节给予了我悉心的指导和巨大的鼓舞。其次，在学习、生活和论文撰写的过程中，还得到了实验室的谢亚萍、何智娥、张潇潇、贾云霞、岳宗达、王涛、何浩、惠永永、季树荣、刘梦依、王帆、刘晓丽、杨文君、张源峰、周文伟和宿舍的王正花、杨婷的大力帮助，三年时间的点点滴滴都将是终身难忘的回忆，感谢他们的帮助，陪我度过充实快乐的每一天，让我明白团队协作力量的巨大和讨论求取进步的乐趣。最后，要衷心感谢我的父母，感谢他们对我的支持和鼓励，让我在遇见困难的时候，充满勇气，有更多的力量勇往直前。51 基于改进支持向量机的数据挖掘分类算法研究附录攻读学位期间所发表的学术论文目录[1]赵小强,张露,基于改进FSVM的数据挖掘分类算法[J].兰州理工大学学报,2016,42(2):101-106[2]赵小强,张露,一种改进的数据挖掘模糊支持向量机分类算法[A].第26届中国过程控制会议(CPCC2015)论文集[C],2015[3]赵小强,张露,基于改进球向量机的不平衡数据集分类算法[J].电子学报（在审）[4]赵小强,张露,基于改进SVM的高维不平衡数据集分类算法[J].系统工程理论与实践（在审）52