（计算机应用技术专业论文）频繁模式发现与多关系贝叶斯方法研究.pdf

删 广西大学学位论文原创性声明和学位论文使用授权说明 学位论文原创性声明 本人声明：所呈交的学位论文是在导师指导下完成的，研究工作所取得的成果和相 关知识产权属广西大学所有。除已注明部分外，论文中不包含其他人已经发表过的研究 成果，也不包含本人为获得其它学位而使用过的内容。对本文的研究工作提供过重要帮 助的个人和集体，均已在论文中明确说明并致谢。 论文作者签名：锨放 学位论文使用授权说明 z o f 睥占月2 1 日 本人完全了解广西大学关于收集、保存、使用学位论文的规定，即： 本人保证不以其它单位为第一署名单位发表或使用本论文的研究内容； 按照学校要求提交学位论文的印刷本和电子版本； 学校有权保存学位论文的印刷本和电子版，并提供目录检索与阅览服务； 学校可以采用影印、缩印、数字化或其它复制手段保存论文； 在不以赢利为目的的前提下，学校可以公布论文的部分或全部内容。 请选择发布时间： 五口时发布口解密后发布 ( 保密论文需注明，并在解密后遵守此规定) 一根撇：葶嘶钿嘞 频繁模式发现与多关系贝叶斯方法研究 摘要 随着数据库以及其管理系统的广泛应用，数据库中存储的海量数据急 剧增大。因此，频繁模式和多关系数据挖掘已成为数据挖掘中快速发展的 重要研究课题。现实数据通常存储于由多个关系组成的关系数据库中，传统 的频繁模式发现方法只能直接完成单一关系中的模式发现，如果要完成多 关系数据的挖掘，会产生操作复杂性和效率低下等难题。 本文在研究原有频繁模式和多关系数据挖掘的基础上，总结频繁模式 发现算法和多关系数据库存在的问题和不足，提出了解决效率问题的 d s e c l a t 的频繁模式发现算法以及在分类准确度与执行效率之间折中的 增强贝叶斯网络多关系分类( t a n - m r c ) 算法。论文主要创新点如下： 一方面，d s e c l a t 算法使用垂直数据格式挖掘频繁项集，在第一次迭 代自连接频繁项集后的每一次迭代都无须扫描整个数据库。使用深度优先 搜索最长项技术，依次优先查找某起始项的所有频繁项集。引入回写集 ( w r i t e b a c ks e t s ) 的概念，暂存新的频繁项集的子集，以减少项之间的对比次 数。该算法相i ：l e c l a t 算法减少了内存的需要，提高了运行效率。 另一方面，现有的t a n 方法通过计算互信息来发现属性节点之间的强 依赖性，放松了朴素贝叶斯网络的条件独立假设。本文改进的t a n - m r c 算 法沿用这一优点，假设表之间的属性是相互独立的，致力寻找表内属性的 强依赖性，在构建模型时以表为单位建立最大权重生成树，最后加入类结 点c 生成t a n m r c 模型。 原元组i d 传播方法仅允许类标非正即负，t a n - m r c 算法扩充了该限 制，允许存在多重分类目标。实验证明改进的算法比多关系相互贝叶斯算 法g r a p h - n b 时间开销稍大，但放松了朴素贝叶斯分类的条件独立假设，而 允许属性结点之间添加新的向量弧，有效地提高了分类的准确率，可较好 地应用到多关系数据库中。 关键词：频繁项集多关系数据挖掘贝叶斯分类元组i d 传播 n s t u d yo n f i 也q u e n t p a t t e r nd i s c o v e r ya n d n n ，t i r e l a t i o n a lb a y e s i a nm 匣t h o d s a bs t r a c t w i t ht h ew i d e s p r e a da p p l i c a t i o no fd a t a b a s ea n di t sm a n a g e m e n ts y s t e m ， t h em a s sd a t ai nd a t a b a s es h a r pi n c r e a s e d t h e r e f o r e ，f r e q u e n tp a a e md i s c o v e r y a n dm u l t i - r e l a t i o n a ld a t am i n i n g ，w h i c hd e v e l o p i n gr a p i d l y , h a v eb e c o m et h e i m p o r t a n ts t u d yi nt h ef i e l do fd a t am i n i n g t h er e a ld a t aa leo f t e ns t o r e di na m u l t i r e l a t i o n a ld a t a b a s e ，a n dt h et r a d i t i o n a lf r e q u e n tp a r e md i s c o v e r ym e t h o d c a r lb eu s e do n l ya n dd i r e c t l yi n s i n g l e r e l a t i o n a ld a t a b a s e t oe x e c u t ed a t a m i n i n g i nam u l t i r e l a t i o n a l d a t a b a s e ，i tw i l l c a u s ed i f f i c u l t i e ss u c ha s c o m p l i c a t e do p e r a t i o na n dl o we f f i c i e n c y b a s e do nt h es t u d yo ff r e q u e n tp a t t e r nd i s c o v e r ya n dm u l t i r e l a t i o n a ld a t a m i n i n g ，t h i sp a p e rs u m m a r i z e st h ep r o b l e m sa n ds h o r t c o m i n g so ft h ee x i s t i n g s t u d y , a n dp r o p o s e st h ea l g o r i t h m so fd s - e c l a tf r e q u e n tp a r e r nd i s c o v e r yt o s o l v et h ep r o b l e mo ft h ee f f i c i e n c y , a n dt h et r e e a u g m e n t e dn a i v eb a y e sn e t m u l t i r e l a t i o n a lc l a s s i f i c a t i o na l g o r i t h m ( t a n - m r c ) ，w h i c hi st h et r a d e o f f b e t w e e ni m p l e m e n t a t i o ne f f i c i e n c ya n dc l a s s i f i c a t i o na c c u r a c y t h ei n n o v a t i o n o ft h ep a p e ri sa sf o l l o w , o nt h eo n eh a n d ，a sd s e c l a t a l g o r i t h mb a s e do nv e r t i c a ld a t af o r m a tt o m i n et h ef r e q u e n ti t e m s e t s ，e a c hi t e r a t i o nt h a ta f t e rt h ef i r s tt i m ed on o tn e e d s c a n n i n gt h ew h o l ed a t a b a s e u s i n gd e p t h - f i r s ts e a r c hf o rt h el o n g e s ti t e m s e t st o i i i f i n do u ti n p r i o r i t y a n do r d e r l ya l lf r e q u e n ti t e m s e t so fa ni n i t i a li t e m w r i t e b a c ks e t sc o n c e p ti si n t r o d u c t e dt om e m o r yat e m p o r a r yn e ws u b s e to f f r e q u e n ti t e m s e t s ，w h i c hc a l lr e d u c et h ec o n t r a s t i n gn u m b e r sa m o n g t h ei t e m s c o m p a r i n ge c l a ta l g o r i t h m ，t h i sa l g o r i t h mn e e d s l e s sm e m o r ya n di m p r o v e s o p e r a t i n ge f f i c i e n c y o nt h eo t h e rh a n d ，t a nm e t h o db yc a l c u l a t i n gt h em u t u a li n f o r m a t i o nt o f i n dt h es t r o n gd e p e n d e n c eb e t w e e nt h ea t t r i b u t en o d e s ，r e l a x e d b a y e s i a n n e t w o r kc o n d i t i o n a li n d e p e n d e n c ea s s u m p t i o n t a n - m r ca l g o r i t h mf o l l o w s t h em e r i t s ，a s s u m i n gt h a tt h ep r o p e r t i e so ft a b l e sa r ei n d e p e n d e n t ，t os t r i v ef o r t h es 打o n gd e p e n d e n c eo fp r o p e r t i e so ft h et a b l e w h e nb u i l d i n gm o d e l si ti st o u s et h et a b l ea sau n i tt ob u i l dt h el a r g e s tw e i g h ts p a n n i n gt r e e ，a n df i n a l l yj o i n t h ec l a s sn o d ect og e n e r a t et a n m r cm o d e l t h eo l dt u p l ei dt r a n s m i t t i n gm e t h o d sa l l o wo n l yp o s i t i v eo rn e g a t i v e c l a s s i f i c a t i o ns t a n d a r d ，w h i l et a n m r ca l g o r i t h me x p a n d st h er e s t r i c t i o n st o a l l o wt h ee x i s t e n c eo fm u l t i p l ec l a s s i f i c a t i o ng o a l t h ee x p e r i m e n ts h o w st h a t t h en e wa l g o r i t h mn e e d ss l i g h t l ym o r et i m et h a nt h em u l t i r e l a t i o n a lb a y e s i a n a l g o r i t h mf o rg r a p h - n be a c ht i m e ，b u ti tr e l a x e st h es u p p o s e dd e p e n d e n t c o n d i t i o no fb a y e s i a nc l a s s i f i c a t i o n ，a l l o w sn e wv e c t o ra r ct ob ea d d e db e t w e e n a t t r i b u t en o d e s ，s ot h a tt h ec l a s s i f i c a t i o na c c u r a c yi s i m p r o v e de f f e c t i v e l y , t h e m e t h o dc a nb eu s e di nat h em u l t i r e l a t i o n a ld a t a b a s e k e y w o r d s ：f r e q u e n ti t e m s e t s ；m u l t i r e l a t i o n a ld a t am i n i n g ；b a y e s i a n c l a s s i f i c a t i o n ；t u p l ei dp r o p a g a t i o n ； i v 目录 摘要i a b s t r a c t 第一章绪论1 1 1 研究的背景及意义1 1 1 1 研究的背景。1 1 1 2 研究的意义1 1 2 论文主要内容与组织结构2 1 2 1 研究的主要内容2 1 2 2 论文的创新点3 1 2 3 论文的组织结构3 1 3 本章小结3 第二章数据挖掘相关知识4 2 1 数据挖掘的概念4 2 2 数据挖掘的过程5 2 3 频繁模式发现的研究现状6 2 4 多关系数据挖掘。7 2 4 1 定义及历史渊源7 2 4 2 研究现状。8 2 4 3 存在的问题与不足1 0 第三章频繁项集d s e c l a t 算法的研究13 3 1 频繁项集挖掘13 3 2 算法推导1 4 3 2 1e c l a t 算法j 1 4 3 2 2d s e c l a t 算法实例分析15 3 3d s e c u 盯算法描述一l7 3 4 实验与小结1 9 3 4 1 实验1 9 3 4 2 小结2 l 第四章多关系贝叶斯分类t a n m r c 算法的研究2 2 4 1 常见的贝叶斯网络分类器2 3 4 2 元组传播2 4 v 4 2 1 语义关系图2 5 4 2 2 元组i d 传播方法2 5 4 2 3 元组i d 传播统计方法2 6 4 31 ：a n m r c 算法。2 7 4 3 1t a n m r c 算法2 8 4 3 2t a n m r c 实例分析2 9 4 7 实验与小结3 2 第五章结论与展望3 4 5 1 结论3 4 5 2 展望3 4 参考文献3 6 致谢4 0 攻读硕士学位期间发表的学术论文目录4 l 攻读硕士学位期间参与的科研项目一4 2 v i 广西大等钮页士掌位论文频繁模式发凌与多关系贝叶扣匕亨法研究 1 1 研究的背景及意义 第一章绪论 1 1 1 研究的背景 随着信息时代的到来，计算机硬件及其存储技术飞速发展，各种软件技术能力增强， 特别是数据库、机器学习、统计学等学科的完善，从海量数据中提取有用的知识变得越 来越困难，社会需求与知识提取能力形成严重矛盾冲突，一种新的信息提取手段呼之欲 出。人们常把海量的数据比作矿藏，而将数据中获取知识的过程形象地称之为数据挖掘 ( d a t am i n i n g ) ，因此该技术应运而生，成为时代发展的产物。 如今，数据库的规模已经发展到t b 级的规模，要从如此大规模的数据中寻找有用的 知识无异于大海捞针，那么我们将如何解决这一问题呢? 答案就是数据挖掘，它能为商 业和科研创造更多的价值，同时也节约了大量成本，回报相当可观。世界上很多走在前 沿的组织已经使用数据挖掘来寻找并吸引具有高价值的客户，重新调整市场策略增加收 入，减少由于错误决策带来的不必要损失。对大型的、复杂的、信息丰富的数据集的理 解实际上是所有的商业、科学、工程领域的共同需要，在商务领域，公司和顾客的数据 逐渐被认为是一种战略资产。在当今的竞争世界中，吸取隐藏在这些数据后面的有用知 识并利用这些知识的能力变得愈加重要。 本文来源于广西自然科学基金项目( p 2 p 环境下基于o g s a 的分布式流数据查询处 理的研究，该项目与上文提到的数据挖掘问题一样，最大的特点是数据量巨大，数据 处理困难，所以必须找到合适的算法解决频繁项集挖掘的效率问题，以及多关系分类的 效率与分类准确度的问题。 1 1 2 研究的意义 数据挖掘的发展依赖于三条线索： 第一，数据保障。计算机硬件的发展，使得存储大容量的数据成为可能；网络带宽 的增加，媒体传输速度增加，使得数据汇集能力增强；数据库、数据仓库等学科的发展， 使得数据管理能力得到加强。 第二，理论保障。机器学习、统计学等众多先行学科理论完备，为数据挖掘提供理 论基础。 第三，市场需要。需求是发展的第一推动力，广阔的应用市场是数据挖掘风行的重 要推动力之一。啤酒与尿布的购物篮分析是数据挖掘最经典的应用实例之一。 g - 西大学硕士掌位美譬期e 繁模宙o k 现与多关系贝叶斯方法研究 数据挖掘应用前景广阔，已经深入到各个行业，g a r t n e r 在2 0 0 0 年的报告就预测了数 据挖掘将是影响世界未来的五大关键技术之首，当然，这个说法有待考究，不过现在正 是蓬勃发展的时期，受到众多商业领航者与研究者的追捧，以数据挖掘为核心的商业智 能( b u s i n e s si n t e l l i g e n c e ，b i ) 成为了i t 业一大新的追逐对象，一些大型企业的发展已 经离不开数据挖掘成为不争的实事。其应用初始于零售业的购物篮分析，这是销售预测 的实例。其他重要应用还包括银行的反欺诈预测，反恐预警系统，生物方面的基因序列 分析，化学方面的毒物分析，医药方面的病理分析及药剂配方，电信等行业的客户分析， 计算机网络挖掘，社会网络挖掘等等。 一方面，频繁模式发现是关联规则分析的重要组成部分，在数据挖掘领域充当不可 或缺的角色，数据量的增大，使得频繁模式发现效率的提高显得更有意义。另一方面， 现代数据库大多以关系数据库数据存储方式，常规的数据挖掘方法无法满足关系数据库 下的知识发现。由此衍生出多关系数据分类方法，着力于在不对表进行物理连接而得到 相应的分类结果，这个过程中由于数据量大，表间关系复杂，需要一种有效的方法来提 高分类的准确度与分类效率。 本文在研究原有频繁模式和多关系数据挖掘的基础上，总结频繁模式发现算法和多 关系数据库存在的问题和不足，提出了解决效率问题的d s e c l a t 的频繁模式发现算法 以及在分类准确度与执行效率之间折中的增强贝叶斯网络多关系分类删一m r c ) 算法。 1 2 论文主要内容与组织结构 1 2 1 研究的主要内容 e c l a t 是一种使用垂直数据格式的迭代算法，以a p r i o r i 算法为基础，k + 1 迭代依赖 于k 次迭代的结果。设( i k ，i k + l ，马- l ，i j ) 是迭代过程中以i k 为起始项i j 为末项的频繁项集， 根据频繁项集的子集也是频繁的j 区_ - - a p r i o r i 性质可以发现，项集( i k + l ，i j - 1 ，i i ) 及其子集 都是频繁项集，如何利用该频繁项集，减少运算过程中项之间的交集操作成了课题的重 心。d s e c l a t 算法引入了深度优先搜索最长项技术依次优先查找某起始项的所有频繁 项集，并回写集技术暂存新的频繁项集的子集。两项新的技术引入减少项之间的对比次 数，内存占用也减少，提高了运行效率。 朴素贝叶斯与t a n 方法用于常规数据分类由来已久，都具有实现简单、牢固的数学理 论基础与良好的分类性能，但朴素贝叶斯方法对属性的条件独立假设在现实数据库中很 难达到理想状态，特别是关系数据库中，会影响分类效果。因此课题引入了t a n 分类器。 元组i d 传播技术为t a n 分类器应用于多关系数据库中提供可能。t a n 模型旨在寻找属性 之间强的依赖关系，而多关系数据库由很多表组成，表间关系复杂，表内元组繁多，不 可能让所有属性一起生成最大权重生成树。因此t a n m r c 模型假设表间属性关系独立， 2 ：频繁模式发现与多关系贝叶斯方法研究 表内属性存在依赖关系。原元组d 传播方法仅允许类标非正即负，t a n - m r c 算法扩充 了该限制，允许存在多重分类目标。实验证明该算法比多关系相互贝叶斯算法g r a p h - n b 时问开销稍大，但分类准确度得到提高，体现了算法的初衷。 1 2 2 论文的创新点 本文的主要创新点： 1 ) 原有的e c l a t 算法迭代过程中，频繁项集的子集也是频繁项集，实际上可以利 用到下一次迭代当中。提出的d s e c l a t 算法使用深度优先最长项集与回写集解决了该 问题。 2 ) 已有的基于朴素贝叶斯多关系分类算法g r a p h - n b ，由于n b 本身条件独立假设的 限制，分类过程中势必影响分类准确度。t a n 分类器能放松该限制，但关系数据库表间 关系复杂，不可能将所有表的属性构造成t a n 分类器，因此文中提出了表间关系独立， 表内关系关联的假设，运用元组i d 传播实现了t a n m r c 算法。 1 2 3 论文的组织结构 第一章主要介绍传统数据挖掘的过程、基本方法，认真分析了研究现状，提出问题， 说明研究路线。 第二章主要介绍数据挖掘的相关知识，为以下研究做出准备。 第三章提出d s - e c l a t 算法，使用深度优先搜索最长项技术与回写集两项技术，经 过与e c l a t 算法的实验对比证明，有效地提高了挖掘频繁项集的时间效率。 第四章对多关系数据挖掘的作出基本介绍，元组i d 传播虚拟链接技术能减少表之间 连接的成本，树增强贝叶斯网络放松朴素贝叶斯网络的属性之间独立假设条件，有良好 的分类性能，综合这些优点提出t a n m r c 算法，实验证明比基于朴素贝叶斯的g r a p h - n b 提高了分类准确度。 第五章是对本文作出简要的总结，结合当今数据挖掘发展趋势提出对数据挖掘发展 方向的展望。 1 3 本章小结 本章主要工作在于阐述了研究背景、目的及意义，介绍了研究内容、创新点及组织 结构。 3 广西大学硕士学位试频繁模式发雩鼍与多关系贝叶剪匕亨法研究 第二章数据挖掘相关知识 数据库中的知识发现( k n o w l e d g ed i s c o v e r yi nd a t a b a s e s ，k d d ) 一词源于上世纪 8 0 年代末，9 0 年代初引起人们的重视，专门为k d d 设置了专题讨论会。1 9 9 5 年开始， k d d 研究人员和企业为此组织了专门的国际年会，2 0 1 0 年第1 6 届k d d 年会将在美国华 盛召开，届时将有数百与会者参加，这是本领域研究中级别最高的会议。 文献【l 】对k d d 做出了完整规范的定义：k d d 是从数据集中识别出有效的、新颖的、 潜在有用的，以及最终可理解的模式的非平凡过程。这一定义得到学术界的广泛认可。 随后，文献1 2 1 总结了k d d 过程的，这是一个反复迭代的过程，分为如下五个基本步骤： l 、数据选择( s e l e c t i o n ) - 从用户的角度出发选择我们需要的数据； 2 、数据预处理( p r e - p r o e e s s i n g ) 对数据进行加工，处理噪声数据和不一致数据， 尽量消除数据中的错误及缺失信息，并将多种数据源集成处理； 3 、数据转换( t r a n s f o r m a t i o n ) 将数据转换成统一数据挖掘工具能够识别的形式， 方便下一步的操作； 4 、数据挖掘( d a t am i n i n g ) 使用选定的方法提取用户感兴趣的知识； 5 、模式评估( i n t e r p r e t a t i o n e v a l u a t i o n ) 评估数据挖掘带来的知识，是否为用户真 正感兴趣的内容，并且与数据挖掘迭代操作，可以产生用户较为满意的结果。 按照这种观点，数据挖掘只是k d d 过程中的一个步骤，仅是其中的一个子集；也有 的观点认为k d d 与数据挖掘是同一个概念的不同说法而已。事实上，作者较为偏向后者 的说法，数据挖掘本身也有着类似的基本过程，而现实应用中很少有人愿意严格区分它 们。 2 1 数据挖掘的概念 现代科学与工程都是基于第一规则模型【3 】( f i r s t - p r i n c i p l em o d e l s ) 来描述物理、生 物和社会系统的。这些方法开始于基本的科学模型，比如牛顿的运动定律和麦克斯韦的 电磁方程，是建立在机械工程或电气工程的基础上的。该方法中，实验数据被用来验证 基础的第一规则模型并估算参数很困难，甚至有时无法直接度量。然而，很多领域基础 第一规则并不知晓，或者该在研究中的系统太复杂而不能数学地形式化。 术语数据挖掘描述的是从结构复杂的大型动态数据库中提取隐含可用的、非平凡的 和有用的知识。隐含知识要满足如下条件：l 、是用户眼中有趣的，2 、实际上存在的。 4 广西大胄瞻页士掌位论文频繁模式发习e 与多关系贝叶冀门亨法研究 模式能描述数据集之间的关系，单一数据纪录或指定频率之间的关系。因此，数据挖掘 的目的就是： 1 、识别模式的类型 2 、用它们获得规则 3 、找到数据集之间的群 4 、给出这些群的描述属性 5 、找到有代表性的实例 6 、应用数字变量构造函数 数据挖掘领域的各种不同的方法一般有以下特点： l 、用户将以容易理解形式获得需要的信息( 如文字或图表) 。另外，一个程序将进 一步处理这些信息。 2 、给出方法评估己提取知识的可靠性和确定性 3 、生成的信息并非用户或系统已经有的冗余知识 4 、基础算法的运行时间必须可接受。依赖数据集搜索的数目，该响应时间不能超 过低级多项式。 数据挖掘的重要性自上世纪9 0 年代以来稳固增加。然而，随着数据库数量和规模持 续增加，用户发现分析这些巨大的数据量是个非常艰巨的任务。因为这些数据常包含混 合数据集( 比如意义相同属性名不同) ，某种程序上，甚至统计方法也无能为力。 数据挖掘发展到独立的研究领域，使用智能数据分析方法搜寻埋藏在原始数据中的 宝藏。而用户则期望从这种数据预备和分析方法中获得竞争优势。 2 2 数据挖掘的过程 数据挖掘就是对收集数据集并进行相应的分析处理，然后建立对应的模型获取知 识，最后对获取的知识进行分析评估，不断的校正模型的一个关联迭代的过程，这些过 程并不是孤立的。用专业术语可总结为三个主要阶段：数据准备、数据挖掘、结果的解 释与评估。 数据准备：包括使用工具挖掘前的很多工序，是一个非常复杂的过程，它大致包括 数据清洗、数据集成、数据选择、数据预处理、数据变换等过程，针对任务的不同，这 些过程并非一成不变。 数据挖掘：是本文研究的核心内容 结果解释与评估：对挖掘结果转变成非领域专家能看懂的内容，对挖掘方法进行评 定。 5 广西大掌硕士胄q 立议薯频繁模式发褒与r 多关系贝叶冀门亨爿阿f 究 2 3 频繁模式发现的研究现状 频繁模式发现任务范围较广，常见的有频繁项集挖掘、频繁子序列挖掘、频繁子结 构挖掘等三个大类。其应用范围也相当广，如关联规则挖掘、相关性分析、序列挖掘、 分类分析等。频繁模式挖掘这一概念由a g r a w a l 在文献 8 】首先提出，通过分析项集之间 的关系，证明频繁模式发现( 包括频繁项集、频繁序列等) 是关联规则分析中的核心总 是，因此该领域向来受到专家们的重视，所得的挖掘算法数量也非常之多。 a p r i o r i 算法是公认的最为经典的频繁项集挖掘算法，该算法使用广度优先逐层搜索 迭代的方法，使得( k + 1 ) 项集的搜索可以依赖于k 项集，因此取得良好的候选项集生 成机制。f p g r o w t h ( f r e q u e n tp a t t e r n sg r o w t h ) 是另一经典算法，它采取分治策略构造一 棵频繁模式树( 或f p 树) ，该树保存了频繁项集的关联信息，通过对f p 的查找可以找到 所有的频繁项。采用位图作为数据存储方法的m a f i a 算法，运算过程中仅需扫描两次数 据库，减少了对磁盘的操作。此外还有知名的基于子集格搜索空间技术的e c l a t 算法， 有良好的性能，后面文章中将会做比较详细的分析。 频繁项集挖掘中，如果存在以下三种情形：数据库规模很大、数据稠密、支持度阈 值较低，使用普通的频繁项集挖掘算法会产生大量冗余信息，不符合现实的需要。根据 频繁项集的子集仍然是频繁的这一定理，产生了挖掘最大频繁项集与闭频繁项集两大任 务。上文提到的m a f i a 算法也可以完成这两项任务，表现出良好的性能。挖掘最大频繁 项集的算法还有：m a x m i n e r 算法采取了自底向上的广度优先搜索策略，能极早地对搜索 空间剪枝；p r i n c e r - s e a r c h 算法采取自顶向下与自底向上的双向搜索策略；以及g e n m a x 算法、f p m a x 算法和舢1 m f s 算法等等一批优秀的算法。挖掘闭频繁项集的算法还有： 采用垂直数据格式的c h a r m 算法，结合有效的剪枝与差集( d i f f s e t ) 技术，对项集与 事务集同时搜索闭频繁项集；随后在此基础上提出c h a r m - l 算法，采用了基于交集的 子集包含检测方法；以f p g r o w t h 为基础的f p t r e e 是c l o s e t 算法的核心；此外还有c l o s e t + 算法、a f o p t 算法、o p 算法、d h p 算法等较有影响力的算法。 频繁序列挖掘、加权频繁序列挖掘、频繁片断序列挖掘构成频繁模式子序列发现的 第二大阵容。该类型的任务必须考虑项集出现的先后顺序而发现频繁模式。在强大的市 场推动力作用下，也涌现了一大批优秀的算法。 频繁子树挖掘、频繁子图挖掘构成频繁模式子结构发现的第三大任务，由于本文重 点研究频繁项集挖掘，在此不一一阐述。 频繁模式发现与分类任务有着千丝万缕的联系。特别提到的是文献 4 】提出了加权频 繁项集挖掘算法，有效地应用于文本分类规则当中。文献 5 】提出频繁项集分类器( r i s c ， f r e q u e n ti t e ms e t sc l a s s i f i e r ) 使用频繁项集作为贝叶斯分类方法的概率统计依据，放松了 朴素贝叶斯分类器属性独立性约束，提高了泛化能力。由此说明频繁项集与贝叶斯分类 6 频繁模式发觏与多关系贝叶斯方法研究 方法的结合是有现实意义的。 常规数据挖掘任务基本为多关系数据挖掘所覆盖，如：频繁模式发现、分类、聚类 等。由于现代数据库以多关系数据库为主，多关系数据挖掘挖掘的研究近年来一直比较 活跃。 2 4 多关系数据挖掘 2 4 1 定义及历史渊源 定义：对于m r d m ，尚无统一定义，一派学者认为m r d m 的任务是从多个表中提 取归纳成一个表；而另一派的学者认为，其挖掘过程就是在多个表中寻找关系，而不用 转化为单表【埽】。 多关系数据挖掘( m u l t i r e l a t i o n a ld a t am i n i n g ，m r d m ) ，顾名思义，是对关系数 据进行数据挖掘，有别于传统数据挖掘，它是从多表中发现有趣的知识，其数据库是由 表的集合构成( 关系数据库) 。每个表中的纪录表示一个整体，个别的记录可通过表之 间的外键关系的连接而被重新构造【1 9 1 。 在多关系数据中寻找模式时，包含多个关系是很自然的，其模式相对于定义在单表 中的模式具有更强的表达力。多关系模式的主要类型扩展了用于单表数据挖掘的命题模 式( p r o p o s i t i o n a lp a t t e r n s ) ，比如：多关系分类规则，多关系回归树及多关系关联规则 等等。 历史：数据挖掘就是在数据中寻找模式。大多现有的数据挖掘方法是命题化的并且 是在单表寻找模式。然而，许多现有数据库将信息存储在多表中，大量关系数据挖掘 ( r e l a t i o n a ld a t am i n i n g ，r d m ) 方法是基于归纳逻辑程序设计( i n d u c t i v el o g i e p r o g r a m m i n g ，i l p ) 的，i l p 的理论基础源于上世纪七十年代，它的发展与成熟得益于 九十年代初机器学习与逻辑程序设计( l o g i cp r o g r a m m i n g ，l p ) 的结合与发展。随着数 据规模的增大，数据问的关系也愈加复杂，传统的基于单表的属性一值表示方式的数据 挖掘方法显现了表达力不足等弱点，i l p 由于自身特点，其应用应运而生。 最初，i l p 关注样例的自动化程序合成( a u t o m a t e dp r o g r a ms y n t h e s i s ) 。然而，近年 来i l p 的应用扩展到了整个数据挖掘领域( 分类，回归，聚类，关联分析等) 。大多普 通模式类型也扩展到它们的多关系版本，并有着主流的数据挖掘算法( 决策树归纳，基 于距离的聚类和预测等) 。 对于不同类型的结构数据的数据挖掘算法的发展也日益受到关注。例如，基于图的 数据挖掘。挖掘树结构和x m l 文档也受到重视。包含复杂的结构化对象的数据挖掘也适 应于m r d m 领域，关系数据库中的这些对象标准化时要转化为多个表。k d d 应用领域 的增强为m r d m 的发展提供了强有力的支持。 7 广西大考瞻页士掌位论文频繁模式发穰与多关系贝叶舅艺分爿阔f 究 许多现实结构数据被存储在多关系中。多关系数据挖掘目标是：直接从多表而不用 连接多表数据到一个单表而发现有趣的知识。它吸引了众多研究者的兴趣，并且在很多 应用领域得到成功应用，如超市、零售、金融、欺诈检测和自然科学。 近年来，随着网络技术的快速发展，因特网得到普及，w 曲服务在计算机工业中得 到广泛应用，一次交易要涉及到多个w 曲服务来协调共同完成，此时的事务处理更是考 虑到网络的分布性、动态性和不确定性，一般放松了对a c i d ( a t o m i c i t y 、c o n s i s t e n c y 、 i s o l a t i o n 、d u r a b i l i t y ，原子性、一致性、隔离性或独立性、持久性) 的严格要求。 2 4 2 研究现状 多关系数据挖掘( m r d m ) 的时代已经到来。许多数据挖掘算法在一个单关系或单表 上操作，现实世界的数据库以多表存储信息，解决该问题的m r d m 可追溯到几十年前的 逻辑归纳程序设计领域( i l p ) 。然而，直到最近，三个因素使该领域增长缓慢：多关系算 法的可伸缩性限制；不能有效处理噪声数据和不确定性；以及缺乏可理解的应用效果。 关于这个问题s i g k d d 国际会议中得到详细描述，而后来m r d m 研究工作都是针对这些 问题，因此，m r d m 进入一个快速发展的时期，促使它成为k d d 研究的重心。 下文依次说明可伸缩性，不确定性和实用性上，特别是对于后者，因为它们是m r d m 近期增长的主要动力。 可伸缩性近年的成果包括：常规i l p 问题的约束标志允许计算有效解；频繁集算法 扩展到多关系；从非常大的图提取模式和另外的信息的算法的数量和种类的增加。不过 仍有许多工作要做，包括扩展到关系集缩放技术成功应用到命题( 单表) 挖掘，并且改进 m r d m 和多关系数据库技术之间的基础接口。 近年最重要的进展之一是i l p 和概率推理与学习的结合( 贝叶斯网络，特别是其扩展 和特殊化) 。i l p 有着处理多关系的能力；概率方法能直接和系统地不确定性。在很大程 度上，m r d m 可被视为这种结合的产物，它的稳步发展还依赖于：概率关系模型，随机 逻辑程序，贝叶斯逻辑程序，关系马尔可夫模型，一阶贝叶斯分类器等等。今后研究的 一个挑战是让这些方法组成一个体系，阐明他们本身与自己的长处和局限性之间的关 系。 最为可喜的是许多主要的k d d 应用的增长，并且有相应的算法作出开发，这些成果 主要包括： 万维网：万维网是一个巨大的图，并考虑到网页到帐户之间的相互联系会使网络搜 索、网页分类等中得到更好的结果，谷歌网页排名算法一“h u b sa n da u t h o r i t i e s 算法成 功引导了挖掘w e b 连接结构激增出现的研究。m r d m 结合有页面文本内容“l i n k st o 关系和h t m l 结构等等，为此该研究提供技术支持。 8 广西大掌硕士掌位截艺频繁模茸。炙飘与多关系贝叶莉匕亨法研究 反恐：9 1 l 事件造成对恐怖威胁的防范意识大大增强，尤其是美国，这成为了反恐 研究的一个强大推力。数据挖掘是此项研究的一个核心部分( 有时有争议的) 。特别地， 在m r d m 语境下，被情报分析人员和法律执行机构使用的传统链接分析技术很自然地被 形式化，此方向的几个重点工程正在进行。 病毒式营销：传统的营销方式越来越多地被病毒式营销补充( 或替代) ，该方式会考 虑到网络的影响，并寻求利用消费者的口碑。特别是在互联网行业，对公司的未来越来 越依赖病毒式营销计划的成功。计划的正确规则包括客户之间，客户属性与产品特征之 间的相互作用，而这些都是m r d m 的基本任务。 社会网络：更一般地说，社会网络分析领域，其重点是社会活动者之间的关系建模， 这关系到上述所有应用，并且是m r d m 的主要模块。建立社会网络模型的可用数据的数 量增长非常快，如果m r d m 提供更多的工具，将会得到更多的成果。 计算生物学：在分子生物学的应用中，i l p 取得了许多显著的成果( 例如，预测癌 变) 。最重要的是，从个体基因和蛋白质的研究到它们在活细胞中之间如何相互作用， 生物学正在快速发展。为它们的相互作用和关系的观测结果建立相应模型，可以成为 m r d m 研究的巨大应用领域。 信息提取：网上基于文本的信息越多，越会对信息提取( i e ) 技术增加潜在的积极影 响。是一个基本的关系问题，不仅因为它的目标是把文本转换为数据库，更是因为这 样做需要成功地理解实体之间有关文本的显性和隐性关系。 普适计算：设备数量和种类上的增长，不断产生的数据是知识发现的一个潜在的数 据源。在普适计算环境下持续挖掘需要多种类型的对象和关系考虑在