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

科学技术与工程基于粗糙分类度的决策树算法吴明泉1，刘童璇1，陈晓伟1（中国石油大学（华东）计算机与通信工程学院东营257061）1摘要在构造决策树的过程中，属性分裂标准直接影响分类的效果。本文针对ID3算法对属性分类精度强调不足问题，基于粗糙集理论提出了粗糙分类度的概念，将粗糙分类度作为选择分离属性的标准。该方法充分考虑了属性分类精度对分类结果造成的影响，兼顾了条件属性与决策属性的依赖性。经实验证明，相比传统的基于信息熵方法构造的决策树，有效的提高了分类的准确率。关键词分类精度；属性相关程度；粗糙集；决策树；信息增益中图分类号：TP182文献标识码:AAnAlgorithmforDecisionTreeConstructionBasedonDegreeofRoughClassificationZHANGQiong-sheng1,WUMing-quan1,LIUTong-xuan1,CHENXiao-wei1,(CollegeofComputerandCommunication,ChinaUniversityofPetroleum,Dongying257061,China)1AbstractIntheprocessofdecisiontreeconstruction,propertydivisionstandardsdirectlyaffecttheclassificationresults.AimedatweaknessofID3innicetyofgrading,weprovidetheconceptofdegreeofroughclassificationasselectcriteriaofseparationofproperty.Themethodtookintoaccountnicetyofgradinganddependencybetweenconditionattributesanddecisionattributes.Comparedwithtraditionaldecisiontreebasedentropy,theexperimentprovedthatthedecisiontreeconstructedinourmethodeffectivelyimprovestheclassificationresults.KeywordsClassificationAccuracy;AttributeRelevance;RoughSet;DecisionTree;InformationGain1引言决策树学习是以示例学习为基础的归纳推理算法，着眼于从一组无次序、无规则的事例推出决策树表示形式的规则。在解决分类问题的各种方法中，决策树方法是运用最广泛的一种，它采用自顶向下、分而治之的方法将搜索空间分为若干个互不相交的子集，形成一种类似于流程图的树状结构，这种方法速度快、易于转换成简单而便于理解的分类规则。ID3[2]算法是一种基于信息熵的决策树学习算法，是决策树算法的代表，但是基于信息熵的方法只考虑了属性之间的互信息，即属性对决策结果的影响，而没有考虑构建决策树的分类精度，从而降低了分类的效率和效果。基金项目：中国石油化工股份有限公司基金项目（P02049）作者简介：张琼声(1968-),女,副教授,主要研究领域为软件工程、智能系统，操作系统等；吴明泉（198？）男,硕士研究生,主要研究领域为操作系统、智能系统.刘童璇(1985-),男,硕士研究生,主要研究领域为操作系统.、软件工程。陈晓伟(1985-),女,硕士研究生,主要研究领域为专家系统、软件工程；E-mail：[e-mail]粗糙集理论是波兰数学家Z.Pawlak在1982年提出的一种分析数据的数学理论，主要用来处理不确定和不精确信息。其特点是不需要预先给定某些特征和属性的数量描述，而是直接从给定问题的描述集合出发，找出该问题的内在规律，其基本思想更接近现实情况。现已有部分研究将粗集理论应用于决策树中，如文献[1]先对样本集进行属性约简，然后根据核构建决策树，该方法构建的决策树通过使用属性约简后去除了噪声和冗余属性。文献[6]定义了分辨率，使用分辨率作为分裂属性的标准来构建决策树。文献[7]使用粗糙集中的属性分类粗糙度作为分裂属性的标准，根据属性分类粗糙度构建决策树，另外文中提出使用变精度粗糙集去除噪声的方法。文献[8][9]都使用了边界域作为分裂属性的标准，其中[9]为避免决策树过于细化而引入了抑制因子，当抑制因子小于一定值后，决策树不再扩展。文献[12]提出使用核属性和辨明矩阵来选择对分类贡献最大的属性。文献[13]中提出了使用决策属性对条件属性的依赖度作为启发信息来选择属性。本文提出使用粗糙分类度来构建决策树。基于粗糙分类度的决策树是以属性分类精度和条件属性与决策属性的依赖性作为分裂属性的标准。属性的粗糙分类度越大，说明属性中包含的确定因素越多并且该属性与决策属性的依赖性更大。经过大量实例的分析，在分裂属性过程中，基于粗糙分类度的决策树算法所选属性的分类精度要优于ID3算法选择的具有最大信息增益的属性。通过实验与ID3算法进行比较，在生成规则数目略有增加的情况下，准确率有了明显提高，并具有稳定性。2粗糙集理论基础信息系统{,,,}SUQVf，其中U：对象的有限集；Q：属性的有限集QCD，C：条件属性子集，D：决策属性子集；V：属性的值域，Vp：属性p的值域；:fUAV是总函数，使得对每个,XUqAi，有(,)ifXqVq。在信息系统{,,,}SUQVf中，设XU是个体全域上的子集，属性子集PQ，则：X的下近似集：{/:}PXYUPYXX的上近似集：{/:}PXYUPYXX的边界域：()BndXPXPXPPX是XU上必然被分类的那些元素的集合，是根据属性子集P，U中所有一定能归入集合X的元素构成的集合，即包含在X内的最大可定义集。PX是U上可能被分类的那些元素的集合，是根据属性子集P，U中所有一定能和可能归入集合X的元素构成的集合，即包含X的最小可定义集合。()BndXP是既不能在XU上被分类，又不能在UX上被分类的那些元素的集合。集合X的边界域()BndXP越大，其确定程度越小。属性子集P关于决策属性D的正域定义为：(){:}POSDPXXDPP关于D的正域()POSDP表示那些根据属性子集P，U中所有一定能归入集合X的元素构成的集合。S上X的近似精度定义为：()()()()(())()()()XcardPXcardPXPXPcardBndXcardPXXcardPXpPcard表示集合的基。近似精度体现了属性P对集合X分类的精确程度，对于一个属性来说，也就是正域中确定样本数目占边界域和正域总的分类样本的比率。条件属性子集PC与决策属性D的相关程度（也称依赖程度）定义为：(())(,)()cardPOSDPKPDcardU其中，0(,)1KPD，(,)KPD为属性子集P与决策属性D之间的相关程度。若(,)1KPD，则D完全依赖于P；若0(,)1KPD，则D部分依赖于P；若(,)0KPD，则D完全独立于P。3基于粗糙分类度的决策树算法3.1算法原理定义：信息系统{,,,}SUQVf，U为对象的有限集，被划分为有限个样例子集,,,12XXXm，使得XUi，Xi，XXijij，,1,2,,ijm，1mXUii。QCD属性集，其中C为条件属性集，D为决策属性集。属性pPC，则粗糙分类度定义为：(,,)(,)*()1mCSDpCDKPDXPii其中()1mXpii表明了属性p对于每个决策属性集合得到的分类精度的和。()Xpi值表明属性p对决策属性分类后的样本集合Xi的分类精度，()Xpi值越大，即()(())()cardPXicardBndXcardPXiip值越大，说明()BndXpi带来的不确定因素越少，分类的效果越好；反之，说明该属性集对Xi的分类效果越不明显，即分类的不确定性越大。因而，()1mXpii表明了属性p对所有集合分类精度的衡量。(,)KPD表示了P的属性重要性度，(,)KPD值越大，表明属性集P与决策属性D的相关程度越大。当属性集P只有一个属性p时，有下式成立：()(())1(,)()()mcardpXcardPOSDiiPkPDcardUcardU其中，1,2,,im。ID3算法以属性之间的互信息最大作为选择属性的准则，属性之间的互信息越大。说明其依赖性越强。文献[6]中证明了属性间的互信息与(())cardPOSDP的相容关系，对于一个信息系统S，()cardU是保持不变的，因此，(,)KPD与互信息存在着相容关系，即(,)KPD能够很好的体现出属性p对决策属性的依赖性。当(,,)0CSDpCD时，说明(,)0KPD或者()01mXipi。若(,)0KPD，那么说明属性p对分类无影响。若()01mXipi，即()0Xip，故表明属性p对决策属性分类后的样本集合Xi的下近似集为0，说明属性的分类精度和下近似集均为0，则该属性对样本集的分类贡献为0。综合以上分析，我们使用粗糙分类度(,,)CSDpCD作为分裂属性的标准，既能够体现出属性分类精度保证构建的决策树分类高效，又兼顾了条件属性与决策属性的依赖性使决策树分类更有效。3.2算法流程计算每个属性的(,,)CSDpCD作为属性分裂的标准，每次选择(,,)CSDpCD最大的属性为分裂属性，即对决策结果影响程度最大并且分类精度越高的属性作为分裂节点。基于粗糙分类度的决策树算法的具体建立步骤如下：输入：训练样本samples，由离散值属性表示，属性集合attribute_list；输出：一棵判定树Generate_decision_tree(samples,attribute_list)。创建节点N如果Samples都在同一类C，返回N作为叶节点，以类C标记如果attribute_list为空，返回N作为叶节点，用Samples中最普通的类标记计算attribute_list中每个属性对应决策属性分类集合的上近似集、下近似集，若下近似集对应所有分类集合均为空，则(,,)0CSDpCD计算attribute_list中每个属性的粗糙分类度(,,)CSDpCD选择attribute_list中具有最大(,,)CSDpCD的属性test_attribute标记节点N为分裂属性test_attribute对于每一个test_attribute中的已知值ai由节点N长出一个条件为test_attribute=ai的分支设si为Samples样本中test_attribute=ai的集合如果si为空，加上一个树叶，用Samples中最普通的类标记。否则，加上一个由Generate_Decision_Tree(Si,attribute_list-test_attribute)返回的节点上述建树过程是一个递归过程，其终止条件为：给定节点的所有样本属于同一类(步骤2)没有剩余属性可以进一步划分样本(步骤3)没有样本满足test_attribute=a(步骤10)3.3实例表1为从油田勘探数据库中选取的部分录井解释成果数据，选择其中重要的8个影响解释结论的属性构成条件属性集，一个决策属性，26个对象构成样本训练集。分别使用ID3和基于粗糙分类度的决策树算法构建决策树，在构建决策树之前已经对样本集连续数值进行了二值离散化。具体构建决策树的过程如下所示Table1Experimentaldata表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丰深10391139