布尔型关联规则挖掘算法研究

《布尔型关联规则挖掘算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、第32卷第1期计算机工程2006年1月Vol.32№1ComputerEngineeringJanuary2006·软件技术与数据库·文章编号：1000—3428(2006)01—0116—03文献标识码：A中图分类号：TP311布尔型关联规则挖掘算法研究12高俊，何守才（1.上海应用技术学院计算机系，上海200233；2.上海第二工业大学计算机系，上海200025）摘要：在分析FP_growth关联规则挖掘算法的基础上，提出了一种MFP的算法，给出了算法的工作原理。MFP算法能在一次扫描事务数据库过程中，把该数据库转换成MFP树，然后对MFP

2、树进行关联规则挖掘。MFP算法比FP_growth算法减少一次对事务数据的扫描，因此具有较高的时间效率。关键词：关联规则挖掘；FP_growth算法；MFP算法AFastAssociationRuleMiningAlgorithm12GAOJun,HEShoucai(1.Dept.ofComputerScience,ShanghaiInstituteofTechnology,Shanghai200233;2.Dept.ofComputerScience,ShanghaiSecondIndustrialUniv.,Shanghai200025)【

3、Abstract】BasedonfullyanalyzingtheFP_growth,anassociationruleminingalgorithm,thispaperpresentsanewassociationruleminingalgorithmcalledMFP.TheMFPalgorithmcanconvertatransactiondatabaseintoaMFPtreethroughscanningthedatabaseonlyonce,andthendotheminingofthetree.BecausetheMFPalgor

4、ithmscansatransactiondatabaseonetimelessthantheFP_growthalgorithm,theMFPalgorithmismoreefficientwithtime.【Keywords】Associationrulemining;FP_growthalgorithm;MFPalgorithm1概述度记数值递减的顺序排列各item，将结果记录在L表中，目前，挖掘频繁模式的经典算法是Apriori算法和L=[I2:7,I1:6,I3:6,I4:2,I5:2]。FP_growth算法[3]。FP_growt

5、h算法是用于从事务数据库中第二阶段，FP_growth算法开始构建FP-tree。它先创建挖掘布尔型关联规则的频繁模式[5]。它的整个挖掘过程比较标号为null的FP-tree根结点，然后再次扫描事务数据库，依复杂，但是可以简单地划分成3个基本步骤[6]：首先是扫描次读入每个事务记录。若一事务中的所有item都出现在L表事务数据库，根据给出的min_sup（最小支持度阈值）建立L中，则按在L表中的顺序重新排列它们，并在FP-tree中建立表；然后第二次扫描事务数据库，依据L表，构建FP-tree；对应的分支。图1事务数据库的第一条记录为T001

6、，因为它最后对构建的FP-tree进行挖掘，找出所有的频繁模式。有了的3个item均出现在L表中，所以按L表的顺序重新排列为：频繁模式就可以根据行业背景方便地建立所需的关联规则I2，I1，I5，并在FP-tree中构建一个以I2:1,I1:1,I5:1为标号[7]。下面是FP_growth算法进行关联规则挖掘的一个例子。的3结点分支，I2被连接到根结点，I1被连接到I2，I5被连被挖掘的事务数据库如图1所示[8]，并设定min_sup=2。图1接到I1。接着读入第二条事务记录T002。同样，T002中的中的Tid列为事务记录的标号，Listof

7、item_ID’s列为事务所I2，I4都出现在L表中，按L表的顺序排列为：I2，I4，并涉及到的item。表1中的事务数据库的首记录是标号为T001在FP-tree中建立对应的分支。由于在FP-tree的根结点下已的事务，该事务涉及到的item为I1，I2，I5。经存在I2:1结点，所以只需将I4:1连接到I2:1结点下，并把表1事务数据库I2:1结点的支持度记数值加上1，使该结点的标号变为I2:2。TIDListofitem_ID’s结点I2:2成为T001和T002的共同前綴。这样，对整个事务T001I1，I2，I5数据库扫描结束后，就构建

8、成了与之对应的FP-tree。为了便T002I2，I4于遍历FP-tree，创建一个项头表。项头表中的元素和排列顺T003I2，I3序与L表相同，每个