張 潤，馮云霞

(青島科技大學(xué) 信息科學(xué)技術(shù)學(xué)院，山東 青島 266000)

0 引 言

肺癌是全球亟待解決的危害生命的最常見的癌癥之一。2017年，世界衛(wèi)生組織的最新數(shù)據(jù)表示，僅僅2015年肺癌導(dǎo)致了約170萬人死亡[1]。研究表明，肺癌早期患者的治愈率較高，而肺癌晚期患者的存活率僅為15%[2]。主要原因是由于肺癌早期癥狀不明顯，而中后期發(fā)病速度快，臨床診斷時(shí)大多為中晚期[3]。

關(guān)聯(lián)規(guī)則是反映出一個(gè)事務(wù)與其他事務(wù)之間相互關(guān)聯(lián)或依賴的關(guān)系，看似不相關(guān)的事件的邏輯關(guān)系的知識，并運(yùn)用于對同一事件中不同的特征之間的依存關(guān)系[4]。一份某種疾病的電子病歷包含太多數(shù)據(jù)，若拿來直接用作預(yù)測或分類，會(huì)有多項(xiàng)不相關(guān)的因素干擾，因此，通過關(guān)聯(lián)分析能尋找某類與該疾病存在密切相關(guān)的特征。其中，Apriori算法是關(guān)聯(lián)規(guī)則中經(jīng)典的算法。關(guān)聯(lián)規(guī)則的運(yùn)用最早追溯到20世紀(jì)90年代，Agrawal首次提出關(guān)聯(lián)規(guī)則問題，并將其運(yùn)用在分析顧客交易數(shù)據(jù)中的關(guān)聯(lián)因素[5]。此后，為了提高該算法的運(yùn)行速率，不斷有改進(jìn)算法提出，如Feng等將MapReduce與Apriori算法相結(jié)合，設(shè)計(jì)了一種適用于大數(shù)據(jù)量的MH-ACT方法，把頻繁項(xiàng)集分成幾個(gè)互不相交的塊，只對每個(gè)分塊掃描一次，將結(jié)果合并到一起再計(jì)算所有項(xiàng)集的支持度[6]。Almaolegi等為了降低數(shù)據(jù)庫的規(guī)模，選用部分?jǐn)?shù)據(jù)庫中部分采樣計(jì)算頻繁項(xiàng)集，用數(shù)據(jù)庫中剩余的數(shù)據(jù)來驗(yàn)證這些結(jié)果是否正確，這樣大大降低了算法的時(shí)間復(fù)雜度[7]。Shah等將哈希函數(shù)引入Apriori算法中，從而降低候選集的數(shù)量，提高了運(yùn)算速率[8]。越來越多的改進(jìn)算法，通過降低數(shù)據(jù)庫的規(guī)模、分布式處理頻繁項(xiàng)集、減少候選項(xiàng)集數(shù)目、引入MapReduce架構(gòu)等方法，能夠彌補(bǔ)傳統(tǒng)Apriori算法的缺點(diǎn)。

1 Hadoop平臺(tái)與Apriori算法

1.1 Hadoop平臺(tái)

Hadoop分布式廣泛應(yīng)用于多個(gè)軟硬件平臺(tái)，能夠高速處理大規(guī)模數(shù)據(jù)的并行運(yùn)算和存儲(chǔ)問題，使用Java解決PB級的數(shù)據(jù)[9]。Hadoop平臺(tái)主要由并行編程模型MapReduce、分布塊HDFS和開源數(shù)據(jù)庫HBase構(gòu)成[10]。Hadoop實(shí)現(xiàn)分布式并行數(shù)據(jù)處理時(shí)，若客戶端想訪問數(shù)據(jù)塊，名稱節(jié)點(diǎn)(NameNode)負(fù)責(zé)數(shù)據(jù)塊的具體路徑映射，并找到對應(yīng)的數(shù)據(jù)節(jié)點(diǎn)(DateNode)，計(jì)算出數(shù)據(jù)的具體位置節(jié)點(diǎn)信息[11]。整個(gè)過程中，NameDode作為Hadoop的主服務(wù)器節(jié)點(diǎn)，處理數(shù)據(jù)塊到Name Node的映射關(guān)系，文件不通過其進(jìn)行發(fā)送[12]。DataNode完成對數(shù)據(jù)塊進(jìn)行創(chuàng)建、復(fù)制和刪除的任務(wù)。工作流程如圖1所示。

