基于均衡分類的腦卒中風險預測模型

曹 艷，殷 旭

（北京信息科技大學 計算機學院，北京100085）

0 引 言

隨著醫療信息量的增長，數據挖掘技術在醫療領域得到廣泛應用。決策樹C4.5算法因其具有直觀、高效和結果易于理解的特點備受 關注。Jinn－Yi Yeh等［1］使 用C4.5 算法得到透析病人是否需要住院治療和相關癥狀的關系，以合理安排住院和治療方案；Zerina Maetic等［2］綜合使用自回歸 （AR）特征提取模塊和C4.5算法檢測分離正常和充血性心臟衰竭，分類準確率高達99.77。在對乳腺癌數據分類中，C4.5算法可以較好的控制決策樹的規模，規則的可理解性較高［3］。Ture、Tokatli等［4］在對乳腺癌患者的無復發生存期預測實驗中發現C4.5在準確度和樹結構方面優于CART、CHAID、QUEST 和ID3 算法。上述研究中C4.5都取得了較好效果，但都建立在均衡數據基礎之上，為了提高整體分類精確度，可能將某些少數類數據作為可允許誤差進行錯誤分類。不均衡數據處理主要是對數據集進行重構，數據重構通常采用欠采樣技術、過采樣技術和Chawla等提出的SMOTE （synthetic minority oversampling technique）算法［5］。文獻 ［6－11］分別是近年針對不均衡數據提出的處理方法。SMOTE 算法與主動學習算法［6］集成使用，在一定程度上避免數據不均衡帶來的分類偏倚問題；許丹丹等從數據水平的過抽樣角度出發，提出SMOTE 的改進算法ISMOTE算法，更好地提高了不均衡數據的分類性能［7］；用陰性免疫算法實現少數類樣本空間覆蓋，可以避免SMOTE生成的新樣本空間代表性不足的問題［8］；在SVM 分類偏倚問題研究中，集成使用代價敏感學習、欠采樣和 過 采 樣 技 術 效 果 明 顯［9］；Wang 等［10］結 合SMOTE、PSO （particle swarm optimization）和C5.0 算 法 對 不 均 衡的乳腺癌數據分類，發現經SMOTE 處理后分類效果明顯提高；孫濤等醫學專家也發現SMOTE 算法可以對臨床的不均衡數據進行有效糾偏［11］。上述方法主要是針對少數類數據進行的，忽略了多數類數據處理，當兩類數據數量相差較大，一味增加少數類數據會造成少數類分類過度擬合，生成虛假關系。

1 SMOTE算法介紹

SMOTE算法［5］是2002年由Chawla等提出的一種針對不均衡數據集的智能型過抽樣技術，可以有效改善傳統過抽樣技術帶來的分類過度擬合現象，解決分類結果偏倚問題。

定義1 設樣本集合為T，x為集合中的單個樣本，k為搜索的少數類最鄰近樣本的數量，向上采樣的倍率為N（N 為可被100整除的數），在k個少數類最鄰近樣本中隨機選取N／100個樣本，m1，m2，…，mn，在x與m1（j＝1，2，…，n）之間隨機線性插入0到1之間的數，形成新的少數類樣本qj

SMOTE算法的核心思想是首先尋找每個少數類樣本的k個最鄰近樣本，然后選取其中N／100個，分和少數類樣本兩兩組合，最后在兩個樣本間進行隨機線性插值，構造新的少數類樣本。

算法的具體是實現過程是：

輸入：訓練樣本集T，最鄰近樣本數量k，向上采樣倍率N

輸出：少數類空間擴大的訓練樣本集T1

（1）判斷N 是否小于100，如果是，則直接對樣本進行隨機采樣；否則計算樣本中各決策屬性中樣本的數量，確定少數類和多數類；

（2）根據k、N 的值和式 （1）合成新的少數類數據；

（3）將新生成的少數類樣本加入原數據集中，生成新數據，算法結束。

