﻿ 改进的频繁模式挖掘算法
 计算机系统应用  2019, Vol. 28 Issue (9): 154-161 PDF

1. 西安理工大学 理学院, 西安 710054;
2. 西北师范大学 教育学院, 兰州 730070

Improved Frequent Patterns Mining Algorithm
WEI En-Chao1, ZHANG De-Sheng1, AN Ping-Ping2
1. Faculty of Sciences, Xi’an University of Technology, Xi’an 710054, China;
2. College of Education, Northwest Normal University, Lanzhou 730070, China
Abstract: In order to solve the problem that the low efficiency of traditional frequent patterns mining algorithm, an improved Apriori algorithm based on FP-tree is proposed. Firstly, the join preprocessing process is added to the join step of Apriori algorithm. Secondly, the CP-tree is extended to construct a new tree structure, ECP-tree. The new tree structure can construct a compact prefix tree with only one scan of the database, and support interactive mining and incremental mining. Then, the improved points are combined with the APFT algorithm for mining frequent patterns. Finally, experiments are performed using two datasets in the UCI database. The experimental results show that the improved algorithm has higher mining efficiency and the frequent pattern mining speed is significantly improved.
Key words: frequent patterns     join preprocessing     ECP-tree structure     interactive mining     incremental mining

1 问题陈述 1.1 频繁模式挖掘

$I = \left\{ {{I_1},{I_2}, \cdots ,{I_m}} \right\}$ 是所有项的集合, 不失一般性, $I$ 中的项按字典顺序排列, 即 ${I_1} < \cdots < {I_m}$ . T为一个事务, 每个事务都由唯一的标识符TID和与之对应的项集 $Item(T)(Item\left( T \right) \subseteq I)$ 构成, 所有事务构成了事务数据库D, D中包含事务的个数称为数据库的大小, 记为 $Size(D)$ . 设 $X \subseteq I$ 为一个项集, 项集中包含项的个数叫做项集的长度, 记为 $Length(X)$ , 即 $Length\left( X \right){\rm{ = }}\left| X \right|$ , 长度为 $k$ 的项集称为 $k$ -项集. 事务T包含项集X, 当且仅当 $X \subseteq Item(T)$ , 项集X的支持度计数 $\sigma (X)$ 定义为数据库 $D$ 中包含项集 $X$ 的事务数, 即 $\sigma (X) = \left| {\left\{ {T|T \in D \wedge X \subseteq Item\left( T \right)} \right\}} \right|$ , 项集 $X$ 的支持度 $sup(X)$ 定义为包含项集 $X$ 的事务在数据库 $D$ 中所占的比例, 即 $sup(X) = \sigma (X)/Size(D)$ . 项集X为频繁模式, 当且仅当 $sup\left( X \right) \geqslant minsup$ , 其中 $minsup$ 为给定的最小支持度阈值, 长度为 $k$ 的频繁项集称为频繁 $k$ -项集, 记为 ${F_k}$ .

1.2 Apriori算法

Apriori算法[2]最早由Agrawal等提出, 该算法使用先验性质压缩搜索空间, 并使用一种逐层搜索的迭代方法, 其中 $k$ -项集用于探索( $k + 1$ )-项集. Apriori算法主要包含以下3个步骤:

1.3 FP-tree结构

FP-tree中每个节点由4个域组成: 项标识item-name、节点计数item-count、节点链item-link和父节点指针item-parent. 同时为了方便对树进行操作, FP-tree还包含一个频繁项头表header-table, 它由两个域组成: 项标识item-name和项元链链头node-link, 其中node-link是指向FP-tree中具有相同项标识的首节点指针, FP-tree中实线是父节点指针, 虚线是节点链. FP-tree相关概念及结构细节见文献[1]. 使用表1中的示例数据生成的FP-tree如图1所示, 设最小支持度阈值 $minsup = 3$ .

 图 1 FP-tree结构

1.4 APFT算法

APFT算法[10]使用Apriori算法挖掘基于FP-tree的频繁模式, 该算法仍采用分治策略. APFT算法主要包括两个步骤, 第一步是利用FP-growth算法中构造树的方法构造FP-tree; 第二步是利用Apriori算法挖掘FP-tree. 在第二步中, 需要添加一个名为 ${\rm{NTable}}$ 的附加节点表, 表中的每个项由两个域组成: Item-name和Item-support. Item-name表示在条件子树 ${{FP}}{{{T}}_j}( j =$ $1,2, \cdots {{,n}} )$ 中节点的名称, ${\rm{Item - support}}$ 表示与频繁1-项集 ${{{I}}_j}\left( {{{j = 1,2,}} \cdots {{,n}}} \right)$ 一起出现的节点数, 即项的支持度计数. APFT是最早将Apriori算法与FP-tree结合的算法, 但由于Apriori算法与FP-tree自身的缺陷导致该算法仍存在一些不足, 因此本文对APFT中的连接步与树构造方法进行了改进, 使算法能有效处理数据流问题. APFT算法的伪代码如算法1所示.

