基于数据流的数据挖掘研究

[摘 要] 由于数据流自身的特性，数据流挖掘已经成为数据挖掘的一个新的研究方向，在介绍数据流的概念的基础上，分析了数据流挖掘的概念和模型，总结了现有的数据流挖掘算法。

[关键词] 数据流 数据流挖掘 模型 算法

近年来，随着计算机技术和通信网络技术的蓬勃发展，由于众多应用领域的需求，数据流处理问题，特别是基于数据流的挖掘问题已受到越来越多的研究人员关注。

一、数据流以及数据流挖掘

1.数据流。数据流由一系列按序到达的数据组成，也可看作是信息传输过程中经编码处理的数字信号串。若令t表示任一时间戳，at表示在t时刻到达的数据元素，则数据流可以表示为无限集合{…，at-1，，at，at+1，…}。

2.数据流挖掘。数据流挖掘就是在数据流上发现提取隐含在其中的。人们事先不知道的，但又潜在有用的信息和知识的过程。流数据挖掘方面的研究主要包括多数据流挖掘和单数据流挖掘，挖掘多条数据流的主要目的是分析多条并行到达的数据流之间的关联，对单数据流的挖掘则涵盖了分类、频繁模式挖掘、聚类等多项传统数据挖掘中的主要任务，挖掘变化的数据流是一项特殊的任务，目前主要是以单数据流为对象进行研究的。

二、数据流挖掘的模型

按算法处理数据流时所选取的时序范围，数据流模型可分为以下几类。

1.快照模型:处理数据的范围限制在两个预定义的时间戳之间。

2.界标模型:处理数据的范围从某一个已知的初始时间点到当前时间点为止。

3.滑动窗口模型:处理数据的范围由某个固定大小的滑动窗口确定,此滑动窗口的终点永远为当前时刻，其中,滑动窗口的大小可以由一个时间区间定义,也可以由窗口所包含的数据项数目定义。

典型的数据流挖掘模型如图所示。

三、数据流挖掘算法

目前数据流挖掘方面的研究成果主要集中在数据流的聚类、分类和频繁模式挖掘方面。

1.数据流分类算法。数据流分类就是提出一个分类模型(或函数）,并通过单遍扫描数据流,持续地利用分类模型将数据对象（数据流的数据点或元组等)映射到某一个给定的类别中。P.Domingos 和 G..Hulten他们提出了一种Hoeffding决策树分类算法VFDT(Very Fast Decision Tree),使用恒定的内存大小和时间处理每个样本,有效地解决了时间、内存和样本对数据挖掘，特别是高速数据流上的数据挖掘的限制。VFDT使用信息熵选择属性,通过建立Hoeffding树来进行决策支持,并使用 Hoeffding 约束来保证高精度地处理高速数据流。

由于VFDT算法假设数据是从静态分布中随机获取的，所以不能反映数据随时间变化的趋势。因此，P.Domingos和G..Hulten引入了滑动窗口技术,对VFDT算法进行改进,提出了CVFDT (Concept-adapting Very Fast Decision Tree)算法，除了保留VFDT算法在速度和精度方面的优点外，增加了对数据产生过程中变化趋势的检测和响应,使得算法更好地适应对高速时变流数据的分类。

2.数据流聚类算法。流数据本身所具有的特征使得传统的聚类算法不可能直接应用于(甚至不能应用于)流数据聚类， 数据流聚类算法就是通过单遍扫描数据流，持续地将数据流数据对象（数据点、元组等）分组成多个类或簇，在同一个簇中的数据对象之间具有较高的相似度，而不同簇间的数据对象的相似度很小。近年来，学者们提出的应用于大规模数据集的一趟聚类算法，如Squeezer算法和BIRCH算法，也可以应用于某些数据流问题，也有学者提出了针对流数据的聚类算法，典型的有STREAM算法和CluStream算法。

3.数据流频繁模式挖掘算法。数据流频繁模式挖掘就是单遍扫描数据流，来连续地发现其中的频繁项集。频繁项集是满足最小支持度的项集(Itemset）。对于数据流上的频繁项集挖掘的研究方法大多数都采用ε-算法和基于FP-tree模型的有效算法FP-stream。FP-stream算法采用倾斜时间窗口技术来维护频繁模式以解决时间敏感问题，研究了在数据流中构造、维护和更新 FP-stream 结构的有效算法，提出了计算和维护所有频率模式并动态更新它们。建立一个框架来挖掘带近似支持度的时间敏感模式，为每个模式在多时间粒度上增量维护一个倾斜时间窗口,在这种框架下可以构建和回答感兴趣的查询。

四、结语

由于数据流具有独特的性质，对其进行挖掘是一个挑战性的问题，当前的有关算法的研究有很多是在传统的增量式挖掘技术基础之上发展而来的，探索数据流挖掘技术与传统的静态数据挖掘技术之间的本质区别，提出更有效、新颖、快速挖掘算法是当前研究面临的重要问题。

参考文献:

[1]Gibbons P B，Matias Y:New sampling based summary statistic for improving approximate query answers[A].Proc of the ACM SIGMOD Int’l Confon Management of Data [C].Seattle:ACMPress，1998.331～342

[2]金澈清 钱卫宁 周傲英:流数据分析与管理综述.软件学报,2004,15(8):1172～1181

[3]Domingos.P,Hulten.G.Mining high-speed data streams[C].Proc of ACM SIGKDD Int Conf Knowledge Discovery in Databases(KDD'00)，2000.71～80

注：本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文