简单详细易懂！决策树及其构造
- 什么是决策树
- 信息熵
- 决策树的构造
什么是决策树
你是否玩过二十个问题的游戏，游戏的规则很简单：参与游戏的一方在脑海里想某个事物，
其他参与者向他提问题，只允许提20个问题，问题的答案也只能用对或错回答。问问题的人通过
推断分解，逐步缩小待猜测事物的范围。决策树的工作原理与20个问题类似，用户输入一系列数
据，然后给出游戏的答案。
信息熵
接下来介绍信息熵的概念，决策树的构造很大程度上需要信息熵这个工具
在上表中可以看到，有“不浮出水面”，“是否有脚蹼”两个特征，在构造决策树时，我们按照不同的特征进行划分，从而产生树的分支。而在每次划分之后，都有其对应的信息熵，而如果将分支后的信息熵与之前的信息熵进行对比，我们就得出了信息增益的概念。
按照“不浮出水面是否可以生存”这个特征进行划分，利用上面介绍的计算信息熵的公式进行计算，最后再分别乘以划分后各个标签占总标签数量的一个占比（这里的标签就是指“属于鱼类”中的“是”或“否”）。这里读者可以认为是一个全概率公式。这样就得出了一个新的信息熵，与之前的信息熵做差，就得出了信息增益，显然信息增益越大越好。
当然，
，这样就会使得树的分支变得非常非常多，这是我们不希望看到的，于是我们就引进了信息增益率和基尼指数的概念。将他们与信息增益结合起来，可以更合理地构造决策树。
决策树的构造
在知道了决策树的原理之后，我们就通过代码来实现决策树的构造，下面有详细代码的讲解。并且使用文章前面提供一个简单的示例（是否属于鱼类的这个例子，读者可以往前翻看）来带入计算，以更好地理解决策树算法。
决策树的一般流程
(1) 收集数据：可以使用任何方法。
(2) 准备数据：树构造算法只适用于标称型数据，因此数值型数据必须离散化。
(3) 分析数据：可以使用任何方法，构造树完成之后，我们应该检查图形是否符合预期。
(4) 训练算法：构造树的数据结构。
(5) 测试算法：使用经验树计算错误率。
(6) 使用算法：此步骤可以适用于任何监督学习算法，而使用决策树可以更好地理解数据
的内在含义。
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
创建数据集，将表格中的数据做成列表的形式初始化。如果数据量大，可以直接导入数据文件。
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 # 如果标签不在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
这是一个计算香农信息熵的函数，在输入之前构造的数据集的dataset之后，首先获得实例的个数，并且建立空的指标集合，不断循环dataset中的元素，取出标记，并且将新的指标加入指标集，旧的不做改变，将他们对应的数量+1.最后根据信息熵的公式计算信息熵，并且返回值。
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
然后再按给定的特征划分数据集，就是根据给定的特征，只取出对应特征和其对应的标签，以便后面计算信息熵，信息增益，并且从中选取最好的数据集划分方式。
def chooseBestFeatureToSplit(dataSet):
numFeatures = len(dataSet[0]) - 1 #the last column is used for the labels 列数-1
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
上面的函数就完成了选择最好的数据集划分方式，代码的具体含义都在注释中啦
def createTree(dataSet, labels):
classList = [example[-1] for example in dataSet] # 取出label标签
if classList.count(classList[0]) == len(classList): # count方法用于统计某个元素在列表中出现的个数
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个。用bestFeat取出属性的名字，并且使用之前定义的chooseBestFeature函数来选出最好的数据划分，再取出最好数据划分的label，定义mytree的一个空树（之后我们要将其长为一棵完整的决策树）。del删除掉已经取出的属性，取出已经取出的属性（即当前最好的属性）的所有值，通过集合set把属性值的列表集合化，即不出现重复元素了。然后递归调用createTree函数，直到满足退出条件，这样就构成一棵完整的树了。
下面赋上结果图
变量myTree包含了很多代表树结构信息的嵌套字典，从左边开始，第一个关键字no
surfacing是第一个划分数据集的特征名称，该关键字的值也是另一个数据字典。第二个关键字
是no surfacing特征划分的数据集，这些关键字的值是no surfacing节点的子节点。这些值
可能是类标签，也可能是另一个数据字典。如果值是类标签，则该子节点是叶子节点；如果值是
另一个数据字典，则子节点是一个判断节点，这种格式结构不断重复就构成了整棵树。本节的例
子中，这棵树包含了3个叶子节点以及2个判断节点。