摘 要:当前关联规则挖掘主要着眼于正关联规则,如AB的关联规则的挖掘,这种单一的只对正关联规则的挖掘方式存在严重的弊端,他掩盖了数据之间存在的隐含负关联规则,进而无法得出一些正关联规则中某些项目间相互制约的负关联关系。在关联规则概念和性质的基础上提出了基于频繁模式树的拓展式的正、负项目的关联规则挖掘算法,通过对数据库的遍历形成前缀链表,不仅挖掘包含所有正项目的关联规则,而且还能够挖掘出所有包含负项目的关联规则,不会造成负关联规则的淹没。并对算法的效率和可行性进行分析,该算法在描述关联规则项目间的相互***程度上比已有的单一挖掘负项目的关联规则算法更具优势。
关键词:关联规则;正关联规则;负关联规则;频繁模式树
中***分类号:TP311文献标识码:B
文章编号:1004-373X(2008)08-090-04オ
Positive and Negative Association Rules Mining Algorithm Based on FPNtree
QU Baida,CHEN Liping
(Communication and Control Engineering College,Southern Yangtze University,Wuxi,214122,China)オ
Abstract:In current,association rules mining mainly focuses on positive association rules,as AB,which has serious disadvantages only to mine positive association rules.It conceals connotative negative association rules among datas,so as not to explain certain items′ restriction relation in positive association rules.Positive and negative association rules mining algorithm based on FPNtree is proposed built on association rules conception and qualities of association rules.Traversing its prefix linked lists which can mine association rules comprising positive items as well as association rules with negative items,not causing negative association rules′ losses.Efficiency and feasibility of algorithm is analysed and has predominance over single algorithm only mining negative association rules in describing indeendence among association rules items.
Keywords:association rules;positive association rules;negative association rules;FPNtree
关联规则是从大量的数据中挖掘出有隐含关系的一种方法,自从文献[1]提出关联规则的问题以后,大量的学者对其进行了深入的研究和探讨。关联规则为:设有事件A和B,正关联规则类似与事件A导致事件B,形如AB这样的表达式,他只能使交易数据库出现的项集发生正面关联,无法发现数据中隐藏的另一种关系:负关联关系,事件A导致事件B不发生,即某数据项集A的出现会减少另一数据项集B的出现机会,甚至使得B不出现。但在实际中对负关联规则的研究却比较少,然而负关联规则依然能带来有价值的规则,这对于决策的作用也是不可忽视的。在商业领域,负关联规则可以帮助决策者牺牲自身小的利益为代价消弱某些大的商业欺骗以换取更大的利益;在医疗领域中,可以根据某些症状的存在与另外一些症状的不存在得到某一诊断结果;企业、市场可以通过综合考虑正、负关联关系,在销售、投资时同时考虑一些有利因素和不利因素,迎接更大的挑战。
尽管在应用中负关联规则非常重要,但由于研究起步晚且难度较大,负关联规则的挖掘还没有能够出现一种像Apriori[2]那样成熟,XinDong Wu在文献\[35\]中正式提出负关联规则的同时还提出一种能同时挖掘正、负关联规则的算法,在挖掘出正频繁项集的基础上考察他们的支持度和兴趣度,当他们不满足阈值要求时再考虑对应的负项集的支持度和兴趣度,如果负项集满足要求,就从中挖掘出包含负项目的关联规则。这种算法思想无法挖掘出所有包含负项目的频繁项集,该算法在生成频繁项目集时会造成丢失。针对以上问题,在包含正、负项目的一般化关联规则进行了比较深入地研究上,提出一种基于频繁模式树混合正、负项目的一般化关联规则挖掘算法,该算法不仅挖掘包含所有正项目的关联规则,而且还能够挖掘出所有包含负项目的关联规则。
1 负关联规则挖掘
1.1 单一正关联规则缺陷
[HTH]例1:[HTSS]假设有5 000个数据集,其中包含事件A和B,同时包含事件A和B记为A∪B,包含A的有3 000项,包含B的有2 500项,minsup=0.2,minconf=0.3,supp(A∪B)=0.25>0.2,conf(AB)=0.42>0.3,得到AB是强关联规则,再考虑ASB,supp(A∪SB)=0.35>0.2,conf(ASB)=0.58>0.3,ASB也是强关联规则,说明由于A的发生B发生的概率反而下降了,因此A和B应该是相互削弱的关系。这与AB相矛盾。由于conf(ASB)>conf(AB),ASB应该更可靠,因此A和B应该是负相关的的关系。
文献[35]提出首先考虑正项集,当正项集无法满足最小支持度和最小信度时再考虑负项集时,然而在例1中按照这种先挖掘正关联规则再挖掘负关联规则的做法将会淹没有效的负关联规则,进而造成某些潜在负关联规则的丢失,本文提出基于频繁模式树的正负关联规则平行挖掘算法,同时考虑正项集和负项集。
1.2 负项目
设任务相关的数据D是数据库事务的集合中有项集A和项集B。形如ASB,SAB,SASB的关联规则称为负关联规则,负的关联规则的支持度和置信度的定义和正关联规则相同,只是分别用SA和SB分别代替了原来的A和B。
首先介绍一个计算支持度计数的定理。
[HTH]定理1 [HTSS] |DB|为事务数据库中事务的总个数,对任意的负项目SA,设他对应的正项目A支持度计数(即在数据库中出现的次数)为A.count,那么SA的支持度为:
ИБSA.count=|DB|-A.count(1)И
证明:因为A.count+SA.count=|DB|;所以SA.count=|DB|-A.count,这是显然成立的。
应用该定理,扫描原始数据库,利用式(1)可以计算出所有负项目的支持度计数,然后将所有支持度计数不小于最小支持度计数minCount的正、负项目合并成一个集合,作为频繁1项集L1;用正整数记录正项目,用负整数记录负项目,并且在频繁1项集中,将各项按照绝对值的升序排列,如果同时含有绝对值相等的一对正、负项目,按照负项目在对应正项目前一位的原则,形成一个有序序列。
2 含负项目的频繁模式树FPN_tree的构造
2.1 基本概念
J.Han等提出一种用频繁模式树FP_Tree产生频繁集的fp_Tree算法,借助与定义对含负项目的频繁模式树(frequent pattern tree with negations,FP_Tree)进行如下的定义:
(1) 他由一个根(值为null)、项目前缀子树(作为根的子女)和一个频繁项头表组成。
(2) 每个项目前缀子树中的节点包括3个域:item,count和first其中item记录节点表示的项目,他可以是正项目也可以是负项目:count表示该项目出现的频度;first用于连接树中同名节点,如果不存在同名节点,则值为“null”。Current表示项目指针,child,parent,Sibling分别表示节点的子,父,和兄结构的指针。
(3) 频繁项头表的表项包括2个域:频繁项目名HEADS:HEADS[i].item=S[i].item; HEADS[i].count=S[i].count; HEADS[i].first=NULL。
2.2 算法思想及其方法描述
前缀链表遍历算法的基本思想是将事务数据库中满足最小支持度的所有项目看成是链表中的各个结点。每条事务看成是从某个结点经若干中间结点到达终结点的路径。从中找出满足最小置信度的路径即为所要发现的正负关联规则。下面给出了频繁模式树FPN_tree构造过程的具体算法:
(1) 第一次遍历事务数据库TID,用正整数记录正项目,用负整数记录负项目,利用式(1)统计各正项目及其负项目的出现频率,并计算所有正负项目的支持度。
(2) 将所有支持度计数不小于最小支持度计数minCount的正、负项目合并成一个集合。
(3) 对上述集合的顺序进行调整,将各项按照绝对值的升序排列,如果同时含有绝对值相等的一对正、负项目,按照负项目在对应正项目前一位的原则,形成一个有序序列,作为频繁1项集S1。
(4) 初始化表头数组HEADS:HEADS[i].item=S[i].iten;HEADS[i].count=S[i].count;HEADS[i].first=NULL;
(5) 将重排后各事务T调用函数insert(PL,T,parent)(首次调用时parent为NULL)插至前缀链表中。
FPNtree中由于引入了负项目,其构造方法与FPTree有所不同。对于数据库中的每个事务T,如果某个正频繁项出现在T中,说明T含有该正频繁项:如果某个负频繁项对应的正项目不出现在T中,说明T中隐含有该负频繁项。构造FPN_tree的主要思想就是将每个事务中包含的正频繁项和隐含的负频繁项按照S1的顺序插入到FPN_tree。
insert(PL,T,parent)
{c=getfirstitem(T);if(c=′’′)return;
If(PL=NULL)
{new(PL);PL>item=c;PL>count=1;PL>child=NULL;PL>parent=parent;
PL>sibling=NUILL:
i=location(c);new(q);q>current=PL;q>next=HEADS[i].first;HEADS[i].first=q;
insert(PL>child,T=delete(T,c),PL)}
else
if(PL>item==c){PL>count++;insert(PL>child,T=delete(T,c),PL);}
if(PL>sibling==NULL)
{new(P);P>item=c;P>count=1;P>child=NULL;P>parent=parent;
p>sibling=PL>sibling;
PL>sibling=P;i=location(c);new(q);q>current=P;
q>next=HEADS[i].first;HEADS[i].first=q;insert(P>child,T=delete(T,c).P);}
else insert(PL>sibling,T,parent);}
2.3 应用举例
假设有表1所示的数据库DB,最小支持度为3,构造含负项目的频繁模式树。
表1 各项目支持度计算[HT6K]
项目abcde-a-b-c-d-e
支持度4311423552[HJ0]
扫描DB,统计各正项的支持度计数,并由式(1)计算负项的支持度计数,结果如表1所示,选出F中支持度大于3的项,选出频繁项集Ll { a:4,-b:3,b:3-c:5,-d:5 ,e:4}。同时计算所有事务的正负频繁项1项集,如表2所示。(各节点以item,name,count形式记录)并依次将各事务中的正、负频繁项插入到FPN_tree中,如最终得到含负项目的频繁模式树如***1所示。
表2 事务数据库1及频繁项[HT6K]
事务TIDTID1TID2TID3TID4TID5TID6
项目a,b,eb,da,ca,eea,b,e[HJ0]
频繁项a,b,-c,-d,eb,-ca,-b,-da,-b,-c,-d,-e-b,-c,-d,ea,b,-c,-d,e
***1 正负频繁模式树
3 从FPN_tree中挖掘包含正、负项目的频繁项集
一般从频繁模式树中挖掘关联规则只需遍历事务数据库2次,第一次形成前缀链表,第二次确定某条事务是否与前缀链表的一条路径重合或者部分重合,从而发现关联规则。第二次遍历事务数据库TID,对重排后的每条事务T,若当前事务T完全或部分重合了前缀链表的某一路径,且满足大于小于minconf约束,就得到关联规则,本文采用在上述频繁模式树的基础上产生一个条件FP树,从而挖掘出所有的正负关联规则。
[HTH]算法2:[HTSS]
算法2建立在算法1所产生的FPNtree上面。他会递归调用自己,并且反复调用算法2产生新的FPtree。
输入:一棵用算法一建立的树Tree;
输出:所有的频繁集。
步骤:
调用FPN_tree (Tree,null)下面是对过程FPgrowth的伪码描述。
ProcedureFPN_tree (Tree,a)
ifTree只有一条路径P
then对P中的节点的每一个组合(记为Е陋В(1)
(1) 产生频繁集Е痢圈陋В并且把他的支持度指定为Е陋е薪诘愕淖钚≈С侄取
else对Tree的头表从表尾到表头的每一个表项(记为a)做(2)~(5)。
(2) 产生频繁集Е=a∪αВ并且支持度为a的支持度。
(3) 建立Е陋У奶跫模式库(conditional pattern base)和Е陋У奶跫树(conditionalFPtree)Tree2
(4)if Tree2!=БhА*
(5)then调用FPgrowth(Tree2,Е陋)。
从***1中的表项b出发,首先可以得到一个频繁集(b:3)。进而得到包含b的所有模式。顺着b表项的nodelink域,找到所有b的路径,,对第一条路径,虽然a出现4次,但他们同b在一起只出2次,所以把他们的计数改为2,得到。第二条路径中,得到,把这2条路径中的b项去掉,就得到b的条件模式库,{( a:2},这是下一步递归的依据。把这个条件模式库看作一个数据库,在上面运用算法一产生一个空的FPtree。
接着考虑-b,先得到(-b:3),顺着他的nodelink得到2条路径,,,但在有序的频繁项中,a与-b在一起只出现2次,所以把他们的计数改为2,得到,第二条路径中,得到,把这2条路径中的-b项去掉,就得到-b的条件模式库{( a:2},运用算法1产生一个空的FPtree。
其次从表项e出发,先可以得到一个频繁集(e:4)。然后,得到包含e的所有模式。顺着e表项的nodeink域,找出所有e的路径,,和,对第一条路径,虽然a出现了4次,b,-c,-d,e各出现2次,但他们同e在一起只出现了2次,所以把他们的计数改为2,得到。第二条路径中,得到,对第3条路径,得到。把这3条路径中的e项去掉,就得到e的条件模式库,{( a:2,b:2,-c:2,-d:2),( a:1,-b:1,-c:1,-d:1),( -b:2,-c:2,-d:2)},这是下一步递归的依据。把这个条件模式库看作一个数据库,在上面运用算法1产生一个新的FPtree,这个新树中有2个节点a:3,-b:3,-c:5,和-d:5,对这个路径中所有的节点组合产生频繁集,得到{(ae:3,e (-b):3,a(-b)e:3,e(-c):4,e(-d):4,e(-c)(-d):4,a(-b)(-c)(-d):3)}.,类似的考虑a:4,和-d:5最终得到两个空的FPtree。
最后考虑-c,先还是得到(-c:5),顺着他的nodelink得到4条路径,,< a:4,-b:2,-c:1,> ,< b:1,-c:1,> 和得到一个新的节点b:3,对这个路径中该节点组合产生频繁集,得到{(b(-c):3}。最终得到条件模式库和条件FP树如表3所示。
表3 条件模式库和FP树
项条件模式库条件FP树
b{(}Бh
-b{} Бh[HJ0]
e{,,}{(ae:3;e(-b):3;a(-b)e:3;e(-c):4;e(-d):4;e(-c)(-d):4;a(-b)(-c)(-d):3)}
aБh Бh
-d{,, }Бh
-c{,,< b:1,-c:1> ,}{(b(-c):3}
4 算法性能分析
FPN_tree算法与现有的挖掘负项目的关联规则的算法相比,在性能上主要有以下优点:
(1) 能够挖掘出所有的负关联规则:目前大多数含负项目的关联规则挖掘算法主要通过考虑频繁正项集的支持度和置信度,当他们不满足要求时,才考虑对应的负项集。但是对于非正频繁项而其对应负项频繁的项集就不能被挖掘出来,因此不能挖掘出所有含负项目的关联规则。FPN_tree算法将所有的正、负频繁项压缩到频繁模式树中,从中挖掘所有长度的频繁项集,所以能挖掘出所有包含正、负项目的关联规则。
(2) 不会使原始数据库增大:算法[6,7]为了挖掘出所有含负项目的关联规则,将所有项目的对应负项目都扩展到原始数据集中,再从中找出频繁项集,这样使得本来就庞大的数据库又扩大了1倍。本文提出的FPN_tree算法只是将频繁的正、负项目压缩的频繁模式树中,采用这种压缩结[LL]构存储负项目以及正项目,有利于使得原始数据库减小。
(3) 很多挖掘含负项目的关联规则挖掘算法都是基于Apriori算法,这需要多次扫描数据库产生大量的候选项集,通过反复扫描数据库模式匹配来检查一个很大的候选项集。FPN_tree算法将频繁项集压缩到一颗频繁模式树,使用模式增长方法挖掘出所有的频繁项集,从而减少了时间和空间的占用,最终产生出所有满足条件的正负关联规则。另外,FPN_tree算法进一步提高了算法的效率,即使会生成矛盾规则,通过规则的致信度的比较,就能够得出满足要求的关联规则。
5 结 语
本文对包含正、负项目的一般化关联规则进行比较深入地研究,提出一种基于频繁模式树的混合正、负项目的关联规则的FPN_tree算法。该算法将事务数据库中出现的正项目和隐含的负项目信息映射到内存中进行处理,平行挖掘正负关联规则。该算法打破了先挖掘正关联规则,其次再挖掘负关联规则这种单一的挖掘模式,从而造成重要负关联规则的丢失。同时该算法在描述关联规则项目间的相互***程度上比已有的单一挖掘负项目的关联规则算法更具优势。
参 考 文 献
[1]Agrawa1 R,Imielinski T,Swami A.Mining Association Rules between Sets of Items in Large Database[A].Proceedings of the 1993 ACMSIGMOD Internatlona1 Conference on Management of Data[C].Washington DC,USA,1993:207216.
[2]Agrawal R,Srikant R.Fast Algorithm for Mining Association rules[A].In:Proceedings of the 20th International Conference on VIDB[C].Santiago,Chile:1994:487499.
[3]Wu X,Zhang C,Zhang S.Mining both Positive and Negative Association Rules\[J\].In:Proc.of ICML,2002:658665.
[4]Savasere A,Omiecinski E,Navathe S.Mining for Strong Negative Associations in a Large Database of Customer Transactions[C].Proceedings of IEEE 14th Intl.Conference on Data Engineering,1998.
[5]WeiGuang Teng,MingJyh Hsieh,MingSyan Chen.On the Mining of Substitution Rules for Statistically Dependent Items[C].Data Mining,ICDM,Proceedings 2002IEEE International Conference,2002.
[6]JeanFranqois Baulicaut,Artur Bykowski,Baptiste Jeud.Towards the Tractable Discovery of Association Rules with Negations [C].FQAS′00,2000:425434.
[7]左万利,刘居红.包含正负属性的关联规则及其挖掘[J].兰州大学学报:自然科学版,1999,33(8):288292.
作者简介 屈百达 男,1956年出生,博士研究生,教授。研究方向为现代控制技术与应用、模式识别与数据处理、运筹与决策。
陈莉平 女,1981年出生,陕西汉中人,江南大学在读硕士研究生。研究方向为数据挖掘、决策支持。
注:本文中所涉及到的***表、注解、公式等内容请以PDF格式阅读原文
转载请注明出处学文网 » 一种基于频繁模式树的正负关联规则挖掘算法