自適應模糊決策樹算法

孫 娟，王熙照

(河北大學數學與計算機學院，河北保定071002)

0 引言

目前最具代表的決策樹算法是Quinlan提出的C4.5［1］。模糊決策樹算法 (fuzzy decision tree，FDT)是在原有決策樹算法的基礎上引入模糊集理論，能很好的處理與人的思維有關的不確定性、模糊性。因此，FDT算法在處理連續值屬性的數據時具有優勢［2-7］。為提高分類準確率，FDT的改進算法主要集中在改進用于建樹的啟發式和改進推理機制這兩個方面，具體算法實現體現在與其他機器學習方法的融合，如應用粗糙集、神經網絡、基于示例推理和SVM等方法，從而提高分類精度［6-7］。但無論哪種改進算法都需要對FDT算法共有的主要參數值進行設置。目前，模糊決策樹算法中的重要參數取值均是經驗設定，這嚴重影響了模糊決策樹算法的預測能力。文［2］使用遺傳算法優化每個屬性的模糊語言項個數，但是對于其他主要參數值卻采用經驗設定。粒子群優化 (particle swarm optimization，PSO)算法是一種基于群智能的優化工具，具有深刻的智能背景［8-9］。通常PSO算法比遺傳算法運行速度快、算法參數少且易于實現［10］。本文提出使用改進例子群算法自動設定FDT的多個主要參數值的自適應模糊決策樹算法 (adaptive fuzzy decision tree algorithm，AFDT)。實驗表明該算法能夠生成性能更優的模糊決策樹;最后，分析了模糊決策樹算法主要參數之間存在交互影響關系。

1 基本概念

模糊決策樹算法可分為3步，首先是模糊預處理階段，然后是建樹階段，最后是匹配分類階段。在建樹過程中使用啟發式從根向葉子方向選取擴展屬性產生模糊決策樹。對啟發式的改進有代表性的方法有使用信息熵的Fuzzy-ID3算法［3］、針對不確定性的 fuzzy-ambiguty算法［5］和引入粗糙集方法的多種算法［6］。

所有FDT算法都必須進行模糊化預處理，而顯著性水平α和每個屬性的模糊語言項個數K是必須確定的主要參數。其值直接影響生成的模糊決策樹的性能。

定義1設模糊信息系統FIS為一個四元組，FIS=(U，A，V，f)，其中，U={x1，x2，…xN}是對象的非空有限集，每個示例 xi=(ai1，ai2，…ais);屬性集為 A={A(1)，A(2)，…，A(s)}，其中 K=(k1，k2，…，ks)為屬性集 A 的語言項個數集，將每個屬性模糊化產生ki個的屬性值為模糊化后的語言項，每個語言項對應定義在U中的一個模糊子集表示一個模糊概念。模糊子集可使用隸屬函數表示，通常采用三角隸屬函數。

1.1 顯著性水平α

在模糊集上進行劃分生成模糊決策樹的過程中，同層屬性值所覆蓋的例子之間有一定的重疊，會影響擴展屬性的選取。模糊集合理論中的α水平截集的引入能在一定程度上減少這種重疊的影響，降低分類的不確定性。FDT算法的建樹過程均在給定的顯著性水平α的基礎上進行。一個示例只有當其相關隸屬度大于α時才能劃分到某個分支。α取值過低不能降低分類的模糊度，即無法去除不重要的分支，取值過高會使得有用數據丟失，降低模糊決策樹的擴展能力［6］。

定義2 設在論域U上的模糊集A∈F(U)，其隸屬函數 A(u)，α∈［0，1］記Aα={u|u∈U，A(u) α}稱Aα為A的一個α截集，α稱為顯著水平。

定義3 對定義在U上的一個模糊條件F和模糊條件集p，p={E1…Ek}在顯著水平α上的模糊劃分為Pα|Fα={Eα1∩Fα1…Eαk∩Fαk}，Eαi是在 α 水平上的條件 Ei，Fαi是在α水平上的條件Fi。

1.2 真實水平β

真實水平β是一個閾值，在產生決策樹葉子時起到了重要作用，直接控制模糊決策樹葉子的生成［6］。FDT算法產生根結點后，計算作為根節點的屬性的每一個非空分枝，計算在該分支上的所有例子分到每個類的分類置信水平，如果置信水平大于真實水平β即作為葉子，否則向下進行分支。β取值過低，生成的決策樹偏小，不能概括訓練集的規律，決策樹的訓練準確率低;取值過高，生成的決策樹巨大，樹的擴展能力低，易產生過擬合現象。因此，過高或過低的β取值都會影響模糊決策樹的性能。

