计算机应用   2016, Vol. 36 Issue (11): 3062-3066  DOI: 10.11772/j.issn.1001-9081.2016.11.3062
0

引用本文 

王敬华, 罗相洲, 吴倩. 基于效用表的快速高平均效用挖掘算法[J]. 计算机应用, 2016, 36(11): 3062-3066.DOI: 10.11772/j.issn.1001-9081.2016.11.3062.
WANG Jinghua, LUO Xiangzhou, WU Qian. Fast high average-utility itemset mining algorithm based on utility-list structure[J]. Journal of Computer Applications, 2016, 36(11): 3062-3066. DOI: 10.11772/j.issn.1001-9081.2016.11.3062.

基金项目

国家自然科学基金资助项目(61370108)

通信作者

罗相洲(1991-), 男, 湖北武汉人, 硕士研究生, 主要研究方向:数据库、数据挖掘.wwwlxzwww@163.com

作者简介

王敬华(1965-), 男, 湖北红安人, 副教授, 硕士, 主要研究方向:数据挖掘、现代信息系统;
吴倩(1990-), 女, 湖北汉川人, 硕士研究生, 主要研究方向:数据挖掘、复杂网络

文章历史

收稿日期:2016-05-16
修回日期:2016-06-20
基于效用表的快速高平均效用挖掘算法
王敬华, 罗相洲, 吴倩    
华中师范大学 计算机学院, 武汉 430079
摘要: 高效用项集挖掘在数据挖掘领域中受到了广泛的关注,但是高效用项集挖掘并没有考虑项集长度对效用值的影响,所以高平均效用项集挖掘被提出;而目前的一些高平均效用项集挖掘算法需要耗费大量的时间才能挖掘出有效的高平均效用项集。针对此问题,给出了一个高平均效用项集挖掘的改进算法--FHAUI。FHAUI算法将效用信息保存到效用列表中,通过效用列表的比较来挖掘出所有的高平均效用值,同时FHAUI算法还采用了一个二维矩阵来有效减少二项效用值的连接比较次数。最后将FHAUI算法在多个经典的数据集上测试。实验结果表明,FHAUI算法在效用列表的连接比较次数上有了极大的降低,同时其时间性能也有非常大提高。
关键词: 平均效用    高效用    模式挖掘    数据挖掘    频繁模式    
Fast high average-utility itemset mining algorithm based on utility-list structure
WANG Jinghua, LUO Xiangzhou, WU Qian     
School of Computer, Central China Normal University, Wuhan Hubei 430079, China
Background: This work is partially supported by the National Natural Science Foundation of China (61370108).
WANG Jinghua, born in 1965, M. S., associate professor. His research interests include data mining, modern information system.
LUO Xiangzhou, born in 1991, M. S. candidate. His research interests include database, data mining.
WU Qian, born in 1990, M. S. candidate. Her research interests include data mining, complex network.
Abstract: In the field of data mining, high utility itemset mining has been widely studied. However, high utility itemset mining does not consider the effect of the itemset length. To address this issue, high average-utility itemset mining has been proposed. At present, the proposed high average utility itemset mining algorithms take a lot of time to dig out the high average-utility itemset. To solve this problem, an improved high average itemset mining algorithm, named FHAUI (Fast High Average Utility Itemset), was proposed. FHAUI stored the utility information in the utility-list and mined all the high average-utility itemsets from the utility-list structure. At the same time, FHAUI adopted a two-dimensional matrix to effectively reduce the number of join-operations. Finally, the experimental results on several classical datasets show that FHAUI has greatly reduced the number of join-operations, and reduced its cost in time consumption.
Key words: average utility    high utility    pattern mining    data mining    frequent pattern    
0 引言

模式挖掘是数据挖掘中的一个重要领域,其中频繁模式挖掘是在事务数据库中找出出现频率比较高的项集,但频繁模式挖掘方法[1-4]仅考虑项是否在事务中出现,并没有考虑项在事务中出现的频率或者项的权重,而项的频率和项的权重往往在实际的推荐中具有非常重要的作用。

