【人工智能基础】一种多样性和精度加权的数据流集成分类算法

团购合买资源类别：文库，文档格式：PDF，文档页数：7，文件大小：0.98MB

第14卷第1期智能系统学报 Vol.14 No.I 2019年1月 CAAI Transactions on Intelligent Systems Jan.2019 D0:10.11992/tis.201806021 网络出版地址：http:/kns.cnki.net/kcms/detail/23.1538.TP.20180927.1309.008.html 一种多样性和精度加权的数据流集成分类算法张本才，王志海，孙艳歌2 (1.北京交通大学计算机与信息技术学院，北京100044,2.信阳师范学院计算机与信息技术学院，河南信阳 464000) 摘要：为了克服数据流中概念漂移对分类的影响，提出了一种基于多样性和精度加权的集成分类方法( versity and accuracy weighting ensemble classification algorithm,DAWE),该方法与已有的其他集成方法不同的地方在于，DAWE同时考虑了多样性和精度这两种度量标准，将分类器在最新数据块上的精度及其在集成分类器中的多样性进行线性加权，以此来衡量一个分类器对于当前集成分类器的价值，并将价值度量用于基分类器替换策略。提出的DAWE算法与MOA中最新算法分别在真实数据和人工合成数据上进行了对比实验，实验表明. 提出的方法是有效的，在所有数据集上的平均精度优于其他算法，该方法能有效处理数据流挖掘中的概念漂移问题。关键词：数据流；概念漂移：多样性；精度；集成学习；数据块；价值度量；MOA 中图分类号：TP391文献标志码：A文章编号：1673-4785(2019)01-0179-07 中文引用格式：张本才，王志海，孙艳歌.一种多样性和精度加权的数据流集成分类算法.智能系统学报，2019,14(1)： 179-185. 英文引用格式：ZHANG Bencai,,WANG Zhihai,.SUN Yan'ge.An ensemble classification algorithm based on diversity and accur. acy weighting for data streamsJ CAAI transactions on intelligent systems,2019,14(1):179-185. An ensemble classification algorithm based on diversity and accuracy weighting for data streams ZHANG Bencai',WANG Zhihai',SUN Yan'ge12 (1.School of Computer and Information Technology,Beijing Jiaotong University,Beijing 100044,China;2.School of Computer and Information Technology,Xinyang Normal University,Xinyang 464000,China) Abstract:To overcome the effect of concept drift on data stream classification,we propose an ensemble classification algorithm based on diversity and accuracy weighting named DAWE.The difference between DAWE and other existing ensemble methods is that DAWE considers both diversity and accuracy.The classifier's accuracy on the new data chunk and its diversity in the ensemble were linearly weighted to measure the value of the current ensemble classifier and the measured value was applied to the substitute strategy of the base classifier.The DAWE algorithm proposed in this pa- per was experimentally compared with the latest algorithms in massive online analysis(MOA),using both synthetic and real-world datasets.Experiments showed that the method proposed in this paper was effective and the average overall accuracy of the data sets was superior to that of other algorithms.Overall,this method can effectively manage concept drift in data stream mining. Keywords:data stream;concept drift;diversity;accuracy;ensemble learning;data chunk;value measurement;MOA 近年来，随着各种网络，比如社交网络、传感速度源源不断地产生大量数据流。与此同时，如器网络的不断发展，越来越多的应用在以极快的何快速地从大量数据流中生成有用的模型或者提收稿日期：2018-06-07.网络出版日期：2018-09-29 取有用信息吸引了大量研究者。基金项目：国家自然科学基金项目(61672086,61702030,61771058)：北京市自然科学基金项目(4182052). 数据流分类是传统的有监督机器学习的一种通信作者：王志海.E-mail:zhhwang@bjtu.edu.cn.. 变体，传统的有监督机器学习都是针对于由特征

DOI: 10.11992/tis.201806021 网络出版地址: http://kns.cnki.net/kcms/detail/23.1538.TP.20180927.1309.008.html 一种多样性和精度加权的数据流集成分类算法张本才1 ，王志海1 ，孙艳歌1,2 （1. 北京交通大学计算机与信息技术学院，北京 100044; 2. 信阳师范学院计算机与信息技术学院，河南信阳 464000）摘要：为了克服数据流中概念漂移对分类的影响，提出了一种基于多样性和精度加权的集成分类方法 (diversity and accuracy weighting ensemble classification algorithm, DAWE)，该方法与已有的其他集成方法不同的地方在于，DAWE 同时考虑了多样性和精度这两种度量标准，将分类器在最新数据块上的精度及其在集成分类器中的多样性进行线性加权，以此来衡量一个分类器对于当前集成分类器的价值，并将价值度量用于基分类器替换策略。提出的 DAWE 算法与 MOA 中最新算法分别在真实数据和人工合成数据上进行了对比实验，实验表明，提出的方法是有效的，在所有数据集上的平均精度优于其他算法，该方法能有效处理数据流挖掘中的概念漂移问题。关键词：数据流；概念漂移；多样性；精度；集成学习；数据块；价值度量；MOA 中图分类号：TP391 文献标志码：A 文章编号：1673−4785(2019)01−0179−07 中文引用格式：张本才, 王志海, 孙艳歌. 一种多样性和精度加权的数据流集成分类算法[J]. 智能系统学报, 2019, 14(1): 179–185. 英文引用格式：ZHANG Bencai, WANG Zhihai, SUN Yan’ge. An ensemble classification algorithm based on diversity and accuracy weighting for data streams[J]. CAAI transactions on intelligent systems, 2019, 14(1): 179–185. An ensemble classification algorithm based on diversity and accuracy weighting for data streams ZHANG Bencai1 ，WANG Zhihai1 ，SUN Yan’ge1,2 (1. School of Computer and Information Technology, Beijing Jiaotong University, Beijing 100044, China; 2. School of Computer and Information Technology, Xinyang Normal University, Xinyang 464000, China) Abstract: To overcome the effect of concept drift on data stream classification, we propose an ensemble classification algorithm based on diversity and accuracy weighting named DAWE. The difference between DAWE and other existing ensemble methods is that DAWE considers both diversity and accuracy. The classifier’s accuracy on the new data chunk and its diversity in the ensemble were linearly weighted to measure the value of the current ensemble classifier and the measured value was applied to the substitute strategy of the base classifier. The DAWE algorithm proposed in this paper was experimentally compared with the latest algorithms in massive online analysis (MOA), using both synthetic and real-world datasets. Experiments showed that the method proposed in this paper was effective and the average overall accuracy of the data sets was superior to that of other algorithms. Overall, this method can effectively manage concept drift in data stream mining. Keywords: data stream; concept drift; diversity; accuracy; ensemble learning; data chunk; value measurement; MOA 近年来，随着各种网络，比如社交网络、传感器网络的不断发展，越来越多的应用在以极快的速度源源不断地产生大量数据流。与此同时，如何快速地从大量数据流中生成有用的模型或者提取有用信息吸引了大量研究者。数据流分类是传统的有监督机器学习的一种变体，传统的有监督机器学习都是针对于由特征收稿日期：2018−06−07. 网络出版日期：2018−09−29. 基金项目：国家自然科学基金项目 (61672086, 61702030, 61771058)；北京市自然科学基金项目 (4182052). 通信作者：王志海. E-mail：zhhwang@bjtu.edu.cn. 第 14 卷第 1 期智能系统学报 Vol.14 No.1 2019 年 1 月 CAAI Transactions on Intelligent Systems Jan. 2019

