决策树的生成与训练-信息增益

Python 3 解法, 执行用时: 821ms, 内存消耗: 65536KB, 提交时间: 2022-07-18

# -*- coding: UTF-8 -*-
from math import log
import pandas as pd

dataSet = pd.read_csv('dataSet.csv', header=None).values.tolist()

#给定一个数据集，calcInfoEnt可以用于计算一个数据集的信息熵，可直接调用
#也可不使用，通过自己的方式计算信息增益
def calcInfoEnt(data):
    numEntres = len(data)
    labelcnt = {} #用于统计正负样本的个数
    for item in data:
        if item[-1] not in labelcnt:
            labelcnt[item[-1]] = 0
        labelcnt[item[-1]] += 1
    infoEnt = 0.0
    for item in labelcnt: #根据信息熵的公式计算信息熵
        curr_info_entr = float(labelcnt[item]) / numEntres
        infoEnt = infoEnt - curr_info_entr * log(curr_info_entr,2)
    return infoEnt
    #返回值 infoEnt 为数据集的信息熵

#给定一个数据集，用于切分一个子集，可直接用于计算某一特征的信息增益 
#也可不使用，通过自己的方式计算信息增益   
#dataSet是要划分的数据集，i 代表第i个特征的索引index
#value对应该特征的某一取值
def create_sub_dataset(dataSet, i, value): 
    res = []
    for item in dataSet:
        if item[i] == value:
            curr_data = item[:i] + item[i+1:]
            res.append(curr_data)
    return res

def calc_max_info_gain(dataSet):#计算所有特征的最大信息增益，dataSet为给定的数据集
    n = len(dataSet[0])-1  # n 是特征的数量，-1 的原因是最后一列是分类标签
    total_entropy = calcInfoEnt(dataSet)#整体数据集的信息熵
    max_info_gain = [0,0]#返回值初始化
    #code start here
    for i in range(n):
        featList=[feat[i] for feat in dataSet]
        featValues=set(featList)
        newEntropy=0.0
        for value in featValues:
            subDataset=create_sub_dataset(dataSet,i,value)
            prob=len(subDataset)/len(dataSet)
            newEntropy+=prob*calcInfoEnt(subDataset)
        infoGain=total_entropy-newEntropy
        if infoGain>max_info_gain[1]:
            max_info_gain[1]=infoGain
            max_info_gain[0]=i 
    
    #code end here
    return max_info_gain
if __name__ == '__main__':
    info_res = calc_max_info_gain(dataSet)
    print("信息增益最大的特征索引为：{0},对应的信息增益为{1}".format(info_res[0],info_res[1]))

Python 3 解法, 执行用时: 825ms, 内存消耗: 65536KB, 提交时间: 2022-07-09

# -*- coding: UTF-8 -*-
from math import log
import pandas as pd

dataSet = pd.read_csv('dataSet.csv', header=None).values.tolist()

#给定一个数据集，calcInfoEnt可以用于计算一个数据集的信息熵，可直接调用
#也可不使用，通过自己的方式计算信息增益
def calcInfoEnt(data):
    numEntres = len(data)
    labelcnt = {} #用于统计正负样本的个数
    for item in data:
        if item[-1] not in labelcnt:
            labelcnt[item[-1]] = 0
        labelcnt[item[-1]] += 1
    infoEnt = 0.0
    for item in labelcnt: #根据信息熵的公式计算信息熵
        curr_info_entr = float(labelcnt[item]) / numEntres
        infoEnt = infoEnt - curr_info_entr * log(curr_info_entr,2)
    return infoEnt
    #返回值 infoEnt 为数据集的信息熵

#给定一个数据集，用于切分一个子集，可直接用于计算某一特征的信息增益 
#也可不使用，通过自己的方式计算信息增益   
#dataSet是要划分的数据集，i 代表第i个特征的索引index
#value对应该特征的某一取值
def create_sub_dataset(dataSet, i, value): 
    res = []
    for item in dataSet:
        if item[i] == value:
            curr_data = item[:i] + item[i+1:]
            res.append(curr_data)
    return res

def calc_max_info_gain(dataSet):#计算所有特征的最大信息增益，dataSet为给定的数据集
    n = len(dataSet[0])-1  # n 是特征的数量，-1 的原因是最后一列是分类标签
    total_entropy = calcInfoEnt(dataSet)#整体数据集的信息熵
    max_info_gain = [0,0]#返回值初始化
    #code start here
    for i in range(n):
        cur1=0.0
        un=[]
        for j in dataSet:
            un.append(j[i])
        un=set(un)
        for val in un:
            zj=create_sub_dataset(dataSet,i,val)
            pro=len(zj)*1.0/len(dataSet)
            cur1+=pro*calcInfoEnt(zj)
        res=total_entropy-cur1
        if res>max_info_gain[1]:
            max_info_gain[0]=i
            max_info_gain[1]=res
    #code end here
    return max_info_gain
