一种增量式频繁模式增长数据挖掘方法

摘要

本发明涉及一种增量式频繁模式增长数据挖掘方法，包括1)将原数据库分成多个数据集，对每个数据集中各项的支持度计数进行并行计算；2)将原数据库中的数据进行分组，构建局部的频繁模式树，通过递归过程提取各局部的频繁项集；3)将各局部的频繁项集进行整合；4)更新阈值，对原数据库执行在新阈值下的支持度计数；5)将局部频繁模式树更新，挖掘新阈值下原数据库的频繁项集；6)新增数据集得到新数据库，挖掘新阈值下原数据库的强频繁项集和新增的频繁项集。与现有技术相比，本发明利用原有的频繁数据项集及频繁模式树，只需对新增数据集进行扫描即可获取新的频繁项集，不仅同时解决了阈值变化和数据库增加两种问题，还大大提高了效率。

说明书

技术领域

本发明涉及数据挖掘技术领域，尤其是涉及一种增量式频繁模式增长数据挖掘方法。 

背景技术

数据挖掘是指从大量数据中寻找出隐含的、有潜在价值的信息的过程。随着信息技术的飞速发展，医疗、互联网等各个领域产生的数据量不断增加。海量数据下隐藏的高价值知识使得数据分析的重要性日益突显。然而，由于数据量过大，使用传统的数据挖掘方法已经无法满足海量级别信息的分析处理需求，给有效利用这些数据带来了困难。关联规则挖掘是近年来数据挖掘领域中，最活跃且最为广泛应用的研究方向之一。关联规则挖掘的最初目的是，商家从大量的消费记录中，寻找顾客所购商品的相关性，从而更好地指导销售策略的制定。 

目前，传统关联规则挖掘算法分为三大类，分别是Apriori算法、闭合频繁项挖掘和频繁模式增长算法。就算法的原理来看，Apriori算法需要重复多次扫描外存中的数据以获取频繁项集，因此I/O负载高、算法的执行性能差。闭合频繁项挖掘是对Apriori算法的改进，只有在处理特定类型数据时能减少扫描次数，效率依旧不高。增量式频繁模式增长算法仅通过2次扫描就能将所需的数据信息收集并压缩至特殊的数据结构——频繁模式树，减少了在输入输出上花费的时间，使得算法效率得到很大提升。面向海量数据的数据挖掘一般有三种思路：抽样、集成及MapReduce。从海量数据中抽样，能够迅速构建数据挖掘模型，但抽样可能导致结果出现偏差；集成方法将整个数据划分为多个子集，分别运算，最后合并；MapReduce基于云计算平台，用于海量级别数据的并行处理。目前，基于增量式频繁模式增长数据挖掘方法仅能解决单一问题，如最小支持度阈值发生改变或数据库内容更新问题。 

发明内容

本发明的目的就是为了克服上述现有技术存在的缺陷而提供一种增量式频繁模式增长数据挖掘方法，用于在非静态数据库及动态阈值下，对海量数据进行快速挖掘。 

本发明的目的可以通过以下技术方案来实现：一种增量式频繁模式增长数据挖掘方法，其特征在于，包括以下步骤： 

(1)将原数据库分成多个数据集，对每个数据集中各项的支持度计数进行并行计算，去除支持度低于阈值的非频繁项，并对频繁项按支持度降序排序，依据排序后的频繁项列表对数据进行分组，并且对事务内的项进行排序； 

(2)读取分组列表和步骤(1)所述的数据集，将原数据库中的数据进行分组，构建局部的频繁模式树，通过递归过程提取各局部的频繁项集； 

(3)将各局部的频繁项集进行整合，得到原数据库的完整的频繁项集； 

(4)阈值重置得到新阈值，将原数据库分成多个数据集，对每个数据集中各项的支持度计数进行并行计算，去除支持度低于新阈值的非频繁项，并对频繁项按支持度降序排序，依据排序后的频繁项列表对数据进行分组，并且对事务内的项进行排序； 

(5)将步骤(2)得到的局部频繁模式树进行更新，增添新节点或删除部分原节点，从这些临时的频繁模式树中挖掘新阈值下原数据库的频繁项集； 

(6)对原数据库增加新数据集得到新数据库，扫描新增的数据集，更新频繁模式树，求出新阈值下原数据库的强频繁项集及新增数据集的频繁项集； 

(7)将新阈值下原数据库的强频繁项集和新增的频繁项集进行整合，得到新阈值下新数据库的频繁项集。 

步骤(5)所述的挖掘新阈值下原数据库的频繁项集具体包括以下步骤： 

11)计算L_Δ1＝L₁′-L₁，式中，L₁′是新阈值下原数据库的频繁1-项集，L₁是原阈值下原数据库的频繁1-项集； 

12)判断差值L_Δ1是否为空集，是则执行步骤14)，否则执行步骤13)： 

13)以差值L_Δ1更新频繁模式树FP-tree，通过更新后的频繁模式树FP-tree′挖掘新阈值下原数据库的频繁项集L′，挖掘结束； 