圖1 HDFS的工作流程

1.2 Apriori算法

作為數(shù)據(jù)挖掘中的重要工具，關(guān)聯(lián)規(guī)則最早運(yùn)用在分析顧客交易數(shù)據(jù)中的關(guān)聯(lián)因素中[13]。最經(jīng)典的算法即Apriori算法，首先按照最小支持度找到所有的頻繁項(xiàng)集，然后產(chǎn)生強(qiáng)關(guān)聯(lián)規(guī)則。Apriori算法的挖掘過程包括挖掘頻繁項(xiàng)集和關(guān)聯(lián)規(guī)則的產(chǎn)生。

(1)頻繁項(xiàng)集的挖掘。

設(shè)置最小支持度閾值(SUP_min)，在所有的候選項(xiàng)集中找出大于或等于SUP_min的項(xiàng)集，即頻繁項(xiàng)集。

(2)強(qiáng)關(guān)聯(lián)規(guī)則的產(chǎn)生。

根據(jù)第一步得出的頻繁項(xiàng)集中，給定最小置信度(CONF_min)，若滿足CONF_min的規(guī)則，稱之為強(qiáng)關(guān)聯(lián)規(guī)則。若存在項(xiàng)集{I3，I4，I5}，則規(guī)則為{I3→I4，I5}，{I4→I3，I5}，{I5→I3，I4}，{I3，I4→I5}，{I3，I5→I4}，{I4，I5→I3}。

Apriori算法是頻繁挖掘項(xiàng)集中最重要的算法，是通過逐層迭代的候選生成方法[14]。核心是通過K-項(xiàng)集挖掘(K+1)-項(xiàng)集[15]。衡量Apriori算法的兩個(gè)重要標(biāo)準(zhǔn)：

(1)支持度(support)：描述關(guān)聯(lián)樣本中某個(gè)特征出現(xiàn)的頻率。指對存在的項(xiàng)集X、Y和B(X、Y均屬于項(xiàng)目集B)，事物集B均包含事物集X、Y的百分比。存在如下關(guān)系：

(2)置信度(confidence)：描述兩個(gè)特征之間相互關(guān)聯(lián)的強(qiáng)度，指在事物B中包含X、Y事物數(shù)的百分比，關(guān)系如下：

支持度和置信度是Apriori算法中兩個(gè)最重要的概念，兩者通過0%～100%的概率來衡量事務(wù)之間的緊密聯(lián)系程度。最小支持度和最小置信度由人為設(shè)定，只有同時(shí)滿足最小支持度和最小置信度才能稱為兩者具有強(qiáng)關(guān)聯(lián)度。

2 基于Hadoop平臺(tái)的Apriori算法并行化改進(jìn)

基于Hadoop平臺(tái)改進(jìn)Apriori算法有兩種主要方法：一種是數(shù)據(jù)集均勻分布在每個(gè)節(jié)點(diǎn)上，對局部并行挖掘頻繁項(xiàng)集，收集全局頻繁項(xiàng)集；第二種是使用MapReduce迭代挖掘頻繁項(xiàng)集[16]。