if __name__ == '__main__':
    info_res = calc_max_info_gain(dataSet)
    print("信息增益最大的特征索引为：{0},对应的信息增益为{1}".format(info_res[0],info_res[1]))

Python 3 解法, 执行用时: 831ms, 内存消耗: 65536KB, 提交时间: 2022-07-18

# -*- coding: UTF-8 -*-
from math import log
import pandas as pd

dataSet = pd.read_csv('dataSet.csv', header=None).values.tolist()

#给定一个数据集，calcInfoEnt可以用于计算一个数据集的信息熵，可直接调用
#也可不使用，通过自己的方式计算信息增益
def calcInfoEnt(data):
    numEntres = len(data)
    labelcnt = {} #用于统计正负样本的个数
    for item in data:
        if item[-1] not in labelcnt:
            labelcnt[item[-1]] = 0
        labelcnt[item[-1]] += 1
    infoEnt = 0.0
    for item in labelcnt: #根据信息熵的公式计算信息熵
        curr_info_entr = float(labelcnt[item]) / numEntres
        infoEnt = infoEnt - curr_info_entr * log(curr_info_entr,2)
    return infoEnt
    #返回值 infoEnt 为数据集的信息熵

#给定一个数据集，用于切分一个子集，可直接用于计算某一特征的信息增益 
#也可不使用，通过自己的方式计算信息增益   
#dataSet是要划分的数据集，i 代表第i个特征的索引index
#value对应该特征的某一取值
def create_sub_dataset(dataSet, i, value): 
    res = []
    for item in dataSet:
        if item[i] == value:
            curr_data = item[:i] + item[i+1:]
            res.append(curr_data)
    return res

def calc_max_info_gain(dataSet):#计算所有特征的最大信息增益，dataSet为给定的数据集
    n = len(dataSet[0])-1  # n 是特征的数量，-1 的原因是最后一列是分类标签
    total_entropy = calcInfoEnt(dataSet)#整体数据集的信息熵
    max_info_gain = [0,0]#返回值初始化
    #code start here
    numEntres = len(dataSet) # 数据集某一类的样本个数
    # print(label_cnt)

    for i in range(n): # 循环获取i特征

        feature_cnt = {} #用于存放i特征正负样本的个数
        for item in dataSet: #用于统计i特征的样本分类个数
            if item[i] not in feature_cnt:
                feature_cnt[item[i]] = 0
            feature_cnt[item[i]] += 1
        # print(feature_cnt)

        H_sum = 0.0	#初始化条件熵	
        for item in feature_cnt: #循环i特征分类值
            res = create_sub_dataset(dataSet, i, item) # 根据i特征的样本分类切割数据

            res_cnt = {} # 存放依据label标签统计i特征的样本分类切割数据个数
            for res_i in res: # 依据label标签统计i特征的样本分类切割数据个数
                if res_i[-1] not in res_cnt:
                    res_cnt[res_i[-1]] = 0
                res_cnt[res_i[-1]] += 1
            # print(res_cnt)

            H = 0.0
            for res_cnt_i in res_cnt: #计算i特征分类res_cnt_i的条件熵
                # print(res_cnt[res_cnt_i])
                Pi = res_cnt[res_cnt_i]/feature_cnt[item]
                H -= Pi * log(Pi, 2)
            
            # print(H) 
            H_sum += feature_cnt[item] / numEntres * H #计算i特征的总条件熵

        # H(D|i) 
        g_Di = total_entropy - H_sum# 计算i特征的信息增益,公式：g(D,i) = H(D) - H(D|i)
        if max_info_gain[1] < g_Di:
            max_info_gain = [i, g_Di]
    #code end here
    return max_info_gain
if __name__ == '__main__':
    info_res = calc_max_info_gain(dataSet)
    print("信息增益最大的特征索引为：{0},对应的信息增益为{1}".format(info_res[0],info_res[1]))

Python 3 解法, 执行用时: 839ms, 内存消耗: 65536KB, 提交时间: 2022-06-23

# -*- coding: UTF-8 -*-
from math import log
import pandas as pd

dataSet = pd.read_csv('dataSet.csv', header=None).values.tolist()

