生物醫學中高維非均衡數據整合算法

肖枝洪，李 季，王一超

(1.重慶理工大學 理學院，重慶 400054；2.內蒙古赤峰市昭烏達中學，內蒙古 赤峰 024099)

0 引言

醫療行業中充斥著大量高維非均衡醫療數據。在數據分析國際研討會議中將非平衡數據以及高維數據列為未來數據挖掘研究所面臨的具有挑戰性的十大問題之一[1]。高維數據指數據特征多，不僅表現在數據的規模大，而且定義的數據不再僅僅局限于數字，醫療病例的文本、圖像、聲音和傳感器信息等一些可測量的信息都可數據化。這使得醫療數據的特征大大增加，數據結構更加復雜。非均衡數據指分類任務的數據來自不同類別的樣本數目相差懸殊，又稱樣本比例失衡。在醫療領域中，正常數據是多數類，病理數據往往是少數類。人們通常更加關注于少數類，且將少數類誤判為多數類的代價通常會更大。因此為了訓練出適合不平衡數據的分類模型，對不平衡數據進行處理顯得格外重要。

對于高維數據的分類，通常都是先對數據進行降維處理，也就是通過對訓練數據集進行特征提取，獲得能夠對樣本進行較好分類的少量具有代表性特征。具體處理方法如低方差濾波、高相關濾波、向前特征選擇、向后特征提取、主成分分析、K-means指標聚類、特征提取轉化等，都具有一定的局限性。低方差濾波是對一些指標變化較小的指標進行刪除，但是這種方法不具備廣泛性，譬如一些醫療指標即使變化很低，但是可能病癥就有很大的差別[2]；高相關濾波與主成分分析適合數據集中存在高度相關的變量集情況，且有可能造成重要指標被刪除的損失；向前特征選擇與向后特征提取2種方法耗時較久，計算成本都很高；K-means指標聚類是以指標之間的相似系數作為聚類標準，對離群點太敏感，并且相似系數的閾值也需要人為確定。此時隨機森林(RF)機器學習模型體現了優勢，RF具有準確率高、魯棒性好、易于使用、一般不需要繁瑣的步驟、適用于各種類型數據的優點。該算法被廣泛應用到諸如生命科學領域中對基因序列的分類和預測回歸[3-5]、金融經濟領域中對企業和客戶信用的分析和反欺詐識別[6-8]，以及人工智能AI等領域中的人臉識別[9]，但是RF在指標提取中有2種指標重要度評價體系，往往得出的重要指標排序不一致。對此用所提出的MAG算法進行特征提取，尋找出具有代表性的特征，達到降維目的，并在選擇重要特征數量時對傳統的“剃須法”進行改進，縮短算法運算時間。

對于非均衡問題，經典的算法莫過于C’Hawla等[10]提出的SMOTE過采樣技術，該方法屬于一種人工合成少數類樣本的過采樣技術，根據過抽樣率，從少數類的一個樣本的K個最近鄰樣本中隨機選出若干個，在該樣本和被選的近鄰樣本之間插值合成新的樣本。該算法原理簡單，運行速度快，但是SMOTE算法也有明顯的不足，不能有效解決非均衡邊界混合數據。Liu等[11]提出了SMOTE和Boost相結合的SVM算法，通過對高維空間的非線性變換將分類問題轉換為二次尋優解，其實驗表明此方法在非平衡數據集上取得了較好的分類效果，但算法采用欠采樣與過采樣結合，不能保證數據的整體性。王超學等[12]提出了GA-SMOTE算法，將3個算子引入到SMOTE中，首先用選擇算子實現對少數類樣本有區別的選擇，再使用交叉算子和變異算子實現對合成樣本質量的控制。然而此算法中的選擇算子仍然沒考慮邊界混合的樣本，而是以適應度函數來確定，恰恰將混合區域數據視為重要樣本。盡管對于非均衡混合問題后續也有相關學者研究，如鐘龍申等[13]提出了用基于K-means聚類算法改進SMOTE算法來解決非均衡數據問題，但此算法沒有擺脫K-means聚類嚴重依賴于初始點的缺點。馮宏偉等[14]針對非均衡數據分類效果不佳的問題，提出了基于邊界混合采樣的非均衡數據處理方法(BMS)。該方法通過引進“變異系數”尋覓樣本的邊界域與非邊界域，然后對邊界域中的少數類樣本進行過采樣，對非邊界域中的多數類樣本進行隨機欠采樣，從而達到訓練數據基本平衡的目標，但是忽略邊界區域往往存在離群點的缺點。趙清華等[15]針對非均衡數據提出了三角質心與最遠距離法改進傳統的SMOTE算法，改善了邊界混合插值困難的問題。雖然此算法在解決邊界混合時體現了一些優良性，但計算的步驟與運算量也增加了數倍之多，算法準確率提升過小。張喜蓮[16]提出了一種魯棒的半監督降維算法，得到了更精確的數據結構，但是此算法中對正則化參數λ的要求十分苛刻，通常難以滿足。丁長興等[17]介紹了最重要最基礎的梯度下降算法進行了高維非均衡數據挖掘的研究，指出隨機梯度下降算法已成為機器學習特別是深度學習研究的焦點，但也存在迭代復雜性和時間效率沒有很好解決的問題。

