论文部分内容阅读
摘要：数据挖掘迎来黄金时代，静态数据上的分类技术已不能满足现实情况的需要了。大量的数据都是以数据流的形式出现，该文对数据流分类算法进行分析。所描述的主要算法有：Hoeffding树算法、快速决策树算法、概念自适应快速决策树、组合分类器、ID4算法。通过学习研究和实验对比结果发现，这些数据流上的分类算法依然有改进。
关键词：数据流；分类算法；概念漂移
中图分类号：TP311文献标识码：A文章编号：1009-3044(2012)11-2445-02
Analysis of Classification Algorithms of Data Stream
BAI Xue-bing, WANG Bao-jun
(Zhejiang Institute of Communications, Hangzhou 311112, China)
Abstract: With the coming of golden age of data mining , static data classification technology cannot meet the real needs of the situation. Large amounts of data are based on data stream，this article mainly describles the classification algorithms.The main algoriflims includes ensemble classification，Hoeffding tree, ID4 and VFDT.Through the study of research and experimental comparison of the results，these gorithms performance still need improve.
Key words: data stream; classification algorithm; concept drift
1数据流分类概述
想象一个人造卫星上的遥感器不断的产生数据,其数据是海量的，而且是不断变化的无限的，这是数据流(Data Streams)的一个例子,它就像流动的水一样源源不绝。数据流技术作为数据挖掘中刚刚兴起的技术，越来越多数据挖掘专家关注它，开发数据流模型的信息管理系统及其相应算法已成为许多数据挖掘专家所要攻克的难题。高效、可行的数据流算法，可以使得在给定的有限的运行空间上，对数据流进行一次或较少次数的线性扫描，就可以实现数据挖掘的功能。
数据流分类是在数据流挖掘的一个分支。传统的数据分类方法是一种基于监督的学习方法，它可以分为两个过程来实现的：训练过程和检测过程。在训练过程中，采用一种数据模型通过一组数据集上对该模型进行训练，建立一个可以用于模型测试的数据模型，检测过程则是通过其他数据对该模型进行测试。常规的神经网络的分类算法，支持向量机的分类算法等等算法都是如此。但是这样的算法对数据流分类来说是不够的，因为数据流是源源不断的，一般对数据只能进行一次扫描，另外数据流分类算法的设计还要考虑到数据流处理中独有的“概念漂移”的问题，这导致传统的分类算法不可用。
数据流技术的所开发出来的软件可以被广泛地使用。工业控制软件，金融商业软件都很需要数据流的挖掘。
2数据流分类算法的基本要求
数据流是实时、连续、有序、时间变化的、无限的序列。数据流具有以下特点：时间顺序的，快速变化的，无限的，不可再现的。由于数据流的数据量太大，没有任何数据库可以容纳它,并且可以不断地对它进行扫描。因此如果想对数据流进行数据挖掘挖掘，必须开发能单遍扫描的，高效的算法。因此数据流分类算法需要满足以下条件。
首先该算法能够适应快速到达的信息，算法还要能满足一次读取的约束。同时该算法必须具有较小的时空复杂度。
其次该算法最好能解决数据漂移问题。数据漂移问题又称概念漂移，它是数据分类器的精度随着时间的不断前移而不断降低。因为随着时间的变化，流过来的数据模式是可能是不断变化的,。如果这种数据流分类算法能将数据的这种模式变化可以捕捉到，那么就可以提高分类器的更新效率。随着时间的变化，如果一个分类器失效的话，那么他的效率会很低。
最后该算法能够识别与响应数据流的变化。数据流变化可分为显著变化和噪声变化。显著变化是指数据流模式发生变化,噪声变化只是数据流模式没有改变只是数据流有轻微变化。一个好的分类算法应能对显著变化反应,而对噪声变化无反应。
3数据流基本分类算法
3.1 Hoeffding树算法
Hoeffding树算法是一种用于数据流分类的决策树算法.，它基于如下思想：小样本数据通常足以选择最佳分裂属性。这在数学上被称为Hoeffding界。该算法与传统的批处理方法决策树近似，以高概率确定在一个节点分裂属性时所需要的样本最小数量N。Hoeffding树最佳分类属性的选择是以使用的样本数超过了Hoeffding界限为标准的。
Hoeffding树算法除了高准确率之外，它对同一数据不会多次扫描。这一点很重要，因为数据流太大了不能储存。另外算法是增量的这也是优点之一。
但是Hoeffding树算法也有缺点，概念漂移问题处理得不是很好。
3.2快速决策树算法(VFDT)和概念自适应快速决策树(CVFDT)
快速决策树算法(VFDT)是一种基于Hoeffding数的决策树系统。该算法对Hoeffding树做了一些修改以提高速度与内存利用率。VFDT算法的高效性在于，它只依赖于整个数据的部分子样本就可以处理每一个决策树的节点，对整个流数据只作一次扫描，尽管它得到的只是一个近似的解，但是对数据流分类已经足够。VFDT算法优点在于它是使用信息熵作为选择属性，通过建立Hoeffding树来进行决策支持，并使用Hoeffding界来处理高速数据流。它的结果良好,效率高。VFDT可以对数据集进行二次扫描，可以方便应用于较大数据集的分类,随时可用,不断优化，但VFDT不是很好的能解决概念飘移问题。针对VFDT的问题，以VFDT为基础，人们又提出概念自适应快速决策树（CVFDT），CVFDT中除了保留了VFDT所有优点特性之外，引入了滑动窗口技术，当存在概念漂移时，一些节点不满足Hoeffding界时，CVFDT将产生另一颗替代的子树，随着数据的流入，当替代的子树比已有的子树更准确，旧的子树将被替代它。
3.3组合分类器
组合分类器的基本思想是从数据流的相继块训练一组分类器，这种算法是基于使用一组分类模型，如C4.5、朴素贝叶斯等分类模型。由于组合分类器是当一个新的数据块到来时,由他建立一个新的分类器。这样不断的训练，单个分类器根据其在随时间变化训练的环境中按照分类准确率加权,最后组合分类器仅保留最高的几个分类器。然后根据这些分类器的加权投票做出决策来决定组合分类器。相对单一分类器而言，实验表明，组合分类器比单个分类器性能好很多。组合分类器有以下优点：1）预测精度高；2）高效率；3）并行扩展和在线分类大规模数据；4）可以避免过度拟合问题。为什么这种方法有用,因为决策树算法不是解决概念漂移的自然方法，但是朴素贝叶斯却没有这个缺点，通过组合分类器模型可以达到很好的效果。
3.4 ID4算法
ID4是增量决策树学习算法，根据每个样本更新决策树。该增量学习方法的理论基础是信息论中的知识：评估不需要所有的样本获取，只需要其中的一个子集而已。ID4算法旨在增量式的构造决策树，每接受一个新的训练实例就更新一次决策树。
在ID4的决策树中，每个节点都保存了可以用于计算信息增益的值得信息，这些信息包裹属性的每个取值得所对应的正例数与反例数。根据节点的信息，就可以判断出那个属性信息增益最大，从而确定那个属性来划分。
ID4不需要保存样本值，所有的样本值都被由于计算信息增益，当各属性间有统计意义上的区别时，就可以选定根节点的测试属性。但随着新样本的不断到达，可能会出现一个新属性比某个子树的根节点的测试属性具有更大的增益的情形。因此如果实例组织不恰当，就会造成算法低效，不能稳定学习。
4结束语
该文介绍了数据流分类中要解决的问题和基本的数据流分类算法。该文对提到的这些算法作了说明与总结。该文所提及的技术可以效地解决数据流分类所产生的问题，但是这些算法依然有局限性,许多数据流分类问题还不能同时被一个方法解决。数据流分类问题仍然有许多的问题要解决，特别是在概念漂移和资源限制方面，矛盾十分突出。
参考文献：
[1]王涛.数据流挖掘分类方法关键技术研究[D].长沙:国防科学技术大学,2007.
[2]黄树成，曲亚辉.数据流分类技术研究综述[J].计算机应用研究,2009(10):3605-3611.
[3] Tan Pang—Ning,Steinbach M,Kumar V.数据挖掘导论[M].范明,范宏建,译.北京:人民邮电出版社,2006.
[4]梁循.数据挖掘算法与应用[M].北京:北京大学出版社,2006.
[5]倪志伟.动态数据挖掘[M].北京:科学出版社,2010.
关键词：数据流；分类算法；概念漂移
中图分类号：TP311文献标识码：A文章编号：1009-3044(2012)11-2445-02
Analysis of Classification Algorithms of Data Stream
BAI Xue-bing, WANG Bao-jun
(Zhejiang Institute of Communications, Hangzhou 311112, China)
Abstract: With the coming of golden age of data mining , static data classification technology cannot meet the real needs of the situation. Large amounts of data are based on data stream，this article mainly describles the classification algorithms.The main algoriflims includes ensemble classification，Hoeffding tree, ID4 and VFDT.Through the study of research and experimental comparison of the results，these gorithms performance still need improve.
Key words: data stream; classification algorithm; concept drift
1数据流分类概述
想象一个人造卫星上的遥感器不断的产生数据,其数据是海量的，而且是不断变化的无限的，这是数据流(Data Streams)的一个例子,它就像流动的水一样源源不绝。数据流技术作为数据挖掘中刚刚兴起的技术，越来越多数据挖掘专家关注它，开发数据流模型的信息管理系统及其相应算法已成为许多数据挖掘专家所要攻克的难题。高效、可行的数据流算法，可以使得在给定的有限的运行空间上，对数据流进行一次或较少次数的线性扫描，就可以实现数据挖掘的功能。
数据流分类是在数据流挖掘的一个分支。传统的数据分类方法是一种基于监督的学习方法，它可以分为两个过程来实现的：训练过程和检测过程。在训练过程中，采用一种数据模型通过一组数据集上对该模型进行训练，建立一个可以用于模型测试的数据模型，检测过程则是通过其他数据对该模型进行测试。常规的神经网络的分类算法，支持向量机的分类算法等等算法都是如此。但是这样的算法对数据流分类来说是不够的，因为数据流是源源不断的，一般对数据只能进行一次扫描，另外数据流分类算法的设计还要考虑到数据流处理中独有的“概念漂移”的问题，这导致传统的分类算法不可用。
数据流技术的所开发出来的软件可以被广泛地使用。工业控制软件，金融商业软件都很需要数据流的挖掘。
2数据流分类算法的基本要求
数据流是实时、连续、有序、时间变化的、无限的序列。数据流具有以下特点：时间顺序的，快速变化的，无限的，不可再现的。由于数据流的数据量太大，没有任何数据库可以容纳它,并且可以不断地对它进行扫描。因此如果想对数据流进行数据挖掘挖掘，必须开发能单遍扫描的，高效的算法。因此数据流分类算法需要满足以下条件。
首先该算法能够适应快速到达的信息，算法还要能满足一次读取的约束。同时该算法必须具有较小的时空复杂度。
其次该算法最好能解决数据漂移问题。数据漂移问题又称概念漂移，它是数据分类器的精度随着时间的不断前移而不断降低。因为随着时间的变化，流过来的数据模式是可能是不断变化的,。如果这种数据流分类算法能将数据的这种模式变化可以捕捉到，那么就可以提高分类器的更新效率。随着时间的变化，如果一个分类器失效的话，那么他的效率会很低。
最后该算法能够识别与响应数据流的变化。数据流变化可分为显著变化和噪声变化。显著变化是指数据流模式发生变化,噪声变化只是数据流模式没有改变只是数据流有轻微变化。一个好的分类算法应能对显著变化反应,而对噪声变化无反应。
3数据流基本分类算法
3.1 Hoeffding树算法
Hoeffding树算法是一种用于数据流分类的决策树算法.，它基于如下思想：小样本数据通常足以选择最佳分裂属性。这在数学上被称为Hoeffding界。该算法与传统的批处理方法决策树近似，以高概率确定在一个节点分裂属性时所需要的样本最小数量N。Hoeffding树最佳分类属性的选择是以使用的样本数超过了Hoeffding界限为标准的。
Hoeffding树算法除了高准确率之外，它对同一数据不会多次扫描。这一点很重要，因为数据流太大了不能储存。另外算法是增量的这也是优点之一。
但是Hoeffding树算法也有缺点，概念漂移问题处理得不是很好。
3.2快速决策树算法(VFDT)和概念自适应快速决策树(CVFDT)
快速决策树算法(VFDT)是一种基于Hoeffding数的决策树系统。该算法对Hoeffding树做了一些修改以提高速度与内存利用率。VFDT算法的高效性在于，它只依赖于整个数据的部分子样本就可以处理每一个决策树的节点，对整个流数据只作一次扫描，尽管它得到的只是一个近似的解，但是对数据流分类已经足够。VFDT算法优点在于它是使用信息熵作为选择属性，通过建立Hoeffding树来进行决策支持，并使用Hoeffding界来处理高速数据流。它的结果良好,效率高。VFDT可以对数据集进行二次扫描，可以方便应用于较大数据集的分类,随时可用,不断优化，但VFDT不是很好的能解决概念飘移问题。针对VFDT的问题，以VFDT为基础，人们又提出概念自适应快速决策树（CVFDT），CVFDT中除了保留了VFDT所有优点特性之外，引入了滑动窗口技术，当存在概念漂移时，一些节点不满足Hoeffding界时，CVFDT将产生另一颗替代的子树，随着数据的流入，当替代的子树比已有的子树更准确，旧的子树将被替代它。
3.3组合分类器
组合分类器的基本思想是从数据流的相继块训练一组分类器，这种算法是基于使用一组分类模型，如C4.5、朴素贝叶斯等分类模型。由于组合分类器是当一个新的数据块到来时,由他建立一个新的分类器。这样不断的训练，单个分类器根据其在随时间变化训练的环境中按照分类准确率加权,最后组合分类器仅保留最高的几个分类器。然后根据这些分类器的加权投票做出决策来决定组合分类器。相对单一分类器而言，实验表明，组合分类器比单个分类器性能好很多。组合分类器有以下优点：1）预测精度高；2）高效率；3）并行扩展和在线分类大规模数据；4）可以避免过度拟合问题。为什么这种方法有用,因为决策树算法不是解决概念漂移的自然方法，但是朴素贝叶斯却没有这个缺点，通过组合分类器模型可以达到很好的效果。
3.4 ID4算法
ID4是增量决策树学习算法，根据每个样本更新决策树。该增量学习方法的理论基础是信息论中的知识：评估不需要所有的样本获取，只需要其中的一个子集而已。ID4算法旨在增量式的构造决策树，每接受一个新的训练实例就更新一次决策树。
在ID4的决策树中，每个节点都保存了可以用于计算信息增益的值得信息，这些信息包裹属性的每个取值得所对应的正例数与反例数。根据节点的信息，就可以判断出那个属性信息增益最大，从而确定那个属性来划分。
ID4不需要保存样本值，所有的样本值都被由于计算信息增益，当各属性间有统计意义上的区别时，就可以选定根节点的测试属性。但随着新样本的不断到达，可能会出现一个新属性比某个子树的根节点的测试属性具有更大的增益的情形。因此如果实例组织不恰当，就会造成算法低效，不能稳定学习。
4结束语
该文介绍了数据流分类中要解决的问题和基本的数据流分类算法。该文对提到的这些算法作了说明与总结。该文所提及的技术可以效地解决数据流分类所产生的问题，但是这些算法依然有局限性,许多数据流分类问题还不能同时被一个方法解决。数据流分类问题仍然有许多的问题要解决，特别是在概念漂移和资源限制方面，矛盾十分突出。
参考文献：
[1]王涛.数据流挖掘分类方法关键技术研究[D].长沙:国防科学技术大学,2007.
[2]黄树成，曲亚辉.数据流分类技术研究综述[J].计算机应用研究,2009(10):3605-3611.
[3] Tan Pang—Ning,Steinbach M,Kumar V.数据挖掘导论[M].范明,范宏建,译.北京:人民邮电出版社,2006.
[4]梁循.数据挖掘算法与应用[M].北京:北京大学出版社,2006.
[5]倪志伟.动态数据挖掘[M].北京:科学出版社,2010.