基于支持向量机和k_近邻分类器的多特征融合方法

󰀁

2009年3月

文章编号:1001-9081(2009)03-0833-03

计算机应用

JournalofComputerApplications

󰀁

Vo.l29No.3Mar.2009

基于支持向量机和k󰀁近邻分类器的多特征融合方法

陈󰀁丽,陈󰀁静

(中国农业大学理学院,北京100083)

(jing_quchen@163.com)

摘󰀁要:针对传统分类方法只采用一种分类器而存在的片面性,分类精度不高,以及支持向量机分类超平面附近

点易错分的问题,提出了基于支持向量机(SVM)和k󰀁近邻(KNN)的多特征融合方法。在该算法中,设样本集特征可分为L组,先用SVM算法根据训练集中每组特征数据构造分类超平面,共构造L个;其次用SVM󰀁KNN方法对测试集进行测试,得到由L组后验概率构成的决策轮廓矩阵;最后将其进行多特征融合,输出最终的分类结果。用鸢尾属植物数据进行了数值实验,实验结果表明:采用基于SVM󰀁KNN的多特征融合方法比单独使用一种SVM或SVM󰀁KNN方法的平均预测精度分别提高了28.7%和1.9%。

关键词:支持向量机;k󰀁近邻;多特征融合;后验概率中图分类号:TP311.13;TP181󰀁󰀁文献标志码:A

Multi󰀁featurefusionmethodbasedonsupportvectormachine

andk󰀁nearestneighborclassifier

CHENL,iCHENJing

(CollegeofScience,ChinaAgriculturalUniversity,Beijing100083,China)

Abstract:Thetraditionalclassificationmethodsonlyuseonesingleclassifier,whichmayleadtoone󰀁sidedness,low

accuracy,andthatthesamplesnearbytheSupportVectorMachine(SVM)hyperplanesaremoreeasilymisclassified.Tosolvetheseproblems,themulti󰀁featurefusionmethodbasedonSVMandK󰀁NearestNeighbor(KNN)classifierswaspresentedinthispaper.Firstly,thefeaturesweredividedintoLgroupsandtheSVMhyperplaneswereconstructedforeachfeatureoftrainingset.Secondly,thetestingsetwastestedbySVM󰀁KNNmethod,andthedecisionprofilematrixeswereobtained.Finally,thesedecisionprofilematrixeswereimplementedbymulti󰀁featurefusionmethod.TheexperimentalresultsonIrisdatashowthattheforecastaccuracyofthemulti󰀁featurefusionmethodbasedonSVM󰀁KNNclassifiersincreasesby28.7%and1.9%thanthoseofSVMandSVM󰀁KNNmethodsrespectively.

Keywords:SupportVectorMachine(SVM);K󰀁NearestNeighbor(KNN)algorithm;multi󰀁featurefusion;inverseprobability

0󰀁引言

传统的分类方法大都采用单一的分类器对数据进行分

类,或者通过增加单个分类器结构的复杂度来提高分类精度,结果往往令人不满意。而通过将多个结构较为简单的分类器进行融合的方法来提高整体的分类精度,不失为明智的选择。然而,常见的融合方法如线性组合法、投票法[1]、计数法[2]、模糊积分[3-4]等都没能利用样本被子分类器分类后的后验概率,忽略了子分类器的性能差异,分类结果都不理想。另外,还有一种融合方法:概率乘积准则[5],此方法虽利用了样本被每个子分类器分类后的后验概率,但由于概率乘积准则在融合过程中要将所有后验概率相乘,增加了融合后样本被错分的概率。这是因为假设存在某个子分类器将样本分为某类的概率为零,则融合过程中将所有后验概率相乘时,该样本被分为该类的概率将大大降低。而采用概率和准则[5]可有效避免此类情况的发生。

研究发现支持向量机[6](SupportVectorMachine,SVM)与k󰀁近邻(K󰀁NearestNeighbor,KNN)相结合能提高支持向量机的分类精度[7]。因此,本文提出了基于支持向量机(SVM)和k󰀁近邻(KNN)的多特征融合分类方法,以期在不增加支持向量机算法时间复杂度的基础上,减少支持向量分类超平面

附近样本的错分率,提高对数据的分类准确率。

1󰀁SVM󰀁KNN分类器简介

支持向量机是由Vapnik等人于1995年提出的一种建立

在统计学习理论基础上的分类方法,在解决小样本、非线性、高维模式识别中具有分类精度高、泛化能力强等优势。但是在使用SVM分类时,分界面附近的样本点比较容易被错分,而SVM分类器等价于每类只选一个代表点的1󰀁NN分类器[7]。因而在对样本进行分类时,可以考虑根据空间的不同分布采用不同的分类方法:当样本距SVM最优超平面的距离大于一给定阈值󰀁时,即样本离分界面较远时,用SVM方法进行分类;反之,当样本和SVM最优超平面的距离小于󰀁时,用KNN方法对测试样本分类。