醫療領域目前對于此類數據的研究，僅從高維或者非均衡的單一角度出發來解決問題，兩者兼顧的整合算法幾乎沒有涉及。例如，陳旭等[2]針對醫療領域往往存在著樣本數據集非均衡的問題，采用從多數類樣本中抽取部分樣本，與少數類樣本組成平衡數據集后再構建模型，同時提出了一種新的基于迭代提升欠采樣的集成分類方法，但是破壞了數據的完整性，而且對于存在的高維問題也沒有提出解決方法；龔彥等[18]針對醫療行業中的高維數據問題，使用模糊神經網絡分類器進行數據整合分析處理，將人工神經網絡與模糊系統相結合，采用神經網絡對數據進行特征選擇，用模糊系統中的隸屬度函數對數據進行分類，但是此方法沒有對非均衡數據進行均衡處理；王星等[19]提出了一種基于基因互作網絡正則化的雙聚類算法，對癌癥亞型進行分類，其中聚類方法雖然通過正則化方式將高維問題解決，但是依舊對非均衡狀況沒有考慮；胡滿滿等[20]發現了不同疾病發病率的差異性導致醫學樣本具有不均衡、小樣本的特點，并且引入動態采樣技術以構造均衡數據集，利用模型在不同樣本上的預測結果來動態更新樣本采樣概率，目的是確保模型可以更多地關注錯誤分類樣本和分類置信度不高的樣本，從而提高預測模型的效果，但是對于醫療中的高維問題沒有提出解決方法。

根據對上述文獻的分析探究，針對醫療中高維非均衡數據的整合問題擬提出MAG算法和PDSSD-SMOTE方法相結合的整合算法，并基于帕金森氏病分類數據集[21]和常規結腸鏡檢查中的胃腸道病變數據集[22]進行實驗分析。首先采用MAG算法對高維數據非均衡進行降維；降維后，采用動態離差平方和(PDSSD)機器學習方法，改進K-means機器學習方法對初始點的依賴性，將少數類也就是負類數據樣本進行區域合理劃分；再利用少數類中高純度樣本區域重心點與近鄰間進行插值來改進SMOTE算法，讓具有邊界混合的負類樣本數據通過插值趨近于高純度樣本，從而提升非均衡數據取樣時的純度。然后在實驗中應用最小二乘支持向量機(LSSVM)與RF對運用MAG算法和PDSSD-SMOTE方法整合后的數據進行數據分類，以分析該方法分類的準確性和精確性。

主要貢獻在于：① 改進RF提取重要特征的準則，提出了用組合標準的MAG算法來提取特征重要度信息；同時剔除相關性較大的特征，對用于重要指標選取的“剃須法”進行改進，縮短了運算時間。② 采用PDSSD機器學習對負類樣本數據集進行區域劃分，對區域中心與樣本間插值的SMOTE算法進行改進，使樣本數據均衡更加合理。

1 相關算法理論

表1 P個指標n個樣本

(1)

也稱其為此類的質心，i=1，2，…，nj，j=1，2，…，k。

表2 所屬各類的觀測

1.1 RF算法

RF是決策樹的集合，通過投票方式進行分類模擬，決策樹算法應用廣泛，有ID3、C4.5[23-24]、CART 3種，CART樹是二叉樹[25]，而ID3和C4.5可以是多叉樹。對于RF分叉的好壞有2個重要指標評價指標：基尼系數節點純度估計與袋外數據(OOB)精度估計。但是往往根據2種標準對特征提取的結果不完全相同。為了使高維數據的特征提取沒有偏頗，將以MAG算法作為標準來進行高維數據的特征提取。