實驗中，在此過程之前，首先應使用隨機抽樣算法抽取訓練集中所有的樣本，即對數據進行隨機排序，避免數據預處理時排序篩選等操作影響最鄰近樣本分布的隨機性。這樣，既可增大少數類數據的規模，又可以避免傳統過抽樣中完全復制少數類樣本帶來的過度擬合問題。

2 基于PAM 的K－means算法PAM－means算法介紹

2.1 K－means算法

K－means算法是MacQueen在1967年提出的基于距離的聚類算法，該算法因效率較高得到廣泛應用。算法的基本思想是：首先選定聚類數量K 和K 個初始聚類中心Zj，依據距離最小原則將樣本nj分配到距離聚類中心最近的類中，分配完后，計算每個類的均值作為新的聚類中心，循環樣本分配過程，直到聚類收斂為止。聚類的目標函數如下

其中，函數d（xj，zj）為歐幾里得距離函數，如下

2.2 PAM 算法

PAM （portioning around medoid），是一種圍繞中心的劃分，試圖對N 個對象進行K 個劃分。該算法首先為每個類選取一個初始中心點數據，剩余的數據依據到與中心點的距離或相異度分配給相近的中心點所在的類；然后反復地用非代表數據替換代表數據，并使用代價函數進行評估聚類質量，選取當前代表數據最好的代替，提高聚類質量，得到正確的劃分。

2.3 PAM－means算法

K－means算法聚類效果相對較好，較為準確，但對孤立點和噪聲較為敏感，且需人為指定K 值。而PAM 算法不需要指定聚類數目K，對孤立點和噪聲不敏感，且能處理不同類型的數據，但聚類效果相對K－means較差。

為了使聚類效果較好，本文采用PAM－means算法，首先使用PAM 算法得到聚類數量K，然后使用K－means算法對多數類數據進行聚類，將相似度較高的數據聚到一簇，相似度較低的數據分開。這樣，對聚類后每個簇進行抽樣所得的數據特點基本可代表整個多數類數據的特點，從而避免傳統欠抽樣造成的信息嚴重丟失問題。

算法的基本流程如下：

（1）PAM 算法聚類，得到K 值；

（2）任意選取K 個數據對象作為初始聚類中心；

（3）計算樣本中所有數據到聚類中心的距離，如式（3）所示，選擇距離最小的數據對象，并將該數據對象劃分到該聚類中心所在的簇；

（4）計算每個簇中數據對象的均值，作為新的聚類中心；

（5）循環步驟 （3）和步驟 （4），直到聚類中心不再改變；

（6）算法結束。

3 決策樹C4.5算法

決策樹C4.5算法是JR Quinlan于1993在算法ID3的基礎上提出的，相對于ID3算法，C4.5具有更高的分類精確度，并且可以處理連續屬性。C4.5算法用信息增益率來選擇決策屬性，對于連續屬性要首先進行離散化，離散化的依據是將連續屬性排序后，從中間開始選取可能分裂點，計算各可能分裂點的信息增益率，將信息增益率最大的點作為分裂點。因此在C4.5算法中對于連續屬性的分裂是二元分裂。

C4.5算法利用信息熵原理，以信息增益率作為分類屬性的選擇標準，克服了信息增益選擇屬性時偏向選擇取值多的屬性的不足，遞歸的構造決策樹［12］。本文在構造樹的過程中使用十折交叉驗證和測試集驗證對分類樹進行剪枝，不斷的訓練樹的結構，以達到最簡最可靠有效的分類結果。

算法的具體實現過程是：

輸入：訓練集T，決策屬性C

輸出：決策樹

（1）以T 為根節點構造分類樹；

（2）判斷T 的樣本的決策屬性是否相同，如果相同，那么當前節點即為葉節點，算法結束；否則，計算k個決策類的總信息量；

