（计算机软件与理论专业论文）基于fp树的关联规则挖掘算法的设计与实现.pdf

、摘要 数据挖掘技术是解决数据丰富而知识贫乏的有效途径，当属信息科学领域 的前沿研究课题之一，有关的研究和应用极大提高了决策支持的能力，它已被 公认为是数据库研究中一个极富应用前景的领域。本文描述了数据挖掘的概念、 功能以及发现模式的分类。在众多的数据挖掘算法中，挖掘关联规则是数据挖 掘领域中的重要研究内容，其中挖掘频繁项目集是挖掘关联规则中的关键问题 之一，又最大频繁项目集已经隐含了所有的频繁项目集，所以可以将发现频繁 项目集的问题转化为发现最大频繁项目集的问题，因而发现最大频繁项目集对 数据挖掘具有重大意义。 以前的许多挖掘最大频繁项目集算法是先生成候选集，再进行检验，然而 候选项目集产生的代价是很高的，尤其是存在大量长模式的时候。本文主要在 以下几个方面对基于f p 一树的关联规则挖掘问题进行研究：第一是研究了f p 一树 的定义和构造过程以及多种改进算法，并分析了基于f p - 树进行挖掘的可行性和 完整性，然后提出了基于f p - 树的快速挖掘最大频繁项目集的算法 m a x f i ( m a x i m a lf r e q u e n ti t e m s e t ) ，该算法不需要生成最大频繁候选项目集。 改进的f p 一树是单向的，每个节点只保留指向父节点的指针，这大约节省了三分 之一的树空间。试验结果表明该算法比同样基于f p - 树的d m f i a 算法挖掘最大频 繁项目集的效率更高。 第二是研究了挖掘有效且无冗余关联规则的问题。传统算法在生成关联规 则时，或者生成规则的效率很低，或者生成的关联规则之间存在着大量的冗余， 或者挖掘出的规则的支持度和可信度都很高，但却是无趣的、甚至是虚假的规 则，且不能产生带有否定项的规则。本文提出了一种新的算法m v n r ( m i n i n g v a l i da n dn o n r e d u n d a n ta s s o c i a t i o nr u l e sa l g o r i t h m ) ，在该算法中，首 先对频繁项集集合进行检查，删除了那些只能生成冗余关联规则的频繁项集， 然后对分析过的频繁项集集合中的每一个频繁项集生成他们的极小子集集合， i 利用极小子集的性质，删除那些在其超集的极小子集集合中也存在的极小子集， 最后根据用户定义的条件生成关联规则。 第三是研究探讨了基于f p _ 树的最大频繁模式挖掘算法m a x f i 和挖掘有效 且无冗余关联规则算法m v n r 在公安决策支持系统中的应用。 关键词：关联规则；最大频繁项目集；频繁模式树；相关度；冗余性 a b s t r a c t d a t am i n i n gt e c h n o l o g yi sa l le f f e c t i v ea p p r o a c ht or e s o l v et h ep r o b l e mo f a b u n d a n td a t aa n ds c a n t yi n f o r m a t i o n i tc u r r e n t l yi st h er e s e a r c hf r o n t i e rw i t h i nt h e i n f o r m a t i o ns c i e n c ef i e l d t h er e l a t e dr e s e a r c h e sa n da p p l i c a t i o n sh a v eg r e a t l y i m p r o v e dt h ea b i l i t yf o rd e c i s i o ns u p p o r t i n g i th a sb e e nd e e m e dt oaf i e l dt h a th a s b r o a dp r o s p e c to fa p p l i c a t i o ni nd a t a b a s er e s e a r c h t h i s p a p e rd e s c r i b e s t h e c o n c e p t i o n , f u n c t i o n a n d p a t t e r n s o fd a t a m i n i n g i nm a n y d a t a m i n i n g a l g o r i t h m s , m i n i n ga s s o c i a t i o nr u l ei sa ni m p o r t a n tm a t t e ri nd a t am i n i n g , i nw h i c h m i n i n gf r e q u e n ti t e m s e t si s ak e yp r o b l e mi nm i n i n ga s s o c i a t i o nr u l e b e c a u s e m a x i m u mf r e q u e n ti t e m s e t se m b r a c ea l lf r e q u e n ti t e m s e t s ，t h ep r o b l e mo fm i n i n g f r e q u e n t i t e m s e ti sc o n v e r t e dt ot h ep r o b l e mo fm i n i n gm a x i m u mf r e q u e n t i t e m s e t s m i n i n gm a x i m a ll 自e q u e n ti t e m s e t si sv e r yi m p o r t a n ti nd a t am i n i n g m a n yo ft h ep r e v i o u sa l g o r i t h m sm i n em a x i m a lf r e q u e n ti t e m s e t sb yp r o d u c i n g c a n d i d a t ei t e m s e t sf i r s t l y , t h e np r u n i n g b u tt h ec o s to f p r o d u c i n gc a n d i d a t ei t e m s e t si s v e r yh i 乒，e s p e c i a l l yw h e nt h e r ee x i s tl o n gp a t t e r n s t h i sp a p e rs t u d i e sm o s t l yt h e p r o b l e mo fm i n i n gm a i x i m a lf r e q u e n tp a t t e r nb a s e do nf p - t r e e f i r s t l y ，w es t u d yt h e d e f i n i t i o na n dc o n s t r u c t i o no ff p t r e ea n di m p r o v e da l g o r i t h m sa n da n a l y z et h e f e a s i b i h t ya n dc o m p l e t e n e s so ff p - t r e e t h e n , w ep r o p o s et h ea l g o r i t h mf o rm i n i n g m a x i m a lf r e q u e n t p a t t e r nm a x - f i , w h i c hn e e d n o t p r o d u c em a x i m a lc a n d i d a t e i t e m s e t s t h ei m p r o v e df p t r e ei sao n e - w a yt r e ea n dt h e r ei sn op o i n t e r st op o i n ti t s c h i l d r e ni ne a c hn o d e ，s oa tl e a s to n et h i r do fm e m o r yi ss a v e d a t l a s t , o u r e x p e r i m e n t a lr e s u l ts h o w st h a tt h ea l g o r i t h mm a x - f ii sm o r ee f f e c t i v e l yt h a nt h e a l g o r i t h md m f i a b a s e do nf p - t r e ef o rm i n i n gm a x i m a lf r e q u e n tp a t t e r n s s e c o n d l y , w es t u d yt h ep r o b l e mo f m i n i n gv a l i da n dn o n r e d u n d a n ta s s o c i a t i o n r u l e s t h et r a d i t i o n a l a l g o r i t h mm i n i n ga s s o c i a t i o nr u l e s ，o rs l o w l yp r o d u c e s a s s o c i a t i o nr u l e s ，o rp r o d u c e st o om a n yr e d u n d a n tr u l e s ，o ri ti sp r o b a b l et of i n da n a s s o c i a t i o nr u l e , w h i c hp o s s e sh i 曲s u p p o r ta n dc o n f i d e n c e , b u ti su n i n t e r e s t i n g ，a n d e v e ni sf a l s e f u r t h e r m o r e ，ar u l ew i t hn e g a t i v e - i t e mc a n tb ep r o d u c e d t h i sp a p e r p r o p o s ean wa l g o r i t h mm v n r ( m i n i n gv a l i da n dn o r l - r e d u n d a n ta s s o c i a t i o n r u l e sa l g o r i t h m ) ，i nt h i sa l g o r i t h m ，f i r s t l y , w ee x a m i n ef r e q u e n tp a t t e r n s ，d e l e t et h e v 山东大学硕士学位论文 f r e q u e n tp a t t e r n sw h i c ho n l yp r o d u c et h er e d u n d a n ta s s o c i a t i o nr u l e s t h e n , w e p r o d u c et h em i n i m a ls u b s e to fe a c hf r e q u e n ti t e m s e t i nt h ee x a m i n e df r e q u e n t i t e m s e t ，d e l e t et h em i n i m a ls u b s e to fe x i s t i n gi nt h em i n i m a ls u b s e tw h i c hi ss u p e r s u b s e to ft h i sm i n i m a ls u b s e tb yu s i n gt h ec h a r a c t e ro fm i n i m a ls u b s e t a tl a s t ，w e p r o d u c ea s s o c i a t i o nr u l e sa c c o r d i n g t ot h ec o n d i t i o n sw h i c hn s e rd e f i n e a tl a s t ，w es t u d yt h ep r o b l e mo ft h ea p p l i c a t i o no fm i n i n gm a x i m a lf r e q u e n t p a r e r n sa l g o r i t h m ( m a x f na n dm i n i n gv a l i da n dn o n - r e d u n d a n ta s s o c i a t i o nr u l e s a l g o r i t h m c m v n r ) i nt h ed e c i s i o ns u p p o s i n gs y s t e mo f g o n g a n k e y w o r d s ：a s s o c i a t i o nr u l e ；m a x i m u mf r e q u e n ti t e m s e t ；f r e q u e n tp a t t e r nt r e e ； c o r r e l a t i o n ；r e d u n d a n c y v i 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的擐导下，独 立进行研究所取得的成果。除文中已经注明引用的内容外，本论文不 包含任何其 也个人或集体已经发表或撰写过的科研成果。对本文的 舞 究做出重要贡献的个人和集体，均已在文中以明确方式标明。本声明 的法律责任由本人承担。 论文作者签名：豳亚药 日期： 2 州篁，；f 0 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学校保留或向 国家有关部门或机构送交论文豹复印件和电子版，允许论文被查阅和借阅：本人 授权山东大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可 以采用影印、缩印或其他复制手段保存沦文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：幽尘塑导师签 1 绪论 1 1 课题提出的背景和意义 随着数据库技术的迅速发展以及数据库管理系统的广泛应用，人们积累的 数据越来越多。激增的数据背后隐藏着许多有价值的重要信息，人们希望对这 些数据进行更高层次的分析，以便更好地利用这些数据，达到为决策服务的目 的。目前的数据库管理系统可以高效地实现数据的录入、查询、统计等功能， 但无法发现数据中存在的关系和规则，无法根据现有的数据预测未来的发展趋 势。缺乏挖掘数据背后隐藏的知识的手段，导致了“数据丰富但知识贫乏”的 现象。 没有强有力的分析工具，理解这些海量的、类型各异的数据已经远远超出 了人的能力。数据挖掘方法的提出，让人们最终有能力认识到数据的真正价值， 即蕴藏在数据中的信息和知识。数据挖掘( d a t am i n i n g ) 指的是从大型数据库或 数据仓库中提取人们感兴趣的知识，这些知识是隐含的、事先未知的、潜在的 有用信息【l 】 数据挖掘的任务是从数据中发现模式模式是一个用语言l 来表示的表达式 e ，它可用来描述数据集f 中数据的特性，e 所描述的数据是集合f 的一个子集f e ， e 作为一个模式要求它比列举数据子集f e 中所有元素的描述方法简单。 模式有很多种，在实际应用中，往往根据模式的实际作用细分为6 种：分类 模式、回归模式、时间序列模式、聚类模式、关联模式、序列模式，其中关联 模式的挖掘是目前数据挖掘领域中最为广泛的研究课题之一。 数据项之间的关联规则称为关联模式。我们所要讨论的问题集中在数据挖 掘中的关联规则上。关联规则起初主要应用于对购物篮的分析，关联规则是发 现交易数据库中不同商品之间的联系，这些规则找出顾客购买行为模式，如购 ：= ：一：= ：堡奎茎堡圭兰堡婆兰 。 买了某一商品对购买其他商品的影响。发现这样的规则可以应用于商品货架设 计、货存安排以及根据购买模式对用户进行分类。虽然关联规则是伴随零售业 的飞速发展而产生的一种需求，但它的应用决不仅仅在零售业上，还体现在银 行业、制造业、经纪业和安全交易、保险业、计算机硬件和软件、政府和防卫、 医药、交通、电信、公安等，所以展开对关联规则的研究具有重大意义。 关联规则是描述数据库中数据项之间潜在关系的规则。在公安分析决策支 持系统中，关联规则数据挖掘可以有效地协助公安机关进行决策分析。如根据 对已有嫌疑人的资料进行分析，进行嫌疑人基本信息和犯罪情况之间的关联分 析，找出比如文化程度与作案手段之间的联系；还可对案件进行分析，找出案 别和作案地域、作案时间等之间的关联，为公安分析和决策提供依据，提高公 安破案和日常社会治安管理的效率。 1 2 国内外研究现状 1 9 9 3 年a g r a w a l r 等人首先提出了关联规则的问题【2 l ，并于1 9 9 4 年提出了 挖掘关联规则的经典算法a p r i o r i 算法【3 1 ，后来有不少学者对关联规则问题进行 了大量的研究。比如对原有a p r i o r i 算法进行优化，如引入哈希方法1 4 、划分的 思想【5 l 、随机采样【6 】等，以提高算法挖掘规则的效率，但这些算法都不能避免 a p r i o r i 系列算法固有的缺陷，就是需要多次重复扫描数据库，而且可能产生大 量的侯选项集；j i a w e ih a r t 等人提出的不产生候选项集的f p g r o w t h 算法【”，虽 然不需要生成频繁候选项目集且只需要扫描数据库两次，但如果大项集的数量 很多，并且如果由原数据库得到的f p t r e e 的分支很多且分支长度很长时，该算 法将需要构造出数量巨大的条件f p - t r e e ，不仅费时而且要占用大量的空间。挖 掘效率不高，而且递归算法本身效率也较低。因为最大频繁项目集隐含了所有 的频繁项目集，所以有很多学者提出了直接挖掘最大频繁项目集的算法，如 g u n o p u l o s 等人提出的随机算法【8 j 使用了垂直位向量的数据结构来表示事务数据 库，但它无法保证发现所有的最大频繁项目集；m a x m i n e r 算法t 9 使用水平数据 库格式和宽度优先( b r e a d t hf i r s t ) l 勺搜索策略，可能需要多次扫描数据库，并且会 2 产生许多无用的候选项目集，带来代价昂贵的i o 开销以及计算开销； p i n c e r - s e a r c h 算法1 1 0 】需要维护一个最大频繁模式的超集最大候选集，其代价通 常也是很高的；m a f i a 算法【1 1 1 是b u r d i c k 等人提出的最大频繁项目集挖掘算法， 但该算法仍需要多次重复扫描数据库；d m f i 算法1 1 2 l 也需要多次重复扫描数据 库；d m f i a 算法【”1 只需扫描数据库两次，但需要生成数量庞大的最大频繁候选 项目集。挖掘关联规则的挑战性在于数据量巨大，算法的效率是关键，因此有 必要研究出占用内存小、i o 操作少、执行速度快的高效算法。本文提出的基于 f p 一树的关联规则挖掘算法m a x - f i 可以很好的解决这一问题，使得挖掘的效率 得到很大的提高。 在生成关联规则的研究中，很多学者也提出了很多算法，如利用邻接有向 无环图的算法【1 4 l f i 习，利用最大祖先来消除冗余的关联规则，因为对每一个频繁 项集都要先建立邻接有向无环图，这样使得生成关联规则的效率降低，且所占 的内存空间也大，特别当项集长度很长时，效率是很低的，而且不能消除错误 或虚假的规则；利用频繁闭包项集的算法f 16 】7 】f l s j l l 9 l - 2 0 l ，需要根据生成的闭包项。 集来生成关联规则，这样需要重复扫描数据库，而且也不能对错误的或虚假的 规则进行排除：很多学者借助使用相关支持度【2 1 1 1 2 2 1 1 2 3 l 提出了挖掘有效的关联规 ， 则的算法，这些算法虽然能挖掘出正确的关联规则，但不能排除冗余的关联规 则。本文提出的挖掘有效且无冗余的关联规则算法m v n r ，通过利用集合的极 小子集性质，直接根据生成的频繁项集生成规则，不需再扫描数据库，既能消 除错误的或虚假的规则，又能消除冗余的规则，使得挖掘出的规则既是正确的， 又是无冗余的。 1 3 论文的组织 论文其余部分按以下方式组织： 第二章，给出关联规则的有关概念，描述了几种经典算法并分析其优缺点。 第三章，介绍了新的数据结构f p 一树的定义、构造，分析研究了f p 一树数据 结构的特点，然后提出新的基于f p 树的最大频繁模式挖掘算法m a x f i ，在 ：= ：一：! ：= 。= 皇至：呈墼圭耋堡堡圣= ：， w i n d o w s 2 0 0 0 平台上用d e l p h i 6 0 实现了m a x f i 算法和d m f i a 算法，并在不 同的数据库下对其性能进行了分析 第四章，给出有效且无冗余关联规则的相关概念和定理，描述了几种相关 算法，利用极小子集性质提出一种新的挖掘有效且无冗余关联规则的算法 m v n r ，并将该算法应用到不同数据库中求关联规则。 第五章，关联规则挖掘在公安决策支持系统中的研究与探讨。 第六章，总结全文并展望了未来可能的进一步研究方向。 4 2 关联规则描述及相关算法 自1 9 9 3 年a g r a w a l 首先提出关联规则概念【2 】以来，关联规则挖掘便迅速受 到数据挖掘领域专家的广泛关注。关联规则挖掘的对象是事务数据库。关联规 则挖掘的一个典型应用是购物篮分析( b a s k e ta n a l y s i s ) 。该过程通过发现顾客放入 其购物篮中不同商品之间的联系从而分析顾客的购买习惯。例如，“8 0 的 顾客在购买笔记本电脑的同时也会购买数码相机”。这种关联发现可以帮助零 售商制定营销策略。譬如，超市经理可以将笔记本电脑和数码相机放在一起， 以便在销售笔记本电脑的同时刺激数码相机的销售。 2 1 关联规则的概念 2 1 1 基本概念 a g r a w a l 等人首先定义了在事务数据库中挖掘关联规则的问剐2 1 。 设i = ( i 1 i 2 ，i m ) 是项( j t 锄) 的集合。设任务相关的数据d 是数据库事务的集 合，其中每个事务t 是项的集合，有t c _ i 。每一个事务有一个标识符，称作t i e ) 。 定义2 1 设x 是i 中项的集合，称作项集( i t e m s e 0 ，事务t 包含x 当且仅 当x t 。 定义2 2 包含k 个项的项集称为l 【项集。例如 牛奶，面包 是一个2 项集。 定义2 3 如果项目集x 在事务数据库d 中的支持度不小于用户给定的最小 支持度阈值，那么称x 为频繁项目集；反之称之为非频繁项目集。 定义2 4 关联规则是形如x j y 的蕴涵式，其中x c i ，y i ，并且 x n y = a 。 描述关联规则属性常用的参数： 山东大学硕士学位论文 1 ) 支持度( s u p p o r t ) 支持度s 是d 中包含a u b 的事务百分比，它是概率p ( a u az l ，即 s u p p o r t l ：a j b ) = p ( 4 u 占) ，它描述了a 和b 这两个物品集的并集在所有的事务 中出现的概率。 2 ) 可信度( c o n f i d e n c e ) 可信度c 为d 中包含a 的事务中同时也包含b 的百分比，它是概率p ( b i a ) ， 即c o n f i d e n c e ( a j g i = p ( b 1 4 ) 。 3 ) 相关支持度( c o r r e l a t i o n _ s u p p o r t ) f z 5 i f z , 目 在事务数据库d 中和d 中的关联规则x y ，该关联规则的相关支持度为： c o r r e l a t i o ns u p p o r t = s u p p o r t ( x uy ) ( , s u p p o r t ( x ) s u p p o r t ( y ) ) = c o n f i d e n c e ( x ；y ) s u p p o r t ( y ) 从某种意义上说，相关支持度更能反映关联规则中x 和y 的关系，由它可 以了解x 和y 之间的关系究竟如何密切；而可信度则反映了在这种情况下的关 系方向，即是从x 到y ，还是从y 到x ；支持度则反映了这种情况在事务中是否 是普遍的规律。 项集的出现频率是包含项集的事务数，简称为项集的频率、支持计数或计 数。在基于支持度可信度框架中，同时满足用户定义的最小支持度阀值( m i n _ s u p ) 和最小可信度阀值( m i n _ c o n o l 拘关联规则称为强关联规则。关联规则的挖掘问题 就是在事务数据库d 中找出满足用户给定的最小支持度和最小可信度的强关联 规则。频繁k 项目集的集合通常记作k 。 2 1 2 关联规则的分类 我们将关联规则按不同的标准进行分类： ( 1 ) 根据规则中处理的变量的类别，关联规则可以分为布尔型和数值型。 布尔型关联规则处理的值都是离散的、种类化的数据，它显示了这些变量 之间的关系。而数值型关联规则可以和多维关联或多层关联规则结合起来，对 6 数值型字段进行处理，将其进行动态分割，或者直接对原始的数据进行处理， 当然数值型关联规则中也可以包含种类变量。例如：下面的规则是数值型关联 规则，其中x 是代表顾客的变量。 a g e ( x ，”1 8 2 5 ”) j o b ( ) 【，”学生”) 等b u y s ( x ，”电脑”) 这条关联规则表示年龄在1 8 至2 5 岁之间，职业为学生的人会买电脑这样 一个规律。注意，属性a g e 的值经过了离散化。 ( 2 ) 基于规则中数据的抽象层次，可以分为单层关联规则和多层关联规则。 单层关联规则不考虑现实生活中的数据实际上具有多个不同的层次，不涉 及不同抽象层的项或属性。多层关联规则充分考虑现实生活中数据的多层性， 规则涉及数据不同抽象层的项或属性。例如：b u y s ( x , s o n y 打印机 ”) j b u y s ( x ，”i b m 电脑”) ，是一个细节数据上的单层关联规则；b u y s ( x , ”打印机 ”) j b u y s ( x ，”联想电脑”) ，是一个较高层次和细节层次之间的多层关联规则。 ( 3 ) 根据规则中涉及到的数据的维数，关联规则可以分为单维的和多维的 在单维的关联规则中，我们只涉及到数据的一个维，如用户购买的物品； 而在多维的关联规则中，要处理的数据将会涉及多个维。也就是说，单维关联 规则是处理单个属性中的一些关系；多维关联规则是处理多个属性之间的某些 关系。例如： b u y s ( x , 牛奶”) 奢b u y s ( x , ”面包”) 为单维关联规则，只涉及到用户购买属性； s e x ( x , ”男”) p r o f e s s i o n ( x , ”i t ”) j b u y s ( x ”电脑”) 为多维关联规则，涉及到 多个字段的信息，分别是s e x ，p r o f e s s i o n 和b u y s 三个字段。 2 2 关联规则挖掘的经典算法及分析 给定一个事务数据库d ，在基于支持度可信度框架中，挖掘关联规则的问 题就是找出所有满足用户给定的最小支持度和最小可信度的关联规则，即挖掘 出所有的强规则，该问题可分解为两个子问题【1 】： ( 1 ) 找出所有的频繁项目集，即出现频率至少和预定义的最小支持度一样 的项目集； ：一： = ：当奎奎兰堡圭兰堡篁耋：；： = ( 2 ) 由频繁项目集产生关联规则。 2 2 1 层次迭代算法 2 2 1 1a p f i o f i 算法 a p r i o r i 算法【3 1 是1 9 9 4 年a g r a w a l 等人提出的。该算法使用一种称作逐层迭 代的候选产生测试的方法，k - 项目集用于探索( k + 1 ) 一项目集。首先，找出频繁1 ， 项目集的集合，该集合记作l l ，然后由l l 得k ，由k 得l 3 ，如此下去，直到 不能找到频繁k 项目集。每找一层l k 均需要一次数据库扫描。 为了提高频繁项目集逐层产生的效率，一种称作a p r i o r i 的重要性质用于压 缩搜索空间。 性质2 1 ( a p r i o r i 性质) 频繁项目集的所有非空子集都必须是频繁的。 a p r i o d 性质应用在算法的以l k - l 找k 过程中，该过程由连接和剪枝【2 8 1 组成： 连接步：为找h ，通过l k - l 与自己连接产生候选k - 项目集的集合。该候 选项目集的集合记作c k q 可拈lo o l k 1 ，l k 1 中的两个元素是可连接的当且仅当 这两个元素的前k - 2 个元素相同。设：l k i = l l ，1 2 ，1 l i ) ，k ，b ( 1 i s 皿l 句sn ，i j ) 是其中的两个元素，l i = 1 【l 】，l 2 】，l k - 1 】 ，k 【m 】( 1 m 兰k - - 1 ) 是项集k 中的第 m 个项，若满足：( 1 【1 】咄【1 】) ( 1 【2 】- l 【2 】) “ k - 2 = l j k - 2 ) ( 1 ， k - 1 】b k 1 】) ， 则有：l i o o l j = 1 。【1 】，l i 2 ，k k - 1 】，b 【k - 1 】) ，l b c k 。 剪枝步：由a p r i o f i 性质可知，任何非频繁的( k - 1 ) - 项集不可能是频繁k - 项集的子集。设：“c k ，即c k 是一个侯选l 卜项集，c k 1 是c k 的一个体一1 ) 项子 集，若满足：c k 1 叠h , - l ，则有：c k 仨k ，即是说，侯选k - 项集c k 应该从侯选l 【- 项 集的集合c k 中删除。 通过一个例子来说明a p r i o r i 算法挖掘频繁项集的过程，给出一个事务数据 库如图2 1 ( 假设最小支持度计数为2 ) ，由a p r i o r i 算法产生频繁项集的过程如 图2 2 。 事务数据库d t i d 项集合 t 0 0 1 a , b ，d t 0 0 2 a , b ，c ，c t 0 0 3a l c t 0 0 4 a , b ，c t 0 0 5 a , c ，d t 0 0 6 a , b ，d c t 0 0 7 a , b t 0 0 8 a c ，f t 0 0 9a t 0 1 0 b 。c t 0 1 l c ，g 图2 1 事务数据库d m 项集台 1 0 0 1b d 项集计数 项集项集 项集| 十獭 t 0 0 2b c i b 1【i j h 酬 5 5 c l jc 扫描d f d 】 3 f d尊棱f jd 计数 矧 2 3 2 2 l ( ，( 酬： 】 1 【b ，e 伯d f he ： 【c jd ： 【q t ： t 0 0 3 g 瓢i c l l t l 【也t 【a l r 0 0 4b c 扫描d f b ，8 t 0 0 5, l e d 计数 f c l t t 0 0 6 b d t d l3 t 0 0 tb i 2 t 0 明 f f j l 旧i ；_ j 1 0 0 9 】l t 0 1 0b c t 0 1 lc 项集b c , l b d c d c d t bed bc b d t 该算法能比较有效地产生关联规则，但也存在着以下缺点：( 1 ) 算法产生 太多的冗余的规则。当数据库太大或支持度、可信度阈值太低时产生的规则太 多，用户很难人为地对这些规则做出区分、判断。( 2 ) 算法在效率上存在着问 题。主要是因为数据库扫描次数太多，寻找每一个k - 项集( k = 1 ，k ) 都需要 扫描数据库一次，共需扫描数据库k 次。另外，当模式太长时产生的候选项目 集也多得让人无法接受。因此，当数据库k 太大时，算法的耗时太大。 2 2 1 2 基于a p r i o r i 的改进算法 由于a p r i o r i 算法存在很多缺点，人们对a p r i o r i 算法进行了大量的改进， 希望能够找出一个高效、可靠的挖掘频繁项集的算法。 基于散列的优化方法【4 1 基于散列( h a s h - b a s e d ) 的优化方法可以用于压缩侯选k - 项集的集合c k ( k 2 ) 的大小。基本思想是：当扫描事务数据库，由侯选k 一项集产生频繁k 项集的时 候，同时产生每个事务的( k + 1 ) 项子集，并把它们散列到散列表的不同桶中，增 加桶的计数，在下次产生侯选( k + 1 ) 项集的时候，可以根据散列表和最小支持 度排除一些无意义的侯选项集。这种技术当k - - 2 时特别有效。它的关键是构造 一个有效的散列函数。 基于事务压缩的优化方法1 2 s 2 9 3 基于事务压缩( t r a n s a c t i o nr e d u c t i o n ) 的优化方法通过减少不必要的事务个数 来减小扫描的事务数据库的大小，以提高挖掘的效率一个基本的原理就是当 一个事务不包含任何k - 项集的时候，它必然也不可能包含任何( k + 1 ) 项集，从而 我们可以将这些事务删除，因为在为产生 十1 ) 项集而扫描事务数据库的时候已 经不再需要它们了 基于划分的优化方法f 5 】 基于划分( p a r t i t i o n i n g ) 的优化方法采用对原事务数据库d 进行两遍扫描的 技术。在第l 遍，首先将事务数据库d 划分成n 个非重叠的部分，每个部分的 最小支持度计数等于d 的最小支持度r a m _ s u p 与该部分的事务数之积。对于每 一部分，找出该部分的频繁项集，称作局部频繁项集( 1 0 c a lf r e q u e n ti t e m s e t ) 局 部频繁项集可能不是整个事务数据库的频繁项集，整个事务数据库的任何一个 频繁项集必须作为局部频繁项集至少出现在一个部分中。这样，把所有局部频 繁项集的集合作为d 的侯选项集，称作全局侯选项集。再次扫描d ，根据全局 1 0 侯选项集和实际最小支持度r a i ns u p 确定全局频繁项集。每一部分的大小和划 分的数目由是否能够把该部分放入内存来确定。 基于采样的优化方法【6 1 基于采样( s a m p l i n g ) 的优化方法是在一个给定数据库d 的随机样本s 中进行 挖掘，这种方法牺牲了精确性以换取有效性，样本s 的大小由是否能够把它放 入内存来确定。样本s 中的频繁项集不定是数据库d 中的频繁项集，而且， 数据库d 中的频繁项集不一定出现在样本s 的频繁项集中，因此，应该使用比 最小支持度低的支持度值来搜索样本s 中的频繁项集，之后，通过数据库的其 余部分再来计算每个项集的实际频繁度。当效率是决定因素的时候，采样方法 特别合适。 基于动态项集计数的优化方法3 0 1 基于动态项集计数( d y n a m i ci t e r n s e tc o u n t i n g ) 的优化方法将数据库划分为标 记开始点的块，算法可以在任何开始点添加新的侯选项集。该技术动态地评估 已被计数的所有项集的支持度，如果一个项集的所有子集已被确定为频繁的， 则添加它作为新的侯选项集。该算法对数据库的扫描次数比a p r i o r i 算法少。 2 2 2 不产生候选挖掘频繁项集的算法 在许多情况下，a p r i o r i 算法大幅度压缩了侯选项集的大小，导致了很好的 性能。但即使是进行了优化，a p r i o f i 系列算法仍然无法克服它的一些固有缺陷： ( 1 ) 可能产生大量的侯选项集。若频繁1 项集的个数为1 0 0 0 0 ，则侯选2 一项 集的个数将超过1 0 m ；若要发现长度为1 0 0 的频繁项集，则必将产生多达2 约等于1 0 3 0 个侯选项集。 ( 2 ) 无法对稀有信息进行分析。算法无法对小于最小支持度m i n _ s u p 的事务 进行处理，若m i ns u p 设置过低，则算法效率又成了个问题。 ( 3 ) g 能需要多次重复扫描数据库扫描的次数随着要发现的频繁项集长度 的增加而增加。 2 2 2 1 频繁模式增长f p 算法 h a n 等人于2 0 0 0 年提出一种新的基于f p 树的频繁模式增长算澍7 1 ，简称 为f p g r o w t h ( f r e q u e n tp a t t e r ng r o w t h ) 算法，能够在不产生侯选项集的情况下产 生所有的频繁项集。它采取如下的分而治之策略：将提供频繁项集的数据库压 缩成一棵频繁模式树( 或称为f p 树) ，但仍保留项集关联信息；然后，将这种压 缩后的数据库分成一组条件数据库( 一种特殊类型的投影数据库) ，每个关联一个 频繁项，并分别挖掘每个数据库。 1 生成频繁模式树 频繁模式树的生成步骤： ( a ) 扫描事务数据库d 一次，产生频繁l 一项集，并得到他们的支持度计数。 频繁项的集合按支持度计数的递减顺序排序，用l 表示。 ( b ) 创建f p 树的根节点，以“n u l l ”标记它。对于d 中的每个事务，执行： 选择事务中的频繁项，并按l 中的次序排序。设排序后的频繁项表为 p i p ， 其中p 是第一个元素，而p 是剩余元素的表。调用i n s e r t _ t r e e ( p i p ，t ) ，该过程 的执行情况如下：如果t 有子女n 使得n i t e m - n a m e = p i t e m - n a m e ，则n 的计数 增加l ；否则创建一个新节点n 将其计数设置为1 ，链接到它的父节点t ，并且 通过节点链结构将其链接到具有相同i t e m - n a m e 的节点。如果p 非空，递归地 调用i n s e r t 。_treefp,n) 我们仍用图2 - 1 所示的例子，通过频繁模式树生成算法得到的事务数据库d 的频繁模式树如图2 3 所示。( 设最小支持度计数为2 ) 项计数；结点链 一三- 固。固_ 矗 9 ： c 71 一- b6 i d3 ： 一一- 、 = - i ! z ：，：l 2 i 匕生回 d ：1c - - 函箫7 图2 - 3 存放压缩的频繁模式信息f p - 树 2 挖掘频繁项集 对f p 一树进行挖掘将生成全部频繁项集，挖掘过程由长度为1 的频繁模式f 初 始后缀模式) 开始，通过构造它的条件模式基( 一个“子数据库”，由f p 树中 与后缀模式一起出现的前缀路径集组成) 和条件f p 树，并递归地在f p 树上进 行挖掘。模式增长通过后缀模式与由条件f p 树产生的频繁模式连接实现。 f p - 增长方法将发现长频繁模式的问题转换成递归地发现一些短模式，然后 连接后缀。它使用最不频繁的项作后缀，提供了好的选择性，该方法大大降低 了搜索开销。 对于图2 3 所示的频繁模式树，对其进行挖掘的结果如表2 一l 所示。由表 2 一l 产生的频繁项集可以看出，这一结果与用a p r i o r i 算法产生的频繁项集( 图2 2 ) 相同。 表2 - 1 挖掘f p - 树产生频繁项集的结果 1 l 咖 务件模式基 备件l q , - # y 产生的频繁项集 e ( a b 。d ：1 ) ，( a c ，b ：1 ) a c ：2 ， b e ：2 ) 。 如e ：2 ) d ( a b ：2 ) ，瓴c ：1 ) a d 3 ， b ，d ：2 ， a ，b ，d ：2 ) b ( a ：3 ) ，( 叩：2 ) ，( c ：1 ) ) 如：5 ) ， b c ：3 ， 曲，c ：2 ) c ( a ：5 ) ) a c ：5 山东大学硕士学位论文 2 2 2 2 对f p g r o w t h 算法的分析 优点：( 1 ) 一个大型数据库能够被有效地压缩成比原数掘库小很多的高密 度的数据结构，避免了重复扫描数据库的开销。( 2 ) 该算法基于f p t r e e 的挖 掘采取模式增长的递归策略，创造性地提出了无候选项目集的挖掘方法，在进 行频繁项目集的挖掘时效率较好。( 3 ) 挖掘过程中采取了分治的策略，将这种 压缩后的数据库d 分成一组条件数据库风，每个条件数据库关联一个频繁项， 并分别挖掘每一个条件数据库。而这些条件数据库要远远小于数据库d 。 缺点：该算法采取模式增长的递归策略，虽然避免了候选项目集的产生， 但在挖掘过程，如果大项集的数量很多，并且如果由原数据库得到的f p t r e e 的分支很多，而且分支长度很长时，该算法将需要构造出数量巨大的条件 f p - t r e e ，不仅费时而且要占用大量的空间，挖掘效率不好，且递归算法本身效 率也较低。 2 2 3 最大频繁项目集挖掘 由频繁项目集的性质我们知道最大频繁项目集已经隐含了所有的频繁项目