1.1.1基尼系數

對于以基尼系數作為分叉標準的計算如下：

假設有K個類，樣本點x屬于第l個類的概率為Pl，則概率分布的基尼系數為：

如果樣本集合D根據特征F是否取某一可能值a被分割成D1與D2兩部分，即：

D1={x∈D|F(x)=a}，D2=D-D1

則在特征F的條件下，集合D的基尼系數定義為：

(2)

將D中所有特征的基尼系數進行排序，其最大值意味著對應的特征最具代表性。然后對D1和D2按照上述方法挑選下一個特征，直到到達事先規定的葉節點為止，從而獲得相應的具有代表性的一系列特征，這種方法數值型特征和字符型特征都可以適用。

1.1.2OOB精度

RF有一個重要的優點就是不必要對它進行交叉驗證或者用一個獨立的測試集來獲得誤差的一個無偏估計。它可以在內部進行評估，也就是說在生成的過程中就可以對誤差建立一個無偏估計。這是因為在構建每棵樹時，對訓練集使用了不同的bootstrap sample方法。對于每棵樹(假設第k樹)而言，若有訓練實例沒有參與到第k棵樹的生成，則稱該實例為第k棵樹的OOB袋外樣本。

OOB精度不僅可以利用OOB對模型性能進行評價，而且還可以用來判定特征的重要度。其原理是：對于某個特征變量，當把噪聲信息加入到該特征后，RF的預測精度會顯著降低，這就說明該特征重要程度很高；相反，若RF的預測精度沒明顯變化，則標志該特征重要程度很低。指標選取就是根據預測精度較少值確定的。

將在2.1節把基尼系數與OOB精度進行組合，得到新的評價標準，并用新的評價標準來對高維數據進行降維處理。

1.2 SMOTE算法

為了方便說明SMOTE算法原理，在表2中不妨取k=2。SMOTE算法原理為：樣本數據集分為樣本多數類(正類)C1與樣本少數類(負類)C2兩大類，根據歐幾里得距離從C2類樣本中挑選出距離第i個樣本最近的m個樣本；根據樣本數據平衡需要再從此m個樣本中隨機挑選iN個樣本并記為集合Yi，Yi={yi1，yi2，…，yiN}表示第i個樣本挑選的最近樣本集合，i=1，2，…，n2。然后在第i個樣本與其最近的iN個樣本之間進行隨機插值，其值記為:

(3)

2 高維非均衡邊界混合數據優化處理

2.1 高維數據降維優化算法

針對1.1節的問題，本節通過整合2種對特征提取的標準而提出MAG算法。其思想就是將基尼系數節點純度與OOB確定變量重要度估計值二者綜合取平均值，然后依據該值重新對特征重要性進行排序。MAG算法如下：

步驟1 對表1中的數據建立RF模型H。記ntree為RF中分類樹的個數，mtry為RF中決策樹的每次分支時所選擇的變量個數。

步驟2 利用OOB數據，測試RF中所有的分類樹，得到每棵樹的OOB估計的準確率，并記ACCj為RF中第j棵分類樹的準確率：

步驟3 隨機打亂OOB樣本數據中第i個特征的觀測值，也就是對之隨機重排。用此數據輸入到第j棵分類樹中進行預測，得到一個新準確率ACCji。

步驟4 計算每個分類樹前后兩次OOB數據準確率之差difji=|ACCj-ACCji|，計算第i個特征的重要程度：

(4)

依據式(4)計算每個特征的Difi并按從小到大順序進行排列。

步驟5 根據式(2)計算各個特征基尼系數值Ginii，按從小到大順序進行排列，并判斷與步驟4的順序是否一致，若不一致繼續步驟6。

步驟6 計算第i個特征綜合重要程度值：

(5)

依據式(5)計算所有指標重要度，并從大到小進行排序。記所有特征的綜合重要程度值集合T={index*1，index*2，…，index*p}，其中index*1>index*2>…>index*p。

