李秀芹 毛振平

摘要：傳統(tǒng)FP-growth算法在處理規(guī)模大、海量的醫(yī)療大數(shù)據(jù)時，構造基于內(nèi)存的FP-tree可能導致失?。恢貜偷啻伪闅v全局FP-tree造成極大浪費；并行處理時各節(jié)點之間需要的巨大通信開銷等問題。針對傳統(tǒng)FP-growth算法存在的這些問題展開研究，提出一種采用數(shù)據(jù)庫分解思想，基于Hadoop平臺并行在局部FP-tree中查找局部頻繁項集且不生成全局FP-tree的挖掘算法。

關鍵詞：醫(yī)療大數(shù)據(jù)；FP-growth算法；Hadoop；數(shù)據(jù)庫分解

中圖分類號：TP311 文獻標識碼：A 文章編號：1009-3044（2019）06-0280-02

醫(yī)療衛(wèi)生行業(yè)屬于一種服務性行業(yè)，是關系國計民生、與人們生活密切相關的特殊產(chǎn)業(yè)。伴隨著信息技術在醫(yī)療行業(yè)地引入，使得醫(yī)療行業(yè)的信息化、自動化程度不斷提高。醫(yī)療行業(yè)的核心都是醫(yī)療數(shù)據(jù)，醫(yī)療大數(shù)據(jù)來源廣泛，主要來自人口數(shù)據(jù)庫、健康檔案數(shù)據(jù)庫、電子病歷數(shù)據(jù)庫等。并且數(shù)據(jù)格式多樣化，文字、圖案、聲視頻等。如何運用這些海量多樣化醫(yī)療信息來更好地為醫(yī)療行業(yè)服務，已被更多的研究人員和機構所關注。

韓家煒等人在2000年提出的FP-growth（ Frequent-Pattern Growth）關聯(lián)分析算法[1]，采取分治策略不需要產(chǎn)生候選集，相對于經(jīng)典的Apriori算法已經(jīng)有了一個數(shù)量級的改善，但是仍有一些不足[2]。2008年Haoyuan Li等人提出了Parallel FP-Growth（簡稱PFP）算法[3]，解決了前文提到的內(nèi)存瓶頸、計算瓶頸等問題，但節(jié)點間需要巨大的通訊開銷。2016年婁書青等人的TFP算法[4]，用于數(shù)據(jù)水平投影過程中，利用貪心策略對F-list中的項進行分組。2018年魏蓮蓮等人在期刊中提出改進的垂直FP-growth算法，求取局部頻繁項集、合并全局頻繁樹[5]。雖然很多學者都提出了改進的FP-growth算法，但仍有一些不足。針對無法構造基于內(nèi)存的FP-tree的問題、挖掘頻繁項集相互獨立需重復迭代遍歷整棵FP-tree，生成大量條件FP-tree帶來極大的浪費、并行處理過程中各節(jié)點之間需要的巨大通信開銷的問題，提出一種采用數(shù)據(jù)庫分解思想、基于Hadoop并行地在局部FP-tree中查找局部頻繁項集且不生成全局FP-tree的挖掘算法。

1 開源分布式文件系統(tǒng)Hadoop

Hadoop使用MapReduce并行運算框架，包含Map和Reduce兩個階段。Map階段負責數(shù)據(jù)的映射，也叫作數(shù)據(jù)轉(zhuǎn)換。Reduce階段負責數(shù)據(jù)聚合。MapReduce的主控節(jié)點為Master，主要用以管理和調(diào)度任務的執(zhí)行，從節(jié)點為Worker，用以管理每個節(jié)點上計算任務的執(zhí)行。數(shù)據(jù)存儲的主控節(jié)點NameNode與并行計算的主控節(jié)點Master可以設置在一個節(jié)點上也可以設置在不同的節(jié)點上。數(shù)據(jù)存儲的從節(jié)點DataNode與并行計算的從節(jié)點Worker合并設置，以實現(xiàn)每個Worker處理本地DataNode上的數(shù)據(jù)。Hadoop的結構框架圖1所示。

2 改進的FP-growth算法

2.1 數(shù)據(jù)劃分

數(shù)據(jù)分解的基本思想是分而治之。常見的數(shù)據(jù)庫分解有劃分和投影，劃分又為水平劃分和垂直劃分，投影又分為水平投影和垂直投影。本文用到的數(shù)據(jù)庫分解策略是水平劃分，是將數(shù)據(jù)庫事務集劃分成沒有交集的連續(xù)多個子部分。劃分的子部分存儲在不同的節(jié)點上，這一步驟由Hadoop自動完成，只需要將事務集數(shù)據(jù)庫中的數(shù)據(jù)拷貝到Hadoop框架的分布式文件管理系統(tǒng)中即可，Hadoop框架會自動進行數(shù)據(jù)劃分處理，分成的多個Block存儲在不同節(jié)點上，同時為每個Block保存副本，防止某節(jié)點因故障損壞造成文件丟失。

2.2 改進算法思想

改進FP-growth算法是一種基于Hadoop并行地在局部FP-tree中查找局部頻繁項集且不生成全局FP-tree的挖掘算法。基本思想是：

（1） 改進算法中，包含了兩次掃描數(shù)據(jù)集的過程，為加快處理速度和效率，將第一次掃描數(shù)據(jù)集進行并行化處理（并行化統(tǒng)計頻繁1-項集列表）：利用數(shù)據(jù)分解中的劃分策略（水平劃分）進行數(shù)據(jù)集分解。

（2） 每個節(jié)點對劃分到本地數(shù)據(jù)集中的數(shù)據(jù)項進行頻數(shù)的統(tǒng)計，得到局部的項集計數(shù)。然后各個節(jié)點之間通信得到每個項目的全局頻數(shù)，根據(jù)最小支持度閾值刪除非頻繁項，從而得到頻繁1-項集。