为了解决这个问题,大量的高效用项集挖掘算法被提出。这些高效用项集挖掘算法可分为一阶段算法和二阶段算法。高效用项集挖掘是指挖掘数据库中效用值高于用户指定阈值的项集。因为高效用项集挖掘算法综合地考虑了项在事务中出现的次数和项本身的权重,所以其在实际场景中具有更广泛的应用;然而高效用项集挖掘仅仅关注项集的效用值,而对项集长度影响效用值的情况并未探讨。一般来说项集的长度越长,其效用值就越大,因此用相同的阈值来衡量长度不同的项集不是很合理。

为了降低项集长度对效用值的影响,以及挖掘出高平均效用项集,Hong等[13]提出了平均效用项集挖掘方法TPAU(Two-Phase Average-Utility)。该方法通过项集效用值和项集的长度来计算项集的平均效用值,即数据库中某一项集的平均效用值是指其真实的效用值除以该项集所含项的个数。高平均效用项集是指项集的平均效用值高于用户指定阈值的项集。由于TPAU是层次计算需要多次扫描数据库,HAUP-Growth(High Average-Utility Pattern Growth)算法[14]被提出。HAUP-Growth是基于树结构的算法,只需要两次数据库扫描即可挖掘出所有的候选项集,但是HAUP-Growth属于二阶段算法,会产生大量的候选项集,所以一阶段算法PBAU(Projection-Based Average-Utility)[15]、HAUI-tree(High Average-Utility Itemsets tree)[16]、HAUI-Miner(High Average-Utility Itemsets Miner)[17]被提出,其中HAUI-Miner是目前已知最优高平均效用项集挖掘算法,它采用AU-list结构保存项集效用信息,然后通过AU-list连接比较挖掘出所有的高平均效用项集,实验表明其时空性能都是最优的。尽管AU-list非常有效,但是其高平均上界并不够紧凑,因此挖掘过程中需要进行大量的连接比较。

为此本文提出了一个改进的效用列表结构IAU-list(Improved Average-Utility list),该结构给出了一个更紧凑的高平均上界,它大幅度减少了效用列表比较和连接的过程;另外,依据快速的高效用项集挖掘(Faster High-Utility Itemset, FHM)提出的EUCS(Estimated Utility Co-occurrence Pruning)结构[9]给出了一个平均效用删减的二维矩阵EAUCS(Estimated Average Utility Co-occurrence Pruning),该矩阵可以有效减少二项集的比较过程。FHAUI也是一个一阶段算法,不需要产生候选项集。

1 高平均效用项集挖掘

高平均效用项集挖掘是指挖掘平均效用值高于用户指定阈值的项集。在这一章中给出了高平均效用项集挖掘的相关定义和性质[17]。设I={i1, i2, …, im}为包含m个不同项的有限项集。D={T1, T2, …, Tn}为包含n个事务数据库,其中事务TkD(1≤kn)是I的一个子集,并且每个事务有一个唯一的tid。事务Tk中的每个项ij(1≤jm)有一个内部权重(如该项在事务中出现的数量)记作q(ij, Tk)∈(1, 2, 3, …)。每个项ij还有一个外部权重(如该项的利润)记作p(ij)。一个包含s个不同项的集合X={i1, i2, …, is}称为s-项集,其中XI表 1表示了一个数据集的实例。表 2表示了每一项对应的外部权重即利润。

表 1 数据集
表 2 利润表

定义1  项ij在事务Tk中的平均效用值(average-utility)记作au(ij, Tk),定义为:

$ au({i_j}, {T_k}) = (q({i_j}, {T_k}) \times p({i_j}))/1 $ (1)

例如,表 1au(A, T1)=(1×2)/1=2,au(B, T3)=(1×5)/1=5。

定义2  s-项集X在事务Tk中的平均效用值记作au(X, Tk),定义为:

$ \begin{array}{l} au(X, {T_k}) = \left( {\sum\limits_{{i_j} \in X \wedge X \subseteq {T_k}} {au\left( {{i_j}, {T_k}} \right)} } \right)/\left| X \right|\; = \\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\left( {\sum\limits_{{i_j} \in X \wedge X \subseteq {T_k}} {au\left( {{i_j}, {T_k}} \right)} } \right)/s \end{array} $ (2)

例如,表 1au(AB, T1)=(2+10)/2=6,au(BC, T3)=(5+12)/2=8.5。

