决策树
$$ Gini_index(D,a)=\frac{|D^{a=v}|}{D}Gini(D^{a=v}) + \frac{|D^{a\neq v}|}{D}Gini(D^{a\neq v}) $$
特点
- 算法原理
- 从逻辑角度,一堆$if \enspace else$语句的组合
- 从几何角度,根据某种准则划分特征空间
- 最终目的:将样本越分越纯
补充
-
在对数几率回归中我们了解了自信息、信息熵，下面引入一个新的概念，纯度。
-
纯度与信息熵成反比，但似乎无法计算，只能依靠计算信息熵来反映
-
条件熵定义：
- 假设现有关于变量$a$的集合$D$，计为$a\in{a^1,a^2,a^3…a^n}$
- $D^v$表示当满足条件$v$时，变量$a$的集合，计为$a\in{a^1,a^2,a^3…a^n}$
- $\frac{|D^v|}{D}$表示满足条件的$a$集合$D^v$，在所有$a$变量集合中的占比
- 那么满足条件$v$后，集合$D$的条件熵计为$\sum\limits_{v=1}^{V}\frac{|D^v|}{D}Ent(D^v)$
-
信息增益定义：
- 在满足条件v后，变量a取值不确定的减少量，也即纯度的提升 $$ Gain(D,a)=Ent(D)-\sum\limits_{v=1}^{V}\frac{|D^v|}{D}Ent(D^v) $$
模型种类
-
$ID3$决策树
-
模型表达式： $$ a_*=arg\enspace max\enspace Gain(D,a) $$
-
模型缺陷：
- 信息增益准则对可能取值数目较多的属性有所偏好，造成每个取值里面所包含的样本量太少，极端情况下，每种特殊划分的取值中仅包含一个样本，在这种情况下，决策树模型过拟合失效
-
-
$C4.5$决策树
-
模型由来：
- 为解决$ID3$模型的缺陷，现引入权重IV来减少高取值数目属性的信息增益
-
因此引入新定义：增益率 $$ Gain_ratio(D,a)=\frac{Gain(D,a)}{IV(a)} $$
- 其中$IV(a)=-\sum\limits_{v=1}^{V}\frac{|D^v|}{D}log_2\frac{|D^v|}{D}$，称为$a$的固有值
- $a$的取值个数$V$越大，通常$IV(a)$越大
- 因此，增益率对可能取值数目较少的属性有所偏好，性质与信息增益正好相反
-
改善后的模型思路：
- 先基于$ID3$模型，选择出信息增益率高于平均水平的属性，然后在基于增益率定义，从中选择出增益率最高的属性
- 用人话：先将所有属性按照增益率高低排序，选取前50%，保证基本盘；而后筛选掉其中取值数目较多的属性
-
-
$CART$决策树
-
模型由来：
- 有别于$ID3$的思路，引入新概念基尼值用于衡量纯度
-
基尼值定义：
-
从集合$D$中随机抽取两个样本，其类别标记不一致的概率。
-
因此，基尼值越小，碰到异类的概率越小，纯度越高。 $$ Gini(D)=\sum\limits_{k=1}^{|y|}\sum\limits_{k\neq1}^{}p_k p_k’\newline =\sum\limits_{k=1}^{|y|}p_k(1-p_k)\newline =1-\sum\limits_{k=1}^{|y|}p_k^2 $$
-
类比信息熵和条件熵，我们得出在条件$v$下的基尼指数 $$ Gini_index(D,a)=\sum\limits_{v=1}^{V}\frac{|D^v|}{D}Gini(D^v) $$
-
-
模型表达式： $$ a_*=arg\enspace max\enspace Gini_index(D,a) $$
-
实际构造算法：
-
基于每个属性$a$的每个可能取值$v$，将数据集$D$分为$a=v$和$a\neq v$两部分计算基尼值 $$ Gini_index(D,a)=\frac{|D^{a=v}|}{D}Gini(D^{a=v}) + \frac{|D^{a\neq v}|}{D}Gini(D^{a\neq v}) $$
-
选择基尼指数最小的属性及其对应取值作为最有划分属性和最优划分点
-
重复以上两步，知道满足停止条件
-
因此，$CART$决策树一定是二叉树，而$ID3$不一定是二叉树
-
-
适用范围
- 主流的使用方法是在集成学习的时候用作森林模型