【机器学习】采用划分融合双向控制的粒度支持向量机

第14卷第6期 智能系统学报 Vol.14 No.6 2019年11月 CAAI Transactions on Intelligent Systems Nov.2019 D0:10.11992/tis.201904047 网络出版地址：http:/kns.cnki.net/kcms/detail/23.1538.tp.20190722.1417.006.html 采用划分融合双向控制的粒度支持向量机 赵帅群，郭虎升2，王文剑 (1.山西大学计算机与信息技术学院，山西太原030006；2.山西大学计算智能与中文信息处理重点实验室， 山西太原030006) 摘要：粒度支持向量机(granular support vector machine,GSVM)引入粒计算的方式对原始数据集进行粒度划分 以提高支持向量机(support vector machine,SVM)的学习效率。传统GSVM采用静态粒划分机制，即通过提取划 分后数据簇中的代表信息进行模型训练，有效地提升了SVM的学习效率，但由于GSVM对信息无差别的粒度 划分导致对距离超平面较近的强信息粒提取不足，距离超平面较远的弱信息粒被过多保留，影响了SVM的学 习性能。针对这一问题，本文提出了采用划分融合双向控制的粒度支持向量机方法(division-fusion support vec- tor machine,DFSVM)。该方法通过动态数据划分融合的方式，选取超平面附近的强信息粒进行深层次的划分， 同时将距离超平面较远的弱信息粒进行选择性融合，以动态地保持训练样本规模的稳定性。通过实验表明，采 用划分融合的方法能够在保证模型训练精度的条件下显著提升SVM的学习效率。 关键词：支持向量机：粒度支持向量机；划分：融合；强信息粒；弱信息粒：动态机制：双向控制 中图分类号：TP18文献标志码：A文章编号：1673-4785(2019)06-1243-12 中文引用格式：赵帅群，郭虎升，王文剑.采用划分融合双向控制的粒度支持向量机J.智能系统学报，2019,14(6)： 1243-1254. 英文引用格式：ZHAO Shuaiqun,GUO Husheng,WANG Wenjian..Granular support vector machine with bidirectional control of division-fusion[J].CAAI transactions on intelligent systems,2019,14(6):1243-1254. Granular support vector machine with bidirectional control of division-fusion ZHAO Shuaiqun',GUO Husheng2,WANG Wenjian2 (1.School of Computer and Information Technology,Shanxi University,Taiyuan 030006,China;2.Key Laboratory of Computation- al Intelligence and Chinese Information Processing,Shanxi University,Taiyuan 030006,China) Abstract:Granular support vector machine(GSVM)introduces the method of granular computing to divide the original dataset;therefore,GSVM improves the efficiency of the support vector machine(SVM).The traditional GSVM adopts the static granules partitioning mechanism to extract representative information from the divided data clusters for model training,which can effectively increase the learning efficiency of the SVM.However,the GSVM uses the same pro- cessing way for different information granules,which may lead to a decline in the generalization ability because of two reasons:(i)No sufficient valid information is extracted from the strong information granules that are close to the hyper- plane,and(ii)excess of the weak information of granules far from the hyper-plane is reserved.These all reduce the learning performance of the SVM.To address this problem,this study proposes a division and fusion SVM model based on dynamical granulation,namely DFSVM.With the DFSVM,the information from the strong information granules near the hyper-plane is divided in depth,and weak information from weak information granules far from the hyper-plane is selectively merged to dynamically maintain the stability of the size of the training samples.The experiments demon- strate that this model can significantly improve the SVM learning efficiency,ensuring the training precision of the model. Keywords:support vector machine(SVM);granular support vector machine(GSVM),division;fusion;strong informa- tion granule;weak information granule;dynamic mechanism;bidirectional control 收稿日期：2019-04-19.网络出版日期：2019-07-23. 基金项目：国家自然科学基金项目(61673249.61503229 支持向量机(support vector machine,SVM)是 U1805263):山西省回国留学人员科研基金项目 由Vapnik等山提出的基于统计学习理论和结构 (2016-004). 通信作者：王文剑.E-mail:wjwang(@sxu.edu.cn. 风险最小化准则的一种学习策略，在小样本多维