定义3  项集X在数据库D中的平均效用值记作au(X),定义为:

$ au(X) = \sum\limits_{X \subseteq {T_k} \wedge {T_k} \in D} {au\left( {X, {T_k}} \right)} $ (3)

例如,表 1au(AB)=11.5,au(CD)=16。

定义4  一个事务Tk的事务效用值(transaction utility)记作tu(Tk),定义为:

$tu({T_k}) = u({T_k}, {T_k})$ (4)

例如,表 1tu(T1)=2+10+4+3=19。

定义5  事务Tk中的事务最大效用值(transaction-maximum utility)记作tmu(Tk),定义为:

$ tmu({T_k}) = max(\{ u({i_j})\left| {{i_j} \in {T_k}} \right.\} ) $ (5)

例如,表 1tmu(T2)=max(4, 8, 3)=8。表 1表 2对应的效用值和每个事务的tmu表 3所示。

表 3 最大效用值

定义6  项集X的平均效用上界(average-utility upper bound)记作auub(X),表示包含项集X的事务的最大效用值之和,定义为:

$ auub\left( X \right) = \sum\limits_{X \subseteq {T_k} \wedge {T_k} \in D} {tmu\left( {{T_k}} \right)} $ (6)

例如,表 3auub(AB)=10+6=16,auub(BC)=10+12=22。每个项的auub表 4所示。

表 4 每个项的平均效用上界

定义7  如果一个项集的平均效用值不小于用户指定的阈值(记作minUti)则该项集是一个高平均效用项集;如果一个项集的平均效用值小于用户指定的阈值minUti,则该项集是一个低平均效用项集。

定义8  如果一个项集Xauub(X)不小于用户指定的阈值minUti,则该项集称为一个高平均效用上界项集;如果一个项集Xauub(X)小于用户指定的阈值minUti,则该项集不是高平均效用上界项集。

例如,在表 3中设阈值minUti=15,因为auub(AB)=16>15,所以AB为高平均效用上界项集,而auub(AE)=14 < 15,所以AE不为高平均效用上界项集。

性质1  项集的平均效用上界满足闭包属性:任何一个项集如果符合高平均效用上界项集,则其非空子集也符合高平均效用上界项集;任何一个项集如果不符合高平均效用上界项集,则其超集也不符合高平均效用上界项集。

证明  设Xs是一个s-项集,Xs-1为(s-1)-项集。因为Xs-1Xs的子集,则包含项集Xs的事务一定包含项集Xs-1。假设Xs是一个高平均效用上界项集,则:

$ \begin{array}{l} auub\left( {{X^s}} \right) = \sum\limits_{{X^s} \subseteq {T_k} \wedge {T_k} \in D} {tmu\left( {{T_k}} \right)} \le \\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\sum\limits_{{X^{s - 1}} \subseteq {T_k} \wedge {T_k} \in D} {tmu\left( {{T_k}} \right)} = auub\left( {{X^{s - 1}}} \right) \end{array} $ (7)
2 FHAUI算法

FHAUI算法是一阶段算法,不需要产生候选项集,其挖掘过程分为IAU-list结构的构建过程和从IAU-list中挖掘出高平均效用项集的过程。下面将介绍算法的具体过程。

2.1 构建IAU-list 2.1.1 第一次数据库扫描

扫描数据库D,统计每个事务的tmu,同时计算每个项的auub值。在统计完每个项的auub值之后,对项按auub降序排序。最后将每个项的auub小于minUti的项删减掉。并把这种删减并排序后的项的关系记为≺。

例如,对表 1表 2中的数据集统计每个事务的tmu表 3所示,而每个项的auub表 4所示。设minUti=15,对项删减并排序后的结果如表 5所示,可以看出项EF被删减了,排序结果为CBDA

表 5 删减并排序后的项
2.1.2 第二次数据库扫描

第二遍扫描数据库D,将数据库D中的每个事务中的项按关系≺进行删减并排序,同时为了获得更紧凑的平均效用上界,重新计算排序后的事务的tmu。这个重排的数据库记作D′,重排的事务记作T′。例如将表 3中的事务按≺进行删减并排序后并重新计算事务tmu的结果如表 6所示,新的tmu记为ntmu(new transaction-maximum utility)。

