基于神經(jīng)網(wǎng)絡(luò)的模糊決策樹改進算法

張 敏，彭紅偉，顏曉玲

大連大學(xué) 信息工程學(xué)院，遼寧 大連116622

分類問題是機器學(xué)習(xí)和數(shù)據(jù)挖掘等領(lǐng)域的熱點問題。決策樹是最基礎(chǔ)和重要的分類算法之一，其優(yōu)點在于提取的規(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)進行簡化，在主成分分析的基礎(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é)點問題。Wang等[5]提出一種極限學(xué)習(xí)機樹模型，信息熵作為決策樹節(jié)點分裂的度量方式，并將ELM模型嵌入為葉節(jié)點。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ò)的模糊決策樹改進算法（Improved algorithm of fuzzy decision tree based on neural network，F(xiàn)NDT）。對于一個數(shù)據(jù)集，先進行模糊化，建樹過程中，采用模糊熵的屬性度量方式“粗略”劃分?jǐn)?shù)據(jù)集，當(dāng)劃分到一定程度時，用神經(jīng)網(wǎng)絡(luò)代替模糊決策樹輸出類別。FNDT對識別大數(shù)據(jù)和復(fù)雜模式的分類問題能夠通過結(jié)構(gòu)自適應(yīng)地確定決策樹規(guī)模。

1 基本概念

1.1 決策樹算法

決策樹是一種歸納學(xué)習(xí)方法，它采用自頂向下的遞歸方式，從根節(jié)點開始在每個節(jié)點上按照給定的度量方式選擇屬性，然后根據(jù)相應(yīng)屬性的可能取值向下建立分支，直到訓(xùn)練集沒有剩余屬性進一步劃分樣本為止。從根節(jié)點到葉節(jié)點的一條路徑對應(yīng)著一條合取規(guī)則，整棵決策樹就對應(yīng)著一組析取表達式規(guī)則。常見的度量方式有信息增益、信息增益率、基尼指數(shù)、卡方檢驗等。決策樹算法具體步驟如下[7]。

（1）創(chuàng)建根節(jié)點N。

（2）如果訓(xùn)練集都屬于同一個類，返回N作為葉節(jié)點，并用該類標(biāo)記。

（3）如果訓(xùn)練集為空或沒有剩余屬性進一步劃分樣本，返回N為葉節(jié)點。

（4）按照一定的度量方式，選擇最佳分裂屬性并建立分支。

（5）對于剩余屬性，遞歸調(diào)用（2）~（4），選擇剩下屬性中最佳分裂屬性，在訓(xùn)練集上創(chuàng)建子節(jié)點，進一步劃分子集。

（6）進行剪枝。

1.2 神經(jīng)網(wǎng)絡(luò)

神經(jīng)網(wǎng)絡(luò)是一種運算模型，由大量神經(jīng)元之間相互連接構(gòu)成。神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)包含輸入層、隱含層、輸出層。輸入層負(fù)責(zé)接受外部數(shù)據(jù)；隱含層負(fù)責(zé)對信息進行處理，不斷調(diào)整神經(jīng)元之間的連接屬性；輸出層負(fù)責(zé)對計算結(jié)果進行輸出。在學(xué)習(xí)階段，通過調(diào)整神經(jīng)網(wǎng)絡(luò)的權(quán)值，使得預(yù)測樣本與實際樣本誤差逐漸縮小，達到最好的擬合結(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)誤差達到預(yù)設(shè)精度或?qū)W習(xí)次數(shù)大于設(shè)定最大迭代次數(shù)時，算法結(jié)束，否則，選取下一個學(xué)習(xí)樣本回到步驟（2）。

2 FNDT算法

FNDT分類器學(xué)習(xí)分為兩步：第一步從訓(xùn)練集中選擇最佳屬性作為分裂點并建樹，直到劃分能力低于真實度閾值ε停止決策樹的增長；第二步對現(xiàn)階段的決策樹利用神經(jīng)網(wǎng)絡(luò)做具有泛化能力的分類。

2.1 模糊熵

設(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)相對模糊頻率為：

2.2 隸屬函數(shù)

構(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é)點平等地使用左右子樹。沒有這種懲罰，樹往往會陷入傾斜，其中一個或多個內(nèi)部節(jié)點始終將幾乎所有概率分配給其子樹之一，并且該決策的邏輯梯度始終非常接近零。節(jié)點i的懲罰因子βi計算如下。

其中，pi(x)是從根節(jié)點到節(jié)點i的路徑概率，則節(jié)點真實度閾值ε計算公式如下：

其中，λ是懲罰強度超參數(shù)，是在訓(xùn)練之前設(shè)置的。懲罰是基于這樣的假設(shè)，即使用替代神經(jīng)網(wǎng)絡(luò)通常會更適合任何給定的分類任務(wù)，并且在實踐中確實提高了準(zhǔn)確率。

