基于改进FP- tree的高实用项目集挖掘研究

白玲玲1，韩天鹏2，王 峰2

（1.中共阜阳市委党校 教务处；2.阜阳师范学院 计算机与信息工程学院，安徽 阜阳 236037）

摘 要：大部分关联规则算法的提出是基于项目的频率值，若从成本、利润和用户的偏好考虑，传统的数据库挖掘频繁模式在现实世界中并不适合应用.本文基于FP-tree提出了一种高效用的模式树HUP-tree挖掘算法.该算法利用在数据库中基于向下封闭性产生压缩的树结构，以达到挖掘出高效用项的目的.实验表明该方法无论是在执行时间上，还是在生成的树的节点数量上，其性能均优于FP-tree.

教育期刊网 http://www.jyqkw.com
关键词 ：效用挖掘；高效用模式；FP-tree；关联规则

中图分类号：TP274;TP311文献标识码：A文章编号：1673-260X（2015）04-0021-05

1 引言

从交易数据库中挖掘频繁项集是知识发现的一个基本任务，其目标是确定项目集及出现频率是否高于一定的阈值.这是通常在寻找关联规则和序列模式时的基本规则[1].在过去，许多方法被提出用来发现频繁项集，这些方法可分为两类：分层方法和模式增长方法.Apriori算法[2]首先提出了基于一个分层处理方式挖掘关联规则.然后FP-growth算法[3]，提出了构建基于Apriori的压缩树形结构的挖掘规则.

Apriori和FP-growth两个算法所处理的是数据库中以二进制变量存在的所有项目，也就是说，他们只考虑在一个事务中是否存在一个项.在这种情况下，频繁项集只是揭示了在事务中项目出现的重要性，但并不反映任何其他的隐性因素，如价格或利润.例如，在百货公司售出钻石的机率要远低于衣服，但前者所获得的利润要比后者高的多.因此仅从频繁项看，不足以识别高度盈利的项目.

因而效用挖掘的提出可以部分地解决上述问题.它可以被看作是频繁项集挖掘与销售的数量和项目的利润考虑的延伸.效用挖掘通常是想找个高效用的项目集，这意味着它们的效用值大于或等于用户定义的阈值.在实践中，一个项集的效用值可以在成本、利润或从用户偏好的其他措施来衡量.本文提出利用一种新的树结构来辅助效用挖掘方法，这种新的树结构称为高效用模式树HUP-tree，旨在保持相关信息的效用挖掘.

2 FP-growth算法

数据挖掘涉及到应用特定的算法来提取数据集的模式或规则的特定表示.数据挖掘的一种常见的类型是从交易数据中获得关联规则，使得在一个事务中某些项目的存在也暗示着一些其他项目的存在.为了实现这一目的，Agrawal等，基于逐层方法提出了几种挖掘算法找到关联规则.Han等[4]提出了频繁模式树FP-tree结构和FP-growth算法，可以有效地挖掘频繁项集而不产生候选项目集.

FP-tree的挖掘算法由两个阶段组成.第一阶段的重点是从数据库中构建FP树，而第二阶段的重点是由FP树推导频繁模式.FP树的建立分为三个步骤.首先，扫描数据库并对所有的项计数.计数大于或等于预定的最小支持度阀值的项目为1-项频繁集.接着，将这些1-项频繁项按它们的频率递减排序.最后，再次扫描数据库，根据频繁项的排列顺序来构建FP-tree.构建的过程是从第一个事务到最后一个，一个元组一个元组的执行.最终，处理完所有事务建立完成FP-tree.

从数据库中构建FP树后，执行FP-growth挖掘算法找到所有的频繁项集.为每一个频繁项目生成条件FP树，从FP-tree树递归得到经过加工处理后的频繁项集.

2.1 效用挖掘

在关联规则挖掘中，只有二项集被认为是在数据库中.然而，在实际应用中，频繁项集只是揭示交易项目集的发生，但不反映任何其他重要因素，如价格或利润.按此方法高盈利，但低频率产品可能无法在传统的关联规则挖掘中被发现.例如，珠宝和钻石是高利润的产品，但在一个数据库中与食品或饮料产品进行比较可能并不频繁.

Yao等[5]，在同时考虑数量和项目的利润的基础上提出了实用模型.Chan等[6]人，提出实用挖掘的专题发现高实用项目集.Liu等[7]，提出了两阶段算法，快速发现高实用项目集通过采用向下封闭性和命名的方式作为交易加权利用率（twu）模型.它由两个阶段组成，第一阶段，交易效用被用作每个候选项集的有效上限，使得在保持搜索空间上交易加权向下闭合，以减少产生的候选项目集的数量.在第二阶段，再次扫描数据库查找候选的实际效用值，并确定高的实用项目集.因此，其主要思想是减少候选集生成的数量，以减少扫描数据库的时间.

本文提出的实用挖掘方法集成了两相法和FP树的概念，以有效地找到高实用模式.并据此设计了一个新的树结构.具体算法描述如下.

3 HUP-tree的构造

