自適應(yīng)模糊決策樹算法

孫 娟，王熙照

(河北大學(xué)數(shù)學(xué)與計(jì)算機(jī)學(xué)院，河北保定071002)

0 引言

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

1 基本概念

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

所有FDT算法都必須進(jìn)行模糊化預(yù)處理，而顯著性水平α和每個(gè)屬性的模糊語(yǔ)言項(xiàng)個(gè)數(shù)K是必須確定的主要參數(shù)。其值直接影響生成的模糊決策樹的性能。

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

1.1 顯著性水平α

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

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

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

1.2 真實(shí)水平β

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

模糊決策樹算法的顯著水平和真實(shí)水平起到了預(yù)剪枝模糊決策樹的作用［11］。這兩個(gè)參數(shù)的取值一般通過(guò)經(jīng)驗(yàn)直接給出，很難為不同數(shù)據(jù)庫(kù)確定最優(yōu)參數(shù)值，因此，約束了FDT算法在實(shí)際分類問題中的應(yīng)用。

1.3 模糊決策樹算法

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

(1)模糊決策樹的每個(gè)結(jié)點(diǎn)屬于F(U)。

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

(3)每個(gè)葉節(jié)點(diǎn)包含一個(gè)或多個(gè)類信息。

1.4 粒子群算法

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

其中d=l，2，…n，i=l，2，…m，m為種群規(guī)模，t為當(dāng)前進(jìn)化代數(shù)，cl和c2為加速常數(shù)，w為慣性權(quán)重。

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

模糊決策樹算法在建樹過(guò)程中，涉及到一些主要參數(shù)值的確定，如果參數(shù)值設(shè)定不恰當(dāng)，模糊決策樹算法會(huì)生成一棵分類能力差的模糊決策樹。而本文提出的AFDT算法能通過(guò)智能算法自主學(xué)習(xí)模糊決策樹算法中的主要參數(shù)值。

2.1 適應(yīng)度函數(shù)的設(shè)計(jì)

機(jī)器學(xué)習(xí)領(lǐng)域應(yīng)用智能算法的關(guān)鍵是如何設(shè)計(jì)適應(yīng)度函數(shù)。多數(shù)決策樹算法［1-2，12］使用分類準(zhǔn)確率作為算法的評(píng)價(jià)策略，但是剃刀原理更偏向于小的決策樹，而擴(kuò)展能力更是評(píng)價(jià)樹的重要標(biāo)準(zhǔn)［3，11］。因此，只使用分類準(zhǔn)確率作為適應(yīng)度函數(shù)的策略不十分充分。本文采用的適應(yīng)度函數(shù)綜合考慮了分類準(zhǔn)確率，擴(kuò)展能力和樹的規(guī)模。

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

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

2.2 AFDT算法

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

步驟2 按式 (3)計(jì)算每個(gè)微粒Xi的適應(yīng)度函數(shù)值

步驟3 對(duì)每個(gè)微粒Xi，將當(dāng)前適應(yīng)度值與其經(jīng)歷的最好位置pBest的值比較，如果pBest，則判斷模糊決策樹規(guī)則數(shù)是否小于pBest保留的規(guī)則數(shù)，如果小于便更新pBest;否則如果則將其作為當(dāng)前的最好位置否則不操作。

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

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

步驟6 未達(dá)到最大代數(shù)Gmax，則返回步驟2。

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

3 算法測(cè)試與分析

3.1 實(shí)驗(yàn)數(shù)據(jù)

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

表1 模糊決策樹測(cè)試準(zhǔn)確率平均值比較

表1中可以看出選用不同參數(shù)值對(duì)模糊決策樹的測(cè)試準(zhǔn)確率影響很大。AFDT算法的測(cè)試結(jié)果明顯高于其他5種參數(shù)值設(shè)置產(chǎn)生的測(cè)試準(zhǔn)確率。表1中AFDT的啟發(fā)式采用信息熵作為選取擴(kuò)展屬性的方法，而使用不確定信息作為啟發(fā)式得出的實(shí)驗(yàn)結(jié)果和表1相同。

AFDT算法與已有文獻(xiàn)中的實(shí)驗(yàn)數(shù)據(jù)比較見表2使用AFDT算法得到的模糊決策樹的性能明顯提高，測(cè)試準(zhǔn)確率幾乎均高于經(jīng)過(guò)多種方法改進(jìn)后的模糊分類算法。這一方面表明參數(shù)值的合理設(shè)置對(duì)FDT算法的重要性另一方面說(shuō)明使用智能算法選取參數(shù)值的必要性。

圖1 不同參數(shù)值產(chǎn)生模糊決策樹的測(cè)試準(zhǔn)確率比較

