基于程序演化的決策樹算法優(yōu)化研究.pdf

1、程序演化是根據(jù)某些法則從一個(gè)程序生成另一個(gè)新的程序，這兩個(gè)程序在語(yǔ)義上是等價(jià)的，通過(guò)對(duì)源程序進(jìn)行一系列保證正確性的演化，進(jìn)行算法和數(shù)據(jù)結(jié)構(gòu)的求精，最終將源程序演化成一個(gè)等價(jià)的、高效的程序文本。 本文在決策樹的優(yōu)化問(wèn)題中，引入程序演化的思想，演化得到了具有更高效率的決策樹。圍繞該問(wèn)題展開了以下工作： (1)用Homomorphisms遞歸結(jié)構(gòu)描述ID3算法。為演化出新的高效程序奠定基礎(chǔ)。 (2)在對(duì)程序的規(guī)范化描述

2、進(jìn)行認(rèn)真分析的基礎(chǔ)上，找到影響程序運(yùn)行效率的主要因素，運(yùn)用tupling策略定義新的數(shù)據(jù)結(jié)構(gòu)。 (3)基于新的數(shù)據(jù)結(jié)構(gòu)，對(duì)標(biāo)準(zhǔn)ID3算法和基于樣本分布元組的決策樹算法進(jìn)行演化，運(yùn)用節(jié)點(diǎn)提升算法，最終演化得到新的基于樣本分布樹的決策樹構(gòu)造算法，該算法構(gòu)造決策樹只需要掃描一次數(shù)據(jù)集合。 (4)對(duì)本文演化所得的新決策樹算法的時(shí)間有效性進(jìn)行分析，并用Haskell函數(shù)式語(yǔ)言編程實(shí)現(xiàn)相關(guān)算法，對(duì)算法的正確性和有效性進(jìn)行驗(yàn)證。