An Improved Algorithm for Association Rules with Multiple Minimum Supports

Yang LIANG; Xiao-dong QIAN

doi:10.13718/j.cnki.xdzk.2019.07.018

Due to the diversity of big data, using a single minimum support in the data mining process will result in inefficient mining and redundancy rules. This paper proposes an improved algorithm based on multi-minimum support association rules. By setting a separate support threshold for each project, a multi-minimum support pattern tree is constructed, and the minimum frequent items are used as node screening criteria to perform redundant node deletion. In the process of mining frequent itemsets, the nature of sorting down-close is utilized to delete redundant candidate sets, and at the same time, it can automatically stop down mining, so that all frequent itemsets can be quickly and directly obtained, and the database does not need to be scanned multiple times. Experimental results show that the improved algorithm can improve mining efficiency and save computing time.

HTML

在这个大数据日益迅速发展的时代, 人们对于数据的价值已经越来越重视.根据IDC(International Data Corporation)的研究报告预测, 全世界数据总量将在2020年由2013年的4.4 ZB增长到35 ZB^[1].数据挖掘作为一个重要的技术手段已经被广泛应用于各个领域的研究当中, 例如机器学习、模式识别、信息检索等^[2-4], 而关联规则挖掘是数据挖掘中十分重要的手段之一, 特别是在大数据时代下进行数据间的关联分析显得尤为重要.由于大数据具有多样性的特点, 使用单个支持阈值来评估数据库中所有项目的发生频率是不够的, 因为每个项目不同, 它们不应该被同等看待.特别是在零售业, 价格低廉的日常用品经常被购买, 而奢侈品和高价位的产品却很少被购买; 如果设置过高最小支持度阈值, 只会挖掘到经常被购买的产品, 而较低的最小支持度阈值又会产生较多无意义的规则, 不利于产品的定位分析.所以, 传统的关联规则挖掘算法在处理海量数据时, 容易挖掘出常规的或无效用规则.

为了处理数据间的差异性问题, Liu等^[5]首次提出一种多最小支持度框架下的关联规则算法MSApriori, 该算法通过给事务数据库中的每一个项目设定单独的最小支持度, 将经典的Apriori算法扩展到关联规则的挖掘中, 避免了设置单一支持度所产生的局限性.但是, 由于Apriori算法结构的缺陷, 需要多次扫描数据库容易受到组合爆炸的影响, Hu等^[6]提出一种基于多最小支持度模式树的关联规则算法CFP-growth, 该算法基于FP-tree结构构造多最小模式树MIS-tree进行频繁项集的挖掘, 由于FP-tree模型的优点, 在挖掘过程中仅需2次扫描数据库来创建一系列条件模式树并生成完整的频繁项集, 在一定程度上节省了挖掘时间. Tseng等^[7]提出了MMS_Cumulate和MMS_Stratify两种算法, 在分类的情况下允许多种形式的最小支持度定义, 并挖掘发现了广义的关联规则. Lee等^[8]提出了一种基于最大约束条件下的多最小支持度关联规则算法, 在约束条件下进行关联规则挖掘, 并证明利用最大约束得到的关联规则数目小于使用最小约束得到的数目, 能够较为有效地减少无用规则产生.

随着研究深入, 更多的基于多最小支持度挖掘关联规则算法被提出, 例如基于属性关系多最小支持度的REMMAR算法^[9]; 模糊定量序列模式关联规则算法FQDN-MMS^[10]; 一种基于多最小置信度的关联规则算法^[11]等.这些算法都从不同角度进行关联规则提取, 但是随着数据不断增大, 在挖掘过程中冗余造成时间和空间上的消耗, 并且会出现较多的冗余规则, 造成挖掘效率不高的问题.所以, 本文基于多最小支持度的定义, 通过改进CFP-growth算法在频繁项集的挖掘过程中进行优化:将频繁项目最小支持度值作为初始项目的支持度阈值进行数据预处理, 并在生成候选项集过程中利用排序向下闭合的属性进行冗余项删除, 以达到解决挖掘时间和减少冗余规则产生的目的.

