李曉楠，馬元吉，肖川

（1.四川大學(xué)計算機學(xué)院，成都　610065；2.四川大學(xué)華西醫(yī)院，成都　610041；3.四川大學(xué)華西公共衛(wèi)生學(xué)院，成都　610041）

基于分布式的關(guān)聯(lián)規(guī)則算法在醫(yī)療數(shù)據(jù)挖掘中的應(yīng)用

李曉楠1，馬元吉2，肖川3

（1.四川大學(xué)計算機學(xué)院，成都610065；2.四川大學(xué)華西醫(yī)院，成都610041；3.四川大學(xué)華西公共衛(wèi)生學(xué)院，成都610041）

0　引言

隨著大數(shù)據(jù)時代的到來，醫(yī)院的信息化建設(shè)逐步完善，電子病歷大量積累、醫(yī)療設(shè)備和儀器的信息逐漸增多，病人病史、診斷、檢驗和治療的信息等大量醫(yī)療信息已經(jīng)積累在醫(yī)院數(shù)據(jù)庫中，并且數(shù)據(jù)信息的結(jié)構(gòu)呈現(xiàn)多樣化的特征。當數(shù)據(jù)量急速增長時，利用計算機對醫(yī)療數(shù)據(jù)做信息挖掘，提取恰當?shù)臄?shù)據(jù)進行處理，利用聚類、分類等各種數(shù)據(jù)挖掘方法構(gòu)建醫(yī)療數(shù)據(jù)分析模型，對病人資料庫中的大量數(shù)據(jù)進行分析，提煉出其中有價值的信息，發(fā)現(xiàn)不同疾病之間的關(guān)聯(lián)，尋找傳染病的傳染特征，預(yù)測疾病發(fā)展趨勢，已成為醫(yī)療信息化中進一步研究的課題。其中，對影響我國居民健康的三大傳染病：乙肝、結(jié)核、艾滋的相關(guān)研究也是醫(yī)學(xué)科學(xué)研究中一個重要的方向。文中依托“十二五”科技重大專項——國家重大傳染病綜合防治綿陽示范區(qū)項目中獲取的體檢信息數(shù)據(jù)，對信息系統(tǒng)中獲取到的醫(yī)療數(shù)據(jù)的乙肝部分進行挖掘研究，對乙肝的并發(fā)癥、乙肝發(fā)病情況和生活習(xí)慣之間的關(guān)聯(lián)關(guān)系進行了探索。

1　Apriori算法及其分布式化

1.1Apriori算法

Apriori算法是一種挖掘關(guān)聯(lián)規(guī)則的頻繁項集算法，最早由R.Agrawal等人提出，目的是從大量數(shù)據(jù)中發(fā)現(xiàn)事物的相關(guān)聯(lián)系，Apriori算法應(yīng)用廣泛，可用于消費市場價格分析、網(wǎng)絡(luò)安全中的入侵檢測、獲取顧客的購物習(xí)慣等。Apriori算法逐層搜索，迭代多次從k項集中尋找（k+1）項集，即先找出所有的頻繁1項集L1，隨后利用L1找到頻繁2項集的集合L2，再用頻繁2項集L2找L3，反復(fù)進行，直到找不到頻繁k項集。所有的頻繁集中找出符合一定置信度的規(guī)則，即產(chǎn)生用戶感興趣的關(guān)聯(lián)規(guī)則。將Ck設(shè)為候選k項集，算法的具體過程描述如下:

（1）以集合I作為候選集C1，通過對數(shù)據(jù)集掃描，得到候選集C1的支持度，將大于設(shè)置的最小支持度的元素提出，即頻繁1項集L1；

（2）掃描數(shù)據(jù)集，計算候選集Ck的支持度，找出大于最小支持度min_sup的元素作為頻繁k項集Lk；

（3）通過頻繁k（k大于1）項集Lk產(chǎn)生k+1項候選集Ck+1；

（4）迭代執(zhí)行步驟（2）、（3），不能找出k+1項候選集時算法結(jié)束。

Apriori算法每次迭代都要對全部數(shù)據(jù)做一次讀取，并做一些復(fù)雜的邏輯運算，是相當耗費時間的，如果將算法并行處理，在多節(jié)點同時執(zhí)行，將會大大地減少算法過程中的資源消耗。

1.2Hadoop的MapReduce編程模型

