前向決策樹算法的研究與改進.pdf

1、決策樹學(xué)習(xí)是應(yīng)用最廣泛的歸納推理算法之一。目前存在的決策樹歸納算法大多數(shù)是基于自頂向下的貪婪算法，它在每個結(jié)點都執(zhí)行一個局部最優(yōu)決策。然而，在大多數(shù)情況下，貪婪算法構(gòu)造的樹不是全局最優(yōu)的。對于貪婪算法的改進，前向搜索是一種眾所周知的技術(shù)。大多數(shù)人認(rèn)為，前向決策樹算法產(chǎn)生的決策樹優(yōu)于貪婪算法，并且搜索深度越深其效果越好。然而，在實際中前向決策樹算法得到的結(jié)果并非如此，許多文獻通過實驗指出在決策樹歸納過程中前向搜索往往會傷害決策樹的質(zhì)量。<

2、br>　　 本文以ID3算法為基礎(chǔ)，研究了前向決策樹算法，并與貪婪算法的建樹過程進行了對比。通過實例將前向決策樹算法與經(jīng)典的ID3算法進行了比較，結(jié)果表明針對某些特定的問題前者在保證分類精度不降低的同時也簡化了決策樹。本文還重點分析了前向決策樹算法存在的缺點，正是由于算法本身存在的這些缺陷使得產(chǎn)生的決策樹沒有質(zhì)量上的提高。為了改進前向決策樹算法，本文提出了一種基于屬性約簡的建樹方法——受限制的前向決策樹算法。改進后的算法限制了前向決策