第33卷第4期2009年8月南京理工大学学报(自然科学版)JournalofNanjingUniversityofScienceandTechnology(NaturalScience)Vol.33No.4

Aug.2009

　收稿日期:2008-10-17 修回日期:2009-05-18

　基金项目:国家自然科学基金(60603029)　作者简介:潘志松(1973-),男,博士,副教授,主要研究方向:模式识别,网络安全,E2mail:Hotpzs@hotmail.com。

单实例分类算法研究潘志松1,燕继坤2,杨绪兵3,缪志敏1,陈　斌3(1.解放军理工大学指挥自动化学院,江苏南京210007;2.西南电子研究所,四川成都610041;

3.南京航空航天大学计算机科学与技术学院,江苏南京210016)

摘　要:针对不平衡分类问题的极端情况,即用于训练的样本极少甚至只有一个实例,该文提出了一种单实例分类算法,这种方法使用球面作为分类面,在目标类的单实例在球内和反类尽量位于球面外的约束条件下,最大化该分类球面的半径,该方法能够有效地处理线性可分的数据分布。当输入样本分布结构呈高度非线性时,该算法通过核映射将低维输入空间中的非线性可分问题变换为高维特征空间中可能的线性可分问题,并以内积形式刻画,最终在特征空间上通过核技巧获得原问题的解决。通过对标准数据集和实际数据集的实验,验证了单实例分类算法在处理数据不平衡问题上的有效性。关键词:单实例;核方法;分类;支持向量中图分类号:TP18 文章编号:1005-9830(2009)04-0444-06

ClassificationAlgorithmBasedonSingleSamplePANZhi2song1,YANJi2kun2,YANGXu2bing3,MIAOZhi2min1,CHENBin3(1.InstituteofCommandAutomation,PLAUniversityofScienceandTechnology,Nanjing210007,China;

2.TheWest2SouthElectronicsInstitute,Chengdu610041,China;3.DepartmentofComputerScienceandEngineering,NanjingUniversityofAeronautics&Astronautics,Nanjing210016,China)

Abstract:Inordertosolvetheextremesituationthatonlyafewtargetexamplesoronlyonecanbeusedintrainingtheclassification,asinglesampleclassificationalgorithmispresentedhere.Spheri2calsurfacesareappliedasclassifiedhypersphere,andthelargestradiuscanbeobtainedenclosingthesinglesampleundertherestrictionthatalloutliersareoutsidethehypersphere.Itfailswhenthedistributionofinputpatternsiscomplex.Theclassifierapplieskernelmeans,performinganonlineardatatransformationintosomehighdimensionalfeaturespace,increasestheprobabilityofthelinearseparabilityofthepatternswithinthefeaturespaceandthereforesolvestheoriginalclassificationproblem.Thepaperverifiesthatthealgorithmcaneffectivelydealwiththeunbalanceddataclassifi2cationonvarioussyntheticandUCIdatasets.Keywords:singlesamples;kernelmeans;classification;supportvectors总第167期潘志松　燕继坤　杨绪兵　缪志敏　陈　斌　单实例分类算法研究　 机器学习中往往假定有几个类,每类有若干训练实例,而且根据PAC学习理论,为了达到比较高的准确率,希望有比较多的训练实例[1]。但在实际应用中,有时也会出现“单实例”的问题。例如,人脸识别、指纹识别等生物特征一般为每个人采集一个训练样本。这时虽然有很多个类,但每类只有一个训练样本,把这个问题称为“单实例分类问题”[2],这也是数据不平衡分类中的极端问题。在模式识别应用中,多类别的分类问题可以转化为多个两分类问题,即将c类问题化为c-1个两分类问题,每个分类器只对其中的两个类别进行分类,这种做法当样本数量较多时比较有效。但是当样本数量稀少,即每个分类器都只有很少的样本用来训练。特别是只有一个样本的时侯,训练得到的分类效果较差甚至不能工作,如图1。针对每一类样本比较少或者只有一个的特点,笔者设想对于每个类别,将单个正实例作为正例训练样本,而所有其它的样本作为反类实例用于训练,这样就增加了训练样本的个数,可以提高总体分类器的分类能力,然后再对这些单实例分类器进行集成学习[3,4],就可以实现对多类别的分类。所以本文只针对两分类的单实例分类算法展开研究。对于该单实例分类器,它的训练实例的正类为目标类训练实例,即单实例,反类为所有其它类的训练实例的总和。由于两类训练的实例数严重不平衡,因此原问题可以转化为一个不平衡分类的问题。图1　单实例问题的多类别情况对于数据严重不平衡的分类问题,可以借鉴单类分类器的思想。单类分类器的主要目的就是定义一个围绕该目标类物体的边界,接受尽量多的目标类样本,而尽可能地拒绝其它类。Tax等提出的支持向量数据描述(Supportvectordatadescription,简称SVDD)试图寻找一个封闭的超球面来包围目标集[4],只有落入超球体以内的实例才属于目标类,超球面的确定仅依靠目标类的训练数据。为了减少错误的接受,要尽量缩小球的体积。超球面由球心a和半径R决定,在约束条件下最小化结构风险误差,和SVM类似,通过解决二次优化问题可得到a、R的解。这样要求数据分布在欧氏空间呈球形分布,如果目标集不是“球形”的,则使用核方法,把特征向量向高维映射,并进一步使用核函数替代内积运算。核方法隐含地通过核函数实现了一个从低维输入空间到高维特征空间的映射,既避免了计算上的维数灾难,又使问题在特征空间中得到简化并得到有效的解决[5]。本文借鉴了单类分类器的思想,提出了“单实例”条件下的分类算法,其也通过一个球形分类面进行分类,但和SVDD不同的是,该算法从两分类问题出发,用球面包围“单实例”的同时,使得所有的反类都位于球面之外,在这两个条件下,

