机器学习 之 尽可能通俗易懂的决策树算法

首先先贴一下百科上关于决策树的基本概念：

决策树(Decision Tree）是在已知各种情况发生概率的基础上，通过构成决策树来求取净现值的期望值大于等于零的概率，评价项目风险，判断其可行性的决策分析方法，是直观运用概率分析的一种图解法。由于这种决策分支画成图形很像一棵树的枝干，故称决策树。在机器学习中，决策树是一个预测模型，他代表的是对象属性与对象值之间的一种映射关系。Entropy = 系统的凌乱程度，使用算法ID3, C4.5和C5.0生成树算法使用熵。这一度量是基于信息学理论中熵的概念。

决策树是一种树形结构，其中每个内部节点表示一个属性上的测试，每个分支代表一个测试输出，每个叶节点代表一种类别。

这么说虽然比较严谨，但是很难理解全貌。现在我们考虑这么一件事：如何对人的职业进行分类。我们有四个要分类的目标：医生，护士，老师，警察。

我们先假设一些数据： 

人员	是否经常穿白大褂	是否有枪	是否给别人上课	性别	学历	收入范围	职业
A	是	否	否	男	博士	10000-11000	医生
B	是	否	是	男	硕士	8000-9000	医生
C	是	否	否	女	本科	6000-7000	护士
D	否	是	否	男	本科	6000-7000	警察
E	是	否	否	女	大专	5000-6000	护士
F	否	否	是	女	硕士	5000-6000	老师
G	否	否	否	男	本科	6000-7000	警察
H	否	是	是	女	大专	6000-7000	警察
I	否	否	是	男	硕士	5000-6000	老师

假设我们分析的第一个特征是，是否带枪，如果是，说明是警察（合法范围内）。如果不是，不一定不是警察，可能是新入职的警察，所以现在先画第一个树杈：

然后我们再分析第二个特征：是否穿白大褂。这样可以把医生和护士区分到一组，把警察和老师分到另一组。

然后针对穿白大褂的人进行学历检测，大于硕士的表示为医生，本科及以下的表示为护士。

通过对所有特征进行分类，我们就可以得到一个树形结构。

现在出现了第二个问题：怎么去寻找每个分类的节点呢（先用那个节点分类，再用哪个节点进行分类呢？）

比如我们上面的图，是首先用是否有枪进行分类的，那我们也可以用是否有白大褂作为第一个分类特征。但是，这两种方式哪个更好呢？

这就提出了关于信息论的分类算法：

首先是ID3算法：

ID3: 由增熵（Entropy）原理来决定使用哪个特征进行分类，即对哪个节点需要判断然后分裂。对于一组数据，熵越小说明分类结果越好。熵定义为：Entropy＝- sum [ P(k) * log2(P(k) ]  其中P(k) 为k出现的概率。

上面在分类的时候，不知道大家有没有注意到一个很严肃的问题，即经过不断细分以后，警察这个选项可能会出现在不同的树杈上，有的树杈是通过有枪来分出去的，有的树杈是通过不穿白大褂等多种特征分出去的，他们一共占据了两个树杈末梢。这就说明了，你确实可以通过决策树把数据分类出去，但是假如我们换一种分类方法：按照是否上课来作为首次区分，警察又会分类到不同的树杈上：这次一共占据了三个树杈末端。

你可能会说，谁这么傻会先分警察呢？但是要知道，如果样本中老师数量比较多，那么先区分是否上课会有很好的作用。毕竟其他行业需要讲课的人的比例会很小（虽然警察也会上课教新人，但是比例小）。

那么这个熵的意义就是找到最好的分类方式，能够综合权衡整体的各个部位的分类，分得最整洁。（模糊地理解一下什么叫整洁。）

我们假设一个二分类问题，当A和B各占一半的时候，

Entropy = -（0.5*log2( 0.5)+0.5*log2( 0.5))= 1

当只有A或只有B类的时候，

Entropy= -（1*log2( 1）+0）=0

所以当Entropy最大为1的时候，熵最大，是分类效果最差的状态，当它最小为0的时候，是完全分到一类的状态。

我们下一节将通过更好的例子来写程序检验分类情况。（P.S. 这里用的例子过于简陋，临时随便想起来的，）