葉枝分辨的決策樹研究

劉 軍

（南京工業(yè)大學(xué) 電子與信息工程學(xué)院，江蘇 南京210009）

0 引 言

當(dāng)前基于單劃分屬性建立決策樹算法主要存在以下問題：基于信息增益的算法是一種局部優(yōu)化策略［1－2］，當(dāng)屬性集中多個屬性的信息增益相近時難以準(zhǔn)確地確定出劃分屬性，且指數(shù)運(yùn)算復(fù)雜度高；基于粗糙集［3］的決策樹生成算法要經(jīng)過屬性約簡和確定劃分屬性兩個步驟［4－5］，屬性約簡存在多選性及難以準(zhǔn)確保留有效屬性的問題［6］，而且單以核屬性強(qiáng)度確定劃分屬性并不能獲得最佳效果，因?yàn)闆Q策樹優(yōu)化是個全局問題，當(dāng)前屬性集中分辨最強(qiáng)的單個屬性可能只是本集局部最優(yōu)而非全局最優(yōu)。如果要達(dá)到全局最優(yōu)需要進(jìn)行大量的預(yù)測計(jì)算，顯然上述算法難以實(shí)現(xiàn)。為此提出了一種基于粒計(jì)算［7］的精準(zhǔn)建樹算法，該算法不僅考慮當(dāng)前層中屬性的分辨能力，而且預(yù)測其后續(xù)層中的分辨趨勢。根據(jù)粒計(jì)算［7］理論，將每個屬性按屬性值劃分為葉 （基本粒），每個條件屬性葉對應(yīng)的決策屬性葉的種類個數(shù)稱為枝，用這兩個參數(shù)測定該條件屬性粒的分辨力。條件屬性的分辨力則由其各基本粒分辨力之和所決定，分辨力最高者為劃分屬性。由于粒計(jì)算的簡潔性，對分辨力相近屬性可以再計(jì)算比較其后續(xù)層的分辨力，最終得到最佳劃分屬性，這是一種全局判優(yōu)的算法。另外，采用數(shù)據(jù)庫SQL語言查詢可以降低計(jì)算復(fù)雜度。由大量實(shí)例比較分析可知，該算法計(jì)算量較小且準(zhǔn)確度較高。

1 理論及實(shí)現(xiàn)

1.1 理 論

決策表［7］S＝（U， ｛An｝，D，V）， ｛An｝為條件屬性集，D為決策屬性，U＝｛x1，x2，…，xm｝是論域，V是屬性值集。

定義1 條件屬性Ai中各取值相同部分為一個基本粒［7－8］，記為 （Ai，v）， ｛（Ai，v）｜Ai∈｛An｝，v∈V）｝?；玖Ｖ邢嗤档挠涗洈?shù)量稱為粒值量 （葉重量），記為WAi（v），WAi（v）＝｛Count（xi∈U）｜（Ai，v）｝。Ai中包括基本粒的數(shù)量稱為該屬性的粒數(shù)量，記為N（Ai）。N（Ai）表示Ai可劃分為幾種葉子Ai（v）；而 WAi（v）表示一種葉子一次可分配的重量。

定義2 決策屬性D中各取值相同部分也為一個基本粒，記為 （D，u），｛（D，u）｜u∈V｝。在決策表S的｛xi∈U｜（Ai，v）｝行集中存在的 （D，u）數(shù)量稱為枝數(shù)量，記為SD（u），｛SD（u）＝ClassCount （xi∈U｜（Ai，v），u∈D）｝。SD（u）表示在 （Ai，v）約束的行集中，可接受WAi（v）分配的枝數(shù)量。

若干個基本粒（Ai，v）組成屬性Ai，所以每個（Ai，v）對應(yīng)于（D，u）的關(guān)系決定（Ai，v）分辨能力，Ai中所有（Ai，v）的分辨能力與N（Ai）又共同決定Ai的分辨能力，這就是葉枝粒比算法的主要理論依據(jù)。

例如在表2中，屬性 A3中有5個基本粒（Ai，v）：（A3，3）、（A3，4）、（A3，5）、（A3，6）、（A3，8），N（A3）＝5。5個基本粒對應(yīng) WAi（v）分別是：｛WA3（3）＝2｜（U＝3，8）｝，｛WA3（4）＝1｜（U＝7）｝，｛WA3（5）＝3｜（U＝5，6，10）｝，｛WA3（6）＝2｜（U＝1，4）｝，｛WA3（8）＝2｜（U＝2，9）｝。