Input: FP-tree, minsup

Output: all frequent patterns L

1) L=L1;

2) for each item ${{{I}}_j}$ in header table, in top down order

3)　　 $\scriptstyle {{{L}}_{{{Ij}}}}{\rm{ = Apriori - mining}}\left( {{{{I}}_j}} \right)$ ;

4) return $\scriptstyle L = L \cup {L_{{I_{\rm{1}}}}} \cup {L_{{I_{\rm{2}}}}} \cup \cdots \cup {L_{{I_n}}}$ ;

Pseudocode $\scriptstyle {\rm{Apriori - mining}}\left( {{{{I}}_j}} \right)$

1) Find item p in the header table which has the same name with $\scriptstyle {{{I}}_j}$ ;

2) $\scriptstyle {{q = p}}{\rm{.tablelink}}$ ;

3) while q is not null

4)　 for each node qj!=root on the prefix path of q

5)　　 if NTablehas a entry N such that N.Item-name=qj.item-name

6)　　　 $\scriptstyle {\rm{N}}{\rm{.Item - support = N}}{\rm{.Item - support + q}}{\rm{.count}}$ ;

7)　　 else

8)　　　add an entry N to the $\scriptstyle {{NTable}}$ ;

9)　　　 $\scriptstyle {{N}}{{.Item - name = }}{{{q}}_j}{{.item - name}}$ ;

10)　　　 $\scriptstyle {{N}}{{.Item - support = q}}{{.count}}$ ;

11) $\scriptstyle {{q = q}}{{.tablelink}}$ ;

12) $\scriptstyle {{k = 1}}$ ;

13) $\scriptstyle {{{F}}_{{k}}}{{ = }}\{ {{i | i}} \in {{NTable}} \wedge {{i}}{\rm{.item - support}} \ge minsup\}$

14) repeat

15)　　 $\scriptstyle {{k = k + 1}}$ ;

16)　　 $\scriptstyle {{{C}}_{{k}}}{{ = apriori - gen}}\left( {{{{F}}_{{{k - 1}}}}} \right)$ ;

17)　　 $\scriptstyle {{q = p}}{{.tablelink}}$ ;

18)　　 while q is not null

19)　　　find prefix path $\scriptstyle {{t \;{\rm{of}} \;q}}$

20)　　　 $\scriptstyle {{{C}}_{{t}}}{{ = subset}}\left( {{{{C}}_{{k}}}{{, t}}} \right)$ ;

21)　　　 for each $\scriptstyle {{c}} \in {{{C}}_{{t}}}$

22)　　　　 $\scriptstyle {{c}}{{.support = c}}{{.support + q}}{{.count}}$ ;

23)　　　 $\scriptstyle {{q = q}}{{.tablelink}}$ ;

24)　　 $\scriptstyle {{{F}}_{{k}}}{{ = \{ c|c}} \in {{{C}}_{{k}}} \wedge {{c}}{{.support}} \ge {{min\_Sup}}\}$

25) until $\scriptstyle {{{F}}_{{k}}}{\rm{ = }}\emptyset$

26) return $\scriptstyle {{{L}}_{{{{I}}_{{i}}}}}{{ = }}{{{I}}_{{i}}} \cup {{{F}}_{{1}}} \cup {{{F}}_{{2}}} \cup \cdots \cup {{{F}}_{{k}}}$

2 改进算法 2.1 算法改进思想

2.2 优化连接步

Input: 频繁k-项集Fk

Output: 满足连接条件的频繁 $\scriptstyle k$ -项集 $\scriptstyle{L_k}$

1) for each items $\scriptstyle {F_i} \in {F_k}$

2)　 for each item $\scriptstyle I \in {F_i}$

3)　　 if $\scriptstyle I \in {F_k}$

4)　　　 $\scriptstyle I.{\rm{count}}{\kern 1pt} {\kern 1pt} {\rm{ + + }}$

5)　 for each item $\scriptstyle I \in {F_i}$

6)　　 if $\scriptstyle I.{\rm{count}}{\kern 1pt} < k$

7)　　　delete $\scriptstyle {F_i}$ from $\scriptstyle {F_k}$

8) return $\scriptstyle {L_k}$

2.3 新树的构造

Input: T和I

