决策树一句话概括

通过信息增益，采用递归的方式生成树（找出最合适的节点顺序以及叶子对应的类标签）

举个栗子: 是否买计算机

问题描述：已知1024个人的年龄、收入、职业是否为学生、信誉是否良好及是否会有买计算机的行为，若已知一个新人的年龄、收入等信息，请判断该新人是否会买计算机。

数学表达：已知 1024 个样本的特征向量 ( x⁽¹⁾, x⁽²⁾, x⁽⁴⁾, x⁽⁴⁾) 和预测值Y以及新样本的特征向量，计算新样本预测值Y。

如图所示：

人数	年龄	收入	是否学生	信誉	标签：是否买计算机
64	青	高	否	良	不买
64	青	高	否	优	不买
128	中	高	否	良	买
60	老	中	否	良	买
64	老	低	是	良	买
64	老	低	是	优	不买
64	中	低	是	优	买
128	青	中	否	良	不买
64	青	低	是	良	买
132	老	中	是	良	买
64	青	中	是	优	买
32	中	中	否	优	买
32	中	高	是	良	买
63	老	中	否	优	不买
1	老	中	否	优	买
新样本	青	低	否	良	？

• 总人数：1024
  买的人数：641
  不买的人数：383
• 青年：384
  青年中买的人数：128
  青年中不买的人数：256
• 中年：256
  中年买：256
  中年不买： 0
• 老年： 252
  老年买： 125
  老年不买： 127
• 学生：略
• 非学生： 略

决策树步骤

一、总览

def createBranch():
    #判断边界
    if 数据集中的每个子项是否属于同一分类(是):
        return 类标签(叶子)    
    #递归生成树
    else：
        寻找划分数据集的最好特征         
        划分数据集                  
        创建分支结点    
            for 每个划分的子集：    
                createBranch()    
            return 分支结点

二、寻找划分数据集的最好特征

ID3：信息增益

C4.5：信息增益率

CART：基尼系数

三、具体过程——以ID3算法为例

• 基本数学符号：

m 个样本 —— m 个人

n 个特征向量 ( X⁽¹⁾, X⁽²⁾, ... , X⁽ⁿ⁾) —— ( X⁽¹⁾, X⁽²⁾, X⁽⁴⁾, X⁽⁴⁾ )

预测值 { Y₁, Y₂, ..., Y_k } —— { Y₁: 买, Y₂: 不买 }

新样本X = ( x⁽¹⁾, x⁽²⁾, ... , x⁽ⁿ⁾) —— 新人X= ( x⁽¹⁾, x⁽²⁾, x⁽³⁾, x⁽⁴⁾ )

---

• 概率计算

X 为买时概率为：
p(Y_1) = 641 / 1024

不买时概率为：
p(Y_2) = 383 / 1024

X在年龄为青年的条件下买电脑的概率为 ：
p(Y_1|youth) = 128 / 384

X在年龄为青年的条件下不买电脑的概率为：
p(Y_2|youth) = 256 / 384

X在年龄为中年的条件下买电脑的概率为：
p(Y_1|middle) = 256 / 256

X在年龄为中年的条件下不买电脑的概率为：
p(Y_2|middle) = 0 / 256

X在年龄为老年的条件下买电脑的概率为：
p(Y_1|old) = 125 / 252

X在年龄为老年的条件下不买电脑的概率为：
p(Y_2|old) = 127 / 252

---

• 寻找划分数据集的最好特征——信息增益

信息熵的大小指的是了解一件事情所需要付出的信息量是多少，这件事的不确定性越大，要搞清它所需要的信息量也就越大，也就是它的信息熵越大，信息熵：
H(Y) = -\sum_{i=1}^{i=k}{p(Y_i)log_2(Y_i)}= -p(Y_1)log_2(p(Y_1))-p(Y_2)log_2(p(Y_2)) = 0.9537

条件熵：
H(Y|age) = p(youth)H(Y|youth) + p(middle)H(Y|middle) + p(old)H(Y|old)=0.6877

其中：
H(Y|youth) = -\sum_{i=1}^{i=k}{p(Y_i|youth)}log_2(p(Y_i|youth)) = p(Y_1|youth)log_2(p(Y_1|youth)+p(Y_2|youth)log_2(p(Y_2|youth) = 0.9183

H(Y|middle) = 0

H(Y|old) = 0.9157

信息增益：
IG(age) = H(Y) - H(Y|age) = 0.9537 - 0.6877 = 0.2660

同理：
IG(income) = H(Y) - H(Y|income) = 0.0176

IG(Student) = H(Y) - H(Y|Student) = 0.01726

IG(credit) = H(Y) - H(Y|credit) = 0.0453

---

• 划分数据集，创建分支节点

年龄的信息增益最大，因此第一个结点为年龄，即：

将样本划分为青年、中年和老年三个数据集，在青年这个数据集中：
H(youth) = H(Y|youth)= 0.9183

IG(income)= H(youth) - H(youth|income)

IG(student)= H(youth) - H(youth|student)

IG(credit) = H(youth) - H(youth|redit)

其中是否为学生的信息增益最大，因此选择是否为学生作为青年集的结点，将青年数据集划分为学生集与非学生集，即：

在中年这个数据集中，所有人都会买电脑，属于同一个类别，返回类标签即可：

在老年这个数据集中，信誉的增益最大，因此选择将信誉作为老年集的结点，将其划分为优信誉集与良信誉集，即：

最终生成的决策树：略

四、补充

剪枝处理

• 预剪枝
• 后剪枝

连续与缺失值

• 连续值

• 缺失值

• 待更新

参考：
《机器学习实战》【美】Peter Harrington