基于屬性離散和特征度量的決策樹構(gòu)建算法

王磊，劉雨，劉志中，齊俊艷

(河南理工大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院,河南 焦作 454000)

0 引 言

決策樹算法是解決分類問題最有效的方法之一[1]。傳統(tǒng)的基于信息熵的決策樹算法如ID3[2]、C4.5[3]等，在對數(shù)據(jù)進(jìn)行分類時，存在多值屬性偏向、生成的決策樹結(jié)構(gòu)過大以及算法效率較低等問題。然而在大數(shù)據(jù)時代，數(shù)據(jù)量越來越大，場景越來越復(fù)雜，導(dǎo)致傳統(tǒng)的基于信息熵的決策樹算法難以滿足精準(zhǔn)分類的需求[4]。

近年來，隨著計算能力提升，研究人員通過不同的特征度量方法來優(yōu)化決策樹的分類性能。MU Y等[5]在決策樹算法的基礎(chǔ)上引入皮爾遜相關(guān)系數(shù)，利用新的特征度量方法確定構(gòu)建決策樹中最優(yōu)分割屬性和分割點(diǎn)，但未能考慮到屬性之間的關(guān)系；YANG S等[6]在ID3算法的基礎(chǔ)上，引入了平衡理論函數(shù)，減少不同值屬性的權(quán)重，并通過一種新的數(shù)據(jù)離散化方法對屬性進(jìn)行轉(zhuǎn)換，解決了經(jīng)典的ID3算法無法處理連續(xù)數(shù)值屬性的問題；王文霞[7]針對傳統(tǒng)C4.5算法需要多次掃描，導(dǎo)致運(yùn)算效率低的問題，提出將連續(xù)屬性的簡單分裂改進(jìn)為最優(yōu)化節(jié)點(diǎn)分裂，提高了算法效率；安葳鵬等[8]在決策樹C4.5算法的基礎(chǔ)上引入肯德爾和諧系數(shù)，用于解決條件屬性相關(guān)性和簡化計算過程，提高了算法的性能，但是在多值屬性偏向的問題上未能得到很好解決；亓常松等[9]提出條件屬性離散度的概念，在時間復(fù)雜度上相比基于信息熵的方法也有所提高，但是無法對含有連續(xù)性屬性的數(shù)據(jù)集進(jìn)行處理，所以具有一定局限性。

本文針對基于信息熵的決策樹算法存在的問題，提出一種結(jié)合聚類離散化的離散比分割方法。利用離散比理論計算取值較多的屬性在該條件屬性中的權(quán)值，在構(gòu)建決策樹的過程中取值更新時，避免多值屬性偏向問題，并可解決在傳統(tǒng)基于熵過程的決策樹算法中為得到分割節(jié)點(diǎn)，需使用大量的對數(shù)運(yùn)算從而導(dǎo)致計算復(fù)雜度高的問題。其次，針對基于信息熵決策樹算法中處理連續(xù)型數(shù)值性能不佳的問題，引進(jìn)K-means聚類算法[10]對數(shù)據(jù)進(jìn)行離散化處理，以期提高算法的精度。

1 基于信息熵的屬性選擇方法

信息熵是度量樣本集合純度最常用的一種指標(biāo)[11]。經(jīng)典的ID3算法和C4.5算法就是采用基于信息熵的方法來進(jìn)行屬性分割。

假設(shè)在樣本數(shù)據(jù)集S中，有s種類別的數(shù)據(jù)。在數(shù)據(jù)集中，可以計算出該數(shù)據(jù)中的信息熵,即

(1)

式中，pi為類別i樣本數(shù)量所占總樣本的比例。

選擇特征A作為決策樹判斷節(jié)點(diǎn)時，特征A作用后的信息熵為InfoA(S),計算式為

(2)

式中，k為樣本S被分成k個部分。

信息增益表示數(shù)據(jù)集S在特征A的作用后，其信息熵減少的值。公式為

Gain (A)=Info (S)-InfoA(S)。

(3)

Gain (A)值最大的特征就是對應(yīng)決策樹最佳屬性分割節(jié)點(diǎn)，對劃分的每個分支執(zhí)行以上操作，最后得到基于信息熵的決策樹,但是可能存在決策樹中某棵子樹重復(fù)的問題，或者是一個屬性被重復(fù)使用，這樣就會降低分類的整體效率，其次是在計算熵過程中存在大量的對數(shù)運(yùn)算，直接增加了算法的時間復(fù)雜度[12]。