本實(shí)驗(yàn)中，由于傳統(tǒng)的Apriori算法的執(zhí)行效率低、頻繁掃描數(shù)據(jù)庫，利用Hadoop平臺(tái)結(jié)合Apriori算法迭代挖掘頻繁項(xiàng)集，多次掃描數(shù)據(jù)庫尋找候選項(xiàng)集。利用MapReduce將輸入數(shù)據(jù)進(jìn)行Map分塊，在每次Apriori算法循環(huán)迭代時(shí)，對分布在每臺(tái)計(jì)算機(jī)上的數(shù)據(jù)塊進(jìn)行累積求和，累計(jì)候選項(xiàng)集Ck的次數(shù)。在每個(gè)分塊數(shù)據(jù)中，通過求和運(yùn)算計(jì)算候選項(xiàng)集Ck中屬性的支持度，找出頻繁項(xiàng)集Lk。基于Hadoop平臺(tái)的Apriori算法的并行化優(yōu)化方法如下：

(1)執(zhí)行Apriori算法得到候選-1項(xiàng)集C1，將C1與原始數(shù)據(jù)集對比，得到候選項(xiàng)集C1中每個(gè)屬性的支持度，通過MapReduce框架程序處理獲得頻繁項(xiàng)集L1。

(2)在分布于每個(gè)計(jì)算機(jī)上的Map塊中，通過頻繁項(xiàng)集L1，產(chǎn)生候選-2項(xiàng)集C2，并逐次產(chǎn)生候選-k項(xiàng)集Ck。

(3)在MapReduce框架的Reduce進(jìn)程中，通過求和運(yùn)算對每個(gè)分布在Map節(jié)點(diǎn)上的k項(xiàng)候選項(xiàng)集的支持度累計(jì)，得到在k項(xiàng)時(shí)的全局支持度計(jì)數(shù)。比較全局支持度計(jì)數(shù)與最小支持度閾值，獲得頻繁項(xiàng)集Lk。

(4)當(dāng)前一臺(tái)計(jì)算機(jī)計(jì)算出頻繁項(xiàng)集后，后一臺(tái)計(jì)算機(jī)啟動(dòng)Map進(jìn)程并計(jì)算出頻繁項(xiàng)集，以此步驟循環(huán)迭代，直到集合Lk為空，結(jié)束進(jìn)程；否則繼續(xù)執(zhí)行步驟(2)。

(5)對處理完的數(shù)據(jù)塊保存于HDFS中，并挖掘出相應(yīng)的強(qiáng)關(guān)聯(lián)規(guī)則。

圖2為改進(jìn)的算法流程。

圖2 改進(jìn)Apriori算法流程

3 改進(jìn)Apriori算法在肺癌電子病歷中的應(yīng)用

3.1 實(shí)驗(yàn)環(huán)境

實(shí)驗(yàn)選用的5臺(tái)PC機(jī)，包括一臺(tái)名稱節(jié)點(diǎn)NameNode和4臺(tái)數(shù)據(jù)節(jié)點(diǎn)DataNode，選取的計(jì)算機(jī)配置如表1所示。

表1 計(jì)算機(jī)配置

Hadoop平臺(tái)的一臺(tái)計(jì)算器作為服務(wù)節(jié)點(diǎn)NameNode Master，另外4臺(tái)計(jì)算機(jī)作為服務(wù)節(jié)點(diǎn)DataNode Slave，IP分配如表2所示。

表2 各個(gè)節(jié)點(diǎn)的IP分配

3.2 實(shí)驗(yàn)數(shù)據(jù)預(yù)處理

