什么是分类决策树？分类决策树能用来干什么？举个例子就明白了。
一位母亲要给她女儿介绍对象，于是有了如下对话：
女儿：多大年纪了？
母亲：26。
女儿：长的帅不帅？
母亲：挺帅的。
女儿：收入高不？
母亲：不算很高，中等情况。
女儿：是公务员不？
母亲：是，在税务局上班呢。
女儿：那好，我去见见。
这个女孩的决策过程就是典型的分类树决策。通过年龄、长相、收入和是否公务员对将男人分为两个类别：见和不见。
现在对机器来说，假设给了它一系列的“前提”（特征），让它对这件事作出判断，这就是分类决策树。说白了，假设有了树，对机器来说，就是不断的if--else--，如果年龄小于30、长的挺帅、收入挺高，机器就知道了，我要去见他。
显然，决策树也是监督学习的一种，先需要历史数据去构建决策树，再可根据决策树去对一些未知数据惊醒分类。
那么，怎么去构建决策树？
再举个例子，表5.1是贷款申请样本数据表，根据年龄、有工作、有房子、信贷情况4个特征来决定是否给你贷款。表格中的数据都是已知的确定的，也就是历史数据，年轻没工作没房子信贷情况一般的人，就一定不给贷款，而青年有工作没房子信贷情况好的人，就一定给贷款…这15种情况是已知的。
我们可以按照上面的情况同样构建一颗树，最开始的节点“年龄”，后有三个分支，“青年”“中年”“老年”，形成三个节点，每个节点后又可以有两个分支，“有工作”“无工作”，总共形成六个节点，“有房子”“无房子”，“信贷好”“信贷一般”…以此类推，最后总共有24种情况，每种情况对应着一种类别“给贷款”“不给贷款”，很显然，这是一种很差的分类方式，完全没有结合数据自身的信息，只是尽数遍历。
怎样去构建一个好的决策树呢？
关键在于选择分类节点的先后顺序。比如有了表5.1的数据，上面我们是选择了“年龄”作为第一个节点，但这是否更有效的？如果我选择“有房子”作为第一个节点，直观上应该更好（因为有房子都给贷款，一下把很多情况都给覆盖了）。
于是我们要根据把类分的更开的特征作为第一个节点，依次往下。也就是说，在根据节点分类之前，总的数据的信息熵一定（在例子中为15条数据），称为经验熵，根据“有房子”这个节点分类后，15条数据变成两类（6条有房子，9条无房子），这两类的熵加起来，称为经验条件熵（在“有无房子”的条件下是否给你贷款），熵代表信息的不确定程度，熵越大，越混乱，信息越不确定。经验熵-经验条件熵的差值称为信息增益，我们要找的“把数据分的更开”的节点，也就是信息增益最大的节点。也就是有了这个节点分类后，这些数据的不确定性最小。
就拿这个例子来讲，什么条件都没有的情况下，15条数据，给不给贷款的不确定性就很大呀，有了第一个节点“有无房子”，分好类之后，显然，假如你有房子，就确定了一定会给你贷款，假如你没有房子，给你贷款也不确定，但总的来说，这两种情况的不确定加起来，还是要远小于原始的15条数据的不确定性。
如果选择“年龄”作为第一个节点分类，假如你是青年，给你贷款不确定；假如你是中年，给你贷款不确定；假如你是老年，给你贷款不确定。有了“年龄”的条件后的不确定还是要大于“有房子”的条件不确定性。于是我们选择“有房子”作为第一个节点。
**这就是ID3算法的核心：选择信息增益最大的特征作为优先节点。
算法步骤：
- 找到信息增益最大的特征，以它为节点
- 递归createTree
- 类别完全相同或分类到了最后一个节点，结束递归**
这里写图片描述
代码如下：
trees.py
'''
Created on 2017年7月29日
@author: fujianfei
'''
from math import log2
import operator
def calcShannonEnt(dataSet):
'''
.计算香农熵
'''
numEntries = len(dataSet)
#提取数据中总共有多少类
labelCounts = {}
for featVec in dataSet:#遍历数据集
currLabel = featVec[-1]#提取每一个样本的最后一列（即标签）
#为所有可能分类创建数据字典
if currLabel not in labelCounts.keys():
labelCounts[currLabel] = 0
labelCounts[currLabel] += 1
shannonEnt = 0.0
#计算香农熵，-Pi*logPi
for key in labelCounts:
prob = float(labelCounts[key])/numEntries
shannonEnt -= prob * log2(prob)
return shannonEnt
def splitDataSet(dataSet, axis, value):
'''
.按照给定特征划分数据集
dataSet:数据集
axis:按照哪维特征划分数据
value:某个特征值
'''
reDataSet = []#定义重组后的数据集
for featVec in dataSet:
if featVec[axis] == value:#如果某行的数据的标签等于传入的value
#则对数据进行重组，把axis去掉，留下其他特征
reduceFeatVec = featVec[:axis]
reduceFeatVec.extend(featVec[axis+1:])
reDataSet.append(reduceFeatVec)
#最后返回的重组后的数据集，reDataSet,特征为除axis维后的dataSet的所有特征，标签全为value
return reDataSet
def chooseBestFeatureToSplit(dataSet):
'''
.在给定dataSet中选择最好的纬度，来划分数据集
.根据计算最好的信息增益来决定哪位哪个纬度最好
'''
numFeatures = len(dataSet[0]) - 1#除去最后一列标签的长度
baseEntropy = calcShannonEnt(dataSet)#计算经验基础熵
bestInfoGain = 0.0;bestFeature = -1;#定义最好的信息增益 和 划分数据集最好的特征
for i in range(numFeatures):
featList = [example[i] for example in dataSet]#第i列特征对应的所有值
uniqueVals = set(featList)#Python语言原生的集合，将重复的特征合并，生成唯一的特征列表
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
if (infoGain > bestInfoGain):
bestInfoGain = infoGain
bestFeature = i
return bestFeature
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), reserve=True)
return sortedClassCount[0][0]
def createTree(dataSet, labels):
'''
.创建决策树
'''
classList = [example[-1] for example in dataSet]#dataSet的最后一列，类别列
#结束递归的条件:
#1.类别完全相同
if classList.count(classList[0]) == len(classList):
return classList[0]
#2.分类到了最后一个节点，用多数投票决定类别
if len(dataSet[0]) == 1:
return majorityCnt(classList)
bestFeat = chooseBestFeatureToSplit(dataSet)#找到dataSet最好的特征，来分割数据
bestFeatLabel = labels[bestFeat]#特征对应的标签
mytree = {bestFeatLabel:{}}#定义树，用字典类型的结构就足以表示决策树全部的信息
del(labels[bestFeat])#将用过的标签删除
featList = [example[bestFeat] for example in dataSet]
uniqueVals = set(featList)
for value in uniqueVals:
subLabels = labels[:]
mytree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value), subLabels)
return mytree
init.py
from DecisionTree import trees
def createDataSet():
dataSet = [[1,1,'yes'],
[1,1,'yes'],
[1,0,'no'],
[0,1,'no'],
[0,1,'no']]
labels = ['no surfacing','flippers']
return dataSet,labels
myDat,labels = createDataSet()
mytree = trees.createTree(myDat, labels)
print(mytree)
运行结果如下，决策树是存放在dict类型里，这周有点事，也懒得准备很多数据了，下周会将画节点图和CART算法补上。