MapReduce是一種處理大量數(shù)據(jù)的并行編程模型和計算框架，將一個復(fù)雜的計算過程劃分到多個節(jié)點上執(zhí)行，將大任務(wù)分而治之，匯總每個節(jié)點上的運算結(jié)果得到最后的計算結(jié)果。主要包括Map和Reduce兩個過程：Map過程，數(shù)據(jù)被分成M個獨立的數(shù)據(jù)塊，M個mapper函數(shù)，每個map得到一個數(shù)據(jù)塊，按照一定的計算過程進行計算，將計算結(jié)果以Key-Value的形式輸出，中間結(jié)果中的Key-Value按照Key的值分組排序，形成N個Key-ValueList。Reduce過程，將中間結(jié)果Key-ValueList作為輸入，分配給N個Reduce函數(shù)，計算并輸出最終結(jié)果。MapReduce工作流程如圖1所示。

圖1　

在這一過程中，Map函數(shù)和Reduce函數(shù)的具體執(zhí)行過程都可以由用戶編程實現(xiàn)。

1.3Apriori算法的分布式化

將Apriori算法應(yīng)用到Hadoop中，主要目標是對算法中每一次迭代求頻繁項集的過程執(zhí)行一次mapreduce過程。計算過程設(shè)計如下：

（1）數(shù)據(jù)分塊。首先將數(shù)據(jù)提交到分布式文件系統(tǒng)，Map-Reduce將數(shù)據(jù)劃分為n個大小相同的數(shù)據(jù)塊，發(fā)送到集群中的m個節(jié)點。

（2）數(shù)據(jù)格式化。n個數(shù)據(jù)塊被格式化為鍵值對＜key，value＞。以num為每個屬性的標識，list為每個屬性對應(yīng)的列表值，格式化為＜num，list＞。

（3）Map過程。Map函數(shù)對輸入的數(shù)據(jù)記錄進行掃描，處理后生成＜key，value＞對，先產(chǎn)生該數(shù)據(jù)塊的頻繁1項集，然后找出該數(shù)據(jù)塊的頻繁k項集。頻繁1項集的產(chǎn)生過程與詞頻統(tǒng)計方法類似，局部頻繁k項集的計算過程與傳統(tǒng)的Apriori算法一致。

（4）Combine函數(shù)。Combine函數(shù)起一個協(xié)助Reduce函數(shù)的功能，在Map函數(shù)完成后，將Map函數(shù)本地輸出做一個合并，并生成局部的頻繁項集，然后再將合并后的鍵值對散列劃分到幾個不同的分區(qū)，每個分區(qū)對應(yīng)Reduce函數(shù)進行執(zhí)行。因為當原始數(shù)據(jù)量很大時，每個Map函數(shù)產(chǎn)生成千上萬條記錄，數(shù)據(jù)通過網(wǎng)絡(luò)發(fā)送到Reduce函數(shù)，將消耗相當大的網(wǎng)絡(luò)資源，產(chǎn)生數(shù)據(jù)延遲。

（5）Reduce函數(shù)。將Map函數(shù)的輸出作為Reduce的輸入，合并所有的局部頻繁項集，生成全部數(shù)據(jù)的候選頻繁項集。

（6）掃描原始數(shù)據(jù)。對原始數(shù)據(jù)中的每條記錄進行掃描，如果該記錄在全局候選頻繁項集中存在，則類似統(tǒng)計過程，將其寫入上下文對象Context中，傳遞給Reduce函數(shù)匯總。

（7）合并輸出結(jié)果。對Reduce函數(shù)的輸出進行合并計算，將所有大于用戶設(shè)置的最小支持度的值輸出，寫入分布式文件系統(tǒng)的輸出文件，即得到所求的頻繁項集。根據(jù)置信度對頻繁項集進行篩選，即可找到相應(yīng)的關(guān)聯(lián)規(guī)則。

流程如圖2所示。

圖2　

相比傳統(tǒng)單機模式下的數(shù)據(jù)挖掘，分布式化后的數(shù)據(jù)挖掘算法有如下幾個特點：

（1）掃描原始數(shù)據(jù)的次數(shù)減少，頻繁項集計算過程只需要對原始數(shù)據(jù)進行兩次掃描，降低了時間消耗和計算開銷。

（2）頻繁項集的查找可以在多節(jié)點并行執(zhí)行，并且，Map過程的執(zhí)行時間僅與輸入文件的大小成正比。

