初学机器学习西瓜书的概要记录（一）机器学习基础知识篇(已完结)
初学机器学习西瓜书的概要记录（二）常用的机器学习方法篇(持续更新)
初学机器学习西瓜书的概要记录（三）进阶知识篇(待更)

文字公式撰写不易，随意学习，转载请注明！谢谢

以下内容出自周志华老师亲讲西瓜书

4.1 决策树的基本流程

决策树基于“树”结构进行决策

• 每个内部结点对应某个属性上的测试
• 每个分支对应于该测试的一种可能结果（即该属性的某个取值）
• 每个叶结点对应于一个预测结果
  

学习过程：通过对训练样本的分析来确定“划分属性”（即内部结点所对应的属性）
预测过程：将测试示例从跟结点开始，沿着划分属性所构成的“判定测试序列”下行，直到叶结点
策略：分而治之，自根至叶的递归过程，在每个中间结点寻找一个"划分"属性

对当前某个结点进行划分时，确定递归停止的三种条件：

• 当前结点包含的样本全属于同一类别，无需划分；
• 当前属性集为空，或是所以样本在所有属性上取值相同，无法划分；
• 当前结点包含的样本集为空，不能划分。
  

4.2 信息增益划分

决策树的提出是收到信息论的启发，因此很多东西是以信息论的准测进行判断，而在信息论中最重要的一个量就是“熵”
信息熵是度量样本集合“纯度”最常用的一种指标，假定当前样本集合 $D$ 中第 $k$ 类样本所占的比例为 $p_k$，则 $D$ 的信息熵定义为
$$Ent(D)=-\sum _{k=1}^{|y|}{p}_{k}lo{g}_2{p}_k$$
计算信息熵时约定：若 $p=0$，则 $plo{g}_{2}p=0$
$Ent(D)$ 的值越小，则 $D$ 的纯度越高，$Ent(D)$ 的最小值为 0，最大值为 $lo{g}_2|y|$
信息增益直接以信息熵为基础，计算当前划分对信息熵所造成的变化

离散属性 $a$ 的取值： { a 1 , a 2 , . . . , a V } \{a^1,a^2,...,a^V\} {a1,a2,...,aV}
$D^v$：$D$ 在 $a$ 上取值 $=a^v$的样本集合
以属性 $a$ 对数据集 $D$ 进行划分所获得的新增增益为：
$$Gain(D,a)=Ent(D)-\sum _{v=1}^V\frac{|D^v|}{|D|}Ent(D^v)$$
其中：
$Ent(D)$ 为划分前的信息熵
$\frac{|D^v|}{|D|}$ 为第$v$个分支的权重，样本越多越重要
$Ent(D^v)$ 为划分后的信息熵