1. 相关论述

1.1. 多最小支持度定义

设项目集合为I={i₁, i₂, …, i_n}, 事务数据库为D={d₁, d₂, …, d_m}, 其中每一条事务为d_i(1≤i≤m), 由一个事务编号Tid表示, d_i为项目集合I的子集, 即${d_i} \subseteq I$(其中包含k个项的项集为k-项集); 若项集$X \subseteq I$, 其在事务数据库中出现的频率, 即支持度计数记作Support(X).

定义1 最小项支持度

对于上述项目集合I={i₁, i₂, …, i_n}, 对任意i∈I, 设定该项i一个最小支持度阈值, 称之为最小项支持度(minimum item support), 记作MIS(i). 表 1为某个数据库中各个项目所对应的MIS值.

定义2 最小项集支持度

对于项集X={i_s, …, i_t}, 1≤s≤t≤n, 其最小支持度为项集中最小的最小项支持度, 记作MIN(X), 即MIN(X)=min[MIS(i_s), …, MIS(i_t)].

定义3 频繁项集

在多最小支持度下, 若项i的支持度计数Support(i)＞MIS(i), 则项i是频繁项; 若项集X的支持度计数Support(X)＞MIN(X), 则项集X是频繁项集.

通过以上定义, 在频繁项集的挖掘过程中, 赋予事务数据库中每一项单独的最小支持度阈值, 能够更加确切地反应事务本身的特点, 因为得到的任意候选项集都是由其本身所需满足的最小支持度决定, 而不是统一的最小支持度, 所以基于多最小支持度关联规则算法的核心步骤为设定单独的支持度阈值, 通过统计得到项集的支持度计数, 再得到频繁项集, 并进一步得到关联规则.

1.2. 改进策略

由于CFP-growth算法中, 用于构造MIS-tree的标准仍然考虑了一些在高阶候选相机中不能产生任何频繁模式的项目, 同时在进行频繁项集的挖掘时, CFP-growth会递归地构建MIS-tree中各个项目条件模式树, 直到其各自的条件模式为空, 但是会构建一些不频繁项的条件模式基, 而这些条件模式基所构建的条件模式树则不会产生任何高阶频繁模式.因此, 本文基于上述问题会导致效率不高的现象进行如下改进策略.

1.2.1. 最小频繁项支持度(LMS)

根据上述定义可知, 在多最小支持度模型中, 判断项集是否为频繁项集是根据该项集中值最小的最小项支持度, 这与单支持度模型下进行频繁项集的判定不一样, 所以在多最小支持度下项集的最小支持度是一个变动的值, 并且取决于该项集中的项, 但是在多最小支持度模式下会出现频繁项集的子集可能不是频繁项集的情况.例如某项集X={b, e, h}为频繁项集, 根据表 1可知MIN(X)=MIS(e)=2, 但其子集Y={b, h}的MIN(Y)=MIS(h)=4则由于最小支持度阈值的改变, 其子集可能不是频繁项集.因此, 为了更好地进行频繁项集挖掘, 本文将项集中最小频繁项所对应的最小项支持度作为该项集的最小支持度阈值.

定义4 在多最小支持度下, 称LMS为所有频繁项集合中最小的MIS值.

例如项集X={a, b, c, d}, 若a, c, d为频繁项, 则

性质1 在事务数据库中, 若存在项集X={i_s, …i_t}且$X \subseteq I$, 那么当s≤k≤t时, 若Support(X)＜LMS, 则Support(X)＜min[MIS(i_s), …MIS(i_t)], 即项集X是非频繁项集.

证由于项集X的支持度小于LMS, 并且LMS又是频繁项目集合中最小的项, 所以根据定义3可以得到该项集X是非频繁项集.

性质2 在事务数据库中, 若存在2个项集X和Y, $X \subset Y$且Support(X)＜LMS, 则Support(Y)＜LMS, 即项集Y是非频繁项集.

