基于hadoop与医疗大数据FP―Growth算法优化研究.docVIP

基于hadoop与医疗大数据FP―Growth算法优化研究 　　摘要：针对传统 FP-Growth 算法在大规模数据环境下挖掘效率低下的问题，提出了一种改进的 FP-Growth 算法。该算法主要是通过基于频繁闭项集策略对完备模式树进行剪枝进而减小有哪些信誉好的足球投注网站空间规模，达到提高算法挖掘效率的目的。并将改进后的 FP-Growth 算法的分治策略与分布式计算框架Hadoop的MapReduce编程模式有机结合，进一步提高了大数据环境下的挖掘效率。实验证明，基于Hadoop的改进 FP-Growth 算法的效率较传统 FP-Growth 算法有所提高。 　　关键词：数据挖掘关联规则；FP-Growth；HadoopMapReduce 　　中图分类号：TP314 文献标识码：A 文章编号：1009-3044（2018）14-0001-02 　　1 绪论 　　在本文中，将采用FP-Growth算法进行医疗大数据的挖掘和分析，之所以采用FP-Growth算法，是因为其比Apriori算法更加方便，仅需2次扫描数据库，就能得到用于数据分析的频繁项集等数据。为了提高数据挖掘的效率，将传统的算法并行化改进后移植到Hadoop平台，这是基于云计算的数据挖掘的核心过程，也是本文的重点和难点。 　　2 FP-Growth 算法 　　FP-Growth 算法使用 FP-tree 直接发现频繁项集，避免了候选项集的产生环节。 　　算法原理：算法的第一步是构造一棵 FP-tree， FP-tree 体现的是对数据的压缩表示。首先分别读取每一条事务，将该事务映射到 FP-tree 上的一条路径，不同的事务可能有相同的前项，那么它们在 FP-tree 上的路径就有可能重合，路径越重合，表明数据压缩效果越好， FP-tree 构造越成功[1]。最理想的情况下就是每一条事务都完全相同，或者起码共享相同的前缀，此时构造的 FP-tree 仅包括一条路径，最不理想的情况是所有事务都不包含任何相同项，此时 FP-tree 的大小就和事务数据集相同，并没有起到压缩数据的作用[2]。 　　产生 FP-tree 后，第二步， FP- Growth算法从底向上探索整棵树，由 FP-tree产生频繁项集。 FP- Growth算法不同于Apriori算法，Apriori算法产生的频繁项集时先产生频繁 1-项集，然后是频繁 2-项集，频繁 3-项集等等。 FP- Growth算法按照结尾项进行频繁项集的寻找，采用分治策略，将寻找频繁项集这个大问题划分为寻找以某个特定项结尾的所有频繁项集这样一个个小问题，进而得到解决[3]。 　　3 改进 FP-Growth 算法 　　针对FP-Growth 算法的缺点，对经典算法进行改进，提出使用支持度计数二维表的方法，从而省去经典算法?μ跫?模式基的第一次遍历，具体算法描述为： 　　（1） 在第一次遍历事务集合T 的同时创建二维向量，记录每个事务中各个项两两组合出现的支持度计数。如有事务“A，B，C，D”，则二维向量表中（A，B）（A，C）、（A，D）、（B，C）、（B，D）、（C，D）项都需要加1。其中向量（C，B）和（B，C）是两个不同的向量。 　　（2）利用递归方式创建α条件下（ α≠{Null}）的条件FP 子树时，无须两次遍历条件模式基（其中第一次遍历条件模式基可得到支持度计数列表，第二次遍历条件模式基可插入树节点从而创建FP 树）。支持度计数列表可以从支持度计数二维向量列表中获得。抽取二维向量表中的与Ei相关的行、列值，将对应行列值相加即可得到条件α下，Ei与其他项的支持度计数。其中Ei为当前项。 　　（3）遍历条件模式基，创建FP 子树的同时创建新的支持度计数二维向量表。例如表1 所示的事务集合T，要求min_Sup=25%，由此可得支持度计数最小为5（17×25%= 4.25）。根据经典算法中的原则，遍历一次事务集合T 可获得项头表如表2 所示。本改进点在此遍历中需要多做一项工作，即生成支持度计数二维向量表。首先创建如表3 所示的空二维向量表1。另外将二维表中的所有相关项对计数值初始化为0。在第一次遍历事务集合时，对于T1 需要更新其在项头表中的频繁度计数。同时获取T1 的所有两两项组合：{A，F}。T1 中只有一个符合条件的组合，将该组合对应的计数值加1。用同样的方式处理T2、T3等事务。T15 中包含的项集对有{A，B}{A，C}{A，D}{B，D}{C，D}，故对应于此6 个组合的项对支持度计数也需要加1。用同样的方式处理T16、T17，最终可获得表3所示的支持度计数二维列表[4]。 　　此支持度计数二维列表中记录了所有项两两组合在事务集合中出现的频率。由于算法不关心支持度计数小于特定值的，因此在获