模糊決策樹算法的顯著水平和真實水平起到了預剪枝模糊決策樹的作用［11］。這兩個參數的取值一般通過經驗直接給出，很難為不同數據庫確定最優參數值，因此，約束了FDT算法在實際分類問題中的應用。

1.3 模糊決策樹算法

定義4 設F(U)為在論域U上的強模糊集，FiF(U)(1 i n)。如果滿足下面的條件，則生成模糊決策樹T。

(1)模糊決策樹的每個結點屬于F(U)。

(2)對每個非葉結點N，其子節點組成F(U)的子集記為Γ(即-i(1 i n)，Γ =Fi∩N)。

(3)每個葉節點包含一個或多個類信息。

1.4 粒子群算法

設在一個n維的搜索空間中，由m個粒子組成的種群X={X1，…，Xm}，其中第i個粒子位置為Xi={xi1，…，xim}，微粒i相應的飛行速度V={vi1，…vim}，P={pi1，…pim}為微粒i所經歷過的最好位置，Pg={pg1，…pgm}為整個粒子群中所有粒子歷史中的最好位置。每個粒子按下式改變其速度和位置

其中d=l，2，…n，i=l，2，…m，m為種群規模，t為當前進化代數，cl和c2為加速常數，w為慣性權重。

2 自適應模糊決策樹算法 (AFDT算法)

模糊決策樹算法在建樹過程中，涉及到一些主要參數值的確定，如果參數值設定不恰當，模糊決策樹算法會生成一棵分類能力差的模糊決策樹。而本文提出的AFDT算法能通過智能算法自主學習模糊決策樹算法中的主要參數值。

2.1 適應度函數的設計

機器學習領域應用智能算法的關鍵是如何設計適應度函數。多數決策樹算法［1-2，12］使用分類準確率作為算法的評價策略，但是剃刀原理更偏向于小的決策樹，而擴展能力更是評價樹的重要標準［3，11］。因此，只使用分類準確率作為適應度函數的策略不十分充分。本文采用的適應度函數綜合考慮了分類準確率，擴展能力和樹的規模。

AFDT算法將主要參數α、β和語言項個數集K組成微粒X。微粒Xi被帶入建樹過程，算法進行模糊化預處理后，使用啟發式產生模糊決策樹FDTj(1 j m，m為粒子群的規模)，其訓練準確率為 Trj(xi)、規則數為rulenumj(xi)，對測試數據集模糊化后匹配FDTj，其測試準確率為Tej(xi)。Xi的適應度函數定義為

其中 comp(xi)=(Tej(xi)－Trj(xi))/Trj(xi)代表FDTj的概括能力，size(xi)=1÷rulenumj(xi)代表FDTj的大小，fi為比例系數通過搜索適應度的最大值，就能找到性能最優的模糊決策樹FDTbest。

2.2 AFDT算法

步驟1 初始化一群微粒X={X1…Xm}，其中第i個微粒 Xi包括 xi=(xi1，…xin)T和 vi=(vi1，…vin)T，隨機位置xi中的xi1、xi2分別代表隨機產生的α和β值，xi3…xin分別代表每個屬性的語言項個數(k1，k2，…，ks)。n為每個微粒長度。

步驟2 按式 (3)計算每個微粒Xi的適應度函數值

步驟3 對每個微粒Xi，將當前適應度值與其經歷的最好位置pBest的值比較，如果pBest，則判斷模糊決策樹規則數是否小于pBest保留的規則數，如果小于便更新pBest;否則如果則將其作為當前的最好位置否則不操作。

步驟4 對每個微粒Xi將其適應度值與全局經歷最好的位置gBest的值比較，如果則判斷rulenum(xi)是否小于gBest保留的規則數，如果小于則更新gBest;否則如果則將其作為當前的最好位置否則不操作。

步驟5 根據式 (4)(5)更新微粒Xi的速度和位置

步驟6 未達到最大代數Gmax，則返回步驟2。

