【AI学习笔记】初学机器学习西瓜书概要记录（二）常用的机器学习方法篇
初学机器学习西瓜书的概要记录（一）机器学习基础知识篇(已完结)
初学机器学习西瓜书的概要记录（二）常用的机器学习方法篇(持续更新)
初学机器学习西瓜书的概要记录（三）进阶知识篇(待更)
文字公式撰写不易，随意学习，转载请注明！谢谢
（二）常用的机器学习方法篇
- 4.1 决策树的基本流程
- 4.2 信息增益划分
以下内容出自周志华老师亲讲西瓜书
4.1 决策树的基本流程
决策树基于“树”结构进行决策
- 每个内部结点对应某个属性上的测试
- 每个分支对应于该测试的一种可能结果（即该属性的某个取值）
- 每个叶结点对应于一个预测结果
学习过程：通过对训练样本的分析来确定“划分属性”（即内部结点所对应的属性）
预测过程：将测试示例从跟结点开始，沿着划分属性所构成的“判定测试序列”下行，直到叶结点
策略：分而治之，自根至叶的递归过程，在每个中间结点寻找一个"划分"属性
对当前某个结点进行划分时，确定递归停止的三种条件：
- 当前结点包含的样本全属于同一类别，无需划分；
- 当前属性集为空，或是所以样本在所有属性上取值相同，无法划分；
- 当前结点包含的样本集为空，不能划分。
4.2 信息增益划分
决策树的提出是收到信息论的启发，因此很多东西是以信息论的准测进行判断，而在信息论中最重要的一个量就是“熵”
信息熵是度量样本集合“纯度”最常用的一种指标，假定当前样本集合 D D D 中第 k k k 类样本所占的比例为 p k p_k pk，则 D D D 的信息熵定义为
E n t ( D ) = − ∑ k = 1 ∣ y ∣ p k l o g 2 p k Ent(D)=-\sum^{|y|}_{k=1}p_klog_2p_k Ent(D)=−k=1∑∣y∣pklog2pk
计算信息熵时约定：若 p = 0 p=0 p=0，则 p l o g 2 p = 0 plog_2p=0 plog2p=0
E n t ( D ) Ent(D) Ent(D) 的值越小，则 D D D 的纯度越高， E n t ( D ) Ent(D) Ent(D) 的最小值为 0，最大值为 l o g 2 ∣ y ∣ log_2{|y|} log2∣y∣
信息增益直接以信息熵为基础，计算当前划分对信息熵所造成的变化
离散属性 a a a 的取值： { a 1 , a 2 , . . . , a V } \{a^1,a^2,...,a^V\} {a1,a2,...,aV}
D v D^v Dv： D D D 在 a a a 上取值 = a v =a^v =av的样本集合
以属性 a a a 对数据集 D D D 进行划分所获得的新增增益为：
G a i n ( D , a ) = E n t ( D ) − ∑ v = 1 V ∣ D v ∣ ∣ D ∣ E n t ( D v ) Gain(D,a)=Ent(D) - \sum_{v=1}^V{|D^v|\over |D|}Ent(D^v) Gain(D,a)=Ent(D)−v=1∑V∣D∣∣Dv∣Ent(Dv)
其中：
E n t ( D ) Ent(D) Ent(D) 为划分前的信息熵
∣ D v ∣ ∣ D ∣ {|D^v|\over |D|} ∣D∣∣Dv∣ 为第 v v v个分支的权重，样本越多越重要
E n t ( D v ) Ent(D^v) Ent(Dv) 为划分后的信息熵