WA3（3）對應(yīng)的行集（U＝6，8）中D有1種粒（D＝2），所以其SD（2）＝1

WA3（4）對應(yīng)的行集（U＝7）中D有1種粒（D＝1），所以其SD（1）＝1

WA3（5）對應(yīng)的行集（U＝5，6）中D有2種粒（D＝4、3），所以其SD（4，3）＝2

WA3（6）對應(yīng)的行集（U＝1，4）中D有2種粒（D＝5、1），所以其SD（5，1）＝2

WA3（8）對應(yīng)的行集（U＝2，9）中D有1種粒（D＝3），所以其SD（3）＝1

1.2 實(shí) 現(xiàn)

最優(yōu)樹的標(biāo)準(zhǔn)是樹葉（重量）大且樹枝少，具體到基本粒（Ai，v）時，因?yàn)?WAi（v）是可分配的葉重量，而SD（u）是接受分配的枝個數(shù)，所以最優(yōu)數(shù)應(yīng)是WAi（v）值大且SD（u）??；具體到 Ai時，則是∑（WAi（v）／SD（u））大且 N（Ai）小。當(dāng)（Ai，v）的分辨力確定后，Ai中各（Ai，v）的分辨力累加和即為Ai的分辨力，而｛An｝中分辨力最大者確定為劃分屬性。

WAi（v）和SD（u）兩個參數(shù)決定了（Ai，v）的分辨能力，依據(jù) WAi（v）和SD（u）可以推導(dǎo)出判別（Ai，v）分辨能力的一般式：若SD（u）＝1，經(jīng)結(jié)點(diǎn)劃分，（Ai，v）一次分辨出u∈D中的WAi（v）行，得葉結(jié)點(diǎn)1個，該葉的平均重量為WAi（v）／SD（u）＝WAi（v）／1＝WAi（v），枝個數(shù)為SD（u）＝1；若SD（u）＝2，一次結(jié)點(diǎn)劃分后只得2個分區(qū)，至少要經(jīng)二次結(jié)點(diǎn)劃分得2個葉結(jié)點(diǎn)，平均葉重量為 WAi（v）／SD（u）＝WAi（v）／2，枝個數(shù)為 SD（u）（＝2）；依此，得（Ai，v）的平均葉重量及枝個數(shù)的一般式

為了判定按（Ai，v）劃分后其后續(xù)層的分辨力，在｛xi∈U｜（Ai，v）｝所組成的行集中判出分辨力最強(qiáng)者代表（Ai，v）極大分辨力，即在｛xi∈U｜（Ai，v）｝行集中判出最優(yōu)列。由于每列又由若干子粒組成（設(shè)共有m列），每列的葉枝量是其各子粒葉枝量之累加和：

而（Ai，v）的極大分辨力定為：

屬性Ai∈｛An｝極大分辨力為其各基本粒之累加和：

屬性Ai的分辨力由LwAi和BnAi及N（Ai）共同確定，其平均極大粒比為：

在｛An｝屬性中平均極大葉枝粒比最大者即為劃分屬性：

當(dāng)有多個Aj時（分辨力接近），則要根據(jù)樹的層次上N（Ai）被分辨情況再次對多個Aj進(jìn)行分辨（見2.2）。經(jīng)Aj劃分后得1個樹結(jié)點(diǎn)，在Aj的各劃分集中再按上述算法逐層進(jìn)行擇優(yōu)，可得葉枝粒比最大，分辨力最強(qiáng)的決策樹。

2 比較實(shí)例

2.1 與ID3［9－10］改進(jìn)算法的比較

將文獻(xiàn)［11］表1經(jīng)等價標(biāo)準(zhǔn)化后見表1，對屬性A1（Topic）共包括3個粒：（A1，2），（A1，3），（A1，4）。其中（A1，2）的劃分集為 U＝｛6，8，12，13，18，19，22｝，被排序至表1的前7行，記為S（A1，2）。

在S（A1，2）中對A1列：

WA1（2）／SD（1，2）＝7／2＝3.5；SD（1，2）＝2；記為（3.5，2）。

對A2列：

∑（WA2（1，2，3）／SD（1，2））＝WA2（1）／SD（1）＋WA2（2）／SD（2）＋WA2（3）／SD（2）＝3／1＋2／1＋2／1＝7；

∑SD（1，2）＝1＋1＋1＝3；記為（7，3）。

同理可得，A3列：（5.5，4）；A4列：（5，5）；A5列：（4.5，4）；A6列：（4，5）。

表1 標(biāo)準(zhǔn)化后的決策數(shù)據(jù)

