一種新的模糊決策樹算法
——基于加權(quán)畢達(dá)哥拉斯模糊熵

劉 帥,吳 濤,2,方 越,胡皓瑋

1.安徽大學(xué) 數(shù)學(xué)科學(xué)學(xué)院,合肥 230031 2.安徽大學(xué) 計算機智能與信號處理教育部重點實驗室,合肥 230039

1 引 言

隨著決策樹在數(shù)據(jù)挖掘中的普遍運用，其在圖像識別、機器學(xué)習(xí)、數(shù)據(jù)分類等方面均取得了顯著效果。傳統(tǒng)決策樹算法如ID3算法和C4.5算法在處理不平衡數(shù)據(jù)時，分類效果不穩(wěn)定，尤其在處理更復(fù)雜的模糊數(shù)據(jù)時不能實現(xiàn)更好的分類，所以將模糊理論和決策樹相結(jié)合，模糊決策樹(Fuzzy Decision Tree, FDT)被提出。

目前很多專家提出多種FDT算法， Wang等[1]提出基于模糊規(guī)則的模糊決策樹算法，該模糊決策樹的節(jié)點能夠涉及多個特征模糊規(guī)則，證明其有更好的分類性能；翟俊海等[2]提出一種模糊粗糙決策樹算法，結(jié)合了知識的粗糙度和數(shù)據(jù)的模糊性，該算法比模糊ID3算法有更高的分類精度；Zheng等[3]將隸屬函數(shù)模型擴展到模糊隨機森林中應(yīng)用于風(fēng)險識別和預(yù)測，結(jié)果表明該方法生成的決策樹比經(jīng)典決策樹更準(zhǔn)確；Wang[4]等提出決策樹與模糊粗糙集中與屬性約簡融合的方法，該算法性能明顯優(yōu)于其他使用優(yōu)勢粗糙集的融合方法；Idris等[5]提出FID3算法,將模糊系統(tǒng)與ID3算法相結(jié)合，在乳腺癌數(shù)據(jù)集分類上有較高的準(zhǔn)確率；Li等[6]將分類問題轉(zhuǎn)化為模糊粒度空間來求解，將數(shù)據(jù)進行模糊粒度化，提出一種自適應(yīng)全局隨機聚類算法，認(rèn)為選擇擴展屬性的標(biāo)準(zhǔn)是信息增益比，結(jié)果可知有較高的準(zhǔn)確率和魯棒性；Farna等[7]提出基于卡方值的多柔性模糊決策樹，將傳統(tǒng)卡方統(tǒng)計擴展到模糊卡方統(tǒng)計用于數(shù)據(jù)分類，實驗結(jié)果表明該算法比傳統(tǒng)卡方統(tǒng)計算法有更優(yōu)的分類效果。

上述FDT算法把模糊粗糙領(lǐng)域概念與傳統(tǒng)決策樹結(jié)合構(gòu)建模糊決策樹，只是選擇分裂屬性的標(biāo)準(zhǔn)不同，每個樣本屬于節(jié)點的程度都是用隸屬度來表示，但是無法獲取樣本數(shù)據(jù)對于節(jié)點非隸屬度和猶豫度的信息，顯然這些算法在實際中不能更好地全面獲取數(shù)據(jù)信息，導(dǎo)致數(shù)據(jù)分類準(zhǔn)確率不高。針對此，基于畢達(dá)哥拉斯模糊集(Pythagorean Fuzzy Set，PFS)理論，定義一種新的加權(quán)畢達(dá)哥拉斯模糊熵，并提出一種新的加權(quán)畢達(dá)哥拉斯模糊決策樹算法(WPFDT)，將PFS與FDT相結(jié)合，推導(dǎo)了WPFDT完整的構(gòu)建過程，相較于傳統(tǒng)FDT算法，WPFDT可以同時包含樣本與節(jié)點之間的隸屬度、非隸屬度和猶豫度，可以更全面地描述節(jié)點中的模糊信息，從而提升數(shù)據(jù)分類準(zhǔn)確性，該算法在處理具有模糊信息的實際問題中有更好的分類效果。

2 預(yù)備知識

