基于分布式倒排索引的频繁项集挖掘

Frequent Itemset Mining Based on Distributed Inverted Index

频繁项集挖掘是关联规则挖掘中的核心,其直接影响了频繁项集的产生效率。针对Eclat算法在挖掘海量数据中的频繁项集时存在的内存和计算资源不足等问题,文中设计了通过分布式倒排索引实现频繁项集挖掘的Dii Eclat算法。倒排索引等同于将数据垂直分布,按事务编号的不同将倒排索引分布式地存储在不同的索引节点上,每个节点上的事务分别做交集,最后由检索代理合并交集结果。在chess、mushroom、T40I10D100K和T10I4D100K数据集上,对Dii Eclat、Eclat、Diffset等算法进行了实验对比。结果表明,给出的Dii Eclat算法通过事务集合垂直划分和并行计算,解决了数据挖掘过程中求交集运算效率低下和内存不足等问题,算法高效、可扩展。

Mining frequent itemsets is the core of mining association roles, which directly affects the efficiency of generating frequent iterasets. Eclat algorithm exists issues of insufficient memory and computing resource when mining frequent itemset of massive data. The DiiEclat algorithm is proposed for mining frequent itemsets through distributed inverted index. Inverted index is equal to the vertical distribution of the data,and according to the number of different transactions inverted index will be distributed on different index nodes,each node calculates the intersection of transactions on itself, the results of the intersection merged by the retrieval agent. The execution time of DiiEclat,Eclat,Diffset and Eclat_opt is compared in four datasets such as chess,mushroom ,T40110D100K and TI014D100K. The experimental results show that DiiEclat is given to improve efficiency of intersection operation through the vertical division of the transaction sets and parallel computing, and it is efficient and scalable.