2 融合離散比的屬性選擇算法

2.1 基于離散比的節(jié)點(diǎn)分割

本文提出一種離散比的決策樹節(jié)點(diǎn)分割方法，計算出各個條件屬性的離散值，將離散值作為決策樹屬性分割的標(biāo)準(zhǔn)。構(gòu)造樹中每一步所選擇的劃分屬性都應(yīng)使劃分后的子集中樣本同屬一類，也就是選擇對樣本分類一致性程度最高的條件屬性，這才有可能構(gòu)造出比較小且精度高的決策樹。

其中，具體算法模型的構(gòu)建如下。

在條件屬性Aj中屬于決策屬性類Bp的平均值為

(4)

第j個條件屬性所有值的平均值為

(5)

兩者的加權(quán)平方和為(相對重要性)

(6)

條件屬性Aj中每個值與所有值的平均值之差的平方和為(整體重要性)

(7)

則最后計算離散比值的公式為

(8)

離散比算法的具體操作如下。

Step1 計算每個結(jié)果類中條件屬性出現(xiàn)的最大頻率與該類中總記錄數(shù)的比值，記為該結(jié)果類中條件屬性的相對重要性。

Step2 計算每個結(jié)果類中的最大頻率之和與條件屬性中總記錄數(shù)的比值，記為該屬性的整體重要性。

Step3 計算結(jié)果類中條件屬性的相對重要性離散度與該屬性的整體離散度的比值。

Step4 其比值的平方根為該條件屬性的離散比值。

2.2 基于離散比的決策性能分析

若D2(λ′)-D2(λ)的取值恒小于0，則該算法能夠很好地解決多值偏向問題。

(9)

(10)

故可以對式(10)進(jìn)行約減，即

(11)

由于t1-t2<0，則可以得到D2(λ′)-D2(λ)<0恒成立，即提出的算法可以有效地解決多值屬性偏向問題。

同時，由上述推算過程可以得出,基于離散比決策樹算法的時間復(fù)雜度為O(n)，而基于信息熵算法的時間復(fù)雜度為O(n2)，基于離散比決策樹算法有效地降低了算法的時間復(fù)雜度。

2.3 基于K-means聚類的連續(xù)屬性離散化

基于離散比的屬性分割方法可以對數(shù)值型數(shù)據(jù)進(jìn)行處理，但是首先需要對這些數(shù)據(jù)進(jìn)行離散化處理[14]。在無監(jiān)督離散化中，最常用的3種方法分別是:等寬法、等頻法、K-means聚類算法[15]。其中K-means聚類方法在處理數(shù)據(jù)集時表現(xiàn)出良好的性能：(1)算法需要參數(shù)的數(shù)量少；(2)在數(shù)據(jù)分布中不需要任何先驗假設(shè)；(3)算法簡單，易實現(xiàn)；(4)聚類簇的個數(shù)可以自己確定等優(yōu)點(diǎn)[16]。離散化處理的具體過程如下。

Step1 輸入訓(xùn)練數(shù)據(jù)集D=x(1),x(2),…,x(m)，聚類簇數(shù)k，從D中隨機(jī)選擇k個樣本作為初始“簇中心”向量：μ(1),μ(2),…，μ(k)。

Step2 令Ci=φ(1≤i≤k)，當(dāng)1≤j≤m時，計算樣本x(j)與各“簇中心”向量μ(i)(1≤i≤k)的歐式距離：

(12)

根據(jù)距離最近的“簇中心”向量確定x(j)的簇標(biāo)記：λj=argmini∈{1,2,…,k}dij，將樣本x(j)劃入相應(yīng)的簇：Cλj=Cλj∪{x(j)}。

Step4 直到當(dāng)前的“簇中心”向量均未更新，結(jié)束循環(huán)。

Step5 結(jié)束離散化過程，輸出簇劃分結(jié)果：C=C1,C2,…,Ck。

聚類算法實現(xiàn)數(shù)據(jù)離散化的主要核心思想就是將同一個簇內(nèi)的屬性值做統(tǒng)一標(biāo)記，其主要步驟流程如圖1所示。

圖1 K-means聚類離散化流程圖

2.4 基于離散比的決策樹構(gòu)建