表 6 重排的数据集D

在第二遍扫描并处理事务的同时,需要将事务中项的效用信息保存到IAU-list结构中。IAU-list结构包含三个部分:项ij所在的重排事务T′的tid(T′),项ij所在重排事务T′中该项的效用值iu(ij, T′),项ij所在重排事务T′中从该项到T′末尾的项中最大的效用值rmu(ij, T′)。

例如,对表 6中的数据集中的各项建立IAU-list,其结果如图 1所示。在图 1中项B的第一列表示的是tidB出现在事务tid(T1)=1,tid(T3)=3,tid(T4)=4中;第二列表示的是iuB在事务1中的效用值是iu(B, T1)=10,在事务3中的效用值是iu(B, T3)=5,在事务4中的效用值是iu(B, T4)=5;第三列表示的是rmu,在事务1中从BB之后的项DA中最大的效用值max(10, 3, 2)=10,则rmu(B, T1)=10,同理rmu(B, T3)=6,rmu(B, T4)=6。

图 1 1项集的IAU-list

相比HAUI-Miner算法中的AU-list,IAU-list最大的不同点是IAU-list的最后一列rmu。在AU-list中其最后一列保存的是该行事务的tmu,但是对于已排序的事务取该项之后的rmu会在后续的计算中得到一个更紧凑的平均效用上界,从而产生更有效的删减。例如,在AU-list中对于图 1中的项B,其对应的tmu(B, T1)=10,tmu(B, T3)=12> rmu(B, T3)=6,tmu(B, T4)=6。可以看出在事务3中IAU-list的平均效用上界更小,在大量的数据集的测试中效果更为明显。

在实际的实现中,为了提高算法的性能,在为项集建立IAU-list时,会同时计算该IAU-list的iu之和与rmu之和。

定义9  项集X中IAU-list的iu之和为sum(X.iu)。例如,在图 1中的项集C,其sum(C.iu)=4+8+12+4=28。

定义10  项集X中IAU-list的rmu之和为sum(X.rmu)。例如,在图 1中项集C,其sum(C.rmu)=10+8+12+4=24。

为了能更有效地减少挖掘过程中的比较次数,本文给出了一个平均效用删减二维矩阵EAUCSEAUCS是利用第一遍数据库扫描后删减并排序的项构成的二维矩阵,该EAUCS中的值初始化为0。在数据库第二次扫描时,将删减并排序后事务中的剩余项进行两两结合找到EAUCS中对应的位置,并把该对应位置的值更新为EAUCS原值加上该事务的ntmu。例如,第一遍扫描数据库后只剩下排序后的项CBDA,对这些项建立二维矩阵EAUCS图 2所示,但是最开始矩阵中初始值为0。在第二遍扫描数据集时,如矩阵中的BC对应的值22等于事务T1ntmu值10和T3ntmu值12之和,矩阵中AC对应的值18等于事务T1ntmu值10和T2ntmu值8之和。因为矩阵是对称的,所以在实际的构建中只需要记录该矩阵的下三角或者上三角即可。

图 2 二维矩阵EAUCS
2.2 从IAU-list中挖掘高平均效用项集

从IAU-list中挖掘出高平均效用项集的过程是项集的IAU-list之间的比较连接的过程。一个项集X可以与另一个项集Y进行比较连接生成项集XY,则XY称为X的扩展项集。判断一个项集是否为另一个项集的扩展项集和挖掘高平均效用项集的算法伪代码如算法1所示。

算法1  从IAU-list中挖掘高平均效用项集FHAUI。

输入  XiauexXiauminUtiEAUCS是伪代码的输入参数;

输出  高平均效用项集HAUIs

1) foreach IAU-list Yiau in exXiau-list do

2)  if sum(Yiau.iu)/|Yiau|≥minUti then

3)   HAUIsHAUIsYiau;

4)  end

5)  if sum(Yiau.rmu)≥minUti then

6)   exXiau←∅

7)   foreach IAU-list ZiauexXiau after Yiau do

8)    if EAUCS(Yiau, Ziau)≥minUti then

