增量数据挖掘初探

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

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

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

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

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

5、库为例介绍算法的实际应用.1.2数据挖掘的基本概念与定义项（item）是一个文字，在交易数据库屮，它可以代表商品；分类时，它可以代表属性的值.设I={ipi2<-ira}为项的全集,D={7],錢,・・・7；}为事务数据库,其中每个事务包含I中的一个子集.支持度计数：项集Xel的支持度是指，事务数据库中，包含X的事务的个数.支持度：项集X的支持度计数等于X的支持度计数除以事务数据库屮事务的总条数.给定一个支持度阈值minsup,若X的支持度

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

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