基于寬松下近似的模糊決策樹歸納算法

張群峰

(河北大學數學與信息科學學院，河北保定　071002)

?

基于寬松下近似的模糊決策樹歸納算法

張群峰

(河北大學數學與信息科學學院，河北保定071002)

利用模糊相似關系對連續型決策表進行模糊化,進而運用寬松下近似定義啟發式作為選擇擴展屬性的標準，從模糊決策表學習模糊決策樹.

連續型決策表；寬松下近似；模糊決策樹

MSC 2010:68T37

如何從連續型決策表歸納出模糊決策樹，是機器學習研究的重要問題.所謂連續型決策表是指用實數值條件屬性和決策屬性刻畫的樣例集合.一個有n個條件屬性值和1個決策屬性值的樣例可記為e=(a1,a2,…，ai,d)，其中ai,d∈R,i=1,2,…，n(R為實數集合).

模糊決策樹是一種由模糊屬性作節點、模糊屬性值即模糊集作邊的樹形圖.當一個用模糊屬性值描述的樣例出現時，可利用模糊決策樹對其進行分類：從根節點開始，用節點屬性對樣例進行測試，將樣例沿隸屬度最大的邊分類到子節點，如此遞歸地對樣例進行測試和分類，直至將樣例分類到模糊決策樹的某個葉子節點，此時葉子節點的模糊集就是該樣例的類標.

常用的從連續型決策表歸納模糊決策樹的幾種方法都是先將連續屬性用三角形或梯形模糊集模糊化，從而使連續型決策表成為模糊決策表，再利用某種啟發式作為選擇節點屬性的標準，產生節點和分支從而產生模糊決策樹，這些方法的不同之處主要在于啟發式信息的構造方法.

本文主要運用模糊粗糙集中寬松下近似概念提出一種連續型決策表的模糊決策樹構建方法，這種方法的主要優點是能充分挖掘樣例的信息.

1　預備知識

1.1模糊相似關系

設U={e1,e2,…,ei}為一個有限論域，其中ei(i=1,2,…,n)為樣例.笛卡爾積U×U上的模糊集R:U×U→[0,1]稱為U上的一個模糊關系.如果模糊關系進一步滿足：

1)自反性：?x∈U,R(x,x)=1；2)對稱性：?x,y∈U,R(x,y)=R(y,x)，則稱R為U上的一個模糊相似關系.

1.2模糊集的寬松下近似

設U為給定的論域，R為U上的模糊相似關系，用F(U)表示U上的全體模糊集合，則對于任意A∈F(U)，A的寬松下近似定義為

(1)

通常的下近似定義為

(2)

其中T為模糊t-模而I為模糊蘊含算子.

一般地有R↓A?R↑↓A?A，而且下例說明第1個包含關系中的等號可能不成立.

例設U=[0,1]，A∈F(U)定義為A(x)=x,?x∈U，U上的模糊相似關系定義為

2　基于寬松下近似的模糊決策樹歸納

2.1連續型決策表的屬性模糊化

通常的模糊化方法是事先人為指定模糊集的個數，再將連續型屬性模糊成若干三角形或梯形模糊集合，這種方法無論對什么屬性做法都一樣，忽視了各屬性的特點.本文受寬松下近似的啟發，對于給定的連續型決策表，針對每個屬性的特點，選用一個合適的模糊相似關系以刻畫樣例間的相似性.進而對每一個屬性建立一個相似矩陣.再通過合成的方法計算該模糊相似關系的傳遞閉包，依據該閉包對樣例進行聚類.進一步確定每一類的聚類中心得出模糊集.

選定模糊相似關系后，產生模糊決策表的算法描述如下.

算法1連續型屬性模糊化.輸入：連續型屬性的值向量.輸出：連續型屬性對應的模糊集.

第1步：計算屬性對應的模糊相似矩陣； 第2步：計算模糊相似矩陣的傳遞閉包；第3步：根據適當的閾值取截集對樣例聚類；第4步：對每個類計算其元素的平均相似度，將平均相似度最高的元素作為聚類中心，并以與其的相似度作為其他元素的隸屬度.

2.2基于寬松下近似的屬性重要度

設U={e1,e2,…,en}為樣例構成的論域，C和D分別為連續型決策表的條件屬性集合與決策屬性，A?C為條件屬性子集.若記RAj為對應于條件屬性Aj∈A的模糊相似關系，則根據定義式(1)，任意模糊決策類Ds(1≤s≤p)(這里p為決策類的總數)的RA-寬松下近似為

(3)

進而定義決策屬性D相對于條件屬性子集A的正域為

(4)

下面定義決策屬性D相對于條件屬性子集A的依賴度

(5)

設A?C為條件屬性子集，Aj∈C為條件屬性.若Aj∈A，則Aj相對于A的內部重要度定義為

(6)

若Aj∈C-A，則Aj相對于A的外部重要度定義為

(7)

選擇決策樹根節點的擴展屬性時，需要計算各個條件屬性相對于C的內部重要度；在選擇子節點的擴展屬性時，需要計算各候選屬性相對于該節點所在路徑上的父節點上擴展屬性集的外部重要度.