DOI: 10.11992/tis.201904047 网络出版地址: http://kns.cnki.net/kcms/detail/23.1538.tp.20190722.1417.006.html 采用划分融合双向控制的粒度支持向量机 赵帅群1 ，郭虎升1,2，王文剑2 （1. 山西大学 计算机与信息技术学院，山西 太原 030006; 2. 山西大学 计算智能与中文信息处理重点实验室， 山西 太原 030006） 摘 要：粒度支持向量机 (granular support vector machine，GSVM) 引入粒计算的方式对原始数据集进行粒度划分 以提高支持向量机 (support vector machine, SVM) 的学习效率。传统 GSVM 采用静态粒划分机制，即通过提取划 分后数据簇中的代表信息进行模型训练，有效地提升了 SVM 的学习效率，但由于 GSVM 对信息无差别的粒度 划分导致对距离超平面较近的强信息粒提取不足，距离超平面较远的弱信息粒被过多保留，影响了 SVM 的学 习性能。针对这一问题，本文提出了采用划分融合双向控制的粒度支持向量机方法 (division-fusion support vec￾tor machine，DFSVM)。该方法通过动态数据划分融合的方式，选取超平面附近的强信息粒进行深层次的划分， 同时将距离超平面较远的弱信息粒进行选择性融合，以动态地保持训练样本规模的稳定性。通过实验表明，采 用划分融合的方法能够在保证模型训练精度的条件下显著提升 SVM 的学习效率。 关键词：支持向量机；粒度支持向量机；划分；融合；强信息粒；弱信息粒；动态机制；双向控制 中图分类号：TP18 文献标志码：A 文章编号：1673−4785(2019)06−1243−12 中文引用格式：赵帅群, 郭虎升, 王文剑. 采用划分融合双向控制的粒度支持向量机 [J]. 智能系统学报, 2019, 14(6): 1243–1254. 英文引用格式：ZHAO Shuaiqun, GUO Husheng, WANG Wenjian. Granular support vector machine with bidirectional control of division-fusion[J]. CAAI transactions on intelligent systems, 2019, 14(6): 1243–1254. Granular support vector machine with bidirectional control of division-fusion ZHAO Shuaiqun1 ，GUO Husheng1,2 ，WANG Wenjian2 (1. School of Computer and Information Technology, Shanxi University, Taiyuan 030006, China; 2. Key Laboratory of Computation￾al Intelligence and Chinese Information Processing, Shanxi University, Taiyuan 030006, China) Abstract: Granular support vector machine (GSVM) introduces the method of granular computing to divide the original dataset; therefore, GSVM improves the efficiency of the support vector machine (SVM). The traditional GSVM adopts the static granules partitioning mechanism to extract representative information from the divided data clusters for model training, which can effectively increase the learning efficiency of the SVM. However, the GSVM uses the same pro￾cessing way for different information granules, which may lead to a decline in the generalization ability because of two reasons: (i) No sufficient valid information is extracted from the strong information granules that are close to the hyper￾plane, and (ii) excess of the weak information of granules far from the hyper-plane is reserved. These all reduce the learning performance of the SVM. To address this problem, this study proposes a division and fusion SVM model based on dynamical granulation, namely DFSVM. With the DFSVM, the information from the strong information granules near the hyper-plane is divided in depth, and weak information from weak information granules far from the hyper-plane is selectively merged to dynamically maintain the stability of the size of the training samples. The experiments demon￾strate that this model can significantly improve the SVM learning efficiency, ensuring the training precision of the model. Keywords: support vector machine (SVM); granular support vector machine (GSVM); division; fusion; strong informa￾tion granule; weak information granule; dynamic mechanism; bidirectional control 支持向量机 (support vector machine，SVM) 是 由 Vapnik 等 [1] 提出的基于统计学习理论和结构 风险最小化准则的一种学习策略，在小样本多维 收稿日期：2019−04−19. 网络出版日期：2019−07−23. 基金项目：国家自然科学基金项 目 (61673249， 61503229， U1805263)；山西省回国留学人员科研基金项目 (2016-004). 通信作者：王文剑. E-mail：wjwang@sxu.edu.cn. 第 14 卷第 6 期 智 能 系 统 学 报 Vol.14 No.6 2019 年 11 月 CAAI Transactions on Intelligent Systems Nov. 2019

