人工智能之机器学习——决策树

    决策树算法是解决分类问题的一种方法。与基于概率推断的朴素贝叶斯分类器和逻辑回归模型不同，决策树算法采用树形结构，使用层层推理来实现最终的分类。与贝叶斯分类器相比，决策树的优势在于构造过程无需使用任何先验条件，因而适用于探索式的知识发现。

人工智能之机器学习——决策树

      决策树的分类方法更接近人类的判断机制，这可以通过买房的实例说明。

      面对眼花缭乱的房源，普通人优先考虑的都是每平方米的价格因素，价格不贵就买，价格贵了就不买。在价格合适的前提下，面积就是下一个待确定的问题，面积不小就买，面积小了就不买。如果面积合适，位置也是不容忽视的因素，单身业主会考虑房源离工作地点的远近，离单位近就买，离单位远就不买；为人父母的则要斟酌是不是学区房，是学区房就买，不是学区房就不买。如果位置同样称心，就可以再根据交通是否便捷、物业是否良好、价格是否有优惠等条件进一步筛选，确定最后的购买对象。

      前面的例子模拟了一套购房策略。在这套策略中，业主对每个可选房源都要做出“买”与“不买”的决策结果，而“每平米价格”、“房屋面积”、“学区房”等因素共同构成了决策的判断条件，在每个判断条件下的选择表示的是不同情况下的决策路径，而每个“买”或是“不买”的决定背后都包含一系列完整的决策过程。决策树就是将以上过程形式化、并引入量化指标后形成的分类算法。

      决策树是一个包含根节点、内部节点和叶节点的树结构，其根节点包含样本全集，内部节点对应特征属性测试，叶节点则代表决策结果。从根节点到每个叶节点的每条路径都对应着一个从数据到决策的判定流程。使用决策树进行决策的过程就是从根节点开始，测试待分类项的特征属性，并按照其值选择输出的内部节点。当选择过程持续到到达某个叶节点时，就将该叶节点存放的类别作为决策结果。

      由于决策树是基于特征对实例进行分类的，因而其学习的本质是从训练数据集中归纳出一组用于分类的“如果...... 那么......”规则。在学习的过程中，这组规则集合既要在训练数据上有较高的符合度，也要具备良好的泛化能力。决策树模型的学习过程包括三个步骤：特征选择、决策树生成和决策树剪枝。

      特征选择决定了使用哪些特征来划分特征空间。在训练数据集中，每个样本的属性可能有很多个，在分类结果中起到的作用也有大有小。因而特征选择的作用在于筛选出与分类结果相关性较高，也就是分类能力较强的特征。理想的特征选择是在每次划分之后，分支节点所包含的样本都尽可能属于同一个类别。

      在最早提出的决策树算法——ID3 算法中，决策树的生成就利用信息增益准则选择特征。ID3 算法构建决策树的具体方法是从根节点出发，对节点计算所有特征的信息增益，选择信息增益最大的特征作为节点特征，根据该特征的不同取值建立子节点；对每个子节点都递归调用以上算法生成新的子节点，直到信息增益都很小或没有特征可以选择为止。

人工智能之机器学习——决策树

      同其他机器学习算法一样，决策树也难以克服过拟合的问题，“剪枝”是决策树对抗过拟合的主要手段。

      园丁给树苗剪枝是为了让树形完好，决策树剪枝则是通过主动去掉分支以降低过拟合的风险，提升模型的泛化性能。