優(yōu)化的ID3算法在酒店客房續(xù)費問題中的應(yīng)用.pdf

1、隨著數(shù)據(jù)庫技術(shù)的逐步成熟，分類預(yù)測之類的數(shù)據(jù)挖掘技術(shù)也得到了高速的發(fā)展，分類預(yù)測技術(shù)中的決策樹方法也常常被應(yīng)用于多個行業(yè)領(lǐng)域。ID3算法作為影響力最大的決策樹算法之一而且得到了大范圍的應(yīng)用，然而ID3算法也有一些不足之處。本文主要針對ID3算法多值偏向、算法公式計算量大兩方面的的缺陷，通過對ID3算法進(jìn)行算法改進(jìn)和公式簡化，從而實現(xiàn)對ID3算法的優(yōu)化，主要進(jìn)行的工作為：
　　(1)提出基于矯正函數(shù)的ID3優(yōu)化方案。在基于矯正函數(shù)的

2、ID3優(yōu)化方案中，克服多值偏向問題的方法為：通過引入矯正函數(shù)的定義，對子元組所需的期望信息量進(jìn)行矯正，多值偏向分析證明改進(jìn)后的ID3算法可克服多值偏向問題；克服ID3信息增益公式運算較為耗時的方法為：通過利用等價無窮小簡化信息增益公式，使得簡化后的信息增益公式中已消除了較為耗時的對數(shù)運算。最后，將算法改進(jìn)和信息增益公式簡化兩部分的工作相結(jié)合，并提出了基于矯正函數(shù)的決策樹優(yōu)化算法。實驗結(jié)果分析表明：與ID3算法相比，在分類精度和計算時間兩

3、個方面，基于矯正函數(shù)的決策樹優(yōu)化算法具有更好的優(yōu)化效果。
　　(2)提出基于相關(guān)系數(shù)的ID3優(yōu)化方案。在基于相關(guān)系數(shù)的ID3優(yōu)化方案中，克服多值偏向問題的方法為：將相關(guān)系數(shù)修改成適用于決策樹領(lǐng)域的新型相關(guān)系數(shù)，通過引入新型相關(guān)系數(shù)子元組所需的期望信息量進(jìn)行重新矯正，實驗中的多值偏向相關(guān)理論的分析證明了改進(jìn)后的ID3算法能夠解決克服多值偏向的缺陷；克服ID3信息增益公式運算較為耗時的方法為：通過利用麥克勞林公式簡化信息增益公式，使得

4、簡化后的信息增益公式中已消除了較為耗時的對數(shù)運算。最后，將算法改進(jìn)和信息增益公式簡化兩部分之間工作進(jìn)行結(jié)合，得到了基于相關(guān)系數(shù)的決策樹優(yōu)化算法。實驗結(jié)果表明，相比于ID3算法，基于相關(guān)系數(shù)的決策樹優(yōu)化算法既能克服多值偏向問題，又具有更高的分類精度，同時也降低了決策樹的生成時間；相比于基于矯正函數(shù)的決策樹優(yōu)化算法，除了在決策樹生成時間方面，基于相關(guān)系數(shù)的決策樹優(yōu)化算法的時間較長；但在分類精度方面，基于相關(guān)系數(shù)的決策樹優(yōu)化算法則更顯優(yōu)勢。<