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

赵旭俊

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

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

在国外的研究中，Brin S首次提到了关于频繁项目集之间的负相关[5];Savasere A等人提出了一种挖掘负关联规则的思想[6]，其算法是用户需要事先确定层次分类结构，但是这一点很难做到，而且与实际不相符合;Do Trong针对一些渐进挖掘频繁模式的算法，不能扩展到现实世界的数据库的问题，提出一种挖掘频繁渐进闭模式算法[7]，使得挖掘闭频繁项集的时间逐步线性;之后，Zhou Jiayi等人提出了采用图形处理单元(GPU)来执行FPM以达到提高挖掘效率的目的[8]，在该算法中，根据GPU硬件划界的特点，设计一个紧凑的数据结构用来存储整个数据库的数据;屈百达[9]提出采用FPTree提取正负关联规则，但没有考虑用户的兴趣度。本文在充分考虑用户感兴趣模式的基础上，采用一阶谓词逻辑作为用户感兴趣的背景知识表示技术，提出了一种基于背景知识的包含正负项目集的频繁模式树，给出了针对正负项目集的约束频繁模式树的构造算法NCFP-Construct，，该算法不但可以发现所有的正规则而且能找到所有的负规则，在整个挖掘过程中只需扫描两次数据库，故算法是有效和可行的。

1 相关概念

定义1 对于已知的项集M、N，其中M∩N=Ø，能生成8种形式的关联规则:1、M⇒N;2、﹁M=＞N;3、M⇒﹁N;4、﹁M= ＞﹁N;5、N= ＞M;6、N=＞﹁M;7、﹁N= ＞M;8、﹁N= ＞﹁M.其中5～8同1～4相对应，将1～4中规则前后件互换就能得到5～8.因此，在后面叙述中，只考虑关联规则的前4种形式，其中把1称为正关联规则，相应地2～4称为负关联规则。负关联规则也有支持度和置信度，其定义同正关联规则相同，只是在描述上分别用﹁M和﹁N分别代替了原来的M和N.

定义2 设L={l1，l2，…，lm}是项目的集合，而集合中元素称为项或项目，设D为交易数据库，则|D|表示数据库中的记录数，事务表示为T={t1，t2，…，tn}，而且每个事务由唯一的标识TID进行描述。

定义3 若M⊂L，N⊂L，且M∩N=Ø，记sup(M)表示D中含M的事务数，则M的支持度为|M|/|D|，同理，M∪N的支持度为|M∪N|/|D|，记为sup(M∪N)。

定义4 规则M⇒N在交易数据库D中的置信度定义为conf(M⇒N)=|M∪N|/|M|，即同时包含M和N的记录数与包含M的记录数之比，由此很容易推出不包含某项集M的支持度计算方法为:

1、sup(﹁M)=1-sup(M)

2、sup(M∪﹁N)=sup(M)-sup(M∪N)

3、sup(﹁M∪N)=sup(N)-sup(M∪N)

4、sup(﹁M∪ ﹁N)=1-sup(N)-sup(M)+sup(M∪N)

引理1|D|为交易数据库中记录的总个数，对任意的负项目﹁M，设其对应的正项目M支持度计数(即在数据库中出现的次数)为A.count，那么﹁A的支持度计数为:﹁A.count=|D|-A.count.

应用该引理，扫描原始数据库，可以计算出所有正负项目的支持度计数，然后利用定义4计算其支持度，将所有支持度不小于最小支持度阈值的正、负项目合并成一个集合，作为频繁l-项集L，用正整数记录正项目，用负整数记录负项目，并且在频繁1-项集中，将各项按照绝对值的降序排列，如果同时含有绝对值相等的一对正、负项目，按照负项目在对应正项目前一位的原则，形成一个有序序列。

2 含负项目的约束频繁模式树构造

2.1 一阶谓词逻辑与背景知识

