基于模糊度的決策樹生成算法

羅秋瑾

(云南財(cái)經(jīng)大學(xué) 統(tǒng)計(jì)與數(shù)學(xué)學(xué)院,云南 昆明 650221)

由于在實(shí)際問題中充斥著大量的不確定性，使用傳統(tǒng)的決策樹難以從不確定性問題中獲取到有用的信息，所以需要對(duì)傳統(tǒng)的決策樹進(jìn)行推廣，推廣以后得到的模糊決策樹，主要用于處理這些不精確的信息.

由ID3算法擴(kuò)展得到的Fuzzy-ID3算法[1]是模糊決策樹歸納算法的典型代表，它主要是依據(jù)平均模糊分類熵選擇擴(kuò)展屬性，利用模糊置信度作為判斷模糊決策樹葉子結(jié)點(diǎn)的終止條件．除此以外，常用的模糊決策樹算法還有Yuan[2]和Yeung等[3]提出的啟發(fā)式算法，這些算法都有一個(gè)共同的特點(diǎn)就是需要對(duì)條件屬性值進(jìn)行模糊化處理，而任何形式的模糊化都不可避免地會(huì)造成信息的丟失，從而造成信息的失真.此外，依據(jù)模糊依賴度選擇擴(kuò)展屬性，也是比較常用的一種啟發(fā)式算法[4-5].

但是，由于粗糙模糊依賴函數(shù)不是單調(diào)地，也就是說較少的條件屬性也有可能計(jì)算出較大的依賴函數(shù)值，從而導(dǎo)致算法有不收斂的可能[5]，基于上述問題，提出了一種改進(jìn)的模糊依賴函數(shù)作為啟發(fā)式選擇擴(kuò)展屬性，再利用模糊粗糙度作為葉子結(jié)點(diǎn)的終止條件.從而可以使得該歸納算法具備很好的收斂性.

1 基本概念

1982年波蘭科學(xué)院院士Pawlak教授[6-7]提出的粗糙集理論是處理知識(shí)中的不確定性的有力的工具.模糊粗糙集理論和方法是由D.Dubois和H.Prade在1990年提出的數(shù)學(xué)理論，用于處理數(shù)據(jù)類型中存在的不一致性的.

模糊粗糙集的特點(diǎn)是將粗糙集和模糊集同時(shí)進(jìn)行了集成擴(kuò)展，使得它既可以處理數(shù)據(jù)中的模糊性又可以處理數(shù)據(jù)中的粗糙性.發(fā)展到現(xiàn)在，它已經(jīng)基本建立起了一個(gè)完備的理論框架，在理論方面和應(yīng)用方面都取得了相當(dāng)豐富的研究成果，在數(shù)據(jù)挖掘等領(lǐng)域有著較為廣泛的應(yīng)用[8-9].

定義2給定模糊信息系統(tǒng)FIS=(U,A∪C,V,f)，P為定義在論域U上的模糊等價(jià)關(guān)系，X是定義在U上的模糊集.對(duì)于給定的x∈X，X的P模糊下近似和X的P模糊上近似分別定義為：

(1)

(2)

定義3給定模糊信息系統(tǒng)FIS=(U,A∪C,V,f)，P∈A，Q∈C. 對(duì)于給定的對(duì)象x∈X，定義對(duì)象x屬于模糊正域的隸屬度定義為[11]：

(3)

定義4給定模糊信息系統(tǒng)FIS=(U,A∪C,V,f)，P∈A，Q∈C.模糊條件屬性P相對(duì)于模糊決策屬性Q的依賴度定義為

(4)

其中，|U|表示論域中包含對(duì)象的個(gè)數(shù).

2 改進(jìn)的模糊決策樹歸納算法

通常模糊決策樹的生成主要包含2個(gè)步驟，一個(gè)是擴(kuò)展屬性的選擇，以此為標(biāo)準(zhǔn)做啟發(fā)式算法，另一個(gè)則是樹的終止條件，否則會(huì)造成過度擬合的情況，通常歸納算法都是圍繞這兩個(gè)問題展開，其中以擴(kuò)展屬性的選擇這一步最為重要，也就成為了算法的核心.

2.1 對(duì)原算法的一些分析

文獻(xiàn)[12-13]中翟俊海等提出的粗糙模糊決策樹歸納算法中，用定義4給出的模糊條件屬性P相對(duì)于模糊決策屬性Q的依賴度τP(Q)作為標(biāo)準(zhǔn)選擇擴(kuò)展屬性，但是文獻(xiàn)[5，10]指出此依賴函數(shù)τP(Q)不具備單調(diào)性，也就是說少的條件屬性可能計(jì)算出大的依賴函數(shù)值，從而導(dǎo)致算法有不收斂的可能.

基于上述問題本文提出了一種改進(jìn)的依賴函數(shù)作為啟發(fā)式選擇擴(kuò)展屬性.

定義5給定模糊信息系統(tǒng)FIS=(U,A∪C,V,f)，P∈A，Q∈C. 對(duì)于給定的對(duì)象x∈X，對(duì)象x屬于模糊負(fù)域的隸屬度定義為

