基于C的apriori算法实现

2013-03-05曾令伟王冬吴蒋

电脑知识与技术 2012年36期

曾令伟　王冬　吴蒋

摘要：Apriori算法是数据挖掘关联规则的经典算法，该文首先分析算法的基本思想，然后，在c语言环境中实现得出结果。

关键词：Apriori算法；C语言；数据挖掘

中图分类号：TP311 文献标识码：A 文章编号：1009-3044(2012)36-8692-03

关联规则数据挖掘的目的是在一个数据集中找出项与项之间的关系，也称之为购物蓝分析 (market basketanalysis)[1]。例如，购买上衣的顾客，有30%的可能也会买裤子，50%的买牛奶的顾客，也会买面包。关联规则的应用场合：在保险业务方面，如果出现了不常见的索赔要求组合，则可能为欺诈，需要作进一步的调查；在商业销售上，关联规则可用于交叉销售，以得到更大的收入；在医疗方面，可找出可能的治疗组合；在银行方面，对顾客进行分析，可以推荐感兴趣的服务等等。Apriori 算法是关联规则里一项经典算法，由Rakesh Agrawal 在 1994年提出[2]。

1 关联规则的概念

联规则挖掘可以发现存在于数据库中的项目或属性间的有趣关系，这些关系是预先未知的或者被隐藏的。下面用事务数据库来定义关联规则。

设交易(transaction) 的集合，，这里交易是项的集合，可以表述为：并且。中的元素称为项。对应每一个交易有唯一的标识，如交易号，记作。设是数据集中所有项的集合，是二进制文字的集合。中的任何子集称为项目集(itemset)，若，则称集合为项集。设和分别为中的事务和项目集，如果，称事务包含项目集。项目集的支持率,若不小于用户指定的最小支持率(记作：minsupport)，则称为频繁项目集，否则称为非频繁项目集。设，是数据集中的项目集。若，则；若，如果是非频繁项目集，则也是非频繁项目集；若，如果是频繁项目集，则也是频繁项目集[3]。

一个关联规则是形如的蕴涵式，这里，都是项目集，且，，并且，，分别称为关联规则的前提和结论[4]。一般使用支持度（support）和置信度（confidence）两个参数来描述关联规则的属性。

给定一个事务集，挖掘关联规则的问题就是产生支持度和置信度分别大于用户事先给定的最小支持度和最小置信度的关联规则。关联规则挖掘的任务就是要挖掘出中所有的强规则。强规则对应的项目集必定是频繁项目集，频繁项目集导出的关联规则的置信度可由频繁项目集和的支持度计算[4]。

3.2算法步骤

1）首先单趟扫描数据集，计算各个一项集的支持度，根据给定的最小支持度阈值，得到一项频繁集L1。

2）然后通过连接运算，得到二项候选集，对每个候选集再次扫描数据集，得出每个候选集的支持度，再与最小支持度比较。得到二项频繁集L2。

3）如此进行下去，直到不能连接产生新的候选集为止。

4）对于找到的所有频繁集，用规则提取算法进行关联规则的提取。

3.3 算法的流程图

参考文献:

[1] Han Jiawei,Kamber M.数据挖掘：概念与技术[M].范明,译.北京:机械工业出版社,2008.

[2] 陈京民.数据仓库与数据挖掘技术[M].北京:北京电子工业出版社,2007.

[3] Cabena P.Discovering Data Mining From Concept to Implementation[Z].IBM,2009.