高效生成频繁模式树的算法研究

　　摘要：频繁模式树的提出，提高了挖掘效率，是关联规则挖掘史上的一个历程碑。频繁模式增长算法在创建频繁模式树时，重复比较新结点与已经插入结点，以便确定新插入点的位置，造成了性能上的浪费。针对此问题，本文提出一种解决方法，即在创建FP-tree之前，将每一事务转换成相应的实数，以便在通过项头表寻找结点链时可以快速定位。然后再对这些由实数组成的对应数据库进行排序，得到一个新的数据库。在新的数据库基础上快速生成频繁模式树，这样就避免了大量的重复的工作，提高了创建FP-tree的效率。理论分析表明，修改后的算法的性能明显优于原算法。
　　关键词：数据挖掘；频繁项集挖掘；频繁模式增长算法；有序频繁模式增长算法；
　　中图分类号：TP311.1
　　1引言
　　频繁模式的挖掘[1]在关联规则[2]、相关分析、序列模式、因果律、显露模式等许多重要数据挖掘任务中承担着重要的角色。长期以来，挖掘频繁模式主要采用Apriori[3,4]算法及其改进形式。然而Apriori及其改进算法仍然会产生大量候选项集，并需要反复频繁的扫描数据库，这严重影响了算法的效率。J.Han等人提出了新的结构FP-tree和相应的模式增长算法FP-growth[5]，该算法采用分治的策略，无须产生候选项集，FP-growth算法是一种本质上不同于Apriori的挖掘频繁项集的有效算法。但它的大部分时间都花费在FP-tree及条件FP-tree的构造与遍历上，如果能提高这方面的效率将对提高算法的效率有较大的帮助。基于这样的分析，我们提出了对FP-growth算法的改进措施。在原数据库D的基础上建立新的数据库D*。以便创建有序FP-tree，使得树中的每一个结点的子结点按照项的序号从小到大排列。这样，加入新结点时需要比较的结点数大大降低了，从而缩短构造一棵树的时间。此外，还采取了其它的优化措施，如将item-no按照item-name的次序排成一个列表，在将item-name转换为item-no时，通过列表可直接找到对应的项。
　　2问题描述
　　2．1频繁项集[6]
　　设I={i1,i2,…,in}是n个不同项目（Item）的集合，如果对一个集合，且k=|X|,则X称为K项集，或者简单地称为一个项集（Itemset）。记D为事务T的集合，。对于给定事务数据库D，定义X的支持度为D中包含X的事务个数，记为sup(X)。用户可自定义一个小于|D|的最小支持度记为s.
　　定义1频繁项集：给定事务数据库D和支持度s，对于项集，若sup(X)≥s,则称X为D中的频繁项集。
　　性质1一个长度为k的项集不是频繁的，则它的长度为（k+1）的超模式不可能是频繁的。
　　2.2FP-tree和FP-growth算法
　　频繁模式树即FP-tree中，每个结点由3个域组成：项名item、结点支持度计数sup-count及结点链node-link。为方便遍历，创建一个项头表Headertable，它由2个域组成:项名item和结点链头headofnode-link，其中结点链头指向FP-tree中与之名称相同的第一结点。
　　FP-growth算法主要是FP-tree的构造过程，需要扫描两次数据库：
　　(1)第一次扫描数据库D，产生所有频繁1-项集及其支持度计数，按其支持度降序排列插人到项头表。
　　(2)创建FP-treeT的根结点，用“null”标记，对D中每个事务做如下处理:①按项头表中的次序排列第一次扫描得到的频繁项集，设排列后的结果为[p|P]，其中p是第1个项目，而p是剩余项目的列表;②调用insert_tree[p|P]，如果T有子女N使得N.item=p，则N的计数增加1，否则创建一个新结点N，将其名称item设置为p，将sup_count设置为1，链接到它的父结点，并通过结点链node-link链接到具有相同项名的结点，如果P非空，递归调用insert_tree([P|N])。
　　3有序频繁模式树
　　3．1有序FP-tree的定义与构造
　　有序FP-tree是在传统FP-tree的基础上通过改进获得的。
　　定义2有序频繁模式树(OFP-tree)是一种树结构，定义如下：
　　(1)它由以下三个部分组成：一个标记为“null"的树根，一棵以项前缀子树集作为树根的孩子所组成的树，以及一个频繁项头表。
　　(2)项前缀子树中的每个结点由6个域组成:item-no,count,parent-link,child-link,last-link和node-link。其中，item-no记录该结点所代表的项在项头表中的序号，count记录从根结点到该结点的路径上所代表的项集在所有数据库事务中出现的次数，parent-link是指向父结点的指针，child-link是指向第一个子结点的指针，last-link是指向最后插入的孩子结点，而node-link则连接到FP-tree中与该结点具有相同item-no的下一个结点，如果没有下一结点，则为null。具有相同父结点的结点按照item-no从小到大的次序排列。
　　(3)频繁项头表中的每个项由两个域组成：item-no(结点所代表的项名)和node-link的头指针(指向FP-tree中具有item-name对应item-no的第一个结点)。项头表中的项按照其出现频度的降序排列。
　　OFP-tree与FP-tree不同之处主要在于：(1)FP-tree中的结点保存的是item-name，而OFP-tree中的结点保存的是item-no，在输出模式时才将item-no换成item-name。(2)FP-tree中的结点是无序的，而OFP-tree中的结点是按照item-no从小到大的次序排列的。
　　3．2算法实例
　　例1设事务数据库中的事务如表1所示，最小支持度阈值为3。
　　
　　表1一个事务数据库示例