·1244· 智能系统学报 第14卷 度的数据分类和回归问题方面表现出了优良的泛 问题进行抽象和简化，以较低的代价来得到问题 化性能，广泛应用于机器学习、模式识别、模式分 的满意近似解。在多种的粒划分方式中，基于聚 类、图像处理等领域2。目前在大规模数据处理 类的粒度支持向量机(clustering-based granular 方面，SVM仍存在一些不足。主要问题是当样本 support vector machine,.CGSVM)是当前研究的热 数n较大时，会消耗大量的内存空间和运算时间， 点之一2-21。CGSVM通过聚类算法将大规模数 严重降低了SVM的学习效率，限制了SVM在大 据集分解成多个小规模数据簇，簇内信息具有高 规模数据集上的应用。 度相似性，而簇间信息相似度较低，挑选出每个 粒度支持向量机的含义最早由Tang等9提 簇中具有代表性的样本信息作为新的训练样本， 出，其主要思想是首先构建粒度空间获得一系列 整合所有挑选出的样本训练得到新的模型。 信息粒，然后在每个信息粒上进行SVM学习，最 CGSVM只采用了少量代表样本作为训练 后聚合信息粒上的信息获得最终的决策函数。依 集，有效地加速了SVM学习过程。但CGSVM本 据粒划分方式的不同，衍生出了基于聚类的GS- 身也存在一些不足，在SVM学习过程中，距离分 VM、基于分类的GSVM以及基于关联规则的 类超平面较近的信息对分类起关键作用，而距离 GSVM等方法o-19。GSVM采用粒化的方式压缩 超平面较远的信息几乎不影响模型训练过程。 数据集的规模，以提高SVM的学习效率，而目前 CGSVM在数据处理过程中没有区分不同信息粒 的GSVM大都在静态层级进行划分，即只对信息 对分类的影响程度，对所有信息粒都进行同等层 粒进行有限次的浅层次划分，丢失了大量对分类 次的划分，导致对重要信息提取不足且仍存在过 起关键作用的样本信息，且冗余信息较多，降低 多的冗余信息。如图1中，距离超平面较近的 了模型的性能。尽管已经提出的动态粒度支持向 G、G、G、G、G、G中包含较多支持向量信息， 量机(dynamic granular support vector machine, 对分类起到了关键作用，距离超平面较远的G、 DGSVM)2o,以及动态支持向量回归机(dynamic G;、G5、G6对分类影响较小。尽管DGSVM通过 granular support vector regression,DGSVR), 对超平面附近重要信息粒深度划分，但远端的冗 动态的方式对重要信息粒深层次划分，对无关信 余信息仍然被保留，在动态划分过程中数据规模 息粒则进行浅层次划分，但DGSVM随着粒划分 会不断增加，导致训练时间也不断地提高。 过程会使数据规模不断增加，使得SVM的效率 G 有所降低。 为了进一步提升SVM在大规模数据集上的 △ 应用能力，本文提出了采用划分融合双向控制的 △ 粒度支持向量机方法。在SVM分类过程中，对 A 分类起关键重要的信息分布于超平面附近，称为 强信息区，超平面远端的信息对分类影响较小， 00 G G 称为弱信息区，本文提出的方法通过对强信息区 G 的强信息粒进行深度划分，同时融合弱信息区的 图1 CGSVM粒度划分 弱信息粒，使训练数据始终动态保持在较小规 Fig.1 CGSVM granular division 模。该方法分为两个阶段，首先通过聚类算法对 2 原始数据集进行初始粒划分，挑选粒中代表信息 DFSVM模型 组成新的训练集训练得到初始分类超平面，然后 现阶段CGSVM通过静态的、浅层次的方式， 通过迭代划分融合的方式深度划分强信息粒，同 对粒划后的信息粒进行无差别的信息提取，导致 时融合远端弱信息粒。实验表明，该方法能够在 对分类起关键作用的信息提取不足且还保留了大 保证模型精度的条件下显著提升SVM的学习效率。 量对分类影响较小的冗余信息。本文提出的方法 1粒度支持向量机 采用多层次的划分策略，由于超平面附近的样本 信息有较大概率成为支持向量，距离超平面较远 粒度支持向量机引人粒计算的概念，对复杂 的样本信息对分类几乎没有影响，因此，DF$

