????最近重温了本科学过的一个算法，决策树。想写篇博文整理一下，一则与大家分享，希望能帮到有需要的人。二来作为一个学习笔记，记录一下学习内容。为了让大家对这个算法有一个系统清晰的认识，这篇博文侧重于对算法整体流程以及算法核心部分进行阐述。决策树算法整体流程大致都一样，不同的是在进行特征选择时，特征选择策略不同，这篇博文以ID3算法进行特征选择来学习决策树。如果你已掌握决策树算法整个工作流程，想要详细学习其他特征选择策略以及有关决策树剪枝的内容，推荐学习资料 《统计学习方法》(李航著）
话不多说，进入正题！
算法介绍
直观理解
????决策树，是有监督学习算法，主要用于分类及回归任务。决策树算法本质是从训练数据集中学习归纳出一组规则，要求该规则能对训练集进行正确分类。举个例子：表中数据，有眼睛颜色、头发颜色两个特征，黄种人、白种人、混血三个分类。
????相较于表格数据，决策树是不是一目了然，（如果你不这样认为，换一种说法，相较于表格，决策树是不是显得数据分类更清晰一些表格中你可以一眼看出分类的规律吗，很不方便），决策树的作用可不是单单让人看着方便。从数据集中训练得到的最终决策树，当你输入测试实例, （眼镜颜色、头发颜色），从根节点开始进行决策，最终会到达一个叶子节点，得到输入数据对应的分类结果。也就是说，决策树可以进行预测。
????决策树最上面的节点称为根节点，是整个决策树的开始，眼睛颜色是什么呢题答案决定数据下一步走向的分支，这是一个决策过程。每一个分支是一个新的决策节点或者是树的叶子节点。每个决策节点代表一个问题，也就是待分类对象的特征。比如”头发颜色“这一节点，头发颜色是什么颜色呢是一个新的决策。每个叶子节点代表一种分类结果。
????沿着决策树从上到下遍历的过程中，每个节点都会进行测试。决策节点上，回答结果（不同的测试输出），导致不同的分支，最后会到达叶子结点。这个过程就是决策树进行决策的过程，利用若干个特征来判断实例的类别。
主要步骤
一、特征选择
二、决策树生成
三、决策树剪枝 （涉及到决策树优化问题，本期内容不做详细介绍）
特征选择，如上方的例子，我们在选取特征时，先使用哪一个呢先要明确，我们的目标是要通过归纳出的规则，使数据在较少的步骤内找到对应的分类。特征选择的准则不同，对应的特征选择的顺序可能会发生变化。
以海洋生物数据为例：
程序输出：
划分数据集函数
程序输出
以索引为1的特征(是否有脚蹼)进行划分，返回对应特征值为1的数据样本。注意：返回的数据中只剩下一个特征（索引为0的特征，即”不浮出水面是否可以生存”），因为以索引为1的特征进行划分，接下来的划分中不能再使用这个特征，所以数据会减少一个特征。
特征选取（选择最好的数据集划分方式）
程序输出
到这里，我们先前的疑问就得到了解答，“不浮出水面是否可以生存”，“是否有脚蹼”，我们先选择哪个特征进行划分呢选择特征”不浮出水面是否可以生存“时，对应的信息增益要大于选择特征”是否有脚蹼”“。这样的解释似乎还不够直观，我们作图理解
按照第一个特征进行划分，特征值为0的分组中有两个鱼类，一个非鱼类。特征值为1的分组里全是非鱼类。按照第二个特征进行划分，第一个分组中有两个属于鱼类，两个属于非鱼类，另一个分组则只有一个非鱼类。第一种方式很好的处理了数据。就如同计算结果一样，选择第一个特征（索引为0）“不浮出水面是否可以生存”，划分前后熵值变化大，数据趋于有序的程度更大，故而选择第一个特征来进行划分。
构建决策树
声明：本站部分文章及图片源自用户投稿，如本站任何资料有侵权请您尽早请联系jinwei@zod.com.cn进行处理,非常感谢！