基于信息增益的决策树

1、精选优质文档-倾情为你奉上基于信息增益的决策树摘 要本文深入研究了ID3算法的理论基础及构建决策树的过程等知识。Quinlan提出的ID3算法虽然经典,但也有美中不足之处。本文使用修正参数修正信息增益，克服了ID3算法偏向于选择取值较多的属性这一缺点(即多值偏向问题)，对连续值的属性进行离散化，解决了连续属性的处理问题，通过有未知值的样本是按照已知值的相对频率随机分布的思想，可以处理缺少属性值的样本。描述了通过改进的ID3算法生成决策树的具体步骤，将改进算法应用到了客户关系管理系统中的客户流失分析问题当中。通过对实验结果的分析比较，得到改进算法与原ID3算法相比具有更高的预测准确率，表明了该算

2、法的有效性。关键词：ID3算法；决策树；信息增益；多值偏向Decision Tree based on the Information Gain TheoryAbstractFirstly, theoretical basis and the process of building decision tree of ID3 algorithm are further researched. The ID3 algorithm which was presented by Quinlan is not only most famous, but also there are some drawb

3、acks. This algorithm correct the information gain by using a modified parameter and overcome the disadvantage that bias to select the attribute has more value (namely multi-value bias) and the discrete of continuous properties to solve the problem of the continuous attributesAs for the idea that a s

4、ample of unknown value is in accordance with the known values of the relative frequency of random，It can deal with the missing attribute values of the sampleLast described the steps that how to generate decision tree by the modified ID3 algorithmThe improved algorithm is applied to the analysis of c

5、ustomer lost in the customer relationship management systemThrough the comparison of the experimental results，the improved algorithm has a higher forecast accuracy than the original ID3 algorithmFinally, the feasibility of the method is validated by practical application.Keywords：ID3 algorithm；Decis

6、ion tree；Information gain； Multi-value bias0 引言近年来，数据挖掘作为一种能发现海量数据中潜在有用信息的数据分析方法和技术，已在银行、证券、房地产、教育等行业领域得到了广泛应用，为人们获取有价值的信息提供了强有力手段。 分类是数据挖掘技术中最常用的方法之一，而决策树分类以其速度快、精度高、直观易懂和生成模式简单等诸多优点而倍受青睐，已在数据挖掘领域中有着不可替代的作用和地位。决策树算法作为数据挖掘中一种简单、实用而有效的快速分类算法，其本质上是一种以实例为基础的归纳学习，它主要着眼于如何从一组无次序、无规则的事例中推理出以决策树表示的分类规则。ID3

7、算法作为最具影响力的一种决策树构造算法是由QuinLan J R于1986年提出，其后很多专家学者对其进行了深入的研究。本文从改进和简化的角度对ID3算法进行了一定程度，针对ID3算法的缺点及不足，提出了一种基于ID3算法的改进算法。基于该改进算法将极大的提高预测的准确率，具有较高的实用性和有效性。1 决策树简介决策树(Decision Tree)是一种有向、无环图(Directed Acyclic Graphics，简称DAG)。决策树方法是利用信息论中的信息增益寻找数据库中具有最大信息量的属性字段，建立决策树的一个结点，再根据该属性字段的不同取值建立树的分支，再在每个分支子集中重复建立树的

8、下层结点和分支的一个过程。构造决策树的具体过程为：首先寻找初始分裂整个训练集作为产生决策树的集合，训练集每个记录必须是已经分好类的，以决定哪个属性域(Field)作为目前最好的分类指标一般的做法是穷尽所有的属性域，对每个属性域分裂的好坏做出量化，计算出最好的一个分裂。量化的标准是计算每个分裂的多样性(Diversity)指标。其次，重复第一步，直至每个叶节点内的记录都属于同一类且增长到一棵完整的树。如图1所示 。图1：决策树构造和优化过程2 ID3算法2.1 ID3算法描述ID3算法是由Quinlan提出的一种归纳学习算法，它可以从一个训练例子集合中归纳出知识，抽取出的知识以决策树的形式表示。

9、该算法的核心用信息增益(即信息论中的互信息)作为属性的选择标准，以使得在对每一个非叶结点进行测试时，能获得关于被测试记录最大的类别信息。ID3总是选择具有最高信息增益(或最大熵压缩)的属性作为当前节点的测试属性具体方法是：检测所有的属性，选择信息增益最大的属性产生决策树结点，由该属性的不同取值建立分支，再对各分支的子集递归调用该方法建立决策树结点的分支，直到所有子集仅包含同一类别的数据为止，最后得到一棵决策树，它可以用来对新的样本进行分类。信息增益是基于信息论中嫡的概念。熵是对事件对应的在信息论中，熵表示的是不确定性的量度。由信息论的创始人Shannon在著作通信的数学理论中提出、建立在概率统

