决策树算法，python结合pandas编程实现

1.信息增益

 

1.1 信息熵

        在信息论中，信息熵度量样本集合纯度是最常用的一种指标，信息熵用来描述信源的不确定度。例如:

A=太阳从东方升起      
B=太阳从西方升起

      对于句子A，确定度很高，基本为必然事件。其信息熵较低，所含的信息量很小。

      对于句子B，不确定性特别高，基本不可能发生，所以其信息熵很高，所含信息量很大。

      需要注意的是，在自然语言处理中：

1.落霞与孤鹜齐飞，秋水共长天一色。 
2.落日下的晚霞与孤独的大雁一同飞翔，晚秋的江水和深远的天空连成一片

       按照信息熵的计算，第二句比第一句的信息熵要高1倍以上，你会觉得第二句比第一句水平要高，信息量更大么？在自然语言处理中出现较大的信息熵，只表示可能出现的语言字符较多，并不意味着你可以从中得到更多的信息。

 

信息熵公式：

1.2 信息增益

 

是否爱学习	是否天天打游戏	是否沉迷女色	是否是优秀学生
爱学习	不打游戏	沉迷女色	是
爱学习	打游戏	不沉迷女色	是
不爱学习	打游戏	沉迷女色	否
不爱学习	打游戏	不沉迷女色	否

        我们用爱学习，打游戏，沉迷女色来对数据集D（是否是优秀学生）进行决策。我们可以通过上式计算出数据集D的信息熵。首先，计算是否是优秀学生的信息熵：

在考虑属性划分时，我们有多个策略 如：

 

那么我们应该怎么选择呢？这里引入了信息增益的概念：

d为每个节点对应的属性，比如打游戏就分为d1=打游戏，d2=不打游戏。一般而言，信息增益越大，则意味着使用此属性来进行划分所获得的‘纯度提升’越大。

让我们来推到一下：

当a为沉迷女色时：

D1为沉迷女色，D2为不沉迷女色

 

a为打游戏时：

D1为天天打游戏，D2为不打游戏

 

 

当a为爱学习时：

从信息增益的结果我们发现爱学习对判断一个学生是否优秀有很大提升，所以在决策树中我们会首选爱学习作为决策属性。然后再对其余属性递归。

 

python代码实现（未进行减枝策略）：

# -*- coding: utf-8 -*-
"""
Created on Tue Sep  4 09:46:00 2018

@author: Adam
"""
import pandas as pd 
import numpy as np


dataSet = [['爱学习','不打游戏','沉迷女色','是'],
           ['爱学习','打游戏','不沉迷女色','是'],
           ['不爱学习','打游戏','沉迷女色','否'],
           ['不爱学习','打游戏','不沉迷女色','否']]

labels = ['是否爱学习','是否天天打游戏','是否沉迷女色','是否是优秀学生']

data = pd.DataFrame(dataSet,columns=labels)
data = data.set_index('是否是优秀学生')


def Ent(data,col):
    number = len(data)
    label = data.index.value_counts()
    ent = 0
    for x in label:
        ent += -(x/number)*np.log2(x/number)
    return ent

indexEnt= Ent(data,data.index.name)

def GainEntTree(data,indexEnt):
    LabelData=list(data.index)
    if LabelData.count(LabelData[0])==len(LabelData):
        return LabelData[0]
    if len(data.columns)==0:
        return data.index.value_counts().sort_values(ascending=False).index[0]
    if len(data.columns)>0:
        GainEntlist=[]
        columnslist = data.columns
        lendata=len(data)
        for i in data.columns:
            Gain=[]
            ColValueCounts=data[i].value_counts()
            ColValueCountsindex=ColValueCounts.index
            ColValueCountsvalues=ColValueCounts.values
            for j in range(len(ColValueCountsindex)):
                D = data[data[i]==ColValueCountsindex[j]].index.value_counts()
                ent=sum([-(z/lendata)*np.log2(z/ColValueCountsvalues[j]) for z in D])
                Gain.append(ent)
            GainEntlist.append(sum(Gain))
        GainEntlist=[indexEnt-x for x in GainEntlist]
        x=dict(zip(columnslist,GainEntlist))
        top=sorted(x.items(),key=lambda item:item[1],reverse=True)[0][0]
        myTree={top:{}}
        for value in set(data[top]):
            newdata=data[data[top]==value].drop(top,axis=1)
            myTree[top][value]=GainEntTree(newdata,Ent(newdata,newdata.index.name))
        return myTree

GainEntTree(data,indexEnt)            
         






     

输出为

In [176]: GainEntTree(data,indexEnt)
Out[176]: {'是否爱学习': {'不爱学习': '否', '爱学习': '是'}}

用周志华老师机器学习书中的西瓜数据集检查一下

dataSet = [['青绿','蜷缩','浊响','清晰','凹陷','硬滑','是'],
           ['乌黑','蜷缩','沉闷','清晰','凹陷','硬滑','是'],
           ['乌黑','蜷缩','浊响','清晰','凹陷','硬滑','是'],
           ['青绿','蜷缩','沉闷','清晰','凹陷','硬滑','是'],
           ['浅白','蜷缩','浊响','清晰','凹陷','硬滑','是'],
           ['青绿','稍蜷','浊响','清晰','稍凹','软粘','是'],
           ['乌黑','稍蜷','浊响','稍糊','稍凹','软粘','是'],
           ['乌黑','稍蜷','浊响','清晰','稍凹','硬滑','是'],
           ['乌黑','稍蜷','沉闷','稍糊','稍凹','硬滑','否'],
           ['青绿','硬挺','清脆','清晰','平坦','软粘','否'],
           ['浅白','硬挺','清脆','模糊','平坦','硬滑','否'],
           ['浅白','蜷缩','浊响','模糊','平坦','软粘','否'],
           ['青绿','稍蜷','浊响','稍糊','凹陷','硬滑','否'],
           ['浅白','稍蜷','沉闷','稍糊','凹陷','硬滑','否'],
           ['乌黑','稍蜷','浊响','清晰','稍凹','软粘','否'],
           ['浅白','蜷缩','浊响','模糊','平坦','硬滑','否'],
           ['青绿','蜷缩','沉闷','稍糊','稍凹','硬滑','否']]

labels = ['色泽','根蒂','敲声','纹理','脐部','触感','好瓜']

第一轮信息增益：

[('纹理', 0.3805918973682686),
 ('脐部', 0.28915878284167895), 
('根蒂', 0.14267495956679277), 
('敲声', 0.14078143361499607),
('色泽', 0.10812516526536531), 
('触感',0.006046489176565695)]

信息增益与决策结果与书中数据吻合。

In [18]:GainEntTree(data,indexEnt)
Out[18]: 
{'纹理': {'模糊': '否','清晰': {'根蒂': {'硬挺': '否','稍蜷': {'色泽': {'乌黑': {'触感': {'硬滑': '是', '软粘': '否'}}, '青绿': '是'}},'蜷缩': '是'}},'稍糊': {'触感': {'硬滑': '否', '软粘': '是'}}}}