欢迎访问一起赢论文辅导网
本站动态
联系我们
 
 
 
 
 
 
 
 
 
 
 
QQ:3949358033

工作时间:9:00-24:00
SCI期刊论文
当前位置:首页 > SCI期刊论文
一种改进的最小二乘孪生支持向量机分类算法
来源:一起赢论文网     日期:2015-04-22     浏览数:3118     【 字体:

 摘要:提出了一种新的模式分类器, 即广泛权重的最小二乘孪生支持向量机. 该支持向量机在正、 负两类样本上广泛地增加权重, 很好地抑制了交叉噪声样本对数据分类的影响. 其次, 根据间隔最大化原理, 该支持向量机在目标函数上增加了一个正规化项, 实现结构风险最小化和避免在求解该目标函数时可能对病态矩阵求逆的处理. 同时, 提出了利用一种指数函数计算训练样本的密度来获得样本权重值的算法. 该算法能够有效缩减计算权重的时间, 且具有较强的鲁棒性. 实验证明本文提出的广泛权重的最小二乘孪生支持向量机能够实现高精度和高效率的分类效果, 而且特别适合于含有交叉噪声样本的数据集分类.

关键词: 模式分类; 最小二乘; 孪生支持向量机; 权重; 指数函数

1 引言

( Support Vector MachineSVM) 1 Vapnik 等人提出, 现已广泛应用于模式分类和回归分析等领域[2 4 标准的支持向量机以结构风险最小化为准则, 且遵循间隔最大化的思想, 其目标是构建一个满足要求的最优分类超平面. 随着技术的发展,支持向量机又衍生出新的算法. 2007 年, Javadeva 等人提出了孪生支持向量机(Twin SVM TSVM) 5 TSVM 寻求两个非平行的最优分类面, 使得每一个分类面靠近一类样本而远离其它类样本. TSVM 适合于交叉分类面数据集的分类, 且求解两个相对更小的二次规划问题(Quadratic Programming Problem QPP) 这使得 TSVM 的速度明显快于标准的支持向量机. 邵元海等人在 TSVM的基础上提出了孪生边界支持向量机 ( Twin BoundSVM TBSVM) 6 它通过在目标函数上增加正规化项来实现结构风险最小化. 其他的研究学者又提出了其它改进的 TSVM 7 9 这些支持向量机在鲁棒性、 有效性和泛化性等方面都有不同程度的提高.2009 年, Kumar Gopal TSVM 基础上提出了最小二乘孪生支持向量机(Least Squares TSVM LSTS-VM) 10 LSTSVM TSVM 样适合 于交叉分 面数据集的分类. LSTSVM 用近似支持向量机(ProximalSVM PSVM)的思想来求解两个线性方程, 而不是求解QPPs 这使得 LSTSVM TSVM 的求解速度更快.

基于LSTSVM 陈静等学者提出了加权的最小二乘孪生支持向量机(Weighted LSTSVM WLSTSVM) 11 WLSTSVM通过对数据样本增加不同的权重值, 来提高算法的鲁棒性. 但是, WLSTSVM 对于每一个 QPP 而言, 仅对其中一类数据样本的误差量增加了权重, 这使得 WLSTSVM对于含有交叉噪声样本数据集的分类效果不好. 而且,WLSTSVM 的权重值是经过对样本数据集训练提取误差信息后计算得到的, 这种方法不但会消耗大量的计算时间, 而且对交叉分类面数据集不具备鲁棒性. 另外, 必须指出的是, 标准的支持向量机考虑了结构风险最小化原则, WLSTSVM LSTSVM 只具备经验风险最小化.本文基于 LSTSVM 算法提出了广泛权重的最小二乘孪生支持向量机(Widely Weighted LSTSVM WWL-STSVM) 对于每一个 QPP 而言, WLSTSVM 相同的是 WWLSTSVM 在一类样本误差量上增加了权重, 不同的是在另一类样本误差量上也增加了权重. 这一改变有利于抑制交叉噪声样本对分类结果的影响.

其次, 利用 TBSVM 的思想, WWLSTSVM 的目标函数增加正规化项以实现结构风险最小化, 而且所增加的正规化项可避免在求解过程中可能对病态矩阵的求逆处理.再者, WWLSTSVM 设计了一种有效的权重算法, 即通过采用一种指数函数估计训练样本的密度信息来获得相应样本的权重. 基于人工数据集的实验表明,WWLSTSVM 能有效地抑制交叉噪声样本对数据分类的影响, 而且其权重算法对非交叉分类面数据集和交叉分类面数据集都具有很好的鲁棒性;基于 UCI 数据集的实验表明, WWLSTSVM 具有高的分类精度和计算效率.

2 最小二乘孪生支持向量机

LSTSVM 源于 TSVM 通过求解两个 QPP 来获得一对非平行的分类超平面, 适合交叉分类面数据集的分类. LSTSVM 又不同于 TSVM LSTSVM 求解的是两个线性方程而不是求解两个 QPP 因此其计算速度要比 TS-VM 快. 下面, 对非线性的 LSTSVM 作一描述:minu 1 γ112K(A C')u 1 + e 1 γ 1 2 +C 12ξ'2 ξ 2s t (K(B C')u 1 + e 2 γ 1 ) = e 2 ξ2(1)minu 2 γ212K(B C')u 2 + e 2 γ 2 2 +C 22ξ'1 ξ 1s t (K(A C')u 2 + e 1 γ 2 ) = e 1 ξ1(2)其中, A 表示 + 1 类样本矩阵, B 表示 1 类样本矩阵,C = A' B' ' ‖·‖表示 L 2 范数, K 表示可选择的核函数, ξ 1 ξ 2 表示误差量, e 1 e 2 表示全 1 向量, C 1 C 2 为惩罚因子.根据式(1)和式(2) 两个非平行的分类超平面 K(x' C')u 1+ γ1 =0 K(x' C')u 2+ γ2= 0 对应的解如下:u 1γ[ ]1= (H'H +1C 1G'G)1H'e 2 (3)u 2γ[ ]2= (G'G +1C 2H'H)1G'e 1 (4)其中, G = K(A C') e 1 H = K(B C') e 2

 (3)有一逆矩阵项(H'H + G'G/C 1 )1 H'H + G'G/C1 可能存在不可逆的情况. 为了避免这种情况发生, 一般将逆矩阵项改为(H'H + G'G/C 1 + εI)110 这里, I 是单位矩阵, ε 是一个很小的正数.对于线性的 LSTSVM 其分类超平面为 x'w 1+ γ1 =0 x'w 2+ γ2 =0 它可以通过使用等式 K(x' C') = x'C w 1 = C'u 1 w 2 = C'u 2 变换获得.

3 广泛权重的最小二乘孪生支持向量机

3. 1 线性 WWLSTSVM假设样本矩阵 A∈R m1 × d B∈R m 2 × d 其中, A = A1A 2 … A m1 ' B = B 1B 2 … B m2 ' A i ∈Rd ×1 表示 +1 类的数据样本, B t ∈R d ×1 表示 1 类的数据样本, 样本的总数为 m = m 1 + m 2 则线性的 WWLSTSVM 二次规划问题可表示如下:minw 1 b 1C 32(w 1 2 + b 12 ) + 12m 1i =1v 1i ξ 21i +C 12m 2t =1v 2t ξ 22ts t A ' i w 1 + b 1= ξ1i i =1 2 …, m 1B ' t w 1 + b 1 +1 = ξ 2t t =1 2 …, m 2 (5)minw 2 b 2C 42(w 2 2 + b 22 ) + C 22m 1i =1v 1i η 21i +12m 2t =1v 2t η 22ts t B ' t w 2 + b 2= η2t t =1 2 …, m 2 (A ' i w 2 + b 2 ) +1 = η 1i i =1 2 …, m 1 (6)其中, C 1 C 2 C 3 C 4 为惩罚因子, v 1i v 2t 为权重参数.显然, (5)有一个额外的正规化项 C 3 (w 1 2 +b 12 ) /2 由式(5)可以看出, 要实现其结构风险最小化的方法是使两个支持超平面 x'w 1 + b 1 = 0 x'w 1 + b 1= 1 的间隔最大化[6 间隔最大化等价于正规化项C 3 (w 1 2 + b 12 ) /2 最小化. 同时, (5)分别给误差量 ξ 1i ξ 2t 增加了权重 v 1i v 2t v 1i 0 v 2t 0 WL-STSVM 相比, WWLSTSVM 给正负两类所有数据样本的误差量增加了权重, 这种广泛实施权重的方法可以有效地去除噪声样本特别是交叉噪声样本对数据分类的影响. 这一点将在后面的实验章节进行验证. (5)中的惩罚因子 C 1 C 3 可以实现最小化误差量 ξ 1i 最小化误差量 ξ 2t 和最大化间隔三者之间的平衡.首先, 将式(5)的等式约束条件代入目标函数, 可得到:minw 1 b 1C 32(w 1 2 + b 12 ) + 12m 1i =1v 1i (A ' i w 1 + b 1 ) 2+C 12m 2t =1v 2t (B ' t w 1 + b 1 +1) 2 (7)其次, 将式(7)对于变量 w 1 b 1 偏导值设为 0 可得到:C 3 w 1 + m 1i =1v 1i A i (A ' i w 1 + b 1 )+ C 1 m 2t =1v 2t B t (B ' t w 1 + b 1 +1) =0(8)C 3 b 1 + m 1i =1 v 1i (A'i w 1 + b 1 )+ C 1 m 2t =1v 2t (B ' t w 1 + b 1 +1) =0(9)然后, 将式(8)(9)合并为矩阵形式:C 3 Iw 1b[ ]1+A'v 1 A A'v 1 e 1e ' 1 v 1 A e ' 1 v 1 e[ ]1w 1b[ ]1+ C 1B'v 2 B B'v 2 e 2e ' 2 v 2 B e ' 2 v 2 e[ ]2w 1b[ ]1= C 1B'v 2 e 2e ' 2 v 2 e[ ]2(10)最后, 定义两个矩阵 E F 并求解 w 1 b 1 如下:E = p 1 A p 1 e 1 F = p 2 B p 2 e 2 (11)C 3 Iw 1b[ ]1+ C 1(p 2 B)'(p 2 e 2 )[ ]'p 2 A p 2 e[ ]2w 1b[ ]1+(p 1 A)'(p 1 e 1 )[ ]'p 1 A p 1 e[ ]1w 1b[ ]1= C 1B'v 2 e 2e ' 2 v 2 e[ ]2(12)w 1b[ ]1= (1C 1E'E + F'F +C 3C 1I)1F'p 2 e 2 (13)上述公式中, e 1 ∈R m1 ×1 e2 ∈Rm 2 ×1是全 1 向量, I(d + 1) × (d + 1) 维单位矩阵, v 1 ∈R m1 × m 1 v 2 ∈R m2 × m 2 是分别以(v1 ) ii (v 2 ) tt 为对角元素的对角矩阵,v 1 = p ' 1 p 1 v 2 = p ' 2 p 2 p 1 p 2 是对角阵. 可以看出, (13)增加了一项 C 3 I/C 1 该项可以在不人为增加 εI 项的情况下, 有效的避免对病态矩阵的求逆处理.同理, 可求得式(6)的解:w 2b[ ]2= (E'E +1C 2F'F +C 4C 2I)1E'p 1 e 1 (14)最终, (13)(14)确定了两个最优的非平行分类超平面:x'w 1 + b 1 =0 x'w 2 + b 2 =0 (15)一个新的未标签数据样本 x∈R d 属于 + 1 类还是-1 类, 取决于样本 x 距离哪一个分类超平面的垂直距离更近. 其公式如(16)所示. 其中,· 表示求绝对值.x+1 类,|x'w 1 + b 1 |w 1 ‖<|x'w 2 + b 2 |w 2 ‖-1 类,|x'w 1 + b 1 |w 1 ‖>|x'w 2 + b 2 |w 2{(16)3. 2 非线性 WWLSTSVM同样的, 可将非线性 LSTSVM 扩展为非线性 WWL-STSVM 非线性 WWLSTSVM 构造的两个非平行分类超平面可表示为:K(x' C')u 1+ γ1 =0 K(x' C')u 2+ γ2 =0(17)其中, C = A' B' ' K 为可选择的核函数. 非线性WWLSTSVM 二次规划问题构造为:minu 1 γ1C 32(u 1 2+ γ12 ) + 12m 1i =1v 1i ξ 21i +C 12m 2t =1v 2t ξ 22ts t K(A ' i C')u 1+ γ1= ξ1i i =1 2 …, m 1K(B ' t C')u 1+ γ1 +1 = ξ 2t t =1 2 …, m 2(18)minu 2 γ2C 42(u 2 2+ γ22 ) + C 22m 1i =1v 1i η 21i +12m 2t =1v 2t η 22ts t K(B ' t C')u 2+ γ2= η2t t =1 2 …, m 2 (K(A ' i C')u 2+ γ2 ) +1 = η 1i i =1 2 …, m 1(19)经过一系列的推导, (18)(19)的解如下:u 1γ[ ]1= (1C 1G'G + H'H +C 3C 1I)1H'p 2 e 2 (20)u 2γ[ ]2= (G'G +1C 2H'H +C 4C 2I)1G'p 1 e 1 (21)其中:G = p 1 K(A C') p 1 e 1 H = p 2 K(B C') p 2 e 2 (22)一个新的未标签数据样本 x∈R d 属于 + 1 类还是-1 类, 取决于样本 x 距离哪一个分类超平面的距离更近, 其公式如下:x+1 类,|K(x' C')u 1+ γ1 |u 1 ‖<|K(x' C')u 2+ γ2 |u 2 ‖-1 类,|K(x' C')u 1+ γ1 |u 1 ‖>|K(x' C')u 2+ γ2 |u 2{(23)

4 WWLSTSVM 算法

4. 1 权重算法在 WWLSTSVM 公式中, 参数 v 1 v 2 决定了分类的可靠性和准确性. 最优的权重值可以有效地去除噪声样本特别是交叉噪声样本对数据分类的影响. WL-STSVM 算法[11 12 但是它耗时长, 而且对交叉分类面的数据集而言鲁棒性不够好. 为了解决这些问题, 本文提出了一种新的权重算法, 它对训练样本的密度进行估计, 并将此估计信息作为样本的权重.核密度估计(Kernel Density Estimation KDE)是从统计学领域发展而来. 样本的 KDE 信息能够反映其在数据集中的重要性[ 8 即样本的密度越大, 该样本在数据集中越重要. 对于样本 x 而言, 它的密度估计值可以通过计算样本 x 与其邻域样本的相似性而得到. 样本 x 的密度值越大, 则样本 x 与它的邻域样本就越相似. 一般, 可以使用高斯核函数来计算两个数据样本之间的距离来估计它们的相似性. 文献[ 13 提到的一种指数函数也可以用于计算两个样本之间的距离, 其表达式如下:μ(x i ) = (exp(d p (x i x j ) λ ))1/β(24)其中, 参数 λ 为正的常数, 参数 β 为距离阈值. d p (x i x j )是样本 x i x j 间的闵科夫斯基(Minkowski)距离.该指数函数可以很好的估计样本间的相似性[13 14 ]. 在文献[ 14 中, 该指数函数被很好的应用于计算两个像素点之间的相似性, d p (x i x j )被定义为欧氏距离, λ被设为 1 β 被定义为一个可调参数.

本文利用式(24)来估计样本的密度, 并认为样本的密度越大, 则样本在数据集的权重越大. 假设训练样本矩阵 A = A 1 A 2 A m1 ' Ω i是以 A i 为中心、 r为半径的邻域. 根据式(24) 可以计算数据样本 A i 在邻域 Ω i 的密度, 并将此密度值作为样本 A i 的权重值,其公式如下:v 1i = A j ∈Ω i(exp(A j A i ))1/r i =1 2 …, m1(25)其中, ‖·‖代表 L 2 范数(欧式距离) λ β 分别定义为 1 r 数据样本 A i 的密度与邻域 Ω i 内的所有样本都相关. 邻域 Ω i 内的样本 A j 与中心样本 A i 越近, 则样本 A j 对中心样本 A i 的密度贡献就越大. 显然, 样本 Ai的密度值最小为 1 同时, 半径 r 会影响样本的密度. 半径 r 越小, 每一个数据样本就越独立, 相反, 数据样本的密度值差异就越小. 因此, 半径 r 应根据实际问题来决定, 一般可从某个区间搜索最优的 r 值.同样, 对训练样本矩阵 B = B 1 B 2 B m2 ',定义 Ω t 是以 B t 为中心、 r 为半径的邻域. 数据样本 B t的权重值计算如下:v 2t = B j ∈Ω t(1 + exp(B j B t ))1/r t =1 2 …, m2(26)

4. 2 线性和非线性 WWLSTSVM 算法根据本文第三节的内容, 可将线性分类器 WWL-STSVM 的算法归纳为: 第一步:选择合适的参数 r C 1 C 2 C 3 C 4 .第二步:用式(25)(26)计算权重参数 v 1i v 2t .第三步:计算 p 1 p 2 并由式(11)定义 E F.第四步:利用式(13)(14)计算并确定两个非平行的分类超平面.第五步:根据式(16)对新的未标签数据样本 x∈R d 进行分类.类似的, 非线性分类器 WWLSTSVM 的算法可归纳为:第一步:选择合适的参数 r C 1 C 2 C 3 C 4 以及核函数 K.第二步:用式(25)(26)计算权重参数 v 1i v 2t .第三步:计算 p 1 p 2 并由式(22)定义 G H.第四步:利用式(20)(21)计算并确定两个非平行的分类超平面.第五步:根据式(23)对新的未标签数据样本 x∈R d 进行分类.

5 实验及分析

为了验证 WWLSTSVM 的性能, 本文既在二维的人工数据集上进行了算法抑制交叉噪声样本干扰的对比实验, 又在 UCI 标准数据集上进行了算法精度与效率的测试实验.首先, 本文针对含有交叉噪声样本的数据集进行分类实验, 以此来验证算法抑制交叉噪声样本的有效性. 假设有两个被交叉噪声样本污染的二维数据集, 一个是非交叉分类面数据集, 一个是交叉分类面数据集.分别用 LSTSVM WLSTSVM 文献[ 11 提出的权重算法的 WWLSTSVM(WWLSTSVM- 1)以及本文提出的新权重算法的 WWLSTSVM 进行分类实验, 且实验的参数{C i |i =1 2 3 4} r 均做了优化选择. 其实验结果如图 1 和图 2 所示. 从图 1 不难看出, LSTSVM 受交叉噪声样本的影响很大. 对于 WLSTSVM 一类分类面的效果较好, 而另一类的分类面发生了偏移, 这是因为 WL-STSVM 只给一类样本增加了权重, 没有考虑另一类样本的权重. 对于 WWLSTSVM- 1 WWLSTSVM 它们都具有很好的分类效果, 这是因为它们对所有噪声样本的误差量赋予了小的权重值, 而对所有的非噪声样本赋予了大的权重值. 从图 2 可以看出, LSTSVM WL-STSVM 分类器在交叉分类面数据集上受交叉噪声样本的影响很大. WWLSTSVM- 1 在交叉分类面数据集上的分类结果也不理想, 这是因为文献[ 11]提出的权重算法对交叉分类面数据集缺乏鲁棒性. 本文提出的新权重算法的 WWLSTSVM 分类效果则较为理想.其次, 为了验证 WWLSTSVM 的分类性能, 本文从标准 UCI 机器学习库中选取了 8 个数据集, 并分别对线性和非线性两种类型的 WWLSTSVM WWLSTSVM- 1WLSTSVM LSTSVM PSVM TSVM 进行分类精度与计算效率的测试实验. 在实验的过程中, 所有数据集的数据样本被归一化到[ 0 1 区间, 并将数据集 90%的数据样本划分为训练集, 10% 的数据样本划分为测试集. 非线性情况均采用高斯核函数, 核参数从[ 28 2 4 ]区间选取. 参数{C i | i = 1 2 3 4}在区间[ 220 2 4 ]中选取, 参数 r 在区间[ 0 1 0 4]中选取. 所有参数的选取方法均采用十字交叉验证法[5 10 最终所有分类器的分类测试结果如表 1 和表 2 所示.从表1 和表2 不难看出, 本文提出的线性和非线性WWLSTSVM 的分类精度要好于 WWLSTSVM- 1 WLSTS-VM LSTSVM PSVM TSVM 以表 2 中的 Ionosphere 数据集为例, WWLSTSVM 的分类精度是 93. 75% WWL-STSVM- 1 WLSTSVM LSTSVM PSVM TSVM 的分类精度 92. 85%92. 05%90. 06%89. 17%90. 06% 这表明本文提出的分类器 WWLSTSVM 提高了分类精度. 从表1 和表2 中也可以看出各个分类器计算耗费的时间. 由于本文提出的新权重算法降低了时间计算的复杂度, 所以 WWLSTSVM 计算耗费的时间明显少 WWLSTSVM- 1 WLSTSVM 同时, TSVM WWLSTSVM 耗费的计算时间要长的多, 这是因为 TS-VM 需要求解两个具有不等式约束的 QPP WWL-STSVM 求解的是两个线性方程. 但是, WWLSTSVM LSTSVM PSVM 两个分类器耗费的计算时间要长一些, 这是因为 WWLSTSVM 花费了时间计算样本的权重来提高分类精度.

6 结论

本文在 LSTSVM 基础上提出了广泛权重的最小二乘孪生支持向量机(WWLSTSVM) WWLSTSVM 通过给所有的数据样本赋予权重值来抑制交叉噪声样本对分类结果的影响. 同时, 根据间隔最大化思想在目标函数上增加了正规化项, 既实现了结构风险最小化, 又避免了在求解过程中可能对病态矩阵求逆的处理. 此外, 本文还提出了一种新的权重算法, 它使用一种指数函数计算训练样本的密度值, 并将此密度作为样本的权重值. 最终, 在二维人工数据集上的实验表明, WWLSTS-VM 可以有效地去除交叉噪声样本对分类结果的影响,并且对交叉分类面数据集具备好的鲁棒性. UCI 数据集上的实验表明, WWLSTSVM 算法具有较高的分类精度和计算效率. 下一步的研究, 可考虑将 WWLSTSVM扩展到多类别分类中.

参考文献[ 1Cortes C Vapnik V Support vector networks J MachineLearning 1995 20(3):273 297.[ 2 Bayro- Corrochano E J Arana- Daniel N Clifford supportvector machines for classification regression and recur-rence J IEEE Trans on Neural Networks 2010 21(11):1731 1746.[ 3Ertekin S et al Nonconvex online support vector machines J IEEE Trans on Pattern Analysis and Machine Intelli-gence 2011 33(2):368 381.[ 4 Zhang Y S et al Adaptive resource allocation with SVM-based multi- hop video packet delay bound violation modeling J Chinese Journal of Electronics 2011 20(2):261 267.[ 5Jayadeva et al Twin support vector machines for patternclassification J IEEE Trans on Pattern Analysis and Ma-chine Intelligence 2007 29(5):905 910.[ 6Shao Y H et al Improvements on twin support vector ma-chines J IEEE Trans on Neural Networks 2011 22(6):962 968.[ 7Qi Z Q Tian Y J et al obust twin support vector machinefor pattern classification J Pattern classification 2013 46(1):305 316.[ 8 Peng X J Xu Dong Bi- density twin support vector ma-chines for pattern recognitionJ Neurocomputing 201399(1):134 143.[ 9Ye Q L Zhao C X et al Weighted twin support vector ma-chines with local information and its application J NeuralNetworks 2012 35(11):31 39.[ 10 Kumar M Gopal M Least squares twin support vectormachines for pattern classificationJ Expert Systemwith Applications 2009 36(4):7535 7543.[ 11Chen J Ji G R. Weighted least squares twin support vectormachines for pattern classificationA The 2nd Interna-tional Conference on Computer and Automation Engineer-ing C Singapore:IEEE 2010 242 246.[ 12Suykens J A K et al Weighted least squares support vec-tor machines:obustness and sparse approximationJ Neurocomputing 2002 48(1 4):85 105.[ 13Plataniotis K N et al Adaptive fuzzy systems for multi-channel signal processingJ Proceedings of the IEEE1999 87(9):1601 1622.[ 14Jin L H et al Improved bilateral filter for suppressingmixed noise in color imagesJ Digital Signal Process-ing 2012 22(6):903 912

[返回]
上一篇:基于 SSVM 的递归统计不相关特征抽取算法
下一篇:L p 范数约束的多核半监督支持向量机学习方法