叶枝分辨的决策树研究

刘 军

（南京工业大学 电子与信息工程学院，江苏 南京210009）

0 引 言

当前基于单划分属性建立决策树算法主要存在以下问题：基于信息增益的算法是一种局部优化策略［1－2］，当属性集中多个属性的信息增益相近时难以准确地确定出划分属性，且指数运算复杂度高；基于粗糙集［3］的决策树生成算法要经过属性约简和确定划分属性两个步骤［4－5］，属性约简存在多选性及难以准确保留有效属性的问题［6］，而且单以核属性强度确定划分属性并不能获得最佳效果，因为决策树优化是个全局问题，当前属性集中分辨最强的单个属性可能只是本集局部最优而非全局最优。如果要达到全局最优需要进行大量的预测计算，显然上述算法难以实现。为此提出了一种基于粒计算［7］的精准建树算法，该算法不仅考虑当前层中属性的分辨能力，而且预测其后续层中的分辨趋势。根据粒计算［7］理论，将每个属性按属性值划分为叶 （基本粒），每个条件属性叶对应的决策属性叶的种类个数称为枝，用这两个参数测定该条件属性粒的分辨力。条件属性的分辨力则由其各基本粒分辨力之和所决定，分辨力最高者为划分属性。由于粒计算的简洁性，对分辨力相近属性可以再计算比较其后续层的分辨力，最终得到最佳划分属性，这是一种全局判优的算法。另外，采用数据库SQL语言查询可以降低计算复杂度。由大量实例比较分析可知，该算法计算量较小且准确度较高。

1 理论及实现

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）｝。基本粒中相同值的记录数量称为粒值量 （叶重量），记为WAi（v），WAi（v）＝｛Count（xi∈U）｜（Ai，v）｝。Ai中包括基本粒的数量称为该属性的粒数量，记为N（Ai）。N（Ai）表示Ai可划分为几种叶子Ai（v）；而 WAi（v）表示一种叶子一次可分配的重量。

定义2 决策属性D中各取值相同部分也为一个基本粒，记为 （D，u），｛（D，u）｜u∈V｝。在决策表S的｛xi∈U｜（Ai，v）｝行集中存在的 （D，u）数量称为枝数量，记为SD（u），｛SD（u）＝ClassCount （xi∈U｜（Ai，v），u∈D）｝。SD（u）表示在 （Ai，v）约束的行集中，可接受WAi（v）分配的枝数量。

若干个基本粒（Ai，v）组成属性Ai，所以每个（Ai，v）对应于（D，u）的关系决定（Ai，v）分辨能力，Ai中所有（Ai，v）的分辨能力与N（Ai）又共同决定Ai的分辨能力，这就是叶枝粒比算法的主要理论依据。

例如在表2中，属性 A3中有5个基本粒（Ai，v）：（A3，3）、（A3，4）、（A3，5）、（A3，6）、（A3，8），N（A3）＝5。5个基本粒对应 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）对应的行集（U＝6，8）中D有1种粒（D＝2），所以其SD（2）＝1

WA3（4）对应的行集（U＝7）中D有1种粒（D＝1），所以其SD（1）＝1

WA3（5）对应的行集（U＝5，6）中D有2种粒（D＝4、3），所以其SD（4，3）＝2

WA3（6）对应的行集（U＝1，4）中D有2种粒（D＝5、1），所以其SD（5，1）＝2

WA3（8）对应的行集（U＝2，9）中D有1种粒（D＝3），所以其SD（3）＝1

1.2 实 现

最优树的标准是树叶（重量）大且树枝少，具体到基本粒（Ai，v）时，因为 WAi（v）是可分配的叶重量，而SD（u）是接受分配的枝个数，所以最优数应是WAi（v）值大且SD（u）小；具体到 Ai时，则是∑（WAi（v）／SD（u））大且 N（Ai）小。当（Ai，v）的分辨力确定后，Ai中各（Ai，v）的分辨力累加和即为Ai的分辨力，而｛An｝中分辨力最大者确定为划分属性。

WAi（v）和SD（u）两个参数决定了（Ai，v）的分辨能力，依据 WAi（v）和SD（u）可以推导出判别（Ai，v）分辨能力的一般式：若SD（u）＝1，经结点划分，（Ai，v）一次分辨出u∈D中的WAi（v）行，得叶结点1个，该叶的平均重量为WAi（v）／SD（u）＝WAi（v）／1＝WAi（v），枝个数为SD（u）＝1；若SD（u）＝2，一次结点划分后只得2个分区，至少要经二次结点划分得2个叶结点，平均叶重量为 WAi（v）／SD（u）＝WAi（v）／2，枝个数为 SD（u）（＝2）；依此，得（Ai，v）的平均叶重量及枝个数的一般式

为了判定按（Ai，v）划分后其后续层的分辨力，在｛xi∈U｜（Ai，v）｝所组成的行集中判出分辨力最强者代表（Ai，v）极大分辨力，即在｛xi∈U｜（Ai，v）｝行集中判出最优列。由于每列又由若干子粒组成（设共有m列），每列的叶枝量是其各子粒叶枝量之累加和：

而（Ai，v）的极大分辨力定为：

属性Ai∈｛An｝极大分辨力为其各基本粒之累加和：

