国产日韩欧美一区二区三区三州_亚洲少妇熟女av_久久久久亚洲av国产精品_波多野结衣网站一区二区_亚洲欧美色片在线91_国产亚洲精品精品国产优播av_日本一区二区三区波多野结衣 _久久国产av不卡

?

一種基于正區(qū)域及其分類純度的決策樹算法

2011-12-28 03:25蔣慧平費(fèi)耀平
關(guān)鍵詞:粗糙集結(jié)點(diǎn)決策樹

蔣慧平 費(fèi)耀平

(1.中南大學(xué)信息科學(xué)與工程學(xué)院,湖南長沙 410012;2.湖南廣播電視大學(xué),湖南長沙 410004;3.中南大學(xué)現(xiàn)代教育技術(shù)中心,湖南長沙 410012)

一種基于正區(qū)域及其分類純度的決策樹算法

蔣慧平1,2費(fèi)耀平3*

(1.中南大學(xué)信息科學(xué)與工程學(xué)院,湖南長沙 410012;2.湖南廣播電視大學(xué),湖南長沙 410004;3.中南大學(xué)現(xiàn)代教育技術(shù)中心,湖南長沙 410012)

本文分析了基于正區(qū)域的決策樹生成算法的不足,針對這些不足,提出了基于正區(qū)域及其分類純度的決策樹算法。該方法計算簡單,易于理解,并用實例說明了該方法的優(yōu)越性。

粗糙集;決策樹;正區(qū)域;分類純度

一、引言

決策樹是以實例為基礎(chǔ)的歸納推理學(xué)習(xí)算法,它從一組無序、無規(guī)則的元組中推導(dǎo)出分類規(guī)則,具有高效、直觀的特點(diǎn)。決策樹算法的關(guān)鍵是屬性選取標(biāo)準(zhǔn),作為決策樹的經(jīng)典算法ID3能較好地提高分類速度和準(zhǔn)確率,但該算法仍存在許多不足。為此,一些學(xué)者將粗糙集理論[1][4]引入決策樹,紛紛提出基于粗糙集理論的決策樹算法[1][5][6][7]:用粗糙邊界[4]的大小作為屬性選擇標(biāo)準(zhǔn)或以正區(qū)域作為屬性標(biāo)準(zhǔn)[5],但實際上,粗糙邊界最小的屬性會有多個,得到的決策樹的泛化能力不好[7]。

針對上述不足,本文基于粗糙集理論和決策樹算法的基本原理,提出了一種改進(jìn)算法:基于正區(qū)域及其分類純度的決策樹算法,提高了決策樹對于未知樣本的分類和預(yù)測能力。最后的實例表明,本文方法正確有效,簡單實用,明顯優(yōu)于傳統(tǒng)的 ID3算法。

二、粗造集基本概念

定義1 決策系統(tǒng)

一個決策系統(tǒng)是一個有序四元組:S=(U,A,V,f),其中 U 是論域,U={X1,X2,…,Xm},A=C∪D,其中C是條件屬性集,D是決策屬性集;V=∪{Va:a∈A}是屬性值的集合,Va是屬性a的值域;f:U×A→V是一個信息函數(shù),對每一個a∈A和x∈U,定義一個信息函數(shù)f(x,a)∈Va,即信息函數(shù)f指定U中的每一個對象x的屬性值。當(dāng)屬性集合A不劃分為條件屬性子集合和決策屬性子集合時,該系統(tǒng)又稱為信息系統(tǒng)[9]。

定義2 上近似、下近似、邊界和R-正區(qū)域

對信息系統(tǒng)S=(U,A,V,f),設(shè)R?A,X?U,則IND(R)是U×U上的等價關(guān)系,R(xi)是按等價關(guān)系IND(R)得到的包含xi的等價類,稱R(xi)為R基本集。用屬性B對U進(jìn)行劃分,獲得的是一個等價類集。子集X的下近似R*(X)和上近似R*(X)分別定義為:R*(X)={x∈∪|[x]R?X},R*(X)={x∈∪|[x]R∩X≠Φ},BNR(X)=R*(X)-R*(X)為X的邊界。POSR(X)=R*(X)稱為集合X 的 R- 正區(qū)域[10]。