　　表2通过排序后得到的新数据库D*
　　
　　
　　图1事务数据库D*对应的OFP树
　　
　　算法1：OFP-tree的建立
　　输入：一个事务数据库D及最小支持度阈值minsup
　　输出：建立后的排序频繁模式树OFP-tree
　　方法：执行以下步骤
　　（1）扫描事务数据库D一遍，获得频繁1-项集及其支持度信息，将频繁1-项集按照支持度降序排列，记为L。
　　（2）第二遍扫描D，将trans中的每个频繁项按L中顺序排列，并将项名用L中的序号替换，不存在的项用0来补位。
　　（3）将替换好的所有事务按实数大小排序，得到一个新的数据库D*。
　　（4）创建SFP-tree的根结点T，记为“null”，对于D*中的每个trans执行如下操作：
　　○1设排列后的结果为［p|P］,其中p是第一个项目,而P是剩余项目列表;
　　○2调用insert_tree([p|P],T),如果T没有子结点，则N.item-no=p,N.count=1,N的父结点链指向T;否则,将p与T的最右子结点进行比较，如果N.item-no=p，则N的计数加1，否则，创建一个新结点N，使N.item-no=p,N.count=1，将T的last-link指向N，N的父结点链指向T。
　　○3如果新加入了结点N，则将N插入到项头表中第p个元素的相同结点链表的末尾.
　　○4如果P非空，则递归调用insert-tree(P,N)。
　　需要指出的是：在OFP-tree中，由于相同父结点的子结点是有序的，在加入新结点时只需要比较最右子结点的item-no，而FP-tree则需要比较所有结点。所以，OFP-tree加入一个新结点的时间大大降低。而且，item-no就是该项在项头表中的位置，不需要进行查找。
　　算法2：OFP-growth
　　输入：建成的OFP-tree及minsup
　　输出：调用OFP-growth(OFP-tree,null)
　　方法：调用OFP-growth(OFP-tree,null)
　　ProcedureOPF-growth(T,a)
　　{
　　(1) if树T包含单一路径P
　　(2) then对路径P中的任一项集组合β，输出项集βα(转换为item-name)，项集支持度取β中结点的最小支持度
　　(3) else{
　　(4) for(i=n;i>=0;i--)//n为项头表的长度减1
　　(5) {β=且sup(β)=sup(i);
　　(6) 构造β的条件FP-treeTβ;
　　(7) ifTβ≠φthencallSFP-growth(Tβ,β);
　　(8) }}}
　　从以上算法可以看出，在插入一个新的结点时，不需要再从项头表的第一项开始比较，将相同项名的结点链相连，只需要根据序号就可以很快的找到所要链接的结点位置。同时在新数据库的基础上，可以不必逐个比较该父结点的各子结点是否与要插入的结点相同，只需比较最后插入的结点即可。这样就大大减少了频繁模式树的创建时间。在这两方面，该算法较原算法有了一定的提高。
　　4结论
　　通过对频繁模式增长算法的详细了解，可以看出该算法具有以往算法所不具备的优点，但是它也同样存在一些缺陷。比如在FP－growth算法中，绝大部分时间主要是消耗在FP－tree及条件FP－tree的构造与遍历上，虽然本文对创建树的算法进行了一些改进，但是仍然存在很大的改进空间。
　　参考文献
　　[1]刘喜苹.基于Fp-growth算法的关联规则挖掘算法研究与应用[D].湖南:湖南大学,2006:1
　　[3]安颖.基于关联规则的数据挖掘算法研究[D].北京:北京工业大学,2009:18
　　[4]范明,孟小峰.数据挖掘概念与技术[M].北京:机械工业出版社,2007.3:155~156.
　　[6]胡可云,田凤占,黄厚宽.数据挖掘理论与应用[M].北京:清华大学出版社；北京交通大学出版社,2008.4:115~120.