羅秋瑾

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

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

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

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

1 基本概念

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

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

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

(1)

(2)

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

(3)

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

(4)

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

2 改進的模糊決策樹歸納算法

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

2.1 對原算法的一些分析

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

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

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

(5)

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

(6)

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

式算法.

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

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

(7)

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

2.2 改進算法

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

輸出：模糊決策樹

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

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

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

Step 4 輸出模糊決策樹.

3 實例說明

表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}.

對于決策屬性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 先計算決策屬性C對條件屬性ai(1≤i≤4)的模糊依賴度，以a1為例：

μNEGa1(C)(x1)=μNEGa1(C)(x3)=μNEGa1(C)(x4)=μNEGa1(C)(x5)=μNEGa1(C)(x9)=μNEGa1(C)(x11)=0.7,

μNEGa1(C)(x2)=0.6,μNEGa1(C)(x6)=μNEGa1(C)(x10)=μNEGa1(C)(x15)=0.3,μNEGa1(C)(x7)=0.1,

μNEGa1(C)(x8)=μNEGa1(C)(x12)=μNEGa1(C)(x13)=μNEGa1(C)(x14)=0.9,μNEGa1(C)(x16)=0.5.

Step 2 因為條件屬性γa1(C)的值最大，所以條件屬性a1(Outlook)被選為擴展屬性，即模糊決策樹的根結(jié)點.

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

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

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

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

4 結(jié)語

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