基于神經網絡的模糊決策樹改進算法

張 敏，彭紅偉，顏曉玲

大連大學 信息工程學院，遼寧 大連116622

分類問題是機器學習和數據挖掘等領域的熱點問題。決策樹是最基礎和重要的分類算法之一，其優點在于提取的規則容易理解和解釋。但在處理很多實際問題時，由于數據不確定性，需要通過一系列值的范圍（概率分布）來度量屬性或特征的值，使得C4.5、C5.0等傳統決策樹處理連續屬性時出現了困難。大數據中客觀存在不確定性、模糊性數據，具有精確描述特征的決策樹歸納學習算法已經不適合大數據中不精確知識的自動獲取。因此，將模糊理論引入決策樹。

對于模糊決策樹而言，樹的規模在一定程度上反映樹的泛化能力，樹的規模越大，從樹中提取的規則越復雜，而規則太復雜會導致過擬合問題[1]。在不影響分類準確率前提下，使優化后的模糊決策樹盡可能小的規模顯得十分重要。神經網絡已被證明是執行分類任務的有效學習方法，特別是當輸入高維數據，輸入與輸出關系復雜時，神經網絡表現出良好性能[2]。研究表明神經網絡模型的表示能力會隨著深度的增加呈指數增長，從而提升分類能力或預測準確率，然而這一過程會消耗大量的訓練時間。

近年來，國內外學者提出了很多關于神經網絡與決策樹的集成學習算法。Zhang等[3]提出將滿意度函數與模糊函數結合，對復雜系統進行簡化，在主成分分析的基礎上構建神經網絡預測模型。Li等[4]提出基于C4.5算法與優化的BP算法混合學習模型，以解決BP神經網絡輸入參數難以選擇與隱含層節點問題。Wang等[5]提出一種極限學習機樹模型，信息熵作為決策樹節點分裂的度量方式，并將ELM模型嵌入為葉節點。Segatori等[6]根據MapReduce編程模型設計分布式FDTs方案，使用模糊信息熵選擇決策屬性。An等[7]提出基于Kendall和諧系數的C4.5決策樹優化算法，用于解決條件屬性之間相關性的問題。但在提高準確率的同時，建立的決策樹容易過擬合。Díez等[8]提出一種決策分析網絡，適合解決非對稱問題。Yao等[9]提出鄰域粗糙集模型的特征選擇算法，由于沒有考慮數據分布不均的問題，屬性鄰域存在一定的缺陷。Li等[10]給出了廣義協調距離表示空間的屬性約簡方法和屬性特征描述。

本文提出了一種基于神經網絡的模糊決策樹改進算法（Improved algorithm of fuzzy decision tree based on neural network，FNDT）。對于一個數據集，先進行模糊化，建樹過程中，采用模糊熵的屬性度量方式“粗略”劃分數據集，當劃分到一定程度時，用神經網絡代替模糊決策樹輸出類別。FNDT對識別大數據和復雜模式的分類問題能夠通過結構自適應地確定決策樹規模。

1 基本概念

1.1 決策樹算法

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

（1）創建根節點N。

（2）如果訓練集都屬于同一個類，返回N作為葉節點，并用該類標記。

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

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

（5）對于剩余屬性，遞歸調用（2）~（4），選擇剩下屬性中最佳分裂屬性，在訓練集上創建子節點，進一步劃分子集。

（6）進行剪枝。

1.2 神經網絡

神經網絡是一種運算模型，由大量神經元之間相互連接構成。神經網絡結構包含輸入層、隱含層、輸出層。輸入層負責接受外部數據；隱含層負責對信息進行處理，不斷調整神經元之間的連接屬性；輸出層負責對計算結果進行輸出。在學習階段，通過調整神經網絡的權值，使得預測樣本與實際樣本誤差逐漸縮小，達到最好的擬合結果[8]。前饋神經網絡訓練過程具體如下。

（1）輸入訓練集( )xi,yi,i=1,2,…,n，最大迭代次數T，并初始化W,b。

（2）計算隱含層各神經元的輸入輸出。

（3）利用網絡期望輸出和實際輸出，計算損失函數。

（4）計算每一層參數偏導數，更新參數。