谓词是表示一个个体的性质或若干个个体之间的关系的词。谓词逻辑是一种形式语言系统，它采用逻辑方法进行推理，可以用来表示属性之间的存在关系。而关联规则是描述事务属性之间的隐含关系，因此采用一阶谓词逻辑能够恰当描述指导关联规则挖掘所需背景知识。此过程是将用户感兴趣模式通过一阶谓词逻辑进行描述，因此首先需要定义谓词，通过谓词描述背景知识，并明确指出各个谓词的含义，然后将谓词通过逻辑运算符号连接起来，生成确定的谓词公式，以此表达完整的关联规则挖掘所需的背景知识。设定如下几个谓词:UserInteresting(g(r))、ItemSupport(g(r)，k)、UserInterested(g(r))、UserP(g(r))和 UserQ(g(r)).其中r是数据库中的某一关系表的表名，g是确定的函词，用其表示关系表r到其属性的映射，因此g(r)表示的是属性集合。谓词 UserInteresting(g(r))表示用户感兴趣的模式一定包含g(r)项目子集;谓词ItemSupport(g(r)，k)表示是g(r)项目集的支持度一定大于等于阈值k;谓词UserInterested(g(r))表示在前一次关联规则挖掘中用户感兴趣的模式包含g(r);谓词 UserP(g(r))和UserQ(g(r))是不同用户根据需要定义自己的需求，因此含义也由用户自己进行确定。

定义5 设r是事务数据库中的关系表的表名，g表示映射，k是用户确定的最小支持度(0≤k≤1)，则由上述谓词组成的谓词公式可表示背景知识G.

(1)UserInteresting(g(r))

(2)ItemSupport(g(r)，k)= ＞UserInteresting(g(r))

(3)UserInterested(g(r))=＞UserInteresting(g(r))

(4)UserP(g(r))∧ UserQ(g(r))=＞UserInteresting(g(r))

在定义5中，UserInteresting(g(r))表示用户直接给出感兴趣的项目集;ItemSupport(g(r)，k)→UserInteresting(g(r))表示在上次关联规则挖掘中，如果项目集g(r)的支持度大于等于阈值k，那么在下次关联规则挖掘中g(r)将成为用户感兴趣的模式集;UserInterested(g(r))=＞UserInteresting(g(r))表示如果用户在上次关联规则挖掘中对项目集g(r)感兴趣，那么在下次挖掘中也将对其感兴趣;谓词公式UserP(g(r))∧UserQ(g(r))=＞UserInteresting(g(r))中UserP和UserQ是不同用户根据需要定义自己的需求，具体含义也由用户确定，UserP和UserQ可以是空式，也可以是合取式。

定义6 设事务数据库用D表示、用户感兴趣的背景知识用G表示，如果从数据库D中挖掘的模式P符合背景知识G的约束，将其记为G(P)=True，反之，如果从数据库D中挖掘的模式P不符合背景知识G的约束，我们将其记为G(P)=False.

定义7 设事务数据库用D表示、用户输入的最小支持度阈值用σmin表示，用户感兴趣的背景知识用G表示，如果频繁模式L满足G(L)=True，则称L为约束频繁模式。

2.2 约束频繁模式树(CFP树)及构造

J.Han等提出一种用频繁模式树FP-Tree提取频繁项目集的算法，借助其频繁模式树的定义对约束频繁模式树进行如下的定义:

定义8 设用户感兴趣的背景知识用G表示，对于任意一颗频繁模式树，如果从根结点到所有叶子结点的路径中，所提取的所有频繁模式P，都能满足G(P)=True，则称此频繁模式树为约束频繁模式树CFP-Tree.