度的数据分类和回归问题方面表现出了优良的泛 化性能，广泛应用于机器学习、模式识别、模式分 类、图像处理等领域[2-8]。目前在大规模数据处理 方面，SVM 仍存在一些不足。主要问题是当样本 数 n 较大时，会消耗大量的内存空间和运算时间， 严重降低了 SVM 的学习效率，限制了 SVM 在大 规模数据集上的应用。 粒度支持向量机的含义最早由 Tang 等 [9] 提 出，其主要思想是首先构建粒度空间获得一系列 信息粒，然后在每个信息粒上进行 SVM 学习，最 后聚合信息粒上的信息获得最终的决策函数。依 据粒划分方式的不同，衍生出了基于聚类的 GS￾VM、基于分类的 GSVM 以及基于关联规则的 GSVM 等方法[10-19]。GSVM 采用粒化的方式压缩 数据集的规模，以提高 SVM 的学习效率，而目前 的 GSVM 大都在静态层级进行划分，即只对信息 粒进行有限次的浅层次划分，丢失了大量对分类 起关键作用的样本信息，且冗余信息较多，降低 了模型的性能。尽管已经提出的动态粒度支持向 量机 (dynamic granular support vector machine， DGSVM)[20] ，以及动态支持向量回归机 (dynamic granular support vector regression，DGSVR)[21] ，采用 动态的方式对重要信息粒深层次划分，对无关信 息粒则进行浅层次划分，但 DGSVM 随着粒划分 过程会使数据规模不断增加，使得 SVM 的效率 有所降低。 为了进一步提升 SVM 在大规模数据集上的 应用能力，本文提出了采用划分融合双向控制的 粒度支持向量机方法。在 SVM 分类过程中，对 分类起关键重要的信息分布于超平面附近，称为 强信息区，超平面远端的信息对分类影响较小， 称为弱信息区，本文提出的方法通过对强信息区 的强信息粒进行深度划分，同时融合弱信息区的 弱信息粒，使训练数据始终动态保持在较小规 模。该方法分为两个阶段，首先通过聚类算法对 原始数据集进行初始粒划分，挑选粒中代表信息 组成新的训练集训练得到初始分类超平面，然后 通过迭代划分融合的方式深度划分强信息粒，同 时融合远端弱信息粒。实验表明，该方法能够在 保证模型精度的条件下显著提升 SVM 的学习效率。 1 粒度支持向量机 粒度支持向量机引入粒计算的概念，对复杂 问题进行抽象和简化，以较低的代价来得到问题 的满意近似解。在多种的粒划分方式中，基于聚 类的粒度支持向量机 (clustering-based granular support vector machine, CGSVM) 是当前研究的热 点之一[22-25]。CGSVM 通过聚类算法将大规模数 据集分解成多个小规模数据簇，簇内信息具有高 度相似性，而簇间信息相似度较低，挑选出每个 簇中具有代表性的样本信息作为新的训练样本， 整合所有挑选出的样本训练得到新的模型。 G + 1 G + 2 G + 3 G − 1 G − 2 G − 3 G + 5 G + 6 G − 5 G − 6 CGSVM 只采用了少量代表样本作为训练 集，有效地加速了 SVM 学习过程。但 CGSVM 本 身也存在一些不足，在 SVM 学习过程中，距离分 类超平面较近的信息对分类起关键作用，而距离 超平面较远的信息几乎不影响模型训练过程。 CGSVM 在数据处理过程中没有区分不同信息粒 对分类的影响程度，对所有信息粒都进行同等层 次的划分，导致对重要信息提取不足且仍存在过 多的冗余信息。如图 1 中，距离超平面较近的 、 、 、 、 、 中包含较多支持向量信息， 对分类起到了关键作用，距离超平面较远的 、 、 、 对分类影响较小。尽管 DGSVM 通过 对超平面附近重要信息粒深度划分，但远端的冗 余信息仍然被保留，在动态划分过程中数据规模 会不断增加，导致训练时间也不断地提高。 G− 4 G− 1 G− 2 G− 5 G− 3 G+ 3 G+ 4 G+ 2 G+ 1 G+ 5 图 1 CGSVM 粒度划分 Fig. 1 CGSVM granular division 2 DFSVM 模型 现阶段 CGSVM 通过静态的、浅层次的方式， 对粒划后的信息粒进行无差别的信息提取，导致 对分类起关键作用的信息提取不足且还保留了大 量对分类影响较小的冗余信息。本文提出的方法 采用多层次的划分策略，由于超平面附近的样本 信息有较大概率成为支持向量，距离超平面较远 的样本信息对分类几乎没有影响，因此，DFS- ·1244· 智 能 系 统 学 报 第 14 卷

第6期 赵帅群，等：采用划分融合双向控制的粒度支持向量机 ·1245· VM采取动态迭代划分的方式，对超平面附近可 面之间的距离D≥y/2+B时，认为样本点对分类 能成为支持向量的信息粒深度划分，同时融合距 超平面影响较小，划分为弱信息区。其中B可在 离超平面较远的冗余信息，不断更新超平面以获 0至y/2之间选取，B*可在y/2至y间选取。强信 得更多潜在有效的分类信息，该方法能够将训练 息区的信息有较大可能在迭代融合划分过程中成 集始终固定在一个较小的规模，加速了SVM的 为支持向量，弱信息区的数据则对分类影响较 训练过程。 小，对强信息粒区域采用划分方式提取分类信 2.1初始粒划分 息，对弱信息区采用融合方式减少冗余信息。其 给定原始数据集D={X,y=(,y),(22,…, 中，超平面最大间隔y为 (x,)h,y.∈1，-1，x∈R,DFSVM首先通过聚类算 2 (4) 法将数据集中的正类与负类样本分别划分为k个 7=IWI 粒，通过初始粒划分方式得到新的信息粒集： 针对每个划分好的信息粒，选择中心点：作 D={(G1,G,…,G)n(Gi,G2,…,G)月 为代表点计算该粒到超平面之间的距离，公式如下： 式中：G表示通过划分得到的信息粒。SVM通过 w.o+b 2k(,4)+b 核函数K(x,y)=(x)py)将数据映射到N维核空 D- (5) W 间，将数据集经过初次划分在N维空间形成的粒 称为超粒，第i个超粒的中心：和半径y:为 动态划分过程通过衡量粒与超平面之间距离 (xp) 来选取候选粒进行深度划分。但由于不同粒的大 4 (Xp:xa) (1) 小、粒内部数据分布等差异，密度较大的粒中信 Yi= max (x)-min (x,) 息分布集中、重叠度大，含有更多潜在成为支持 向量的信息；密度较小的粒中信息分布稀疏，包 2Ve-246px)+x}= (2) 含的支持向量信息少。因此，对超平面附近密度 VK(xL,x1)-2K(x,xm)+K(Xm,xm) 较大的信息粒优先选择在当前迭代过程中划分， 式中：(x)和p(xm)代表核空间上下边界，超粒半 密度相对较小的信息粒可能成为后续划分过程中 径通过其平均值衡量，样本(x,)到任意超粒G 的候选粒。为了衡量每个粒的差异程度，给出粒 中心山：的距离可表示为 密度的定义： dis((x,),)= A (6) Yi VK)-2K(1,Xm)+K(X:xm) K)-2)+ >K(xp:xa) S 式中：n为第i个粒中的样本数；为第i个粒的 p=1=] 半径。 通过初始粒划分将原始数据集划分为G、 图2表示DFSVM动态粒划过程，其中G, G2、…G个粒，提取每个粒中的代表信息以训练 G2被选为当前最优分类信息粒，G被划分为 获得初始分类超平面。 Gan、Gn,G2被划分为Gai、Gn。同时将G4 2.2动态划分融合方法 和G5融合为Gmˉ，Ga和G5+融合为Gm 通过初始粒划过程获得超平面y=Wr·(x)+ 2.3 DFSVM算法 b,在SVM模型分类过程中，对分类起关键作用 DFSVM模型的数据处理过程分为两个阶段： 的样本信息主要分布在最大间隔内部以及间隔线 1)对原始数据进行初始粒划分，然后通过式(1) 附近，该区域的样本在模型训练过程中会被多次 计算得到每个粒的粒心，将所有粒心作为训练集 遍历，而位于超平面相对较远的样本无需过多的 训练得到初始分类超平面；2)利用动态划分融合 遍历即可将其分类正确。因此，基于以上条件将 的思想，对信息粒不断迭代处理以获得最优分类 样本划分为强信息区与弱信息区。给出两个参数 超平面。首先通过式(4)与参数B、B划分强信 B和B,其中B>B。当样本与超平面之间的距 息区与弱信息区，利用式（⑤）、(6)计算这两个区域 离满足D≤y/2+B时，样本点对分类超平面具有 内每个粒与超平面的距离和自身的粒密度，挑选 重要影响，划分为强信息区。同理，样本与超平 强信息区距超平面较近且粒密度大的粒在当前迭

