基于Hadoop與醫療大數據的FP—growth算法的優化研究

李秀芹 毛振平

摘要：傳統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.

【通聯編輯：梁書】