基于粗糙分类度的决策树算法

1、基于粗糙分类度的决策树算法吴明泉1，刘童璇1，陈晓伟1（中国石油大学（华东）计算机与通信工程学院 东营 ）1摘 要 在构造决策树的过程中，属性分裂标准直接影响分类的效果。本文针对ID3算法对属性分类精度强调不足问题，基于粗糙集理论提出了粗糙分类度的概念，将粗糙分类度作为选择分离属性的标准。该方法充分考虑了属性分类精度对分类结果造成的影响，兼顾了条件属性与决策属性的依赖性。经实验证明，相比传统的基于信息熵方法构造的决策树，有效的提高了分类的准确率。关键词 分类精度；属性相关程度；粗糙集；决策树；信息增益中图分类号：TP182 文献标识码: AAn Algorithm for Decision T

2、ree Construction Based on Degree of Rough ClassificationZHANG Qiong-sheng 1, WU Ming-quan 1,LIU Tong-xuan1, CHEN Xiao-wei1,(College of Computer and Communication, China University of Petroleum, Dongying , China)1Abstract In the process of decision tree construction, property division standards direc

3、tly affect the classification results. Aimed at weakness of ID3 in nicety of grading, we provide the concept of degree of rough classification as select criteria of separation of property. The method took into account nicety of grading and dependency between condition attributes and decision attribu

4、tes. Compared with traditional decision tree based entropy, the experiment proved that the decision tree constructed in our method effectively improves the classification results.Keywords Classification Accuracy; Attribute Relevance; Rough Set; Decision Tree; Information Gain1 引言决策树学习是以示例学习为基础的归纳推理算

5、法，着眼于从一组无次序、无规则的事例推出决策树表示形式的规则。在解决分类问题的各种方法中，决策树方法是运用最广泛的一种，它采用自顶向下、分而治之的方法将搜索空间分为若干个互不相交的子集，形成一种类似于流程图的树状结构，这种方法速度快、易于转换成简单而便于理解的分类规则。ID32算法是一种基于信息熵的决策树学习算法，是决策树算法的代表，但是基于信息熵的方法只考虑了属性之间的互信息，即属性对决策结果的影响，而没有考虑构建决策树的分类精度，从而降低了分类的效率和效果。基金项目：中国石油化工股份有限公司基金项目（P02049）作者简介：张琼声(1968-),女,副教授,主要研究领域为软件工程、智能系统

6、，操作系统等；吴明泉（198？）男,硕士研究生,主要研究领域为操作系统、智能系统.刘童璇(1985-),男,硕士研究生,主要研究领域为操作系统.、软件工程。陈晓伟(1985-),女,硕士研究生,主要研究领域为专家系统、软件工程；E-mail：粗糙集理论是波兰数学家Z. Pawlak 在1982年提出的一种分析数据的数学理论，主要用来处理不确定和不精确信息。其特点是不需要预先给定某些特征和属性的数量描述，而是直接从给定问题的描述集合出发，找出该问题的内在规律，其基本思想更接近现实情况。现已有部分研究将粗集理论应用于决策树中，如文献1先对样本集进行属性约简，然后根

7、据核构建决策树，该方法构建的决策树通过使用属性约简后去除了噪声和冗余属性。文献6定义了分辨率，使用分辨率作为分裂属性的标准来构建决策树。文献7使用粗糙集中的属性分类粗糙度作为分裂属性的标准，根据属性分类粗糙度构建决策树，另外文中提出使用变精度粗糙集去除噪声的方法。文献89都使用了边界域作为分裂属性的标准，其中9为避免决策树过于细化而引入了抑制因子，当抑制因子小于一定值后，决策树不再扩展。文献12提出使用核属性和辨明矩阵来选择对分类贡献最大的属性。文献13中提出了使用决策属性对条件属性的依赖度作为启发信息来选择属性。本文提出使用粗糙分类度来构建决策树。基于粗糙分类度的决策树是以属性分类精度和条件

8、属性与决策属性的依赖性作为分裂属性的标准。属性的粗糙分类度越大，说明属性中包含的确定因素越多并且该属性与决策属性的依赖性更大。经过大量实例的分析，在分裂属性过程中，基于粗糙分类度的决策树算法所选属性的分类精度要优于ID3算法选择的具有最大信息增益的属性。通过实验与ID3算法进行比较，在生成规则数目略有增加的情况下，准确率有了明显提高，并具有稳定性。 2 粗糙集理论基础信息系统，其中：对象的有限集；：属性的有限集，：条件属性子集，：决策属性子集；：属性的值域，：属性的值域；是总函数，使得对每个，有。在信息系统中，设是个体全域上的子集，属性子集，则：的下近似集：的上近似集：的边界域：是上必然被分类

