基于權(quán)重項(xiàng)的決策樹算法研究

嚴(yán)軍峰

(陜西機(jī)電職業(yè)技術(shù)學(xué)院,陜西 寶雞 721001)

0 引言

隨著大數(shù)據(jù)、人工智能等技術(shù)的發(fā)展[1],隱藏在數(shù)據(jù)背后有價(jià)值的信息越來(lái)越多。如何利用機(jī)器學(xué)習(xí)算法挖掘數(shù)據(jù)背后潛在的信息成為近年數(shù)據(jù)處理研究關(guān)注的焦點(diǎn)。數(shù)據(jù)挖掘主要是利用機(jī)器學(xué)習(xí)算法,從海量數(shù)據(jù)中挖掘、尋找有用信息或潛在模式的過(guò)程,從而幫助企業(yè)做出更加科學(xué)的判斷和決策,提高數(shù)據(jù)利用價(jià)值,最大程度利用數(shù)據(jù)服務(wù)社會(huì)發(fā)展。隨著計(jì)算機(jī)技術(shù)的不斷發(fā)展,電子商務(wù)、互聯(lián)網(wǎng)等領(lǐng)域數(shù)據(jù)呈現(xiàn)爆發(fā)式增長(zhǎng),數(shù)據(jù)存在形式也呈多元化趨勢(shì),如圖片、視頻、文本等非結(jié)構(gòu)化數(shù)據(jù)。海量增長(zhǎng)的數(shù)據(jù)也不斷促使新的技術(shù)革新,如機(jī)器學(xué)習(xí)、數(shù)據(jù)挖掘等正成為研究熱點(diǎn)。目前,機(jī)器學(xué)習(xí)、數(shù)據(jù)挖掘在教育、醫(yī)療、交通、工業(yè)、互聯(lián)網(wǎng)等領(lǐng)域得到廣泛應(yīng)用[2],如音樂推薦、智慧交通、用戶畫像、入侵檢測(cè)、智能安防等。數(shù)據(jù)挖掘有利于解決數(shù)據(jù)堆積問題,從而最大限度地發(fā)揮數(shù)據(jù)價(jià)值。決策樹作為數(shù)據(jù)挖掘領(lǐng)域的重要算法,在處理分類問題中被廣泛應(yīng)用,如癌癥診斷、天氣預(yù)測(cè)、入侵檢測(cè)等。決策樹分為分類樹和回歸樹[3-4],分別用于解決數(shù)據(jù)挖掘中的分類問題和回歸問題[5]。

1 基于權(quán)重項(xiàng)的決策樹算法

決策樹是一種基于樹結(jié)構(gòu)決策算法,樹結(jié)構(gòu)包括一個(gè)根節(jié)點(diǎn)、若干個(gè)葉子節(jié)點(diǎn)和若干個(gè)中間節(jié)點(diǎn)。根節(jié)點(diǎn)與中間節(jié)點(diǎn)之間對(duì)應(yīng)一個(gè)屬性節(jié)點(diǎn),葉子節(jié)點(diǎn)對(duì)應(yīng)結(jié)果。葉子節(jié)點(diǎn)為決策樹最終的預(yù)測(cè)分類結(jié)果。一般而言,一棵剛剛生成的決策樹葉子節(jié)點(diǎn)和分支較多。此時(shí),需要對(duì)該決策樹進(jìn)行必要的剪枝[6],以免出現(xiàn)過(guò)擬合現(xiàn)象。決策樹剪枝包含預(yù)剪枝和后剪枝2種,預(yù)剪枝通過(guò)先對(duì)每個(gè)節(jié)點(diǎn)在屬性劃分前進(jìn)行估計(jì),如果當(dāng)前節(jié)點(diǎn)屬性的劃分不能帶來(lái)該決策樹模型泛化性能的提升,則不以當(dāng)前節(jié)點(diǎn)為劃分屬性節(jié)點(diǎn),并將其標(biāo)記為葉子節(jié)點(diǎn)。后剪枝即先將整個(gè)決策樹構(gòu)造完成,然后自下而上地對(duì)所有非葉子節(jié)點(diǎn)進(jìn)行逐個(gè)考察,若將該節(jié)點(diǎn)對(duì)應(yīng)的子樹換為葉子節(jié)點(diǎn)可以帶來(lái)決策樹模型泛化能力的提升,則將該子樹替換為葉子節(jié)點(diǎn),否則不做改動(dòng)。

一棵完整決策樹生成步驟具體如下:

(1)從根節(jié)點(diǎn)開始,對(duì)存在該記錄的某一屬性進(jìn)行測(cè)試,根據(jù)結(jié)果將其分配到子節(jié)點(diǎn)。

(2)當(dāng)沿該分支可能到達(dá)葉子節(jié)點(diǎn)或者中間節(jié)點(diǎn)時(shí),使用新的測(cè)試條件遞歸重復(fù)執(zhí)行該操作。如果到達(dá)葉子節(jié)點(diǎn)或樹的深度達(dá)到指定深度則停止。

在決策樹遞歸過(guò)程中,如果所有節(jié)點(diǎn)都屬于同一個(gè)特征類別,則選擇另外一個(gè)特征作為測(cè)試條件,將記錄劃分成較小的子集。對(duì)測(cè)試條件中的每個(gè)輸出,為其創(chuàng)建一個(gè)新的子節(jié)點(diǎn),并依據(jù)測(cè)試結(jié)果將父節(jié)點(diǎn)中的記錄全部分布到子節(jié)點(diǎn),最后對(duì)每個(gè)子節(jié)點(diǎn)執(zhí)行第一步。