2　乙肝數(shù)據(jù)的挖掘?qū)崿F(xiàn)

2.1數(shù)據(jù)預(yù)處理

利用項目中獲取的30萬居民的體檢數(shù)據(jù)，篩選出乙肝抗原h(huán)bsag為陽性的患者15000條，即乙肝患者數(shù)據(jù)，進行嘗試性的數(shù)據(jù)挖掘。提取了病人年齡（age）、性別（gender）、職業(yè)（career）、是否高血壓（hypertension）、是否糖尿病（diabetes）、乙肝家族史（family_history_hb）、乙肝疫苗接種史（hb_vaccination）、吸煙史（smoke_habit）、飲酒史（drink_habit）、BMI指數(shù)（bmi）、肝部B超情況（bultrasound_liver）等30個字段作為每條數(shù)據(jù)的屬性，對這些數(shù)據(jù)做結(jié)構(gòu)化的統(tǒng)一，然后上傳到Hadoop集群，通過已完成的數(shù)據(jù)挖掘算法對數(shù)據(jù)進行分析，建立乙肝抗原陽性這一屬性值與其他屬性間的關(guān)系。具體實現(xiàn)步驟如下：

（1）搭建Hadoop集群，設(shè)置完全分布式模式，4個節(jié)點的配置如下：運行環(huán)境：Ubuntu、Hadoop版本：Hadoop0.20.2，JDK版本：JDK1.6.，處理器：Core duo e6700雙核處理器，主頻：3.2GHz，內(nèi)存：2GB。

（2）對數(shù)據(jù)進行預(yù)處理，如字符串格式的替換，屬性值的統(tǒng)一等，將預(yù)處理后的數(shù)據(jù)上傳到Hadoop集群的分布式文件系統(tǒng)中。

（3）將預(yù)先完成的分布式化后的Apriori算法移植到到Hadoop集群中的一個客戶端，指定要處理的數(shù)據(jù)路徑，運行客戶端數(shù)據(jù)挖掘程序，將任務(wù)提交到Hadoop集群。

（4）生成挖掘結(jié)果。

2.2挖掘結(jié)果分析

使用Hadoop集群結(jié)合分布式化的關(guān)聯(lián)規(guī)則算法，本例中處理數(shù)據(jù)條數(shù)約15000，設(shè)置最低支持為1000，置信度0.7，這兩項值可根據(jù)實際情況進行調(diào)整，挖掘算法挖掘出來的結(jié)果選取了代表性部分，如下所示：

其中，不同的整數(shù)值代表不同的屬性的不同值域，如22代表職業(yè)是農(nóng)民、96代表年齡段46～50等。根據(jù)關(guān)聯(lián)的重要度和概率強度，結(jié)合實際中的情況我們選取了以下幾條規(guī)則：

本次居民健康體檢范圍內(nèi)，乙肝患者職業(yè)多為農(nóng)民，且有吸煙的生活習(xí)慣，有飲酒史生活習(xí)慣的患病概率更高。乙肝患者年齡多集中在41～60歲，且BMI指數(shù)顯示體重超重的人患乙肝的概率更高；乙肝患者有一定概率出現(xiàn)肝硬化、脂肪肝；乙肝與心率、血壓無明顯聯(lián)系。

由于項目中得到的數(shù)據(jù)具有一定的地域局限性，因此得到的結(jié)果僅作為一個參考，當數(shù)據(jù)量規(guī)模足夠大，各個年齡段、各種職業(yè)類別的樣本足夠多時，挖掘結(jié)果將更加具有醫(yī)學(xué)研究價值。

分布式化后的關(guān)聯(lián)規(guī)則運行在集群上和運行在單機上的傳統(tǒng)情況相比，執(zhí)行效率有明顯提升，隨著集群節(jié)點的增加，針對相同數(shù)據(jù)量的計算，分布式系統(tǒng)中實現(xiàn)的算法加速比顯著上升，如圖3所示：

圖3　

同時，針對不同的數(shù)據(jù)量大小，也在分布式Apriori算法下進行了測試，4個節(jié)點環(huán)境下執(zhí)行時間對比如表1所示：

表1　

傳統(tǒng)模式下，運行在單機上的Apriori算法瓶頸在于候選集的生成，需要占用很大的空間和時間，當算法移植到分布式平臺中，算法執(zhí)行上的開銷會大大減少，并且集群中每個節(jié)點中的挖掘過程是不依賴的，減少節(jié)點間通信，使算法的效率得到了提高。當數(shù)據(jù)量龐大時，傳統(tǒng)單機模式的執(zhí)行效率只能依賴于硬件的提升，且效果不顯著，此時，分布式平臺的高效性將更加明顯。

