多最小支持度关联规则改进算法

梁杨; 钱晓东

doi:10.13718/j.cnki.xdzk.2019.07.018

多最小支持度关联规则改进算法

梁杨,
钱晓东

兰州交通大学电子与信息工程学院, 兰州 730070

基金项目: 国家自然科学基金项目(71461017)

详细信息

作者简介:
梁杨(1991-), 男, 硕士研究生, 主要从事数据挖掘研究 .

通讯作者: 钱晓东, 博士, 教授

中图分类号: TP274

An Improved Algorithm for Association Rules with Multiple Minimum Supports

School of Electronic and Information Engineering, Lanzhou Jiaotong University, Lanzhou 730070, China

摘要: 由于大数据具有多样性的特点，在数据挖掘过程中采用单一最小支持度会出现较多冗余规则，造成挖掘效率不高等问题，该文提出一种基于多最小支持度关联规则改进算法.通过给每一项目设置单独的支持度阈值，构建多最小支持度模式树，利用最小频繁项目作为节点筛选标准，进行冗余节点删除；在挖掘频繁项集的过程中利用排序向下闭合的性质，删除冗余的候选项集，同时能够自动停止向下挖掘，从而快速直接地得到所有频繁项集，并且不需要多次扫描数据库.实验结果表明，改进算法能够提高挖掘效率，节省计算时间.
- 大数据 /
- 频繁项集 /
- 关联规则 /
- 多最小支持度
Abstract: 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.
- big data /
- frequent itemset /
- association rule /
- multiple minimum support .

图 1 初始NMIS-tree

下载: 全尺寸图片幻灯片

图 2 剪枝过程

下载: 全尺寸图片幻灯片

图 3 完整NMIS-tree

下载: 全尺寸图片幻灯片

图 4 项f的前缀路径

下载: 全尺寸图片幻灯片

图 5 候选项集生成过程

下载: 全尺寸图片幻灯片

图 6 不同σ值下挖掘时间对比

下载: 全尺寸图片幻灯片

图 7 不同MIN值下挖掘时间对比

下载: 全尺寸图片幻灯片

图 8 挖掘时间和候选项集数量对比

下载: 全尺寸图片幻灯片

表 1 项目的MIS值

Item	a	b	c	d	e	f	g	h
MIS	5	5	6	7	2	3	3	4

下载: 导出CSV

表 2 构建NMIS-tree算法

算法构建NMIS-tree
输入:事务数据库D, 包含n项的项集I, 各个项的MIS
输出: NMIS-tree
步骤:
1:创建NMIS-tree的根节点Null;
2: for每一条事务t∈D do
3:将每一条事务中的项按照MIS值大小进行降序排列;
4:计算每个项的支持度, 记作Sup(i);
5:将排序后的每一条事务记作[p\|P], p代表第一个元素, P代表该事务剩余的集合,
6:调用insert_tree([p\|P], T)
7: end for
8: for (; j≥0; j=j-1) do
9: if (Sup(i_j)＜MIS(i_j)) then
10:删除头表中的项i_j; 调用NMIS_Pruning(NMIS-tree, f);
11: else
12: LMS=MIS[i_j]; break;
13: end if
14: end for
15: for (; j≥0; j=j-1) do
16: if (Sup(i_j)＜LMS) then
17:删除头表中的项i_j; 调用NMIS_Pruning(NMIS-tree, f)
18: end if
19: end for
20:调用MIN_Merge(NMIS-tree)

下载: 导出CSV

表 3 insert_tree过程

过程1 insert_tree([p\|P], T)
1: if存在一个T的子节点N, 使得p.item-name=N.item-name then
2: N的Count增加1;
3: else
4:创建一个新的子节点N, 使其节点的Conut为1, 并链接到父节点T;
5:通过节点链接的结构将该节点链接到同名的节点上;
6: end if
7: if $P \notin \emptyset $ then
8:调用insert_tree([p\|P], T)
9: end if

下载: 导出CSV

表 4 NMIS_Pruning过程

过程2 NMIS_Pruning(NMIS-tree, f)
1: for任意在NMIS-tree与i_j链接的节点
2: if如果该节点是叶子节点then直接删除;
3: else删除该节点, 并将该节点的子节点链接到它的父节点上;
4: end if
5: end for

下载: 导出CSV

表 5 MIN_Merge过程

过程3 MIN_Merge(NMIS-tree)
1: for Frequent header table中每一项do
2: if存在相同名称的子节点then
3:合并这些节点, 支持度计数为这些节点的计数之和;
4: end if
5: end for

下载: 导出CSV

表 6 NCFP-growth

算法 NCFP-growth
输入: NMIS-tree, MIS(i_j), k
输出:频繁项集
步骤:
1: for each i_j in the header of NMIS-tree do
2: if k=2 then
3: generate pattern β=i_j∪α with i_j. support;
4: else
5: generate pattern β=Apriori-gen(k, Fs);
6: end if
7: end for
8: Construct set of β′s conditional pattern do
9: for each β in the set of β′s conditional pattern do
10: if β is frequent then
11: Fs.add(β);
12: Call NCFP-growth(NMIS-tree, k+1, β, MIS(i_j))

下载: 导出CSV

表 7 原始事务数据库D

Tid	Items
1	c, d
2	a, d
3	b, c, d, g
4	a, b, c, f, h
5	a, d, g
6	c, d
7	a, c, d, h
8	b, d, f
9	a, b, c, e, f
10	a, c

