基于模糊核聚类的svm多类分类方法

基于模糊核聚类的svm多类分类方法

0svm多类分类方法支持向量机（svm）作为一种机器学习方法，可以更好地解决非线性、高维数和局部小距离问题，并具有其他机器学习方法的优势。但是,SVM是针对两类分类问题提出的,而实际中多类分类问题更为普遍,如何将SVM的优良性能推广到多类分类一直是SVM研究的一个重要问题,尤其对于大类别分类问题,目前还缺乏有效的SVM多类分类方法。大类别分类问题类别数目多,训练样本规模大,在已提出的SVM多类分类方法中:一次性求解方法因计算复杂度过高、精度较低而不实用;one-against-one(1-a-1)方法、directedacyclicgraph(DAG)方法因需要训练的SVM数目太多而训练速度较低;one-against-rest(1-a-r)方法因每个SVM都是在全部训练样本上学习的,而同样具有较低的训练速度;基于二叉分类树的decision-tree-basedmulticlasssupportvectormachines(DT-SVM)方法和hierarchicalsupportvectormachines(H-SVM)方法因模糊类之间交叠严重以及分类树的错分积累而精度较低。本文首先分析了已提出的各种SVM多类分类方法存在的问题,然后提出了一种基于模糊核聚类的SVM多类分类方法(supportvectormachinesmulti-classclassificationbasedonfuzzykernelclustering,FKC-SVMmulti-classclassification),并给出了一种快速半模糊核聚类算法。新方法利用模糊核聚类生成模糊类,并采用树结构将多个两类分类器组合起来实现多类分类。模糊核聚类不但能够较好地分辨、提取并放大有用的特征,实现更为准确的聚类,而且能够挖掘有关模糊类的外围、不同模糊类之间的衔接和离散信息。利用这些信息能够使分类器在具有树型结构识别效率高的特点的同时,减少训练样本的规模、发现模糊类中的野值点,从而提高分类器的训练速度和精度。实验表明了新方法的有效性。1模糊类生成方法对识别精度的影响SVM最初是针对两类分类问题提出的,用于多类分类问题必须将其推广。目前,已提出的SVM多类分类方法大致可分为两类:一次性求解法和分解重构法。一次性求解法是在所有训练样本上求解一个大型二次规划问题,同时将所有类别分开,该方法变量个数多,计算复杂度很高,尤其当类别数目较多时,它的训练速度很低,分类精度也不高。分解重构法是一种将多类分类问题转化为多个两类分类问题,并采用某种策略将多个两类分类器组合起来实现多类分类的方法。实验表明,分解重构法比一次性求解法更适合于实际应用。用分解重构法实现多类分类需要解决两个关键问题:模糊类的生成方法和多个两类分类器的组合策略。目前,已提出的SVM分解重构法主要包括:1-a-r、1-a-1、DAG、DT-SVM和H-SVM等,表1对上述方法进行了对比。模糊类生成方法决定了两类分类器的个数、各两类分类器的训练样本数目和模糊类间的交叠程度,进而对多类分类器的训练速度、分类速度和精度有较大影响。在上述方法中,1-a-r的模糊类方法是依次将所有类别中的一个类别与其余类别分开的“一对其余”方法,1-a-1和DAG的模糊类就是原始类别。直接用原始类别作为模糊类时,模糊类的可分性相对较好,分类器的分类精度较高,但所付出的代价是需要训练的SVM数目较多,训练速度较慢。1-a-r需要训练的SVM数目相对较少,但是各SVM都是在全部训练集样本上进行学习的,因而,当样本数较多时,训练速度依然很慢,而且模糊类之间的交叠严重。文献给出的DT-SVM的模糊类生成方法实际上是一种在分类树的各个决策节点的“一对其余”方法,该方法生成的模糊类依然存在交叠严重、野值点数目多的问题。文献给出的H-SVM的模糊类生成方法则是在输入空间对分类树的各个决策节点所包含的训练样本进行聚类,然后根据聚类结果生成模糊类。多类分类问题类别数目多,训练集样本分布复杂,而输入空间聚类的有效性在很大程度上取决于样本的分布情况,因而,H-SVM的模糊类生成方法的效果通常也不好。另外,分解重构方法的组合策略影响了多类分类器的识别效率。在已提出的分解重构法中,1-a-r采用最大输出法将多个分类器的输出组合起来实现多类分类,1-a-1采用投票法决定未知样本的类别,这两种方法分类时都需要遍历所有的SVM分类器,因而识别效率低。DAG与1-a-1的模糊类方法相同,但分类时DAG采用树结构将多个分类器组合起来实现多类分类,从而具有比1-a-1快得多的分类速度。DT-SVM和H-SVM也是采用树结构的组合策略,具有较高的训练和分类速度,但是它们生成的模糊类交叠严重,而分类树又存在错分积累,因而分类精度较低。由以上分析可知,首先,对于大类别多类分类问题,目前已提出的方法或者训练速度过慢(如1-a-1、DAG、1-a-r),或者因分类精度过低而不适用于精度要求较高的场合(如DT-SVM、H-SVM)。另外,通过对比各种方法表明,树结构是一种提高大类别多类分类器识别效率的有效方法,但是,树结构存在差错积累,当模糊类生成不当时,分类精度较低。为了提高树型分类器的精度,应解决以下问题:(1)由多个类别组成的模糊类之间的交叠严重,野值点对SVM的影响较大;(2)树结构存在差错积累。2模糊核聚类算法模糊核聚类就是依照核方法思想,首先用非线性映射把输入空间的数据映射到高维特征空间,扩大模式类之间的差异,然后在特征空间中对数据进行模糊聚类的方法。令x1,x2,…,xn∈RN为输入空间中的一个样本集,ϕ(xi)是将样本xi映射到高维特征空间的非线性映射,设在特征空间中采用模糊c-聚类算法把样本集划分成为c个模糊簇,模糊划分矩阵U={μji1≤j≤c,1≤i≤n},μji∈[0,1]表示xi隶属于第j个簇的程度,vj是第j个簇的聚类中心,m∈(1,∞)是模糊加权指数,模糊核聚类对应的优化问题为minJkm(U,V)=c∑i=1n∑k=1(μik)m⋅∥ϕ(xi)-ϕ(vj)∥2E=c∑j=1n∑i=1(μji)m(k(xi,xi)-2k(xi,vj)+k(vj,vj))(1)s.t.c∑j=1μji=1,对∀i(2)minJkm(U,V)=∑i=1c∑k=1n(μik)m⋅∥ϕ(xi)−ϕ(vj)∥2E=∑j=1c∑i=1n(μji)m(k(xi,xi)−2k(xi,vj)+k(vj,vj))(1)s.t.∑j=1cμji=1,对∀i(2)模糊核聚类具有如下优势:(1)通过非线性映射能较好地分辨、提取并放大有用的特征,从而能实现更为准确的聚类,在输入空间聚类算法失效的情况下,核聚类算法也能够得到正确的聚类;(2)模糊聚类的结果能指明划分的外围、不同划分块间的衔接和离散情况,因此能挖掘更多的细节信息。按模糊c-聚类的优化方法,可以得到如下模糊核聚类算法的迭代公式μji=(1dji)1m-1/c∑j=1(1dji)1m-1(3)ϕ(vj)=n∑i=1(μji)mϕ(xi)/n∑i=1(μji)m(4)μji=(1dji)1m−1/∑j=1c(1dji)1m−1(3)ϕ(vj)=∑i=1n(μji)mϕ(xi)/∑i=1n(μji)m(4)并有模糊c-聚类算法收敛速度较慢,为了结合硬聚类收敛速度快和模糊聚类对初始化不敏感而且能反映样本间相近信息等优点,Selim、Ismail、Kamel以及裴继红等人提出了半模糊划分方法。本文将半模糊聚类算法推广到模糊核聚类算法中,给出了一种收敛速度较快的半模糊核聚类算法。算法1λ=0.65+1/2c步骤1选择迭代停止条件ε∈(0,1),最大迭代次数T;步骤2初始化类中心v1,v2,…,vc;步骤3计算dji(xi,vj)=k(xi,xi)-2k(xi,vj)+k(vj,vj),并令Qi=c∑j=1∑j=1c(1dji)1m-1‚i=1,2,⋯,n;步骤4对每个类别j,j=1,2,…,c,首先计算djp=min(dji);如果某个样本xs的djs=0,那么μji={1,i=s0,i≠s如果所有样本的dji都不为零,并有(1djp)1m-1Qp≥λ,那么μji={1,i=p0,i≠p如果所有样本的dji都不为零,并有(1djp)1m-1Qp<λ,那么用式(3)计算μji;步骤5用μji按式(6)、式(7)计算k(xi,vj),k(vj,vj);步骤6用新k(xi,vj),k(vj,vj)返回步骤3-步骤4计算μji的新值μ*ji;步骤7若maxμji-μ*ji<ε或达到最大迭代次数T,则终止,否则,转步骤5。3类别交叠结构本文提出的FKC-SVM多类分类方法是一种分解重构法,它首先利用模糊核聚类生成模糊类,挖掘有关模糊类的外围、不同模糊类之间的衔接和离散信息,并根据这些信息减少训练样本的规模、发现模糊类中的野值点并通过给它们加以较小的权值以减少它们对分类的不利影响,然后采用树结构将多个两类分类器组合起来实现多类分类。FKC-SVM方法与其它已提出的采用树结构的SVM多类分类方法的不同之处在于:(1)模糊类的生成方法不同;(2)多类分类模糊类间的交叠严重,野值点数目比两类分类更多,FKC-SVM方法利用模糊核聚类发现野值点并设法减少野值点对分类的不利影响,而其它方法没有这方面的相应措施;(3)FKC-SVM方法根据模糊核聚类提供的信息,仅用可能是支持向量的训练样本训练SVM,从而进一步加快了分类器的训练速度。(4)FKC-SVM方法允许部分类别存在如图1(b)所示的交叠来克服错分积累,而其它采用树结构的方法,如DT-SVM、H-SVM等不允许类别交叠。通常,交叠会降低分类器的速度,但是本文一方面根据模糊核聚类的结果只对在模糊类之间交叠特别严重的类别采用交叠结构,另一方面只用可能成为支持向量的训练样本训练SVM。实验表明,在FKC-SVM方法中,交叠对分类器速度的影响不是很大。FKC-SVM方法首先将多类分类中的所有类别划分为两个子类(模糊类),然后再将子类中所包含的类别划分到两个次级子类中,如此循环,直到子类中只包含一个类别为止,这样就得到了一个倒立的二叉分类树。相应地,FKC-SVM方法模糊类的生成过程就是从根节点开始,按下文提到的算法2将节点所包含的类别划分为到两个子类中,直到子类中只包含一个类别为止。设某节点包含类别C1,C2,…,Ct,其中类别Cj在该节点的训练样本集Trj的样本数为Nj,按下述将类别Cj(j=1,2,…,t)划分到两个子类S1或S2中:算法2(参数0≤δ<1)步骤1令c=2,利用算法1对训练集Tr1∪Tr2…∪Trt进行模糊核聚类,得到类别Cj(j=1,2,…,t)的样本xji对S1和S2的隶属度分别为μj1i和μj2i,将满足条件μj1i-μj2i>0,μj1i-μj2i<0、μj1i-μj2i=0的样本分别分到集合Tj1、Tj2、Tj3中,并设Tj1、Tj2、Tj3中的样本数分别为为Nj1,Nj2,Nj3;步骤2对于类别Cj(j=1,2,…,t),如果|Νj1Νj-Νj2Νj|>δ,则将类别Cj划分到S1(当Νj1Νj>Νj2Νj)或S2(当Νj1Νj<Νj2Νj)中,并且:如果Cj∈Sp且Njq≠0,(p,q=1,2,p≠q),则对集合Tjq中的样本加以小于1的权值(加权方法见本节末尾),否则,Cj中样本的权值均为1;步骤3对于类别Cj(j=1,2,…,t),若|Νj1Νj-Νj2Νj|≤δ,则将集合Tj1划分到S1中,Tj2划分到S2中,Tj3划分到S1(当Nj1<Nj2)或S2(当Nj1≥Nj2)中,Cj中样本的权值均为1。算法中,参数δ越大,存在交叠结构的类别数目越多。另外,设步骤2的Tjq中的样本x1,x2,…,xNjq对Sq的隶属度为μjq1,μjq2,…,μjqNjq并有μjq1≤μjq2≤…μjqNjq。由于μjqi越大,样本xi离Sp越远,权值应越小,所以可令样本xi的权值ti与μjqi的函数关系为ti=aμjqi+b(8)并当μjqi=0.5时,取ti=1,当μjqi=μjqNjq,取ti=εj<1,由此可得:a=1-εj0.5-μjqΝjq,b=0.5εj-μjqΝjq0.5-μjqΝjq。所以,可按下式计算Tjq中的样本xi的权值titi=1-εj0.5-μjqΝjqμjqi+0.5εj-μjqΝjq0.5-μjqΝjq(9)式(9)中,μjqNj越大,参数εj的取值应越小。从根节点开始,生成各节点的两个模糊类之后,再从每个模糊类中选择对该模糊类的隶属度小于1的样本训练模糊支持向量机(在本文的半模糊核聚类算法中,当样本以很大的概率属于某一子类时,算法使得其对于该子类的隶属度为1,而对另一子类的隶属度为0),这样可以减少SVM的训练样本数,提高分类器的训练速度。从上述模糊类的生成和训练样本的选择可以看出,FKC-SVM方法利用模糊核聚类提供的信息减少了训练样本的规模、野值点对分类的不利影响和错分积累的发生,因而能有效提高分类器的速度和精度。4分类精度分析表2对比了各种方法对各数据集的最高分类精度,以及在具有最高分类精度时的训练时间、支持向量数目(#SV)、测试时所需SVM的平均数目(#SVM)。其中,支持向量数目是指在相应方法的各个两类SVM分类器中,至少有一次成为支持向量的训练样本数目。对于没有测试集的数据集,由于采用ten-foldcross-validation训练SVM,最终的支持向量数目是指各次训练SVM所得的支持向量数目的平均值,因而#SV为小数。在FKC-SVM方法中,参数δ的选择影响了存在交叠的类别数,如果参数δ选择过大,相当于用非常复杂的函数完全将训练集分开,不但降低了分类器的训练速度,而且易于引起分类器产生过学习。表2中,数据集Glass和Vehicle分别有一个类别存在交叠结构,其余数据集不存在交叠结构。从表2可以看出,就分类精度而言,FKC-SVM方法和1-a-1、DAG方法具有相对较高的分类精度,而H-SVM和DT-SVM的分类精度相对较低。1-a-1、DAG直接采用原始类别作为模糊类,各模糊类间的可分性相对较好,分类精度较高;FKC-SVM基于模糊核聚类方法生成模糊类,并采用样本加权和交叠技术消除野值点和错分积累对分类的不利影响,获得了与1-a-1和DAG方法相当甚至更高的分类精度。H-SVM和DT-SVM也是基于树结构的多类分类方法,它们与FKC-SVM方