浅谈加权频繁项集挖掘的研究进展

房新秀

摘要：加权频繁项集挖掘是目前研究热点之一。自从关联规则挖掘提出以来，大部分的研究工作都围绕频繁项集挖掘问题进行。传统的关联挖掘算法往往忽略数据库中各个项目的重要程度区别，因此利用加权关联规则是有意义的。十几年来，学者们从不同的角度进行改进从而提高挖掘加权频繁项集算法的效率。本文首先分析了频繁项集挖掘现状，其次对加权频繁项集挖掘进行深入分析，最后通过对比频繁项集与加权频繁项集算法，对未来的工作进行了展望。

关键词：关联规则;频繁项集;加权关联规则;加权频繁项集;算法

中图分类号：TP301.6        文献标识码：A

文章编号：1009-3044（2019）27-0225-02

Abstract： Mining frequent weighted itemsets is one of the hotspots of research at present. Since the association rule mining was put forward， most of the research work has focused on frequent itemset mining. Traditional association mining algorithms often ignore the differences between items in the database in importance， so it is meaningful to use weighted association rules. For more than a decade， Scholars have improved the efficiency of the mining weighted frequent itemset algorithm from different angles. Firstly ， this paper analyzes the current situation of frequent itemset mining， then makes an in-depth analysis of weighted frequent itemset mining， and finally looks forward to the future work by comparing the frequent itemset algorithm and the weighted frequent itemset algorithm.

Key words：asocciation rule; frequent itemsets; weight asocciation rule; weighted frequent itemsets; algorithm

1 频繁项集挖掘现状

自从Agrawal在1993年首次提出关联规则[1-2]分析问题后，大部分的研究工作都围绕频繁项集挖掘问题进行。目前已经提出了许多算法来挖掘频繁项集。这些算法分为静态挖掘和动态挖掘。静态挖掘又分为两类：（1）使用“候选生成”方法的算法;（2）使用“模式增长”方法的算法。同时，频繁项集挖掘方法并不只是局限于挖掘关联规则，还可以广泛应用于相关性分析、孤立点分析、分类和聚类等，多种数据挖掘任务和入侵检测、序列模式、Web挖掘、top-k频繁项集等多种数据挖掘应用和数据分析处理任务中。因此，频繁项集挖掘问题是一个具有重要理论意义和广阔应用背景的研究课题，收到理论界和产业界的广泛重视。

2 加权频繁项集挖掘现状

传统的关联挖掘算法往往忽略数据库中各个项目的重要程度的区别。因此，在分析实际数据时，利用加权关联规则是有意义的。它发现那些出现频率较低但权值比较大的重要频繁项集。

Ramkumar（1998）等人首次提出挖掘加权频繁项集的问题。由Yun和Leggett发起的第一种方法是使用平均函数来评估权重的一个项目集，当向其添加新项时，项集的权重可以增加或减少，因此不满足向下封闭属性。为了解决这个问题，Yun等人 （2006）提出了一种上限模型，其采用最大权重值作为每个交易的权重上限，并且每个项目在预定的权重范围内被分配不同的权重值。后来lan等人在2015年提出了序列最大权重模型，以加强对子序列的加权支持的上限，从而减少数据挖掘中候选人数。第一种方法在挖掘过程中同时考虑项目集的权重和支持。然而，这种方法认为事务是相同的，但是在实践中，事务具有不同的重要性。