（5）判斷網絡誤差是否滿足要求。當誤差達到預設精度或學習次數大于設定最大迭代次數時，算法結束，否則，選取下一個學習樣本回到步驟（2）。

2 FNDT算法

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

2.1 模糊熵

設模糊信息系統是一個二元組FIS=(U,A?D)，其中U={x1,x2,…,xN}是非空有限的數據集，A={A1,A2,…,An}是模糊條件屬性，D是模糊決策屬性。對于任意的模糊條件屬性Ai(1≤i≤n)，有ki個模糊術語構成，記為FLT(Ai)={Ai1,Ai2,…,Aiki}。D是模糊決策屬性，它對應的模糊術語為FLT(D)={D1,D2,…,Dm}。每個模糊術語Aij(1≤i≤n;1≤j≤ki)或者Dl(1≤l≤m)是一個模糊集，可表示為：其中表示相應的條件隸屬度表示類別隸屬度。給定模糊信息系統FIS=(U,A?D)，對于任意的Aij∈FLT(Ai)和任意Dl∈FLT(D)，定義Aij相對于Dl的相對模糊頻率：

模糊術語Aij相對于Dl模糊頻率為定義Aij模糊熵為：

定義樣本x相對于模糊條件屬性Ai的模糊熵為：

定義x相對于模糊條件屬性Ai的模糊特征熵權為：

模糊術語Aij相對于Dl的相對模糊頻率為定義x關于Ai相對于Dl模糊頻率為：

給定模糊信息系統FIS=(U,A?D),x∈U，定義x相對于Dl加權相對模糊頻率為：

2.2 隸屬函數

構建模糊決策樹過程中，需要考慮兩個參數，顯著性水平α和真實度閾值ε。對于模糊集合Aij，用μAij表示隸屬度函數，在顯著水平α(0≤α≤1)下，模糊集Aij定義為：

較大的α可以減少訓練數據的模糊性，但α過大，訓練集可能成為空集，通常α取值范圍在(0,0.5]。其中μAij是降半梯形分布的隸屬函數。

真實度閾值ε為了避免決策樹在訓練過程中陷入困境，引入了懲罰因子，激勵每個內部節點平等地使用左右子樹。沒有這種懲罰，樹往往會陷入傾斜，其中一個或多個內部節點始終將幾乎所有概率分配給其子樹之一，并且該決策的邏輯梯度始終非常接近零。節點i的懲罰因子βi計算如下。

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

其中，λ是懲罰強度超參數，是在訓練之前設置的。懲罰是基于這樣的假設，即使用替代神經網絡通常會更適合任何給定的分類任務，并且在實踐中確實提高了準確率。

2.3 FNDT構造算法

FNDT模型以樹狀結構，在根節點與中間節點處，按照決策樹算法建樹；在葉節點處，選擇合適特征，嵌入神經網絡實現樣本子集局部決策。具體構造流程如下。

（1）輸入訓練集，并進行模糊化處理。

（2）對于每一個模糊條件屬性Ai的每一個模糊術語Aij(1≤i≤n;1≤j≤ki)，根據公式（3）計算模糊術語Aij相對于Dl的模糊頻率

（3）根據公式（4），計算模糊術語Aij的模糊熵Entropy(Aij)。對于測試樣本x，根據公式（5），計算x相對于模糊條件屬性Ai的模糊熵SEntropy(Ai,x)。

（4）根據公式（6），計算測試樣本x相對于模糊條件屬性Ai的模糊特征熵權WSEntropy(Ai,x)。

（5）對測試樣本x，根據公式（7），計算測試樣本x關于模糊條件屬性Ai(1≤i≤n)相對于Dl類模糊頻率SP(Dl,Ai,x)。

（6）對測試樣本x，根據公式（8），計算測試樣本x相對于Dl類的加權相對模糊頻率WSP(Dl,x)。

（7）根據公式（10）、（11）、（12）計算顯著性水平α和真實度閾值ε，當節點的模糊熵小于真實度閾值ε時，停止決策樹的增長。

（8）在葉節點處，通過反向傳播訓練神經網絡，并采用梯度下降方法調整參數。交叉熵損失函數lossi(x)計算如下：