（3）判斷條件屬性是連續屬性還是離散屬性，如果是連續屬性，根據連續屬性的可能分裂點的信息增益率對該屬性進行離散化；

（4）分別計算條件屬性基于決策屬性的條件信息量和分裂信息；

（5）計算各條件屬性的信息增益率，并選擇最大的為分裂屬性，同時將該屬性對應的樣本作為子分類樣本集；

（6）針對選中的分裂屬性，根據分裂信息構建對應的節點，并將對應的樣本劃分到該節點下；

（7）重復步驟 （2）到步驟 （6），對個訓練樣本子集進行劃分，生成新的決策分支，直到沒有可以再分的屬性，算法停止。

C4.5算法雖然可以比較準確有效的對連續和離散數據進行分類，但是沒有針對數據本身分布不均的特點進行處理，尤其是在遇到普遍存在不均衡性的醫學數據時，C4.5算法為了保證整體分類精確度，很容易產生不可預知的偏倚性，將少數類數據誤分到多數類中，隱藏少數類數據的信息，造成靈敏度較高，特異度較低的結果。因此合理的對不均衡數據進行均衡處理至關重要。

4 實驗及結果分析

本文以腦卒中高危因素篩查和防治項目的調查問卷數據為樣本數據，分析與腦卒中相關的因素之間的關系，并預測患腦卒中的風險，為有效干預腦卒中預防提供支持。

4.1 評價標準

提高少數類的分類性能是不均衡數據分類問題的研究重點，表1是3類數據集的混淆矩陣，這3類數據的標號分別為A、B和C，以A 類為例，TA 為A 類正確分類的樣本數量，FAB表示A 類樣本誤分到B類的樣本數量，FAC表示A 類樣本誤分到C類的樣本數量。

表1 3類數據集的混淆矩陣

分類模型中常用的評價標準為精確度Accuracy，體現分類的整體性能，但不能合理準確的評價不均衡數據集的分類性能。對于不均衡數據分類評價標準常用F－measure，是查全率Recall和查準率Precision的組合，β通常為1。只有少數類的查全率和查準率都大時，少數類的F－measure才會大，因此他能正確的反應少數類的分類性能。式 （5）、式 （6）和式 （7）分別是類A 的F－measure（A）、查準率Precision （A）和查全率Recall（A），分類的總體Recall在3類數據集分類中為每類查全率的加權均值，權重為各類樣本所占比例，整體Precision和F－measure同Recall。

4.2 數據預處理

原始數據集有冗余數據、缺失數據、不確定數據和不一致數據等，導致結果不準確、不全面，甚至得出錯誤的規則。所以首先對數據進行預處理，消除數據噪聲帶來的分類問題。

此次調查問卷得到的原數據共有524條記錄，100個數據項，其中除了與腦卒中相關的數據項，還有大量的與腦卒中無關的個人統計學信息和醫院信息，如姓名，民族，篩查日期等。

首先刪除如姓名、篩查日期等無關信息，去除數據項中只包含一兩條記錄的數據項。其次，整合數據，在醫生專家的指導下將某些數據項整合到一起形成新的數據項，如在判斷是否是家族遺傳腦卒中時，可以將父母、子女、兄弟姐妹中有得腦卒中的情況視為有家族遺傳腦卒中；將身高體重合并為身體質量指數 （BMI）作為衡量身體胖瘦程度的標準等。經過這些處理，數據中包含15項數據項，179條數據。最后，統一數據格式，并用出現頻率最高的數據填充本數據項中個別的缺失值。最后生成的數據形式見表2。

表2 腦卒中數據

