基于多源迁移学习的数据流分类研究

周 胜， 刘三民

(安徽工程大学计算机与信息学院， 安徽 芜湖 241000)

引 言

随着大数据技术的不断发展，数据流挖掘在许多领域得到了广泛应用，如天气预报、金融预测、电子商务等。在这些应用领域中，每时每刻都有大量的数据产生，因此需要对这些数据进行实时分类，从而在这些不断产生的数据流中挖掘有价值的信息。传统的数据流分类方法需要大量的标签样本训练分类模型，这种方法实时性低，无法有效解决数据流中的概念漂移和噪声问题。

目前，迁移学习受到了广泛的关注和研究。迁移学习是指运用已存有的知识对不同但相关领域问题进行求解的一种新的机器学习方法[1]，能够解决目标域标注样本不足的问题。迁移学习根据源领域个数可分为单源迁移和多源迁移。单源迁移学习使用一个与目标领域较为相似的源领域进行知识迁移，如Dai等[2]建立一种基于样本迁移的TrAdaBoost迁移学习算法，通过Boosting方法增加有效数据权重的同时降低无效数据的权重，解决源领域和目标域数据不匹配的问题。文献[3]为了显著地减少域分布之间的距离，提出一种降维框架。Zhao等[4-5]设计基于集成学习策略的方案来解决同构域上的单源迁移学习问题，实验结果显示该方法具有较高的准确率。当前绝大多数单源迁移学习算法都有先决条件，即是必须获得与目标领域较为相似的源领域才能进行知识迁移，但是在现实环境中，获得与目标领域较为相似的源领域比较困难。针对单源迁移学习方法的不足，众多国内外学者提出使用多个源领域进行迁移的多源迁移学习算法。Ge等[6]建立一种多源迁移学习算法OMS-TL，根据二部图实现对目标领域样本的预测，通过对数据样本进行重用来进行迁移学习。针对概念漂移数据流分类中的概念重现问题，一种重现概念漂移数据流分类算法RC-OTL被提出[7]，算法根据领域相似度挑选最适合的源领域分类器，实验结果证明该方法能够有效克服“负迁移”。文献[8]构建一种多源迭代自适应算法MSIDA，根据贪婪思想实现最佳源领域的选择，同时通过创建额外的伪标记实例解决样本标注问题。文献[9]设计算法OTLMS，提出将集成源领域分类器和目标领域分类器组合在一起构建预测分类器的方案，解决与目标学习任务无关的噪声源数据影响分类精度的问题。文献[10]通过将目标特征空间分成源领域的同构和异构两个部分，将基分类器加权组合获得多个源领域分类器，并将多个源领域分类器组合成一个集成模型来解决多源异构迁移学习问题。Yan等[11]构建算法OHTWC，通过计算异构域中同现数据的异构相似性，解决异构域上的数据流分类问题。文献[12]通过求解每个源领域对应的权值向量，并用对应的权值向量来表示源领域和目标领域之间的相似度，显著地提高迁移学习效率以及分类性能。文献[13]设计一种基于自适应弃权策略的数据流分类方法，该方法通过将每个源领域分类器对新到样本的确定性与给定阈值进行比较，从而选择合适的源领域分类器参与集成决策，该方法能够对源领域分类器集成的多样性进行选择性控制。文献[14]通过调整每个源领域分类器对应的权重，同时用目标领域分类器更换权重最大的源领域分类器，该方法能够在出现概念漂移后快速地恢复集成分类器的分类准确率，从而改善集成分类器的分类性能。

综上可知，数据流分类采用多源迁移学习技术具有明显优势，而在迁移学习过程中如何从多个源领域分类器中挑选最合适的源领域分类器，是本文关注点所在。本文基于互近邻的动态分类器选择方法设计出一种局部分类精度计算方案能够有效地挑选出最合适的源领域分类器，从而有效解决数据流中的概念漂移和噪声问题。

1 基本概念

K近邻算法[15]通过计算新到样本xt和样本集合中训练样本之间的距离，挑选与新到样本xt距离最近的K个样本构造新到样本xt的邻域，然后基于邻域的类别信息，根据投票的准则对新到样本进行分类。

定义1K-近邻指与新到样本xt距离最近的K个样本集合，记Nk(xt)。

然而，K近邻算法仅通过度量样本之间的距离(忽略了样本之间是否互为近邻)来预测新到样本的类别标签，会导致伪近邻现象的产生。伪近邻现象如图1所示，如N3(x1)={x2,x3,x4}表示x1的3个近邻，N3(x6)={x7,x8,x9}表示x6的3个近邻，N3(x7)={x6,x8,x9}表示x7的3个近邻，N3(x5)={x1,x6,x7} 表示x5的3个近邻，但x5却不在x1、x6、x7的近邻中，原因是x1、x6、x7实际上距离x5很远。

图1 样本x5的3-近邻分布图

定义2K-互近邻指互相作为对方的K近邻，令Nk(xt)表示xt的K个近邻，Nk(xi)表示xi的K个近邻，Mk(xt)表示xt的K-互近邻，可记为Mk(xt)={xi|xi∈Nk(xt)∩xt∈Nk(xi)}。