三、相關(guān)工作分析

用正區(qū)域作為屬性標(biāo)準(zhǔn)的方法,存在著相同的屬性較多、不易選擇屬性和葉子結(jié)點(diǎn)的泛化能力不足的問題。以下面的例子為例:

例1:U={b1,b2,b3,b4,b5,b6,b7,b8,b9},A,Y,Q是條件屬性,D是決策屬性。

U/D={(b1,b2,b3,b4,b5,b6),(b7,b8,b9)};U/A={(b1,b2),(b3,b4,b5),(b7,b8),(b6,b9)};U/Y={(b1,b2,b3,b4),(b5,b7,b8),(b6,b9)};U/Q={b1,b2,b3,b4,b5,(b7,b8),(b6,b9)}.

由正區(qū)域定義可以|POSA(D)|=7,|POSY(D)|=7,|POSQ(D)|=4。按基于正區(qū)域的屬性選擇標(biāo)準(zhǔn)應(yīng)該選擇屬性A或者Q。但實際上選擇屬性A最為合理,因為由A分割出來的決策樹的葉子結(jié)點(diǎn)最小,且得到的決策樹的葉子深度最小。

理想的決策樹的要求是:葉子結(jié)點(diǎn)最少,葉子結(jié)點(diǎn)深度最小,葉子結(jié)點(diǎn)最少且結(jié)點(diǎn)深度最?。?]。為解決上述問題,本文根據(jù)正區(qū)域區(qū)分能力的思路,先定義條件屬性正區(qū)域的分類純度[8]。

定義3 決策表T=(U,C,D),u為論域,A?C,U/D={Y1,Y2,…,Ym},U/A={Al,A2,…,An},記A的正區(qū)域為POSA(D)={P1,P2,…,Pk},則該條件屬性正區(qū)域的分類純度[8]定義為:

顯然0<PPDA(D)≤1。

條件屬性正區(qū)域的分類純度反映了對決策屬性的分類程度,值越高,反映分類能力越強(qiáng)。

對于例1,可得:

可見,選擇屬性P作為分類屬性是合理的。

例2:U={a1,a2,a3,a4,a5,a6,a7,a8,a9},P,Q,R是條件屬性,Y是決策屬性。U/Y={(a1,a2,a3,a4,a5,a6),(a7,a8),a9};U/P={(a1,a2),(a3,a4,a5),(a6,a7,a8,a9)};U/Q={(a1,a2,a3),(a7,a8),(a4,a5,a6,a9)};U/R={a1,a2,a3,a4,(a5,a6,a7,a8),a9}。

由正區(qū)域定義可知:

|POSP(Y)|=|POSQ(Y)|=|POSR(Y)|=5,PPDP(D)=0.24,PPDQ(D)=0.22,PPDR(D)=0.19。

|POSP(Y)|+PPDP(D)=5.24,為最大,故選擇屬性P最為分類屬性是合理的。

四、算法

記POSPPD(D)=|POSA(D)|+PPDA(D),該算法描述為:

輸入:訓(xùn)練樣本集U,條件屬性C,決策屬性D

輸出:決策樹

(1)創(chuàng)建結(jié)點(diǎn);

(2)計算訓(xùn)練樣本集U條件屬性的POSPPD;

(3)從C中選擇POSPPD(D)為最大的那個屬性A作為測試屬性;

(4)以A為根建立決策樹;對A的可能取值進(jìn)行計算,若沒有到達(dá)葉子節(jié)點(diǎn),則繼續(xù)調(diào)用該算法;

(5)返回樹。

五、實例

以下面的決策表來說明新算法。

決策表

a1,a2,a3,a4 為條件屬性,D 為決策屬性。

U/a1={(1,2,3),(4,5,6,7),(8,9),(10,11,12,13,14,15)};

U/a2={(1,2,3,4,5),(6,7,8),(9,10,11),(12,13,14,15)};

U/a3={(1,2),(3,4,5,6,7),(8,9,10,11,12),(13,14,15)};

U/a4={(1,3,4,7,8,11),(2,5,6),(9,10,12,13,14,15)}

