数据流挖掘研究和其进展.doc

数据流挖掘研究及其进展 计算机应用技术 刘晓莹) 摘　要: 有关数据流挖掘技术的研究是当前国际数据库研究领域的一个热点，数据流的特点在于数据规模宏大，并快速、持续地到达，对应的挖掘算法只能在内存中单遍扫描样本子集就可以获取相应的知识结构，还需要在一定时间内对学习的结果进行更新以适应数据分布的变化。本文对现有数据流上的挖掘算法进行综述，最后给出了数据流挖掘今后的一些研究方向。 关键词：数据流；挖掘；聚类；分类；频繁模式；时间序列 Abstract: The study on mining data streams is one of the hot topics among the database circle all over the world recently. Data streams are continuous, unbounded, rapid, time-varying streams of data elements. Mining algorithms on data streams are concerned with extracting knowledge structures by one-pass scan in memory, updating the results to suit the change of the distribution. This article introduces some data stream mining algorithms and summarizes the main ideas. Finally, this paper presents some research trends in this area. Keywords: data streams; mining; cluster; classification; frequent pattern; time series 1　引　言 在实时监控、联机分析等先进应用领域，如网络监控、股市分析、传感器网络等，需要对大量的动态数据进行实时的、连续的数据收集与查询处理。由于连续到达的数据的多样性、快速性、时变性等特点， 形成了难以预测的无界数据流，传统的数据库技术很难提供有效的管理，于是产生了数据流这一新型技术。 数据流管理系统(Data Stream Management System,DSMS)不同于传统的数据库管理系统(Data Base Management System,DBMS), 当数据在线到达之后，并不是存储到磁盘上，而是直接进入到流查询处理器当中，流查询处理器实时地对数据进行处理。当用户或应用注册一个查询之后，流查询处理器将保持这个查询直至其失效为止，也就是说用户注册的查询始终保持有效状态，这也就是连续查询(Continuous query)的形式.数据流入查询处理器之后，查询处理器直接根据当前注册的查询对数据进行操作，所产生的结果同样以流的形式返回给用户或应用。 目前，国外很多大学和研究机构都在对数据流管理系统(Data Stream Management System,DSMS)进行研究，并进行了原型系统的开发以及相关算法的研究。例如斯坦福大学的STREAM系统[1],加州大学伯克力分校的TelegraphCQ系统[2]，布朗大学和麻省理工大学合作的Aurora系统[3]，威斯康星州立大学的NiagaraCQ[4]。 其它项目还包括StatStream[5]、Gigascope[6]等等。 在数据流管理系统基础上，结合机器学习、知识发现、数据挖掘等理论和技术，同时兴起一项新的智能信息处理技术-数据流挖掘. 例如,在实时数据流监测应用中，需要提供预定义模式的检测、数据流间相关性的发现、频繁项的发现、异常点的捕捉等功能。 近几年来,数据流的挖掘研究已经得到学术界的广泛关注.在聚类、分类、频繁模式发现和时序分析等几个方面针对数据流的挖掘算法相继被提出，以下将对这些算法进行综述。 2　聚　类 聚类是根据数据的不同特征，将其分组为不同的数据类或簇(cluster)，使得同一类个体之间的距离尽可能小，而不同类别个体之间的距离尽可能大。流数据的分析为聚类算法提出了前所未有的挑战，因为新算法需要能够只使用新数据就能追踪聚类的变化，这就要求算法必须是增量式的, 要尽可能少的扫描数据集, 而且对聚类的表示要简洁,对新数据的处理要快速，对噪音和异常数据要稳健。 近年来，很多学者提出了基于流数据的聚类算法，它们可以应用于某些数据流问题。 2.1　基于K-median的方法 K-median算法中，每个簇用接近聚类中心的一个对象来表示。文献[7]首先提出了基于K-median方法的单遍