关联规则算法的实现与优化

ISSN 1002 - 4956实验技术与管理第29卷第8期2012年8月CN11- 2034/TExperimental Technology and ManagementVol.29 No.8 Aug. 2012关联规则算法的实现与优化王晶'，赵志强2(1. 首都医科大学科技处，北京10069;2. 首都医科大学后勤集团，北京100069>摘要:对基于关联规则的 数据挖掘算法进行了研究,对经典的频繁项集计数算法进行了改进.提高了关联规则数据挖掘的效率。优化结果证明了关联规则算法在医学科研实验室数据挖掘中的重要作用。关键词:关联规则;算法优化;数据挖掘中图分类号: TP311.13文献标志码: A文章 编号: 1002- 4956(2012)08- 0111 02.Implementation and optimization of algorithm of data miningassociation rules of data miningWang Jing'，Zhao Zhiqiang2(1. Office of Science and Technology, Capital Medical University, Beiing 10069, China;2. Logistics Service Group, Capital Medical University, Beijing 100069, China)Ahbstraet: This article analyses the algorithn to raise the asciation rules of data mining, and improves theclassic algorithm for Frequent Item Set Counting to raise the eficiecg of data mining. The opimized resultsshow that the algorithm of associaion rules of data mining in medical research laboratory has very importantrole.Key words: association rules; algorithm optimication; data mining本文对基于关联规则的数据挖掘算法进行了研I。称事务T支持物品集X，如果XCT,关联规则是究,分析了频繁项目生成算法规则,包括对经典算法如下形式的一种蕴含:X→Y,其中xC1,YC1,且x∩Apriori'I的设计与实现、分析与改进，以提高算法Y=φ。效率。(1)称物品集X具有大小为s的支持度,如果D .中有s%的事务支持物品集x;1关联规则挖掘定 义及形式(2)称关联规则X- +Y在事务数据库D中具有大考察一些涉及许多物品的事务:事务1中出现了小为s的支持度，如果物品集X∪Y的支持度为s;物品甲,事务2中出现了物品乙,事务3中则同时出现.(3)称规则x→Y在事务数据库D中具有大小为了物品甲和乙。那么，物品甲和乙在事务中的出现相s的可信度,如果D中支持物品集X的事务中有c%互之间是否有规律可循呢?在数据库的数据挖掘中，的事务同时也支持物品集Y。关联规则就是描述这种在-个事务中物品之间同时出2 Apriori 算法现的规律的知识模式。更确切地说,关联规则通过量化的数字描述物品甲的出现对物品乙的出现有多大的在基于关联规则的数据库挖掘技术中，频繁项目影响。集的计算问题(frequent item set counting, FIC) 是制设I= {i,iz, ..n. )是一组物品集(一个商场的约数据挖掘效率的关键。当事务数据库和所包含的项物品可能有上万种),D是一组事务集(称之为事务数目的数量很大时,频繁项集的数目也会变得非常大,导据库)。D中的每个事务T是一组物品,显然满足rS致频繁项集计数问题所花费的时间代价很高。Aprio-ri算法采用中国煤化工，是解决FIC问收稿日期:2012- 01-27题的有效的作者简介:王晶(1980-),女,山西晋城，工学硕士.助理研究员。从事科2.1算法思JYHCNMHG研信息管理及计算机技术应用.主要用于关联规则挖掘,即在交易数据、关系数据E-mail: wanging@ cmu. edu. cn或其他信息载体中,查找存在于项目集合或对象集合112实验技术与管理之间的频繁模式、关联、相关性或因果结构。其基本思3算法优化想[27是:频繁项集的任何子集也一定是频繁的。所谓频繁集是指满足最小支持度的项目集合,如果{AB)是(1)从逻辑上把数据库分成几个互不相交的块，频繁集,则(A},{B}也-定是频繁集。得到频繁项集每次单独考虑一个分块并对它生成所有的频集,然后后,便可产生基于该频繁集的强关联规则。合并产生的频集生成所有可能频集,最后计算这些项主要使用逐层搜索的迭代方法,即探索K项集来集的支持度[7。这里分块的大小选择要使每个分块可产生(K+1)-集,并用数据库扫描和模式匹配计算候放人主存,每个阶段只需被扫描一次[8]。而算法的正选集的支持度”。首先,找出频繁1-项集的集合。该确性是由每.-一个可能的频集至少在某一-个分块中是频集合记作L1. L1用于找频繁2-项集的集合,而L2用集保证[9的。于找L3 ,如此下去,直到不能找到频繁K-项集。(2)基于前一遍扫描得到的信息进行组合分析，Apriori算法基于以下性质来有效减少候选项目得到一个改进的算法[10 ,即在计算K-项集时，如果认集数目:一个K-项集是频繁项目集(1,当且仅当其所为某个(K + 1)项集可能是频集时,就并行地计算这个有的(K-1)子项集是频繁的。但在计算候选项集的(K+1)项集的支持度,这样需要的总的扫描次数通常支持率方面仍然存在一些问题,在第K轮的递推中，少 于最大的频集的项数11]。数据库中的每个事务t的所有K阶子项集都要判断(3)动态地评估已被计数的所有项集,可以避免其是否在K阶候选项集中。为了降低这个过程的复仅在每次完整的数据库扫描之前确定新的候选,它可杂性,其采用T Hash Tree和Hash Table表技术。但以在任何点添加，一旦一个项集的所有子集被确定为当K较小时,该技术效果不理想。而K较小时(K-<是频繁的，就可以启动对该项集支持度的计算1[12]。因4)算法的计算量可占到执行时间的90%以上。此所需的数据库扫描次数要比原算法要少。2.2算法设计与实现改进后的算法较原算法在时间和空间上都有了明Apriori算法的实现过程分为2步:一为连接,二显的提高。为剪枝。该算法基于一个频繁项集中任一子 集也应该参考文献( References)是频繁项集的性质,使用一种逐层搜索的迭代方法[5]，K-项集用于(K+1)项集。其算法流程如下:首先遍历[1]柴华昕,干勇. Apriori挖掘频繁项月集算法的改进[J].计算机工程目标数据库一次,记录每个项目或属性的出现次数,即与应用，2007(24):24-26.计算每个项目的支持度,收集所有支持度不低于用户[2]谢宗毅.关联规则挖掘Apriori算法的研究与改进[J].杭州电子科技大学学报,2006 ,23(3) :78-82.最小支持度的项目构成频繁1-项集L1,然后链接L1[3]钱少华,蔡勇,钱雪忠.基于数组的Apriori算法的改进[J].计算机中所有的元素形成候选2项集C2,再次遍历事务数据应用与软件，2006 ,23(2)44-46.库,计算C2中每个候选2项集的支持度,收集所有支[4]程玉胜,邓小光，江效尧. Apriori算法中频繁项集挖摑实现研究持度不低于用户最小支持度的项目构成频繁2-项集J].计算机技术与发展，2006,16(3):58- 60.L2,再链接L2形成C3,遍历数据库得L3,反复执行以[5]郭健美,宋顺林。基于Apriori算法的改进算法[J].计算机工程与.设计，2008.29<11).2814-2820.上过程，直到没有候选项集为止。[6]张梅峰,张建伟。基于Apriori的有效关联规则挖掘算法的研究首先在程序中用SQL语句生成了项集LI,即:[].计算机工程与应用，2003.39<19);196-198.create tablel l(tl char(5) ,tcount integer)其中,tl表示[7]袁万莲,郑诚、翟明清.一种改进的Apriori算法[J].计算机技术与项集中的每一项,tcount表示该项的支持度计数。扫发展,2008,18(5) :51-53.描表cP的tlist字段,根据该字段的存储特点,需要将[8] J卫平.关联规则挖抿Apriori算法的改进及其应用研究[J].南通大学学报,2008,7(1);50-53.tlist 字段各分量中以逗号分隔的数字取出并且通过模[9]何小东,刘卫国.数据挖掘中关联规则挖掘算法比较研究[J].计算式匹配统计它们的个数,取消重复后分别存放到LI表机工程与设计.2005 ,26<5):1265-1267.的tl和tcount字段中。[10]王创新.关联规则提取中对Apriori 算法的一种改进[J].计算机再逐层搜索迭代生成频繁候选K-项集LK,根据工程与应用,2004,40(34) :183-185.Apriori算法的思想，可以循环生成频繁K-项集,若生[11]安建成,刘超惠.频繁项集快速挖掘及更新算法[J].微电子学与计算机,2008,25(6);132-136.成的K项集为空集,则算法结束,K-I项集便是所求[12]吴伟平，中国煤化工关联规则发现算法[J].的频繁项集0]。计算机工YHCNMHG运用上述方法,得到频繁项集后，即可产生关联规则。由此我们可以实现算法。