14)令新阈值下原数据库的频繁项集L′为原数据库原阈值下的频繁项集L，频繁模式树FP-tree′＝FP-tree。 

实施步骤(6)所述的挖掘新阈值下数据集的频繁项集具体包括以下步骤： 

21)计算L_Δ2＝L_DP1+L_dP1-L₁，式中，L_DP1是新阈值下原数据库的强频繁1-项集，L_dP1是新阈值下新增数据集的强频繁1-项集，L₁是原阈值下原数据库的频繁1-项集； 

22)以差值L_Δ2更新频繁模式树FP-tree′； 

23)初始化k＝1； 

24)令k＝k+1，采用Apriori算法，通过新增数据集的强频繁l-项集L_dPl，其中l＝k-1，生成新增数据集的候选频繁k-项集c_dk，判断新增数据集的候选频繁k-项集c_dk是否为空集，是则挖掘结束； 

25)执行c_Δk＝c_dk-L_k，求出新增数据集的候选频繁k-项集c_dk与原阈值下原数据库频繁k-项集L_k之差，判断差值c_Δk是否为空集，是则执行步骤27)，否则执行步骤26)； 

26)对于步骤25)得到的差值c_Δk中的每个项，通过更新后的频繁模式树FP-tree″求出各路径的支持数； 

27)通过判断c_dk中的项的支持数是否不小于新阈值s′，得到新增数据集的强频繁k-项集L_dPk； 

28)通过判断c_Δk中的项的支持数是否不小于新阈值s′，得到新增的频繁k-项集L_Δk，返回步骤24)。 

所述的以差值L_x更新频繁模式树Tree包括以下步骤： 

31)判断差集L_x是否是空集，是则结束流程； 

32)更新频繁列表L_f′＝L₁∪L_x； 

33)将更新后的频繁列表L_f′降序排序； 

34)对原数据库中的任意事项t，执行nItem＝L_f′∩t，取出事务中与频繁列表相交的事务，即在频繁列表上出现的数据库中的事务； 

35)执行nNode＝nItem∩L_x，在频繁列表中出现的数据库中的事务与差集L_x相交，求出新的节点nNode； 

36)将新节点nNode插入到频繁模式树Tree中，更新结束。 

与现有技术相比，本发明不仅创新地同时解决了阈值变化以及数据库数据增加两种问题，并且基于MapReduce对该增量式算法实现了并行化，利用原有的频繁数据项集及频繁模式树，只需对新增数据集进行扫描即可有效获取新的频繁项集， 无需再次扫描全部数据库、生成频繁模式树，进行重复计算，从而大大提高了算法的效率。 

附图说明

图1为MapReduce处理数据集的过程图； 

图2为本发明并行化方案的整体流程图。 

具体实施方式

下面结合附图和具体实施例对本发明进行详细说明。 

如图1所示，MapReduce通过划分的步骤，将海量数据分组并将对其的处理分配给主节点下的各个分节点共同完成，最后整合各个分节点的计算结果得到最终结果。MapReduce将整个数据处理过程抽象为两个部分，用函数表示，分别为map和reduce。map的工作是将任务分解成多个，reduce负责汇总多任务处理的结果。MapReduce框架下的数据集必须可以分解成多个小数据集，并且可以被并行化处理。 

如图2所示，一种增量式频繁模式增长数据挖掘方法，其特征在于，包括以下步骤： 

(1)split函数将原数据库D分成多个数据集，将数据集传递至Mapper及Reducer，对每个数据集中各项的支持度计数进行并行计算，去除支持度低于阈值s的非频繁项，并对频繁项按支持度降序排序，依据排序后的频繁项列表对数据进行分组，并且对事务内的项进行排序； 

(2)MapReduc读取分组列表和步骤(1)所述的数据集，将原数据库D中的数据进行分组，Reducer构建局部的频繁模式树，通过递归过程提取各局部的频繁项集； 

(3)将各局部的频繁项集进行整合，得到原数据库D的完整的频繁项集； 

(4)阈值重置得到新阈值s′，将原数据库D分成多个数据集，对每个数据集中各项的支持度计数进行并行计算，去除支持度低于新阈值s′的非频繁项，并对频繁项按支持度降序排序，依据排序后的频繁项列表对数据进行分组，并且对事务内的项进行排序； 

(5)Reducer将步骤(2)得到的局部频繁模式树进行更新，增添新节点或删 除部分原节点，从这些临时的频繁模式树中挖掘新阈值s′下原数据库D的频繁项集； 

(6)对原数据库D增加新数据集d得到新数据库D′，扫描新增的数据集d，更新频繁模式树，求出新阈值下原数据库的强频繁项集及新增数据集的频繁项集； 

(7)整合步骤(6)得到的新阈值下新增的频繁项集，得到新阈值s′下新数据库D∪d的频繁项集。 

实现步骤(5)～(7)的具体算法流程如下： 

相关符号说明如下：原数据库D，原阈值s，新增数据集d，新阈值s′，D的频繁模式树FP-tree，D的频繁项集L。 

①以下部分为数据库D不变，新阈值s′下的频繁项集的计算 

②以下部分是在新的阈值s′下开始更新数据库D′＝D∪d