




已阅读5页,还剩76页未读, 继续免费阅读
(电路与系统专业论文)不完整关系数据库中关联规则挖掘问题的研究.pdf.pdf 免费下载
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
:髦 : 硕士学位论文 n a s t e r s t h e s i s 度的评估方法,并定义了它的期望支持率和期望置信度,这些定 义保证了关联规则挖掘的某些必需的性质;研究了以往的丢失值 处理方法并分析了其不足之处,最后结合前面的定义给出了不完 整关系数据库中关联规则挖掘问题的新的定义和解决方法。 关键词:知识发现数据挖掘关联规则事务数据库关系数 据库等价类丢失值 第 ii页 共7 页 硕士学位论文 ,w a s t e r s t n e sf s -. -, -一 -, -一 一=卜 -, 一一 -一 一-一-一 一一 a b s t r a c t d a t a m i n i n g i s a f i e l d o f i n c r e a s i n g i n t e r e s t c o m b i n i n g d a t a b a s e , a rt i f i c i a l i n t e l l i g e n c e a n d m a c h in e l e a r n i n g . t h e p u r p o s e o f d a t a m i n i n g i s t o f a c i l i t a t e u n d e r s t a n d i n g l a r g e a m o u n t s o f d a t a b y i n t e l l i g e n t l y a n d a u t o m a t i c a l l y d i s c o v e r i n g u s e f u l i n f o r m a t i o n a n d k n o w l e d g e . d i s c o v e ry o f a s s o c i a t i o n r u l e s i s a n i n t e r e s t i n g s u b f i e l d o f d a t a m i n i n g . h i s t o r i c a l l y , t h e p r o b l e m o f a s s o c i a t i o n r u l e m i n i n g w a s f i r s t i n t r o d u c e d b y a g r a w a l e t c . i n 1 9 9 3 , t h e m o t iv a t i o n f o r it c a m e fr o m t h e d e s ir e t o a n a l y z e l a r g e a m o u n t s o f s u p e r m a r k e t b a s k e t d a t a ( e t c u s t o m e r t r a n s a c t i o n d a t a b a s e ) a n d f i n d s o m e r e g u l a r i t i e s f o r b u s i n e s s d e c i s i o n s . t h e i n f o r ma t i o n ma i n t a i n e d f o r t h e d i ff e r e n t t r a n s a c t io n s i s t h e s e t s o f it e m s b o u g h t b y e a c h c u s t o m e r . i n t h i s c a s e , i t m a y b e d e s i r a b l e t o f in d h o w t h e p u r c h a s e b e h a v i o r o f o n e it e m a ff e c t s t h e p u r c h a s e b e h a v i o r o f a n o t h e r . a s s o c i a t io n ru l e s h e l p i n f i n d s u c h r e l a t io n s h i p s a c c u r a t e l y . ma n y r e s e a r c h e r s h a v e s h o w n g r e a t in t e r e s t i n t h e p r o b l e m . t h e y h a v e m a d e d e e p l y r e s e a r c h i n t h e a r e a . me a n w h i l e , t h e p r o b l e m o f a s s o c i a t i o n r u l e m i n i n g h a s b e e n e x t e n d e d a n d a p p l i e d t o m a n y o t h e r f i e l d , s u c h a s t e l e c o m m u n i c a t i o n , f i n a n c e e t c , w h i c h a l l h a v e a c h i e v e d g o o d e ff e c t mi s s i n g v a lu e h a v e n o t b e e n c o n s i d e r e d o f i n t e r e s t s in c e t h e p r o b l e m o f a s s o c i a t i o n ru le m in i n g w a s fi r s t i n t r o d u c e d b e c a u s e a s s o c i a t io n ru l e s h a v e b e e n f ir s t d e v e l o p e d t o e x p l o r e t r a n s a c t io n d a t a b a s e w h e r e t h e p r o b l e m o f m i s s i n g v a l u e s d o e s n o t p r a c t i c a l l y e x i s t . h o w e v e r t h i s p r o b l e m b e c o m e s i m p o rt a n t if w e t ry t o f i n d a s s o c i a t i o n s b e t we e n v a l u e s o f d i ff e r e n t a t t r i b u t e s i n r e l a t i o n a l d a t a b a s e w h e r e m i s s i n g v a l u e s a r e o ft e n i n e v i t a b l e . i t i s n o t o b v i o u s h o w t o c o m p u t e a s s o c i a t io n ru l e s fr o m s u c h i n c o m p l e t e d a t a b a s e . i n t h i s p a p e r , s e v e r a l t y p i c a l a lg o r it h m s o f b o o l a s s o c i a t i o n ru l e m i n i n g , a i s a lg o r it h m , s e t m a lg o r it h m , a p r i o r i a l g o r i t h m a n d d i c a l g o r i t h m , a r e i n t r o d u c e d i n d e t a i l a n d c o m p a r e d ; t h e c l a s s i c a l 第 m 页 共7 页 硕士学位论文 i a s t e k s t h e s i s m e t h o d a n d k e y t e c h n i q u e s i n c l u d i n g t h e d i s c r e t i o n o f q u a n t i t a t i v e a tt r i b u t e , t h e i n t e r e s t i n g n e s s o f a s s o c i a t i o n r u l e s , a n d t h e p r o c e s s i n g o f c o u n t i n g s u p p o rt o f c a n d i d a t e s d u r i n g s c a n n i n g d a t a b a s e , a r e a l s o i n t r o d u c e d i n d e t a i l ; a n e w m e t h o d o f m i n i n g a s s o c i a t i o n r u l e i n r e l a t io n a l d a t a b a s e b a s e d o n e q u i v a l e n c e c l a s s i n r o u g h s e t t h e o ry i s p r e s e n t e d , i n w h i c h t h e p r o b l e m o f a s s o c i a t i o n r u l e m i n i n g , t h e s u p p o rt a n d c o n f i d e n c e o f t h e a s s o c i a t i o n r u l e a r e r e d e f i n e d ; b y i n v e s t i g a t i n g p r o p e rt i e s o f i n c o m p l e t e r e l a t i o n a l d a t a b a s e , t h e a s s o c i a t i o n r u l e i n d u c e d f r o m a n i n c o m p l e t e r e l a t io n a l d a t a b a s e a n d h o w t o e s t i m a t e s u p p o rt a n d c o n f i d e n c e o f i t a r e i n t r o d u c e d ; m e a n w h i l e , t h e d e f i n i t i o n s o f e x p e c t e d s u p p o rt a n d c o n f i d e n c e o f a n a s s o c i a t i o n r u l e i s p r e s e n t e d , w h i c h g u a r a n t e e s o m e r e q u i r e d p r o p e rt ie s o f a s s o c i a t i o n r u l e s m i n i n g ; s e v e r a l p r e v io u s s o l u t i o n s t o t h e p r o b l e m o f m i s s i n g a t t r i b u t e v a lu e s h a v e b e e n d i s c u s s e d , b y a n a ly z i n g t h e s h o rt c o m i n g o f t h e s e s o l u t i o n s a n d c o m b i n i n g t h e d e f i n e s a b o v e , a n e w d e f i n e a n d m e t h o d o f a s s o c i a t i o n r u l e m i n i n g in i n c o m p l e t e d a t a b a s e a r e p r e s e n t e d f i n a l l y . k e y w o r d s : k n o w l e d g e d i s c o v e r y , d a t a m i n i n g, a s s o c i a t i o n r u l e t r a n s a c t i o n e q u i v a l e n c e d a t a b a s e ,r e l a t i o n a l d a t a b a s e c l a s s , mi s s i n gv a l u e s 第 n 页 共7 页 、厥 硕士学位论文 m a s t e r s t h e s i s 第一章 绪论 当前,信息技术的发展已成为了社会进步的重要推动力, 现代计算机技术的迅速发展,使得数据的收集和处理变得更加方 便和快捷,各行业都积累了海量的数据。如何利用计算机对各行 各业保存的大规模数据进行分析,从中发现有用的信息和知识以 有效地支持决策已成为了当前信息科学领域的一个重要课题。本 文根据当前的实际需要并结合国内外在数据挖掘方面的研究进 展,在清华大学智能与系统国家重点实验室开放课题的资助下, 对数据挖掘中的关联规则挖掘问 题进行了详细的介绍,对事务数 据库和关系数据库、特别是不完整关系数据库中的关联规则挖掘 问题进行了深入地研究。 1 . 1数据挖掘的兴起 随着信息科学技术的迅速发展,一方面,由于许多信息收集 和处理技术被发明或改进, 使得数据的收集过程更有效、 更精确; 另一方面,由 于数据存储设备价格的大幅下降、新的大容量存储 介质的不断出现, 使得存储大量数据更加方便, 成本也大幅下降。 以上两方面的原因使数据的收集和存储变得更为方便和快捷。 许多企业、机构和政府部门在过去若干年里都积累了海量 的、以 不同形式存储的数据,这些数据异常庞大和繁杂,而且仍 在不断增长,如何处理这些规模巨大的数据,并从中发现有价值 的信息和知识以 达到为决策服务的目 的己 成为一个严唆的问题。 当然,一些传统的统计分析方法 ( 如计算均值、 标准方差等) 在一定程度上还是有用的,但这种简单分析的结果还不能揭示出 隐藏于大量数据中的知识,依赖人工对这些g b甚至t b ( 1 0 ) 数量级的数据进行有效的分析更是不可能。数据的极大丰富而数 据分析工具的匠乏使得研究并设计一种可以从大规模数据中自 动、高效地提取有价值的信息或知识的数据处理分析新技术迫在 眉睫,数据挖掘正是为了解决这个问 题而在八十年代末产生并在 九十年代发展起来的新兴的研究领域d 1 2 1(3 1 6 y ,得到 s u p p o r i ( x ) = 鲁: su p p o r t ( y ) = 鲁 !刀!i圳 得证。 ( i i )由x是非频繁项目 有: 口 , su p p o r t(a 一 前_ s u p p o r t ( y ) 由此可知 s u p p o r t ( y ) _ s u p p o r t ( y ) 由此可知 s u p p o r t ( x ) - m i n s u p p o r t ,即x 是频繁项目 集 得证。 定义 2 . 4 若x , y为项目集,且 x n y = 0,筑涵式 x = y称 为关联规则, x ,丫 分别称为关联规则x = y的前提和结论.项目 集 ( x u y )的支持率称为关联规则 x = y的支持率,记作: s u p p o r t ( x y ) , s u p p o r t ( x = y ) = s u p p o r t ( x u y ) ( 2 . 3 ) 第 1 1页 共7 8 页 一娜 石 页 士学位论文 m a s t e r s t i i e si s 关 联规则x = y 的五信度记作:c o n f i d e n c e ( x = y ) , c o n f i d e n c e ( x = y ) =s u p p o r t( x u y ) x 1 0 0 % s u p p o r t ( x ) ( 2 . 4 ) 通 常 用 户 根据 挖 掘需 要指定的 最小 兰 信度记为m i n c o n f i d e n c e . 支持率和置信度是描述关联规则的两个重要概念,前者用 于衡量关联规则在整个数据集中的统计重要性,后者用于衡量关 联规则的可信程度。一般来说,只有支持率和置信度均较高的关 联规则才可能是用户感兴趣的、有用的关联规则。 定 义 2 . 5如 果 s u p p o r t ( x = y ) ? m i n s u p p o r t 且 c o n f i d e n c e ( x = y ) _ m i n c o n f i d e n c e ,称关联规则 x = y为强规 则,否则称关联规则 x = y 为弱规则, 2 . 3关联规则挖掘问题的分解 关联规则挖掘的任务就是要挖掘出 d中所有的强规则。强 规则x = y对应的项目 集 ( x u y) 必定是频繁项目 集 ( 由定义2 . 5 和 ( 2 .3 ) 式 可知) ,由 定 理 2 . 1 ( i i) 和 ( 2 .4 ) 式 可知:频 繁项目 集 ( x u y )导出的关联规则 x = .y的置信度可由频繁项目 集 x和 ( x u y )的支持率计算。因此, 可以 把关联规则挖掘划分为两 个子问题: ( 1 ) 根据最小支持率找出数据集 d 中的所有频繁项目 集; ( 2 ) 根据频繁项目 集和最小置信度产生关联规则。 第一个子问题的任务是迅速高效地找出 d 中全部频繁项目 集,是关联规则挖掘的中心问题.是衡量关联规则挖掘算法的标 准,目 前大多数有关关联规则挖掘问 题的研究都是针对第一个子 问 题而展开的;第二个子问题可直接 ( 2 . 1 )式和 ( 2 .4 )式求解。 2 . 3 . 1 根据频繁项目 集产生强规则 由 ( 2 .4 )式知,强规则的产生过程如下: 对于每个频繁项目集f ,产生f 的所有非空真子集; 对 于f 的 每 个 非 空 子 集m , 如 果 丛里型应x 1 0 0 % _ m in c o n fi d e n c e , 则 输出 强规 则“ m = : s u p p o r r l m) u-m)气 : 第 1 2页 共7 8 页 、肇 硕士学位论文 n a s r e a s t h e s e s 2 . 4关联规则挖掘算法 现有的各种关联规则挖掘算法大致可分为搜索算法、层次 算法、数据集划分算法、抽样算法等。 2 . 4 . 1搜索算法 搜索算法的在读入数据集中的每条事务时,对该事务中包 含的所有项目 集进行处理,因此搜索算法需计算数据集 d 中 所 有项目 集的支持数。a i s算法a e l , s e t m 算法(2 1 1 、以及以建格算 法为主体的关联规则挖掘算法2 刀 都是这种搜索算法。 搜索算法只需对数据集一次扫描就可以找出所有的频繁项 目 集,对每一条包含 n个项目的事务就将产生 2 个项目 集,数 据集 d中包含的项目 数很大时, 所需计算和存储的候选项目 集 的 数量往往非常庞大。因此,该类算法只适合于项目 集数量相对 较小的数据集中的关联规则挖掘。 2 . 4 . 2层次算法 以a p r i o r i 算法为 代表的 层次 算法是按 含项目 数自 小而 大的 顺序寻找频繁项目 集 ( 数据集中含项目 数最大的频繁项目 集称为 最大频繁 项目 集) 。 a p r i o r i 算法在 第k 次扫描 数据集时找出 所有 的频繁 k项目集,第 k + l次扫描数据集时的候选项目 集由所有 的 频繁k项目 集通过连接运算产生 1 1 ) . a p r i o r i 算法需 扫描数据 集的 次 数 等于 最大 频繁 项目 集的 项目 数. a p r i o r it id 算 法在a p r io r i 算法的基础上对数据集进行修剪,以 减少扫描数据库的时间,但 对数据集的修剪需要额外的计算和 u o操作。 d h p算法采用哈 希技术对数据集和候选项目 集进行修剪,特别是对候选2 项目 集 的 修 剪 特 别 有效 12 1e a p r io h y b r o 算 法 是a p r io r i 算 法和a p r io r it i d 算法的融合,该算法开始采用 a p r i o r i 算法, 然后在每次扫描完 数据集之后计算修剪后的数据集的大小:若修剪后的数据集可在 内 存中 进 行处 理, 则切 换至a p r io r it i d 算 法 直到找出 出 所 有的 频 繁项 目 集。 以a p r i o r i 算法为代 表的 层次 算法可以 产生 相 对较小的 候 选 项目 集,扫描数据库的次数由最大频繁项目 集的项目 数决定。因 此, 这类算法适合于最大频繁项目 集相对较小的数据集中的关联 第 1 4页 共龙页 冬氰 硕士学 位论文 m a s t e r s t h e s i s 规则的挖掘。 2 . 4 . 3数据集划分算法 数据集划分算法包括p a rt it io n 29 算法、 d i c算法2 0 等,这些 算法将整个数据集划分成可以存放在内存中 进行处理的数据块, 以节省访问外存的v 0开销。p a rt it i o n算法只需要对整个数据集 进行两次扫描,d i c算法在数据块划分恰当时可以通过两次扫描 数据集找出所有的频繁项目集。 数据集 划分 算 法的 候选项目 集的 数量一 般比a p r i o r i 算法的 候选项 目 集的数量大,增加各数据块的数据扭曲性可以减少候选 项目 集数量。数据集划分算法是各种并行关联规则挖掘算法和分 布式关联规则挖掘算法的基础。 2 . 4 . 4抽样算法 抽样算法通过对数据集d抽样产生抽样数据集 d ,找出抽 样数据集 d 中的频繁项目集作为候选项目 集,然后扫描数据集 d确定其中的频繁项目 集3 0 如何计算负边界以找回部分遗漏的频繁项目 集是抽样算法 的关键。抽样算法适合于要求挖掘效率较高,而挖掘准确性不太 高的环境下的关联规则挖掘。 2 . 5关联规则挖掘的改进和扩展模型 关联规则挖掘的基本模型是针对事务数据库中的关联规则 挖掘问题而提出来的,其它数据集或软、硬件环境下的关联规则 挖掘必须对基本模型进行扩展,以完成挖掘任务或提高挖掘效 率。 2 . 5 . 1针对数据集的扩展 关联规则挖掘的基本模型所能处理的数据集只能是事务数 据库,缺乏对其他数据集,如包含连续属性的关系数据库、不完 整关系数据库的处理能力。许多文献介绍了从关系数据表中挖掘 关联规则的方法3 1 3 2 3 3 1 。文献 2 3 中介绍了 一种在有丢失值的关 系数据库中 挖掘关联规则的处理思路,文献 3 4 2 2 讨论了不完 整关系数据库的某些性质。在本文的后面章节中,我们将重点讨 第 巧 页 共7 8 页 冬氰 硕士学位论文 m a s t e r s t h f s s 论在关系数据库以及不完整关系数据库中挖掘关联规则的方法。 对于关系数据库,我们给出了一种基于粗糙集理论中等价类思想 进行关联规则挖掘的新方法;对于不完整关系数据库,我们在研 究不完整关系数据库性质的基础上,给出了评估不完整关系数据 库中关联规则的支持率和置信度的方法,并定义了它的期望支持 率和期望置信度;分析了以往相关研究中存在的某些问题,最后 给出了不完整关系数据库中关联规则挖掘问题的新定义和方法。 2 . 5 . 2针对应用环境的扩展 在实际的数据挖掘任务中,其应用环境是多样的,可以充 分利用己有的软、硬件条件提高关联规则挖掘的效率。 随着关系型数据库应用日 益广泛, s q l技术使得数据的访 问 和获取变得简单而迅速。关系数据库中的关联规则挖掘, 可以 利用s q l操作来实现 。一方面, s q l本身是经过合理优化的, 另一方面整个或部分挖掘任务可以 在服务器上完成3 5 j 。 利用s q l 技术实现关联规则挖掘是一种较好的解决方案,如 s e t m 算法 就是由s q l实现的2 1 1 此外,可以利用大型并行机的高速处理能力来进一步提高 关联规则的挖掘效率3 6 1 。并行关联规则挖掘算法就是针对大型并 行机而设计的并行算法。通过分布在网络上的多台微机的协同工 作来完成同一挖掘任务,是提高关联规则挖掘效率的另一种方法 3 7 1 。分布式关联规则挖掘算法针对网络环境下实现关联规则挖掘 需要解决的通讯和协同问题进行了 研究。 2 . 5 . 3关联规则挖掘方式的改进 关联规则挖掘的基本模型在数据集更新 ( 事务数的少量增 减)时,需要对整个数据集重新进行挖掘。关联规则挖掘的增量 算法对数据集数据集中的事务增加时的关联规则挖掘进行了优 化,算法只需要找出新增数据集中的频繁项目 集并对原数据集扫 描一次就可以确定更新后的整个数据集中的新的频繁项目集 1 4 1 3 8 1 ( 3 9 1 1 0 1 o n l in e关联规则挖掘是针对关联规则挖掘的基本模型的封 闭 性而作的改进。关联规则挖掘的 基本模型的封闭 性是指在寻找 频繁项目 集的过程中, 用户难以与挖掘算法交互。 因此, 很多k d d 系统都提供给用户多种交互方法4 0 1 4 1 4 2 1 , 通过交互来进行关联规 第 1 6页 共7 8 页 :最 硕士学位论文 m a s t e r s 丁 i i e s i s 则的挖掘,使用户直接指导采掘过程,以获取所需要了解的关联 规则4 3 (4 4 1 ;或在用户的指导下进行数据划分和有关参数的修改等 来搜寻属性之间的关联、数据的特征等方面的知识4 5 1 。可视化技 术可以对数据进行转换并以各种图形、图象、图标的形式加以显 示,有助于用户对数据的理解、获取数据总体特征方面的知识或 选择感兴趣的部分作进一步的分析4 6 1 为了 挖掘出 用户希望了 解的关联规则, r .n g等人提出了限 制关联规则挖掘4 7 4 8 1 。限制关联规则挖掘通过对项目 或项目 集的 限制来聚焦整个挖掘过程。项目限制可以使算法只挖掘出项目 集 i g i 中的各个项目 间存在的关联规则;项目 集限制根据项目 的附 加信息和用户的需要对候选项目 集进行修剪,针对不同类型的项 目 集限制,修剪过程可以在扫描数据库之前一次完成或在每次扫 描完数据集后进行。限制关联规则的挖掘由于项目 数或候选项目 集数量的减少而降低了寻找频繁项目 集所需的计算量,并可由此 对关联规则挖掘算法进行优化;通过规定项目 或项目 集限制降低 了算法的搜索空间,可以使关联规则挖掘算法在较短的时间内对 用户的挖掘要求作出反应,增强了关联规则挖掘算法的交互性 ( 4 9 ) 5 0 1 2 . 6关联规则挖掘技术的研究方向 国内外在关联规则挖掘方面的研究己经取得了较大的进 展,但关联规则挖掘技术在有些方面仍然存在着不足,需要进一 步的研究和更好的解决方案。 2 . 6 . 1关联规则挖掘算法效率的提高。 关联规则所面对的是大规模的数据集 ( 事务数和项目数巨 大) ,而且,数值关联规则挖掘中由于涉及到连续属性的属性值 划分和合并使得项目 数量急剧增加5 1 1 。对存在大量频繁项目 集的 数据集,采用一般的关联规则挖掘算法寻找其中所有频繁项目 集 需要的 计 算 量异常庞大, t o b e r t o j .b a y a r d 。 等人提出了 长模式 挖 掘可高效地从含较多频繁项目 集的数据集中找出最大频繁项目 集 (5 2 1 。总的来说,目 前的大多数关联规则挖掘算法在处理大数据集 时效率仍较低,因此必须对关联规则挖掘算法作进一步的 研究。 第 1 7页 共7 8 页 :肇 硕士学位论文 、 1 巧t e r s丁 h e s s 2 . 6 . 2关联规则的兴趣度 最小支持率和最小置信度并不能确保所挖掘出的关联规则 都是用户所感兴趣的,其中可能包含许多冗余、无意义的关联规 则,而且支持率和置信度较高的关联规则有可能是常识性的知识 5 3 1 。制定好的关联规则兴趣度计算标准可以使挖掘出的关联规则 更能满足用户的需要;同时还可用于优化关联规则 挖掘算法, 提 高关联规则挖掘的效率5 4 1 通过对关联规则的聚类可以对挖掘出的关联规则进行整 理,便于用户的浏览;通过制定规则模板5 5 1 、元规则5 6 5 7 1 、项目 或项目 集限制可以减小算法的搜索空间,挖掘出满足这些要求的 关联规则, 但这些方法并不能防止挖掘出冗余、无意义的关联规 则。确定数据挖掘结果的兴趣度的方法分为客观方法和主观方 法。 数值关联规则的兴趣度计算方法、基于近邻的关联规则兴趣 度计算方法对确定关联规则兴趣度的客观方法进行了 研究。一条 关联规则对用户来说是否为兴趣的,往往还与用户知识密切相 关,具有较大的主观性,有必要对确定关联规则主观兴趣度的方 法进行研究。 2 . 6 . 3关联规则挖掘算法的交互性 目 前的关联规则挖掘过程一般是在用户规定最小支持率和 最小置信度等参数之后,通过扫描数据集找出所有的频繁项目 集,并 根据频繁项目 集生成关联规则, 最后将挖掘出的关联规则 提交给用户。由于频繁项目 集的寻找比 较费时, 用户在指定最小 支持率、最小置信度等参数之后,不得不等待较长的时间才能获 得挖掘结果。如果用户不满意所得到的挖掘结果,则需要修改最 小支持率、最小置信度等参数并再次运行关联规则挖掘算法。用 户要得到满意的结果可能需要上述过程的多次反复,因此需要较 长的等待时间。虽然上述过程可以优化,但仍然难以达到理想的 结果。增强关联规则挖掘算法与用户的交互性可以 减小算法的搜 索空间,提高挖掘效率1 6 , 挖掘出满足用户需求的关联规则。 o n l i n e 关联规则挖掘技术为提高关联规则挖掘算法的 交互性而提 出的一种可行的解决方案阴。 2 . 6 . 4关联规则挖掘技术与 其他技术的融合 关联规则挖掘技术的研究吸引了许多其它领域的研究者从 第 1 8页 共7 8 页 硕士学位论文 m a s t e r s t h e s i s 事该问 题的 研究,使得关联规则挖掘可以吸收其他领域的研究成 果。 如关联规则挖掘可以 利用 s q l技术来进行数据访问、 数据 获取甚至进行关联规则的挖掘5 9 1 ;元规则指导的数据立方中的关 联规则挖掘则是数据立方技术与关联规则挖掘技术的有机融合。 关联规则挖掘技术与数据立方、数据仓库、空间 数据库系统60 等 数据库技术的 融合将推动关联规则挖掘技术进一步走向实用化。 此外,关联规则挖掘技术不仅可直接作为一种决策支持的 手段, 还可以 应用到其它数据挖掘技术中。 如关联规则挖掘技术 可用于时间序列数据分析 13 116 1 6 2 1 、 分类以 及决策树归纳4 4 1等数据 挖掘技术中。 2 . 7 / j 、 结 本章通过定义项目 集、支持率、置信度、强规则及项目 集关 系定理等内容介绍了关联规则挖掘的基本概念;对搜索算法、层 次算法、 数据集划分算法、 抽样算法等各种关联规则挖掘算法进 行了比较; 分析了 各种关联规则挖掘的改进和扩展模型;最后指 出了关联规则挖掘技术的研究方向。 第 1 9页 共7 9 页 一氰 4 i 士学位论文 v l s t e r s t h e s i s 第三章事务数据库中的关联规则 在关联规则挖掘问题提出时,关联规则挖掘所针对的数据集主要 是事务数据库。事务数据库中的关联规则挖掘问题称为布尔关联 规则挖掘,挖掘出的关联规则称为布尔关联规则。表 3 . 1 是一个 事务数据库的例子。 表 3 . 1 事务号包含在事务中的项目 a , c , d b , c , e a , b , c , e b , e 卜u八un八曰 000n 百12内j4 3 . 1布尔关联规则挖掘算法的设计 在关联规则挖掘的两个子问题中,强规则的产生比较容易、 直接, 所需的计算量相对较小; 而频繁项目 集的寻找要复杂得多, 一般所说的关联规则挖掘算法通常指的就是频繁项目 集的搜索算 法。 最直接的频繁项目 集搜索算法可以这样设计:从 i中产生 所有可能的项目 集,并为每个项目 集分配一个初值为零的计数 器,然后顺序扫描 d 中的每条事务,并把包含在当前事务中的 所有项目 集的计数器值增 1 。在扫描完数据集 d 中的全部事务 后,即可根据各个项目 集的计数器值确定所有的频繁项目 集。 上述算法仅需要对数据集 d扫描一次就可以找出其中的所 有频 繁项目 集, 但困 难在于i 中 可能的 项目 集有留 i i - 1 个, 如果 每 个项目 集和其计数 器仅需 要 l b y t e的 存储空间,当 i i = 1 0 0 0 时共需要 2 0 0 %1 0 3 0 b y t e的 存储空间, 这是目 前的 微机系统难以 承受的。因此,必须设计效率更高、更有效的算法,减少需要计 算支持率的项目 集数量。 定义 3 . 1 一种关 联规则挖掘算法为找出所有的频繁项目 集而需 要计算支持率的项目 集称为候选项目 集. 第 2 0页 共i8页 :续 硕士学位论文 m a s t e r s t h e s i s 由 候选项目 集的定义可知, 候选项目 集的数量必须大于或等 于频繁项目 集的数量,否则将遗漏部分频繁项目 集。 从时间复杂度和空间复杂度来考虑,设计布尔关联规则挖掘算法 需要解决的主要问题有两个: ( 1 )减少 】 ! o操作。关联规则挖掘的数据集有时可达 g b 甚至 t b数量级,频繁的 u o操作必将影响关联规则 的 挖掘效率,减少v 0操作主要是减少扫描数据集d 的次数; ( 2 )降低候选项目 集的数量,使其与频繁项目 集的数量接 近。 候选项目 集数量的降低可以节省为处理部分候选 项目 集所需的计算时间和存储空间。 一般来说,减少扫描数据集的次数和减少候选项目集的数 量是一对矛盾,如何处理这一对矛盾,寻找最佳的平衡点是提高 布尔关联规则挖掘算法效率的关键。 3 . 2 a i s 算法 a i s 算 法 是a g r a w a l 等 人 在1 9 9 3 年 提出 的 最早的 布尔 关 联 规则挖掘算法,该算法给出了解决布尔关联规则挖掘问题的基本 思路,是以后发展起来的其它关联规则挖掘算法的基础。 3 . 2 . 1 a i s 算法的主要过程 定义 3 . 2对项目集x , y ( x n y = q j ) ,项目 集 z ( z = x u y ) 称为 项目 集x 的 扩 展项目 集, 若y l= k , 则称项目 集z 为 项目 集x 的k 扩展项目集. 定义3 . 3 若项目 集m 和n 都是项目 集x的 扩展项目 集, 则称项目 集x 为项目集m 和n 的父集, m , n 互为同 胞项目 集. 在 a i s算法中, 候选项目 集通过对扩展项目 集的扩展产生, 每次扫描数据集时将被扩展的项目 集称为初始项目 集。 a i s算法 如算法 3 . 1 所示,其中 c为候选项目 集的集合,f s为初始项目 集的集合,f为频繁项目集的集合。 算法3 . 1 : a i s 算法 输入: d , m i n s u p p o rt , m i n c o n fi d e n c e ; 输出:所有强规则的集合: 第 2 1页 共7 8 页 爵 硕士学位论文 v a s t e r s t h e s i s 主要过程: f = o; f s = o j ; w h i l e ( f s - o ) c = 0: f o r ( 每 条事务t e d ) f o r ( 每个f e f s ) i f ( 仁 t ) c ,= e x t e n d ( f , t ) f o r ( 每个c f e c ) i f ( c f r c ) c f . c o u n t + + ; e l s e c n c o u n t = 0 f s = o; f = f u c e c t l c . c o u n t 一 可 “ m m su p p o rt ” 、.少、,.少、1、,、,了、,了 、.尹、.少、少、.尹、.尹、.尹、.产、.产、,了n.卫五气乙飞j峪舒、 1,飞4气砂67a几911111,.t ( 1 6 ) f s = g e n e r a t e es f r o n t i e r ( c ) ; ( 1 7 ) ( 1 8 ) r e t u r n ( f ) ; 在 a i s算法中, f s在第一次扫描数据集之前初始化为o; 在扫描数据集的 过程中, 每读入一条事务, 就 通过 e x t e n d ( ) 过程 对每个初始项目 集进行扩展,并由产生的扩展项目 集构成候选项 目 集;在完成对整个数据集的一次扫描之后, a i s算法根据各候 选项目 集的计数器值来计算各自的支持率、确定其中的频繁项目 集, 同时由g e n e r a t e 一 fr o n t i e r o 过 程产生下次扫描 数据集时的 初始 项目 集集合。 3 . 2 . 2候选项目 集的产生 在 a i s算法中,每次扫描数据集时的候选项目 集通过对扩 展项目 集的扩展而得到 ( 为了讨论方便,假设每个项目 集和每条 事务中的项目 都是有序的) :令 t为当前读入的事务, f 为包含 在t 中 的 初 始 项目 集 , 项目 集s = t - i l i z , . . ., 动, 则 根 据t 对 初 始项目 集进行扩展产生2 个扩展项目 集: x v s ; e ( s j( s g s ) a ( s * o ) ( 1 s i 5 2 勺 对每个项目 集 x v 袱1 5 i _ 2 0 ) 都要判断其是否包含在候选项目 集集 合c中, 若x u s ; o c ,就为之分配一个初始为1 的计数器并将其 第 2 2页 共7 8 页 硕士学位论文 b 1 a s t f r s t h f si s 加入到候选项目 集的集合中,否则将该项目 集对应的计数器值加 t o a i s 算法的 候选项目 集产生过程e x t e n d s 如下: e x t e n d ( x :项目 集, t :数据集中 的事务 ) i;- 项目 集x 中 序 号 最 大 的 项目 ; f o r ( 每 个 项目ik ( ik e t 且ik 的 序 号 大 于i;) ) i 产 生 候 选 项目 集x + k : 试 项目 集x + ik 被预测为 频繁 项目 集) e x t e n d ( x + i k , t ) : 在 a i s算法中一旦产生了 某个候选项目 集,在后续的数据 集扫描过程主送都必须计算该候选项目 集的支持数。如果能对新 产生的候选项目 集的支持率进行预测, 在对初始项目 集进行扩展 的时找出并放弃不可能成为频繁项目 集的扩展项目 集,就可以 减 少候选项目 集的数量,提高关联规则的挖掘效率。 由 定理 2 . 1 可知: 若预测 项目 集 x u s ( s = ( i l, i2 , . . . , ik ) , 1 _ k 5 p ) 为非 频 繁 项目 集, 则 项目 集x v s ( s c l lk+ 11 ik+ 2 r . . .i ip ) 且s # o j , 1 _ k tk l ) , 设x的 支 持 率 为 。 x ( 。 x 已 经在 上次 扫描数 据 集时 计算出 ) , 产生 项目 集 x v s 时 己 经 扫描了c 个包含项目 集x的 事务, 在假设 项目1 1 1 1 2 1 . . . k 在 数据集中的分布统计独立的前提下,项目 集 x v s的预测支持率 记 为s u p p o r t_pr e d ( x v s ) , s u p p o rt -pr e d ( x v s ) = t ( i ) x 1 ( i 2 ) x . . . x f ( i k ) x 一c 口x一l id i 其中t( i,) ( 1 5 j - 1 ) 次扫描数据集的过程中的初始项目 集集合f中的初始项目 集由下述三部分项目 集构成: ( 1 )上次扫描数据集时预测为非频繁项目 集而实际上是频繁项目 集的项目 集,这些项目 集的扩展项目 集中由可能存在频繁项 目 集,需要在下次扫描数据集的过程中被扩展,以考察其扩 展项 目 集; ( 2 )为释放部分内 存空间而被保存到磁盘上的、没被扩展的本次 扫描数据集时初始项目 集; ( 3 )为 释放部分内 存空间而 被删除掉所有同 胞集的 项目 集, 这样 的项目集的父集也是没被扩展的、被保存到磁盘上的项目 集。 3 . 3 s e t m 算法 s e t
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 护理慢病考试题及答案
- 考点解析-苏科版九年级物理上册《机械能和内能》专项测评试题(含答案解析)
- 护考心电图考试题及答案
- 考点解析人教版八年级上册物理声现象《声音的特性》同步训练试题(含答案及解析)
- 难点解析-人教版八年级上册物理《物态变化》难点解析试卷(含答案详解)
- 2025护士初级考试真题及答案
- 学位证模拟考试题及答案
- 汽车驾照学员考试题库及答案
- 三支一扶扶贫考试题型及答案
- 扬州数学高一月考试卷及答案
- 2025-2026学年第一学期高二语文学科10份月考试卷及答案
- 2025年武汉车谷体育场馆运营投资发展有限公司招聘3人笔试题库历年考点版附带答案详解
- 中医药政策知识培训课件
- 物业维修安全培训课件
- 2025年国企中层干部竞聘笔试题+答案
- 胎盘早剥处理课件
- 肉鸡屠宰行业安全培训课件
- 2024年北京门头沟区招聘社区工作者真题
- 城市亮化工程项目监理规划与实施方案研究
- 工厂防冻知识培训
- 2025江西新余市北诚建设投资有限公司招聘合同制工作人员2人笔试参考题库附答案解析
评论
0/150
提交评论