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

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

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

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

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

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

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

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

2.1 決策樹(shù)與分類樹(shù)

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

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

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

2.2 分類樹(shù)的提升

隨機(jī)森林對(duì)分類樹(shù)的集成，是基于袋裝（bagging）的機(jī)制，而實(shí)際使用中還有提升（boosting）的集成機(jī)制。

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

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

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

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

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

4 實(shí)驗(yàn)與分析

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

圖1 置換誤差曲線

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

圖2 Holdout誤差曲線

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

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

5 結(jié)論

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

［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)計(jì)學(xué)習(xí)理論與支持向量機(jī)［J］.自動(dòng)化學(xué)報(bào)，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.