實(shí)驗(yàn)所使用的數(shù)據(jù)均來自本市某三甲級醫(yī)院的腫瘤科電子病歷，該電子病歷記錄患者從入院的身份數(shù)據(jù)、主訴、醫(yī)囑、檢驗(yàn)數(shù)據(jù)到出院的各項(xiàng)數(shù)據(jù)。實(shí)驗(yàn)數(shù)據(jù)選取2017年3月至2018年9月的患者病歷，以分析肺癌與吸煙、肺部疾病史、職業(yè)致病因子、咳嗽胸痛等信息之間的關(guān)聯(lián)信息，以及癥狀之間的潛在規(guī)律。在進(jìn)行關(guān)聯(lián)分析之前，首先要對數(shù)據(jù)進(jìn)行預(yù)處理，包括對數(shù)據(jù)合并、數(shù)據(jù)結(jié)構(gòu)化、數(shù)據(jù)清洗以及數(shù)據(jù)轉(zhuǎn)換等步驟。本次實(shí)驗(yàn)共選取肺部腫瘤患者共18個(gè)屬性(包括性別、年齡、吸煙史、肺部疾病等信息)進(jìn)行分析。

(1)數(shù)據(jù)合并：從醫(yī)院his系統(tǒng)導(dǎo)出來的電子病歷分為醫(yī)囑、診斷、檢驗(yàn)等模塊，需要根據(jù)患者唯一的PID標(biāo)識進(jìn)行關(guān)聯(lián)，將患者的診斷、主訴、既往史、檢驗(yàn)數(shù)據(jù)同步，所以運(yùn)用excel表格對數(shù)據(jù)集成合并處理。

(2)數(shù)據(jù)結(jié)構(gòu)化：使用ICTCLAS作為分詞工具，建立醫(yī)學(xué)用戶詞典，提取按詞頻分類結(jié)果的結(jié)構(gòu)化屬性表。

(3)數(shù)據(jù)清洗：提取特征屬性的結(jié)構(gòu)化電子病歷存在異常數(shù)據(jù)、缺失值數(shù)據(jù)[17]。缺失值處理中，對數(shù)值型數(shù)據(jù)，選擇均值代替；對字符型數(shù)據(jù)，選擇眾數(shù)代替。存在大量缺失值的數(shù)據(jù)，選擇直接刪除。異常值處理中，計(jì)算出每類數(shù)據(jù)所占比例，并畫出正態(tài)分布，對于所占比例過低的數(shù)據(jù)判斷為異常值[18]。異常值的處理方式與缺失值相同。

(4)數(shù)據(jù)轉(zhuǎn)換：由于Apriori算法只能對離散化數(shù)據(jù)進(jìn)行處理，所以在進(jìn)行數(shù)據(jù)挖掘前，要對連續(xù)性數(shù)值進(jìn)行離散化處理。以吸煙史為例，從未吸煙為0，1至10年為1，10至20年為2等。

3.3 改進(jìn)算法對比分析

在本實(shí)驗(yàn)中，由于涉及的患者病歷數(shù)據(jù)量較大，為了獲得更加有價(jià)值的信息，將最小值支持度和最小置信度不斷改進(jìn)。在最小置信度固定為0.6的情況下，最小支持度為0.06時(shí)，挖掘的強(qiáng)關(guān)聯(lián)規(guī)則太多，這種情況下的規(guī)則是無意義的。直到最小支持度提高到0.1時(shí)，挖掘的關(guān)聯(lián)規(guī)則數(shù)量產(chǎn)生了明顯的變化。通過多次實(shí)驗(yàn)對比，選定最小支持度為0.1，最小置信度為0.6，這是肺癌數(shù)據(jù)挖掘較為合適的參數(shù)設(shè)置。

Apriori串行算法與改進(jìn)并行算法在處理相同規(guī)模數(shù)據(jù)時(shí)所用時(shí)間的對比如表3所示。當(dāng)數(shù)據(jù)規(guī)模不斷增大時(shí)，串行算法所用的時(shí)間明顯增多，直到提示內(nèi)存不足。而改進(jìn)的并行算法在處理大規(guī)模數(shù)據(jù)時(shí)完成能力較好。因此，在處理小規(guī)模數(shù)據(jù)量時(shí)，傳統(tǒng)的串行算法比改進(jìn)的并行算法效果好，這是因?yàn)镠adoop平臺(tái)的節(jié)點(diǎn)啟動(dòng)運(yùn)行需要一定的時(shí)間；在處理大規(guī)模數(shù)據(jù)量時(shí)，改進(jìn)的并行算法的效率遠(yuǎn)遠(yuǎn)高于傳統(tǒng)的串行算法。