表2 與其他分類算法的測(cè)試準(zhǔn)確率比較

圖1給出3種測(cè)試準(zhǔn)確率的比較圖，第一列為AFDT算法用PSO設(shè)定主要參數(shù)值、第二列為5組參數(shù)值中最優(yōu)參數(shù)值生成的模糊決策樹，第三列是文獻(xiàn)［11］憑經(jīng)驗(yàn)設(shè)定最優(yōu)參數(shù)值的模糊決策樹的準(zhǔn)確率。圖1中可以明顯看出AFDT算法對(duì)主要參數(shù)進(jìn)行智能學(xué)習(xí)后，生成的模糊決策樹的預(yù)測(cè)能力明顯提高，特別是對(duì)glass數(shù)據(jù)庫(kù)，參數(shù)值的變化對(duì)其性能的影響更為明顯。

3.2 參數(shù)間交互作用的分析

表3對(duì)參數(shù)α、β出現(xiàn)的最優(yōu)域和模糊決策樹性能的關(guān)系進(jìn)行分析。

表3 參數(shù)α，β優(yōu)化結(jié)果匯總表

其中，概括能力強(qiáng)是指測(cè)試準(zhǔn)確率高于訓(xùn)練準(zhǔn)確率。α、β的密集度指其最優(yōu)值出現(xiàn)的位置是否臨近。樹形差別是指最優(yōu)模糊決策樹的規(guī)則數(shù)是否相差較大。從實(shí)驗(yàn)數(shù)據(jù)中發(fā)現(xiàn):

(1)參數(shù)α、β的最優(yōu)值出現(xiàn)區(qū)域均不相同。這說(shuō)明使用傳統(tǒng)的參數(shù)值設(shè)定方法 (即α取0.4附近，β取0.7附近)是不可行的。

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

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

(4)相同訓(xùn)練集、相同初始種群找到的最優(yōu)參數(shù)值α、β不會(huì)完全相同。最優(yōu)參數(shù)值出現(xiàn)區(qū)域會(huì)聚集在幾個(gè)小區(qū)域。在各個(gè)小區(qū)域中，通常α變化區(qū)間小β變化區(qū)間大。實(shí)驗(yàn)分析發(fā)現(xiàn)，在最優(yōu)小區(qū)域中，α找到最優(yōu)區(qū)域取值后，β取值越高產(chǎn)生的決策樹越大，但并不能提高訓(xùn)練與測(cè)試準(zhǔn)確率;β取值越低產(chǎn)生的決策樹越小，擴(kuò)展能力強(qiáng)。α的對(duì)應(yīng)最優(yōu)區(qū)間波動(dòng)較小 (0.1內(nèi)波動(dòng))，β的對(duì)應(yīng)最優(yōu)區(qū)間波動(dòng)較大 (0.2～0.3內(nèi)波動(dòng))。實(shí)驗(yàn)顯示，不同數(shù)據(jù)庫(kù)的α出現(xiàn)的最優(yōu)區(qū)域不同，且該區(qū)域極少出現(xiàn)在α取0.5處，β的最優(yōu)區(qū)域也會(huì)在0.6～1之間變化。

3.3 AFDT算法的收斂性分析

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

圖2 數(shù)據(jù)庫(kù)適應(yīng)度函數(shù)的收斂趨勢(shì)

4 結(jié)束語(yǔ)

本文提出自適應(yīng)模糊決策樹算法用于解決模糊決策樹算法中主要參數(shù)值的手動(dòng)設(shè)置問題，實(shí)驗(yàn)結(jié)果表明AFDT算法可以明顯提高模糊決策樹的概括能力和預(yù)測(cè)能力。該方法設(shè)計(jì)的適應(yīng)度函數(shù)有效的在模糊決策樹的訓(xùn)練準(zhǔn)確率，測(cè)試準(zhǔn)確率，擴(kuò)展能力和樹的規(guī)模四個(gè)方面找到了一個(gè)權(quán)衡。在應(yīng)用中，AFDT算法可以和任何改進(jìn)的模糊決策樹算法相結(jié)合，智能設(shè)定其主要參數(shù)值，減少經(jīng)驗(yàn)設(shè)定參數(shù)造成的低性能，增強(qiáng)了模糊決策樹算法的實(shí)用性。

［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，F(xiàn)AN 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).［張建科，劉三陽(yáng)，張曉清.改進(jìn)的粒子群算法［J］.計(jì)算機(jī)工程與設(shè)計(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).［孫娟，王熙照.規(guī)則簡(jiǎn)化與模糊決策樹剪枝的比較［J］.計(jì)算機(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.