在本節(jié)中，首先給出畢達(dá)哥拉斯模糊集的基本知識，然后介紹FDT的基本知識，最后介紹如何將連續(xù)數(shù)據(jù)轉(zhuǎn)換成PFS的主要手段。

定義1[8]設(shè)X為論域，則稱A={〈x,μA(x),νA(x)〉|,0≤μA2(x)+vA2(x)≤1,x∈X},μA(x),νA(x),πA(x)∈[0,1]為PFS，其中μA(x)，νA(x)，πA(x)分別是A的隸屬度、非隸屬度、猶豫度。Ai={〈x,μAi(x),νAi(x)〉|x∈X},A1?A2(i=1,2),當(dāng)且僅當(dāng)μA1(x)≤μA2(x),νA1(x)≥νA2(x)(?x∈X)。

定義2[9-10]設(shè)Ωi?F(U)(1≤i≤m)是m維的模糊子集，如果T是FDT，則滿足以下條件：

(1)T的節(jié)點屬于F(U)；

(2) 記F(U)由所有子節(jié)點構(gòu)成，若有非葉子節(jié)點N，則存在i(1≤i≤m)，滿足Γ=Ωi∩N；

(3)T的每一個葉子節(jié)點對應(yīng)一個或多個決策分類屬性值。

其中，Ωi為分裂屬性的分裂子集，Ωi中的元素是分裂屬性中的取值。

定義3[10]假設(shè)Pi(i=1,2,…,n)是屬性Ai的模糊分裂，且有fs∈Pi(s=1,2,…,l)表示屬性Ai模糊分裂后的取值，則定義以下集合：

B≡Pi1∧Pi2…∧Pik(i=1,2，…，N；k=1,2，…，n)

(1)

通過上面的定義，可以計算模糊頻率：

P(Ai1isf1|Ai2isf2∧…∧Aikisfk)=

(2)

定義4[11]設(shè)A是X上的模糊集，{μ1,…，μn}，μi>μi+1為A的隸屬度，A的質(zhì)量分配函數(shù)mA的概率分布為

mA(Fi)=μi-μi+1

mA(F1)=1-μ2

(3)

其中,Fi={x∈Ω|μ(x)≥μi},i=1,…,n；集合F1,…,Fn是mA的焦點元素。

mA(Gi)=yi-yi+1,i=1,…,n-1
mA(Gn)=yn，mA(G1)=1-y2

其中,

Gi={x∈Ω|p(x)≥pi}

(4)

(5)

由于μ2+ν2+π2=1 ，所以有：

(6)

3 一種新的加權(quán)畢達(dá)哥拉斯模糊熵

在文獻(xiàn)[14]中，作者定義的某些畢達(dá)哥拉斯模糊熵沒有考慮猶豫度，所以當(dāng)模糊性和猶豫性都最大時取到最大值。當(dāng)μ=ν時，模糊度最大，這使得畢達(dá)哥拉斯熵值與模糊集定義的熵有矛盾，這是因為畢達(dá)哥拉斯模糊集的熵值受到模糊性和猶豫性的影響，當(dāng)模糊性越大時，熵越大；猶豫性越大時，熵也越大。針對這種情況，對文獻(xiàn)[14]定義做以下修改：即當(dāng)μ=ν=0時，熵值取最大，此時模糊性和猶豫性都最大，所以能使熵值最大。接下來在考慮猶豫性和模糊性的基礎(chǔ)上，對猶豫度和模糊度賦予權(quán)重，定義新的加權(quán)Pythagorean模糊熵。

定義7A是X上的PFS,A的模糊度為hA(x)=1-|μA2(x)-vA2(x)|，其中hA(x)∈[0,1]。

定義8 設(shè)A和B是X上的PFS，有以下條件：

(1)A為清晰集，等價于E(A)=0；

(2) ?xi∈X,μA(xi)=νA(xi)=0，等價于E(A)=1；

(3)E(A)=E(Ac)；

(4)E(A)是關(guān)于模糊度hA(x)的單調(diào)增函數(shù)，是關(guān)于猶豫度πA(x)的單調(diào)增函數(shù)。

