基于频繁模式树的正负项目集挖掘

赵旭俊

(太原科技大学计算机科学与技术学院，太原030024)

关联规则是数据挖掘的一个主要研究方向，它主要是发现大量数据中的项集与项集之间存在的有趣的相互关系。R.Agrawal在1993年第一次提出关联规则的相关概念[1]，在此之后很多研究者对关联规则的相关问题进行了大量的探讨与研究。传统的关联规则算法仅能挖掘正关联规则[2-4]，如“买了鸡蛋的顾客很有可能买火腿”这样的规则，而忽略了“买了鸡蛋的顾客很可能不去买鸭蛋”这样的负规则。但是在竞争与投资分析等重多领域决策制订中，负规则起了非常重要的作用。从规则的的正确性与完整性角度来看，负规则与正规则—起为决策者能做出正确决策提供全面和完整的信息，二者缺一不可。正因为这样，负规则的研究变得越来越重要。

在国外的研究中，Brin S首次提到了关于频繁项目集之间的负相关[5];Savasere A等人提出了一种挖掘负关联规则的思想[6]，其算法是用户需要事先确定层次分类结构，但是这一点很难做到，而且与实际不相符合;Do Trong针对一些渐进挖掘频繁模式的算法，不能扩展到现实世界的数据库的问题，提出一种挖掘频繁渐进闭模式算法[7]，使得挖掘闭频繁项集的时间逐步线性;之后，Zhou Jiayi等人提出了采用图形处理单元(GPU)来执行FPM以达到提高挖掘效率的目的[8]，在该算法中，根据GPU硬件划界的特点，设计一个紧凑的数据结构用来存储整个数据库的数据;屈百达[9]提出采用FPTree提取正负关联规则，但没有考虑用户的兴趣度。……