用互近邻进行数据流分类可以防止伪近邻现象产生，提高分类的准确率，这也是本文的出发点之一。

2 局部分类精度

根据聚类的思想，相邻样本间的样本相似度较大，如果基分类器对新到样本周围区域内的数据样本分类准确率较高，那么基分类器对新到样本的类别预测也会比较准确。基于此，本文提出一种局部分类精度计算方法，利用该方法来挑选最合适的源领域分类器。

基于局部分类精度[16]的动态分类器选择方法，假设基分类器在新到样本周围区域的分类精度不同，从而通过局部分类精度方法挑选局部分类精度最高的基分类器，并用局部分类精度最高的基分类器的输出结果作为分类器集合的输出。局部分类精度计算方法可以分为两类：基于类别无关的方法和基于类别相关的方法，本文提出的局部分类精度计算方法是基于类别相关的方法，其公式如下：

(1)

其中，K为邻域的样本个数，xt为目标领域数据块中的样本，Mk(xt)为目标领域数据块中每个样本的互近邻样本集合，yi为目标领域数据块中每个样本的互近邻样本的真实类别，fsj(Mk(xt))为源领域分类器对目标领域数据块中每个样本的互近邻样本的预测类别，dis(Mk(xt),xt)为目标领域数据块中每个样本与目标领域数据块中每个样本的互近邻样本之间的距离，本文采用的是欧式距离。I(x)为示性函数，其定义如下：

(2)

若某源领域分类器能够正确预测目标领域数据块中每个样本的互近邻样本的类别，那么示性函数的值为1，否则，示性函数的值为0。

在目标领域数据块中挑选与目标领域数据块中每个样本互为近邻的K个样本构造其邻域，从而将训练得到的多源领域分类器在目标领域数据块中每个样本的K-互近邻样本集合Mk(xt)计算局部分类精度LCA。

3 算法描述

在上述互近邻思想和局部分类精度计算方法基础上，给出基于互近邻的多源迁移学习算法(Multi-source Transfer Learning based on Mutual Nearest Neighbor，MNNTL)描述。算法利用互近邻思想求得目标领域数据块中每个样本的互近邻样本集合Mk(xt)，然后计算各源领域分类器对目标领域数据块中每个样本的互近邻样本集合Mk(xt)的局部分类精度，最后将局部分类精度最高的源领域分类器fs与目标领域分类器ft加权集成对目标领域数据块进行分类，并更新分类器对应的权重以及目标领域分类器。

MNNTL算法的输入包括目标域数据流DS、源领域分类器集合CS、近邻样本数量K；输出为集成分类模型对目标领域数据块的分类准确率。其详细过程为：

step 1参数初始化K，缓存两个规模大小相等的数据块，并分别在数据块上训练源领域分类器。

step 2Forj=1,2,...,20，对后续数据块Dj依次循环处理。

step 3基于目标领域数据块Dj构建目标领域分类器ftj。

step 4计算目标领域数据块Dj中样本之间的距离。

step 5在目标领域数据块Dj中求每个样本的K-近邻样本集合Nk(xt)。

step 6在每个样本的K-近邻样本集合Nk(xt)中求每个样本的K-互近邻样本集合Mk(xt)。

step 7计算各源领域分类器对每个样本的K-互近邻样本集合Mk(xt)的局部分类精度LCAj：

step 8将局部分类精度最高的源领域分类器fs与目标领域分类器ftj加权组合成分类器f对目标领域数据块Dj进行分类：

其中：xt为目标领域样本；ωs和ωt分别为源领域分类器和目标领域分类器对应的权值向量；α1,t和α2,t分别为源领域分类器和目标领域分类器对应的权重，初始化

为映射函数[4]。

step 9更新分类器权重α1,t和α2,t：

其中：st(u)=exp{-ηl*(Π(uTxt),Π(yt))}，η=0.5，∀u∈Rm；分类器损失函数l*(z,y)=(z-y)2；xt为目标领域样本，yt为目标领域样本的真实类别。

step 10更新目标领域分类器ftj。

step 11End For.

算法过程中：step 1表示算法初始化，初始化参数K以及初始化源领域分类器；step 3表示基于目标领域数据块构建目标领域分类器；step 4～step 6表示求目标领域数据块中每个样本的互近邻样本集合；step 7表示计算各源领域分类器对目标领域数据块中每个样本的互近邻样本集合的局部分类精度；step 8表示选取局部分类精度最高的源领域分类器与目标领域分类器加权集成对目标领域数据块进行分类；step 9表示分类器权重的更新；step 10表示目标领域分类器的更新。这里，step 8使用的分类方法和step 9使用的分类器权重调整方案与文献[4]提出的分类方法和分类器权重调整方案类似。

4 仿真实验与结果分析

4.1 仿真数据集

4.2 实验方案及结果分析