VM 采取动态迭代划分的方式，对超平面附近可 能成为支持向量的信息粒深度划分，同时融合距 离超平面较远的冗余信息，不断更新超平面以获 得更多潜在有效的分类信息，该方法能够将训练 集始终固定在一个较小的规模，加速了 SVM 的 训练过程。 2.1 初始粒划分 D = {X, y} ={(x1, y1) (x2, y2), ··· , (xe , ye)} ye ∈{1,−1} xe ∈R l k 给定原始数据集 ， ， ， ，DFSVM 首先通过聚类算 法将数据集中的正类与负类样本分别划分为 个 粒，通过初始粒划分方式得到新的信息粒集： D ′ = {(G + 1 ,G + 2 ,··· ,G + k )∩(G − 1 ,G − 2 ,··· ,G − k )} Gk K(x, y) = φ(x)φ(y) N N i ui γi 式中： 表示通过划分得到的信息粒。SVM 通过 核函数 将数据映射到 维核空 间，将数据集经过初次划分在 维空间形成的粒 称为超粒，第 个超粒的中心 和半径 为 µi = ∑ni p=1 φ ( xp ) ni = 1 ni vut∑ni p=1 n ′ ∑i q=1 K ( xp, xq ) (1) γi = max(xl)−min(xs) 2 = 1 2 √ φ(xl) 2 −2φ(xl)φ(xm)+φ(xm) 2 = √ K(xl , xl) −2K(xl , xm)+K(xm, xm) (2) φ(xl) φ(xm) φ(xs) Gi µi 式中： 和 代表核空间上下边界，超粒半 径通过其平均值衡量，样本 到任意超粒 中心 的距离可表示为 dis(φ(xs), µi) = vut K(xs , xs)− 2 ni ∑ni j=1 K ( xs , xp ) + 1 ni 2 ∑ni p=1 n ′ ∑i q=1 K ( xp, xq ) (3) G1 G2 ···Gk 通过初始粒划分将原始数据集划分为 、 、 个粒，提取每个粒中的代表信息以训练 获得初始分类超平面。 2.2 动态划分融合方法 y WT ·φ(x) b β + β − β +>β − D ′ ⩽ γ/2+β − 通过初始粒划过程获得超平面 = + ，在 SVM 模型分类过程中，对分类起关键作用 的样本信息主要分布在最大间隔内部以及间隔线 附近，该区域的样本在模型训练过程中会被多次 遍历，而位于超平面相对较远的样本无需过多的 遍历即可将其分类正确。因此，基于以上条件将 样本划分为强信息区与弱信息区。给出两个参数 和 ，其中 。当样本与超平面之间的距 离满足 时，样本点对分类超平面具有 重要影响，划分为强信息区。同理，样本与超平 D ′ ⩾ γ/2+β + β − 0 γ/2 β + γ/2 γ γ 面之间的距离 时，认为样本点对分类 超平面影响较小，划分为弱信息区。其中 可在 至 之间选取， 可在 至 间选取。强信 息区的信息有较大可能在迭代融合划分过程中成 为支持向量，弱信息区的数据则对分类影响较 小，对强信息粒区域采用划分方式提取分类信 息，对弱信息区采用融合方式减少冗余信息。其 中，超平面最大间隔 为 γ = 2 ||W|| (4) 针对每个划分好的信息粒，选择中心点 µi 作 为代表点计算该粒到超平面之间的距离，公式如下： D ′ = WT ·φ+b ||W|| = n∑′ i=1 αiyik (xi , µi)+b vt  n∑′ i=1 αiyixi   2 (5) 动态划分过程通过衡量粒与超平面之间距离 来选取候选粒进行深度划分。但由于不同粒的大 小、粒内部数据分布等差异，密度较大的粒中信 息分布集中、重叠度大，含有更多潜在成为支持 向量的信息；密度较小的粒中信息分布稀疏，包 含的支持向量信息少。因此，对超平面附近密度 较大的信息粒优先选择在当前迭代过程中划分， 密度相对较小的信息粒可能成为后续划分过程中 的候选粒。为了衡量每个粒的差异程度，给出粒 密度的定义： ρi = ni γi = ni √ K(xl , xl) −2K(xl , xm) +K(xm, xm) (6) ni i γi 式中： 为第 个粒中的样本数； 为第 i 个粒的 半径。 G1 + G2 − G1 + Gd1 + Gd2 + G2 − Gd1 − Gd2 − G4 − G5 − Gm − G4 + G5 + Gm + 图 2 表示 DFSVM 动态粒划过程，其中 、 被选为当前最优分类信息粒， 被划分为 、 ， 被划分为 、 。同时将 和 融合为 ， 和 融合为 2.3 DFSVM 算法 β + β − DFSVM 模型的数据处理过程分为两个阶段： 1) 对原始数据进行初始粒划分，然后通过式 (1) 计算得到每个粒的粒心，将所有粒心作为训练集 训练得到初始分类超平面；2) 利用动态划分融合 的思想，对信息粒不断迭代处理以获得最优分类 超平面。首先通过式 (4) 与参数 、 划分强信 息区与弱信息区，利用式 (5)、(6) 计算这两个区域 内每个粒与超平面的距离和自身的粒密度，挑选 强信息区距超平面较近且粒密度大的粒在当前迭 第 6 期 赵帅群，等：采用划分融合双向控制的粒度支持向量机 ·1245·

