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

馮云霞,張 潤

(青島科技大學 信息科學技術學院,青島 266061)

1 引言

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

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

2 相關理論基礎

2.1 主成分分析法相關原理及基本思想

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

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

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

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

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

圖1 PCA原理

2.2 決策樹相關理論

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.2 早期肺癌輔助診斷模型構建

肺癌輔助診斷決策樹模型的實現過程:

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

3.3 模型剪枝

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

決策樹優化過程偽代碼如下:

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

4 實驗驗證

4.1 數據預處理

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

(1)數據合并:從醫院His系統導出來的電子病歷分為醫囑、診斷、檢驗等模塊,需要將根據患者唯一的PID標識進行關聯,將患者的診斷、主訴、既往史、檢驗數據同步,所以運用excel表格對數據集成合并處理.

(2)數據結構化:使用ICTCLAS作為分詞工具,建立醫學用戶詞典,提取按詞頻分類結果的結構化屬性表.

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

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

圖2 數據預處理

4.2 實驗過程

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

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

4.3 實驗結果

4.3.1 兩種主成分分析特征降維結果

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

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

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

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

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

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

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

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

圖5 生成的決策樹

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

5 結束語

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