通過上述比較可得最優(yōu)列為A2列，即選其為（A1，2）的有效葉、枝量（Lw（A1，2）＝7，Bn（A1，2）＝3）。

類似地可得A1其它粒優(yōu)選后的有效葉、枝量：（Lw（A1，3）＝7，Bn（A1，3）＝5）；

則A1平均極大葉枝粒比為ALB（A1）＝20／13＝1.5

類似上述過程得A2、A3、A4、A5和A6的平均極大葉枝粒比分別為：

所以 Max（ALB（Ai））（1，2，3，4，5，6）＝ALB（A1）

屬性按上述葉枝粒比，優(yōu)選屬性順序?yàn)椋篈1、A2、A3、A4、A5、A6。

首選A1為劃分屬性，逐級擇優(yōu)劃分為決策樹：

此樹共有18個枝（是文獻(xiàn)［11］表1的最優(yōu)決策樹）。而首選A2劃分則為20個枝；首選A3劃分則為22個枝；首選A4劃分則為25個枝；首選A5劃分則為25個枝（深度比A4多一層）；首選A6劃分則為26個枝，完全符合上述葉枝粒比的排優(yōu)順序。文獻(xiàn)［11］中圖1所示是以A2（view and arguments）為首選劃分屬性建樹，比首選a（Topic）建樹多了2個樹枝，所以并非最優(yōu)樹。

2.2 與 C4.5算法［12］比較分析

文獻(xiàn)［13］中的表1訓(xùn)練集（1～10行），因篇幅原因經(jīng)相應(yīng)等價后，只對分辨度較高的6個條件屬性列表，見表2。

表2 標(biāo)準(zhǔn)化后的決策數(shù)據(jù)

A3有5個粒（A3，3），（A3，4），（A3，5），（A3，6），（A3，8）。參見2.1的算法，對于（A3，3）有（Lw（A3，3）＝2，Bn（A3，3）＝1）；對于（A3，4）有（1，1）；對于（A3，5）有（3，4）；對于（A3，6）有（2，3）；對于（A3，8）有（2，1）。

LwA3＝∑LwA3v＝∑（WA3（v）／SD（u））＝2＋1＋3＋2＋2＝10；BnA1＝（∑SD（u）｜LWA1）＝1＋1＋4＋3＋1＝10。

則A3平均極大葉枝粒比為ALB（A3）＝10／10＝1。

A5有3個粒（A5，1），（A5，2），（A5，3）。對于（A5，1）有（Lw（A5，1）＝3，Bn（A5，1）＝3）；對于（A5，2）有（5，5）；對于（A5，3）有（2，1）。

LwA5＝∑LwA5v＝∑（WA5（v）／SD（u））＝3＋5＋3＝10；BnA5＝（∑SD（u）｜LWA5）＝3＋5＋1＝9。

則A5平均極大葉枝粒比為 ALB（A5）＝10／9＝1.1

同理，

所以 Max（ALB（Ai））（3，5，6，15，17，18，21）＝ALB（A5）∪ALB（A15）∪ALB（A18）∪ALB（A21）

由于A5、A15、A18、A21分辨力相同，都可得9枝7葉決策樹，則要根據(jù)首層N（Ai）中被分辨出的情況進(jìn)行再次分辨。A5首層完全分辨出1個粒（A5，3），其WA5（3）＝2；A15首層分辨出1個粒（A15，6），其 WA15（6）＝1；A18首分出3個粒（A18，2）、（A18，3）、（A18，9），其∑WA18（v）＝2＋3＋1＝6；A21首分出5個粒，其∑WA21（v）＝5。由于首層分辨出的 WAi（v）越大則樹越優(yōu)，所以得首選順序?yàn)锳18、A21、A5、A15。

首選屬性A18、A21、A5、A15之一都可得9枝7葉樹，而首選屬性A18則得最優(yōu)樹（首層葉最重）。將首選A18和A17（文獻(xiàn)［14］算法）比較如下（→示樹枝，D.k示樹葉）：

首選A18和A17屬性都為2層樹，A18首層完全分辨出3個粒，總重量為6；而A17分辨出2個粒，總重量為4。A18為9枝7葉樹；而首選A17只可得10枝8葉樹。顯然，雖然C4.5克服了ID3用信息增益選擇屬性時偏向取值多的屬性，但確定劃分屬性的準(zhǔn)確性仍不足。

2.3 與相對核的算法比較分析

