机器学习算法-决策树

1. 决策树是什么

名词: 决策树(Decision Tree)

解释: 机器学习中的算法,决策树是分类回归的算法,常用于分类。

在分类问题中,用于表示基于特征对实例进行分类的过程,可以认为是代码if-then的集合,也可以认为是定义在特征中与分类中的条件概率分布。
决策树是一个预测模型;他代表的是对象属性与对象值之间的一种映射关系。
通俗的讲决策树是一个类似于流程图的树结构,其中每一个树节点表示一个特征属性上的判断,每一个分支代表一个属性的输出,每一个树叶节点代 表一个类或者类的分布,树的最顶层是树的根节点。

比如朋友要给你介绍女朋友,然后给你先说了女方的情况:

机器学习算法-决策树
示例
机器学习算法-决策树
决策过程

女孩的决策过程就是典型的分类树决策。相当于通过 :[年龄、长相、收入、是否是公务员] 男人 (实例)分为两个类别:[见、不见] ,决策树是一种描述对样本实例 (男人) 进行分类(见或不见)的树形结构。

决策树由结点有向边组成。最上部是根节点,此时所有样本都在一起,经过该节点后样本被划分到各子节点中。每个子节点再用新的特征来进一步决策,直到最后的叶节点。叶节点上只包含单纯一类样本(见或不见),不需要在进行划分。

结点两种类型: 内部结点叶结点

内部结点表示一个特征或属性,叶节点表示一个结果类。

内部节点 :收入、长相、年龄等,叶节点:见、不见

其中函数式为: y = f(x)

其含义是输入数据 x(实例数据) 返回预测值 y(分类)

2. 决策树创建

决策树创建通常需要三个部分:特征选择、决策树的生成、决策树的修剪

2.1 决策树特征选择

  • 决策树特征选择 – 熵(entropy)

我们首先了解下什么是 “” 熵的解释是混乱度的度量单位,一个系统 (一个分类结果) 的混乱度越高 (不确定性越高) 它的熵就越高,用 H(Y) 表示,这是一种很恰当的解释

那么我们该选择什么标准(属性、特征)作为我们的首要条件(根节点)对样本(女人)进行划分,决定见或不见,这个过程我们称之为特征选择

朋友希望能够得到你的一个准确的决定见或不见,这样好给人家一个明确的答复。为了减少不确定性,朋友需要从你这里获得尽可能多的信息。那么信息如何度量呢?朋友从你这里获取的信息越多,对你的态度信息得知的越明确,那么要不要与女方见不见面的不确定性就越低。因此,获知的信息量与决定的不确定性相对应。使用熵来表示不确定性的度量。那么熵又是什么呢?

如果一件事有 k 种不确定的可能结果,每种结果的概率为如下;

机器学习算法-决策树
P(i) 为 i 的概率,i 为1··· K 中任意可能

对此事件的结果进行观察后得到的信息为

机器学习算法-决策树

其中熵越大,随机变量(见与不见)的不确定性越大。如果熵为 0 说明没有不确定性,比如你没有一次去见80岁的小姐姐

  • 决策树特征选择 – 条件熵 (Conditional Entropy)

随机样本 X 已知的情况下,随机分类样本 Y 不确定性即为 分类样本Y条件熵,用H(Y|X)表示

条件熵 H( Y[见、不见] | X[长相、身高、收入···] ) 表示在已知随机变量X的条件下随机变量Y的不确定性。例如,知道女方年龄的前提条件下,得出见与不见的不确定性是多少

机器学习算法-决策树
条件熵公式

例如 朋友给你准备了一系列可供挑选的女朋友信息X1,X2,·····Xn,希望你给出见或不见的结果 Y1,Y2,·····Yn

样本号X=身高X=漂亮X=性格Y=是否相见
1一般温和不见
2一般温和不见
3漂亮温和
4漂亮温和
5漂亮温和
6漂亮暴躁不见
7漂亮暴躁不见
8漂亮暴躁不见

其中的分类样本空间 (叶节点) Y 的空间范围为

样本变量值不见
样本值分布不见=5次见=3次
值概率分布Y为不见的概率:
P(Y=不见) = 5/8
Y为见的概率:
P(Y=见) = 3/8

样本空间 (内部节点) 当 X = 身高 时 X 的空间范围为

身高特征
总数 8  高矮相加
身高-高概率为:
P(身高=高)=3/8
身高-矮概率为:
P(身高=矮)=5/8
身高 X = 高
X 总数为 3
Y 的概率分布为
Y=不见 | X=高
不见 | 高 = 2次
p(不见 | 高)=2/3
Y=见 | X=高
见 | 高 = 1
p(见 | 高) = 1/3
Info(Y | 身高=高)
-2/3log(2/3)-1/3log(1/3)
身高 X = 矮
X 总数为 5
Y 的概率分布为
Y=不见 | X=矮
不见 | 矮= 3
p(不见 | 矮)=3/5
Y=见 | X=矮
见 | 矮 = 2
p(见 | 矮)=2/5
Info(Y | 身高=矮)
-3/5log(3/5)-2/5log(2/5)

