一種基于鄰接表的最大頻繁項(xiàng)集挖掘算法

殷茗; 王文杰; 張煊宇; 姜繼嬌

doi:10.11999/JEIT180692

一種基于鄰接表的最大頻繁項(xiàng)集挖掘算法

doi: 10.11999/JEIT180692

1.
西北工業(yè)大學(xué)軟件與微電子學(xué)院西安 710072
2.
西北工業(yè)大學(xué)管理學(xué)院西安 710072

基金項(xiàng)目: 教育部人文與社會(huì)科學(xué)基金(16YJA630068, 18YJA630043)，航空科學(xué)基金(2016ZG53071)，陜西省自然科學(xué)基礎(chǔ)研究計(jì)劃項(xiàng)目(2018JM7008)，陜西省社會(huì)科學(xué)基金(2018S28)，西北工業(yè)大學(xué)研究生種子基金(ZZ2018222)

詳細(xì)信息

作者簡(jiǎn)介:
殷茗：女，1978年生，博士，副教授，主要研究方向?yàn)槠髽I(yè)信息化、信息管理與信息系統(tǒng)、電子服務(wù)

王文杰：男，1992年生，碩士，主要研究方向?yàn)閿?shù)據(jù)挖掘、機(jī)器學(xué)習(xí)

張煊宇：男，1995年生，碩士，主要研究方向?yàn)樾畔⒐芾砼c信息系統(tǒng)

姜繼嬌：男，1979年生，博士，副教授，主要研究方向?yàn)樾袨榻鹑谂c風(fēng)險(xiǎn)管理

通訊作者:
王文杰　wenjie@mail.nwpu.edu.cn

中圖分類號(hào): TP311.5
計(jì)量
- 文章訪問(wèn)數(shù): 2009
- HTML全文瀏覽量: 1251
- PDF下載量: 80
- 被引次數(shù): 0
出版歷程
- 收稿日期: 2018-07-08
- 修回日期: 2019-05-17
- 網(wǎng)絡(luò)出版日期: 2019-05-29
- 刊出日期: 2019-08-01

A Maximal Frequent Itemsets Mining Algorithm Based on Adjacency Table

1.
Institute of Software and Microelectronics, Northwestern Polytechnical University, Xi’an 710072, China
2.
Management School, Northwestern Polytechnical University, Xi’an 710072, China

Funds: Ministry of Education Humanities and Social Science Foundation (16YJA630068, 18YJA630043), Aeronautical Science Fund of China (2016ZG53071), Shaanxi Natural Science Basic Research Project (2018JM7008), Shaanxi Social Science Foundation Project (2018S28), Graduate Student Seed Fund Project of Northwestern Polytechnical University (ZZ2018222)

摘要

摘要: 針對(duì)Apriori算法與FP-Growth算法在最大頻繁項(xiàng)集挖掘過(guò)程中存在的運(yùn)行低效、內(nèi)存消耗大、難以適應(yīng)稠密數(shù)據(jù)集的處理、影響大數(shù)據(jù)價(jià)值挖掘時(shí)效等問(wèn)題，該文提出一種基于鄰接表的最大頻繁項(xiàng)集挖掘算法。該算法只需遍歷數(shù)據(jù)庫(kù)一次，同時(shí)用哈希表對(duì)鄰接表進(jìn)行輔助存儲(chǔ)，減小了遍歷的空間規(guī)模。理論分析與實(shí)驗(yàn)結(jié)果表明，該算法時(shí)間與空間復(fù)雜度較低，提高了最大頻繁項(xiàng)集挖掘速率，尤其在處理稠密數(shù)據(jù)集時(shí)具有較好的優(yōu)越性。
- 數(shù)據(jù)挖掘 /
- 頻繁項(xiàng)集 /
- Apriori /
- FP-Growth /
- FP-Tree
Abstract: To solve the problems of Apriori algorithm and FP-Growth algorithm in the process of mining the maximal frequent itemsets, which refer to inefficient operation, high memory consumption, difficulty in adapting to the process of dense datasets, and affecting the time-effectiveness of large data value mining, this paper proposes a maximal frequent itemsets mining algorithm based on adjacency table. The algorithm only needs to traverse the database once and adopts the hash table to store the adjacency table, which reduces the memory consumption. Theoretical analysis and experimental results show that the algorithm has lower time and space complexity and improves the mining rate of maximal frequent itemsets, especially when dealing with dense datasets.
- Data mining /
- Frequent itemsets /
- Apriori /
- FP-Growth /
- FP-Tree