·1246· 智能系统学报 第14卷 代过程进行划分，挑选弱信息区距超平面较远且 5)将更新后的信息粒代替原信息加人到训练 粒密度小的粒在当前迭代过程进行融合，用划分 集并更新分类超平面，同时记录模型测试结果； 后的超粒代替原始超粒。在该方式下，数据规模 6)重复4)6)，直到满足停止条件： 能够保持在较低水平，SVM的学习效率也得到有 )记录模型结果集，算法结束。 效的提升。 传统SVM模型训练的时间复杂度和空间复 杂度分别为o(m)和o(m2),其中n为数据的规模。 SVM在模型训练过程中，需要存储和计算大规模 的核矩阵，随着数据规模的增长，效率会大大降 G 低。DFSVM算法采用动态划分融合双向控制的 方式对数据集进行迭代划分，始终将训练集维持 G 在较小的规模，提高了模型的学习效率。尽管 DFSVM在划分过程中会多次训练超平面，但训 练总耗时仍然较少，并进一步改进了CGSVM静 态单层划分对重要信息提取不足的缺点，针对于 强信息粒进行信息提取，同时融合冗余的弱信息 粒，降低训练规模的同时提升CGSVM的训练精 度。DFSVM模型在保证较高分类精度的条件 下，有效地提升了模型的学习效率。 图2动态划分融合过程 3实验和分析 Fig.2 Dynamic division and fusion process 本文提出的DFSVM针对传统SVM无法高 3.1实验数据集 效的处理大规模数据以及CGSVM静态划分的不 本文实验在多个UCI数据集和标准数据集上 进行实验，见表1，SVM选用高斯核函数，在多种 足进行了改进，探讨的目标是DFSVM是否能够 在保证精度损失较少的情况下有效提升SVM的 参数下进行实验。实验在一台CPU为2.50GHz, 学习效率。本文在不同的参数下做了大量实验， 内存8GB计算机上运行，实验平台为Matlab2016a。 基本算法描述如下： 表1实验数据集 Table 1 Experimental data sets 算法采用划分融合双向控制的粒度支持向 数据集样本总数训练集测试集特征维度数据比例 量机 输入原始数据集D,初始粒化参数k,动态 banana 8726 69821744 2 1:1 粒化参数m,迭代粒化参数d,停止条件t(预先设 thyroid 3220 2576 644 5 1:1 定的模型迭代次数)： image 9900 7920 1980 e 1:l 输出划分融合过程得到的模型测试结果集。 german 3000 2400 600 20 1:1 1)用聚类算法将数据集D中每一类划分为 diabetis 5360 4288 1072 8 1:1 k个粒G1,G2,…,Gk; spambase 3200 2560 640 57 :1 2)将划分后的每个粒中心加入到训练集中训 splice 15270 122163054 60 11 练得到初始分类超平面'； kdd-1999 1000008000020000 41 l:l 3)通过式(4)和式(6)计算强信息区的信息粒 与超平面的距离D,以及粒密度P,挑选当前需要 3.2动态粒划分结果分析 划分的d个信息粒，并将这些信息粒分别深度划 本文提出的采用划分融合双向控制的粒度支 分为m个子粒； 持向量机模型，在粒划分过程中逐步提取潜在的 4)通过式(4)和式(6)计算弱信息区信息粒、 支持向量信息，通过信息融合清除掉过多的冗余信 超平面的距离D,与粒密度P,挑选出当前需要融 息，提升SVM的学习效率。本小节实验验证DFSVM 合的d×m个弱信息粒； 粒划分融合过程中对SVM泛化能力的影响