·180· 智能系统学报第14卷向量表示的未标记实例的值的预测。与传统的分真的出现概念漂移；还有一些方法不断检测数据类学习的不同之处在于：传统机器学习方法根据流中是否出现概念漂移，如果出现概念漂移则对一个静态的数据集合建立模型，而在数据流环境模型进行相应的调整。Brzezinski等提出了一种下，实例是不断到来的，只能根据部分实例建立可以对多种概念漂移反应同样好的分类算法，称分类模型。因此，数据流分类器必须准备好处理为精度更新集成(accuracy updated ensemble, 大量的、快速输人的实例，而且每个实例只能在 AUE2)。该方法根据基分类器在当前数据块上的短时间内被处理或存储一次。目前，数据流学精度计算其权重并用于基分类器替换。Pietruczuk 习还面临很多挑战，这些挑战包括概念漂移、时等提出了一种可以动态扩展集成分类器大小的间依赖关系、新类、特征漂移、类不平衡以及时间集成分类算法，其主张一个新的基分类器是否被和内存受限等。本文主要解决的是概念漂移问题。添加进集成分类器中取决于这个添加操作是否不解决概念漂移问题目前最流行的方法是集成光提高了当前数据的精度而且也会提高整个数据学习，而现有的多数数据流集成分类方法通常只流的分类精度。除了精度这种度量方式之外，多考虑精度或者只考虑多样性。这两种方法在思路样性对于集成学习来说也是一个十分有意义的度上的区别就是：前者重视基分类器在最新数据上量。Sun等认为，应该鼓励模型之间的差异性，的表现，认为新数据最符合目前这个阶段的数据即多样性(diversity)提出了一种基于多样性和迁分布；后者考虑在以后阶段会出现各种各样的数移的集成学习方法(diversity and transfer based en- 据分布，即各种各样的“概念”。使用多样性的基 semble learning,DTEL)来处理带有概念漂移的数分类器能使集成分类器在各种“概念”下都能取得据流分类问题。该方法使用Q统计量作为差异不错的性能。但是，多样性和精度这两个方面对性度量，以基分类器之间的分类差异性作为标准数据流分类来说都是重要的，所以如何综合这两来决定以前的基分类器是否保留。Rijn等提出个方面来提出一个更加有效的方法，是本文主要了一种结合异构模型的集成技术用于数据流分类，对集成分类器中不同基分类器的投票进行加的工作。权，重视分类器之间的差异性。也有一些研究者本文的主要贡献如下：1)提出了一种线性加认为分类精度和分类多样性二者可以结合。Chandra 权方式来计算分类器权重，将分类器在最新数据等证明了一个泛化性能好的集成分类器中，基块上的精度以及该分类器在集成分类器中的多样分类器需要同时具备多样性和精确性，并且提出性这两种度量分类器价值的标准以一种线性加权多样性和精度之间有一个折衷(trade-ofm。Li等图的方式融合成一个标准，以此作为衡量一个分类提出了将一种结合多样性和精度的度量标准应用器对于当前集成分类器价值大小的依据：2)使用到遗传算法中，并通过实验结果表明了该度量方一种基于价值度量的集成分类器更新策略来根据法的有效性。最新数据对集成分类器进行更新，将对精度和多样性线性加权得到的权重作为基分类器价值的度 2加权多样性和精度的集成方法量。当有新的分类器到来时，价值最低的基分类在正式介绍之前，先对本节所使用的符号作器将会被新建立的分类器替换。简单说明。令数据流S是由无数个大小相等的数 1相关工作据块B组成的，其中每个数据块是由数量相等的实例={x,y}构成。集成分类器E是由n个基分由于数据流的动态性，其学习过程存在很多类器C构成。问题，比如，在处理大规模数据流时，经常会发生 2.1分类器的精度和多样性度量数据分布变化的情况，这种情况被称为“概念漂 1)精度度量移”(concept drift),概念漂移的出现打破了机器精度的度量通常通过计算均方误差(MSE)得学习中一个假设前提，即数据是独立同分布的。到，一个分类器C,在一个数据块B,的均方误差相反，也正是因为数据流不符合这个假设前提， MSEg可以用式(1)表示：才吸引了无数研究者。 1 MSE= 自概念漂移问题被发现以来，研究者们提出 E之1-pU)= (1) 了大量的方法和策略用于处理概念漂移问题，其使用MSE,表示对当前数据所有可能的类别中有的方法假定概念漂移存在，在学习过程中不进行随机预测所得到的均方误差，以此来反映当断根据当前数据对模型进行调整，而不关心是否前数据的类分布，计算公式为

