（计算机应用技术专业论文）最大频繁项目集挖掘算法研究(1).pdf

中文摘要 关联规则是数据挖掘的一个重要分支，用于发现存在于数据库中的项或属性 间的有趣联系，这些联系是事先未知且隐藏的，即不能通过传统的数据库逻辑操 作或统计的方法得出。 本文首先介绍了数据挖掘的基本概念、分类及一些常见的算法思想，其中着 重讨论了关联规则中挖掘频繁项目集算法。由于最大频繁项目集已经隐含了所有 频繁项目集，所以可以把发现频繁项目集的问题转化为发现最大频繁项目集的问 题。另外，某些数据挖掘应用仅需发现最大频繁项目集，而不必发现所有频繁项 目集，因而发现最大频繁项目集对数据挖掘具有重大意义。 第二是研究了在偶然或随机向数据库添加新记录的情况下，确定新的最大频 繁项目集的算法，即最大频繁项目集的增量更新问题。本文提出了一种高效的更 新算法，即利用原来f p - 树和已经挖掘出的最大频繁项目集去发现新的最大频繁 项目集。本算法对新增事务处理时，不再向原来f p _ 树子树上增加结点或增加某 结点的支持数，而是建立根的新子树或者向新子树上增加结点或增加某结点的支 持数。算法只对新增的频繁项目进行处理。对于支持数不变的频繁项目不再进行 处理。试验结果表明该算法比同样基于f p 一树的d m f i 算法挖掘最大频繁项目集 的效率更高。 第三是提出了一种基于频繁模式矩阵f p a r r a y 的挖掘最大频繁项目集的算 法。以前的许多挖掘最大频繁项目集算法是扫描数据库两遍，建立f p - 树，然后 在f p - 树上挖掘。本文设计了一种快速挖掘最大频繁项目集的算法。算法基本思 想：只扫描事务数据库一遍，把该数据库转换成一个矩阵f p - a r r a y ，矩阵保留 了所有事务数据库中项目间的关联信息，然后对该矩阵进行挖掘。在f p - a r r a y 中只存放逻辑型数据，节省了存储空间。直接在f p a r r a y 上挖掘而不需要递归 创建大量条件模式矩阵，挖掘过程采用逻辑运算，在效率上有独特的优势。通过 实验验证了算法的有效性。 关键词：数据挖掘，关联规则，增量更新算法，频繁模式矩阵，最大频繁项且 集 a bs t r a c t a s s o c i a t i o nr u l ei so n eo ft h em o s ti m p o r t a n td o m a i n so fd a t am i n i n g i ti su s e d t od i s c o v e rt h ei n t e r e s t i n gr e l a t i o n sb e t w e e ni t e m so ra t t r i b u t e so fd a t a b a s e t h e s e r e l a t i o n sa r eu n k n o w na n dh i d d e n ，i e i tc a n n o tb ea c q u i r e dt h r o u g h t r a d i t i o n a ll o g i c o p e r a t i o n so rs t a t i s t i c s f i r s t l vt h i sp a p e ri n t r o d u c e st h eb a s i cc o n c e p t i o n s ，c l a s s i f i c a t i o no fd a t am i n i n g a n ds o m eg e n e r a lt h o u g h t so fa l g o r i t h m sa b o u ta s s o c i a t i o nr u l e e m p h a s i si sp u to n t l l ed i s c u s s i o no fm i n i n ga l g o r i t h m so ff r e q u e n ti t e m s e t s b e c a u s em a x i m u mf r e q u e n t i 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 gf r e q u e n ti t e m 。s e t si s c 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 ti t e m 。s e t s m o r e o v e r , s o m e d a t am i n i n ga p p l i c a t i o nn e e d so n l yt od i s c o v e rm a x i m u mf r e q u e n ti t e m 。s e t s ，i n s t e a d o fa l lf r e q u e n ti t e m - s e t s t h e r e f o r em 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 sl sv e r y i m p o r t a n ti nd a t am i n i n g s e c o n d l y , t h i sp a p e rs t u d i e st h ea l g o r i t h mo f d e t e r m i n i n gn e wm a x i m u mf r e q u e n t i t e m s e t s i nt h ec o n t e x to fa d d i n gn e wr e c o r dt ot h ed a t a b a s ea c c i d e n t a l l y , i e t h e p r o b l e mo fi n c r e m e n t a lu p d a t i n go fm a x i m u mf r e q u e n ti t e m - s e t s t h i sp a p e rp r e s e n t s a ne f f e c t i v eu p d a t i n ga l g o r i t h m i tu s e sf p - t r e ea n dm a x i m u mf r e q u e n ti t e m - s e t st h a t h a v eb e e nm i n e dt od i s c o v e rn e wm a x i m u mf r e q u e n ti t e m 。s e t s i np r o c e s s i n gn e w w o r k t h i sa l g o r i t h mn ol o n g e ra d d sn e wn o d e st ot h ef p - t r e eo rs u p p o r tc o u n to fa n y n o d e i n s t e a di tc r e a t e sn e ws u bt r e eo fr o o to ra d d sn o d e s t ot h en e ws u b 。t r e eo ra d d s s u p p o r tc o u n to fa n yn o d e t h i sa l g o r i t h mo n l y h a n d l e sn e w l yi n c r e a s e df r e q u e n t i t e m si n s t e a do ff r e q u e n ti t e m sw h o s es u p p o r tc o u n td o s en o tc h a n g e t h ee x p e r i m e n t r e s u i ts h o w st h a t t h i sa l g o r i t h mi sm o r ee f f i c i e n tt h a nt h ed m f i aa l g o r i t h mb a s e do n f p t r e ef o rm i n i n gm a x i m u mf r e q u e n ti t e m s e t s t h i r d l y , an e wa l g o r i t h mf o rm 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 sb a s e do n f p a r r a yi sp r e s e n t e d m a n yo r i g i n a la l g o r i t h m s f o rm 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 ss c a nd a t a b a s et w ot i m e s ，c r e a t ef p - t r e ea n dm i n eo nf p _ t r e e an e w a i g o r i t h mf o rm i n i n gm a x i m u mf r e q u e n ti t e m - s e t sb a s e do nf p - a r r a yi sp r e s e n t e d t h em a i nc o n c e p to ft h i sa l g o r i t h mi st oc o n v e r tat r a n s a c t i o nd a t a b a s ei n t oaf p 。a r r a y t h r o u g hs c a n n i n gt h ed a t a b a s eo n l yo n c e t h ef p - a r r a y r e t a i n sa l li n f o r m a t i o no f i t e m si nd a t a b a s e t h ea l g o r i t h mt h e nd o e st h em i n i n go nt h ea r r a y f p a r r a yi sb e t t e r i nm e m o r yb e c a u s ei to n l ys t o r e sl o g i cd a t a m i n i n gu p o nf p 。a r r a yn e e dn o tc r e a t e c o n d i t i o n a la r r a yi nt h em i n i n gp r o c e s s a st h em i n i n gp r o c e s sa d o p t sl o g i co p e r a t i o n ， i th a sp r e d o m i n a n c ei ne f f i c i e n c y a ne x p e r i m e n ti sd o n et ov e r i f yt h ee f f e c t i v e n e s so f t h i sa l g o r i t h m k e yw o r d s ：d a t am i n i n g ，a s s o c i a t i o nr u l e s ，i n c r e m e n t a lu p d a t i n ga l g o r i t h m ， f r e q u e n tp a t t e r na r r a y , m a x i m u mf r e q u e n ti t e m 。s e t s 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得盔连盘茔或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 学位论文作者签名：李意哗 签字日期： 名舶7 年 月? d 日 学位论文版权使用授权书 本学位论文作者完全了解丕鲞苤堂有关保留、使用学位论文的规定。 特授权苤鲞盘鲎可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校 向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：季棼哗 导师签名： 签字日期： z 聊年f 月5 d 同 签字日期： 。7 年7 月岁汐日 犀卟 天津大学硕士学位论文 第一章绪论 第一章绪论 1 1 数据挖掘产生的背景和应用前景 随着科学技术的飞速发展，经济和社会都取得了极大的进步，在各个领域产 生了大量的数据，如人类对太空的探索，银行每天的巨额交易数据。显然在这些 数据中有丰富的信息，如何处理这些数据得到有益的信息，人们进行了有益的探 索。计算机技术的迅速发展使得处理这些数据成为可能，这就推动了数据库技术 的极大发展，但是面对不断增加如潮水般的数据，人们不再满足于数据库的查询 功能，提出了深层次问题：能不能从数据中提取信息或者知识为决策服务。就数 据库技术而言已经显得无能为力了，同样，传统的统计技术也面临了极大的挑战。 这就急需有新的方法来处理这些海量般的数据。于是，人们结合统计学、数据库、 机器学习等技术，提出数据挖掘来解决这一难题。 数据挖掘( d a t a m i n i n g ) 就是从大量的、不完全的、有噪声的、模糊的、随 机的实际应用数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用 的信息和知识的过程。 数据挖掘是一门交叉学科，它把人们对数据的应用从低层次的简单查询，提 升到从数据中挖掘知识，提供决策支持。在这种需求牵引下，汇聚了不同领域的 研究者，尤其是数据库技术、人工智能技术、数理统计、可视化技术、并行计算 等方面的学者和工程技术人员，投身到数据挖掘这一新兴的研究领域，形成新的 技术热点。 现今资料流通量巨大，我们遇到了诸如巨量的记录，高维的资料增加的传统 分析技术上的困难，搜集到的资料仅有5 至1 0 用来分析，以及资料搜集过程 中并不探讨特性等问题，这就让我们不得不利用d a t am i n i n g 技术。 数据挖掘综合了各个学科技术，有很多的功能，当前的主要功能如下： 1 分类：按照分析对象的属性、特征，建立不同的组类来描述事物。例如： 银行部门根据以前的数据将客户分成了不同的类别，现在就可以根据这些来区分 新申请贷款的客户，以采取相应的贷款方案。 2 聚类：识别出分析对内在的规则，按照这些规则把对象分成若干类。例如： 将申请人分为高度风险申请者，中度风险申请者，低度风险申请者。 3 关联规则和序列模式的发现：关联是某种事物发生时其他事物会发生的这 天津大学硕士学位论文第一章绪论 样一种联系。例如：每天购买啤酒的人也有可能购买香烟，比重有多大，可以通 过关联的支持度和可信度来描述。与关联不同，序列是一种纵向的联系。例如： 今天银行调整利率，明天股市的变化。 4 预测：把握分析对象发展的规律，对未来的趋势做出预见。例如：对未来 经济发展的判断。 5 偏差的检测：对分析对象的少数的、极端的特例的描述，揭示内在的原因。 例如：在银行的1 0 0 万笔交易中有5 0 0 例的欺诈行为，银行为了稳健经营，就要 发现这5 0 0 例的内在因素，减小以后经营的风险。 我们讨论的问题集中在数据挖掘的关联规则上，发现数据项之间的关联规 则。关联规则是发现事务数据库中不同商品( 项) 之间的联系，这些规则找出顾 客购买行为模式，如购买了某一商品对购买其他商品的影响。发现这样的规则可 以应用于商品货架设计、货存安排以及根据购买模式对用户进行分类。虽然关联 规则是伴随零售业的飞速发展而产生的一种需求，但它的应用决不仅仅在零售业 上，还体现在银行、电信、保险、交通、证卷等，所以展开对关联规则的研究具 有重大意义。 1 2 数据挖掘研究现状 数据挖掘与传统的数据分析( 如查询、报表、联机应用分析) 的本质区别是 数据挖掘是在没有明确假设的前提下去挖掘信息、发现知识( 也包括大量的不公 开的数据) 。它是人们长期对数据库技术进行研究和开发的结果。起初各种数据 是存储在计算机的数据库中的，然后发展到可对数据库进行查询和访问，进而发 展到对数据库的即时遍历。数据挖掘使数据库技术进入了一个更高级的阶段，它 不仅能对过去的数据进行查询和遍历，并且能够找出过去数据之间的潜在联系， 从而促进信息的传递( 对于公开信息与非公开信息是相同的) 。因为对这种技术 进行支持的三种基础技术( 海量数据搜集，强大的多处理器计算机，数据挖掘算 法) 已经发展成熟，现在数据挖掘技术已经具备切实的可行性。 数据挖掘技术广泛应用于如银行、电信、保险、交通、零售( 如超级市场) 等领域【l z 3 4 】。数据挖掘所能解决的典型商业问题包括：数据库营销( d a t a b a s e m a r k e t i n g ) 、客户群体划分( c u s t o m e rs e g m e n t a t i o n & c l a s s i f i c a t i o n ) 、背景分析 ( p r o f i l e a n a l y s i s ) 、交叉销售( c r o s ss e l l i n g ) 等市场分析行为以及客户流失性分 析( c h u ma n a l y s i s ) 、客户信用记分( c r e d i ts c o r i n g ) 、欺诈发现( f r a u dd e t e c t i n g ) 等。数据挖掘在网络中的应用也已经成为一个热点。在电子商务方面，从服务器 以及浏览器端的日志记录中自动发现隐藏在数据中的模式信息，了解系统的访问 天津大学硕士学位论文 第一章绪论 模式以及用户的行为模式，作出预测性分析；在网站设计方面，通过对网站内容 的挖掘，可以有效地组织网站信息，例如采用自动归类技术实现网站信息的层次 性组织，通过对用户访问日志记录信息的挖掘，把握用户的兴趣，有助于开展网 站信息推送服务以及个人信息的定制服务；在搜索引擎的使用方面，数据挖掘的 最大特色体现在它所采用的对网页l i n k s 信息的挖掘技术上，如通过对网页内容 挖掘，可以实现对网页的聚类、分类，实现网络信息的分类浏览与检索；通过用 户所使用的提问式的历史记录的分析，可以有效地进行提问扩展，提高用户的检 索效果；运用网络内容挖掘技术改进关键词加权算法，提高网络信息的标引准确 度，从而改善检索效果。 为了适应数据挖掘的发展和应用，涌现出了大量不同的数据挖掘软件【5 j ，据 著名数据挖掘网站k d n u g g e t s 统计，目前约有5 0 多种数据挖掘软件问世。当前 主流的挖掘工具如s a se n t e r p r i s em i n e r 、i b mi n t e l l i g e n tm i n e r 、t e r a d a t a w a r e h o u s em i n e r 、s p s sc l e m e n t i n e 等都能够提供常用的挖掘过程和挖掘模式。 与国外相比，国内对数据挖掘和知识发现的研究稍晚，没有形成整体力量。 1 9 9 3 年国家自然科学基金首次支持对该领域的研究项目。目前，国内的许多科 研单位和高等院校竞相开展数据挖掘和知识发现的基础理论及其应用研究，这些 单位包括清华大学、中科院计算技术研究所、空军第三研究所、海军装备论证中 心等。其中，北京系统工程研究所对模糊方法在知识发现中的应用进行了较深入 的研究，北京大学也在开展数据立方体代数的研究，华中理工大学、复旦大学、 浙江大学、中国科技大学、中科院数学研究所、吉林大学等单位开展了对关联规 则挖掘算法的优化和改造；南京大学、四川联合大学和上海交通大学等单位探讨、 研究了非结构化数据的知识发现以及w e b 数据挖掘。最近几年，国内关于数据 挖掘的研究论文增长很快f 6 j 。 目前在国内采用数据挖掘软件的企业和机构还很少，但是随着数据库和 i n t e m e t 在国内企业的普遍运用，使用数据挖掘软件获取信息会被越来越多的国 内企业和机构所接受，数据挖掘软件的国内市场在未来几年也将不断扩大并趋向 成熟。 1 3 本文主要研究内容 数据挖掘的目标是采用有效的算法，从大量现有的数据集合中发现并找出最 初未知的但最终可理解的有用知识，并用简明的方式表示出来。是否能够达到预 期的目的在很大程度上与数据挖掘的算法有关。因此，算法研究在数据挖掘上起 了至关重要的作用。 天津大学硕士学位论文第一章绪论 论文主要对数据挖掘中关联规则的挖掘算法进行了研究。关联规则用于发现 大量数据中的项集之间有意义的关联，寻找给定数据集中项集之间的有趣关系。 论文其余部分按以下方式组织： 第二章，介绍了关联规则的有关概念、种类和挖掘过程。 第三章，介绍了关联规则挖掘的经典算法及分析。 第四章，实现了基于f p 树的最大频繁项目集增量更新挖掘算法。 第五章，提出了基于频繁模式矩阵的最大频繁项目集挖掘算法。 第六章，总结与展望。总结全文并展望了未来可能的进一步研究方向。 天津大学硕士学位论文 第二章关联规则挖掘 2 1 关联规则的概念 第二章关联规则挖掘 关联规则是一种常见的数据挖掘方法，近年引起了很多研究者的关注【7 岿】。 关联规则是美国i b ma l m a d e nr e s e a r c hc e n t e r 的r a k e s ha g r a w a l 等人于1 9 9 3 年 首先提出来的k d d 研究的一个重要课题，现实中一个比较典型的例子是购物篮 分析。超级市场利用前端收款机收集存储了大量的售货数据，这些数据是一条条 的购买事务记录，每条记录存储了事务处理时间，顾客购买的物品，物品的数量 及金额等。这些数据中常常隐含形式如下的关联规则：在购买牛奶的顾客当中， 有6 0 的人同时购买了面包。这些关联规则很有价值，商场管理人员可以根据 这些关联规则有选择地安排货架，能够促进销售【9 】。 简单的说，关联规则就是描述这种在一个事务中物品之间同时出现的规律的 知识模式。更确切地说，关联规则通过量化的数字描述物品甲的出现对物品乙的 出现有多大的影响。关联规则模式属于描述型模式，发现关联规则的算法属于无 监督学习的方法。 关联规则的基本模型描述如下： 设有事务数据库d = t 1 ，t 2 ，：，t n ) ，t j 0 = 1 ，2 ，n ) 称为事务t ；构成t 的元素i k ( k = l ，2 ，p ) 被称为项；设d 中所有项的集合为i = i l ，i 2 ，i m ) 。 【定义1 项集与频繁项集设a = ，m i n s u p ，则a 称为d 中的频繁项集。 定义2 】关联规则关联规则是形如a = b 的蕴含式，其中a 和b 都是d 中的项集，且a n b = 。a 称为关联规则的条件，b 称为关联规则的结论。 一般用三个参数来描述一个关联规则。 ( 1 ) 可信度 关联规则a = b 的可信度就是同时包含项集a 和项集b 的事务在所有包含 项集a 的事务中所占的百分比。设d 中包含项集a 的事务中，有c 的事务同 时也包含项集b ，c 称为关联规则的可信度。即： 天津大学硕士学位论文第二章关联规则挖掘 c o n f i d e n c e ( a = b ) = p ( b a ) ( 2 ) 支持度 关联规则a = b 的支持度就是同时包含项集a 和项集b 的事务在d 的所有 事务中所占的百分比。也就是项集的支持度。设d 中有s 的事务同时包含项集 a 和b ，s 称为关联规则的支持度。即： s u p p o r t ( a = b ) = p ( aub ) 关联规则的支持度和可信度分别反映了该规则的实用性和可靠性，它们是衡 量用户对关联规则感兴趣程度的常用度量指标。 事实上人们一般只对满足一定的支持度和可信度的关联规则感兴趣。因此， 为了发现有意义的关联规则，需要给定两个阈值：最小支持度( m i n s u p ) 和最小 置信度( m i n c o n f ) 。前者即用户规定的关联规则必须满足的最小支持度，它表示 了一组物品集在统计意义上的需满足的最低程度；后者即用户规定的关联规则必 须满足的最小可信度，它反应了关联规则的最低可靠度。这些阈值可以由用户或 专家设定。 ( 3 ) 相关支持度( c o r r e l a t i o i l s u p p o n ) 【1 0 1 1 】 在事务数据库d 中有关联规则x = y ，该关联规则的相关支持度为： c o r r e l a t i o n _ _ s u p p o r t = s u p p o r t ( xuy ) ( s u p p o r t ( x ) xs 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 ；支持度则反映了这种情况在事务 中是否是普遍的规律。 定义3 】强关联规则 如果存在关联规则a = b ，其支持度和可信度都不低 于用户预设的最小支持度阈值( m i n s u p ) 和最小可信度阈值( m i n c o n f ) ，则称其为强 关联规则。强关联规则是用户感兴趣的、对用户发现大量数据集中潜在规律具有 重要指导意义的关联规则。 根据以上关联规则的概念描述，关联规则挖掘的基本过程可以概括为从给定 的事务数据库中，通过一定的数据挖掘算法，寻找满足预设的最小支持度阈值和 最小可信度阂值的所有强关联规则。 2 2 关联规则的种类 我们将关联规则按不同的情况进行分类： 1 基于规则中处理的变量的类别，关联规则可以分为布尔型和数值型。 天津大学硕士学位论文第二章关联规则挖掘 布尔型关联规则处理的值都是离散的、种类化的，它显示了这些变量之间的 关系；而数值型关联规则可以和多维关联或多层关联规则结合起来，对数值型字 段进行处理，将其进行动态的分割，或者直接对原始的数据进行处理，当然数值 型关联规则中也可以包含种类变量。 例如：性别= “女 = 职业= “秘书 ，是布尔型关联规则； 性别= “女”： a v g ( 收入) = 2 3 0 0 ，涉及的收入是数值类型，所以是一个数 值型关联规则。 2 基于规则中数据的抽象层次，可以分为单层关联规则和多层关联规则。 在单层的关联规则中，所有的变量都没有考虑到现实的数据是具有多个不同 的层次的；而在多层的关联规则中，对数据的多层性已经进行了充分的考虑。 例如：i b m 台式机= s o n y 打印机，是一个细节数据上的单层关联规则； 台式机= s o n y 打印机，是一个较高层次和细节层次之间的多层关联规则。 3 基于规则中涉及到的数据的维数，关联规则可以分为单维的和多维的。 在单维的关联规则中，我们只涉及到数据的一个维，如用户购买的物品；而 在多维的关联规则中，要处理的数据将会涉及多个维。换成另一句话，单维关联 规则是处理单个属性中的一些关系；多维关联规则是处理各个属性之间的某些关 系。 例如：啤酒= 尿布，这条规则只涉及到用户所购买的物品； 性别= “女”- 职业= “秘书”，这条规则就涉及到两个字段的信息，是两个 维上的一条关联规则。 2 3 关联规则的挖掘过程 关联规则的挖掘一般包括两步： ， ( 1 ) 找出事务数据库d 中所有大于等于用户指定最小支持度的项目，具有最 小支持度的项目的集合称为频繁项目集，简称频集。 ( 2 ) 由频繁项集产生强关联规则。这些规则必须满足最小支持度和最小置信 度。 这两步中，第( 2 ) 步很容易，挖掘关联规则的总体性能由第一步决定。 天津大学硕士学位论文 第三章关联规则挖掘的经典算法及分析 第三章关联规则挖掘的经典算法及分析 挖掘关联规则首先需要找到所有支持度满足最小支持度的频繁项集。如果采 用直接多次遍历数据集的办法，找出所有可能的项集再加以判断其是否为频繁 项，可能会消耗很长的时间。采用一个好的频繁项集挖掘算法会极大地提高工作 效率。目前常用的典型算法有a p f i o f i 算法和f p - g r o w t h 算法等。 3 1a p r i o r i 算法及其优化 3 1 1a p r i o r i 算法 a p r i o r i 算法f 1 2 】是19 9 4 年a g r a w a l 等人提出的。该算法使用一种称作逐层迭 代的候选集产生测试的方法，k - 项目集用于探索( k + 1 ) 一项目集。首先，找出频繁 1 项目集的集合，该集合记作l l ，然后由l 1 得l 2 ，由l 2 得l 3 ，如此下去，直 到不能找到频繁k 项目集。每找一层l k 均需要一次数据库扫描。 算法：a p r i o r i 利用迭代逐级方法找出频繁项集 输入：事务数据库d ，最小支持度阈值m i n s u p 输出：频繁项集l ( 1 ) l1 = f i n d _ f r e q u e n t _ 1 - i m m s e t s ( d ) ； ( 2 ) f o r ( k = 2 ；l k - l 由；k + + ) ( 3 ) c k = a p r i o r i _ g e n ( l k 1 ，m i n s u p ) , ( 4 ) f o re a c ht r a n s a c t i o n st d ( 5 ) c t = s u b s e t ( c k ，t ) ；事务t 中包含的候选集 ( 6 ) f o re a c hc a n d i d a t ec c td oc c o u n t + + ； ( 7 ) ) ( 8 ) l k = c c k j c c o u n t 一m i n s u p ( 9 ) ) ( 1 0 ) r e t u r nl = uk l k , 产生侯选集的过程 p r o c e d u r ea p r i o r i g e n ( l k 1 ，m i n s u p ) ( 1 ) f o re a c hi t e m s e tp l k 1d o ( 2 ) f o re a c hi t e m s e tqel k id o 天津大学硕士学位论文第三章关联规则挖掘的经典算法及分析 ( 3 ) i f ( p 【1 】- q 1 】) 八a ( p 【2 】= q 【2 】) 八八( p 【k - 2 1 2 q k - 2 】) 八( p 【k l 】 q 【k - 1 】) ( 4 ) c = p q ； ( 5 ) i fh a s _ i n f r e q u e n t _ s u b s e t ( c ，l k - 1 ) t h e nd e l e t ec ； ( 6 ) e l s ea d dct oc k ； ( 7 ) ) ( 8 ) r e t u r nc k ； 检测c 的( k 1 ) 项集是否频繁 p r o c e d u r eh a s _ i n f r e q u e n t _ s u b s e t ( c ，l k q ) ( 1 ) f o re a c h ( k 1 ) 一s u b s e tso f cd o ( 2 ) i fn o ts l k qn 证nr e t u r nt r u e ； ( 3 ) r e t u r nf a l s e ； 在a p r i o r i 算法中，寻找频繁项目集需要对数据集进行多步处理。首先，统 计所有含一个因素项集出现的概率，并找出那些不小于最小支持度的项目集，即 一维频繁项目集。然后，开始循环寻找更大频繁项集直到没有频繁项目集生成。 循环过程是：第k 步中，根据第k 1 步生成的( k 1 ) 维频繁项目集产生k 维候选项 目集，然后对数据库进行搜索，得到候选项目集的支持度，将其与最小支持度比 较，从而找到k 维频繁项目集。 a p r i o r i 算法是一种最有影响的挖掘布尔关联规则的算法，算法基于频繁项 集的先验知识，利用a p r i o r i 性质：频繁项集的所有非空子集都必须是频繁的。 性质用于压缩搜索空间。可以提高频繁项目集逐层产生的效率。 a p r i o r i 算法主要有两个步骤：连接( j o i n ) 和剪枝，( p r u n e ) 。 连接是指通过将l k - 1 与自身连接构成候选项集c k 。设l k = i l ，1 2 ，1 3 i k ) ，i i ( j ) 表示i i 的第j 项，可以连接的条件是l k 的前k 一1 项相同。l k 1 和l k - i 连接的结果 就是i l ( 1 ) i l ( 2 ) 1 1 ( 3 ) 1 1 ( 1 ( - 1 ) 1 2 ( k ) 。 剪枝是指对c k 分析，找出其中的频繁k 项集l k 。 从数据库中的事务找出频繁项集后，就可以产生出强关联规则了。 设有数据库d ，有四个事务记录，如表3 1 所示 表3 1 数据库d t i di t e m g t 1i1 ，i3 ，i4 t 2i2 ，工3 ，i5 t 3i1 ，i2 ，i3 ，i5 t 4i2 ，i5 天津大学硕士学位论文第三章关联规则挖掘的经典算法及分析 在a p r i o r i 算法中每一步创建该步的侯选集。统计每个侯选项目集的支持度， 并和预定义的最小支持度比较，来确定该步的频繁项目集。 首先统计出一维项目集，即c 1 。这里预定义最小支持度m i n s u p = 2 ，侯选项目 集中满足最小支持度要求的项目集组合成频繁的1 - i t e m s e t s 。为生成频繁 2 - i t e m s e t s ，使用i o i n ，即：l 1j o i nl 1 ，并通过p r u n e 删除那些子集不在l 1 中的项目 集。生成了侯选项目集c 2 。搜索d 中4 个事务，统计c 2 中每个侯选项目集的支 持度。然后和最小支持度比较，生成l 2 。侯选项目集c 3 是由l 2 生成。要求自连 接的两个频繁2 - i t e m s e t s 中，第一个项目相同，在l 2 中满足该条件的有 0 2 ，1 3 ， 1 2 ，1 5 ) 。这两个集合经过j o i n 后，产生集合 1 2 ，1 3 ，i 5 。在p r u n e 中，测 试 1 2 ，1 3 ，1 5 的子集 1 3 ，1 5 ) ， i 2 ，i 3 ， i 2 ，i 5 是否在l 2 中，由l 2 可以知道 1 3 ，1 5 ， 1 2 ，i 3 ， 1 2 ，1 5 本身就是频繁2 - i t e m s e t s 。即 1 2 ，1 3 ，1 5 的子集都是频繁项目 集。那么 1 2 ，1 3 ，1 5 ，为侯选3 - i t e m s e t 。然后搜索数据库中所有事务记录，生成频繁 3 4 i e m s e t sl 3 。 此时，从l 3 中不能再生成侯选4 i t e m s e t 。a p r i o r i 算法结束。如 图3 1 所示。 天津大学硕士学位论文第三章关联规则挖掘的经典算法及分析 d ：s u p p o r - t - - - - 2c 1 t i di t e m s t 1i l 燃 t 2 1 2 燃 t 3 i l 工五瓿验 t 4 1 2 城 项集 ( 1 1 ，1 2 ) ( 1 1 ，1 3 ) ( 1 1 ，1 5 ) 1 2 ，1 3 ) ( 1 2 ，1 5 ) 1 3 ，1 5 ) 扫描d ，对每个候选计数 c ：o 扫描d ，对_ 个候选计数 项集支持度计数 ( i l ，1 2 ) l ( 1 1 ，1 3 ) 2 ( i l ，1 5 ) 1 ( 1 2 ，1 3 ) 2 ( 1 2 ，1 5 ) 3 ( 1 3 ，1 5 ) 2 l 3 项集 支持度计数 ( 1 1 ) 2 ( 1 2 ) 3 ( 1 3 ) 3 ( 1 4 ) 1 ( 1 5 ) 3 项集支持度计数 ( 1 1 ) 2 ( 1 2 ) 3 ( 1 3 ) 3 ( 1 5 ) 3 比较候选支持度计数 与最小支持度计数 i 项集支持度计数 i ( 1 2 ，1 3 ，1 5 ) 2 l 2 项集支持度计数 ( 1 1 ，1 3 ) 2 ( 1 2 ，1 3 ) 2 ( 1 2 ，1 5 ) 3 ( 1 3 ，1 5 ) 2 二：o c 3 比较候选支持度计数 与最小支持度计数 ：= = 匿i 3i s ) j ( 1 2 ，i ，i 候选支 计数与 支持度 图3 - i算法的图例说明 a p r i o r i 算法作为经典的频繁项目集生成算法，在数据挖掘中具有里程碑的 作用。但是随着研究的深入，在挖掘实践中a p r i o r i 暴露出二个致命的性能瓶颈。 第一：在每一步产生侯选项目集时循环产生的组合过多，没有排除不应该参 与组合的元素，可能产生庞大的候选集。 第二：每次计算项集的支持度时，都对数据库d 中的全部记录进行了一遍扫 描比较，如果是一个大型的数据库的话，这种扫描比较会大大增加计算机系统的 i o 开销。而这种代价是随着数据库的记录的增加呈现出几何级数的增加。因此 人们开始寻求一种能减少这种系统i o 开销的更为快捷的算法。 雠 = 生 二 产 = u l 广 2 由 兰 天津大学硕士学位论文 第三章关联规则挖掘的经典算法及分析 3 1 2 基于a p r i o r i 的几种优化方法 虽然a p r i o r i 算法自身已经进行了一定的优化，但是在实际的应用中，还是 存在令人不满意的地方，于是人们相继提出了一些优化的方法。为了提高算法的 效率，m a n n i l a 等引入了修剪技术来减小候选集c k 的大小【1 引，由此可以显著地 改进生成所有频集算法的性能。算法中引入的修剪策略基于这样一个性质：一个 项集是频集当且仅当它的所有子集都是频集。那么，如果c k 中某个候选项集有 一个( k 1 ) 子集不属于l k - 1 ，则这个项集可以被修剪掉不再被考虑，这个修剪过 程可以降低计算所有的候选集的支持度的代价。 l 、散列 该算法由p a r k 等在1 9 9 5 年提出【1 4 】。通过实验发现寻找频繁项集的主要计算 是在生成频繁2 项集l 2 上，p a r k 就是利用这个性质引入散列技术来改进产生频 繁2 项集的方法。 其基本思想是：当扫描数据库中每个事务，由c 1 中的候选1 项集产生频繁 1 项集l 1 时，对每个事务产生所有的2 项集，将它们散列到散列表结构的不同 桶中，并增加对应的桶计数，在散列表中对应的桶计数低于支持度阂值的2 项集 不可能是频繁2 项集，可从候选2 项集中删除，这样就大大压缩了要考虑的2 项 集。 2 、事务压缩 a g r a w a l 等提出压缩进一步迭代扫描的事务数的方法【1 5 1 6 】。因为不包含任何 k 项集的事务，不可能包含任何( k + 1 ) 项集，可对这些事务加上删除标志，扫描 数据库时不再考虑。 3 、划分 s a v a s e r e 等设计了一个基于划分的算法【1 7 】，这个算法先把数据库从逻辑上分 成几个互不相交的块，每次单独考虑一个分块并对它生成所有的频集，然后把产 生的频集合并，用来生成所有可能的频集，最后计算这些项集的支持度。这里分 块的大小选择要使得每个分块可以被放入主存，每个阶段只需被扫描一次。而算 法的正确性是由每一个可能的频集至少在某一个分块中是频集保证的。上面所讨 论的算法是可以高度并行的，可以把每一分块分别分配给某一个处理器生成频 集。产生频集的每一个循环结束后，处理器之间进行通信来产生全局的候选k 项集。通常这里的通信过程是算法执行时间的主要瓶颈；另一方面，每个独立的 处理器生成频集的时间也是一个瓶颈。其他的方法还有在多处理器之间共享一个 杂凑树来产生频集。更多的关于生成频集的并行化方法可以在文献1 8 中找到。 4 、选样 天津大学硕士学位论文第三章关联规则挖掘的经典算法及分析 基本思想是在给定数据的一个子集挖掘。对前一遍扫描得到的信息，仔细地 组合分析，可以得到一个改进的算法，m a n n i l a 等先考虑了这一点【l3 1 ，他们认为 采样是发现规则的一个有效途径。随后又由t o i v o n e n 进一步发展了这个思想【i9 】， 先使用从数据库中抽取出来的采样得到一些在整个数据库中可能成立的规则，然 后对数据库的剩余部分验证这个结果。t o i v o n e n 的算法相当简单并显著地减少了 的代价，但是一个很大的缺点就是产生的结果不精确，即存在所谓的数据扭曲 ( d a t as k e w ) 。分布在同一页面上的数据时常是高度相关的，可能不能表示整个数 据库中模式的分布，由此而导致的是采样5 的事务数据所花费的代价可能同扫 描一遍数据库相近。 5 、动态项集计数 b r i n 等人给出该算法【2 0 】。动态项集计数技术将数据库划分为标记开始点的 块。不象a p r i o r i 仅在每次完整的数据库扫描之前确定新的候选，在这种变形中， 可以在任何开始点添加新的候选项集。该技术动态地评估己被计数的所有项集的 支持度，如果一个项集的所有子集已被确定为频繁的，则添加它作为新的候选。 结果算法需要的数据库扫描比a p r i o r i