10、计模型上的信息度量。他把信息定义为“用来消除不确定性的东西”。 设S是s个训练数据样本的集合。假定类标号属性具有m个不同值，定义m个不同类Ci，i=1，m，si是类Ci中的样本数。一个给定的样本分类所需的期望信息由下式给出：其中：pi是任意样本属于Ci的概率，一般用sis来估计。注意，对数函数以2为底，其原因是信息用二进制编码。设属性A具有v个不同值a1，a2，an，可以用属性A将S划分为v个子集S1，S2 ，Sv，Sj中的样本在属性A上具有相同的值aj，j=1，2，v，sij是子集Sj中类Ci的样本数，由A划分成子集的期望信息由下式给出：其中：充当第j个子集的权，并且等于子集(即A值为aj

11、)中的样本个数除以S中的样本总数。熵值越小，子集划分的纯度越高。对于给定的子集Sj，其期望信息由下式给出：其中：pij=sij/sj是Sj中样本属于Ci的概率。属性A上分支将获得的信息增益为：算法计算每个属性的信息增益，并选取具有最高信息增益的属性作为给定集合S的测试属性，创建 一个结点，并以该属性标记，对该属性的每个值创建一个分支，并据此划分样本。2.2 ID3建树算法在决策树生成过程中引入信息增益作为训练样本集合的分裂度量标准，就得到如下的ID3算法生成决策树的基本步骤：(1)以待分类的训练样本集合作为根节点开始建树。 (2)如果训练样本属于同一类，则当前节点为叶节点，并用训练样本所属的类

12、进行标记。 (3)否则，计算各个属性对当前训练样本集合进行划分的信息增益，选择信息增益最大的属性作为当前训练样本集合的判断属性。 (4)对于选定的判断属性，根据其每个不同的值分别建立相应的分枝，并将对应的训练样本子集划分到相应的分枝中。 (5)算法递归应用步骤(2)、(3)、(4)，对各训练样本子集继续划分，生成新的决策树分枝。 (6)算法停止。3 决策树ID3算法的改进3.1 ID3算法的不足及改进思路本文重点关注了ID3算法的3个方面的不足： (1)ID3算法的分裂度量标准采用的是信息增益，通过以前大量的研究分析与实际应用可以知道，这种分裂度量标准偏向于选择属性值个数较多的属性，而属性取值

13、个数较多的属性并不一定是最优的属性。所以需要改进选择属性的分裂度量标准。 (2)ID3算法只能处理离散属性，对于连续值的属性，必须首先对其进行离散化才能投入使用。比如性别属性是离散属性，适合用ID3算法处理，而收入属性就是一个连续值的属性， 那么按照ID3算法是无法计算的，必须对收入离散化后才可用。所以需要针对连续值属性的离散化方法做出改进。(3)采用ID3算法产生的决策树进行预测时，必须知道从叶子节点到树根的路径上所有内节点对应的属性的属性值。如果样本的某个属性缺少具体的属性值，那么这种样本应用于ID3算法就不合适，所以要针对未知或在生成决策树过程中才对缺省属性赋值的情况做出改进，让ID3算

14、法能够满足这种情况。以下是对上述提到的3个主要方面的不足的改进思路： (1)针对ID3算法的第一个缺点，在改进算法中引入一个修正参数，在对每个属性求出信息增益后，用一个关于决策属性取值个数的函数算出的参数去修正该信息增益，成为属性选择以及样本分区成子集的分裂度量标准，这样即可解决属性值个数多少对生成决策树的影响。 (2)针对ID3算法的第二个缺点，采用k-均值的聚类分析方法，通过选择适当的k值，将该连续属性上的值分为k个区间，即可将该属性分为k个类。再按照离散属性计算信息增益的方式计算出该属性的分裂度量标准，与其它属性进行比较得出最优判断属性。通过选择适当的连续属性离散化方法，就解决了连续属性

15、的处理问题。 (3)针对ID3算法的第三个缺点，解决思路是将有缺少属性值的样本按照该属性已知值的相对频率随机分布，在产生决策树的节点时，同时记录下满足从该节点到根节点的路径的条件的概率数，从而解决在属性值缺失情况下的决策树的预测能力问题。 为了防止决策树的过度拟合问题，必须对生成的决策树进行剪枝，此处采用后剪枝的方法，通过剪枝，去掉那些对未知检验样本的分类精度没有帮助的部分子树，生成一个更简单，更容易理解的树。 ID3算法还有以下缺点：ID3算法对噪声较为敏感，Quinlan定义噪声为训练样本数据中的属性值错误和分类类别错误。ID3算法在搜索中不进行回溯，每当在树的某一层选择了一个属性进行测试