第二种方法源于Tao等人在2003年所做的研究，该研究通过计算事务中项目权重的算术平均值来得到事务权重。首先，项集的加权支持度反映了项集支持和事务具有不同的重要性。其次是它满足向下封闭属性。Tao等人在2003年提出了基于生成和检查候选者策略的算法。但是这个算法因为多次扫描数据库而耗费时间。Vo，Coenen在2013年提出了WIT-FWIs-Diff算法，该算法采用了WIT数据结构，其中WIT树是用于存储权值的IT树的扩展，WIT-FWIs-Diff算法仅扫描数据库一次，并采用diffset策略在WIT树上挖掘FWIs，从而达到高效的查找。但是该算法的缺点是它消耗了很多内存来存储tidsets，因此它在稀疏数据库上效果不明显。Nguyen在2016年提出了IWS算法[3]，IWS算法算法采用IWS数据结构，通过消除tidsets的位向量中的所有0来减少存储集的内存。但是IWS算法适用于稀疏数据集，对于密集数据集，它具有相反的效果。Lee等人在2017年提出了两种算法：FWI*TCD[4]、FWI*WSD[4]算法。以上两种算法均采用了一种新的前缀树結构来压缩数据，但是这两种算法必须通过多次遍历树来挖掘FWIs，因此花费了很多时间。

最近Huong Bui等人在2018年提出了一种基于加权N列表的算法[5]，用于挖掘频繁加权项集（称为NFWI），该算法使用加权N列表结构（WN列表），即N列表的括展。大大提高了算法的效率。

目前还有许多研究关注WD（Weighted Database）中的模式挖掘，挖掘加权频繁效用项集[6]、挖掘加权项集平行方法、挖掘加权最大频繁项集[7]、挖掘不频繁的加权频繁项集、加权可消除模式[8]、有趣的加权频繁模式挖掘、加权时态关联规则挖掘、等等。但是在挖掘效率方面仍然存在着一定的不足： （1）在扫描数据库方面：许多算法需要多次扫描数据库，当数据量很大时，需要消耗的时间更长影响了挖掘效率。（2）在数据项权值设置方面：权值设置过高会导致小概率事件中规则的丢失，权值设置过低容易挖掘出对用户无价值的规划。 （3）在连接和剪枝策略方面，每连接一次都会产生大量的频繁项集，特别是候选2-项集，当数据增多时，产生的候选项集几乎称爆炸式增长，降低了挖掘效率。

3 结束语

通过分析以上算法，比较频繁项集和加权频繁项集算法之后，采用满足向下闭合属性去挖掘加权频繁项集。在未来的工作中，通过分析现有算法存在的不足，在已有算法的基础上去改进数据结构，提高算法的效率，减少内存;同时考虑规则的时间适用性和项目的权重，去寻找一种考虑时间约束的加权关联规则挖掘的有效算法。从而大大提高关联规则挖掘的效率，避免决策者做出一些错误的决定。

参考文献：

[1] JiaweiHan， MichelineKamber， JianPei， et al. 数据挖掘：概念与技术[M]. 机械工业出版社， 2012.

[2] Grahne， G.， & Zhu， J. （2005）. Fast algorithms for frequent itemset mining using FPtrees. IEEE Transactions on Knowledge and Data Engineering， 17（10）， 1347–1362.

[3] Nguyen H， Vo B， Nguyen M， et al. An efficient algorithm for mining frequent weighted itemsets using interval word segments[J]. Applied Intelligence， 2016， 45（4）： 1008-1020.

[4] Lee G ， Yun U ， Ryu K H . Mining Frequent Weighted Itemsets without Storing Transaction IDs and Generating Candidates[J]. International Journal of Uncertainty， Fuzziness and Knowledge-Based Systems， 2017， 25（01）：111-144.

[5] Huong Bui ，Bay Vo ， Ham Nguyen， et al. A weighted N-list-based method for mining frequent weighted itemsets[J]. Expert Systems with application，2018， 96：388-405.

[6] Tran T ， Vo B ， Le T T N ， et al. Text Clustering Using Frequent Weigted Utility Itemsets[J]. Cybernetics and Systems， 2017， 48（3）：193-209.

[7] Yun U， Lee G .Incremental mining of weighted maximal frequent itemsets from dynamic databases[M].2016.

[8] Lee G ， Yun U ， Ryang H . Mining weighted erasable patterns by using underestimated constraint-based pruning technique[M]. IOS Press， 2015.

【通聯编辑：王力】