基于決策樹的單調(diào)分類算法研究.pdf

1、決策樹算法是應(yīng)用最廣泛的歸納學(xué)習(xí)算法之一,是一種逼近離散值目標(biāo)函數(shù)的方法,它自頂向下運用遞歸方式,構(gòu)造一棵揭示數(shù)據(jù)內(nèi)部關(guān)系的樹,進(jìn)而得出決策規(guī)則。單調(diào)分類是一種重要的分類任務(wù),在這種任務(wù)中需要考慮條件屬性和決策之間的單調(diào)性約束:當(dāng)一個對象的所有條件屬性上的取值都不比另一個對象差時,它的決策也不會比另一個對象的決策差。Hu等人提出基于有序信息熵的決策樹算法REMT,該算法用于單調(diào)分類問題,只要訓(xùn)練數(shù)據(jù)是單調(diào)的,就能生成單調(diào)一致的決策樹,即

2、使數(shù)據(jù)中包含噪聲,也能夠獲得較好的結(jié)果。為了得到精度和分類效率更高的分類器,本文在REMT算法的基礎(chǔ)上,研究了基于決策樹的單調(diào)分類算法,主要工作如下:
　　(1)在決策樹算法中引入了前向有序互信息和后向有序互信息,討論了它們在不同噪聲等級下的變化情況,提出用前向和后向有序互信息分別構(gòu)造前向和后向有序決策樹的決策樹生成算法,并利用規(guī)則精度將兩者集結(jié)構(gòu)造了分類器。在人造數(shù)據(jù)集和真實數(shù)據(jù)集中分別進(jìn)行了實驗,實驗證明該算法不但保證了單調(diào)分

3、類問題上決策規(guī)則的單調(diào)一致性,還提高了分類器的分類精度,并通過適當(dāng)放寬決策樹的終止條件,減少了決策樹的深度以及分類規(guī)則的長度,避免了決策樹的過度擬合。
　　(2)借鑒決策森林的思想,提出了基于決策森林的單調(diào)分類算法,算法中引入了重采樣技術(shù),對訓(xùn)練集進(jìn)行重采樣獲得多個訓(xùn)練子集,從不同的角度構(gòu)造決策森林中的每棵決策樹,得到了既有一定的相似性,又能較大程度的覆蓋原始訓(xùn)練集中數(shù)據(jù)對象的多棵決策樹。在人造數(shù)據(jù)集和真實數(shù)據(jù)集中分別進(jìn)行了實驗,