关联规则挖掘中数据增量方式比较研究

程敏*，郭晓军，李骁，何佶星



关联规则挖掘中数据增量方式比较研究

程敏*，郭晓军，李骁，何佶星

(西南石油大学计算机科学学院，四川成都610500）

随着电子商务的迅速发展，不仅交易数据程爆炸式增长，而且商品类别日新月异。因此，实时地、高效地、准确地获得频繁项集和关联规则对于商品的销售和推荐有着现实的指导意义。现有的工作针对交易数据的动态变化提出了很多增量式的挖掘算法，但只有较少的研究工作解决属性的增量变化问题。本文设计了一个增量算法来解决商品种类增加而引起的频繁项集和关联规则的更新问题。分析实际的卖家场景，商品的种类往往以两种方式动态增加，即一次只增加一种商品和一次性增加多种商品，其中，前者被称为逐一增加，后者被称为批量增加。针对商品不同的增加方式，分别提出两种挖掘子算法（addOneByOne与addAll），电商卖家可以根据实际情况来选择相应的解决方案。丰富的实验在真实商品交易数据集上进行，讨论了两种子算法和经典的Apriori算法在挖掘结果、运行时间两方面的性能。实验结果表明：1）两种子算法所得的结果完全一致；2）最好情况下，addOneByOne算法所用平均时间比addAll少2.93倍，比Apriori快12.85倍。

增量关联规则；数据增加方式；时间效率

引言

随着时间的推移，数据挖掘技术逐渐被应用到各个行业领域中。诸多数据挖掘算法被提出解决各类实际问题便于决策分析，如分类、聚类、关联规则挖掘等。关联规则挖掘[1-3]被广泛地应用于购物数据分析、医疗检测、天气预测等。目前，对关联规则挖掘的研究已经有很多算法被提出[4]。其中，Apriori算法是最为经典的算法，简单易懂，但它要求多次扫描数据库并会产生大量的中间候选集。较Apriori算法而言，FP-tree算法[5-7]很好解决了多次扫描的问题。但是，随着社会的发展以及关联规则挖掘研究的深入，为了更好的解决实际问题，增量关联规则挖掘的研究日益紧迫。

增量关联规则的研究具有非常重要的现实意义。目前，已经有很多增量关联规则挖掘的相关算法被提出来。FUP[8,9]算法通过利用已知频繁项集的支持度，过滤掉许多中间候选集，相比直接运用Apriori算法而言，效率更高。FUP2算法[10]在FUP算法的基础上进一步做了优化，通过利用先前的挖掘结果减少了计算出行规则的代价。IUA[11]算法研究了在有效利用已挖掘的结果的基础上，最小支持度阈值发生变化时的高效更新问题，以空间代价换取时间代价，提高效率。FIUA2算法[12]扫描数据库的次数远小于FUP算法，性能更加优越。文献[13]在引入前缀广义表结构的前提下，提出了一种增量式更新算法，克服了多次扫描数据库和产生大量候选集的缺陷。文献[14]提出了具有时间约束的增量规则挖掘算法TIDM。此外，针对时态数据库的增量关联规则的挖掘也有很多有重要贡献的研究[15]。基于FP-tree算法的增量关联规则挖掘的研究也有众多有效的算法[16-19]。TDUP算法[20]提出一种三支模式解决了重复扫描数据库和在线更新时规则的维护问题。文献[21]中为维持数据更新时的频繁项集，提出了一种通过预先存储可能的频繁项集的方法提高挖掘的效率。文献[22]根据时间区间来区分不同数据的重要性，提出了一种基于时间权值的增量优化关联规则挖掘算法。

虽然以上算法从不同角度及不同程度上解决了增量关联规则挖掘中的一些问题，但为了更好的应对实际问题，如何更加简便高效地更新新增商品后的规则仍亟待解决。本文在同时考虑增加新商品前后最小支持度与最小置信度不变的同时，在保证已挖掘频繁项集和规则有效的前提下，提出两种不同的方案，从数据新增数量和新增方式的角度出发，通过实验研究了不同方案下算法结果的一致性及方案的有效性。本文第1节简述了增量关联规则的问题描述并给出了所涉及的算法描述；第2节对相关算法示例说明；第3节应用真实数据集进行测试并对实验结果加以分析；最后，对本文的工作加以总结并指出进一步的工作方向。

1 问题描述与理论分析

1.1 增量关联规则的描述

静态关联规则挖掘是在固定数据集和支持度下，发现数据中的频繁项集及强关联规则。本文研究了属性增加的增量关联规则挖掘。设数据集，数据集的大小，其中事务项集，项集是I的子集且为关联规则。X在数据集中出现的次数为count(X)，其支持度：，若（为最小支持度，取值为0~1），称X为频繁项。规则置信度：，若则称X→Y为强关联规则。

假设已知n个商品并且均为既得频繁项集，新增加m个商品且计算后这些商品也是频繁项，数据模型如表1所示，得到如下结果：

…….

表1 数据模型

图1 理论频繁项集增加个数

若n=20和m=10, 20, 30, 40, 50，以长度为1、2、3的频繁项集为例对比频繁项增加的个数，如图1所示，随着新商品的增加，频繁项的数量也呈现递增的趋势，尤其是三阶及其以上频发项的数量增加更为明显。当然，设置不同的最小支持度和最小置信度会得到不同的挖掘结果。理论上，最小支持度的值越小，得到的挖掘结果就越多，若最小支持度的值设置恰当，会出现四阶频繁项集，五阶频繁项乃至更多阶的频繁项，从而得到更多的规则。

1.2 相关算法描述

根据文献[23,24]，本文假设是经过长期实践证明的稳定的既得频繁项集（增加新商品之前）。本文在进行增量计算时，仅使用新的交易数据集中中所包含的商品以及新增加的商品所对应的交易数据，即中不包含新增商品之前非频繁的商品的交易记录。交易记录数据集中数据表示对某一商品的购买数量。如果没有购买某一商品，则在交易记录数据集中对应为0。先计算长度为1的频繁项，用新增的商品在交易数据集中所对应的数据进行计算，得到新增频繁项集。再通过与间的排列组合形成更大长度的项，计算其是否为频繁项，然后计算该项中的强关联规则。若前一长度的频繁项集为空，则停止计算，否则继续计算下一长度的频繁项。

既得挖掘结果是一种经过符合长期实践，趋于稳定的数据。不同的数据增加方式在计算时，实质都是对不同数据的数据量统计，针对同一数据集，在最小支持度和最小置信度不变的条件下进行计算，所得结果也就能够保证一致性。

1.3 方案介绍

在此算法基础上，本文提出如下两种方案及对比参考方案：

图2 逐一增加流程图

图3 批量增加流程图

2 示例说明

设新增商品前的交易数据如表2所示，新增商品后的交易数据如表3所示，最小支持度：，最小置信度：；原商品集合，新增商品集合，故既得频繁项和规则所包含的元素集合。

表2 新增商品前交易数据

表3 新增商品后的交易数据

以上三种算法得到的结果一致。

3 实验

本实验采用真实交易数据集作为测试数据集（http://download.csdn.net/detail/guoshiwei536/9213281），通过复制、交换数据确定增加项的数据集，从而模拟增量计算过程。使用Java语言在window10（64位，4G内存）系统环境下利用myEclipse10.0软件进行3种方案的算法实现，根据不同的数据增加方式所得结果进行对比。其中，本数据集中共约5000条交易数据，5种新商品个数以10为梯度成等差增加（10,20,30,40,50），最小支持度和最小置信度的值保持与历史挖掘设定值一致。根据频繁项长度的不同，多次试验，分别依次对获取各长度的频繁项集所用的平均增加时间作对比。图3、图4、图5分别表示3种方式在长度为1,2,3的频繁项集在10次试验的情况下所用平均增加时间的对比。

图3 Frequency_len_1

图4 Frequency_len_2

图5 Frequency_len_3

图3、图4、图5显示，无论频繁项的长度如何，随着商品新增个数的增加，三种方式所用的增加时间都是线性增加的；频繁项的长度越长，所用的时间越多；对比三种方式，的效率最高，的效率高于。

4 结语

本文依据现实中出现的增量方式的不同，提出了两种不同情况下的增量子算法，即批量增加和单个增加。算法在最小支持度和最小置信度不变的情况下，利用已有挖掘结果，满足不同情况下的增量计算。通过示例和实验证明，两种子算法较经典算法而言，都具有更高的挖掘效率，逐一增加的子算法较批量增加的计算方式所需的计算时间更短，效率更高，能更好的应用到实际情况中。应对现实情况类似问题时，在有限的资源和成本前提下，为管理者如何决策益以获取最大利润提供高效的依据选择方式。下一步的研究目标：推广应用于分布式及并行数据库。

[1] Hipp J, Güntzer U, Nakhaeizadeh G. Algorithms for association rule mining—a general survey and comparison[J]. ACM sigkdd explorations newsletter, 2000, 2(1): 58-64.

[2] Kotsiantis S, Kanellopoulos D. Association rules mining: A recent overview[J]. GESTS International Transactions on Computer Science and Engineering, 2006, 32(1): 71-82.

[3] 张步忠, 江克勤, 张玉州. 增量关联规则挖掘研究综述[J]. 小型微型计算机系统, 2016, 01:18-23.

[4] 王爱平, 王占凤, 陶嗣干, 等. 数据挖掘中常用关联规则挖掘算法[J]. 计算机技术与发展, 2010, 20(4): 105-108.

[5] 陆楠, 王喆, 周春光. 基于FP-tree频集模式的FP-Growth算法对关联规则挖掘的影响[J]. 吉林大学学报: 理学版, 2003, 41(2):180-185.

[6] Shrivastava V K, Kumar P, Pardasani K R. FP-tree and COFI Based Approach for Mining of Multiple Level Association Rules in Large Databases[J]. International Journal of Computer Science & Information Security, 2010, 7(2).

[7] Qin L X, Luo P, Shi Z Z. Efficiently Mining Frequent Itemsets with Compact FP-Tree[C]// Intelligent Information Processing Ii, Ifip Tc12/wg12.3 International Conference on Intelligent Information Processing. 2004:397-406.

[8] Cheung D W, Han J, Ng V T, et al. Maintenance of discovered association rules in large databases: An incremental updating technique[C]//Data Engineering, 1996. Proceedings of the Twelfth International Conference on. IEEE, 1996: 106-114.

[9] 王新龙, 李强. 基于FUP算法的关联规则增量算法的研究[J]. 微计算机信息, 2009, 25(3):279-280.

[10] Cheung D W L, Lee S D, Kao B. A General Incremental Technique for Maintaining Discovered Association Rules[C]//DASFAA. 1997, 6: 185-194.

[11] 冯玉才, 冯剑琳. 关联规则的增量式更新算法[J]. 软件学报, 1998, 9(4): 301-306.

[12] 朱玉全, 孙志挥, 季小俊. 基于频繁模式树的关联规则增量式更新算法[J]. 计算机学报, 2003, 26(1): 91-96.

[13] 杨明, 孙志挥. 一种基于前缀广义表的关联规则增量式更新算法[J]. 计算机学报, 2003, 10:1318-1325.

[14] 马元元, 孙志挥, 高红梅. 时态数据库中增量关联规则的挖掘[J]. 计算机研究与发展, 2000, 12:1446-1451.

[15] Amornchewin R, Kreesuradej W. Incremental association rule mining using promising frequent itemset algorithm[C]//Information, Communications & Signal Processing, 2007 6th International Conference on. IEEE, 2007: 1-5.

[16] Ezeife C I, Su Y. Mining incremental association rules with generalized FP-tree[C]//Conference of the Canadian Society for Computational Studies of Intelligence. Springer Berlin Heidelberg, 2002: 147-160.

[17] Jian-Ping L, Ying W, Fan-Ding Y. Incremental Mining Alogorithm Pre-FP in Association Rules Based on FP-tree[C]// International Conference on NETWORKING & Distributed Computing. IEEE, 2010:199-203.

[18] 钟勇发, 吕红兵. 基于FP-growth的关联规则增量更新算法[J]. 计算机工程与应用, 2004, 26:174-175.

[19] 赵岩, 姚勇, 刘志镜. 基于 FP_tree 的频繁项目集增量式更新算法[J]. 计算机工程, 2008, 34(11): 63-65.

[20] Li Y, Zhang Z H, Chen W B, et al. TDUP: an approach to incremental mining of frequent itemsets with three-way-decision pattern updating[J]. International Journal of Machine Learning and Cybernetics, 2015: 1-13.

[21] Tsai P S M, Lee C C, Chen A L P. An efficient approach for incremental association rule mining[C]//Pacific-Asia Conference on Knowledge Discovery and Data Mining. Springer Berlin Heidelberg, 1999: 74-83.

[22] 李佳. 增量式优化关联规则算法研究及应用[D]. 江苏科技大学, 2010.

[23] 曹增明, 于书举, 贾豪杰. 多属性变化的增量关联规则更新研究[J]. 计算机工程与应用, 2010, 30:138-141.

[24] 邵勇, 陈波, 方杰, 等. 基于属性变化的增量关联规则挖掘[J]. Computer Engineering and Applications, 2009, 45(1).

Comparison among Data Incremental Approaches in Association Rule Mining

CHENG Min*, GUO Xiaojun, LI Xiao , HE Jixing

(School of Computer Science, Southwest Petroleum University, Chengdu 610500, China)

With the development of E-commence, not only the explosive of transaction datagrows, but also the commodity categories changes rapidly. Therefore, efficient and accurate getting frequent item sets and association rules in real time has practical significance, In the present work, a lot of incremental mining algorithms have been proposed to deal with the dynamic change of transaction data. But only a few researches have been done to solve the problem of incremental change of attributes. In this paper, we design an incremental algorithm to solve the updating problem of frequent item sets and associational rules. Analysis of the actual situation of the seller, the kind of goods are often dynamically increased in two ways, add only one item at a time and add more than one at a time. Among which, the former named addOneByOne, the latter is addAll. Two kinds of mining algorithms are proposed for different ways to increase the commodity. Then the sellers can choose the appropriate solution based on the actual situation. Extensive experiments are performed on real commodity transaction data. And the performance of two seed algorithms and the classical Apriori algorithm in mining results and running time are discussed. The experimental results show that firstly, the results obtained by the seed algorithms are identical. Secondly, in the best case, the average time of addOneByOne is 2.93 times less than addAll, and it is about 12.85 times faster than Apriori algorithm.

incremental association rule, add way, efficiency

10.19551/j.cnki.issn1672-9129.2017.02.05

TP3

A

1672-9129(2017)02-0028-05

2016-12-23；

2017-01-07。

国家自然科学基金61379089。

程敏（1991-）女，四川绵阳，学生，硕士，主要研究方向：数据挖掘、关联规则、推荐系统。

E-mail: cm_913@163.com

引用：程敏, 郭晓军, 李骁, 等. 关联规则挖掘中数据增量方式比较研究[J]. 数码设计, 2017, 6(2): 28-32.

Cite：Cheng Min, Guo Xiaojun, Li Xiao , et al.Comparison among Data Incremental Approaches in Association Rule Mining [J]. Peak Data Science, 2017,6(2): 28-32.