贾涛,韩萌,王少峰,邢成

(北方民族大学 计算机科学与工程学院,宁夏 银川 750021)

0 引言

近年来,随着信息技术和大数据的不断发展,产生了大量的数据流。因此数据流的收集和分析就变得至关重要。数据流量的爆炸式增长,势必需要更大的内存来存储这些数据流,所以传统的数据挖掘技术很难满足社会的需求，而数据流的处理技术将发挥越来越重要的作用。常见用于处理数据流的分类方法包括决策树[1-2]、神经网络[3-4]、关联/分类规则、支持向量机等[5-6]。其中决策树分类算法是最有效的分类方法之一。如今决策树算法已经成功地应用于许多应用领域的分类,如在医疗诊断、天气预报、金融分析、顾客分类、身份识别、网络安全和行为分析等领域逐渐发挥着越来越重要的作用。与此同时,国内外研究工作者也在不断丰富决策树算法的理论知识。

决策树分类算法是一种非常经典的、处理效率很高的分类方法。它是一种类似于树的结构,其中每个内部节点表示一个属性值的决策。每个分支代表决策的结果,树的叶节点代表类。在数据挖掘和机器学习中,决策树是一种预测模型;也就是说,从观察一个项目到关于它的目标值的结论的映射[7]。用于数据流挖掘的传统技术需要多次扫描数据以提取信息,这对于流数据是不可行的。与传统的数据集不同,数据流具有高速流动、有序变化、实时处理等特征[8]。不同于数据仓库,它是实时产生,且一般不被存储,所以要求快速地处理,尽量短时间内挖掘出其中有用的信息。因此传统的数据挖掘技术已不再适合数据流环境。从而,数据流环境下的数据挖掘研究具有更大的机遇和挑战性[9]。

本文研究并设计了一种基于McDiarmid不等式的数据流决策树分类算法,该算法可以处理非数值数据,并且在处理数据流属性分裂度量方面具有一定优势。为了进一步提高分类性能,设计使用ε/2进行属性分类度量。McTree算法与经典算法相比,在分类准确率升高或者几乎保持不变的情况下,生成决策树的节点数与层数明显降低。

1 研究现状

为了处理数据流问题，Domingos等人最初提出了快速决策树(VFDT)算法[10],VFDT是一种基于Hoeffding树的经典数据流分类算法,首先将决策树学习应用于数据流挖掘[11],解决了构建决策树过程中训练不足的问题,也在数据流环境中能够取得不错的分类效果。这开辟了决策树算法处理数据流问题的先河。

1.1 Hoeffding决策树的研究现状