HUP树构造算法提出在数据库中基于向下封闭性的树结构保持高效用项目.该算法首先计算每个事务的交易效用.然后，发现所有项目的交易加权利用率值.如果项目的交易加权利用率大于或等于预定的最小实用阈值，该项目被认为是一个高交易加权1-项集.算法根据自己的交易频率，只保留了较高的交易加权1-项集的交易，然后对它们排序.事务通过元组来构建HUP-tree元组，从事务项的第一个到最后一个.树中的每个节点具有用于存储交易加权利用率的项目以及其前述项目的数量（包括其本身）中的路径.把quan_Ary数组连接到一个节点，以保存这些值.HUP-tree构算法陈述如下.

3.1. HUP-tree构造算法

输入：

1、I={i1，i2，...，ij，...，im}，每个项目ij的利润值为pj；

2、事务数据库D={T1，T2，...，TK，...，TN}，其中包含每个事务项目子集的数量;

3、最小的高效用阈值λ.

输出：

高效用模式树（HUP-tree）.

第1步：计算在每个事物Tk中的每项ij的效用值Ujk，Ujk=qjk*pj，其中qjk是每个事务Tk的项目ij的数量，pj是ij的利润.使事物Tk中的每个项目的效用值累计值为tuk，公式如下：

第2步：在执行上述步骤的过程中，还发现ij在数据库中的每个项目的发生频率f（ij）.

第3步：当一个事务的高效子集包含项目ij时计算出每个项目ij的高加权利用率（简称：twu），公式如下：

第4步：检查twu（ij）的值是否大于等于最小高效值，计算方法如下：

如果ij满足上述条件，把其放入高效1-项候选集C1中.集合满足条件如下：

第5步：在C1中根据它们交易的频率对高效1-项候选集排序.

第6步：给第5步C1中排序的1-项候选集结果建立表头.

第7步：删除在C1中不存在的项目，并对剩余的项目按照第5步的方法排序.

第8步：初始化HUP-tree的根节点集作为根.

第9步：逐步把更新后的事务加入到HUP tree中，方法如下：

如果第k个事务中的ij项出现在当前处理的HUP树的相应路径，则该事务的ujk作为节点添加到ij路径中，作为它的累加值.此外，将节点ij的前缀项的数量添加到quan_Ary数组中相应的元素中.

否则，将ij添加到相应路径的末尾的节点，并设置第k个事务效用值为ujk作为其节点值.此外，将节点ij的前缀项的数量添加到quan_Ary数组相应的元素中.最后，连接最后一个分支到当前的节点ij.如果不存在这样的分支，连接表头到当前节点.

第9步后，HUP-tree建立，注意在步骤9中，一个相应的路径意味着，在这个树中一个事务中对应的项目应根据项目出现在表头中的顺序进行出来.另外，步骤7和9可以在扫描数据库时来进行.下面给出一个例子来说明所提出的HUP-tree构造算法.假设有表1中所示的定量数据库.

在表1中给出了10个交易和6项，记为A到F.假定最小高效用阈被设定为35％.还假设对于项目的预定义利润值的定义如表2中所示.

根据算法树构造步骤进行如下：

第1、2步：每个事务中每项的效用值计算如表1， 采取的第一个交易作为一个例子来说明.与数量在第一笔交易的项目是（A：3，B：2，D：3）.在表2中对于物品A、B和D的利润是3，150和50.从而所述第一事务的事务效用计算为tu（T1）=（3*3）+（2*150）+（3*50），结果是459.其他事务的事务效用可以用相同的方法计算.此外，每个项目的发生频率也可以计算得到.以项目A为例.它出现在交易1，2，3，4，5，6，7和10.因此它的交易频率f（A）中设定为8.在步骤1和2后得到的结果列于表3.

第3步：本次交易加权利用率的交易（简称twu）每个项目都加在一起.以项目A为例.它出现在交易1，2，3，4，5，6，7和10中.其事务效用twu（A）则计算为tu（T1，A）+tu（T2，A）+tu（T3，A）+tu（T4，A）+tu（T5，A）+tu（T6，A）+tu（T7，A）+tu（T10，A），这是459+406+74+146+353+503+578+209=2728.其他项目，以同样的方式处理.结果见表4.

第4步：计算1-项集的twu值最小高效用值，其计算结果为1022.35，占总效用的35％.在这个例子中，记录在候选组的高效用1-项集C1中的4项A、B、D和E满足条件.C1={A：2725，B：1540，D：2080，E：1483}.

第5步：候选高效用1-项集C1中根据其发生频率降序排序.排序列表（A，D，E，B）.

第6步：候选高效用1-项集C1按顺序保存在表头中.其结果在表5中.

第7步：不存在C1的项目从交易的定量数据库中删除.在每个更新的交易剩余项根据上述顺序，然后进行排序.更新后的记录，其结果显示在表6中.

第8步：在HUP-tree的根节点最初设定为节点的根.