向量表示的未标记实例的值的预测。与传统的分类学习的不同之处在于：传统机器学习方法根据一个静态的数据集合建立模型，而在数据流环境下，实例是不断到来的，只能根据部分实例建立分类模型。因此，数据流分类器必须准备好处理大量的、快速输入的实例，而且每个实例只能在短时间内被处理或存储一次[1]。目前，数据流学习还面临很多挑战，这些挑战包括概念漂移、时间依赖关系、新类、特征漂移、类不平衡以及时间和内存受限等[1]。本文主要解决的是概念漂移问题。解决概念漂移问题目前最流行的方法是集成学习，而现有的多数数据流集成分类方法通常只考虑精度或者只考虑多样性。这两种方法在思路上的区别就是：前者重视基分类器在最新数据上的表现，认为新数据最符合目前这个阶段的数据分布；后者考虑在以后阶段会出现各种各样的数据分布，即各种各样的“概念”。使用多样性的基分类器能使集成分类器在各种“概念”下都能取得不错的性能。但是，多样性和精度这两个方面对数据流分类来说都是重要的，所以如何综合这两个方面来提出一个更加有效的方法，是本文主要的工作。本文的主要贡献如下：1) 提出了一种线性加权方式来计算分类器权重，将分类器在最新数据块上的精度以及该分类器在集成分类器中的多样性这两种度量分类器价值的标准以一种线性加权的方式融合成一个标准，以此作为衡量一个分类器对于当前集成分类器价值大小的依据；2) 使用一种基于价值度量的集成分类器更新策略来根据最新数据对集成分类器进行更新，将对精度和多样性线性加权得到的权重作为基分类器价值的度量。当有新的分类器到来时，价值最低的基分类器将会被新建立的分类器替换。 1 相关工作由于数据流的动态性，其学习过程存在很多问题，比如，在处理大规模数据流时，经常会发生数据分布变化的情况，这种情况被称为“概念漂移”(concept drift)，概念漂移的出现打破了机器学习中一个假设前提，即数据是独立同分布的。相反，也正是因为数据流不符合这个假设前提，才吸引了无数研究者。自概念漂移问题被发现以来，研究者们提出了大量的方法和策略用于处理概念漂移问题，其中有的方法假定概念漂移存在，在学习过程中不断根据当前数据对模型进行调整，而不关心是否真的出现概念漂移；还有一些方法不断检测数据流中是否出现概念漂移，如果出现概念漂移则对模型进行相应的调整。Brzezinski 等 [2]提出了一种可以对多种概念漂移反应同样好的分类算法，称为精度更新集成 (accuracy updated ensemble, AUE2)。该方法根据基分类器在当前数据块上的精度计算其权重并用于基分类器替换。Pietruczuk 等 [3]提出了一种可以动态扩展集成分类器大小的集成分类算法，其主张一个新的基分类器是否被添加进集成分类器中取决于这个添加操作是否不光提高了当前数据的精度而且也会提高整个数据流的分类精度。除了精度这种度量方式之外，多样性对于集成学习来说也是一个十分有意义的度量。Sun 等 [4-5]认为，应该鼓励模型之间的差异性，即多样性 (diversity) 提出了一种基于多样性和迁移的集成学习方法 (diversity and transfer based ensemble learning, DTEL) 来处理带有概念漂移的数据流分类问题。该方法使用 Q 统计量作为差异性度量，以基分类器之间的分类差异性作为标准来决定以前的基分类器是否保留。Rijn 等 [6]提出了一种结合异构模型的集成技术用于数据流分类，对集成分类器中不同基分类器的投票进行加权，重视分类器之间的差异性。也有一些研究者认为分类精度和分类多样性二者可以结合。Chandra 等 [7]证明了一个泛化性能好的集成分类器中，基分类器需要同时具备多样性和精确性，并且提出多样性和精度之间有一个折衷 (trade-off)。Li 等 [8] 提出了将一种结合多样性和精度的度量标准应用到遗传算法中，并通过实验结果表明了该度量方法的有效性。 2 加权多样性和精度的集成方法在正式介绍之前，先对本节所使用的符号作简单说明。令数据流 S 是由无数个大小相等的数据块 B 组成的，其中每个数据块是由数量相等的实例 z={x, y}构成。集成分类器 E 是由 n 个基分类器 C 构成。 2.1 分类器的精度和多样性度量 1) 精度度量精度的度量通常通过计算均方误差 (MSE) 得到，一个分类器 Ci 在一个数据块 Bj 的均方误差 MSEij 可以用式 (1) 表示： MSEi j = 1 Bj ∑ {x,y}∈Bj (1− p(fi(x) = y))2 (1) 使用 MSEr 表示对当前数据所有可能的类别进行随机预测所得到的均方误差，以此来反映当前数据的类分布，计算公式为 ·180· 智能系统学报第 14 卷