为验证研究目标，本文把所提方法与现有文献采用基于K-近邻思想计算局部分类精度的多源在线迁移学习方法(Multi-source Online Transfer Learning based on K-nearest Neighbor，KNNOTL)进行对比。实验采用Bayes分类器作为基分类器，采用批处理模式训练生成，其中源领域数据块大小为5000，源领域数据块个数为2，训练2个源领域分类器，同时基于目标域数据流DS形成20个数据块，数据块大小设为500，求得各源领域分类器对目标领域数据块中每个样本的互近邻样本集合Mk(xt)的局部分类精度，将局部分类精度最高的源领域分类器fs与目标领域分类器ft加权集成对目标领域数据块进行分类。

实验1验证近邻样本数量参数影响

为验证近邻样本数量对算法的影响，本文选择三个近邻样本数值通过平均准确率和标准差统计量来说明它们之间的关系，见表1。

表1 MNNTL与近邻样本数量间的关系

从表1可以看出，当近邻样本数值为7时，此时平均准确率和标准差统计量是最好的。当近邻样本数值较大时，每次迭代求得的近邻样本与目标领域数据块中的样本差异性较大，而近邻样本数值较小时，会使得计算出来的各源领域分类器对目标领域数据块中每个样本的互近邻样本集合的局部分类精度差异性较小。显然，近邻样本数值较大或较小都会影响局部分类精度的计算，导致无法挑选出最合适的源领域分类器。

实验2验证MNNTL分类能力

无噪声环境下的实验现象如图2所示。在无噪声的情况下，随着数据块数量的增加，两种方法的分类准确率都在不断地提升。这是由于两种方法在挑选最优源领域分类器的同时，在对目标领域样本完成分类后，都对目标领域分类器进行了更新，因此能够更快地适应新到概念。同时相对于KNNOTL，MNNTL的分类准确率没有明显的提高，这是由于在无噪声的情况下，MNNTL使用互近邻思想求得的互近邻样本集合与KNNOTL使用K近邻思想求得的近邻样本集合几乎相等，导致大多数情况下挑选出来的源领域分类器相同，因此分类准确率差别不大。

图2 数据集D1实验结果

噪声环境下的实验现象如图3与图4所示。从图3和图4可以看出，在分类初期MNNTL和KNNOTL的分类准确率均较低，这是因为在分类初期能获得的目标领域数据块较少。在有噪声的情况下，不仅MNNTL的分类准确率要优于KNNOTL，尤其在分类的初始阶段优势明显，而且随着数据块的增加，MNNTL分类准确率比KNNOTL增长的幅度要快，这是由于相对于KNNOTL只使用K近邻思想求近邻样本集合，MNNTL使用了互近邻思想求互近邻样本集合，其策略消除了噪声数据的影响，因此能够更快地适应概念漂移，使分类模型面对概念漂移具有更好的泛化能力。

图3 数据集D2实验结果

图4 数据集D3实验结果

综上分析可知，MNNTL数据流分类方法是可行的，分类准确率优于基于K近邻的数据流分类方法。这是由于MNNTL方法在目标领域数据块中每个样本的K近邻样本集合的基础上求得互近邻样本集合，避免了伪近邻现象的产生，即排除了近邻样本集合中存在噪声数据的可能，提高了分类模型的预测精度，同时MNNTL方法是基于类别相关的方法求局部分类精度，能够从近邻样本中挑选出与目标领域数据块中每个样本类别相同的样本，能够更准确地求得各源领域分类器对目标领域数据块中每个样本的互近邻样本集合的局部分类精度，从而更准确地挑选出最合适的源领域分类器。两种方法的平均准确率与标准差统计见表2。

表2 平均准确率和标准差统计量

分析表2中的统计数据可知，MNNTL算法明显优于KNNOTL算法，平均准确率约高出9%，在噪声环境下仍然具有较高的准确率，说明MNNTL算法能够有效地处理数据流中的噪声，能够更快地适应概念漂移现象。随着噪声数据的增加，MNNTL方法的分类准确率下降程度明显小于KNNOTL方法，说明MNNTL方法面对噪声数据流时具有更好的稳定性和更强的抗噪性。同时MNNTL方法的标准差明显大于KNNOTL方法，说明MNNTL方法的分类准确率比KNNOTL方法增长的幅度要快，MNNTL方法能够更快地适应噪声数据流。这是因为MNNTL算法利用互近邻思想求得目标领域数据块中每个样本的互近邻样本集合，能够有效避免伪近邻现象的产生，使分类模型保持较高的分类精度以及较好的稳定性。综上所述，基于互近邻的多源迁移学习方法是可行的，能够从K近邻样本集合中进一步挑选出互近邻样本集合，能够有效解决数据流中的概念漂移和噪声问题。

5 结束语

本文结合互近邻思想和局部分类精度计算方法，提出了一种新的多源迁移数据流分类学习方法。该方法能够有效利用互近邻思想，从目标领域数据块中挑选合适的样本作为目标领域数据块中每个样本的真近邻，同时构建出局部分类精度计算方法从源领域分类器集合中挑选最合适的源领域分类器与目标领域分类器加权集成。实验结果表明所设计的方案能够排除近邻样本集合中存在噪声数据的可能，有效消除噪声数据的影响。本文研究表明，迁移学习方法能够解决数据流中概念变化和样本标注的难题。