9)     exYiauexYiauconstruct(Xiau, Yiau, Ziau);

10)    end

11)   end

12)   FHAUI(Yiau, exYiau, minUti);

13)  end

14) end

算法1的第2)~4)行判断当前项集X的一个扩展项集Y是否为高平均效用项集,如果Y是高平均效用项集则将其添加到高平均效用项集表中。第5)~13)行通过sum(Y.rmu)判断项集Y是否可扩展,如果可扩展,将X扩展项集中排在Y之后的项集ZY进行连接生成Y的扩展项集。第12行同样地,处理Y的所有扩展项集。如此遍历下去直到找出所有的高平均效用项集。

算法1对项集的效用列表的比较连接是一个深度优先的处理过程。例如,图 1中的项集按≺排序CBDA,因为初始项集为null,则CBDA均为null的扩展。算法先处理C生成所有C的扩展项集CBCDCA,然后处理CB的扩展项集CBDCBA等等,当处理完与C相关的扩展然后依次处理与BDA相关的扩展项集直到挖掘出所有的高平均效用项集。

下面介绍IAU-list之间的比较连接过程和如何使用EAUCS进行删减。对于项集X和项集Y的比较连接生成项集XY是指,找出项集X与项集Y之间具有公共tid的行,令XY.iu=X.iu+Y.iuXY.rmu=max(X.rmu, Y.rmu)。例如,图 1中的1项集直接比较连接生成部分的2项集如图 3所示。而EAUCS则可以减少1项集之间比较连接判断是否可以生成二项集的过程。因为IAU-list之间的比较连接是比较耗时的,通过使用EAUCS可以在1项集比较连接之前就判断哪些是不可扩展的项集,如图 2中EAUCS(A, D)=10 < minUti就是不可扩展的。EAUCS虽然比较简单,但是在大量数据集中还是非常有效的。

图 3 比较连接后的AUI-list
3 实验结果与分析

为了检验FHAUI算法的性能,将其与另一个目前已知的最优的算法HAUI-Miner进行比较。实验采用的系统是64位的Windows 7,CPU为第四代i5处理器,内存8 GB。这两个实验都是采用Java实现。实验中使用了4个标准的数据集Retail、Kosarak、Mushroom、ChainStore。这4个数据集的数据特性如表 7所示, 其中:Avg.length表示事务的平均长度,Items表示不同项的个数,Trans表示事务的个数。

表 7 数据特性

实验结果如图 4~7所示。实验中只给出了运行时间和比较连接的次数而没有给出内存图的原因是,FHAUI和HAUI-Miner都是采用效用列表的结构,所消耗的内存也基本是相同的。

图 4 数据集Retail
图 5 数据集Kosarak
图 6 数据集Mushroom
图 7 数据集ChainStore

图 4~7可以看出随着阈值的增大,算法所需的运行时间越少,这是因为阈值越大所挖掘的高平均效用项集越少,所需要比较连接的次数也随之减少。同时,从图 4~7也可以看出随着比较连接次数的减少所需要的运行时间也随之减少。这是因为效用列表的比较和连接是非常耗时的。在图 4~7中可以明显看出FHAUI的性能要优于HAUI-Miner算法。这是因为FHAUI采用了平均效用删减二维矩阵,它有效地减少了二项集的比较次数,而IAU-list则因为给出的是一个更紧凑的高平均上界,可以极大地减少子连接的过程。因此,在Retail、Kosarak、Mushroom、ChainStore上FHAUI相比HAUI-Miner分别有2.4倍、32.3倍、16.8倍、75.96倍的性能提升。

4 结语

本文提出了一种高平均效用项集挖掘的改进算法,该算法属于一阶段算法,可以在不产生候选项集的情况下挖掘出所有的高平均效用项集,它只需要扫描两次数据库。同时,给出了一种改进的效用列表结构IAU-list和一个平均效用删减二维矩阵,使用这两种结构可以有效地减少效用列表之间的比较连接的次数。通过在多个数据集上与目前最优的HAUI-Miner算法比较,可以明显看出本文算法具有非常好的时效性。

