基于電子病歷的肺癌診斷決策樹算法①

馮云霞,張 潤

(青島科技大學(xué) 信息科學(xué)技術(shù)學(xué)院,青島 266061)

1 引言

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

隨著現(xiàn)代技術(shù)的快速發(fā)展,計算機技術(shù)運用在醫(yī)學(xué)領(lǐng)域的越來越多.特別在疾病預(yù)防、診斷、治療與檢測方面,數(shù)據(jù)挖掘技術(shù)發(fā)揮著重要的作用.有基于主成分分析的GEP算法[4]、基于遺傳算法的GA-SVM模型[5]及GA-BPNN模型[6]、基于粗糙集理論的決策樹模型[7]、模糊聚類FCM模型[8]、基于粒子群算法的支持向量機模型[9]等.本文將主成分分析法與C5.0算法相結(jié)合,用于早期肺癌輔助診斷.主成分分析法是統(tǒng)計學(xué)中的方法,將復(fù)雜的原始數(shù)據(jù)提取出較為簡單的數(shù)據(jù),并且這些簡單數(shù)據(jù)能夠最大程度地代表原始數(shù)據(jù)的特點,從而達到簡化屬性的目的.決策樹是常用于疾病預(yù)測的一種算法,決策樹是基于信息論方法的對數(shù)據(jù)進行分類的數(shù)據(jù)挖掘經(jīng)典算法,通過訓(xùn)練大量數(shù)據(jù)進行分類,從中尋找疾病與患者的生活習(xí)性、發(fā)病癥狀、檢驗數(shù)據(jù)之間潛在、有價值的信息.

2 相關(guān)理論基礎(chǔ)

2.1 主成分分析法相關(guān)原理及基本思想

主成分分析(Principal Component Analysis,PCA)于20世紀初首次運用在數(shù)學(xué)領(lǐng)域中,Pearson通過運算將具有很多特征的屬性降低到幾個具有代表性的屬性,這些屬性既能克服單一屬性不能完全反映數(shù)據(jù)信息的缺點,又能克服無關(guān)屬性過多而造成的干擾[10].基本思想是:主成分分析法能將復(fù)雜的原始數(shù)據(jù)提取出較為簡單的數(shù)據(jù),并且這些簡單數(shù)據(jù)能夠最大程度地代表原始數(shù)據(jù)的特點,從而達到簡化屬性的目的.

通常在數(shù)據(jù)選取后,需要進行特征選擇,特征的選取若維度過高,需要通過數(shù)學(xué)變換來將特征對應(yīng)到低維度空間.對于要處理的肺癌電子病歷中的屬性,各種屬性混雜可能多達上百個,而其中有些屬性可能是關(guān)鍵,另一些屬性可能沒有用,并且還能影響到?jīng)Q策樹模型的構(gòu)建.基于此,選用主成分分析來約簡屬性,降低特征維度,提高決策樹模型的準確度.

主成分分析中常用的幾個公式:

(3)樣本x、y的協(xié)方差:

PCA具體原理可有圖1看出,經(jīng)過坐標變換y1和y2方向作為新的基底,由于y2方向上數(shù)據(jù)的方差較小,降低數(shù)據(jù)維度的時候可以保證不會太多的損失信息,因此這一維度的數(shù)據(jù)可以丟棄.這樣重構(gòu)的坐標系得到的數(shù)據(jù)與原數(shù)據(jù)之間的誤差降到最低.經(jīng)過PCA后,新的維度間的數(shù)據(jù)是線性不相關(guān)的,并按照方差由大到小排列選取主成分.

圖1 PCA原理

2.2 決策樹相關(guān)理論

決策樹算法是在信息論基礎(chǔ)上分類和預(yù)測的重要技術(shù)之一,采用自頂而下的遞歸算法建立一棵類似于自然界中的樹結(jié)構(gòu),包括根節(jié)點、分枝、葉節(jié)點組成[11].決策樹產(chǎn)生的標準依據(jù)信息熵的計算,通常包括兩步:(1)開始所有屬性都在根節(jié)點,然后根據(jù)信息熵的計算決定分裂屬性,用不同的測試數(shù)據(jù)進行分割.(2)決策樹的剪枝是為了彌補決策樹過擬合現(xiàn)象,通過刪除異常的孤立點和噪音,一般分為前剪枝和后剪枝[12].

