單位代價(jià)收益敏感決策樹(shù)分類(lèi)算法及其剪枝算法的研究.pdf

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

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

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

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

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

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

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