证由于在事务数据库中, $X \subset Y$, 则根据先验原理知Support(Y)≤Support(X), 又因为Support(X)＜LMS, 则Support(Y)≤Support(X)＜LMS, 根据性质1可知项集Y是非频繁项集.

以上2个性质表明, LMS能够保证在多最小支持模式下获得的频繁项集具有全局反单调性, 并且在频繁项集的生成过程中使用LMS作为约束条件, 可用于修剪无法生成任何高阶频繁项集的项, 能够减少搜索空间和提高挖掘效率.

1.2.2. 条件最小支持度

由于多最小支持度模式树的构建过程遵循了FP-tree思想, 并且该结构是将事务数据库中的每条事物按照项目的MIS值大小重新排序后进行构建, 所以在结构树中越靠下位置的项MIS值越小.因此, 考虑存在于树中的某一项i作为后缀项并构造其前缀子路径(即条件模式基)时, 该项i的MIS是其所有条件模式基中包含的项中最小的MIS值, 因此从该i的条件模式基中生成的任何频繁项集都大于i的MIS值.因此, 本文在挖掘频繁项集的过程中以该后缀项i的MIS作为该条件模树种的条件最小支持度,

定义5 当多最小支持度模式树存在一个项x, Support(x)是该项集X的支持度, 则MIS(x)表示为x必须满足的最小支持度阈值; Y是以x为后缀的条件模式基, y表示为该条件模式基Y中的一个项, 项y在该模式基中的支持度为Support(y), 其最小支持度为MIS(y), 则模式〈x, y〉的最小支持度为MIS(x).

1.2.3. 排序向下闭合

由上所述可知, 在多最小支持度模式下, 若项集X是频繁项集, 那么它的子集可能是非频繁项集, 这与传统FP-growth算法中频繁项集向下闭合的性质有所差别, 这是由于其子集的最小支持度阈值发生了改变所导致的.在频繁项集的挖掘过程中, 为了将频繁项集向下闭合的性质能够重新适用于多最小支持度模式, 本文提出一种排序向下闭合的概念, 重新对该性质进行形式化定义, 为了更好地区别传统的挖掘方法, 一个按照序号排序好的k-项集表示为X={i₁, i₂, …, i_k}.

性质3 (排序向下闭合)若存在一个频繁k-项集X={i₁, i₂, …, i_k}(其中k≥2, $X \subset I$), 且MIS(i₁)≤MIS(i₂)≤…≤MIS(i_k), 那么任何包含项i₁的k-1项集是频繁项集.

证由于项集X是频繁项集, MIS(i₁)≤MIS(i₂)≤…≤MIS(i_k), 则根据定义2可知Support(X)＞MIN(X)=MIS(i₁), 假设项集$Y \subset X$且i₁∈Y, 则MIN(Y)=MIS(i₁), 又因为项集Y是项集X的子集, 则Support(Y)≥Support(X), 所以Support(Y)≥Support(X)≥MIS(i₁)=MIN(Y), 因此项集Y是频繁项集.

根据性质3, 可以推导其反单调性.

性质4 若k-1项集X={i₁, i₂, …, i_k-1}($X \subset I$)是非频繁项集且MIS(i₁)≤MIS(i₂)≤…≤MIS(i_k-1), 若存在一个i_k∈I, 使MIS(i₁)≤MIS(i_k), 则k-项集也是非频繁项集.

根据这2个性质就可以解决在多最小支持度模式下频繁项集的子集是否为频繁项的问题, 同时由于本文采用基于FP-tree结构的模式, 其构建条件模式树是按照各项的最小支持度进行路径排序的, 所以若后缀项不频繁, 那么它的所有超后缀项集也将不频繁.

4. 结论

本文在挖掘关联规则的过程中, 针对单一支持度算法的局限性以及挖掘效率不足的问题, 提出一种基于多最小支持度的挖掘算法.在挖掘关联规则的主要步骤即挖掘频繁模式的过程中, 以LMS值作为筛选标准, 在生成频繁项集的步骤中将无法产生频繁项集的候选项集直接删除, 从而快速得到频繁项集; 通过实验结果对比, 证明了本文所提改进算法能够大幅地提高挖掘效率, 并且在大规模数据集下的性能表现良好.由于数据规模的不断增大, 对于算法运行存储空间的要求越来越高.随着分布式储存和计算的迅猛发展, 如何利用有限的资源去获取数据价值的探讨和研究十分必要.

