开发者学堂课程【高校精品课-北京理工大学-数据仓库与数据挖掘（上）：Hunt' s Algorithm】学习笔记，与课程紧密联系，让用户快速学习知识。
课程地址：https://developer.aliyun.com/learning/course/921/detail/15642
Hunt' s Algorithm
hunt 算法
在决策树模型构建中，我们需要使用到有标记的数据对决策树模型进行训练，得到训练好的决策树模型，但是我们根据训练集是可以得到很多棵决策树模型的。决策树模型的数量非常巨大，我们不可能列出所有的决策树模型并选择最优的决策数。
一般我们采用的策略是采用贪心策略，在构建决策树模型的时候，使用局部最优策略去选择一个比较合适的属性测试条件，从而完成我们决策树的构建，Hunt 算法就是这一类策略的集中代表。后续决策树算法的 C4.5算法、ID3 算法和 cart 算法都是基于 hunt 算法改造而来的。
所以我们首先向大家介绍 Hunt 算法，用的算法构建决策树的过程是一个自顶向下递归、分而自知的过程。我们用 DT 代表录入到一个节点T上的数据。那如果 DT 中所有数据对象的类都是一致的，当前的T就是一个叶子节点。我们可以构建一个叶子节点器，然后把它标上所有数据对象的类标签。那如果 DT 所包含的数据对象有多个类别，我们的节点T就是一个中间节点，这时我们需要确定一个合理的属性测试条件。根据属性测试条件，我们把落入到节点器上的数据集合 DT 划分成为若干个更小的子集。我们迭代循环以上步骤，一直到满足我们的终结条件。
终结条件主要有三种情况，第一种情况就是落入到这个节点上的所有数据对象，它的类标签是一致的。第二种条件就是没有属性供我们选择去构造我们的属性测试条件。第三种情况就是我们训练集中的所有数据对象都已经被使用完。
我们通过一个例子向大家来介绍 hunt 算法构建决策树模型的过程。首先从根节点开始，我们所有的数据对象落入到根节点上，在根节点上我们确定一个合适的属性测试条件。比如这里我们选择了 home owner 作为我们的测试条件，将我们的数据集一分为二，其中在我们的划分中，我们的这样的一个分支，也就是我们的 home owner 取值为 yes 的时候，那么他的所有数据对象的集合都是一致的，那这时候我就可以为它构建一个叶子节点。
对于 home owner 取值为 no 的这一部分集合，它所包含数据对象的取值有多种情况，因此这个节点就是一个中间节点，在这个节点上，我们选择合适的属性测试条件，这个时候我们选择的是婚姻状态，根据婚姻状态，我们又将我们的数据对象集合划分成两个小的集合，那么其中一部分是他的婚姻状态为 single 和 divorce 的，那么另一部分是maried，在这两个集合中，我们会发现对于我们的婚姻状态是 maried 的情况下，那么它所包含的数据对象的类标签是一致的，我们就构造一个叶子节点被标上它的类标签，对于我们的婚姻状态是 divorce 和 single 的时候，我们发现这个集合中数据对象的类标签有多种情况，那我们就选择合适的属性测试条件将这样一个集合继续划分，一直到我们最后所有的集合中的数据对象的类标签都是一致的，那我们就完成了决策树的构建。
对于我们决策树构建过程中，其中一个重要的环节就是用来测试属性条件。对于不同属性，测试条件的表达形式是不一样的。
如果我们的属性是标称属性。由于标称属性，它的取值是离散的。那我们就可以根据标称属性的取值。将我们的集合划分为若干个小的子集。实现多路划分。当然我们也可以实现两路划分，我们以这样的一个 Mary state 这样的一个属性为例。它的取值有三种情况。
我们可以根据它的取值实现自然的三路划分，那如果想实现两路划分的时候，我们可以把它的取值进行划分，比如说我们可以把它的取值划分成为 Mary 的，Single divorce 的，Single divorce married，还有 single married 和 divorce 的。那么这种就是对标称属性的属性测试条件的表达。
我们再来看一下连续属性。对于连续属性，如果我们想实现多路划分，那我们就可以设置多个取值范围取值。取值范围的表达形式就是这样的。那么通过设置多个取值范围，我们可以得到多个子集。
对于联系属性，我们同样也可以实现二路划分，对于要实现二路划分，我们可以选择一个最佳的分裂值V，然后将这个属性分成 a 小于 V 和 a 大于等于V2个部分。
在我们刚才介绍的 hunt 算法中，我们对于落入到一个节点上的数据集合，他的属性测试条件是有多种选择的。那我们怎么样才能得到一个合理的属性测试条件，从而实现最佳的划分？
我们这里举一个例子，比如说我们这里有一个数据集，它是由20个数据对象主。那我们怎么样去选择合理的属性测试条件，对这个数据集进行划分？
在一般的决策树算法中，我们是通过贪心策略用来评估这个属性测试条件分裂之后各个节点的纯度。如果节点的纯度越高，那么我们认为这样的一个属性测试条件是比较理想的，得到的划分是比较好的。那什么是节点的纯度？
节点的纯度就指的是这个节点中数据对象它的类的倾斜性。如果一个节点中所有的数据对象都是一个类别，那么它的纯度就最高。我们下面向大家通过举例介绍这样的一个数据节点的纯度，比如说我们这里有两个节点。
这两个节点中，它的数据对象的个数都是十个。其中第一个节点，它的 C0 类别的数据对象有五个，C1 类别的数据对象有五个，那么对于这样的一种节点，它的纯度是非常低的，因为 C0 和 C1 出现的概率是一样的。但是对于第二个节点，我们可以看一下，同样是十个数据对象，其中有九个数据对象是属于 C0 类别，只有一个数据对象属于 C1 类别，也就是在这个节点中，大部分的数据对象都是属于 C0 类别的，那么我们认为这个节点它的纯度就比较高。
那么在决策树模型中，我们主要是通过设定评估节点纯度的方法来判断我们的属性测试题是否合理。