表3 改進(jìn)算法與傳統(tǒng)算法的比較

節(jié)點(diǎn)數(shù)選取1、2、3、4，電子病歷數(shù)據(jù)量大小分別為1 G、2 G、3 G。每次實(shí)驗(yàn)進(jìn)行3輪取平均值，最終的運(yùn)行時(shí)間結(jié)果如圖3所示。

圖3 改進(jìn)算法實(shí)驗(yàn)結(jié)果

從圖3中可以看出，從下到上的折線分別為1 G、2 G、3 G大小數(shù)據(jù)量的運(yùn)行結(jié)果，隨著數(shù)據(jù)規(guī)模的不斷增大，運(yùn)行所用時(shí)間隨著節(jié)點(diǎn)數(shù)的增加而減少。因此，增加Hadoop集群的節(jié)點(diǎn)數(shù)可以顯著提高數(shù)據(jù)處理能力，基于Hadoop平臺(tái)改進(jìn)的Apriori算法具有良好的性能，在處理肺癌電子病歷具有較高的執(zhí)行效率。

3.4 實(shí)驗(yàn)結(jié)果

最終得到強(qiáng)關(guān)聯(lián)規(guī)則，部分如表4所示.從表中的關(guān)聯(lián)結(jié)果，得到以下結(jié)論：

(1)在性別對比上，患肺癌男性遠(yuǎn)遠(yuǎn)高于女性，這與男性為吸煙主要群體有一定關(guān)系。在年齡對比上，60至70歲的老年人患肺癌最多，但由于吸煙人數(shù)的增多，肺癌患者也呈現(xiàn)低齡化趨勢，尤其是在年輕的男性中，患肺癌人數(shù)逐年增加。

(2)有胸悶憋氣、胸痛、咳嗽、咳血等癥狀與肺癌有著密切的關(guān)系，對化驗(yàn)數(shù)據(jù)的關(guān)聯(lián)規(guī)則挖掘，基于CT影像數(shù)據(jù)能夠及時(shí)發(fā)現(xiàn)早期肺癌。

(3)吸煙對肺癌有著嚴(yán)重的影響，吸煙史與肺癌的發(fā)病率有極大的關(guān)系。

(4)肺癌與職業(yè)治病因子之間有一定關(guān)聯(lián)規(guī)則，從事石油、粉末、煤炭等職業(yè)人群患肺癌的概率較大。

(5)肺部疾病患者中，有肺結(jié)核等疾病的患者癌變的可能性比較大。

改進(jìn)的算法與臨床醫(yī)學(xué)結(jié)論相符合，能夠挖掘疾病與病因之間的潛在規(guī)律和規(guī)則，這對肺癌疾病的分析與研究具有重要的意義。

表4 關(guān)聯(lián)規(guī)則結(jié)果

4 結(jié)束語

基于Hadoop平臺(tái)改進(jìn)的Apriori算法可以協(xié)助臨床醫(yī)生快速、準(zhǔn)確、高效地做出判斷，對肺癌早期預(yù)防、早期治療具有重要的意義。通過實(shí)驗(yàn)結(jié)果可以看出，在處理大規(guī)模電子病歷數(shù)據(jù)時(shí)，基于Hadoop平臺(tái)改進(jìn)的Apriori算法的執(zhí)行效率遠(yuǎn)遠(yuǎn)高于傳統(tǒng)Apriori算法。并且改進(jìn)后的算法具有良好的可移植性，能夠適用于肺癌電子病歷的數(shù)據(jù)挖掘，及時(shí)有效地挖掘出肺部腫瘤疾病與癥狀之間的潛在規(guī)律，具有一定可行性。