代过程进行划分，挑选弱信息区距超平面较远且 粒密度小的粒在当前迭代过程进行融合，用划分 后的超粒代替原始超粒。在该方式下，数据规模 能够保持在较低水平，SVM 的学习效率也得到有 效的提升。 G− 4 G− 1 G− 2 G− 5 G− 3 G+ 3 G+ 4 G+ 2 G+ 1 G+ 5 G− m G− 1 G− d1 G− d2 G− 3 G+ 3 G+ m G+ 2 G+ d1 G+ d2 图 2 动态划分融合过程 Fig. 2 Dynamic division and fusion process 本文提出的 DFSVM 针对传统 SVM 无法高 效的处理大规模数据以及 CGSVM 静态划分的不 足进行了改进，探讨的目标是 DFSVM 是否能够 在保证精度损失较少的情况下有效提升 SVM 的 学习效率。本文在不同的参数下做了大量实验， 基本算法描述如下： 算法 采用划分融合双向控制的粒度支持向 量机 D k m d t 输入 原始数据集 ，初始粒化参数 ，动态 粒化参数 ，迭代粒化参数 ，停止条件 (预先设 定的模型迭代次数)； 输出 划分融合过程得到的模型测试结果集。 D k G1,G2,··· ,Gk 1) 用聚类算法将数据集 中每一类划分为 个粒 ； f ′ 2) 将划分后的每个粒中心加入到训练集中训 练得到初始分类超平面 ； Di ρi d m 3) 通过式 (4) 和式 (6) 计算强信息区的信息粒 与超平面的距离 以及粒密度 ，挑选当前需要 划分的 个信息粒，并将这些信息粒分别深度划 分为 个子粒； Di ρi d ×m 4) 通过式 (4) 和式 (6) 计算弱信息区信息粒、 超平面的距离 与粒密度 ，挑选出当前需要融 合的 个弱信息粒； 5) 将更新后的信息粒代替原信息加入到训练 集并更新分类超平面，同时记录模型测试结果； 6) 重复 4)~6)，直到满足停止条件 t ； 7) 记录模型结果集，算法结束。 o(n 3 ) o(n 2 ) n 传统 SVM 模型训练的时间复杂度和空间复 杂度分别为 和 ，其中 为数据的规模。 SVM 在模型训练过程中，需要存储和计算大规模 的核矩阵，随着数据规模的增长，效率会大大降 低。DFSVM 算法采用动态划分融合双向控制的 方式对数据集进行迭代划分，始终将训练集维持 在较小的规模，提高了模型的学习效率。尽管 DFSVM 在划分过程中会多次训练超平面，但训 练总耗时仍然较少，并进一步改进了 CGSVM 静 态单层划分对重要信息提取不足的缺点，针对于 强信息粒进行信息提取，同时融合冗余的弱信息 粒，降低训练规模的同时提升 CGSVM 的训练精 度。DFSVM 模型在保证较高分类精度的条件 下，有效地提升了模型的学习效率。 3 实验和分析 3.1 实验数据集 本文实验在多个 UCI 数据集和标准数据集上 进行实验，见表 1，SVM 选用高斯核函数，在多种 参数下进行实验。实验在一台 CPU 为 2.50 GHz， 内存 8 GB 计算机上运行，实验平台为 Matlab2016a。 表 1 实验数据集 Table 1 Experimental data sets 数据集 样本总数 训练集 测试集 特征维度 数据比例 banana 8 726 6 982 1 744 2 1:1 thyroid 3 220 2 576 644 5 1:1 image 9 900 7 920 1 980 18 1:1 german 3 000 2 400 600 20 1:1 diabetis 5 360 4 288 1 072 8 1:1 spambase 3 200 2 560 640 57 1:1 splice 15 270 12 216 3 054 60 1:1 kdd-1999 100 000 80 000 20 000 41 1:1 3.2 动态粒划分结果分析 本文提出的采用划分融合双向控制的粒度支 持向量机模型，在粒划分过程中逐步提取潜在的 支持向量信息，通过信息融合清除掉过多的冗余信 息，提升 SVM 的学习效率。本小节实验验证 DFSVM 粒划分融合过程中对 SVM 泛化能力的影响。 ·1246· 智 能 系 统 学 报 第 14 卷

