最近微信朋友圈很多人在转发的一个游戏叫做“微软小冰读心术”，游戏的规则很简单：参与游戏的一方在脑海里想好一个人的名字，然后微软小冰会问你15个问题，问题的答案只能用“是”、“不是”或者“不知道”回答。
微软小冰通过你的回答进行推断分解，逐步缩小待猜测人名的范围，决策树的工作原理与这些问题类似，用户输入一系列数据，然后会给出游戏的答案。
###一、决策树简介
决策树（decision tree）是机器学习与数据挖掘中一种十分常用的分类和回归方法，属于有监督学习（supervised learning）算法。通俗来说，决策树分类的思想类似于找对象。现在想象一个女孩的母亲要给这个女孩介绍男朋友，于是有了下面的对话：
女儿：多大年纪了？
母亲：26。
女儿：长的帅不帅？
母亲：挺帅的。
女儿：收入高不？
母亲：不算很高，中等情况。
女儿：是公务员不？
母亲：是，在税务局上班呢。
女儿：那好，我去见见。
这个女孩的决策过程就是典型的决策树方法。相当于通过年龄、长相、收入和是否公务员对将男人分为两个类别：见和不见。假设这个女孩对男人的要求是：30岁以下、长相中等以上并且是高收入者或中等以上收入的公务员，那么这个可以用下图表示女孩的决策逻辑：
决策树是一种树型结构，其中每个内部结点表示在一个属性上的测试，每个分支代表一个测试输出，每个叶结点代表一个类别。
决策树学习是以实例为基础的归纳学习，决策树学习采用的是自顶向下的递归方法，其基本思想是以信息熵为度量构造一棵熵值（熵的概念请参考信息论的书籍）下降最快的树，到叶子结点处的熵值为零，此时，每个叶结点中的实例都属于同一类。
###二、决策树的构造
1.创建分支
创建分支的伪代码函数createBranch()如下所示：
检测数据集中的每一个子项是否属于同一类；
If so return 类标签；
Else
寻找划分数据集的最好特征；
划分数据集；
创建分支结点；
for 每个划分的子集
调用函数createBranch()并增加返回结果到分支结点中
return 分支结点；
上面的伪代码createBranch()是一个递归函数，在倒数第二行直接调用了它本身。
上表的数据包含5个海洋生物，特征包括：不浮出水面是否可以生存，以及是否有脚蹼。
我们可以将这些生物分成两类：鱼类和非鱼类，现在我们想要决定依据第一个特征还是第二个特征来划分数据。
在讨论这个问题前，我们先了解决策树算法中的一些信息论概念：
1.信息量
定义事件X发生的信息量为：
某事件发生的概率越小，则该事件的信息量越大，一定发生和一定不会发生的必然事件的信息量为0。
例如，今天是22号，别人说明天是23号，这就没有一点信息量。
2.信息熵
信息熵是信息量的期望，定义为：
其中p(x)是，事件x发生的概率。信息熵一般用来表征事件或变量的不确定性，变量的不确定性越大，信息熵就越大。一个系统越有序，它的信息熵就越小，反之，一个混乱的系统信息熵越大，所以信息熵是系统有序化程度的一个度量。
3.联合熵和条件熵
两个随机变量X、Y的联合分布形成联合熵H(X,Y)，已知Y发生的前提下，X的熵叫做条件熵H(X|Y)。
4.互信息两个随机变量X、Y的互信息定义为X、Y的信息熵减去X、Y的联合熵。
5.信息增益
信息熵又称为先验熵，是在信息发送前信息量的数学期望，后验熵是指信息发送后，从信宿（即信息的接收者）角度对信息量的数学期望。一般先验熵大于后验熵，先验熵与后验熵的差就是信息增益，反映的是信息消除随机不确定性的程度。
决策树学习中的信息增益等价于训练集中类别与特征的互信息。
信息增益表示得知特征A的信息而使得类X的信息的不确定性减少的程度。
划分数据集的最大原则是：将无序的数据变得更加有序。划分数据集前后信息发送的变化就行信息增益，通过计算每个特征值划分数据集获得的信息增益，我们就可以根据获得信息增益最高的特征来选择其作为划分数据的特征。
信息增益的计算方法：
（1）计算给定数据集的信息熵
~~~
from math import log
def calcShannonEnt(dataSet):
numEntries = len(dataSet)
labelCounts = {}
for featVec in dataSet: #the the number of unique elements and their occurance
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) #log base 2
return shannonEnt
~~~
代码解析：首先，计算数据集中实例的总数numEntries，然后创建一个字典，它的键值是最后一列的数值，如果当前键值不存在，则扩展字典并将当前键值加入字典，每个键值都记录了当前类别出现的次数labelCounts，最后，使用所有类别标签的发生频率计算类别出现的概率。
（2）创建数据集
利用createDataSet（）函数得到表3-1所示的简单鱼鉴定数据集：
~~~
def createDataSet():
dataSet = [[1, 1, 'yes'],
[1, 1, 'yes'],
[1, 0, 'no'],
[0, 1, 'no'],
[0, 1, 'no']]
labels = ['no surfacing','flippers']
#change to discrete values
return dataSet, labels
~~~
（3）划分数据集
对每个特征划分数据集的结果计算一次信息熵，然后判断按照哪个特征划分数据集是最后的划分方式。
~~~
def splitDataSet(dataSet, axis, value):
retDataSet = []
for featVec in dataSet:
if featVec[axis] == value:
reducedFeatVec = featVec[:axis] #chop out axis used for splitting
reducedFeatVec.extend(featVec[axis+1:])
retDataSet.append(reducedFeatVec)
return retDataSet
~~~
代码解析：spiltDataSet()的三个输入参数分别是待划分数据集dataSet、划分数据集的特征axis、需要返回的特征的值。遍历数据集中的每个元素，一旦发现符合要求的值，则将其添加到新创建的列表中。
选择最好的数据集划分方式：
~~~
def chooseBestFeatureToSplit(dataSet):
numFeatures = len(dataSet[0]) - 1 #the last column is used for the labels
baseEntropy = calcShannonEnt(dataSet)
bestInfoGain = 0.0; bestFeature = -1
for i in range(numFeatures): #iterate over all the features
featList = [example[i] for example in dataSet]#create a list of all the examples of this feature
uniqueVals = set(featList) #get a set of unique values
newEntropy = 0.0
for value in uniqueVals:
subDataSet = splitDataSet(dataSet, i, value)
prob = len(subDataSet)/float(len(dataSet))
newEntropy += prob * calcShannonEnt(subDataSet)
infoGain = baseEntropy - newEntropy #calculate the info gain; ie reduction in entropy
if (infoGain > bestInfoGain): #compare this to the best gain so far
bestInfoGain = infoGain #if better than current best, set to best
bestFeature = i
return bestFeature #returns an integer
~~~
代码运行结果告诉我们，第0个特征是最好的用于划分数据集的特征。数据集的数据来源于表3-1，
如果我们按照第一个特征属性划分数据，也就是说第一个特征为1的放在一组，第一个特征是0的放在另一个组，按照这种方式划分的话，第一个特征为1的海洋生物分组将有两个属于鱼类，一个属于非鱼类；另一个分组则全部属于非鱼类。
如果我们按照第二个特征分组，第一个海洋生物分组将有两个属于鱼类，两个属于非鱼类；另一个分组则只有一个非鱼类。
可以看出，第一种划分很好地处理了相关数据。
（4）递归构建决策树
~~~
def majorityCnt(classList):
classCount={}
for vote in classList:
if vote not in classCount.keys(): classCount[vote] = 0
classCount[vote] += 1
sortedClassCount = sorted(classCount.iteritems(), key=operator.itemgetter(1), reverse=True)
return sortedClassCount[0][0]
~~~
创建决策树的函数代码：
~~~
def createTree(dataSet,labels):
classList = [example[-1] for example in dataSet]
if classList.count(classList[0]) == len(classList):
return classList[0]#stop splitting when all of the classes are equal
if len(dataSet[0]) == 1: #stop splitting when there are no more features in dataSet
return majorityCnt(classList)
bestFeat = chooseBestFeatureToSplit(dataSet)
bestFeatLabel = labels[bestFeat]
myTree = {bestFeatLabel:{}}
del(labels[bestFeat])
featValues = [example[bestFeat] for example in dataSet]
uniqueVals = set(featValues)
for value in uniqueVals:
subLabels = labels[:] #copy all of labels, so trees don't mess up existing labels
myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value),subLabels)
return myTree
~~~
###三、决策树的过拟合
决策树对训练属于有很好的分类能力，但对未知的预测数据未必有好的分类能力，泛化能力较弱，即可能发生过拟合现象。
解决过拟合的方法：
1.剪枝
2.随机森林
