本篇是接着上一篇的决策树算法学习，只要提到决策树算法，提到ID3，就一定会提到它的改进算法：C4.5
其实在学习C4.5时我曾经困惑于信息增益率的式子，通过几个例子，和几篇博文，大致理清了它的思路，其实对于基本的算法，每篇博文的讲法大致类似，有时间还是应多拜读一些大师们的论文，有利于对算法更好的理解，这段话是对自己的劝诫；好了，言归正传，说一下算法；
首先，C4.5是基于对于ID3的改进：它的改进主要体现在以下三个方面：
1）对于连续值属性的处理，C4.5增加了对连续值属性的处理；
2）ID3有一个很大的弱点在于偏向多值属性，通过增益率解决了这个问题，并且，增益率使得避免选择均匀分布的属性，这是因为作为分母的分裂值=|Si|/|S|log(|Si|/|S|）会得到log2n，而布尔分布则是1，显然后者的增益率会大；
3）C4.5增加了剪枝属性（个人理解：当在比赛或者实践中实现算法时，为了优化算法，几乎不会很死板的只考虑用什么算法，各种优化的方法都会尝试，只要对结果有明显提升，并且空间复杂度和时间复杂度均可接受，都会被应用，说到底，决策树是基于信息增益，各种算法针对了各种情况做出优化，自己明确何种情况用何种算法即可）
对于1），每一篇博文都会介绍信息增益率的公式，
这四个公式是两个算法的核心：自己在这个公式中结合例子理解的，看到一个博文对此描述的不错，对其进行转述，方便理解：首先对于信息熵，主要是根据目标属性算出未划分属性前信息量和划分后信息量；而对于分裂信息它的值不考虑目标属性，而只考虑属性带来的信息含义（结合例子很好懂，要多看昆兰的经典例子）
上面的公式就是基于昆兰的例子给出的~
2）对于剪枝方法，上一节已经说了悲观剪枝，这里补充下预剪枝
预剪枝的方法包括：1）高度：树的高度达到一定的高度就停止；2）宽度：里面包含的种类少于某个阈值，就停止生长；3）类别：并非要一个类，只要其中特征向量相同，也可以停止生长；4）考虑增益情况，没有显著变化可以不生长；不难看出预剪枝有很多主观因素，何为合适阈值，多由经验判断，影响较大；
对于后剪枝问题，除了悲观剪枝法，还有一种方法是错误率降低剪枝，它的确定是采用训练集建立决策树，然后将验证集带入，它将所有的叶子节点视为可减，然后将验证集带入后判断是否有使得错误率降低；该方法简单明了是优点，但由于过于简单，使得它忽略了训练集的效果，只对验证集容易过拟合，因此当验证集比训练集小很多时不太适合；
还有一种下一节会讲到的用于CART算法的代价复杂度剪枝方法（还不是特别明白,下面是按照我的理解，日后有新的理解会对其做出修改）：生成一颗要决策树，它是一个序列形式{T0,T1,.....Tn}其中Ti+1是由Ti基于减去后误差增加最小形成的（还没想明白剩下的）
不过剪枝的依据，依赖于下面一篇博文，它的思想依据主要有三种：
1）基于训练集和验证集的交叉验证（如第一种，错误率剪枝方法）
2）基于统计学理论（悲观剪枝法）
3）使用明确样例以最小化决策树复杂度；
剪枝来得尤为重要，甚至比选择何种方法构造树更为重要~（明白代价复杂度剪枝后会回来补充）