9、的那些元素的集合，是根据属性子集，中所有一定能归入集合的元素构成的集合，即包含在内的最大可定义集。是上可能被分类的那些元素的集合，是根据属性子集，中所有一定能和可能归入集合的元素构成的集合，即包含的最小可定义集合。 是既不能在上被分类，又不能在上被分类的那些元素的集合。集合的边界域越大，其确定程度越小。属性子集关于决策属性的正域定义为：关于的正域表示那些根据属性子集，中所有一定能归入集合的元素构成的集合。上的近似精度定义为：表示集合的基。近似精度体现了属性对集合分类的精确程度，对于一个属性来说，也就是正域中确定样本数目占边界域和正域总的分类样本的比率。条件属性子集与决策属性的相关程度（也称依赖

10、程度）定义为：其中，为属性子集与决策属性之间的相关程度。若，则完全依赖于；若，则部分依赖于；若，则完全独立于。3 基于粗糙分类度的决策树算法3.1 算法原理定义：信息系统，为对象的有限集，被划分为有限个样例子集，使得，。属性集，其中为条件属性集，为决策属性集。属性，则粗糙分类度定义为： 其中表明了属性对于每个决策属性集合得到的分类精度的和。值表明属性对决策属性分类后的样本集合的分类精度，值越大，即值越大，说明带来的不确定因素越少，分类的效果越好；反之，说明该属性集对的分类效果越不明显，即分类的不确定性越大。因而，表明了属性对所有集合分类精度的衡量。表示了的属性重要性度，值越大，表明属性集与决策

11、属性的相关程度越大。当属性集只有一个属性时，有下式成立：其中，。ID3 算法以属性之间的互信息最大作为选择属性的准则，属性之间的互信息越大。说明其依赖性越强。文献6中证明了属性间的互信息与的相容关系，对于一个信息系统，是保持不变的，因此，与互信息存在着相容关系，即能够很好的体现出属性对决策属性的依赖性。当时，说明或者。若，那么说明属性对分类无影响。若，即，故表明属性对决策属性分类后的样本集合的下近似集为0，说明属性的分类精度和下近似集均为0，则该属性对样本集的分类贡献为0。综合以上分析，我们使用粗糙分类度作为分裂属性的标准，既能够体现出属性分类精度保证构建的决策树分类高效，又兼顾了条件属性与决

12、策属性的依赖性使决策树分类更有效。3.2算法流程计算每个属性的作为属性分裂的标准，每次选择最大的属性为分裂属性，即对决策结果影响程度最大并且分类精度越高的属性作为分裂节点。基于粗糙分类度的决策树算法的具体建立步骤如下：输入：训练样本samples，由离散值属性表示，属性集合attribute_list； 输出：一棵判定树Generate_decision_tree (samples, attribute_list)。创建节点N如果 Samples都在同一类C，返回N作为叶节点，以类C标记如果 attribute_list为空， 返回N作为叶节点，用Samples中最普通的类标记计算attrib

13、ute_list中每个属性对应决策属性分类集合的上近似集、下近似集，若下近似集对应所有分类集合均为空，则计算attribute_list中每个属性的粗糙分类度选择attribute_list中具有最大的属性test_attribute 标记节点N为分裂属性test_attribute 对于每一个test_attribute中的已知值ai 由节点N长出一个条件为test_attribute= ai 的分支设si为Samples样本中test_attribute=ai 的集合如果si为空，加上一个树叶，用Samples中最普通的类标记。否则，加上一个由Generate_Decision _Tree

14、(Si,attribute_list-test_attribute)返回的节点上述建树过程是一个递归过程，其终止条件为：给定节点的所有样本属于同一类(步骤2)没有剩余属性可以进一步划分样本(步骤3)没有样本满足test_attribute = a(步骤10)3.3实例表1为从油田勘探数据库中选取的部分录井解释成果数据，选择其中重要的8个影响解释结论的属性构成条件属性集，一个决策属性，26个对象构成样本训练集。分别使用ID3和基于粗糙分类度的决策树算法构建决策树，在构建决策树之前已经对样本集连续数值进行了二值离散化。具体构建决策树的过程如下所示Table 1 Experimental data表

