基于最小闭球的多类支持向量机.pdfVIP

第 26卷 第 1期 聊城大学 ：报 (自然科学版 ) V0L26NO． 20l3年 12Jj _】rI ()f】[aochcngUniversity(Nat．Sci．) DCC．20l4 基于最小闭球的多类支持向量机 高希占 范丽亚 (聊城大学 数学科学学院，山东 聊城 252059) 摘 要 针对多类分类问题 中样本数量分布不均衡和测试速度较慢两种情况，本文提 出了两个 基于闭球的二叉树 多类支持 向量机算法：MEB～MCSVM一1和 MEB—MCSVM一2．算法利用最小 闭球来协调样本数量间的不均衡性，利用球心进行最远距离聚类或最近一最远距 离聚类，构建二 叉树结构，使：-Yk树的每个节点代表 】个二类支持 向量机．为了检验所提算法的有效性，本文 从需要训练的sVM个数、训练时间和测试时间三个方面对五种算法 1-v一1，1～v—r，MEB-MCS— VM—O，MEB—MCSVM一1和MEB—MCSVM～2进行了比较分析，结果表明本文所提方法对解决 多类分类 问题 中样本数 目不均匀和测试速度较慢这两种情况有明显的优势，实用性更强． 关键词 支持向量机 ，聚类 ，训练时间，测试时间，时间复杂度 中图分类号 0224 文献标识码 A 文章编号 1572—6634(2013)04—0024—06 U 引 磊 1995年，CotinnaCortes和Vapnik等学者提出了一种新的机器学习方法——支持 向量机 (Support VectorMachine，简记SVM)．由于SVM在解决小样本、非线性及高维模式识别中的优势，使得它受到 越来越多的关注．经典的SVM是一个二类分类器，但在实际应用中大多数分类问题都是多类问题，无 法直接使用经典的SVM，因此，把经典的SVM推广到多类分类情况就成了机器学习领域中的一个值得 研究的问题．1998年，Vapnik在文献[13中提出了一对余 (one-versus—rest，简记 1一v—r)多类分类器．1999 年，Krebel在文献[2]中提出了一对一 (one-versus—one，简记 1一、卜1)多类分类器．同年 Weston和 Wat～ kins提出了多类 目标函数法 ]，它是将SVM 的目标函数直接扩展到多类情况．2003年，Zhu等提出了 将超球单类支持向量机 (MinimumEnclosingBallOne—classSVM，简记 MEB-OCSVM)扩展到多分类 的 情况 ． 经典的SVM没有考虑到两类样本数量间的不均衡性 ，当两类样本数量不均衡时，分类超平面会朝 数量多的一类偏移，从而导致分类精度下降．利用最小闭球可以有效回避这一弊端，其思想是寻找一个 闭球r使之在包含尽可能多的样本的前提下，使球半径尽可能的小．因为球结构只涉及到单类样本，因 此不会受到样本数量不均衡的影响． 针对常见的多类分类算法的测试速度较慢这一情况，本文考虑用二叉树结构进行改进．结合最小闭 球和二叉树结构，本文提出了两种新的支持向量机多类分类算法． 1 预备知识 本节简要 回顾二类 SVM 和基于闭球的单类 SVM(MEB-OCSVM)算法，详细内容见文献[5—8]． 收稿 日期 ：2013-0612 基金项 目：山东省高等学校利技计划项 目资助(Jl3LI10) 通讯作者 ：高希 占，Email：gaoxizh；lnl23@ l26．c0n]． 第 4期 高希 占等 ：基于最小闭球的多类支持 向量机 25 1．1 二类 SVM 设 {(i，3，i)} CR x 卜一1，1)是线性可分的二类问题训练集 ，软间隔二类支持向量机是通过求解下 述最优化问题来寻找一个分离超平面 (，z)+b_--0 min专i耳I善一iam ，一—1 f1、 s．t． ∑Yiai一0，0≤口≤c，i1，…”． 具体算法如下 算法 1(软间隔二类 SVM) 1。给出