决策树之ID3算法

代码之神

2019-06-26

前言

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

ID3算法

首先，让我们以例子来看看ID3算法的实现过程。
假设我们现在要做一次决策：判断一个人会买什么类型的保险。在这个例子中有如下特征：

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

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

决策树之ID3算法

接下来，ID3算法根据每个特征的重要程度（该值通过信息熵来判断，但是信息熵这个概念等下具体实现时候再说XD），构造如下的一个树：
对于如上格式的每个样例，首先判断性别（男或女），如果是男的，就需要用婚姻状况来判断；如果是女的，则需要用年龄来判断。这样迭代判断直到到达叶子节点，也就得出了可能选择的保险类型。

决策树之ID3算法

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

实现

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

信息熵（Entropy）
```
用于描述一组数据的混乱、不确定程度
    计算公式如下：
```
用上述例子来说，p（Xi）指所有数据中A、B、C这三个各自出现的概率，就是A、B、C各自的个数/总个数。
个人理解信息熵就是描述给出的这组数据的分类有多不确定。就比如预测明天下不下雨这一问题，信息熵就很大；而预测每一个人明天吃不吃饭这一问题，信息熵就很小。因为绝大部分人，明天肯定是要吃饭的orz。。。。
条件熵
```
用于描述一组数据的子数据的混乱、不确定程度
```
这是什么意思呢？个人理解就是确定数据的某一特征之后，在这一特征上的数据分类的不确定程度。比如依旧是预测明天下不下雨这一问题，如果现在明确告诉你，明天云的情况（多云、少云、没有云），那么在明天云情况这一特征上的每个分类都能计算相应的信息熵。
信息增益
```
用于描述某一特征对整体的重要程度
       根据定义，可以知道，信息增益就是总信息熵减去某个特征上各个分类的条件熵，如下：
```
1、被减数就是总信息熵。
2、减数中的value（T）是指在某一个特征的一种分类，如性别就包含两个分类（男、女），entropy（Sv）就是在该特征的某个分类上的条件熵。
3、S是指所有数据个数
4、Sv是指在该特征的一种分类下数据个数。

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

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

代码

#coding=utf-8
import csv
import pandas as pd
import math
import drewTree

def 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,bfNum

def 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)