決策樹算法及其改進

蔡星

摘 要：該文對傳統(tǒng)的C4.5決策樹數(shù)據(jù)挖掘算法進行了改進，提出了一種雙重熵平均決策樹算法。傳統(tǒng)的C4.5決策樹算法易出現(xiàn)無意義分枝，過度擬合等問題，針對該類問題，基于雙重熵平均決策樹算法，通過兩次對樣本子集熵平均值的計算、排序、合并處理，得到修正后的屬性信息增益，并以此作為屬性選擇的依據(jù)，從而解決了傳統(tǒng)C4.5決策樹算法可解釋性差、易產(chǎn)生碎片等問題。

關(guān)鍵詞：C4.5決策樹 算法 熵 平衡因子

中圖分類號：TP311.13 文獻標(biāo)識碼：A 文章編號：1674-098X（2014）04（c）-0040-02

數(shù)據(jù)聯(lián)機分析功能是通過對數(shù)據(jù)的處理發(fā)現(xiàn)已知要素與分析度量值之間的關(guān)系，而數(shù)據(jù)挖掘則是從大量的數(shù)據(jù)中發(fā)現(xiàn)隱藏的規(guī)律。數(shù)據(jù)挖掘包括多種挖掘算法，為了研究畢業(yè)生不同屬性與其就業(yè)狀況之間的潛在知識和規(guī)律，該文采用決策樹方法對高校畢業(yè)生數(shù)據(jù)進行分析，主要選用的是C4.5決策樹算法。

1 C4.5算法思想

決策樹的優(yōu)點在于原理簡單，發(fā)現(xiàn)知識較快；計算較為簡單，運算速度較快，對于訓(xùn)練數(shù)據(jù)的處理和待決策數(shù)據(jù)的處理效率相對較高；適用于大量數(shù)據(jù)的綜合處理，有利于挖掘數(shù)據(jù)中的重要屬性；最終得到的挖掘結(jié)果是有意見的規(guī)則，有利于用戶的理解。決策樹的主要缺點包括：對數(shù)據(jù)的時間屬性較為敏感，需要大量的預(yù)處理工作；對于非離散的連續(xù)性數(shù)據(jù)值處理效率和準(zhǔn)確率不佳；易出現(xiàn)過度擬合的情況，產(chǎn)生大量的決策分支，導(dǎo)致決策規(guī)則過于龐大。

C4.5決策樹算法是決策樹算法的主流，它繼承于傳統(tǒng)的ID3算法，繼承了其優(yōu)勢，改進了其缺點。但C4.5決策樹算法依然存在著較多的問題，其中最為突出的是過度擬合情況，以及決策準(zhǔn)確性方面的問題。針對上述問題，本課題提出了一種改進的C4.5決策樹算法，在算法構(gòu)建過程中，以樹分枝的信息熵為研究對象，將熵值較高的部分和熵值較低的部分進行合并和平衡處理，從而達到減少決策樹分支數(shù)量的目的；與此同時，考慮到C4.5算法在決策分支的確定過程中采用的是局部最優(yōu)的方法，在準(zhǔn)確性方面從整體上看有所欠缺，所以引入了了平衡因子控制算法的整體最優(yōu)化性。

C4.5決策樹算法設(shè)研究對象數(shù)據(jù)集為，該數(shù)據(jù)集中包括個類別，每一個類別表示為，選取該數(shù)據(jù)集中的一個屬性數(shù)據(jù)，則可以被劃分為多個子集，設(shè)有個取值，則被劃分的子集可表示為。設(shè)為的例子總數(shù)，而為的例子數(shù)，為的例子總數(shù)，是的所有例子中所包括的的例子數(shù)，基于上述的設(shè)定，則可以得到如下定義：

（1）類別在出現(xiàn)的概率如式（1）所示：

（1）endprint

摘 要：該文對傳統(tǒng)的C4.5決策樹數(shù)據(jù)挖掘算法進行了改進，提出了一種雙重熵平均決策樹算法。傳統(tǒng)的C4.5決策樹算法易出現(xiàn)無意義分枝，過度擬合等問題，針對該類問題，基于雙重熵平均決策樹算法，通過兩次對樣本子集熵平均值的計算、排序、合并處理，得到修正后的屬性信息增益，并以此作為屬性選擇的依據(jù)，從而解決了傳統(tǒng)C4.5決策樹算法可解釋性差、易產(chǎn)生碎片等問題。

關(guān)鍵詞：C4.5決策樹 算法 熵 平衡因子

中圖分類號：TP311.13 文獻標(biāo)識碼：A 文章編號：1674-098X（2014）04（c）-0040-02

數(shù)據(jù)聯(lián)機分析功能是通過對數(shù)據(jù)的處理發(fā)現(xiàn)已知要素與分析度量值之間的關(guān)系，而數(shù)據(jù)挖掘則是從大量的數(shù)據(jù)中發(fā)現(xiàn)隱藏的規(guī)律。數(shù)據(jù)挖掘包括多種挖掘算法，為了研究畢業(yè)生不同屬性與其就業(yè)狀況之間的潛在知識和規(guī)律，該文采用決策樹方法對高校畢業(yè)生數(shù)據(jù)進行分析，主要選用的是C4.5決策樹算法。

1 C4.5算法思想

