基于決策樹與質(zhì)譜分析數(shù)據(jù)的癌癥判別

嚴(yán) 勇， 王 鑫， 楊慧中

（1.無錫職業(yè)技術(shù)學(xué)院 繼續(xù)教育學(xué)院，江蘇 無錫 214121；2.江南大學(xué) 物聯(lián)網(wǎng)工程學(xué)院，江蘇 無錫 214122）

模式識別（Pattern Recognition）是對感知信號（圖像、視頻、聲音等）進(jìn)行分析，對其中的物體對象或行為進(jìn)行判別和解釋的過程，是信息科學(xué)和人工智能的重要組成部分。模式識別所研究的理論和方法在很多科學(xué)和技術(shù)領(lǐng)域中得到廣泛的認(rèn)可和重視，近些年越來越多地被應(yīng)用在生物醫(yī)學(xué)工程領(lǐng)域，如進(jìn)行醫(yī)學(xué)圖像處理、生物電信號分析、細(xì)胞的識別以及中醫(yī)診斷治療，它已經(jīng)成為生物醫(yī)學(xué)工程中的重要研究手段。

本文擬用模式識別領(lǐng)域常用的決策樹與Ada－Boost技術(shù)來處理醫(yī)學(xué)領(lǐng)域常用的質(zhì)譜分析數(shù)據(jù)，對癌變細(xì)胞和正常細(xì)胞進(jìn)行有效分類，這將對疾病的治療與預(yù)防有著廣泛而積極的意義。

1 數(shù)據(jù)介紹

本文擬分析的數(shù)據(jù)集來自下面鏈接的網(wǎng)絡(luò)資源：http：／／home.ccr.cancer.gov／ncifdaproteomics／ppatterns.asp。

該數(shù)據(jù)提供了大量的質(zhì)譜分析數(shù)據(jù)，供醫(yī)療機構(gòu)進(jìn)行癌癥診斷的研究。本文擬使用研究的算法對其進(jìn)行分類研究，即根據(jù)特定病人的質(zhì)譜分析數(shù)據(jù)，來自動推斷該病人是否患有癌癥。該數(shù)據(jù)集共有216個樣本。為了合理地設(shè)計一個推廣性能較好的分類器，也為了準(zhǔn)確地評估設(shè)計好的分類器，隨機選用其中152個作為訓(xùn)練數(shù)據(jù)集，32個作為訓(xùn)練中使用的驗證數(shù)據(jù)集，32個作為測試數(shù)據(jù)集。

2 分類樹與AdaBoost技術(shù)

2.1 決策樹與分類樹

決策論中，決策樹由一個決策圖和可能的結(jié)果（包括資源成本和風(fēng)險）組成，用來創(chuàng)建到達(dá)目標(biāo)的規(guī)劃。決策樹是一個利用像樹一樣的圖形或決策模型的決策支持工具，包括隨機事件結(jié)果，資源代價和實用性。決策樹建立并用來輔助決策，是一種特殊的樹結(jié)構(gòu)，也是一個算法顯示的方法。決策樹經(jīng)常在運籌學(xué)中使用，特別是在決策分析時，它幫助確定一個能最可能達(dá)到目標(biāo)的策略。如果在實際中，決策不得不在沒有完備知識的情況下被在線采用，一個決策樹應(yīng)該平行概率模型作為最佳的選擇模型或在線選擇模型算法。決策樹的另一個使用是作為計算條件概率的描述性手段。

機器學(xué)習(xí)中，決策樹是一個預(yù)測模型［1］。它表示的是一種對象屬性與對象值之間的映射關(guān)系。決策樹中的各個節(jié)點代表是所要描述的對象，而每個分叉路徑則表示為可能實現(xiàn)的屬性值，而每個葉結(jié)點則對應(yīng)從根節(jié)點到該葉節(jié)點所經(jīng)歷的路徑所表示的對象的值。決策樹僅有單一輸出，若欲有復(fù)數(shù)輸出，可以建立獨立的決策樹以處理不同輸出。數(shù)據(jù)挖掘中決策樹是一種經(jīng)常要用到的技術(shù)，可以用于分析數(shù)據(jù)，同樣也可以用來作預(yù)測。

從數(shù)據(jù)產(chǎn)生決策樹的機器學(xué)習(xí)技術(shù)叫做決策樹學(xué)習(xí)，通俗說就是決策樹。決策樹學(xué)習(xí)也是資料探勘中一個普通的方法。在這里，每個決策樹都表述了一種樹型結(jié)構(gòu)，它由它的分支來對該類型的對象依靠屬性進(jìn)行分類。每個決策樹可以依靠對源數(shù)據(jù)庫的分割進(jìn)行數(shù)據(jù)測試。這個過程可以遞歸式地對樹進(jìn)行修剪。當(dāng)不能再進(jìn)行分割或一個單獨的類可以被應(yīng)用于某一分支時，遞歸過程就完成了。另外，隨機森林分類器［2］將許多決策樹結(jié)合起來以提升分類的正確率。

2.2 分類樹的提升

隨機森林對分類樹的集成，是基于袋裝（bagging）的機制，而實際使用中還有提升（boosting）的集成機制。

