基于信息增益的决策树

1基于信息增益的决策树摘要本文深入研究了ID3算法的理论基础及构建决策树的过程等知识。Quinlan提出的ID3算法虽然经典,但也有美中不足之处。本文使用修正参数修正信息增益，克服了ID3算法偏向于选择取值较多的属性这一缺点(即多值偏向问题)，对连续值的属性进行离散化，解决了连续属性的处理问题，通过有未知值的样本是按照已知值的相对频率随机分布的思想，可以处理缺少属性值的样本。描述了通过改进的ID3算法生成决策树的具体步骤，将改进算法应用到了客户关系管理系统中的客户流失分析问题当中。通过对实验结果的分析比较，得到改进算法与原ID3算法相比具有更高的预测准确率，表明了该算法的有效性。关键词：ID3算法；决策树；信息增益；多值偏向DecisionTreebasedontheInformationGainTheoryAbstractFirstly,theoreticalbasisandtheprocessofbuildingdecisiontreeofID3algorithmarefurtherresearched.TheID3algorithmwhichwaspresentedbyQuinlanisnotonlymostfamous,butalsotherearesomedrawbacks.Thisalgorithmcorrecttheinformationgainbyusingamodifiedparameterandovercomethedisadvantagethatbiastoselecttheattributehasmorevalue(namelymulti-valuebias)andthediscreteofcontinuouspropertiestosolvetheproblemofthecontinuousattributes．Asfortheideathatasampleofunknownvalueisinaccordancewiththeknownvaluesoftherelativefrequencyofrandom，Itcandealwiththemissingattributevaluesofthesample．LastdescribedthestepsthathowtogeneratedecisiontreebythemodifiedID3algorithm．Theimprovedalgorithmisappliedtotheanalysisofcustomerlostinthecustomerrelationshipmanagementsystem．Throughthecomparisonoftheexperimentalresults，theimprovedalgorithmhasahigherforecastaccuracythantheoriginalID3algorithm．Finally,thefeasibilityofthemethodisvalidatedbypracticalapplication.Keywords：ID3algorithm；Decisiontree；Informationgain；Multi-valuebias0引言近年来，数据挖掘作为一种能发现海量数据中潜在有用信息的数据分析方法和技术，已在银行、证券、房地产、教育等行业领域得到了广泛应用，为人们获取有价值的信息提供了强有力手段。分类是数据挖掘技术中最常用的方法之一，而决策树分类以其速度快、精度高、直观易懂和生成模式简单等诸多优点而倍受青睐，已在数据挖掘领域中有着不可替代的作用和地位。决策树算法作为数据挖掘中一种简单、实用而有效的快速分类算法，其本质上是一种以实例为基础的归纳学习，它主要着眼于如何从一组无次序、无规则的事例中推理出以决策树表示的分类规则。ID3算法作为最具影响力的一种决策树构造算法是由QuinLanJR于1986年提出，其后很多专家学者对其进行了深入的研究。本文从改进和简化的角度对ID3算法进行了一定程度，针对ID3算法的缺点及不足，提出了一种基于ID3算法的改进算法。基于该改进算法将极大的提高预测的准确率，具有较高的实用性和有效性。21决策树简介决策树(DecisionTree)是一种有向、无环图(DirectedAcyclicGraphics，简称DAG)。决策树方法是利用信息论中的信息增益寻找数据库中具有最大信息量的属性字段，建立决策树的一个结点，再根据该属性字段的不同取值建立树的分支，再在每个分支子集中重复建立树的下层结点和分支的一个过程。构造决策树的具体过程为：首先寻找初始分裂．整个训练集作为产生决策树的集合，训练集每个记录必须是已经分好类的，以决定哪个属性域(Field)作为目前最好的分类指标．一般的做法是穷尽所有的属性域，对每个属性域分裂的好坏做出量化，计算出最好的一个分裂。量化的标准是计算每个分裂的多样性(Diversity)指标。其次，重复第一步，直至每个叶节点内的记录都属于同一类且增长到一棵完整的树。如图1所示。图1：决策树构造和优化过程2ID3算法2.1ID3算法描述ID3算法是由Quinlan提出的一种归纳学习算法，它可以从一个训练例子集合中归纳出知识，抽取出的知识以决策树的形式表示。该算法的核心用信息增益(即信息论中的互信息)作为属性的选择标准，以使得在对每一个非叶结点进行测试时，能获得关于被测试记录最大的类别信息。ID3总是选择具有最高信息增益(或最大熵压缩)的属性作为当前节点的测试属性．具体方法是：检测所有的属性，选择信息增益最大的属性产生决策树结点，由该属性的不同取值建立分支，再对各分支的子集递归调用该方法建立决策树结点的分支，直到所有子集仅包含同一类别的数据为止，最后得到一棵决策树，它可以用来对新的样本进行分类。信息增益是基于信息论中嫡的概念。熵是对事件对应的在信息论中，熵表示的是不确定性的量度。由信息论的创始人Shannon在著作《通信的数学理论》中提出、建立在概率统计模型上的信息度量。他把信息定义为“用来消除不确定性的东西”。设S是s个训练数据样本的集合。假定类标号属性具有m个不同值，定义m个不同类Ci，i=1，…，m，si是类Ci中的样本数。一个给定的样本分类所需的期望信息由下式给出：imiimppsssI2121log,,,其中：pi是任意样本属于Ci的概率，一般用si／s来估计。注意，对数函数以2为底，其原因是信息用二进制编码。设属性A具有v个不同值{a1，a2，…，an}，可以用属性A将S划分为v个子集{S1，S2，…，Sv}，Sj中的样本在属性A上具有相同的值aj，j=1，2，…，v，sij是子集Sj中类Ci的样本数，由A划分成子集的期望信息由下式给出：mjjjvjmjjjsssIssssAE,,/211213其中：ssssmjjj21充当第j个子集的权，并且等于子集(即A值为aj)中的样本个数除以S中的样本总数。熵值越小，子集划分的纯度越高。对于给定的子集Sj，其期望信息由下式给出：ijmiijmjjjppsssI2121log,,,其中：pij=sij/sj是Sj中样本属于Ci的概率。属性A上分支将获得的信息增益为：AEsssIAGainm,,,21算法计算每个属性的信息增益，并选取具有最高信息增益的属性作为给定集合S的测试属性，创建一个结点，并以该属性标记，对该属性的每个值创建一个分支，并据此划分样本。2.2ID3建树算法在决策树生成过程中引入信息增益作为训练样本集合的分裂度量标准，就得到如下的ID3算法生成决策树的基本步骤：(1)以待分类的训练样本集合作为根节点开始建树。(2)如果训练样本属于同一类，则当前节点为叶节点，并用训练样本所属的类进行标记。(3)否则，计算各个属性对当前训练样本集合进行划分的信息增益，选择信息增益最大的属性作为当前训练样本集合的判断属性。(4)对于选定的判断属性，根据其每个不同的值分别建立相应的分枝，并将对应的训练样本子集划分到相应的分枝中。(5)算法递归应用步骤(2)、(3)、(4)，对各训练样本子集继续划分，生成新的决策树分枝。(6)算法停止。3决策树ID3算法的改进3.1ID3算法的不足及改进思路本文重点关注了ID3算法的3个方面的不足：(1)ID3算法的分裂度量标准采用的是信息增益，通过以前大量的研究分析与实际应用可以知道，这种分裂度量标准偏向于选择属性值个数较多的属性，而属性取值个数较多的属性并不一定是最优的属性。所以需要改进选择属性的分裂度量标准。(2)ID3算法只能处理离散属性，对于连续值的属性，必须首先对其进行离散化才能投入使用。比如性别属性是离散属性，适合用ID3算法处理，而收入属性就是一个连续值的属性，那么按照ID3算法是无法计算的，必须对收入离散化后才可用。所以需要针对连续值属性的离散化方法做出改进。(3)采用ID3算法产生的决策树进行预测时，必须知道从叶子节点到树根的路径上所有内节点对应的属性的属性值。如果样本的某个属性缺少具体的属性值，那么这种样本应用于ID3算法就不合适，所以要针对未知或在生成决策树过程中才对缺省属性赋值的情况做出改进，让ID3算法能够满足这种情况。以下是对上述提到的3个主要方面的不足的改进思路：(1)针对ID3算法的第一个缺点，在改进算法中引入一个修正参数，在对每个属性求出信息增益后，用一个关于决策属性取值个数的函数算出的参数去修正该信息增益，成为属性选4择以及样本分区成子集的分裂度量标准，这样即可解决属性值个数多少对生成决策树的影响。(2)针对ID3算法的第二个缺点，采用k-均值的聚类分析方法，通过选择适当的k值，将该连续属性上的值分为k个区间，即可将该属性分为k个类。再按照离散属性计算信息增益的方式计算出该属性的分裂度量标准，与其它属性进行比较得出最优判断属性。通过选择适当的连续属性离散化方法，就解决了连续属性的处理问题。(3)针对ID3算法的第三个缺点，解决思路是将有缺少属性值的样本按照该属性已知值的相对频率随机分布，在产生决策树的节点时，同时记录下满足从该节点到根节点的路径的条件的概率数，从而解决在属性值缺失情况下的决策树的预测能力问题。为了防止决策树的过度拟合问题，必须对生成的决策树进行剪枝，此处采用后剪枝的方法，通过剪枝，去掉那些对未知检验样本的分类精度没有帮助的部分子树，生成一个更简单，更容易理解的树。ID3算法还有以下缺点：ID3算法对噪声较为敏感，Quinlan定义噪声为训练样本数据中的属性值错误和分类类别错误。ID3算法在搜索中不进行回溯，每当在树的某一层选择了一个属性进行测试，就不会再回溯重新考虑这个选择。这样，算法容易收敛到局部最优的答案，而不是全局最优的，这些缺点和不足有待于进一步改进。3.2ID3算法的改进方法所提出的改进算法除了拥有原ID3算法的基本功能外，将从以下几个方面加以改进：通过修正参数修正算出的信息增益以改进ID3算法偏向属性取值个数较多的属性、对连续值的属性进行离散化、处理缺少属性值的训练样本、使用后剪枝技术避免树的不平衡，以下从几个方面进行详细的阐述：(1)使用修正参数修正信息增益ID3算法使用信息增益标准对紧凑型决策树的构造有较好的效果，但也有一个严重的缺陷：对具有较多数目的属性有严重的偏差。论文中的改进算法将使用修正参数的概念对这一缺陷进行改进，可以指定一个附加的修正参数：f(n)=1／n，上式中的n表示各决策属性的取值个数，取值个数越多，n越大，则修正参数fin)越小。然后定义一个新的增益标准：Gain’(Q)=f(n)Gain(Q)这个新的增益标准通过参数f(n)修正了原来的信息增益。在对每个属性求出新增益标准以后，再用修正参数修正其值，并以此作为判断属性选择以及样本分区成子集的选择准则。用新增益标准，可以避免偏向选择属性值个数较多的属性为判断属性，因为属性值越多，修正后的增益标准就越小，就不会轻易被选为判断属性了。(2)对