基于用户兴趣度的关联规则挖掘算法

更新时间:2023-12-19 作者:用户投稿原创标记本站原创 点赞:4465 浏览:12325

摘 要 :经典Apriori关联规则挖掘算法需要多次扫描整个事务数据库,产生庞大的候选集.文章提出基于Apriori的IOIR算法,算法根据用户的兴趣,有选择的挖掘数据库,并通过对每个候选集进行支持数排序,从而减少扫描的数据量和扫描的时间.

关 键 词 :关联规则;数据挖掘;IOIR算法;兴趣度

中图分类号:TP311.13 文献标识码:A 文章编号:1007-9599 (2012) 16-0000-01

1.前言

关联规则挖掘是数据挖掘技术的一个重要分支,帮助发现大量数据库中项集之间的关联关系,以获得有用的帮助用户决策的信息.经典Apriori关联规则挖掘算法需要多次扫描整个事务数据库,产生庞大的候选集,并且需要很大的I/O负载,生成的关联规则只有部分符合用户的需求.目前有了很多针对不同条件的改进算法,主要是从减少扫描次数、减少候选项集等方面优化.FP-tree算法只进行2次数据库扫描,不使用候选集,直接压缩数据库成一个频繁模式树,最后通过这棵树生成关联规则,内存开销大,而且只能用于挖掘单维的布尔关联规则.频繁闭合模式(frequent closed pattern)的相关算法由于每次扫描都要生成闭合,且要对闭合进行计数,生成子集,同样存在占用较大内存空间,影响结果生成时间.论文提出IOIR算法(Interesting Order Items Rule),提取用户感兴趣的事务进行关联规则挖掘,减少了频繁项集的数量及空间开销.


2.IOIR算法

2.1 优化Apriori算法设计思路

在关联规则的实际数据挖掘中,事务数据库规模通常较大,扫描事务数据库和产生频繁项目集是非常耗时的.因此尽可能剔除无用的候选集和减少事务数据库扫描频率是提高算法效率的关键.

由事务数据库中的事务是项目的集合且集合具有无序性,可得在同一事务中,是不必考虑项目之间的顺序的.如事务T的项目集合{A,B,C,D,E}与{E,A,B,D,C}是相同的.

在Apriori算法执行中对每次获取的K-项候选集进行排序,可用隔板的方法把不满足最小支持度的项集隔去,剩下的就都是满足条件的项集了.

2.2 优化算法的设计步骤

先根据用户的兴趣,选择出用户感兴趣的数,并在生成K-1项集过程中,对K-1项集进行按照支持数的值从小到大排序,那么在LK-1连接生成候选集CK,CK也进行按照支持数的值从小到大排序并采用支持度剪枝后,将使得支持度小的频繁K-项集排在前面,依此类推,这样与Apriori算法相比较就提升了速度.

3.实验结果分析

为了验证IOIR算法的性能,用JA分别实现Apriori算法和IOIR算法.硬件设备配置相同.用两种方式比较:

事务数据库中包含事务的个数分别100,500,1000,1500,2000,2500,5000,10000,20000,项目数量为30.表1给出在最小支持度为40%的运行时间对比.

由运行结果可以看出,在事务逐渐增多时,IOIR的优势较明显;在不同的支持度下也有一定的优势.

相关论文范文