神刀安全网

决策树学习

下文介绍学习决策树的过程,我们通过例子来更好地理解决策树。

决策树是什么,是一种基本的分类与回归的方法。分类决策树模型是一种描述对实例进行分类的树形结构。

决策树的算法包含:特征选择,决策树的生成、决策树的剪枝过程。

通过下面的例子来更好地了解决策树的机制。

决策树学习

希望通过训练得出决策树,用以对未来的贷款申请进行分类,即当新的客户提出贷款时,直接通过决策树决定是否批准贷款申请。

1.特征选择

特征选择是决定用哪个特征来划分特征空间。

现在存在四种可能的决策树的根节点,年龄(青年、中年、老年),工作(是、否),有房(是、否),信贷状况(非常好、好、一般)。那么问题是选择哪一个作为根特征更好一些?需要通过信息增益来解决。

1.1信息增益

熵(entropy)是表示随机变量不确定性的度量。设x是一个取有限个值的离散随机变量,其概率分布为P(X=xi)=pi,i=1,2,3…,n则随机变量x的熵定义为

决策树学习

条件熵H(Y|X)表示在已知随机变量x的条件下随机变量y的不确定性。

决策树学习

信息增益表示得知特征x的信息而使得y的信息不确定性减少的程度。

特征A对训练数据集D的信息增益g(D,A)=H(D)-H(D|A)。等价于训练数据集中类与特征的互信息。

决策树学习应用信息增益准则选择特征,给定训练数据集D合特征A,H(D)表示对D分类的不确定性,而H(D|A)表示在特征A给定的条件下对数据集D进行分类的不确定性,差值为信息增益。不同的特征会有不同的信息增益,比较大小后信息增益大的特征具有更强的分类能力。

决策树学习

那么通过例子计算信息增益:

1.计算经验熵H(D)

决策树学习

2.计算四个特征的信息增益。

设A1,A2,A3,A4表示年龄、有工作、有房子、信贷状况。

年龄:D1,D2,D3为青年,中年,老年。

决策树学习

工作:D1,D2位是,否。

决策树学习

房子:

决策树学习

信贷状况:

决策树学习

其中A3的信息增益最大,则为最优特征。

在C4.5中使用信息增益比计算特征值:gR(D,A)=g(D,A)/H(D).

2.决策树的生成

2.1 ID3算法

决策树的各个节点上应用信息增益准则选择特征,递归构建决策树,具体方法是从根节点开始,对节点计算所以可能的特征信息增益,选择信息增益最大的特征作为节点的特征,在对子节点递归调用以上方法构建决策树。

决策树学习

决策树学习

由于特征A3的信息增益最大,所以选择特征A3为根节点,他可以划分为两个子集D1(A3为是),D2(A3为否),由于D1样本点均同意贷款,所以他成为一个没有子节点的叶节点。

对于D2需要从特征A1,A2,A4中选择最大特征作为其子节点。那么要计算信息增益:

决策树学习

A2的信息增益最大,那么作为房子后的节点。

工作有两个值是和否,但是由于没有房子但工作为是的有放了贷款,没有房子但是没有工作的都没有放贷,所以无需再增加子节点,该决策树只使用两个特征构成决策树。

决策树学习

2.2 C4.5

C4.5与ID3的区别在于使用信息增益比计算gR(D,A)=g(D,A)/H(D)。

决策树学习

2.3 CART分类与回归树

CART(classification and regression tree)的算法整体过程和上面的差异不大,然是CART的决策是二叉树的每一个决策只能是“是”和“否”,换句话说,即使一个feature有多个可能取值,也只选择其中一个而把数据分类两部分而不是多个,这里我们主要讲一下分类树,它用到的是基尼指数。

cart决策树生成就是递归地构建二叉决策树的过程,对回归树用平方误差最小化准则,对分类树用基尼指数最小化准则,进行特征选择,生成二叉树。

1.回归树的生成:?

