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

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

0 引 言

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

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

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

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

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

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

(1)

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

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

(2)

式中，k為樣本S被分成k個(gè)部分。

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

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

(3)

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

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

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

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

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

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

(4)

第j個(gè)條件屬性所有值的平均值為

(5)

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

(6)

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

(7)

則最后計(jì)算離散比值的公式為

(8)

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

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

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

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

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

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

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

(9)

(10)

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

(11)

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

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

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

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

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

Step2 令Ci=φ(1≤i≤k)，當(dāng)1≤j≤m時(shí)，計(jì)算樣本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é)束離散化過(guò)程，輸出簇劃分結(jié)果：C=C1,C2,…,Ck。

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

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

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

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

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

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

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

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

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

3 結(jié)果與分析

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

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

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

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

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

則

同理，可得

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

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

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

3.2 UCI數(shù)據(jù)集實(shí)驗(yàn)與分析

3.2.1 實(shí)驗(yàn)數(shù)據(jù)集

為了驗(yàn)證離散比算法的泛化能力及適應(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個(gè)公開(kāi)數(shù)據(jù)集，數(shù)據(jù)集的樣本數(shù)量從768到3 571不等，同時(shí)條件屬性個(gè)數(shù)和決策屬性個(gè)數(shù)也不同，并對(duì)6個(gè)數(shù)據(jù)集中的部分連續(xù)屬性數(shù)值進(jìn)行K-means聚類離散化處理，使離散比決策樹(shù)分類模型的驗(yàn)證更具說(shuō)服力。數(shù)據(jù)集的具體特征信息如表3所示。

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

3.2.2 實(shí)驗(yàn)評(píng)價(jià)指標(biāo)

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

(13)

(14)

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

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

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

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

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

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

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

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

表5 3種算法性能比較

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

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

圖4 3種算法的精確率對(duì)比

圖5 3種算法的召回率對(duì)比

4 結(jié) 語(yǔ)

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

圖6 3種算法的F1值對(duì)比

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