若E滿足以上條件，稱E為PFS上的畢達(dá)哥拉斯模熵。

條件(4)的說明：當(dāng)πA(x)=πB(x)且hA(x)≤hB(x)時，E(A)≤E(B)；當(dāng)hA(x)=hB(x)且πA(x)≤πB(x)時，E(A)≤E(B)。

定義9 設(shè)論域X={x1,x2,x3,…,xn},A是X上的PFS，定義新的加權(quán)Pythagorean模糊熵如下：

(7)

其中,ω1+ω2=1,0≤ω1≤1,0≤ω2≤1。

證明

1)E(A)=0??xi∈X,ω1fA(xi)+ω2πA(xi)=0?

?xi∈X,ω1(1-|μA2(x)-vA2(x)|)+

0≤|μA2(x)-vA2(x)|≤1且0≤μA2(x)+vA2(x)≤1??xi∈X,|μA2(x)-vA2(x)|=1且μA2(x)+vA2(x)=1??xi∈X,uA(xi)=0,vA(xi)=1且uA(xi)=1,vA(xi)=0?A∈P(X)。

2)E(A)=1??xi∈X,ω1fA(xi)+ω2πA(xi)=1?

?xi∈X,ω1(1-|μA2(x)-vA2(x)|)+

?xi∈X,1-|μA2(x)-vA2(x)|=1

μA2(x)+vA2(x)=0??xi∈X,uA(xi)=vA(xi)=0

新的加權(quán)畢達(dá)哥拉斯模糊熵對模糊性和猶豫性賦予權(quán)重，符合畢達(dá)哥拉斯模糊熵的條件，同時考慮了模糊度和猶豫度對新的加權(quán)畢達(dá)哥拉斯模糊熵所起的作用，所以更符合客觀實際。

4 WPFDT的生成過程

4.1 屬性的模糊化

對于屬性的模糊處理主要有兩種，如果是清晰屬性，則直接根據(jù)語言術(shù)語語義將隸屬度標(biāo)記為0或者1；如果是連續(xù)屬性，則首先需要通過使用改進的K-means算法[14]求出各屬性的聚類中心，得出各屬性中心點就是三角隸屬度函數(shù)的參數(shù)，從而將屬性劃分為對應(yīng)數(shù)量的模糊集，然后用相應(yīng)的模糊語言術(shù)語來描述連續(xù)值屬性，最后使用上述所得的三角隸屬度函數(shù)把數(shù)據(jù)轉(zhuǎn)換成模糊數(shù)據(jù)。

4.2 分裂屬性的選擇標(biāo)準(zhǔn)

以屬性A為例計算新的加權(quán)畢達(dá)哥拉斯模糊熵的過程如下：假設(shè)屬性A有l(wèi)個模糊子集As(s=1,…,l)，兩個決策屬性C+和C-，則由式(1)得：

C+:w(C+∧As),C-:w(C-∧As),s=1,…,l

由式(2)計算每一個子節(jié)點As的相對頻率：

通過上述，計算所有條件屬性的新的加權(quán)畢達(dá)哥拉斯模糊熵，選擇熵最小的屬性為決策樹的根節(jié)點，遞歸地計算加權(quán)畢達(dá)哥拉斯模糊熵,從而選擇分裂節(jié)點。

4.3 WPFDT的剪枝處理

WPFDT在生成過程中需要限制樹的深度，如果生成的WPFDT深度太深，就會增加復(fù)雜的計算量，而且不一定有好的分類效果，因此要限制WPFDT的生長。在FDT中常用的限制樹規(guī)模的方法有預(yù)剪枝、后剪枝等，都通過控制顯著水平、真實度來控制樹的規(guī)模，顯著水平α和真實度β的定義見參考文獻(xiàn)[15]。對于WPFDT的每一個待分裂節(jié)點都可以知道其隸屬度、非隸屬度，通過比較μA(x)、νA(x)與設(shè)定閾值的大小來決定是否對節(jié)點進行分割；設(shè)定的閾值為0.96(一般β0>0.75)[9]，當(dāng)μA(x)、νA(x)有一個值大于閾值時，則停止對該節(jié)點進行分割，當(dāng)μA(x)、νA(x)都小于閾值時，則繼續(xù)對該節(jié)點進行分割。

