基于改進Apriori算法的肺癌致病因素研究

張 潤，馮云霞

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

0 引 言

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

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

1 Hadoop平臺與Apriori算法

1.1 Hadoop平臺

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

圖1 HDFS的工作流程

1.2 Apriori算法

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

(1)頻繁項集的挖掘。

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

(2)強關聯(lián)規(guī)則的產生。

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

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

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

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

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

2 基于Hadoop平臺的Apriori算法并行化改進

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

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

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

(2)在分布于每個計算機上的Map塊中，通過頻繁項集L1，產生候選-2項集C2，并逐次產生候選-k項集Ck。

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

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

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

圖2為改進的算法流程。

圖2 改進Apriori算法流程

3 改進Apriori算法在肺癌電子病歷中的應用

3.1 實驗環(huán)境

實驗選用的5臺PC機，包括一臺名稱節(jié)點NameNode和4臺數(shù)據(jù)節(jié)點DataNode，選取的計算機配置如表1所示。

表1 計算機配置

Hadoop平臺的一臺計算器作為服務節(jié)點NameNode Master，另外4臺計算機作為服務節(jié)點DataNode Slave，IP分配如表2所示。

表2 各個節(jié)點的IP分配

3.2 實驗數(shù)據(jù)預處理

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

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

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

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

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

3.3 改進算法對比分析

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

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

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

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

圖3 改進算法實驗結果

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

3.4 實驗結果

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

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

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

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

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

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

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

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

4 結束語

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