数据流挖掘技术研究

王大将，孙 洁

（1.南京陆军指挥学院 作战实验中心，南京 210045，2.常州技术师范学院 计算机系，江苏 常州 213001）

数据流挖掘技术研究

王大将1，孙 洁2

（1.南京陆军指挥学院 作战实验中心，南京 210045，2.常州技术师范学院 计算机系，江苏 常州 213001）

数据流挖掘技术是数据挖掘技术的新研究方向之一。文章介绍了数据流、数据流挖掘的特点，对现有的数据流挖掘算法进行了总结、分析，提出了数据流挖掘的研究方向和应用前景。

数据流；数据流挖掘；聚类；分类；频繁模式

0 引言

近年来，随着软硬件技术的高速发展，人们获取数据的能力得到了很大的提高，获取数据的领域越来越广。经常有大量需要处理的数据以很快的速度产生。由于数据量太大、而且数据产生的速度太快，如果仍然按传统的数据库应用模式来处理这些数据，则这样的任务将是不可能完成的。于是，一种新型的解决方案应运而生，其最大特点是，待处理的数据以一种动态、流式的形式出现，即数据流(Data Streams)，对数据流中的数据只能按顺序进行一次或有限次的访问[1]。与传统的静态存储在磁盘上的数据相比，数据流具有连续快速、短暂易逝以及不可预测等特点，因此对数据流的处理必须要实时地进行，并且无法直接访问所有的数据，只能存储数据的摘要信息。数据流的这些特性使得传统的数据挖掘算法不再适用，基于数据流的挖掘算法也就成了当前的研究热点和难点。

1 数据流

所谓数据流就是大量连续到达的、潜在无限的、随时间不断变化的数据有序序列，令t表示任一时间点，dt表示在该时间点到达的数据，则数据流可表示为{…,dt-1,dt,dt+1,…}。这些数据或其摘要信息无法全部保存在内存中，只能按照顺序存取并被读取一次或有限次。许多应用领域，例如通信领域的通话记录数据分析、网络流量分析、电子商务和在线股票交易数据分析、气象卫星数据分析等等都面临着如何分析和处理数据流的问题，都要求在海量、连续、快速到达的数据流上应用高级的数据分析和数据挖掘技术以捕捉趋势、模式、变化、孤立点等知识。

数据流具有与传统数据库模式下的数据集合不同的特征：数据流中的数据是随着时间的推进而连续不断产生的，其总量潜在无限；数据流中的数据是动态变化的；数据流中数据的到达次序是不可控制的，对数据流中数据的读取与处理只能被动地依据数据的到达次序进行，不可能通过改变数据的输入次序来对处理的结果进行改进。由于数据流具有时效性、实时性、无限性和瞬时性等特点，在处理数据流时，必须注重时空性，对数据流中的数据通常只能采取单一扫描的线性算法，用精度换时间，尽量在对数据的一次访问中获得较优的解。一些传统数据库应用中常用的操作，如排序、找最值、计数等在数据流处理中是不可行的，并且一般的数据流算法是不可回溯的。

2 数据流挖掘技术

数据挖掘也称为知识发现，就是从大量的、不完全的、有噪声的、模糊的、随机的实际应用数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识的过程。数据流挖掘就是从连续不断的数据流中提取潜在有用的信息和知识的过程。

针对数据流的特殊性，许多传统的数据挖掘算法不适合于数据流的挖掘，数据流的数据挖掘系统应满足以下标准：处理单条记录的平均时间要短，否则数据的处理会落后于数据的产生；使用的内存数量是相对固定的，与数据的量是没关系的；一条数据记录最多使用一次，因为系统没有时间第二次访问一条数据，并且数据量很大，处理过的数据很快被存到低速设备上去，要重新访问非常困难；系统随时都可以提供有效的信息，而不是在处理完所有数据后再提供信息，因为数据不可能被处理完；随着数据产生的变化，系统应当在任何时候都保持最新，既能正确反应数据中新出现的模式，又不使未过时的信息丢失。由于数据产生速度非常快，同时，内存相对于数据量又是非常有限的，所以满足前三项是非常困难的，所以现有的多数数据流挖掘算法，在结果的准确性可以接受的前提下，尽量减少实际处理的数据的量。

目前数据流挖掘方面的研究成果主要集中在数据流的聚类、分类和频繁模式挖掘方面。虽然已存在许多有效的方法应用于挖掘静态数据集，但数据流挖掘对这些方法又有额外的限制，只能使用有界的内存和有限的处理时间，并对数据单遍扫描。为了有效的挖掘出数据流中潜在的信息，需要对传统的数据挖掘技术进行改进或者针对数据流提出新的方法。

2.1 数据流聚类

聚类技术是把一个数据集中的数据分成不同的组，在同一组中的数据彼此相似，不同组的数据彼此相异。聚类可以应用在模式识别、空间数据分析、图象处理、市场调查等方面。数据流上的聚类就是通过单遍扫描数据流，持续地将数据流数据对象分组成多个类，在同一个簇中的数据对象之间具有较高的相似度，而不同簇间的数据对象的相似度很小。数据流的聚类算法不同于传统数据的聚类算法，必须是增量式的，对聚类的表示要简洁，对新数据的数理要快速，对噪音和异常数据必须是稳健的。因而，基于数据流的聚类算法是在一个相对较小的内存空间上，对数据流进行一遍扫描后，把数据集合分成不同的组。另外，在一些应用中需要对多条数据流进行聚类。对多条数据流聚类是将每一数据流看成一个聚类对象，考虑的是数据流间的相似度。近年来，根据实际使用情况，人们不仅希望知道数据流在某一时刻的聚类结果，也希望得到在某一时间段中产生的聚簇结果及聚簇是如何随时间变化的，从而得到数据流的生成规律，从而产生了基于网格和密度的聚类算法。例如文献[2]中提出的GDDS算法，该算法把数据空间划分为网格单元，然后在网格的基础上对稠密的单元进行聚类。