文獻(xiàn)［14］中表1經(jīng)等價標(biāo)準(zhǔn)化后見表3，表中的屬性A3中共包括3個粒：（A3，0），（A3，1），（A3，2）。在表3各基本粒的劃分集中求Lw（A1，v）和Bn（Ai，v），其中v＝0，1，2。

A3有5個粒（A3，0），（A3，1），（A3，2）。

對（A3，0）行集，最優(yōu)列為 A3，WA1（0）／SD（0）＝1／1＝1，SD（0）＝1，記為（1，1）。

對（A3，1）行集，最優(yōu)列為 A4，∑（WA4（0，1，2）／SD（u））＝（2／1＋3／1＋5／2）＝7.5，記為（7.5，5）。

對（A3，2）行集，最優(yōu)列為 A5，∑（WA5（0，1，2）／SD（u））＝（1／1＋1／1＋3／2）＝3.5，記為（3.5，5）。

表3 標(biāo)準(zhǔn)化后的決策數(shù)據(jù)

所以，

LwA3＝∑LwA3v＝∑（WA3（v）／SD（u））＝1＋7.5＋3.5＝12，BnA3＝（∑SD（u）｜LWA3）＝1＋5＋5＝11，則A3平均極大葉枝粒比為 ALB（A3）＝12／11＝1.09。

對（A4，0）行集，最 優(yōu)列為 A3，∑ WA3（1，2）／SD（u）＝（3／1＋1／1）＝4，記為（4，3）。

對（A4，1）行集，最優(yōu)列為 A5，∑（WA5（0，1，2）／SD（u））＝（1／1＋1／1＋8／2）＝6，記為（6，5）。

對（A4，2）行集，最優(yōu)列為 A4，WA4（2）／SD（u））＝2／1＝2，記為（2，1）。

所以，

LwA4＝∑LwA4v＝∑（WA4（v）／SD（u））＝4＋6＋2＝12，BnA4＝（∑SD（u）｜LWA4）＝3＋5＋1＝9。

則A4平均極大葉枝粒比為 ALB（A4）＝12／9＝1.33。

類似地，LwA5＝2＋2＋4＋1＋1＝10，BnA5＝6＋1＋1＝8，ALB（A5）＝10／8＝1.25。

LwA6＝2＋4＋2＋1＋1＝10＝10，BnA6＝1＋1＋6＝8，ALB（A5）＝10／8＝1.25。

經(jīng)ALB（Ai）（i＝3，4，5，6）比較可得單屬性分辨強(qiáng)度順序：A4、A5、A6、A3，證明以核屬性作為首選劃分屬性并非可得最優(yōu)樹［14］。

3 結(jié)束語

本文以粒計(jì)算［7］為理論依據(jù)，提出以屬性的葉枝粒比確定劃分屬性的算法：將屬性劃分為若干基本粒，以粒的葉枝比預(yù)測其劃分后可能的最好情況代表該粒最強(qiáng)分辨能力，以屬性中各基本粒的最強(qiáng)分辨能力之累加和作為該屬性的最強(qiáng)分辨能力，而表中屬性分辨能力最強(qiáng)者為劃分屬性。按劃分屬性建立結(jié)點(diǎn)，依此逐級遞規(guī)劃分得最優(yōu)決策樹。算法不涉及概率計(jì)算和指數(shù)對數(shù)復(fù)雜運(yùn)算（信息增益算法）和屬性約簡復(fù)雜過程（粗糙集算法），具有準(zhǔn)確度高、算法簡潔的特點(diǎn)。

［1］DING Chunrong，LI Longshu，YANG Baohua.Decision tree constructing algorithm based on rough set ［J］.Computer Engineering，2010，36 （11）：75－77 （in Chinese）. ［丁春榮，李龍澍，楊寶華.基于粗糙集的決策樹構(gòu)造算法 ［J］.計(jì)算機(jī)工程，2010，36 （11）：75－77.］

［2］ZHANG Fenglian，LIN Jianliang.New method of building decision tree ［J］.Computer Engineering and Applications，2009，45 （10）：141－143 （in Chinese）.［張鳳蓮，林健良.新的決策樹構(gòu)造方法 ［J］.計(jì)算機(jī)工程與應(yīng)用，2009，45（10）：141－143.］

［3］XU Fen，JIANG Yun，WANG Yong，et al.Improved algorithm for attribute reduction based on rough sets and information gain ［J］.Computer Engineering and Design，2009，30（24）：5698－5700 （in Chinese）. ［徐分，蔣蕓，王勇，等.基于粗糙集和信息增益的屬性約簡改進(jìn)方法 ［J］.計(jì)算機(jī)工程與設(shè)計(jì)，2009，30 （24）：5698－5700.］

