一种基于倒排索引的频繁项集挖掘方法  

A Frequent Item Set Mining Method Based on Inverted Index

作　　者：贾丽波 姜晓明[1] 叶青[1] 陈占芳[1] JIA Libo;JIANG Xiaoming;YE Qing;CHEN Zhanfang(School of Computer Science and Technology,Changchun University of Science and Technology,Changchun 130022)

机构地区：[1]长春理工大学计算机科学技术学院,长春130022

出　　处：《长春理工大学学报（自然科学版）》2019年第2期117-119,124,共4页Journal of Changchun University of Science and Technology(Natural Science Edition)

基　　金：吉林省科技厅项目(KYC-JC-XM-2018-03);吉林省教育厅科技攻关项目(KYC-JC-XM-2016-021)

摘　　要：针对频繁项集挖掘算法中多次扫描数据库、生成大量无效频繁项集的问题,提出一种基于倒排索引和二维数组的挖掘算法。通过一次扫描数据库建立包含事务的倒排索引,解决多次扫描数据库的问题。在二维数组存储候选频繁项集时,引入标志位约束,避免产生大量无效的频繁项集。与其他算法在不同规模的数据集上进行性能比较,发现算法在数据集超过25万时执行效率优于其他算法。通过实验验证了所提出算法的高效性和可行性。In mining algorithm for frequent itemsets with repeatedly scanning database and mining result itemsets are not frequent. In this paper,a new mining algorithm is developed based on inverted index and two-dimensional array. The problem of multiple scans of the database is solved by creating an inverted index with transaction by scanning the database once. When a two-dimensional array stores candidate frequent itemsets,a flag bit constraint is introduced to avoid generating a large number of invalid frequent itemsets. Compared with other algorithms on different scale data sets,it is found that the algorithm performs better than other algorithms when the data set exceeds 250,000. The results from experiments shows that the proposed algorithm is efficient and feasible.

关 键 词：频繁项集挖掘 倒排索引 二维数组 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]