一种改进的关联规则挖掘方法
发布时间：2015-07-11 10:02
摘 要 从大量事务记录中发现有意义的关联规则，可以帮助做出许多商务决策，如分类设计、交叉购物，从而提高销售额和利润。本文提出了一种基于链表族数据结构的关联规则挖掘的改进方法，性能明显优于Apriori算法。由于该方法只需访问数据库一次，对于挖掘海量数据其性能尤为明显。
关键词 数据挖掘；关联规则；支持度
1 问题概述
关联规则的挖掘的形式化描述令I={i1，i2，…im}为项目集(也称为模式)，D为事务(又称交易)数据库，其中每个事务T是I中一组项目集合，即T I，并令其有一个唯一的标识符TID。如果对于I中的子集X有X T，则事务包含项目集X。关联规则就是形如XY的逻辑蕴涵式，其中X I，Y I，且X∩Y= 。如果D中S%交易包含X∪Y，关联规则X Y在D中具有支持s。如果D中c%的包含X的交易也同时包含Y，则关联规则X Y在D中可信度c成立。关联规则挖掘一般分为两步：①发现所有的频繁项目集，也就是说这些项目集在数据库中的支持计数必须不小于预先设定的一个阈值，即最小支持度；②由频繁项目集产生强关联规则，也就是说这些强关联规则必须满足最小支持度和最小可信度。其中第2步，一般采用如下方法：对于一个频繁项目集l的每一个非空子集s如果support_count(1)/ support_count(s)≥min_conf，(其后support_count(1)表示项目集l在数据库中的支持计数，而min_conf表示最小可信度)则规则输出：“s (1-s)”，该规则也称为强关联规则，第2步相对比较简单，目前大部分研究工作都针对第1步，以改进寻找频繁项目集的效率，本文针对第1步提出了一种称为ALT的改进算法。
2 研究现状
目前，关联规则挖掘算法中，最有影响的是AGRWAL和SRIKANT于1994年提出的Apriori算法[1]。在许多情况下，Apriori的候选产生-检查方法大幅度压缩了候选项目集的大小，并导致很好的性能，然而，它有两种开销微不足道：①可能产生大量候选项目集；②可能需要重复地扫描数据库，通过模式匹配检查有一个很大的候选集合，但有一种有趣的称为频繁模式增长(Frequent_Pattern Growth)，或简称FP-增长解决了此问题。它采用如下分治策略：将提供频繁项目集的数据库压缩到一棵频繁模式树(FP-树)，并仍保留项目集关联信息；然后将这种压缩后的数据库分成一组条件数据库(一种特殊类型的投影数据库)，每个关联一个频繁项，并分别挖掘每个数据库。对于挖掘长的和短的频繁模式，FP-树方法都是有效的和可伸缩的，并且比Apriori方法快一个数量级。其它关联规则挖掘方法还有参考文献[1]中讨论且给出的AIS算法，参考文献给出的SETM算法及文献给出的IUA算法。
3 ALT算法
Alt算法只需遍历事务数据库一次，用来生成频繁1—项目集。并由此可以得到频繁2—项目集，频繁3—项目集，……，频繁k项目集。对于频繁i(1≤i≤k)—项目集，采用了一种特殊的数据结构——链表簇来存贮。簇中的每一链表用来表示频繁i—项目集各项目的信息，表头节点(patternData)和表节点(tidData)存储结构如图1所示。
nextL
pattern
newed
count
nextP
(patternData)
tid
nextP
(tidData)
图1 存储结构
图1中nextL是一指针，用来链接簇中下一链表；pattern用来存储频繁i—项目集某一项目；newed用来标示项目集pattern域是否生成了新的频繁项目集，同时也作为最大频繁项目集判断条件，初始值为false，若由pattern域产生了新的频繁项目集，其值变为true，当新的频繁K+1项目集的链表族生成后，若某频繁k项目集对应newed域值仍然为false，则该频繁-k项目集链表对应的pattern域值为一最大频繁项目集；count是该项目集的支持计数；nextP用来链接表节点。对于tidDada，tid是支持项目集pattern的事务标识，保持字典递增有序，nextP用来链接下一个支持项目集pattern节点。
例：有如表1所示事务数据库，最小支持计数为3。
定义：最大频繁项目集——如果某一频繁项目集的所有超集都是非频繁项目集，则该频繁项目集称为最大频繁项目集。
根据定义知：当一个频繁i项目集不能据此生成频繁i＋1项目集，该频繁项目集是一最大频繁项目集。
则其频繁1—项目集的链表簇构造如图2所示。
图2 频繁1-项目集链表簇构造
性质：频繁项目集的所有子集都是频繁的。
ALT算法的原理在于先求取所有的最大频繁项目集，然后依次求取每一个最大频繁项目集的子集，从而得到频繁项目集。
ALT算法求最大频繁项目集
输入：事务数据库(T)，最小支持度(根据最小支持度和项目集的个数，可以得到最小支持计数)；
输出：最大频繁项目集(Answer)。
①计算最小支持计数，最小支持计数(Minsup)＝最小支持度×事务数；
②生成频繁1—项目集L，及其对应的链表族；
③依次处理频繁K—项目集对应的链表，据此得到最大频繁项目集。
（1）初始化pvh，pvn为链表族表头结点扫描指针，pvh指向链表族第一条单链表，pvn指向pvh所指链表的下一条链表。
（2）while(pvn→next≠null)/*链表族中还有待处理链表时*/
{/*依次处理各链表*/
while(pvn≠null){
pvhw=pvh→nextP；pvnw=pvn→nextP/*初始化pvhw为pvh指针所指单链表的工作指针，初始化pvnw为pvn所指单链表的工作指针*/
if(pattern=GeneratePattern(pvh-pattern，pvn-pattern) ≠null){
/*用pvh，pvn所在链表头结点的项目集生成新的项目集pattern，如果pattern符合条件，计算对应事务数是否大于阈值minsup。*/
count=0；
while(pvhw≠null&&pvnw≠null){
if(pvhw→tid==pvnw→tid) count++；
else if(pvhw→tidpvnw→tid) pvhw=pvhw→nextP；
else pvnw=pvnw→nextP；}
if(count=minsup) {
/*对于项目集pattern生成一个新的链表加入到频繁(k+1)项目集链表族中*/
join(ph，pattern，pvh，pvn)；
pvh→newed=true；pvn→newed=true；/*表明这两条链表产生了频繁(k+1)项目集*/}}
pvn=pvn→nextP；}
if(pvh→newed==false)/*表明该频繁k项目集没有生成频繁(k+1)项目集 */
Answer=answer∪pvh→pattern/*pvh所在频繁k项目集加入到最大频繁项目集*/
else {
pvh=pvh→nextP；pvn=pvh→nextP；}
}
（3）由于算法在生成新的项目集时，采用了穷举法，Answer中某个项目集可能是另外一个项目集的真子集，要将其删除。
对于表1中的事务数据库，其产生频繁2—项目集链表族如图3所示，以及最终频繁4—项目集如图4所示。
该事务数据库中，最大频繁项目集为Answer={CP，AFM，CFM，ACFM}，又因为AFM，CFM为ACFM的真子集。将其删除后的Answer={ CP，ACFM }。则该事务数据库的最大频繁项目集为{ CP，ACFM }。
4 结论
为验证该算法，作者在Celeron 2.53GHz，512MB内存的微机上进行了试验，所用数据为mushroom(共8000多条记录)，并与Apriori算法进行了比较，结果如图5所示。
该算法借助特殊数据结构实现了最大频繁项目集的挖掘，从而实现了关联规则的快速发现。由于该算法只需一次访问事务数据库，可以避免频繁访问数据库造成时间上的巨大浪费。对于数量级别越高的数据库其优越性表现尤为明显。
参考文献
[1] AGRAWAL R，IMIELINSKI T，SWAMIA. Mining association rules between sets of items in large database[A].Proceedings of ACM SIGOD Conference on Management of Data[C].Washington DC，1993，207~216
HOUTSMA M，SWAMI A. Set-oriented mining of association rules[R].Research Report Jose： IBM Almaden Research Center，1993
冯玉才，冯剑琳.关联规则的增量式更新算法[J].软件学报，1998，9(1)： 301~306
STRINANT R，AGRAWAL R. Mining quantitative association rules in large relational tables[A]. Proceedings of ACM SIGMOD Conference on Management of Data (SIGMOD’96)[C]. Montreal，1996.1-12