[TOC]
从LR到决策树
1、总体流程与核心问题
首先，在了解树模型之前，自然想到线性模型和树模型有什么区别呢？其中最重要的是，树形模型是一个一个特征进行处理，之前线性模型是所有特征给予权重相加得到一个新的值。决策树与逻辑回归的分类区别也在于此，逻辑回归是将所有特征通过sigmoid函数变换为概率后，通过大于某一概率阈值的划分为一类，小于某一概率阈值的为另一类；而决策树是对每一个特征做一个划分。另外逻辑回归只能找到线性分割（输入特征x与logit之间是线性的，除非对x进行多维映射），而决策树可以找到非线性分割。
而树形模型更加接近人的思维方式，可以产生可视化的分类规则，产生的模型具有可解释性（可以抽取规则）。树模型拟合出来的函数其实是分区间的阶梯函数。
决策树学习：采用自顶向下的递归的方法，基本思想是以信息熵为度量构造一棵熵值下降最快的树，到叶子节点处熵值为0（叶节点中的实例都属于一类）。
其次，需要了解几个重要的基本概念：根节点（最重要的特征）；父节点与子节点是一对，先有父节点，才会有子节点；叶节点（最终标签）。
2、熵、信息增益、信息增益率
信息熵(Information Entropy)
信息熵是用来评估样本集合的纯度的一个参数，就是说，给出一个样本集合，这个样本集合中的样本可能属于好多不同的类别，也可能只属于一个类别，那么如果属于好多不同的类别的话，我们就说这个样本是不纯的，如果只属于一个类别，那么，我们就说这个样本是纯洁的。
而信息熵这个东西就是来计算一个样本集合中的数据是纯洁的还是不纯洁的。下面上公式：
下面解释一下公式的意思，其实很好理解，计算一个集合的纯度，就是把集合中每一个类别所占的比例（k从1到
，其中
表示类别的个数）乘上它的对数，然后加到一起，然后经过计算之后，可以得到一个数据集的信息熵，然后根据信息熵，可以判断这个数据集是否纯粹。信息熵越小的话，表明这个数据集越纯粹。信息熵的最小值为0，此时数据集D中只含有一个类别。
信息增益(Information Gain)
下面来介绍信息增益，所谓的信息增益，是要针对于具体的属性来讲的，比如说，数据集D中含有两个类别，分别是好人和坏人，那么，随便选择一个属性吧，比如说性别，性别这个属性中包含两个值，男人和女人，如果用男人和女人来划分数据集D的话，会得到两个集合，分别是和
。划分后的两个集合中各自有 好人和坏人，所以可以分别计算划分后两个集合的纯度，计算之后，把这两个集合的信息熵求加权平均
，跟之前没有划分的时候的信息熵
相比较，用后者减去前者，得到的就是属性-性别对样本集D划分所得到的信息增益。可以通俗理解为，信息增益就是纯度提升值，用属性对原数据集进行划分后，得到的信息熵的差就是纯度的提升值。信息增益的公式如下：
先解释一下上式中的参数，D是数据集，a是选择的属性，a中一共有V个取值，用这个V取值去划分数据集D，分别得到数据集到
，分别求这V个数据集的信息熵，并将其求加权平均。两者的差得到的就是信息增益。
那么这个信息增益有什么用呢？有用，可以根据信息增益值的大小来判断是否要用这个属性a去划分数据集D，如果得到的信息增益比较大，那么就说明这个属性是用来划分数据集D比较好的属性，否则则认为该属性不适合用来划分数据集D。这样有助于去构建决策树。
著名的算法ID3就是采用信息增益来作为判断是否用该属性划分数据集的标准。
信息增益率(Information Gain Ratio)
为什么要提出信息增益率这种评判划分属性的方法？信息增益不是就很好吗？其实不然，用信息增益作为评判划分属性的方法其实是有一定的缺陷的，书上说，信息增益准则对那些属性的取值比较多的属性有所偏好，也就是说，采用信息增益作为判定方法，会倾向于去选择属性取值比较多的属性。那么，选择取值多的属性为什么就不好了呢？举个比较极端的例子，如果将身份证号作为一个属性，那么，其实每个人的身份证号都是不相同的，也就是说，有多少个人，就有多少种取值，它的取值很多吧，让我们继续看，如果用身份证号这个属性去划分原数据集D，那么，原数据集D中有多少个样本，就会被划分为多少个子集，每个子集只有一个人，这种极端情况下，因为一个人只可能属于一种类别，好人，或者坏人，那么此时每个子集的信息熵就是0了，就是说此时每个子集都特别纯。这样的话，会导致信息增益公式的第二项整体为0，这样导致的结果是，信息增益计算出来的特别大，然后决策树会用身份证号这个属性来划分原数据集D，其实这种划分毫无意义。因此，为了改变这种不良偏好带来的不利影响，提出了采用信息增益率作为评判划分属性的方法。
公式如下：
其中的计算方式如下：
被称为是的“固有值”，这个
的公式是不是很熟悉啊，简直和信息熵的计算公式一毛一样，就是看属性a的纯度，如果a只含有少量的取值的话，那么a的纯度就比较高，否则的话，a的取值越多，a的纯度越低，
的值也就越大，因此，最后得到的信息增益率就越低。
采用信息增益率可以解决ID3算法中存在的问题(ID3会对那些属性的取值比较多的属性有所偏好，如西瓜的颜色有10种)，因此将采用信息增益率作为判定划分属性好坏的方法称为C4.5。
需要注意的是，增益率准则对属性取值较少的时候会有偏好，为了解决这个问题，C4.5并不是直接选择增益率最大的属性作为划分属性，而是之前先通过一遍筛选，先把信息增益低于平均水平的属性剔除掉，之后从剩下的属性中选择信息增益率最高的，这样的话，相当于两方面都得到了兼顾。 （结合信息增益与信息增益率使用）
采用信息增益率可以解决ID3算法中存在的问题，因此将采用信息增益率作为判定划分属性好坏的方法称为C4.5。需要注意的是，增益率准则对属性取值较少的时候会有偏好，为了解决这个问题，C4.5并不是直接选择增益率最大的属性作为划分属性，而是之前先通过一遍筛选，先把信息增益低于平均水平的属性剔除掉，之后从剩下的属性中选择信息增益率最高的，这样的话，相当于两方面都得到了兼顾。
基尼指数(gini index):CART中使用
定义：
- 是一种不等性度量；
- 通常用来度量收入不平衡，可以用来度量任何不均匀分布；
- 是介于0~1之间的数，0-完全相等，1-完全不相等；
- 总体内包含的类别越杂乱，基尼指数就越大
基尼不纯度指标
在CART算法中, 基尼不纯度表示一个随机选中的样本在子集中被分错的可能性。基尼不纯度为这个样本被选中的概率乘以它被分错的概率。当一个节点中所有样本都是一个类时，基尼不纯度为零。
假设y的可能取值为{1, 2, …, m},令fifi是样本被赋予i的概率，则基尼指数可以通过如下计算：
Gini(p)=∑Kk=1pk(1−pk)=1−∑Kk=1p2k
反映了从D中随机抽取两个样例，其类别标签不一致的概率。
