·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 sup￾ported 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 方法的快速算法。所提 SVC￾CVM 方法具有以下特点： 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 卷