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

A Frequent Item Set Mining Method Based on Inverted Index

针对频繁项集挖掘算法中多次扫描数据库、生成大量无效频繁项集的问题,提出一种基于倒排索引和二维数组的挖掘算法。通过一次扫描数据库建立包含事务的倒排索引,解决多次扫描数据库的问题。在二维数组存储候选频繁项集时,引入标志位约束,避免产生大量无效的频繁项集。与其他算法在不同规模的数据集上进行性能比较,发现算法在数据集超过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.