基于剪枝优化与索引求交的改进Eclat算法

An Improved Eclat Algorithm Based on Pruning Optimization and Indexing Intersection

摘要: 针对现有Eclat算法中普遍存在的候选集规模大、求交效率低的问题，提出了基于剪枝优化和索引求交的改进Eclat算法。首先根据频繁集的性质采用预剪枝和后剪枝相结合的候选集优化策略，即利用预剪枝技术裁剪待连接的项集数量以减少项集连接操作，同时利用先验性质对连接后的项集进行后剪枝处理；接着提出了一种基于事务索引的布尔数组求交方法，即通过将事务标识作为索引来设置并检索布尔数组，以获得项集支持度计数；最后通过设计对比实验，在经典数据集上测试该方法的有效性。实验表明，通过该方法能够有效压缩候选集规模，改善求交计算效率，特别是在支持度阈值小、事务数规模大的情况下，算法的运行效率得到了明显的提升。

Abstract: In view of the problem of large number of candidate sets and low intersecting efficiency in the existing Eclat algorithm, an improved Eclat algorithm based on pruning optimization and index intersection is proposed. First, according to the properties of frequent itemsets, a candidate set optimization strategy based on pre pruning and post pruning is adopted, and that is to use pre pruning technology to tailor the number of itemsets to be linked to reduce itemset join operations, and use the transcendental property to prune the linked itemsets. Then a Boolean array intersection method based on transaction index is proposed, that is, to set and retrieve Boolean arrays by using the transaction identifier as an index to obtain the support count of the item set. Finally, the effectiveness of the method is tested on the classical dataset by designing contrast experiments. Experiments show that this method can effectively compress the size of the candidate sets and improve the efficiency of intersection calculation, especially in the case of small support threshold and large number of transactions, and the efficiency of the algorithm has been greatly improved.