针对VFDT不能很好地处理概念漂移问题并且只能处理离散属性,Gama等人提出了基于VFDT的VFDTc算法[12],该算法不仅可以处理离散数据流,而且还可以处理连续数据流。Hulten等人提出了CVFDT算法[13],CVFDT算法在VFDT算法的基础上做了一些优化,能够很好地适应概念漂移数据流,并且与VFDT相比提高了分类性能[14]。Pfahringer等人提出的霍夫丁选项树(Hoeffding Option Tree,HOT)是一个常规的Hoeffding树,除了内部决策节点和叶子外,还包含额外的选项节点。并且允许应用多个测试,从而将多个Hoeffding树作为单独的路径。这个结构使得一个例子可以通过多个不同路径到达多个不同的树节点[15]。Bifet等人提出了霍夫丁自适应树(Hoeffding Adaptive Tree,HAT),该方法作为一种从Hoeffding Window Tree演化而来的新方法,自适应地学习随时间变化而不需要固定大小的滑动窗口。滑动窗口的最优大小是用户很难猜测的参数,因为它取决于数据流分布的变化率。为了避免参数大小的选择,文献[16]提出了一种管理节点统计信息的新方法。其基本思想很简单:在每个节点上放置频率统计估计器的实例,即用估计器的Aijk实例替换Hoeffding Window Tree中的每个nijk计数器。Yang等人提出了一种增量优化快速决策树(iOVFDT)算法[17-18],用于处理噪声数据流。虽然在处理大数据流时,该算法很难全面地实现预处理和抽样，但该算法在较高的精度和较小的模型尺寸方面具有很大优势。Cazzolato等人描述了一种基于VFDT系统的增量决策树算法StARMiner Tree(ST)[19],该算法处理数值型数据流,采用基于统计的方法作为启发式算法来决定何时分割节点,以及选择测试节点中使用的最佳属性。韩萌等人提出了一种处理可变数据流的频繁模式决策树算法(PatHT),与其他同类算法相比,该方法对稳态数据流处理时可以明显提高正确率或可以明显缩短训练时间,在处理不同概念漂移特性的可变数据流时也具有很好的分类效果[20]。Jankowski等人提出了一种利用概念漂移对数据流进行分类的数据流挖掘算法,称为基于决策树的进化算法(EVO-Tree)。它不需要任何的知识环境,比如数据流的数量和速度。这种方法的新颖之处在于将树学习机制和进化算法结合在一起。在这种算法中,决策树是增量的,所有信息都存储在树的内部结构中。该算法在减少树大小的同时也减小了分类误差[21]。针对当前数据流挖掘应用中的隐私泄露问题,陈煜等人提出了一种基于决策树隐私保护的数据流分类算法PPFDT。该算法通过采用添加随机噪声的方法对数据加以隐私保护,并使用阀值算法找到扰动数据流的最佳分裂属性和最佳分裂点,从而直接在扰动数据流上构造决策树[22]。Song等人提出了MHFlexDT算法,该算法可以在降低模糊决策树层数的同时获得更高的分类精度,使属性操作值的范围更加灵活,提高了分类响应性。MHFlexDT 可以在决策树的不同层次上添加新特征,这可以使模糊决策树的构造更加灵活,并且该方法与二进制HFlexDT算法相比减少了数据计算成本[23]。Gomes等人提出了自适应随机森林(ARF)算法,用于分类演化数据流。与先前为数据流学习复制随机森林的尝试相比,ARF包括一种有效的重采样方法和自适应算子,可以处理不同类型的概念漂移而无需对不同数据集进行复杂优化[24]。Chaitanya等人提出的极速决策树(Extremely Fast Decision Tree,EFDT)算法等同于Hoeffding树,只是它使用Hoeffding边界来确定最佳属性上拆分的增益是否超过未拆分的增益或当前拆分属性的增益。实际上,如果一个节点上不存在拆分属性,而不是仅当第一候选拆分属性的性能优于第二好的候选者时才进行拆分。那么,当来自第一候选拆分的信息增益非零且具有所需的置信度时,EFDT将进行拆分。与HoeffdingTree相比,其运行时间变长,但准确率升高并且内存需求明显降低[25]。

在VFDT算法上优化的数据流决策树分类算法都是基于Hoeffding不等式设计的,这些算法中使用的主要数学工具是Hoeffding不等式[26],其中ε的计算形式如公式(2)所示。

定理1[27]如果X1,X2,…,Xn是独立的随机变量并且ai≤Xi≤bi(i=1,2,…,n),然后对于ε>0有如下不等式(1):

(1)

对于ai=a和bi=b,(i=1,2,…,n),它表明在n次观察之后,范围R=b-a的随机变量的真实均值与估计均值的差异不超过

(2)

其中,R=log2C,C是类的数目,δ是分裂置信度,n是实例数。

(3)

(4)

公式(4)等价于

(5)

现在回顾一下Hoeffding不等式:

(6)

和

(7)

显然,Hoeffding不等式只适用于实值数据流。

如果每个Yi来自相同的分布,则E[Y]=E[Y1]=…=E[YN],因此E[S]=N·E[Y].将Hoeffding不等式(6)应用于公式(5)得到

(8)

简化分母并将公式(8)的右边等于δ得到

(9)

关于ε求解公式(9),得到公式(2)。即完成了Hoeffding不等式的证明。

1.2 McDiarmid决策树的研究现状

基于Hoeffding不等式设计的决策树方法是常见的分类决策树方法之一。在Hoeffding不等式中,当n倾向于无穷大时,ε倾向于0。但是,通过分析可以看出Hoeffding不等式有一些缺陷:首先,只有数值数据流适用于Hoeffding不等式。在一般情况下,数据流不必全是数值数据。其次,在属性分裂度量方面,如信息增益和基尼指数,不能表示为元素Yi的和S[28]。因此,这个问题的解决方案似乎是应用McDiarmid不等式而不是Hoeffding不等式。