U/D={(1,2,3,4,5,6),(7,8,9,10,12),(11,13,14,15)};

根據(jù)算法可得:

故選擇屬性a2。

對于數(shù)據(jù)集(6,7,8),(9,10,11),(12,13,14,15),依照上述計算,選擇相應(yīng)的條件屬性,最后得到?jīng)Q策樹如圖1所示:

圖1 新算法生成的決策樹

相對于正區(qū)域的屬性選擇標(biāo)準(zhǔn)(分別選擇屬性a1,a2),生成的決策樹圖2、圖3,基于新算法生成的決策樹更理想。

圖2 基于正區(qū)域決策樹算法(選擇屬性a1)

圖3 基于正區(qū)域決策樹算法(選擇屬性a3)

六、結(jié)論

本文提出了一種基于正區(qū)域及其分類純度相結(jié)合的決策樹算法,所生成的決策樹葉子數(shù)目較小、葉子的平均深度較小,效率高,實例說明新算法提高了決策樹的分類和預(yù)測能力。

[1]鄒瑞芝,羅可,曾正良.基于粗糙集理論的決策樹分類方法[J].計算機(jī)工程與科學(xué),2009,31(10):112-114.

[2]Quinlan J R.Simplifying decision trees[J],International Journal of Man-Machine Studies,1987,27(3):221-234.

[3]王國胤.Rough集理論與知識獲?。跰].西安:西安交通大學(xué)出版社,2001.

[4]張文修,吳偉志等.粗糙集理論與方法[M].北京:科學(xué)出版社,2003.

[5]王名揚(yáng),衛(wèi)金茂,尹衛(wèi)國.基于粗造集理論的新決策樹剪枝方法[J].東北師范大學(xué)(自然科學(xué)版),2005,37(3):28-32.

[6]朱紅.基于Rough Set的最簡決策樹去頂算法的研究[J].計算機(jī)工程與應(yīng)用,2003,41(13):129-131.

[7]高靜,楊炳儒,徐章艷,宋威.一種改進(jìn)的基于正區(qū)域的決策樹算法[J].計算機(jī)科學(xué),2008,35(5):138-142.

[8]喬梅.基于粗糙集和數(shù)據(jù)庫技術(shù)的知識發(fā)現(xiàn)與推理方法研究[D].天津大學(xué),2005.

[9]蔣蕓,李戰(zhàn)懷,張強(qiáng),劉楊.一種基于粗糙集構(gòu)造決策樹的新方法[J].計算機(jī)應(yīng)用,2004,(8).

[10]張玉紅,胡學(xué)鋼,鄭錦良.基于粗糙集決策樹優(yōu)化研究[J].合肥工業(yè)大學(xué)學(xué)報,2009,(12).

An Algorithm for Decision Tree Based on Positive Region and Its Classification Ability

JIANG Hui-ping,F(xiàn)EI Yao-ping

In this paper,disadvantages of algorithm for constructing decision tree based on positive region are analyzed.Aiming at these disadvantages,a new algorithm for decision tree based on positive region and its classification ability is proposed.The method is simple and easy-to-understand.The example shows that the method is effective.

rough sets;decision tree;positive region;classification ability

TP183

A

1009-5152(2011)03-0057-03

2011-07-25

蔣慧平(1972- ),男,湖南網(wǎng)絡(luò)工程職業(yè)學(xué)院副教授。

猜你喜歡
粗糙集結(jié)點(diǎn)決策樹
基于八數(shù)碼問題的搜索算法的研究
基于Pawlak粗糙集模型的集合運(yùn)算關(guān)系
一種針對不均衡數(shù)據(jù)集的SVM決策樹算法
基于二進(jìn)制鏈表的粗糙集屬性約簡
決策樹和隨機(jī)森林方法在管理決策中的應(yīng)用
Ladyzhenskaya流體力學(xué)方程組的確定模與確定結(jié)點(diǎn)個數(shù)估計
多?;植诩再|(zhì)的幾個充分條件
基于決策樹的出租車乘客出行目的識別
雙論域粗糙集在故障診斷中的應(yīng)用
基于肺癌CT的決策樹模型在肺癌診斷中的應(yīng)用