一，什么是决策树

所谓决策树，顾名思义，是一种树，一种依托于策略抉择而建立起来的树。机器学习中，决策树是一个预测模型；它代表的是对象属性与对象值之间的一种映射关系。树中每个节点表示某个对象，而每个分叉路径则代表的是某个可能的属性值，而每个叶子节点则对应根节点到该叶子节点所经历的路径所表示的对象的值。决策树仅有单一输出，若欲有复数输出，可以建立独立的决策树以处理不同的输出。

         从数据产生决策树的机器学习技术叫做决策树学习，通俗点就是决策树，是一种依托于分类、训练上的预测树，根据已知预测、归类未来。
 

二，ID3算法

   ID3算法是一个由RossQuinlan发明的用于决策树的算法。这个算法便是建立在奥卡姆剃刀的基础上：越是小型的决策树越优于大的决策树。尽管如此，该算法也不是总是生成最小的树形结构，而是一个启发式算法。

         汤姆米歇尔《机器学习》中对ID3算法的描述：

         ID3算法思想描述：

1)                对当前例子集合，计算属性的信息增益；

2)                选择信息增益大的属性A

3)                把在A处取值相同的例子归于同意子集，A取几个值就得几个子集

4)                依次对每种取值情况下的子集，返回1）递归调用建树算法，

5)                若子集中只含有单个属性，则分支为叶子节点，判断其属性值并标上相应的符号，然后返回调用处。
 

三，通过案例理解决策

头发	声音	性别
长	粗	男
短	粗	男
短	粗	男
长	细	女
短	细	女
短	粗	女
长	粗	女
长	粗	女

此案例有两种判断方法
一是先按头发长短判断，再按声音粗细判断，判断过程如下图

 于是，一个简单的直观的决策树就这么出来了

此时我们又可以通过声音来判断，然后再根据头发来判断：

四，通过ID3算法选出更优决策树

我们可以使用多种方法划分数据集，但是每种方法都有各自的优缺点。于是我们这么想，如果我们能测量数据的复杂度，对比按不同特征分类后的数据复杂度，若按某一特征分类后复杂度减少的更多，那么这个特征即为最佳分类特征。
Claude Shannon 定义了熵（entropy）和信息增益(information gain)。
用熵来表示信息的复杂度，熵越大，则信息越复杂。公式如下：

信息增益(information gain)，表示两个信息熵的差值。
首先计算未分类前的熵，总共有8位同学，男生3位，女生5位。
熵（总）=-3/8*log2(3/8)-5/8*log2(5/8)=0.9544
接着分别计算同学A和同学B分类后信息熵。
同学A首先按头发分类，分类后的结果为：长头发中有1男3女。短头发中有2男2女。
熵（同学A长发）=-1/4*log2(1/4)-3/4*log2(3/4)=0.8113
熵（同学A短发）=-2/4*log2(2/4)-2/4*log2(2/4)=1
熵（同学A）=4/8*0.8113+4/8*1=0.9057
信息增益（同学A）=熵（总）-熵（同学A）=0.9544-0.9057=0.0487
同理，按同学B的方法，首先按声音特征来分，分类后的结果为：声音粗中有3男3女。声音细中有0男2女。
熵（同学B声音粗）=-3/6*log2(3/6)-3/6*log2(3/6)=1
熵（同学B声音粗）=-2/2*log2(2/2)=0
熵（同学B）=6/8*1+2/8*0=0.75
信息增益（同学B）=熵（总）-熵（同学A）=0.9544-0.75=0.2087

按同学B的方法，先按声音特征分类，信息增益更大，区分样本的能力更强，更具有代表性。

 五，pyth实现ID3算法

from math import log
import operator

def calcshannonEnt(dataset): #计算数据的嫡(entropy)
    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
    for key in labelcounts:
        prob = float(labelcounts[key]) / numEntries  # 计算单个类的嫡值
        shannonEnt -= prob*log(prob,2)#累加每个类的嫡值
    return shannonEnt

def createDataset1():# 创造示例数据
    dataset = [['长', '粗', '男'],
               ['短', '粗', '男'],
               ['短', '粗', '男'],
               ['长', '细', '女'],
               ['短', '粗', '女'],
               ['短', '细', '女'],
               ['长', '粗', '女'],
               ['长', '粗', '女']]
    labels = ['头发', '声音']#两个特征
    return dataset, labels

def splitDataset(dataset,axis,value):#按某个特征分类后的数据
    retDataSet = []
    for featvec in dataset:
        if featvec[axis] == value:
            reducedFeatvec = featvec[: axis]
            reducedFeatvec.extend(featvec[axis + 1:])
            retDataSet.append(reducedFeatvec)
        return retDataSet

def chooseBestFeatureToSplit(dataset): #选择最优的分类特征
    numFeatures = len(dataset[0]) - 1
    baseEntropy = calcshannonEnt(dataset)  # 原始的嫡
    bestInfoGain = 0
    bestFeature = -1
    for i in range(numFeatures):
        featlist = [example[i] for example in dataset]
        uniquevals = set(featlist)
        newEntropy = 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):#按分类后类别数量排序，比如:最后分类为2男1女，则判定为男;
    classcount = {}
    for vote in classList:
        if vote not in classcount.keys():
            classcount[vote] = 0
        classcount[vote] += 1
    sortedclasscount = sorted(classcount.items(), 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]
    if len(dataSet[0]) == 1:
        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[:]
        myTree[bestFeatLabel][value] = createTree(splitDataset\
                                                      (dataSet, bestFeat, value), subLabels)
    return myTree


if __name__ == '__main__':
    dataset, labels=createDataset1() #创造示列数据
    print(createTree(dataset, labels))  # 输出决策树模型结果

输出结果：