那么,针对Hoeffding不等式存在的不足,基于McDiarmid不等式的数据流决策树算法也就随之诞生了。下面将介绍基于McDiarmid不等式的数据流决策树分类算法。Rutkowski等人2014年提出用于数据流的CART算法是基于泰勒定理和正态分布设计的[29]。同年Rutkowski等人提出了基于McDiarmid不等式的决策树算法对ID3算法中使用的信息增益和CART算法中使用的Gini索引的约束。实验结果保证了应用于数据流并基于McDiarmid不等式的决策树学习系统的输出几乎与传统学习系统相同[30]。Maciej等人提出了一种混合分裂准则,其结合了针对两种不同分裂测量函数建立的两个标准:基尼误差增益和基于误分类误差的分裂测量。混合分裂标准揭示了其两个组成部分的优点。数值实验表明,混合准则的在线决策树的分类精度优于单一分裂准则的在线决策树的分类精度[31]。Bartosz等人提出了一种有效且快速,自适应成本敏感的决策树学习方案,该解决方案能够从二进制和多类不平衡数据流中学习,用于处理在线不平衡类。在树的每个叶子中,训练具有输出适应性的感知器以补偿偏斜的类分布,而McDiarmid不等式用于控制分裂属性选择[32]。

1.3 属性选择度量

属性选择度量是一种选择分裂准则,把给定类标记的训练元组的数据流分区D“最好地”划分成单独类的启发式方法。属性选择度量又称为分裂规则,因为它们决定给定结点上的元组如何分裂。本小节将介绍三种常用的属性选择度量——信息增益(Information Gain)、增益率(Gain Rate)和基尼指数(Gini index)[33],目前用于处理数据流问题的常用度量标准是信息增益和基尼指数。

符号定义:设数据分区D为标记类元组的训练集。假定类标号属性具有m个不同值,定义了m个不同的类Ci(i=1,2,3,…,m)。设Ci,d是D中Ci类元组的集合,|D|和|Ci,D|分别是D和Ci,D中元组的个数。

① 信息增益根据信息增益最大的属性作为分裂节点。其计算公式如下:

(10)

其中,pi是D中任意元组属于类Ci的非零概率,并用|Ci,D|/|D|估计。使用以2为底的对数函数是因为信息用二进制编码。Info(D)是识别D中元组的类标号所需要的平均信息量。Info(D)又称为信息熵。

(11)

信息增益定义为原来的信息需求(仅基于类比例)与新的信息需求(对A划分后)之间的差。即

Gain(A)=Info(D)-InfoA(D) .

(12)

② 增益率根据信息增益率最大的属性作为分裂节点。C4.5[33]使用一种称为增益率(gain ratio)的信息增益扩充,它用“分裂信息(split information)”值将信息增益规范化。分裂信息类似于Info(D),定义如下:

(13)

该值代表由训练集D划分成对应于属性A测试的v个输出的v个分区产生的信息。信息增益率定义为:

(14)

③ 基尼指数根据基尼指数最小的属性作为分裂节点。基尼指数度量数据分区或训练元组集D的不纯度,定义为:

(15)

其中,pi是D中元组属于Ci类的概率,并用|Ci,D|/|D|估计。对m个类求和。

基尼指数考虑每个属性的二元划分。当考虑二元划分裂时,计算每个结果分区的不纯度加权和。若A的二元划分将D划分成D1和D2,则给定该划分,D的基尼指数为:

(16)

属性A的二元划分导致的不纯度降低为:

ΔGini(A)=Gini(D)-GiniA(D) .

(17)

2 基于McDiarmid不等式的分类算法研究

已有的数据流决策树分类方法中,基于Hoeffding不等式设计的决策树方法是常见的方法之一。在公式(2)中,当n趋向于无穷大时,ε趋向于0。但是,通过1.1节的证明分析可以容易地看出Hoeffding不等式存在一些不足:首先,Hoeffding不等式只适合数值属性的处理。其次,在属性分裂度量方面,如信息增益和基尼指数,不能使用S表示元素Yi的和[28]。因此,这个问题使用McDiarmid不等式处理似乎比Hoeffding不等式更加合理和可行。因此,本文研究并设计出一种基于McDiarmid不等式的数据流决策树分类算法(McTree)。

2.1 McDiarmid不等式的证明

由于在第1节中提到Hoeffding不等式处理数据流存在很多不足。因此,本文利用Hoeffding不等式的推广McDiarmid不等式[34]作为决策树分割准则统计工具的思想在[27]中被提出。下面给出了McDiarmid定理如下:

定理2[31](McDiarmid不等式)设X1,…,Xn是一组独立的随机变量,让f(x1,…,xn)成为满足以下不等式(18)的函数:

(18)

然后对于任何ε>0,以下不等式(19)为真

(19)

Hoeffding不等式(6)是McDiarmid不等式(19)的一个特例,当Xi∈Ai=[ai,bi]时,对于i=1,…,N,是实值随机变量。

