刘冲 陈晓辉 宋小小

桂林理工大学信息科学与工程学院 广西 541004

0 引言

关联规则是一个重要的知识发现(KDD)研究课题，它反映了大量数据中项目集之间有趣的关联或相关联系，经过十多年的发展，目前已经形成了一些较为有影响的挖掘算法，其中以Apriori算法，FP-树算法为代表。Apriori算法通过产生候选频繁项集来挖掘关联规则，人们对其改进做了许多研究工作。2000年左右，J.Han等人提出了一种不产生候选项集的挖掘方法，即FP-树算法。但是，该算法也有一些不足。

传统的FP-树算法主要缺点：(1)建树和挖掘过程都需要占用大量的内存。当数据库很大或者数据库中的频繁1-项集的数目很大时，运行速度将大为降低；更有甚者，可能由于无法构造基于内存的FP树，该算法将不能有效地工作。(2)挖掘大型数据库时，运算速度慢。本文在深入研究 FP-树算法的基础上，提出了一种改进的 FP树算法，新颖的分解方法分解数据库，然后对分解后得到的各个数据库子集进行约束频繁项挖掘来挖掘关联规则的新算法。

1 基本概念

设I={il,i2,……,in}是项的集合，D是数据库事务的集合，其中每一个事务T是项的集合，使得T⊆I。每一个事务有一个标识符，称作 TID。设A是一个项集，事务 T包含A当且仅当A⊆T。关联规则是形如A⇒B的蕴含式，A⊆I，B⊆I，并且A∩B=空集。规则A⇒B在事务集D中成立，具有支持度s，其中s是D中事物包含A∪B的百分比。它是概率P(A∪B)规则A⇒B在事物集D中具有置信度c，如果D中包含A的事务同时也包含B的百分比c。这是条件概率P(B|A)。既是：

s= support(A⇒B)= P(A∪B);

c= confidence(A⇒B)= P(B|A)

同时满足最小支持度阈值(min＿sup)和最小置信度阈值(min＿conf)的规则称为强规则。