第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·
·940· 智能系统学报 第13卷 试两个阶段，首先需要基于训练集，利用验证集 化参数和建模测试两个阶段。核函数选用最常 获得各方法的最优参数；其次基于得到的优化参 用的线性核及高斯核。当两个概念漂移数据 数对训练集建模，并利用测试集来获得各方法的 Task1、Task2呈现出不同的偏离程度r时，求得各 性能。本文采用网格遍历法来寻找最优参数。 方法在两个概念漂移数据Task1、Task,上的分类 将旋转超平面数据集记为数据集DS,中的第 精度及平均值Average。每个方法对各训练集共 1个任务Task,Task1数据集的样本量为500，采 计10次运行后的平均分类精度及标准差记录在 样于独立分布的2维立方体[-1,1，两类之间的 图1中。 边界是一个超平面，并绕原点缓慢旋转。设超平 表2实验所用的数据集 面的法向量为y,Task,的训练、验证、测试数据由 Table 2 Description of artificial dataset 式(24)生成： 数据集 样本量 描述 y(i)=cos(2ri/500),v2(i)=sin(2πi/500) (24) 旋转超平面数据集，任务间偏移 y=sign(x(i),1≤i≤500 DS 500 不同角度 数据集DS,中的第2个任务Task2数据则由 DS2 500 高斯漂移数据集，任务间振幅变化 Task模型顺时针旋转一定的角度r(r∈{2,4,6,8,10) DS: 500 DS,中加入2%-10%的噪音 后随机生成，以体现出Task与Task模型的相关性。 将TA-SVM方法中所使用的高斯漂移数据集 DS 500 DS2中加入2%~10%的噪音 记为数据集DS2中的第1个任务Task1,数据集中 DSs 500-30000 逐步加大DS,中的采样量 包含两个类别，共含有n(n=500)个数据点，每个类 DS6 500-30000 逐步加大DS,中的采样量 别中数据的特征都在缓慢变化。Task,的训练、验 由图1可以得到如下观察： 证、测试数据由式(25)取r=0时独立生成，DS2中 1)在数据集DS1上，不管采用高斯核还是线 还包含另一个概念漂移数据集Task2,其数据同 性核，当多个任务呈不同偏移程度时，协同求解 样由(25)式生成，这时r≠0，以体现任务之间的差 多个概念漂移问题的SVC-SVM、SVC-CVM方法 异性。 在任务Task,和Task2上总是优于独立求解单个 -元+0.2，+8，(1-r)xsin(2 -元+0.2y)+82 概念漂移问题的TA-SVM和ITA-SVM方法，显 (25) 示了协同求解多任务概念漂移问题是有效的。 式中：t=1,2,…,n,s12服从于均值为0，方差为 2)随着多个任务之间偏离程度的增加，相对 σ=0.1的正态分布，y2、y2是±1的随机序列，并保 于独立求解单个任务，协同求解方法的优势逐渐 持正类负类个数的均衡。为体现出两个概念漂移 减弱。 数据集Task,与Task2的相关性及差异性，将Task2 3)不管是采用高期核还是线性核，也不管任 的生成模型式(11)中的第二维数据作了适度的扰 务间的偏移程度，用普通方法求解的SVC-SVM 动，用参数r来表示概念漂移数据Task2较之 与核心集技术求解的SVC-CVM的分类性能都非 Task1的偏离程度，其中r∈{0.05,0.1,0.2,0.3}。 常接近。 对高斯漂移数据集DS2,按照同样的实验流 将DS1、DS,中的类别标签按一定比例随机 程，求得当两个任务Task,、Task2呈现出不同的 替换以模拟噪音数据，得到数据集DS,、DS4,用 偏离程度时，各方法的分类性能。每个方法对各 于测试SVC-SVM方法在噪音条件下的分类能力。 训练集共计10次运行后的平均分类精度及标准 数据集DS5、DS6由DS,DS2逐步加大采样量 差记录在表3及表4中。 分别得到，它们用于测试SVC-CVM方法的算法 由表3及表4可以得到如下观察： 时间复杂度。实验所用数据集如表2所示。 1)在高斯漂移数据集DS2上，不管是采用高 3.2SVC-SVM的分类性能 斯核还是线性核，协同求解多个概念漂移问题的 本子节基于数据集DS,和DS,来观察SVC SVC-SVM、SVC-CVM方法总是优于独立求解单 CVM方法的分类能力，并将在噪音数据集DS、 个概念漂移问题的TA-SVM方法及ITA-SVM方 DS,上观察SVC-CVM方法在噪音条件下的性能。 法，与数据集DS,上的实验结果相似。 针对数据集DS1,依据文献[13]的策略，我们 2)采用高期核或线性核时，不管任务间的偏 独立生成10组训练集、测试集及用于选择最优参 移程度，SVC-CVM与SVC-SVM方法的分类性能 数的验证集。根据前述的实验设置，实验分为优 是相当的
试两个阶段，首先需要基于训练集，利用验证集 获得各方法的最优参数；其次基于得到的优化参 数对训练集建模，并利用测试集来获得各方法的 性能。本文采用网格遍历法来寻找最优参数。 [−1,1]d v 将旋转超平面数据集记为数据集 DS1 中的第 1 个任务 Task1，Task1 数据集的样本量为 500，采 样于独立分布的 2 维立方体 ，两类之间的 边界是一个超平面，并绕原点缓慢旋转。设超平 面的法向量为 ，Task1 的训练、验证、测试数据由 式 (24) 生成： v1(i) = cos(2πi/500), v2(i) = sin(2πi/500) yi = sign(xiv(i)),1 ⩽ i ⩽ 500 (24) r r ∈ {2,4,6,8,10} 数据集 DS1 中的第 2 个任务 Task2 数据则由 Task1 模型顺时针旋转一定的角度 ( ) 后随机生成，以体现出 Task2 与 Task1 模型的相关性。 n(n = 500) r = 0 r , 0 将 TA-SVM 方法中所使用的高斯漂移数据集 记为数据集 DS2 中的第 1 个任务 Task1，数据集中 包含两个类别，共含有 个数据点，每个类 别中数据的特征都在缓慢变化。Task1 的训练、验 证、测试数据由式 (25) 取 时独立生成，DS2 中 还包含另一个概念漂移数据集 Task2，其数据同 样由 (25) 式生成，这时 ，以体现任务之间的差 异性。 xt = 2tπ n −π+0.2yt +ε1,(1−r)×sin(2tπ n −π+0.2yt)+ε2 (25) t = 1,2,··· ,n ε1,2 σ = 0.1 yt2 yt2 ±1 r r ∈ {0.05,0.1,0.2,0.3} 式中： ， 服从于均值 为 0，方差为 的正态分布， 、 是 的随机序列，并保 持正类负类个数的均衡。为体现出两个概念漂移 数据集 Task1 与 Task2 的相关性及差异性，将 Task2 的生成模型式 (11) 中的第二维数据作了适度的扰 动，用参数 来表示概念漂移数 据 Task 2 较 之 Task1 的偏离程度，其中 。 将 DS1、DS2 中的类别标签按一定比例随机 替换以模拟噪音数据，得到数据集 DS3、DS4，用 于测试 SVC-SVM 方法在噪音条件下的分类能力。 数据集 DS5、DS6 由 DS1 , DS2 逐步加大采样量 分别得到，它们用于测试 SVC-CVM 方法的算法 时间复杂度。实验所用数据集如表 2 所示。 3.2 SVC-SVM 的分类性能 本子节基于数据集 DS1 和 DS2 来观察 SVCCVM 方法的分类能力，并将在噪音数据集 DS3、 DS4 上观察 SVC-CVM 方法在噪音条件下的性能。 针对数据集 DS1，依据文献[13]的策略，我们 独立生成 10 组训练集、测试集及用于选择最优参 数的验证集。根据前述的实验设置，实验分为优 r 化参数和建模测试两个阶段。核函数选用最常 用的线性核及高斯核。当两个概念漂移数据 Task1、 Task2 呈现出不同的偏离程度 时，求得各 方法在两个概念漂移数据 Task1、Task2 上的分类 精度及平均值 Average。每个方法对各训练集共 计 10 次运行后的平均分类精度及标准差记录在 图 1 中。 由图 1 可以得到如下观察： 1) 在数据集 DS1 上，不管采用高斯核还是线 性核，当多个任务呈不同偏移程度时，协同求解 多个概念漂移问题的 SVC-SVM、SVC-CVM 方法 在任务 Task1 和 Task2 上总是优于独立求解单个 概念漂移问题的 TA-SVM 和 ITA-SVM 方法，显 示了协同求解多任务概念漂移问题是有效的。 2) 随着多个任务之间偏离程度的增加，相对 于独立求解单个任务，协同求解方法的优势逐渐 减弱。 3) 不管是采用高期核还是线性核，也不管任 务间的偏移程度，用普通方法求解的 SVC-SVM 与核心集技术求解的 SVC-CVM的分类性能都非 常接近。 r 对高斯漂移数据集 DS2，按照同样的实验流 程，求得当两个任务 Task1、 Task2 呈现出不同的 偏离程度 时，各方法的分类性能。每个方法对各 训练集共计 10 次运行后的平均分类精度及标准 差记录在表 3 及表 4 中。 由表 3 及表 4 可以得到如下观察： 1) 在高斯漂移数据集 DS2 上，不管是采用高 斯核还是线性核，协同求解多个概念漂移问题的 SVC-SVM、SVC-CVM 方法总是优于独立求解单 个概念漂移问题的 TA-SVM 方法及 ITA-SVM 方 法，与数据集 DS1 上的实验结果相似。 2) 采用高期核或线性核时，不管任务间的偏 移程度，SVC-CVM 与 SVC-SVM 方法的分类性能 是相当的。 表 2 实验所用的数据集 Table 2 Description of artificial dataset 数据集 样本量 描述 DS1 500 旋转超平面数据集，任务间偏移 不同角度 DS2 500 高斯漂移数据集，任务间振幅变化 DS3 500 DS1 中加入 2%～10% 的噪音 DS4 500 DS2 中加入 2%～10% 的噪音 DS5 500～30 000 逐步加大 DS1 中的采样量 DS6 500～30 000 逐步加大 DS2 中的采样量 ·940· 智 能 系 统 学 报 第 13 卷
第6期 史荧中，等：基于核心向量机的多任务概念漂移数据快速分类 ·941· ◆--TA-SVM SVC-SVM -ITA-SVMSVC-CVM 。M◆Ww 97.5 97.5 97.0 97.0 96.5 96.5 96.0 96.0 95.5 955 95.0 95.0 94.5 94.5 94.0 94.0 2 345 345 6 子任务间偏移量 子任务间偏移量 (a)Task1上采用高斯核 (b)Task2上采用高斯核 ◆-·TA-SVM SVC-SVM ◆-TA-SVM-…o-·TA-SVM o-·ITA-SVM-SVC-CVM eSVC-SVM--SVC-CVM 98.0 98.0 97.5 97.5 97.0 97.0 写类 96.5 96.5 96.0 96. 3 4 0 23 4 6 子任务间偏移量 子任务间偏移量 (c)Task1上采用线性核 (d)Task,上采用线性核 图1旋转超平面数据集DS,上各概念漂移数据之间偏移角度变化时的分类性能 Fig.1 Classification accuracies on DS with different diversities of data stream 表3数据集DS,上采用高斯核时各方法的平均分类精度 Table 3 Classification accuracies on dataset DS,with Gaussian kernel 不同偏移的分类精度 方法 Task =0.05 =0.1 1=0.2 =0.3 TA-SVM 98.25+0.32 98.26+0.23 98.13+0.14 97.64+0.21 ITA-SVM 98.33+0.21 98.40+0.12 98.1740.18 97.82+0.19 Task SVC-SVM 98.65+0.08 98.60+0.12 98.30+0.14 97.92+0.13 SVC-CVM 98.64+0.08 98.62+0.08 98.27+0.14 97.91+0.16 TA-SVM 98.38+0.09 98.43+0.14 98.38+0.22 98.38+0.18 ITA-SVM 98.49+0.11 98.50+0.09 98.48+0.16 98.45+0.18 Task2 SVC-SVM 98.77+0.04 98.69+0.09 98.61+0.09 98.55+0.17 SVC-CVM 98.71+0.06 98.66+0.04 98.57+0.10 98.54+0.11 表4数据集DS?上采用线性核时各方法的平均分类精度 Table 4 Classification accuracies on dataset DS,with Linear kernel 不同偏移的分类精度 方法 Task 1=0.05 =0.1 1=0.2 =0.3 TA-SVM 97.92+0.39 97.76+0.50 97.70+0.26 97.30+0.49 ITA-SVM 97.80+0.23 97.71+0.19 97.46+0.39 97.05+0.31 SVC-SVM Taski 98.36+0.06 98.17+0.13 97.89+0.20 97.55+0.29 SVC-CVM 98.31+0.10 98.15+0.13 97.82+0.21 97.56+0.35 TA-SVM 98.04+0.39 98.12+0.21 97.85+0.83 97.92+0.36 ITA-SVM Task2 97.91+0.25 97.86+0.18 97.90+0.21 97.77+0.27 SVC-SVM 98.48+0.11 98.30+0.11 98.31+0.14 97.98+0.30 SVC-CVM 98.44+0.13 98.27+0.16 98.23+0.15 98.03+0.29
0 1 2 3 4 5 6 7 94.0 94.5 95.0 95.5 96.0 96.5 97.0 97.5 (a) Task1 上采用高斯核 准确率/% TA-SVM ITA-SVM SVC-SVM SVC-CVM 0 1 2 3 4 5 6 7 94.0 94.5 95.0 95.5 96.0 96.5 97.0 97.5 (b) Task2 上采用高斯核 准确率/% TA-SVM ITA-SVM SVC-SVM SVC-CVM 0 1 2 3 4 5 6 7 96.0 96.5 97.0 97.5 98.0 (c) Task1 上采用线性核 准确率/% TA-SVM ITA-SVM SVC-SVM SVC-CVM 0 1 2 3 4 5 6 7 96.0 96.5 97.0 97.5 98.0 (d) Task2 上采用线性核 准确率/% TA-SVM SVC-SVM ITA-SVM SVC-CVM 子任务间偏移量 子任务间偏移量 子任务间偏移量 子任务间偏移量 图 1 旋转超平面数据集 DS1 上各概念漂移数据之间偏移角度变化时的分类性能 Fig. 1 Classification accuracies on DS1 with different diversities of data stream 表 3 数据集 DS2 上采用高斯核时各方法的平均分类精度 Table 3 Classification accuracies on dataset DS2 with Gaussian kernel 方法 Task 不同偏移的分类精度 r=0.05 r=0.1 r=0.2 r=0.3 TA-SVM Task1 98.25+0.32 98.26+0.23 98.13+0.14 97.64+0.21 ITA-SVM 98.33+0.21 98.40+0.12 98.17+0.18 97.82+0.19 SVC-SVM 98.65+0.08 98.60+0.12 98.30+0.14 97.92+0.13 SVC-CVM 98.64+0.08 98.62+0.08 98.27+0.14 97.91+0.16 TA-SVM Task2 98.38+0.09 98.43+0.14 98.38+0.22 98.38+0.18 ITA-SVM 98.49+0.11 98.50+0.09 98.48+0.16 98.45+0.18 SVC-SVM 98.77+0.04 98.69+0.09 98.61+0.09 98.55+0.17 SVC-CVM 98.71+0.06 98.66+0.04 98.57+0.10 98.54+0.11 表 4 数据集 DS2 上采用线性核时各方法的平均分类精度 Table 4 Classification accuracies on dataset DS2 with Linear kernel 方法 Task 不同偏移的分类精度 r=0.05 r=0.1 r=0.2 r=0.3 TA-SVM Task1 97.92+0.39 97.76+0.50 97.70+0.26 97.30+0.49 ITA-SVM 97.80+0.23 97.71+0.19 97.46+0.39 97.05+0.31 SVC-SVM 98.36+0.06 98.17+0.13 97.89+0.20 97.55+0.29 SVC-CVM 98.31+0.10 98.15+0.13 97.82+0.21 97.56+0.35 TA-SVM Task2 98.04+0.39 98.12+0.21 97.85+0.83 97.92+0.36 ITA-SVM 97.91+0.25 97.86+0.18 97.90+0.21 97.77+0.27 SVC-SVM 98.48+0.11 98.30+0.11 98.31+0.14 97.98+0.30 SVC-CVM 98.44+0.13 98.27+0.16 98.23+0.15 98.03+0.29 第 6 期 史荧中，等：基于核心向量机的多任务概念漂移数据快速分类 ·941·
·942· 智能系统学报 第13卷 下面继续评估SVC-CVM方法在噪音数据集 到表6中。 DS,和DS4上的表现，以观察本文方法的抗噪能 由表5及表6可知： 力。与文献[13]的实验设置相同，通过将DS,和 1)在噪音数据集DS,及DS4上，不管采用高 DS,上的类别标签随机变换来模拟噪音数据，噪 斯核或是线性核时，SVC-SVM和SVC-CVM方法 音比例分别为2%~10%。在数据集DS3和DS4上， 相对于独立求解的TA-SVM方法及ITA-SVM方 当含有不同噪音时各方法的实验结果记录在表5 法，都有较大的优势。 表5数据集DS,上各方法在不同噪音下的平均分类精度 Table 5 Classification accuracies on dataset DS;with Different kernel 不同噪声的分类精度 方法 Kernel 2 4 6 8 10 TA-SVM 96.24+0.13 94.09+0.24 92.08+0.34 90.03+0.30 87.88+0.38 ITA-SVM 96.27+0.12 94.01+0.14 91.86+0.26 89.71+0.38 87.40+0.27 Gauss SVC-SVM 96.41+0.08 94.35+0.13 92.34+0.18 90.24+0.16 88.14+0.22 SVC-CVM 96.42+0.28 94.40+0.14 92.3740.40 90.42+0.16 88.25+0.39 TA-SVM 95.73+0.30 93.64+0.38 91.48+0.56 89.42+0.43 86.98+0.79 ITA-SVM 95.40+0.19 93.13+0.17 90.95+0.25 88.78+0.40 86.47+0.37 Linear SVC-SVM 96.04+0.09 93.98+0.20 91.93+0.18 89.83+0.21 87.65+0.30 SVC-CVM 95.94+0.43 93.99+0.24 91.89+0.22 89.73+0.42 87.51+0.55 表6数据集DS4上各方法在不同噪音下的平均分类精度 Table 6 Classification accuracies on dataset DS,with Different kernel 不同噪声的分类精度 方法 Kernel 2 4 6 8 10 TA-SVM 92.39+0.50 90.17+0.27 88.15+0.82 86.00+0.61 83.94+0.56 ITA-SVM 93.12+0.31 90.88+0.26 88.62+0.50 86.65+0.33 84.43+0.47 Gauss SVC-SVM 94.17+0.35 92.16+0.32 89.77+0.33 87.81+0.48 85.83+0.40 SVC-CVM 94.07+0.33 91.91+0.38 89.66+0.35 87.68+0.25 85.63+0.69 TA-SVM 93.96+0.39 91.76+0.32 89.57+0.41 87.65+0.47 85.73+0.51 ITA-SVM 93.99+0.42 91.66+0.33 89.48+0.56 87.58+0.41 85.37+0.56 Linear SVC-SVM 94.89+0.43 92.78+0.33 90.73+0.37 88.72+0.58 86.70+0.45 SVC-CVM 94.95+0.34 92.88+0.28 90.62+0.39 88.63+0.38 86.54+0.30 2)SVC-CVM与SVC-SVM方法在噪音情况 位为s)为纵坐标描述各方法的时间性能图，将始 下的分类性能是相当的。 的指数曲线转化为线性曲线，斜率代表运行时间 3.3SVC-CVM方法的时间性能 的指数量级，如图2b)所示。 本子节将以数据集DS、DS。为基础来评估各 由图2可以得到如下观察： 方法的算法时间效率。各数据集的样本量从 图2(a)可知，在数据集合DS上，随着训练数 500缓慢增加到30000个。对于数据集DS,独立 据量的加大，各方法的泛化性能稳定增加。同时 生成10组训练集及测试集，并将各方法在取不同 SVC-SVM和SVC-CVM方法优于独立求解单个 容量样本时的平均准确率及平均训练时间显示在 概念漂移问题的TA-SVM和ITA-SVM方法。由 图2中。随着数据量增加时，为了能更准确地观 于用普通SVM方法求解时需要先求解相应方法 察各方法时间性能的量级，本文分别以log1on 的核矩阵，因此受硬件约束较大，当数据量较大 (n为样本量)为横坐标，以1ogoS(S为运行时间，单 时，相应方法无法继续求解。而SVC-CVM方法
下面继续评估 SVC-CVM 方法在噪音数据集 DS3 和 DS4 上的表现，以观察本文方法的抗噪能 力。与文献[13]的实验设置相同，通过将 DS1 和 DS2 上的类别标签随机变换来模拟噪音数据，噪 音比例分别为 2%～10%。在数据集 DS3 和 DS4 上， 当含有不同噪音时各方法的实验结果记录在表 5 到表 6 中。 由表 5 及表 6 可知： 1) 在噪音数据集 DS3 及 DS4 上，不管采用高 斯核或是线性核时，SVC-SVM 和 SVC-CVM 方法 相对于独立求解的 TA-SVM 方法及 ITA-SVM 方 法，都有较大的优势。 2) SVC-CVM 与 SVC-SVM 方法在噪音情况 下的分类性能是相当的。 3.3 SVC-CVM 方法的时间性能 log10n n log10S 本子节将以数据集 DS5、DS6 为基础来评估各 方法的算法时间效率。各数据集的样本量从 500 缓慢增加到 30 000 个。对于数据集 DS5，独立 生成 10 组训练集及测试集，并将各方法在取不同 容量样本时的平均准确率及平均训练时间显示在 图 2 中。随着数据量增加时，为了能更准确地观 察各方法时间性能的量级，本文分别以 ( 为样本量) 为横坐标，以 (S 为运行时间，单 位为 s) 为纵坐标描述各方法的时间性能图，将始 的指数曲线转化为线性曲线，斜率代表运行时间 的指数量级，如图 2(b) 所示。 由图 2 可以得到如下观察： 图 2(a) 可知，在数据集合 DS5 上，随着训练数 据量的加大，各方法的泛化性能稳定增加。同时 SVC-SVM 和 SVC-CVM 方法优于独立求解单个 概念漂移问题的 TA-SVM 和 ITA-SVM 方法。由 于用普通 SVM 方法求解时需要先求解相应方法 的核矩阵，因此受硬件约束较大，当数据量较大 时，相应方法无法继续求解。而 SVC-CVM 方法 表 5 数据集 DS3 上各方法在不同噪音下的平均分类精度 Table 5 Classification accuracies on dataset DS3 with Different kernel 方法 Kernel 不同噪声的分类精度 2 4 6 8 10 TA-SVM Gauss 96.24+0.13 94.09+0.24 92.08+0.34 90.03+0.30 87.88+0.38 ITA-SVM 96.27+0.12 94.01+0.14 91.86+0.26 89.71+0.38 87.40+0.27 SVC-SVM 96.41+0.08 94.35+0.13 92.34+0.18 90.24+0.16 88.14+0.22 SVC-CVM 96.42+0.28 94.40+0.14 92.37+0.40 90.42+0.16 88.25+0.39 TA-SVM Linear 95.73+0.30 93.64+0.38 91.48+0.56 89.42+0.43 86.98+0.79 ITA-SVM 95.40+0.19 93.13+0.17 90.95+0.25 88.78+0.40 86.47+0.37 SVC-SVM 96.04+0.09 93.98+0.20 91.93+0.18 89.83+0.21 87.65+0.30 SVC-CVM 95.94+0.43 93.99+0.24 91.89+0.22 89.73+0.42 87.51+0.55 表 6 数据集 DS4 上各方法在不同噪音下的平均分类精度 Table 6 Classification accuracies on dataset DS4 with Different kernel 方法 Kernel 不同噪声的分类精度 2 4 6 8 10 TA-SVM Gauss 92.39+0.50 90.17+0.27 88.15+0.82 86.00+0.61 83.94+0.56 ITA-SVM 93.12+0.31 90.88+0.26 88.62+0.50 86.65+0.33 84.43+0.47 SVC-SVM 94.17+0.35 92.16+0.32 89.77+0.33 87.81+0.48 85.83+0.40 SVC-CVM 94.07+0.33 91.91+0.38 89.66+0.35 87.68+0.25 85.63+0.69 TA-SVM Linear 93.96+0.39 91.76+0.32 89.57+0.41 87.65+0.47 85.73+0.51 ITA-SVM 93.99+0.42 91.66+0.33 89.48+0.56 87.58+0.41 85.37+0.56 SVC-SVM 94.89+0.43 92.78+0.33 90.73+0.37 88.72+0.58 86.70+0.45 SVC-CVM 94.95+0.34 92.88+0.28 90.62+0.39 88.63+0.38 86.54+0.30 ·942· 智 能 系 统 学 报 第 13 卷
第6期 史荧中，等：基于核心向量机的多任务概念漂移数据快速分类 ·943· 采用核心集技术求解，相应的支持向量逐个添加 需时间与数据量之间呈现稳定的指数级关系，其 到核心集中，不需要预先计算核矩阵，因而能处 中SVC-CVM方法所表示的准直线的斜率明显小 理更大容量的数据，得到泛化能力更强的模型。 于其他方法，显示了SVC-CVM方法在时间效率 图2b)可知，在数据集DS上，求解各方法所 上远优于TA-SVM、TA-SVM与SVC-SVM方法. 100 4 99 97 TA-SVM --e-ITA-SVM TA-SVM 95 SVC-SVM -e-ITA-SVM SVC-CVM 0 SVC-SVM SVC-CVM 93 10 10 15 20 .5 3.0 3.5 4.0 4.5 数据量 数据量(Qg) (a)分类准确率 (b)求解时间 图2各方法在数据集DS5上的性能 Fig.2 Performance on DSs 在数据集DS。上，按相同的流程进行训练及 表7及表8中（其中一表示在本文实验环境中无 测试，并将各方法在不同容量样本上的平均准确 法得到相应结果)。 率和标准差、平均训练时间和标准差分别记录在 由表7及表8可以得到如下观察： 表7在数据集DS6上当不同数据量情况下各方法的平均分类准确率及标准差 Table 7 Classification accuracies with different dataset size of DS % 数据总量 TA-SVM ITA-SVM SVC-SVM SVC-CVM 500 97.40+0.34 97.65+0.27 98.30+0.16 98.36+0.18 1000 98.31+0.12 98.48+0.14 98.63+0.08 98.63+0.08 1500 98.53+0.09 98.61+0.11 98.69+0.06 98.67+0.07 3000 98.73+0.07 98.77+0.08 98.81+0.05 98.80+0.05 6000 98.81+0.05 98.85+0.06 98.89+0.03 98.88+0.04 10000 98.83+0.04 98.88+0.04 98.91+0.03 20000 98.93+0.02 30000 98.94+0.02 表8在数据集DS。上当不同数据量情况下各方法的平均训练时间及标准差 Table 8 Training time with different dataset size of DSc 数据总量 TA-SVM ITA-SVM SVC-SVM SVC-CVM 500 0.194±0.010 0.187±0.0125 0.470±0.011 3.587±1.512 1000 1.092±0.047 0.976±0.0737 7.177±0.587 7.485±3.379 1500 4.794±0.328 3.861±0.1787 27.958±1.457 15.481±7.193 3000 74.483±3.523 56.893±3.2578 225.199±11.843 36.439±14.452 6000 612.213±27.575 524.879±39.3632 1874.750±106.262 135.923±74.687 10000 2519.897±90.988 2192.208±64.0528 296.321±183.391 20000 753.458±287.496 30000 1266.967±453.862 1)从表7中可以看出，在数据集DS。上，随着 当，都优于独立求解单个概念漂移问题的TA-SVM 训练数据量的增加，各方法的分类性能逐渐增 与ITA-SVM方法。 高，其中SVC-SVM和SVC-CVM的分类性能相 2)从表8可以看出，在数据集DS6上，当数据
采用核心集技术求解，相应的支持向量逐个添加 到核心集中，不需要预先计算核矩阵，因而能处 理更大容量的数据，得到泛化能力更强的模型。 图 2(b) 可知，在数据集 DS5 上，求解各方法所 需时间与数据量之间呈现稳定的指数级关系，其 中 SVC-CVM 方法所表示的准直线的斜率明显小 于其他方法，显示了 SVC-CVM 方法在时间效率 上远优于 TA-SVM、ITA-SVM 与 SVC-SVM 方法。 在数据集 DS6 上，按相同的流程进行训练及 测试，并将各方法在不同容量样本上的平均准确 率和标准差、平均训练时间和标准差分别记录在 表 7 及表 8 中 (其中—表示在本文实验环境中无 法得到相应结果)。 由表 7 及表 8 可以得到如下观察： 1) 从表 7 中可以看出，在数据集 DS6 上，随着 训练数据量的增加，各方法的分类性能逐渐增 高，其中 SVC-SVM 和 SVC-CVM 的分类性能相 当，都优于独立求解单个概念漂移问题的 TA-SVM 与 ITA-SVM 方法。 2) 从表 8 可以看出，在数据集 DS6 上，当数据 0 5 10 15 20 ×103 93 94 95 96 97 98 99 100 (a) 分类准确率 准确率/% TA-SVM ITA-SVM SVC-SVM SVC-CVM 数据量 2.5 3.0 3.5 4.0 4.5 −1 0 1 2 3 4 (b) 求解时间 lgS/s TA-SVM ITA-SVM SVC-SVM SVC-CVM 数据量 (lgX) 图 2 各方法在数据集 DS5 上的性能 Fig. 2 Performance on DS5 表 7 在数据集 DS6 上当不同数据量情况下各方法的平均分类准确率及标准差 Table 7 Classification accuracies with different dataset size of DS6 % 数据总量 TA-SVM ITA-SVM SVC-SVM SVC-CVM 500 97.40+0.34 97.65+0.27 98.30+0.16 98.36+0.18 1 000 98.31+0.12 98.48+0.14 98.63+0.08 98.63+0.08 1 500 98.53+0.09 98.61+0.11 98.69+0.06 98.67+0.07 3 000 98.73+0.07 98.77+0.08 98.81+0.05 98.80+0.05 6 000 98.81+0.05 98.85+0.06 98.89+0.03 98.88+0.04 10 000 98.83+0.04 98.88+0.04 — 98.91+0.03 20 000 — — — 98.93+0.02 30 000 — — — 98.94+0.02 表 8 在数据集 DS6 上当不同数据量情况下各方法的平均训练时间及标准差 Table 8 Training time with different dataset size of DS6 s 数据总量 TA-SVM ITA-SVM SVC-SVM SVC-CVM 500 0.194± 0.010 0.187± 0.012 5 0.470± 0.011 3.587± 1.512 1 000 1.092± 0.047 0.976± 0.073 7 7.177± 0.587 7.485± 3.379 1 500 4.794± 0.328 3.861± 0.178 7 27.958± 1.457 15.481± 7.193 3 000 74.483± 3.523 56.893± 3.257 8 225.199± 11.843 36.439± 14.452 6 000 612.213±27.575 524.879±39.363 2 1 874.750±106.262 135.923± 74.687 10 000 2 519.897±90.988 2 192.208±64.052 8 — 296.321±183.391 20 000 — — — 753.458±287.496 30 000 — — — 1 266.967±453.862 第 6 期 史荧中，等：基于核心向量机的多任务概念漂移数据快速分类 ·943·
·944· 智能系统学报 第13卷 量较小时，SVC-CVM方法的求解时间上并不具 bution[C]//Proceedings of the Fifth Annual Workshop on 有优势。当数据量的逐渐增加时，SVC-CVM Computational Learning Theory.Pittsburgh,Pennsylvania, 方法求解时间的变化很缓慢，明显优于用普通二 USA,1992:243-252 次规划方式进行求解。 [7]KLINKENBERG R,JOACHIMS T.Detecting concept 在数据集DS,和DS6上的实验可知，当数据 drift with support vector machines[C]//Proceedings of the Seventeenth International Conference on Machine Learn- 量不大时，SVC-SVM方法和SVC-CVM方法都优 ing.San Francisco,CA.USA.2000:487-494 于独立求解的方法，且两者的分类性能相当。当 [8]RUANO-ORDaS D.FDEZ-RIVEROLA F.MeNDEZAB J 数据量很大时，只有SVC-CVM方法能处理较大 R.Concept drift in e-mail datasets:an empirical study with 规模数据集，且在算法时间性能上保持近线性时 practical implications[J].Information sciences,2018,428: 间复杂度，因而具有较强的实用性。 120-135 [9]C LANQUILLON.Enhancing test classification to im- 4结束语 prove information filtering[D].Magdeburg,Germany:Fac- ulty Comp Sci,Univ.Magdeburg,2001. 本文提出了适用于对概念漂移大规模数据集 [10]文益民，强保华，范志刚.概念漂移数据流分类研究综 快速求解的多任务核心向量机方法SVC-CVM。 述U.智能系统学报，2013,8(2)：95-104 由于采用共享矢量链技术协同求解多个概念漂移 WEN Yimin,QIANG Baohua,FAN Zhigang.A survey of 问题，SVC-CVM方法在分类精度上等价于SVC the classification of data streams with concept drift[J]. SVM方法，明显优于独立求解单个概念漂移问题 CAAI transactions on intelligent systems,2013,8(2): 的TA-SVM及ITA-SVM方法，且SVC-CVM算法 95-104. 在面对多个概念漂移大数集时仍然能够进行快速 [11]ALIPPI C,ROVERI M.Just-in-time adaptive classifiers- 建模决策。当然SVC-CVM方法仍需要进一步研 part II:designing the classifier[J].IEEE transactions on neural networks,2008,1912):2053-2064 究，特别是多任务概念漂移大规模数据集的回归 [12]EVGENIOU T,PONTIL M.Regularized multi--task 问题；多任务概念漂移大规模数据集的单类问 learning[C]//Proceedings of the 10th ACM SIGKDD In- 题，将是更有意义的挑战。 ternational Conference on Knowledge Discovery and 参考文献： Data Mining.Seattle,WA.USA,2004:109-117. [13]GRINBLAT G L,UZAL L C,CECCATTO H A,et al. [1]HELMBOLD D P,LONG P M.Tracking drifting con- Solving nonstationary classification problems with cepts by minimizing disagreements[J].Machine learning. coupled support vector machines[J].IEEE transactions on 1994,141):27-45 neural networks,2011,22(1):37-51 [2]BARTLETT P L,BEN-DAVID S,KULKARNI S R. [14]SHI Yingzhong,CHUNG F L K,WANG Shitong.An im- Learning changing concepts by exploiting the structure of proved ta-svm method without matrix inversion and its change[J].Machine learning,2000,41(2):153-174 fast implementation for nonstationary datasets[J].IEEE [3]ZHOU Xiangyu,WANG Wenjun,YU Long.Traffic flow transactions on neural networks and learning systems, analysis and prediction based on GPS data of floating 2015,26(9:2005-2018. cars[Cl/Proceedings of the 2012 International Conference [15]史荧中，邓赵红，钱鹏江，等.基于共享矢量链的多任务 on Information Technology and Software Engineering. 概念漂移分类方法).控制与决策，2018,33(7)：1215- [S.1],2013:497-508. 1222 [4]KUWATA S,INABA Y,YOKOGAWA M,et al.Stream SHI Yingzhong,DENG Zhaohong,QIAN Pengjiang,et data analysis application for customer behavior with com- al.Multi-task concept drift classification method based on plex event processing[C]//IEICE Technical Committee shared vector chain[J].Control and Decision,2018,33(7) Submission System Conference Paper's Information.[S.1.], 1215-1222 2010,110(113-18 [16]PLATT J.Fast training of support vector machines using [5]VERGARA A.VEMBU S,AYHAN T,et al.Chemical gas sequential minimal optimization[C]//Advances in Kernel sensor drift compensation using classifier ensembles[J]. Methods-Support Vector Learning.Cambridge,MA:MIT Sensors and actuators B:chemical,2012,166-167: Press,.2000:185-208. 320-329 [17]TSANG I W,KWOK J T,CHEUNG P M.Core vector [6]BARTLETT P L.Learning with a slowly changing distri- machines:fast SVM training on very large data sets[J]
量较小时，SVC-CVM 方法的求解时间上并不具 有优势。当数据量的逐渐增加时， SVC-CVM 方法求解时间的变化很缓慢，明显优于用普通二 次规划方式进行求解。 在数据集 DS5 和 DS6 上的实验可知，当数据 量不大时，SVC-SVM 方法和 SVC-CVM 方法都优 于独立求解的方法，且两者的分类性能相当。当 数据量很大时，只有 SVC-CVM 方法能处理较大 规模数据集，且在算法时间性能上保持近线性时 间复杂度，因而具有较强的实用性。 4 结束语 本文提出了适用于对概念漂移大规模数据集 快速求解的多任务核心向量机方法 SVC-CVM。 由于采用共享矢量链技术协同求解多个概念漂移 问题，SVC-CVM 方法在分类精度上等价于 SVCSVM 方法，明显优于独立求解单个概念漂移问题 的 TA-SVM 及 ITA-SVM 方法，且 SVC-CVM 算法 在面对多个概念漂移大数集时仍然能够进行快速 建模决策。当然 SVC-CVM 方法仍需要进一步研 究，特别是多任务概念漂移大规模数据集的回归 问题；多任务概念漂移大规模数据集的单类问 题，将是更有意义的挑战。 参考文献： HELMBOLD D P, LONG P M. Tracking drifting concepts by minimizing disagreements[J]. Machine learning, 1994, 14(1): 27–45. [1] BARTLETT P L, BEN-DAVID S, KULKARNI S R. Learning changing concepts by exploiting the structure of change[J]. Machine learning, 2000, 41(2): 153–174. [2] ZHOU Xiangyu, WANG Wenjun, YU Long. Traffic flow analysis and prediction based on GPS data of floating cars[C]//Proceedings of the 2012 International Conference on Information Technology and Software Engineering. [S.l.], 2013: 497–508. [3] KUWATA S, INABA Y, YOKOGAWA M, et al. Stream data analysis application for customer behavior with complex event processing[C]//IEICE Technical Committee Submission System Conference Paper's Information. [S.l.], 2010, 110(1): 13–18. [4] VERGARA A, VEMBU S, AYHAN T, et al. Chemical gas sensor drift compensation using classifier ensembles[J]. Sensors and actuators B: chemical, 2012, 166-167: 320–329. [5] [6] BARTLETT P L. Learning with a slowly changing distribution[C]//Proceedings of the Fifth Annual Workshop on Computational Learning Theory. Pittsburgh, Pennsylvania, USA, 1992: 243–252. KLINKENBERG R, JOACHIMS T. Detecting concept drift with support vector machines[C]//Proceedings of the Seventeenth International Conference on Machine Learning. San Francisco, CA, USA, 2000: 487–494. [7] RUANO-ORDáS D, FDEZ-RIVEROLA F, MéNDEZAB J R. Concept drift in e-mail datasets: an empirical study with practical implications[J]. Information sciences, 2018, 428: 120–135. [8] C LANQUILLON. Enhancing test classification to improve information filtering[D]. Magdeburg, Germany: Faculty Comp Sci, Univ. Magdeburg, 2001. [9] 文益民, 强保华, 范志刚. 概念漂移数据流分类研究综 述[J]. 智能系统学报, 2013, 8(2): 95–104. WEN Yimin, QIANG Baohua, FAN Zhigang. A survey of the classification of data streams with concept drift[J]. CAAI transactions on intelligent systems, 2013, 8(2): 95–104. [10] ALIPPI C, ROVERI M. Just-in-time adaptive classifierspart II: designing the classifier[J]. IEEE transactions on neural networks, 2008, 19(12): 2053–2064. [11] EVGENIOU T, PONTIL M. Regularized multi--task learning[C]//Proceedings of the 10th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Seattle, WA, USA, 2004: 109–117. [12] GRINBLAT G L, UZAL L C, CECCATTO H A, et al. Solving nonstationary classification problems with coupled support vector machines[J]. IEEE transactions on neural networks, 2011, 22(1): 37–51. [13] SHI Yingzhong, CHUNG F L K, WANG Shitong. An improved ta-svm method without matrix inversion and its fast implementation for nonstationary datasets[J]. IEEE transactions on neural networks and learning systems, 2015, 26(9): 2005–2018. [14] 史荧中, 邓赵红, 钱鹏江,等. 基于共享矢量链的多任务 概念漂移分类方法[J]. 控制与决策, 2018, 33(7): 1215- 1222. SHI Yingzhong, DENG Zhaohong, QIAN Pengjiang, et al. Multi-task concept drift classification method based on shared vector chain[J]. Control and Decision, 2018, 33(7): 1215-1222. [15] PLATT J. Fast training of support vector machines using sequential minimal optimization[C]//Advances in Kernel Methods-Support Vector Learning. Cambridge, MA: MIT Press, 2000: 185–208. [16] TSANG I W, KWOK J T, CHEUNG P M. Core vector machines: fast SVM training on very large data sets[J]. [17] ·944· 智 能 系 统 学 报 第 13 卷