由于f(X1,…,XN)是随机变量的函数,因此它也是随机变量。E[f(X1,…,XN)]是其预期值。为了获得与公式(2)中相同形式的ε,应满足以下条件如公式(20)

(20)

对于某个常数C,则有公式(21)

(21)

如果C=R,我们可以得到公式(2)给出的ε。化简公式(21),得到公式(22):

(22)

通过多次实验表明,使用信息增益进行分裂度量得到的实验结果明显比基尼指数的好,因此本文也将采用信息增益作为分裂度量。下面定理3保证了一个应用于数据流的决策树学习方法,它的输出几乎与传统学习的输出相同。

定理3[27](McDiarmid定理)令Z={X1,…,Xn}为独立随机变量的集合,其中每个随机变量取值于集合A×B×…×Λ。对于任何固定的δ与任何一对属性a和b,有f(Z)=Gaina(Z)-Gainb(Z)>0,若

(23)

则有

Pr(f(Z)-E[f(Z)]>ε)≤δ，

(24)

其中,

CGain(K,n)=6(Klog2en+log22n)+2log2K.

(25)

由于文献[10]中考虑一个实值随机变量r,其范围是R(例如概率范围为1,而对于信息增益范围是logK,其中K是类的数目),则有关系式K=2R代入(25)中有如下公式(26):

C=6(2Rlog2en+log22n)+2R.

(26)

通过对文[10]的学习过程中看到使用ε2<τ作为属性分裂判断,从而得到灵感,将(22)进行变形,得到一种新的用于分裂判断的度量标准(27):

(27)

将公式(26)代入,则有(28):

(28)

2.2 基于McDiarmid不等式的决策树

针对Hoeffding不等式在属性分裂度量方面存在的不足,本文使用Hoeffding不等式的扩展,提出了一种基于McDiarmid不等式的数据流决策树分类算法(McTree)来解决Hoeffding不等式存在的不足,并使用McTree 算法提高处理性能。

在McTree算法中,首先当新的示例到达之后便放入到叶节点l中,从而更新统计信息nl,当满足nmin可以整除nl并且叶节点都不是同一类才计算每个属性的信息增益差进行分裂,如图1中算法步骤①-⑥所示。在进行分裂的过程中,影响分裂的主要因素是nmin,ε和τ。其中,nmin直接影响属性的信息增益,即影响的是最大信息增益与次大信息增益的差值。τ是当⑨ 中的Gl(Xa)-Gl(Xb)>ε/2不满足时候才会执行后半部分ε/2 <τ,所以决定是否分裂的直接因素是ε和τ。而τ是直接取值即可(本文中τ取值为默认值0.05),但是ε是由步骤⑧ 计算而来的。因此,本算法首先对ε的计算公式进行优化,使得该算法的分类性能更好。但是在实验中,使用ε进行分裂判断得到的分类精度并不尽人意,因此本算法采用ε/2作为分裂判断,将得到更高的分类精度。该算法的具体实现伪代码如图1所示。

输入:数据流实例S, 属性集X, 分裂评价函数G(X), 分裂置信度δ, 主动分裂阈值τ, 最小分裂实例数nmin;输出:决策树McTree。算法步骤:① McTree是一棵具有单一叶子(根)的树② 对于所有训练示例,使用McTree将例子放入到叶节点l中③ 更新叶子l的统计信息④ 在l中观察到的实例统计数量,递增nl⑤ nmin可以整除nl并且在l处得到的例子不全是同一类⑥ 对每个属性计算Gl(Xi)⑦ 设Xa是最大信息增益的属性,Xb是次大信息增益的属性⑧ 计算McDiarmid不等式ε=[6(2Rlog2en+log22n)+2R]ln(1/δ)2n()2⑨ 如果Gl(Xa)-Gl(Xb)> ε/2 或者 ε/2 < τ⑩ 在l下面添加一个在Xa拆分的节点,属性Xa为该节点的决策属性 将产生一个新的分支,产生新的叶子节点 实例统计数量nl=0

Fig.1 pseudo-code of McTree algorithm

图1 McTree算法伪代码

本节主要针对Hoeffding不等式存在的不足,提出并设计了一种基于McDiarmid不等式的数据流决策树分类算法(McTree)。在进行分类的时候,得到的结果并不是很理想。然而为了得到更好的分类精度,本算法设计使用ε/2进行属性分类度量,最终使得实验分类效果更好。实验的对比结果将在第3节重点描述和分析。

3 实验设计与分析