(5)

定義6給定模糊信息系統(tǒng)FIS=(U,A∪C,V,f)，P∈A，Q∈C.模糊條件屬性P相對(duì)于模糊決策屬性Q的依賴度定義為

(6)

γP(Q)的值越大，說明條件屬性P相對(duì)于決策屬性Q就越重要.因此用γP(Q)作為選擇擴(kuò)展屬性的啟發(fā)

式算法.

定義7給定模糊信息系統(tǒng)FIS=(U,A∪C,V,f)，P∈A，Q∈C. 修改模糊條件屬性P相對(duì)于模糊決策

屬性Q的模糊粗糙度定義為：

(7)

在模糊信息系統(tǒng)中，模糊粗糙度刻畫的是模糊集的粗糙程度．模糊粗糙度越小，說明對(duì)模糊集分類的粗糙性就越小，也就越容易實(shí)現(xiàn)分類．所以，本文用βP(Q)作為葉子結(jié)點(diǎn)的終止條件．

2.2 改進(jìn)算法

輸入：模糊信息系統(tǒng)FIS=(U,A∪C,V,f)，閾值參數(shù)λ.

輸出：模糊決策樹

Step 1 對(duì)每一個(gè)條件屬性ai∈A，用式(6)分別計(jì)算決策屬性C相對(duì)于條件屬性ai的模糊依賴度；

Step 2 根據(jù)模糊依賴度的取值，選擇依賴度值最大的條件屬性a0作為擴(kuò)展屬性，即：

Step 3 用式(7)計(jì)算出a0各個(gè)分支的模糊粗糙度βaij(C)，如果存在aij，使得βaij(C)>λ，則產(chǎn)生一個(gè)葉子結(jié)點(diǎn)；否則，重復(fù)第1至第3步驟；

Step 4 輸出模糊決策樹.

3 實(shí)例說明

表1 模糊決策表

在表1所示的Ⅰ-型模糊決策表中，U={x1,x2,…,x16}，A={a1,a2,a3,a4}，其中a1={a11,a12,a13}，a2={a21,a22,a23}，a3={a31,a32}，a4={a41,a42}.

對(duì)于決策屬性C，U/C={C1,C2},其中，C1={x2,x4,x5,x12,x14,x16}；

C2={x1,x3,x6,x7,x8,x9,x10,x11,x13,x15}.

Step 1 先計(jì)算決策屬性C對(duì)條件屬性ai(1≤i≤4)的模糊依賴度，以a1為例：

μN(yùn)EGa1(C)(x1)=μN(yùn)EGa1(C)(x3)=μN(yùn)EGa1(C)(x4)=μN(yùn)EGa1(C)(x5)=μN(yùn)EGa1(C)(x9)=μN(yùn)EGa1(C)(x11)=0.7,

μN(yùn)EGa1(C)(x2)=0.6,μN(yùn)EGa1(C)(x6)=μN(yùn)EGa1(C)(x10)=μN(yùn)EGa1(C)(x15)=0.3,μN(yùn)EGa1(C)(x7)=0.1,

μN(yùn)EGa1(C)(x8)=μN(yùn)EGa1(C)(x12)=μN(yùn)EGa1(C)(x13)=μN(yùn)EGa1(C)(x14)=0.9,μN(yùn)EGa1(C)(x16)=0.5.

Step 2 因?yàn)闂l件屬性γa1(C)的值最大，所以條件屬性a1(Outlook)被選為擴(kuò)展屬性，即模糊決策樹的根結(jié)點(diǎn).

Step 3 根結(jié)點(diǎn)Outlook有3個(gè)分支：Sunny，Cloudy和Rain.計(jì)算3個(gè)分支相對(duì)于C1，C2的模糊粗糙度：

在分支Rain，相對(duì)于C2的模糊粗糙度是0.91，超過了閾值λ=0.85，所以終止于C2，屬性決策值為No的葉結(jié)點(diǎn).

在分支Sunny, Cloudy處重復(fù)過程，可從表1生成一棵模糊決策樹.

Step 4 輸出模糊決策樹.如圖1所示.

4 結(jié)語

針對(duì)模糊信息系統(tǒng)，提出了一種新的模糊決策表歸納算法，該算法重新定義了模糊決策屬性相對(duì)于條件屬性的模糊依賴度和模糊粗糙度，以模糊依賴度作為選擇擴(kuò)展屬性的依據(jù)，以此為標(biāo)準(zhǔn)生成模糊決策樹啟發(fā)式算法，再利用模糊粗糙度作為葉子結(jié)點(diǎn)的終止條件.最后用實(shí)例說明該算法生成的決策樹較為簡化，且不會(huì)造成信息丟失，并且算法收斂性也較好.本文后續(xù)工作將研究把決策表的屬性約簡引入到?jīng)Q策樹的生成過程中，以簡化在條件屬性較多的情況下，簡化樹的生長過程.