第1期张本才，等：一种多样性和精度加权的数据流集成分类算法 ·181· MSE,=∑p0I-p (2) 器所构成集合的多样性值可以通过式（⑧）计算： div,=∑Q/IEl (8) 精度可以使用MSE和MSE,来表示，本文使 C∈E,#j 用式(3)来表示集成分类器中已有的基分类器的 2.2基于多样性和精度加权的集成算法精度，即 1)基于多样性和精度加权的分类器权重计算本文提出了一种新的分类器权重计算方式 Accij=MSE+6 (3) 以往的集成方法在计算基分类器或者新建立分类式中6的存在是为了防止式(3)的分母为0。另器的权重时通常只根据精度或者多样性一个标准外，新建立的分类器的精度Accc根据式(4)来计算：来计算，这难免具有片面性，所以为了同时考虑 1 Accc MSE,+6 (4) 一个分类器的精度和多样性，本文采用了一种线 2)集成分类器中的多样性度量性加权方式来计算分类器权重，将在最新数据块目前已有的理论和实验研究可以证明，由多上分类器的精度以及该分类器与集成分类器之间个分类器组合而成的集成分类器相对于单个分类的多样性这两种度量分类器价值的标准以一种线器来说泛化能力更强，并且由相互独立、互为补性加权的方式融合成一个标准，以此作为衡量一充且相对精确的分类器集成得到的集成分类器在个分类器对于当前集成分类器价值大小的依据，泛化性能上要优于性能最好的基分类器例。当发并通过1个位于0~1的可调整的参数来控制精度生概念漂移时，所有基分类器可能全都无法处理和多样性各自在计算权重过程中的重要性。计算这类新问题；而如果集成分类器中的基分类器是权重有两个目的：1)使用权重来表示一个分类器多样性的，那么总能找到一个最擅长处理这个新在整个集成分类器的价值，用于集成分类器更问题的基分类器，从而使集成分类器具有良好的新；2)在预测阶段将每个基分类器的预测结果融泛化性能。合，权重高的分类器在预测时将起到更重要的作本文采用的多样性度量方法为Q统计量，计用。下面是具体的权重计算方式。算两个分类器之间的Q统计量值的公式如式当一个新的数据块到来时，使用此数据块构 (5)所示：建一个新的分类器C',并根据式(4)计算C的精 N11N00 -NOi N10 度Accc,根据式(T)计算C的多样性divc'。C的 =NI N+NOI NIO (5) 权重根据式(9)来计算，即式中：W表示分类器i分类结果为a、分类器j分 Wc aAccc+(1-a)divc. (9) 类结果为b的实例数量；1代表正确分类；0代表式中a∈[0,1。错误分类。比如，W表示分类器i和分类器j同已有基分类器的权重也需要根据新来的数据时分类正确的实例数量。块调整，使用式(10)计算基分类器新的权重值为了方便加权后的度量，所以需要将多样性 P即转化为越大代表多样性越强，如式(6)所示： Wij=aAcci+(1-a)div (10) Q=0.5(1-Q) (6) 式中w,表示基分类器C,在数据块B,上的权重。式中Q表示分类器C,与C,的Q统计量，用这个 2)基于价值度量的集成分类器更新策略值表示二者的差异程度，由于Q的值域为[-1，本文假定集成分类器的大小是固定的，即基 1],因此1-Q的值域为[0,2]，然后进行了归一分类器的个数是固定的，因此在新数据块建立一化，归一化这一步不是必需的，是否归一化对结个新的分类器C'后，如果基分类器的数量已经达果影响不大。到了规定的数目，则需要将集成分类器中的其中一个分类器C与一个集成分类器E的多样性一个基分类器替换出，那么如何选择被替换的基值为C与E中的每一个基分类器根据式(6)计算分类器将至关重要。得到的Q,的平均值。因此，新建立的分类器本文采用的是一种基于价值度量的集成分类 C与集成分类器E之间的多样性值divc可以通过器更新策略，将式(10)计算得到的权重，作为分式(7计算：类器C,当前的价值，当有新的分类器到来时，价 divc=∑g/l回 (7 值最低的基分类器将会被新建立的分类器替换掉。 i=C.CJEE 另外，之所以每次建立新分类器C后都将其集成分类器中一个基分类器C,与其余分类加入到集成分类器中，而不是先比较其是否比最

MSEr = ∑ y p(y)(1− p(y))2 (2) 精度可以使用 MSEij 和 MSEr 来表示，本文使用式 (3) 来表示集成分类器中已有的基分类器的精度，即 Acci j = 1 MSEi j +δ (3) 式中 δ 的存在是为了防止式 (3) 的分母为 0。另外，新建立的分类器的精度 AccC’根据式 (4) 来计算： AccC′ = 1 MSEr +δ (4) 2) 集成分类器中的多样性度量目前已有的理论和实验研究可以证明，由多个分类器组合而成的集成分类器相对于单个分类器来说泛化能力更强，并且由相互独立、互为补充且相对精确的分类器集成得到的集成分类器在泛化性能上要优于性能最好的基分类器[9]。当发生概念漂移时，所有基分类器可能全都无法处理这类新问题；而如果集成分类器中的基分类器是多样性的，那么总能找到一个最擅长处理这个新问题的基分类器，从而使集成分类器具有良好的泛化性能。本文采用的多样性度量方法为 Q 统计量，计算两个分类器之间的 Q 统计量值的公式如式 (5) 所示： Qi j = N 11N 00 −N 01N 10 N11N00 +N01N10 (5) 式中：N ab 表示分类器 i 分类结果为 a、分类器 j 分类结果为 b 的实例数量；1 代表正确分类；0 代表错误分类。比如，N 11 表示分类器 i 和分类器 j 同时分类正确的实例数量。为了方便加权后的度量，所以需要将多样性转化为越大代表多样性越强，如式 (6) 所示： Q ∗ i j = 0.5(1− Qi j) (6) 式中 Qij 表示分类器 Ci 与 Cj 的 Q 统计量，用这个值表示二者的差异程度，由于 Qij 的值域为[−1, 1]，因此 1 − Qij 的值域为[0, 2]，然后进行了归一化，归一化这一步不是必需的，是否归一化对结果影响不大。一个分类器 C 与一个集成分类器 E 的多样性值为 C 与 E 中的每一个基分类器根据式 (6) 计算得到的 Qi j *的平均值。因此，新建立的分类器 C′与集成分类器 E 之间的多样性值 divC′可以通过式 (7) 计算： divC′ = ∑ i=C′ , Cj∈E Q ∗ i j/ |E| (7) 集成分类器中一个基分类器 Ci 与其余分类器所构成集合的多样性值可以通过式 (8) 计算： divi = ∑ Cj∈E,i,j Q ∗ i j/ |E| (8) 2.2 基于多样性和精度加权的集成算法 1) 基于多样性和精度加权的分类器权重计算本文提出了一种新的分类器权重计算方式，以往的集成方法在计算基分类器或者新建立分类器的权重时通常只根据精度或者多样性一个标准来计算，这难免具有片面性，所以为了同时考虑一个分类器的精度和多样性，本文采用了一种线性加权方式来计算分类器权重，将在最新数据块上分类器的精度以及该分类器与集成分类器之间的多样性这两种度量分类器价值的标准以一种线性加权的方式融合成一个标准，以此作为衡量一个分类器对于当前集成分类器价值大小的依据，并通过 1 个位于 0~1 的可调整的参数来控制精度和多样性各自在计算权重过程中的重要性。计算权重有两个目的：1) 使用权重来表示一个分类器在整个集成分类器的价值，用于集成分类器更新；2) 在预测阶段将每个基分类器的预测结果融合，权重高的分类器在预测时将起到更重要的作用。下面是具体的权重计算方式。当一个新的数据块到来时，使用此数据块构建一个新的分类器 C′，并根据式 (4) 计算 C′的精度 AccC′，根据式 (7) 计算 C′的多样性 divC′。C′的权重 wC′根据式 (9) 来计算，即 wC′ = αAccC′ +(1−α)divC′ (9) 式中α ∈ [0,1]。已有基分类器的权重也需要根据新来的数据块调整，使用式 (10) 计算基分类器新的权重值 wij，即 wi j = αAcci j +(1−α)divi (10) 式中 wij 表示基分类器 Ci 在数据块 Bj 上的权重。 2) 基于价值度量的集成分类器更新策略本文假定集成分类器的大小是固定的，即基分类器的个数是固定的，因此在新数据块建立一个新的分类器 C′后，如果基分类器的数量已经达到了规定的数目，则需要将集成分类器中的其中一个基分类器替换出，那么如何选择被替换的基分类器将至关重要。本文采用的是一种基于价值度量的集成分类器更新策略，将式 (10) 计算得到的权重 wij 作为分类器 Ci 当前的价值，当有新的分类器到来时，价值最低的基分类器将会被新建立的分类器替换掉。另外，之所以每次建立新分类器 C′后都将其加入到集成分类器中，而不是先比较其是否比最第 1 期张本才，等：一种多样性和精度加权的数据流集成分类算法 ·181·

