基于二进制编码的Apriori改进算法

Improved Apriori algorithm based on binary encoding

Apriori算法在挖掘频繁项集时需要多次扫描数据库,这样会因为频繁的IO操作而导致效率低下。为了改进算法的执行效率,提出BE-Apriori(binary encoded Apriori)算法,其充分利用了二进制数相比编程语言中各种数据结构在内存及运算速度上的优势,对事务记录进行二进制编码后加载到内存,然后利用等效的二进制数之间运算代替集合之间的运算。分析了算法性能,并利用UCI数据集中的毒蘑菇数据对BE-Apriori算法进行实验验证。结果表明BE-Apriori可以正确挖掘频繁项集,并且相比Apriori算法有着更好的性能。

Apriori algorithm has to scan the database multiple times when mining frequent item sets,resulting in inefficiencies because of frequent IO operations.To improve efficiency of Apriori algorithm,this paper proposed BE-Apriori algorithm,which made full use of the advantages of binary numbers compared to the memory usage and computational speed of various data structures in programming languages.It loaded the transaction record with binary encoding into memory through,then translated the set operations into the equivalent binary number operations.The analysis of algorithm performance and the experimental result using the poisonous mushroom data in the UCI data show that BE-Apriori can correctly mine frequent itemsets and has better performance than the original Apriori algorithm.