在RF特征重要度排序之后，如何選取特征重要度閾值是一個難點，傳統的RF剃須法[26]是常用的方法，其原理為將所有指標重要度從大到小排序，然后依次剔除重要值排名在后10%的特征。例如，假設有n個特征，不妨取n=100，剔除{indexn-9，…，indexn}所對應的特征，再用剩余的90個特征建立RF模型。然后根據此模型，計算每個特征的重要程度值和OOB誤差。如此這般，一直到事先約定為止。這樣就得到一系列特征集合和OOB誤差，選擇OOB誤差最小且數據特征最少的特征集，但是這個剃須法在確定剔除比例時具有主觀性，不能根據特征集重要值進行具體劃分，而且特征較多時運算過于費時，為此提出了分段式的剃須法(segmentation shaving)，根據第一次建立的RF得到的特征重要值進行分段計算，分段的準則依據實際特征重要值的均值與方差來確定，均值與方差計算方法如下式：

根據以上分段確定選取的特征數，分別建立5個RF模型，選取OOB誤差最小且特征數最少的數據特征集。

得到最少特征數p1的數據特征集M后，計算特征的相關系數矩陣，給定閾值λ，將相關系數大于閾值的進行相關性檢驗，剔除相關性較大的特征，將數據特征集進一步優化。

2.2 非均衡邊界混合數據優化算法

針對1.2節的問題，本節假設表2中數據集C只有2 類：多數類樣本集C1和少數類樣本集C2。并假設C2潛在地可劃分為區域C21、C22和C23，如圖1所示。其中C21為C1和C2邊界混合附近的數據集；C22為C2中高純度數據集；C23為C2中離群點數據集。

圖1 少數類樣本集數據分布圖

為了使數據均衡，使用SMOTE算法對C2進行過采樣。同時也為了避免過多地抽到邊界混合數據集C21中的數據，采用文獻[27]中的PDSSD準則下的機器學習方法對C2進行劃分。動態離差平和準則下的機器學習是根據總體離差平方和不變，依次調整樣本的類別，使類內樣本離差平方和最小，類間離差平方和最大，能夠保證機器學習減少對初始點的依賴度。

首先,從C2中計算樣本距離矩陣，隨機選定這3個初始凝聚點，運用PDSSD機器學習法將C2劃分為3類，仍然記為C21、C22和C23。

其次，根據式(1)計算C21、C22和C23樣本集的質心分別為d21、d22和d23。再計算3個樣本集的質心與最近多數類樣本集質心的距離：

比較υ21與υ22、υ23的大小進行排序，如果υ21<υ22<υ23，則說明d22所在的數據集C22是高純度少數類樣本集，就選擇C22進行中心SMOTE算法插值。

再次改進中心SMOTE算法：采用樣本集質心與樣本之間插值，即

(6)

將此算法叫做PDSSD機器學習中心插值法，簡稱為PDSSD-SMOTE算法。

3 實驗

3.1 實驗環境與醫療數據

本次實驗采用R3.4.4與Matlab 6.0數據分析軟件進行實驗數據分析。