第9步：表6中的更新事务使用元组从第一个到最后一个来构造HUP-tree.每个节点的组成不仅包括twu值，而且包括其在路径上的前缀数量.取所述第一和第二数字的例子来说明构建过程.开始，第一次更新事务后（A：3，D：3，B：2）HUP-tree没有相应路径，三个新的节点.依次为项目创建三个新的节点，然后链接在一起.在第一个更新的事务后，每个节点不仅由事务效用值459组成，还包括该事务的前缀项数量的值.在这个例子中，A项中的第一个事务的前缀项为空（记值为NULL）.quan_Ary数组只保留项A本身的数量（A：3）.接着，D项被插入，其事务的第一个前缀项是A.D项加入quan_Ary数组中，数组为（A：3，D：4）.同样，quan_Ary数组加到B的节点的数组保持（A：3; D：3，B：2）.第一个交易被处理后，HUP-tree如图1.

在这之后，第二次进行处理后更新的交易为（A：2，D：4，E：2）.（A，D）为HUP树第二个事务的相应路径.节点A和D在路径中的事务效用值，计算结果为459+406=865.在quan_Ary数组中也更新了节点A和D的值.第二更新事务分别是{A：3+2=5}和{A：3+2=5，D：3+4=7}.此外，一个新节点被用于创建项目E并与D链接.quan_Ary产生（A：2，D：4，E：2）.第二次更新后的事务插入HUP树，其结果如图2.

其他的交易也以同样的方式处理.在处理所有10个交易后，最终构建的HUP树如图3.

第9步后，一个完整的HUP树已建成.然后可以通过上面所提出的HUP-tree算法来导出高效用项集.

4 算法验证

实验在Java平台中执行，CPU为英特尔酷睿2，主频2.8GHz处理器和4G主存储器，Microsoft Windows XP操作系统.在实验中使用商场购物的数据集，数量和利润的值被分配到数据库中所购买的物品.数量和利润的值范围分别均匀分布在1-20，、1-200.实验从树结构和挖掘过程执行的时间两个方面进行比较.最小实用阈值设定在70％至90％，每次5％的增量.结果如图4所示.

从图4可以很明显地看到，随着执行时间的增加，最小实用阈值在降低.这是合理的，因为最小效用门槛越小，就会有越多的候选项集进行了处理.此外，本文所提出的HUP-tree树结构，在5个不同的最小实用阀值中，显现出了更好的性能，特别当最小使用阀值较低时，HUP-tree算法的性能更优.

本文所提出的树构造算法中，高效用的1-项集是按照其交易频率来分类的.然而，除了频率排序外，1-项集还可以根据其twu值或字典顺序（lexicographic order）来进行排序.三个排序方法都可以产生正确的挖掘结果，但有不同的效率.按照三个方法进行实验比较其效果，产出的树节点数如图5所示.

从图5可以看出，基于所述频率排序与其他两个相比产生了较少的树节点.因此，所提出的树构建算法中使用的频率排序是合理和可以接受的.

5 结束语

本文提出了一种新的树结构称为高效用模式树（HUP-tree）.它有助于保持关联挖掘信息，使得数据库扫描时间可以大大减少.HUP-tree虽和FP-tree相似，但它们在结构上有不同之处，HUP-tree每个节点上都链接一个数组，以存储它的前缀项的数量及其在效用挖掘过程中的路径.实验结果表明，该算法的性能比改进前算法快.另外，从三种方法的项目集排序结果来看，频率排序比其他两种推导出的树节点更少.

在本文中，我们假设数据库是静态的.在实际应用中，数据可以被动态地插入或从数据库中删除.今后，当交易被插入，删除或修改时，我们将尝试处理效用挖掘的维护问题.如何进一步完善HUP-tree结构是笔者今后拓展研究的方向.

教育期刊网 http://www.jyqkw.com
参考文献：

（1）KantardzicM．数据挖掘：概念、模型、方法和算法[M]．王晓海，吴志刚．译．北京：清华大学出版社，2013：4-13．

（2）Agrawal R，ImielinskiT， Swami A.Mining association rules between sets of items in large databases[J]. Proceedings of ACMSIGMOD Conference on Management of Data，1993：207-216.

（3）章志刚，吉根林.一种基于FP-Growth的频繁项目集并行挖掘算法[J].计算计算机工程与应用，2014，50（2）：103-105.

（4）HanJ， Pei J， YinY. Mining frequent patterns without candidate generation[J]. The ACMSIGMOD international conference on management of data，2000，29（2）： 1–12.

（5）YaoH， HamiltonHJ， ButzCJ. A foundational approach to miningitemset utilities from databases[J]. The fourth SIAM international conference on datamining ，2004： 482–486.

（6）ChenMS， Han J，YuPS. Data mining： An overview from a databaseperspective[J]. IEEE Transactions on Knowledge and Data Engineering，1996： 866–883.

（7）LiuY， LiaoWK， Choudhary A. A fast high utility itemsets miningalgorithm [J]. The first international workshop on utility-based data mining，2005： 90–99.

（8）李玲娟，张敏.云环境下关联规则挖掘算法的研究[J].计算机技术与发展，2011，21（2）：43-46.

（9）牛新征，佘堃.基于FPMAX的最大频繁项目集挖掘改进算法[J].计算机科学，2013，40（12）：223-228.

（10）张圣.一种基于云计算的关联规则Apriori算法[J].通信技术，2011，44（6）：141-143.