#给定一个数据集，calcInfoEnt可以用于计算一个数据集的信息熵，可直接调用
def calcInfoEnt(data):
    numEntres = len(data)
    labelcnt = {} #用于统计正负样本的个数
    for item in data:
        if item[-1] not in labelcnt:
            labelcnt[item[-1]] = 0
        labelcnt[item[-1]] += 1
    infoEnt = 0.0
    for item in labelcnt: #根据信息熵的公式计算信息熵
        curr_info_entr = float(labelcnt[item]) / numEntres
        infoEnt = infoEnt - curr_info_entr * log(curr_info_entr,2)
    return infoEnt
    #返回值 infoEnt 为数据集的信息熵

#给定一个数据集，用于切分一个子集，可直接用于计算某一特征的信息增益    
#dataSet是要划分的数据集，i 代表第i个特征的索引index
#value对应该特征的某一取值
def create_sub_dataset(dataSet, i, value): 
    res = []
    for item in dataSet:
        if item[i] == value:
            curr_data = item[:i] + item[i+1:]
            res.append(curr_data)
    return res

def calc_max_info_gain(dataSet):#计算所有特征的最大信息增益，dataSet为给定的数据集
    n = len(dataSet[0])-1  # n 是特征的数量
    total_entropy = calcInfoEnt(dataSet)#整体数据集的信息熵
    max_info_gain = [0,0]#返回值初始化
    #code start here
    for i in range(n):
        cur_info_ent = 0.0
        unique_val = []
        for item in dataSet:
            unique_val.append(item[i])
        unique_val = set(unique_val)
        for val in unique_val:
            sub_dataset = create_sub_dataset(dataSet, i, val)
            prob = len(sub_dataset) * 1.0 / (len(dataSet))
            cur_info_ent += prob * calcInfoEnt(sub_dataset)
        cur_info_gain = total_entropy - cur_info_ent
        if cur_info_gain > max_info_gain[1]:
            max_info_gain[0] = i
            max_info_gain[1] = cur_info_gain
    #code end here
    return max_info_gain
if __name__ == '__main__':
    info_res = calc_max_info_gain(dataSet)
    print("信息增益最大的特征索引为：{0},对应的信息增益为{1}".format(info_res[0],info_res[1]))

Python 3 解法, 执行用时: 855ms, 内存消耗: 65536KB, 提交时间: 2022-07-18

# -*- coding: UTF-8 -*-
from math import log
import pandas as pd
from collections import Counter

dataSet = pd.read_csv('dataSet.csv', header=None).values.tolist()

#给定一个数据集，calcInfoEnt可以用于计算一个数据集的信息熵，可直接调用
#也可不使用，通过自己的方式计算信息增益
def calcInfoEnt(data):
    numEntres = len(data)
    labelcnt = {} #用于统计正负样本的个数
    for item in data:
        if item[-1] not in labelcnt:
            labelcnt[item[-1]] = 0
        labelcnt[item[-1]] += 1
    infoEnt = 0.0
    for item in labelcnt: #根据信息熵的公式计算信息熵
        curr_info_entr = float(labelcnt[item]) / numEntres
        infoEnt = infoEnt - curr_info_entr * log(curr_info_entr,2)
    return infoEnt
    #返回值 infoEnt 为数据集的信息熵

#给定一个数据集，用于切分一个子集，可直接用于计算某一特征的信息增益 
#也可不使用，通过自己的方式计算信息增益   
#dataSet是要划分的数据集，i 代表第i个特征的索引index
#value对应该特征的某一取值
def create_sub_dataset(dataSet, i, value): 
    res = []
    for item in dataSet:
        if item[i] == value:
            curr_data = item[:i] + item[i+1:]
            res.append(curr_data)
    return res

def calc_max_info_gain(dataSet):#计算所有特征的最大信息增益，dataSet为给定的数据集
    n = len(dataSet[0])-1  # n 是特征的数量，-1 的原因是最后一列是分类标签
    total_entropy = calcInfoEnt(dataSet)#整体数据集的信息熵
    max_info_gain = [0,0] #返回值初始化
    #code start here
    for i in range(n):
        f = [x[i] for x in dataSet]
        c = Counter(f)
        te = 0
        for k, v in c.items():
            td = create_sub_dataset(dataSet, i, k)
            e = calcInfoEnt(td)
            te = te + v/len(dataSet) *e
        gain = total_entropy - te
        if gain > max_info_gain[1]:
            max_info_gain[0] = i
            max_info_gain[1] = gain
    
    #code end here
    return max_info_gain
if __name__ == '__main__':
    info_res = calc_max_info_gain(dataSet)
    print("信息增益最大的特征索引为：{0},对应的信息增益为{1}".format(info_res[0],info_res[1]))

详情