（计算机科学与技术专业论文）数据流频繁项集挖掘系统的研究.pdf

武汉理工大学硕士学位论文 独创性声明 本人声明 所呈交的论文是本人在导师指导下进行的研究工作及取得的研究 成果 尽我所知 除了文中特5 l i j j r l 以标注和致谢的地方外 论文中不包含其他人 已经发表或撰写过的研究成果 也不包含为获得武汉理工大学或其它教育机构的 学位或证书而使用过的材料 与我一同工作的同志对本研究所做的任何贡献均已 在论文中作了明确的说明并表示了谢意 研究生 签名 盔迤幽鱼日期 兰呈 f 妄竺 学位论文使用授权书 本人完全了解武汉理工大学有关保留 使用学位论文的规定 即 学校有权 保留并向国家有关部门或机构送交论文的复印件和电子版 允许论文被查阅和借 阅 本人授权武汉理工大学可以将本学位论文的全部内容编入有关数据库进行检 索 可以采用影印 缩印或其他复制手段保存或汇编本学位论文 同时授权经武 汉理工大学认可的国家有关机构或论文数据库使用或收录本学位论文 并向社会 公众提供信息服务 保密的论文在解密后应遵守此规定 研究生 签名 缸导师 签名 武汉理工大学硕士学位论文 摘要 随着信息技术的发展 新型的数据流模型出现在数据挖掘领域中 这使得该 领域的发展出现了新的挑战 由于数据流的动态性 使得已有的针对静态数据的 成熟挖掘技术无法对这种连续到达 无限规模的数据进行有效的信息挖掘 所以 对于数据流的挖掘逐渐成为国内外研究人员的关注点 对于数据流挖掘的研究 可以应用在广泛的生活环境中 比如电信行业 大型连锁超市销售行业 多传感 器网络领域以及网络监控领域都有其存在应用的意义 带着如此规模巨大的应用 前景 相信数据流挖掘技术会飞速发展 本文在引入数据流挖掘的相关概念及数 据挖掘中相关算法理论的同时 主要研究了数据流中频繁项集挖掘的问题 提出 了一个基于c a n t r e e 概要数据模型的数据流频繁项集挖掘系统的实现方法 在 该系统实现中 改进了概要数据模型的构建方式 提出与之匹配的频繁模式挖掘 算法 并通过多次实验得出结果 并做了结果分析 本文主要涉及到以下几个方 面的内容 1 引入数据流挖掘概念 对比静态数据 讲述数据流的概念 发展过程及 其特点 介绍当前存在的一些数据流模型构建算法 数据挖掘中关联规则和频繁 模式挖掘的一些经典算法 介绍数据流管理系统目前的发展现状及特点 2 设计了基于c a n t r e e 结构的概要数据模型 引入训练的思想 使用前期 数据流事务集构建基本有序的项头表 提高了后期子树的压缩率 改进子树的结 构 使其更符合后期的频繁模式挖掘的需要 3 提出了f p m c 算法 在基于改进的c a n t r e e 结构上 提出了一种快速的 频繁模式挖掘算法 省去了以往的递归思想 使得后续的挖掘过程中尽量节省资 源 提高挖掘速度和效率 使其更符合动态的数据流挖掘的思想 总体上讲 通过多次实验证明 系统基本满足了预期的设计期望 实现了一 个基本符合数据流挖掘系统定义的完整应用系统 关键字 数据流挖掘 频繁模式 c a n t r e e 概要模型 武汉理工大学硕士学位论文 a b s t r a c t a st h ed e v e l o p m e n to fi n f o r m a t i o nt e c h n o l o g y t h en e wd a t as t r e a m i n gm o d e l s a p p e a ri nd a t am i n i n gf i e l d i tm a k e san e wc h a l l e n g ei nt h ef i e l d s b e c a u s eo ft h e d y n a m i cc h a r a c t e r i s t i c s o fd a t as t r e a m i n g m a k i n gt h ee x i s t i n gd a t am i n i n g t e c h n o l o g yi ns t a t i cd a t ac a n n o tr e a c he f f e c t i v e l yw i t hi n f i n i t es c a l ef o rt h ed a t a s o t h ei n f o r m a t i o no fd a t as t r e a m sm i n i n gg r a d u a l l yb e c a m e st h ed o m e s t i ca n d i n t e r n a t i o n a lr e s e a r c h e r s c d n c e r l 鸠 t h er e s e a r c hf o rd a t as t r e a mm i n i n gc a nb e a p p l i e di nab r o a dr a n g eo fl i v i n ge n v i r o n m e n t s u c ha st e l e c o mi n d u s t r y l a r g e s u p e r m a r k e tc h a i ns a l e si n d u s t r y m u l t i s e n s o rn e t w o r kf i e l da n dn e t w o r km o n i t o r i n g d o m a i nh a si t se x i s t i n ga p p l i c a t i o ns i g n i f i c a n c e w i t hs u c hal a r g es c a l ea p p l i c a t i o n p r o s p e c t b e l i e v et h a td a t as t r e a mm i n i n g st e c h n o l o g yw i l lb ed e v e l o p e dr a p i d l y b a s e do ni n t r o d u c i n gc o n c e p t si nd a t as t r e a mm i i l i n ga n da l g o r i t h m si nd a t am i n i n ga t t h es a m et i m e t h i sp a p e r sr e s e a r c hf o c u so nt h ef r e q u e n ti t e m s e tm i n i n gp r o b l e m si n d a t as t r e a m a n dp u tf o r w a r daf r e q u e n tp a r t t e r nm i n i n gs y s t e mo nd a t as t r e a m t h r o u g has u m m a r ym o d e lb a s e do nc a n t r e e 1 l 凹o u g ht h i sp r o g r e s s t h ep a p e r r e p r e s e n t sa ni m p r o v i n gm e t h o d so fc o n s t r u c t i n gt h es u m m a r ym o d e la n das u i t a b l e f r e q u e n tp a t t 锄m i n i n ga l g o r i t h m f i n a l l y i ti n t r o d u c em u l t i p l et e s t sr e s u l t sa n d a n a l y s i so ft h er e s u l t s t l l i sp a p e rm a i n l yi n v o l v e st h ef o l l o w i n gs e v e r a la s p e c t so f l i n t r o d u c i n gd a t as t r e a mm i n i n gc o n c e p t s b yc o m p a r i n gt h es t a t i cd a t a t h e p a p e r t e l l st h e c o n c e p t s o fd a t as t r e a m a n di t s d e v e l o p m e n tp r o c e s sa n d c h a r a c t e r i s t i c s a n da l s o i ti n t r o d u c es o m ec u r r e n tm o d e lc o n s t r u c t i n ga l g o r i t h m so f d a t as t r e a m a n da s s o c i a t i o nm l e sa n df r e q u e n tp a r t t e nm i n i n gi nd a t as t r e a m 砸s a r t i c l ei n t r o d u c ec u r r e n td e v e l o p m e n t sa n dc h a r a c t e r i s t i c so fd a t as t r e a mm a n a g e m e n t s y s t e m 2 1 1 伦p a p e rd e s i g n sas m n m a r ym o d e lb a s e do nc a n t r e es t r u c t u r e t h r o u g h i n t r o d u c i n gat h o u g h to ft r a i n s u s et h ed a t as t r e a mi t e m s e t sc o n s t r u c t i n gb a s i co r d e r l y t a b l e t h i si m p r o v e st h ec o m p r e s s i o nr a t i oo ft h ec a n t r e e i m p r o v i n gt h et r e e s s t r u c t u r e t om a k ei tc o n f o r m st ot h en e e do fl a t e l yf r e q u e n tp a t t e r nm i n i n g 3 f p m ca l g o r i t h mp r o p o s e d b a s e do nt h ei m p r o v e dc a n t r e e ss t r u c t u r e m e n t i o n saf a s ta l g o r i t h mf o rf r e q u e n tp a t t e r nm i n i n g i tm a k e ss u b s e q u e n tm i n i n g p r o c e s ss a v i n ga sm a n yr e s o u r c e sa sp o s s i b l e a n du n p r o v m gt h em m m gs p e e da n d e 伍c i e n c y m a k ei tm o r ea c c o r dw i t hd y n a m i cd a t as t r e a mm i m n gt h o u g h t s g e n e r a l l ys p e a k i n g t h r o u g ht h ee x p e r i m e n t sp r o v e d t h ed e s i g no ft h es y s t e m m e e t st h eo r i g i n a lr e q u i r e m e n t s r e a l i z e dac o m p l e t e da p p l i c a t i o ns y s t e mw h i c h a c c o r dw i t hd a t as t r e a mm i m n gs y s t e md e f i n e d k e yw o r d s d a t as t r e a mm i n i n g f r e q u e n tp a t t e m c a n t r e e s u m m a r ym o d e l 武汉理工大学硕士学位论文 摘要 j a b s t r a c t i i 第l 章绪论 1 1 1j i i 言 1 1 2数据流挖掘发展现状以及特点 l 1 3论文的结构 2 1 4本章小结 3 第2 章数据流挖掘基本算法研究 4 2 1数据流的概念 4 2 2模型构建算法 4 2 3数据流管理系统 6 2 3 1数据流管理系统模型 6 2 3 2数据流管理系统与关系数据库管理系统的区别 8 2 3 3数据流管理系统的发展现状 9 2 4关联规则 9 2 4 1关联规则相关定义 9 2 4 2数据挖掘中关联规则分类 1 0 2 4 3关联规则算法 1 l 2 5频繁模式挖掘算法 1 6 2 5 1频繁模式挖掘概念 16 2 5 2频繁模式的挖掘过程 l7 2 5 3基于数据流的频繁模式挖掘 1 8 2 6现有c a n t r e e 结构频繁模式挖掘的主要问题 2 l 2 7本章小结 2 3 第3 章数据流频繁模式挖掘系统设计 2 4 3 1系统要解决的问题 2 4 3 2系统特点概述 2 4 3 3数据流挖掘系统的设计 2 5 3 3 1构建c a n t r e e 过程 2 5 3 3 2频繁模式挖掘过程 3 0 3 4系统的应用 3 1 3 5系统关键问题的解决 3 1 3 6 本章总结 3 2 第4 章数据流频繁模式挖掘算法流程及实现 3 3 m 武汉理工大学硕士学位论文 4 1算法所需结构体及类定义 3 3 4 1 1类定义 3 3 4 1 2结构体定义 3 4 4 2算法流程描述 3 4 4 3算法具体设计 3 5 4 3 1 c a n t r c e 结构实现过程 3 5 4 3 2频繁模式挖掘阶段 3 8 4 4本章小结 4 0 第5 章实验结果分析 一4 1 5 1实验环境 4 1 5 2 实验结果分析 4 l 5 3本章小结 4 3 第6 章系统的总结与展望 4 5 6 1 论文总结 4 5 6 2数据流挖掘的展望 4 5 致 谢 5 0 附录 1 i v 武汉理工大学硕士学位论文 1 1 引言 第1 章绪论 随着现代信息技术的飞速发展 以及计算机硬件 软件 数据存储和数据收 集技术的快速进步 数据流应运而生 这种新型的数据信息充斥着信息化领域的 各个角落 各个领域的机构和组织都可轻易生成海量的数据信息 例如气候环境 监测数据 网络监控数据 金融交易数据 网页搜索日志或是电信用户管理数据 数据流是一种高速的 连续的 无限的 时变的有序数据集序列 对于这些数据 流的挖掘可以发现很多有用的知识和信息 而这些信息是人们迫切想得到的 所 以对于数据流的挖掘和分析日益成为一个研究热点 数据挖掘技术在近十几年的发展过程中 得到了深入的研究 而频繁模式挖 掘作为数据挖掘中的一个基础任务 一直是该领域的研究热点 在例如分类问题 聚类问题和关联规则发现问题中 频繁模式挖掘都有广泛的应用 当前 在数据 流这种新型环境下研究频繁模式挖掘 同样有着深刻的意义 例如在电信行业 如果对用户选取的通信套餐进行频繁模式挖掘 就可能得到哪些套餐是用户选用 最多的 哪几个套餐是用户经常搭配使用的 有哪些套餐的推出是不能够吸引用 户的 针对这些套餐数据做进一步的分析 可有助于电信行业推出更高质量的套 餐服务 同样 在大型连锁超市商品交易中 对销售记录的频繁模式挖掘可以找 出畅销商品之间可能存在的联系 据此 超市可以改进商品的摆放位置 进一步 提高商品的销售额 在数据挖掘领域 频繁模式的理论研究和实际应用都取得大量的成果 产生 了许多经典的算法 但这些所研究的对象都只是静态数据 当这些理论和应用面 对动态数据 数据流时 则无法做到增量更新 其结果是难以适应对动态数据流 的挖掘 鉴于数据流的无限 连续 高速的特性 对算法的时间复杂度 空间复 杂度 自适应性和实时性提出了更高的要求 这给研究带来了更大的机遇和挑战 对于数据流中的频繁模式挖掘 当前的许多研究人员和组织都进行了广泛的研 究 1 2 数据流挖掘发展现状以及特点 所谓的静态数据就是存储于数据库中的数据 以数据流形式的数据相应的被 称为动态数据 因为通常数据流的规模十分庞大 增长速度较快并且源源不断 同时对其后续数据流的数据规律也无法预测 对于静态数据的数据挖掘过程是 武汉理工大学硕士学位论文 先将待挖掘的数据存储在数据库或以其他 文本等 形式存放在存储器里 然后 通过利用各种分析和挖掘技术来挖掘其中有价值的信息 而数据流则具有这些特 性 1 数据以时间维度到达 2 数据到达的顺序是相对独立的 不受其他因素 的干扰 3 数据规模比静态数据规模要庞大 对于后续的数据规律无法预知 4 数据无法进行二次处理 即任何数据都是通过一次挖掘就丢弃的 无法对处理过 的数据进行再次的分析 所以 一般情况下 对于数据流的收集过程和挖掘过程 是同时进行的 这就要求我们在数据流传输的有限时间内 对于流动规模及规律 无法预知的数据进行挖掘 来获得用户所感兴趣的信息 但是由于数据流的时间 空间有限性 使得我们的数据流挖掘程序的运行必须有较高的处理速度和较低的 空间使用率 因此 与静态数据挖掘的准确率相比 数据流挖掘无法在精度上做 过多的要求 数据流在数据挖掘 1 中是一个新的研究领域 国外的一些相应研究机构已经 对其做了比较深层次的探讨 并取得了一些阶段性的成果 比如r a j e 尼vm o t w a n i 和c n u m c e ts i n g hm a n k u 利用l o s s yc o u n t i n g 算法和s t i c k ys a m p l i n g 算法来进行 数据流中频繁项集的挖掘 r i c h a r dm k a r l 与s c o t ts h c n k c r 提出了一种通过两 遍扫描来实现挖掘频繁项集的算法 国内的一些科研院所对随后也对该领域投入 了许多研究精力 也取得了大量高质量的研究成果 中国人民大学信息学院和 n c r 共同创建的数据仓库与商务智能实验室在o l a f 数据仓库和商务智能方 面做了高质量的研究 其余国外的研究也有紧密联系 复旦大学在数据流挖掘方 面进行了深入的研究 其数据挖掘讨论组对数据流挖掘的讨论 对该技术在国内 领域的研究起到了积极的促进作用 另外 清华大学 中科院 北京大学等国内 一流大学对数据流挖掘都做了很多出色的研究工作 1 3 论文的结构 第一章 绪论 主要介绍了数据流挖掘发展的当前现状 第二章 主要介绍数据流的相关概念和频繁模式挖掘算法 第三章 主要介绍本论文所实现的数据流频繁模式挖掘系统的详细设计方 案 并且分析主要实现技术 第四章 主要介绍该系统的整个实现过程 结构和类定义 建模算法 挖掘 算法的流程和系统的详细设计 第五章 系统实验结果展示 运用标准评价方法对本论文所设计的系统实验 结果进行分析 第六章 系统总结和后期展望 2 武汉理工大学硕士学位论文 i 一 1 4 本章小结 本章主要介绍数据流挖掘的研究背景和研究意义 介绍数据流挖掘的当前发 展现状和本身所具有的特点 在本章的最后 简要介绍了论文的主要章节以及研 究内容 本章从总体上明确了研究的具体目标和任务 3 武汉理工大学硕士学位论文 第2 章数据流挖掘基本算法研究 2 1 数据流的概念 数据流 d a t as t r e a m 3 6 是一种连续的 数据规模近似无限的 以时间维 度有序的且高速到来的数据元素组成的无限序列 如令时间t 表示任意的时间戳 s i 表示在t 时刻到达的数据项 那么数据流可表示为无限集合 s s i s 冲l l 在现实生活中 数据流存在于网络环境中的各个结点中 数据流具有有序 连续 实时的特点 数据通常有序地 连续地到来并且实 时变化 无限性 数据量大 甚至无限 所以存储所有数据的代价是非常大的 一般无特殊需要 不会存储数据流 不可逆性 由于当前物理设备的限制 不具 备保存所有数据流的能力 往往只能对数据流进行单遍扫描 概要性 通常通过 构建概要数据结构来处理数据流 近似性 对于数据流进行查询及挖掘处理得到 的结果是近似的 数据流与传统数据比较有以下明显的区别 传统数据因在静态存储器上存储 对其的访问可以是随机的 多次访问 而 由于数据流是按时间顺序流入的 如果不做特殊存储 对其访问 只有一次 传统数据因其数据量的有限性 往往可以通过多次处理得到精确的挖掘结 果 数据流由于其规模的无限性 无法在理想环境下进行挖掘 所以数据流挖掘 多数只能得到近似结果 由于数据流的时序性和无限性 数据流往往要进行高频率的更新挖掘结果 所以 相较于传统数据 数据流挖掘的更新频率要高很多 2 2 模型构建算法 数据流处理的过程与传统数据的处理过程相比有明显的区别 在传统处理模型中 由于所有事务集均存在物理介质上 所以用户所进行的 查询可以直接作用在全部事务集上 而数据流由于其实时性 无限性和高速的特 性 无法将全部的事务集 因此需要通过合适的数据流处理算法提取出概要数据 结构 s y n o p s i sd a t as t r u c t u r e 然后对其进行相应的挖掘 因为用户对于数据流 的操作都只作用于概要数据结构上 所以对数据流的数据挖掘处理和响应的速度 要快于传统的数据处理模型 4 武汉理工大学硕士学位论文 图2 1 为数据流处理模型 该模型主要由以下几部分组成 图2 1 数据流处理模型 预处理模块将首先处理刚刚到达的数据流事务集 再将处理过的事务集放入 临时缓冲区中 数据流挖掘引擎主要负责响应用户提出的查询需求和处理相应数据的挖掘 问题 通过在内存中维护一些数据结构可以帮助数据挖掘提高处理的速度 而这 些数据结构又由数据集压缩结构 用于处理过程的数据结构和结果集压缩结构三 部分组成 数据集压缩结构主要是指通过前期处理以紧缩的方式存放原始的数据 流事务集之间有价值的信息 当新数据到达时 通过挖掘引擎将当前事务集中有 价值的信息压缩到该结数据结构中 挖掘过程中的数据结构是指在挖掘过程中 帮助实现挖掘的一些数据结构 例如f p t r e e 结构 c a n t r e e 结构等 结果集压 缩结构用于以压缩的形式存储数据挖掘的结果 当用户查询请求到达以后 可以 直接从该数据结构中提取结构 并且无需动态维护结果集 维护结果集的益处是 能加速查询速度 提高响应用户请求时间 不足之处是会占用算法的时间和空间 资源 一般情况下 前两种结构是经常在数据流挖掘中存在的 后一种 因其效 率问题 很多算法都采取谨慎态度 数据流挖掘引擎在处理缓冲区数据时 存在两种不同的处理方法 第一种是 当事务集到达以后 挖掘引擎不但将其存入数据集压缩结构还对其进行数据挖 掘 并将结果存入结果集或相应结构体中 这种方式的好处是可以动态的了解结 果的变化 对于用户提出的请求响应时间较短 缺点是当数据密度较大时或结果 变化较频繁时效率会降低 第二种方法是当事务集到达时 只将其存入数据压缩 结构中 只有当用户提出请求时才对其进行数据挖掘或者周期性的挖掘数据 这 5 武汉理工大学硕士学位论文 种方法的好处是可以允许原始数据有较高的密度 缺点是响应时间较长 在数据流挖掘研究领域有多种模型 各个模型都有其使用范围 不同的范围 需要不同的处理算法来挖掘 比如有输入流 s l s 2 是按时间顺序到达 它们共同描述了一个事务 集s 按照s i 描述事务的方式不同 可将数据流模型分为以下几类 时间序列模型 t i m es e r i e sm o d e l 每个s i 等于s i 并且以i 的增序出现 是个对按时间序列出现的数据比较适合的模型 同时根据其时序范围的不同 数 据流模型主要可以分为 界标模型 l a n d m a r km o d e l 衰减模型 d a m p e dm o d e l 以及滑动窗口模型 s l i d i n gw i n d o wm o d e l 界标模型主要处理的是从过去的某个特定时间点 到当前时间点为止的数据 流 这种模型窗口的两端是固定的 其内容是数据流的子集 如若初始时间为i 当前时间戳为n 贝t j 处理的范围是 a i a n 的项集 虽然对于这种模型的研 究已经有很多成果 但是这种模型不适用于在数据流中动态关注近期数据的应用 情况 衰减模型的每个事务都有一个权重 w e i g h t 这个权重是随着时间不断变小 的 该项事务在模型中的时间越久 则其权重就越小 这种模型在数据流挖掘中 采用的比较多 比较适合在旧数据对挖掘结果存在影响 但是随着时间推移影响 力要逐渐降低的情况中 滑动窗口模型与界标模型相似 但它的改进是把窗口固定的两端变为可以滑 动的两端 在滑动窗口模型中 事务集总是最近刚到来的新数据 随着连续的事 务集的输入 旧数据总是从窗口的一端移出 而新数据从另一端移入 滑动窗口 又分为基于顺序定义的滑动窗e l s c c l u c n c c b a s c dw i n d o w 也称物理滑动窗1 3 和基于时间定义的滑动窗口 t i m e s t a m p b a s e dw i n d o w 也称逻辑滑动窗口 基 于顺序定义的滑动窗口在其窗口内保存最近到来的k 个事务 而基于时间定义的 滑动窗口则是按固定时间为单位 顺序的按批次将最先进入的一批事务集移出 然后将最近一个时间段批次的事务集移入 后者对于事务集数没有严格的控制 2 3 数据流管理系统 2 3 1 数据流管理系统模型 数据流管理系统 2 1 是为处理数据流而设计 其处理对象与传统的数据库管理 系统有比较大的区别 如表2 1 所示 6 武汉理工大学硕士学位论文 表2 1 数据库管理系统与数据流管理系统对比 比较内容数据流管理系统数据库管理系统 数据关系处理瞬时连续的数据流处理持久稳定的关系 查询方式连续的查询一次性查询 询问方式顺序存取随机存取 存储空间有限的内存空间极大的磁盘存储 数据状态关注历史状态和到达顺序只关注当前的状态 存储方式主动存储被动存储 数据率数据更新率高相对较低的更新率 响应时间非精确数据非实时性服务 精确度非精确的数据精确的数据 系统特性不可预料的变化的数据特征查询计划态生成 图2 2 为传统的关系型数据库的处理系统模型 数据一般存储到磁盘上 当 用户提交查询条件后 系统按要求进行处理 然后将符合条件的查询结构反馈给 用户 输入数据 匕 图2 2 传统关系型数据库的处理系统模型 7 武汉理工大学硕士学位论文 典型的数据流管理系统的机构如图2 3 所示 当数据流事务集到达后 进入 数据流查询处理器中 处理器会即时对到达的事务集进行处理 当用户提出一个 查询请求后 处理器会根据当前构建好的概要数据结构进行挖掘操作 输入监控 器主要用于控制输入数据流的速率 输入的事务集分为三个部分存储 临时工作 存储 该部分用于提供数据给窗口查询 数据流的概要存储部分保存窗口中数据 流的概要信息 静态存储器部分用于保存刚刚从临时工作存储部分移出的数据流 事务集 该系统只对数据流事务集进行一次查询分析过程 查询优化器与输入监 控器之间进行交互 使得系统可以实现在改变数据流速率的同时改进查询计划 对流入的事务集进行优化处理 最后 通过挖掘所得到的数据信息通过输出缓存 部分提供给用户使用 上 r l 临时工作存储输输 查询 查询处理 出 l 1 一一 入 l 概要数据存储 优化 嚣 r 八 监缓 i一一 嚣 控存 l 数据静态存储 tt 更新静态数据 用户查询 图2 3 典型的数据流管理系统机构 2 3 2 数据流管理系统与关系数据库管理系统的区别 数据流系统的处理可以使得查询结果以连续的数据流的形式展现 同时该系 统即可以处理静态数据 也可以处理动态 连续的数据流事务集 相比较而言 数据流管理系统与关系数据库管理系统之间有如下区别 在处理对象方面 传统的关系型数据库是以既定的 静态数据集合作为处理 对象 它们往往有有限的大小 可以控制的操作方法 查询生成的是持久的 详 细的数据信息 数据流管理系统则要面对在线连续的 规模无限的 无规律的数 据流事务集 对于事务集在下个时段所出现的规律是无法预测的 在处理方法方面 传统的关系数据库对其处理对象的分析处理可以是多次的 或无限次的 这使得处理过程有较高的时间和空间复杂度 而数据流管理系统则 是对动态的数据流进行一次分析处理 这要求处理过程对用户提出的需求要及时 响应 8 武汉理工大学硕士学位论文 2 3 3 数据流管理系统的发展现状 目前 针对数据流管理系统的研究 国外大多数机构已经对其展开了研究工 作 现在已实现的 经典的数据流管理系统有t e l e g r a p h a u r o r a n i g a r a s t r e a m 和c o u g a r 其中s t r e a m 系统是由斯坦福大学设计并实现原型的一种数据流管 理系统 其目标是实现对通用的数据流进行分析处理的系统 包含了内存管理 数据流查询语言的定义以及近似查询等数据流查询处理的方面 由于只是一个原 型实现 所以s t r e a m 还有许多有待改进的方面 其查询计划的形成方式还有 待更深入的研究 这些问题都是该系统需要改进的方面 a u r o r a 系统是一个在建 的新型数据处理系统 是由三校 布朗大学 布兰代斯大学和麻省理工学院 联 合开发的 其功能是处理流式控制 并能支持大量的触发器 所以也被称为触发 器网络 a u r o r a 有三种查询模式 实时处理 试图和a d 查询 并且可以处理三 种应用 实时监控应用 处理按时间顺序的旧数据流事务集应用和对当前事务集 进行分析处理的应用 t d e g r a p h c q 系统用于对按时间顺序到达的数据流事务集 进行分析处理 其特点是对规模巨大的 无规律的实时数据流进行持续的分析处 理操作 n i g a r a 系统是针对互联网的查询处理引擎 该系统用于搜索 抽取和查 询x m l 数据流 康奈尔大学的c o u g a r 系统是针对传感器所产生的数据流的分 析处理 2 4 关联规则 2 4 1 关联规则相关定义 关联规则 2 0 是由a g r a w a l 等人提出的 是近几年在数据挖掘领域广泛研究的 热点问题 关联规则是通过算法发现事务集中项与项之间的联系 例如在超市交 易数据中 关联规则发现顾客购买的行为模式 比如顾客购买了商品a 对购买 其它商品会有什么影响 通过一些关联规则的应用我们可以发现如 面包 黄油 牛奶的置信度为9 0 的结果 发现这种结果后就可将其应用于购买模式的促销 行动中 也可以将关联规则应用于网络中 发现网页的相关性 从而提供网络代 理中的预读功能 关联规则发现主要处理的对象是事务型数据集 应用主要针对超市售货数 据 电信用户消费数据等 2 1 1 所谓事务主要是由事务产生时间 产生的数据项和 顾客标识号组成 由于当前嵌入式技术和手持终端的发展 连锁超市或电信行业 会产生大量的售货数据和消费数据 因此 对这些数据的关联规则的发现会对这 些行业的活动决策提供重要帮助 9 武汉理工大学硕士学位论文 定义2 1 关联规则概念 2 2 1 设有项目子集i fi l 1 2 i m 事务数据 库d t l i 2 t n 其中t i o i n 是组成事务数据库的单个事务 其 包含事务编号 t i d 和i 的子集 设a b 是i 的子集 也被称为项集或模式 若a c i b c i 并且a n b 矽 则存在关联规则为 怜b 的蕴含关系 定义2 2 置信度概念 若事务数据库d 中包含a 且同时包含b 的比例是c 那么就认为j 惨b 的置信度为c 表示为条件概率p b i a 即有如下公式 c o n f i d 饥c c a b s u p p o r t aub s u p p o r t a p b i a 支持度 s u p p o r t 和置信度 c o n f i d e n c e 两个阈值是与关联规则相关的两 个重要参数 支持度用于反映该项集在数据事务集中的重要性 置信度用于衡量 关联规则的可信程度 由于在事务数据库中存在着大量项与项之间的关联规 则 但用户只会对满足某一特定支持度或大于某一置信度的关联规则感兴趣 为 了发现这种关联规则 一般需要给定两个阈值 最小支持度 m i n s u p 和最小可 信度 m i n e o n f 最小支持度指定用户所感兴趣的关联规则中的个项必须满足的 最小支持度f 2 4 最小可信度指用户所需的关联规则必须满足的最小可信度 定义2 3 频繁k 项集 指频繁项集长度为k 的频繁项集 即包含k 个项 定义2 4 最大频繁项集 指如果频繁项集的所有超集 即以当前频繁项集为 子集的频繁项集 都是非频繁项集 那么称当前频繁项集为最大频繁项集 所有 该频繁项集的集合称为最大频繁模式集 m a x i m a lf r e q u e n ts e t s 或m f s 性质2 5 对于给定的频繁项集 其子集也一定是频繁项集 性质2 6 同理 对于给定的非频繁项集 其超集也一定是非频繁项集 性质2 7 长度为k 的项集如果是非频繁项集 则其长度为 k 1 的子集有 可能是频繁项集 2 4 2 数据挖掘中关联规则分类 对关联规则的分类主要有以下几种方式 1 基于规则中的数据维度分类 按数据维度可以将关联规则分为单维度关联规则或多维度关联规则 2 5 1 如果 关联规则中的每个项只涉及数据的单一维度 则称它是单维度关联规则 例如 啤酒 尿布 这是条单维度关联规则 如果关联规则中涉及数据的多个 大 于一个 维度的属性 则称为多维度关联规则 其主要处理多个维度之间的关系 例如 性别 女 职业 秘书 一 这条规则就涉及到两个属性 2 基于规则中处理数据的类型分类 关联规则f 4 2 l 中处理的数据类型主要有两类 布尔型和数值型数据 布尔型数 据指的是范围布尔值的关系 例如 性别 女 冷 职业 秘书 修 涉及的两 i o 武汉理工大学硕士学位论文 个变量都是以布尔值作为返回 数值型关联规则指的是处理数据的类型为数值型 的数据 例如 职业 秘书 收入 4 5 0 0 该关联关系涉及的收入属性 就是数值型的数据 数值型关联规则可以将其处理的对象按量化分为多个区间 3 基于数据的抽象层次分类 可分为多层关联规则和单层关联规则 如果关联规则中的项或属性涉及多个 层次 则称其为多层关联规则 例如 手机 u s b 接口 是一个多层关联 有如 诺基亚手机 u s b 接口 却是一个细节数据上的单层关联 这种关联 规则就被称为单层关联规则 2 4 3 关联规则算法 1 a p r i o r i 算法 a g r a w a l 等人提出了a p r i o r i 算法 该算法的核心依据是 频繁项集中的所 有空子集一定也是频繁项集 由非频繁项集形成的所有超集也一定是非频繁项 集 a p r i 砸算法使用逐层搜索的迭代方法来挖掘 通过项集长度不断增长的方 式来发现频繁项集 l o l 例如首先产生频繁l 项集l l 然后在此基础上产生频繁2 项集k 依次进行下去 直到产生的频繁项集不能再扩展时停止 在使用频繁 k 1 项集来生成频繁k 项集的过程中 需要先由频繁 k 1 项集生成候选k 项集c k 在这个过程中首先要通过频繁 k 1 项集内部两两合并 所有生成的 长度为k 的项集都加入c k 中 然后通过性质2 1 来判断c l 中的各项是否为频繁 项集 判断的方法是 逐个取出c k 中的候选项 判断其所有子集是否在频繁 k 1 项集中 若都存在并且该候选集支持度大于用户定义的最小支持度阈值 则改项 集为频繁k 项集 依次再判断c k 中的下一个候选项集 a p r i o r i 算法发掘频繁模 式的步骤总结来说就有两步 第一步 合并 即通过频繁k 项集内部的两两合并 生成候选集合c k 第二步 剪枝 将子集不存在于频繁 k 1 项集中的候选k 项 集剪除 或候选k 项集支持度小于用户定义最小支持度阈值的项剪除 有如下a p r i o r i 算法示例 该例基于图书馆借书信息产生的事务集 见表2 2 表2 2 图书馆借书信息事务集 t i d事务 t 1 1 1 1 3 他 i l 1 3 1 4 t 3 i l 1 2 1 3 t 4 1 2 1 5 t 5 i l 1 2 1 3 1 5 假定 用户当前给定最小支持度为m i n s u p 2 武汉理工大学硕士学位论文 首先扫面事务集 计算出所有事务集中每个1 项集的支持度 在此基础上生 成候选1 项集c l 删除支持度小于r a i ns u p 的项集 生成频繁1 项集l l 如图 2 4 所示 枉描羚的每个候 选集 瑗集支持魔 拜l i 4 删除支持度奎予最 项集支持魔 1 2 3 小支持度的项集 l l 4 l 1 2 3 1 3 l 4 i 1 3 4 i 1 4 j l i i s 2 i s 2 图2 4a p r i o r i 算法示例图l 然后 由l l 产生候选2 项集c 2 然后扫描事务数据库对c 2 中的每个项集进 行计数 通过与用户提供的最小支持度阈值的比较 删除那些支持度小于阈值的 项集 生成的频繁2 项集为k 该过程如图2 5 所示 由l l 产生候选 集 c 2 顼集 i l 1 2 1 1 1 3 l l l s 1 1 2 1 3 1 1 2 l s l 扫擒d 对每个 候逢裳计数 项囊 1 1 1 2 1 i l 1 3 l l i l 1 5 1 2 1 3 1 支掺度 2 馏溉嚣匦 i 项集 小支持度的顼集卜 叫1 1 1 1 3 l1 1 2 j 3 1 支持度 z 3 2 1 1 2 1 5 li 2 图2 5a p r i o r i 算法示例图2 再由k 产生候选3 项集为c 3 然后扫描事务数据库对c 3 中的每个项集进行 技数 通过与用户提供的最小支持度阈值的比较 删除那些支持度小于阈值的项 集 生成频繁3 项集l 3 在当前情况下 通过频繁项集l 3 已经无法生成候选4 项集 所以挖掘过程结束 该过程如图2 6 所示 图2 6a p r i o r i 算法示例图3 实验表明a p r i o r i 算法在处理稀疏型事务集时表现优异 但是a p r i o r i 算法自 身还是存在 些缺点 1 算法处理效率不高 在产生频繁k 项集的过程中就需要扫描数据库k 次 这对与处理速度有较大的影响 1 2 武汉理工大学硕士学位论文 2 如果事务集中存在长模式 则会产生大量的候选集 耗费内存资源 影响执行时间 由于a p r i o r i 算法需要通过多次的重复扫描数据事务集完成对于频繁模式的 挖掘 所以其实现方式无法在对数据流挖掘的模型中使用 2 f p g r o w t h 算法 f p g r o w t h 算法是由h a aj i a w e i 等人于2 0 0 0 年提出的一种新的频繁模式挖掘 算法 其算法最大的特点是脱离了a p r i o r i 算法必须产生候选项集的方法 并用 f p t r e e 结构代替了a p r i o r i 产生候选项集的过程 l f p t r e e f r e q u e n tp a t t e r nt r e e 称为频繁模式树 使用了一种紧缩的数据结构来 存储项集中项与项之间的全部有价值的信息 f p t r e e 是由一个值为n u l l 的根结 点组成的项前缀子树和一个频繁项头表组成 其结构符合以下原则 i z j 1 项前缀子树中的每个结点主要包含三个域 i t e m n a m e s u p h u m 和 m o d el i n k 其中i t e mn r m c 用于存储结点的项标识 s u p指的是记录到达 该结点的路劲数 则指向下一个与当前结点标识 i相1umnodel i n k同的结点在子树中 的位置 如果当前结点为最后一个 则该值为 n u l l 2 项头表中每个表项主要包含两个域 i t e mn a n l o 和i i n o d el i n k 其中 i t e m 彻m e 用于存储当前项标识 h n o d el i n k 指针域指向与当前存储的项标识同 名的项在子树中的第一个位置 f p t r e e 的构建过程 首先扫描一次事务数据库 获得数据库中频繁l 项集 支持度降序序列 并将其存储在项头表中 然后第二次扫描数据库 取出其中的 事务集 将每条事务集中的个项按其在项头表中的项序排列 将该条事务集插入 子树中 插入的方法是 从根结点开始查找子树中是否存在以该条项集的前缀为 路径的子树 如果存在 则对其路径上的个结点的s u p加一 如果没有项 nuin 集前缀子树路路径存在 则在不匹配处以当前项集顺序创建一个子树 分枝 依次输入所有事务集 即可构成f p t r e e f p t r e e 挖掘过程如下 先从长度为1 的频繁模式开始挖掘 构造符合条件 的条件模式基 然后构造其条件f p t r 并递归的在条件f p t r e e 上挖掘 还是以图书馆借书信息事务集为例 进行f p g r o w t h 算法的演示 首先扫描整个事务集 按支持度降序排列频繁1 项集如图2 7 1 3 武汉理工大学硕士学位论文 顼集支持魔 l l 4 1 1 2 3 好 l 1 1 4 i 1 1 5 z 项集支持度 1 1 1 l 4 1 3 l 4 i 1 2 l 3 1 1 5 2 1 1 4 l l 图2 7f p g r o w t h 算法示例图1 将事务集中各项按支持度计数降序排列 如图2 8 t l d 事务集 f li i j 捧序蘑 t 2 i i 1 3 j 4 t 31 1 1 2 1 3 t 4 1 2 1 5 弱i l 1 2 3 3 1 5 t i d事务囊 t l1 1 d t 2 ll 1 3 1 4 t 3 1 1 i 文1 2 t 41 2 j 5 r 51 1 1 3 j 2 1 5 图2 8f p g r o w t h 算法示例图2