·182· 智能系统学报第14卷弱的分类器强再决定是否加入，这里假设基分类过设置概念漂移位置、漂移的数目和漂移的幅度器数量已经达到规定数量，主要因为C是根据最等属性，实现对不同类型概念漂移的模拟，但是新的数据块建立的分类器，因此可以说C'是最适合成数据集无法完全代替真实数据集，因此为了合当前数据的。由于当前数据块的数据分布情况评价算法的性能，除了在合成数据集上验证之有很大概率与以后数据的数据分布情况类似，所外，还需要在真实数据集上验证。本文选取3个以可以认为使用C对接下来的数据分类是有效的。真实数据集和3个合成数据集对提出的算法性能 3)算法过程进行验证。本文提出的多样性精度加权集成算法DAWE 3.1.1真实数据集是一个基于块的方法，对于每一个新到来的数据 I)扑克牌(Poker)数据集：来源于UCI数据块B,首先使用B,构建一个新分类器C',并根据库，每个实例有11个属性。数据集中每个实例式(9)计算C的权重，然后根据式(10)计算集成由52张牌中的5张组成，每张牌使用两个属性分类器中基分类器的权重，分类器的权重均通过 (suit和rank)来描述。将其在最新数据块B,上的精度与其在集成分类 2)Covertype数据集：来自UCI数据库，该数器中多样性值线性加权得到，使用权重值作为分据集包含了4个野生区域覆盖类型信息。该数据类器的价值度量。当基分类器数量达到规定数目集有581012个实例，每个实例有53个属性对应时，每产生一个新分类器C',便选择一个权重最 7种可能的森林覆盖类型中的1种。小的基分类器被C替换。DAWE算法过程描述如 3)Airlines数据集：该数据集包含根据航班的下所示。出发信息来预测此次航班是否会晚点的数据。此输入数据流S,集成分类器中的基分类器数n。数据集包含539383个实例，每个实例包含7个属性。输出n个加权的基分类器的集成E。 3.1.2合成数据集 1)begin 1)SEA数据集：该数据集是Street于2001年 2)将E初始为空；提出的，因仅含有连续型属性而著名，是经典的 3)对于数据流S的每个到来的数据块B: 突变式概念漂移数据集。 4)在数据块B,上训练新分类器C"; 2)LED数据集：该数据集用来预测7段数码 5)由式(9)计算C"的权重；显示器上显示的数字。该数据集有24个属性，其 6)对于每个E中的分类器C: 中前7个属性用于显示0~9的数字。 7)计算C,的精度（由式(3）)： 3)随机树数据集：该数据集由5个nominal属 8)由式(8)计算C,的多样性；性和5个numeric属性组成，类属性值通过随机 9)由式(10)计算C,的权重；树(random tree)确定。 10)如果E中分类器个数小于：将C直接添 3.2实验结果对比与分析加到E中；实验结果将通过3个方面展示：不同数据块 11)否则使用C替换E中权重最低的分类器；大小对算法性能影响、不同方法精度的对比以及 12)对于E中除去C之外的基分类器C: α值设置对算法性能影响。 13)在数据块B,上增量训练C: 3.2.1不同数据块大小对算法性能影响 14)end 图I展示了本文提出的算法DAWE在Cover-- 3 实验 type数据集、SEA数据集以及Tree(随机树)数据集上采用不同的数据块大小时的表现。在基于块本文的算法在大规模数据在线分析开源平的数据流挖掘中，块大小的选取对最终的分类性台MOA(massive online analysis)o下实现，在CPU 能将有着重要的影响，选择较大的数据块意味着为1.8GHz、内存为8GB、操作系统为Windows10 使用更多的实例建立分类器，使得当前分类器分的PC机上进行实验，评价类使用的是MOA下的类精度较高，缺点是对概念漂移反应不敏感：反 EvaluateInterleavedChunk类。之，选择较小的数据块虽然对概念漂移反应较敏 3.1数据集感，但缺点是每次建立分类器时使用的实例较少在数据流挖掘中，数据集可以分为两种：真实导致每个分类器的分类精度较低。因此，综合来数据集和合成数据集。人工合成的数据集可以通看数据块过大或者过小都使得最终分类性能不佳

