張 敏,彭紅偉,顏曉玲
大連大學(xué) 信息工程學(xué)院,遼寧 大連116622
分類問題是機(jī)器學(xué)習(xí)和數(shù)據(jù)挖掘等領(lǐng)域的熱點(diǎn)問題。決策樹是最基礎(chǔ)和重要的分類算法之一,其優(yōu)點(diǎn)在于提取的規(guī)則容易理解和解釋。但在處理很多實際問題時,由于數(shù)據(jù)不確定性,需要通過一系列值的范圍(概率分布)來度量屬性或特征的值,使得C4.5、C5.0等傳統(tǒng)決策樹處理連續(xù)屬性時出現(xiàn)了困難。大數(shù)據(jù)中客觀存在不確定性、模糊性數(shù)據(jù),具有精確描述特征的決策樹歸納學(xué)習(xí)算法已經(jīng)不適合大數(shù)據(jù)中不精確知識的自動獲取。因此,將模糊理論引入決策樹。
對于模糊決策樹而言,樹的規(guī)模在一定程度上反映樹的泛化能力,樹的規(guī)模越大,從樹中提取的規(guī)則越復(fù)雜,而規(guī)則太復(fù)雜會導(dǎo)致過擬合問題[1]。在不影響分類準(zhǔn)確率前提下,使優(yōu)化后的模糊決策樹盡可能小的規(guī)模顯得十分重要。神經(jīng)網(wǎng)絡(luò)已被證明是執(zhí)行分類任務(wù)的有效學(xué)習(xí)方法,特別是當(dāng)輸入高維數(shù)據(jù),輸入與輸出關(guān)系復(fù)雜時,神經(jīng)網(wǎng)絡(luò)表現(xiàn)出良好性能[2]。研究表明神經(jīng)網(wǎng)絡(luò)模型的表示能力會隨著深度的增加呈指數(shù)增長,從而提升分類能力或預(yù)測準(zhǔn)確率,然而這一過程會消耗大量的訓(xùn)練時間。
近年來,國內(nèi)外學(xué)者提出了很多關(guān)于神經(jīng)網(wǎng)絡(luò)與決策樹的集成學(xué)習(xí)算法。Zhang等[3]提出將滿意度函數(shù)與模糊函數(shù)結(jié)合,對復(fù)雜系統(tǒng)進(jìn)行簡化,在主成分分析的基礎(chǔ)上構(gòu)建神經(jīng)網(wǎng)絡(luò)預(yù)測模型。Li等[4]提出基于C4.5算法與優(yōu)化的BP算法混合學(xué)習(xí)模型,以解決BP神經(jīng)網(wǎng)絡(luò)輸入?yún)?shù)難以選擇與隱含層節(jié)點(diǎn)問題。Wang等[5]提出一種極限學(xué)習(xí)機(jī)樹模型,信息熵作為決策樹節(jié)點(diǎn)分裂的度量方式,并將ELM模型嵌入為葉節(jié)點(diǎn)。Segatori等[6]根據(jù)MapReduce編程模型設(shè)計分布式FDTs方案,使用模糊信息熵選擇決策屬性。An等[7]提出基于Kendall和諧系數(shù)的C4.5決策樹優(yōu)化算法,用于解決條件屬性之間相關(guān)性的問題。但在提高準(zhǔn)確率的同時,建立的決策樹容易過擬合。Díez等[8]提出一種決策分析網(wǎng)絡(luò),適合解決非對稱問題。Yao等[9]提出鄰域粗糙集模型的特征選擇算法,由于沒有考慮數(shù)據(jù)分布不均的問題,屬性鄰域存在一定的缺陷。Li等[10]給出了廣義協(xié)調(diào)距離表示空間的屬性約簡方法和屬性特征描述。
本文提出了一種基于神經(jīng)網(wǎng)絡(luò)的模糊決策樹改進(jìn)算法(Improved algorithm of fuzzy decision tree based on neural network,F(xiàn)NDT)。對于一個數(shù)據(jù)集,先進(jìn)行模糊化,建樹過程中,采用模糊熵的屬性度量方式“粗略”劃分?jǐn)?shù)據(jù)集,當(dāng)劃分到一定程度時,用神經(jīng)網(wǎng)絡(luò)代替模糊決策樹輸出類別。FNDT對識別大數(shù)據(jù)和復(fù)雜模式的分類問題能夠通過結(jié)構(gòu)自適應(yīng)地確定決策樹規(guī)模。
決策樹是一種歸納學(xué)習(xí)方法,它采用自頂向下的遞歸方式,從根節(jié)點(diǎn)開始在每個節(jié)點(diǎn)上按照給定的度量方式選擇屬性,然后根據(jù)相應(yīng)屬性的可能取值向下建立分支,直到訓(xùn)練集沒有剩余屬性進(jìn)一步劃分樣本為止。從根節(jié)點(diǎn)到葉節(jié)點(diǎn)的一條路徑對應(yīng)著一條合取規(guī)則,整棵決策樹就對應(yīng)著一組析取表達(dá)式規(guī)則。常見的度量方式有信息增益、信息增益率、基尼指數(shù)、卡方檢驗等。決策樹算法具體步驟如下[7]。
(1)創(chuàng)建根節(jié)點(diǎn)N。
(2)如果訓(xùn)練集都屬于同一個類,返回N作為葉節(jié)點(diǎn),并用該類標(biāo)記。
(3)如果訓(xùn)練集為空或沒有剩余屬性進(jìn)一步劃分樣本,返回N為葉節(jié)點(diǎn)。
(4)按照一定的度量方式,選擇最佳分裂屬性并建立分支。
(5)對于剩余屬性,遞歸調(diào)用(2)~(4),選擇剩下屬性中最佳分裂屬性,在訓(xùn)練集上創(chuàng)建子節(jié)點(diǎn),進(jìn)一步劃分子集。
(6)進(jìn)行剪枝。
神經(jīng)網(wǎng)絡(luò)是一種運(yùn)算模型,由大量神經(jīng)元之間相互連接構(gòu)成。神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)包含輸入層、隱含層、輸出層。輸入層負(fù)責(zé)接受外部數(shù)據(jù);隱含層負(fù)責(zé)對信息進(jìn)行處理,不斷調(diào)整神經(jīng)元之間的連接屬性;輸出層負(fù)責(zé)對計算結(jié)果進(jìn)行輸出。在學(xué)習(xí)階段,通過調(diào)整神經(jīng)網(wǎng)絡(luò)的權(quán)值,使得預(yù)測樣本與實際樣本誤差逐漸縮小,達(dá)到最好的擬合結(jié)果[8]。前饋神經(jīng)網(wǎng)絡(luò)訓(xùn)練過程具體如下。
(1)輸入訓(xùn)練集( )xi,yi,i=1,2,…,n,最大迭代次數(shù)T,并初始化W,b。
(2)計算隱含層各神經(jīng)元的輸入輸出。
(3)利用網(wǎng)絡(luò)期望輸出和實際輸出,計算損失函數(shù)。
(4)計算每一層參數(shù)偏導(dǎo)數(shù),更新參數(shù)。
(5)判斷網(wǎng)絡(luò)誤差是否滿足要求。當(dāng)誤差達(dá)到預(yù)設(shè)精度或?qū)W習(xí)次數(shù)大于設(shè)定最大迭代次數(shù)時,算法結(jié)束,否則,選取下一個學(xué)習(xí)樣本回到步驟(2)。
FNDT分類器學(xué)習(xí)分為兩步:第一步從訓(xùn)練集中選擇最佳屬性作為分裂點(diǎn)并建樹,直到劃分能力低于真實度閾值ε停止決策樹的增長;第二步對現(xiàn)階段的決策樹利用神經(jīng)網(wǎng)絡(luò)做具有泛化能力的分類。
設(shè)模糊信息系統(tǒng)是一個二元組FIS=(U,A?D),其中U={x1,x2,…,xN}是非空有限的數(shù)據(jù)集,A={A1,A2,…,An}是模糊條件屬性,D是模糊決策屬性。對于任意的模糊條件屬性Ai(1≤i≤n),有ki個模糊術(shù)語構(gòu)成,記為FLT(Ai)={Ai1,Ai2,…,Aiki}。D是模糊決策屬性,它對應(yīng)的模糊術(shù)語為FLT(D)={D1,D2,…,Dm}。每個模糊術(shù)語Aij(1≤i≤n;1≤j≤ki)或者Dl(1≤l≤m)是一個模糊集,可表示為:其中表示相應(yīng)的條件隸屬度表示類別隸屬度。給定模糊信息系統(tǒng)FIS=(U,A?D),對于任意的Aij∈FLT(Ai)和任意Dl∈FLT(D),定義Aij相對于Dl的相對模糊頻率:
模糊術(shù)語Aij相對于Dl模糊頻率為定義Aij模糊熵為:
定義樣本x相對于模糊條件屬性Ai的模糊熵為:
定義x相對于模糊條件屬性Ai的模糊特征熵權(quán)為:
模糊術(shù)語Aij相對于Dl的相對模糊頻率為定義x關(guān)于Ai相對于Dl模糊頻率為:
給定模糊信息系統(tǒng)FIS=(U,A?D),x∈U,定義x相對于Dl加權(quán)相對模糊頻率為:
構(gòu)建模糊決策樹過程中,需要考慮兩個參數(shù),顯著性水平α和真實度閾值ε。對于模糊集合Aij,用μAij表示隸屬度函數(shù),在顯著水平α(0≤α≤1)下,模糊集Aij定義為:
較大的α可以減少訓(xùn)練數(shù)據(jù)的模糊性,但α過大,訓(xùn)練集可能成為空集,通常α取值范圍在(0,0.5]。其中μAij是降半梯形分布的隸屬函數(shù)。
真實度閾值ε為了避免決策樹在訓(xùn)練過程中陷入困境,引入了懲罰因子,激勵每個內(nèi)部節(jié)點(diǎn)平等地使用左右子樹。沒有這種懲罰,樹往往會陷入傾斜,其中一個或多個內(nèi)部節(jié)點(diǎn)始終將幾乎所有概率分配給其子樹之一,并且該決策的邏輯梯度始終非常接近零。節(jié)點(diǎn)i的懲罰因子βi計算如下。
其中,pi(x)是從根節(jié)點(diǎn)到節(jié)點(diǎn)i的路徑概率,則節(jié)點(diǎn)真實度閾值ε計算公式如下:
其中,λ是懲罰強(qiáng)度超參數(shù),是在訓(xùn)練之前設(shè)置的。懲罰是基于這樣的假設(shè),即使用替代神經(jīng)網(wǎng)絡(luò)通常會更適合任何給定的分類任務(wù),并且在實踐中確實提高了準(zhǔn)確率。
FNDT模型以樹狀結(jié)構(gòu),在根節(jié)點(diǎn)與中間節(jié)點(diǎn)處,按照決策樹算法建樹;在葉節(jié)點(diǎn)處,選擇合適特征,嵌入神經(jīng)網(wǎng)絡(luò)實現(xiàn)樣本子集局部決策。具體構(gòu)造流程如下。
(1)輸入訓(xùn)練集,并進(jìn)行模糊化處理。
(2)對于每一個模糊條件屬性Ai的每一個模糊術(shù)語Aij(1≤i≤n;1≤j≤ki),根據(jù)公式(3)計算模糊術(shù)語Aij相對于Dl的模糊頻率
(3)根據(jù)公式(4),計算模糊術(shù)語Aij的模糊熵Entropy(Aij)。對于測試樣本x,根據(jù)公式(5),計算x相對于模糊條件屬性Ai的模糊熵SEntropy(Ai,x)。
(4)根據(jù)公式(6),計算測試樣本x相對于模糊條件屬性Ai的模糊特征熵權(quán)WSEntropy(Ai,x)。
(5)對測試樣本x,根據(jù)公式(7),計算測試樣本x關(guān)于模糊條件屬性Ai(1≤i≤n)相對于Dl類模糊頻率SP(Dl,Ai,x)。
(6)對測試樣本x,根據(jù)公式(8),計算測試樣本x相對于Dl類的加權(quán)相對模糊頻率WSP(Dl,x)。
(7)根據(jù)公式(10)、(11)、(12)計算顯著性水平α和真實度閾值ε,當(dāng)節(jié)點(diǎn)的模糊熵小于真實度閾值ε時,停止決策樹的增長。
(8)在葉節(jié)點(diǎn)處,通過反向傳播訓(xùn)練神經(jīng)網(wǎng)絡(luò),并采用梯度下降方法調(diào)整參數(shù)。交叉熵?fù)p失函數(shù)lossi(x)計算如下:
其中,x表示樣本,n表示樣本總數(shù),p表示樣本x預(yù)測為正的概率。
(9)權(quán)重w、b計算如下:
給定一個訓(xùn)練集Train=(xi,yi),其中xi是樣本訓(xùn)練內(nèi)容,yi是樣本對應(yīng)的期望內(nèi)容,F(xiàn)NDT預(yù)測模型為f(x)。訓(xùn)練的目的是盡可能使得f(x)=y。若f(x)≠y,代表預(yù)測偏差,需要一個函數(shù)定義偏差帶來的損失。設(shè)h(x)是FNDT損失函數(shù)。
為驗證本文提出的基于神經(jīng)網(wǎng)絡(luò)決策樹算法,設(shè)計了13組實驗,數(shù)據(jù)集都來自UCI公共數(shù)據(jù)集。每個數(shù)據(jù)集的描述如表1所示。將每個數(shù)據(jù)集分解為訓(xùn)練和測試數(shù)據(jù)集。使用Sklearn的train_test_split()函數(shù)來生成訓(xùn)練數(shù)據(jù)集(占總數(shù)據(jù)的80%)和測試數(shù)據(jù)集(占總數(shù)據(jù)的20%)。為了更客觀地反映模型性能,將10次結(jié)果的平均值作為最終實驗結(jié)果。
表1 數(shù)據(jù)集描述Table 1 Data set description
本文實驗是用Python實現(xiàn)的,并在裝有Window 7操作系統(tǒng),i5-6100 CPU和8 GB RAM的PC上運(yùn)行。
對于模糊決策樹而言,樹的規(guī)模在一定程度上反映樹的泛化能力,樹的規(guī)模越大,它的準(zhǔn)確率越高,從樹中提取的規(guī)則越復(fù)雜,而規(guī)則太復(fù)雜會導(dǎo)致過擬合問題。FNDT模型以樹狀結(jié)構(gòu),在根節(jié)點(diǎn)與中間節(jié)點(diǎn)處,按照模糊決策樹算法建樹;在葉節(jié)點(diǎn)處,選擇合適特征,嵌入神經(jīng)網(wǎng)絡(luò)實現(xiàn)樣本子集局部決策。
表2 展示了在13個數(shù)據(jù)集上ELM-Trees、FT、FTLeaves、LMT與FNDT算法準(zhǔn)確率。為了更客觀地反映模型性能,采用十折交叉驗證作為最終實驗結(jié)果。ELM-Trees[11]、FT[12]、FTLeaves[13]、LMT[14]樹之間主要區(qū)別是樹中節(jié)點(diǎn)類型:極限學(xué)習(xí)機(jī)作為ELM-Trees葉節(jié)點(diǎn);不同的線性判別式作為FT和FTLeaves葉節(jié)點(diǎn);線性邏輯回歸作為LMT葉節(jié)點(diǎn)。從表2可以看出與FNDT相比,ELM-Trees、FT、LMT分別在6、9、4中獲得較好性能。在剩下10個數(shù)據(jù)集中FNDT準(zhǔn)確率明顯高于其他算法,說明在葉節(jié)點(diǎn)處嵌入神經(jīng)網(wǎng)絡(luò)可以提高算法準(zhǔn)確率。
表2 各種算法準(zhǔn)確率比較Table 2 Comparison of accuracy of various algorithms
表3 展 示 了 在13個 數(shù) 據(jù) 集 上ELM-Trees、FT、FTLeaves、LMT與FNDT算法召回率。召回率是覆蓋面的度量,即有多少個正例被正確分為正例。ELM-Trees是一種極限學(xué)習(xí)機(jī)樹,每個葉節(jié)點(diǎn)都是一個極限學(xué)習(xí)機(jī)(Extreme Learning Machines,ELM),最早由Huang等于2006年提出。在ELM中,不需要反向傳播來調(diào)整權(quán)值,而是通過Moore-Penrose generalized inverse來設(shè)置權(quán)值。從實驗結(jié)果可以看出,雖然縮短了ELM網(wǎng)絡(luò)調(diào)整權(quán)值的時間,但算法召回率表現(xiàn)差。FT、FTLeaves、LMT三種算法在葉節(jié)點(diǎn)上略有不同。相同點(diǎn)是葉節(jié)點(diǎn)都是廣義線性模型(Generalized Linear Model,GLM)。不同點(diǎn)在于,F(xiàn)T樹的葉節(jié)點(diǎn)是高斯函數(shù),F(xiàn)TLeaves葉節(jié)點(diǎn)是伯努利函數(shù),LMT葉節(jié)點(diǎn)是邏輯回歸函數(shù)。從實驗結(jié)果可以看出,F(xiàn)T、FTLeaves、LMT分別在9、3、4中獲得較好性能。在剩下10個數(shù)據(jù)集中FNDT表現(xiàn)良好。與其他算法相比,召回率提高了3%~6%。FNDT算法節(jié)點(diǎn)分裂方式采用模糊熵,從根節(jié)點(diǎn)可以到不同的“葉節(jié)點(diǎn)”,因此正確預(yù)測正例的覆蓋面更大。
表3 各種算法召回率比較Table 3 Comparison of recall rates of various algorithms
表4 展 示 了 在13個 數(shù) 據(jù) 集 上ELM-Trees、FT、FTLeaves、LMT與FNDT算法F1值。F-measure是準(zhǔn)確率和召回率加權(quán)和平均[15]當(dāng)參數(shù)a=1時,就是最常見的,其中P代表準(zhǔn)確率,R代表召回率。從表中可以看出,F(xiàn)NDT在13個數(shù)據(jù)集中10個表現(xiàn)良好。說明本文提出的算法比較有效。
表4 各種算法F1值比較Table 4 Comparison of F1 values of various algorithms
本文提出了一種基于神經(jīng)網(wǎng)絡(luò)的模糊決策樹改進(jìn)算法,先利用決策樹對已經(jīng)模糊化大數(shù)據(jù)進(jìn)行劃分,當(dāng)節(jié)點(diǎn)劃分能力小于真實度閾值ε時,將神經(jīng)網(wǎng)絡(luò)嵌入為其葉節(jié)點(diǎn),并通過優(yōu)化函數(shù),不斷訓(xùn)練神經(jīng)網(wǎng)絡(luò)達(dá)到最好效果。FNDT算法能有效解決模糊數(shù)據(jù)和不確定性數(shù)據(jù)問題;結(jié)合神經(jīng)網(wǎng)絡(luò)泛化能力的優(yōu)點(diǎn),在一定程度上緩解了決策樹過擬合問題;引入真實度閾值ε這一概念,神經(jīng)網(wǎng)絡(luò)替換葉節(jié)點(diǎn)更加符合奧卡姆剃刀原理。實驗結(jié)果顯示,本文提出的算法在準(zhǔn)確率、召回率、F1值方面表現(xiàn)良好。如何選取最佳的優(yōu)化函數(shù)對葉節(jié)點(diǎn)上神經(jīng)網(wǎng)絡(luò)模型的訓(xùn)練和整個算法時間復(fù)雜度很重要。因此,設(shè)計更適合的優(yōu)化函數(shù)是今后有待研究的問題。