在構(gòu)建樹的過程中，選取離散比[17]作為屬性分割的標(biāo)準(zhǔn)，選取離散值最大的屬性作為根節(jié)點(diǎn)，其他節(jié)點(diǎn)根據(jù)離散比的大小依次按照構(gòu)造決策樹的規(guī)則進(jìn)行劃分，具體構(gòu)建決策樹的步驟為如下。

Step1 在數(shù)據(jù)集D中，將所有特征看作分開的節(jié)點(diǎn)。

Step2 遍歷所有的特征，遍歷當(dāng)前特征的所有分割方式，根據(jù)離散比分割方法找到最佳分割點(diǎn)，將數(shù)據(jù)劃分為不同的子節(jié)點(diǎn)，計算每個子節(jié)點(diǎn)的離散比。

Step3 在遍歷所有特征時，尋找最優(yōu)特征以及最優(yōu)分割方式，若當(dāng)前屬性離散比最大，則對該組數(shù)據(jù)進(jìn)行劃分操作。

Step4 對新的節(jié)點(diǎn)遞歸操作,步驟(2)和(3)，直到每個子節(jié)點(diǎn)集為空。

Step5 完成決策樹的構(gòu)建。

3 結(jié)果與分析

3.1 離散比方法具體實現(xiàn)

以一組天氣信息數(shù)據(jù)為例，詳細(xì)介紹算法實現(xiàn)過程，數(shù)據(jù)集中包括條件屬性“天氣”、“溫度”、“濕度”和“風(fēng)速”以及決策屬性“活動”，決策屬性“活動”中包括“取消”和“進(jìn)行”，如表1所示。

表1 樣本數(shù)據(jù)集

其中，“天氣”的好壞是決定活動是否進(jìn)行、取消的一方面因素。決策屬性為“進(jìn)行”和“取消”，條件屬性“天氣”中有3個子屬性分別為“晴”、“陰”、“雨”(表2)，天氣的離散比計算過程如下。

表2 天氣數(shù)據(jù)

則

同理，可得

D(溫度)=0.388 5，D(濕度)=0.248 0，D(風(fēng)速)=0.147 0。

根據(jù)計算結(jié)果可知，D(天氣)>D(溫度)>D(濕度)>D(風(fēng)速)，因此，選取天氣作為根節(jié)點(diǎn)，根據(jù)決策樹構(gòu)造方法生成的樹結(jié)構(gòu)如圖2所示。

圖2 決策樹結(jié)構(gòu)圖

3.2 UCI數(shù)據(jù)集實驗與分析

3.2.1 實驗數(shù)據(jù)集

為了驗證離散比算法的泛化能力及適應(yīng)性，選取UCI[18]數(shù)據(jù)集中的Energy Efficiency(E.E.),Drug Review(D.R.),EMG Gestures(E.G.),Mechanical Analysis(M.A.),Parking Birmingham(P.B.),User Knowledge (U.K.)6個公開數(shù)據(jù)集，數(shù)據(jù)集的樣本數(shù)量從768到3 571不等，同時條件屬性個數(shù)和決策屬性個數(shù)也不同，并對6個數(shù)據(jù)集中的部分連續(xù)屬性數(shù)值進(jìn)行K-means聚類離散化處理，使離散比決策樹分類模型的驗證更具說服力。數(shù)據(jù)集的具體特征信息如表3所示。

表3 UCI數(shù)據(jù)集特征信息

3.2.2 實驗評價指標(biāo)

在本文實驗中，筆者采用4種性能評價指標(biāo)：正確率(Accuracy)、精確率(Precision)、召回率(Recall)和F1(F-score)值。其中精確率衡量分類效果，召回率衡量分類效率，F(xiàn)1值用來衡量分類算法的性能[18]。各評價指標(biāo)的計算公式為

(13)

(14)

式中：TP為預(yù)測結(jié)果的真正例；FN為假反例；FP為假正例；TN為真反例。

3.2.3 實驗環(huán)境及結(jié)果分析

根據(jù)以上性能評價指標(biāo)進(jìn)行實驗，本實驗是在Pycharm平臺上進(jìn)行，采用python語言。實驗硬件環(huán)境：CPU-Intel(R)Core(TM)i5-7200U，3.40 GHz，內(nèi)存為8 GB。由于改變了基于信息熵決策樹的計算方法，所以將本文提出的決策樹改進(jìn)算法(D-decision)與兩種基于信息熵決策樹改進(jìn)算法(K_C4.5算法[8])(Id3_improved算法[6])進(jìn)行對比，檢驗D-decision算法在數(shù)據(jù)集上的分類性能，并觀察在不同數(shù)據(jù)集上各評測指標(biāo)的精度。其實驗結(jié)果如表4所示。

