基于频繁模式挖掘知识库的增量式更新算法的研究.pdf

V01．6No．10 2006 第6卷第10期2006年5月 科学技术与工程 May Science and 1671—1815(2006)10—1372·04 TechnologyEngineering ⑥2006Sci．Tech．Engng． 计算机技术 基于频繁模式挖掘知识库的增量式 更新算法的研究 何宏1’2 肖建华1 肖伟平1 (湖南工程学院计算机科学系1，湘潭411101；湘潭大学信息工程学院2，湘潭411105) 识数据库中保留的频繁模式树，减少了对原挖掘数据库和更新后的数据库的扫描次数，提高了算法的运行效率。 关键词关联规则 频繁模式 增量更新 条件模式库 中图法分类号TP311．12；文献标识码A 关联规则反映了数据库中数据项目之间有趣 的关联关系，而其中发现频繁项目集是关联规则挖 持度minsup(minimum 掘应用中的关键技术和步骤。关于频繁项目集的 conf(minimum 挖掘算法研究，人们对此进行了大量的工作，其中 库中关联规则的更新问题。这些算法都没有从挖 掘知识库的信息总体角度考虑问题。针对这些问 以R．Agrawal¨,21等人提出的Apriori、AprioriTid∞o等 算法最具有影响力和代表性。而这些算法的提出 题，本文提出了IUA—FPKB新算法，可以处理最小支 都是在挖掘数据库和最小支持度不变的条件下进 持度发生变化或挖掘数据库更新时的情况。该算 行的。但实际中，遇到的情况可能是：随着时间的 法利用FP—tree算法的挖掘知识库信息即原数据库 推移，挖掘数据库的规模可能不断膨胀或需要删除 挖掘时产生的频繁模式树，建立条件模式库，避免 一部分记录，或者需要对最小支持度进行调整从而 了候选项目集的数量庞大和多次扫描挖掘数据库 逐步聚集到我们感兴趣的频繁项目集上。因而如 的问题。条件模式库的建立给关联规则的增量式 何从数据发生变动后的数据库中高效地对已经推 更新提供了有效的解决途径。 导出的关联规则进行更新具有非常重要的应用价 值，这就是所谓的增量式挖掘关联规则的问题。但 1 FP-tree算法 目前的增量式更新关联规则挖掘算法存在多次读 1．1频繁模式树FP-tree的结构及其构造方法陋1 取未变动之前的原始数据库内容及产生大量的候 频繁模式树FP—tree是一种满足以下定义的树 选项目集过于庞大等问题。如IUARHo算法，用于 结构。 解决元组数和最小支持度发生变化时关联规则增 (1)由一个标记为“root”的根节点，一组作为根 量式更新问题，该算法是通过修正候选项目集来进 节点的子节点的项前缀子树，和一个高频项头表 2006年1月1813收到 湖南省教育厅重点项目(04A011)组成。 资助 (2)项前缀子树中的每个节点由3个域组成： 第一作者简介：何宏(197l一)，男，硕士研究生，研究方向：数据 挖掘。E—mail：hehong@hnie．edu．cn；hhwjj710308@sina．tom。 保存此节点所表示的项，计数值保存从此节点所在