16、，就不会再回溯重新考虑这个选择。这样，算法容易收敛到局部最优的答案，而不是全局最优的，这些缺点和不足有待于进一步改进。3.2 ID3算法的改进方法所提出的改进算法除了拥有原ID3算法的基本功能外，将从以下几个方面加以改进：通过修正参数修正算出的信息增益以改进ID3算法偏向属性取值个数较多的属性、对连续值的属性进行离散化、处理缺少属性值的训练样本、使用后剪枝技术避免树的不平衡，以下从几个方面进行详细的阐述：(1) 使用修正参数修正信息增益 ID3算法使用信息增益标准对紧凑型决策树的构造有较好的效果，但也有一个严重的缺陷：对具有较多数目的属性有严重的偏差。论文中的改进算法将使用修正参数的概念对这一

17、缺陷进行改进，可以指定一个附加的修正参数：f(n)= 1n，上式中的n表示各决策属性的取值个数，取值个数越多，n越大，则修正参数fin)越小。然后定义一个新的增益标准： Gain(Q)=f(n)Gain(Q)这个新的增益标准通过参数f(n)修正了原来的信息增益。在对每个属性求出新增益标准以后，再用修正参数修正其值，并以此作为判断属性选择以及样本分区成子集的选择准则。用新增益标准，可以避免偏向选择属性值个数较多的属性为判断属性，因为属性值越多，修正后的增益标准就越小，就不会轻易被选为判断属性了。(2)对连续值的属性进行离散化 ID3算法只能处理离散类型的属性。实际应用中包含两种类型的检验结构：一

18、个方面是对离散属性值的检验，ID3算法对离散属性的每个可能值有一个分枝和输出；另一个方面是对连续属性检验。对于连续属性Y，即数值型属性的检验，改进算法采用k-均值聚类分析方法，将属性Y上的取值进行聚类，首先随机选择该属性上的k个值作为初始簇，这k个值即为各簇的中心值，然后对其它值分别计算到这些簇的距离，选择距离最小的簇加入进去，然后通过加权平均的方法得出每个簇的中心值，依次类推，将剩余的值分别加入各簇，就得到该连续属性Y上所有值的k个聚类，然后选择第1到第k-1个簇中的最大值作为标准对Y进行划分，设这k-1个值分别为V1，V2，Vk-1，则Y可以分为k个区间yV 1，V 1yV 2 ，V k-

19、1 y，这样，该属性就有k个属性值，再按照离散属性计算信息增益的方式计算出该属性的修正信息增益。(3)处理缺少属性值的样本 ID3算法是基于所有属性值都确定的情况下的分类，而实际应用中经常会缺少某些样本的一些属性值或存在数据值丢失的情况，直接抛弃数据库中有丢失数据的样本，这显然不是 一个好的方法。 在论文提出的改进算法中，有未知值的样本是按照已知值的相对频率随机分布的。对于有未知值的样本，每个样本都有一个概率参数，当一个值己知的样本从T分配给T i时，属于其它子集的概率为0。当一个值为未知时，只能得出不稳定的概率描述。改进算法中将每个子集Ti中的每个样本用权重W标注，它表示属于每个子集的样本概

20、率。分区后，属性己知的样本属于子集Ti的概率为1，有未知值的样本被表示在每个Ti子集中，对于有未知值的样本属于子集Ti的概率为：己知的样本属于子集Ti的概率和属性值己知的样本数量。由于最终分类的不明确性，叶子结点的每个决策都以(|Ti|E)表示。|Ti|是到达结点的部分样本和，E是除了指定类以外的类的样本数量。(|Ti|E)的意思是|Ti|个部分训练样本到达叶结点，其中E并不属于分配给叶的类。 (4)采用后剪枝方法优化决策树 决策树剪枝的基本思想是去掉那些对未知检验样本的分类精度没有帮助的部分子树，生成一个更简单，更容易理解的树。本文的改进算法采用了后修剪方法，用默认的置信度25，比较所给内节

21、点Ti的U25%(|Ti|E)信度，从而决定该结点是否替换叶子结点。权值是每个叶的样本的总数，若子树中的某个根节点的预测误差比叶的U25% (子树的预测误差)的加权和小，那么用它的根节点替换该子树，变成剪枝后的树的一个新叶。3.3改进的ID3算法的具体实现步骤根据改进的ID3算法的思想，通过以下几个步骤来生成决策树：(1)确定根结点： 1)统计样本总量，样本总量为训练样本集合中属性值己知的样本的数量。2)令p1=|E1|，p2=|E2|，pn=|En|，分别得到训练样本集合中第1类记录的个数、第2类记录的个数、第n类记录的个数，根据公式计算期望信息I(p1，p2，pn)。3)根据某个属性A具有