表4 UCI數(shù)據(jù)集的分類準(zhǔn)確率

在實驗中，通過10折交叉驗證計算分類的準(zhǔn)確率，從表4可以看出，D-decision模型的準(zhǔn)確率在各個數(shù)據(jù)集中都普遍優(yōu)于基于信息熵的分類模型，在U.K.數(shù)據(jù)集中準(zhǔn)確率可達(dá)98.5%，由此可以看出該方法的有效性。同樣算法復(fù)雜度低是算法的另一個優(yōu)點(diǎn)，為了驗證模型在時間復(fù)雜度方面的優(yōu)勢，采取模擬數(shù)據(jù)的方式，并將模擬數(shù)據(jù)容量不斷增大，檢驗3種算法在不同數(shù)據(jù)集下時間復(fù)雜度方面的特性，實驗結(jié)果如圖3所示。

圖3 3種算法運(yùn)行時間對比

實驗結(jié)果表明，在3種算法的運(yùn)行時間對比中，隨著樣本容量的增加,算法運(yùn)行時間都隨之增加，但在相同的樣本容量情況下，D-decision算法在不同數(shù)據(jù)集下的運(yùn)行時間都是最少的，ID3_improved運(yùn)行時間次之，K_C4.5運(yùn)行時間最長。由此可以證明，在基于離散比的計算方法下，減少了冗余的對數(shù)運(yùn)算，對分類效率有了明顯的提高。

通過計算數(shù)據(jù)集的精確率(P)，召回率(R)和F1數(shù)值，對提出的決策模型性能進(jìn)行分析，將改進(jìn)算法(D-decision)與基于熵運(yùn)算的ID3_improved算法和K_C4.5算法進(jìn)行比較,實驗結(jié)果如表5所示。

表5 3種算法性能比較

實驗結(jié)果表明，對于E.G.數(shù)據(jù)集，K_C4.5和D-decision算法在精確率上結(jié)果一致，ID3_improved和D-decision算法在召回率上結(jié)果一致。在其他5個數(shù)據(jù)集中，提出的D-decision算法在精確率、召回率方面均比其他2種基于信息熵的算法高。對于F1值，D-decision算法比另外2個算法都略高。由此可以表明，結(jié)合K-means聚類離散化和離散比理論的決策樹分類效果與效率有了明顯提高。

為了更直觀觀察和分析各種評測指標(biāo)，使用折線圖比較3種算法在不同特征集上的分類結(jié)果。從圖4～6可以看出,本文提出的方法，在各種評測指標(biāo)上均優(yōu)于基于熵過程的決策樹算法。

圖4 3種算法的精確率對比

圖5 3種算法的召回率對比

4 結(jié) 語

本文提出了一種新的基于離散比理論的屬性分割方法，與傳統(tǒng)需要大量對數(shù)運(yùn)算的基于信息熵決策樹算法不同，主要通過對連續(xù)性屬性進(jìn)行K-means聚類離散化及運(yùn)用離散比的方法進(jìn)行屬性分割，使選擇屬性時不僅僅只參照屬性取值出現(xiàn)的次數(shù)，避免了多值屬性偏向的問題，同時省去了計算熵過程中大量的對數(shù)運(yùn)算，明顯降低算法時間復(fù)雜度，提高運(yùn)算效率。根據(jù)此思想，通過對6個公開數(shù)據(jù)集以及與最近提出的具有代表性的決策樹改進(jìn)算法進(jìn)行實驗對比，結(jié)果表明，進(jìn)行數(shù)據(jù)分類時D-decision算法在時間復(fù)雜度和準(zhǔn)確率上都更具有優(yōu)勢。

圖6 3種算法的F1值對比

此外，改進(jìn)的決策樹算法針對某些特征不平衡數(shù)據(jù)集的擬合仍存在類別分布不均勻的問題，如何在分類擬合適應(yīng)性強(qiáng)的前提下，提高算法性能，使決策樹算法在分類上更加智能化和精確化是下一步研究目標(biāo)。