属性Ai的分辨力由LwAi和BnAi及N（Ai）共同确定，其平均极大粒比为：

在｛An｝属性中平均极大叶枝粒比最大者即为划分属性：

当有多个Aj时（分辨力接近），则要根据树的层次上N（Ai）被分辨情况再次对多个Aj进行分辨（见2.2）。经Aj划分后得1个树结点，在Aj的各划分集中再按上述算法逐层进行择优，可得叶枝粒比最大，分辨力最强的决策树。

2 比较实例

2.1 与ID3［9－10］改进算法的比较

将文献［11］表1经等价标准化后见表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 标准化后的决策数据

通过上述比较可得最优列为A2列，即选其为（A1，2）的有效叶、枝量（Lw（A1，2）＝7，Bn（A1，2）＝3）。

类似地可得A1其它粒优选后的有效叶、枝量：（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）

属性按上述叶枝粒比，优选属性顺序为：A1、A2、A3、A4、A5、A6。

首选A1为划分属性，逐级择优划分为决策树：

此树共有18个枝（是文献［11］表1的最优决策树）。而首选A2划分则为20个枝；首选A3划分则为22个枝；首选A4划分则为25个枝；首选A5划分则为25个枝（深度比A4多一层）；首选A6划分则为26个枝，完全符合上述叶枝粒比的排优顺序。文献［11］中图1所示是以A2（view and arguments）为首选划分属性建树，比首选a（Topic）建树多了2个树枝，所以并非最优树。

2.2 与 C4.5算法［12］比较分析

文献［13］中的表1训练集（1～10行），因篇幅原因经相应等价后，只对分辨度较高的6个条件属性列表，见表2。

表2 标准化后的决策数据

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叶决策树，则要根据首层N（Ai）中被分辨出的情况进行再次分辨。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）越大则树越优，所以得首选顺序为A18、A21、A5、A15。

首选属性A18、A21、A5、A15之一都可得9枝7叶树，而首选属性A18则得最优树（首层叶最重）。将首选A18和A17（文献［14］算法）比较如下（→示树枝，D.k示树叶）：

首选A18和A17属性都为2层树，A18首层完全分辨出3个粒，总重量为6；而A17分辨出2个粒，总重量为4。A18为9枝7叶树；而首选A17只可得10枝8叶树。显然，虽然C4.5克服了ID3用信息增益选择属性时偏向取值多的属性，但确定划分属性的准确性仍不足。

2.3 与相对核的算法比较分析

文献［14］中表1经等价标准化后见表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）行集，最优列为 A3，WA1（0）／SD（0）＝1／1＝1，SD（0）＝1，记为（1，1）。

对（A3，1）行集，最优列为 A4，∑（WA4（0，1，2）／SD（u））＝（2／1＋3／1＋5／2）＝7.5，记为（7.5，5）。

对（A3，2）行集，最优列为 A5，∑（WA5（0，1，2）／SD（u））＝（1／1＋1／1＋3／2）＝3.5，记为（3.5，5）。

表3 标准化后的决策数据

所以，

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）行集，最 优列为 A3，∑ WA3（1，2）／SD（u）＝（3／1＋1／1）＝4，记为（4，3）。

对（A4，1）行集，最优列为 A5，∑（WA5（0，1，2）／SD（u））＝（1／1＋1／1＋8／2）＝6，记为（6，5）。

对（A4，2）行集，最优列为 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。

经ALB（Ai）（i＝3，4，5，6）比较可得单属性分辨强度顺序：A4、A5、A6、A3，证明以核属性作为首选划分属性并非可得最优树［14］。

3 结束语

本文以粒计算［7］为理论依据，提出以属性的叶枝粒比确定划分属性的算法：将属性划分为若干基本粒，以粒的叶枝比预测其划分后可能的最好情况代表该粒最强分辨能力，以属性中各基本粒的最强分辨能力之累加和作为该属性的最强分辨能力，而表中属性分辨能力最强者为划分属性。按划分属性建立结点，依此逐级递规划分得最优决策树。算法不涉及概率计算和指数对数复杂运算（信息增益算法）和属性约简复杂过程（粗糙集算法），具有准确度高、算法简洁的特点。

［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）. ［丁春荣，李龙澍，杨宝华.基于粗糙集的决策树构造算法 ［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）.［张凤莲，林健良.新的决策树构造方法 ［J］.计算机工程与应用，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］.计算机工程与设计，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］.计算机工程，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）.［巩固，黄永青，郝国生.决策树算法的优化研究 ［J］.计算机工程与应用，2010，46 （13）：139－141.］

［6］CHEN Xi，LEI Jian，FU 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］.计算机工程与设计，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］.计算机工程与应用，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］.计算机工程与应用，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）.［王永梅，胡学钢.决策树中ID3算法的研究 ［J］.安徽大学学报 （自然科学版），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）.［杨静，张楠男，李建，等.决策树算法的研究与应用 ［J］.计算机技术与发展，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］.计算机工程，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］. 软 件 学 报，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. ［张利，姚轶崭，彭建芬，等.基于决策树的智能信息安全风险评估方法 ［J］.清华大学学报 （自然科学版），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）.［陈世联，罗秋瑾.基于粗集和距离函数的决策树构造方 法 ［J］. 计 算 机 工 程 与 设 计，2008，29 （12）：3191－3193.］