決策樹的優(yōu)點在于原理簡單，發(fā)現(xiàn)知識較快；計算較為簡單，運算速度較快，對于訓(xùn)練數(shù)據(jù)的處理和待決策數(shù)據(jù)的處理效率相對較高；適用于大量數(shù)據(jù)的綜合處理，有利于挖掘數(shù)據(jù)中的重要屬性；最終得到的挖掘結(jié)果是有意見的規(guī)則，有利于用戶的理解。決策樹的主要缺點包括：對數(shù)據(jù)的時間屬性較為敏感，需要大量的預(yù)處理工作；對于非離散的連續(xù)性數(shù)據(jù)值處理效率和準(zhǔn)確率不佳；易出現(xiàn)過度擬合的情況，產(chǎn)生大量的決策分支，導(dǎo)致決策規(guī)則過于龐大。

C4.5決策樹算法是決策樹算法的主流，它繼承于傳統(tǒng)的ID3算法，繼承了其優(yōu)勢，改進了其缺點。但C4.5決策樹算法依然存在著較多的問題，其中最為突出的是過度擬合情況，以及決策準(zhǔn)確性方面的問題。針對上述問題，本課題提出了一種改進的C4.5決策樹算法，在算法構(gòu)建過程中，以樹分枝的信息熵為研究對象，將熵值較高的部分和熵值較低的部分進行合并和平衡處理，從而達到減少決策樹分支數(shù)量的目的；與此同時，考慮到C4.5算法在決策分支的確定過程中采用的是局部最優(yōu)的方法，在準(zhǔn)確性方面從整體上看有所欠缺，所以引入了了平衡因子控制算法的整體最優(yōu)化性。

C4.5決策樹算法設(shè)研究對象數(shù)據(jù)集為，該數(shù)據(jù)集中包括個類別，每一個類別表示為，選取該數(shù)據(jù)集中的一個屬性數(shù)據(jù)，則可以被劃分為多個子集，設(shè)有個取值，則被劃分的子集可表示為。設(shè)為的例子總數(shù)，而為的例子數(shù)，為的例子總數(shù)，是的所有例子中所包括的的例子數(shù)，基于上述的設(shè)定，則可以得到如下定義：

（1）類別在出現(xiàn)的概率如式（1）所示：

（1）endprint

摘 要：該文對傳統(tǒng)的C4.5決策樹數(shù)據(jù)挖掘算法進行了改進，提出了一種雙重熵平均決策樹算法。傳統(tǒng)的C4.5決策樹算法易出現(xiàn)無意義分枝，過度擬合等問題，針對該類問題，基于雙重熵平均決策樹算法，通過兩次對樣本子集熵平均值的計算、排序、合并處理，得到修正后的屬性信息增益，并以此作為屬性選擇的依據(jù)，從而解決了傳統(tǒng)C4.5決策樹算法可解釋性差、易產(chǎn)生碎片等問題。

關(guān)鍵詞：C4.5決策樹 算法 熵 平衡因子

中圖分類號：TP311.13 文獻標(biāo)識碼：A 文章編號：1674-098X（2014）04（c）-0040-02

數(shù)據(jù)聯(lián)機分析功能是通過對數(shù)據(jù)的處理發(fā)現(xiàn)已知要素與分析度量值之間的關(guān)系，而數(shù)據(jù)挖掘則是從大量的數(shù)據(jù)中發(fā)現(xiàn)隱藏的規(guī)律。數(shù)據(jù)挖掘包括多種挖掘算法，為了研究畢業(yè)生不同屬性與其就業(yè)狀況之間的潛在知識和規(guī)律，該文采用決策樹方法對高校畢業(yè)生數(shù)據(jù)進行分析，主要選用的是C4.5決策樹算法。

1 C4.5算法思想

決策樹的優(yōu)點在于原理簡單，發(fā)現(xiàn)知識較快；計算較為簡單，運算速度較快，對于訓(xùn)練數(shù)據(jù)的處理和待決策數(shù)據(jù)的處理效率相對較高；適用于大量數(shù)據(jù)的綜合處理，有利于挖掘數(shù)據(jù)中的重要屬性；最終得到的挖掘結(jié)果是有意見的規(guī)則，有利于用戶的理解。決策樹的主要缺點包括：對數(shù)據(jù)的時間屬性較為敏感，需要大量的預(yù)處理工作；對于非離散的連續(xù)性數(shù)據(jù)值處理效率和準(zhǔn)確率不佳；易出現(xiàn)過度擬合的情況，產(chǎn)生大量的決策分支，導(dǎo)致決策規(guī)則過于龐大。

C4.5決策樹算法是決策樹算法的主流，它繼承于傳統(tǒng)的ID3算法，繼承了其優(yōu)勢，改進了其缺點。但C4.5決策樹算法依然存在著較多的問題，其中最為突出的是過度擬合情況，以及決策準(zhǔn)確性方面的問題。針對上述問題，本課題提出了一種改進的C4.5決策樹算法，在算法構(gòu)建過程中，以樹分枝的信息熵為研究對象，將熵值較高的部分和熵值較低的部分進行合并和平衡處理，從而達到減少決策樹分支數(shù)量的目的；與此同時，考慮到C4.5算法在決策分支的確定過程中采用的是局部最優(yōu)的方法，在準(zhǔn)確性方面從整體上看有所欠缺，所以引入了了平衡因子控制算法的整體最優(yōu)化性。

C4.5決策樹算法設(shè)研究對象數(shù)據(jù)集為，該數(shù)據(jù)集中包括個類別，每一個類別表示為，選取該數(shù)據(jù)集中的一個屬性數(shù)據(jù)，則可以被劃分為多個子集，設(shè)有個取值，則被劃分的子集可表示為。設(shè)為的例子總數(shù)，而為的例子數(shù)，為的例子總數(shù)，是的所有例子中所包括的的例子數(shù)，基于上述的設(shè)定，則可以得到如下定義：

（1）類別在出現(xiàn)的概率如式（1）所示：

（1）endprint