第14卷第6期 智能系统学报 Vol.14 No.6 2019年11月 CAAI Transactions on Intelligent Systems Nov.2019 D0:10.11992/tis.201904048 网络出版地址：http:/kns.cnki.net/kcms/detail/23.1538.TP.20190904.1734.002.html 基于模糊核聚类粒化的粒度支持向量机 黄华娟，韦修喜，周永权2 (1.广西民族大学信息科学与工程学院，广西南宁530006,2.广西民族大学广西高校复杂系统与智能计算重 点实验室，广西南宁530006) 摘要：针对传统的粒度支持向量机(granular support vector machine,GSVM)将训练样本在原空间粒化后再映射 到核空间，导致数据与原空间的分布不一致，从而降低GSVM的泛化能力的问题，本文提出了一种基于模糊核 聚类粒化的粒度支持向量机学习算法(fuzzy kemel cluster granular support vector machine,FKC-GSVM)。FKC-GS- VM通过利用模糊核聚类直接在核空间对数据进行粒的划分和支持向量粒的选取，在相同的核空间中进行支 持向量粒的GSVM训练。在UCI数据集和NDC大数据上的实验表明：与其他几个算法相比，FKC-GSVM在更 短的时间内获得了精度更高的解。 关键词：模糊核聚类：粒化：支持向量机：粒度支持向量机：原空间：核空间：支持向量：聚类 中图分类号：TP18文献标志码：A文章编号：1673-4785(2019)06-1271-07 中文引用格式：黄华娟，韦修喜，周永权.基于模糊核聚类粒化的粒度支持向量机J小.智能系统学报，2019,14(6)： 1271-1277. 英文引用格式：HUANG Huajuan,.WEI Xiuxi,.ZHOU Yongquan..Granular support vector machine based on fuz四y kernel cluster- ing granulation[J].CAAI transactions on intelligent systems,2019,14(6):1271-1277. Granular support vector machine based on fuzzy kernel clustering granulation HUANG Huajuan',WEI Xiuxi',ZHOU Yongquan'2 (1.College of Information Science and Engineering,Guangxi University for Nationalities,Nanning 530006,China;2.Guangxi High- er School Key Laboratory of Complex Systems and Intelligent Computing,Guangxi University for Nationalities,Nanning 530006, China) Abstract:For the traditional granular support vector machine(GSVM),the training samples are granulated in the origin- al space and then mapped to the kernel space.However,this method will lead to the inconsistent distribution of the data between the original space and the kernel space,thereby reducing the generalization of GSVM.To solve this problem,a granular support vector machine based on fuzzy kernel cluster is proposed.Here,the training data are directly granu- lated,and support vector particles are selected in kernel space.The support vector particles are then trained in the same kernel space by the GSVM.Finally,experiments on UCI data sets and NDC big data sets show that FKC-GSVM achieves more accurate solutions in a shorter time than other algorithms. Keywords:fuzzy kernel cluster;granulation;support vector machine;granular support vector machine;original space; kernel space;support vector,clustering 收稿日期：2019-04-18.网络出版日期：2019-09-05. 支持向量机(support vector machine,SVM) 基金项目：国家自然科学基金资助项目(61662005)：广西自然 科学基金项目(2018JA170121):广西高校中青年教 自1995年由Vapnik提出以来就受到理论研究和 师科研基础能力提升项目(2019KY0195). 通信作者：韦修喜.E-mail:weixiuxi(@163.com. 工程应用2方面的重视，是机器学习的一个研究
DOI: 10.11992/tis.201904048 网络出版地址: http://kns.cnki.net/kcms/detail/23.1538.TP.20190904.1734.002.html 基于模糊核聚类粒化的粒度支持向量机 黄华娟1 ，韦修喜1 ，周永权1,2 （1. 广西民族大学 信息科学与工程学院，广西 南宁 530006; 2. 广西民族大学 广西高校复杂系统与智能计算重 点实验室，广西 南宁 530006） 摘 要：针对传统的粒度支持向量机 (granular support vector machine, GSVM) 将训练样本在原空间粒化后再映射 到核空间，导致数据与原空间的分布不一致，从而降低 GSVM 的泛化能力的问题，本文提出了一种基于模糊核 聚类粒化的粒度支持向量机学习算法 (fuzzy kernel cluster granular support vector machine, FKC-GSVM)。FKC-GSVM 通过利用模糊核聚类直接在核空间对数据进行粒的划分和支持向量粒的选取，在相同的核空间中进行支 持向量粒的 GSVM 训练。在 UCI 数据集和 NDC 大数据上的实验表明：与其他几个算法相比，FKC-GSVM 在更 短的时间内获得了精度更高的解。 关键词：模糊核聚类；粒化；支持向量机；粒度支持向量机；原空间；核空间；支持向量；聚类 中图分类号：TP18 文献标志码：A 文章编号：1673−4785(2019)06−1271−07 中文引用格式：黄华娟, 韦修喜, 周永权. 基于模糊核聚类粒化的粒度支持向量机 [J]. 智能系统学报, 2019, 14(6): 1271–1277. 英文引用格式：HUANG Huajuan, WEI Xiuxi, ZHOU Yongquan. Granular support vector machine based on fuzzy kernel clustering granulation[J]. CAAI transactions on intelligent systems, 2019, 14(6): 1271–1277. Granular support vector machine based on fuzzy kernel clustering granulation HUANG Huajuan1 ，WEI Xiuxi1 ，ZHOU Yongquan1,2 (1. College of Information Science and Engineering, Guangxi University for Nationalities, Nanning 530006, China; 2. Guangxi Higher School Key Laboratory of Complex Systems and Intelligent Computing, Guangxi University for Nationalities, Nanning 530006, China) Abstract: For the traditional granular support vector machine (GSVM), the training samples are granulated in the original space and then mapped to the kernel space. However, this method will lead to the inconsistent distribution of the data between the original space and the kernel space, thereby reducing the generalization of GSVM. To solve this problem, a granular support vector machine based on fuzzy kernel cluster is proposed. Here, the training data are directly granulated, and support vector particles are selected in kernel space. The support vector particles are then trained in the same kernel space by the GSVM. Finally, experiments on UCI data sets and NDC big data sets show that FKC-GSVM achieves more accurate solutions in a shorter time than other algorithms. Keywords: fuzzy kernel cluster; granulation; support vector machine; granular support vector machine; original space; kernel space; support vector; clustering 支持向量机 (support vector machine, SVM) 自 1995 年由 Vapnik 提出以来就受到理论研究和 工程应用 2 方面的重视，是机器学习的一个研究 收稿日期：2019−04−18. 网络出版日期：2019−09−05. 基金项目：国家自然科学基金资助项目 (61662005)；广西自然 科学基金项目 (2018JJA170121)；广西高校中青年教 师科研基础能力提升项目 (2019KY0195). 通信作者：韦修喜. E-mail：weixiuxi@163.com. 第 14 卷第 6 期 智 能 系 统 学 报 Vol.14 No.6 2019 年 11 月 CAAI Transactions on Intelligent Systems Nov. 2019
·1272· 智能系统学报 第14卷 方向和热点，已经成功应用到很多领域中。 X={X,Y),i=1,2,…,0 SVM的基本算法是一个含有不等式约束条件的 其中： 二次规划(quadratic programming problem,QPP)问 l,+1 Xl+h+…++ 题，然而，如果直接求解QPP问题，当数据集较大 x1,+2 X1+h4+++2 …,X= 时，算法的效率将会下降，所需内存量也会增大。 Xh+l 因此，如何克服SVM在处理大规模数据集时的 X,+h++-+4 则在GSVM中，最优化问题变为： 效率低下问题，一直是学者们研究的热点。 1 为了更好地解决大规模样本的分类问题，基 min.b亏w2 (1) 于粒度计算理论911和统计学习理论的思想， S.t. Y(w:X)+b)≥1，j=1,2,…,l Tang等于2004年首次提出粒度支持向量机(gran- 将上述问题根据最优化理论转化为其对偶问题： ular support vector machine,.GSVM)这个术语。GS max W(a)=max- VM的总体思想是在原始空间将数据集进行划 ∑∑auYY/Xx)+∑a 人 分，得到数据粒。然后提取出有用的数据粒，并 对其进行SVM训练a。与传统支持向量机相 S.t. ∑a=0. 0≤a≤C 比，GSVM学习机制具有以下优点：针对大样本 解得最优解a=[aa2'…a,计算最优权值向 数据，通过数据粒化和对有用粒子（支持向量粒） 的提取，别除了无用冗余的样本，减少了样本数 量w=ayx,和最优偏置公=y-乃4xX. 人 量，提高了训练效率。然而，Tang只是给出了 i∈{lg>0。因此得到最优分类超平面(w)+b=0, GSVM学习模型的一些设想，没有给出具体的学 而最优分类函数为： 习算法。2009年，张鑫]在Tang提出的GS- f(x)=sgn((wX)+b]= VM思想的基础上，构建了一个粒度支持向量机 的模型，并对其学习机制进行了探讨。此后，许 gm∑yX,X》+b,reR (3) 多学者对支持向量机和粒度计算相结合的具体模 当数据集是线性不可分时，GSVM不是在原 型进行了研究，比如模糊支持向量机)、粗糙集 始空间构造最优分类面，而是映射到高维特征空 支持向量机、决策树支持向量机和商空间支 间，然后再进行构造，具体为： 持向量机等。但这些模型的共同点都是在原 将X从R:变换到Φ： 始空间直接划分数据集，然后再映射到高维空间 X一(X)=[(X)中2(X)…Φ(X 进行SVM学习。然而，这种做法很有可能丢失 以特征向量(X)代替输入向量X,则可以得 了大量包含有用信息的数据粒，其学习算法的性 到最优分类函数为： 能会受到影响。为此，本文采用模糊核聚类的方 f(X)=sgn(wD(X)+b)= 法将样本直接在核空间进行粒的划分和提取，然 sgn∑ayX)o)+b) (4) 后在相同的核空间进行GSVM训练，这样保证了 =1 数据分布的一致性，提高了算法的泛化能力。最 利用核函数来求解向量的内积，则最优分类 后，在标准UCI数据集和NDC大数据上的实验结 函数变为： 果表明，本文算法是可行的且效果更好。 f(X)=sgn(w(X)+b)= (5) 1粒度支持向量机 sg(∑axkK,+b 张鑫1在Tang提出的GSVM思想的基础 其中，k(X,)为粒度核函数。当a>0,根据以上 上，构建了一个粒度支持向量机的模型。 分析，可知X:是支持向量。显然地，式(5)的形式 设给定数据集为X={x,),i=1,2,…,n,n 和SVM的最优分类函数很一致，确保了最优解 为样本的个数；y为：所属类的标签。采用粒度 的唯一性。 划分的方法（聚类、粗糙集、关联规则等）划分X, 2基于模糊核聚类粒化的粒度支持 若数据集有1个类，则将X分成1个粒，表示为： 向量机 (X1,Y),(X2,Y2,…,(X,Y),…,(X,Y) 若每个粒包含1：个点，Y表示第i个粒的类 2.1问题的提出 别，则有： 在研究中发现，只有支持向量才对SVM的训
方向和热点，已经成功应用到很多领域中[ 1 - 3 ]。 SVM 的基本算法是一个含有不等式约束条件的 二次规划 (quadratic programming problem, QPP) 问 题，然而，如果直接求解 QPP 问题，当数据集较大 时，算法的效率将会下降，所需内存量也会增大[4-8]。 因此，如何克服 SVM 在处理大规模数据集时的 效率低下问题，一直是学者们研究的热点。 为了更好地解决大规模样本的分类问题，基 于粒度计算理论[ 9 - 1 0 ] 和统计学习理论的思想， Tang 等于 2004 年首次提出粒度支持向量机 (granular support vector machine, GSVM) 这个术语。GSVM 的总体思想是在原始空间将数据集进行划 分，得到数据粒。然后提取出有用的数据粒，并 对其进行 SVM 训练 [11-12]。与传统支持向量机相 比，GSVM 学习机制具有以下优点：针对大样本 数据，通过数据粒化和对有用粒子 (支持向量粒) 的提取，剔除了无用冗余的样本，减少了样本数 量，提高了训练效率。然而，Tang 只是给出了 GSVM 学习模型的一些设想，没有给出具体的学 习算法。2009 年，张鑫[ 1 3 ] 在 Tang 提出的 GSVM 思想的基础上，构建了一个粒度支持向量机 的模型，并对其学习机制进行了探讨。此后，许 多学者对支持向量机和粒度计算相结合的具体模 型进行了研究，比如模糊支持向量机[13] 、粗糙集 支持向量机[14] 、决策树支持向量机[15]和商空间支 持向量机[16] 等。但这些模型的共同点都是在原 始空间直接划分数据集，然后再映射到高维空间 进行 SVM 学习。然而，这种做法很有可能丢失 了大量包含有用信息的数据粒，其学习算法的性 能会受到影响。为此，本文采用模糊核聚类的方 法将样本直接在核空间进行粒的划分和提取，然 后在相同的核空间进行 GSVM 训练，这样保证了 数据分布的一致性，提高了算法的泛化能力。最 后，在标准 UCI 数据集和 NDC大数据上的实验结 果表明，本文算法是可行的且效果更好。 1 粒度支持向量机 张鑫[17] 在 Tang 提出的 GSVM 思想的基础 上，构建了一个粒度支持向量机的模型。 X = {(xi , yi),i = 1,2,··· ,n} n yi xi X l X l 设给定数据集为 ， 为样本的个数； 为 所属类的标签。采用粒度 划分的方法 (聚类、粗糙集、关联规则等) 划分 ， 若数据集有 个类，则将 分成 个粒，表示为： (X1 ,Y1),(X2 ,Y2),··· ,(Xi ,Yi),··· ,(Xl ,Yl) li Yi 若每个粒包含 个点， 表示第 i 个粒的类 别，则有： X = {(Xi ,Yi),i = 1,2,··· ,l} 其中： X1 = x1 x2 . . . xl1 ,X2 = xl1+1 xl1+2 . . . xl1+l2 ,··· ,Xl = xl1+l2+···+ll−1+1 xl1+l2+···+ll−1+2 . . . xl1+l2+···+ll−1+ll 则在 GSVM 中，最优化问题变为： minw,b 1 2 w 2 s.t. Yj((w· Xj)+b) ⩾ 1, j = 1,2,··· ,l (1) 将上述问题根据最优化理论转化为其对偶问题： max a W(a) = max a − 1 2 ∑l i=1 ∑l j=1 aiajYiYj(XiXj)+ ∑l i=1 ai s.t. ∑l i=1 aiYi = 0, 0 ⩽ ai ⩽ C (2) a ∗ = [a1 ∗ a2 ∗ ··· al ∗ ] T w ∗ = ∑l j=1 aj ∗ yjXj b ∗ = yi − ∑l j=1 yja ∗ j (XjXi) i ∈ {i|a ∗ i > 0} (w ∗X)+b ∗ = 0 解得最优解 ，计算最优权值向 量 和最优偏置 ， 。因此得到最优分类超平面 ， 而最优分类函数为： f(x) =sgn{(w ∗X)+b ∗ } = sgn{( ∑l j=1 a ∗ j yj(XjXi))+b ∗ },X ∈ R n (3) 当数据集是线性不可分时，GSVM 不是在原 始空间构造最优分类面，而是映射到高维特征空 间，然后再进行构造，具体为： X R 将 从 n 变换到 Φ： X→− Φ(X) = [Φ1(X)Φ2(X) ··· Φl(X)]T 以特征向量 Φ(X) 代替输入向量 X ，则可以得 到最优分类函数为： f(X) =sgn(wΦ(X)+b) = sgn(∑l i=1 aiyiΦ(Xi)Φ(X)+b) (4) 利用核函数来求解向量的内积，则最优分类 函数变为： f(X) =sgn(wΦ(X)+b) = sgn(∑l i=1 aiyik(Xi ,X)+b) (5) k(Xi ,X) ai > 0 Xi 其中， 为粒度核函数。当 ，根据以上 分析，可知 是支持向量。显然地，式 (5) 的形式 和 SVM 的最优分类函数很一致，确保了最优解 的唯一性。 2 基于模糊核聚类粒化的粒度支持 向量机 2.1 问题的提出 在研究中发现，只有支持向量才对 SVM 的训 ·1272· 智 能 系 统 学 报 第 14 卷
第6期 黄华娟，等：基于模糊核聚类粒化的粒度支持向量机 ·1273· 练起积极作用，它们是非常重要的，对于SVM是 量粒，它们决定了分类超平面。并且从中可以看 不可或缺的，而其余的非支持向量对于分类超平 出，对于每一类，离类中心越远的点，就越有可能 面是不起作用的，甚至可能产生负面影响，比如 是支持向量粒。并且，从图1中还可以看出，落在 增加了核矩阵的容量，降低了SVM的效率。GS- 每一个环上的样本，它们离类中心的距离差不多 VM也存在同样的问题，只有支持向量粒才对 相等。离类中心越远的环就越有可能含有多的 GSVM的训练起决定性作用。可以通过理论证明 支持向量粒。基于这个思想，本文先把样本映射 来说明这个观点的正确性。 到核空间，按类标签的个数进行粗粒划分，确保 定理1粒度支持向量机的训练过程和训练 相同标签的样本都在同一个粗粒中。然后，对于 结果与非支持向量粒无关。 每一个粗粒，采用模糊聚类的方法进行粒化，具 证明定义I,w={ia>0)和1asv={a=0)分别 有相同隶属度的样本归为一个粒，进行细粒划 为支持向量粒和非支持向量粒对应样本序号的索 分。每一个细粒就对应图1中的一个环，从图中 引集，支持向量粒的个数记为！。引入只优化支 可以看出，离粗粒中心越远的环，越靠近分类超 持向量粒对应样本的问题 平面，其是支持向量粒的可能性越大。而离粗粒 中心越远的环，其隶属度越小。因此，给定一个 1 maxg(a)=max- ∑∑aa,Yxx)+a 阈值，当细粒的隶属度小于给定的阈值，就说明 2 (6) 其处于粗粒的边缘，是支持向量粒，进而提取出 S.t. ∑ay=0,0≤a<Ci=1.2…,rel 支持向量粒 i=t 要证明定理1，只需要证明式(2)和式(6)同 解。用反正法，假设式(6)存在一个最优解使 得g(a)>g(a)。由于a是式(2)的最优解，也即 是式(6)的可行解，同样，d也是式(2)的可行解。 由于a是式(2)的最优解，可得w(a)>w(a)。又 图1支持向量分布图 因为 Fig.1 The distribution of support vectors w(a)=max- dwA+2a= 2.3 模糊核聚类 模糊核聚类(fuzzy kernel cluster,FKC)的主要 1 ∑∑ddyy k(X.X)+∑a=ga max2 思想是先将数据集映射到高维空间，然后直接在高 人 维空间进行模糊聚类。而一般的聚类算法是直接 ∑∑ddyyA(X.X)+∑a= 在原始空间进行聚类划分。与其他的聚类算法相 w(a')=max-22 比，模糊核聚类引入了非线性映射，能够在更大程 度上提取到有用的特征，聚类的效果会更好。 1夕 max-2 aay,kX,x)+∑a=ga 设原空间样本集为X=(x1,,…,w),x∈R4 11 1 j=1,2,…,N。核非线性映射为0：x→0(x,在本 可得w(a')=g(a)>g(a)=w(a),即w(a')>w(a), 文中，采用Euclid距离作为距离测量方法，由此得 这与a是式(2)的最优解得出的w(a)>w(a')相 到模糊核C-均值聚类： 矛盾。定理1得证。注：a是r维向量，代入w的 J=(X,U,V)= 时候拓展为I维向量。 要想迅速地得到支持向量粒，节省粒化的时 ∑立-o 间，首先了解支持向量的特征，文献[13]对其特 征做了归纳总结。 (7) 1)现实中，支持向量一般都是稀疏地聚集在 2立0-2，+ 训练数据集的边缘。 2立g.M.2sc<N 2)根据第一个特征，则每个类中心附近的数 1=】 据不会是支持向量，即，离支持向量机超平面较 式中：C是事先确定的簇数；m∈(1，o)是模糊加权 近的数据比较可能是支持向量，这就为支持向量 指数，对聚类的模糊程度有重要的调节作用；”为 的选取提供了快速的获取方法。 第i类的类中心；()为该中心在相应核空间中 2.2问题分析 的像。 图1中，红色部分的数据是GSVM的支持向 按模糊C均值优化方法，隶属度设计为
练起积极作用，它们是非常重要的，对于 SVM 是 不可或缺的，而其余的非支持向量对于分类超平 面是不起作用的，甚至可能产生负面影响，比如 增加了核矩阵的容量，降低了 SVM 的效率。GSVM 也存在同样的问题，只有支持向量粒才对 GSVM 的训练起决定性作用。可以通过理论证明 来说明这个观点的正确性。 定理 1 粒度支持向量机的训练过程和训练 结果与非支持向量粒无关。 Isv = {i|al > 0} Insv = {i|al = 0} l ′ 证明 定义 和 分别 为支持向量粒和非支持向量粒对应样本序号的索 引集，支持向量粒的个数记为 。引入只优化支 持向量粒对应样本的问题 max a g(a) = max a − 1 2 l ∑′ i=1 l ∑′ j=1 aiajYiYj(XiXj)+ l ∑′ i=1 ai s.t. ∑l i=1 aiYi = 0, 0 ⩽ ai ⩽ C, i = 1,2,··· , l ′ ∈ Isv (6) a ′ g(a ′ ) > g(a ∗ ) a ∗ a ∗ a ′ a ∗ w(a ∗ ) > w(a ′ ) 要证明定理 1，只需要证明式 (2) 和式 (6) 同 解。用反正法，假设式 (6) 存在一个最优解 使 得 。由于 是式 (2) 的最优解，也即 是式 (6) 的可行解，同样， 也是式 (2) 的可行解。 由于 是式 (2) 的最优解，可得 。又 因为 w(a ′ ) = max− a 1 2 ∑l i=1 ∑l j=1 a ′ ia ′ j yiyjk(Xi ,Xj)+ ∑l i=1 a ′= max a − 1 2 l ∑′ i=1 l ∑′ j=1 a ′ ia ′ j yiyjk(Xi ,Xj)+ l ∑′ i=1 a ′ = g(a ′ ) w(a ∗ ) = max− a 1 2 ∑l i=1 ∑l j=1 a ∗ i a ∗ j yiyjk(Xi ,Xj)+ ∑l i=1 a ∗= max a − 1 2 l ∑′ i=1 l ∑′ j=1 a ∗ i a ∗ j yiyjk(Xi ,Xj)+ l ∑′ i=1 a ∗ = g(a ∗ ) w(a ′ ) = g(a ′ ) > g(a ∗ ) = w(a ∗ ) w(a ′ ) > w(a ∗ ) a ∗ w(a ∗ ) > w(a ′ ) a ′ l ′ w l 可 得 ， 即 ， 这与 是式 (2) 的最优解得出的 相 矛盾。定理 1 得证。注： 是 维向量，代入 的 时候拓展为 维向量。 要想迅速地得到支持向量粒，节省粒化的时 间，首先了解支持向量的特征，文献 [13] 对其特 征做了归纳总结。 1) 现实中，支持向量一般都是稀疏地聚集在 训练数据集的边缘。 2) 根据第一个特征，则每个类中心附近的数 据不会是支持向量，即，离支持向量机超平面较 近的数据比较可能是支持向量，这就为支持向量 的选取提供了快速的获取方法。 2.2 问题分析 图 1 中，红色部分的数据是 GSVM 的支持向 量粒，它们决定了分类超平面。并且从中可以看 出，对于每一类，离类中心越远的点，就越有可能 是支持向量粒。并且，从图 1 中还可以看出，落在 每一个环上的样本，它们离类中心的距离差不多 相等。 离类中心越远的环就越有可能含有多的 支持向量粒。基于这个思想，本文先把样本映射 到核空间，按类标签的个数进行粗粒划分，确保 相同标签的样本都在同一个粗粒中。 然后，对于 每一个粗粒，采用模糊聚类的方法进行粒化，具 有相同隶属度的样本归为一个粒，进行细粒划 分。 每一个细粒就对应图 1 中的一个环，从图中 可以看出，离粗粒中心越远的环，越靠近分类超 平面，其是支持向量粒的可能性越大。而离粗粒 中心越远的环，其隶属度越小。因此，给定一个 阈值，当细粒的隶属度小于给定的阈值，就说明 其处于粗粒的边缘，是支持向量粒，进而提取出 支持向量粒. 图 1 支持向量分布图 Fig. 1 The distribution of support vectors 2.3 模糊核聚类 模糊核聚类 (fuzzy kernel cluster, FKC) 的主要 思想是先将数据集映射到高维空间，然后直接在高 维空间进行模糊聚类。而一般的聚类算法是直接 在原始空间进行聚类划分。与其他的聚类算法相 比，模糊核聚类引入了非线性映射，能够在更大程 度上提取到有用的特征，聚类的效果会更好。 X = (x1, x2,··· , xN) xj ∈ R d j = 1,2,··· ,N Ø : x → Ø(x) C 设原空间样本集为 ， ， 。 核非线性映射为 ，在本 文中，采用 Euclid 距离作为距离测量方法，由此得 到模糊核 -均值聚类： Jm =(X,U,V) = ∑C i=1 ∑N j=1 u m i j Ø(xj)−Ø(vi) 2 = ∑C i=1 ∑N j=1 u m i j[k(xj , xj)−2k(xj , vi)+k(vi , vi)] = ∑C i=1 ∑N j=1 u m i jd 2 Ki j(xj , vi), 2 ⩽ C < N (7) C m ∈ (1,∞) vi i ϕ(vi) 式中： 是事先确定的簇数； 是模糊加权 指数，对聚类的模糊程度有重要的调节作用； 为 第 类的类中心； 为该中心在相应核空间中 的像。 按模糊 - C 均值优化方法，隶属度设计为 第 6 期 黄华娟，等：基于模糊核聚类粒化的粒度支持向量机 ·1273·
·1274· 智能系统学报 第14卷 [1/dx,- 支持向量粒；在核空间对支持向量粒进行SVM (8) 训练。具体的算法步骤如下： 之d成，wa- 1)粗粒划分：以类标签个数1为粒子个数，对 且有 训练样本进行粗粒的划分，得到1个粒子； 2)细粒划分：采用模糊核聚类分别对1个粒 Gom 子进行细粒划分，计算每个粒子的隶属度； 0）= 妇1 i=1,2,…,C (9) 3)支持向量粒的提取：给定一个阈值，当一 N 个粒子的隶属度小于给定的阈值，提取这个粒子 (支持向量粒)，提取出来的支持向量粒组成了一 为了最小化目标函数，需要计算k(x,)和 个新的训练集； k(,),由k(x,x)=<(x),(x)>可得： 4)支持向量集的训练：在新的训练样本集上 进行GSVM训练； ∑，x) 5)泛化能力的测试：利用测试集测试泛化 k(x,)=<0x,0A）>= (10) 能力。 2.5FKC-GSVM算法性能分析 下面，从2个方面对FKC-GSVM的算法性能 uuk(xgx,) 进行分析： k(,)=<0(,0)>= k=1s=1 (11) 1)FKC-GSVM的收敛性分析 与SVM相比，FKC-GSVM采用核空间代替 原始空间进行粒化，提取出支持向量粒后在相同 把式(9)(11)代入式(7)，可以求出模糊核C- 的核空间进行GSVM训练，其训练的核心思想依 均值聚类的目标函数值。 然是采用支持向量来构造分类超平面，这与标准 模糊核C-均值聚类的算法步骤如下： 支持向量机相同。既然标准支持向量机是收敛 1)初始化参数：s、m、T和C; 的，则FKC-GSVM也是收敛的。但是由于FKC- 2)对训练数据集进行预处理： GSVM别除了大量对训练不起积极作用的非支持 3)设置(i=1,2,…,C)的初始值； 向量，直接采用支持向量来训练，所以它的收敛 4)计算隶属度(i=1,2,…,C:j=1,2,…,N) 速度要快于标准支持向量机。 5)计算新的kx,)和kv,v,更新隶属度 2)FKC-GSVM的泛化能力分析 为； 评价一个学习器性能好坏的重要指标是其是 6)若max,-i<s或迭代次数等于预定送 否具有较强的泛化能力。众所周知，由于SVM 代次数T则算法停止，否则转到4)。 采用结构风险最小(SRM)归纳原则，因此，与其 2.4FKC-GSVM的算法步骤 他学习机器相比，SVM的泛化能力是很突出的。 目前，已有的粒度支持向量机算法模型大都 同样，FKC-GSVM也执行了SRM归纳原则，并且 是直接在原始空间对数据集进行粒化和提取，然 直接在核空间选取支持向量，确保了数据的一致 后映射到核空间进行SVM的训练。然而，不同 性，具有更好的泛化性能。 空间的转换，很有可能丢失了数据集的有用信 息，降低学习器的性能。为了避免因数据在不同 3实验结果及分析 空间分布不一致而导致泛化能力不高的问题，本 文采用模糊核聚类的方法直接在核空间对数据集 3.1UCI数据集上的实验 进行粒化、提取和SVM的训练。基于以上思想， 为了验证FKC-GSVM的学习性能，本文在 本文提出了基于模糊核聚类粒化的粒度支持向量 Matlab7.11的环境下对5个常用的UCI数据集进 (fuzzy kernel cluster granular support vector ma- 行实验，这5个数据集的描述如表1所示。在实验 chine,FKC-GSVM。FKC-GSVM算法包括3部 中，采用的核函数为高斯核函数，并且采用交叉验 分：采用模糊核聚类进行粒度的划分；设定阈值， 证方法选取惩罚参数C和核参数σ，聚类数c设为 当每个粒子的隶属度大于规定的阈值时，认为这 20。影响算法表现的主要因素是阈值k的设定，为 个粒子为非支持向量粒，丢弃，而剩余的粒子为 此，对不同的阈值对算法的影响进行了分析
ui j = [1/d 2 Ki j(xj , vi)]1/(m−1) ∑C j=1 [1/d 2 Ki j(xj , vi)]1/(m−1) (8) 且有 Ø(vi) = ∑N k=1 u m ikØ(xk) ∑N k=1 u m ik , i = 1,2,··· ,C (9) k(xj , vi) k(vi , vi) k(xi , xj) =< ϕ(xi), ϕ(xj) > 为了最小化目标函数，需要计算 和 ，由 可得： k(xj , vi) =< Ø(xj),Ø(vi) >= ∑N k=1 u m ikk(xk , xj) ∑N k=1 u m ik (10) k(vi , vi) =< Ø(vi),Ø(vi) >= ∑N k=1 ∑N s=1 u m iku m is k(xk , xs) ∑N k=1 u m ik 2 (11) 把式 (9)~(11) 代入式 (7)，可以求出模糊核 - C 均值聚类的目标函数值。 模糊核 - C 均值聚类的算法步骤如下： 1) 初始化参数： 、 、 ε m T 和 C ； 2) 对训练数据集进行预处理； 3) 设置 vi(i = 1,2,··· ,C) 的初始值； 4) 计算隶属度 ui j(i = 1,2,··· ,C; j = 1,2,··· ,N) ； k(xj , vi) k(vi , vi) ui j uˆi j 5) 计算新的 和 ，更新隶属度 为 ； max j,i ui j −uˆi j < ε T 6) 若 或迭代次数等于预定迭 代次数 则算法停止，否则转到 4)。 2.4 FKC-GSVM 的算法步骤 目前，已有的粒度支持向量机算法模型大都 是直接在原始空间对数据集进行粒化和提取，然 后映射到核空间进行 SVM 的训练。然而，不同 空间的转换，很有可能丢失了数据集的有用信 息，降低学习器的性能。为了避免因数据在不同 空间分布不一致而导致泛化能力不高的问题，本 文采用模糊核聚类的方法直接在核空间对数据集 进行粒化、提取和 SVM 的训练。基于以上思想， 本文提出了基于模糊核聚类粒化的粒度支持向量 机 (fuzzy kernel cluster granular support vector machine, FKC-GSVM)。FKC-GSVM 算法包括 3 部 分：采用模糊核聚类进行粒度的划分；设定阈值， 当每个粒子的隶属度大于规定的阈值时，认为这 个粒子为非支持向量粒，丢弃，而剩余的粒子为 支持向量粒；在核空间对支持向量粒进行 SVM 训练。具体的算法步骤如下： l l 1) 粗粒划分：以类标签个数 为粒子个数，对 训练样本进行粗粒的划分，得到 个粒子； 2) 细粒划分：采用模糊核聚类分别对 l 个粒 子进行细粒划分，计算每个粒子的隶属度； 3) 支持向量粒的提取：给定一个阈值，当一 个粒子的隶属度小于给定的阈值，提取这个粒子 (支持向量粒)，提取出来的支持向量粒组成了一 个新的训练集； 4) 支持向量集的训练：在新的训练样本集上 进行 GSVM 训练； 5) 泛化能力的测试：利用测试集测试泛化 能力。 2.5 FKC-GSVM 算法性能分析 下面，从 2 个方面对 FKC-GSVM 的算法性能 进行分析： 1) FKC-GSVM 的收敛性分析 与 SVM 相比，FKC-GSVM 采用核空间代替 原始空间进行粒化，提取出支持向量粒后在相同 的核空间进行 GSVM 训练，其训练的核心思想依 然是采用支持向量来构造分类超平面，这与标准 支持向量机相同。既然标准支持向量机是收敛 的，则 FKC-GSVM 也是收敛的。但是由于 FKCGSVM 剔除了大量对训练不起积极作用的非支持 向量，直接采用支持向量来训练，所以它的收敛 速度要快于标准支持向量机。 2) FKC-GSVM 的泛化能力分析 评价一个学习器性能好坏的重要指标是其是 否具有较强的泛化能力。众所周知，由于 SVM 采用结构风险最小 (SRM) 归纳原则，因此，与其 他学习机器相比，SVM 的泛化能力是很突出的。 同样，FKC-GSVM 也执行了 SRM 归纳原则，并且 直接在核空间选取支持向量，确保了数据的一致 性，具有更好的泛化性能。 3 实验结果及分析 3.1 UCI 数据集上的实验 C σ c k 为了验证 FKC-GSVM 的学习性能，本文在 Matlab7.11 的环境下对 5 个常用的 UCI 数据集进 行实验，这 5 个数据集的描述如表 1 所示。在实验 中，采用的核函数为高斯核函数，并且采用交叉验 证方法选取惩罚参数 和核参数 ，聚类数 设为 20。影响算法表现的主要因素是阈值 的设定，为 此，对不同的阈值对算法的影响进行了分析。 ·1274· 智 能 系 统 学 报 第 14 卷
第6期 黄华娟，等：基于模糊核聚类粒化的粒度支持向量机 ·1275· 表1实验采用的数据集 Table 1 Datasets used in experiments 数据集Abalone Contraceptive Method Choice Pen-Based Recognition of Hand-written Digits NDC-10k NDC-11 #训练集3177 1000 6280 10000 100000 #测试集 1000 473 3498 1000 10000 维度 8 9 6 32 32 为了比较数据集在原空间粒化和在核空间粒 测试，测试结果如表2所示。为了更直观地看出 化的不同效果，本文采用基于模糊聚类的粒度支 FKC-GSVM在不同阈值条件下的分类效果，给出 持向量机(FCM-GSVM)、基于模糊核聚类的粒度 了Contraceptive Method Choice数据集在不同阈值 支持向量机(FKC-GSVM)和粒度支持向量机(GS 条件下采用FKC-GSVM分类的效果图，如图2~ VM)等3种算法对5个典型的UCI数据集进行了 图5所示。 表2FCM-GSVM与FKC-GSVM测试结果比较 Table 2 Comparison of test results between FCM-GSVM and FKC-GSVM % 数据集 算法 阈值k 0.9 0.85 0.8 0.75 GSVM 80.1 75.6 76.7 65.6 Abalone FCM-GSVM 82.9 79.1 75.9 68.8 FKC-GSVM 94.8 85.4 79.2 75.9 GSVM 82.1 76.4 78.4 64.9 Contraceptive Method Choice FCM-GSVM 85.4 82.7 79.3 69.8 FKC-GSVM 91.6 87.2 85.6 81.5 GSVM 81.2 77.1 70.2 63.8 Pen-Based Recognition of Handwritten Digits FCM-GSVM 84.6 80.6 75.6 70.3 FKC-GSVM 90.7 83.3 80.4 72.9 GSVM 85.2 82.1 79.7 69.3 NDC-10k FCM-GSVM 86.5 83.8 81.4 79.6 FKC-GSVM 89.6 86.1 84.6 82.3 GSVM 80.2 72.4 73.5 66.6 NDC-11 FCM-GSVM 83.7 79.3 76.9 72.9 FKC-GSVM 86.5 83.8 82.3 79.2 FCM-GSVM和GSVM是在原空间进行粒度 说，只要在能接受的分类效果的范围内，选取合 划分和支持向量粒的提取，然后把支持向量粒映 适的阈值，采用FKC-GSVM就能快速地得到需要 射到高维空间进行分类，而FKC-GSVM是直接在 的分类效果。图2~5是Contraceptive Method Cho- 核空间进行粒度划分和支持向量粒的提取，然后 ice数据集在不同阈值条件下采用FKC-GSVM分 在相同的核空间进行分类。从表2的测试结果可 类的效果图，从这几个图中可以很直观地看出， 以看出，由于FCM-GSVM和GSVM可能导致数 FKC-GSVM的分类效果还是比较令人满意的。 据在原空间和核空间分布不一致，在相同的阈值 3.0t 条件下，其分类效果要比FKC-GSVM的分类效果 28 。实际测试集分类 差，这说明FKC-GSVM的泛化能力比FCM-GS- 6 ·预测测试集分类 2.4 VM的泛化能力强。 2.2 为了分析在不同阈值条件下FKC-GSVM的 蓝2.0 1.8 泛化性能，本文给出了0.9、0.85、0.8、0.75四个不 梁16 同阈值条件下的实验。从表2可以看出，阈值越 .4 1.2 小，FKC-GSVM的分类效果越差，这是因为阈值 1.0 0 50100150200250300350400450500 越小，选取的支持向量粒就越少，这一过程可能 测试样本数/个 丢失了一些支持向量，影响了分类效果。但是阈 图2FKC-GSVM在阈值为0.9条件下的分类效果 值越小，大大压缩了训练样本集，算法训练的速 Fig.2 The classification results of FKC-GSVM under the 度得到了很大的提高。因此，对于大规模样本来 threshold 0.9
表 1 实验采用的数据集 Table 1 Datasets used in experiments 数据集 Abalone Contraceptive Method Choice Pen-Based Recognition of Hand-written Digits NDC-10k NDC-1l #训练集 3 177 1 000 6 280 10 000 100 000 #测试集 1 000 473 3 498 1 000 10 000 维度 8 9 16 32 32 为了比较数据集在原空间粒化和在核空间粒 化的不同效果，本文采用基于模糊聚类的粒度支 持向量机 (FCM-GSVM)、基于模糊核聚类的粒度 支持向量机 (FKC-GSVM) 和粒度支持向量机 (GSVM) 等 3 种算法对 5 个典型的 UCI 数据集进行了 测试，测试结果如表 2 所示。为了更直观地看出 FKC-GSVM 在不同阈值条件下的分类效果，给出 了 Contraceptive Method Choice 数据集在不同阈值 条件下采用 FKC-GSVM 分类的效果图，如图 2~ 图 5 所示。 表 2 FCM-GSVM 与 FKC-GSVM 测试结果比较 Table 2 Comparison of test results between FCM-GSVM and FKC-GSVM % 数据集 算法 阈值 k 0.9 0.85 0.8 0.75 Abalone GSVM 80.1 75.6 76.7 65.6 FCM-GSVM 82.9 79.1 75.9 68.8 FKC-GSVM 94.8 85.4 79.2 75.9 Contraceptive Method Choice GSVM 82.1 76.4 78.4 64.9 FCM-GSVM 85.4 82.7 79.3 69.8 FKC-GSVM 91.6 87.2 85.6 81.5 Pen-Based Recognition of Handwritten Digits GSVM 81.2 77.1 70.2 63.8 FCM-GSVM 84.6 80.6 75.6 70.3 FKC-GSVM 90.7 83.3 80.4 72.9 NDC-10k GSVM 85.2 82.1 79.7 69.3 FCM-GSVM 86.5 83.8 81.4 79.6 FKC-GSVM 89.6 86.1 84.6 82.3 NDC-1l GSVM 80.2 72.4 73.5 66.6 FCM-GSVM 83.7 79.3 76.9 72.9 FKC-GSVM 86.5 83.8 82.3 79.2 FCM-GSVM 和 GSVM 是在原空间进行粒度 划分和支持向量粒的提取，然后把支持向量粒映 射到高维空间进行分类，而 FKC-GSVM 是直接在 核空间进行粒度划分和支持向量粒的提取，然后 在相同的核空间进行分类。从表 2 的测试结果可 以看出，由于 FCM-GSVM 和 GSVM 可能导致数 据在原空间和核空间分布不一致，在相同的阈值 条件下，其分类效果要比 FKC-GSVM 的分类效果 差，这说明 FKC-GSVM 的泛化能力比 FCM-GSVM 的泛化能力强。 为了分析在不同阈值条件下 FKC-GSVM 的 泛化性能，本文给出了 0.9、0.85、0.8、0.75 四个不 同阈值条件下的实验。从表 2 可以看出，阈值越 小，FKC-GSVM 的分类效果越差，这是因为阈值 越小，选取的支持向量粒就越少，这一过程可能 丢失了一些支持向量，影响了分类效果。但是阈 值越小，大大压缩了训练样本集，算法训练的速 度得到了很大的提高。因此，对于大规模样本来 说，只要在能接受的分类效果的范围内，选取合 适的阈值，采用 FKC-GSVM 就能快速地得到需要 的分类效果。图 2~5 是 Contraceptive Method Choice 数据集在不同阈值条件下采用 FKC-GSVM 分 类的效果图，从这几个图中可以很直观地看出， FKC-GSVM 的分类效果还是比较令人满意的。 3.0 2.8 2.6 2.4 2.2 2.0 1.8 1.6 1.4 1.2 1.0 0 50 100 150 200 250 300 350 400 450 500 类别标签/个 测试样本数/个 实际测试集分类 预测测试集分类 图 2 FKC-GSVM 在阈值为 0.9 条件下的分类效果 Fig. 2 The classification results of FKC-GSVM under the threshold 0.9 第 6 期 黄华娟，等：基于模糊核聚类粒化的粒度支持向量机 ·1275·