定义9 在定义8的基础上，能够得到含负项目的约束频繁模式树的定义，即可定义为满足下面4个条件的树型结构:①包含一个值为“NULL”的根结点(可用root描述)，root的孩子是项前缀子树集合，该项前缀子树还包含频繁项头表。②项目前缀子树中的结点都包含3个域:ItemName，ItemCount，ItemNodeLink，其中，ItemName描述项目的名称，既可以描述正项目也可以描述负项目;ItemCount描述包含该结点的事务计数，即支持度计数;ItemNodeLink是一指针，指向约束频繁模式树中具有相同的项目名称的的下一个结点，当下一个结点不存在时，ItemNodeLink为NULL.③频繁项目头表中的每一个结点包含两个域:FreqName，FreqLink，其中FreqLink为指向约束频繁模式树中具有相同名称的首结点指针。④从根结点到所有叶子结点的路径中，所提取的所有频繁模式P，都能满足G(P)=True.

2.3 算法思想及其方法描述

对于确定的事务数据库D，最小支持度为σmin、一阶谓词逻辑描述的背景模式为G，由于任意的符合约束的频繁模式P，满足G(P)=True，所以并非数据库D中所有事务都符合要求，只有满足背景知识G的事务来构造FP树，才能包含符合约束条件的约束频繁模式，因此按照下述步骤，通过两次扫描事务数据库来实现约束频繁模式树的构造:

1)第一次扫描数据库，正项目采用正整数记录，负项目采用负整数记录，利用定义4中给出的公式统计各正项目及其负项目的出现频率，并计算所有正负项目的支持度。将所有满足最小支持度阈值条件的正、负项目合并成一个集合;

2)对上述集合的顺序进行调整，将各项按照支持度降序排序，如果某对正、负项目的支持度恰好相等，那么按照负项目在前，其对应正项目在后的原则进行排序，生成一个有序序列，这就是正负项目挖掘中的频繁l项集，用L表示;

3)创建频繁模式树的根结点，以“NULL”表示;

4)对于事务数据库D中任意事务T，判断T是否满足背景知识约束，即如果T中不包含定义5中描述的模式，则读取下一条记录，否则，执行5);

5)将事务T中频繁项按频繁1项集L中的次序进行排序，结果为T'，并按如下步骤来更新约束频繁模式树:

(1)在约束频繁模式树中，寻找与T'的最长前缀匹配的路径;

(2)对于该匹配路径上的结点，其计数增加1;

(3)确定该路径中最后一个匹配的结点，以此结点为为根结点，在约束频繁模式树中依次创建孩子结点，其值依次为T'中剩余频繁项，其计数为1.

约束频繁模式树(CFP-Tree)中由于引入了负项目，其构造方法与传统约束频繁模式树有所不同。对于事务数据库D中的任意事务T，如果T中包括某个正频繁项，说明T含有该正频繁项;如果T中不包括某个负频繁项所对应的正项目，说明T中隐性包括此负频繁项。构造约束频繁模式树的主要思想就是将每个事务中包含的正频繁项和隐含的负频繁项，按照第一次扫描数据库形成的频繁1项集L中的顺序插入到CFP-Tree.通过上述分析，CFP-Tree构造算法NCFP-Construct，可描述如下:

输入:一个事务数据库D、最小支持度阈值σmin和背景知识G(g1，g2，…gk).

输出:CFP-Tree

步骤:

1)第一次扫描事务数据库，正项目采用正整数记录，负项目采用负整数记录，利用引理1统计各正项目及其负项目的出现频率，并利用定义4中公式计算所有正负项目的支持度。

2)将所有满足最小支持度阈值条件的正、负项目合并成一个集合F.

3)如果某对正、负项目的支持度恰好相等，那么按照负项目在前，其对应正项目在后的原则进行排序，生成一个有序序列，这就是正负项目挖掘中的频繁1项集，用L表示;

4)计算背景知识G(g1，g2，…gk)的支持度Si.

5)每个事务按如下程序执行。

在上述算法中，创建约束频繁模式树的根结点，记为T，并且标记为“NULL”，然后对D中的每个交易Trans做如下操作:根据L中的顺序，选出并排序Trans中的频繁项，把Trans中排好序的频繁项列表记为[p|P]，其中p是第一个元素，P是列表的剩余部分，最后调用 insert_tree([p|P]，T).

