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

An improved frequent itemsets mining algorithm based on vertical data format

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

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.