對于AFDT算法，一個粒子Xi代表著一組參數值的組合，而在訓練矢量空間中，參數組代表著N(N=2+s)個主要參數Xi={xi1，xi2，…，xiN}，因此一個粒子Xi包含N維，即Xi∈RN。在解空間中搜索的粒子可以看成N個主要參數在訓練矢量空間RN中搜索最優模糊決策樹FDTbest的過程。在搜索過程中，一個粒子產生一棵模糊決策樹FDTj代表了訓練矢量空間中的一個位置矢量Xi，根據公式3計算Xi當前的適應值，即可衡量粒子位置 (模糊決策樹性能)的優劣。Vi=(vi1，vi2，…viN)為粒子的飛行速度，即參數值調整的幅度;pBest為本粒子迄今產生的性能最優的模糊決策樹，gBest為整個粒子群迄今生成到的最優模糊決策樹。式 (4)的第二項代表了粒子對自身的學習，第三項代表粒子間的協作。式 (4)正是粒子根據它上一次迭代的速度、當前位置和自身最好經驗與群體最好經驗之間的距離來更新速度。然后粒子根據式 (5)飛向新位置，得到新的參數組。

3 算法測試與分析

3.1 實驗數據

從UCI數據庫中選取10個典型的連續值屬性的數據集，使用AFDT算法產生模糊決策樹。采用分層旁置法，隨機選取70%的數據為訓練集，其余為測試集，進行10次無重復實驗。AFDT算法確定例子群規模m為20個微粒;每個微粒的長度n取值為2+s;微粒的范圍分別是α［0，0.5］，β［0，1］，ki(1 i s)為 ［2，10］;最大代數Gmax設定為30代。AFDT算法生成的模糊決策樹與使用手工設定的5組參數值生成的5棵模糊決策樹進行對比。手工設定參數值的模糊決策樹算法使用與AFDT算法相同的語言項個數集K模糊化訓練數據。實驗結果見表1，其中，MAX(t)列為t=1～5列最高值，α=0.3+t*0.05;β=0.6+t*0.1。

表1 模糊決策樹測試準確率平均值比較

表1中可以看出選用不同參數值對模糊決策樹的測試準確率影響很大。AFDT算法的測試結果明顯高于其他5種參數值設置產生的測試準確率。表1中AFDT的啟發式采用信息熵作為選取擴展屬性的方法，而使用不確定信息作為啟發式得出的實驗結果和表1相同。

AFDT算法與已有文獻中的實驗數據比較見表2使用AFDT算法得到的模糊決策樹的性能明顯提高，測試準確率幾乎均高于經過多種方法改進后的模糊分類算法。這一方面表明參數值的合理設置對FDT算法的重要性另一方面說明使用智能算法選取參數值的必要性。

圖1 不同參數值產生模糊決策樹的測試準確率比較

表2 與其他分類算法的測試準確率比較

圖1給出3種測試準確率的比較圖，第一列為AFDT算法用PSO設定主要參數值、第二列為5組參數值中最優參數值生成的模糊決策樹，第三列是文獻［11］憑經驗設定最優參數值的模糊決策樹的準確率。圖1中可以明顯看出AFDT算法對主要參數進行智能學習后，生成的模糊決策樹的預測能力明顯提高，特別是對glass數據庫，參數值的變化對其性能的影響更為明顯。

3.2 參數間交互作用的分析

表3對參數α、β出現的最優域和模糊決策樹性能的關系進行分析。

表3 參數α，β優化結果匯總表

其中，概括能力強是指測試準確率高于訓練準確率。α、β的密集度指其最優值出現的位置是否臨近。樹形差別是指最優模糊決策樹的規則數是否相差較大。從實驗數據中發現:

(1)參數α、β的最優值出現區域均不相同。這說明使用傳統的參數值設定方法 (即α取0.4附近，β取0.7附近)是不可行的。

(2)易生成高性能決策樹的數據庫如iris，rice等，最優參數取值范圍較分散，對參數預剪枝的要求不大;而不易產生高性能決策樹的數據庫如glass，liver等，最優α、β的取值范圍集中，即α、β設定的值對FDT算法預剪枝起到關鍵作用。

(3)從樹的擴展能力分析，高性能決策樹的擴展能力強，樹型變化小，不需要參數α、β干預樹的預剪枝，實驗數據表現為參數α、β取值范圍大、較分散;低性能決策樹擴展能力差，樹型變化大，需要參數α、β起到預剪枝的功能，實驗數據表現為參數α、β取值范圍小、密集。

