（计算机应用技术专业论文）数据流频繁项挖掘系统的研究和实现.pdf

浙江大学硕士学位论文摘要 摘要 随着互联网的发展，世界已经走向信息经济时代；信息资源并不稀缺，稀缺 的是发现信息资源、综合信息资源的手段。搜索引擎就是因此应运而生的。但是 随着可搜索资源和搜索引擎使用者的不断增加，搜索引擎的查询性能成为一个制 约其发展的瓶颈。 改善搜索引擎的性能可以从不同方面入手，如加大服务器集群规模，推出各 种垂直搜索，优化搜索目标排名方案，提供个性化搜索服务等。本文试图从分析 查询输入入手，采用数据流挖掘技术，研究和改进一种面向数据流的频繁项挖掘 算法，并实现一个频繁项实时统计系统，指导搜索搜索引擎的索引组织和网页抓 取，从丽提供更高效的搜索性能、更准确的查询结果。 本文针对目前的l o s s yc o u n t i n g 算法在处理大数据流量的事务数据流上没有 空间需求上限，处理速度随着数据量增大而降低的特点，提出了一种针对这种算 法的改进算法l a t t i c el o s s yc o u n t i n g 。通过设置时问窗格的方法是原算法具有挖 掘结果具有实效性，并且为控制挖掘过程设置所需空间的上限；通过将算法拆分 成两个阶段处理，在不影响精度的前提下提高算法处理速度。以使其符合在大数 据流量长时间处理的情况下的应用需要。 另一方面，为了测试算法性能、实现算法应用，本文提出了一套面向搜索引 擎的、基于数据流的频繁项挖掘系统f e n s t e r 。该系统可以处理由查询产生的 输入事务流或由点击产生的事务流，采用在线算法挖掘频繁项。根据应用环境的 区别，本文分别介绍了f e n s t e r 的两种运行架构：集成环境应用于小型应用和算法 性能测试；分布式的架构应用于大规模的应用。 通过实验，本文论证了这种新的算法在时间性能和空间性能上对于l o s s y c o u n t i n g 算法的改进是卓有成效的，具有广泛的应用前景；验证了该基于数据流 的频繁项挖掘系统的可用性，并提出了该系统未来改进的方向。 除了搜索引擎之外，本系统提供的高度可配置性能力让系统在其他领域的应 用成为可能。同时，数据流频繁项挖掘研究的不断深入也让本系统在诸如股票分 析、人群行为分析、商业行为分析、天气和环境检测等诸多方面具有广阔的应用 前景。 关键词数据流，频繁项，数据挖掘，搜索引擎 浙江大学硕士学位论文a b s t r a c t a b s t r a c t w i t ht h ed e v e l o p m e n to ft h ei n t e m e t t h ew o r l dh a se n t e r e di n t ot h ea g eo f i n f o r m a t i o n - e c o n o m y w h e r e a s ，w h a tu s e rd e s i r e i sn o tm o r ei n f o r m a t i o n , b u tt h e s o l u t i o no ff i n d i n gh i d i n gi n f o r m a t i o ne n dt h em e t h o dt of i n dm o r eh i 9 1 ll e v e l k n o w l e d g ef r o mt h ei n f o r m a t i o n w em a yn o wr e f e rt os e a r c he n g i n e s ，b u tt h e p e r f o r m a n c eo ft h es e a r c he n g i n e sh a sb e e nr e s t r i c t e db yt h et r e m e n d o u sg r o w i n g s p e e do f t h ei n f o r m a t i o na n dt l l el l s e rn u m b e ro f t h es e a r c he n g i n e s t h e r ea s e v e r a lm e t h o d st oi m p r o v et h ep e r f o r m a n c eo fs e a r c he n g i n e s f o r e x a m p l e ，c l u s t e r i n g ，v a r i o u sk i n d so f v e r t i c a ls e a r c he n g i n e s ，o p t i m i z a t i o nf o rr a n k i n g , p e r s o n a l i z e ds e a r c he n ds oo i l w eh o p et od e v e l o pab e t t e rf r e q u e n ti t e ms c tm i n i n g a l g o r i t h mi nd a t as t r e a ma sak i n do f i n f o r m a t i o na g g r e g a t i o nm e t h o d i nt h i sp a p e r , w ep r o p o s e dan o v e la l g o r i t h mf o rt h i ss y s t e m ，w h i c hi sm o r e s u i t a b l ef o rc u r r e n ta p p l i c a t i o n s ，w i t ht h en a m eo fl a t t i c el o s s yc o u n t i n gb a s e do n l o s s yc o u n t i n g b yt h eu s eo f l a t t i c e s ，t h em i n i n ga l g o r i t h mc a ng i v er e s u l t sw h i c ha r e t i m es e n s i b l e b yd i v i d i n gt h ea l g o r i t h mi n t ot w op h a s c s ，t h ee f f i c i e n c yo ft h e a l g o r i t h m i sa c c e l e r a t e d ，b u tk e e p i n gt h eo r i g i n a lp r e c i s i o n w ea l s od e v e l o p e dan o v e lf r e q u e n ti t e ms e tm i n i n gs y s t e mi nd a t as t r e a mn a m e d f e n s t e r i tr e c e i v e st h es t r e a mo fc l i c kt r a n s a c t i o no rk e y - w o r dt r a n s a c t i o na si n p u t , e n dt h e nm i n e sf r e q u e n ti t e ms e ti nt h ed a t as t r e a me n dg i v e si m m e d i a t er e s u l t s w e j n t r o d u c et w od i f f e r e n ta r c h i t e c t u r e sf o r t h ev a r i e t ya p p l i e dc i r c u m s t a n c e t 1 】e c o m p r e s s e do n ei sf o ri n t e g r a t e da p p l i c a t i o n sa n dt h ed i s t r i b u t e do n ei sf o re n t e r p r i s e a p p l i c a t i o n s 1 1 l ee x p e r i m e n t sp r o v et h a to u ra l g o r i t h mo u t p e r f o r m st h ec l a s s i c a la l g o r i t h m b o t l li nt h et i m ee n ds p a c ec o m p l e x i t y t 1 l et w os y s t e m sc a na l s ow o r kw e l l m e a n w h i l e ，t h e yc a l lb ea p p l i e di nd i f f e r e n ta r e a s b yc o n f i g u r e di nd i f f e r e n tw a y s , w e c a l lu s et h e mi nf m e n c i a la n a l y s i s , b u s i n e s sa n a l y s i se n dw e a t h e rf o r e c a s ta n d e n v i r o n m e n t a lm o n i t o r i n g t 1 l em a i nw o r kh e r ei st oi n t r o d u c et h ei m p r o v e m e n to ft h ea l g o r i t h ma n dt h e i m p l e m e n to ft h ef r e q u e n ti t e m s e tm i n i n gs y s t e m a tl a s t ，w eg i v et h er e s u l t so fo u r e x p e r i m e n t s 。 k e y w o r d s d a t as t r e a m ，f r e q u e n ti t e ms e t ，d a t am i n i n g , s e a r c he n g i n e 浙江大学硕士学位论文图目录 图目录 图2 1f e n s t e r - s 系统结构1 l 图2 - 2f e n s t e r - c 系统1 2 图2 4f e n s t e r - d 系统部署图一1 8 图2 - 5 f e n s l e r 数据流程图。1 9 图2 - 6f e n s t e r 系统基于构件化技术实现一2 3 图3 1 有效时间窗格一2 9 图3 2 时间窗格。2 9 图3 3 渐变粒度自然时间窗格。3 0 图3 - 4 频繁项分布图。3 1 图3 5l a t t i c el o s s yc o u n t i n g 算法数据流图3 5 图3 - 6l a t t i c el o s s ) c o u n t i n g 算法实现存储结构u m l 图3 8 图3 7l a t t i c el o s s yc o u n t i n g 算法实现策略结构u m l 图3 9 图3 - 8p h a s ei 和p h a s e1 1 的单机结构v s 分布式结构4 0 图4 1 数据流处理子系统功能模块 图4 2 封装了完成端口的重叠f o 模型 4 2 4 3 图4 - 3 缓冲窗口u m l 结构图4 5 图4 - 4 数据流分流处理策略。4 6 图5 1h a s h 更新和存储5 l 图5 - 2 结果查询的注册和查询过程5 4 图6 1l a t t i c el o s s yc o u n t i n g 和l o s s yc o u n t i n g 算法处理时间5 9 图6 - 2l a t t i c el o s s yc o u n t i n g 和l o s s yc o u n t i n g 平均每秒处理5 9 图6 3 不同的支持度对算法处理速度的影响6 0 图6 - 4l l c 算法p h a s ei l 处理事务数量和算法总共处理事务数量的比较6 0 图6 5l l c 算法和l c 算法的监控列表规模6 l 图6 - 6 在2 0 0 万数据量的实验环境下，不同的频繁支持度所需要的内存6 2 图6 7 在6 0 0 万数据量的实验环境下，不同的频繁支持度所需要的内存一6 2 图6 - 81 0 0 0 万数据量的实验环境下，不同的频繁支持度所需要的内存。6 3 图6 - 9l l c 算法、l c 算法以及a p r i o r i 算法处理不同数据量的内存需求。6 4 图6 - 1 0l l c 算法和l c 算法处理不同数据量的内存需求“ 图6 1 l 采用了4 0 万+ 】o 时间窗口的l l c 算法内存需求6 5 图6 - 1 2l l c 查全率6 7 图6 - 1 3l l c 查准率。6 7 图6 - 1 43 0 0 0i t c m s e t s 速度，0 0 0 0 1 最小支持度的c p u 曲线6 9 图6 - 1 56 0 0 0 i t e r a s e ! t s 速度，o 0 0 0 1 最小支持度的c p u 曲线7 0 图6 - 1 63 0 0 0 i t e m s e t s 速度，0 0 0 0 0 1 支持度的c p u 曲线。7 0 浙江大学硕士学位论文图目录 图 图 图 图 6 1 76 0 0 0 i t e m s e t s 速度，o 0 0 0 0 1 支持度的c p u 曲线 良1 8 7 1 不同的支持度对监控集的项的数量的影响7 1 6 - 1 9f c n s t e r - d 以6 1 d s 的速度，o 0 0 0 1 支持度的l l c 算法c p u 曲线7 3 6 2 0f e n s t e r - d 以6 k s 的速度，0 0 0 0 0 1 支持度的l l c 算法c p u 曲线。7 4 v 浙江大学硕士学位论文 表目录 表目录 表2 1 查询事务流2 0 表2 - 2 点击事务流一2 0 表2 3 统一事务格式2 0 表4 1 配置模块接口表4 9 表5 1 引用格式的频繁项记录。5 5 表5 - 2 记录服务器详细信息的频繁项记录格式一5 5 表5 3 更新归并数据库记录格式。5 6 表6 ，1l l c 相对于l c 算法的查全率和查准率6 6 表6 2f e n s t e r - c 和f e n s t e r d 处理l l c 算法结果比较7 2 表6 - 3f e n s t e r - c 处理l c 算法和f e n s t e r - d 处理l l c 算法结果比较7 3 v l 浙江大学硕士学位论文第1 章绪论 第1 章绪论 1 1 课题研究的背景和意义 近年来，数据流处理一直是国内外研究的热点。简单地说，它是一种由实时、 连续、有序的数据组成的序列。这种数据广泛地存在于现实世界中，例如，w e b 服务器的日志记录、传感器网络监控、网络通讯监察、股票交易、天气或者环境 监测都生成了大量的数据流。与传统的静态数据不同，数据流具有连续快速短暂 易逝和不可预测i s 9 】的特点。 作为一种新兴的，但是却以极快的速度发展的计算机技术，互联网为人类提 供了空前的信息。仅仅二十年，i n t e m e t 已经深入到了每一个人的生活中去。人们 使用电子邮件沟通彼此，使用门户网站查询新闻，使用论坛聚会聊天，电子钱包 和专门网站购物，使用b l o g 写下自己生活的点点滴滴。信息的空前爆炸极大地方 便了人们的生活；但是，相对的，无处不在的信息带来的是一个与“发布”信息 同样重要的问题如何“收集”信息? 解答这个问题的是所谓的第二代全文检索引擎。1 9 9 8 年，g o o g l e 1 ，2 犊空出 世，迅速以其简介的界面，高效而准确的搜索结果获得了全世界超过半数的流量 i o l 。而在国内，将主要精力集中于中文信息搜索的b a i d u 同样获得了巨大的成功， 依靠其准确的中文信息检索，图片、音乐等多媒体信息检索以及“百度知道”，“百 度帖吧”等面向w e b 2 0 的新技术的支撑，b a i d u 在国内市场占有率一举超过六成 1 1 ”。g o o g l e 和b a i d u 的巨大成功让搜索引擎市场让其他的公司也毅然投入到这个 竞争激烈的战场之中。在国外，有l t 巨人微软、雅虎，国内则有搜狗，中搜，一 搜，甚至主营是即时通讯技术的腾讯公司也投入到这个市场中。 随着信息技术的不断发展，我们从信息短缺的时代迈入了信息极大丰富的时 代。科学技术的发展增强了人们之间的联系纽带，更加频繁的社会和经济活动带 来了无穷无尽的信息。人们需要从这些海量的数据中及时提取有用的信息。数据 流处理技术就是在这种大流量的信息处理需求背景下产生的。 搜索引擎的技术已经逐步成熟，但是伴随着互联网的发展，信息爆炸和用户 数量爆炸必将使搜索引擎的负荷随之增大。而各个搜索引擎公司面对这个挑战， 纷纷在搜索引擎的结果和效率上提高自己的质量，以期获得更加广泛的市场。 针对这个需求，本文提出了一种基于数据流的频繁项挖掘系统( f e n s t e r ) 。 所谓频繁项就是在一个数据集合中出现频率比较高的数据。提取数据集合中 浙江大学硬士学位论文第1 章绪论 的频繁项可以对该数据集合产生一个概要的描述。以传感器网络为例，通过搜集 海量传感器传输的信息，提取最频繁出现的值，描述该传感器网络覆盖范围内的 信息。以搜索引擎为例，从用户的输入中提取频繁项，可以获得目前用户关心的 网页内容，从而为个性化【6 】服务，搜索引擎周边产品等提供支持。以网络调度系 统为例，统计经过路由器的数据包的来源和目的，可以优化网络拓扑结构，提供 更高的互联网传输性能。 f e n s t e r 系统主要以搜索引擎为主要服务对象，从搜索数据流( 包括关键词流 和点击流) 中提取频繁出现的事务项，为其他的搜索引擎性能优化方案提供频繁 项同时，该系统并不把使用范围局限在搜索引擎领域，其高度的可配置性和可 裁减性也使频繁项挖掘技术能够应用到其他诸如传感器网络、股票交易，日志统 计等数据流中。 1 2f e n s t e r 概述 f e n s t e r 能够从不间断的数据流中根据可配置的数据流处理协议获得一定格式 的事务项；然后根据负荷情况反馈将这些事务分流到各个分布式的频繁项挖掘服 务器；在频繁项挖掘服务器中采用一次扫描的算法实现频繁项的提取工作；最后 将结果集合归并到结果存储服务器上。f e n s t e r 有电子窗口的意思，比较好描述了 这个系统功能和作用。 f e n s t e r 在搜索引擎的性能优化技术上有非常广泛的应用前景，它的挖掘结果 可以应用到诸如缓冲构造，c r a w l e r 网页抓取，网页r a n k 参考等方面。同时，在 搜索引擎周边产品和辅助技术方面，也可以为个性化查询分析，点击来源和目标 分析等方面应用提供技术支持。除此之外，f e n s t e r 在传感器网络，路由器控制以 及商业行为分析等领域同样有其用武之地。 1 3 搜索引擎技术现状概述 搜索引擎按照一定方式搜索互联网上的信息，然后将这些信息进行分类，并 建立索引，再把索引的内容存储到数据库中。当用户向搜索引擎提交搜索请求的 时候，搜索引擎会从数据库中找出匹配的资料，反馈给用户；用户再根据这些信 息访问相关的网站，从而找到自己需要的资料像g o o g l e 、百度等专业搜索引擎 的搜索功能都是在这个原理的基础上日趋成熟和完善的。 搜索引擎技术伴随着互联网的发展引入注目，大约经历了三代的发展。 第一代搜索引擎出现于1 9 9 4 年。这类搜索引擎的索引一般都少于1 , 0 0 0 。0 0 0 2 浙江大学硕士学位论文 第1 章绪论 个网页，极少重新搜索网页和更新索引。而且其检索速度非常慢。在实现技术基 本上沿用了较为成熟的i r 、网络、数据库技术，相当于利用一些已有技术实现的 一个新的互联网上的应用。 第二代搜索引擎系统大多采用分布式方案来提高数据规模、响应速度和用户 数量。自1 9 9 8 年到现在，出现了一个搜索引擎空前繁荣的时期，这一时期的搜 索引擎主要有如下特点： 索引数据库的规模庞大，一般的商业搜索引擎都保持在1 0 亿个网页以上。由 于索引数据库的巨大规模，使得对应于搜索关键字的返回结果数量非常大，检索 结果相关度评价成为研究的热点。相关的研究又可以分为两类：类是对超链接 的分析：另一类是对用户查询的分析和研究。 搜索引擎的技术综合性和用户广泛性带来的经济价值，引起了世界各国计算 机科学界和信息产业界的高度关注，目前的研究、开发十分活跃，并出现了很多 值得关注的动向。 1 十分注意提高信息查询结果的精度，提高检索的有效性 用户在搜索引擎上进行信息查询时，并不十分关注返回结果的多少，而是看 结果是否和自己的需求吻合。对于一个查询，传统的搜索引擎动辄返回几十万、 几百万文档，用户不得不在结果中筛选。解决查询结果过多的现象目前出现了几 种方法：一是通过各种方法获得用户没有在查询语句中表达出来的真正意图，包 括跟踪用户检索行为，分析用户模型；使用相关度反馈机制，使用户告诉搜索引 擎哪些文档和自己的需求相关，哪些不相关，通过多次交互逐步求精。二是用正 文分类( t e x tc a t e g o r i z a t i o n ) 技术将结果分类，使用可视化技术显示分类结构， 用户可以只浏览自己感兴趣的类别。三是进行站点类聚或内容的类聚，减少信息 总量。 2 基于智能代理的信息过滤和个性化服务 信息智能代理是另外一种利用互联网信息的机制。它使用自动获得的领域模 型( 如w e b 知识、信息处理、与用户兴趣相关的信息资源、领域组织结构) 、用 户模型( 如用户背景、兴趣、行为、风格) 知识进行信息搜集、索引、过滤( 包 括兴趣过滤和不良信息过滤) ，并自动地将用户感兴趣的、对用户有用的信息提 交给用户智能代理具有不断学习、适应信息和用户兴趣动态变化的能力，从而 提供了个性化的服务。智能代理可以在用户端进行，也可以在服务器端运行。 3 采用分布式体系结构提高系统规模 搜索引擎的实现可以采用集中式和分布式体系结构，两种方法各有千秋。但 浙江大学硕士学位论文 第l 章绪论 当系统规模达到一定程度( 如网页数量达到亿级) 时，必然要采用某种分布式方 法，以提高系统性能。搜索引擎的各个组成部分，除了用户接口之外，都可以进 行分布：搜索器可以在多台机器上相互合作、相互分工地进行信息发现，以提高 信息发现和更新速度；索引器可以将索引分部在不同的机器上，以减少索引对机 器的要求；检索器可以在不同的机器上进行文档的并行检查，以提高检索的速度 和性能。 4 采用新的创意和技术提高查询性能和结果反馈 缓存是搜索引擎一个非常重要的环节，通过研究查询日志记录的局部性，优 化缓存集合的结构和性能1 1 3 1 ，成为最近的一个研究热点。而g o o g l e 从2 0 0 4 年也 开始关注于这方面的研究【1 4 】。另外，像a s k 等公司则把注意力集中在给用户更好 的界面表达上。将多媒体搜索集合到文本搜索上来，在给出文本描述的同时给出 图片形式存在的更加感性的搜索结果。本文正是从这个方面入手，参考了通过构 建三级缓存索引提高性能的方案，并以此为出发点，设计f e n s t e r 系统。 1 4 数据流处理技术概述 数据流以及数据流处理包含以下几个概念： 数据元素的获取方式是采用联机( o n - l i n e ) 方式的，即所有数据都是在线 产生，在线到达。同时，系统对到达数据元素的处理，在次序上没有控 制。 数据持续不断，可能从多个通道同时到达；潜在地，数据流大小无边界 可言( u n b o u n d e d ) 数据一旦被处理，它将要么被丢弃，要么被存储，且存储的数据量极大， 不考虑重新计算。因此，数据元素不能轻易找回，除非被明确地存储在 内存中。 数据流的这些特点要求一个完整、优秀的数据流处理系统必须具有以下特点： 实时接受到达的数据，在不作存储的情况下立即处理，并且其处理速度 要求满足输入数据的速度要求。 由于数据流无边界，所以其处理结果的反馈也必须是实时的：结果即时 更新、即时可查。 其处理算法必须满足一次扫描的要求，即不再对数据做重复扫描和计算。 数据流的应用分布主要集中在实时金融数据流查询( w e b - b a s e df i n a n c i a l s e a r c h ) 、大型网站在线日志数据监控、传感器数据监控( s e n s o r m o n i t o r i n g ) 、路 4 浙江大学硕士学位论文第1 章绪论 由器数据包包头检测( n e t w o r kt r a f l i cm a n a g e m e n t ) 、以及科学计算等领域。随着 信息量的进一步爆炸，在可以预见的将来，必定会有越来越多的领域需要应用数 据流处理系统。探讨更加优秀的数据流处理算法，开发功能和处理能力更加强大 的数据流处理系统已经成为目前业界研究的热点。 当前比较著名的数据流处理系统包括应用于电子邮件过滤领域的t a p e s t r y s y s t e m 、采用最新x m l 技术的x f i l t e rc o n t e n t - b a s e df i l t e r i n gs y s t e m 、应用于连续 查询技术的o v e n c q 和s t a n f o r d 的s t r e a m ( s t a n f o r ds t r e a md a t am a n a g e r ) 等。 这些数据流处理系统大都会设计到以下这些技术细节： 1 有限内存 由于潜在的数据流大小可能非常巨大，精确计算查询结果所需的内存大小可 能无边界可言；处理数据集大小比内存大的外部存储算法( e x t e r n a lm e m o r y a l g o r i t h m s ) 的速度往往不能满足数据流处理的要求：在新数据持续不断地到达、 而旧数据甚至还在进行处理的情形下，每一数据元素分配到的计算时间必须尽可 能小，否则计算的延时就高了，使得算法跟不上数据流的速度，导致数据在缓冲 中的积累。所以，数据流的处理算法通常采用完全使用内部存储的方案，而数据 流算法的研究的一个重要方向就是在不进行磁盘存取的前提下，使系统内存使用 限定在主存大小之内。 2 非精确计算 由于限定了内存空间上限，目前很多数据流处理应用在产生精确回答方面是 不太可能的，而高质量的近似回答成为一种可以接受的解决办法。这就要求对数 据采样一些缩减技术( d a t ar e d u c t i o n ) 和大纲结构相关技术。这方面的技术包括 s k e t c h e s 、r a n d o ms a m p l i n g 、h i s t o g r a m s 、w a v e l e t s 等。 3 滑动窗口 数据流处理系统通常采用滑动窗1 ：3 ( s l i d i n g w i n d o w ) 实现数据采集操作。采 用滑动窗口主要有三个好处：待处理数据集能够更容易地定义和被理解；具有确 定性( d e t e r m i n i s t i c ) 特征，不会因为随机选择不当导致近似结果误差的问题：相 比旧的数据，更强调最近的数据，符合实时系统应用的特点。而滑动窗1 3 主要有 时序( t e m p o r a l ) 和序列( s e q u e n c e ) 的差别。前者关注数据的时序性，根据数 据的时间戳确定滑动窗口的变化；后者关注数列的序列统计，以数量统计作为滑 动窗口内容变化标准。 4 批处理、采样以及大纲技术 这三种技术的目的都是一样的提高处理效率，以使处理的速度跟得上数 5 浙江大学硕士学位论文 第l 章绪论 据输入的速度。批处理即采用一定量的数据缓冲，当输入数据达到一定量的时候 一起处理，从而避免到达即处理的情况，提高处理速度。采样技术则是通过忽略 一些输入的方式提高处理速度。但是采用这种技术的查询是在部分数据流样本上 进行计算，对由抽样处理引入的错误程度，通常采用给定置信边界( c o n f i d e n c e b o u n d s ) 的方式确定。在很多场合，特别是包含连接操作的查询场合，这种方法 是不可靠的。大纲处理的速度比前两种都要更快，但是这种技术能够满足的精确 度更低。这种处理技术通常设计一种近似的数据结构，维护小的数据大纲或者数 据的概要( s k e t c h ) ，而非精确的表示，因此，平均用于每个数据元素的计算时间 是很小的。 5 查询操作符以及二次查询 查询操作符在数据流上通过目前的已经获得的数据和自定义的操作产生查询 的中间结果，并把这种中间结果输入到下一个数据流处理系统中，该系统可以是 一个新的数据流处理系统，也可以是本系统中另一个自定义的操作符。二次查询 则是对经典的数据流次扫描策略的创新。通过采样、大纲等技术以确定的空间 保存过去的数据信息，让针对数据流的多次扫描也成为可能。 1 5 频繁项挖掘技术概述 频繁项挖掘起源于购物篮分析。该过程通过发现顾客放入其购物篮中不同商 品之间联系，分析顾客的购物习惯。这种关联的发现可以帮助零售商制定营销策 略。频繁项挖掘技术的研究从静态集合上的精确的多次扫描算法开始。 1 5 1 经典静态集合的频繁项挖掘 a 研嘶算法l l6 j 是一种最有影响的挖掘布尔关联规则频繁项集的算法。a p r i o r i 使用一种称作逐层搜索的迭代方法，矗项集用于探索( j ) 项集。首先，找出频繁 j - 项集的集合。该集合记作上j 。j 用于查找频繁2 - 项集的集合2 ，而三2 用于查找 上，如此下去，直到不能找到频繁缸项集。查找每个肌需要一次数据库扫描。为 提高频繁项集逐层产生的效率，一种称作a p r i o r i 性质的重要性质用于压缩搜索空 间。 a p r i o r i 定律：频繁项集的所有非空子集都必须也是频繁的。a 嘶o f i 定律基于 如下观察：根据定义，如果项集环满足最小支持度阈值s ，则环是频繁的，即 日砂 结果归并与存储子系统 图2 - 1f e n s t e r - s 系统结构 图2 一l 是f e n s t e r 标准结构系统( 下文将用f e n s t e r - s 表示，s 取s t a n d a r d 的首 浙江大学硕士学位论文 第2 章系统框架设计 字母) 模块关系图。该系统通过从个数据流上截获并复制流，实现基于数据流 的频繁项挖掘功能。该图描述了上面所述的三个子系统相互之间的关系以及同其 他应用模块之间的关联。 这三个模块的功能分别如下。 数据流处理子系统负责接受数据流、评估频繁项挖掘子系统运行性能、实现 流调度和频繁项挖掘子系统管理。 频繁项挖掘子系统维护批量处理缓冲窗口、算法框架和结果本地管理。 结果归并和存储子系统完成从频繁项挖掘子系统获得的增量结果流，维护最 终结果存储以及在线查询功能。 实际上，f e n s t e r - s 并不是系统的实际运行模式。该结构图只是演示了系统运 行的主要框架。 除了图2 1 所示的f e n s t e r - s 系统之外，f e n s t e r 还有如图2 2 和图2 3 所示的 精简结构和扩展结构： | 本地数繁模拟模 吲 弋适夕 i 频繁项挖掘子系统 尊 f 结果本地输出模块 图2 - 2f e n s t e r - c 系统 f e n s t e r 精简结构( 下文将用f c n s t e r - c 表示，c 取c o m p r e s s e d 的首字母) 简化了 数据流处理环节和结果本地输出环节，省略了模块之间的网络连接，把功能集中 到一台服务器上完成，即把输入和输出都定向到文件。这种结构的目的在于测试 结构最复杂的子系统频繁项挖掘子系统，并且算法的正确性。 f e n s t e r 扩展结构( 下午将用f e n s t e r - d 表示，d 取d i s t r i b u t e d 的