很多人都玩过一个游戏，通过限定次数的提问猜出对方在纸上写出的一个词，当然对方必须对我们的每一个猜测做出回应，通过一连串正确或者错误的判断，如果最终我们猜出了对方的那个词，那么我们就取得了胜利，决策树的工作原理就和这个游戏类似，看下面一个例子：
上面这张图就是一个典型的决策树，我们每天出门前要想一下今天是开车还是走路呢？首先看看窗外，下雨了吗？如果有再看看到底是雪还是雨？哇靠！是雪，开车吧！这样一个决策的过程就是在根节点处做出的，其他的节点可以类似的推导，每一个椭圆的节点都对应着我们需要考虑的属性（天气，气温，时间，地点.....）而每个叶子节点就是我们做出的决策了，到这里就是一棵树生长的终点。
现在如果要建立一棵决策树，需要什么数据呢？需要建立的是一堆属性到最后决策的映射关系，那么训练数据集包含了一堆属性值，以及样例正确分类的值，如下所示，对于星期六，我们有一下属性，每个属性的取值包含在了花括号内。
outlook, with values {sunny, overcast, rain}
temperature, with values {cool, mild, hot}
humidity, with values {high, normal}
windy, with values {true, false }
将各个属性去一定的值并集合在一起，就形成了一个特殊的星期天：
outlook: overcast
temperature: cool
humidity: normal
windy: false
分类的类别只有两类：N（反例），P（正例），任务是建立一个分类的方式，将属性值正确的映射至分类方式。
试想如果训练样例中只有两例，而且他们的属性值相同，但是对应着不同的分类，那么这样肯定不能从这样的数据集中正确的分类。所以我们需要足够的原料来开锅（喂给算法学习）.如果训练的样例充足，我们总是可能利用训练数据来建立一棵决策树的，所以是否能不仅仅让它符合训练数据，还能在未知的数据集上表现出色？那么需要我们的决策树很好的抓住了属性与分类值之间的联系，越是简单的树约可能在未知的数据集上表现良好，因为他的复杂度较低，可能遭遇的variance也会较低，在未知的数据中的表现更接近于在训练数据中的表现。
从原则上讲，给定我们一个训练数据集，通过各种属性的组合可以构造指数级的决策树，找出最佳的决策树在计算上是不可行的，所以决策树是人们在复杂度和效率之间权衡的产物，现在市面上的决策树都采用了贪心算法策略，在选择划分的数据属性时，采用一系列局部最优决策来构造决策树。他们的基础就是Hunt算法，算法的描述如下：
Hunt算法：
在Hunt算法中，通过递归的方式建立决策树。
1：如果数据集D中所有的数据都属于一个类，那么将该节点标记为为节点。
2：如果数据集D中包含属于多个类的训练数据，那么选择一个属性将训练数据划分为较小的子集，对于测试条件的每个输出，创建一个子女节点，并根据测试结果将D中的记录分布到子女节点中，然后对每一个子女节点重复1，2过程，对子女的子女依然是递归的调用该算法，直至最后停止。
ID3算法（Iterative Dichotomiser 3 迭代二叉树3代）是一个由Ross Quinlan发明的用于决策树的算法。这个算法便是建立在上述所介绍的奥卡姆剃刀的基础上：越是小型的决策树越优于大的决策树（be simple简单理论）。尽管如此，该算法也不是总是生成最小的树形结构，而是一个启发式算法。
从信息论知识中我们知道，期望信息越小，信息增益越大，从而纯度越高。ID3算法的核心思想就是以信息增益度量属性选择，选择分裂后信息增益最大的属性进行分裂。该算法采用自顶向下的贪婪搜索遍历可能的决策树空间。
所以，ID3的思想便是：
这形成了对合格决策树的贪婪搜索，也就是算法从不回溯重新考虑以前的选择。
下图所示即是用于学习布尔函数的ID3算法概要：
ID3算法的核心思想就是以信息增益度量属性选择，选择分裂后信息增益最大的属性进行分裂。接下来，咱们就来看看这个信息增益是个什么概念。
上述的ID3算法的核心问题是选取在树的每个结点要测试的属性。我们希望选择的是最有利于分类实例的属性，信息增益(Information Gain)是用来衡量给定的属性区分训练样例的能力，而ID3算法在增长树的每一步使用信息增益从候选属性中选择属性。
为了精确地定义信息增益，我们先定义信息论中广泛使用的一个度量标准，称为熵（entropy），它刻画了任意样例集的纯度（purity）。给定包含关于某个目标概念的k种样例的样例集S，那么S相对这个k种分类的熵为：
其中P表示的是每s中每个类出现的频率，表示如下：
如果写python代码实现熵的计算，则如下所示：
def calcShannonEnt(dataSet):
numEntries = len(dataSet)
labelCounts = {}
for featVec in dataSet:
currentLabel = featVec[-1]
if currentLabel not in labelCounts.keys():
labelCounts[currentLabel] = 0
labelCounts[currentLabel] += 1
shannonEnt = 0.0
for key in labelCounts:
prob = float(labelCounts[key])/numEntries
shannonEnt -= prob*log(prob,2)
return shannonEnt
为了对熵有直观的了解，需要明白它到底是干嘛的，信息论中对熵的一种解释，熵确定了要编码集合S中任意成员的分类所需要的最少二进制位数。看他的公式进一步理解，P是种类出现的概率，log(P)表示了携带的信息，试想一下如果一件事发生的概率为1，它给我们带来的信息是0，越是不确定的事情携带的信息越高，那么其与概率的加权和就代表了这个大类中不同小类所携带信息的期望，举例来说，假设S是一个关于布尔概念的有14个样例的集合，它包括9个正例和5个反例（我们采用记号[9+，5-]来概括这样的数据样例），那么S相对于这个布尔样例的熵为：
Entropy（[9+，5-]）=-（9/14）log2（9/14）-（5/14）log2（5/14）=0.940。
根据上述这个公式，我们可以得到：S的所有成员属于同一类，Entropy(S)=0； S的正反样例数量相等，Entropy(S)=1；S的正反样例数量不等，熵介于0，1之间，如下图所示橙色线所示：
信息增益Gain(S,A)定义
已经有了熵作为衡量训练样例集合纯度的标准，现在可以定义属性分类训练数据的效力的度量标准。这个标准被称为“信息增益（information gain）”。简单的说，一个属性的信息增益就是由于使用这个属性分割样例而导致的期望熵降低(或者说，样本按照某属性划分时造成熵减少的期望)。更精确地讲，一个属性A相对样例集合S的信息增益Gain(S,A)被定义为：
其中 Values(A)是属性A所有可能值的集合，是S中属性A的值为v的子集。换句话来讲，Gain(S,A)是按照属性A来分类后各类熵的加权平均值，权值就是各个分类占总体样本的比例。当对S的一个任意成员的目标值编码时，Gain(S,A)的值是在知道属性A的值后可以节省的二进制位数。
下面，举个例子，假定S是一套有关天气的训练样例，描述它的属性包括可能是具有Weak和Strong两个值的Wind。假定S包含14个样例，[9+，5-]。在这14个样例中，假定正例中的6个和反例中的2个有Wind =Weak，其他的有Wind=Strong。由于按照属性Wind分类14个样例得到的信息增益可以计算如下。
决策树需要有停止的条件来终止其生长的过程，一般来说最低的条件是：当该节点下面的所有记录都属于同一类，或者当所有的记录属性都具有相同的值时。这两种条件是停止决策树的必要条件，也是最低的条件，在实际运用中我们希望决策树提前停止生长，限定叶节点包含的最低数据量，防止由于过度生长造成的过拟合是十分重要的。
·简单易用，而且输出的结果易于解释，树能够被图形化，加深了直观的理解。
·几乎不需要对数据进行预处理。
·算法的开销不大，而且决策树一旦建立，对于未知样本的分类十分快，最坏情况下的时间复杂度是O(w),w是树的最大深度。
·能够用于多类的分类。
·能够容忍噪点。
·容易过拟合。
·容易被类别中占多数的类影响而产生bias，所以推荐在送入算法之间先平衡下数据中各个类别所占的比例。
·决策树采用的是自顶向下的递归划分法，因此自定而下到了末端枝叶包含的数据量会很少，我们会依据很少的数据量取做决策，这样的决策是不具有统计意义的，这就是数据碎片的问题。
处理决策树中的过拟合问题：
过拟合主要是决策树生长的节点过多导致的，所以对于过拟合问题，治本的方法还在于剪枝。剪枝可以分为先剪枝和后剪枝。下面对不同的情况做出讨论：
1：先剪枝：
这种方法中,我们在算法还未进行时，给它一个限制，让其最大深度在增长过程达到一定程度时停止增长。为了达到这一点我们需要采取更加苛刻的停止条件，如：当观察到最大信息增益低于某个值时停止增长，或者限制决策树的最大深度和最低叶节点分裂样本数，但是这样的方法操作起来较为困难，如何选取最佳的参数？阈值设置太高容易导致模型的过拟合，设置太低又容易导致欠拟合，那么就需要我们将这些参数也加入整个树的重复建立测试中，根据测试的结果采用表现最好的树。
2：后剪枝：
该方法中，决策树按照最大规模疯狂的生长，我们将得到一颗最大深度的决策树，然后进行剪枝的步骤，修建的顺序是从下往上，修建的方式有：1.用叶节点来替换子树，叶节点的类别有子树下面的多类决定。（子树替换）2.用子树种最常用的分支来替代子树（子树替换）
在强大的机器学习库sklearn中已经集成了决策树模型，所以我们可以利用该模块方便的实施决策树学习。下面介绍一些常用的方法：
class sklearn.tree.DecisionTreeClassifier(criterion=‘gini‘, splitter=‘best‘, max_depth=None, min_samples_split=2,min_samples_leaf=1, max_features=None, random_state=None, min_density=None, compute_importances=None,max_leaf_nodes=None)
在创建一个决策树分类器时，我们有很多参数可以初始化，其中主要需要考虑的是：
criterion ：规定了该决策树所采用的的最佳分割属性的判决方法，有两种：“gini”，“entropy”。
max_depth ：限定了决策树的最大深度，对于防止过拟合非常有用。
min_samples_leaf ：限定了叶子节点包含的最小样本数，这个属性对于防止上文讲到的数据碎片问题很有作用。
模块中一些重要的属性方法：
n_classes_ ：决策树中的类数量。
classes_ ：返回决策树中的所有种类标签。
feature_importances_ ：feature的重要性，值越大那么越重要。
fit(X, y, sample_mask=None, X_argsorted=None, check_input=True, sample_weight=None)
将数据集x，和标签集y送入分类器进行训练，这里要注意一个参数是：sample_weright，它和样本的数量一样长，所携带的是每个样本的权重。
get_params(deep=True)
得到决策树的各个参数。
set_params(**params)
调整决策树的各个参数。
predict(X)
送入样本X，得到决策树的预测。可以同时送入多个样本。
transform(X, threshold=None)
返回X的较重要的一些feature，相当于裁剪数据。
score(X, y, sample_weight=None)
返回在数据集X,y上的测试分数，正确率。
下面是一个应用的例子：
from sklearn import tree X = [[0, 0], [1, 1]] Y = [0, 1] clf = tree.DecisionTreeClassifier() clf = clf.fit(X, Y) clf.predict([[2., 2.]])
利用python中的pydot模块可以方便的输出决策树的效果图，不过需要注意的是pyparsing必须是旧版本的，比如1.5，另外需要在电脑商安装Graphviz软件。下面是一个例子：
from sklearn.externals.six import StringIO
import pydot
dot_data = StringIO.StringIO()
tree.export_graphviz(clf, out_file=dot_data)
graph = pydot.graph_from_dot_data(dot_data.getvalue())
graph.write_pdf("iris.pdf")
·当我们数据中的feature较多时，一定要有足够的数据量来支撑我们的算法，不然的话很容易overfitting
·PCA是一种避免高维数据overfitting的办法。
·从一棵较小的树开始探索，用export方法打印出来看看。
·善用max_depth参数，缓慢的增加并测试模型，找出最好的那个depth。
·善用min_samples_split和min_samples_leaf参数来控制叶子节点的样本数量，防止overfitting。
·平衡训练数据中的各个种类的数据，防止一个种类的数据dominate。
Pang-Ning Tan 《数据挖掘导论》
Tom M Mitchell 《机器学习》
Peter Harrington 《机器学习实战》
从决策树学习谈到贝叶斯分类算法、EM、HMM http://blog.csdn.net/v_july_v/article/details/7577684
Trevor Hastie/Robert Tibshirani/Jerome Friedman 《The Elements of Statistical Learning》
Sklearn:decision tree http://scikit-learn.org/stable/modules/tree.html
JR Quinlan 《Introduction decision tree》1986
JR Quinlan 《C4.5 programs for machine learning》1993
原文：http://blog.csdn.net/frog_in_a_well/article/details/30725341