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

Improved binary encoding Apriori algorithm based on Hash table

作　　者：王洋[1] 贺春林[2] 姜玥[1] 崔梦天 WANG Yang;HE Chun-lin;JIANG Yue;CUI Meng-tian(The Key Laboratory for Computer Systems of State Ethnic Affairs Commission,Southwest Minzu University,Chengdu 610041,China;School of Computer Science,China West Normal University,Nanchong 637000,China)

机构地区：[1]西南民族大学计算机系统国家民委重点实验室,四川成都610041 [2]西华师范大学计算机学院,四川南充637000

出　　处：《西南民族大学学报（自然科学版）》2020年第6期623-630,共8页Journal of Southwest Minzu University(Natural Science Edition)

基　　金：国家自然科学基金项目(12050410248);2020年中央高校优秀学生培养工程项目(2020YYXS63);国家留学基金委(202008510078);四川省科技计划项目(NO.21GJHZ0256)。

摘　　要：针对关联规则中Apriori算法反复扫描数据库以及运算效率低的问题,提出了一种基于Hash表的二进制编码改进的Apriori算法HBE-Apriori(Hashed Binary Encode).该算法通过Hash表保存事务数据库,因此只需要扫描一次数据库,从而避免了传统Apriori算法反复扫描数据库带来的时间消耗;通过引入与运算对项集二进制编码进行运算,以达到了节省了存储空间的效果,同时提升了算法的执行效率.论文最后,通过举例和实验分析对比,证明了所提出的算法具有可行性和更好地运算效率.An improved Apriori algorithm HBE-Apriori(Hashed Binary Encode)based on hash table is proposed to solve the problem of repeatedly scanning database and low efficiency of Apriori algorithm in association rules in this paper.The algorithm saves the transaction database through Hash table so that it only needs to scan the database once to avoid the time consumption caused by the traditional Apriori algorithm repeatedly scanning the database;and the algorithm uses AND operation to calculate the binary code of item set,which can save the storage space and improve the efficiency of the algorithm.The example and experiments prove the algorithm proposed in the paper is feasible and efficient.

关 键 词：关联规则 APRIORI算法 HASH表 二进制编码 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]