为了验证McTree算法的可行性和分类性能,本节进行了相应的7组实验。实验运行环境的CPU为2.2 GHz,内存为16 GB,操作系统是Win10专业版,所有的实验采用Java语言实现。实验中采用两类数据。一是来自于UCI[35]数据集的真实数据流,二是通过在MOA(大规模在线分析平台)生成的数据流。本文使用VFDT[14]、HOT[15]、ARFHoeffdingTree[24]、EFDT[25]和McTree算法分别在8个数据流上运行,实验结果将在3.2节重点描述与分析。

3.1 真实与虚拟数据流

本文使用各种各样的数据流进行评估,其中有真实数据流和生成数据流,大部分是MOA数据流生成的数据流,以弥补缺乏大型公开可用的真实数据流。

本实验共用到8个数据流:其中kddcup99是真实数据流,来自于UCI数据集。kddcup99数据流共1 000 000条数据,就是KDD竞赛在1999年举行时采用的数据流。其余7个数据流分别是RTS、RTC、LED、Wave、RRBFS、RRBFC和Hyperplane,均是1 000 000条数据。它们是通过数据流在线分析平台MOA生成的合成数据流。RTS和RTC是简单和复杂的随机树概念,基于文献[10]中描述的生成方法,添加10%的噪声。RTS的最大层数为5,叶节点从3级开始,之后出现叶节点的概率为0.15;最后一棵树有741个节点,其中509个是叶子。RTC的最大层数为10,叶节点从5级开始;最后一棵树有127 837个节点,其中90 259个是叶子。每个名称属性有5个可能的值。Hyperplane数据流由10个数值属性组成,两个类别,共1 000 000条数据流。LED数据流包含25个属性,其中17个属性为无关属性,在该数据流中前7个属性为漂移属性维,共包含1 000 000个事例及10个不同的类标签[36]。Wave数据流包含22个属性,前21个属性在实数范围内取值,共含有3个不同的类标签及1 000 000条事例,该数据流含有5%的噪声。RRBFS是一个简单的随机RBF(径向基函数)数据流,由100个中心、10个属性和2个类组成。RRBFC是一个包含1 000个中心,50个属性和2个类的复杂版本[15]。表1列出了实验中各个数据流的属性类型、属性数量和类数目。

表1 数据流属性

3.2 实验结果

在下列实验中,VFDT[14]、HOT[15]、ARFHoeffdingTree[24]、EFDT[25]和McTree均在MOA上运行。同时分别在7组参数下运行得出实验结果。本实验参数设置分别为:①nmin=100,δ=1.0E-4;②nmin=200,δ=1.0E-4;③nmin=300,δ=1.0E-4;④nmin=400,δ=1.0E-4;⑤nmin=500,δ=1.0E-4;⑥nmin=1 000,δ=0.1.0E-4;⑦nmin=200,δ=1.0E-7。其中,nmin代表叶节点最小分裂数,δ代表分裂置信度。决策树算法主要从生成树规模(tree (nodes)、tree (leaves)、tree (depth))、运行时间(Time)、分类准确率(accuracy(%))等几个方面对算法性能进行评价。

在实验过程中,不同参数下的实验结果大同小异,因此本实验对结果进行抽取记录。即在LED数据运行得到的结果来自参数①,在Wave、RRBFC数据运行得到的结果来自参数②,在kddcup99数据运行得到的结果来自参数④,在RTS数据运行得到的结果来自参数⑤,在RRBFS数据运行得到的结果来自参数⑥,在Hyperplane、RTC数据运行得到的结果来自参数⑦。因此,VFDT、HOT、ARFHoeffdingTree、EFDT和McTree使用上述数据流在MOA上运行得到的分类结果如表2和表3所示。

(1)生成树规模对比实验

McTree和VFDT算法[14]分别在8个不同数据流上进行实验对比。首先,RTC、RRBFC和Hyperplane数据流生成的树规模减小最明显,生成树节点和叶节点均基本变为原来的20%左右;RRBFC数据流生成的树层数变为原来的20.2%、Hyperplane数据流生成的树减少4层、RTC数据流生成树减少1层。其次,Wave和RRBFS数据流生成的树规模减小也特别明显,生成树节点和叶节点变为原来的30%左右;生成树层数分别减少7层和12层。LED、RTS和kddcup99数据流生成的树节点和叶节点数目相比原算法基本减少50%,RTS和kddcup99数据流生成树分别减少2层。