图1󰀁SVM󰀁KNN分类算法示意图

具体地,对于待识别样本x,计算x与两类支持向量代表

󰀁󰀁收稿日期:2008-09-28;修回日期:2008-11-28。󰀁󰀁基金项目:国家自然科学基金资助项目(10871022)。

󰀁󰀁作者简介:陈丽(1982-),女,河南安阳人,硕士研究生,主要研究方向:数据挖掘、模式识别、支持向量机;󰀁陈静(19-),女,河南南阳人,教授,主要研究方向:数据挖掘、数值模拟、最优化方法、支持向量机。󰀁834󰀁󰀁󰀁计算机应用

*

第29卷

j(x)=argmax[󰀁j(x)]

j=1c

点x+和x-的距离差,如果距离差大于󰀁,如图1中区域󰀁,用SVM一般都可以正确分类;当距离差小于󰀁,即落入区域󰀁,如果分类时仍用SVM,相当于只计算x与每类所取的一个代表点的距离,比较容易错分。所以这时采用KNN算法进行分类,将所有支持向量作为代表点,计算待识别样本和每个支持向量的距离,对待识别样本做出判断。

(3)

3.2󰀁SVM󰀁KNN多特征融合分类算法

设样本集有L组特征。首先,根据训练样本集中的L组特征数据用SVM方法分别得到L组支持向量集Tksv和决策超平面gk(x):

gk(x)=

2󰀁多特征融合分类方法

多特征融合[8]是指首先根据样本的每组特征分别对样本进行分类,然后将所有的分类结果进行融合,得到最终分类结果,其构架如图2所示。它能整合来自多信息源的信息,降低单信息源中存在的不确定性,从而提高系统的整体性能。

󰀁󰀁

i=1

m

*iyiK(xi,k,x)+b*;k=1,2,󰀁,L

(4)

其中,xi,k表示第i个训练样本的第k组特征,K(󰀁,󰀁)为支持

向量机核函数。

对于一个两分类问题,基于SVM󰀁KNN的多特征融合分类算法步骤如下。

输入:测试样本集T和训练样本集。输出:测试集中每个样本的类别*j(x)。方法:

1)取x󰀁T,计算样本x的决策轮廓矩阵(di,j(x))L󰀁2。1.1)设初始k=1。根据式(4)计算gk(xk),其中xk表示x的第k组特征数据。

1.1.1)若gk(xk)>󰀁,计算xk分别被分为正类和负类的概率{dk,1(x),dk,2(x)}[9]:

1

dk,1(x)=,d(x)=1-dk,1(x)

1+exp(-gk(xk))k,2

(5)

否则,转1.1.2)。1.1.2)若gk(xk)<󰀁,用KNN分类算法重新分类,训练集为第k个支持向量机分类器的支持向量集Tksv,则:

dk,1(x)=q/p,󰀁dk,2(x)=1-dk,1(x)(6)其中,p为KNN算法中所取近邻的个数,q为所取近邻中属于正类的代表点的个数[10]。在KNN算法中计算xk与每个支持向量的距离时采用下式:

d(xk,xi)=K(xk,xk)-2K(xk,xi)+K(xi,xi);

xi󰀁Tksv1.2)k󰀁k+1,若k=L,转2);否则,转1.1)。

d1,1(x)d1,2(x)2)得到样本的决策轮廓矩阵

󰀁di,1(x)󰀁dL,1(x)

(7)

图2󰀁多特征融合构架

图2中󰀁样本󰀁为测试集中一个样本,󰀁特征i󰀁表示第i组参与融合的特征数据,i=1,2,󰀁,L。设所有样本可分为c类。首先,根据训练样本集每组特征数据构造出L组基本分类器。然后,用这L组基本分类器分别对测试样本x进行分类。设经第i组分类器分类后得到的分类结果记为:{di,1(x),󰀁,di,j(x),󰀁,di,c(x)},di,j(x)表示第i个分类器将测试样本分为第j类的概率(后验概率),其中i=1,2,󰀁,L,j=1,2,󰀁,c。于是对每个测试样本x,经L个分类器分类后可以得到一个决策轮廓矩阵:

d1,1(x)d1,2(x)󰀁d1,j(x)󰀁d1,c(x)d2,1(x)󰀁di,1(x)󰀁dL,1(x)

d2,2(x)󰀁di,2(x)󰀁dL,2(x)

󰀁󰀁󰀁

d2,j(x)󰀁di,j(x)󰀁dL,j(x)

󰀁󰀁󰀁

d2,c(x)󰀁di,c(x)󰀁dL,c(x)(1)

最后,将这些结果经多特征融合后输出最终分类结果。

