第二十四节决策树系列之分裂流程和Gini系数评估(3)
上一节中我们讲解了决策树的数学表达形式,本节的话我们讲解决策树的分裂流程以及分裂条件的评估。我们基于决策树的递归表达式上:
就可以知道训练一颗决策树需要哪些条件?台湾大学林轩田教授给我们一个总结。
所以决策树从迭代考虑分裂的话我们需要4个条件: 1、分支个数(number of branches)即每次分裂要分成几支。 2、分支条件(branching criteria),当前分支判断的条件。 3、终止条件(termination criteria),不可能一直分下去,要有个终止条件。 4、基本算法(base hypothesis),叶子结点到底如何表达。四个问题搞明白了,如何得到一棵决策树我们就明白了。
我们的目标是通过大量的数据生成一棵非常好的树,用这棵树来预测新来的数据。好就是一定要能反映客观规律,在大数定理的理论支持下,如果收集的训练集足够庞大,训练集就一定程度上能够反映客观规律。然后我们用生成好的树来预测新来的数据,举个例子来解释下如何生成决策树的4个条件?假如训练集上有100条数据,首先所有的数据都在根节点里面出现。我们要给它分到各个子树里面,那么每次分裂要分成几份?这是第一个问题;假如分成两份的情况下,以什么条件来分份?什么分裂条件最好,一定是通过实际的计算,遍历所有的分裂条件,得到某种分裂条件下某种评分形式最高,就用什么作为分裂条件。所以第二个问题是以什么条件来分份。但什么时候停止分裂呢?数据不断分裂的递归过程,每一次分裂,尽可能让类别一样的数据在树的一边,当树的叶子节点的数据都是一类的时候,则停止分类(if else语句)。这是第三个问题。分好的叶子节点里有yes和no两种表达,当新数据过来落到这些叶子结点上到底是yes还是no?这是第四个问题。
假如现在有30个正例30个负例如图,哪种分法更好?为什么不直接给它30正例,30负例分好就可以?
所以接下来我们的文章会围绕着以下生成一颗决策树的几点考虑进行展开。
1、第一个将原始数据集筛选.分类成子数据集的分类依据? 也就是需要计算分类后的纯度。
2、第二个对生成的子数据集不断分类 直到停止。那什么时候会停止,也就是停止的条件是什么?
3、第三个只要停止了之后,你现在得到的是一个包含着若干数据点的一个节点,但是节点到底是Y还是N,或者多分类情况的时候是1还是2还是3还是4,也需要通过落在最终叶子节点上的训练集上的数据的共性来代表这个节点。假如这个节点分出来的全都是正例,那么将来也得说,它判断出来为正例。如何定性的判断它的共性?
本节的话我们讲解第一个问题,纯度的量化方式,即我们分裂条件的计算标准。常用的纯度的计算方式有Gini系数,信息增益,信息增益率。而这三种计算方式所生成的树分别对应着,CART树,ID3树,C4.5树。对于CART树和ID3这两个树来讲,它的默认分两支,永远只分两支,它是一个二叉树。对C4.5来说,它可以分若干个节点。CART意思是Classification and Regression Trees,分类与回归树, 既可以处理分类问题,又可以处理回归问题。
我们说下第一种定量的计算纯度的方式,基尼系数。公式如下:
pi代表各个类别的概率,对于离散的情况来说,通常我们认为在数据量足够大的情况下,频率可以近似等于概率。假设有10000条数据,其中有2000条是正例,8000条是负例,在不知道任何信息的情况下,拿一条新的数据,就判断属于正例的概率是多少,只有估计20%是最合理的。有可能估计错,但只有这么估计是最合理的。因为概率永远在小数据集上没有意义,拿了一条数据,说它概率是20%正例80%负例没有任何意义,因为有可能估计错;但一下拿来10万条数据,它最终在统计上会趋近于有20%的数据变成正例,80%数据变成负例。概率在大数据量上才有它的意义。我们这里通过一个节点内各个label样本的占比(即频率)近似这里的各个类别的pi概率,所以从这里能看出决策树是有监督学习。因为是通过样本的label,得到各个类别的比例。所以训练的时候有人说用到y,是用在计算基尼系数上了,而不是用来作为分裂条件的。
i代表着当前节点包含几种可能性,对分类来说,也就是所有的类别占比。
我们所谓统计纯度就是统计某一个节点内部的纯度。举个例子说明下,假如一个节点有2000个正例,8000个负例,也就是正负0.8:0.2的比例,在这种情况下,p(i)有几种可能?两种。一个是p(Y)即0.2,一个是p(N)即0.8。根据公式,这时这个节点内部的基尼系数是1-(0.2^2+0.8^2)。假如一个节点内全部是正例的话,正负比例为1:0,此时基尼系数等于0;最纯不过。假如比例是0.5:0.5 ,此时基尼系数等于0.5。所以我们可以总结出基尼系数用来评估纯度时,数值 越低代表着越纯。
因此现在就有一个工具,可以定性的去计算,这个节点里边纯还是不纯,可以一定程度上通过基尼系数来判断。这是判断一个节点纯还是不纯,而每次的分裂不仅仅分列出一个节点,怎么评估这次分裂的好坏呢?比如下面例子:
通过基尼系数来选择一个最好的分类标准,就是尝试进行若干种分裂方式,哪种最后结果最好,纯度最高,就选哪种,因为纯度高代表着未来子树会少分几次。
通常一棵树要分多少层?如果不加限制的话,可能会分成几百层,对于Cart树来说,就会有一个致命的缺陷,它是按照计算纯度来评价分裂好坏,如果不对它进行限制,让它一直分裂纯度会达到100%,最极端情况,每个叶子节点有一个数据,总能让它分到纯度最高,相当于就是记录了一下。所以生成的树通常会人为限制它的层数,不让它太深。
下节的话我们讲解另外两种评估纯度的计算方式。