弱的分类器强再决定是否加入，这里假设基分类器数量已经达到规定数量，主要因为 C′是根据最新的数据块建立的分类器，因此可以说 C′是最适合当前数据的。由于当前数据块的数据分布情况有很大概率与以后数据的数据分布情况类似，所以可以认为使用 C′对接下来的数据分类是有效的。 3) 算法过程本文提出的多样性精度加权集成算法 DAWE2 是一个基于块的方法，对于每一个新到来的数据块 Bi，首先使用 Bi 构建一个新分类器 C′，并根据式 (9) 计算 C′的权重，然后根据式 (10) 计算集成分类器中基分类器的权重，分类器的权重均通过将其在最新数据块 Bi 上的精度与其在集成分类器中多样性值线性加权得到，使用权重值作为分类器的价值度量。当基分类器数量达到规定数目时，每产生一个新分类器 C′，便选择一个权重最小的基分类器被 C′替换。DAWE算法过程描述如下所示。输入数据流 S，集成分类器中的基分类器数 n。输出 n 个加权的基分类器的集成 E。 1) begin 2) 将 E 初始为空； 3) 对于数据流 S 的每个到来的数据块 Bi； 4) 在数据块 Bi 上训练新分类器 C′； 5) 由式 (9) 计算 C′的权重； 6) 对于每个 E 中的分类器 Cj； 7) 计算 Cj 的精度 (由式 (3))； 8) 由式 (8) 计算 Cj 的多样性； 9) 由式 (10) 计算 Cj 的权重； 10) 如果 E 中分类器个数小于 n；将 C′直接添加到 E 中； 11) 否则使用 C′替换 E 中权重最低的分类器； 12) 对于 E 中除去 C′之外的基分类器 Cj； 13) 在数据块 Bi 上增量训练 Cj； 14) end 3 实验本文的算法在大规模数据在线分析开源平台 MOA(massive online analysis)[10]下实现，在 CPU 为 1.8 GHz、内存为 8 GB、操作系统为 Windows 10 的 PC 机上进行实验，评价类使用的是 MOA 下的 EvaluateInterleavedChunk 类。 3.1 数据集在数据流挖掘中，数据集可以分为两种：真实数据集和合成数据集。人工合成的数据集可以通过设置概念漂移位置、漂移的数目和漂移的幅度等属性，实现对不同类型概念漂移的模拟，但是合成数据集无法完全代替真实数据集，因此为了评价算法的性能，除了在合成数据集上验证之外，还需要在真实数据集上验证。本文选取 3 个真实数据集和 3 个合成数据集对提出的算法性能进行验证。 3.1.1 真实数据集 1) 扑克牌 (Poker) 数据集：来源于 UCI 数据库，每个实例有 11 个属性。数据集中每个实例由 52 张牌中的 5 张组成，每张牌使用两个属性 (suit 和 rank) 来描述。 2)Covertype 数据集：来自 UCI 数据库，该数据集包含了 4 个野生区域覆盖类型信息。该数据集有 581 012 个实例，每个实例有 53 个属性对应 7 种可能的森林覆盖类型中的 1 种。 3)Airlines 数据集：该数据集包含根据航班的出发信息来预测此次航班是否会晚点的数据。此数据集包含 539 383 个实例，每个实例包含 7 个属性。 3.1.2 合成数据集 1)SEA 数据集：该数据集是 Street 于 2001 年提出的[11] ，因仅含有连续型属性而著名，是经典的突变式概念漂移数据集。 2)LED 数据集：该数据集用来预测 7 段数码显示器上显示的数字。该数据集有 24 个属性，其中前 7 个属性用于显示 0~9 的数字。 3) 随机树数据集：该数据集由 5 个 nominal 属性和 5 个 numeric 属性组成，类属性值通过随机树 (random tree) 确定。 3.2 实验结果对比与分析实验结果将通过 3 个方面展示：不同数据块大小对算法性能影响、不同方法精度的对比以及 α 值设置对算法性能影响。 3.2.1 不同数据块大小对算法性能影响图 1 展示了本文提出的算法 DAWE 在 Covertype 数据集、SEA 数据集以及 Tree(随机树) 数据集上采用不同的数据块大小时的表现。在基于块的数据流挖掘中，块大小的选取对最终的分类性能将有着重要的影响，选择较大的数据块意味着使用更多的实例建立分类器，使得当前分类器分类精度较高，缺点是对概念漂移反应不敏感；反之，选择较小的数据块虽然对概念漂移反应较敏感，但缺点是每次建立分类器时使用的实例较少，导致每个分类器的分类精度较低。因此，综合来看数据块过大或者过小都使得最终分类性能不佳。 ·182· 智能系统学报第 14 卷

第1期张本才，等：一种多样性和精度加权的数据流集成分类算法 ·183· 90 量训练时各个阶段的实时精度。虽然从表1中 88 看Blast的平均精度最高，但是从图3中可以看 Covtype ---SEA 出，Blast之所以平均精度高是因为训练开始精度 86 Tree 高，随着实例的不断增加，其精度呈不断下降趋势，在300000个实例后，精度最好的算法一直是 83 DAWE。 82 图4展示了4种算法在SEA数据集上增量训 81 8 练时各个阶段的实时精度。SEA是突变漂移数据 250 500 75010001250150017502000 块大小集，因此为了更好检测并处理概念漂移，将数据块大小设置为500。可以看出，本文提出的算法图1不同数据块大小对算法的影响 Fig.1 Effect of data chunk size DAWE在平均精度上仅次于APF,并且与ARF只相差0.31%。由图1可以看出，对于Covertype数据集来说 80 数据块大小为1000是最合适的，即每到来1000 个实例将其作为一个数据块来训练一个分类器：而数据块大小为500对于SEA数据集来说是最合适的。由此可以看出，对于不同数据集可能需 ADE 要选用不同大小的数据块来达到其最佳性能。东66 64 3.2.2不同方法对比 ARF 60 本文选取的对比方法为MOA下的Accuracy 3 5 6 *10 已处理实例数 Updated Ensemble(AUE2),Adaptive Random Forest (ARF)2 Heterogeneous Ensemble Blast(Blast). 图24种算法在Poker数据集上分类精度对比 Fig.2 Accuracy contrast of 4 algorithms on Poker 别在Poker数据集、Airlines数据集、SEA数据集 70 和Covertype数据集上进行了对比实验。表I为几种算法在不同数据集上的平均精度对比。表1算法平均精度对比表 68 Table 1 Contrast of different algorithms % 67 66 算法 ARF AUE2 Blast DAWE ·DAWE Poker 68.28 69.67 67.53 75.83 65 一AR Airlines 65.69 66.88 67.18 67.12 64 4 5*10 已处理实例数 SEA 89.56 89.24 88.48 89.25 图34种算法在Airlines数据集上分类精度对比 Covertype 84.23 86.27 86.50 86.29 Fig.3 Accuracy contrast of 4 algorithms on Airlines Average 76.94 78.02 77.43 79.62 由表1可以看出，在4个数据集上本文提出 90 的算法DAWE的平均精度要优于其他3个算法。为了更详细地展示算法在不同数据集上的对比结果，接下来将分别展示在不同数据集上增量训练模型时各个阶段测试的精度情况。以下对比 88 DAWE -Blast 实验默认指定数据块大小为1000。。-AUE2 ARF 图2展示了4种算法（本文提出的算法以及 23 4567 891010 3个对比算法)在Pokr数据集上增量训练时各个已处理实例数阶段的实时精度，可以看出，本文提出的算法DAWE 图44种算法在SEA数据集上分类精度对比在Poker数据集上要远好于其他3个，在表1中也 Fig.4 Accuracy contrast of 4 algorithms on SEA 可以看出，在Poker数据集上，DAWE的平均精度图5展示了4种算法在Covertype数据集上相比其他3种算法分别高出6.16%、7.55%和8.30%。增量训练时各个阶段的实时精度。可以看出，图3展示了4种算法在Airlines数据集上增 DAWE和AUE2在训练前期表现较好，训练后期

