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

馮云霞,張 潤(rùn)

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

1 引言

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

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

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

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

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

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

主成分分析中常用的幾個(gè)公式:

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

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

圖1 PCA原理

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

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

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

在決策樹(shù)算法總,計(jì)算分裂屬性的重要指標(biāo)有如下3個(gè):

已知數(shù)據(jù)集M,按照離散度C分成n個(gè)特征子集,n個(gè)特征子集包括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ù)雜程度,若信息增益值越大則說(shuō)明節(jié)點(diǎn)的復(fù)雜程度高;反之,則節(jié)點(diǎn)復(fù)雜程度低.其公式如下:

信息增益是ID3算法中屬性分支的衡量標(biāo)準(zhǔn),但其缺點(diǎn)是更傾向于特征屬性最多的那類(lèi),因此,C5.0算法采用信息增益率來(lái)選擇屬性分支.

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

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

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

3.1 基于主成分分析法的特征簡(jiǎn)化

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

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

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

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

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

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

3.3 模型剪枝

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

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

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

4 實(shí)驗(yàn)驗(yàn)證

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

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

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

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

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

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

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

4.2 實(shí)驗(yàn)過(guò)程

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

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

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

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

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

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

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

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

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

圖4 提取主成分累計(jì)貢獻(xiàn)率大于85%的屬性

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

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

圖5 生成的決策樹(shù)

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

5 結(jié)束語(yǔ)

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