增量数据挖掘初探

《增量数据挖掘初探》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、陕西理工学院毕业论文增量数据挖掘初探赵浩磊(陕西理工学院数学系信息与计算科学专业2003级3班，陕西　汉中　723001)指导教师周涛[摘要]本文介绍了数据挖掘领域中的增量频繁模式挖掘，在介绍了频繁项集挖掘与增量频繁模式挖掘的一搬概念后，文章又相继介绍了了三种由相关研究人员提出的增量频繁模式挖掘算法，并分析了这些算法的优点与不足，并且在分析的同时发现了IUAMAR算法的严重缺陷，指出它是不可靠的算法．最后，文章根据火锅销售数据挖掘的现实情况，结合其中的两种算法的优点，介绍了销售数据挖掘的实现。[关键词]数据挖掘；关联规则；频繁项集；增量挖掘算法⒈引言1.1问题的提出近年来，信息技术

2、的广泛应用提出了对信息处理能力的更高要求，老式的数据统计方法面对海量的数据以及全新的数据处理概念显得力不从心，在这种背景下,数据挖掘技术应运而生，并成为研究的热点．数据挖掘就是从大量的、不完全的、有噪声的、模糊的、原始的数据中提取隐含在其中人们事先不知道也不可能直接获取的，但却非常有潜在价值的信息，它们包括关联规则挖掘、特征规则、分类规则等．其中关联规则挖掘是发现大量数据中项与项之间有趣的关联或联系，它是数据挖掘领域中的一个热闹课题，得到了业界广泛的研究．其中:Apriori算法是最早提出的也是最经典的算法，后来又出现了另一个高效的算法―FP-Growth,它解决了Apriori算

3、法中的一个最大缺陷但它本身的实现却比较困难．之后，广大学者就以上述算法为蓝本进行改进，使之更加有效，更加容易实现，并将其融入到各种数据处理系统中，使之发挥出自己巨大的作用．但是以上的研究都是以假设数据库为静态的前提的．事实上，在很多领域数据库都处在不断地更新（增加、删除、修改）中，所用的支持度阈值也会不断改变，并且动态数据库往往要求对用户的查寻指令做出快速地反应．因此，提高动态数据库中关联规则发现的效率便成了一个重要的问题．进行增量数据挖掘最直接的方法就是对更新后的数据库进行一次关联规则挖掘，但这样显然有很大的开销，而且随着时间的增长、数据库规模的不断增长，这样的方法也显得不现实．

4、如何利用原始数据库的挖掘结果来更新频繁项集便成了增量频繁模式挖掘研究的起点．虽然目前频繁模式的增量挖掘领域研究地还不很充分，但是广大研究人员对它们所做出的改进还是值得肯定的，针对阈值不变的增量频繁模式挖掘研究总体分为两大类：第一种的分别挖掘出原始数据库和更新数据库中的频繁项集，然后使用某种规则对其进行更新，这种算法的特点是可以最大利用现有的关联规则挖掘算法，但是频繁项集的更新规则很重要，规则制定或实现的时候一但发生问题，将对结果的分析产生致命影响．第二种的基于散列的方法，这种方法不需要添加复杂的更新规则，实现起来也非常容易，结果可靠性高，但是它将占用较高的系统资源．本文将带介绍、分

5、析几种不同类型的算法，然后以一销售数据库为例介绍算法的实际应用．1.2数据挖掘的基本概念与定义第18页共18页陕西理工学院毕业论文项（item）是一个文字，在交易数据库中，它可以代表商品；分类时，它可以代表属性的值．设为项的全集，为事务数据库，其中每个事务包含Ｉ中的一个子集．支持度计数：项集的支持度是指，事务数据库中，包含Ｘ的事务的个数．　支持度：项集Ｘ的支持度计数等于Ｘ的支持度计数除以事务数据库中事务的总条数．给定一个支持度阈值minsup，若Ｘ的支持度minsup，则Ｘ是频繁的，若Ｘ包含有k个项，则称X为频繁k-项集[1]．　Apriori性质[1]：若一个项集是频繁的，则它的

6、所有子集也是频繁的；同样，如果一个项集有不频繁的子集，则这个项集就不可能是频繁的．⒈融合原始、增量数据库频繁模式的算法前面已经介绍过，基于融合思想的算法需要用基本的数据挖掘算法分别挖掘出原始、增量数据库中的频繁项集，然后对它们进行融合．融合的时候需要以下三大结论的支持：设K是项集，DB为原始数据库，db为增量数据库，NDB为更新后的数据库．1．K在DB中是频繁的，在db中也是频繁的，则K在NDB中是频繁的．2．K在DB中是不频繁的，在db中也是不频繁的，则K在NDB中是不频繁的．3．K只在DB或db其中之一中频繁，则K在NDB中是否频繁是不确定的[2]．其中DB是原始数据库，db是

7、增量数据库，K是频繁项集，NDB是更新后的数据库．以上结论很容易根据频繁项集的定义得到证明．有了上面的理论，很多学者对此思想产生的算法进行了一些研究、改进，比如：只需要挖掘出原始数据库中的频繁项集，而用其它方法处理增量数据库．如：何宏，肖建华，肖伟平提出了IUAMAR算法[3]，该算法可以处理对挖掘数据库进行追加的情况，利用挖掘知识库信息即原数据库挖掘出来的高频项目集和最小非高频繁项目集来产生新候选项目集，避免了类似Apriori的算法中候选项目集的数量庞大的问题．下