單位代價收益敏感決策樹分類算法及其剪枝算法的研究.pdf

1、數(shù)據(jù)挖掘是一門可以應(yīng)用于多研究領(lǐng)域的交叉學(xué)科，分類分析法因其在信息化產(chǎn)業(yè)界中的廣泛應(yīng)用逐漸變成了數(shù)據(jù)挖掘中的研究熱點。常用的分類算法包括決策樹分類算法、貝葉斯分類算法、神經(jīng)網(wǎng)絡(luò)算法、支持向量機算法、k-最近鄰分類算法等等。而決策樹分類法以其速度快、精確度高、直觀易懂等優(yōu)點深得研究者們的喜愛，在數(shù)據(jù)挖掘領(lǐng)域里得到了深入的研究與應(yīng)用。
　　決策樹分類算法的主要特征在四個方面:一是擴展屬性選擇標準，二是停止建樹的準則，三是葉子結(jié)點的類標

2、號判斷準則，四是剪枝優(yōu)化策略。目前，對決策樹分類算法的研究主要致力于兩個方面:擴展屬性選擇標準和剪枝優(yōu)化策略。本文也是重點在這兩個方面展開研究。修剪決策樹的兩個簡單理由:一是訓(xùn)練數(shù)據(jù)集中存在噪聲，使得生成的決策樹對訓(xùn)練樣例產(chǎn)生過擬合現(xiàn)象，從而造成對新的實際數(shù)據(jù)分類效果不理想。二是訓(xùn)練數(shù)據(jù)樣例分布具有特殊性，造成構(gòu)建出來的決策樹分類器難以代表現(xiàn)實世界中的一般規(guī)律。本文對預(yù)剪枝和后剪枝算法做了系統(tǒng)闡述，并對常見的幾種后剪枝算法做了分析比較。

3、
　　代價敏感分類學(xué)習(xí)問題的出現(xiàn)將對決策樹分類算法的研究推到了一個嶄新的高度。然而，其研究方向大都致力于對擴展屬性選擇標準的改進，將代價敏感學(xué)習(xí)與剪枝優(yōu)化算法結(jié)合的研究還不多見。同時，代價敏感學(xué)習(xí)是以最小化代價為目標，忽略了決策過程中可能產(chǎn)生的收益。例如，在投資領(lǐng)域中，激進的投資者往往會犧牲一部分代價來換取最大的收益。針對上述代價與收益并存的應(yīng)用環(huán)境，本文提出一種單位代價收益敏感決策樹分類算法。其能實現(xiàn)在同等代價條件下最大化收益的

4、決策目標。在此基礎(chǔ)上，進一步提出了兩種基于單位代價收益的決策樹后剪枝算法，并通過實驗證明所提算法的可行性和實用性。本文的主要研究工作如下:
　　(1)基于代價與收益并存的應(yīng)用環(huán)境，提出一種單位代價收益敏感決策樹分類算法。為彌補代價敏感學(xué)習(xí)中忽略了正確分類可能會帶來收益的不足，本文采用調(diào)和函數(shù)權(quán)衡屬性信息增益與性價比重新構(gòu)造了新型的擴展屬性選擇標準ASF。并采用“單位代價收益最大化”原則代替?zhèn)鹘y(tǒng)的“多數(shù)類”原則，作為葉子結(jié)點的類標號

5、判斷準則。為對該算法的實用性和有效性進行評估，通過三部分實驗進行分析比較。第一部分實驗將本文所提算法UCGS與C4.5以及一種代價敏感算法CS C4.5進行比較分析。結(jié)果表明在相同代價下，通過UCGS算法構(gòu)建的決策樹所獲得的單位代價收益最大，且具有較高的分類正確率和良好的穩(wěn)定性。第二部分實驗表明其對于非均衡問題，也表現(xiàn)出了良好的分類效果，具備一定的應(yīng)用價值。第三部分實驗表明該算法在與其他三種代價敏感算法的比較中也表現(xiàn)出了良好的效果。綜合

6、來看，該算法能夠在保證決策樹分類正確率的前提下實現(xiàn)以最小代價獲得最高收益的決策目標，能夠很好的解決代價與收益并存的應(yīng)用環(huán)境下的實際問題。
　　(2)提出一種與預(yù)剪枝策略相結(jié)合的單位代價收益決策樹剪枝算法。此算法采用單位代價收益剪枝策略與預(yù)剪枝策略相結(jié)合的方式對生成的決策樹進行剪枝，使其具有代價敏感的性質(zhì)。實驗結(jié)果表明本文所提算法與REP、EBP兩種剪枝算法相比，在絕大多數(shù)數(shù)據(jù)集上其決策樹規(guī)模要小于REP和EBP算法所生成的決策樹，

7、在具有多種類別的數(shù)據(jù)集上表現(xiàn)尤為良好。且此算法擁有良好的分類正確率，能夠提高決策樹的預(yù)測準確度。此外，通過代價收益矩陣的設(shè)置，用戶可以根據(jù)自己的需求調(diào)整分類決策樹，從而改變了依賴固有算法的缺點，在靈活性上有一定的改善。
　　(3)提出一種基于代價復(fù)雜度的單位代價收益敏感決策樹剪枝算法(以下簡稱UCG-CCP)。此算法采用單位代價收益剪枝策略與代價復(fù)雜度相結(jié)合的方式，設(shè)置剪枝因子β，選擇具有最小β(T)值的一棵子樹作為最終剪枝后的最