基于相反分类器的数据流挖掘方法分析

1相反分类器及分类器精度赋权公式

本文的基本思想, 是通过建立相反分类器使分类算法可以从错误中学习。当一个分类器的期望分类精度较低时, 不是简单放弃该分类器而应建立并验证其相反分类器。当相反分类器和现有概念一致时, 通过更新组合分类器, 就有可能提高组合分类器的分类精度[1]。

定义1相反分类器:一个分类器用C来表示, 对于一个实例X, C (X) =ci, ci∈c, 则分类器C的相反分类器记为, 其中X) =c′i, c′i≠ci, c′i∈c。特别当c=[0, 1]时, 分类器C的相反分类器是

图1中的直线表示目标概念1。图2是分类器C1的相反分类器。图3是目标概念2以及对应的分类器C2。数据流中经常面临概念变化的情况, 当概念由1变化到2时, 用分类器C1去分类, 实际上由概念2决定的实例, 就会出现很大的错误率。此时Weighted Bagging方法就会舍弃分类器C1, 而逐步训练新的分类器以适应概念2。从而会导致分类器收敛速度下降和分类器C1中信息的浪费。而分类器C1的相反分类器却和概念2比较接近, 可以先用去分类概念2标记的实例, 等得到与概念2更近似的高精度分类器时再替换分类器。判断一个分类器的相反分类器是否与最近的概念相近, 必须计算它的期望预测错误率, 只有该相反分类器的分类能力较高时, 才将它加入集合中更新组合分类器。

当数据流逐步流入时, 到来的数据被分成数据段S1, S2, , …, Sn, …, 其中凡是最近时间步到来的数据段。记每个段的大小为Chunk Size, 在每个数据段上训练分类器C1, 组成一个分类器集合。为了对每个分类器进行准确度赋权, 可在测试数据集上计算它的期望预测错误率。如果假设最近的训练数据段和测试集合的类分布非常近似, 则分类器的准确率赋权可以通过在Sn上的分类错误率近似得到。具体来说, 一个分类器C在Sn上的平均平方错误率可定义为:

其中:S n中的每个实例具有形式 (X, ci) , X表示一个实例, Ci是该实例的类标号;fC (X) 是分类器C计算得出的实例X属于类Ci的概率Ci∈c (Sn) 是凡中实例的类标记的集合。分类器C的权应该和平均平方错误率成反比。

另一方面, 当用一个随机分类器来分类数据段Sn时, 它的平均平方错误率为:

当一个分类器的权为负时, 表示该分类器的分类精度比一个随机分类器的精度还要差, 所以Weight Bagging会放弃权为负的所有分类器, 这也反映了该分类器的相反分类器与当前的概念比较接近, 如果这个相反分类器的精度较高, 就可以帮助改进分类的精度。

2 IWB (Improved Weighted Bagging) 算法

推进和装袋是两种经常使用的产生组合分类器的方法, 而推进方法要求对数据点进行重新赋权和对噪音敏感, 因此本文中使用装袋方法来产生组合分类器。[2]

输入:S//数据流中新到来的Chunk Size个点构成的集合

Ec//K个预先训练的分类器组成的集合

K//Ec中的分类器数目的最大值

输出:Ec//分类器的集合, 其中每个元素是一个分类器及其权

算法1是挖掘概念漂移的数据流组合分类器算法。在每一个时间步, 一个新的数据段到达时, 首先在这个数据段上训练一个分类器, 其次在这个数据段上使用基于交叉验证的方法来评价这个分类器, 最后根据公式更新集合中其它基础分类器的权。如果某个基础分类器的权小于0, 就计算其相反分类器, 并在这个数据段上进行评价。只有当相反分类器的权大于0时, 它才被加入集合中。算法最终返回这个集合中权最高的k个分类器。

在预测测试实例的类标号时, 使用集合中所有权大于0的分类器进行赋权投票来决定最终的类标号。

3实验验证

为了验证我们的算法, 首先在STAG-GER概念上和Weighted Bagging方法进行比较。在STAGGER概念中, 每个实例有三个属性值color∈{green, blue, red}, shape∈{triangle, circle, rectangle}和size∈{small, medium, large}。练实例陆续在120个时间点上到达, 在每个时间点, 学习器接收到一个实例[3]。在前40个时间点上, 目标概念是color=red∧size=small接下来的4 0个时间点, 目标概念是size=medium∨shape=cicle, 在最后的40个时间点上目标概念是。为了评价学习器, 在每个时间点上随机地产生100个测试实例, 这100个实例是以当前时间的目标概念标记的。每学习一个新的训练实例后, 用集合中的分类器在相应的100个测试实例上计算正确预测的百分比。在整个的实验中, 重复这个过程50次, 取其平均值。组合分类器中的每个分类器都是采用决策树分类器C4.5。

每当概念发生变化, Weighted Bagging算法重复出现突然地准确度降低。而在概念发生漂移的时候, IWB算法具有更快的收敛到目标函数的能力。不仅在发生概念漂移的时候, 预测的精度下降比较低, 而且收敛到新的目标概念的速度比较快, 更重要的是随着时间的推移, IWB的学习能力越来越强。在时间步240后, 预测的精度不再随着概念的变化而出现突然降低, 一直保持较平稳的预测精度, 预测错误率应该和概念漂移的数目不相关。

4结语

本文定义了相反分类器, 设计并实现了基于相反分类器的组合分类器算法IWB。在基准数据集和移动的超平面数据集上进行了检验。实验结果表明, IWB算法比Weighted Bagging方法在遇到概念漂移的时候具有更快的收敛到目标函数的能力并具有更高的精度。

摘要：本文提出了基于组合分类器的IWB算法, 定义了相反分类器。通过使用相反分类器, 在遇到突然的概念漂移时, IWB算法可以从错误中学习, 具有更快地收敛到新的目标概念的能力, 而当概念稳定时没有大的波动。

关键词：相反分类器,IWB算法,数据流

参考文献

[1] 高宏宾, 张小彬, 杨海振.一种实时挖掘数据流近似频繁项的算法[J].计算机应用, 2008 (12) .

[2] Wei　Fan.Systematic　data　selection　to Mine　Concept-Drifting　Data　Streams.In　proceeding　of　the　conference　KDD, 2004:128～137.

[3] F.　Chu　and　C.　Zaniolo.　Fast　and Light　Boosting　for　Adaptive　Mining　of Data　Streams.　In　Proc.　of　the　5th Pacific-Asic　Conference　on　Knowl-edge　Discovery　and　Data　Mining (PAKDD) , 2004.