决策树算法（一）ID3算法

ID3算法是一种贪婪算法，用来构造决策树。

决策树是什么？

决策树和你利用车辆用户手册排查你的车到底出了什么问题没有什么不同。

下图是判断是否外出打高尔夫球的决策树。Outlook代表光照，有三种值。

典型的决策树

该算法最早由J. Ross Quinlan于1975年提出，算法的核心是“信息熵”。ID3算法通过计算每个属性的信息增益，选择信息增益最高的属性为划分标准，重复这个过程，直至生成一个决策树。

信息熵：香农将其定义为离散随机时间出现的概率，一个系统越是有序，信息熵就越低，反之一个系统越是混乱，它的信息熵就越高。所以信息熵可以认为是系统有序化程度的一个度量。

假如一个随机变量X的取值为X={x1,x2,...,xn}，每一种取到的概率分别为{p1,p2,...,pn}，那么X的熵定义为

X的熵

通过下图可以看出，对于任意的p，如果p<0.5，那么认为概率较小，函数对其进行放大，这会增加系统的熵；反之，对于大概率则会对其进行缩小，这会减少系统的熵。整个过程是通过函数-x*log2(x)实现的，最后对所有样本点进行累加，求出系统熵值。

-x*log2(x)

对于分类系统来说，分类总体记为C，它可以分为n类，记作C1，C2,...,Cn，而每一个类别出现的概率分别是P(C1),P(C2),...,P(Cn)，此时分类系统的熵可以表示为

C的熵

下面介绍信息增益。

信息增益IG是相对于属性（特征）而言，系统有它和没有它的信息熵各是多少，前后的差值即信息增益。它在一定程度上反映了了属性的重要程度。定义如下：

信息增益

IG(S|T)表示加入属性T后，系统S的信息增益；value(T)是属性T取值的集合，v是该集合的一个值，Sv是S中属性T为v的样例的集合（即根据T划分簇），|Sv|是Sv中的样例个数。

上式表达的意思就是，通过属性T对集合进行分类，求出新的分类的加权信息熵，比较与原来的差值就是信息增益。

总的来说，搞明白分枝是如何产生的，就理解了ID3算法。该方法选择分枝（属性）的方式是通过计算每个属性的信息增益，选择信息增益最高的属性为新的划分。该算法认为属性的重要性的体现方式是通过对系统熵的影响，如果可以降低很多不确定性，那么它就是一个重要的属性。通过一步步地选择分枝，构建处决策树，构建完成之后，我们就可以对将来的数据进行预测了。

---

参考文献：

XindongWu, VipinKumar. 数据挖掘十大算法[M]. 清华大学出版社, 2013.

决策树之ID3算法 blog.csdn.net/fly_time2012/article/details/70210725