下载: 导出CSV

表 8 排序后的事务数据库D

Tid	Items
1	c, d
2	d, a
3	c, d, b, g
4	c, a, b, f, h
5	d, a, g
6	c, d
7	c, d, a, h
8	d, b, f
9	c, a, b, f, e
10	c, a

下载: 导出CSV

表 9 数据集

数据集	项的个数	事务数	平均长度	最大长度
T10I4D100K	1 000	100 000	10	29
Transaction	20	46 243	5.5	68
注:平均长度和最大长度的单位, 都为项的个数.

下载: 导出CSV

[1]	GANTZ J, REINSEL D. 2011 Digital Universe Study:Extracting Value from Chaos[M]. Hopkinton:IDC Go-to-Market Services, 2011.
[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
[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
[4]	NAUN C C. Book Review:Introduction to Modern Information Retrieval[J]. Library Resources & Technical Services, 2011, 55(4):239-240.
[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.
[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.
[7]	doi: http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=e4247371b971944482d7d3ed42b840cb 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.
[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
[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
[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
[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
[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

图( 8) 表( 9)

计量

文章访问数: 788
HTML全文浏览数: 675
PDF下载数: 121
施引文献: 0

全文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值作为筛选标准, 在生成频繁项集的步骤中将无法产生频繁项集的候选项集直接删除, 从而快速得到频繁项集; 通过实验结果对比, 证明了本文所提改进算法能够大幅地提高挖掘效率, 并且在大规模数据集下的性能表现良好.由于数据规模的不断增大, 对于算法运行存储空间的要求越来越高.随着分布式储存和计算的迅猛发展, 如何利用有限的资源去获取数据价值的探讨和研究十分必要.

参考文献 (12)

姓名
	姓名不能为空！
邮箱
	邮箱不能为空！非法的邮箱地址。
手机号码
	电话不能为空！请输入有效手机号!
标题
	标题不能为空！
留言内容
	内容不能为空！
验证码
	验证码不能为空！验证码错误！

留言板

多最小支持度关联规则改进算法

兰州交通大学电子与信息工程学院, 兰州 730070

作者简介:
梁杨(1991-), 男, 硕士研究生, 主要从事数据挖掘研究 .

通讯作者: 钱晓东, 博士, 教授

An Improved Algorithm for Association Rules with Multiple Minimum Supports

School of Electronic and Information Engineering, Lanzhou Jiaotong University, Lanzhou 730070, China

计量

多最小支持度关联规则改进算法

通讯作者: 钱晓东, 博士, 教授

作者简介: 梁杨(1991-), 男, 硕士研究生, 主要从事数据挖掘研究
兰州交通大学电子与信息工程学院, 兰州 730070

English Abstract

An Improved Algorithm for Association Rules with Multiple Minimum Supports

Corresponding author: Xiao-dong QIAN

全文HTML

1.1. 多最小支持度定义

1.2. 改进策略

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

1.2.2. 条件最小支持度

1.2.3. 排序向下闭合

2.1. 算法思想

2.2. 算法流程

2.2.1. NMIS-tree构建

2.2.2. NCFP-growth

2.3. 算法示例

2.3.1. 数据库预处理

2.3.2. 构建NMIS-tree

2.3.3. 冗余剪枝

2.3.4. 合并重复路径

2.3.5. 频繁项集挖掘

3.1. 实验环境及数据

3.2. 实验结果分析

3.2.1. 时间消耗

3.2.2. 效率性能

目录

留言板

多最小支持度关联规则改进算法

兰州交通大学 电子与信息工程学院, 兰州 730070

作者简介: 梁杨(1991-), 男, 硕士研究生, 主要从事数据挖掘研究 .

通讯作者: 钱晓东, 博士, 教授

An Improved Algorithm for Association Rules with Multiple Minimum Supports

School of Electronic and Information Engineering, Lanzhou Jiaotong University, Lanzhou 730070, China

计量

出版历程

多最小支持度关联规则改进算法

通讯作者: 钱晓东, 博士, 教授

作者简介: 梁杨(1991-), 男, 硕士研究生, 主要从事数据挖掘研究 兰州交通大学 电子与信息工程学院, 兰州 730070

English Abstract

An Improved Algorithm for Association Rules with Multiple Minimum Supports

Corresponding author: Xiao-dong QIAN

全文HTML

1.1. 多最小支持度定义

1.2. 改进策略

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

1.2.2. 条件最小支持度

1.2.3. 排序向下闭合

2.1. 算法思想

2.2. 算法流程

2.2.1. NMIS-tree构建

2.2.2. NCFP-growth

2.3. 算法示例

2.3.1. 数据库预处理

2.3.2. 构建NMIS-tree

2.3.3. 冗余剪枝

2.3.4. 合并重复路径

2.3.5. 频繁项集挖掘

3.1. 实验环境及数据

3.2. 实验结果分析

3.2.1. 时间消耗

3.2.2. 效率性能

目录

兰州交通大学电子与信息工程学院, 兰州 730070

作者简介:
梁杨(1991-), 男, 硕士研究生, 主要从事数据挖掘研究 .

作者简介: 梁杨(1991-), 男, 硕士研究生, 主要从事数据挖掘研究
兰州交通大学电子与信息工程学院, 兰州 730070