4.4 模糊規(guī)則抽取和分類預(yù)測

生成的WPFDT轉(zhuǎn)換成模糊規(guī)則的過程如下：如果有n個葉子節(jié)點就會有n條模糊分類規(guī)則，n個模糊規(guī)則，WPFDT在抽取規(guī)則時不僅會得出葉子節(jié)點的分類結(jié)果，也會得出屬于不同決策屬性的μ、ν，同時也會得出模糊分類規(guī)則的猶豫度。WPFDT在預(yù)測過程中會有多個模糊規(guī)則可以適合匹配，選擇所有隸屬度中最大值的模糊規(guī)則結(jié)果作為預(yù)測結(jié)果，并得出規(guī)則的μ、ν、π。

5 WPFDT算法流程

步驟1 輸入訓(xùn)練集，運用改進的K-means算法[14]和三角隸屬度函數(shù)把數(shù)據(jù)轉(zhuǎn)換成模糊數(shù)據(jù)。

步驟2 對于每一個Ai的每一個模糊子集值A(chǔ)ij(1≤i≤n;1≤j≤ki),根據(jù)式(1)和式(2)計算Aij相對于C+或C-的模糊頻率pij。

步驟4 根據(jù)式(6)得每個子節(jié)點Aij由以下畢達(dá)哥拉斯模糊集描述：{Aij,μ(Aij),υ(Aij),π(Aij)}。

步驟5 根據(jù)式(7)計算每一個屬性Ai的加權(quán)畢達(dá)哥拉斯模糊熵E(Ai)，選取最小的E(Ai)作為根節(jié)點。

步驟6 設(shè)定閾值β0，當(dāng)每個子節(jié)點μ(Aij)、ν(Aij)都小于β0時，繼續(xù)對該節(jié)點Ai劃分，否則標(biāo)記成為葉子節(jié)點。

步驟7 在根節(jié)點下遞歸選取最小的加權(quán)畢達(dá)哥拉斯模糊熵對應(yīng)的屬性作為分裂節(jié)點，直至最終生成WPFDT模型。

6 WPFDT實例分析

假設(shè)有A和B兩個條件屬性，決策屬性為C，其中A和B分別有兩個條件屬性A1,A2和B1,B2，C有C+和C-兩個決策屬性，假設(shè)有4個樣本隸屬度數(shù)據(jù)如下：μ(A1)=(1,1,0.59,0.01),μ(A2)=(0,0,0.41,0.99),μ(B1)=(1,0,1,0.88),μ(B2)=(0,1,0,0.12),μ(C1)=(0,1,0,1),μ(C2)=(1,0,1,0)。

接下來在屬性B1的條件下計算模糊子集A1、A2的新的加權(quán)Pythagorean模糊熵。按照上面步驟，計算A1、A2分別相對于B1的相對頻率，用式(4)和式(5)計算屬性A在B1這個條件屬性下支持C+的最大可能性。由式(7)可得μ(A1)=0,ν(A1)=0.98,π(A1)=0.199；μ(A2)=0.59,ν(A2)=0,π(A2)=0.807，由于只有兩個屬性，所以直接確定葉子節(jié)點，最終生成的WPFDT如圖1所示。

圖1 加權(quán)畢達(dá)哥拉斯模糊決策樹Fig.1 Weighted Pythagorean fuzzy decision tree

由圖1可知，規(guī)則1：如果B是B1并且A是A1，則分類為C+，規(guī)則的μ、ν、π分別為0.59、0、0.807。規(guī)則2：如果B是B1并且A是A2，則分類為C-，規(guī)則的μ、ν、π分別為0、0.98、0.199。規(guī)則3：如果B是B2，則分類為C+，規(guī)則的μ、ν、π分別為1、1、0。

