基于fp—growth关联规则算法接警参数挖掘研究

《基于fp—growth关联规则算法接警参数挖掘研究》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、基于FP—Growth关联规则算法接警参数挖掘研究摘要：本文围绕110接警参数中的接警类别等实战参数，研究了FP-Growth关联规则算法在大城市110接警参数中的数据挖掘分析与应用问题。关键字：关联规则；算法；接警类别；接警类型；分析中图分类号：TP311.13文献标识码：ADOI:10.3969/j.issn.1003-6970.2013.08.021本文著录格式：［1］高家明，薛京生，肖涛.基于FP-Growth关联规则算法的接警参数挖掘分析［J］.软件，2013,34（8）：67-690引言关联规则挖掘的研究大体经历了4个阶段：第一阶段，关联规则原始问题

2、研究，即购物篮分析或单维单层布尔型关联规则挖掘（频繁项集挖掘）研究；随着应用需求的发展，关联规则形式出现了很多扩展，即进入第二阶段，包括：多层关联规则、多维关联规则、量化关联规则、基于约束关联规则等研究；第三阶段，是对关联规则一般性问题的研究，即规则完备性，规则兴趣度和度量，规则挖掘语言等方面的研究；随着多种数据形式的出现，关联规则概念出现新的扩展（即一般化的频繁模式），关联规则挖掘进入了第四个阶段，如序列模式挖掘，时序模式挖掘，子结构挖掘等。关联规则挖掘问题是通过用户指定最小支持度和最小可信度来寻找强关联规则的过程，即关联规则挖掘问题可划分成两个重要的子问题：

3、子问题1:发现频繁项目集。通过用户设定的最小支持度，寻找所有频繁项目集，即满足支持度大于或等于最小支持度的所有项目子集。发现所有的频繁项目集是形成关联规则的最重要基础。子问题2：生成关联规则。通过用户设定的最小可信度,在每个最大频繁项目集中，寻找可信度大于或等于最小可信度的关联规则。相对于第1个问题而言，第2个问题处理起来相对简单,且在内存、I/O以及算法效率上改进的余地不大。所以关联规则挖掘的研究主要集中在第1个问题即发现频繁项目集方面，因而产生了许多优秀的产生频繁集的算法。对于发现频繁项目集的研究，关联规则算法可按照是否生成频繁项集的候选项而分成两大类：一类

4、是产生频繁项集候选项的算法，另一类是不产生候选项的算法。对于这两类关联规则算法，最具有代表性的是Apriori和FP-Growth算法。本文应用FP-Growth算法，对城市110接警参数进行数据挖掘和分析。1FP-Growth算法1.1算法思想2000年Han等人提出了FP-tree算法。这个算法挖掘频繁项目集的基本思想是分而治之，即使用FP-tree递归增长频繁集的方法：(1)对每个项，生成它的条件模式库，然后是它的条件FP-tree；(2)对每个新生成的条件FP-tree,重复这个步骤；(3)直到结果FP-tree为空，或只含惟一的一个路径(此路径的每个子

5、路径对应的项目集都是频繁集)。可见，FP-tree算法只进行2次数据库扫描。它不使用候选集，直接压缩数据库成一个频繁模式树，最后通过这棵树生成关联规则。该算法构造频繁模式树的过程如下：(1)按Apriori算法，扫描数据库一次生成1-频繁集,并把它按降序排列，放入L表中；(2)创建根节点，并标志为null,扫描数据库一次；当得到数据库的一个项目集(即一个元组)时，就把其中的元素按L表的次序排列，然后递归调用频繁模式树的生成(FP-growth)来实现FP-tree的增长。1.2挖掘过程FP-tree的挖掘步骤如下：(1)为FP-tree中的每个节点生成条件模式库

6、。从FP-tree的表头开始，按照每个频繁项的连接遍历FP-tree,列出能够到达此项的所有前缀路径，得到FP-tree条件模式库，如表1所示：（2）用FP-tree条件模式库建立条件FP-tree树。对该模式库计算库中每个项的支持度，并用模式库中的频繁项建立FP-tree树，表2列出了所有从条件模式库到条件FP-tree树（假设项集共同出现的次数大于等于2为频繁项）的节点（树枝和树叶）。（3）递归挖掘条件FP-tree由条件模式树（条件按FP-tree）生成频繁模式，需要对条件FP-tree树分两种情况讨论：第一，单一FP-treeT路径生成。假设FP-tre

7、e只包含一个路径P,那么P的子路径的所有可能组合就是T包含的所有频繁集。第二，FP-tree中的惟一前缀路径。假设一个条件FP-treeT有一个共享的惟一前缀路径P,则处理过程分为两步：第一步用一个节点代替此前缀路径P;第二步分别计算这两个部分的结果。（4）频繁模式树FP-growth(Tree,）频繁模式树的生成算法如下:2关联规则在110接警参数中的挖掘应用城市110接警系统积累了海量的实战数据，如何快速准确地找出所需要的内在关联信息，已成为应用工作的重要课题。我们利于FP-Growth关联规则算法对110接警数据中的接警参数信息进行分析，着重从接警类别等信

8、息中挖掘出各个接警事件类