决策树是一种用于解决分类问题的算法。决策树是由一个个“决策”组成的树，其中非叶节点放的是“决策依据”，叶节点放的是“决策结果”。
圆圈：内部节点（非叶节点）方框：叶子节点首先，我们以区分男女学生为例。这里有一些数据，且带有一些属性以及其正确标签。
学号长头发喉结性别1是无女2是有男3否无女4是无女5否有男…………对于以上这个比较简单的数据，很清楚的可以看出我们在区分性别的时候起作用的属性是头发的长短以及有无喉结。这里先画一下这棵决策树，如下图：
上面这些数据，喉结和头发就是我们所说的样本的特征，性别就是标签，即类别。这里我们假设有很多个这种数据，先用这些数据进行训练，然后我们可以得到这样的一棵决策树。那怎么用它来对新的样本进行分类呢？ 当一个新的样本来临时，假设新样本为(无喉结，短头发)，那么根据这棵决策树，我们将会预测这是一个男生。即下图中红色箭头就是预测的过程！
这里是一组关于用户婚姻状况、是否有房、年收入以及是否会拖欠贷款的数据。为了便于后续的计算，这里我以10个数据为例。
ID有房者婚姻状况年收入拖欠贷款1是单身125k否2否已婚100k否3否单身70k否4是已婚120k否5否离异95k是6否已婚60k否7是离异220k否8否单身85k是9否已婚75k否10否单身90k是在构造这棵决策树之前，我门需要知道如何通过属性构造节点。因为有的属性分支为2，有的属性分支有多个，还有的属性是数值型的。这个例子中的有房者就是一个二元属性，分支结果为是和否；婚姻状况是一个多元属性：单身、已婚、离异；年收入是一个序数属性，是数值型的。下面以此例对这三种形式的属性节点构造做个总结和示例：
二元属性
多元属性
序数属性
在构造决策树时，我们要通过选择某个属性来构造节点，比如说最开始我们会选择一个属性作为根节点，根节点分支后又会选择属性作为内部节点，那么选择哪个属性构造出来的决策树更好呢？这肯定不是随便选择的，对于属性的选择有相应的度量指标。
信息熵(entropy)：熵是描述信息的不确定度的，是随机变量不确定度的度量。熵越大，信息的不确定度越大，信息越“混乱”，越不符合决策树分类的需求。Ent(D) = - ∑ k = 1 n \sum_{k=1}^n ∑k=1n p k p_k pk l o g 2 log_2 log2 p k p_k pk
D：样本集合； p k p_k pk：第k类样本所占的比例(k=1,2,3…n)
GINI公式：Gini(D) = 1- ∑ k = 1 n \sum_{k=1}^n ∑k=1n p k 2 p_k^2 pk2
D：样本集合； p k p_k pk：第k类样本所占的比例(k=1,2,3…n)
下面可以任选以上一个公式对属性进行选择。此处我选择GINI计算，简单举例说明一下这个公式。 在数据足够多的情况下，可以绘制出如下曲线（这里将信息熵的曲线也绘制出来，与GINI绘制出的曲线十分相似）： 也就是说，我们计算出的GINI系数越小表示这个属性对分类越好（为0时是最好的状态），就选择这个属性作为分类标准。
前面讲了构造一棵决策树需要了解和注意的一些问题，终于写完了。现在可以开始进入正题构建一棵决策树了！ 这里的数据还是上面准备的那个数据
ID有房者婚姻状况年收入拖欠贷款1是单身125k否2否已婚100k否3否单身70k否4是已婚120k否5否离异95k是6否已婚60k否7是离异220k否8否单身85k是9否已婚75k否10否单身90k是这里对这些数据做一个说明，有房、婚姻、年收入是我们常说的样本的特征（属性），拖欠贷款有两种分类：是、否，是否拖欠贷款就是我们所说的标签（类别）。这里我们需要利用这些数据构造出一棵决策树用来对新的样本进行预测。也就是说，先通过这些数据构造出一棵决策树，对于一个新的样本比如该样本为(有房，单身，90k)，然后就可以根据这些样本特征通过之前构造的决策树来预测这个人是否会拖欠贷款，即我们对这个人分类了，结果会将他归属到拖欠贷款这一类或者不拖欠贷款这一类！
下面开始构建决策树：
选择一个属性作为根节点（注：我这里用GINI系数的方式来选择） 这里需要计算所有属性的加权平均GINI以上，最小的GINI加权是婚姻状况，所以选择婚姻状况作为根节点。
继续根据GINI计算结果选择属性 上一步我们已经确定了婚姻左边分支会得到叶节点了，即婚姻状况为已婚的我们会预测为不会拖欠贷款；接着我们要对右边的这6条数据进行计算，算有房者和年收入的GINI系数，算出来小的那一个作为节点。（此处需要注意的是我们计算是在这6条数据中进行计算），这里还是把计算过程列在下边：更小的GINI加权是有房者，所以这一步我们继续选择的属性是有房者。
再往后就是对年收入分支补充了，下面直接给出最终的决策树的图了！
最终的决策树前边在对数据进行说明的时候，举了一个例子，来了一个新的样本(有房，单身，90k)，然后现在我们用刚刚创建对决策树来预测他会不会拖欠贷款。 红色箭头表示了我们在决策树中对他进行预测的过程，最后可以看到这个人不会拖欠贷款，也就是说我们把他分到了不拖欠贷款的这一类。
以上就是对决策树的理解以及自己手动构造决策树的一个过程，后面会尝试用代码来实现这个过程。
