基于SVM的多类分类集成
- 格式：pdf
- 大小：307.85 KB
- 文档页数：6
华东理工大学学报(自然科学版)Journal of East China University of Science and Technology (Natural Science Edition )Vol.34No.52008210收稿日期:2007207216基金项目:国家自然科学基金(60543005,60674089);教育部高校博士点基金(20040251010);广西青年科学基金项目(桂科青0728091)作者简介:张红梅(19702),女,广西梧州人,副教授,博士生,从事机器学习与网络入侵检测的研究。
E 2mail :hmzh2004@ 文章编号:100623080(2008)0520734206基于SVM 的多类分类集成张红梅1,2, 高海华1, 王行愚1(1.华东理工大学信息科学与工程学院,上海200237;2.桂林电子科技大学信息与通信学院,广西桂林541004) 摘要:为了解决单个SVM 可能产生的泛化能力恶化问题以及当SVM 采用一对多组合策略解决多类分类时可能产生的误差无界情况,本文采用Bagging 方法构造了一个基于SVM 的多类分类集成模型,利用MIT KDD 99数据集进行仿真实验,通过实验探讨了其中的两个参数———训练样本数和单分类器个数对集成学习效果的影响,并将其与采用全部样本进行训练及部分样本进行训练的单分类器检测进行了比较。
结果表明:集成学习算法能够有效降低采用全部样本进行训练所带来的计算复杂性,提高检测精度,而且也能够避免基于采样学习带来检测的不稳定性和低精度。
关键词:SVM 集成;多类分类;Bagging (自助聚集);入侵检测中图分类号:TP393文献标识码:ASVM B ased Multi 2class Classif ication E nsembleZ H A N G Hong 2mei1,2, GA O H ai 2hua 1, W A N G X i ng 2y u1(1.S chool of I nf orm ation S cience an d Engi neeri ng ,East Chi na U ni versit y of S cience and Technolog y ,S han g hai 200237,Chi na;2.S chool of I nf orm ation and Com m unication ,Guili n U ni versit y ofElect ronic Technolog y ,Guili n 541004,Guang x i ,Chi na )Abstract :To overcome t he deterioration of generalization ability caused by individual SVM and t he p roblem of unbounded error begotten by using one 2against 2rest combination of SVM in multi 2class classifi 2cation ,a Bagging based multi 2class SVM ensemble model is const ructed and applied to t he M IT KDD 99dataset to perform t he simulation experiment.In t he simulation experiment ,t he performance of SVM ensemble are evaluated by choosing t he t raining sample number and t he number of base classifiers ,and t hen comparison wit h t he individual classifier using all t raining data and using sampled t raining data.The result demo nstrates t hat t he Bagging based SVM ensemble algorit hm can depress t he complex of comp uta 2tion in classifier wit h all training data and improve t he detection rate ;Moreover ,it can avoid t he instability and t he low p recision in classifier wit h sampled t raining data.K ey w ords :SVM ensemble ;multi 2class classification ;Bagging (Boost srap aggregation );int rusion detection 支持向量机(Support Vector Machine ,SVM )是一种分类和回归技术[1],它通过学习得到一个分类间隔最大化的超平面,因而具有良好的泛化能力。
目前已被广泛应用于人脸识别、数据挖掘、入侵检测437等领域。
尽管研究表明,理论上支持向量机容易实现良好的泛化能力甚至达到全局最优[2],然而这是建立在精确训练求解以及最优参数组合的基础上。
在实际应用中,如果训练样本集过大时将不得不采用一些快速近似算法(如SMO)来减少训练复杂性和时间要求,另外获得最优的核参数组合也有一定难度,从而造成单个的SVM在泛化能力上的恶化。
除此以外,SVM最初设计为一种二类分类算法,而在实际应用时遇到的常常是多分类问题。
SVM在实现多类分类时一般是通过采用组合策略(如一对一、一对多等)来实现,性能难以达到稳定,如采用一对多策略时会产生误差无界的情况。
为改进上述两种状况,本文采用多个SVM的集成学习来提高单个SVM的性能,构建SVM的分类集成不仅能提高单个SVM分类器的分类精度和稳定性能,而且能实现更有效的SVM多类分类[3]。
集成学习(Ensemble learning)通过将数个简单的、精度比随机猜测略好的弱(Weak)分类器以某种方式组合在一起对新样本进行分类,构成一个高精度的估计,从而有效克服过学习,提高分类准确率。
1990年,Hansen[3]通过投票法将一组神经网络结合起来求解,发现这一组神经网络形成的集成比最好的个体神经网络的性能还好,这一现象引起了研究界的重视;同年,Schapire等[4]提出的Boosting 算法,构造性地证明了只要找到一个比随机猜测略好的弱学习算法,就可以将其提升为强学习算法。
这些工作有力地推动了集成学习的发展,使之成为机器学习的研究热点。
2003年,K im等[5]提出了基于Bagging和Boosting的SVM集成,证明了SVM 集成对IRIS数据、手写体识别和欺诈检测数据在分类精度上比单个的SVM有很大的提高。
2005年,谷雨等[6]也通过实验证明,SVM集成对入侵检测数据比单个SVM的分类性能更好。
然而,文献[6]将入侵检测数据分为正常和异常两类,做的是二类分类的SVM集成,而本文研究的SVM多类分类集成更接近入侵检测的实际情况。
再者,前面的工作也未见集成规模与分类性能之间关系的讨论,而本文通过实验得到的结果对两者之间的关系进行了讨论,这些讨论对如何得到最优的SVM多分类集成有着重要的现实意义。
本文以入侵检测为多类分类集成方法的应用平台,构造一个基于SVM多分类集成的分类模型,利用M IT KDD99数据集进行仿真实验,探讨了训练样本数和单分类器数对集成学习效果的影响。
1 SVM集成SVM集成的实现主要包括个体分类器的生成和结论综合判断两部分。
对于个体分类器的生成策略,常用的技术包括自助聚集Bagging、提升Boosting等。
研究表明:这两种方法在精确性和对不同领域数据的计算可行性等方面的表现都是比较突出的[7]。
Bagging采用的是重采样技术,从大小为n的原始数据集中分别独立随机选取n′个数据(n′<n)形成自助数据集,并且将这过程独立进行多次,直到产生很多个独立的自助数据集。
原始训练集中的样本可能在单个分类器训练中出现多次,也可能一次也不出现。
然后,每一个自助数据集被独立地用于训练一个分量分类器,最终的结果将根据这些分量分类器各自的判决结果投票来综合决定。
Bagging 方法通过重新选取训练集增加了弱分类器集成的差异度,从而提高泛化能力。
Boosting算法首先对训练集样本赋一初始权重,随后对训练集采用学习分类器进行多次训练,对训练失败(如错分)的样本赋以较大的权重,在后续学习中更重视对这些样本的学习,从而得到评价函数序列,最后根据某种策略进行综合。
由于Bagging算法的个体分类器之间不存在强的依赖关系,因此算法可以并行。
如果利用现有网络的分布式计算可以进一步提高算法的时间效率,并且Bagging总是可以改善学习器的性能[8],本文采用Bagging算法来生成个体分类器。
在生成多个个体分类器后,需通过某种综合评判策略进行最终输出结果生成。
常用的策略包括多数投票法、基于L SE误差的加权、双层递归组合、选择性集成等。
为了简单起见,本文采用的是多数投票法。
多数投票法首先设f k(k=1,2,…,K)为第k个单分类器的决策函数,C j(j=1,2,…,C)表示第j 类。
对于测试样本x,令集成中各个单分类器将其划分为类j的个数N j={k|f k(x)=C j},则对于x 通过多数投票策略的最终输出为:f mv(x)=arg max N j(1) 2 SVM多类分类集成SVM基本算法针对二类分类问题,为将SVM 推广到多类分类问题的求解,可通过进行二类分类的组合将多类分类问题转化为二类分类问题进行求537第5期张红梅,等:基于SVM的多类分类集成解。
常用的组合策略有一对一和一对多等。
一对一方法在k 类训练样本中构造所有可能的二类分类器,通过两两组合构造C 2k =k (k -1)/2个二类分类器,每个仅仅在k 类中的二类训练样本上训练,最后组合这些二类分类的输出形成最终输出。
这种方法对于类别k 过大时,产生的单分类器过多,训练时间较长。
此外如果单个二类分类器不先规范化,则易趋向过学习。
一对多方法对于k 类问题构造k 个分类器,对于第i 个分类器采用第i 类中的训练样本作为正的训练样本,将其他样本作为负的训练样本。