Figure (8) Table (9) Reference (12)

Name
	Name cannot be empty!
E-mail
	Mailbox cannot be empty! Mailbox cannot be empty!
Telephone
	Mobile number cannot be empty! Please enter a valid mobile number!
Title

Content
Verification Code

[1]	GANTZ J, REINSEL D. 2011 Digital Universe Study:Extracting Value from Chaos[M]. Hopkinton:IDC Go-to-Market Services, 2011. Google Scholar
[2]	WU F, WANG Z, ZHANG Z, et al. Weakly Semi-Supervised Deep Learning for Multi-Label Image Annotation[J]. IEEE Transactions on Big Data, 2015, 1(3):109-122. doi: 10.1109/TBDATA.2015.2497270 CrossRef Google Scholar
[3]	CORMACK G V, CLARKE C L A, BUTTCHER S. Information Retrieval:Implementing and Evaluating Search Engines[J]. The Electronic Library, 2011, 29(6):853-854. doi: 10.1108/02640471111188088 CrossRef Google Scholar
[4]	NAUN C C. Book Review:Introduction to Modern Information Retrieval[J]. Library Resources & Technical Services, 2011, 55(4):239-240. Google Scholar
[5]	LIU B, HSU W, MA Y M. Mining Association Rules with Multiple Minimum Supports[C]//San Diego: Proceedings of the Fifth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining-KDD'99, 1999. Google Scholar
[6]	HU Y H, CHEN Y L. Mining Association Rules with Multiple Minimum Supports:A New Mining Algorithm and a Support Tuning Mechanism[J]. Decision Support Systems, 2006, 42(1):1-24. Google Scholar
[7]	TSENG M C, LIN W Y. Efficient Mining of Generalized Association Rules with Non-Uniform Minimum Support[J]. Data & Knowledge Engineering, 2007, 62(1):41-64. Google Scholar
[8]	LEE Y C, HONG T P, LIN W Y. Mining Association Rules with Multiple Minimum Supports Using Maximum Constraints[J]. International Journal of Approximate Reasoning, 2005, 40(1-2):44-54. doi: 10.1016/j.ijar.2004.11.006 CrossRef Google Scholar
[9]	LIU Y C, CHENG C P, TSENG V S. Discovering Relational-Based Association Rules with Multiple Minimum Supports on Microarray Datasets[J]. Bioinformatics, 2011, 27(22):3142-3148. doi: 10.1093/bioinformatics/btr526 CrossRef Google Scholar
[10]	HUANG T C K. Discovery of Fuzzy Quantitative Sequential Patterns with Multiple Minimum Supports and Adjustable Membership Functions[J]. Information Sciences, 2013, 222:126-146. doi: 10.1016/j.ins.2012.07.047 CrossRef Google Scholar
[11]	RAGE U K, KITSUREGAWA M. Efficient Discovery of Correlated Patterns Using Multiple Minimum All-Confidence Thresholds[J]. Journal of Intelligent Information Systems, 2015, 45(3):357-377. doi: 10.1007/s10844-014-0314-7 CrossRef Google Scholar
[12]	TANG K, CHEN Y L, HU H W. Context-Based Market Basket Analysis in a Multiple-Store Environment[J]. Decision Support Systems, 2008, 45(1):150-163. doi: 10.1016/j.dss.2007.12.016 CrossRef Google Scholar

Message Board

An Improved Algorithm for Association Rules with Multiple Minimum Supports

Abstract

References

Access History

通讯作者: 陈斌, bchen63@163.com

Article Metrics

Access History

Other Articles By Authors

An Improved Algorithm for Association Rules with Multiple Minimum Supports

Corresponding author: Xiao-dong QIAN