LIANYONGXING. BLOG

# 决策树

# 机器学习中分类和预测算法的评估

  • 准确率
  • 速度
  • 鲁棒性
  • 可规模性
  • 可解释性

# 决策树

# 什么是决策树？

决策树是一个类似于流程图的树结构：其中，每个内部节点表示在一个属性上的测试，每个分支代表一个属性输出，而每个树叶节点代表类或类分布。树的最顶层是根节点。

graph TD A[Play 9/Noplay 5] --> C{Weather?} C -->|Sunny| D[Play 2/Noplay 3] C -->|Rainy| E[Play 4/Noplay 2] C -->|Cloudy| F[Play 3/Noplay 0] D -->G{Windy?} G -->|True| H[Play 2/Noplay 0] G -->|False| I[Play 0/Noplay 3] E -->J{Humidity?} J -->|True| K[Play 4/Noplay 0] J -->|False| M[Play 0/Noplay 2]

上面的例子：刚开始有14个样例，首先按照Weaher这个特征来分类，当Cloudy的时候，完全分开；Sunny和Rainy的情况下，样例无法完全分开，因此再根据另一个特征进行分类（第二层分别按照Winyd和Humidity来分类），最好的结果就是按照某个特征，把样例能够完全分开，这样构建一棵树出来，就是决策树（按照不同的特征进行分类时，可能会得到不同的决策树，决策树不唯一）。对测试集进行使用的时候，只需要把样例扔到树里面，就可以得到它的预测结果。

# 熵

1948年，香农提出了“信息熵”的概念。
一条信息的信息量与它的不确定性相关，信息量越大，熵越大，信息的不确定性越大；当一件事确定的时候，它的信息量是零，也就是没有信息量。

信息量公式

H(x)=−∑i=1n(p(xi)∗logp(xi))H(x) = -\sum^{n}_{i=1}(p(x_i)*logp(x_i))

# 例子

RID age student buy or not
1 middle_age yes yes
2 middle_age no yes
3 senior no no
4 youth no yes
5 youth yes yes
6 youth no no

总的信息量为：

info(D)=−46∗log246−26∗log226info(D) = - \frac{4}{6}*log_2\frac{4}{6} - \frac{2}{6}*log_2\frac{2}{6}

如果有年龄信息的话，按照年龄比例算的话，信息量为：

infoage(D)=26∗(−1∗0)+16∗(−1∗0)+36∗(−23∗log223−13∗log213)info_{age}(D) = \frac{2}{6}*(-1*0) + \frac{1}{6}*(-1*0) +\frac{3}{6}*(- \frac{2}{3}*log_2\frac{2}{3} - \frac{1}{3}*log_2\frac{1}{3})

因此年龄信息带来的信息增益为：

Gain(age)=info(D)−infoage(D)Gain(age) = info(D) - info_{age}(D)

同样可以计算出是否是student的信息所带来的信息增益

因此，可以通过比较age和student两个特征所带来的的信息增益的大小，确定哪个特征所带来的信息增益更大，选择信息增益最大的那个特征作为分类标准，最大限度地减小这件事的不确定性。

通过每一层都计算信息增益最大的那个特征，把决策树不断延伸下去，直到某个特征下，完全是某一类样例（buy or not）。

# ID3算法

  • 树以代表训练样本的单个节点开始。
  • 如果样本都在同一个类中，则该节点成为树叶，并用该类标号。
  • 否则，算法使用称为信息增益的度量作为评判标准，选择出信息增益最大的那个特征。这个特征成为该节点的判定标准。
  • （对于所有特征的分类，连续属性必须离散化，给个阈值分成不同的区间，比如某个年龄属性，可能是1到100岁，则需要分成1到30岁、31岁到80岁，81岁到100岁三个区间）。
  • 在节点下，对于选择出的那个特征的每个已知的值都创建一个分支，并根据此划分样本。
  • 算法使用同样的过程，递归的形成每个划分上的样本判定树，如果一个特征已经在上层考虑完了，以后就不再考虑了。
  • 递归划分步骤仅当下列条件之一停止：
    （a）给定节点的所有样本属于同一类。
    （b）没有剩余属性可以进一步划分样本，在这种情况下，使用多数表决

# 其他算法

CART、C4.5，都是贪心算法，自上而下
C4.5是根据信息增益比（gain ratio）划分，CART是根据基尼系数（gini index）

# 其他

# overfitting

如果决策树过深的话，就是分的太细了，容易产生过拟合现象，因此决策树最好不要太深。

  • 先剪枝：树达到一定的深度就不往下生长了
  • 后剪枝：全部分完后，把底下的几层树剪掉

# 优缺点

# 优点

直观，便于理解，小规模数据集有效

# 缺点

  • 处理连续变量不好
  • 类别过多的时候，错误增加的比较快
  • 可规模性一般

← 决策树应用（sklearn） →