论文部分内容阅读
摘要：关联规则挖掘向来是数据挖掘的一个重要领域，挖掘算法也层出不穷。本文在深入分析了FP树特性的基础上，改进了FP树构造过程，通过一次扫描事务数据库生成FP树。缩短了关联规则挖掘时间，提高了效率，实验验证了其有效性。
关键词：数据挖掘；关联规则；FP树
中图分类号：TP311 文献标识码：A文章编号：1009-3044(2007)18-31707-01
An Improved FP-Tree Algorithm for Mining Association Rules
LI Tao
(Nanjing Information Engineering University,Nanjing 210044,China)
Abstract:This paper introduces an improved FP-Tree algorithm for mining association rules. The new algorithm accelerates the process of constructing FP-Tree and generates the nodes by scanning the database only once. The presented algorithm can efficiently improve the performance of association rules mining.
Key words:Data Mining; Association Rules; FP-Tree
1 引言
关联规则挖掘是从大量数据中提取项集之间的关联和相互关系，由R.Agrawal等人在1993年首先提出[1]，经过十多年的发展，目前已经形成了一些较为有影响的挖掘算法[2~4]，以Apriori算法，FP树算法为代表。其中，Apriori算法通过产生候选频繁项集来挖掘关联规则，人们对其改进做了许多研究工作[5]。2004年左右，J.Han等人提出了一种不产生候选项集的挖掘方法，即FP树算法[3]。本文在深入研究FP树算法的基础上，提出了一种改进的FP树算法，它只需要对数据库进行一次扫描即可构造出FP树，从而缩短了关联规则挖掘时间，提高了效率。
2 相关概念描述
2.1 关联规则挖掘的相关概念
关联规则挖掘的数据集记为TDB（称为事务数据库），T={t1,t2,…,tk,…,tn} ，tk={i1,…,ij,L,ip} ，tk(k=1,2,…,n)称为事务，ij(j=1,2,…,p)称为项目。设I={i1,i2,…,im}是TDB中全体项目组成的集合，l的任何子集X称为TDB中的项目集。设tk和X分别为TDB中的事务和项目集，如果X?哿tk，称事务tk包含项目集。
数据集TDB中包含项目集X的事务数量称为项目集X的支持数，记为σx。项目集X的支持度记为support(X)。support(X)=σx/|TDB|，其中|TDB|是数据集TDB的事务数。
若X、Y为项目集，且X|Y=?椎，蕴涵式X=>Y称为关联规则。项目集X∪Y的支持度称为关联规则X=>Y的支持度，记作：support(X=>Y),support(X=>Y)=support(X∪Y)。
关联规则X=>Y的置信度记作：confidence(X=>Y)。
confidence(X=>Y)=support(X∪Y)/support(X)
2.2 FP树挖掘的相关概念
一棵频繁模式树[3](简称为FP树)是一棵定义如下的树结构：(1)它由一棵以标记为 的节点为根节点和一系列代表频繁项的节点构成的树，以及一个频繁项头表组成。(2)除根节点外，树中的每个节点包含三个域：项名(item_name)，计数(count)，以及节点链(node_link)。其中，项名是指该节点所代表的项；计数用于记录经过此节点的事务的数目；节点链指向具有相同项名的下一个节点，当没有下一个节点时，其指针为空。(3)在频繁项头表中的每一个条目由三个域组成，即项名(item_name)，支持度计数(count)和节点链头(head of node_link)，其中节点链头是一个指向FP树中具有相同项名的节点链中第一个节点的指针。
根据文献[3]中的FP树的构造过程，FP树显然具有下列性质。(1)FP树中的各非根节点所代表的项在按支持度排序的频繁1-项集中必定位于其后裔节点所代表的项之前。(2)若FP树中从根节点到某节点的分支上所有节点所代表的项（根节点代表空项）组成的项集为A，TDB中包含A的所有事务称为该节点对应的支持事务集，根节点对应的支持事务集为TDB中的所有含有频繁项的事务，则除根节点外，FP树中任一节点所对应的支持事务集为其父节点对应的支持事务集的子集。
3 相关的数据结构及挖掘算法
3.1 相关数据结构
本文算法中新增的相关数据结构主要包括如下几个。
(1)事务支持数表（Trade_used table）
该表的每个条目的结构为{ trade_num, count }。其中，trade_num为事务号；开始构造FP树前，count为该事务所包含的频繁1-项项目的个数。该表的目的是记录事务项所包含的频繁项数量，算法中用于判断FP树各个节点及其子树构造是否完成，以便释放多余内存空间。
(2)事务节点（trade_node）
事务节点的结构为{trade_num,node_link}。其中，trade_num为事务号；node_link指向另一个事务节点。该结构用于下面所定义的项支持事务表。
(3)项支持事务表（Item_used table）
该表的每个条目的结构为{item_name,count,node_link}。该表主要存放频繁1-项集，以及含有该项的事务计数。其中，item_name为频繁1-项集的项名；count为该项的支持数计数；node_link指向包含该项的事务所组成的事务链的第一个节点，事务链由事务节点（trade_node）构成，事务链中事务节点的个数即是count值。项支持事务表中的条目及其所指向的事务链在构造FP树时不断被释放，当构造完成时，项支持事务表将全部被释放，以免额外占用内存空间。
3.2 算法描述
有了上述的数据结构，其FP-Tree的构造和挖掘过程如下：
(1)构造初始项支持交易表和初始交易支持数表。扫描数据库，将每条交易中包含的项统计到项支持交易表中，并构造初始交易支持数表。
(2)确定项支持交易表和交易支持数表。对初始项支持交易表按支持数由大到小排序，在给定最小支持数（或支持度）的基础上，去除低于最小支持数的项即可得到频繁1-项集。在此过程中，同时对初始交易支持数表进行调整。每去除一个非频繁项，交易支持数表中相关条目的计数相应的减去1。此过程结束后，项支持交易表仅仅包含频繁1-项集，而且其中各条目指向的交易链记录了支持该项的所有的交易号。交易支持数表中包含了各交易对频繁1-项集的支持程度，即该交易号在项支持交易表中出现的总次数。
(3)根据项支持交易表和交易支持数表构造FP-Tree。根据性质1可知，FP-Tree中每个非根节点的子女节点所代表的项在频繁1-项集中位于该节点所代表的项之后，也就是说，每个非根节点的子女节点代表的项在项支持交易表中位于该节点代表的项之后。此外，根据性质2，子女节点所对应的支持交易集为其父节点对应的支持交易集的子集。
由此，在构建了根节点root后，每次从项支持交易表中选取排在第一位的项建立root的子节点，以其项支持交易表中的指针链作为比较链，将排在其后的每一个项所含的交易链与比较链作比较，如果含有某些相同的交易编号，则建立一个子节点，该节点支持度即是具有相同编号的交易数量；调整交易支持数表和项支持交易表，将交易支持数表中相应的交易数量减去1，支持交易表中对应项的交易节点从指针链中释放；这样继续下去，直至与比较链对应的交易支持数表中的交易计数均为0。依次对项支持交易表中的第一位的项进行此种处理，直至项支持交易表中所有项均处理完成。此时FP-Tree构造完成，相应的项支持交易表亦在构造过程中不断释放而为空，交易支持数表中所有记录亦为0。
(4)在FP-Tree的基础上进行挖掘。此过程与文献[4]相同，此处不再赘述。
4 实验
实验平台采用P3.0G CPU，1G Memory，120GHD的IBM服务器，操作系统是Windows2000 Server，采用Visual Studio.NET2003编写程序。对比算法包括：Apriori算法、FP树算法和本文算法(IFP)。实验数据采用UCI机器学习数据库中的Mushroom数据集(其包括22属性，8124条记录)和Connect-4数据集(其包括43属性，67, 557条记录)。实验过程中，变化支持度阈值进行不同的实验，实验结果如图1、图2所示。
由实验结果明显看出，在同等数据集上，采用不同支持度阈值，本文提出的算法(IFP)挖掘时间均少于对比算法，说明其关联规则挖掘性能要优于对比算法，证明了本文算法的有效性。
5 结论
针对关联规则挖掘，本文提出了一种FP树的快速构造方法，仅需要一次扫描数据库即可生成FP树，进而提高了关联规则挖掘速度，实验结果也证明了算法的有效性。
图1 Mushroom数据集实验结果
图2 Connect-4数据集实验结果
参考文献：
[1]R.Agrawal, T.Imielinski, and A.Swami. Mining association rules between sets of items in large databases[A]. In Proc.1993 ACM-SIGMOD Int. Conf. Management of Data (SIGMOD’93), Washington, DC, May 1993,207-216.
[2]R.Agrawal and R.Srikant. Fast algorithms for mining association rules[A]. In Proc.1994Int. Conf. Very Large Data Bases(VLDB’94), Santiago, Chile. Sept.1994, 487-499.
[3]J.Han, J.Pei, Y.Yin, and R.Mal. Mining frequent patterns without candidate generation: a frequent-pattern tree approach[J]. Data mining and knowledge discovery, 2004,8(1), 53-87,.
[4]J.Pei, J.Han, H.Lu, S.Nishio, S.Tang, and D.Yang. H-Mine: Hyper-structure mining of frequent patterns in large databases[A]. Proc.2001 Int.Conf.on Data Mining(ICDM’01), San Jose, CA, Nov. 2001.
注：本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。
关键词：数据挖掘；关联规则；FP树
中图分类号：TP311 文献标识码：A文章编号：1009-3044(2007)18-31707-01
An Improved FP-Tree Algorithm for Mining Association Rules
LI Tao
(Nanjing Information Engineering University,Nanjing 210044,China)
Abstract:This paper introduces an improved FP-Tree algorithm for mining association rules. The new algorithm accelerates the process of constructing FP-Tree and generates the nodes by scanning the database only once. The presented algorithm can efficiently improve the performance of association rules mining.
Key words:Data Mining; Association Rules; FP-Tree
1 引言
关联规则挖掘是从大量数据中提取项集之间的关联和相互关系，由R.Agrawal等人在1993年首先提出[1]，经过十多年的发展，目前已经形成了一些较为有影响的挖掘算法[2~4]，以Apriori算法，FP树算法为代表。其中，Apriori算法通过产生候选频繁项集来挖掘关联规则，人们对其改进做了许多研究工作[5]。2004年左右，J.Han等人提出了一种不产生候选项集的挖掘方法，即FP树算法[3]。本文在深入研究FP树算法的基础上，提出了一种改进的FP树算法，它只需要对数据库进行一次扫描即可构造出FP树，从而缩短了关联规则挖掘时间，提高了效率。
2 相关概念描述
2.1 关联规则挖掘的相关概念
关联规则挖掘的数据集记为TDB（称为事务数据库），T={t1,t2,…,tk,…,tn} ，tk={i1,…,ij,L,ip} ，tk(k=1,2,…,n)称为事务，ij(j=1,2,…,p)称为项目。设I={i1,i2,…,im}是TDB中全体项目组成的集合，l的任何子集X称为TDB中的项目集。设tk和X分别为TDB中的事务和项目集，如果X?哿tk，称事务tk包含项目集。
数据集TDB中包含项目集X的事务数量称为项目集X的支持数，记为σx。项目集X的支持度记为support(X)。support(X)=σx/|TDB|，其中|TDB|是数据集TDB的事务数。
若X、Y为项目集，且X|Y=?椎，蕴涵式X=>Y称为关联规则。项目集X∪Y的支持度称为关联规则X=>Y的支持度，记作：support(X=>Y),support(X=>Y)=support(X∪Y)。
关联规则X=>Y的置信度记作：confidence(X=>Y)。
confidence(X=>Y)=support(X∪Y)/support(X)
2.2 FP树挖掘的相关概念
一棵频繁模式树[3](简称为FP树)是一棵定义如下的树结构：(1)它由一棵以标记为 的节点为根节点和一系列代表频繁项的节点构成的树，以及一个频繁项头表组成。(2)除根节点外，树中的每个节点包含三个域：项名(item_name)，计数(count)，以及节点链(node_link)。其中，项名是指该节点所代表的项；计数用于记录经过此节点的事务的数目；节点链指向具有相同项名的下一个节点，当没有下一个节点时，其指针为空。(3)在频繁项头表中的每一个条目由三个域组成，即项名(item_name)，支持度计数(count)和节点链头(head of node_link)，其中节点链头是一个指向FP树中具有相同项名的节点链中第一个节点的指针。
根据文献[3]中的FP树的构造过程，FP树显然具有下列性质。(1)FP树中的各非根节点所代表的项在按支持度排序的频繁1-项集中必定位于其后裔节点所代表的项之前。(2)若FP树中从根节点到某节点的分支上所有节点所代表的项（根节点代表空项）组成的项集为A，TDB中包含A的所有事务称为该节点对应的支持事务集，根节点对应的支持事务集为TDB中的所有含有频繁项的事务，则除根节点外，FP树中任一节点所对应的支持事务集为其父节点对应的支持事务集的子集。
3 相关的数据结构及挖掘算法
3.1 相关数据结构
本文算法中新增的相关数据结构主要包括如下几个。
(1)事务支持数表（Trade_used table）
该表的每个条目的结构为{ trade_num, count }。其中，trade_num为事务号；开始构造FP树前，count为该事务所包含的频繁1-项项目的个数。该表的目的是记录事务项所包含的频繁项数量，算法中用于判断FP树各个节点及其子树构造是否完成，以便释放多余内存空间。
(2)事务节点（trade_node）
事务节点的结构为{trade_num,node_link}。其中，trade_num为事务号；node_link指向另一个事务节点。该结构用于下面所定义的项支持事务表。
(3)项支持事务表（Item_used table）
该表的每个条目的结构为{item_name,count,node_link}。该表主要存放频繁1-项集，以及含有该项的事务计数。其中，item_name为频繁1-项集的项名；count为该项的支持数计数；node_link指向包含该项的事务所组成的事务链的第一个节点，事务链由事务节点（trade_node）构成，事务链中事务节点的个数即是count值。项支持事务表中的条目及其所指向的事务链在构造FP树时不断被释放，当构造完成时，项支持事务表将全部被释放，以免额外占用内存空间。
3.2 算法描述
有了上述的数据结构，其FP-Tree的构造和挖掘过程如下：
(1)构造初始项支持交易表和初始交易支持数表。扫描数据库，将每条交易中包含的项统计到项支持交易表中，并构造初始交易支持数表。
(2)确定项支持交易表和交易支持数表。对初始项支持交易表按支持数由大到小排序，在给定最小支持数（或支持度）的基础上，去除低于最小支持数的项即可得到频繁1-项集。在此过程中，同时对初始交易支持数表进行调整。每去除一个非频繁项，交易支持数表中相关条目的计数相应的减去1。此过程结束后，项支持交易表仅仅包含频繁1-项集，而且其中各条目指向的交易链记录了支持该项的所有的交易号。交易支持数表中包含了各交易对频繁1-项集的支持程度，即该交易号在项支持交易表中出现的总次数。
(3)根据项支持交易表和交易支持数表构造FP-Tree。根据性质1可知，FP-Tree中每个非根节点的子女节点所代表的项在频繁1-项集中位于该节点所代表的项之后，也就是说，每个非根节点的子女节点代表的项在项支持交易表中位于该节点代表的项之后。此外，根据性质2，子女节点所对应的支持交易集为其父节点对应的支持交易集的子集。
由此，在构建了根节点root后，每次从项支持交易表中选取排在第一位的项建立root的子节点，以其项支持交易表中的指针链作为比较链，将排在其后的每一个项所含的交易链与比较链作比较，如果含有某些相同的交易编号，则建立一个子节点，该节点支持度即是具有相同编号的交易数量；调整交易支持数表和项支持交易表，将交易支持数表中相应的交易数量减去1，支持交易表中对应项的交易节点从指针链中释放；这样继续下去，直至与比较链对应的交易支持数表中的交易计数均为0。依次对项支持交易表中的第一位的项进行此种处理，直至项支持交易表中所有项均处理完成。此时FP-Tree构造完成，相应的项支持交易表亦在构造过程中不断释放而为空，交易支持数表中所有记录亦为0。
(4)在FP-Tree的基础上进行挖掘。此过程与文献[4]相同，此处不再赘述。
4 实验
实验平台采用P3.0G CPU，1G Memory，120GHD的IBM服务器，操作系统是Windows2000 Server，采用Visual Studio.NET2003编写程序。对比算法包括：Apriori算法、FP树算法和本文算法(IFP)。实验数据采用UCI机器学习数据库中的Mushroom数据集(其包括22属性，8124条记录)和Connect-4数据集(其包括43属性，67, 557条记录)。实验过程中，变化支持度阈值进行不同的实验，实验结果如图1、图2所示。
由实验结果明显看出，在同等数据集上，采用不同支持度阈值，本文提出的算法(IFP)挖掘时间均少于对比算法，说明其关联规则挖掘性能要优于对比算法，证明了本文算法的有效性。
5 结论
针对关联规则挖掘，本文提出了一种FP树的快速构造方法，仅需要一次扫描数据库即可生成FP树，进而提高了关联规则挖掘速度，实验结果也证明了算法的有效性。
图1 Mushroom数据集实验结果
图2 Connect-4数据集实验结果
参考文献：
[1]R.Agrawal, T.Imielinski, and A.Swami. Mining association rules between sets of items in large databases[A]. In Proc.1993 ACM-SIGMOD Int. Conf. Management of Data (SIGMOD’93), Washington, DC, May 1993,207-216.
[2]R.Agrawal and R.Srikant. Fast algorithms for mining association rules[A]. In Proc.1994Int. Conf. Very Large Data Bases(VLDB’94), Santiago, Chile. Sept.1994, 487-499.
[3]J.Han, J.Pei, Y.Yin, and R.Mal. Mining frequent patterns without candidate generation: a frequent-pattern tree approach[J]. Data mining and knowledge discovery, 2004,8(1), 53-87,.
[4]J.Pei, J.Han, H.Lu, S.Nishio, S.Tang, and D.Yang. H-Mine: Hyper-structure mining of frequent patterns in large databases[A]. Proc.2001 Int.Conf.on Data Mining(ICDM’01), San Jose, CA, Nov. 2001.
注：本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。