·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 年首次提出粒度支持向量机 (gran￾ular support vector machine, GSVM) 这个术语。GS￾VM 的总体思想是在原始空间将数据集进行划 分，得到数据粒。然后提取出有用的数据粒，并 对其进行 SVM 训练 [11-12]。与传统支持向量机相 比，GSVM 学习机制具有以下优点：针对大样本 数据，通过数据粒化和对有用粒子 (支持向量粒) 的提取，剔除了无用冗余的样本，减少了样本数 量，提高了训练效率。然而，Tang 只是给出了 GSVM 学习模型的一些设想，没有给出具体的学 习算法。2009 年，张鑫[ 1 3 ] 在 Tang 提出的 GS￾VM 思想的基础上，构建了一个粒度支持向量机 的模型，并对其学习机制进行了探讨。此后，许 多学者对支持向量机和粒度计算相结合的具体模 型进行了研究，比如模糊支持向量机[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 卷