你在一生中遇到各种不同的人，在有了一些经验后，你知道自己喜欢哪种类型的人。于是在遇见新人类时，很多时候你可以判断自己是否喜欢它们，通过经验知道的，然后不通过大脑感觉。我们通过建立相似的机制。
我们来假设你遇到了一些人，你不希望vmpires成为你的未来的朋友，所以你做出以下的列表，判断他们是否是吸血鬼。
观察这个数据集后，我们画出一个树来判断是否是吸血鬼
因为画出这棵树可以帮助我们做出选择，所以我们称之为“Decision Tree”，这棵树必须满足所给数据集中的所有数据，并且我们也希望它可以满足以后的所有输入。
但如何构造出这棵树呢？以上的树是通过所及观察画出的。
通过观察我们得出以下结论：
所有with pale complexion的人都不是吸血鬼
所有有ruddy complexion和吃garlic的人都不是吸血鬼，如果他们不吃大蒜则是吸血鬼
所有有average complexion的人，并且他们没有影子或不知道是否有影子的是吸血鬼，否则如果有影子则不是吸血鬼
这是我们通过简单数据判断出的决策树，这种随机的猜测在巨大的数据集上是行不通的，我们需要更加系统的步骤来解决这个问题。
那我们来用贪心算法尝试解决一下！
首先通过看数据集，决定选择哪一个属性作为树的根节点.... 这是个二分类问题，所以在决策树的最后我们可以有两种可能的解决方式，所以每个输入的例子可以分类为真或假两类。这里用P表示positive，是吸血鬼，N表示negative，不是吸血鬼。
我们想要那些把数据分为同类的属性，也就是说，P或N各自存在于一个子集，也就可以区分是否是吸血鬼，这就将是叶子节点。
检查每个特征，观察哪一个在相同集合中有最多的元素，此时找到了shadow？这个属性
shadow这个属性，可以决定一个人是否是吸血鬼，但是如果不清楚是否有shadow则不能判断这个人是否是吸血鬼，我们需要另一个特征在shadow=？时将数据集分开。
当shadow=？时，我们分析得知garlic这个属性将其划分为同质子集，区分了最多的元素。
此时的决策树长这样：
这棵树比我们之前随机选特征得出的树更加简单，所以我们发现贪心算法帮助我们获得更好的结果。但这是正确的方式去做吗？
不是，因为数据集很庞大，我们不需要最终将属性区分到同质集中，我们可能会发现所有的属性元素在同质集中是零个。
ID3 Algorithm
现在我们用ID3算法生成决策树，这运用了Information gain这个概念，是通过entropy熵定义的，熵是在信息理论学中的根本quantity
想象这有通过某个特征区分的两个分类
我们观察到，左边的P和N有相同的数量，所以这不能给我们提供任何判断的提示，但是右边的P大于N，所以它可能会指引我们到P，所以这两个中我们会考虑右边的分类。
所以，我们并不直接给它们打零分，我们说，如果一个分类中P和N有相同的数量的有更高的熵值，最混乱，另一个分类中只有P或只有N，它的熵最低，值为0，表示最不混乱。以下我们可以看到这个图，P/（P+N）和熵值的图
所以，当P=N时，也就是P/(P+N)=0.5时，熵值最大为1，如果P=K(某个int值)&N=0，熵值为0
那计算出这个熵值，得出这个图有没有数学方程呢？幸运的是，这个曲线可以通过以下方差获得：
我们可以把x的取值代入这个熵的形式
公式中的P 和 N就是根据该特征划分的Ps和Ns的数量，同时我们也想从属性中获取信息熵Information gain，也定义为IG。
IG(Attribute)=Entropy of attribute - Weighted average of Entropy of each child set
举个例子
知道了信息熵和熵之后，我们来构建决策树
我们计算出最大的IG信息熵是shadow属性，将其作为根节点
此时我们需要决定另一个属性划分Shadow=？的子集
接着算出garlic的 IG值最大，画出的树如下：