接下來用μ(A1)=0.37,μ(A2)=0.63,μ(B1)=1,μ(B2)=0進行預(yù)測。與規(guī)則1適合的隸屬度min{1.00,0.63}=0.63，該樣本屬于C+類的可能性為0.59，屬于C-類的可能性為0，猶豫度為0.807。與規(guī)則2適合的隸屬度為min{1.00,0.37}=0.37，該樣本屬于C+類的可能性為0，屬于C-類的可能性為0.98，猶豫度為0.199。與規(guī)則3適合的隸屬度為min{0.00}=0,表示該樣本屬于C+類的可能性為1，屬于C-類的可能性為0,猶豫度為0。最終選擇與所有規(guī)則適合最高的條件隸屬度結(jié)果作為分類結(jié)果，即選擇規(guī)則1，分類為C+。

7 WPFDT實驗分析

7.1 分類準(zhǔn)確率對比

為進一步說明加權(quán)畢達(dá)哥拉斯模糊決策樹的優(yōu)越性，選取UCI上的Haberman、 Breast Cancer、Parkinson 3個醫(yī)學(xué)數(shù)據(jù)集，將其與3種傳統(tǒng)決策樹算法(CART算法、C4.5算法、模糊ID3算法)進行實驗比較，得到的分類準(zhǔn)確率如表1，并得出WPFDT算法 的準(zhǔn)確率、精確率、召回率、F1值如表2所示。

表1 分類準(zhǔn)確率的對比

表2 WPFDT算法評價指標(biāo)

由表1可知:本文的WPFDT算法在3個醫(yī)學(xué)數(shù)據(jù)集上，分類準(zhǔn)確率是最高的，表明對分裂節(jié)點過程中獲取的模糊信息越全面，分類準(zhǔn)確率越高。由表2知：WPFDT算法在較高的分類準(zhǔn)確率情況下，有較高的召回率和精確率。

7.2 規(guī)則數(shù)量比較

葉子節(jié)點的數(shù)量越多，抽取規(guī)則的數(shù)量就越多，在分類預(yù)測時匹配規(guī)則就越多，得出的模糊決策樹規(guī)模就越大，分類的準(zhǔn)確性也越高，但當(dāng)規(guī)則數(shù)量過多的時候，不僅帶來過多的復(fù)雜計算，而且容易出現(xiàn)過擬合。下面比較4種算法在3個醫(yī)學(xué)數(shù)據(jù)集(Haberman、Breast Cancer、Parkinson)上得出模糊規(guī)則的數(shù)量，得到的結(jié)果如表3所示。

表3 IF THEN規(guī)則的數(shù)量Table 3 Number of IF THEN rules

由表3可知：在Haberman、 Breast Cancer、Parkinson 3個醫(yī)學(xué)數(shù)據(jù)集上，本文的WPFDT算法得出的規(guī)則數(shù)更加適中，說明生成的模糊決策樹更容易理解，用較合適的規(guī)則就能進行更好地分類預(yù)測，分類性能更好。

8 結(jié)論與展望

提出一種新的加權(quán)畢達(dá)哥拉斯模糊決策樹算法(WPFDT)。首先，使用改進的K-means聚類算法得到連續(xù)屬性聚類中心，并結(jié)合三角模糊數(shù)對連續(xù)數(shù)據(jù)進行模糊處理；其次，定義并計算每一個屬性的加權(quán)畢達(dá)哥拉斯模糊熵,選擇加權(quán)畢達(dá)哥拉斯模糊熵最小的屬性作為決策樹根節(jié)點,在根節(jié)點下遞歸選擇模糊熵最小的屬性作為分裂節(jié)點，直至生成WPFDT模型，同時通過閾值控制樹的規(guī)模，得到從根節(jié)點到葉子節(jié)點路徑的模糊規(guī)則以及模糊規(guī)則的μ、ν、π，并完成預(yù)測分類；最后，將UCI上的數(shù)據(jù)集與3種傳統(tǒng)決策樹算法進行實驗比較，結(jié)果表明：WPFDT在分類精度和樹大小方面都優(yōu)于其他決策樹。在進一步工作中，將結(jié)合卷積神經(jīng)網(wǎng)絡(luò)[16]，模糊邏輯優(yōu)化加權(quán)畢達(dá)哥拉斯模糊熵，生成具有更優(yōu)分類性能的模糊決策樹。