前言

决策树算法，是指一类通过对数据集中特征的选择，构造一个树，实现对数据的分类的算法。这棵树的每一个节点都是选中的其中一种特征，而该节点的边则是这种特征的分类。更详细的定义可以Google之。

ID3算法

首先，让我们以例子来看看ID3算法的实现过程。

假设我们现在要做一次决策：判断一个人会买什么类型的保险。在这个例子中有如下特征：

• 性别（男、女）
• 年龄（<21、>=21and=<25、>25）
• 婚姻状况（已婚、未婚）

而根据这些特征，我们会有最终每个人购买的保险类型（A、B、C），以下给出数据：

接下来，ID3算法根据每个特征的重要程度（该值通过信息熵来判断，但是信息熵这个概念等下具体实现时候再说XD），构造如下的一个树：

对于如上格式的每个样例，首先判断性别（男或女），如果是男的，就需要用婚姻状况来判断；如果是女的，则需要用年龄来判断。这样迭代判断直到到达叶子节点，也就得出了可能选择的保险类型。

---

那么，此时重点来了，我们该如何判断选择哪个特征最合适呢？？

实现

经过许多大神的不懈研究，借鉴了物理学上的熵的概念，信息领域提出了如下几个定义：

• 信息熵（Entropy）

  用于描述一组数据的混乱、不确定程度    计算公式如下：

  

  用上述例子来说，p（Xi）指所有数据中A、B、C这三个各自出现的概率，就是A、B、C各自的个数/总个数。

  个人理解信息熵就是描述给出的这组数据的分类有多不确定。就比如预测明天下不下雨这一问题，信息熵就很大；而预测每一个人明天吃不吃饭这一问题，信息熵就很小。因为绝大部分人，明天肯定是要吃饭的orz。。。。

• 条件熵

  用于描述一组数据的子数据的混乱、不确定程度

  这是什么意思呢？个人理解就是确定数据的某一特征之后，在这一特征上的数据分类的不确定程度。比如依旧是预测明天下不下雨这一问题，如果现在明确告诉你，明天云的情况（多云、少云、没有云），那么在明天云情况这一特征上的每个分类都能计算相应的信息熵。

• 信息增益

  用于描述某一特征对整体的重要程度       根据定义，可以知道，信息增益就是总信息熵减去某个特征上各个分类的条件熵，如下：

  

  1、被减数就是总信息熵。

  2、减数中的value（T）是指在某一个特征的一种分类，如性别就包含两个分类（男、女），entropy（Sv）就是在该特征的某个分类上的条件熵。
  3、S是指所有数据个数
  4、Sv是指在该特征的一种分类下数据个数。

---

在了解了这些定义后，我们回到最开始的问题：如何判断哪个特征最合适你？

上面说到，信息熵越大，数据集就越混乱，就越难得到准确的结果，所以我们要选择的特征应该能使得在确定这个特征后的信息熵越小，也就是条件熵越小，亦即信息增益最大。因此，具体实现思路如下：**遍历所有特征，根据遍历的每个特征进行数据集分类，算出每个特征下的条件熵，然后取条件熵最小的，信息增益最大的特征。接着，根据选择的特征进行分类，得到的子数据在删除选择的特征后，递归选择下一个特征**

代码

#coding=utf-8import csvimport pandas as pdimport mathimport drewTreedef readData(path):    df=pd.read_csv(path)    return df.values.tolist(),df.columns.values.tolist()#计算信息熵def countEntropy(data):    sumEg=len(data)    labelCount={}    #计算不同保险类别的数量    for example in data:        if example[-1] not in labelCount.keys():            labelCount[example[-1]]=0        labelCount[example[-1]]+=1    #开始计算信息熵    ent=0    for key in labelCount:        prop=float(labelCount[key])/sumEg        ent-=prop*math.log(prop,2)    return ent#根据特征分类划分数据集def splitData(data,featureNum):    res={}    for example in data:        if example[featureNum] not in res.keys():            res[example[featureNum]]=[]        res[example[featureNum]].append(example)    return res#移除数据中已经选择的特征值def removeFeature(data,featureNum):    res=[]    for example in data:        example.pop(featureNum)        res.append(example)    return res#单特征投票#当所有特征都选择完时，还有多于1个以上的样例，则直接根据保险类型投票，票高者得胜def vote(classData):    count={}    for example in classData:        if example not in count.keys():            count[example]=0        count[example]+=1    return max(count)#选择信息增益最大的特征def selectBestFeature(data,dataLabel):    sumEnt=countEntropy(data)    sumFeatureNum=len(data[0])-1    minConditionEnt = 999999    bestFeature = []    bfNum = -2    #计算每个特征的信息增益    for i in range(sumFeatureNum):        spData=splitData(data,i)        num=len(data)        conditionEnt=0        for key in spData:            conditionEnt+=float(len(spData[key]))/num*countEntropy(spData[key])        if (conditionEnt < minConditionEnt):            minConditionEnt = conditionEnt            bestFeature =dataLabel[i]            bfNum=i    return bestFeature,bfNumdef createTree(data,dataLabel):    #只剩保险类型时，根据剩余的数据集进行投票    if len(data[0])==1:        return vote(example[-1] for example in data)    bestFeature,bfNum=selectBestFeature(data,dataLabel)    dicisionTree={bestFeature:{}}    bestFeatureData=splitData(data,bfNum)    label=dataLabel    temp=label.pop(bfNum)    #剩余特征进行递归构造决策树    for key in bestFeatureData:        rmFData=removeFeature(bestFeatureData[key],bfNum)        dicisionTree[bestFeature][key]=createTree(rmFData,label)    label.insert(bfNum,temp)    return dicisionTree    #调用data,dataLabel=readData("./ID3New.csv")res=createTree(data,dataLabel)

参考博客：