Output: 仅包含频繁项的Tsort和Isort

1) Compute Isort from I in frequency-descending order using merge sort technique

2) for each branch Bi in T

3)　 for each unprocessed path Pj in Bi

4)　　 if Pj contains only frequent items in order according to Isort

5)　　　Process_Branch(Pj)

6)　　 else Sort_path(Pj)

7) Terminate when all the branches are sorted and output Tsort ang Isort.

8) Process_Branch(P){

9) for each branching node nb in P from the leafP node

10)　 for each sub-path from the leafk with k $\ne$ p

11)　　 if item ranks of all nodes betweennb and leafk are greater than that of nb

12)　　　 P=sub-path from nb to leafk

13)　　　　 if P is contains only frequent items in order according to Isort

14)　　　　　Process_Branch(P)

15)　　 else P=path from the root to leafk

16)　　　Sort_path(P)

17) }

18) Sort_ path(Q){

19) Reduce the count of all node of Q by the value of leafQcount

20) Delete all nodes contains infrequent items and sort remaining nodes in an array according to Isort order

21) Delete all nodes having count zero from Q

22) Insert sorted Q into T at the location from where it was taken

23)}

 图 2 插入阶段后的I和T

 图 3 重排I构造Isort

 图 4 移除未排序路径

 图 5 在临时数组中对路径排序

3 实验分析

 图 6 将排序后的路径插入T中

 图 7 重构后的最终树

 图 8 mushroom上运行时间对比

 图 9 T10I4D100K上运行时间对比

4 结束语

 [1] Han JW, Kamber M, Pei J. 数据挖掘: 概念与技术. 范明, 孟小峰, 译. 3版. 北京: 机械工业出版社, 2012. [2] Agrawal R, Imieliński T, Swami A. Mining association rules between sets of items in large databases. ACM SIGMOD Record, 1993, 22(2): 207-216. DOI:10.1145/170036 [3] 刘步中. 基于频繁项集挖掘算法的改进与研究. 计算机应用研究, 2012, 29(2): 475-477. DOI:10.3969/j.issn.1001-3695.2012.02.019 [4] 邢长征, 安维国, 王星. 垂直数据格式挖掘频繁项集算法的改进. 计算机工程与科学, 2017, 39(7): 1365-1370. DOI:10.3969/j.issn.1007-130X.2017.07.025 [5] 于守健, 周羿阳. 基于前缀项集的Apriori算法改进. 计算机应用与软件, 2017, 34(2): 290-294. DOI:10.3969/j.issn.1000-386x.2017.02.052 [6] 王蒙, 邹书蓉, 方睿. 一种基于矩阵的Apriori改进算法. 信息技术, 2018(3): 150-154. [7] Han JW, Pei J, Yin YW. Mining frequent patterns without candidate generation. Proceedings of 2000 ACM SIGMOD International Conference on Management of Data. Dallas, Texas, USA. 2000. 1–12. [8] 肖继海, 崔晓红, 陈俊杰. 基于COFI-Tree的N-最有兴趣项目集挖掘算法. 计算机技术与发展, 2012, 22(3): 99-102. DOI:10.3969/j.issn.1673-629X.2012.03.026 [9] Yin M, Wang WJ, Liu Y, et al. An improvement of FP-Growth association rule mining algorithm based on adjacency table. MATEC Web of Conferences, 2018, 189(1): 10012. [10] Lan QH, Zhang DF, Wu B. A new algorithm for frequent itemsets mining based on apriori and FP-tree. Proceedings of 2009 WRI Global Congress on Intelligent Systems. Xiamen, China. 2009. 360–364. [11] 吴倩. 基于压缩FP-tree的频繁项集快速挖掘算法研究[硕士学位论文]. 上海: 华东理工大学, 2015. [12] 张宁. 基于FP-tree的Apriori算法的改进. 信息通信, 2015(2): 94-95. DOI:10.3969/j.issn.1673-1131.2015.02.056 [13] 倪政君, 夏哲雷. 一种基于fp-tree的Apriori算法改进研究. 中国计量大学学报, 2018, 29(1): 50-54. DOI:10.3969/j.issn.2096-2835.2018.01.009 [14] 吴磊, 程良伦, 王涛. 基于事务映射区间求交的高效频繁模式挖掘算法. 计算机应用研究, 2019, 36(4). DOI:10.19734/j.issn.1001-3695.2017.10.0972. [15] Tanbeer SK, Ahmed CF, Jeong BS, et al. Efficient single-pass frequent pattern mining using a prefix-tree. Information Sciences, 2009, 179(5): 559-583. DOI:10.1016/j.ins.2008.10.027