決策樹生成過(guò)程主要是從眾多特征中不斷選擇屬性的過(guò)程,如何選擇最優(yōu)的特征劃分屬性是決策樹生成的關(guān)鍵。對(duì)一棵決策樹而言,隨著屬性的不斷劃分,位于同一屬性節(jié)點(diǎn)下的樣本類別應(yīng)當(dāng)盡可能屬于一類,這也被稱為節(jié)點(diǎn)的“純度”[7]。“純度”越高,則認(rèn)為該屬性劃分越準(zhǔn)確。決策樹算法不僅可以處理分類問題,還可以處理回歸類問題,多棵決策樹聯(lián)合在一起被稱為隨機(jī)森林[8]。

1.1 信息熵度量計(jì)算

ID3算法采用信息熵(Information Entropy)作為度量樣本集合純度的指標(biāo),假設(shè)當(dāng)前樣本集合為D,集合中第k類樣本所占比例為pk(k=1,2,···,n),則該數(shù)據(jù)集的信息熵定義為公式為:

(1)

Ent(D)的值越小,說(shuō)明D的純度越高。

1.2 信息增益計(jì)算

假設(shè)屬性c有M個(gè)取值{c1,c2,···,cm},如果使用c屬性劃分?jǐn)?shù)據(jù)集,會(huì)產(chǎn)生m個(gè)分支節(jié)點(diǎn),其中第m個(gè)分支包括樣本在全部c屬性上的取值為cm的記錄,記為Dm。根據(jù)公式(1)計(jì)算其信息熵,并為其添加賦予權(quán)重|Dm|/|D|。由此,記錄數(shù)目越多,分支節(jié)點(diǎn)影響越大,得到屬性c的信息增益,如式(2)所示。

(2)

1.3 基于權(quán)重項(xiàng)的信息增益算法

(3)

(4)

(5)

2 實(shí)驗(yàn)分析

為驗(yàn)證基于權(quán)重項(xiàng)的決策樹算法效果,本次使用Windows 10的64位操作系統(tǒng),平臺(tái)采用Python 3作為實(shí)際開發(fā)語(yǔ)言。

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

本次使用改進(jìn)后的天氣預(yù)告數(shù)據(jù)集作為測(cè)試數(shù)據(jù),數(shù)據(jù)特征包括溫度、濕度、是否有風(fēng)等參數(shù)。數(shù)據(jù)集分布均勻,部分樣本特征缺失,符合本次實(shí)驗(yàn)要求。

2.2 實(shí)驗(yàn)評(píng)估指標(biāo)

本次采用決策樹算法常用的預(yù)測(cè)準(zhǔn)確率(Accuracy)、召回率(Recall)作為模型性能的評(píng)價(jià)指標(biāo)。準(zhǔn)確率P表示預(yù)測(cè)正確樣本數(shù)與全部樣本數(shù)的比例,計(jì)算公式如下:

(6)

召回率R表示在所有類別為陽(yáng)性的樣本中預(yù)測(cè)正確項(xiàng)的占有率,召回率越高,表示模型預(yù)測(cè)效果越好,計(jì)算公式如下:

(7)

2.3 實(shí)驗(yàn)結(jié)果分析

為了驗(yàn)證實(shí)驗(yàn)結(jié)果,本次將決策樹算法中經(jīng)典的ID3分類算法與改進(jìn)后的算法在同一數(shù)據(jù)集上從預(yù)測(cè)準(zhǔn)確率、召回率等方面進(jìn)行對(duì)比,從而驗(yàn)證算法性能。從數(shù)據(jù)中隨機(jī)多次選取10%作為驗(yàn)證集,用于實(shí)驗(yàn)結(jié)果驗(yàn)證。

為驗(yàn)證2種算法在同一數(shù)據(jù)集上效果,在實(shí)驗(yàn)過(guò)程保持算法參數(shù)、數(shù)據(jù)集大小等一致,ID3與改進(jìn)后的算法在準(zhǔn)確率上的變化影響,如圖1所示。

圖1 2種算法準(zhǔn)確率變化對(duì)比

和傳統(tǒng)算法相比,改進(jìn)后的算法在提升準(zhǔn)確率上效果較為明顯,說(shuō)明改進(jìn)后的算法在應(yīng)對(duì)特征缺失值時(shí)能很好地處理此類問題,如圖1所示。

為進(jìn)一步驗(yàn)證算法性能效果,重新隨機(jī)選取驗(yàn)證數(shù)據(jù),按照相同參數(shù)等要求,驗(yàn)證數(shù)據(jù)中正樣本的預(yù)測(cè)效果,如圖2所示。

圖2 2種算法召回率變化對(duì)比

2種算法在召回率方面表現(xiàn)差異較為明顯,改進(jìn)后的算法召回率方面表現(xiàn)更為突出,優(yōu)于傳統(tǒng)算法,如圖2所示。

3 結(jié)語(yǔ)

針對(duì)傳統(tǒng)決策樹算法不能解決樣本特征缺失的問題,本文通過(guò)在計(jì)算信息增益過(guò)程中增加權(quán)重項(xiàng)的方法提升算法對(duì)缺失值的處理能力。實(shí)驗(yàn)通過(guò)與傳統(tǒng)算法在相同條件下的不斷對(duì)比測(cè)試,證明基于增加權(quán)重項(xiàng)的方式可以有效提高決策樹算法分類效果,在一定程度上模型的泛化能力優(yōu)于現(xiàn)有算法。后續(xù)將進(jìn)一步研究算法層面的改進(jìn)方法,以解決決策樹在回歸問題上存在的缺陷。