自适应模糊决策树算法在数据流挖掘中的应用

1、自适应模糊决策树算法在数据流挖掘中的应用朱参世，李响(空军工程大学工程学院，陕西西安710038)0引言数据挖掘是从大量数据中“挖掘”知识，旨在从大量数据中提取隐藏的预测性信息，发掘数据间潜在的模式，找出某些被忽略的信息，作为决策的依据。在网络的许多应用中数据是以流形式存在的。传统的数据挖掘方法是基于静态数据库的频繁模式，挖掘算法可以对数据库进行多次扫描，多次查找等。然而，数据流是大量连续到达、潜在无限的数据集合，其特点是：数据高速到达，数据流朱参世，李响(空军工程大学 工程学院，陕西西安 710038)0引 言数据挖掘是从大量数据中“挖掘”知识，旨在从大量数据中提取隐藏的预测性信息，发掘数据

2、间潜在的模式，找出某些被忽略的信息，作为决策的依据。在网络的许多应用中数据是以流形式存在的。传统的数据挖掘方法是基于静态数据库的频繁模式，挖掘算法可以对数据库进行多次扫描，多次查找等。然而，数据流是大量连续到达、潜在无限的数据集合，其特点是：数据高速到达，数据流无法再现，实时性要求高以及数据量无限增长等。因此，传统的数据挖掘不适合对数据流的挖掘。在数据流挖掘研究中，有许多经典算法，譬如：Manku提出的Lossy Counting算法，Han提出基于FP-growth的FP-stream算法等。数据流常用的处理与分析方法可归纳为数据流频繁项集挖掘算法、分类挖掘算法和聚类挖掘算法。但这些算法在处

3、理数据流时不同程度地产生概念漂移现象，在分类挖掘数据流时，必须考虑数据流的变化特征，要及时删除过时的类定义模式。在聚类算法中，数据流随着时间在不断地变化，其隐含的聚类可能随时间的动态变化而导致聚类质量的降低。本文提出一种改进的基于概念自适应模糊决策树算法，以解决数据挖掘中的概念漂移问题。1 快速决策树算法及其性能分析快速决策树算法(very fast decision tree，VFDT)的目标是通过已有的训练样本得出一个分类模型y=f(x)，对新测试样本进行正确分类。VFDT是一种基于Hoeffding不等式，并针对数据流挖掘环境建立分类决策树的方法，它通过不断地将叶节点替换为分支节点，而生

4、成决策树，其所研究的样本属性为离散属性。1.1 快速决策树算法的过程快速决策树算法过程如下：(1)快速决策树(VFDT)的构建是从根节点开始的，根节点即为最初的叶节点。若s为一数据流序列，包含潜在无限多的样本数据，则误差参数由用户在初始时刻给出。样本的不同属性字段由属性集合X1，X2，Xk表示，k表示属性的个数。(2)当样本数据依次流入VFDT系统时，起初所有的样本数据都聚集在决策树的根节点。随着根节点样本数据的增多，信息增益不断增长。用nt表示从零时刻到t时刻流入的样本总数。(3)以信息增益为属性选择度量，当t时刻聚集在根节点的样本数量为nt时，可以计算各属性的信息增益。若属性Xa的平均信息

5、增益Gain(Xa)最大，属性Xb的平均信息增益次之，并令：若Gain，则由Hoeffding界可以保证选择属性X作为根节点的分裂属性在概率1-下得到保证，且真正的信息增益之差GainGain-0在概率1-下得到保证。因此，根据Hoeffding界便可以确定在根节点聚集的样本数量nt，可进行属性分裂，这便是Hoeffding树算法通过小样本选择最佳分裂属性的过程。(4)决策树生长。若式(1)得到满足，则根节点将根据最佳分裂属性Xa生长出子节点，并在其子节点中的备选属性集中删除属性Xa，此过程递归进行。由于数据流的潜在无限性，如果不加限制，决策树将无限制增长下去，若确定了树的最大深度或其他度量指

6、标后，VFDT将通过最新到来的样本数据对决策树进行增量更新，以保持其判断的准确性。(5)对内存进行优化。在Hoeffding树算法的基础上，通过VFDT在内存的优化方面做出改进，在当前数据占满内存空间时，VFDT系统将暂时解除对分类决策影响最小的子节点所使用的空间。对于暂时失去活性的子节点，若后来其分类准确率较之当前的活跃节点高，将再次恢复其活性。(6)打破平局。当最佳分裂属性与次佳分裂属性的平均信息增益之差很小时，传统的Hoeffding树算法将在属性选择上花费大量的时间。VFDT算法引入了一个界限参数(由用户提供)，若Gain<时，选择增益最大的属性为分裂属性。(7)处理速度优化，在

7、步骤(3)中，传统的Hoeffding树算法会在每一个样本到达时进行一次分裂属性测试，这将极大地影响系统的计算效率。VFDT系统引入了一个分裂属性最小样本数nmin(由用户提供)，当到达节点的样本数为nmin的整数倍时才进行测试。1.2 快速决策树算法分析VFDT算法利用Hoeffding界，以高概率确定在1个节点选择分裂属性时需要的样本最小数量，这个属性将与使用无限样本得到的属性一样。由于快速决策树算法的分类精度与单纯样本数量无关，其需要维护的惟一统计量是具有类标号yk属性Ai值vj的计数nijk。因此，若d是属性的个数，v是属性值的最大个数，c是类的个数，l是树的最大深度，则内存总需求为O