在ID3算法中,采用最大信息增益作為分支判定.而ID3算法由于不能對連續(xù)數(shù)據(jù)處理,因而C4.5算法進行了改進采用信息增益率作為分支判定,可以對連續(xù)數(shù)據(jù)處理.C5.0算法在C4.5算法的基礎(chǔ)上提高了內(nèi)存和使用效率.

在決策樹算法總,計算分裂屬性的重要指標有如下3個:

已知數(shù)據(jù)集M,按照離散度C分成n個特征子集,n個特征子集包括A1,A2,···,An.

(1)信息熵ENTROPY(M):是指數(shù)據(jù)M中不同特征屬性數(shù)量的分布均勻程度.若分布不均勻,則信息熵偏低;分布較為均勻,則信息熵較高.其公式如下:

其中,Pi指的是特征屬性A在數(shù)據(jù)集M中所占的比例.

(2)信息增益(info_Gain):信息增益是形容數(shù)據(jù)集M中,特征屬性X在M中的復(fù)雜程度.表示為分支前M的復(fù)雜程度-分支后A的復(fù)雜程度,若信息增益值越大則說明節(jié)點的復(fù)雜程度高;反之,則節(jié)點復(fù)雜程度低.其公式如下:

信息增益是ID3算法中屬性分支的衡量標準,但其缺點是更傾向于特征屬性最多的那類,因此,C5.0算法采用信息增益率來選擇屬性分支.

(3)信息增益率(info_GAINRATIO):信息增益率是C4.5算法以后所運用的標準,表示信息增益與分裂信息之間的比值.在決策樹模型中,某個節(jié)點的信息增益率越大,代表該屬性的分支效果越好.其公式如下:

其中,split_info_GAIN是分裂因子,表示分支后的子結(jié)點的信息增益,其計算公式如下:

3 基于優(yōu)化決策樹算法的早期肺癌輔助診斷模型

3.1 基于主成分分析法的特征簡化

由于決策樹模型具有不穩(wěn)定性,數(shù)據(jù)集稍微改動,則會造成決策樹的完全改變.因此,在選取輸入的訓(xùn)練屬性要格外注意,若數(shù)據(jù)的本身屬性過多,有與肺癌不相關(guān)的屬性存在,那么決策樹模型可能選擇無關(guān)屬性分類,造成結(jié)果不準確.因此,我們在建模之前進一步對數(shù)據(jù)降維,從而達到簡化模型的目的,提取特征屬性的主要成分,達到最優(yōu)模型.在主成分分析法中,最重要的定義是對累計貢獻率的設(shè)定,若設(shè)定過低,則難以達到降維的目的;若設(shè)定過高,則造成數(shù)據(jù)過多的信息損失.另一種是對特征根大于1的屬性作為分界點選取合適的屬性.

基于主成分分析法的特征降維步驟如下:

輸入:電子病歷樣本集G={x1,x2,xm},降維維數(shù)d';輸出:屬性降維后的樣本集.images/BZ_263_1675_1153_1916_1194.png1.病歷集取中心化處理:images/BZ_263_1652_1234_1869_1275.png.在這里不需要對數(shù)據(jù)去中心化,因為在數(shù)據(jù)預(yù)處理中已經(jīng)對數(shù)據(jù)標準化,排除數(shù)據(jù)量綱不同造成的影響.2.求協(xié)方差矩陣XXT.3.特征分解法求XXT的特征根和特征向量.∑ images/BZ_263_1290_1579_1453_1604.png5.返回4.滿足特征根＞1或累計貢獻率＞0.85的d'個特征值對應(yīng)的特征向量.images/BZ_263_1390_1621_1632_1663.png

3.2 早期肺癌輔助診斷模型構(gòu)建

肺癌輔助診斷決策樹模型的實現(xiàn)過程:

輸入:主成分分析法簡化后的病歷特征屬性.輸出:基于C5.0算法的決策樹模型.1.對主成分分析法簡化后的23個特征屬性計算每個特征屬性的取值范圍.2.如果當前的病歷集的特征取值全部相同,則葉子節(jié)點即為決策屬性.3.否則,計算23個特征屬性的信息熵增益;針對連續(xù)值,年齡、日均吸煙量等2個特征求其離散值和基于決策屬性的信息增益率;針對離散值,剩下的性別、咳嗽咳痰等特征,直接求其基于決策屬性的信息增益率.4.選擇信息增益率最大的特征作為決策樹模型的節(jié)點,最后將此特征從條件屬性中刪除.5.按照特征的取值劃分樣本集,并返回到步驟2.6.返回決策樹模型T.

