改進(jìn)代價(jià)敏感的決策樹學(xué)習(xí)方法研究.pdf

1、從廣義上講，機(jī)器學(xué)習(xí)（Machine Learning）是以使其包括任何計(jì)算機(jī)程序通過經(jīng)驗(yàn)來提高其任務(wù)處理性能的行為。如果機(jī)器能夠真正完全地根據(jù)經(jīng)驗(yàn)來自動(dòng)提高，其影響將是空前的。為此，自從第一臺(tái)電子計(jì)算機(jī)ENIAC問世以來，大批學(xué)者與專家就在為使其能夠自我學(xué)習(xí)而不懈努力。到目前為止，針對(duì)特定學(xué)習(xí)任務(wù)的算法已產(chǎn)生，關(guān)于學(xué)習(xí)的理論認(rèn)識(shí)已開始形成，其中，從特殊的訓(xùn)練樣例中歸納出一般函數(shù)是機(jī)器學(xué)習(xí)的中心問題，而決策樹學(xué)習(xí)則是應(yīng)用最廣的歸納推理算

2、法之一]。決策樹方法在實(shí)際中有著廣泛的應(yīng)用，如根據(jù)疾病分類患者；根據(jù)起因分類設(shè)備故障；根據(jù)拖欠支付的可能性分類貸款申請(qǐng)。這類問題的核心任務(wù)都是把樣例分入各個(gè)可能的對(duì)應(yīng)的類別中，因此稱為分類問題（Classification problem）。 經(jīng)典的分類問題是在假設(shè)為各種分類錯(cuò)誤所要付出的代價(jià)相同的情況下，要求達(dá)到高的分類正確率。然而這種假設(shè)在實(shí)際應(yīng)用中很難滿足，如根據(jù)疾病分類患者問題中，將病人判斷為健康者與將健康者判斷為病人，

3、這兩種錯(cuò)誤的診斷所要付出的代價(jià)一定是不相同的。針對(duì)此類問題，專家們提出了代價(jià)敏感的學(xué)習(xí)方法（Cost-sensitive Learning，CSL）。由于其在現(xiàn)實(shí)中廣泛的應(yīng)用，近年來一直是機(jī)器學(xué)習(xí)領(lǐng)域中的一個(gè)研究熱點(diǎn)。 本文首先介紹了機(jī)器學(xué)習(xí)的主要研究領(lǐng)域，并分析了目前國內(nèi)外關(guān)于代價(jià)敏感學(xué)習(xí)的理論與方法，指出現(xiàn)有的代價(jià)敏感學(xué)習(xí)方法的優(yōu)點(diǎn)與不足。針對(duì)存在的問題與不足，提出了一些新方法，并通過實(shí)驗(yàn)證明本文所提出的方法的可行性與有效性

4、。本文的主要內(nèi)容如下（其中部分工作于參考文獻(xiàn)中發(fā)表）： （1）簡(jiǎn)述決策樹（Decision Tree）方法以及代價(jià)敏感學(xué)習(xí)（CSL）現(xiàn)有的方法，分析其優(yōu)缺點(diǎn)。同時(shí)也介紹了與代價(jià)敏感學(xué)習(xí)密切相關(guān)的代價(jià)約束（Budget Learning）及主動(dòng)學(xué)習(xí)（Active Learning）的概念和基本方法。 （2）提出代價(jià)約束下的代價(jià)敏感學(xué)習(xí)的新方法。 本論文改變了前人將代價(jià)敏感學(xué)習(xí)中各種代價(jià)（如獲得每個(gè)實(shí)例的屬性值的代價(jià)

5、和發(fā)生錯(cuò)誤判斷時(shí)所要付出的代價(jià)）用同一代價(jià)尺度來衡量的習(xí)慣做法，取而代之用不同的代價(jià)尺度來衡量不同的代價(jià)。另外，在前人的部分工作中，假設(shè)獲取訓(xùn)練實(shí)例需要代價(jià)且訓(xùn)練階段存在資源約束，因而此時(shí)需要使用一定的方法用最小的資源獲得關(guān)鍵的實(shí)例進(jìn)行訓(xùn)練，從而得到有效的分類器。但現(xiàn)實(shí)中，還存在一種約束，即在測(cè)試階段的資源約束。如對(duì)于醫(yī)療數(shù)據(jù)庫，當(dāng)分類器建立好以后，進(jìn)入測(cè)試階段，若測(cè)試的實(shí)例由于資源約束無法得到分類器所需要的屬性值，在前人的工作中，此時(shí)

6、只能停留在當(dāng)前結(jié)點(diǎn)中，無法進(jìn)一步判斷。我們的問題是如何在資源有限的條件下，怎樣使得分類效果總體相對(duì)最優(yōu)。針對(duì)此問題，我們采用擴(kuò)展的主動(dòng)學(xué)習(xí)與含有空結(jié)點(diǎn)的決策樹相結(jié)合的方法，充分利用給定的有限資源，獲取盡可能多的有用信息，提高分類效果，降低誤分類代價(jià)。 （3）提出代價(jià)敏感決策樹學(xué)習(xí)方法的進(jìn)一步優(yōu)化的新方法。 本論文還基于現(xiàn)實(shí)存在的捆綁測(cè)試屬性打折情況，指出了前人此工作[51]存在的問題。提出了組合測(cè)試的方法，從而化解了決策

7、樹要求順序測(cè)試屬性與捆綁屬性打折要求組合屬性進(jìn)行測(cè)試之間的矛盾，使得捆綁打折可以有效地降低測(cè)試代價(jià)。最終使得建立的分類器能夠在資源有限的條件下，最小化誤分類代價(jià)。 本論文主要有以下創(chuàng)新點(diǎn)： (1) 指出了前人工作中將測(cè)試代價(jià)和誤分類代價(jià)轉(zhuǎn)化為一維代價(jià)所帶來的問題，提出了用二維代價(jià)尺度表示兩類不同的代價(jià)。 (2) 資源約束是隨處可見的。在前人的工作中，只注意到在做實(shí)驗(yàn)中為獲取實(shí)例時(shí)所受資源的約束；本文提出了在另一階

8、段，即測(cè)試階段，由于資源約束而無法獲得應(yīng)有的知識(shí)情況下，追求最優(yōu)結(jié)果的方法。 (3) 針對(duì)本文提出的問題，提出了采用擴(kuò)展的主動(dòng)學(xué)習(xí)與含有空結(jié)點(diǎn)的決策樹相結(jié)合的方法以達(dá)到在此類資源約束下的最優(yōu)結(jié)果。 (4) 指出了已有的關(guān)于處理捆綁測(cè)試打折問題工作的不足之處，提出了新的組合測(cè)試的方法。 本文所提出的方法是在前人工作的基礎(chǔ)上，以現(xiàn)實(shí)存在的問題為出發(fā)點(diǎn)，力求算法彌補(bǔ)已有算法的不足之處，使之更適合于現(xiàn)實(shí)的應(yīng)用。對(duì)于文中提