通过整理我们可以求出当已知 X =身高 的条件下的分类样本空间 Y 的 (不确定性)条件熵

H(Y={不见 , 见}}|X=身高)
= p(身高=高) * H(Y|身高=高) + p(身高=矮) * H(Y|身高=矮)    
=(3/8) * {-2/3log(2/3)  -1/3log(1/3)}  +  (5/8)* {-3/5log(3/5) -2/5log(2/5)}  

机器学习算法-决策树

X = 长相 的条件下的分类样本空间 Y 的 (不确定性) 条件熵

H( Y={不见, 见}|X=长相)  
= p(X长相 = 一般) * H(Y|X长相 = 一般) + p(长相 = 漂亮) * H( Y|X长相 = 漂亮)
= (2/8) * {-2/2log(2/3)  -0/2log(0/2)}  +  (6/8)* {-3/6log(3/6) -3/6log(3/6)}  

机器学习算法-决策树

X = 性格 的条件下的分类样本空间 Y 的 (不确定性) 条件熵

H(Y={不见 , 见}|X=性格)  
= p(X性格=温和) * H(Y|X性格=温和) + p(性格=暴躁) * H(Y|X性格=暴躁)  
= (5/8) * {-2/5log(2/5)  -3/5log(3/5)}  +  (3/8)* {-3/3log(3/3)  -0/3log(0/3)}  

机器学习算法-决策树
#python 2.7
#coding:utf8
import math
import numpy as np

# X = 身高
# math 计算
print (3.0/8.0) * (-2.0/3.0*math.log(2.0/3.0,2)  -1.0/3.0*math.log(1.0/3.0,2))  +  (5.0/8.0) * (-3.0/5.0*math.log(3.0/5.0,2) -2.0/5.0*math.log(2.0/5.0,2))
# np 计算
print (3.0/8.0) * (-2.0/3.0*np.log2(2.0/3.0)  -1.0/3.0*np.log2(1.0/3.0))  +  (5.0/8.0) * (-3.0/5.0*np.log2(3.0/5.0)-2.0/5.0*np.log2(2.0/5.0))

# X = 长相
# math 计算
print (2.0/8.0) * (-2.0/2.0*math.log(2.0/3.0,2)  -0/2.0)  +  (6.0/8.0) * (-3.0/6.0*math.log(3.0/6.0,2) -3.0/6.0*math.log(3.0/6.0,2))
# np 计算
print (2.0/8.0) * (-2.0/2.0*np.log2(2.0/3.0)  -0/2.0)  +  (6.0/8.0) * (-3.0/6.0*np.log2(3.0/6.0) -3.0/6.0*np.log2(3.0/6.0))

# X = 脾气
# math 计算
print (5.0/8.0) * (-2.0/5.0*math.log(2.0/5.0,2)  -3.0/5.0*math.log(3.0/5.0,2))  +  (3.0/8.0) * (-3.0/3.0*math.log(3.0/3.0,2)  -0/3.0)
# np 计算
print (5.0/8.0) * (-2.0/5.0*np.log2(2.0/5.0)  -3.0/5.0*np.log2(3.0/5.0))  +  (3.0/8.0) * (-3.0/3.0*np.log2(3.0/3.0)  -0/3.0)

通过以上信息可以得出 叶节点 Y 在已知 X 的情况下其条件熵的值如下:
已知 X = 身高 Y {不见 | 见}的条件熵为 0.95120505930
已知 X = 长相 Y {不见 | 见}的条件熵为 0.89624062518
已知 X = 脾气 Y {不见 | 见}的条件熵为 0.60684412153

  • 决策树特征选择 – 信息增益 (informat Gain)

信息增益表示得知内部节点(特征) X=年龄 的信息使得叶节点分类 Y (见与不见)的信息的不确定性减少程度。特征 X 对训练 叶节点分类数据集 Y 的信息增益g(D,A),定义为集合 D 的经验熵 H(A) 与特征 A 给定条件下的经验条件熵 H(D|A) 之差,熵 H(Y) 与条件熵H(Y|X)之差称为互信息,即g(D,A)。信息增益大表明信息增多,信息增多,则不确定性就越小,朋友应该选择能使信息增益增大的条件询问你。

http://absec.cn/wp-content/uploads/2019/01/456673-20150929223440746-1947706262.png
信息增益计算公式

其中信息增益特征的选择需要遵循:求出每个特征的信息增益,选择信息增益最大的特征。

  • 决策树特征选择 – 信息增益率

信息增益率定义: 特征A对训练数据集D的信息增益比定义为其信息增益与训练数据D关于特征A的值的熵HA(D)之比

原创文章,作者:absec,如若转载,请注明出处:http://absec.cn/?p=55

发表评论

电子邮件地址不会被公开。 必填项已用*标注

联系我们

010-61943626

在线咨询:点击这里给我发消息

邮件:marketing@anbai.com

工作时间:电话:周一至周五,10:00-18:30,节假日休息,邮件随时发哦~