(4)相同訓練集、相同初始種群找到的最優參數值α、β不會完全相同。最優參數值出現區域會聚集在幾個小區域。在各個小區域中，通常α變化區間小β變化區間大。實驗分析發現，在最優小區域中，α找到最優區域取值后，β取值越高產生的決策樹越大，但并不能提高訓練與測試準確率;β取值越低產生的決策樹越小，擴展能力強。α的對應最優區間波動較小 (0.1內波動)，β的對應最優區間波動較大 (0.2～0.3內波動)。實驗顯示，不同數據庫的α出現的最優區域不同，且該區域極少出現在α取0.5處，β的最優區域也會在0.6～1之間變化。

3.3 AFDT算法的收斂性分析

粒子群算法具有很好的收斂性。通常AFDT算法學習10代后就可以得到最優解。已經證明決策樹算法是NP難問題，因此，粒子群算法易陷入局部最優解的缺陷對AFDT算法的影響很小。圖2顯示AFDT算法對rice和iris數據庫進行50次試驗，其適應度平均值的變化情況，可以看出AFDT算法有很好的收斂性。

圖2 數據庫適應度函數的收斂趨勢

4 結束語

本文提出自適應模糊決策樹算法用于解決模糊決策樹算法中主要參數值的手動設置問題，實驗結果表明AFDT算法可以明顯提高模糊決策樹的概括能力和預測能力。該方法設計的適應度函數有效的在模糊決策樹的訓練準確率，測試準確率，擴展能力和樹的規模四個方面找到了一個權衡。在應用中，AFDT算法可以和任何改進的模糊決策樹算法相結合，智能設定其主要參數值，減少經驗設定參數造成的低性能，增強了模糊決策樹算法的實用性。

［1］AYMERICH F X，ALONSO J，CABANAS M E，et al.Decision tree based fuzzy classifier of1H magnetic resonance spectra from cerebrospinal fluid samples［J］.Fuzzy Sets and Systems，2011，170(1):43-63.

［2］FAN Chinyuan，CHANG Peichann，LIN Jyunjie，et al.A hybrid model combining case-based reasoning and fuzzy decision tree for medical data classification［J］.Applied Soft Computing，2011，11(1):632-644.

［3］LI Yan，JIANG Dandan，LI Fachao.The application of generating fuzzy ID3 algorithm in performance evaluation［J］.Procedia Engineering，2012(29):229-234.

［4］Smith Tsang，Ben Kao，Kevin Y YIP，et al.Decision trees for uncertain data［J］.IEEE Transactions on Knowledge and Data Engineering，2001，23(1):64-78.

［5］Mohammad Ebadi，Mohammad Ali Ahmadi，Shahab Gerami，et al.Application fuzzy decision tree analysis for prediction condensate gas ratio:Case study［J］.International Journal of Computer Applications，2012，39(8):23-28.

［6］ZHAI Junhai.Fuzzy decision tree based on fuzzy-rough technique［J］.Soft Compute，2011(15):1087-1096.

［7］CHANG Peichann，FAN Chinyuan，DZAN Weiyuan.A CBR-based fuzzy decision tree approach for database classification［J］.Expert Systems with Applications，2010，37(1):214-225.

［8］Leonardo Vanneschi，Daniele Codecasa，Giancarlo Mauri.A comparative study of four parallel and distributed PSO methods［J］.New Generation Computing，2011，29(2):129-161.

［9］ZHANGJianke，LIUSanyang，ZHANGXiaoqing.Improved particle swarm optimization ［J］.Computer Engineering and design，2007，28(17):4215-4219(in Chinese).［張建科，劉三陽，張曉清.改進的粒子群算法［J］.計算機工程與設計，2007，28(17):4215-4219.］

［10］Sudheer Ch，Shashi Mathur.Particle swarm optimization trained neural network for aquifer parameter estimation［J］.KSCE Journal of Civil Engineering，2012，16(2):298-307.

［11］SUN Jua，WANG Xizhao.A comparative analysis of rule simplification and pruning fuzzy decision trees［J］.Computer Engineering，2006，32(12):210-211(in Chinese).［孫娟，王熙照.規則簡化與模糊決策樹剪枝的比較［J］.計算機工程，2006，32(12):210-211.］

［12］Eghbal G Mansoori，Mansoor J Zolghadri，Seraj D Katebi.SGERD:A steady-state genetic algorithm for extracting fuzzy classification rules from data［J］.IEEE Transactions on Fuzzy Systems，2008，16(4):1061-1071.

［13］Jens Huhn，Eyke Hullermeier.FR3:A fuzzy rule learner for inducing reliable classifiers［J］.IEEE Transactions on Fuzzy Systems，2009，17(1):138-149.