关联规则挖掘方法探究论文

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

1、关联规则挖掘方法探究论文　　摘要从大量事务记录中发现有意义的关联规则，可以帮助做出许多商务决策，如分类设计、交叉购物，从而提高销售额和利润。本文提出了一种基于链表族数据结构的关联规则挖掘的改进方法，性能明显优于Apriori算法。由于该方法只需访问数据库一次，对于挖掘海量数据其性能尤为明显。　　关键词数据挖掘；关联规则；支持度　　1问题概述　　关联规则的挖掘的形式化描述如下：令I={i1，i2，…im}为项目集(也称为模式)，D为事务(又称交易)数据库，其中每个事务T是I中一组项目集合，即TI，并令其有一个唯一的标识符TID。如果对于I中的子集X有XT，则事务包

2、含项目集X。关联规则就是形如XY的逻辑蕴涵式，其中XI，YI，且X∩Y=。如果D中S%交易包含X∪Y，关联规则XY在D中具有支持s。如果D中c%的包含X的交易也同时包含Y，则关联规则XY在D中可信度c成立。关联规则挖掘一般分为两步：①发现所有的频繁项目集，也就是说这些项目集在数据库中的支持计数必须不小于预先设定的一个阈值，即最小支持度；②关联规则挖掘方法探究论文　　摘要从大量事务记录中发现有意义的关联规则，可以帮助做出许多商务决策，如分类设计、交叉购物，从而提高销售额和利润。本文提出了一种基于链表族数据结构的关联规则挖掘的改进方法，性能明显优于Apriori算法

3、。由于该方法只需访问数据库一次，对于挖掘海量数据其性能尤为明显。　　关键词数据挖掘；关联规则；支持度　　1问题概述　　关联规则的挖掘的形式化描述如下：令I={i1，i2，…im}为项目集(也称为模式)，D为事务(又称交易)数据库，其中每个事务T是I中一组项目集合，即TI，并令其有一个唯一的标识符TID。如果对于I中的子集X有XT，则事务包含项目集X。关联规则就是形如XY的逻辑蕴涵式，其中XI，YI，且X∩Y=。如果D中S%交易包含X∪Y，关联规则XY在D中具有支持s。如果D中c%的包含X的交易也同时包含Y，则关联规则XY在D中可信度c成立。关联规则挖掘一般分为两

4、步：①发现所有的频繁项目集，也就是说这些项目集在数据库中的支持计数必须不小于预先设定的一个阈值，即最小支持度；②由频繁项目集产生强关联规则，也就是说这些强关联规则必须满足最小支持度和最小可信度。其中第2步，一般采用如下方法：对于一个频繁项目集l的每一个非空子集s如果support_count(1)/support_count(s)≥min_conf，(其后support_count(1)表示项目集l在数据库中的支持计数，而min_conf表示最小可信度)则规则输出：“s(1-s)”，该规则也称为强关联规则，第2步相对比较简单，目前大部分研究工作都针对第1步，以改

5、进寻找频繁项目集的效率，本文针对第1步提出了一种称为ALT的改进算法。　　2研究现状　　目前，关联规则挖掘算法中，最有影响的是AGRWAL和SRIKANT于1994年提出的Apriori算法[1]。在许多情况下，Apriori的候选产生-检查方法大幅度压缩了候选项目集的大小，并导致很好的性能，然而，它有两种开销微不足道：①可能产生大量候选项目集；②可能需要重复地扫描数据库，通过模式匹配检查有一个很大的候选集合，但有一种有趣的称为频繁模式增长(Frequent_PatternGrowth)，或简称FP-增长解决了此问题。它采用如下分治策略：将提供频繁项目集的数据库

6、压缩到一棵频繁模式树(FP-树)，并仍保留项目集关联信息；然后将这种压缩后的数据库分成一组条件数据库(一种特殊类型的投影数据库)，每个关联一个频繁项，并分别挖掘每个数据库。对于挖掘长的和短的频繁模式，FP-树方法都是有效的和可伸缩的，并且比Apriori方法快一个数量级。其它关联规则挖掘方法还有参考文献[1]中讨论且给出的AIS算法，参考文献[2]给出的SETM算法及文献[3]给出的IUA算法。　　3ALT算法　　Alt算法只需遍历事务数据库一次，用来生成频繁1—项目集。并由此可以得到频繁2—项目集，频繁3—项目集，……，频繁k项目集。对于频繁i(1≤i≤k)—

7、项目集，采用了一种特殊的数据结构——链表簇来存贮。簇中的每一链表用来表示频繁i—项目集各项目的信息，表头节点(patternData)和表节点(tidData)存储结构如图1所示。　　nextLpatternnewedcountnextP　　(patternData)　　tidnextP　　(tidData)　　图1存储结构　　图1中nextL是一指针，用来链接簇中下一链表；pattern用来存储频繁i—项目集某一项目；newed用来标示项目集pattern域是否生成了新的频繁项目集，同时也作为最大频繁项目集判断条件，初始值为false，若由pattern域产生

8、了新的频繁项目集，其值变