HTML全文

圖 1 頂頭表與FP-Tree

下載: 全尺寸圖片幻燈片

圖 2 基于鄰接表的最大頻繁項(xiàng)集挖掘過(guò)程

下載: 全尺寸圖片幻燈片

圖 3 由數(shù)據(jù)集生成鄰接表

下載: 全尺寸圖片幻燈片

圖 4 處理稀疏與稠密數(shù)據(jù)集不同事務(wù)數(shù)量的效率對(duì)比圖

下載: 全尺寸圖片幻燈片

圖 5 處理稀疏與稠密數(shù)據(jù)集不同支持度計(jì)數(shù)的效率對(duì)比圖

下載: 全尺寸圖片幻燈片

表 1 事務(wù)數(shù)據(jù)庫(kù)

TID	項(xiàng)
T100	B, C, E
T200	F, B
T300	C, A, D
T400	D, B, C, A, E
T500	C, E, D
T600	E, F

下載: 導(dǎo)出CSV

表 2 3種算法的最大頻繁項(xiàng)集挖掘結(jié)果

Apriori	FP-Growth	基于鄰接表的算法	支持度
(A,C:2)	(A,C:2)	(C,A:2)	0.3
(D,A:2)	(A,D:2)	(A,D:2)	0.3
(B,C:2)	(B,C:2)	(B,C:2)	0.3
(E,B:2)	(B,E:2)	(B,E:2)	0.3
(D,C:3)	(D,C:3)	(C,D:3)	0.5
(C,E:3)	(E,C:3)	(C,E:3)	0.5
(D,E:2)	(D,E:2)	(E,D:2)	0.3
(D,A,C:2)	(A,C,D:2)	(C,A,D:2)	0.3
(E,C,B:2)	(B,C,E:2)	(B,C,E:2)	0.3
(D,C,E:2)	(D,C,E:2)	(C,D,E:2)	0.3

下載: 導(dǎo)出CSV

參考文獻(xiàn)(15)

WU Xindong, KUMAR V, QUINLAN J R, et al. Top 10 algorithms in data mining[J]. Knowledge and Information Systems, 2008, 14(1): 1–37. doi: 10.1007/s10115-007-0114-2

FASIH H and SHAHRAKI M H N. Incremental mining maximal frequent patterns from univariate uncertain data[J]. Knowledge-Based Systems, 2018, 152: 40–50. doi: 10.1016/j.knosys.2018.04.001

易彤, 徐寶文, 吳方君. 一種基于FP樹(shù)的挖掘關(guān)聯(lián)規(guī)則的增量更新算法[J]. 計(jì)算機(jī)學(xué)報(bào), 2004, 27(5): 703–710. doi: 10.3321/j.issn:0254-4164.2004.05.017

YI Tong, XU Baowen, and WU Fangjun. A FP-tree based incremental updating algorithm for mining association rules[J]. Chinese Journal of Computers, 2004, 27(5): 703–710. doi: 10.3321/j.issn:0254-4164.2004.05.017

陳安龍, 唐常杰, 陶宏才, 等. 基于極大團(tuán)和FP-Tree的挖掘關(guān)聯(lián)規(guī)則的改進(jìn)算法[J]. 軟件學(xué)報(bào), 2004, 15(8): 1198–1207. doi: 10.13328/j.cnki.jos.2004.08.012