参考文献
[1] AGRAWAL R, IMIELINSKI T, SWAMI A. Mining association rules between sets of items in large databases[J]. ACM SIGMOD Record, 1993, 22 (2) : 207-216. doi: 10.1145/170036
[2] HAN J W, PEI J, YIN Y W. Mining frequent patterns without candidate generation[J]. ACM SIGMOD Record, 2000, 29 (2) : 1-12. doi: 10.1145/335191
[3] AGRAWAL R, SRIKANT R. Fast algorithms for mining association rules in large databases[C]//Proceedings of the 20th International Conference on Very Large Data Bases. San Francisco, CA:Morgan Kaufmann Publishers Inc., 1994:487-499.
[4] 李也白, 唐辉, 张淳, 等. 基于改进的FP-tree的频繁模式挖掘算法[J]. 计算机应用, 2011, 31 (1) : 101-103. ( LI Y B, TANG H, ZHANG C, et al. Frequent pattern mining algorithm based on improved FP-tree[J]. Journal of Computer Applications, 2011, 31 (1) : 101-103. doi: 10.3724/SP.J.1087.2011.00101 )
[5] LIU M, QU J. Mining high utility itemsets without candidate generation[C]//Proceedings of the 21st ACM International Conference on Information and Knowledge Management. New York:ACM, 2012:55-64.
[6] FOURNIER-VIGER P, WU C W, ZIDA S, et al. FHM:faster high-utility itemset mining using estimated utility co-occurrence pruning[C]//Proceedings of the 21st International Symposium Foundations of Intelligent Systems. Berlin:Springer, 2014:83-92.
[7] KRISHNAMOORTHY S. Pruning strategies for mining high utility itemsets[J]. Expert Systems with Applications, 2015, 42 (5) : 2371-2381. doi: 10.1016/j.eswa.2014.11.001
[8] YAO H, HAMILTON H J, BUTZ C J. A foundational approach to mining itemset utilities from databases[C]//Proceedings of the 2004 SIAM International Conference on Data Mining. Philadelphia, PA:SIAM, 2004, 4:215-221.
[9] LIU Y, LIAO W, CHOUDHARY A. A two-phase algorithm for fast discovery of high utility itemsets[C]//Proceedings of the 9th Pacific-Asia Conference on Advances in Knowledge Discovery and Data Mining. Heidelberg:Springer-Verlag, 2005:689-695. http://www.oalib.com/references/16876471
[10] TSENG V S, SHIE B E, WU C W, et al. Efficient algorithms for mining high utility itemsets from transactional databases[J]. IEEE Transactions on Knowledge and Data Engineering, 2013, 25 (8) : 1772-1786. doi: 10.1109/TKDE.2012.59
[11] TSENG V S, WU C W, SHIE B E, et al. UP-Growth:an efficient algorithm for high utility itemset mining[C]//Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York:ACM, 2010:253-262.
[12] 祝孔涛, 李兴建, 王乐. 高效用项集挖掘算法[J]. 计算机工程与设计, 2013, 34 (12) : 4220-4225. ( ZHU K T, LI X J, WANG L. Improved algorithm for mining high utility itemsets[J]. Computer Engineering and Design, 2013, 34 (12) : 4220-4225. )
[13] HONG T P, LEE C H, WANG S L. Effective utility mining with the measure of average utility[J]. Expert Systems with Applications, 2011, 38 (7) : 8259-8265. doi: 10.1016/j.eswa.2011.01.006
[14] LIN C W, HONG T P, LU W H. Efficiently mining high average utility itemsets with a tree structure[M]. Berlin: Springer-Verlag, 2010 : 131 -139.
[15] LAN G C, HONG T P, TSENG V S. A projection-based approach for discovering high average-utility itemsets[J]. Journal of Information Science and Engineering, 2012, 28 (1) : 193-209.
[16] LU T, VO B, NGUYEN H T, et al. A new method for mining high average utility itemsets[C]//Proceedings of the 13th IFIP TC8 International Conference on Computer Information Systems and Industrial Management. Berlin:Springer, 2014:33-42.
[17] LIN J C W, LI T, FOURNIER-VIGER P, et al. An efficient algorithm to mine high average-utility itemsets[J]. Advanced Engineering Informatics, 2016, 30 (2) : 233-243. doi: 10.1016/j.aei.2016.04.002