【《决策树的结构与原理分析》2400字】

决策树的结构与原理分析目录TOC\o"1-3"\h\u4521决策树的结构与原理分析 169951.1ID3定义及计算 2110641.2C4.5定义及计算 3252971.3CART定义及计算 4机器学习算法是使用的大量的数据对计算机进行训练来模拟人的思维方式和学习行为，以收获一些新的知识技能或是在训练的过程中不断地为完善自己的功能提升自己的性能，决策树作为机器学习中的一大算法，它的决策过程与人的思维过程十分类似，决策树的原理如图3.1所示：图3.1决策树原理可以观察到它是一棵由上而下，向下生长的一棵“倒置的树”，决策树由节点和边组成，节点存放数据或属性判定，边则指示着方向，最初的节点叫做根节点，其余的节点叫做子节点，其中带有分支的节点叫做内节点，最终不在生长的节点叫做叶节点或叶子节点，它代表最终的分类或者数据的处理结果。一个数据进来之后将会从根节点依次经历所有的节点最终到达叶子节点完成分类和数据处理，一个样本集所有的样本都经历这一棵决策树的决策分类之后，那么也就完成了对这一样本集的分类决策。在决策树的最优特征选取的过程中，决策树会一次次不断地重复学习算法到最终找到最优特征为止。之后便会将最优特征放入子节点（非叶子节点）中，将待训练样本集进行分类以获得最优的输出结果。这样样本集就分类结束了。决策树具有天然的可解释性，就像一类事物之所以被归为这一类是因为他具有某些特征。那么决策树的工作就是根据这些特征将一组无序的混乱的样本集完成分类，将其中好目标样本分类出来。广泛的来讲，它采用自上而下递归的方式，同过比较样本内部特征数据的属性值，并以此为根据将他输送给下一个子节点，最终输送到叶子节点上完成最终的分类，目前决策树有基于熵构建的ID3树，基于信息增益率构建的C4.5树，基于Gini系数构建的CART树。构造决策树时首要解决的问题就是确定根节点，由于根节点是最初的节点要给全部样本进行分类，所以应让每个样本尽可能获得最优的输出分类。其次便是构建最终的分类结果（叶子节点），将上一步分类好的样本放入对应的叶子节点中。若有未正确分类的样本，重复上述步骤直到大部分样本均被正确分类为止。决策树的优点在于它天然的可解释性，易于理解，计算复杂度较低，对中值缺失的敏感度较低，所以便于处理一些不相关数据。决策树的缺点也很明显，数据都是有特例的，如果一个决策树能将训练数据完美分类那他一定是过拟合的。1.1ID3定义及计算为了解决如何选择根节点以及之后子节点的问题，引入了信息熵(informationentropy)的概念，熵代表了一个总体的混乱成度，在决策树中他代表样本种类的丰富性，一个决策树分类器的一个分类结果的熵值越低代表这个分类结果的纯度(purity)越高也代表着分类结果越好。一个含有N种样本的样本集M中的第i种样本(i=1,2,3,...,N)的概率为Pi，则M的信息熵可定义为：(3.1)对于决策树而言，总希望用最少的层数(depth)来使熵值降低的最快，来节约资源提高效率，所以选用特征熵与初始熵值相差最多的特征来作为该决策树分类器的根节点，从而引出信息增益的概念。假设离散特征种类f有K种取值可能{f1,f2,...,fK}，若用f将M划分为若干子集，那么会获得K个连接着分支的子节点，其中第K个子节点将包含M中全部在属性f上取值为f的样本，将之表示为MK。则可通过式(2.1)求出MK的信息熵，又由于每个含有分支的子节点包含不一样数目的样本数量，因此为给分支点权重|MK|/|M|，这就是说，分支节点将拥有与样本数目成正比的重要性，由此可以够推出利用属性f对划分M时产生的信息增益如公式3.2所示：(3.2)信息增益所代表的是分类后样本种类的（熵值）纯度相较于分类前的（初始熵）初始纯度的纯度提升，熵值下降的量即信息的增益量，信息增益的值越高说明该特征越优秀。然而ID3仍然存在一些问题，他无法避免一些无关特征对结果的影响，例如如果为含有n个样本的样本集进行编号，编号为从1到n，将编号是做一个新的特征，可以发现每个样本的该特征都有所不同（因为每个样本的编号都不一样），在进行决策树训练的时候发现该特征（编号）的信息增益经过计算后非常高，在逻辑上显然，样本的编号这一特征将n个样本集分为了n类，每一类下只囊括了一个样本，换言之分类纯度非常高信息增益也非常高。然而很清楚编号并不是会影响样本分类结果的一个特征，简言之一个类物品的分类标准是因为它具有一些自有的特征而不会因为他编号是多少，同时将n个样本分为n类也十分的不合理，将样本集切的太碎了而产生了过拟合，此时编号就成为了一个与样本分类结果无关却在决策树中对样本分类结果产生过大影响的一个不良特征，而ID3并不能很好的区分这些特征且，无法减弱这一类特征对样本分类结果的影响，所以引入了C4.5算法。1.2C4.5定义及计算为了解决ID3无法发现并减弱对样本具有较大影响的不良特征对样本分类结果的影响，且由于信息增益准则在使用数据量较大的训练集时会明显偏大，无法有效的行使功能，也因此有了误差，为此选用信息增益率C4.5算法有效地解决了这种问题，该算法在筛选最佳特征时，没有使用被经常使用的信息增益，而是用增益率取而代之，这样减小了过高的信息增益的同时也大幅减弱了不良特征对分类结果的不良影响。信息增益率为：(3.3)其中(3.4)是f的“固有熵”，当f下分种类越多时V(f)的值就越大，这样便有效的减弱了类似于上述“编号”这一不良特征对分类结果的影响。当在实际操作过程中，也选用先计算信息增益，再用信息增益率去掉一些不良特征的方法来筛选出较好的特征，以得到更好的输出结果。1.3CART定义及计算Gini系数（基尼系数）在决策树分类器中是用于分类问题中选择最优属性的一种评价标准。CART型决策树采用Gini系数作为评价标准。与熵值相类似Gini系数也能为样本种类的纯度做出评价，而与熵值不同的是，数据样本集的纯度越高熵值越低，而Gini系数则与之相反，样本集纯度越高则Gini系数越高，沿用公式(3.1)的表达式则样本集M的Gini系数可以表达为：(3.5)显然，Gini系数所计算的是从总的样本集中抽出两个样本被分配在并不同种类