CHEN Anlong, TANG Changjie, TAO Hongcai, et al. An improved algorithm based on maximum clique and FP-Tree for mining association rules[J]. Journal of Software, 2004, 15(8): 1198–1207. doi: 10.13328/j.cnki.jos.2004.08.012

BUI H, VO B, NGUYEN H, et al. A weighted N-list-based method for mining frequent weighted itemsets[J]. Expert Systems with Applications, 2018, 96: 388–405. doi: 10.1016/j.eswa.2017.10.039

AGRAWAL R and SRIKANT R. Fast algorithms for mining association rules in large databases[C]. The 20th International Conference on Very Large Data Bases, San Francisco, 1994: 487–499.

APILETTI D, BARALIS E, CERQUITELLI T, et al. Frequent itemsets mining for big data: A comparative analysis[J]. Big Data Research, 2017, 9: 67–83. doi: 10.1016/j.bdr.2017.06.006

肖波, 徐前方, 藺志青, 等. 可信關(guān)聯(lián)規(guī)則及其基于極大團(tuán)的挖掘算法[J]. 軟件學(xué)報(bào), 2008, 19(10): 2597–2610.

XIAO Bo, XU Qianfang, LIN Zhiqing, et al. Credible association rule and its mining algorithm based on maximum clique[J]. Journal of Software, 2008, 19(10): 2597–2610.

HAN Jiawei, PEI Jian, and YIN Yiwen. Mining frequent patterns without candidate generation[C]. The 2000 ACM SIGMOD International Conference on Management of Data, Dallas, 2000: 1–12. doi: 10.1145/342009.335372.

KARIM R, COCHEZ M, BEYAN O D, et al. Mining maximal frequent patterns in transactional databases and dynamic data streams: A spark-based approach[J]. Information Sciences, 2018, 432: 278–300. doi: 10.1016/j.ins.2017.11.064

吉根林, 楊明, 宋余慶, 等. 最大頻繁項(xiàng)目集的快速更新[J]. 計(jì)算機(jī)學(xué)報(bào), 2005, 28(1): 128–135. doi: 10.3321/j.issn:0254-4164.2005.01.016

JI Genlin, YANG Ming, SONG Yuqing, et al. Fast updating maximum frequent itemsets[J]. Chinese Journal of Computers, 2005, 28(1): 128–135. doi: 10.3321/j.issn:0254-4164.2005.01.016

宋余慶, 朱玉全, 孫志揮, 等. 基于FP-Tree的最大頻繁項(xiàng)目集挖掘及更新算法[J]. 軟件學(xué)報(bào), 2003, 14(9): 1586–1592. doi: 10.13328/j.cnki.jos.2003.09.012

SONG Yuqing, ZHU Yuquan, SUN Zhihui, et al. An algorithm and its updating algorithm based on FP-Tree for mining maximum frequent itemsets[J]. Journal of Software, 2003, 14(9): 1586–1592. doi: 10.13328/j.cnki.jos.2003.09.012

VIJAYARANI S and SHARMILA S. Comparative analysis of association rule mining algorithms[C]. 2016 International Conference on Inventive Computation Technologies, Coimbatore, 2016: 1–6. doi: 10.1109/INVENTIVE.2016.7830203.

LIU Li, YU Shuo, WEI Xiang, et al. An improved Apriori-based algorithm for friends recommendation in microblog[J]. International Journal of Communication Systems, 2018, 31(2): e3453. doi: 10.1002/dac.3453

連志春, 伊鳳新. 一種改進(jìn)的頻繁模式樹(shù)生長(zhǎng)算法[J]. 應(yīng)用科技, 2008, 35(6): 47–51. doi: 10.3969/j.issn.1009-671X.2008.06.012

LIAM Zhichun and YI Fengxin. An improved frequent pattern tree growth algorithm[J]. Applied Science and Technology, 2008, 35(6): 47–51. doi: 10.3969/j.issn.1009-671X.2008.06.012

相關(guān)文章

施引文獻(xiàn)

資源附件(0)

訪問(wèn)統(tǒng)計(jì)