北京化工大学博士学位论文频繁模式挖掘和动态维护的理论与方法研究姓名：林晓勇申请学位级别：博士专业：控制理论与控制工程指导教师：朱群雄20080529频繁模式挖掘和动态维护的理论与方法研究摘要频繁模式挖掘是许多数据挖掘任务中的核心问题，有着广泛的应用。而现有的挖掘方法普遍存在多次扫描数据库或重复遍历复杂数据结构的问题。本文以频繁模式挖掘为切入点，系统地研究了频繁模式／效用频繁模式挖掘和动态维护的理论与方法。主要研究内容如下：l基于分享和继承策略的挖掘理论与方法从频繁模式构成的搜索空间入手，提出了贯穿全文的分享和继承挖掘策略。通过引进分享表结构，避免了由绝对的分而治之带来的重复遍历与计数，提高了挖掘效率；同时，在挖掘过程中根据数据集的局部子集特性动态地调整挖掘策略，给出了提高时间效率与节省空间消耗的优化方法。2效用频繁模式挖掘从分析现有频繁模式挖掘任务的局限性入手，提出了效用频繁模式挖掘模型。该模型同时考虑各项出现的次数及其对目标模型的不同影响程度，能够更好地处理实际的挖掘应用；拓展了频繁模式挖掘的任务。3频繁等价模式挖掘分析了频繁模式压缩表示的方法，提出频繁等价模式的概念和挖掘方法，它将频繁模式中具有等价关系的项集中在一个子空间内，在不丢失任何信息的同时极大地减少了频繁模式的冗余。通过与频繁闭T合模式比较，表明其拥有更高的压缩率。4频繁模式的交互挖掘提出了基于分享表结构的交互挖掘方法。该方法可与分享和继承策略无缝地集成在一个框架下。通过尽量避免复杂数据结构的重建和充分利用已有的计算结果，极大地提升了挖掘的效率。5频繁模式的增量挖掘从分析增量挖掘机制入手，提出了基于分享和继承策略的增量挖掘方法。该方法可完全不依赖先前的挖掘方法，减少了大量的原库检索和计算，较好地解决了数据库发生变化下的频繁模式维护问题。6频繁模式在关联规则挖掘中的应用从分析关联规则挖掘入手，描述了频繁模式在关联规则挖掘中的作用；实现了规则生成算法，能够快速地由频繁模式生成规则。通过在数据集上的测试结果，验证了频繁模式挖掘的实际应用价值。本文还将交互挖掘与增量挖掘扩展到效用频繁模式挖掘中去，有效地解决了效用频繁模式的交互挖掘与增量挖掘问题。通过在不同数据集中与已有的各类算法做比较，证明了分享和继承策略的高效性，能较好地解决频繁模式／效用频繁模式挖掘中普遍存在重复扫描和遍历问题，提升了挖掘的效率。关键词：数据挖掘，频繁模式，效用频繁模式，频繁等价模式，动态维护MININGDYNAMICMAINTENANCEFREQUENTof(utility)frequentoNABSTRACTMiningpattems，theresearch．Mostgro、Ⅳth印proache伍cientlyRESEARCHANDOFPATTERNSmlesmining，hasadoptpattemdoescandidatetmVelingf-requentpattemsminingdynamicmaintenancebasedtheinheritingstrategy，basedtheoIMispattems．BasedandproVidesoff．requentassociationbeenstudiedpopularlyindatastudiesa疳equentwhichbnnggeneration．HoweVer，repeatedlyscanningdatabasestillhigh，andVerylittleworkhasdonemined．Based仔equentmining，thispapermining．Themainfollowing．1ResearchsharingstrategyThelatticeprI)poseddiscoVersharetablestllJcture，thesbaringwaymostresultsf．rompreViousprocessinsteadseparatingcurrentnotcoststructurescontentstocoreonareainfomationh培hersumcientlyfbmdistinctiVely，therebydramaticallyreducingdatabaseVariousoptimizationusedefj[iciency．UtilityfrequentpattemsminingdiscoVersconsideringdif苗朗．entofutility行equentpattemmodelfindcombinationitemscontinuallyhighsatisfiestheandmining．de矗nitionpattems，acompressi