AdaBoost算法是二元分類問題中常用的一種提升方法［3］。它針對不同的訓(xùn)練集訓(xùn)練同一個基本分類器（弱分類器），然后把這些在不同訓(xùn)練集上得到的分類器集合起來，構(gòu)成一個更強的最終的分類器（強分類器）。理論證明，只要每個弱分類器分類能力比隨機猜測要好，當(dāng)其個數(shù)趨向于無窮個數(shù)時，強分類器的錯誤率將趨向于零。AdaBoost算法中不同的訓(xùn)練集是通過調(diào)整每個樣本對應(yīng)的權(quán)重實現(xiàn)的。最開始的時候，每個樣本對應(yīng)的權(quán)重是相同的，在此樣本分布下訓(xùn)練出一個基本分類器h1（x）。對于h1（x）錯分的樣本，則增加其對應(yīng)樣本的權(quán)重；而對于正確分類的樣本，則降低其權(quán)重。這樣可以使得錯分的樣本突出出來，并得到一個新的樣本分布。同時，根據(jù)錯分的情況賦予h1（x）一個權(quán)重，表示該基本分類器的重要程度，錯分得越少權(quán)重越大。在新的樣本分布下，再次對基本分類器進(jìn)行訓(xùn)練，得到基本分類器h2（x）及其權(quán)重。依次類推，經(jīng)過T次這樣的循環(huán)，就得到了T個基本分類器，以及T個對應(yīng)的權(quán)重。最后把這T個基本分類器按一定權(quán)重累加起來，就得到了最終所期望的強分類器。

AdaBoost具有以下優(yōu)勢：快速，易于編程，不需要調(diào)整參數(shù)，可以組合任何學(xué)習(xí)算法，不需要關(guān)于弱分類器的先驗知識等。

3 關(guān)鍵特征排序

特征選擇，通過只選擇被測特征（預(yù)測變量）的一個子集來創(chuàng)建模型，降低了數(shù)據(jù)的維數(shù)。選擇準(zhǔn)則通常涉及最小化擬合不同子集的模型的一個特定的預(yù)測誤差的度量。算法搜索一個預(yù)測變量的子集，以最優(yōu)化模型的測量響應(yīng)，最優(yōu)化的約束條件為要求的特征、排除的特征、或者子集的大小。為了避免過擬合，對于高維數(shù)據(jù)，在進(jìn)行分類之前，首先要進(jìn)行降維。降維的方法之一就是從特征向量中選擇出顯著性較高的特征。

質(zhì)譜分析數(shù)據(jù)是高維數(shù)據(jù)。以本文的數(shù)據(jù)集為例，其維數(shù)高達(dá)15 000。在進(jìn)行數(shù)值實驗之前，根據(jù)類可分性準(zhǔn)則（這里使用的準(zhǔn)則是相對熵，即KL距離），將數(shù)據(jù)中的關(guān)鍵特征排序，取其中的前10位作為分類預(yù)測使用的特征向量。常用的類可分性準(zhǔn)則有：t檢驗準(zhǔn)則、KL距離準(zhǔn)則、Chernoff界準(zhǔn)則。這三者都假定各個類服從正態(tài)分布，而ROC準(zhǔn)則與Wilcoxon測試準(zhǔn)則則屬于非參數(shù)檢驗。

4 實驗與分析

本文使用KL距離可分性準(zhǔn)則，選出15個最顯著的特征。在獲取顯著性較高的特征之后，使用以分類樹為弱學(xué)習(xí)器的AdaBoost算法進(jìn)行實驗。實驗所得的置換誤差曲線如圖1所示。從圖中可以看出，隨著決策樹的個數(shù)的增大，模型的置換誤差迅速減小。

圖1 置換誤差曲線

Hold誤差是對推廣誤差的更好的一種評估。圖2給出了該模型的Hold誤差曲線。決策樹個數(shù)較小的時候，該模型就達(dá)到了較低的推廣誤差。但是，隨著決策樹個數(shù)的增大，推廣誤差仍呈現(xiàn)出減小的趨勢。

圖2 Holdout誤差曲線

AdaBoost的優(yōu)異性能可以從間隔最大化的角度來解釋。盡管集成分類器變得越來越大，但是間隔很可能也在增大，所以，最終的分類器實際上接近于一個更簡單的分類器，從而降低了測試誤差。

相比于經(jīng)典的支持向量機［4－5］，二者相同點是：都通過最大化間隔來工作，都在高維空間中尋找線性閾值函數(shù)；不同點是：使用不同的范數(shù)來度量間隔，SVM 使用核技巧來處理高維空間，而Ada－Boost使用弱分類器在空間中搜索；SVM最大化最小的間隔，而AdaBoost最大化間隔分布［6］。

5 結(jié)論

本文研究了基于決策樹的AdaBoost的質(zhì)譜數(shù)據(jù)分析。首先，介紹了AdaBoost的一般理論，然后，以分類樹為弱學(xué)習(xí)器，調(diào)整集成學(xué)習(xí)器中的弱分類器的個數(shù)，研究了弱分類器個數(shù)對分類性能的影響。最后，將AdaBoost與SVM類比，從大間隔學(xué)習(xí)的觀點出發(fā)，解釋了AdaBoost的優(yōu)勢。

［1］Safavian，S.R.and D.Landgrebe.A survey of decision tree classifier methodology ［J］.IEEE Transactions on Systems，Man and Cybernetics，1991，21（3）：660－674.

［2］Breiman L.Random Forests［J］.Machine Learning，2001，45（1）：5－32.

［3］Schapire，R.and Y.Freund，et al.Boosting the Margin：A New Explanation for the Effectiveness of Voting Methods［J］.The Annals of Statistics，1998，26（5）：1651－1686.

［4］張學(xué)工.關(guān)于統(tǒng)計學(xué)習(xí)理論與支持向量機［J］.自動化學(xué)報，2000，26（1）：32－42.

［5］Cortes，C.and V.Vapnik.Support－Vector Networks［J］.Machine Learning，1995，20（3）：273－297.

［6］Freund，Y.and R.Schapire.A Desicion－Theoretic Generalization of On－Line Learning and an Application to Boosting［J］.Lecture Notes in Computer Science，1995，904：23－27.