表2中與腦卒中相關的數據項包括決策屬性患腦卒中的風險和條件屬性年齡、性別、身體質量指數 （BMI）、是否從事輕體勞動、體育鍛煉情況、是否有腦卒中史、是否有短暫性腦缺血發作史 （TIA）、是否患有高血壓、是否有過房顫或瓣膜性心臟病 （AF／AHD）、是否吸煙、是否飲酒、是否有血脂異常、是否有慢性病史、是否是家族遺傳腦卒中。數據中性別項F表示女性，M 表示男性；體育鍛煉情況1表示有規律性鍛煉，2表示有鍛煉但不規律，3表示無體育鍛煉；其它數據項中1表示是，2表示否；決策屬性有3個取值L、M、H，分別表示低危、中危和高危。

4.3 SMOTE＆PAM－means＋C4.5算法實現過程介紹

整個實驗過程如圖1所示，數據預處理后進行均衡判斷，首先統計每個類中記錄數，找出記錄數的最大值max和最小值min，然后對max和min做商，如果max／min＜3則判斷數據均衡，直接進入C4.5分類器進行分類；否則判斷該數據集存在不均衡性，需要先進行均衡處理，然后進入分類模塊。

（1）菌種活化分別取適量乳桿菌菌株凍干菌粉接種于10 mL滅苗MRS肉湯培養基中，旋渦混勻于37℃在恒溫培養箱中培養24 h得到一代菌懸液。按5%的接種量將一代菌懸液接種于MRS肉湯培養基中，37℃恒溫培養24 h得二代菌懸液。重復上述步驟37℃恒濕培養18 h，進行第三次活化得到三代活化菌懸液，4℃冰箱儲存備用。

圖1 模型實現流程

均衡處理的工作流程如圖2所示，生成的是均衡處理后的均衡數據集。整個均衡處理過程包含兩個部分，一部分針對少數類數據，首先對整個數據集抽樣，抽樣方式為不可重復抽樣，數量為數據集數量，使各記錄隨機排序，然后使用SMOTE 生成新的少數類數據。排除預處理時篩選排序等操作對SMOTE 算法的影響，確保SMOTE 得到的數據是隨機綜合多數類數據和少數類數據得到的，避免SMOTE生成的數據僅來源于少數類數據而造成過度擬合問題。針對多數類數據，主要是進行欠抽樣，但考慮到欠抽樣帶來的信息丟失問題，首先對多數類數據做PAMmeans聚類，然后計算聚類結果中每簇中各個分類屬性的樣本數量，按比例進行抽樣，使最終得到的數據集中每類數據的數量相當。

圖2 數據均衡處理流程

4.4 實驗結果及分析

原始C4.5算法分類結果的混淆矩陣如表3所示。表3顯示樣本總量為179，其中P＝L 的有104例，P＝H 的有66例，而P＝M 的只有9例，P＝M 相對P＝L和P＝H 類別屬于少數類。混淆矩陣顯示P＝M 類中只9例樣本，只有44.445% 正 確 分 類，有33.333% 偏 向p ＝L 類，22.222%偏向P＝H 類，即大部分少數類數據被誤分到其它類別。而P＝H 類別中，分類正確的占78.788%，分類偏向P＝M 類的7.576%，偏向P＝L類的13.636%。對于多數類P＝L，只有2例被誤分到了P＝H 類中。縱向看，P＝M 類9例中只有4例來自正確數據，其余都是P＝H 類錯誤分類的結果。綜上所述，少數類數據的分類性能極差，結果不能正確體現少數類數據的特點。因此，不均衡的腦卒中數據在C4.5算法分類中存在嚴重的分類偏倚問題，解決數據不均衡問題是改善分類性能的首要問題。

表3 C4.5算法分類混淆矩陣

為了解決分類偏倚問題，實驗中分別對原始數據做了不同的均衡處理，包括欠采樣、過采樣、SMOTE 和SMOTE＆PAM－means算法，然后用C4.5 算法進行分類，分類過程中采用十折交叉驗證對樹進行剪枝。均衡處理過程中，欠采樣以少數類樣本數量為標準分別對兩個多數類進行欠采樣，形成新的數據集。SMOTE 算法處理數據，形成的均衡數據集中P＝M 含有27例樣本。過采樣中少數類數據數量與SMOTE 處理結果中P＝M 類的樣本數量相同，同時從多數類數據中隨機取一半數據，以便與SMOTE和原始C4.5算法進行F－measure和驗證精確度的對比。由于均衡處理后進入分類器的數據為部分原始數據，所以使用整個原始數據集對生成的規則進行驗證，得到驗證精確度。

