（计算机系统结构专业论文）基于数据流的关联规则算法研究与实现.pdf

摘要 摘要 随着网络的迅速发展和普及，分布式计算的研究在9 0 年代后达到 了高潮，目前，在i n t e r n e t 网上分布式计算已非常流行。分布式计算研 究主要集中在分布式操作系统研究和分布式计算环境研究两个方面。在 过去的2 0 多年问出现了大量的分布式计算技术，如中间件技术、网格 技术、移动a g e n t 技术、p 2 p 技术以及最近推出的w e bs e r v i c e 技术等。 每一种技术都在特定的范围内得到了广泛的应用。但是，随着无线网络 容量、带宽的增大，移动设备的快速发展和应用，开始提出了移动分布 式的计算环境。移动挖掘正是在此基础上提出的。 移动挖掘的最大特点是面向数据流。移动设备资源有限以及数据流 的高速、无限、随时间变化的特性给移动挖掘带来了挑战。 因而，本文作如下研究，以解决在移动平台上的关联规则挖掘的问 题。 1 充分利用f p 一树的紧密性，在此基础上利用滑动窗口的近似策 略，解决数据流高速性，无限性等特点，提出一个基于整个数 据流历史频繁计数的数据流频繁模式算法d s m f p i 。 2 研究f p g r o w t h 频繁模式生成过程，发掘内在并行性，提出一 个适合在移动分布式平台应用的数据流频繁模式挖掘算法 d s m f p 2 ，充分利用移动计算平台上分散的计算能力； 3 在理论分析和实例分析的基础上，设计实现算法，再次通过实 验验证所提出的两个算法的正确性和扩展性。与传统的关联规 则算法相比较，在保持正确性的基础上，提高性能，稳定性和 扩展性。 目前对于数据流的研究，由于实验条件不充分，国内还开展的很少。 本文的研究意义在于通过对传统算法的改进，设计出适合移动环境的算 法，对数据流挖掘进行有益的探索。 关键词数据流；数据流管理系统：频繁模式树；模式增长 a b s t r a c t a b s t r a c t w i t ht h ef a s td e v e l o p m e n ta n dd i s s e m i n a t i o no fn e t w o r k ，r e s e a r c ho n d i s t r i b u t e d c o m p u t i n g r e a c h e si t sc l i m a xi n 19 9 0 s a n dn o w a d a y s ， d i s t r i b u t e d c o m p u t a t i o n i s p o p u l a r i n t h ei n t e r n e t r e s e a r c h e r so f d i s t r i b u t e dc o m p u t a t i o nf o c u so nt w oa s p e c t s ，d i s t r i b u t e do p e r a t i n gs y s t e m a n dd i s t r i b u t e dc o m p u t i n ge n v i r o n m e n t a n di nt h el a s t2 0y e a r s ，m a n y c o m p u t i n gt e c h n o l o g i e sc a m ei n t ob e i n g ，s u c ha sm i d w a r et e c h n o l o g y ，g r i d c o m p u t i n g ，m o b i l ea g e n t ，p 2 pt e c h n o l o g ya n dr e c e n t l yt h ew e bs e r v i c e e a c ht e c h n o l o g yi s w i d e l ya p p l i e di nap a r t i c u l a rf i e l d h o w e v e r ，w i t h g r o w t ho fw i r e l e s sn e t w o r kb a n d w i d t ha n dc a p a c i t ya n dd e v e l o p m e n ta n d a p p l i c a t i o no fm o b i l ed e v i c e ，m o b i l ed i s t r i b u t e dc o m p u t i n ge n v i r o n m e n ti s p u tf o r w a r d 。i nt h i ss e n s e ，m o b i l em i n i n gi sb r o u g h tu p t h em o s ts i g n i f i c a n tc h a r a c t e r i s t i co fm o b i l em i n i n gi st oh a n d l ed a t a s t r e a m s d a t as t r e a mi sh i g hs p e e d ，i n f i n i t ea n dt i m ev a r y i n g ，w h i c hw i t h l i m i t e dr e s o u r c ei nm o b i l ed e v i c ef l i n g sd o w nac h a l l e n g et om o b i l em i n i n g t h e r e f o r e ，t h i st h e s i sd o e ss o m er e s e a r c h e st os o l v ep r o b l e m so fm i n i n g a s s o c i a t i o nr u l e so nm o b i l ep l a t f o r m 1 c o m p a c t n e s so ff p t r e e i sw e l lm a d eu s eo f b a s e do nt h i s ， a p p r o x i m a t i o np o l i c y o f s l i d i n g w i n d o w si su s e dt om e e tt h e c h a l l e n g e so fh i g hs p e e da n di n f i n i t y a n dt h e n ，ad a t as t r e a m f r e q u e n tp a t t e r na l g o r i t h mb a s e do nf r e q u e n tc o u n t i n go v e re n t i r e h i s t o r y ，d s m f p1 ，i sd e v i s e d 2 p a t t e r n g r o w t h o ff p - g r o w t hi s i n v e s t i g a t e d a n di t si n h e r e n t p a r a l l e l i s mi se x p l o r e d t h u s ，ip r o p o s ead a t as t r e a mf r e q u e n t p a t t e r nm i n i n gd s m f p 2 ，w h i c hi s s u i t a b l ef o rm o b i l ed i s t r i b u t e d p l a t f o r mt ot a k ef u l l ya d v a n t a g eo fc o m p u t i n gc a p a c i t yi nm o b i l e e n v i r o n m e n t 3 a f t e rt h e o r e t i c a la n a l y s i sa n di l l u s t r a t i o n ，id e s i g na n di m p l e m e n t t h ea l g o r i t h m s ，v e r i f yt h e i rc o r r e c t n e s sa n ds c a l a b i l i t y c o m p a r e dt o t r a d i t i o n a l a l g o r i t h m ，n e w m e t h o d so b t a i nb e t t e r e x p e r i m e n t p e r f o r m a n c e ，b e t t e rs t a b i l i t ya n ds c a l a b i l i t y ，w h i l ek e e p i n gh i g h c o r r e c t n e s s tt 华南理工大学硕士学位论文 p r e s e n t l y ， b e c a u s eo f i n s u f f i c i e n t e x p e r i m e n tr e q u i r e m e n t s ， d o m e s t i c a l l yf e wp e o p l ea r ed o i n gr e s e a r c ho nd a t as t r e a m s o ，m yr e s e a r c h b e a r st h es e n s et h a tt h r o u g hs o m ei m p r o v e m e n to nt r a d i t i o n a la l g o r i t h ma n d d e v i s i n gs o m ea l g o r i t h m sa d a p t i v et om o b i l ee n v i r o n m e n t ，im a k es o m e p r o f i t a b l ee x p l o r a t i o na b o u td a t as t r e a mm i n i n g k e y w o r d s ：s t r e a md a t a ；d a t as t r e a mm a n a g e m e n t s y s t e m ；f p - t r e e ； f p g r o w t h ； i i i 华南理工大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研 究所取得的研究成果。除了文中特另, j d n 以标注引用的内容外，本论文 不包含任何其他个人或集体已经发表或撰写的成果作品。对本文的研 究做出重要贡献的个人和集体，均已在文中以明确方式标明。本人完 全意识到本声明的法律后果由本人承担。 作者签名： 驰蕾话日期：j m 璋舌月一日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定， 同意学校保留并向国家有关部门或机构送交论文的复印件和电子版， 允许论文被查阅和借阅。本人授权华南理工大学可以将本学位论文的 全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫 描等复制手段保存和汇编本学位论文。 保密口，在年解密后适用本授权书。 本学位论文属于 不保密口。 ( 请在以上相应方框内打“”) 作者签名：岬纯t 磐日期：协5 - 年石月j 日 导师签名：以专n 日期：厂年6 月矿日 第一章绪论 1 1 课题背景 第一章绪论 随着网络的迅速发展和普及，分布式计算的研究在9 0 年代后达到了 高潮，目前，在i n t e r n e t 网上分布式计算己非常流行。分布式计算研究主 要集中在分布式操作系统研究和分布式计算环境研究两个方面。在过去 的2 0 多年间出现了大量的分布式计算技术，妇中阊件技术、网格技术、 移动a g e n t 技术、p 2 p 技术以及最近推出的w e bs e r v i c e 技术等。每一 种技术都在特定的范围内得到了广泛的应用。但是，随着无线网络容量、 带宽的增大，移动设备的快速发展和应用，开始提出了移动分布式的计 算环境。 数据挖掘技术是在海量数据中发现规律模式等有用的知识，为企业 决策作支持。其中，频繁模式的挖掘是数据挖掘研究的一大热点，尽管 频繁模式挖掘被广泛的研究与应用，数据流计算环境对数据挖掘提出了 新的挑战。与静态的事务数据集相比较数据流的情况需要记录更多的 信息，而且也更复杂。 目前数据挖掘已进入第四代系统的研究。第四代数据挖掘系统即移 动挖掘系统，系统的最大特色是把挖掘的环境转移到嵌入式设备和移动 环境。自2 0 0 2 以来移动数据管理召开了两次国际会议，主要讨论问题 都是围绕u b i q u i t o u s 这一环境特征，讨论如何管理u b iq u i t o usd a t a ， 开发移动设备上的复杂计算程序和进行移动挖掘。 移动挖掘与传统挖掘方法不同，具有很多独特的地方。它们会令传 统数据挖掘算法失效，主要原因是应用不同，算法要根据应用定制： b 传统的数据挖掘系统，面向的应用是知识发现，模式识别， 决策支持，预测预警等等，它们关心挖掘结果的正确性、完 整性，这类应用计算密集，计算时间长。 c 移动挖掘，属于第四代的数据挖掘系统，面向移动用户，用 户需要获得的是即时的挖掘结果，对于一些检测和监控的程 序，甚至需要处理实时数据，获得实时结果和实时反馈。 华南理工大学硕士学位论文 1 2 当前研究状况 对于数据流所引起的问题，有一些简单的数据预处理方法，被广泛 采用的，下面作些介绍。 1 2 1 适应输入数据率 该策略包括了抽样、过滤、聚集和负载脱落，如图l l 所示。抽样是 一种运用统计方法来选择部分输入数据流的技术。过滤本质是语义采样， 它对每个数据流的元素进行分析，抛掉那些认为不重要的元素。聚集操 作把一个向量影射成一个标量，这个标量是统计结果，反映原本数据的 统计特性。负载脱落与抽样、过滤、聚集不同，它所作用的对象不是整 个数据流，不像前面几种策略一样检查数据流里面的全部元素，当数据 率过高时，它会不加判别地丢弃数据流里的数据，所以会严重影响准确 性。 d 矾曲。 件d m 毒柑n 一：7 ： o 城p 饿l ”潮hm 弹 图卜l适应输入数据率算法( 采样) 1 。2 。2 数据抽象方法 对现实世界建模，会形成一个层次结构图。通常，接收的数据流数 据属于层次结构中比较底层的对象。根据后继分析的需要，有选择地采 用高层次的抽象对象来分类减少数据值种类。这种方法结合数据流按 时间分段技术，可以统计每个时间段的数据种类和出现次数，不必记录 全部数据，降低内存需求简化后面的挖掘算法。合理划分出时间段是时 态数据挖掘研究内容。 2 皋 第一章绪论 1 2 3 近似算法 在可接受的误差极限内，设计一次遍历的挖掘算法来获得近似的挖 掘结果。就如上面所多次提到的，在资源有限的情况下，不采取近似的 措施几乎是不可能的，选择与设计挖掘算法是移动挖掘系统设计的关键。 1 2 4 a o g 算法( a l g o r i t h mo u t p u tg r a f l u l a r i t y ) 算法的基本思路如下1 2 】，如图l 一2 ： a 首先确定时间闽值和算法输出粒度； b 由数据速率，计算算法输出率和算法阈值： c 用算法阈值来挖掘数据流； d 一个时间段后，由数据率增( 减) 量，用线性回归方法调整算法 阈值： e 重复上面c ，d 两步直到最后的一个时间区问。 1 3 频繁模式算法 图1 2a o g 算法 频繁模式与关联规则挖掘阀题首先出【3 】提出，它是很多其它挖掘问 题的基础。频繁模式与关联规则挖掘根据数据类型可分为布尔型与数量 型，根据规则涉及的数据维数分为单维与多维，根据规则集涉及的抽象 层次分为单层与多层，根据模式与规则间的相互关系分为完全、最大、 闭合型。关联规则挖掘问题还可以拓展为顺序模式挖掘、周期性片断挖 掘、空间关联规则挖掘等问题等。 3 华南理1 二大学硕士学位论文 a g r a w a l 提出的a p r i o r i 算法”5 l 是挖掘关联规则的最基本、最具影 响的核心算法，用于挖掘单层单维布尔型的频繁模式。a p r i o r i 算法的基 础是频繁模式的( 反) 单调性原则，即频繁模式的子模式必定是频繁的，而 包含非频繁模式的超级模式必定是非频繁的。m a n n i l a 等同时独立提出了 一个与a p r i o r i 等价的算法，称为o c d l 6 1 。 对于a p r i o r i 的改进主要在于控制候选集的规模或减少数据库扫描次 数，并有以下几个方面研究成果： 1 s a v a s e r e 等提出了p a r t i t i o n 算法【7 l 将数据库分割为若干个可调入 内存的子库，分别求出各个子库的局部频繁模式，所有局部频繁模式的 并集为全局频繁模式的候选集，最后一遍扫描数据库可最终求出全局频 繁模式集。p a r t i t i o n 考虑的候选集比a p r i o r i 还要多，有可能更加剧了组 合爆炸的问题。 2 文献【8 】提出了抽样法。即从数据库中随机抽取一个可调入内存的 子集，采用一个略低的支持率阀值，求出该子集中的局部频繁模式，第 二遍扫描数据库，求出局部频繁模式的全局支持率。该文还提出了确保 全局频繁模式不被遗漏的机制。 3 b r in 等提出了动态模式计数法d i c b l ，即在同一遍数据库扫描过 程中分段增加候选频繁模式集。一般来讲，长度为k 的模式的支持数要 在第k 遍数据库扫描时，才进行统计。d i c 在确定一个模式的所有子集都 是频繁后，不久就开始其支持率的统计，而不是等到下一轮数据库扫描。 4 文献f 1 0 】提出了一种有趣的算法t r e e p r o j e c t i o n ，它将频繁模式挖 掘转化为逐步构造一种模式字典树的过程，与之相伴随的是将一个大型 数据库投影为一系列予库的过程。t r e e p r o j e c t i o n 直接对数据库进行投影， 投影子库可以用某种形式存放或直接扫描原始数据库临时产生，投影的 策略有宽度优先、深度优先、混合投影等三种策略。 5 文献【1 1 】提出了不生成候选集直接生成频繁模式的算法 f p g r o w t h 。其基本思想是将整个数据库压缩表达为一个存放在内存中的 f p t r e e ，将频繁模式挖掘过程转化为递归地产生“条件”子库及对应的 “条件”f p t r e e 的过程。 1 4 研究内容与本文结构 在基于内存的频繁模式挖掘算法中，f p t r e e 存储结构使得事务集可 以压缩在有限的空间，而且f p g r o w t h 的效率较高，因此适合于应用在 4 第一章绪论 资源紧缺的移动设备上。 本文主要研究内容： 1 发挥了f p ，树的紧密性，利用滑动窗口的近似策略，解决数据流 高速性，无限性等特点，提出一个基于内存的数据流频繁模式 算法d s m f p l ： 2 研究f p g r o w t h 频繁模式生成过程，发掘内在并行性，提出一 个分布式的数据流频繁模式挖掘算法d s m f p 2 ，充分利用移动 计算平台上分散的计算能力： 3 在理论分析和实例分析的基础上，设计实现算法，再次通过实 验验证所提出的算法的正确性和效率。 从第二章开始，本文结构组织如下： 第二章数据流与数据流管理系统主要介绍数据流系统的模型，数据 流模型以及查询语义。 第三章重点介绍了频繁模式树的特点，正确性和紧密性，并且重点 讨论了f p g r o w t h 的模式生成算法。并且举例说明构造的过程。在第三 章所用的例子也成为第四章讨论的对象。 第四章主要针对f p t r e e 和f p g r o w t h 的特点，结合数据流的特点， 提出了两个改进算法，分别举例说明，并且证明其正确性。 第五章是实验与分析，通过实验证明算法的正确性与可行性。 1 5 小结 本章主要介绍一类新的计算环境，数据流计算环境；然后介绍了目 前解决数据流的一些简单策略，并且概要介绍频繁模式算法，并把本文 工作设定为数据流上的关联规则挖掘算法研究与实现，提出研究思路。 5 第二章数据流与数据流管理系统 第二章数据流与数据流管理系统 传统数据库已经在持久数据存储和复杂查询中得到广泛应用，通常 数据存储的是些无序的对象，在这些对象上，查询操作比插入、更薪、 删除操作要多。每个查询操作是非连续的，只对当前状态的数据库数据 进行查询。但是近几年出现了一些应用，它们并不适应这种数据模型和 查询案例。取而代之，信息是以一列数据的形式出现，包括传感器数据、 i n t e r n e t 流量数据、财务收报机、事务日志以及电话呼叫记录。本章将对 数据流以及数据流管理系统作简要介绍。 2 1 数据流的特点 对比传统关系型数据，数据流具有以下几个特点“： a ，数据记录是动态的，即数据不是静态的，存储在管理系统中以备 使用。 b 数据流管理系统d s m s 无法知道下个到达的数据是什么，甚至在 同一个数据漉中，d s m s 也无法控制待处理的数据记录的顺序。 c 本质上，数据流的长度是无限的，查询处理的数据流是高速的， 连续的，随时间变化的。 d 数据流中的记录一旦被处理，可能抛弃，也可能归档；无论是哪 一种处理方式，很难重新查询。当然有部分可以存放在主存中，例如 聚集函数。a v g ，s u m ，c o u n t 等，它们运算结果可以被记录存储，但 具体细节无法追踪。 e ，在数据流处理中，可能会结合d b m s 。例如，某一次数据查询中， 可能需要用到关系数据库中的数据，例如，连接操作，可能把数据流与 关系表连接，以获得所需的数据流。 2 2数据流管理系统抽象参考模型 文献【13 】介绍了数据流管理系统的参考模型，如图2 一l 7 华南理工大学硕士学位论文 禽埘c 湘q 泔由 图2 1数据流管理系统参考模型 系统的模型由五个部分组成： 1 输入检测器调节输入的数据流。当无法与数据流同步的时候，可能 会抛弃些数据包； 2 流数据通常存放在三个地方，工作存储器存放输入监测器接收的数 据，以便于滑动窗口查询，概要存储器存放数据流的概要数据和一些聚 集结果。静态存储器存放元数据以及数据源的位置； 3 查询仓库记录了所有注册的数据查询： 4 查询处理器负责调度每个查询，优化查询，生成查询结果 5 输出缓冲器缓冲查询结果的输出流，传送到用户端。 目前，从事这项研究的较有代表性的有斯坦福大学，伯克利分校以 及布朗大学等。其中比较出名的原型系统有：斯坦福大学的s t r e a m 系 统，伯克利分校的t e l e g r a p h c q 系统和布朗大学的a u r o r a 原型系统等。 s t r e a m 原型系统是一个数据流管理系统，他着重处理在内存有限 的条件下计算查询近似结果情况【。 t e l e g r a p h c q 是一个自适应的数据流系统，它用自适应的查询执行引 擎来处理各种情况下的数据流f j 。 a u r or a 系统是一个数据流的监视系统，它允许用户定义触发器形成 触发器网，并且在运行时会对触发器网进行优化【1 6 1 。 由于数据流中所有的数据不可能存储在传统的关系数据库中：而且， 数据流系统中的数据处理技术和传统关系数据库有着差异现有的处理技 术不适用于数据流处理。为了能够有效地实现数据流处理过程，我们必 须研究出适用于数据流处理的方法和技术。 8 命岛岛瓣 苟唏唏j 茎 第二章数据流与数据流管理系统 2 3 d s m s 与d b m s 的区别 数据流模型与传统数据模型相比有几大特殊之处“7 1 ： 1 大规模数据实时到达： 2 深度的网络特性： 3 系统对数据顺序的不可控和对数据和环境特性不可预测： 4 数据通常只能被处理一次，随即丢失或只有有限的数据存在有限 的内存中。 因此，在这些针对数据流处理的应用系统中，我们不能简单地将数 据流存放到传统的数据库( d b m s ) 中再进行查询。因为传统的数据库并不 是为不断快速到达的连续的数据流设计的，不能直接支持数据流应用中 典型的“连续查询”。而且，在对数据流的查询和其它处理( 例如数据分 析和挖掘) 中，近似性和适应性也是两个重要特点，而传统的数据库管理 系统所注重的却是通过静态的执行计划提供精确的查询结果，与数据流 处理的需求背道而驰。 在这种情况下，数据流管理系统( d s m s ) 就应运而生了。它是专门为 处理数据流而设计的。它的处理对象与传统的数据库管理系统( d b m s ) 有 很大区别，如表2 1 。 l ，d l h ok 姒循牌日珏尔矾，11 ”o 、o i l 姒循目j 王不纠l ，1 持久的关系转瞬即逝的流 一次查询( o n e t i m eq u e r y )连续的查询 随机的访问顺序访问 “无限”的磁盘空间有限内存s 只有当前状态起作用数据的到达顺序是重要 被动的存储主动的存储 相对较低的更薪率数据传输率未知 很少实时服务实时处理 精确数据陈旧和非精确数据 查询计划静态生成不可预料的变化的数据特性 表2 - 1d b m s 与d s m s 的区别 9 华南理工大学硕士学位论文 2 4数据流查询 就如上面所介绍的，数据流的应用需要有连续查询、有序关系操作 符的查询，例如：滑动窗口操作符，在这节将介绍数据流模型和查询 语言。 2 4 1 数据模型 实时数据流是一列按某种顺序到达数据项，可能只可被一次遍历。 由于数据可能并发同时到达，所以数据流又可以看作是元素列表的序列。 每个流元素是一些关系元组或者实例化的对象，在基于关系的模型中【l ”， 项是一些存放在虚拟关系中的瞬时记录，可能水平分割在多个远程节点 中。在基于对象的模型中1 ，源及项的类型被建模为与方法关联的层次 数据类型。 流数据可能是有序或者无序，也可能被预处理，或者来被处理过， 从而派生出下面几种模型： 1 u n o r d er e dc a s hr e g is t e f ：来自不同域的数据是不经处理， 也没有特定顺序： 2 o r d e r e dc a s hr e g is t e r ：每个数据项是不经处理的，但是 以某种顺序到达； 3 u n o r d e r e da g g r e g a t e ：来自相同域的数据被聚集成一个项 目，但是数据特征项的到达是无序的； 4 0 r d e r e da g g r e g a t e ：来自相同域的数据被聚集成一个项且， 数据特征项以某种顺序到达。 在某个时间，只有部分数据流是感兴趣的，因而产生了所谓的窗口模 型。一般采用下面的几个标准来区分： 1 端点移动的方向： 两个端点固定的窗口是固定窗口( f ix e dw in d o w ) ：两个端 点同时向前或者向后定义一个滑动窗口( s l i d tr l gw in d o w ) ： 一端固定，另一端向前或者向后移动的窗口是界标窗口 ( l a n d m a r k # in d o w ) 。以上3 种加两个方向的组合总共有 九种可能。 2 物理上v s 逻辑上：基于时间的模型通常以时间间隔来定一 个窗口，而在逻辑上是以元组的数目来定义时间窗口的。 3 更新间隔：饥渴重估策略是在每个元组到来时就进行更新， 1 0 第二章数据流与数据流管理系统 而懒散重估策略是成批处理一堆元组，它包含了一个“跳跃 窗口”，假如更新间隔大于窗口的大小，产生的结果是一系 列不重叠的滚动窗口。 2 4 2 连续查询的语义 在一个只能添加的数据库中，所有的连接查询都是单调的：一旦一 个元组添加迸取，它或者满足查询的条件或者不满足，在这个过程中， 满足条件并没有随时间而改变。但是，如果添加否定的语义将会违反单 调性，例如：从e m a i l 消息数据流中选出没有回复的消息。同样的，如果 数据库不是只能添加，那么所有的查询都不是单调的，因为更新数据可 能会导致条件不满足。 a r a su 等在文献“”中陈述了单调和非单调在数据流连续查询的语义。 为方便。假定时间使用自然数集合来表示，所有的连续查询时在时钟点 上重新评估，再假定，a ( q ，r ) 是在时间t 的查询结果集。t 是当前的时间， o 是开始时间。在；时间的单调连续查询的结果集； r a ( q ，r ) = u ( 爿( q ，f ) 一a ( q ，t i ) ) ua ( q ，o ) ( 2 一1 ) f = l 即使说，只需要对新到达的数据项重新评估，并且把满足条件的元 组放入结果集中，相反的，非单调查询每次重估都从新开始查询计算， 因此它的语义可以表示为： r a ( q r f ) = ua ( q ，幻 ( 2 - 2 ) 2 5 小结 本章主要介绍数据流的特点以及数据流管理系统参考模型。并且 把它跟传统的关系数据库作比较；接着介绍了数据流的模型分类和数据 流查询的语义。为在第四章的算法描述中奠定基础，数据流的关联规则 挖掘正是基于单调连续查询的语义上进行讨论的。 第三章关联规则算法 第三章关联规则算法 关联规则是表示数据库中一组对象之间某种关联关系的规则。自 1 9 9 3 年a g r a w a l 首先提出关联规则概念以来，关联规则挖掘便迅速受到 数据挖掘领域专家的广泛关注。关联规则挖掘的对象是事务数据库，借 助条形码技术，使得数据的收集变得更容易，更完整，从而可以存储大 量的是数据，关联规则挖掘的一个典型应用是购物篮分析。在超市购物 篮分析中，可以认为每个事务表示一个顾客的购物行为，而事务对应的 项目表示顾客一次性购买的商品。该过程通过发现顾客放入其购物篮中 不同商品之间的联系，从而分析顾客的购买习惯。例如“8 0 的顾客在购 买笔记本电脑的同时也会购买数码相机”。这种关联发现可以帮助零售商 制定营销策略。譬如，超市经理可以将笔记本电脑和数码相机放在一起， 以便在销售笔记本电脑的同时刺激数码相机的销售。关联规则挖掘还广 泛应用于商品目录设计、贱卖分析、网络入侵检测、生物序列检测等。 3 1 关联规则的概念 3 1 1 基本概念及问题描述 a g r a w a l 等人首先定义了在事务数据库中挖掘关联规则的问题。 设i = i l ，i2 ，i 。 是由m 个不同的项目组成的集合。给定一个事务数 据库t d b ，其中的每一个事务t 是i 中一组项目的集合，即t ，y 有一个 唯一的标识符t i d 。 定义2 1 假设项目集x 是i 中项目的集合，如果x 包含k 个项目，那 么称x 为k 一项目集。 定义2 2 如果项目集z t ，则我们称事务t 满足项目集x ：项目集x 在事务数据库t d b 中的支持度，记为s u p p o r t r v s ( x ) ，即事务数据库t d b 中 满足项目集x 的事务数。 定义2 3 如果项目集x 在事务数据库中的支持度不小于用户或专家给 定的最小支持度阀值，那么称项集x 为大项目集或频繁项目集：反之称之 为小项目集或非频繁项目集。 定义2 4 一条关联规则就是形如x = y 的蕴涵式，其中z 量，r ， 1 3 华南理工大学硕士学位论文 n y = 巾。x 称为规则的前件，y 称为规则的后件。关联规则x = y 成立 的条件是满足：支持度s ，即事务数据库t d b 中至少s 的事务包含 x u r ；置信度，c 2 s u p p o r t w e ( x u y ) s u p p o r t m b ( x ) ，即事务数据库t d b 包含x 的事务中至少有c 的事务同时也包含y 。 同时满足最小支持度阀值( m in s u p ) 和最小置信度阀值( m inc o n f ) 的关联规则称为强关联规则。关联规则的挖掘问题就是在事务数据库d 中找出满足用户或专家给定的最小支持度和最小置信度的强关联规则。 项目集在事务数据库了d b 中的出现频率是包含项目集的事务数，简记为 项目集的频率、支持计数或计数。如果项目集的出现频率大于或等于 m in s u p 与t d b 中事务总数的乘积，则我们说项目集满足最小支持度 m ins u p 。频繁k 项目集的集合通常一记作l k 。 关联规则挖掘可以分解为下列两个子问题”“2 0 1 ： 找出所有频繁项目集：这些项目集出现的频率满足最小支持度 m i ns u p ，即这些项目集在t d b 中的频繁性不小于最小支持计数。 由频繁项目集产生强关联规则：这些规则必须满足最小置信度 j l l i nc o n f 。当然，除了这两个度量标准以外也可以使用附加的度量，例 如兴趣度( in te r e s t in g ) 度量等。在这两个子问题中，第二个子问题最容 易，找出所有频繁项目集以后，产生用户感兴趣的强关联规则是很自然 的事情，文献 3 2 0 己经给出了较好地解决第二个子问题的算法。目前 大多数的研究工作主要集中在第一个子问题上，关联规则挖掘的总体性 能主要由它得到解决的好坏来决定。因此，本文论述的内容针对第一个 子问题进行。 3 1 2 关联规则的分类 购物篮分析出的规则仅是关联规则挖掘的一种形式。事实上，有挖 掘关联规则很多种。根据不同的标准进行分类： ( 1 ) 基于规则处理的值的类型，关联规则可以分为布尔型和数值型。 如果关联规则只考虑项在还是不在某个集合中，它就是布尔关 联规则。布尔型关联规则处理的值都是离散的、种类化的，它显 示了这些变量之间的关系。如果规则描述量化的项与属性之间的 关联，则它是量化关联规则。量化关联规则可以和多维关联或多 1 4 第三章关联规则算法 层关联规则结合起来，对数值字段进行处理。 例如： 性别= “女”= 职业= “秘书”是布尔型关联规则。 年龄= “3 0 3 9 ”八收入= “4 2 k - 4 8 k ”= 购买高质量产品。年 龄和收入是都是量化的类型，所以是一个量化关联规则。 ( 2 ) 根据规则中涉及数据的维数，可以分为单维关联规则和多维关联 规则。 如果关联规则中的每个项、属性只涉及一个维，则它是单维关 联规则。 例如： b u y ( x ，”c o m p u te r ”) = b u y ( x ，”f in a n c i a l m e t n a g e m e n t s o f t w a r e ”) 。 它仅涉及一个维( b u y ) ，这是一个单维的关联规则。 如果规则涉及两个或多个维，则它是多维关联规则。在( 1 ) 中 的第二个规则涉及了年龄、收入、购买三个维，因而它是多维关 联规则。 ( 3 )根据规则集所涉及的抽象层，可分为单层关联规则和多层关联规 则。 有些挖掘方法可以在不同的抽象层次发现规则。 例如： a g e ( x ，“3 0 3 9 ”) = b u y ( x ，“l a p t o pe o m p u t e r ”) a g e ( x ，“3 0 3 9 ”) = b u y ( x ，“c o m p u t e f ”) 两则规则的抽象层次是不同的，c o m p u te r 的比1 a p t o pc o m p u t e r 要抽象层次更高，因为膝上电脑属于在电脑范畴。因此，我们可 以直观的想象出，它们之间可以有不同的支持度与置信度。而且 后者要比前者的支持度高，至少是等于。像这种集合包含的思想 经常用在关联规则的挖掘上。 ( 4 ) 根据关联规则的各种扩充，关联规则可以扩充到相关分析。 3 2 层次迭代算法 1 9 9 3 年，a g r a w a l 等人首先提出了挖掘关联规则的基本算法a i s 3 1 。 于产生的候选项目集太大，于是a g r a w a l 等人在1 9 9 4 年提出a p r i o r i 算 法4 1 。a p r i o r i 算法使用一种称作逐层迭代的候选产生测试( c a n d i d a t e g e n e r a t i o na n dt e s t ) 的方法，k 一项目集用于探索( k + 1 ) 项目集。首先，找出 华南理工大学硕士学位论文 频繁项目集的集合，该集合记作l l 。l t 用于找频繁项目集的集合l 2 ，而 l 2 用于找l 3 。如此下去，直到不能找到频繁k 项目集。每找一层l k 均需 要一次数据库扫描。 算法a p r i o r i 描述如下： 算法2 1 ( a p r i o r i 算法，使用根据候选生成的逐层迭代找出频繁项 目集) 输入：事务数据库t d b ：最小支持度阈值m i ns u d ， 输出：t d b 中频繁项目集l 方法： (1)ll=fi n d f r e q u e n t 一卜i t e m s e t s ( t d 3 ) ( 2 )f o r( k = 2 ：l k l o ：k + + ) ck = a p t i o r i g e n ( l k _ i ，m ins o p ) f o rt t d bd o 扫描t d b 用于计数 c t = s u b s e t ( c k ，t ) ：生成候选子集 f o r 每一个候选项目集c c td o ( 1 0 ) l k = c c k 1 3 c o u r t t = m if i _ s u p ) 1 6 )； 3 4 5 6 7 8 9l(； 第二章关联规则算法 l k + 1 为频繁( k 一1 ) 项目集；m i f l _ s u p 为最小支持度阈值 ( 1 )f o r 每个项目集1 1 l k + ld o ( 2 ) ( 3 ) ( 4 ) ( 5 ) ( 6 ) ( 7 ) ( 8 ) ( 9 ) ( 1 0 ) f o r 每个项目集i2 l k + 1d o i f ( 1 1 1 = i2 t i l k 一1 只有节点 与路径 ，共享公共前缀 ，因此，树节点 计数加l ，同时创建新节点( b ：i ) ，连接作为