垂直数据格式挖掘频繁项集算法的改进

计算机工程与科学

垂直数据格式挖掘频繁项集算法的改进

邢长征，安维国，王星

（辽宁工程技术大学电子与信息工程学院，辽宁葫芦岛 125105）

收稿日期:2015-12-14 修回日期:2016-03-17 出版日期:2017-07-25 发布日期:2017-07-25
基金资助:
国家自然科学基金(61402212);辽宁省高等学校杰出青年学者成长计划项目(LJQ2015045);辽宁省自然科学基金（2015020098）

An improved frequent itemsets mining

algorithm based on vertical data format

XING Chang-zheng,AN Wei-guo,WANG Xing

(School of Electronic and Information Engineering,Liaoning Technical University,Huludao 125105,China)

Received:2015-12-14 Revised:2016-03-17 Online:2017-07-25 Published:2017-07-25

摘要/Abstract

摘要：

针对现有的基于垂直格式挖掘频繁项集采用正交的方式两两进行比较耗费大量时间和产生的Tid集可能很大浪费存储空间的问题，提出了一种基于三角矩阵和差集的垂直数据格式挖掘频繁项集的挖掘算法。该算法利用差集解决了对稠密数据集进行频繁项集挖掘时的Tid集可能很大的问题，并且利用一种前提方法判断是否有必要连接产生候选频繁k+1项集，减少时间的开销，而且在存储上用三角矩阵的数据结构可以进一步节省存储空间。实验结果表明，本算法大大减少挖掘频繁项集时间和空间内存的开销。

关键词: 频繁项集, 三角矩阵, 差集, 垂直数据格式

Abstract:

The existing vertical format based frequent itemsets mining employs the intersection method to compare two Tid sets, which costs a large amount of time and wastes storage space. Aiming at these problems, we propose a vertical data format based frequent itemsets mining algorithm based on triangular matrix and diffset. The algorithm utilizes the diffset to solve the large number of Tid sets when conducting frequent item mining for dense data sets. A prerequisite method is used to determine whether it is necessary to connect and generate candidate frequent k+1 itemsets, and reduce the cost of time. With the help of the data structure of the triangular matrix on storage can further save storage space. Experimental results show that the algorithm can greatly reduce time cost and space memory overhead for mining frequent itemsets.

Key words: frequent itemsets, triangular matrix, diffset, vertical data format

邢长征，安维国，王星. 垂直数据格式挖掘频繁项集算法的改进[J]. 计算机工程与科学.

XING Chang-zheng,AN Wei-guo,WANG Xing.

An improved frequent itemsets mining

algorithm based on vertical data format

[J]. Computer Engineering & Science.

[1]	文凯, 耿小海, 朱璐伟, 许萌萌, . 基于AO算法的数据流频繁项集挖掘[J]. 计算机工程与科学, 2020, 42(12): 2259-2264.
[2]	廖纪勇，吴晟，刘爱莲. 基于布尔矩阵约简的Apriori算法改进研究[J]. 计算机工程与科学, 2019, 41(12): 2231-2238.
[3]	肖文，胡娟. 稀疏数据频繁项集挖掘算法研究综述[J]. 计算机工程与科学, 2019, 41(05): 780-787.
[4]	熊臻,岳勤. 一类周期为偶数的二元序列的自相关值[J]. 计算机工程与科学, 2018, 40(09): 1572-1578.
[5]	徐春，李广原，王玄，田换. 一种基于倒排索引树的增量更新关联挖掘算法[J]. J4, 2016, 38(05): 1039-1045.
[6]	王卫平,周忠眉,郑艺峰. 基于支持度和增比率的改进关联分类算法[J]. J4, 2016, 38(02): 370-375.
[7]	张晓，王红. 一种改进的基于大数据集的混合聚类算法[J]. J4, 2015, 37(09): 1621-1626.
[8]	胡健，吴毛毛. 一种改进的数据流最大频繁项集挖掘算法[J]. J4, 2014, 36(05): 963-970.
[9]	曹波伟，薛青. 面向装备作战仿真数据流的改进型频繁项集搜索方法研究[J]. J4, 2013, 35(6): 152-155.
[10]	崔贯勋，李梁，王柯柯，倪伟，苟光磊. 基于改进Apriori算法的入侵检测系统研究[J]. J4, 2011, 33(4): 40-44.
[11]	刘彩虹1,刘强2,李爱平3. 基于向量内积的非频繁项挖掘算法研究[J]. J4, 2011, 33(2): 92-96.
[12]	李国雁[1,2] 沈夏炯[1]. 一种基于矩阵的多值关联规则的挖掘算法[J]. J4, 2008, 30(5): 72-74.
[13]	王永恒杨树强贾焰. 海量文本数据库中的高效并行频繁项集挖掘方法[J]. J4, 2007, 29(9): 110-113.
[14]	李新良[1,2] 陈湘涛[1]. 数据挖掘中关联规则算法的研究[J]. J4, 2007, 29(12): 111-113.
[15]	梁碧珍[1,2] 陆月然[1,3] 秦亮曦[1]. 一种改进的基于FP-树的最大目标频繁项集挖掘算法[J]. J4, 2007, 29(10): 70-72.