15、1 实验数据序号井号顶界深度p1底界深度p2甲烷基值p3乙烷基值p4正丁烷基值p5异丁烷基值p6甲烷异常值p7乙烷异常值p8解释结论1丰深103622362510.261.7360.2260.887.184.34油层2丰深10386438655.090.8150.0820.5125.950.885干层3丰深1039113916.53.030.4580.0310.11311.421.536干层4丰深103920.539340.0050.030.280.05油层5丰深103957396210.631.0390.2480.18216.571.657干层6丰深1041374138

16、14.791.1730.0810.319.822.111干层7丰深104169417117.641.5090.0960.30423.852.095干层8丰深104234.542377.30.9750.1310.48911.271.473干层9丰深104265.542020.1580.56410.481.165干层10丰深10426942757.520.6410.1580.7118.310.883干层11丰深6334733480.750.1420.0360.0991.760.389油层12丰深6346534680.240.0480.0250.0981.250.176干层13

17、丰深6350135031.740.1850.0180.0752.460.229油层14丰深6355035531.040.1370.0140.0754.270.533干层15丰深6355935622.620.3720.0210.08712.891.787油层16丰深6357235741.140.1630.0190.0767.50.92油层17丰深6365636600.480.0520.0080.0241.390.09干层18丰深6367936810.530.0590.0080.020.530.059干层19丰深6370337070.770.0690.0080.0190.770.069干层20丰深

18、6374037430.940.0470.010.0180.940.047干层21丰深6383738400.360.0260.0050.0110.930.074油层22丰深638563874.50.750.0590.0070.0181.060.075油层23丰深6387639340.40.0290.0050.0132.690.175干层24丰深6393639390.590.0550.0070.0191.670.134油层25丰深6394039560.710.060.0080.0210.890.083油层26丰深6398140230.140.0140.0040.0110.420.099干层1）使用

19、基于粗糙分类度的决策树算法构造决策树按决策属性“解释结论”分类的样本集合为：、首先计算每个属性对样本分类的上近似集和下近似集，然后计算和，最后得到。对属性=“乙烷异常值”和样本集合的上近似集和下近似集分别是：，。因此有，即，。同理得到其他属性的分别是：，。比较其中的最大，故第一个节点的属性为“乙烷异常值”。然后判断其每个分支下的集合，其中“3.2255”所对应样本集合的决策属性都在同一类，故已经到叶子节点。以此类推，计算“=3.2255”对应的子节点为“甲烷基值”。最后得到决策树，如图1所示：图1 基于粗糙分类度的决策树算法构造决策树图Fig. 1 Decision Tree based on

20、 Roughness Categories Decision Tree Algorithm2）使用ID3算法构建的决策树，如图2所示：图2 ID3构造决策树图Fig. 2 Decision Tree based on ID3 Decision Tree Algorithm比较基于粗糙分类度方法构建的决策树与ID3构建的决策树，首先根节点ID3选择了“甲烷基值”，基于粗糙分类度方法选择了“乙烷异常值”。由于ID3算法选择属性考虑的是属性对整个信息系统信息熵的减少量，也就是属性与决策属性的依赖性，而缺乏属性分类精度的比较。下面我们通过粗集理论中各个属性此时的分类精确度和属性依赖性这一标准，比较两种

21、算法在选择根节点时的区别和优劣。此时，根据决策属性得到的样本集合为：， 对应属性=“乙烷异常值”，根据前面的计算得知：属性的分类精度为：属性的依赖度为：对应属性=“甲烷基值”，得到样本集合的上近似集和下近似集分别是：，则属性的分类精度为：属性的依赖度为：故有，并且。从结果可以看出，无论从分类精度还是对决策属性的依赖性，选择属性“乙烷异常值”都要比选择属性“甲烷基值”更对分类有利。根据根节点计算的比较可以看出基于粗糙分类度的决策树分类精确度、依赖度结果都要优于ID3算法。4 实 验实验数据使用胜利油田勘探数据库数据，选用探井生产管理决策支持系统中的下套管决策过程构建决策树。下套管决策过程所需数据