2.3 FNDT構(gòu)造算法

FNDT模型以樹狀結(jié)構(gòu)，在根節(jié)點與中間節(jié)點處，按照決策樹算法建樹；在葉節(jié)點處，選擇合適特征，嵌入神經(jīng)網(wǎng)絡(luò)實現(xiàn)樣本子集局部決策。具體構(gòu)造流程如下。

（1）輸入訓(xù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é)點的模糊熵小于真實度閾值ε時，停止決策樹的增長。

（8）在葉節(jié)點處，通過反向傳播訓(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計算如下：

2.4 FNDT優(yōu)化函數(shù)（損失函數(shù)）

給定一個訓(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ù)。

3 實驗

為驗證本文提出的基于神經(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上運行。

對于模糊決策樹而言，樹的規(guī)模在一定程度上反映樹的泛化能力，樹的規(guī)模越大，它的準(zhǔn)確率越高，從樹中提取的規(guī)則越復(fù)雜，而規(guī)則太復(fù)雜會導(dǎo)致過擬合問題。FNDT模型以樹狀結(jié)構(gòu)，在根節(jié)點與中間節(jié)點處，按照模糊決策樹算法建樹；在葉節(jié)點處，選擇合適特征，嵌入神經(jīng)網(wǎng)絡(luò)實現(xiàn)樣本子集局部決策。

3.1 各種算法準(zhǔ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é)點類型：極限學(xué)習(xí)機作為ELM-Trees葉節(jié)點；不同的線性判別式作為FT和FTLeaves葉節(jié)點；線性邏輯回歸作為LMT葉節(jié)點。從表2可以看出與FNDT相比，ELM-Trees、FT、LMT分別在6、9、4中獲得較好性能。在剩下10個數(shù)據(jù)集中FNDT準(zhǔn)確率明顯高于其他算法，說明在葉節(jié)點處嵌入神經(jīng)網(wǎng)絡(luò)可以提高算法準(zhǔn)確率。

表2 各種算法準(zhǔn)確率比較Table 2 Comparison of accuracy of various algorithms

3.2 各種算法召回率比較

表3 展 示 了 在13個 數(shù) 據(jù) 集 上ELM-Trees、FT、FTLeaves、LMT與FNDT算法召回率。召回率是覆蓋面的度量，即有多少個正例被正確分為正例。ELM-Trees是一種極限學(xué)習(xí)機樹，每個葉節(jié)點都是一個極限學(xué)習(xí)機（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é)點上略有不同。相同點是葉節(jié)點都是廣義線性模型（Generalized Linear Model，GLM）。不同點在于，F(xiàn)T樹的葉節(jié)點是高斯函數(shù)，F(xiàn)TLeaves葉節(jié)點是伯努利函數(shù)，LMT葉節(jié)點是邏輯回歸函數(shù)。從實驗結(jié)果可以看出，F(xiàn)T、FTLeaves、LMT分別在9、3、4中獲得較好性能。在剩下10個數(shù)據(jù)集中FNDT表現(xiàn)良好。與其他算法相比，召回率提高了3%~6%。FNDT算法節(jié)點分裂方式采用模糊熵，從根節(jié)點可以到不同的“葉節(jié)點”，因此正確預(yù)測正例的覆蓋面更大。

表3 各種算法召回率比較Table 3 Comparison of recall rates of various algorithms

3.3 各種算法F1值比較

表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

4 結(jié)束語

本文提出了一種基于神經(jīng)網(wǎng)絡(luò)的模糊決策樹改進算法，先利用決策樹對已經(jīng)模糊化大數(shù)據(jù)進行劃分，當(dāng)節(jié)點劃分能力小于真實度閾值ε時，將神經(jīng)網(wǎng)絡(luò)嵌入為其葉節(jié)點，并通過優(yōu)化函數(shù)，不斷訓(xùn)練神經(jīng)網(wǎng)絡(luò)達到最好效果。FNDT算法能有效解決模糊數(shù)據(jù)和不確定性數(shù)據(jù)問題；結(jié)合神經(jīng)網(wǎng)絡(luò)泛化能力的優(yōu)點，在一定程度上緩解了決策樹過擬合問題；引入真實度閾值ε這一概念，神經(jīng)網(wǎng)絡(luò)替換葉節(jié)點更加符合奧卡姆剃刀原理。實驗結(jié)果顯示，本文提出的算法在準(zhǔn)確率、召回率、F1值方面表現(xiàn)良好。如何選取最佳的優(yōu)化函數(shù)對葉節(jié)點上神經(jīng)網(wǎng)絡(luò)模型的訓(xùn)練和整個算法時間復(fù)雜度很重要。因此，設(shè)計更適合的優(yōu)化函數(shù)是今后有待研究的問題。