改進代價敏感的決策樹學習方法研究.pdf

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

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

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

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

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

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

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

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