8、(ldvc)。与其他决策树算法相比，这一内存需求是适度的，因此可实现对实时增量数据流的处理。但是，由于VFDT算法没有考虑概念漂移问题，因此将VFDT算法直接对广泛存在概念漂移的网络数据流进行分类时，会出现很大偏差。另外，随着时间的推移和概念漂移的产生，VFDT树中将积累大量过时的样例，使得VFDT树变得非常臃肿。2 快速决策树算法优化方法对于概念漂移问题，可在原决策树的生长过程中予以解决，即若有节点出现分类不准，则在相应节点旁派生出一颗替代子树(Talt)。当替代子树生长到足以对新到样本进行准确分类时，将替代原树中相应的子树。2.1 优化后算法的执行过程(1)优化后的算法核心决策树仍然是Ho

9、effding树。其原因是Hoeffding决策树能够依靠Hoeffding界原理，以小样本替换无限样本，构建高效增量决策树，并只需对数据流进行一次扫描，这符合应用需求。(2)优化后的算法保持了VFDT系统的处理速度和准确度，并引入了对新到样本发生概念漂移时的响应机制。在算法中，加入了滑动窗口W，当新样本到达时，将其加入滑动窗口。滑动窗口的任务是当有新样本到达时，靠增加决策树相应节点中的计数来回应新样本特性。与此同时，减少旧样本或过时样本中相应的计数来维持一个最新的分类模型，而不是一有新样本到达就创建一个新模型。(3)优化后的算法中对滑动窗口进行了改进，对每个数据流样本引入1个影响因子0，1。

10、值的作用是用来判断决策树的分类效用，并根据其取值的不同来影响滑动窗口中样本的计数值，进而对滑动窗口的大小进行动态调整。在改进的滑动窗口中，对流过样本的计数则基于影响因子的计数nijk。当决策树中，某个样本分类出现偏差时。该样本在滑动窗口中的影响因子将在01的范围内，趋于0的程度正比于偏差节点与根节点的距离，可以用树深z(出现偏差的层数)来表示，即l。相反，当实际分类为正确分类时，=1。在滑动窗口中设定1个阈值(如0.5)，设W为滑动窗口中的样本计数，W0，nijk，并规定当满足：说明发生明显概念漂移，锁定出错节点，构造替代子树，并缩小滑动窗口的大小，直到下式成立；成立，并至少在T(人为界定)个

11、窗口周期内保持稳定，此时以W2增量递归扩大滑动窗口的大小，直到到达式(2)的临界点时停止。(4)优化后的算法将根据滑动窗口中有效样本的数量来判断分裂的有效性，即：若式(2)满足，将重新计算在滑动窗口出现严重分裂偏差的节点中各属性的模糊信息增益。若当内部某节点在向下分类且滑动窗口中相应样本点的影响因子较前一样本点快速趋于0时，说明在对该样本点进行分类时发生了概念漂移。这说明该节点的属性测试出现了偏差，此时将有1棵替代子树产生。若一新样本属性Xnew的模糊信息增益高于当前的分裂属性Xcurr,则优化后的算法将在相应节点处以属性Xnew为根节点生成1棵替代子树。(5)对属性分裂效用的判断，将改进VF

12、DT算法中的方法。使用模糊信息增益的方法可周期性地检测最佳分裂属性。由于现实网络数据流中存在大量的噪声数据或非确定信息，即便是对于某些离散属性字段，采用传统的陡峭属性分裂方法也会导致分类界限不清晰。因此，改进后的算法，对于离散属性和连续属性都采用模糊信息增益作为属性选择度量。(6)替代子树生长过程控制。为提高内存利用率，替代子树也需要控制其规模，并进行适当剪枝。剪枝的判断标准以原子树与替代子树间分类的准确度增量大小为依据。优化后的算法规定，若替代子树满足式(5)，将对其保留；否则，将删除该替代子树。式中：i为原树和替代树中的节点编号；为替代子树保留的阈值。式(5)中，准确度可用该节点正确分类样

13、本数与流经该节点总样本之比来定义，即：2.2 优化流程如图优化流程如图1所示。3优化算法验证由于本文研究的是数据流环境下的挖掘算法，为了验证算法的有效性，必须对静态数据集进行动态化处理。根据流数据区别于静态数据的潜在无限、动态变化，以及对流数据的处理单遍扫描、实时处理等特点及要求进行动态处理。另外，由于在网络传输过程中传输数据将受到自然环境和电磁环境的干扰，因此在实验中将向每组实验数据加入5的噪声数据。在实际操作中，从数据集中随机顺序抽取100万条样本作为测试数据，初始属性数为5，每增加10个属性检测1次结果，经Matlab仿真后的效果图如图2所示，图中标出了随着用于分类的属性增多，概念漂移的变化情况。4 结 语改进算法引入了滑动窗*术，滑动窗口中的所有样本都可以全部放入内存，并通过窗口机制来实时判断系统对外围数据的分类效果。因此，其效率与样本总数无关。另外，滑动窗口的引入也使得改进系统所生成的分类模型始终与当前情况相适应，改善了概念漂移对前面分类模型的影响。另