函数insert_tree([p|P]，T)的运行如下:如果T有一个子结点N，其项目值恰好等于p，则将N的计数域值增加1;否则创建一个新结点N，使它的count为1，父结点为T，并将node_link和那些具有相同item_name的域串起来.如果P非空，则递归调用 insert_tree(P，N).

3 实验分析

为了进一步验证算法的有效性、可行性以及针对性，用 PentiumIV-2.0G CPU，512M 内存，Windows XP操作系统，DBMS为ORACLE 9i，用VC++实现了NCFP-Construct算法和频繁模式挖掘算法FP-growth，并同时实现了 FPN_tree 算法[9]，对其效率做了比较，结果如图1和图2所示。采用随机生成数据作为实验数据，其属性数量设定为100，|D|表示事物数据记录的数目;|T|表示事物数据记录的平均长度;|I|表示最大频繁项目集的平均长度;|L|表示最大频繁项目集的数目;N表示事物项目集的个数。在实验中，N=1 000，|L|=2 000，|D1|=10 000，|D2|=30 000，|T|=20，|I|=10，实验结果如图1、图 2所示。从图1、2可看出:NCFP-Construct算法与FPN_tree算法相比，效率有了近50%的提高，说明NCFP-Construct是可行的、有效的。

图1 |D1|=10 000的实验结果Fig.1 The experimental results including 10 000 records

图2 |D2|=30 000的实验结果Fig.2 The experimental results including 30 000 records

文献[9]中虽然也采用FP-Tree来构造包含正负项目集的频繁模式树，但由于没有考虑用户的兴趣度，导致生成的FP-Tree非常庞大，效率太低，而且从其树上提取的关联规则没有针对性。本文算法在充分考虑用户感兴趣模式的基础上，弥补了文献[9]算法的不足，不仅提高了近50%的效率，而且仅生成用户感兴趣模式，提高了针对性。

4 结束语

对包含正、负项目的一般化关联规则进行比较深入地研究，在充分考虑用户感兴趣模式的基础上，提出了一种采用约束频繁模式树的正负关联规则挖掘方法，给出了包含负项目集的约束频繁模式树的构造算法NCFP-Construct，从而提高了关联规则挖掘结果的针对性，实验结果显示该方法是有效的。

[1]AGRAWAL R，IMIELINSKI T，SWAMI A.Mining association rules between sets of items in large databases[C]//Proc of 1th Int Conf on Management of Data，Washington DC，USA，1993:207-216.

[2]刘勇，李建中，高宏.从图数据库中挖掘频繁跳跃模式[J].软件学报，2010，21(10):2477-2493.

[3]弓秀莲，赵旭俊，张继福.基于FP树的特异关联规则挖掘算法研究[J].太原科技大学学报，2007，28(6):428-432.

[4]马洋.恒星光谱数据分类规则挖掘系统研究[J].太原科技大学学报，2011，32(4):269-272.

[5]BRIN S，MOTWANI R，SILVERSTEIN C.Beyond market:Generalizing association rules to correlations[C]//Processing of the ACM SIGMOD Conference 1997.New York:ACM Press，1997:265-276.

[6]SAVASERE A，OMIECINSKI E，NAVATHE S.Mining for Strong Negative Rules for Statistically Dependent Items[C]//Proc of ICDM’02，Maebashi，2002:442-449.

[7]DO TRONG DINH THAC，LAURENT ANNE，TERMIER ALEXANDRE.PGLCM:Efficient parallel mining of closed frequent gradual itemsets[C]//IEEE International Conference on Data Mining，Sydney，Australia，2010:138-147.

[8]ZHOU JIAYI，YU KUNMING，WU BINCHANG.Parallel frequent patters mining algorithm on GPU[C]//Conference Proceedings-IEEE International Conference on Systems，Man and Cybernetics.2010:435-440.

[9]屈百达，陈莉平.一种基于频繁模式树的正负关联规则挖掘算法[J].现代电子技术，2008，271(8):90-94.