3󰀁基于SVM󰀁KNN的多特征融合分类方法

多特征融合方法能避免只采用单一分类器分类方法存在的片面性和分类精度不高的问题。其中,多特征融合方法中的概率和准则充分利用了样本被分类后的后验概率,是一种比投票法、计数法等融合方法更有效的特征融合方法。同时,由于SVM󰀁KNN可以减轻对核函数参数选择的敏感程度,一定程度上比使用SVM具有更好的分类性能[7]。因此,本文提出了基于SVM和KNN的多特征融合分类方法。新算法在不增加传统支持向量机方法时间复杂度的基础上,降低了其分类超平面附近样本点的错分率,考虑到了各个子分类器之间的差异,是一种比只采用单一的SVM或SVM󰀁KNN分类器分类精度更高的一种方法,且通过不同的融合方案能够分析出在分类过程中占主要因素的特征。3.1󰀁概率和准则

概率和准则[5]的思想是:首先假设对于测试样本x,经L个基本分类器分类后,得到了一个决策轮廓矩阵,如式(1)。

然后,计算测试样本x属于第j类的置信度󰀁j(x):

󰀁j(x)=(1-L)p(j)+

󰀁

di,2(x),代入󰀁dL,2(x)到式(2~3)中,此时c=2,得到测试点x经多特征融合后的最终分类结果j*(x)并输出。

3)T󰀁T-{x},若T=󰀁,停止;否则,转1)。3.3󰀁算法时间复杂度分析

设n为训练样本的个数,L为将样本特征分成的组数,d为每组特征包含的特征数目。对于一个测试样本,由于KNN法的时间复杂度是O(dn2)[11],计算后验概率时只需要将分类后的结果代入式(5~6)中,因此其时间复杂度是O(1),而判断gk(xk)与󰀁的大小的时间复杂度是一常数,步骤1.1.1)和1.1.2)共循环了L次,所以步骤1.1.1)的时间复杂度是O(L),步骤1.1.2)的时间复杂度是O(Ldn2+L)。所以,步骤1)计算样本决策轮廓矩阵的总时间复杂度是O(Ldn2+L)。步骤2)中多特征融合的计算相当于对决策轮廓矩阵的每一列元素求和,再分别加上一个常数后求每列的最大值,然后取其下标,所以步2)的时间复杂度是O(2L)。又由于标准支持向量机的时间复杂度是O(n3)[12],所以基于SVM󰀁KNN的多特征融合分类算法总的时间复杂度是:

O(Ln3)+O(Ldn2+L)+O(2L)=󰀁d

i=1

L

i,j

(x);j=1,2,󰀁,c(2)

其中,p(j)=Nj/N,j=1,2,󰀁,c,Nj为训练样本集中属于第j类的样本数量,N为训练样本的总数量。

则融合后样本x的判别结果为:第3期陈丽等:基于支持向量机和k󰀁近邻分类器的多特征融合方法󰀁󰀁󰀁835󰀁

O(Ln3+Ldn2+L+2L)=O(n3)(8)

其中,L是不依赖于n的指定正常数,d由上面可以看出,本文提出的基于SVM󰀁KNN的多特征融合分类算法并没有增加支持向量机的时间复杂度。

4󰀁实验与讨论

为了验证算法的有效性,采用鸢尾属植物数据集的Iris󰀁versicolor和Iris󰀁virginca两类数据进行实验,这两类数据共包含100个样本,每个样本包含四个特征,分别为萼片长度、萼片宽度、花瓣长度和花瓣宽度。实验采用五折交叉验证的方法,将SVM、SVM󰀁KNN、基于SVM的多特征融合算法与基于SVM󰀁KNN的多特征融合算法四种算法的分类准确率作对比。实验中支持向量机核函数采用高斯径向基核函数K(x,y)=exp{-x-y2/2󰀁2},惩罚参数C取1000。实验结果如图3和4所示。

各种特征包含的信息之间并非完全互补,而是存在着一定的冲突。同时,通过统计分类准确度在85%以上的融合方案中各种特征出现的次数,以及由C3,C4与C1,C3,C4的分类准确率相等,可以说明花瓣长度和花瓣宽度是鸢尾属的主要特征,其他特征是辅助特征。

图4󰀁基于SVM和SVM󰀁KNN的多特征融合分类方法准确率

5󰀁结语

本文研究的基于SVM󰀁KNN的多特征融合的方法,整合了多种特征信息,避免了单一分类器可能存在的片面性和在SVM分类中核参数选择问题,在不增加支持向量机算法时间复杂度的基础上,降低了SVM分类面附近样本点的错分率,提高了分类系统的总体性能,是一种有效的分类预测方法。同时也发现,参与融合的特征数据之间并非是完全互补的,而是存在着一定的冲突,如何选择合适的特征使它们间的信息互补达到最大化,是一个值得研究的问题。另外,如何将本文的算法从两分类推广到多分类,并将其运用到基因表达数据分类中是进一步要解决的问题。参考文献:

[1]󰀁BATTITIR,COLLAM.Democracyinneuralnets:Votingschemes

forclassification[J].NeuralNetworks,1994,7(4):691-707.[2]󰀁HOTK,HULLJJ,SRIHARISN.Decisioncombinationinmultiple

classifiersystems[J].IEEETransactionsonPatternAnalysisand

MachineIntelligence,1994,16(1):66-75.[3]󰀁CHOSB,JINHK.Combiningmultipleneuralnetworksbyfuzzyintegralforrobustclassification[J].IEEETransactionsonSystems,ManandCybernetics,1995,25(2):380-384.[4]󰀁CHOSB,JINHK.Multiplenetworkfusionusingfuzzylogic[J].IEEETransactionsonNeuralNetworks,1995,6(2):497-501.[5]󰀁KITTLERJ,HATEFM,DUINRPW,etal.Oncombiningclassi󰀁fiers[J].IEEETransactionsonPatternAnalysisandMachineIntel󰀁

ligence,1998,20(3):226-239.

[6]󰀁邓乃扬,田英杰.数据挖掘中的新方法󰀁󰀁󰀁支持向量机[M].北京:科学出版社,2004:45-76.

[7]󰀁LIR,YESW,SHIZZ.SVM󰀁kNNclassifier-Anewmethodof

mprovingtheaccuracyofSVMclassifier[J].ActaElectronicaSini󰀁ica,2002,30(5):745-748.

[8]󰀁施建宇,潘泉,张绍武,等.基于多特征融合的蛋白质折叠子预

测[J].北京生物医学工程,2006,25(5):482-485.[9]󰀁PLATTJC.Probabilisticoutputsforsupportvectormachinesandcom󰀁parisontoregularizedlikelihoodmethods[C]//AdvancesinLargeMarginClassifiers.Cambridge,MA:MITPress,2000:61-74.[10]娄震,金忠,杨静宇.基于类条件置信变换的后验概率估计方法[J].计算机学报,2005,28(1):19-24.[11]RICHARDOD,PETEREH,DAVIDGS.Patternclassification[M].李宏东,姚天翔,等译.北京:机械工业出版社,2003:151-158.

[12]业宁,王迪,窦立君.信息熵与支持向量的关系[J].广西师范大

学学报:自然科学版,2006,24(4):127-130.图3󰀁三种方法在不同特征选取方案下的分类准确率

图3中横轴表示各种不同的特征选取方案,共有11种选取方案,C1、C2、C3、C4分别表示萼片长度、萼片宽度、花瓣长度、花瓣宽度四种特征。如方案C1,C2表示选取萼片长度,萼片宽度两个特征,分别用SVM、SVM󰀁KNN、基于SVM󰀁KNN的多特征融合分类方法三种方法进行分类,纵轴表示平均分类准确率。通过图3可以看出:11种特征选取方案中,基于SVM󰀁KNN的多特征融合方法的分类正确率高于SVM的有11种,等于或高于SVM󰀁KNN的有8种。并且SVM󰀁KNN和SVM的所有融合方案的平均分类准确率分别只有81.3%和52.6%,而基于SVM󰀁KNN的多特征融合分类方法的平均准确率为83.4%,分别比SVM和SVM󰀁KNN方法提高了28.7%和1.9%。同时,从最后一个融合方案C1,C2,C3,C4(选取样本的所有特征),可以看出只采用SVM或SVM󰀁KNN方法对测试样本进行分类的平均准确率为54%和79%,而基于SVM󰀁KNN的多特征融合分类方法的分类准确率为87%,比SVM和SVM󰀁KNN准确率分别提高了32%和8%。从以上分析可以看出,基于SVM󰀁KNN的多特征融合分类方法与SVM或SVM󰀁KNN分类方法相比有较高的准确率。

图4比较了基于SVM和SVM󰀁KNN两种分类器的多特征融合方法的分类准确率,横轴表示参与融合的特征选取方案,纵轴表示分类准确率。从图中可以看出,基于SVM󰀁KNN的多特征融合方法的11种融合方案的分类准确率均高于基于SVM的多特征融合方法,且基于SVM的多特征融合方法的平均准确率只有70.8%,比基于SVM󰀁KNN的多特征融合方法的平均准确率低12.6%。这表明基于SVM󰀁KNN的多特征融合方法是一种比基于SVM更有效的多特征融合方法。

与此同时,对比基于SVM󰀁KNN的多特征融合分类方法中的11种融合方案,从C1,C3与C1,C2,C3,C1,C4与C1,C2,C4,C1,C3,C4与C1,C2,C3,C4的分类准确率可以看出