250 500 750 1 000 1 250 1 500 1 750 2 000 块大小 80 81 82 83 84 85 86 87 88 89 90 分类精度/% Covtype SEA Tree 图 1 不同数据块大小对算法的影响 Fig. 1 Effect of data chunk size 由图 1 可以看出，对于 Covertype 数据集来说数据块大小为 1 000 是最合适的，即每到来 1 000 个实例将其作为一个数据块来训练一个分类器；而数据块大小为 500 对于 SEA 数据集来说是最合适的。由此可以看出，对于不同数据集可能需要选用不同大小的数据块来达到其最佳性能。 3.2.2 不同方法对比本文选取的对比方法为 MOA 下的 Accuracy Updated Ensemble (AUE2)、Adaptive Random Forest (ARF)[12]和 Heterogeneous Ensemble Blast (Blast)，分别在 Poker 数据集、Airlines 数据集、SEA 数据集和 Covertype 数据集上进行了对比实验。表 1 为几种算法在不同数据集上的平均精度对比。表 1 算法平均精度对比表 Table 1 Contrast of different algorithms % 算法 ARF AUE2 Blast DAWE Poker 68.28 69.67 67.53 75.83 Airlines 65.69 66.88 67.18 67.12 SEA 89.56 89.24 88.48 89.25 Covertype 84.23 86.27 86.50 86.29 Average 76.94 78.02 77.43 79.62 由表 1 可以看出，在 4 个数据集上本文提出的算法 DAWE 的平均精度要优于其他 3 个算法。为了更详细地展示算法在不同数据集上的对比结果，接下来将分别展示在不同数据集上增量训练模型时各个阶段测试的精度情况。以下对比实验默认指定数据块大小为 1 000。图 2 展示了 4 种算法 (本文提出的算法以及 3 个对比算法) 在 Poker 数据集上增量训练时各个阶段的实时精度，可以看出，本文提出的算法 DAWE 在 Poker 数据集上要远好于其他 3 个，在表 1 中也可以看出，在 Poker 数据集上，DAWE 的平均精度相比其他 3 种算法分别高出 6.16%、7.55% 和 8.30%。图 3 展示了 4 种算法在 Airlines 数据集上增量训练时各个阶段的实时精度。虽然从表 1 中看 Blast 的平均精度最高，但是从图 3 中可以看出，Blast 之所以平均精度高是因为训练开始精度高，随着实例的不断增加，其精度呈不断下降趋势，在 300 000 个实例后，精度最好的算法一直是 DAWE。图 4 展示了 4 种算法在 SEA 数据集上增量训练时各个阶段的实时精度。SEA 是突变漂移数据集，因此为了更好检测并处理概念漂移，将数据块大小设置为 500。可以看出，本文提出的算法 DAWE 在平均精度上仅次于 APF，并且与 ARF 只相差 0.31%。 ×105 1 2 3 4 5 6 7 8 已处理实例数 60 62 64 66 68 70 72 74 76 78 80 分类精度/% ADE Blast AUE2 ARF 图 2 4 种算法在 Poker 数据集上分类精度对比 Fig. 2 Accuracy contrast of 4 algorithms on Poker 1 2 3 4 5 已处理实例数 64 65 66 67 68 69 70 分类精度/% DAWE Blast AUE2 ARF ×105 图 3 4 种算法在 Airlines 数据集上分类精度对比 Fig. 3 Accuracy contrast of 4 algorithms on Airlines 1 2 3 4 5 6 7 8 9 10 已处理实例数 87 88 89 90 分类精度/% DAWE Blast AUE2 ARF ×105 图 4 4 种算法在 SEA 数据集上分类精度对比 Fig. 4 Accuracy contrast of 4 algorithms on SEA 图 5 展示了 4 种算法在 Covertype 数据集上增量训练时各个阶段的实时精度。可以看出， DAWE 和 AUE2 在训练前期表现较好，训练后期第 1 期张本才，等：一种多样性和精度加权的数据流集成分类算法 ·183·

·184· 智能系统学报第14卷 Blast更好，从平均精度上来看DAWE与Blast只的集成方法用于处理数据流分类问题，使用精度相差0.21%。与多样性的线性加权来计算一个分类器的权重， 90 通过权重来衡量一个分类器对于整个集成分类器 89 8 的重要性，权重越高表示这个分类器越重要，当 87 有新分类器建立时需替换权重最低的基分类器。 85 实验验证了本文所提出的算法可以有效处理数据尔84 3 ADE 流中的概念漂移问题。 --Blast 82 AUE2 81 ARF 参数α的选择会在一定程度上决定算法的性 80 3*10s 能，如何根据不同数据集选择一个合适的α值是已处理实例数今后研究的方向。在加权方式上，本文选择的是图54种算法在Covertype数据集上分类准确度对比线性加权，在今后的研究中还可以对加权方式进 Fig.5 Accuracy contrast of 4 algorithms on Covertype 一步优化。另外，将迁移学习用于数据流分类是 3.2.3α值设置对算法性能影响个值得研究的问题，迁移学习的目的是利用已本文提出的算法通过多样性和精度的线性加有模型帮助新环境下样本的分类，与数据流挖掘权来计算分类器权重，由式(9)、式(10)可以看中的概念漂移和特征漂移问题相符合，因此二者出，通过α来控制多样性和精度在计算权重过程具备良好结合的可操作性。中分别所占比重，所以其取值对最终的分类精度会产生影响，图6以Poker数据集以及LED数据参考文献：集为例展示了不同α的取值对集成分类器的平均 [1]GOMES H M,BARDDAL J P,ENEMBRECK F,et al.A 分类精度产生的影响。由此可以看出，对于不同 survey on ensemble learning for data stream classification 数据集，需要选用不同α值以达到最佳分类性能。 [J].ACM computing surveys,2017,50(2):23. 95 [2]BRZEZINSKI D,STEFANOWSKI J.Reacting to differ- 90 ent types of concept drift:the Accuracy Updated En- 80 semble algorithm[J].IEEE transactions on neural net- 75 works and learning systems,2014,25(1):81-94. 彩70 [3]PIETRUCZUK L,RUTKOWSKI L,JAWORSKI M,et al. 565 60 How to adjust an ensemble size in stream data mining[J]. Poker 55 --HyperPlane Information sciences,2017,381:46-54 50 00.10.20.30.40.50.60.70.80.9 [4]孙宇.针对含有概念漂移问题的增量学习算法研究D] 合肥：中国科学技术大学，2017 图6不同a值对平均分类精度的影响 SUN Yu.Incremental learning algorithms with concept Fig.6 Effect of different a on average accuracy drift adaptation[D].Hefei:University of Science and Tech- 通过表1以及图2~5可以看出，本文提出的 nology of China,2017. 算法DAWE在部分数据集上优于其他算法，特别 [5]SUN Yu,TANG Ke,ZHU Zexuan,et al.Concept drift ad- 是在Poker数据集上，相较于其他算法有大幅提 aptation by exploiting historical knowledge[J].IEEE trans- 升；在Airlines数据集上表现也不错，在训练后半 actions on neural networks and learning systems,2018, 段一直占据精度第一的位置；在SEA数据集上平 29(10):4822-4832 均精度仅次于ARF;在Covertype数据集上平均精 [6]VAN RIJN J N,HOLMES G,PFAHRINGER B,et al. 度仅次于Blast。,综合4个数据集来看，对4种算 Having a Blast:meta-learning and heterogeneous en- 法在4个数据集上的平均精度取平均值（即表1 sembles for data streams[C]//Proceedings of the 2015 IEEE International Conference on Data Mining.Atlantic City, 的最后一行)，通过平均值可以看出，本文提出的 USA,2015:1003-1008. 算法DAWE在参与对比的4种算法中是最优的。 [7]CHANDRA A,CHEN Huanhuan,YAO Xin.Trade-off 4结束语 between diversity and accuracy in ensemble generation [M//JIN Yaochu.Multi-Objective Machine Learning.Ber- 本文提出了一种综合考虑精度和多样性的新 lin Heidelberg:Springer,2006:429-464

