李曉楠，馬元吉，肖川

（1.四川大學(xué)計(jì)算機(jī)學(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é)計(jì)算機(jī)學(xué)院，成都610065；2.四川大學(xué)華西醫(yī)院，成都610041；3.四川大學(xué)華西公共衛(wèi)生學(xué)院，成都610041）

0　引言

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

1　Apriori算法及其分布式化

1.1Apriori算法

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

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

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

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

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

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

1.2Hadoop的MapReduce編程模型

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

圖1　

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

1.3Apriori算法的分布式化

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

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

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

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

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

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

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

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

流程如圖2所示。

圖2　

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

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

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

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

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

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

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

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

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

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

2.2挖掘結(jié)果分析

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

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

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

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

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

圖3　

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

表1　

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

3　結(jié)語

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

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

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

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

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

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

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)縣人，在讀碩士研究生，研究方向這計(jì)算機(jī)網(wǎng)絡(luò)與信息系統(tǒng)、醫(yī)療信息化

馬元吉（1981-），男，四川新都人，碩士研究生，講師，研究方向?yàn)椴《拘愿尾〉幕A(chǔ)與臨床

肖川（1990-），女，湖南長(zhǎng)沙人，在讀碩士研究生，研究方向?yàn)榱餍胁W(xué)

2015-01-20

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

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

國(guó)家重大科技專項(xiàng)（No.2012ZX10004-901）、四川省科技支撐計(jì)劃項(xiàng)目（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.