最大化球的半径。由于只有一个“稀少”的正类实例,需要充分利用这一个实例,使之确定在定义的球内,同时最大化求得体积来优化分类器的泛化性能。论文通过推导给出了分类决策面的表达式,并在国际标准数据集上进行了实验,验证了该单实例分类算法的有效性。

1　单实例分类算法图2给出了单实例分类的示意,考虑两分类的特殊情况:正类实例只有一个,定义标号为“+”,如图所示,但有很多反类实例,标号为“-”。笔者设想用一个球面包围正类,为了使形成的分类面能够正确分类但又不会拒绝正类,所以在使反类都位于球面之外的条件下,使这个球的半径尽可能的大。由于只有一个“稀少”的正类实例,需要充分利用这一个实例,使之尽可能包含在定义的球内。

图2　单实例分类示意图设xi(i=1,2,…,n)为反例,x+为正例。目的是设计一个球体的分类面,保证反类都位于球面之外和正例样本能够被包含在球内的条件下,

使这个球的半径尽可能的大。符号说明:负类样本x

1,x2,…,xn,

单个正类

544　南京理工大学学报(自然科学版)第33卷第4期样本x+。原理:生成包含正类样本,且排斥所有负类样本的最大球,球的半径为R,球心为a。单实例模型如下:　minC-∑ni=1ξi+C+‖x+-a‖2-R2(1)Ⅰ.　s.t.　‖x+-a‖2问题:

　max　∑n1i=1αi‖xi-a‖2-β‖x+-a‖2s.t.　0≤αi≤C-,i=1,2,…,n∑n

i=1αi-β=1

(10)

将式(9′)代入式(10)目标函数中并化简,以矩阵形式表示如下:

　max　∑n+1i=1󰁪αi󰁪xTi󰁪xi-∑n+1i,j=1󰁪αi󰁪αj󰁪xTi󰁪x

j

　s.t.　0≤󰁪αi≤C

-,i=1,2,…,n

󰁪αn+1≤0

∑n+1

i=1󰁪α

i=1

(11)

以矩阵形式表示如下:

　max　󰁪αTdiag(XTX-󰁪αTXTX󰁪α

s.t.　0≤ET󰁪α≤C-1n×1

󰁪αT

e

n+1

≤0

󰁪αT

1

(n+1)×1

=1

(12)

其中diag(A)表示取A的对角线元素作为列向量。其中ei表示n+1维向量,除第i个元素为1外,其余的全为0。并记E=[e1　e2　…　en]。1n×1是n维列向量,其元素全为1。当输入空间的样本点不满足球状分布时,可用核方法在高维特征空间中解决。先通过非线性映射<,把输入空间的样本映射到高维空间,在映射后的高维空间中通过核代入实现问题求解。即将上述公式中的内积形式都用核函数代替如下[7]:

　󰁪xTi󰁥xj→<(󰁪x

i)T<(󰁥xj)=K(󰁥xi,󰁥xj)(13)

选择一个适当的核函数也是比较重要的,如果选取的核函数能够将输入空间正好映射成高维空间的一个球体分布,那么所求得的分类器也会比较吻合实际的分布情况。常用的核函数有[5]:

(1)多项式核函数　K(x,y)=(1+x・y)

d

(14)

(2)GaussianRBF

核函数

　K(x,y)=exp

-

‖x-y‖2

σ2(15)

(3)Sigmoid

核函数

　K(x,y)=tanh[b(x・y)-c](16)

引入核函数后,原来的公式变成了如下形式:

当分类边界不是圆形时,可以把数据由低维映射到高维,以增强学习机的表达能力,在高维空间可

644