如何构建决策树?
决策树是一种类似流程图的树形结构，其中每个内部节点表示对某个属性的测试，每个部门定义测试的结果，叶节点描述类别或类别分布。树中最大的节点是根节点。
构建决策树的过程可以用递归的方式定义。首先，选择一个属性作为根节点，并为每个可能的值创建一个分支。这会将示例集划分为多个子集，每个子集对应该属性的每个值。该过程可以对每个分支递归重复，只使用到达该部门的实例。如果某个节点上的某些实例具有相似的分类，则停止创建该树的元素。
我们将使用的纯度度量称为信息，以比特为单位进行测量。它与树的每个节点相关联，表示在实例到达该节点的情况下，确定新实例应被分类为"是"还是"否"所需的预期信息量。
剪枝是减小决策树大小的过程。它通过描述树的大小或移除树中能力较小的区域来降低过拟合的风险。剪枝通过修剪训练数据中因噪声或异常值而导致异常的部分来实现，并以一种提高树泛化效率的方法提供初始树。
一些方法经常使用统计方法来移除可靠性最低的部分，这通常会加快分类速度，并增强树对独立测试数据进行准确分类的能力。
决策树学习算法
算法 −根据给定的训练信息创建决策树。
输入 − 训练样本，samples，用离散值属性描述;学生属性集合，attribute-list。
输出 − 一棵决策树。
方法
创建节点 N;
如果样本属于同一类别，则为 C
返回标记为 C 类的叶节点 N
如果属性列表为空，则
返回标记为样本中最常见类别的叶节点 N。 // 多数表决
选择测试属性，即属性列表中信息增益最大的属性。
用测试属性标记节点 N。
对于测试属性的每个已知值 ai // 对样本进行划分。
从节点 N 生成一个分支，条件是测试属性 = ai。
设 si 为样本中测试属性 = ai 的样本集合。
如果 si 为空，则
它可以链接到标有样本中最常见类别的叶子节点。
否则，附加由生成决策树 ( si，属性列表 - 测试属性)