其中，x表示樣本，n表示樣本總數，p表示樣本x預測為正的概率。

（9）權重w、b計算如下：

2.4 FNDT優化函數（損失函數）

給定一個訓練集Train=(xi,yi)，其中xi是樣本訓練內容，yi是樣本對應的期望內容，FNDT預測模型為f(x)。訓練的目的是盡可能使得f(x)=y。若f(x)≠y，代表預測偏差，需要一個函數定義偏差帶來的損失。設h(x)是FNDT損失函數。

3 實驗

為驗證本文提出的基于神經網絡決策樹算法，設計了13組實驗，數據集都來自UCI公共數據集。每個數據集的描述如表1所示。將每個數據集分解為訓練和測試數據集。使用Sklearn的train_test_split()函數來生成訓練數據集（占總數據的80%）和測試數據集（占總數據的20%）。為了更客觀地反映模型性能，將10次結果的平均值作為最終實驗結果。

表1 數據集描述Table 1 Data set description

本文實驗是用Python實現的，并在裝有Window 7操作系統，i5-6100 CPU和8 GB RAM的PC上運行。

對于模糊決策樹而言，樹的規模在一定程度上反映樹的泛化能力，樹的規模越大，它的準確率越高，從樹中提取的規則越復雜，而規則太復雜會導致過擬合問題。FNDT模型以樹狀結構，在根節點與中間節點處，按照模糊決策樹算法建樹；在葉節點處，選擇合適特征，嵌入神經網絡實現樣本子集局部決策。

3.1 各種算法準確率比較

表2 展示了在13個數據集上ELM-Trees、FT、FTLeaves、LMT與FNDT算法準確率。為了更客觀地反映模型性能，采用十折交叉驗證作為最終實驗結果。ELM-Trees[11]、FT[12]、FTLeaves[13]、LMT[14]樹之間主要區別是樹中節點類型：極限學習機作為ELM-Trees葉節點；不同的線性判別式作為FT和FTLeaves葉節點；線性邏輯回歸作為LMT葉節點。從表2可以看出與FNDT相比，ELM-Trees、FT、LMT分別在6、9、4中獲得較好性能。在剩下10個數據集中FNDT準確率明顯高于其他算法，說明在葉節點處嵌入神經網絡可以提高算法準確率。

表2 各種算法準確率比較Table 2 Comparison of accuracy of various algorithms

3.2 各種算法召回率比較

表3 展 示 了 在13個 數 據 集 上ELM-Trees、FT、FTLeaves、LMT與FNDT算法召回率。召回率是覆蓋面的度量，即有多少個正例被正確分為正例。ELM-Trees是一種極限學習機樹，每個葉節點都是一個極限學習機（Extreme Learning Machines，ELM），最早由Huang等于2006年提出。在ELM中，不需要反向傳播來調整權值，而是通過Moore-Penrose generalized inverse來設置權值。從實驗結果可以看出，雖然縮短了ELM網絡調整權值的時間，但算法召回率表現差。FT、FTLeaves、LMT三種算法在葉節點上略有不同。相同點是葉節點都是廣義線性模型（Generalized Linear Model，GLM）。不同點在于，FT樹的葉節點是高斯函數，FTLeaves葉節點是伯努利函數，LMT葉節點是邏輯回歸函數。從實驗結果可以看出，FT、FTLeaves、LMT分別在9、3、4中獲得較好性能。在剩下10個數據集中FNDT表現良好。與其他算法相比，召回率提高了3%~6%。FNDT算法節點分裂方式采用模糊熵，從根節點可以到不同的“葉節點”，因此正確預測正例的覆蓋面更大。

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

3.3 各種算法F1值比較

表4 展 示 了 在13個 數 據 集 上ELM-Trees、FT、FTLeaves、LMT與FNDT算法F1值。F-measure是準確率和召回率加權和平均[15]當參數a=1時，就是最常見的，其中P代表準確率，R代表召回率。從表中可以看出，FNDT在13個數據集中10個表現良好。說明本文提出的算法比較有效。

表4 各種算法F1值比較Table 4 Comparison of F1 values of various algorithms

4 結束語

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