原始C4.5算法、欠采樣＋C4.5 算法、過采樣＋C4.5算法、SMOTE＋C4.5算法和最終改進的SMOTE＆PAMmeans＋C4.5算法分類結果對比見表4。

表4 各算法結果對比

表4中顯示均衡處理后，分類樹的結構有不同程度的簡化，樹的節點和葉節點數都減少，過采樣簡化程度相對最小，SMOTE＆PAM－means＋C4.5 相對最大。從均衡角度分析，原始C4.5算法的F－measure（M）值僅0.394，而整體F－measure值為0.879，相對較大，說明少數類分類性能比較差，而多數類分類性能很好，再次說明原始C4.5算法的分類結果嚴重偏倚。均衡處理后，少數類的分類性能都有明顯提高，但整體F－measure 只有SMOTE＆PAMmeans＋C4.5算法有明顯改善，其它3 種都有不同程度的下降，說明只針對少數類數據進行的均衡會造成多數類數據信息嚴重丟失，影響整體的分類性能，使得均衡處理得不償失。而SMOTE＆PAM－means＋C4.5算法的分類精確度和驗證精確度也明顯提高。因此，SMOTE＆PAM－means＋C4.5算法同時對少數類和多數類數據進行處理，可有效增大少數類樣本空間的同時需減少多數類樣本信息損失量，改善不均衡數據分類偏倚問題，提高分類性能。

SMOTE＆PAM－means＋C4.5算法生成的樹結構如圖3所示，對應的規則如下：

規則2：如果慢性病史＝1∧腦卒中史＝2∧飲酒＝1，則風險＝H；

規則3：如果慢性病史＝1∧腦卒中史＝2∧飲酒＝2∧年齡＞66，則風險＝H；

規則4：如果慢性病史＝1∧腦卒中史＝2∧飲酒＝2∧年齡＜＝66，則風險＝M；

規則5：如果慢性病史＝2∧腦卒中史＝1，則風險＝H；

規則6：如果慢性病史＝2∧腦卒中史＝2∧血脂異常＝2，則風險＝L；

規則7：如果慢性病史＝2∧腦卒中史＝2∧血脂異常＝1∧高血壓＝1，則風險＝H；

規則8：如果慢性病史＝2∧腦卒中史＝2∧血脂異常＝1∧高血壓＝2，則風險＝L。

圖3 SMOTE＆PAM－means＋C4.5算法生成的樹結構

實驗結果顯示，在沒有慢性病史的情況下，腦卒中史或血脂異常、高血壓都會增大病人患腦卒中的概率，使病人處于高危患病人群。而在有慢性病史的情況下，腦卒中史仍是導致病人患腦卒中的關鍵因素；同時，對于沒有腦卒中史的人，飲酒和年齡大于66歲是兩個導致腦卒中發病的關鍵因素。因此，此預測模型有助于人們尤其是老年人及時了解自身健康情況，準確預測腦卒中發病風險，并根據自身情況，尋求更適合自己遠離腦卒中的預防措施，最終達到有效干預腦卒中預防治療的效果。

5 結束語

基于均衡分類的腦卒中風險預測模型中SMOTE＆PAM－means＋C4.5算法對少數類數據進行了處理，通過少數類數據和少數類最鄰近的樣本生成新的少數類數據，一定程度增大少數類數據規模。同時對多數類進行PAM－means聚類，然后按比例對每簇樣本進行隨機抽樣，達到少數類和多數類數據均衡的效果。通過實驗可知，均衡后有效解決了分類結果偏倚問題，并且分類精確度和樹的結構也得到了改善。此模型生成了8條腦卒中風險預測規則，為人們及時準確的預測腦卒中風險提供依據。在以后的工作中我們將進一步研究如何更有效解決不均衡數據分類問題，提高最終準確度的分類，簡化樹的結構，為疾病的有效預防治療等提供數據支持。

