第13卷第6期 智能系统学报 Vol.13 No.6 2018年12月 CAAI Transactions on Intelligent Systems Dec.2018 D0:10.11992/tis.201712019 网络出版地址：http:/kns.cnki.net/kcms/detail/23.1538.TP.20180417.0849.002.html 基于核心向量机的多任务概念漂移数据快速分类 史荧中2，王士同，邓赵红3，侯立功2，钱冬杰2 (1.江南大学数字媒体学院，江苏无锡214122,2.无锡职业技术学院物联网学院，江苏无锡214121；3.江苏省 媒体设计与软件技术重点实验室（江南大学），江苏无锡214122) 摘要：通过协同求解多个概念漂移问题并充分挖掘相关概念漂移问题中蕴含的有效信息，共享矢量链支持向 量机(shared vector chain supported vector machines,SVC-SVM)在面向多任务概念漂移分类时表现出良好性能。 然而实际应用中的概念漂移问题通常有较大的数据容量，较高的计算代价限制了SVC-SVM方法的推广能力。 针对这个弱点，借鉴核心向量机的近线性时间复杂度的优势，提出了适于多任务概念漂移大规模数据的共享矢 量链核心向量机(shared vector chain core vector machines,.SVC-CVM)。SVC-CVM具有渐近线性时间复杂度的算 法特点，同时又继承了SVC-SVM方法协同求解多个概念漂移问题带来的良好性能，实验验证了该方法在多任 务概念漂移大规模数据集上的有效性和快速性。 关键词：多任务；大规模数据集：概念漂移：核心向量机：线性时间复杂度 中图分类号：TP181文献标志码：A文章编号：1673-4785(2018)06-0935-11 中文引用格式：史荧中，王士同，邓赵红，等.基于核心向量机的多任务概念漂移数据快速分类.智能系统学报，2018， 13(6):935-945. 英文引用格式：SHI Yingzhong,WANG Shitong,DENG Zhaohong,etal.The core vector machine-based rapid classification of multi-task concept drift dataset Jl.CAAI transactions on intelligent systems,2018,13(6):935-945. The core vector machine-based rapid classification of multi-task concept drift dataset SHI Yingzhong,WANG Shitong',DENG Zhaohong,HOU Ligong,QIAN Dongjie (1.School of Digital Media,Jiangnan University,Wuxi214122,China;2.School of Internet of Things,Wuxi Institute of Techno- logy,Wuxi 214121,China;3.Jiangsu Key Laboratory of Media Design and Software Technology,Jiangnan University,Wuxi 214122,China) Abstract:The shared vector chain-supported vector machine(SVC-SVM)can solve multiple concept drift problems as well as related problems,and it shows attractive performance in multi-task concept drift classification.However,in many practical scenarios,the concept drift dataset is usually large,and its high computational cost severely limits the generalization ability of the SVC-SVM.To overcome this shortcoming,a novel classifier termed shared vector chain- core vector machine(SVC-CVM)is proposed for large scale multi-task concept drift dataset,considering the asymptot- ic linear time complexity of the core vector machines.This classifier has the merit of asymptotic time complexity and in- herits the good performance of SVC-SVM in solving multi-task concept drift problems.Furthermore,the effectiveness and rapidness of the proposed method is experimentally confirmed on large-scale multi-task concept drift datasets. Keywords:multi-task;large-scale dataset;concept drift;core vector machines;linear time complexity 收稿日期：2017-12-13.网络出版日期：2018-04-17. 随着计算机信息技术的发展，每天都会产生 基金项目：国家自然科学基金项目(61300151)：江苏省杰出青年 基金项目(BK20140001,江苏省高等教育教改研究 大量电信服务、电子商务、金融市场、交通流量、 课题(2017JSJG282):江苏省高校自然科学研究项目 网络监控、超市零售等方面的数据，这些数据是 (18KJB520048). 通信作者：史荧中.E-mail:shiyz@(wxit.edu.cn. 持续增加且不断变化的。由于数据特征会随着时
DOI: 10.11992/tis.201712019 网络出版地址: http://kns.cnki.net/kcms/detail/23.1538.TP.20180417.0849.002.html 基于核心向量机的多任务概念漂移数据快速分类 史荧中1,2，王士同1 ，邓赵红1,3，侯立功2 ，钱冬杰2 （1. 江南大学 数字媒体学院，江苏 无锡 214122; 2. 无锡职业技术学院 物联网学院，江苏 无锡 214121; 3. 江苏省 媒体设计与软件技术重点实验室 (江南大学)，江苏 无锡 214122） 摘 要：通过协同求解多个概念漂移问题并充分挖掘相关概念漂移问题中蕴含的有效信息，共享矢量链支持向 量机 (shared vector chain supported vector machines，SVC-SVM) 在面向多任务概念漂移分类时表现出良好性能。 然而实际应用中的概念漂移问题通常有较大的数据容量，较高的计算代价限制了 SVC-SVM 方法的推广能力。 针对这个弱点，借鉴核心向量机的近线性时间复杂度的优势，提出了适于多任务概念漂移大规模数据的共享矢 量链核心向量机 (shared vector chain core vector machines，SVC-CVM)。SVC-CVM 具有渐近线性时间复杂度的算 法特点，同时又继承了 SVC-SVM 方法协同求解多个概念漂移问题带来的良好性能，实验验证了该方法在多任 务概念漂移大规模数据集上的有效性和快速性。 关键词：多任务；大规模数据集；概念漂移；核心向量机；线性时间复杂度 中图分类号：TP181 文献标志码：A 文章编号：1673−4785(2018)06−0935−11 中文引用格式：史荧中, 王士同, 邓赵红, 等. 基于核心向量机的多任务概念漂移数据快速分类[J]. 智能系统学报, 2018, 13(6): 935–945. 英文引用格式：SHI Yingzhong, WANG Shitong, DENG Zhaohong, et al. The core vector machine-based rapid classification of multi-task concept drift dataset[J]. CAAI transactions on intelligent systems, 2018, 13(6): 935–945. The core vector machine-based rapid classification of multi-task concept drift dataset SHI Yingzhong1,2 ，WANG Shitong1 ，DENG Zhaohong1,3 ，HOU Ligong2 ，QIAN Dongjie2 (1. School of Digital Media, Jiangnan University, Wuxi 214122, China; 2. School of Internet of Things, Wuxi Institute of Technology, Wuxi 214121, China; 3. Jiangsu Key Laboratory of Media Design and Software Technology, Jiangnan University, Wuxi 214122, China) Abstract: The shared vector chain-supported vector machine (SVC-SVM) can solve multiple concept drift problems as well as related problems, and it shows attractive performance in multi-task concept drift classification. However, in many practical scenarios, the concept drift dataset is usually large, and its high computational cost severely limits the generalization ability of the SVC-SVM. To overcome this shortcoming, a novel classifier termed shared vector chaincore vector machine (SVC-CVM) is proposed for large scale multi-task concept drift dataset, considering the asymptotic linear time complexity of the core vector machines. This classifier has the merit of asymptotic time complexity and inherits the good performance of SVC-SVM in solving multi-task concept drift problems. Furthermore, the effectiveness and rapidness of the proposed method is experimentally confirmed on large-scale multi-task concept drift datasets. Keywords: multi-task; large-scale dataset; concept drift; core vector machines; linear time complexity 随着计算机信息技术的发展，每天都会产生 大量电信服务、电子商务、金融市场、交通流量、 网络监控、超市零售等方面的数据，这些数据是 持续增加且不断变化的。由于数据特征会随着时 收稿日期：2017−12−13. 网络出版日期：2018−04−17. 基金项目：国家自然科学基金项目 (61300151);江苏省杰出青年 基金项目 (BK20140001); 江苏省高等教育教改研究 课题 (2017JSJG282);江苏省高校自然科学研究项目 (18KJB520048). 通信作者：史荧中. E-mail：shiyz@wxit.edu.cn. 第 13 卷第 6 期 智 能 系 统 学 报 Vol.13 No.6 2018 年 12 月 CAAI Transactions on Intelligent Systems Dec. 2018
·936· 智能系统学报 第13卷 间逐渐变化，针对这些非静态数据的分类、回归、 方法优于独立求解单个概念漂移问题的TA-SVM 聚类模型也在随着时间而缓慢漂移，称为概念漂 及ITA-SVM方法； 移。对概念漂移的研究已在理论上及交通 2)SVC-CVM方法采用了与SVC-SVM方法相 流量预测、超市客户行为分析、气体传感器阵 同的技巧，即假设多个概念漂移问题共享渐变的 列漂移可、垃圾邮件过滤8等应用场合取得了良好 矢量链序列，因而在分类性能上，SVC-CVM方法 的效果。概念漂移建模过程中每个时刻的数据量 与SVC-SVM方法相当： 都很少，因而需要借助相邻时刻的一些数据来构 3)SVC-CVM方法可以借鉴CVM理论Im设计 建合适的当前时刻模型。以往针对概念漂移分类 出快速求解算法，以处理多任务概念漂移中数据 所作的工作大多是基于滑动窗算法的思路，即 量较大的问题，算法时间复杂度接近O)。 采用一定时间窗口（区间）内的数据进行建模。 2011年，Grinblat等2借鉴Crammer等在多任务 1概念漂移问题相关研究 学习中兼顾局部优化与全局优化的策略，提出了 在概念漂移研究方面，传统的研究是基本滑 时间自适应支持向量机方法来求解渐变的子分 动窗算法，这是一类局部优化模式。TA-SVM和 类器。Shi等1提出了增强型时间自适应支持向 ITA-SVM方法对局部优化和全局优化进行了权 量机方法，在提高分类性能的同时，从理论上保 衡，取得了良好的效果。 证了其对偶为凸二次规划问题。 1.1单任务概念漂移分类方法 由于生活中的概念漂移问题并不是孤立出现 TA-SVM方法及ITA-SVM方法针对的是 的，如某个气体传感器阵列上对多种气体的测定 传统的单任务概念漂移分类。假设有T个按时间 数据可能会同时漂移；相邻城市的天气情况具有 顺序采集的子数据集，TA-SVM方法在优化各子 一定的关联；相近街区的交通流量会相互影响 分类器的同时，还假设子分类器应该能够光滑地 等。对多个相关概念漂移问题同时建模，挖掘其 变化，因此约束相邻子分类器之间的差异，其基 他问题中的有效信息，能对建模起到有益的补充。 共享矢量链支持向量机(shared vector chain sup- 本思想可由()式来表示。 T-1 ported vector machines,SVC-SVM)方法通过对相 min∑Risk(+a∑df4,fD (1) 关概念漂移问题协同建模，有效地提升了所得模 = 型的泛化性能。但由于具有较高的算法时间复杂 式中：第1项为局部优化项，为第1个子分类器； 度，限制了其在数据量急剧增长的社会现状下的 第2项为全局优化项，df,)为相邻两个子分类 应用能力。 器之间的差别，以保证子分类器能平稳变化；是 现在已进入大数据时代，各种社交和电子商 对局部优化与全局优化进行权衡的因子。 务等信息量都越来越大，多任务概念漂移算法的 1.2SVC-SVM方法及其对偶 时间复杂度也变得越来越重要。SVC-SVM方法 为了能进一步挖掘出相关概念漂移数据集中 可转化为核空间中的另一SVM问题，算法时间 蕴含的有效信息，需要协同求解多个分类模型。 复杂度一般为On),其中n为样本容量。如采用 假定现有K个相关概念漂移数据集，每个概念漂 SMO(sequential minimal optimization)l6方法来求 移数据集中的数据由T个按时间顺序采集的子数 解，其复杂度可降为O(n2),但SVC-SVM方法仍 据集组成，每个子数据集中的数据量为m个。将 然无法从容面对大规模概念漂移数据集。本文旨 所有数据合并记为数据集{(x,y)i=1,2,…,以，n=K× 在寻找出一种新的概念漂移学习方法，除了能保 T×m。记f为第k(k=1,2,…,K个任务在第(t=1,2,…, 持SVC-SVM方法良好的分类特性外，又能在面 T)时刻的分类模型，w,为第时刻的共享矢量， 对多任务概念漂移大规模数据集时具有较好的算 表示在第时刻共享矢量与第k个任务f之间的差 法时间性能。 异。面向多任务概念漂移分类的共享矢量链支持 结合前期在概念漂移领域的研究基础46 向量机方法SVC-SVM的原理可通过式(2)来表示： 本文提出了共享矢量链核心向量机(shared vector chain core vector machines,.SVC-CVM)方法，并基 m72w+分-w =1 于核心向量机a(core vector machine,.CVM)理论 (2) 给出了SVC-CVM方法的快速算法。所提SVC 2+c2列 CVM方法具有以下特点： -1 1)面对多任务概念漂移问题时，SVC-CVM 式中：min∑w,为正则化项，min∑w1-w,通
间逐渐变化，针对这些非静态数据的分类、回归、 聚类模型也在随着时间而缓慢漂移，称为概念漂 移 [1-2]。对概念漂移的研究已在理论上[1-4]及交通 流量预测[5] 、超市客户行为分析[6] 、气体传感器阵 列漂移[7] 、垃圾邮件过滤[8]等应用场合取得了良好 的效果。概念漂移建模过程中每个时刻的数据量 都很少，因而需要借助相邻时刻的一些数据来构 建合适的当前时刻模型。以往针对概念漂移分类 所作的工作大多是基于滑动窗算法[9-11]的思路，即 采用一定时间窗口 (区间) 内的数据进行建模。 2011 年，Grinblat 等 [12]借鉴 Crammer 等在多任务 学习中兼顾局部优化与全局优化的策略，提出了 时间自适应支持向量机[13]方法来求解渐变的子分 类器。Shi 等 [14]提出了增强型时间自适应支持向 量机方法，在提高分类性能的同时，从理论上保 证了其对偶为凸二次规划问题。 由于生活中的概念漂移问题并不是孤立出现 的，如某个气体传感器阵列上对多种气体的测定 数据可能会同时漂移；相邻城市的天气情况具有 一定的关联；相近街区的交通流量会相互影响 等。对多个相关概念漂移问题同时建模，挖掘其 他问题中的有效信息，能对建模起到有益的补充。 共享矢量链支持向量机[15] (shared vector chain supported vector machines, SVC-SVM) 方法通过对相 关概念漂移问题协同建模，有效地提升了所得模 型的泛化性能。但由于具有较高的算法时间复杂 度，限制了其在数据量急剧增长的社会现状下的 应用能力。 O(n 3 ) n O(n 2.3 ) 现在已进入大数据时代，各种社交和电子商 务等信息量都越来越大，多任务概念漂移算法的 时间复杂度也变得越来越重要。SVC-SVM 方法 可转化为核空间中的另一 SVM 问题，算法时间 复杂度一般为 ，其中 为样本容量。如采用 SMO(sequential minimal optimization) [16]方法来求 解，其复杂度可降为 ，但 SVC-SVM 方法仍 然无法从容面对大规模概念漂移数据集。本文旨 在寻找出一种新的概念漂移学习方法，除了能保 持 SVC-SVM 方法良好的分类特性外，又能在面 对多任务概念漂移大规模数据集时具有较好的算 法时间性能。 结合前期在概念漂移领域的研究基础[14-16] ， 本文提出了共享矢量链核心向量机 (shared vector chain core vector machines, SVC-CVM) 方法，并基 于核心向量机[17-19] (core vector machine, CVM) 理论 给出了 SVC-CVM 方法的快速算法。所提 SVCCVM 方法具有以下特点： 1) 面对多任务概念漂移问题时，SVC-CVM 方法优于独立求解单个概念漂移问题的 TA-SVM 及 ITA-SVM 方法； 2)SVC-CVM 方法采用了与 SVC-SVM 方法相 同的技巧，即假设多个概念漂移问题共享渐变的 矢量链序列，因而在分类性能上，SVC-CVM 方法 与 SVC-SVM 方法相当； O(n) 3)SVC-CVM 方法可以借鉴 CVM 理论[17]设计 出快速求解算法，以处理多任务概念漂移中数据 量较大的问题，算法时间复杂度接近 。 1 概念漂移问题相关研究 在概念漂移研究方面，传统的研究是基本滑 动窗算法，这是一类局部优化模式。TA-SVM 和 ITA-SVM 方法对局部优化和全局优化进行了权 衡，取得了良好的效果。 1.1 单任务概念漂移分类方法 TA-SVM[13]方法及 ITA-SVM[14]方法针对的是 传统的单任务概念漂移分类。假设有 T 个按时间 顺序采集的子数据集，TA-SVM 方法在优化各子 分类器的同时，还假设子分类器应该能够光滑地 变化，因此约束相邻子分类器之间的差异，其基 本思想可由 (1) 式来表示。 min∑T t=1 Risk(ft)+λ ∑T−1 t=1 d (ft+1 , ft) (1) ft t d(ft+1, ft) λ 式中：第 1 项为局部优化项， 为第 个子分类器； 第 2 项为全局优化项， 为相邻两个子分类 器之间的差别，以保证子分类器能平稳变化； 是 对局部优化与全局优化进行权衡的因子。 1.2 SVC-SVM 方法及其对偶 {(xi , yi)|i = 1,2,··· ,n} n = K× T ×m ftk k(k = 1,2,··· ,K) t(t = 1,2,··· , wt t vtk t k ftk 为了能进一步挖掘出相关概念漂移数据集中 蕴含的有效信息，需要协同求解多个分类模型。 假定现有 K 个相关概念漂移数据集，每个概念漂 移数据集中的数据由 T 个按时间顺序采集的子数 据集组成,每个子数据集中的数据量为 m 个。将 所有数据合并记为数据集 ， 。记 为第 个任务在第 T) 时刻的分类模型， 为第 时刻的共享矢量， 表示在第 时刻共享矢量与第 个任务 之间的差 异。面向多任务概念漂移分类的共享矢量链支持 向量机方法 SVC-SVM 的原理可通过式 (2) 来表示： min 1 2T ∑T t=1 ∥wt∥ 2 + λ 2T ∑T−1 t=1 ∥wt+1 −wt∥ 2+ γ 2 ∑T t=1 ∑K k=1 ∥vtk∥ 2 +C ∑n i=1 L(ftk, x, y) (2) min∑T t=1 ∥wt∥ 2 min∑T−1 t=1 ∥wt+1 −wt∥ 式中： 为正则化项 2 , 通 ·936· 智 能 系 统 学 报 第 13 卷
第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) 可知，SVCSVM 方法对多个概念漂移问题同时建模，其对偶 问题为核空间中的另一个支持向量机问题，当采 用普通方法来求解此二次规划问题时，其算法时 间复杂度为 ，即便采用 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·
·938· 智能系统学报 第13卷 非+a侧-小- 由 8 2=0→k-∑apx)→M=1/y∑aw4x) 若定义矩阵M为 M={0地0 得 st 因矩阵M可逆，则 aiyivip(xi)= w=∑Meyx) (12) L5∑wawwywywoFw4au- 因此有 zq"((R'R/A)8K@Y)a wR-∑∑Momp/y (17) 因此有 由于 (PMrP=∑MMd -3a(PMPOK@Y）a- ia'(《G1)©K8n+ 则由(12)可得： J-UIC)at1- wf=∑PMP,my -zq((PM-P+G/y)K@Y)a+ (13) ar(PrM2P)⑧K⑧Y)a J.+J-QICa 同时有 又： 22a.m-mf=∑a∑MG-Mx =1= 器=07+2-+ (Md-Ma,ayy,(x,p(r）= aJ 224∑ML-2M0 (14) =0→4-∑d4=n∑ jEpl 由此可得： aiaiyiyo(x)p(x）= 2a(PrM(D-Q)M-P)⑧K⑧Y)a J--jq(PM-P+RR/ysKeY)a- 式中：Q是对称矩阵，且记对角矩阵D为 _a(PM-P+RR/yGK)a-o(/C)a Du= ∑0,1= J=-2a'(《PMP+RR)©K@(Y+D+I1Ca t≠ 将(12、(13)代入(8)有 原始问题的对偶问题如下： 人72mf+希22a-f max-2a'HasL.a≥0，a1=1 (18) 式中： axyawpx)=27c（PMPK@Y H=(PMrP+RR/y)⑧K⑧(Y+E)+I/C(19) K为核矩阵； 子e(prD-QMr'mcKey) (15) Y=y'yy=y2…a] E=1×1;1=[1112…1nJ' a-a(PMF)⑧K⑧Y）a= 由此，SVC-CVM方法中虽然包含了多个数 -jo((PM-P)sksy)a 据流，但其对偶问题仍相当于核空间中的另一个 则由(7可知 SVM问题，可以用常规方法来求解，其算法时间 J--jg(PM-P)8KgY)a+ 复杂度为O㎡)，在算法效率上并不具有优势。因 J-dlC)a (16) 此下文将介绍SVC-CVM的快速求解方法。 2.2核心向量机 下面求解J,。 求解最小包含球(minimum enclosing ball,, =Y∑Iwaf-〉之awoo(x) MEB)是一个数学问题，等价于求解一个二次规 划问题19，如式(20)所示：
1 T wt +λ ∑T s=1 Qts(wt −ws) = ∑ j∈ptk αjyjφ(xj) 若定义矩阵 M 为 Mst = { (1+λ ∑ k Qtk)/T, s = t −λQts/T, s , t 因矩阵 M 可逆，则 wt = ∑ j M−1 tt(j)αjyjφ(xj) (12) 因此有 ∑T t=1 ∥wt∥ 2 = ∑ t ∑ i j M−1 tt(i)M−1 tt(j)αiαjyiyjφ(xi)φ(xj) 由于 ( P TM−2P ) i j = ∑ t M−1 tt(i)M−1 tt(j) 则由 (12) 可得： ∑T t=1 ∥wt∥ 2 = ∑ i j ( P TM−2P ) i j αiαjyiyjφ(xi)φ(xj) = α T ( (P TM−2P)⊗ K ⊗Y ) α (13) 同时有 ∑T t=1 ∑T s=1 Qts∥wt −ws∥ 2 = ∑ ts Qts∑ i j (M−1 tt(i) − M−1 ss(i) )× (M−1 tt(j) − M−1 ss(j) )αiαjyiyjφ(xi)φ(xj) = ∑ i j 2(∑ t M−1 tt(i)M−1 tt(j) Dtt − ∑ ts M−1 tt(i)M−1 st(j)Qts)× αiαjyiyjφ(xi)φ(xj) = 2α T ( (P TM−1 (D−Q)M−1P)⊗ K ⊗Y ) α (14) 式中：Q 是对称矩阵，且记对角矩阵 D 为 Dts = ∑ k Qtk, t = s 0, t , s 将 (12)、(13) 代入 (8) 有 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) = 1 2T α T ( (P TM−2P)⊗ K ⊗Y ) α+ λ 2T α T ( (P TM−1 (D−Q)M−1P)⊗ K ⊗Y ) α−α T ( (P TM−1P)⊗ K ⊗Y ) α = − 1 2 α T ( (P TM−1P)⊗ K ⊗Y ) α (15) 则由 (7) 可知 J=− 1 2 α T ( (P TM−1P)⊗ K ⊗Y ) α+ Jv + Jb + Jd − 1 2 α T (I/C)α (16) 下面求解 Jv。 Jv= γ 2 ∑T t=1 ∑K k=1 ∥vtk∥ 2 − ∑n i=1 αiyivtk (i)φ(xi) 由 ∂J ∂vtk = 0 ⇒ γvtk − ∑ j∈ptk αiyiφ(xi) ⇒ vtk = 1/γ∑ j∈ptk αiyiφ(xi) 得 Jv= γ 2 ∑T t=1 ∑K k=1 ∥vtk∥ 2 − ∑n i=1 αiyivtk (i)φ(xi) = − 1 2γ ∑T t=1 ∑K k=1 ∑ i, j∈ptk αtk(i)αtk(j)ytk(i)ytk(j)φ(xtk(i))φ(xtk(j)) = − 1 2 α T ( (R TR / λ 2 )⊗ K ⊗Y ) α (17) 因此有 J=− 1 2 α T ( (P TM−1P)⊗ K ⊗Y ) α− 1 2 α T ((G/λ2)⊗ K ⊗Y)α+ Jb + Jd − 1 2 α T (I/C)α+α T 1= − 1 2 α T ( (P TM−1P+G/γ)⊗ K ⊗Y ) α+ Jb + Jd − 1 2 α T (I/C)α 又： ∂J ∂bt = 0 ⇒ 1 T bt + λ T ∑T s=1 Qst(bs −bt)+ ∑ j∈ptk αjyj ∂J ∂dtk = 0 ⇒ γdtk − ∑ j∈ptk αiyi ⇒ dtk = 1/γ∑ j∈ptk αiyi 由此可得： J=− 1 2 α T ( (P TM−1P+ R TR/γ)⊗ K ⊗Y ) α− 1 2 α T ( (P TM−1P+ R TR/γ)⊗ K ) α− 1 2 α T (I/C)α J=− 1 2 α T ( (P TM−1P+ R TR/γ) ⊗ K ⊗(Y + E)+ I/C)α 原始问题的对偶问题如下： max α − 1 2 α THα s.t. α ⩾ 0,α T1 = 1 (18) 式中： H = (P TM−1P+ R TR/γ)⊗ K ⊗(Y + E)+ I/C (19) K 为核矩阵； Y = y T y y = [y1 y2 ··· yn] E = 1×1 T ;1 = [11 12 ··· 1n] T O(n 3 ) 由此，SVC-CVM 方法中虽然包含了多个数 据流，但其对偶问题仍相当于核空间中的另一个 SVM 问题，可以用常规方法来求解，其算法时间 复杂度为 ，在算法效率上并不具有优势。因 此下文将介绍 SVC-CVM 的快速求解方法。 2.2 核心向量机 求解最小包含球 (minimum enclosing ball, MEB) 是一个数学问题，等价于求解一个二次规 划问题[17-19] ，如式 (20) 所示： ·938· 智 能 系 统 学 报 第 13 卷
第6期 史荧中，等：基于核心向量机的多任务概念漂移数据快速分类 ·939· max a'diag(K)-aTKa s.t. a≥0，a1=1(20) 心co,并设置初始迭代次数t=1 式中：a=[a12…anJ为Lagrange乘子，Knm= 2)若所有点都包含在球B(c,(1+)R)中，则 [k(x,x】=[()'(x】为核矩阵。diag(K)表示由核 转7) 矩阵K的主对角线元素组成的一维向量。 3)找到离中心c,最远的点x,并将其加人核心 Tsang等在文献[17-18]中指出，形如式(20)的 集，即S4=S,Ux 二次规划问题，如果核矩阵对角线元素为常量， 4)对新的核心集进行求解，得到新的半径 则均等价于求解MEB问题。他们借助求解 R+1和中心c+1,并更新权重系数a; MEB问题时的近似包含球方法，提出了核心向 5)计算新的中心到其他各点的距离； 量机(core vector machines,.CVM),在处理大规模数 性质2对于给定的近似误差ε，SVC-CVM算 据集时有接近线性的时间复杂度。对形如式 法时间复杂度上界应为OW/e2+1/e)。 (20)的二次规划问题，即使核矩阵对角线元素不为常 6)t=1+1,转2； 量，也可以使用核心集方法进行求解，这时就需 7)终止训练，返回求解的核心集S,及权重系 要给核空间中每个样本点(x)都添加一个新的维 数a; 度6，∈R样本在新特征空间中表示为(x)=【(x)6:], 输出核心集S,权重系数a。 然后求解在新特征空间中的最小包含球。该问题 3实验研究和分析 的形式如下： maxa(diagK+△)-arKa 本节将对SVC-CVM方法进行实验验证， (21) s.t.m≥0，a1=1 实验将从SVC-CVM方法的分类准确率、SVC 式中：A=[号…≥0是为了保证(20)式中α的 CVM算法的时间性能两个方面展开。这里有必 系数为常量。将式(21)进一步改写为如下形式： 要首先验证其分类准确率。1)需要考察引入分类 max a'(diagK+A-n1)-aKo 间隔P及采用平方损失函数以后，SVC-CVM算法 (22) s.ta≥0,1=1 是否保持了良好的分类能力；2)因为SVC-CVM 式中：n∈R为用户自定义常数，目的是为了保证 方法的有效性是其快速算法有效的必要条件。本 a的系数为非负的。 文另外选取了在单任务概念漂移建模中取得良好 2.3SVC-CVM的快速算法 效果的两个方法作为对比算法，作为对比算法的 当使用普通方法来求解SVC-CVM时，其求 共有：1)TA-SVM方法I;2)ITA-SVM方法1； 解时间复杂度为O),对于多任务概念漂移大规 3)SVM-SVM方法。为了对比的客观性，本节实 模数据集来说，是相当大的计算开销。对比式 验中所使用的数据集及实验的设置都参照对比算 (18)和式(22)，它们具有相似的形式，因此，SVC- 法TA-SVM。实验环境为MATLAB R20I3a,操 CVM方法可以利用核心向量机技巧来求解。可 作系统为Windows7,8GB内存及3.30GHz奔腾 以将式(18)等价地改写为 处理器。 max a (diag(H)+A-n1)-a Ka (23) 3.1实验设置 sL.m≥0，a1=1 实验中涉及的各方法与相应参数在表1中 这是一个标准MEB问题，其中A=-diag()+l, 列出。 通过适当调节常数的值，可以保证4≥0。 表1实验所用的对比方法及相应参数 SVC-CVM算法的输人为多任务概念漂移大 Table 1 Methods and parameters used in experiments 规模数据集S,核心集逼近精度ε、)、A等参数；输 对比算法 求解对象 求解方法 参数 出为核心集S,和权重系数α。下面给出实现步骤： 由于SVC-CVM算法是基于核心集理论的， TA-SVM 单概念漂移 普通二次规划 C,o,入 因而在描述算法的时间与空间复杂度时，可以参 ITA-SVM 单概念漂移 普通二次规划 C,,入 考文献17-18]，得到相关结论： SVC-SVM 多概念漂移 普通二次规划 Co,A.y 性质1对于给定的误差ε，由SVC-CVM算法 SVC-CVM多概念漂移 核心集技术 C.o,A.y.s 求得的核心集数量的上界、算法迭代次数的上 界、得到的支持向量数目上界都为0(1/8)。 本文独立生成相同分布的训练集、验证集和 输入数据集S,最小包含球近似精度； 测试集各10组，共进行10次重复实验，以获得比 1)初始化核心集S。,最小包含球半径R和中 较客观的实验结果。实验分为参数优化和建模测
max α α T diag(K)−α TKα s.t. α ⩾ 0, α T1 = 1 (20) α = [α1 α2 ··· αn] T Kn×n = [k(xi , xj)] = [ϕ(xi) Tϕ(xj)] diag(K) K 式中： 为 Lagrange 乘子, 为核矩阵。 表示由核 矩阵 的主对角线元素组成的一维向量。 ϕ(xi) δi ∈ R ϕ˜(xi) = [ ϕ(xi) δi ] T Tsang 等在文献[17-18]中指出，形如式（20）的 二次规划问题，如果核矩阵对角线元素为常量， 则均等价于求 解 M EB 问题。他们借助求 解 MEB 问题时的近似包含球方法[19] ，提出了核心向 量机 (core vector machines, CVM),在处理大规模数 据集时有接近线性的时间复杂度。对形如式 (20) 的二次规划问题，即使核矩阵对角线元素不为常 量，也可以使用核心集方法进行求解，这时就需 要给核空间中每个样本点 都添加一个新的维 度 ,样本在新特征空间中表示为 ， 然后求解在新特征空间中的最小包含球。该问题 的形式如下： max α α T (diagK + ∆)−α TKα s.t. α ⩾ 0, α T1 = 1 (21) ∆ = [ δ 2 1 δ 2 2 ··· δ 2 n ]T 式中： ⩾ 0 是为了保证 (20) 式中α的 系数为常量。将式 (21) 进一步改写为如下形式： max α α T (diagK +∆−η1)−α TKα s.t. α ⩾ 0, α T1 = 1 (22) η ∈ R α 式中： 为用户自定义常数，目的是为了保证 的系数为非负的。 2.3 SVC-CVM 的快速算法 O(n 3 ) 当使用普通方法来求解 SVC-CVM 时，其求 解时间复杂度为 ，对于多任务概念漂移大规 模数据集来说，是相当大的计算开销。对比式 (18) 和式 (22)，它们具有相似的形式，因此，SVCCVM 方法可以利用核心向量机技巧来求解。可 以将式 (18) 等价地改写为 max α α T (diag(H)+∆−η1)−α TKα s.t. α ⩾ 0, α T1 = 1 (23) ∆ = −diag(H)+η1 η ∆ ⩾ 0 这是一个标准 MEB 问题，其中 ， 通过适当调节常数 的值，可以保证 。 ε η ∆ S t α SVC-CVM 算法的输入为多任务概念漂移大 规模数据集 S, 核心集逼近精度 、 、 等参数；输 出为核心集 和权重系数 。下面给出实现步骤： 由于 SVC-CVM 算法是基于核心集理论的， 因而在描述算法的时间与空间复杂度时，可以参 考文献[17-18]，得到相关结论： ε O(1/ε) 性质 1 对于给定的误差 ，由 SVC-CVM 算法 求得的核心集数量的上界、算法迭代次数的上 界、得到的支持向量数目上界都为 。 输入 数据集 S, 最小包含球近似精度； 1) 初始化核心集 S 0，最小包含球半径 R0和中 心c0，并设置初始迭代次数 t = 1 ; B(ct 2) 若所有点都包含在球 ,(1+ε)Rt) 中,则 转 7); ct x S t+1 S t ∪ x 3) 找到离中心 最远的点 ,并将其加入核心 集，即 = ; Rt+1 ct+1 α 4) 对新的核心集进行求解，得到新的半径 和中心 ，并更新权重系数 ; 5) 计算新的中心到其他各点的距离 ; ε O(N/ε2 +1/ε4 ) 性质 2 对于给定的近似误差 ，SVC-CVM 算 法时间复杂度上界应为 。 6) t = t+1，转 2 ; S t α 7) 终止训练，返回求解的核心集 及权重系 数 ; 输出 核心集 S t，权重系数α。 3 实验研究和分析 ρ 本节将对 SVC-CVM 方法进行实验验证， 实验将从 SVC-CVM 方法的分类准确率、SVCCVM 算法的时间性能两个方面展开。这里有必 要首先验证其分类准确率。1) 需要考察引入分类 间隔 及采用平方损失函数以后，SVC-CVM 算法 是否保持了良好的分类能力；2) 因为 SVC-CVM 方法的有效性是其快速算法有效的必要条件。本 文另外选取了在单任务概念漂移建模中取得良好 效果的两个方法作为对比算法,作为对比算法的 共有：1)TA-SVM 方法[13] ；2)ITA-SVM 方法 [14] ； 3)SVM-SVM 方法[15]。为了对比的客观性，本节实 验中所使用的数据集及实验的设置都参照对比算 法 TA-SVM [13]。实验环境为 MATLAB R2013a，操 作系统为 Windows7， 8 GB 内存及 3.30 GHz 奔腾 处理器。 3.1 实验设置 实验中涉及的各方法与相应参数在表 1 中 列出。 本文独立生成相同分布的训练集、验证集和 测试集各 10 组，共进行 10 次重复实验，以获得比 较客观的实验结果。实验分为参数优化和建模测 表 1 实验所用的对比方法及相应参数 Table 1 Methods and parameters used in experiments 对比算法 求解对象 求解方法 参数 TA-SVM 单概念漂移 普通二次规划 C,σ,λ ITA-SVM 单概念漂移 普通二次规划 C,σ,λ SVC-SVM 多概念漂移 普通二次规划 C,σ,λ,γ SVC-CVM 多概念漂移 核心集技术 C,σ,λ,γ,ε 第 6 期 史荧中，等：基于核心向量机的多任务概念漂移数据快速分类 ·939·