McTree和HOT[15]算法分别在7个不同数据流上进行实验对比。除了LED数据流生成树规模为原算法的28%。在其它数据流上,生成树节点均为原算法的10%左右,同时生成树层数也明显减少。其中,RRBFC数据流生成树层数减少35层,RRBFS和Wave数据流生成树层数也分别减少了58%和56%。

McTree和ARFHoeffdingTree[24]算法(后面出现使用ARF)分别在8个数据流上进行实验。通过观察,除了kddcup99数据流生成树减小为原算法的一半,RTS和RRBFS数据流生成树为原算法的20%。在其它数据流的生成树节点数均为原算法的10%以下。

McTree和EFDT[25]算法分别在8个数据流上进行实验。首先,Hyperplane、Wave和RRBFC数据流生成树节点减小最明显,基本变为原算法树节点数目的20%左右,Hyperplane和RRBFC数据流生成树层数均减少4层。在kddcup99数据流生成树规模减小不是很明显,但是也减少为原算法的68%。总体而言,McTree算法生成树规模还是比原算法减小一半以上。VFDTHOT、ARFHoeffdingTree、EFDT和McTree算法生成树规模比较如表2所示(其中生成树规模最小的数据已加粗标注)。

(2)算法分类性能对比实验

首先,ARF[24]与其他4个算法相比,虽然在运行时间上用时最少,但是生成树规模与其它算法相比大很多,而且分类精度均低于其它算法。因此,McTree算法与ARF相比,除了运行时间长,在精度和生成树规模方面均好于ARF算法。

McTree和VFDT[14]算法分别在8个不同数据流上进行实验。首先从运行时间上去分析,除了RRBFC和kddcup99数据流的运行时间比VFDT算法的时间略微变长,其余6个数据流的运行时间均是减少或者不变的,并且RTC数据流的运行时间减少最为明显,相比减少了6 s。通过观察各个数据流在VFDT和McTree算法上的分类精度,除了RTS数据流分类精度降低1.25%,RRBFS和RRBFC的精度降低2%左右,在其它数据流上准确率均升高。

表2 VFDT, HOT, ARF, EFDT与McTree生成树规模比较

McTree和HOT[15]算法分别在7个不同数据流上进行实验。McTree算法在所有数据流的运行时间均降低,平均运行时间降低50%左右。通过观察各个数据流在HOT和McTree算法上的分类精度,除了在RTS、RRBFS和RRBFC 3个数据流的分类精度降低2%左右,在其它四个数据流上的分类精度均升高。

McTree和EFDT[25]算法分别在8个数据流上进行实验。McTree算法在所有数据流的运行时间均降低,其中最明显的是在RRBFC数据流上从79 s降低到43.91 s,减少了35.09 s的运行时间。然而在分类精度方面,除了在RTS数据流分类精度降低1.43%,在RRBFS数据流降低0.89%之外,在其它6个数据流上均精度升高,其中在RRBFC数据流上精度提升2.59%。VFDT、HOT、ARFHoeffdingTree、EFDT和McTree算法性能比较如表3所示(其中运行时间最短、分类精度最高的数据已加粗标注)。

表3 VFDT, HOT, ARF, EFDT和McTree算法的性能比较

以上两组实验是在七组不同参数下得出,在McTree和经典算法性能对比实验中,除了RRBFS和RRBFC两个数据流在实验中分类精度有所下降(2%左右),其它数据流的分类精度均提升。其次观察生成树规模,无论是节点数目和生成树层数、运行时间都降低特别明显,因此在一定程度上减小算法的时间复杂度和内存。通过对比VFDT、HOT、ARFHoeffdingTree、EFDT和McTree算法,得出在分类精度基本不变的情况下,生成树节点数平均降低70%左右,树层数平均降低50%左右。

4 结束语

数据流处理问题在近十几年来得到了一定的发展。本文针对Hoeffding不等式存在的缺陷,在前人研究的基础上提出了一种基于McDiarmid不等式的数据流决策树分类算法。该算法中使用了McDiarmid不等式来作为决策树分割准则的统计工具；设计使用ε/2进行属性分类度量。对比VFDT、HOT、ARFHoeffdingTree、EFDT和McTree算法的实验结果,明显看出在使得生成的决策树大小明显降低的情况下,分类准确率提高或者几乎保持不变,本文的不足之处是在生成决策树大小明显降低的情况下,其中有个别数据流的准确率略有下降。这是下一步工作中需要解决的问题。预期目标是在生成模型树的尺寸明显降低的情况下,使得算法准确率普遍提高。