论文部分内容阅读
摘要：传统FP-growth算法在处理规模大、海量的医疗大数据时，构造基于内存的FP-tree可能导致失败；重复迭代多次遍历全局FP-tree造成极大浪费；并行处理时各节点之间需要的巨大通信开销等问题。针对传统FP-growth算法存在的这些问题展开研究，提出一种采用数据库分解思想，基于Hadoop平台并行在局部FP-tree中查找局部频繁项集且不生成全局FP-tree的挖掘算法。
关键词：医疗大数据；FP-growth算法；Hadoop；数据库分解
中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2019）06-0280-02
医疗卫生行业属于一种服务性行业，是关系国计民生、与人们生活密切相关的特殊产业。伴随着信息技术在医疗行业地引入，使得医疗行业的信息化、自动化程度不断提高。医疗行业的核心都是医疗数据，医疗大数据来源广泛，主要来自人口数据库、健康档案数据库、电子病历数据库等。并且数据格式多样化，文字、图案、声视频等。如何运用这些海量多样化医疗信息来更好地为医疗行业服务，已被更多的研究人员和机构所关注。
韩家炜等人在2000年提出的FP-growth（ Frequent-Pattern Growth）关联分析算法[1]，采取分治策略不需要产生候选集，相对于经典的Apriori算法已经有了一个数量级的改善，但是仍有一些不足[2]。2008年Haoyuan Li等人提出了Parallel FP-Growth（简称PFP）算法[3]，解决了前文提到的内存瓶颈、计算瓶颈等问题，但节点间需要巨大的通讯开销。2016年娄书青等人的TFP算法[4]，用于数据水平投影过程中，利用贪心策略对F-list中的项进行分组。2018年魏莲莲等人在期刊中提出改进的垂直FP-growth算法，求取局部频繁项集、合并全局频繁树[5]。虽然很多学者都提出了改进的FP-growth算法，但仍有一些不足。针对无法构造基于内存的FP-tree的问题、挖掘频繁项集相互独立需重复迭代遍历整棵FP-tree，生成大量条件FP-tree带来极大的浪费、并行处理过程中各节点之间需要的巨大通信开销的问题，提出一种采用数据库分解思想、基于Hadoop并行地在局部FP-tree中查找局部频繁项集且不生成全局FP-tree的挖掘算法。
1 开源分布式文件系统Hadoop
Hadoop使用MapReduce并行运算框架，包含Map和Reduce两个阶段。Map阶段负责数据的映射，也叫作数据转换。Reduce阶段负责数据聚合。MapReduce的主控节点为Master，主要用以管理和调度任务的执行，从节点为Worker，用以管理每个节点上计算任务的执行。数据存储的主控节点NameNode与并行计算的主控节点Master可以设置在一个节点上也可以设置在不同的节点上。数据存储的从节点DataNode与并行计算的从节点Worker合并设置，以实现每个Worker处理本地DataNode上的数据。Hadoop的结构框架图1所示。
2 改进的FP-growth算法
2.1 数据划分
数据分解的基本思想是分而治之。常见的数据库分解有划分和投影，划分又为水平划分和垂直划分，投影又分为水平投影和垂直投影。本文用到的数据库分解策略是水平划分，是将数据库事务集划分成没有交集的连续多个子部分。划分的子部分存储在不同的节点上，这一步骤由Hadoop自动完成，只需要将事务集数据库中的数据拷贝到Hadoop框架的分布式文件管理系统中即可，Hadoop框架会自动进行数据划分处理，分成的多个Block存储在不同节点上，同时为每个Block保存副本，防止某节点因故障损坏造成文件丢失。
2.2 改进算法思想
改进FP-growth算法是一种基于Hadoop并行地在局部FP-tree中查找局部频繁项集且不生成全局FP-tree的挖掘算法。基本思想是：
（1） 改进算法中，包含了两次扫描数据集的过程，为加快处理速度和效率，将第一次扫描数据集进行并行化处理（并行化统计频繁1-项集列表）：利用数据分解中的划分策略（水平划分）进行数据集分解。
（2） 每个节点对划分到本地数据集中的数据项进行频数的统计，得到局部的项集计数。然后各个节点之间通信得到每个项目的全局频数，根据最小支持度阈值删除非频繁项，从而得到频繁1-项集。
（3） 在各个节点上，根据频繁1-项集，对本地数据集中的事务进行排序，构建各自的局部FP-tree，并挖掘该树，挖掘频繁项集过程中，不需要挖掘其他节点数据和信息，因此不需要进行节点通信，减少了节点间通信的资源开销。获得局部频繁项集合（此过程并不删除局部频繁项不满足支持度计数的项）。
（4） 完成之后，将局部频繁项集传送到主节点，不再生成全局FP-tree、迭代遍歷全局FP-tree和生成大量的条件FP-tree，根据频繁1-项集，依次统计每一数据项计数频繁项计数，将不满足支持度计数和置信度的频繁项删除，即可得到全局频繁项集。
2.3 改进算法描述
按照执行顺序和功能总体流程大致分为四个流程。按照Hadoop集群的MapReduce框架进行实现，分为获取表头链算法、构建局部FP-tree算法、挖掘局部频繁项集算法、挖掘全局最大频繁项集的关联规则算法。
获取表头链：并行地读取HDFS中的数据块，统计数据项item出现的次数；保留满足最小支持度的数据项；按照计数从大到小的顺序进行排序，即获得表头链。通过节点通信，每个节点都有一份表头链，此过程设置Map、Reduce函数简单易实现。构建局部FP-tree传统FP-growth算法创建FP-tree方法相同；挖掘局部频繁项集与传统算法中挖掘全局FP-tree方法类似，在挖掘局部FP-tree时，不执行的是：根据支持度和置信度删除不频繁项集。 算法：挖掘全局频繁项集的关联规则算法
輸入：局部最大频繁项集Map frequentCollectMaps
输出：通过频繁项集挖掘的关联规则
（1） n个mappers并行地读取输入的局部频繁项集依次读取某个items频繁项集，并进行如下操作：if（items）
1） 若items不为空，则输出键值对，其中 count指的是items频繁项集出现的次数。2）否则，忽略此项。
（2） 以其中一个站点的频繁项集map为基准，作为全局频繁项集，将各站点项集进行合并至全局频繁项集：1） 将与map中key相同的项集进行合并，count值相加，将其他站点频繁项集集合中此项集移除，若不满足支持度和置信度，将全局频繁项集中此项集移除； 2） 以第二个站点为基准，与第三至第n个站点的频繁项集进行合并，合并后的count值满足支持度和置信度，则添加到全局频繁项集map中；并将第二至第n个站点中的此频繁项移除；直到该站点频繁项集为空；3） 以（2）中相同方法，遍历至第n个站点中的频繁项集为空。即可得全局最大频繁项集。
（3） 通过全局最大频繁项集，挖掘出关联规则。
3 算法分析
本文改进算法的明显优势是，将数据划分思想与Hadoop平台工作机制相结合，实现更简单；生成及其挖掘局部FP-tree过程中，不需要进行节点间通信，更加高效；改进算法不像传统并行FP-growth算法要生成全局FP-tree，有效解决创建基于内存的FP-tree导致的失败，以及迭代挖掘全局FP-tree造成的空间和时间的资源浪费。
与魏莲莲提出的改进算法[5]进行对比，在生成和挖掘局部FP -tree过程中节点间不需要进行通信；本文算法将局部频繁项集进行合并，不必合并成全局FP-tree。当集群越大，单次能够处理的Map和Reduce数量越多，该算法的时间复杂度越低，实现效率越高。
4 结束语
本文通过研究医疗大数据的特征，在传统FP-growth算法的基础上，一种基于Hadoop的并行地在局部FP-tree中查找局部频繁项集且不生成全局FP-tree，从而获得全局频繁项集的挖掘算法。算法有效的解决无法构造基于内存FP-tree的问题、挖掘全局FP-tree，生成大量条件FP-tree带来极大的浪费、并行处理过程中各节点之间需要的巨大通信开销的问题，该改进算法有利于对医疗卫生及其他行业大数据关联规则的研究。
参考文献：
[1] Jiawei Han，Jian Pei，Yiwen Yin. Mining frequent patterns without candidate generation[J]. ACM SIGMOD Record . 2000 （2）
[2] 付小妮.基于hadoop与医疗大数据的apriori算法并行化研究[J].信息通信，2017（09）：30-31.
[3] Yan H，Wang Y，et al.Pfp：parallel fp-growth for query recommendation[A]. In： IMocccdings of the 2008 ACM conferenceon Recommender Systems[C]. ACM，2008：107-114..
[4] 娄书青. 并行FP-growth关联规则算法研究[D].电子科技大学，2016.
[5] 王嵘冰，徐红艳，魏莲莲.基于MapReduce的垂直FP-growth挖掘算法研究[J].计算机与数字工程，2018，46（07）：1284-1287 1296.
【通联编辑：梁书】
关键词：医疗大数据；FP-growth算法；Hadoop；数据库分解
中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2019）06-0280-02
医疗卫生行业属于一种服务性行业，是关系国计民生、与人们生活密切相关的特殊产业。伴随着信息技术在医疗行业地引入，使得医疗行业的信息化、自动化程度不断提高。医疗行业的核心都是医疗数据，医疗大数据来源广泛，主要来自人口数据库、健康档案数据库、电子病历数据库等。并且数据格式多样化，文字、图案、声视频等。如何运用这些海量多样化医疗信息来更好地为医疗行业服务，已被更多的研究人员和机构所关注。
韩家炜等人在2000年提出的FP-growth（ Frequent-Pattern Growth）关联分析算法[1]，采取分治策略不需要产生候选集，相对于经典的Apriori算法已经有了一个数量级的改善，但是仍有一些不足[2]。2008年Haoyuan Li等人提出了Parallel FP-Growth（简称PFP）算法[3]，解决了前文提到的内存瓶颈、计算瓶颈等问题，但节点间需要巨大的通讯开销。2016年娄书青等人的TFP算法[4]，用于数据水平投影过程中，利用贪心策略对F-list中的项进行分组。2018年魏莲莲等人在期刊中提出改进的垂直FP-growth算法，求取局部频繁项集、合并全局频繁树[5]。虽然很多学者都提出了改进的FP-growth算法，但仍有一些不足。针对无法构造基于内存的FP-tree的问题、挖掘频繁项集相互独立需重复迭代遍历整棵FP-tree，生成大量条件FP-tree带来极大的浪费、并行处理过程中各节点之间需要的巨大通信开销的问题，提出一种采用数据库分解思想、基于Hadoop并行地在局部FP-tree中查找局部频繁项集且不生成全局FP-tree的挖掘算法。
1 开源分布式文件系统Hadoop
Hadoop使用MapReduce并行运算框架，包含Map和Reduce两个阶段。Map阶段负责数据的映射，也叫作数据转换。Reduce阶段负责数据聚合。MapReduce的主控节点为Master，主要用以管理和调度任务的执行，从节点为Worker，用以管理每个节点上计算任务的执行。数据存储的主控节点NameNode与并行计算的主控节点Master可以设置在一个节点上也可以设置在不同的节点上。数据存储的从节点DataNode与并行计算的从节点Worker合并设置，以实现每个Worker处理本地DataNode上的数据。Hadoop的结构框架图1所示。
2 改进的FP-growth算法
2.1 数据划分
数据分解的基本思想是分而治之。常见的数据库分解有划分和投影，划分又为水平划分和垂直划分，投影又分为水平投影和垂直投影。本文用到的数据库分解策略是水平划分，是将数据库事务集划分成没有交集的连续多个子部分。划分的子部分存储在不同的节点上，这一步骤由Hadoop自动完成，只需要将事务集数据库中的数据拷贝到Hadoop框架的分布式文件管理系统中即可，Hadoop框架会自动进行数据划分处理，分成的多个Block存储在不同节点上，同时为每个Block保存副本，防止某节点因故障损坏造成文件丢失。
2.2 改进算法思想
改进FP-growth算法是一种基于Hadoop并行地在局部FP-tree中查找局部频繁项集且不生成全局FP-tree的挖掘算法。基本思想是：
（1） 改进算法中，包含了两次扫描数据集的过程，为加快处理速度和效率，将第一次扫描数据集进行并行化处理（并行化统计频繁1-项集列表）：利用数据分解中的划分策略（水平划分）进行数据集分解。
（2） 每个节点对划分到本地数据集中的数据项进行频数的统计，得到局部的项集计数。然后各个节点之间通信得到每个项目的全局频数，根据最小支持度阈值删除非频繁项，从而得到频繁1-项集。
（3） 在各个节点上，根据频繁1-项集，对本地数据集中的事务进行排序，构建各自的局部FP-tree，并挖掘该树，挖掘频繁项集过程中，不需要挖掘其他节点数据和信息，因此不需要进行节点通信，减少了节点间通信的资源开销。获得局部频繁项集合（此过程并不删除局部频繁项不满足支持度计数的项）。
（4） 完成之后，将局部频繁项集传送到主节点，不再生成全局FP-tree、迭代遍歷全局FP-tree和生成大量的条件FP-tree，根据频繁1-项集，依次统计每一数据项计数频繁项计数，将不满足支持度计数和置信度的频繁项删除，即可得到全局频繁项集。
2.3 改进算法描述
按照执行顺序和功能总体流程大致分为四个流程。按照Hadoop集群的MapReduce框架进行实现，分为获取表头链算法、构建局部FP-tree算法、挖掘局部频繁项集算法、挖掘全局最大频繁项集的关联规则算法。
获取表头链：并行地读取HDFS中的数据块，统计数据项item出现的次数；保留满足最小支持度的数据项；按照计数从大到小的顺序进行排序，即获得表头链。通过节点通信，每个节点都有一份表头链，此过程设置Map、Reduce函数简单易实现。构建局部FP-tree传统FP-growth算法创建FP-tree方法相同；挖掘局部频繁项集与传统算法中挖掘全局FP-tree方法类似，在挖掘局部FP-tree时，不执行的是：根据支持度和置信度删除不频繁项集。 算法：挖掘全局频繁项集的关联规则算法
輸入：局部最大频繁项集Map
输出：通过频繁项集挖掘的关联规则
（1） n个mappers并行地读取输入的局部频繁项集依次读取某个items频繁项集，并进行如下操作：if（items）
1） 若items不为空，则输出
（2） 以其中一个站点的频繁项集map为基准，作为全局频繁项集，将各站点项集进行合并至全局频繁项集：1） 将与map中key相同的项集进行合并，count值相加，将其他站点频繁项集集合中此项集移除，若不满足支持度和置信度，将全局频繁项集中此项集移除； 2） 以第二个站点为基准，与第三至第n个站点的频繁项集进行合并，合并后的count值满足支持度和置信度，则添加到全局频繁项集map中；并将第二至第n个站点中的此频繁项移除；直到该站点频繁项集为空；3） 以（2）中相同方法，遍历至第n个站点中的频繁项集为空。即可得全局最大频繁项集。
（3） 通过全局最大频繁项集，挖掘出关联规则。
3 算法分析
本文改进算法的明显优势是，将数据划分思想与Hadoop平台工作机制相结合，实现更简单；生成及其挖掘局部FP-tree过程中，不需要进行节点间通信，更加高效；改进算法不像传统并行FP-growth算法要生成全局FP-tree，有效解决创建基于内存的FP-tree导致的失败，以及迭代挖掘全局FP-tree造成的空间和时间的资源浪费。
与魏莲莲提出的改进算法[5]进行对比，在生成和挖掘局部FP -tree过程中节点间不需要进行通信；本文算法将局部频繁项集进行合并，不必合并成全局FP-tree。当集群越大，单次能够处理的Map和Reduce数量越多，该算法的时间复杂度越低，实现效率越高。
4 结束语
本文通过研究医疗大数据的特征，在传统FP-growth算法的基础上，一种基于Hadoop的并行地在局部FP-tree中查找局部频繁项集且不生成全局FP-tree，从而获得全局频繁项集的挖掘算法。算法有效的解决无法构造基于内存FP-tree的问题、挖掘全局FP-tree，生成大量条件FP-tree带来极大的浪费、并行处理过程中各节点之间需要的巨大通信开销的问题，该改进算法有利于对医疗卫生及其他行业大数据关联规则的研究。
参考文献：
[1] Jiawei Han，Jian Pei，Yiwen Yin. Mining frequent patterns without candidate generation[J]. ACM SIGMOD Record . 2000 （2）
[2] 付小妮.基于hadoop与医疗大数据的apriori算法并行化研究[J].信息通信，2017（09）：30-31.
[3] Yan H，Wang Y，et al.Pfp：parallel fp-growth for query recommendation[A]. In： IMocccdings of the 2008 ACM conferenceon Recommender Systems[C]. ACM，2008：107-114..
[4] 娄书青. 并行FP-growth关联规则算法研究[D].电子科技大学，2016.
[5] 王嵘冰，徐红艳，魏莲莲.基于MapReduce的垂直FP-growth挖掘算法研究[J].计算机与数字工程，2018，46（07）：1284-1287 1296.
【通联编辑：梁书】