决策树之ID3算法

前言

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

ID3算法

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

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

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

决策树之ID3算法

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

决策树之ID3算法


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

实现

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

  • 信息熵(Entropy)

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

    决策树之ID3算法

    用上述例子来说,p(Xi)指所有数据中A、B、C这三个各自出现的概率,就是A、B、C各自的个数/总个数。
    个人理解信息熵就是描述给出的这组数据的分类有多不确定。就比如预测明天下不下雨这一问题,信息熵就很大;而预测每一个人明天吃不吃饭这一问题,信息熵就很小。因为绝大部分人,明天肯定是要吃饭的orz。。。。

  • 条件熵

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

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

  • 信息增益

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

    决策树之ID3算法

    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)
参考博客:http://blog.csdn.net/wzmsltw/...

相关推荐