［4］GAO Jing，XU Zhangyan，SONG Wei，et al.New decision tree algorithm based on rough set model ［J］.Computer Engineering，2008，34 （3）：9－11 （in Chinese）. ［高靜，徐章艷，宋威，等.一種新的基于粗糙集模型的決策樹算法 ［J］.計(jì)算機(jī)工程，2008，34 （3）：9－11.］

［5］GONG Gu，HUANG Yongqing，HAO Guosheng.Analysis and improved implementation of decision tree algorithms ［J］.Computer Engineering and Applications，2010，46 （13）：139－141（in Chinese）.［鞏固，黃永青，郝國生.決策樹算法的優(yōu)化研究 ［J］.計(jì)算機(jī)工程與應(yīng)用，2010，46 （13）：139－141.］

［6］CHEN Xi，LEI Jian，F(xiàn)U Ming.Attribute reduction algorithm for rough set based on improving genetic algorithm ［J］.Computer Engineering and Design，2010，31 （3）：602－607 （in Chinese）.［陳曦，雷健，傅明.基于改進(jìn)遺傳算法的粗糙集屬性約簡算法 ［J］.計(jì)算機(jī)工程與設(shè)計(jì)，2010，31 （3）：602－607.］

［7］XU Jiucheng，SHI Jinling，CHENG Wanli.Algorithm for decision rules extraction based on granular computing ［J］.Com－puter Engineering and Applications，2009，45 （25）：132－134（in Chinese）.［徐久成，史進(jìn)玲，成萬里.粒計(jì)算中決策規(guī)則的提取 ［J］.計(jì)算機(jī)工程與應(yīng)用，2009，45 （25）：132－134.］

［8］LI Hong，MA Xiaoping.Research on feature and formal representation of granule ［J］.Computer Engineering and Applications，2011，47 （11）：3－6 （in Chinese）.［李鴻，馬小平.粒的特征及形式化表示研究 ［J］.計(jì)算機(jī)工程與應(yīng)用，2011，47（11）：3－6.］

［9］WANG Yongmei，HU Xuegang.Research of ID3algorithm in decision tree ［J］.Journal of Anhui University（Natural Science Edition），2011，35 （3）：71－75 （in Chinese）.［王永梅，胡學(xué)鋼.決策樹中ID3算法的研究 ［J］.安徽大學(xué)學(xué)報 （自然科學(xué)版），2011，35 （3）：71－75.］

［10］YANG Jing，ZHANG Nannan，LI Jian，et al.Research and application of decision tree algorithm ［J］.Computer Technology and Development，2010，20 （2）：114－120 （in Chinese）.［楊靜，張楠男，李建，等.決策樹算法的研究與應(yīng)用 ［J］.計(jì)算機(jī)技術(shù)與發(fā)展，2010，20 （2）：114－120.］

［11］ZHANG Lin，CHEN Yan，LI Taoying，et al.Research on decision tree classification algorithms ［J］.Computer Engineering，2011，37 （13）：66－70 （in Chinese）. ［張琳，陳燕，李桃迎，等.決策樹分類算法研究 ［J］.計(jì)算機(jī)工程，2011，37 （13）：66－70.］

［12］XU Peng，LIN Sen.Internet traffic classification using C4.5 decision tree ［J］.Journal of Software，2009，20 （10）：2692－2704 （in Chinese）.［徐鵬，林森.基于 C4.5決策樹的流 量 分 類 方 法 ［J］. 軟 件 學(xué) 報，2009，20 （10）：2692－2704.］

［13］ZHANG Li，YAO Yizhan，PENG Jianfen，et al.Intelligent information security risk assessment based on a decision tree algorithm ［J］.Journal of Tsinghua University （Science and Technology），2011，51 （10）：1236－1239. ［張利，姚軼嶄，彭建芬，等.基于決策樹的智能信息安全風(fēng)險評估方法 ［J］.清華大學(xué)學(xué)報 （自然科學(xué)版），2011，51 （10）：1236－1239.］

［14］CHEN Shilian，LUO Qiujin.Decision tree construction method based on rough set and distance function ［J］.Computer Engineering and Design，2008，29 （12）：3191－3193 （in Chinese）.［陳世聯(lián)，羅秋瑾.基于粗集和距離函數(shù)的決策樹構(gòu)造方 法 ［J］. 計(jì) 算 機(jī) 工 程 與 設(shè) 計(jì)，2008，29 （12）：3191－3193.］