机器学习——决策树

    决策树类似于数据结构中树地分类思想，经常用于分类问题，关键在于信息熵的处理。

   整个算法的过程是一个递归调用的过程， 训练集就是包含全部训练数据样本，属性集就是针对数据样本进行特征划分的判断条件，类别指的是最后的分类结果，在算法的过程中一般选取样本数据最多的类作为结果类别输出，例如第12行。

    在属性集A中，已经完成划分了的属性，将从候选集中扔出，不再参与信息熵的计算。

    整个算法最关键的步骤就是第八行：选择最优秀的划分属性a*，这个划分的选择分别对应了不同的算法。

    在上式中，y表示最终分类的个数，pk就是第k类数据样本所占的比例。Ent越小，说明数据D的纯度越高。

    Dv指的是根据属性V分割后所包含的样本信息，D指的是分割之前的样本信息，每次划分完成之后，D就是新的小范围的样本了，再计算同一属性的信息增益也得重新计算量，因为D发生了变化。第二轮每个部分的属性划分就不再相同了，因为每个部分的样本信息不同，D发生了改变，信息增益的计算也就不一样了。递归的思想。

    增益率就是C4.5算法所采用的

    V表示一个属性划分中的选项个数，比如颜色包括红色、黑色、绿色等。一般情况下V越大Ⅳ（a)也就越大，所以增益率可能对于划分选项个数少的属性有偏好，C4.5并未完全采用增益率，先从候选属性当中找出信息增益高于平均值的属性，然后再从中选择增益率最高的。

    剪枝算法

    剪枝算法是针对过拟合现象提出来的，因为决策树算法是针对特征属性进行学习，可能会对训练样本的特征学习过好，导致模型的泛化能力变差。

    剪枝算法中的泛化能力的评估是在测试集样本上的准确率来代替的。

    预剪枝算法是在划分之前进行计算判断，此次划分对于模型的泛化能力能否得到提升，如果不能则将此节点标记为叶子节点，不再进行划分，从当前分支的样本数据中选择类别属性最多的那一个类作为结果输出。

    后剪枝算法则是在决策树成型之后对于分支节点自底向上进行筛选，如果发现将此节点替换为叶子节点后可以提升模型的泛化能力，则取消此属性划分，将其替换为叶子节点，并从叶子节点中选择数量最多的那个类别作为结果输出。

    预剪枝算法会导致很多分支未展开，属性划分没有用上，降低了过拟合的风险并减少了训练时间，但是会带来欠拟合的风险，模型的性能受限。后剪枝算法会比预剪枝算法保留更多的分支，泛化性能也比较好，由于在决策树构建完成后再自底向上的递归遍历，会使得训练成本显著提升。

    有很多基础的算法，比如多变量决策和缺失值决策，在遇到相应的实际问题时可以进一步地去考虑。