机器学习算法|决策树ID3--python实现

####1.前言
最近在看一篇论文——《why_xgboosting_win_every_machine_learning_competition 》，顺便打算写几篇博文，把决策树相关知识做一个整理，从概念开始，经由一些经典算法，最终到对xgboosting的分析。
####2.概念
决策树是机器学习中的一个经典的算法，其简单性无与伦比，甚至一个不懂机器学习的人也能用它开始机器学习，可谓居家旅行，修身养性的必备良药。

决策树可分为两类，一类是分类树(Classification Tree)，主要用于处理离散的数据，比如性别、黑白、胖瘦这样的非连续变量。另一类是回归树(Regression Tree)，主要用于处理连续的数据，比如年龄、身高、体重这样的连续变量。

那么究竟什么是决策树呢？很简单，就是问问题，根据yes/no来选择下一个问题，直到能够做出判断。
这里，举个栗子。
任务：利用决策树判断未知对象是男的还是女的。
假设条件：已知的对象的属性只有声音和头发。
过程：首先，问问Ta声音粗还是声音细。如下图，根据声音的粗细分为２类。然后，问问Ta的头发是长发还是短发。如图所示，在第一次分类的基础上，又可分为２类，长发和短发。最后，判别出结果：如果Ta是声音细、头发长，那么很大可能是女的；相反，如果声音粗、头发短，很有可能是男的；以此类推。

上面的例子就是一个简单到不能再简单的决策树了。可以看出，决策树的本质就是根据数据的特征进行数据分类的递归过程。刚才是笼统的语言描述，现将具体步骤列出来，如下：

输入: 训练集 $D=(x_1,y_1),(x_2,y_2),...,(x_m,y_m);$
属性集 $A=a_1,a_2,a_3,...,a_d;$
过程: 函数CreateTree(D,A)
1. 生成节点node;
2. if D中样本全部属于同一类别C then
3. 将node标记为C类叶节点; return
4. end if
5. if $A＝\varnothing$ OR D中的样本在A上取值都相同 then
6. 将node标记为叶节点，其类别标记为D中样本数量最多的类; return
7. end if
8. 从A中选择最优的划分属性$a_{\ast };$
9. for $a_{\ast }$的每一个值$a_{\ast }^v$ do
10. 为node节点生成一个分支;令$D_v$表示D中在$a_{\ast }$上取值为$a_{\ast }^v$的样本子集;
11. if $D_v$为空 then
12. 将分支节点标记为叶节点，其类别标记为D中样本最多的类; return
13. else
14. 以CreateTree($D_v$,$a_{\ast }$)为分支节点
15. end if
16. end for
**输出:**以node为根节点的一棵决策树

####3.关于最优划分属性的选择
在上文决策树具体步骤的描述中，最关键的部分应该是第8步，即从A中选择最优的划分属性$a_{\ast }$。在最开始的例子中，我们为什么要先判断声音的粗细呢？为什么不能先判断头发的长短呢？答案是可以。那只是一个举例，并没有经过理性的计算和分析。

那么究竟如何计算和分析最优划分属性呢？

先来说说几个概念:

3.1.信息熵
我们希望每一次根据某个属性划分，得到的分支节点所包含的样本尽可能属于同一类别,即节点的“纯度”越来越高。在计算机领域，“信息熵”是度量样本集合纯度最常用的一种指标。假定当前样本集合D中第k类样本所占的比例为$p_k$(k=1,2,…,|Y|),则D的信息熵定义为
$$Ent(D)=-\sum _{k=1}^{|Y|}{p}_{k}lo{g}_2{p}_k,$$Ent(D)的值越小，则D的纯度越高。

3.2.信息增益
再考虑到不同的分支节点所包含的样本数量不同，理应具有不同的权重，那么给分支赋予权重$|D^v|/|D|$，即样本数量越多的分支节点所具有的影响越大，于是得到属性a对样本集D进行划分所获得的“信息增益”(information gain):
$$Gain(D,a)=Ent(D)-\sum _{v=1}^V\frac{|D^v|}{|D|}Ent(D^v),$$信息增益越大，意味着用属性a进行划分所获得的“纯度提升”越大。

####4.python实现
决策树学习算法最著名的代表是ID3、C4.5和CART。
这里先介绍ID3算法的python实现，C4.5算法我会在下一篇讨论决策树剪枝问题的文章一并讲述。

from math import log
import operator

#创建数据集
def createDataSet():
    dataSet = [['长', '粗', '男'],
               ['短', '粗', '男'],
               ['短', '粗', '男'],
               ['长', '细', '女'],
               ['短', '细', '女'],
               ['短', '粗', '女'],
               ['长', '粗', '女'],
               ['长', '粗', '女']]
    labels = ['头发', '声音']  # 两个特征
    return dataSet, labels

#从当前许多类别中挑出数目最多的类别
def majorityClass(classList):
    list={}
    for one in classList:
        if one not in list.keys():
            list[one]=0
        list[one]+=1
    sortedClass=sorted(list.items(),key=operator.itemgetter(1),reverse=True)
    return sortedClass[0][0]

#计算给定数据集的信息熵
def calcShannonEnt(dataSet):
    numberData=len(dataSet)
    classCount={}
    shannonEnt=0
    for one in dataSet:
        currentLabel=one[-1]
        if currentLabel not in classCount.keys():
            classCount[currentLabel]=0
        classCount[currentLabel]+=1
    for key in classCount:
        prob=float(classCount[key])/numberData
        shannonEnt-=prob*log(prob,2)
    return shannonEnt

#在数据集中选出第axis个属性值为value的子集，并且去掉该属性值（删除已判断过的属性及其值）
def splitDataSet(dataSet,axis,value):
    retDataSet=[]
    for examle in dataSet:
        if(examle[axis]==value):
            reducedDataSet=examle[:axis]
            reducedDataSet.extend(examle[axis+1:])
            retDataSet.append(reducedDataSet)
    return retDataSet

#在数据集中选出最优的划分属性，返回值为索引值
def chooseBestFeat(dataSet):
    numberFeats=len(dataSet[0])-1
    baseEntropy=calcShannonEnt(dataSet)
    baseInfoGain=0
    bestFeat=-1
    newEntropy=0
    for i in range(numberFeats):
        featList=[example[i] for example in dataSet]
        uniqueVals=set(featList)
        for one in uniqueVals:
            subDataSet=splitDataSet(dataSet,i,one)
            prob=len(subDataSet)/float(len(dataSet))
            newEntropy-=prob*calcShannonEnt(subDataSet)
        infoGain=baseEntropy-newEntropy
        if(infoGain>baseInfoGain):
            bestFeat=i
            baseInfoGain=infoGain
    return bestFeat

#对数据集创建树
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 majorityClass(classList)
    bestFeat=chooseBestFeat(dataSet)
    bestLabel=labels[bestFeat]
    Tree={bestLabel:{}}
    del(labels[bestFeat])
    featVals=[example[bestFeat] for example in dataSet]
    uniqueVals=set(featVals)
    for value in uniqueVals:
        subLabels=labels[:]
        #对分割后的数据子集递归创建树
        Tree[bestLabel][value]=CreateTree(splitDataSet(dataSet,bestFeat,value),subLabels)
    return Tree

if __name__ == '__main__':
    dataSet,labels=createDataSet()
    print(CreateTree(dataSet,labels))

####5.结尾
第一次认认真真的写markdown，发现好多知识点心里明白，但就是不能条理清晰地进行阐述，参考了我的启蒙教材——周志华教授的《机器学习》。
本人才疏学浅，对机器学习仅知皮毛，语言表述能力较弱，若有差错，还请指出，一起成长。