决策树

在这里插入图片描述

在这里插入图片描述
决策树划分时，当前属性集为空，或所有样本在所有属性上取值相同，将结点标记为叶节点，其类别标记为当前样本集中样本数最多的类。

决策树算法的核心在于：选择最优划分属性
判别分类的三种情形：

当前节点包含的样本全属于一个类别，则可视为叶子节点，分类就是本身
当前节点为空，则分类就是父类的分类
当前节点包含样本不全属于一个类别，那么多数作为类别

信息增益information gain

在这里插入图片描述

ID3

在二分类任务中，若当前样本集合的正类和负类的数量刚好各一半，此时信息熵为Ent(D)=−(12log212+12log212)=1Ent(D)=-(\frac{1}{2}log_{2}\frac{1}{2}+\frac{1}{2}log_{2}\frac{1}{2})=1Ent(D)=−(21log221+21log221)=1
信息增益=划分前的信息熵-第v个分支的权重*划分后的信息熵
在这里插入图片描述

C4.5

IV(a)IV(a)IV(a)的形式是在做规范化，其把原来不可以直接比较的东西变得可比较。归一化是规范化的特例，归一化是把规范化的范围限制在[0,1]区间。
由于无法判断Gain(D,a)Gain(D,a)Gain(D,a)与IV(a)IV(a)IV(a)之间应该是控制Gain(D,a)Gain(D,a)Gain(D,a)更大，还是控制IV(a)IV(a)IV(a)更小，采用启发式的方法——先从候选划分属性中找出信息增益高于平均水平的，再从中选取增益率最高的。
在这里插入图片描述

CART算法，基尼指数

按照概率来理解，如果每次抓两个球，如果两次抓到的球属于同一类，说明候选属性集合比较纯；因此Gini(D)Gini(D)Gini(D)中，抓球抓到第一类的概率是∑k=1∣y∣pk\sum_{k=1}^{|y|}p_k∑k=1∣y∣pk,抓球抓到第二类的概率是∑k′≠kpk′\sum_{k \prime \ne k}p_k^{\prime}∑k′=kpk′,如果二者乘积越小，数据集D的纯度越高。同理，用1-两次抓出相同类型球的概率（纯度）=不纯度,即Gini(D)Gini(D)Gini(D).
在这里插入图片描述