［1］Jinn－Yi Yeh，Tai－Hsi Wu，Chuan－Wei Tsao.Using data mining techniques to predict hospitalization of hemodialysis patients ［J］.Decision Support Systems，2011，50 （1）：439－448.

［2］Zerina Masˇetic，Abdulhamit Subasi.Detection of congestive heart failure using C4.5decision ［J］.Southeast Europe Journal of Soft Computing，2013，2 （2）：74－77.

［3］LI Zhi，LI Guolin.Comparative study of C4.5and CART algorithm in medical data mining ［J］.Electronic Technology ＆Software Engineering，2013，10 （3）：47－48 （in Chinese）.［李治，李國琳.C4.5 和CART 算法在醫學數據挖掘中的對比研究 ［J］.電子技術與軟件工程，2013，10 （3）：47－48.］

［4］MevlutTure，FusunTokatli，Imran Kurt.Using Kaplan－Meier analysis together with decision tree methods（CART，CHAID， QUEST，C4.5and ID3）indetermining recurrence－free survi－val of breast cancer patients ［J］.Expert Systems with Applications，2009，36 （2）：2017－2026.

［5］Chawla NV，Bowyer K，Hall L，et al.SMOTE：Synthetic minority over－sampling technique［J］.Journal of Artificial Intelligence Research，2002，16 （1）：321－357.

［6］ZHANG Yong，LI Zhuoran，LIU Xiaodan.Active learning SMOTE based imbalanced data classification ［J］.Computer Application and Software，2012，29 （3）：91－94 （in Chinese）.［張永，李卓然，劉曉丹.基于主動學習SMOTE 的非均衡 數 據 分 類 ［J］.計 算 機 應 用 軟 件，2012，29 （3）：91－94.］

［7］XU Dandan，WANG Yong，CAI Lijun.ISMOTE algorithm for imbalanced data set［J］.Journal of Computer Application，2011，30 （9）：2399－2401 （in Chinese）.［許丹丹，王勇，蔡立軍.面向不均衡數據集的ISMOTE 算法 ［J］.計算機應用，2011，30 （9）：2399－2401.］

［8］TAO Xinmin，XU Jing，TONG Zhijing，et al.Over－sampling algorithm based on negative immune in imbalanced data sets learning ［J］.Control and Decision，2010，25 （6）：1－7（in Chinese）.［陶新民，徐晶，童志靖，等.不均衡數據下基于陰性免疫的過抽樣新算法［J］.控制與決策，2010，25 （6）：1－7.］

［9］Tang Y，Zhang YQ，Chawla NV，et a1.SVMs modeling for highly imbalanced classifications ［J］.IEEE Transaction on Systems，Man，and Cybernetics，Part B：Cybernetics，2009，39 （1）：281－288.

［10］Wang K J，Makond B，Chen KH，et al.A hybrid classifier combining SMOTE with PSO to estimate 5－year survivability of breast cancer patients ［J］.Applied Soft Computing，2014，20 （3）：15－24.

［11］SUN Tao，WU Haifeng，LIANG Zhigang，et al.SMOTE algorithm in the application of imbalanced data ［J］.Beijing Biomedical Engineering，2012，31 （5）：528－530 （in Chinese）.［孫濤，吳海豐，梁志剛，等.SMOTE算法在不平衡數據中的應用 ［J］.北京生物醫學工程，2012，31 （5）：528－530.］

［12］Zhong L，Wang B，Wang Z，et al.Research and application of massive data processing technology ［C］／／8th International Conference on Computer Science ＆ Education.IEEE，2013：829－833.