第6期 史荧中，等：基于核心向量机的多任务概念漂移数据快速分类 ·937· 过约束相邻时刻共享矢量的差异使共享矢量链的 变化尽量平稳，入为约束各个模型平稳变化的参 m27 w.l2+b)+ 数；mim∑ar是使各子任务在同一时刻的模 4T☑ 2.lw,-wl+(b,-b)2)+ =1k=1 型尽量相似，这是协同求解多个概念漂移问题的 (4) 关键；权衡因子y表示多个任务间的相关程度； 22+-p+2 =1k=1 1 L(fk,x,y)为损失函数。根据文献[15]的推导，可得 s.t.y:((w,+v)(x )+(b,+di)p-5i 到SVC-SVM方法的对偶形式： i=1,2…,n ma1-0 Ha st≥0 式(4)中用记号k0、dko间接表示第i个样本属于 (3) 任务k中的第t个子数据集。下面求解式(4)的对 式中：H为扩展核空间上的某个核函数，具体表 偶问题： 达形式可以参见相关文献[15]。从式(3)可知，SVC SVM方法对多个概念漂移问题同时建模，其对偶 J=27∑awP+的+ 问题为核空间中的另一个支持向量机问题，当采 用普通方法来求解此二次规划问题时，其算法时 2a.-f+6-b+ (5) 间复杂度为On),即便采用SMO161方法来求解 SVC-SVM的对偶问题，使其复杂度降为On2), 22f+-2 仍然是无法承受计算的代价，难以从容面对现实 ∑o6(,+umgu)+b+dn小-p+s刻 生活中数据规模较大的应用场景。 由KKT条件，J取得极值时，有 2共享矢量链核心向量机及快速算法 aJ J0 E=0,a=0,w= =0. 2.1共享矢量链核心向量机 鉴于VC-SVM方法在针对多任务概念漂移 黑-兴--0 大规模数据集时算法时间复杂度偏高，本文借鉴 因此有： 8J CVM9的思路，提出了与SVC-SVM方法在分类 OE: =0=C5-a→6=，/C 性能相似，但在数据量较大的场景时又能进行快 -0=-1+2=24= (6) 速处理的SVC-CVM方法。SVC-CVM方法借鉴 ap 人 了SVC-SVM方法的思想，为了能进一步用快速 将式(6)代入式(5)则有 算法求解，本文按文献[17-18]的方法对SVC-SVM阿 (7) 的目标函数稍作变化，采用平方损失函数，通过 2 推导得到可以用CVM方法快速求解的对偶形式。 式中： 设数据集{x,y)i=1,2,…n中含有n个样本点， 其中包含K个数据流，每个数据流中的数据由 (8) T个按时间顺序采集的子数据集组成。在每个时 Saywe(x 刻引入某个共享矢量，记第时刻各个数据流共享 某个矢量为"，第时刻第k个数据流的决策函数为 (9) f,并记决策函数与共享矢量之间的差为"k= f-w,。P为T×n矩阵，用于标识第j个点是否为第 J6=2 2r号22--a t个时间段的数据，P,=1当且仅当j∈pP,否则取值 (10) 为0。R为k×n矩阵，用于标识第j个点是否属于 (11) 第k个子数据集，当且仅当jer时Rk=1,否则取 值为0。Q为指示各共享向量之间相关性的T×T 又： 矩阵，实际应用中只考虑直接相邻的各共享向 量，即当且仅当s-=1时有Q.=1,否则值为0。 SVC-CVM方法的目标函数为 得：λ min∑T t=1 ∑K k=1 ∥vtk∥ 2 γ L(ftk, x, y) 过约束相邻时刻共享矢量的差异使共享矢量链的 变化尽量平稳， 为约束各个模型平稳变化的参 数； 是使各子任务在同一时刻的模 型尽量相似，这是协同求解多个概念漂移问题的 关键；权衡因子 表示多个任务间的相关程度； 为损失函数。根据文献[15]的推导，可得 到 SVC-SVM 方法的对偶形式： max α α T 1− 1 2 α THα s.t. α ⩾ 0 (3) O(n 3 ) O(n 2.3 ) 式中：H 为扩展核空间上的某个核函数，具体表 达形式可以参见相关文献[15]。从式 (3) 可知，SVC￾SVM 方法对多个概念漂移问题同时建模，其对偶 问题为核空间中的另一个支持向量机问题，当采 用普通方法来求解此二次规划问题时，其算法时 间复杂度为 ，即便采用 SMO[16]方法来求解 SVC-SVM 的对偶问题，使其复杂度降为 ， 仍然是无法承受计算的代价，难以从容面对现实 生活中数据规模较大的应用场景。 2 共享矢量链核心向量机及快速算法 2.1 共享矢量链核心向量机 鉴于 SVC-SVM 方法在针对多任务概念漂移 大规模数据集时算法时间复杂度偏高，本文借鉴 CVM[17-19]的思路，提出了与 SVC-SVM 方法在分类 性能相似，但在数据量较大的场景时又能进行快 速处理的 SVC-CVM 方法。SVC-CVM 方法借鉴 了 SVC-SVM 方法的思想，为了能进一步用快速 算法求解，本文按文献[17-18]的方法对 SVC-SVM[15] 的目标函数稍作变化，采用平方损失函数，通过 推导得到可以用 CVM 方法快速求解的对偶形式。 {(xi , yi)|i=1,2,···,n} n t wt t k ftk vtk = ftk−wt P T ×n j t Pt j = 1 j ∈ pt R tk×n j tk j ∈ rtk Rtk, j = 1 Q T ×T |s−t| = 1 Qst = 1 设数据集 中含有 个样本点， 其中包含 K 个数据流，每个数据流中的数据由 T 个按时间顺序采集的子数据集组成。在每个时 刻引入某个共享矢量，记第 时刻各个数据流共享 某个矢量为 ,第 时刻第 个数据流的决策函数为 ，并记决策函数与共享矢量之间的差为 。 为 矩阵，用于标识第 个点是否为第 个时间段的数据， 当且仅当 ，否则取值 为 0。 为 矩阵，用于标识第 个点是否属于 第 个子数据集，当且仅当 时 ，否则取 值为 0。 为指示各共享向量之间相关性的 矩阵，实际应用中只考虑直接相邻的各共享向 量，即当且仅当 时有 ，否则值为 0。 SVC-CVM 方法的目标函数为 min w,v,b,d 1 2T ∑T t=1 (∥wt∥ 2 +b 2 t )+ λ 4T ∑T t=1 ∑T s=1 Qts(∥wt −ws∥ 2 +(bt −bs) 2 )+ γ 2 ∑T t=1 ∑K k=1 (∥vtk∥ 2 +d 2 tk)−ρ+ C 2 ∑n i=1 ξ 2 i s.t. yi ( (wt +vtk(i)) T φ(xi)+(bt +dtk(i)) ) ⩾ ρ−ξi i = 1,2,··· ,n (4) vtk(i) dtk(i) i k t 式 (4) 中用记号 、 间接表示第 个样本属于 任务 中的第 个子数据集。下面求解式 (4) 的对 偶问题： J = 1 2T ∑T t=1 (∥wt∥ 2 +b 2 t )+ λ 4T ∑T t=1 ∑T s=1 Qts(∥wt −ws∥ 2 +(bt −bs) 2 )+ γ 2 ∑T t=1 ∑K k=1 (∥vtk∥ 2 +d 2 tk)−ρ+ C 2 ∑n i=1 ξ 2 i − ∑n i=1 αi ( yi ( (wt +vtk(i)) T φ(xi)+(bt +dtk(i)) ) −ρ+ξi ) (5) 由 KKT 条件，J 取得极值时，有 ∂J ∂ξi = 0, ∂J ∂ρ = 0, ∂J ∂wt = 0, ∂J ∂bt = 0, ∂J ∂vtk = 0, ∂J ∂dtk = 0 因此有： ∂J ∂ξi = 0 = Cξi −αi ⇒ ξi = αi/C ∂J ∂ρ = 0 = −1+ ∑n i=1 αi ⇒ ∑n i=1 αi = 1 (6) 将式 (6) 代入式 (5) 则有 J=Jw + Jv + Jb + Jd − 1 2C ∑n i=1 α 2 i (7) 式中： Jw= 1 2T ∑T t=1 ∥wt∥ 2 + λ 4T ∑T t=1 ∑T s=1 Qts∥wt −ws∥ 2− ∑n i=1 αiyiwt(i)φ(xi) (8) Jv= γ 2 ∑T t=1 ∑K k=1 ∥vtk∥ 2 − ∑n i=1 αiyivtk (i)φ(xi) (9) Jb= 1 2T ∑T t=1 ∥bt∥ 2 + λ 4T ∑T t=1 ∑T s=1 Qts∥bt − bs∥ 2 − ∑n i=1 αiyibt(i) (10) Jd= γ 2 ∑T t=1 ∑K k=1 d 2 tk − ∑n i=1 αiyidtk (i) (11) 又： ∂J ∂wt = 0= 1 T wt + λ T ∑T s=1 Qts(wt −ws)− ∑ j∈ptk αjyjφ(xj) 得： 第 6 期 史荧中，等：基于核心向量机的多任务概念漂移数据快速分类 ·937·