（计算机软件与理论专业论文）数据流频繁项挖掘算法研究与应用.pdf

大连理工大学硕士学位论文 摘要 数据流是按时间顺序到达的一个连续数据组成的一个序列。近年来，挖掘数据流的 应用越来越广泛。在动态数据集上挖掘频繁项是一项困难的任务，也是一个热点。流数 据频繁项挖掘是数据流挖掘中的重要组成部分。 目前数据流频繁项挖掘算法的研究成果主要有基于h a s h 的和基于抽样的。本文首 先对这两类的经典算法的主要思想进行了探讨，对这些算法在误差范围、空间复杂度和 单项处理的时间复杂度等方面重点进行了比较。接着，本文重点对数据流频繁项挖掘的 e c 算法进行了研究探讨。虽然该算法在误差范围、空间复杂度和处理单项数据项的时 间复杂度方面是目前进行频繁项挖掘中的较好算法，但该算法在最坏时间复杂度方面没 有给出最坏保证，在精度方面还可以进一步提高。然后，本文给出了基于计数和局部性 原理的频繁项挖掘算法。一方面，改进e c 算法维护样本集合的方法，将数据流每个数 据项的最坏处理时间控制在0 ( 8 - 1 ) ；另一方面，根据局部性原理可知，如果一个数据项 被访问，则该项可能很快被再次访问。因此，利用增加历史样本集，暂存历史流数据的 概要信息，通过动态维护样本集和历史样本集来进一步降低输出频率值的误差，用一定 的空间换取一定的精度。通过理论分析和实验验证，通常情况，改进算法的误差更小。 而且，最坏时间复杂度可以得到保证。最后，在公安局的点击流频繁项挖掘系统中该算 法得到具体应用。访问者点击网页时形成连续的、数据量巨大的点击流信息，保存所有 数据是不现实的。当点击流信息产生时，首先，数据流处理模块负责接收数据、流量控 制等。然后，通过数据流频繁项挖掘模块快速、有效地近似统计出点击量最大的网页， 将该信息保存在概要数据结构中。当查询时，从概要结构中快速返回感兴趣的网页。 关键词：数据流；数据挖掘；一近似；频繁项 大连理工大学硕士学位论文 r e s e a r c ha n da p p l i c a t i o no fm i n i n gf r e q u e n ti t e m sa l g o r i t h mi nd a t a s t r e a m s a b s tr a c t ad a ms t r e a mi sa l lo r d e r e ds e q u e n c eo fi t e m st h a ta r r i v e si nt i m e l yo r d e r r e c e n t l y t h e a p p l i c a t i o no fd a t as t r e a mr n j n i u gi sw i d e l y - n s e d i ti sc h a l l e n g ea n dh o tt om a i n t a i nf r e q u e n t i t e m so v e rad y n a m i c a ld a t as t l e a n l d a t as t r e a mf r e q u e n ti t e m sm i n i n gi sa ni m p o r t a n t c o m p o n e n to f d a t as t r e a mm i n i n g r e s e a r c hr e s u l t so fd a t as t r e a mm i n i l l ga l g o r i t h m sm o s t l yi n c l u d eh a s ha l g o r i t h m sa n d s a m p l i n ga l g o r i t h m s f i r s t l y ，t h e s et w ot y p e so fc l a s s i c a la l g o r i t h mf o rt h em a i ni d e aa r e d i s c n s s e d f o c u si nt h i sa r t i c l ei so nt h ed i f f e r e n c eo f f r e q u e n te r r o rb o u n d 、s p a r er e q u i r e m e n t a n dt i m ef o rp e r - i t e mo fa l g o r i t h m s s e c o n d l y , e ca l g o r i t h mo fm a i n t a l n i n gd a t as t r e a m f r e q u e n ti t e m si sr e s e a r c h e da n d i ti sd i s c u s s e d f r e q u e n te r r o rb o u n d 、s p a c er e q u i r e m e n ta n d t i m ef o rp e r - i t e mo fe ca l g o r i t h mi sb e t t e rn o w , b u tt h ew o l - s t - e a 站e o m p l e x i t yi sn o t c o n s i d e r e da n dt h ef r e q u e n c ye r r o rb o u n do ft h er e s u l t sc a nb es m a l l t h i r d l y , t h i sp a p e r p r o p o s e da ni m p r o v e da l g o r i t h mf o rm i n i n gf r e q u e n ti t e mb a s e do nc o u n t e ra n dl o c a l i z e d p r i n c i p l e o nt h eo n eh a n d , t h em e t h o dh o w t ou p d a t et h es a m p l es e to fe ca l g o r i t h mi s c h a n g e db yac o u n t e r t h ew o r s t - c a s ec o m p l e x i t yi so ( 8 _ 1 ) b yi t o nt h eo t h e rh a n d , i fa i t e mi sa r r i v e d , i ti sp r o b a b l ya r r i v e dr e c e n t l y s o ，t h es y n o p s i si n f o r m a t i o ni ss a v e dw i t h h i s t o r ys a m p l es e t t h ef r e q u e n tg l - o rb o u n di sl o w e rb yd y n a m i c a l l yu p d a t es a m p l es e ta n d h i s t o r ys a m p l es e t i tt a k e sc e r t a i ns p a c et og e tm u c hb e t t e ra c o m - a e y t h e o r e t i c a la n a l y s i sa n d e x p e r i m e n t a lr e s u l t ss h o wt h a tt h ea l g o r i t h mp r o p o s e di nt h i sp a p e ri sb e 慨b e c a u s eo f s m a l l e rf r e q u e n ta i t o rb o u n da n dl o w e rw o r s t - t i m ec o m p l e x i t y l a s t l y ，t h ei m p r o v e d a l g o r i t h mi sr e a l i z e di np r a c t i c a la p p l i c a t i o no nf r e q u e n ti t e m sm i n i n gp r o j e c to fp u b l i c s e c u r i t yb u r e a u w h e nw e bp a g e sa l ec l i c k e d , t h ec o n t i n u n n sa n dh u g ec l i c k s t r e a md a t ai s a r r i v e d i ti si m p o s s i b l et os a v et h ew h o l ed a t as t r e a mt od i s kw h e nd a t as t r e a mi sa r r i v e d , f i r s t l y , d a t as t r e a mp r o c e s s i n gm o d u l er e s p o n s i b l ef o rr e c e i v i n gd a t aa n dt r a 伍cc o n t r 0 1 t h e n , f r e q u e n ti t e m sm i n i n gm o d u l er e s p o n s i b l ef o re f f i c i e n t l yp r o c e s s i n gd a l as t r e a ma n ds a v i n g t h eu s e f u li n f o r m a t i o nt os y n o p s i sd a t as t r u c t u r e t h ei n t e r e s t i n gp a g e sa r cr a p i d l yr e t u r n e db y s e l e e t i u gs y n o p s i sd a t as t r u e t u r e ，w h e naq u e r yr e q u e s ti sa r r i v e d k e yw o r d s ：d a t as t r e a m ；d a t am i n i n g ：s - a p p r o x i m a t e ；f r e q u e n ti t e m i i i 独创性说明 作者郑重声明：本硕士学位论文是我个人在导师指导下进行的研究工 作及取得研究成果。尽我所知，除了文中特别加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得大连理 工大学或者其他单位的学位或证书所使用过的材料。与我一同工作的同志 对本研究所做的贡献均已在论文中做了明确的说明并表示了谢意。 作者签名：堇灶日期：型! z 堡：12 大连理工大学硕士研究生学位论文 大连理工大学学位论文版权使用授权书 本学位论文作者及指导教师完全了解“大连理工大学硕士、博士学位 论文版权使用规定”，同意大连理工大学保留并向国家有关部门或机构送 交学位论文的复印件和电子版，允许论文被查阅和借阅。本人授权大连理 工大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，也 可采用影印、缩印或扫描等复制手段保存和汇编学位论文。 作者签名：j 三钦作者签名：! 二笪】芷 导师签名： 巡年卫月卫日 大连理工大学硕士学位论文 1 绪论 自2 0 世纪7 0 年代以来，数据库技术发展迅速且得到了广泛应用。一方面，数据建模 形式多样，从层次数据库、网状数据库、关系数据库、对象数据库，以及关系对象数据 库等等；另一方面，数据规模也越来越大。传统数据库技术的一个共同点是：数据存储 在介质中，可以多次使用。用户提交数据操纵语言( d a t a m a n i p u l a t i o n l a n g u a g e ) 来获取查 询结果。数据库技术得到了迅速的发展和广泛的应用，而且获得了巨大的成功。 在2 0 世纪末，随着信息技术的飞速发展，数据流( d a t ab q a e a l i l ) 的应用模型出现在众 多应用领域，这种新的应用模型对传统数据库技术提出了有力的挑战。例如，w e b 日志 分析、网页点击流、网络监控和交通工程、电信记录管理和分析、商业交易管理和分析、 传感器信息监控等等。流数据的共同特点是不断地产生、在时间上严格有序、数值不断 地变化，数据规模一般很庞大，而且增长迅速。在有限的存储空间中无法保存数据流的 无限数据，而且，数据流应用对查询处理的实时性要求通常很高，因此，流数据不能先 保存，然后再进行处理。与传统的静态数据库相比，数据流具有连续快速、短暂易逝、 和不可预测的特点【l ，2 1 ，使得传统数据挖掘算法在空间复杂度和时间复杂度方面都不能 适应数据流挖掘。 数据流所要求的单次线性扫描迸一步增加了这项任务的难度。随着数据的不断流 入，频繁项可能会变得不频繁，非频繁项也可能成为频繁项。要精确地计算数据流中的 频繁项，算法必须保存所有的历史数据。但是，对于流数据，这是一个无法达到的要求。 通常情况，数据流上的频繁项挖掘算法只能得到近似计算结果。因此，在动态数据集上 挖掘频繁项是一项困难的任务【3 】。流数据应用的特性产生了一些本质性的新的研究问题， 它们是传统的数据库技术和数据挖掘技术无法解决的。为解决这些问题，适应于新的应 用需求，数据流挖掘成为目前研究的热点。 1 1 数据挖掘 数据库技术的成熟和数据库应用的普及使得人类积累的数据量正在以指数速度增 长，人们应用数据库技术处理着日常繁杂的事务。大量信息在给人们带来方便的同时也 带来了一系列问题：第一是信息过量，难以消化；第二是信息真假难以辨识；第三是信 息安全难以保证；第四是信息形式不一致，难以统一处理。人们开始考虑如何才能不被 信息淹没，而是从中及时发现有用的知识、提高信息的利用率。这些问题的出现促成了 数据挖掘技术的出现。 数据挖掘就是从大量的、不完全的、有噪声的、模期的、随机的原始数据中，提取 数据流频繁项挖掘算法研究与应用 隐含在其中的、人们事先不知道的、但又是潜在有用、可信、新颖的信息和知识的过程。 从广义角度讲数据、信息是知识的表现形式，但在数据挖掘中更多把概念、规则、模式、 规律和约束等看作知识。原始数据可以是结构化的，如关系型数据库中的数据，也可以 是半结构化的，如文本、图形、图像数据，甚至是分布在网络上的异构型数据。发现知 识的方法可以是数学的或非数学的、演绎的或归纳的。发现的知识可以被用于信息管理、 查询优化、决策支持、过程控制等。总之，数据挖掘是一门广义的交叉学科，它的发展 和应用涉及到不同的领域，尤其是数据库、人工智能、数理统计、可视化等【4 1 。 图1 1 数据挖掘的形成 f i g 1 1 f o r m a t i o no f d a t a m i n i n g 数据挖掘也被称为数据库中知识发现，它的研究主要基于三大技术支柱，包括数据 库、人工智能和数理统计。图1 1 简要描述了数据挖掘技术的形成过程。数据库理论的 发展促成了数据仓库的形成，人工智能的发展促迸了机器学习的进步，同时这些技术与 传统的数理统计理论的结合，形成新的技术热点。 1 2 国内外研究现状 当前，数据库重点研究的三个问题分别是流数据管理和挖掘、对等计算环境下的数 据管理和x m l 数据管理和w c b 服务。 h e n z i n g e r 等人于1 9 9 8 年在论文“c o m p u t i n g o i ld a t as t r e a m ”中首次将数据流作为一 种数据处理模型提出来【5 】。从2 0 0 0 年开始，数据流作为一个热点研究方向出现在数据挖掘 与数据库领域的几大顶级会议中，如v l d b 、s i g m o d 、s i g k d d 、i c d e 、i c d m 等会 议每年都有多篇有关数据流处理的文章，提出了一系列的理论、方法和技术，有力地推 动了数据库技术的发展。目前，数据流研究大致可分为两个方面：数据流管理系统( d a t a s t r e a mm a n a g e m e n ts y s t e m s ，d s m s ) 和流数据挖掘【6 】。其中，建立数据流管理系统方面的 研究主要集中在数据流查询。已有多个研究机构进行了d s m s 的研究，并构建出一些系 统。例如，斯坦福大学的s t r e a m 项卧“，加州大学伯克利分校的t e l e g r a p h 项目 7 1 ，布 蓦 著 罢 大连理工大学硕士学位论文 朗大学和麻省理工学院合作的a u r o r a 项目嗍等等。数据流挖掘技术，包括聚类分析、决 策树和数据分类、频繁项以及频繁模式挖掘等等。前者侧重于数据流管理系统的开发和 相关技术的实现，如数据流的处理模型、连续查询语言等等；后者侧重于数据流的在线 分析，在聚类、分类、频繁项和频繁项集的挖掘以及可视化方面都做了大量的工作。流 数据挖掘方面的研究主要包括多数据流挖掘和单数据流挖掘。u i u c 开发的 m a i d s ( m i n i n gm a n n i n gi n c i d e n t sf t o md a t as t r e a m s ) 就是一个集查询、聚类、分类、频 繁项挖掘，以及处理结果可视化五大功能为一体的流数据挖掘系统1 9 】。 最近几年，国内外开始研究基于一遍扫描的频繁项挖掘近似算法，并取得一些研究 成果。目前，数据流频繁项挖掘算法的研究成果主要有两类：h a s h 和抽样。在基于h a s h 的方法中，c h a d k a r 等人提出了c o u n ts k e t c h 算、法【1 0 l 、c o r m o d e 等人提出了g r o u pt e s t 算法【3 】、j i n 等人提出了h c o u n t 算法【l ”。在基于抽样的方法中，m a r d m 和m o t w a n i 在文 【1 2 q b 提出了一种确定的近似算法l o s s yc o u n t i n g 算法和一种p ，占) 随机近似算法 s 缸c k ys a m p l i n g 算法，m e t w a l l y 等人提出了s p a c e s a v i n g 算法【1 3 】，解决了同时处理数 据流频繁项查询和t o p - k 查询的问题，文 1 4 】基于切尔诺夫( c h e m o f f b o u n d ) 不等式提出 f d p m ( f r e q u e n td a t as t r e a mp a t t e r nm j n i n g ) 算法，文【1 5 】提出了一种确定的近似算法 e c 算法。 1 3 项目背景 本课题源于大连市公安局网上作战项目。近年来，随着公安信息建设的不断推进， 公安信息应用的不断深化，各地各级公安部分都建立了w e b 网站。如何提高网站的服务 质量是个关键的问题，网站的服务质量在一定程度上可以通过网站的点击率来反映，经 常被访问的网页通常都是访问者感兴趣的网页。通过发现访问者感兴趣的网页，了解访 问者的偏好，通过调整网页内容，进而改善和提高网站的服务质量。因此，当访问网站 时，形成源源不断地点击流信息，如何通过点击流信息发现访问频率较高的网页是一个 重要的问题。 1 4 本文工作重点 流数据挖掘技术包含的内容很多，涉及的领域也很广，比如对流数据进行聚类、分 类、频繁项挖掘、频繁模式挖掘以及多个流数据复杂的连接查询等等。本文工作主要有 频繁项挖掘理论探讨和工程应用两个方面。 ( 1 ) 针对数据流频繁项挖掘的算法进行了深入的探讨。通过对目前国内外经典的数 据流频繁项挖掘算法进行讨论，并进行对比。在相对较好的e c 算法的基础上，由于e c 数据流频繁项挖掘算法研究与应用 算法在最坏时间复杂度方面没有给出保证，而且在精度方面还可以进一步提高。在本文 中通过改善算法处理的流程，引入局部性原理，采用空间换精度的方法，给出了一种改 进的e c 算法。 ( 2 ) 针对公安局网上作战项目，将本文改进算法应用到实际中。访问者在不断地访 问网站时，形成海量的点击流数据，文中通过数据处理模块和频繁项挖掘模块实现频繁 项挖掘系统。通过采用数据流模型快速、有效地从点击流中挖掘出点击频率较高的网页， 为改善和组织网页的内容提供辅助信息。 1 。5 论文组织 对本文主要在数据流频繁项挖掘算法理论研究和在公安局网上作战项目中实际应 用两个方面做工作，全文的组织结构主要包括五部分。 第一章介绍数据挖掘的基础知识，数据流频繁项挖掘的国内外现状和本文的主要工 作和组织结构。 第二章介绍流数据挖掘的主要特点和模型，+ 并于传统数据挖掘算法进行比较。 第三章对经典的数据流频繁项挖掘算法的两类经典算法进行探讨，并对算法的性能 和特点进行了比较。 第四章通过深入分析e c 算法，在该算法的基础上给出了改进的e c 算法，并对改 进算法的误差范围、空间和时间复杂度进行理论分析和实验验证。 第五章主要是将改进的e c 算法应用在公安局网上作战项目中，给出具体的设计模 型，并对模型进行实现。 大连理工大学硕士学位论文 2 数据流挖掘 数据流l l6 】是按时间顺序到达的一个连续数据组成的一个序列。令t 表示任一时间戳， 表示在该时间戳到达的数据，流数据可以表示成4 ，吐，磷，4 。，。这个数据项序列 只能按下标i 的递增顺序读取一次。如股票交易所的股票价格信息，环境温度的监测数 据，电信部门的通话记录，网站的点击数据以及传感器网络中的监测数据等。比如网络 流量监控是通过对网络中传输的数据包和网络中的通讯链路数据进行采集和分析，根据 分析的结果可以及时发现网络拓扑结构的变化，可以了解各类应用在网络负载中的分 布，还可以对网络攻击等有害行为进行及时预警。传统的网络流量监控主要采用离线分 析的方法，首先将所采集的数据保存在数据库或文件系统中，然后对保存的数据进行离 线分析。最大的不足是对数据的分析不能够及时进行，分析的结果不能够反映出当前网 络中的流量现状。 2 1 数据流的特点 数据流不同于传统的数据仓库，数据流的到来往往是高速的，并且数据量是无穷的， 通过对比传统关系型数据，数据流具有以下几个特点。 ( 1 ) 数据处理模型。 传统的数据处理技术将所有数据存放在数据库或者数据仓库中，系统响应用户提交 的请求，允许不只一次搜索数据存储媒介，返回查询结果。因而需要大量的i o 操作， 效率低下，不能适应实时系统的需求。而流数据处理通常是通过维护一个规模非常小的 且常驻内存的概要数据结构来完成。数据流处理在响应时间上比传统的数据库数据处理 要求更严格，但是数据流查询结果允许有误差。 ( 2 ) 流数据应用中的数据是按照时间顺序连续到达。 与传统数据库中保存静态的数据不同，流数据应用中处理的数据主要是从外部数据 源获取，并且数据不是一次性提供，而是随时间不断地到达。 ( 3 ) 数据到达的时间和次序独立，不受应用系统控制。 传统数据库的数据是保存在存储介质当中的，数据库管理系统可以根据用户的请 求，查询请求经性能优化后，选择对数据的操作次序。流数据的数据全部来自于外部的 数据源，并且是随着时间的推进，数据连续地到达，应用系统无法选择数据到达的顺序， 只能按照数据到达的顺序依次处理。 ( 4 ) 通常情况，单遍扫描流数据。 流数据应用中处理的数据是不断到达的，有时数据到达的速度很快，系统无法在有 数据流频繁项挖掘算法研究与应用 限的时间和空间内缓存所有到达的数据，也无法支持对数据的处理。一般认为系统只能 够保存一段时间内所到达的数据，在此之前的数据已经被丢弃或己保存到外部存储介质 中，实时应用中无法被重复检索，因此，流数据的处理具有单遍扫描的特性。 ( 5 ) 对数据的查询处理是连续的、主动的。 流数据应用采用“d b m s 主动一用户被动”的处理模型。当新的数据到达时，根据 预先定义的条件，将计算的结果主动发送给用户。在这种处理模型下，用户事先定义好 查询请求，系统支持连续查询，即对后续到达的数据都是有效的。比如实时分析金融信 息应用中，用户可以定义对某只股票价格的查询，指定当股票价格变化幅度超过某一指 定阈值时，及时通知用户。这样的查询具有连续和事件触发的特性。 ( 6 ) 要求查询处理是实时的，可以接受近似的查询结果。 多数的流数据应用对数据处理都有实时性的要求。由于系统不在有限的存储空间保 存所有的数据，而且在很短的处理时间处理完数据，因此，查询流数据往往得到的是近似 的结果。 综上可知，传统的数据库关系模型很难满足新型的流数据应用需求，需要针对流数 据应用的特点设计新的流数据管理系统和研究新的流数据挖掘技术。 2 2 数据流模型 数据流是现象驱动的，其速度与数据项到达的次序无法被控制。数据流通常具有潜 在无限的体积，而且数据可能的取值是无限的，处理数据流的系统无法保存整个数据流。 而数据流的在线处理要求又使系统无法进行代价昂贵的磁盘存取。因此，通常情况下， 数据流中的数据项在被读取一次之后，就被丢弃，以后很难再读到。在实际应用中，某些 超大型的静态数据集要求处理算法只能进行一次线性扫描以降低算法的处理代价，可将 算法的输入也可当作数据流处理。 目前，在数据流研究领域中存在多种数据流模型。不同的数据流模型具有不同的适 用范围，需要设计不同的处理算法。可以分别按照数据流中数据描述现象的方式和算法 处理数据流时所采用的时序范围对这些模型进行划分。 设数据流中的数据项x ，屯，依次按下标顺序到达，它们描述了一个信号彳。按墨 描述信号么的方式，数据流模型可分为以下几类i lh ： ( 1 ) 时序模型( t i m es e r i e sm o d e l ) ：a 明= 五。数据流中的每个数据项都代表一个独 立的信号。 ( 2 ) 现金登记模型( c a s h r e g i s t e r m o d e l ) ：令薯= ( ，) ( t 0 ) ，则4 忉= 4 ，们+ 。 数据流中的多个数据项增量式地表达一个一们。在这种模型中，各项的值不是按序变化 大连理工大学硕士学位论文 的，但是每次变化都增加项值。例如，每个客户在购物完毕之后都需要到超市收银机前 付款，从而产生一个顾客付款流。当某一个顾客要付m 钱时，首先找到数组中属于这个 人的项( 假设为彳硼) ，然后a i 】_ 爿 f 】+ 脚。值得注意的是，i r a 总是一个正数。 ( 3 ) 十字转门模型( t u r n s t i l e m o d e l ) ：令而= ( u ) ，则4 们= 4 ，们+ u f 。其中，v 可 为正数，也可为负数。此时，数据流中的多个数据项表达一个4 们。4 明随着数据的流入， 可能会增加，也可能会减小。转盘模型的条件比另两个模型的条件都宽松，也比较常见。 例如，一个大电话公司想监控长途电话的使用情况，则市民拨打电话行为就构成一个数 据流。首先，公司可以创建一个包含d 个城市数组而，x ：，而。当某用户拨出一个电话 时，其所在城市所对应的数组项( 假设是铆习) 加1 ，即珥订= 彳阴+ 1 ；当通话完毕挂机时， 贝j j a i = 4 平1 。 在这3 种模型中，t u r n s t i l e 是最具一般性的数据流模型，其适用范围最广，也最难处 理。流数据分类与聚类通常使用的是时序模型，它们将数据流中的每个数据项看作一个 独立的对象。若将4 们记为信号，出现的次数，则流数据频繁模式挖掘通常使用的是c a s h r e g i s t e z 模型，只允许数据的插入。也有算法研究了同时存在数据插入和删除时的流数 据频繁模式挖掘问题。此时，算法应用的是数据流的t u r n s t i l e 模型。 由于数据流是一个长期、动态的过程，部分算法在处理数据流时并不是将所有的数 据流数据作为处理对象，而是根据应用需求选取某个时间范围内的数据进行处理。按算 法处理数据流时所选取的时序范围，数据流模型可分为以下几类【18 】： ( 1 ) 快照模型( s n a p s h o t m o d e l ) ：处理数据的范围限制在两个预定义的时间戳之间。 ( 2 ) 界标模型( 1 锄d m a r km o d e l ) ：处理数据的范围从某一个己知的初始时间点到当 前时间点为止。创建基于界标模型的概要数据结构，要求这个结构能够近似模拟这个数 据集合的特征。直方图方法、抽样方法、小波方法、哈希方法等都是非常有效的手段【堋。 直方图方法能够有效地表示大数据集合轮廓。抽样方法从大数据集中选取部分数据，表 征整个集合。小波变换方法是利用变换后生成的少数小波参数近似模拟原始信号。哈希 方法可以将大值域的数据集映射生成一个小值域内的目标数据集。 ( 3 ) 滑动窗口模型( s l i d i n g w i n d o w m o d e l ) ：处理数据的范围由某个固定大小的滑动 窗口确定，此滑动窗口的终点永远为当前时刻。其中，滑动窗口的大小可以由一个时间 区间定义，也可以由窗口所包含的数据项数目定义。目前的研究成果主要有指数直方图 技术、基本窗口技术和链式抽样技术i ls 】。 在这3 种模型中，界标模型和滑动窗口模型是采用得比较多的模型。界标模型通常 将数据流的起始点作为数据处理的初始时间点。此时，算法对数据流中所有数据进行处 数据流频繁项挖掘算法研究与应用 理，数据流上只存在插入操作。在滑动窗口模型中，窗口随着数据的流入向前滑动，窗 口中存在数据的插入和删除。滑动窗口模型非常适用于只要求对最近时间段内的数据进 行处理的应用。 2 3 与传统数据挖掘算法的不同 流数据挖掘与传统数据的不同。数据流中的数据量以惊人的速度持续不断增长，这 对数据挖掘提出了新的挑战。表2 1 概括了流数据挖掘与传统数据挖掘主要的不同之处。 这些差别归根结底是由于数据流数据量无限增长、数据快速到达的特性所决定的。 数据流挖掘算法和传统挖掘算法相对比有其特殊的地方。无论是分类、聚类还是频 繁模式挖掘，数据流上的算法注重的都是一遍扫描数据集，并尽可能对结果集压缩存储。 表2 1 传统数据挖掘与流数据挖掘的比较 t a b 2 1 c o m p a r i s o nb e t w e e nd a t as t r c 蜘m i n i n ga n dt r a d i t i o nd a t am i n i n g 所有的分类和聚类算法注重模型的定义及再建立，以取得更好的匹配效果，使得分 类或聚类的效果更好，而时间效率并不太关心；在数据流上进行分类或聚类算法则注意 动态的适应数据的变化，尽可能及时地调整模型，算法的执行速度要达到一定要求，而 建模的精确程度没有过多研究。 原有的频繁模式挖掘算法因为最终结果是固定的，所以算法重点在于减少扫描数据 集的次数，以获德更好的时间效果；在数据流上挖掘频繁模式，算法一方面要保证只扫 描一遍数据，另一方面要使结果集与统计的结果相比尽可能准确，挑战是可想而知的。 有的算法通过哈希或抽样等方法，在保证一定误差下降低处理的数据量，加快响应时间； 有的算法以低支持度阈值的方法，来保证在一遍扫描的前提下，及时记录可能频繁的模 式，使挖掘结果的误差尽量低。 数据历史信息的压缩存储也是数据流挖掘算法共同关心的问题。一般来说，算法只 保存数据的概要信息，如统计值；或分时间段保存数据，将大量信息存储为几个代表点。 另外，随着数据的流动，部分信息可能过时，算法通常以一定策略进行删除，以释放存 储空间。 大连理工大学硕士学位论文 3 数据流频繁项挖掘算法 挖掘静态数据集合的频繁项已有很长历史，在已经取得的研究结果中【l 妣”，最好的 算法【2 1 】需要两遍扫描数据集合，只使用o ( s 。1 ) 的存储空间。近年来，在数据流上挖掘频 繁项成为一个热点的研究问题。由于多遍扫描的精确频繁项挖掘算法不适用于数据流模 型。因此，人们开始研究基于一遍扫描的频繁项挖掘近似算法，并取得一些研究成果。 目前，数据流频繁项挖掘算法的研究成果主要有两类：h a s h 和抽样。 3 1基于h a s h 的频繁项挖掘算法 使用很小的空间来描述数据的分布，它将数据流中的数据映射到建立的数据结构 中。该算法的优点是高效快速，算法通过简单的哈希操作将数据项映射到结构中进行统 计，但是，算法的误差相对较大，并且目前的算法主要是针对项集的挖掘。 该类算法能够处理收银机和转盘模型。该类算法维护一组哈希表，任何一个元素p 均 有对应的一组关联的计数器。 一般地，基于h a s h 的方法将数据流的值域映射到主存能够保存的h a s h 表中，h a s h 表的每个桶对应一个计数器，具有相同h a s h 值的数据项共用一个计数器。这些具有相 同h a s h 值的数据项的频率使用同一计数器的值进行估计，其估计的频率值与真实频率 值之间会有一定的误差，基于h a s h 的方法可以保证其估计的频率值误差不超过一定的 界限。在基于h a s h 的方法中，c h a r i k a r 等人提出了c o u n ts k e t c h 方法【1 0 l ，c o r m o d e 等 人提出了g r o u p t e s t 算法 3 1 ，j i n 等人提出了h c o u n t 算法【】。基于h a s h 的方法均是( ，占) 随机近似算法，其中多数算法需要知道数据流的值域范围，然而数据流的值域通常是未 知的。 3 1 1 c o u n ts k e t c h 算法 c o u n ts k e t c h 算法用c o u n ts k e t c h 数据结构来可靠的估计数据流中频繁项集的 频率，算法一遍扫描数据流并且在能够达到很好的空间范围。 算法需要确定和两个参数t 和b ，假设两个参数t 和b ，令h a s h 函数| l l ，岛， 将对象 映射到集合 l ，b ，h a s h i 蚕数s t ，s 2 ，岛将对象映射到集合 + 1 ，一1 ，上面两组中的全部 h a s h 函数彼此独立。该算法的数据结构中包含上面两组h a s h 函数和一个t * b 的计数器矩 阵，矩阵被t 个h a s h 函数分成t 个h a s h 表，每行包含b 个桶( 计数器) 。h a s h 函数囊将对象g 映射到第i ) p h a s h 表中的b 个计数器中的一个，用m 胡来表示这个计数器。 数据结构( 记作c ) 支持两种操作： 数据流频繁项挖掘算法研究与应用 ( 1 ) m d ( c ，q ) ：f o rf 1 州，则啊【g 】+ = 跗们。a d d 函数将元素g 在每+ h a s h 表的计 数器根据0 。m 进行加1 或者减1 操作。 ( 2 ) e s 衄u e ( c ，g ) ：r e t u r nm e d i a n ， 每【g 五【窖】 。该操作返回数据项在各+ h a s h 表 中的值乘以s ，豳】后的t 个值的中间值。 算法最终的估计是通过t 个h a s h 表的估计的中值，而不是平均值。这是因为即使到 了最后也没有完全消除高频率元素的碰撞问题，并且仍然会对估计的一些子集会引入大 量的误差。均值对于例外非常敏感，然而中值比较健壮。 建立了数据结构后，算法就能直接并且简单的实现。对于每一个元素，我们使用数 据结构来估计它的计数，并且保持一个到目前为止最多的个元素的堆。 对于一个数据流毋，吼，吼，对于每一个，= 1 ，2 ，即。操作包含以下两步： ( 1 ) a d d ( c ，q ，) ； ( 2 ) 如果g ，在堆中，则增加计数器；如果g ，不在堆中，当e s t i m a t e ( c ，q j ) 大于堆中 最小的评估值，则添加g ，到难中，并将该最小评估值从堆中删除。 c o u n ts k e m h 算法在内存中维护一个大小为的堆，并利用c o u n ts k e t c h 数据结构来 对项集进行统计。算法不断调整堆中的项集，最后得到最频繁的_ 个项集。 3 1 2h c o u n t 算法 该算法能在较少的内存中对数据项进行插入和删除操作，不需要预先知道数据流的 数据范围，能够处理数据范围动态改变的流数据。 h c o 咖t 算法的主要思想是使用一个h a s h 表s 所】 明和h 个相互独立的h 雒h 函数。每个 h 嬲h 函数均将数据流的值域从 o ，m 一1 】映射到 o ，肌一1 】，即每个h 雒h 函数均将数据流的 值域【o ，m 一1 】映射到m 个桶中，每个桶中保存一个计数器。当数据流到来一个数据项k ， 则用h 个h a s h 函数对其哈希，如果该数据项i 为正，则相应的计数器加l ，如果该数据项 k 为负，则相应的计数器减1 。然后使用计数器中最小的值作为其频率的估计结果。 h ，( 七) = ( ( q + k + 6 f ) m o d 力m o d m ( 1 i ) ( 3 1 ) 假如使用的h a s h 公式( 3 1 ) 。h ；( _ | ) 和i 分别表示数据项在h a s h 表肌】【明中的列位 置和行位置。令p = 3 1 ，数据流中数据项的取值范围是 1 1 6 ，创建的h a s h 表j 【聊】【明的 m = 5 和h = 4 。对于公式( 3 1 ) ，4 个h a s h 函数蝎、吼、马和也，参数为4 对( q ，包) ： ( q ，岛) = ( 7 ，1 3 ) 、( g 2 ，b 2 ) = ( 2 2 ，6 ) 、( 码，b 3 ) = ( 2 4 ，1 1 ) 和( q ，以) = ( 1 4 ，2 7 ) ，设处理的数据项k 是 2 ，1 ，6 , 3 ，9 ，一1 ) ，当处理完第四项后的h a s h 表状态如下图3 1 ( 1 ) ，在图3 1 ( 2 ) 和图3 1 ( 3 ) 大连理工大学硕士学位论文 用灰色分别表示第五项和第六项在h a s h 表中的处理过程。 l o 1 11 lool 2 11o11 10l1l 1 o11 2 。，； 1 oo“22 | 2 1o11 1o11 2 “： 1 011 。i ； 1 oo2 ：1 l ， “l 0l1 lol”o j2 ( 1 ) 第四项( 2 ) 第五项( 3 ) 第六项 图3 1 处理数据项时h a s h 表的状态 f i g 3 1 s t a t e so f h a s ht a b l e sw h e nh a n d l i n gd a t as u e m n s 当用户查询频繁项时，对任意的一个| i ( 1 s f m ) ，获取该元素在h 个h a s h 函数中的 最小值c - - - - i l l l 。n l ；j ；, k ( s 【h ，( 七) 】 月) 作为其评估值，如果该值c 印) ，) 2 e 2 ( 3 2 ) 令r = r n ，概率p 为最小支持度j ，则上式为不等式( 3 3 ) 。 一二! p r ir - s 陋j y 2 e 2 ( 3 3 ) 在令占= s y ，则可得不等式( 3 4 ) 。 一二生 p r ir s j s ) 2 e 知( 3 4 ) 令5 等于不等式( 3 4 ) 的右端，可以得出，以概率小于等于艿的条件下，运行平均值 r 不在b - 8 ，s + 8 ) 范围之内，即可以保证在大于等于1 - 5 的概率下，数据项0 。的支持度 在b - - 8 ，5 + s ) ，s 大小通过公式( 3 5 ) 计算可得。 g = 乒乎 ( 3 5 ) f d p m 基于c h c m o f f b o u n d 将到达的项分为两组，即潜在的非频繁模式和潜在的频繁 模式：给定疗个观察值，运行误差s 。可根据上一段介绍的方法获得。s u p ( x ) n = s 一毛， 则模式为潜在非频繁模式：反之，为潜在非频繁模式。 f d p m - - 1 频繁项挖掘算法有支持度s 和5 两个输入参数。忆为需要观察的次数， 1 4 大连理工大学硕士学位论文 的大小如公式( 3 6 ) 。 n o ；2 + 2 1 n ( 2 * k 1 6 ) ( 3 t 一5 、) = 一 l j 占 事实上为f d p m 1 的内存b o u n d 。每当从事务数据流1 项集中收到一个