Blast 更好，从平均精度上来看 DAWE 与 Blast 只相差 0.21%。 1 2 3 4 5 已处理实例数 ×105 80 81 82 83 84 85 86 87 88 89 90 分类精度/% ADE Blast AUE2 ARF 图 5 4 种算法在 Covertype 数据集上分类准确度对比 Fig. 5 Accuracy contrast of 4 algorithms on Covertype 3.2.3 α 值设置对算法性能影响本文提出的算法通过多样性和精度的线性加权来计算分类器权重，由式 (9)、式 (10) 可以看出，通过 α 来控制多样性和精度在计算权重过程中分别所占比重，所以其取值对最终的分类精度会产生影响，图 6 以 Poker 数据集以及 LED 数据集为例展示了不同 α 的取值对集成分类器的平均分类精度产生的影响。由此可以看出，对于不同数据集，需要选用不同 α 值以达到最佳分类性能。 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 α 50 55 60 65 70 75 80 85 90 95 分类精度/% Poker HyperPlane 图 6 不同 α 值对平均分类精度的影响 Fig. 6 Effect of different α on average accuracy 通过表 1 以及图 2~5 可以看出，本文提出的算法 DAWE 在部分数据集上优于其他算法，特别是在 Poker 数据集上，相较于其他算法有大幅提升；在 Airlines 数据集上表现也不错，在训练后半段一直占据精度第一的位置；在 SEA数据集上平均精度仅次于 ARF；在 Covertype 数据集上平均精度仅次于 Blast。综合 4 个数据集来看，对 4 种算法在 4 个数据集上的平均精度取平均值 (即表 1 的最后一行)，通过平均值可以看出，本文提出的算法 DAWE 在参与对比的 4 种算法中是最优的。 4 结束语本文提出了一种综合考虑精度和多样性的新的集成方法用于处理数据流分类问题，使用精度与多样性的线性加权来计算一个分类器的权重，通过权重来衡量一个分类器对于整个集成分类器的重要性，权重越高表示这个分类器越重要，当有新分类器建立时需替换权重最低的基分类器。实验验证了本文所提出的算法可以有效处理数据流中的概念漂移问题。参数 α 的选择会在一定程度上决定算法的性能，如何根据不同数据集选择一个合适的 α 值是今后研究的方向。在加权方式上，本文选择的是线性加权，在今后的研究中还可以对加权方式进一步优化。另外，将迁移学习用于数据流分类是一个值得研究的问题，迁移学习的目的是利用已有模型帮助新环境下样本的分类，与数据流挖掘中的概念漂移和特征漂移问题相符合，因此二者具备良好结合的可操作性。参考文献： GOMES H M, BARDDAL J P, ENEMBRECK F, et al. A survey on ensemble learning for data stream classification [J]. ACM computing surveys, 2017, 50(2): 23. [1] BRZEZINSKI D, STEFANOWSKI J. Reacting to different types of concept drift: the Accuracy Updated Ensemble algorithm[J]. IEEE transactions on neural networks and learning systems, 2014, 25(1): 81–94. [2] PIETRUCZUK L, RUTKOWSKI L, JAWORSKI M, et al. How to adjust an ensemble size in stream data mining[J]. Information sciences, 2017, 381: 46–54. [3] 孙宇. 针对含有概念漂移问题的增量学习算法研究[D]. 合肥: 中国科学技术大学, 2017. SUN Yu. Incremental learning algorithms with concept drift adaptation[D]. Hefei: University of Science and Technology of China, 2017. [4] SUN Yu, TANG Ke, ZHU Zexuan, et al. Concept drift adaptation by exploiting historical knowledge[J]. IEEE transactions on neural networks and learning systems, 2018, 29(10): 4822–4832. [5] VAN RIJN J N, HOLMES G, PFAHRINGER B, et al. Having a Blast: meta-learning and heterogeneous ensembles for data streams[C]//Proceedings of the 2015 IEEE International Conference on Data Mining. Atlantic City, USA, 2015: 1003–1008. [6] CHANDRA A, CHEN Huanhuan, YAO Xin. Trade-off between diversity and accuracy in ensemble generation [M]//JIN Yaochu. Multi-Objective Machine Learning. Berlin Heidelberg: Springer, 2006: 429–464. [7] ·184· 智能系统学报第 14 卷

点击进入文档下载页（PDF格式）

已到末页，全文结束

点击下载（PDF格式）

浏览记录