（3） 在各個節(jié)點上，根據(jù)頻繁1-項集，對本地數(shù)據(jù)集中的事務進行排序，構建各自的局部FP-tree，并挖掘該樹，挖掘頻繁項集過程中，不需要挖掘其他節(jié)點數(shù)據(jù)和信息，因此不需要進行節(jié)點通信，減少了節(jié)點間通信的資源開銷。獲得局部頻繁項集合（此過程并不刪除局部頻繁項不滿足支持度計數(shù)的項）。

（4） 完成之后，將局部頻繁項集傳送到主節(jié)點，不再生成全局FP-tree、迭代遍歷全局FP-tree和生成大量的條件FP-tree，根據(jù)頻繁1-項集，依次統(tǒng)計每一數(shù)據(jù)項計數(shù)頻繁項計數(shù)，將不滿足支持度計數(shù)和置信度的頻繁項刪除，即可得到全局頻繁項集。

2.3 改進算法描述

按照執(zhí)行順序和功能總體流程大致分為四個流程。按照Hadoop集群的MapReduce框架進行實現(xiàn)，分為獲取表頭鏈算法、構建局部FP-tree算法、挖掘局部頻繁項集算法、挖掘全局最大頻繁項集的關聯(lián)規(guī)則算法。

獲取表頭鏈：并行地讀取HDFS中的數(shù)據(jù)塊，統(tǒng)計數(shù)據(jù)項item出現(xiàn)的次數(shù)；保留滿足最小支持度的數(shù)據(jù)項；按照計數(shù)從大到小的順序進行排序，即獲得表頭鏈。通過節(jié)點通信，每個節(jié)點都有一份表頭鏈，此過程設置Map、Reduce函數(shù)簡單易實現(xiàn)。構建局部FP-tree傳統(tǒng)FP-growth算法創(chuàng)建FP-tree方法相同；挖掘局部頻繁項集與傳統(tǒng)算法中挖掘全局FP-tree方法類似，在挖掘局部FP-tree時，不執(zhí)行的是：根據(jù)支持度和置信度刪除不頻繁項集。

算法：挖掘全局頻繁項集的關聯(lián)規(guī)則算法

輸入：局部最大頻繁項集Map frequentCollectMaps

輸出：通過頻繁項集挖掘的關聯(lián)規(guī)則

（1） n個mappers并行地讀取輸入的局部頻繁項集依次讀取某個items頻繁項集，并進行如下操作：if（items）

1） 若items不為空，則輸出鍵值對，其中 count指的是items頻繁項集出現(xiàn)的次數(shù)。2）否則，忽略此項。

（2） 以其中一個站點的頻繁項集map為基準，作為全局頻繁項集，將各站點項集進行合并至全局頻繁項集：1） 將與map中key相同的項集進行合并，count值相加，將其他站點頻繁項集集合中此項集移除，若不滿足支持度和置信度，將全局頻繁項集中此項集移除； 2） 以第二個站點為基準，與第三至第n個站點的頻繁項集進行合并，合并后的count值滿足支持度和置信度，則添加到全局頻繁項集map中；并將第二至第n個站點中的此頻繁項移除；直到該站點頻繁項集為空；3） 以（2）中相同方法，遍歷至第n個站點中的頻繁項集為空。即可得全局最大頻繁項集。

（3） 通過全局最大頻繁項集，挖掘出關聯(lián)規(guī)則。

3 算法分析

本文改進算法的明顯優(yōu)勢是，將數(shù)據(jù)劃分思想與Hadoop平臺工作機制相結合，實現(xiàn)更簡單；生成及其挖掘局部FP-tree過程中，不需要進行節(jié)點間通信，更加高效；改進算法不像傳統(tǒng)并行FP-growth算法要生成全局FP-tree，有效解決創(chuàng)建基于內(nèi)存的FP-tree導致的失敗，以及迭代挖掘全局FP-tree造成的空間和時間的資源浪費。

與魏蓮蓮提出的改進算法[5]進行對比，在生成和挖掘局部FP -tree過程中節(jié)點間不需要進行通信；本文算法將局部頻繁項集進行合并，不必合并成全局FP-tree。當集群越大，單次能夠處理的Map和Reduce數(shù)量越多，該算法的時間復雜度越低，實現(xiàn)效率越高。

4 結束語

本文通過研究醫(yī)療大數(shù)據(jù)的特征，在傳統(tǒng)FP-growth算法的基礎上，一種基于Hadoop的并行地在局部FP-tree中查找局部頻繁項集且不生成全局FP-tree，從而獲得全局頻繁項集的挖掘算法。算法有效的解決無法構造基于內(nèi)存FP-tree的問題、挖掘全局FP-tree，生成大量條件FP-tree帶來極大的浪費、并行處理過程中各節(jié)點之間需要的巨大通信開銷的問題，該改進算法有利于對醫(yī)療衛(wèi)生及其他行業(yè)大數(shù)據(jù)關聯(lián)規(guī)則的研究。

參考文獻：

[1] Jiawei Han，Jian Pei，Yiwen Yin. Mining frequent patterns without candidate generation[J]. ACM SIGMOD Record . 2000 （2）

[2] 付小妮.基于hadoop與醫(yī)療大數(shù)據(jù)的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關聯(lián)規(guī)則算法研究[D].電子科技大學，2016.

[5] 王嶸冰，徐紅艷，魏蓮蓮.基于MapReduce的垂直FP-growth挖掘算法研究[J].計算機與數(shù)字工程，2018，46（07）：1284-1287+1296.

【通聯(lián)編輯：梁書】