1700534661
1700534662
1700534663
1700534664
图3.15 初始决策树T0
1700534665
1700534666
1700534667
1700534668
1700534669
图3.16 对初始决策树T0的t3结点剪枝得到新的子树T1
1700534670
1700534671
而后继续计算所有结点对应的误差增加率，分别为α(t1)=3，α(t2)=3，α(t4)=4。因此对t1进行剪枝，得到T2，如图3.17所示。此时α(t0)=6.5，α(t2)=3，选择t2进行剪枝，得到T3。于是只剩下一个内部结点，即根结点，得到T4。
1700534672
1700534673
在步骤（2）中，我们需要从子树序列中选出真实误差最小的决策树。CCP给出了两种常用的方法：一种是基于独立剪枝数据集，该方法与REP类似，但由于其只能从子树序列{T0,T1,T2,…,Tn}中选择最佳决策树，而非像REP能在所有可能的子树中寻找最优解，因此性能上会有一定不足。另一种是基于k折交叉验证，将数据集分成k份，前k−1份用于生成决策树，最后一份用于选择最优的剪枝树。重复进行N次，再从这N个子树中选择最优的子树。
1700534674
1700534675
1700534676
1700534677
1700534678
图3.17 对T1中t1结点剪枝得到新的子树T2
1700534679
1700534680
代价复杂度剪枝使用交叉验证策略时，不需要测试数据集，精度与REP差不多，但形成的树复杂度小。而从算法复杂度角度，由于生成子树序列的时间复杂度与原始决策树的非叶结点个数呈二次关系，导致算法相比REP、PEP、MEP等线性复杂度的后剪枝方法，运行时间开销更大。
1700534681
1700534682
剪枝过程在决策树模型中占据着极其重要的地位。有很多研究表明，剪枝比树的生成过程更为关键。对于不同划分标准生成的过拟合决策树，在经过剪枝之后都能保留最重要的属性划分，因此最终的性能差距并不大。理解剪枝方法的理论，在实际应用中根据不同的数据类型、规模，决定使用何种决策树以及对应的剪枝策略，灵活变通，找到最优选择，是本节想要传达给读者的思想。
1700534683
1700534684
逸闻趣事
1700534685
1700534686
1700534687
1700534688
奥卡姆剃刀定律（Occam’s Razor，Ockham’s Razor）
1700534689
1700534690
14世纪，逻辑学家、圣方济各会修士奥卡姆威廉（William of Occam）提出奥卡姆剃刀定律。这个原理最简单的描述是“如无必要，勿增实体”，即“简单有效原理”。
1700534691
1700534692
很多人误解了奥卡姆剃刀定律，认为简单就一定有效，但奥卡姆剃刀定律从来没有说“简单”的理论就是“正确”的理论，通常表述为“当两个假说具有完全相同的解释力和预测力时，我们以那个较为简单的假说作为讨论依据”。
1700534693
1700534694
奥卡姆剃刀的思想其实与机器学习消除过拟合的思想是一致的。特别是在决策树剪枝的过程中，我们正是希望在预测力不减的同时，用一个简单的模型去替代原来复杂的模型。而在ID3决策树算法提出的过程中，模型的创建者Ross Quinlan也确实参照了奥卡姆剃刀的思想。类似的思想还同样存在于神经网络的Dropout的方法中，我们降低模型复杂度，为的是提高模型的泛化能力。
1700534695
1700534696
严格讲，奥卡姆剃刀定律不是一个定理，而是一种思考问题的方式。我们面对任何工作的时候，如果有一个简单的方法和一个复杂的方法能够达到同样的效果，我们应该选择简单的那个。因为简单的选择是巧合的几率更小，更有可能反应事物的内在规律。
1700534697
1700534698
1700534699
1700534700
1700534701
百面机器学习：算法工程师带你去面试 [:1700532187]
1700534702
百面机器学习：算法工程师带你去面试 第4章 降维
1700534703
1700534704
宇宙，是时间和空间的总和。时间是一维的，而空间的维度，众说纷纭，至今没有定论。弦理论说是9维，霍金所认同的M理论则认为是10维。它们解释说人类所能感知的三维以外的维度都被卷曲在了很小的空间尺度内。当然，谈及这些并不是为了推荐《三体》系列读物，更不是引导读者探索宇宙真谛，甚至怀疑人生本质，而是为了引出本章的主题——降维。
1700534705
1700534706
机器学习中的数据维数与现实世界的空间维度本同末离。在机器学习中，数据通常需要被表示成向量形式以输入模型进行训练。但众所周知，对向维向量进行处理和分析时，会极大地消耗系统资源，甚至产生维度灾难。因此，进行降维，即用一个低维度的向量表示原始高维度的特征就显得尤为重要。常见的降维方法有主成分分析、线性判别分析、等距映射、局部线性嵌入、拉普拉斯特征映射、局部保留投影等。本章将选取比较经典的主成分分析和线性判别分析进行介绍和对比，以便读者更深入地理解降维的基本思想。
1700534707
1700534708
1700534709
1700534710