3　結(jié)語

通過研究Hadoop分布式平臺的技術(shù)特點，結(jié)合數(shù)據(jù)挖掘技術(shù)，給出了基于分布式的Apriori算法設(shè)計思想，并將算法實現(xiàn)運用在居民體檢中的乙肝患者數(shù)據(jù)，對乙肝的并發(fā)癥等進行了數(shù)據(jù)分析。實驗表明，基于分布式的數(shù)據(jù)挖掘技術(shù)在醫(yī)療數(shù)據(jù)分析領(lǐng)域的應(yīng)用是有價值的。隨著醫(yī)院醫(yī)療數(shù)據(jù)的增加，居民對醫(yī)療健康的關(guān)注，基于分布式的數(shù)據(jù)分析能夠更大地發(fā)揮其高效性，分布式數(shù)據(jù)挖掘技術(shù)在醫(yī)療信息中的疾病診斷、治療、預(yù)測等諸多方面的研究將會被更加廣泛地應(yīng)用。

［1］趙虎.云計算環(huán)境下的關(guān)聯(lián)數(shù)據(jù)挖掘算法實現(xiàn)［D］.成都：電子科技大學(xué)，2011

［2］朱安柱.基于Hadoop的Apriori算法改進與移植的研究［D］.武漢：華中科技大學(xué)，2012

［3］鄭丹青．基于數(shù)據(jù)挖掘的臨床醫(yī)療數(shù)據(jù)分析系統(tǒng)［J］.長春工業(yè)大學(xué)學(xué)報（自然科學(xué)版），2011

［4］周云輝，王嬌.數(shù)據(jù)挖掘技術(shù)在醫(yī)療領(lǐng)域中的應(yīng)用研究［J］.機械工程與自動化，2013

［5］鄭啟龍，房明，汪勝，王向前，吳曉偉.基于MapReduce模型的并行科學(xué)計算［J］.微電子學(xué)與計算機

Distributed；Apriori Algorithm；Medical Data；Data Mining

Application of Association Rules Algorithm Based on Distributed in Medical Data Mining

LI Xiao-nan1，MA Yuan-ji2，XIAO Chuan3
（1．College of Computer Science，Sichuan University，Chengdu 610065；2.West China Hospital of Sichuan University，Chengdu 610041；3.West China School of Public Health，Sichuan University，Chengdu 610041）

1007-1423（2015）08-0047-04

10.3969/j.issn.1007-1423.2015.08.011

李曉楠（1989-），女，山西應(yīng)縣人，在讀碩士研究生，研究方向這計算機網(wǎng)絡(luò)與信息系統(tǒng)、醫(yī)療信息化

馬元吉（1981-），男，四川新都人，碩士研究生，講師，研究方向為病毒性肝病的基礎(chǔ)與臨床

肖川（1990-），女，湖南長沙人，在讀碩士研究生，研究方向為流行病學(xué)

2015-01-20

通過研究基于Hadoop平臺的map/reduce思想，針對關(guān)聯(lián)規(guī)則算法Apriori算法提出其在分布式平臺下的改進算法，利用分布式化的Apriori算法對居民體檢中發(fā)現(xiàn)的乙肝患者疾病數(shù)據(jù)進行分析挖掘，主要建立乙肝陽性和其他健康指標間的關(guān)聯(lián)規(guī)則。實驗結(jié)果證明關(guān)聯(lián)規(guī)則算法Apriori在醫(yī)療數(shù)據(jù)挖掘中的有效性和高效性。

分布式；Apriori算法；醫(yī)療數(shù)據(jù)；數(shù)據(jù)挖掘

國家重大科技專項（No.2012ZX10004-901）、四川省科技支撐計劃項目（No.2013SZ0002、No.2014SZ0109）

By researching on the map/reduce theory based on Hadoop distributed system,for Apriori algorithm,which is a kind of association rules algorithm,puts forward the improved algorithm in a distributed platform.Uses distributed data Apriori algorithm to analyze data of disease patients with hepatitis B which is found in healthy examination.The purpose is to establish association rules between HBV-positive and other health indicators.The results prove that the association rule mining algorithms on medical data is effectiveness and efficiency.