3.3 模型剪枝

決策樹容易造成過擬合現(xiàn)象,對訓(xùn)練數(shù)據(jù)診斷結(jié)果良好,對測試數(shù)據(jù)卻沒有較好的診斷效果.因此,本文針對決策樹算法的不足,對其進行優(yōu)化處理,通過剪枝操作解決過擬合現(xiàn)象.模型優(yōu)化的思路:對生成的決策樹T0,計算每個非葉子節(jié)點α值,根據(jù)設(shè)定的最小α值進行剪枝,分別得到T1,T2,···直到只有根節(jié)點Tn;在測試集上,根據(jù)實際的誤差值分別對這n個決策樹進行估計,選擇損失函數(shù)最低的樹Tk作為優(yōu)化后的決策樹.

決策樹優(yōu)化過程偽代碼如下:

輸入:決策樹 T, α.輸出:剪枝后的決策樹Tk.1.計算每個非葉子節(jié)點α值.2.對系數(shù)α最小的節(jié)點進行剪枝得到Ti (i=0,1,…,n).3.計算以r節(jié)點為根的子樹Tr剪枝前后的損失函數(shù).4.若 C1≥C2,則剪枝.images/BZ_264_958_923_1163_952.png5.重復(fù)步驟1～4直到只有根節(jié)點Tn停止,得到剪枝后的決策樹系列.6.在測試集上,根據(jù)實際的誤差值分別對這n個決策樹進行估計,選擇損失函數(shù)最低的樹Tk作為優(yōu)化后的決策樹,返回決策樹Tk.images/BZ_264_218_1082_389_1115.png

4 實驗驗證

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

本實驗所使用的數(shù)據(jù)均來自本市某三甲級醫(yī)院的腫瘤科電子病歷,數(shù)據(jù)選取2017年3月至2018年9月的患者病歷,該電子病歷記錄患者從入院的身份數(shù)據(jù)、主訴、醫(yī)囑、檢驗數(shù)據(jù)到出院的各項數(shù)據(jù).首先要對數(shù)據(jù)進行預(yù)處理,包括對數(shù)據(jù)合并、數(shù)據(jù)結(jié)構(gòu)化、數(shù)據(jù)清洗、以及數(shù)據(jù)轉(zhuǎn)換等步驟.本次實驗共選取肺部腫瘤患者共28個屬性,包括性別、年齡、吸煙史、肺部疾病等信息進行分析,預(yù)處理后的數(shù)據(jù)如圖2所示.

(1)數(shù)據(jù)合并:從醫(yī)院His系統(tǒng)導(dǎo)出來的電子病歷分為醫(yī)囑、診斷、檢驗等模塊,需要將根據(jù)患者唯一的PID標識進行關(guān)聯(lián),將患者的診斷、主訴、既往史、檢驗數(shù)據(jù)同步,所以運用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ù)[13].缺失值處理中,對數(shù)值型數(shù)據(jù),選擇均值代替;對字符型數(shù)據(jù),選擇眾數(shù)代替.存在大量缺失值的數(shù)據(jù),選擇直接刪除.異常值處理中,計算出每類數(shù)據(jù)所占比例,并畫出正態(tài)分布,對于所占比例過低的數(shù)據(jù)判斷為異常值[14].異常值的處理方式與缺失值相同.

(4)數(shù)據(jù)轉(zhuǎn)換:在進行數(shù)據(jù)挖掘前,要對連續(xù)性數(shù)值離散化處理.以吸煙史為例,從未吸煙為0,1至10年為1,10至20年為2等.

圖2 數(shù)據(jù)預(yù)處理

4.2 實驗過程

(1)傳統(tǒng)決策樹模型:首先運用C5.0算法對預(yù)處理后的數(shù)據(jù)進行建模,將結(jié)果保存下來.

(2)運用主成分分析法對數(shù)據(jù)進行降維處理,將結(jié)果保存下來,再對降維后的數(shù)據(jù)用C5.0算法建模,得到實驗結(jié)果.

4.3 實驗結(jié)果

4.3.1 兩種主成分分析特征降維結(jié)果

