基于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]。

此支持度计数二维列表中记录了所有项两两组合在事务集合中出现的频率。由于算法不关心支持度计数小于特定值的，因此在获得该表后需要对其进行必要的删减。根据支持度计数列表显示，F 项、G 项、H 项是不满足min_Sup的项不在算法考虑范围内，故删除与此3 项相关的支持度计数二维表中的行与列。调整后的支持度计数二维表如表4 所示。

由于E为有效支持度计数列表中最小的项，故首先增长为{E}，从调整后的支持度计数二维表中提取与E 相关的所有行列可见{A，E}：2+0、{B，E}：1+0、{C，E}：0+0、{D，E}：4+0。由此无须遍历所有事务集合可得到α条件下的支持度计数表为L_E={D：4，A：2，B：1，C：0}。

当α增长为{D}时，获取支持度计数二维表中第4 行与第4 列关于D 的所遇支持度计数信息可得α条件下支持度计数表为L_D={E：0+4，A：4+0，B：2+0，C：1+0}，同样无须遍历海量事务集合T 即可得到α条件下支持度计数的所有信息。

4 代码编写与算法打包

本研究中使用Eclipse集成开发环境进行代码的编写，Hadoop平台内置了分词和计数的程序，只需要将输入文件存放到指定输入目录中，以的方式将输入文件通过代码简单设置，就可以通过Hadoop内置计数程序执行得到需要的结果。

由于Hadoop内置计数程序默认是读取.txt文件，可以很好地得到计数结果，但该论文中研究对象为糖尿病患者数据集，数量多达10W条，存放方式以Excel文件的方式保存，不能被内置计数程序直接读取，所以需要编写一个转换程序，将Excel文件中的数据转换成内置计数程序可以识别的类型。

将通过工具类获取到的Excel数据作为规则关联算法的原始数据，进行频繁项集的挖掘，应用到改进的FP-Growth算法中。

最后将编写好的工程打包为.jar的Java执行文件，拷贝到Hadoop工作空间目录中，同时将Excel数据文件拷贝到输入目录中，输入对应的命令即可进行分布式计算。

5 实验过程和实验结果

本实验中的原始数据来源于http：//archive.ics.uci.edu/ml/datasets/Diabetes+130-US+hospitals+for+years+1999-2008美国130家医院1999-2008年的10W条糖尿病数据集。在该原始数据中，每条数据包含属性50多个，经过数据预处理之后，将最终的数据属性保留在11个，分别是max_glu_serum（最大葡萄糖血清）、A1Cresult（A1C测试结果）、metformin（二甲双胍）、glimepiride（格列美脲）、glipizide（格列吡嗪）、glyburide（格列本脲）、rosiglitazone（罗格列酮）、insulin（胰岛素）、change（糖尿病药物是否有变化）、diabetesMed（是否有任何糖尿病药物处方）、readmitted（重新入院的日子）。将处理之后的文件以Excel文件保存至本地磁盘中，下面将详细描述实验步骤。

（1）通过编写预处理算法对原始数据进行预处理，将算法中的文件输入路径和输出路径设置为正确路径即可。

（2）运行本地cmd控制台，进入到hadoop目录中，通过start-all.cmd命令启动hadoop，打开浏览器输入：localhost：50070进入到hadoop文件管理系统。

（3）输入命令hadoopfs –put D：＼datas.xls hdfs：//localhost：9000/user/wcinput将处理后的数据文件上传到hadoop的文件系统中

（4）将编写好的关联规则改进FP-Growth算法打包为fpgrowth.jar文件，放到hadoop工作空间的workplace/test目录下。

（5）通过控制台进入到工作空间workplace/test目录下，执行命令hadoop–jar fpgrowth.jar hdfs：//localhost：9000/user/wcinput/datas.xls hdfs：//localhost：9000/user/output

（6）通过浏览器可以查看当前hadoop文件系统中，输出路径下多出一个result.txt文件，改文件则是算法最终执行结果

（7）控制台执行命令hadoopfs–cat hdfs：//localhost：9000/user/output/result.txt就可以在控制台中查看程序执行结果。

diabetesMed--Yes：readmitted-->30， diabetesMed--Yes

insulin--Steady：diabetesMed--Yes， insulin--Steady

readmitted-->30， insulin--Steady

diabetesMed--Yes， readmitted-->30， insulin--Steady

metformin--Steady：diabetesMed--Yes， metformin--Steady

readmitted--<30：diabetesMed--Yes， readmitted--<30

change--Ch：diabetesMed--Yes， change--Ch

readmitted-->30， change--Ch

diabetesMed--Yes， readmitted-->30， change—Ch

通过改进的FP-Growth算法求出的频繁项集清晰的打印在控制台中，可以明确地看出有糖尿病处方药及胰岛素状态为Steady的患者和有糖尿病处方药及糖尿病药物发生变化的患者将有很大风险在30天后再次入院；若只有又糖尿病处方药的患者，则有风險在30天内再次入院。

该实验结果达到了预期目标：挖掘糖化血红蛋白测量对医院再入院率的影响。

6 小结

对FP-Growth算法进行了不足之处的改进，在Windows环境中搭建Hadoop的运行环境，并将算法运用到Hadoop分布式中，对庞大的糖尿病患者数据进行挖掘处理，最终得到挖掘结果，完成了预期目标。

参考文献：

[1] 苏冲.基于最大频繁项集的搜索引擎查询结果聚类方法[D].哈尔滨：哈尔滨工业大学，2009.

[2] 王越.分布式关联规则挖掘的方法研究[D].重庆：重庆大学，2003.

[3] 朱孟杰.基于改进FP-树的最大频繁项目集研究[D]. 哈尔滨：哈尔滨理工大学，2009.

[4] 杨云.FP-Growth算法的改进[J] .计算机工程与设计，2010，31（7） ：1506-1509.