基于前缀项集的Apriori算法改进-计算机应用与软件.PDFVIP

第３４卷第２期　　　 计算机应用与软件 Ｖｏｌ３４Ｎｏ．２ ２０１７年２月　　 ＣｏｍｐｕｔｅｒＡｐｐｌｉｃａｔｉｏｎｓａｎｄＳｏｆｔｗａｒｅ Ｆｅｂ．２０１７ 基于前缀项集的Ａｐｒｉｏｒｉ算法改进 于守健　周羿阳 （东华大学计算机学院　上海２０１６００） 摘　要　　关联规则的挖掘是数据挖掘中一个重要内容，主要目的是找到事务数据库中的有趣的模式。Ａｐｒｉｏｒｉ 算法是关联规则挖掘的最经典算法之一，但是它本身存在着效率上的瓶颈。在深入了解Ａｐｒｉｏｒｉ算法前提下，提 出基于前缀项集的候选集存储结构，并利用哈希表在快速查找上的优势，大大提高了经典Ａｐｒｉｏｒｉ算法在连接步 骤和剪枝步骤中的效率。实验证明改进后的Ａｐｒｉｏｒｉ算法在一定支持度下比经典Ａｐｒｉｏｒｉ算法有着更大的效率优 势，并且支持度越小时提升效率越大。 关键词　　数据挖掘　Ａｐｒｉｏｒｉ算法　前缀项集　关联规则　哈希表 中图分类号　ＴＰ３　　　　文献标识码　Ａ　　　　ＤＯＩ：１０．３９６９／ｊ．ｉｓｓｎ．１０００３８６ｘ．２０１７．０２．０５２ ＴＨＥＩＭＰＲＯＶＥＭＥＮＴＯＦＡＰＲＩＯＲＩＡＬＧＯＲＩＴＨＭＢＡＳＥＤＯＮＰＲＥＦＩＸＥＤＩＴＥＭＳＥＴ ＹｕＳｈｏｕｊｉａｎ　ＺｈｏｕＹｉｙａｎｇ （ＣｏｌｌｅｇｅｏｆＣｏｍｐｕｔｅｒＳｃｉｅｎｃｅａｎｄＴｅｃｈｎｏｌｏｇｙ，ＤｏｎｇｈｕａＵｎｉｖｅｒｓｉｔｙ，Ｓｈａｎｇｈａｉ２０１６００，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ　　Ｔｈｅｍｉｎｉｎｇｏｆａｓｓｏｃｉａｔｉｏｎｒｕｌｅｉｓａｎｉｍｐｏｒｔａｎｔｍｅｔｈｏｄｆｏｒｄｉｓｃｏｖｅｒｉｎｇｉｎｔｅｒｅｓｔｉｎｇｒｅｌａｔｉｏｎｓｂｅｔｗｅｅｎｖａｒｉａｂｌｅｓ ｉｎｌａｒｇｅｄａｔａｂａｓｅｓ．Ａｐｒｉｏｒｉａｌｇｏｒｉｔｈｍｉｓｏｎｅｏｆｔｈｅｍｏｓｔｃｌａｓｓｉｃａｌａｌｇｏｒｉｔｈｍｓｏｆａｓｓｏｃｉａｔｉｏｎｒｕｌｅｓ，ｂｕｔｉｔｈａｓｂｏｔｔｌｅｎｅｃｋｉｎ ｅｆｆｉｃｉｅｎｃｙ．Ｔｈｕｓ，ａｃａｎｄｉｄａｔｅｉｔｅｍｓｅｔｓｔｏｒａｇｅｓｔｒｕｃｔｕｒｅｂａｓｅｄｏｎｐｒｅｆｉｘｅｄｉｔｅｍｓｅｔｉｓｐｒｏｐｏｓｅｄｗｉｔｈｔｈｅｈｅｌｐｏｆｔｈｅｑｕｉｃｋ ｓｅａｒｃｈｏｆｈａｓｈｍａｐ，ａｎｄｔｈｅｅｆｆｉｃｉｅｎｃｙｏｆｃｌａｓｓｉｃａｌＡｐｒｉｏｒｉａｌｇｏｒｉｔｈｍｉｎｃｏｎｎｅｃｔｉｎｇａｎｄｐｒｕｎｉｎｇｓｔｅｐｈａｓｂｅｅｎｉｍｐｒｏｖｅｄ ｇｒｅａｔｌｙ．ＴｈｅｅｘｐｅｒｉｍｅｎｔｓｓｈｏｗｔｈａｔｔｈｅｉｍｐｒｏｖｅｄＡｐｒｉｏｒｉａｌｇｏｒｉｔｈｍｄｏｅｓｂｅｔｔｅｒｉｎｅｆｆｉｃｉｅｎｃｙｔｈａｎｔｈｅｃｌａｓｓｉｃａｌＡｐｒｉｏｒｉ ａｌｇｏｒｉｔｈｍｉｎｃｅｒｔａｉｎｄｅｇｒｅｅｓｓｕｐｐｏｒｔ，ａｎｄｔｈｅｓｍａｌｌｅｒｓｕｐｐｏｒｔ，ｔｈｅｂｅｔｔｅｒｅｆｆｉｃｉｅｎｃｙ． Ｋｅｙｗｏｒｄｓ　　Ｄａｔａｍｉｎｉｎｇ　Ａｐｒｉｏｒｉａｌｇｏｒｉｔｈｍ　Ｐｒｅｆｉｘｅｄｉｔｅｍｓｅｔ　Ａｓｓｏｃｉａｔｉｏｎｒｕｌｅｓ　Ｈａｓｈｍａｐ 近年来也出现了针对不同方面的的算法改进方式。 ０　引　言 Ｚｈａｎｇ等［４］提出了基于分类的改进的Ａｐｒｉｏｒｉ算法，在 效率上有一定程度的提升。Ｊｉａ等［５］从事务数据库划 随着计算机技术在各个行业的迅猛发展，各行业 分和动态项集统计的角度对经典 Ａｐｒｉｏｒｉ算法进行改 所产生的数据也越来越多，但是如何在这些海量数据 进。Ｌｉｕ等［６］在研究煤炭隐患数据时提出了数据库矩 中获取有价值的信息也成了一个新的问题。数据挖 阵化的方法来进一步提升算法效率。Ｗａｎｇ等［７］提出 掘，即数据知识发现，正是在这个大背景下应运而生。 一种优化的方法来