22、包括测井数据和录井数据，其中测井数据记录每口井每个小层的测井属性数据及其测井解释结果；录井数据记录、录取钻井过程中的各种相关信息，主要包含气测综合录井解释成果数据、定量荧光分析数据、罐顶气评价成果数据等不同类别数据。下套管决策过程的目的是根据录井数据推理出每口井每个小层含油、气、水产状解释结果。实验选择了气测综合录井解释成果数据构建决策树。实验主要分为五个阶段：第一步，确定一口测试井，选取聚类属性，聚类求参考井。第二步，根据参考井，选取参考井在录井表中的小层属性数据，将参考井各小层的测井解释结果作为最后一列加入选出的录井小层数据，构成训练样本。第三步，根据训练样本，将测井解释结果作为决策属性，

23、使用决策树算法，建立决策树。第四步，根据已建好的决策树推理出If-Then决策规则。第五步，选取测试井小层在录井表中的属性数据，根据决策规则推理出测试井小层的决策结果。实验按以上步骤选取已完钻井的相关数据，把利用基于粗糙分类度的决策树算法、ID3算法获得的决策结果与数据库中已完钻井的实际解释结果数据相比较，以测试两种不同算法的平均准确率，验证利用基于粗糙分类度的决策树算法的改善决策准确度的有效性。实验结果如图3所示。图3 基于粗糙分类度的决策树算法实验测试结果Fig. 3 Experimental test results by Decision Tree Algorithm based on

24、 Roughness Categories图3中各字段的含义：井号即为测试井名，层位是测试井对应的段层，底界深度和顶界深度为段层中一个小层的底界和顶界，测井结果是测试井小层对应的正确解释结果，ID3算法和基于粗糙分类度的决策树算法分别是两种决策树算法推理出的分类结果。将两种算法推理出的结果与测井结果进行比较，与测井结果一致，说明推理正确。实验结果如表2所示。Table 2 Experimental results表2 实验结果ID3算法基于粗糙分类度的决策树算法测试井数目3636测试小层数目229229录井表数据总数12021202属性个数（条件属性/结论类别）25/625/6生成规则数目22

25、5273平均准确率62.38%65.35%由实验结果看出，基于粗糙分类度的决策树算法在生成规则的数目上来看要比ID3算法多，说明该算法构建的决策树相对复杂，但基于粗糙分类度的决策树算法比ID3算法的平均准确率高出3个百分点。实验经过反复测试，基于粗糙分类度决策树算法具有稳定性。5 结束语 本文设计了一个新的基于粗糙分类度的决策树生成算法。该算法在属性分裂上，既考虑了属性分类精度又兼顾了条件属性与决策属性的依赖性。经大量实例分析证明在兼顾依赖度的条件下，基于粗糙分类度的决策树算法在分类精度上优于ID3算法。实验中采用实际数据分析比较了该算法与ID3算法在准确率和生成规则数目的差别。结果表明，基于

26、粗糙分类度算法在生成规则的数目上多于ID3算法，但在准确率上优于ID3算法，并且具有稳定性。参 考 文 献吴成东，许可，韩中华，裴涛. 基于粗糙集和决策树的数据挖掘方法 J. 东北大学学报, 2006, 27(5): P481-484.QUINLAN J R. Induction of Decision Tree J. Machine Learning, 1986, P81106.ZDZISLAW P. Rough set theory J. Kunstliche Intelligenz, 2001, 5(3): P38-39.HU Keyun, LU Yunchang, SHI Chunyi

27、. Feature ranking in rough sets J. AI Communications, 2003 16: P41-50.王国胤. Rough集理论与知识获取 M. 西安:交通大学出版社. 2001.赵卫东，盛昭瀚，何建敏. 粗糙集在决策树生成中的应用 J. 东南大学学报, 2000, 30(4): P132-137.乔梅，韩文秀. 基于Rough集的决策树算法 J. 天津大学学报, 2005, 38(9): P842-846.高静, 徐章艳, 宋 威, 杨炳儒. 一种新的基于粗糙集模型的决策树算法 J. 计算机工程, 2008, 34(3): P9-11.WEI Jinma

28、o. Rough Set based Approach to Selection of Node J. International Journal of Computational Cognition, 2003, 1(2): P25-40.WEI Jinmao, HUANG Dao, WANG Shuqin. Rough Set based Decision Tree C. Proceedings of the 4th World Congress on Intelligent Control and Automation (VCICA), Shanghai, China: IEEE, Jan, 2002: P426-431.BLEYBERG M Z, ELUMALAI A. Using Rough Sets to Construct Sense Type Decision Trees for Text Categorization C.