Apriori算法关联规则挖掘技术研究
时间:2017-06-10 14:52 来源:毕业论文 作者:毕业论文 点击:次
| 1.1 关联规则挖掘产生原因啤酒和尿布的购买有关系吗？答案是肯定的，跟尿布一起购买最多的商品就是啤酒。据沃尔玛的分析调查，美国的太太们常叮嘱她们的丈夫下班后为小孩买尿布，而丈夫们在买尿布后又随手带回了他们喜欢的啤酒。对于隐藏在啤酒和尿布这类表面上风马牛不相及的商品背后的关联，如果不通过数据挖掘的技术，是没有办法靠拍脑袋的办法想出来的。这就是关联规则挖掘中最经典的例子。10031 世间万物的事情发生多多少少会有一些关联。一件事情的发生，很可能也会引起另外一件事情的发生。或者说，这两件事情在很多时候很大程度上是会一起发生的。那么人们通过发现这个关联的规则，可以由一件事情的发生，来推测另外一件事情的发生，从而更好地了解和掌握事物的发展、动向等等。这就是数据挖掘。数据挖掘，又称数据库中的知识发现，在最近几年里已被数据库界所广泛研究，其中关联规则的挖掘是一个重要的问题。 关联规则是发现交易数据库中不同商品（项）之间的联系，这些规则找出顾客购买行为模式，如购买了某一商品对购买其他商品的影响。发现这样的规则可以应用于商品货架设计、货存安排以及根据购买模式对用户进行分类。 例如：研究发现43%购买了雀巢速溶咖啡的顾客都会购买雀巢咖啡伴侣。基于这个规则，在实体超市中，应当把这两种产品放到相近的地方，而在网上超市中，如果顾客购买了雀巢速溶咖啡却没有购买咖啡伴侣，则可以在关联商品栏目中添加相应的推荐。现在很多企业已经认识到详细的原始购买记录的重要性，并且建立了规范的数据仓库，这些都为关联规则挖掘技术的应用奠定了良好的基础。于是关联规则挖掘技术应运而生。 1.2 关联规则挖掘的发展 1.2.1 初级算法的产生 R. Agrawal等人[17]于1993年首先提出了在交易数据库中挖掘关联规则，典型的例子是“多数顾客在购买面包和黄油的同时也会购买牛奶”，找出所有这类规则，对于确定市场策略是很有价值的，例如可用于追加销售、仓储规划，并可根据购买模式对顾客进行划分。 AIS算法是第一个发表的生成事务数据库中所有大项目集的算法。它集中在增强数据库必要的功能以支持决策支持查询。该算法的目标是发现定性规则。该技术的局限性是结论中只有一个项目。 AIS算法要对整个数据库进行多次分析。每次分析都要扫描全部事务。第一次分析计算数据库中单个项目的支持度，并确定哪个是大项目集或者频繁项目集。对每次分析的大项目集进行扩展以生成候选项目集。扫描一个事务之后，可确定上一次分析的大项目集和该事务项目的公共项目集。这些公共项目集被该事务中的其它项目扩展，生成新的候选项目集。大项目集只能是由当前事务中的大项目并且按照词典顺序排列组合而成。为了高效地完成该任务，它采用了一种评估工具和剪枝技术。该评估和剪枝技术通过删除候选集合中不必要的项目集来确定最终的候选集合。然后计算每个候选集合的支持度。支持度大于等于最小支持度阈值的候选集合被选出作为大项目集。这些大项目集继续被扩展以生成下一次分析的候选集合。直到不能发现更多大项目集时该处理过程结束。 STEM算法在其后被提出，其目的是用SQL来处理候选大项目集。与AIS算法类似，SETM算法也要多次分析数据库。 1.2.2 经典算法的出现及改进 随后，研究人员总结得出了关联规则挖掘技术中最为经典的算法Apriori。Apriori是对AIS和SETM算法的改进，并且是第一个可扩展的关联规则挖掘算法。当进行初始数据库扫描时Apriori算法搜索大项目集合，然后用该搜索结果作为后续扫描并发现其它的数据集合的种子。支持度大于给定最小值的规则称为大项目集或者频繁项目集，支持度小于给定最小值规则的称为小项目集。 (责任编辑：qin) |