此實驗數據來源于UCI(http://archive.ics.uci.edu/ml/index.php)機器學習數據庫中的2個醫療數據集，數據集1：“Gastrointestinal Lesions in Regular Colonoscopy”；數據集2：“Voice Back”數據集。數據集1為二分類樣本數據集，其中特征變量為698個，多數類(正類)樣本量為55，少數類(負類)樣本量為21；數據集2也為二分類樣本數據集，其中特征變量為752個，多數類(正類)樣本量為564，少數類(負類)樣本量為192，2個醫療數據集顯然都為高維非均衡數據，如表3所示。數據集1和2的特征變量均為數值變量。

表3 數據樣本集矩陣

采用F-value、G-mean值和Accuracy值作為分類器的評價標準，其中TP和TN分別表示分類中正類和負類樣本正確分類的樣本數量；FN和FP分別表示為正類與負類被錯分的樣本數量。

(7)

(8)

(9)

3.2 基于MAG算法對醫療數據降維實驗

RF對于特征重要度評價有2種體系，驗證2種體系得出的特征重要度排名是否一致，根據式(2)與式(4)分別計算得到各個特征的基尼系數與OOB估計重要度。因為特征變量過多，在此僅展示前30個特征變量的基尼系數與OOB估計值，2個數據集的結果分別如圖2與圖3所示。

圖2 數據集1基于OOB估計值與基尼系數指標重要度排名

圖3 數據集2基于OOB估計值與基尼系數指標重要度排名

從圖2、圖3可以看出2種指標評價體系在指標重要程度排名上是不相同的，所以有必要運用MAG優化算法，再次對指標重要度進行排序。

根據MAG算法式(5)計算得到所有特征變量重要度值，其中重要度大于0的指標為167個，表示數據樣本中698個指標只有167個為有效指標。再將167個有效指標根據分段剃須法選取出35個特征，作為數據降維后的特征，特征重要度數值如表4和表5所示。

表4 數據集1在MAG算法下得到特征重要度數值

表5 數據集2在MAG算法下得到特征重要度數值

對上述MAG算法得到的特征集計算相關系數矩陣，設定閾值λ為0.9，并對大于閾值的特征進行相關性檢驗，得到相關性較弱的重要度高的最優特征集，如表6和表7所示。

表6 數據集1特征相關性檢驗篩選后得到特征集

表7 數據集2特征相關性檢驗篩選后得到特征集

3.3 基于PDSSD-SMOTE算法對醫療數據平衡實驗

為驗證數據集是否存在混合情況，運用PDSSD算法將數據集1和2在PDSSD準則下分別進行第一次聚類，其實驗結果如表8所示。

表8 數據集1和2的PDSSD算法第一次聚類結果

表9 數據集1和2的負類樣本集PDSSD算法第二次聚類結果

表10 數據集1合成前后負類樣本

表11 數據集2合成前后負類樣本

3.4 MAG-PDSSD-SMOTE算法與傳統方法對高維非均衡醫療數據整合的有效性比較

表12 不同方法降維后的數據集1和2在2種分類器下分類效率

表13 不同方法整合后的數據集1和2在2種分類器下的分類效率

為驗證提出的算法具有優勢，將提出的算法與處理非均衡高維數據的主流算法BP神經網絡與隨機梯度下降的支持向量機算法相比較，分類效率如表13和表14所示。

表14 數據集1和2在不同算法下的分類效率

從表13和表14可以看出，2種算法分別對數據集1和2的3個分類評價值都低于提出的MAG-PDSSD-SMOTE算法的數據集的分類評價值。因為BP神經網絡算法和隨機梯度下降支持向量機算法沒有對數據進行整合，所以運算時間比MAG算法與PDSSD-SMOTE算法相結合的算法運行時間要短。

實驗表明，在疾病的輔助預診中，越高的召回率和越好的F-value和G-mean具有更小的診斷風險，對疾病的輔助決策具有更重要的價值。所提出的MAG-PDSSD-SMOTE算法整合數據之后，模型對常規結腸鏡檢查中的胃腸道病變的分類效率和帕金森病的分類效率有了明顯提升。這正是因為MAG-PDSSD-SMOTE算法能夠更加關注醫療行業的少數類樣本和預測過程中的易錯樣本，從而保證了模型預測準確性，提高了模型效率，使其具有更小的診斷風險。

4 結論

由于經典的SMOTE算法與RF算法對高維非均衡數據進行整合時存在不足，即RF在特征提取中有2種特征重要度評價體系，往往得出的重要指標排序不一致，且特征提取的“剃須法”過于耗時，SMOTE算法對混合非均衡狀態數據均衡處理時，不能對邊界混合數據進行識別而實現有區別插值。針對上述問題，首先提出了RF組合評價標準的MAG算法，對于特征提取標準提出了“分段剃須法”，從而有效地克服了RF的特征重要度雙標準以及特征提取剃須法過于費時的弊端。對于少數類數據的均衡處理提出了可以進行區域劃分的MAG-PDSSD-SMOTE算法，解決了SMOTE算法對邊界混合的少數類數據純度不高的問題，也避免了K-means-SMOTE算法對初始聚類點的依賴問題。實驗中將各算法整合后的數據集進行分類比較，結果表明對于高維非均衡數據的分類所提出的算法有較為明顯的優勢。

RF和LSSVM兩種分類器對上述數據集進行分類的情況都驗證了對于高維非均衡邊界混合數據，直接運用SMOTE算法不能有效均衡數據結構，所提出的MAG-PDSSD-SMOTE算法對傳統SMOTE算法具有顯著的改進效果，且優于經典的K-mean-SMOTE算法。但是從各個算法對數據集整合并分類的時間來看，所提出的MAG-PDSSD-SMOTE算法所用時間要遜于其他算法，這是算法的復雜性所造成的。

此外，在研究過程中也注意到：非均衡數據結構做均衡處理時，如果數據集中存在字符型數據時如何計算其距離的問題；SMOTE算法無法有效處理那些特征變量是定性變量的數據集，對定型變量進行SMOTE插值會使其數值失去實際意義；如何提升MAG-PDSSD-SMOTE算法運算速度等問題，將在今后的研究中繼續探討。