论文研究-基于KNN算法的改进的一对多SVM多分类器.pdf

所需积分/C币:50 2019-09-13 07:48:03 597KB .PDF
收藏 收藏
举报

针对传统支持向量机(SVM)多分类一对多算法存在的运算量大、耗时长、数据偏斜以及对最优超平面附近点分类易出错问题,提出了一种改进方法。将数据空间分为密集区和稀疏区,各类中密集点归于密集区,其余归于稀疏区。将每类中密集点连同它附近的点用于训练得到相应的SVM分类器。在测试阶段,对密集区的待测样本用传统的一对多判别准则来做类别预测;对稀疏区的待测样本则采用K近邻(KNN)算法。数值实验结果表明,改进的算法在耗时和分类精度上都优于原算法,对解决一对多算法存在的问题有较好的成效。
128 015,51(24) Computer Engineering and Applications计算机工程与应用 由于某些训练样本不能满足式(1)的条件,虽然在此它训练全过程速度很慢,消耗的时间很长;同时,由于 构建分类模型时尽可能降低错分程度,但对丁最优超平训练的时候总是将剩余的多类看作一类,在处理大规模 面附近的点,SVM仍不是最好的分类方法。 数据时,会出现正负类佯本数目极不平衡的问题,从而 22K近邻方法( K Nearest Neighbour,KNN)影响预测精度。 1986年, Vapnik在文献[1提出一种基于经验数 据的依赖性估计,由此改进的KNN是一种基于向量空3改进算法 间模型的机器学习方法,用来给无标记的测试集分类。3.1基本思想 它是一种经典的懒惰学习算法。其算法思想:在训练样 同一类别中的元素间相似度极高,所以多数同一类 本中选定一些点作为代表点,所有代表点组成的集合称别中的样本点在向量空间中的位置比较集中,并且SⅴM 为代表集,对一待分类样本x,在代表点集中找到K个决策函数的生成只与支持向量有关。针对投入一对多 在向量空间中离它最相近的代表点,然后使用这K个SVM分类器中的k类训练数据集生成的第i=1,2,…,k) 代表点的类别为该待测样本x的侯选类别,x与K个个SVM二值分类器,这其中作为支持向量的正类点其 代表点之间的相似度为候选类别的权重,并基于预设的实就是与其他类别的点相混的i类点,负类点是与κ类 相似度阀值,就可以最终判定待分类样本x的类别。具点相混的其他类别的点。这些点的混合有三种情况(如 体实现方法如下 图1):第一种是i类密集点(详见3.2.4节)与其他类别的 y(xC)=∑f(x,dc1b) 稀疏点(详见3.2.4节)相混(如圆①),第二种是i类稀疏 d.∈KNN 点与其他类别的密集点相混(如圆②),第三种是i类稀 sim(r, d)(d,c)-b,>0 f(x, d,,,b)= 疏点与其他类别的稀疏点相混(如圆③)。 0,.in(x,d)(a,e)-b,≤0 类 其中,x表示待分类样本,d为K个最相近代表点中的 E(△△△△ A其但类 第i个,c1表示类别(d,c)∈0,1,当d属于c,时取1 ②也△4 反之取0;b,为类别c所设的阀值,一般由类别c,在总数 据中所占比例所决定;simn(x,d,)为待分类样本x与代表 (1)一 点d之间的相似度,是通过两样本点所对应的向量间 D go (2) 夹角的余弦值来衡量的。当y(x,c)=1=m2x((x,c) (3) 图1改进算法的中心思想 (m:样本集类别总数)时,待测样本x属于类别c:。 23一对多支持向量机(Ivs- ul svM) 根据SVM决策函数构造原理,考虑这三种数据的 对多(1-vws-al)算法呆用最大输出法将多个SV 缺失对生成最优超平面的影响:缺失第一·种数据生成的 最优超平面如虚线(1),缺失第二种数据生成的最优超 分类器的输出组合起来实坝多类分类。这种方法只需 要在每一类样本和对应剩余样本之间产生一个最优决 平面如虚线(3),缺失第三种数据生成的最优超平面如 虚线(2),SⅥM分类器在最优超平面附近的分类性能 策面,其中属于该类的样本点作正类点,剩余样本点作 负类点。因此,对k个类别仅需构造k个SVM(k>2) 不及KNN算法(见文献[12]),于是提出以下想法:舍去 第二种数据,对于落在虚线(1)和虚线(3)外侧区域的待 每个SVM分别将某一类的数据从其他类别中分离出 测点,SVM多值分类器可以更准确地测试出它们的类 来。測试时,取决策函数输出值最大的那个SVM模型别:而对于落在虚线(1)和虚线(3)内侧区城的待测点 对应的类别作为测试样本的所属类别。其体方法如下 采用性能稳定、准确率高的KNN方法来测试类别。这 假定将第j类样本看作正类(=1,2,…,k),而将样不但弥补了SVM在最优超平面处分类易出错的缺 其他类别的样本看作是负类,通过两类SVM方法求出陷,提高了分类准确率;而且生成类对应的SM模型 个决策函数f(x)=∑(1yK(x,x)+b,这样的决策函只需要i类密集点和与它相近的氵类以及其他类别的稀 疏点,将训练数据界定在一个很小的范围,数目上大大 数∫(x)共有k个。给定一个测试输入x,当fn(x) 减少,可以明显缩短运算时间。 ((x)时,x属于类别m 3.2算法实现 l-vs-al1分类方法简单、有效,需要构造的决策平面3.2.1算法主要流程 数少,可用于大规模数据。但当类别数较大时,由于它 步骤1综合考虑密集程度和各类中心间距离来确 每次构造决策平面的时候都需要川上全部的样本集,因定类别总数K并基于数据样本密度和距离在各类中分 刘雨康,张正阳,陈琳琳,等:基于KNN算法的改进的一对多SVM多分类器 2015,51(24)129 别选出类中心点(详见3.2.2节、3.2.3节)。 同,自接相乘不具有可比性,因此需要进行归一化处理。 步骤2设定可调阀值a(∈R),筛选出各类中的密对于给定的样本yn,将其到样本点y1(=1.2,…,N) 集点(详见3.24节)。以半径最小为原则用超球将所有(N为样本总数)的距离按下式进行归一化 的密集点包裹起来,输出半径值,每个超球对应某 D,= (l=1,2,…,N) 类。确定向量空间的划分:密集区和稀疏区(详见3.2.5 d 节)(这一步超球裹住了3.1节所述的第一种点) 步骤3设定可调阀值b,b2,步长c,对超球中正类 设已选定前(j-1)个类的中心,则在选取第j类的 样本数占超球中样本总数的比值po大于b的超球j中心时除了考虑该点在第j类样本点中的密度较大,还 (类别j对应的超球)按步长c向外扩,直到pro≤b1,输 要考虑它到已有类中心总的距离较大。总的来说,就是 出最终半径r,和超球中正类样本数T;对psb的超在第/类的样本中选取y,使得该样本点的分布密度 球输出步骤2中得到的半径和正类样本数将乘以该样本点到已选聚类中心的归一化离之科8 T≤b2的超球类别的所有点看作桥疏点将它对应的超p∑Dm最大,其中P表示类别j中第个样本点的密 球半径设为0(详见32.5节),仅对7>b2的那些超球类 别构建相应的SVM二值分类器,训练样本为超球内部度,D为样本点x到已选定的第t类的中心y的归 所有数据(这一步超球又裹住了3.1节所述的第三种点,化距离。 初步解决数据偏斜问题,并且对稀有类别进行了处理)。 3.2.4密集点的选取 步骤4结合步骤2和步骤3更新向量空间的密集区 密集点是否选取恰当,对分类的准确率和运算时间 和稀区。测试阶段,对落在集区的点,采用原始的的影响很大:密集点过少会导致过多的待测样本需要采 1)别准则来做类别预测;对落在稀疏区的点,用用KN算法进行类别测试,由于该算法运算的时间复 KN算法,以所有训练样本作为代表点预测它的类别杂度和样本数成正比,因而测试速度会减慢;过多会误 (这一步解决了SVM分类器对最优超平面附近点分类将最优超平面附近的待测点也用SWM多值分类器进行 易出错问题,并提升了对稀有类别的分类性能从而进一类别预测,从而降低分类准确率 步解决了数据偏斜问题 本文通过将某一类的点与该类中心点的密度相对 322样本密度的度量 差值e与已经设定的一个可调阀值a进行比较(a∈R) 引入分布密度的概念(见文献[3])对样本数据在来适当师选出密集点。这里参数a是结合运算结果进 它所属类别中的密集程度进行度量对于每个样本点x行调节的。对/类点x,它对应的相对差值c= (指类判j中的第i个样本点),其点密度函数定义如下 P 其中P为类j的中心点的密度。若en>a,则x是密 集点,否则,它就是稀疏点。 其中::y,4=|:-x1,Pn表示类别j中第i个 3.25获取最优超球半径 将数据空间川超球来进行划分。按3.24节所述的 样本点的密度,P越大,样本点x周围属于类别j的 规则选取密集点后,各类超球以类中心为球心,以半径 尽可能小为原则将相应类的密集点包住,所有包裹密集 样本点越多。n,为j类样本点总数,4表示样本点x点的超球内部区域称为密集区,所有的这类超球外部区 和x在向量空间中的距离。 域称为稀疏区。此时超球内部点分布情况有三种可能: 323类中心点的选取 第一种是正类点数远大于负类点数,第二种是正负类点 基于最大最小距离法(见文献[4])选取初始聚类数目相当,第三种是正类点数远小于负类点数 中心,但本文要求保证每个类的类中心都隶属于该类, 处理这三种情况首先要通过进行3.2.1节中步骤2 具体实现如下:按照3.22节的密度度量方法得到各训得到不同类别的超球,然后将各类超球内正类样本数r 练数据的密度值p,对于第一类,直接选取该类别中密和参数b2进行比较。对于7>b2的邶些类,本文把它们 度值最大的点作为类中心点,对其他类中心的选取还需看作是前两种情况,输出经过步骤2得到的半径值,对 要考虑距离的因素,使所得的类中心点间距离尽可能于T≤b2的类别,把它们看作是第三种情况,输出半径 远,这样就保证了超球(详见3.2.5节)重叠的区城尽可为0 能小,从而尽可能提高分类效率和准确率。本文使用密 前两种情况的类别点在数捃空间中分布较集中,适 度和距离的乘积作为选择的度量。密度和距离的单位不合用SVM分类器进行分类,通过步骤3中输出的半径 130 015,51(24) Computer Engineering and4 pplications计算机工程与应用 值即为最优半径;对于T>b,的那些类,要对超球中正本进行分类时,用SVM分类的时间复杂度是o(n2),用 类样本数占超球中样本总数的比值po与参数b进行KNN分类的时间复杂度是odm2)。所以,基于KNN算 比较。对超球中正类样本数占超球中样本总数的比值法的改进的一对多SVM多分类器的时间复杂度小于 pro≥b的超球(类别j对应的超球)按步长c向外扩, 3+2n|+o +2n+o(2m)+0(m)+o(m1)+(m2) 直到po≤b1,从而得到超球半径,和超球中正类样本 数T;对po≤b1的超球s,输出步骤2中得到的半径r o(dn"+ 6n+ni++ m)=o(n) 由此可以看出,本文提出的基于KNN算法的改进 和正类样本数T。 的一对多SVM多分类器(1-vs- all KNN-SVM)相比支持 第三种情况的超球对应的是稀有类别中较难处理向量机的时间复杂度有所减少。同时,由于n1<n,所以 的一·种,可以直接把这类点全部看作是稀疏点,对该类 1-vs- all KNN-SVm算法比原算法耗费的时间更少。具 别不生成相应的SⅴM分类器,也就是说,对稀有类别 体耗费时间则是由改进算法中SⅤM和KNN两种方式 s,给超球$的半径0值。因为它不但训练样本数目各白分类的样本数决定的,用KN算法分类的样本数 稀少,而且在向量空间中分布稀疏,所以用半径尽可能 越多,所耗时间越少 小的超球将它内部相对密集的点包裹起来还是无法解 决数据偏斜问题即使生成了SVM分类器,这类点都处4数值实验与结果分析 在分类超平面附近,所以分类效果不会太好。 本文实验均在 LENOVO PO机( Pentium@ dual-Core 33算法参数选取 CPUT400@2.20GHz2.19GHz,内存为296GB) 参数a的选取决定了样本点中密集点的个数,对于 上利用 MATLAB7.9编程实现。实验采用台湾大学 SⅴM分类效果差的数据,文中通过选取较大的a来增 林智仁开发设计的 LIBSVM3.14工具箱,选用其中性能 加用KNN算法分类的样本个数,从而提高分类正确 率。具体来说,对于原SⅥM算法正确率高于90%的数 较好的高斯核函数(RBF)K(x,y)=exp(x-y和多 据,a∈[0.9,-0.5],对于正确率在80%到90%的数据, 项式核函数K(x,y)=(6(xy)+c)2,对UC数据库(见文 a∈[04,0.1,正确率低于80%的数据,a∈[-0.1,0)。 献[16])中8个数据集:iris, glass Identification, Statlog (Landsat Satellite), Computer Hardware, waveform, Page b的选取要根椐运算时间和正负类点数目两种情况折 Blocks Classification, Optical Rccognition of Handwritten 中考虑,一方面,b1过小会导致用SVM运算的数据比例 Digits, Letter Recognition(简记为iris,glas,.sat,CH, 过大,从而影响政进效果;另一方面,从算法的时间复杂 waveform, page blocks, optical, letter)分别进行了实验。 度可以看出,b过大或者过小都会影响运算时间。因此, 采用十折交叉验证得到分类精度并统计整个十折 b选取范围是b∈[0.3.1)参数c过小会导致达代速度验证过程(从训练到测试)消耗的时长,来将原算法和改 太慢,过大会使得超球中样本数过多,所以c值要根据进算法进行比较。原算法是采用原始的1s:l法。 数据特征和观察超球外扩的迭代快慢来调试,其中数据对于改进的算法得到的分类准确率和运算时间是将 特征有着重要的作用。在本实验中c=10″,n=0,1,5。KN算法中的K值固定为5,调节新添加参数a,b 参数b2是通过观察比较最优超球中正类样本数来确定c,b,而得到的近似最优值。实验结果如表1-3 的,将其设定为比那些极小的数大,比其他数小即可,在 表Ⅰ选用帶高斯核数的SVM分类器用于进行分类性能比较 本实验中b2=10n,n=0,1,10。 运算时间/s 正确率 34算法的时间复杂度分析 UCI数据样本数类别数 改进 凉算法 原算法 设n为训练集样本的个数,n1为需要用SvM多分 算法 算法 类器分类的样本数,n2为需要用KNN算法分类的样本 150 30.72830.632097.3398.00 4435 数,L为样本类别数,d为样本特征数目。对于一个测 611197558004286086.49 glass 214 9.358744839.59999 试样本,由于kNN算法的时间复杂度是o(4n2)通过ps 482808780.9913491.92 计算每组中样本之间的距离来度量样本密度的吋间复 waveform 5000 34671.03651.185.2085.64 letter 20000261384928452997.7397.77 杂度为oa+2n。为使每一类的中心点距离尽量远, 表2选用带多项式核函数的SVM分类器 类中心点选取过程中的时间复杂度为om+2n。密 用于进行分类性能比较 确率 集点进取的时间复杂度为2),获取最优超平面的时据样本数类别数原算法改进算法原算法改进算法 间复杂度与步长c和类别数有关,为一个常数m。对样cH209647662077262.368332 刘雨康,张正阳,陈琳琳,等:基于KNN算法的改进的一对多SVM多分类器 2015,51(24)131 表3改进算法对应的参数值 4 Hsu L C.A comparison of methods for multiclass support 微据 vcctor machinc[J].IEEE Trans on Ncural Nctworks, 2002 0.7000.60 13(2):415-425 at -0.0100.60 [5 Zhang L, Zhou W D, Su T T, et al. Decision tree Support g1 0.9000.40 Vector Machine J.International Journal on Artificial Intelli- page blocks -0 900 0.95 gence Tools, 2007, 16: 1-16 0.3000.60 [6 Yang Yiming, Liu Xin. A re-examination of test categori letter -0.9000.60 10 zation method[cl/Pro of the 22th Annual International CH 0.0010.7010000010 ACM SIGIR Conference on Research and Development in the Information Retrieval, Berkeley, USA, 1999: 42-49 由表1,表2可得出如下结论 [7 Zhang Lei, Liu Jianwei, Luo Xionglin. kNN and RVM (1)1-vs- all knn-SVM算法比原始的一对多算法 based classification method KNN-RVM classifier[J].Pr 有更高的分类精度,改进算法可以通过调节几种参数来 AI,2010,23(3):376-384 调整新算法中用SvM和KNN进行分类的样本数目,当8] Zhang H, Berg A C, Maire y,eta.sMKN: discrimi 原算法分类效果很差时,诚少新算法中用SVM分类的 native nearest neighbor classification for visual category 样本数,增加浙算法中用KNN分类的样本数,这样分类 recognition C],IEEE Computer Society Conference on 正确率就会有很大的提高。 Computer Vision and Pattern Recognition, 2006: 2126-2136 (2)1-ws-akNN-sVM算法比原始的一对多算法9 Deng Nanyang, Tian Yingjie. Support Vector Machines- 消耗的运算时间明显减少,时间减少的比例跟参数选取 optimization based theory, algorithms, and extensions [M]. 有关。 Bcijing: Scicncc Press, 2009: 54-5 0 Deng Naiyang, Tian Yingjic The new mcthod in data 5结论 mining Support Vector Machine[M] Beijing: Science Press,2004:98-100 传统的1vsl算法运算量很大,总体耗时长,同时1 I Vapnik v N Estimation of dependences based on empirical 出于训练时正负类数据分布极不平衡,再加上SVM分 data[M]. Berlin Springer-Verlag, 1982 类器本身存在对最优超平面附近点分类易出错的问题,[12] Zhang Suzhi, Sun peifeng.a new short -test categorization 导致分类精度降低。它的这些缺陷在对稀有类别分类 algorithm based on improved KSVMICI/Pro of the 3rd 时的影响更是显著。数值实验结果表明,本文提出的改 International Conference on Communication Software and 进算法确实很好地解决了上述传统的1-vs-al算法存在 Networks, 2011:154-157. 的问题。未来的T作是进一步改进算法,提升它的稳定131 Xie Juanying, Guo Wenjuan, Xie Weixin,, et al.K-means 性,并实现参数优化 clustering algorithm based on optimal initial centers related to pattern distribution of samples in space[J]. Appli cation Rescarch of Computers, 2012, 29(3):888-892 参考文献 [14 Xiong Zhongyang, Chen Ruotian, Zhang Yufang. Effective [1 Vapnik V nThe nature of statistical learning thery [M] method for cluster centers initialization in K-means New York: Springer-Verlag, 1995: 4-80. clustering[J]. Application Research of Computers, 2011 [2 Guo Xian'e, Wu Wei, Liu Chungui, et al. Research of 28(11):4188-4190 cmbedded IP supervisory system bascd on Intranct/Inter- [15] Richard O D, Peter E H, David G SPattcrn classifica net[J] Journal of Shanxi Datong University: Natural Sci tion[M]李宏东,姚天翔,译北京:机槭工业出版社,2003 nce,2010,26(3):6-8 15l-158 [3] Fan Baichao, WangJianyu, Bo Yuming Binary trec SVM [16] Blake C, Merz C J.UCI repository for machine learning multi-class classification algorithm with feature selection[J databases[eb,ol].[2013-09-02]httP://www.ics.uci.edu/ Computer Engineering and Design, 2010, 31(12): 2823-2825 mlearn/MLRepository html

...展开详情
试读 6P 论文研究-基于KNN算法的改进的一对多SVM多分类器.pdf
立即下载 低至0.43元/次 身份认证VIP会员低至7折
抢沙发
一个资源只可评论一次,评论内容不能少于5个字
weixin_38744375 如果觉得有用,不妨留言支持一下
2019-09-13
  • 至尊王者

    成功上传501个资源即可获取
关注 私信 TA的资源
上传资源赚积分or赚钱
最新推荐
论文研究-基于KNN算法的改进的一对多SVM多分类器.pdf 50积分/C币 立即下载
1/6
论文研究-基于KNN算法的改进的一对多SVM多分类器.pdf第1页
论文研究-基于KNN算法的改进的一对多SVM多分类器.pdf第2页

试读结束, 可继续阅读

50积分/C币 立即下载 >