最小二乘回归树生成算法:

决策树学习

决策树学习

2.分类树的生成:

决策树学习

决策树学习

首先计算各个特征的基尼指数,分别以A1,A2,A3,A4表示年龄、工作、房子和信贷状况,以1,2,3表示年龄的青年、中年、老年,已1,2表示是、否,已1,2,3表示信贷状况的非常好、好、一般。

》求A1的基尼指数:

Gini(D,A1=1)=P(A1=1)Gini(D1)+P(A1!=1)Gini(D2)

决策树学习

其中5/15为A1的概率,Gini(D1)为青年中放贷的基尼指数2p(1-p),其中p为青年中放贷的概率为2/5,10/15为不是青年的概率,Gini(D2)为不是青年但是放贷的基尼指数2p(1-p),其中p为不是青年但是放贷的概率7/10.

同理,算出其他的基尼指数:

Gini(D,A1=2)=0.48

Gini(D,A1=3)=0.44

由于Gini(D,A1=1)和Gini(D,A1=3)相等,且最小,所以A1=1和A1=3都可以最为A1的最优切分点。

》求特征A2和A3的基尼指数:

由于工作和房子均只有两种情况,是否,是和否的基尼指数相同,所以只有一个切分点。 

Gini(D,A2=1)=5/15Gini(D1)+10/15Gini(D2)=5/15*0+10/15*2*4/10*6/10=0.32

Gini(D,A3=1)=0.27

》求特征A4的基尼指数:

Gini(D,A4=1)=0.36

Gini(D,A4=2)=0.47

Gini(D,A4=3)=0.32

Gini(D,A4=3)最小,所以A4=3为A4的最优切分点。

在4个特征中,Gini(D,A3=1)最小,所以选择特征A3为最优特征,A3=1为最优切分点,于是A3为根节点,有两个子节点,其中一个全为是,则为叶节点,对领完一个节点继续使用以上方法,直至都为叶节点。

递归的停止条件,节点中的样本个数小于预定阈值,或样本集的基尼指数小于一定阈值(样本基本属于同一类)或没有更多特征。

3.剪枝

决策树会一直递归到结束为止,存在过拟合,原因是学习时过多的考虑如何提高对数据分类的准确性,构建了过于复杂的决策树。

前置裁剪在构建决策树的过程时,提前停止。那么,会将切分节点的条件设置的很苛刻,导致决策树很短小。结果就是决策树无法达到最优。实践证明这中策略无法得到较好的结果。

后置裁剪决策树构建好后,然后才开始裁剪。采用两种方法:1)用单一叶节点代替整个子树,叶节点的分类采用子树中最主要的分类;2)将一个字数完全替代另外一颗子树。后置裁剪有个问题就是计算效率,有些节点计算后就被裁剪了,导致有点浪费。

决策树剪枝往往通过极小化决策树整体的损失函数(loss function)或代价函数(cost function)来实现。设树T的叶节点个数为|T|,t是树T的叶节点,该叶节点有Nt个样本点,其中k类的样本点有Ntk个,k=1,2…k,Ht(T)为叶节点t上的经验熵,α>=0为参数,则决策树学习的损失函数可以定义为:

决策树学习

C(T)表示模型对训练数据的预测误差,|T|为复杂度。损失函数为预测误差与复杂度的综合评价。

剪枝,就是当α确定时,选择损失函数最小的模型,即损失函数最小的子树。

如何进行剪枝:

(1)假设减掉最左边第一支,计算一次Cα(T1).

(2)假设减掉最左边第二支,计算一次Cα(T2).

(3)以上述方式递归向上每减掉一支计算一次一次Cα(Tn).

(4)求出Cα(T1)到Cα(Tn)中的最小值。

(5)减去此支,得到最优决策树。

转载本站任何文章请注明:转载至神刀安全网,谢谢神刀安全网 » 决策树学习

分享到:更多 ()

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址