说来真是惭愧，今天上午看了一个阿里云大学的课，中午吃完饭就信心十足点击 “考试” 了，结果.....
OK ,里面考了很多决策树的知识，想想也对，课程中唯一提到的机器学习算法就是决策树，你说考不考(ノへ￣、)
总之，单单靠之前学习的一点知识机器学习入门|决策树（一）是远远不够对付这场考试的，以考促学，OK！
下面让我们再深入的了解一下决策树吧！
注：再看这一篇之前，最好先回顾一下上一篇机器学习入门|决策树（一），之前提过的概念，这篇就不再啰嗦啦(/▽＼)
信息增益与ID3算法
ID3算法（Iterative Dichotomiser 3，迭代二叉树3代），是Ross Quinlan发明的一种决策树算法。
这个算法是建立在奥卡姆剃刀的基础上：越是小型的决策树越优于大的决策树（简单理论）。尽管如此，该算法也不是总是生成最小的树形结构。而是一个启发式算法。奥卡姆剃刀阐述了一个信息熵的概念：
$$ Ent(D)=-\sum_{k=1}^{|\gamma|}p_{k}log_{2}p_{k}. $$
进而引入信息增益：
$$ Gain(D,a)=Ent(D)-\sum_{v=1}^{V}\frac{|D^{v}|}{|D|}Ent(D^{v}). $$
这个ID3算法可以归纳为以下几点：
- 分别计算各个属性的信息增益
- 选取其中信息增益最大的属性最为划分属性
- 生成包含该属性的结点
ID3算法的核心思想就是以信息增益来度量属性的选择，选择分裂后信息增益最大的属性进行分裂。该算法采用自顶向下的贪婪搜索遍历可能的决策空间。
ID3算法的一些优缺点：
- ID3算法在构造决策树的结构时从不回溯，是一种典型的贪婪搜索算法
- 用信息增益选择属性时偏向于选择分枝比较多的属性值，即取值多的属性（这个在上一篇中提到了）
- 不能处理连续值的属性
- 不做剪枝，容易过拟合
增益比率与C4.5算法
信息增益是一种选择特征的有效办法，但是它偏向于选择取值较多的哪些特征。比如，按编号进行划分，会产生庞大的分支，而每一支分支只包含一个样例。这种情况下为“纯”划分，此时信息增益为最大，但是这种划分对于分类并无意义。因此需要对具有不同特征值数目的特征进行校准。于是C4.5算法就在ID3的基础上引入了增益比率：
$$ Gain-ratio(D,a)=\frac{Gain(D,a)}{IV(a)}, $$
其中
$$ IV(a)=-\sum_{v=1}^{V}\frac{|D^{v}|}{|D|}log_{2}\frac{|D^{v}|}{|D|} $$
C4.5算法改进了ID3算法，ID3算法只能处理离散型特征，而C4.5算法能够处理连续型特征。C4.5算法对数据进行预处理将连续型特征离散化。
那么，问题来了。
怎么将连续型的特征离散化呢？
最简单的策略是采取二分法（bi-partition）对连续属性进行处理，这正是C4.5决策树算法中采用的机制。
给定样本集$D$和连续属性$a$，假定$a$在$D$上出现了$n$个不同的取值，将这些值从小到大进行排序，记为$\left\{a^{1},a^{2},...,a^{n}\right\}.$基于划分点$t$可将$D$分为子集$D_{t}^{-}$和$D_{t}^{+}$，其中$D_{t}^{-}$包含那些属性$a$上取值不大于$t$的样本，$D_{t}^{+}$相反。显然，对于相邻的属性取值$a^{i}$与$a^{i+1}$来说，$t$在区间$[a^{i},a^{i+1})$中取任意值所产生的划分结果相同。因此，对连续属性$a$，我们可考察包含$n-1$个元素的候选划分点集合
$$ T_{a}=\left \{ \frac{a^i+a^{i+1}}{2}|1\leqslant i\leqslant n-1 \right \}, $$
即把区间$[a^i,a^{i+1})$的中位点作为候选划分点。然后，我们就可以像离散属性值一样来考察这些划分点，选取最优的划分点进行样本集合的划分
$$ Gain(D,a)=\underset{t\in T_a}{max}\;Gain(D,a) $$
$$ =\underset{t\in T_a}{max}Ent(D)-\underset{\lambda \in \left\{-,+ \right \}}{\sum}\frac{|D^{\lambda }_{t}|}{|D|}Ent(D^{\lambda }_{t}) $$
其中$Gain(D,a,t)$是样本集$D$基于划分点$t$二分后的信息增益。于是，我们就可选择使$Gain(D,a,t)$最大化的划分点。
这里可能有难理解，举个例子。就比如说判别一个西瓜好坏的属性中有一个叫做“纹理”，它就是可以用ID3算法来处理的离散值，取值有1.清晰，2.稍糊，3.模糊.很容易根据ID3中信息增益的公式求出其信息增益。好了，现在回到我们要处理的连续值，这可麻烦大了！连续值该怎么求！因为不是说取固定一个值来作为划分点，我们这里是要找到连续值属性比如密度的信息增益，求法如上，比如可以得到密度$\leqslant $0.318的为好瓜，反之为坏瓜，当然如果划分出来的“纯度”还是不高，那还可以再分，也可以再次用密度这个属性（注意！！这跟离散值不同了，离散值属性划分完就不可以再用了）。OK，对比一下，仔细思考，希望能理解，不理解可以留言噢（￣︶￣）↗
再次强调，与离散属性不同，若当前结点划分属性为连续属性，该属性还可以作为其后代结点的划分属性。
和ID3相比的改进：
- 用信息增益率代替信息增益
- 能对连续属性进行离散化，对不完整数据进行处理
- 进行剪枝
补充:在阿里云大学课堂中还介绍了C50算法，其相对于C4.5的改进：
- 使用了boosting
- 预剪枝，后剪枝
Gini指数与CART算法
CART(classification and regression tree)算法，即分类回归树，顾名思义，是一个既能用于分类（如ID3算法，C4.5算法），又能用于回归的算法。
至于基尼指数计算都在机器学习入门|决策树（一）中了。
根据视频中的，CART总结：
- 核心是基尼系数（Gini）
- 分类是二叉树
- 支持连续值和离散值
- 后剪枝进行修剪
- 支持回归，可以预测连续值
总结
OK !写完这篇博客，再战！
啥？只是飘过，有啥得意的╰(￣ω￣ｏ)
但我觉得，OK就行！
参考：
wiki
于 剑 《机器学习：从公理到算法》
周志华 《机器学习》