經(jīng)過主成分分析算法降維后,本文根據(jù)主成分特征根大于1以及主成分累計貢獻率大于85%來提取特征:

(1)基于Kaiser標準化的正交旋轉(zhuǎn)法提取特征根取值大于1的屬性,旋轉(zhuǎn)18次后迭代收斂,如圖3所示.共有14個特征根屬性大于1,因而選取14個主成分屬性,分別為:結(jié)節(jié)面積、毛刺征、分葉征、D-二聚體、癌胚抗原、神經(jīng)元特異烯醇化酶、細胞角蛋白19片段、鈉、氯、總蛋白、咳嗽咳痰、胸悶憋氣、年齡、咳血.這14個屬性總共代表70.604%的數(shù)據(jù)信息量,說明該14個屬性作為建模輸入值對結(jié)果影響最大.

圖3 提取主成分特征根取值大于1的屬性

(2)基于Kaiser標準化的正交旋轉(zhuǎn)法提取主成分累計貢獻率大于85%的屬性,旋轉(zhuǎn)13次后迭代收斂,如圖4所示.共有23個特征根累計貢獻率86.313%,因而選取23個主成分屬性.

由于兩種主成分特征簡化方式來看,第一種提取特征根大于1的主成分僅能代表70.604% 病歷集的信息,而第二種特征根累計貢獻率提取的主成分能代表86.313% 病歷集的信息.因此,在簡化特征的同時盡可能減少數(shù)據(jù)信息的損失,我們選取第二種方式簡化特征.采取主成分累計貢獻率的PCA方法與C5.0算法相結(jié)合,在不降低模型的精度同時又能防止決策樹算法的維度過高,從而避免過擬合現(xiàn)象.4.3.2 決策樹構(gòu)建結(jié)果

圖4 提取主成分累計貢獻率大于85%的屬性

采用基于主成分累計貢獻率特征降維的C5.0建模,訓(xùn)練集60%,測試集40%.生成的決策樹模型如圖5所示.模型剪枝的置信因子設(shè)定為0.75,建模運行時間僅用了0.32秒.其中,按照變量重要程度由大到小依次為結(jié)節(jié)面積、分葉征、癌胚抗原、中性粒細胞等,這與綜合多篇文獻的臨床診斷指標相吻合.而結(jié)節(jié)面積對于整個模型來說重要程度最高,這也說明結(jié)節(jié)面積對于模型是最重要的變量,它的具體指決定著模型判斷的結(jié)果,當結(jié)節(jié)面積越大,就越有可能患癌.其他的變量相對影響程度較小,但對模型也有一定影響.

兩種模型實驗準確率結(jié)果對比如表1.通過對算法執(zhí)行時間及三組診斷準確率數(shù)據(jù)對比,傳統(tǒng)C5.0決策樹模型的測試集相對來說診斷精度較低,而PCAC5.0模型的測試集效果較好,說明優(yōu)化后的模型不存在訓(xùn)練過度擬合的現(xiàn)象.因此,我們能得出結(jié)論,基于PCA-C5.0算法構(gòu)建的肺癌輔助診斷模型提高了診斷準確率,并在執(zhí)行速度上也有一定提高.

圖5 生成的決策樹

表1 PCA-C5.0算法與C5.0算法比較

5 結(jié)束語

影響肺癌發(fā)病的原因是多方面的,各種因素之間具有不確定性,肺癌的發(fā)病與發(fā)病癥狀、檢驗數(shù)據(jù)之間存在著復(fù)雜的關(guān)系.本文提出的基于肺癌電子病歷的早期輔助診斷方法,結(jié)合了PCA算法和C5.0算法的優(yōu)點.針對C5.0算法的存在模型不穩(wěn)定和過擬合的不足將其進行優(yōu)化,結(jié)合主成分分析法的優(yōu)勢,實現(xiàn)早期肺癌輔助診斷,模型在測試及的準確率達到了87.89%.主成分分析法以數(shù)學(xué)理論為基礎(chǔ),在保證特征信息的前提下,能夠去除數(shù)據(jù)之間的冗余性,減少噪音影響,提高數(shù)據(jù)集的質(zhì)量.本文通過建立的優(yōu)化決策樹模型能夠適用于肺癌早期輔助診斷,挖掘肺癌與電子病歷中的發(fā)病癥狀、實驗數(shù)據(jù)之間的潛在信息,適用于肺癌臨床診療.