22、的属性值为A1，A2，Av，若A为离散属性，将训练样本集合按照分类类别划分成E11，E12 ，E1v，E21，E22 ，E2v和En1，En2 ，Env。E1i，E2i，Eni中每个训练样本 的属性取值为Ai，令p1i =| E1i |，p2i =| E2i |，pni =| Eni |，根据公式，求出E(A)；若A为连续属性，首先设定要划分的区间数k，然后随机选择该属性A上的k个值 作为初始簇A1，A2，Ak，对剩下的取值分别计算与各簇的距离，选择距离最短的加入各簇，依次类推，即可得到A上所有值的k个聚类，选择簇A1到Ak-1中的最大值V1，V2，Vk-1作为标准对A进行划分，得到A上取值的

23、k个区间aV 1，V 1aV 2 ，V k-1 a。再次用A的属性值A1，A2，Ak，将训练样本集合划分成E11，E12 ，E1k，E21，E22 ，E2k和En1，En2 ，Enk。4)根据公式Gain(Q)=fin)Gain(Q)求得按属性A划分训练样本集合的新增益标准值Gain(A)。 5)类似于3)、4)两步，分别求出各属性的新增益标准值Gain(A)，Gain(B)，选择其中值最大的作为决策树的根结点。 (2)确定根结点的下一级结点，根据根结点的各个属性取值，采用广度优先搜索的策略，将下级结点作为新的根节点再按照第一步的方法递归地求出各根结点的全部子结点，缺少 属性值的训练样本被分别

24、表示在每个子结点的子集中。 (3)求出各级结点，直至求出全部的叶子结点，结束递归过程。 (4)考察各级结点以及叶子结点，对于所含缺少属性值的训练样本分别计算其所属类的概率(|Pi|E)，最后生成决策树，采用深度优先搜索策略递归来求出该决策树每个叶子的对 应规则。4 实验及分析本文采用文献10中的数据库中若干标准数据集进行试验分析，并分别基于ID3算法和改进的ID3算法进行客户流失的分析。4.1 选择决策属性，数据准备和预处理客户流失分析系统数据检测建模的样本数据为某企业的客户数据451条记录。与前面的潜在客户发现一样，为了对改进算法进行验证，将客户数据分为3份，每次选用2份用于生成决策树，1份

25、用于测试生成的决策树的预测准确率。具体数据如表4-1所示。 表4-1：客户流失分析决策树原始样本客户等级性别年龄婚姻状况居住地与销售点距离历史最长购买间隔本次购买间隔1男250300844女371400354002男28180015232女39038012153男2912000152173根据企业具体情况进行分类，最后得到各连续属性的离散化处理，如表4-2所示。表4-2：客户流失分析决策树修正样本客户等级性别年龄婚姻状况居住地与销售点距离历史最长购买间隔本次购买间隔10202804131235320213151213021213021415224.2 生成决策树下面首先使用传统的ID3算法建立

26、决策树，根据数据样本建立客户流失分析的决策树模型。得到完整的数据样本的决策树如图4-1所示。 图4-1：传统ID3算法生成的客户流失分析决策树然后再将训练样本交给改进的ID3算法进行处理，得到的决策树如图4-2所示。图4-2：改进的ID3算法生成的客户流失分析决策树4.3 改进算法结果分析与评估在客户流失分析模型的建立过程中，系统共采集了451条数据样本，由于整体样本数量不足够大，因此采用3折交叉验证的方法对该模型准确性做出评估，并与ID3算法所得结果进行比较。首先将采集到的451条记录等量分为3份，取其中的2份作为训练样本，剩余1份作为测试样本，分别对两种算法进行测试。0表示稳定客户、1表示

27、可能流失客户、2表示极可能流失客户、3表示流失客户；表格中的第x行Y列的数据是指真实值为第x行所示数据被预测为第Y列数据的个数。整理以上各决策树混淆矩阵，可得表4-3所示统计表。表4-3：传统ID3算法和改进的ID3算法在客户流失分析应用中的效率分析传统ID3算法改进的ID3算法0类客户(即稳定客户)1类客户(即可能流失客户)2类客户(即极可能流失客户)3类客户(即流失客户)0类客户(即稳定客户)1类客户(即可能流失客户)2类客户(即极可能流失客户)3类客户(即流失客户)预测个数1879880861841029075正确个数165835858168876858预测准确率88.2%84.7%72.5%67.4%91.3%85.3%75.6%77.3%图4-3：改进前后两种算法预测准确率对比从试验结果可以直观发现：针对不同规模的数据集，改进算法