第6期 赵帅群，等：采用划分融合双向控制的粒度支持向量机 ·1247· 由于初始参数k决定了动态划分融合阶段的 合过程中，SVM的分类准确率逐步提高，但不同 数据规模，k值过小会导致学习性能的下降，过大 数据集的变化情况也存在差异。 会增加时间消耗，因此对于不同数据集需要选择 实验结果表明本文提出的方法能够充分提取 合适的参数值，在3.4.3节中有相关参数讨论。为 数据集中的关键信息，有效地提升了模型的学习 了尽可能观测粒划过程中预测准确率的变化，本 效率。在有限次的数据处理过程中，数据分布增 节实验设定迭代粒划参数d=1,动态粒化参数m=2, 强了对SVM的适应性，但随着划分次数增加，数 既每次将一个强信息粒划分为2个子粒，同时将 据分布的改变可能导致SVM过拟合化，降低模 远端的两个弱信息粒进行融合，图中初始结果即 型性能，如spambase数据显示出迭代次数大于 为CGSVM结果，SVM惩罚因子c=1,高斯核参 20时，准确率有明显下降趋势。实验表明采用划 数g=1kK为特征数). 分融合双向控制的粒度划分方法在一定程度上具 从图3中可以看出，在对数据集迭代划分融 有普适性。 89.4 84 89.2 89.0 88.6 81 88.4 88. 0 8 20 40 0 20 40 60 粒划分次数 粒划分次数 (a)banana(=100) (b)diabetis (=250) 83 93.5 93.0 92.5 81 久rnT0 92.0 91.5 19 91.0 73 90.5 20 0 0 20 40 60 畅 粒划分次数 粒划分次数 (c)german (=200) (d)image (k=250) 75.0 93.6 74.5 93.4 74.0 93.2 73.5 93.0 73.0 92.8 72.5 92.6 72.0 92.4 2 71.5 10 20 30 40 92.2 10 20 30 40 粒划分次数 粒划分次数 (e)spambase (=200) (f)splice (=500)

k k d = 1 m = 2 c = 1 g = 1 k ′ k ′ 由于初始参数 决定了动态划分融合阶段的 数据规模， 值过小会导致学习性能的下降，过大 会增加时间消耗，因此对于不同数据集需要选择 合适的参数值，在 3.4.3 节中有相关参数讨论。为 了尽可能观测粒划过程中预测准确率的变化，本 节实验设定迭代粒划参数 ，动态粒化参数 ， 既每次将一个强信息粒划分为 2 个子粒，同时将 远端的两个弱信息粒进行融合，图中初始结果即 为 CGSVM 结果，SVM 惩罚因子 ，高斯核参 数 / ( 为特征数)。 从图 3 中可以看出，在对数据集迭代划分融 合过程中，SVM 的分类准确率逐步提高，但不同 数据集的变化情况也存在差异。 实验结果表明本文提出的方法能够充分提取 数据集中的关键信息，有效地提升了模型的学习 效率。在有限次的数据处理过程中，数据分布增 强了对 SVM 的适应性，但随着划分次数增加，数 据分布的改变可能导致 SVM 过拟合化，降低模 型性能，如 spambase 数据显示出迭代次数大于 20 时，准确率有明显下降趋势。实验表明采用划 分融合双向控制的粒度划分方法在一定程度上具 有普适性。 89.4 89.2 89.0 88.8 准确率/% 粒划分次数 88.6 88.4 88.2 0 20 40 60 (a) banana (k=100) 84 83 82 81 准确率/% 粒划分次数 80 0 20 40 60 (b) diabetis (k=250) 83 80 79 82 81 准确率/% 粒划分次数 73 0 20 40 60 (c) german (k=200) 93.5 93.0 92.5 92.0 91.5 91.0 准确率/% 粒划分次数 90.5 0 20 40 80 60 (d) image (k=250) 75.0 74.5 74.0 73.5 73.0 72.5 72.0 准确率/% 粒划分次数 71.5 0 20 10 30 40 (e) spambase (k=200) 93.6 93.4 93.2 93.0 92.8 92.6 92.4 准确率/% 粒划分次数 92.2 0 10 20 30 40 (f) splice (k=500) 第 6 期 赵帅群，等：采用划分融合双向控制的粒度支持向量机 ·1247·