算法2計算條件屬性的重要度.輸入：條件屬性子集A，條件屬性Aj，決策屬性集合D.輸出：條件屬性Aj的重要度Ij.

2.3模糊決策樹的歸納算法

算法3模糊決策樹歸納.輸入：模糊決策表.輸出：模糊決策樹.

第1步：對所有條件屬性計算其相對于條件屬性集C的余集的正域，選擇余集具有最小正域的條件屬性作為根節點的測試屬性.

第2步：按根節點測試屬性的每一個模糊值術語產生一個分支.按照給定的α可能會產生該模糊值的截集為空集的情況，即所有樣例對該模糊集的隸屬度都在α以下，這時該分支稱為空分支.刪除所有的空分支.對于每一個非空分支，計算該分支相對于各個決策類的真值.如果存在真值大于β的決策類，則產生一個以該決策類為標簽的葉子節點.否則，看是否有其他的條件屬性能產生新的非空分支.若有，則選擇相對于該路徑屬性集具有最大正域的屬性作為擴展屬性進一步產生新的分支.否則，產生新的葉子節點，其類標為具有最大真值的決策類.

第3步：對所有新的非葉子節點，重復第2步，直至樹的生長結束.

下面的表1為一連續型決策表.選定如下模糊相似關系(其中σAj為屬性Aj的屬性值的均方差)，對表1運用前述算法可得到如圖1所示的模糊決策樹.

(8)

表1　連續型決策表的例子Tab.1　Examples of continuous decision table

圖1模糊決策樹

Fig.1Fuzzydecisiontree

3　結論

在模糊粗糙集理論中，寬松下近似比其他形式的下近似概念能更準確地逼近目標概念.在從連續型決策表學習模糊決策樹時，運用寬松下近似構造啟發式并將其作為選擇擴展屬性的標準，能充分利用數據信息.而且，根據不同屬性選擇不同的模糊相似關系對連續值屬性模糊化，可以反映屬性的特點，避免通常模糊化方法的機械性.

[1]MOTOHIDEU,HIROTAKAO,ITSUOH.FuzzydecisiontreesbyfuzzyID3algorithmanditsapplicationtodiagnosissystems[C].ProceedingsoftheThirdIEEEConferenceonFuzzySystems,1994(3):2113-2118.DOI：10.1109/FUZZY.1994.343539.

[2]YUANY,SHAWMJ.Inductionoffuzzydecisiontrees[J].FuzzySetsSystem,1995,69(2):125-139.DOI：10.1016/0165-0114(94)00229-Z.

[3]WANGXZ,YEUNGDS,TSANGECC.Acomparativestudyonheuristicalgorithmsforgeneratingfuzzydecisiontrees[J].IEEEtransactionsonsystems,man,andcybernetics-partb:Cybernetics,2001,31(2):215-226.DOI：10.1109/3477.915344.

[4]TSANGECC,CHENDG,YEUNGDS,etal.Attributesreductionusingfuzzyroughsets[J].IEEETransFuzzySyst,2008,16(5):1130-1141.DOI：10.1109/TFUZZ.2006.889960.

[5]ZHAIJH.Fuzzydecisiontreebasedonfuzzy-roughtechnique[J].SoftComputing,2011,(15):1087-1096.DOI：10.1007/s00500-010-0584-0.

[6]RADZIKOWSKAAM,KERREEE.Acomparativestudyoffuzzyroughsets[J].FuzzySetsSystem，2002,126(2):137-155.DOI:10.1016/S0165-0114(01)00032-X.

[7]MARSALAC.Fuzzydecisiontreesfordynamicdata[EB/OL].(2013-04-15)[2015-03-12].http://webia.lip6.fr/～marsala/articles/2013-ssci.pdf.DOI：10.1109/EAIS.2013.6604100.

(責任編輯：王蘭英)

A fuzzy decision tree induction algorithm based on loose lower approximation

ZHANG Qunfeng

(College of Mathematics and Information Science,Hebei University,Baoding 071002,China)

To induce a fuzzy decision tree from a continuous decision table,a method based on loose lower approximation in fuzzy rough set theory is proposed.First,a fuzzy decision table is generated by clustering fuzzy similarity relations.Second,based on loose lower approximation,a measure of the importance of a condition attribute is introduced.Finally,using this measure as a criterion for selecting the expanding attribute,a fuzzy decision tree induction algorithm is proposed and an illustrative example is provided.

continuous decision table;loose lower approximation;fuzzy decision tree

10.3969/j.issn.1000-1565.2016.03.001

2015-06-16

河北省自然科學基金資助項目(F2015201185)；保定市科學技術研究與發展計劃指導項目(12ZS005；12ZS006)

張群峰(1963-)，男，河北邯鄲人，河北大學副教授，主要從事機器學習及粗糙集理論研究.

E-mail:zhangqunfeng@hbu.cn

O235

A

1000-1565(2016)03-0225-04