一种基于倒排索引树的增量更新关联挖掘算法

An incremental updating association rule mining algorithm based on inverted index tree

增量更新关联规则挖掘主要解决事务数据库中交易记录不断更新和最小支持度发生变化时关联规则的维护问题。针对目前诸多增量更新关联规则挖掘算法存在效率低、计算成本高、规则难以维护等问题,提出一种基于倒排索引树的增量更新关联挖掘算法。该算法有效地将倒排索引技术与树型结构相结合,使得交易数据库中的数据不断更新和最小支持度随应用环境不同而不断改变时,以实现无需扫描原始交易数据库和不产生候选项集的情况下生成频繁项集。实验结果表明,该算法只需占用较小的存储空间、且检索项集的效率较高,能高效地解决增量更新关联规则难以维护的问题。

The primary mission of incremental updating association rule mining is to solve the prob- lem of the maintenance of the association rules, when transaction records are updated constantly and minimum support is changed in the online database. Given that many incremental update association rule mining algorithms have many problems, such as low efficiency and high computation cost, as well as dif- ficult maintenance of the association rules, we propose an efficient algorithm for incremental updating association mining based on inverted index tree. The algorithm effectively combines the inverted index and the tree structure, so that the data in the transaction database is updated constantly with time and the minimum support degree is changed continuously with the application environment. Frequent item sets are generated without scanning the original transaction database and without generating candidate i- tem sets. Experimental results show that the proposed algorithm can effectively solve the problem of in- cremental updating association rules with less memory space and higher efficiency.