2.2 数据流分类

分类是一种非常重要的数据挖掘技术，其目的是根据已有的数据集学习构造一个分类函数或分类模型,该分类模型能够将新到样本映射到一个具体的类别上。传统的分类模型包括决策树、决策规则、贝叶斯理论分类、神经网络法、支持向量机法、K近邻分类器、范例式推理、进化算法、粗糙集法及模糊集法等。但是，这些算法都要求对数据集进行多次扫描，因此并不适用于数据流的分类。因为,随着时间的更迭而生成的数据流,其数据量大且数据分布可能会发生变化，即概念漂移(concept—drift)。数据流的这些特性要求分类算法不仅能够利用有限的内存和空间，而且学习到的模型能够不断调整来适应新流入的数据以提高分类准确率。数据流上的分类就是提出一个分类模型通过单遍扫描数据流，持续地利用分类模型将数据流对象影射到某一个给定的类别中，并以特定的频度重新修正模型以消除旧样本的影响。例如文献[3]中提出的增量决策树算法，该方法用固定的内存和固定的时间为每个样本构建一颗决策树，有效地解决了时间、内存和样本对高速数据流上的数据挖掘的限制。

2.3 数据流频繁模式挖掘

频繁模式挖掘的任务是通过对一个数据集进行统计，找出出现频率最高的一个数据或一组数据，从而挖掘出频繁模式。虽然频繁模式挖掘已经被广泛研究，出现了许多经典算法，但这些算法难以增量式更新，不适合数据流挖掘。因为数据流的流动性和连续性，数据流上频繁模式信息随着数据流的连续产生而不断发生变化。在大多数数据流应用中，用户往往更加关注数据流上最近事务数据所包含的信息。数据流上的频繁项集挖掘就是单遍扫描数据流来连续发现其中的频繁项集。对于数据流，内存的限制导致只能选择可能成为频繁的项来进行快速近似地进行频度计数。现有的频繁模式挖掘算法主要分为两类：批处理方法和启发式方法。批处理方法的主要思想是对数据流分段，通过分段上的局部频繁模式来求解全局近似频繁模式，该类算法实时性不高。启发式方法的主要思想是随着数据流中数据的不断到达，由已知频繁模式逐步生成新的频繁模式，该方法能够随着数据的到达直接进行处理，在一定程度上可以实时地反应频繁模式的变化，但模式估计与查询精度较低。针对数据流的无限性、流动性和不规则性等特点，人们不断提出新的频繁模式挖掘算法。如文献[4]提出的FP-IDS算法，该方法采用时序数据分段的思想，逐段挖掘局部频繁项集，然后以及局部频繁项集有效地挖掘出所有的全局频繁项集。

2.4 数据流挖掘应用

由于数据流在人们的日常生活很常见，目前，数据流挖掘系统已初步得到发展，主要应用于一些需要处理海量数据的重要部门[5]。例如：用于股票市场的数据流系统，可以帮助人们预测股市的起伏；用于零售业的交易数据流挖掘系统，可以对促销活动的有效性、顾客的忠诚度等进行分析；用于医学监视中的数据流分析系统，可以得到治疗效果的测量数据，发现生死攸关的征兆；用于航天科技中的数据流挖掘系统，可以从空间对象的实时图像中提取模式，从而利用高度自动化的航天器以及传感器进行空间探测；用于移动车辆的监控和信息提取的数据流系统，可以对驾驶员进行行为分析；用于网络监控的数据流系统，通过跟踪网络中数据的流动变化来研究网络流通模式及可能的非法入侵等。随着技术的不断发展，数据流挖掘技术将在更多的领域得到应用。

3 结论

随着信息技术的发展，越来越多的应用领域产生或获得了大量的源源不断的数据流。数据流的分析与挖掘已成为一个研究热点。本文介绍了数据流挖掘有关的概念、特点、研究现状和应用。由于数据流具有的时效性、实时性、无限性和瞬时性等特点，传统的数据挖掘技术面临巨大的挑战，它们必须根据数据流的需要重新建模，当前的有关算法的研究有很多是在传统的增量式挖掘技术基础之上发展而来的，探索数据流挖掘技术与传统的静态数据挖掘技术之间的本质区别，提出更有效、新颖、快速挖掘算法是当前研究面临的重要问题。数据流挖掘面临着内存的限制、实时响应、单次扫描、结果的近似性、算法的自适应性等困难。提高数据流挖掘算法的精度和适应性，使得算法具有较小的内存开销和快速的数据处理能力，并利用挖掘的知识帮助人们做出决策将会是一项非常有实际应用前景的工作。

[1]金澈清，钱卫宁，周傲英.流数据分析与管理综述[J].软件学报，2004，15（8）.

[2]高永梅，黄亚楼.一种基于网格和密度的数据流聚类算法,计算机科学[J],2008：35（2）.

[3]G.Hulten,L.Spencer, P.Domingos.Mining Time-changing Data Streams[C].In Proc.of ACM SIGKDD,2001.

[4]朱琼，施荣华.一种数据流中的频繁模式挖掘算法[J].计算机应用,2008,28(6).

[5]王涛，李舟军，颜跃进，陈火旺.数据流挖掘分类技术综述[J].计算机研究与发展，2007，44（11）.

TP274

A

1002－6487（2010）07－0161-02

王大将（1983-），女，江苏淮安人，助教，研究方向：数据挖掘、智能决策。

孙洁（1983-），女，江苏盐城人，助教，研究方向：粗糙集、神经网络。

（责任编辑/易永生）