李秀芹 毛振平

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

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

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2019）06-0280-02

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

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

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

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

2 改進(jìn)的FP-growth算法

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

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

2.2 改進(jìn)算法思想

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

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

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

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

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

2.3 改進(jìn)算法描述

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

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

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

輸入：局部最大頻繁項(xiàng)集Map frequentCollectMaps

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

（1） n個(gè)mappers并行地讀取輸入的局部頻繁項(xiàng)集依次讀取某個(gè)items頻繁項(xiàng)集，并進(jìn)行如下操作：if（items）

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

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

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

3 算法分析

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

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

4 結(jié)束語(yǔ)

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

參考文獻(xiàn)：

[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關(guān)聯(lián)規(guī)則算法研究[D].電子科技大學(xué)，2016.

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

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