200字范文,内容丰富有趣,生活中的好帮手!
200字范文 > 周志华《机器学习》习题4.4——python实现基于信息熵进行划分选择的决策树算法

周志华《机器学习》习题4.4——python实现基于信息熵进行划分选择的决策树算法

时间:2020-10-23 23:00:54

相关推荐

周志华《机器学习》习题4.4——python实现基于信息熵进行划分选择的决策树算法

1.题目

试编程实现基于信息熵进行话饭选择的决策树算法,并为表4.3中数据生成一棵决策树。

表4.3如下:

另外再附个txt版的,下次可以复制粘贴:

青绿,蜷缩,浊响,清晰,凹陷,硬滑,0.697,0.460,是

乌黑,蜷缩,沉闷,清晰,凹陷,硬滑,0.774,0.376,是

乌黑,蜷缩,浊响,清晰,凹陷,硬滑,0.634,0.264,是

青绿,蜷缩,沉闷,清晰,凹陷,硬滑,0.608,0.318,是

浅白,蜷缩,浊响,清晰,凹陷,硬滑,0.556,0.215,是

青绿,稍蜷,浊响,清晰,稍凹,软粘,0.403,0.237,是

乌黑,稍蜷,浊响,稍糊,稍凹,软粘,0.481,0.149,是

乌黑,稍蜷,浊响,清晰,稍凹,硬滑,0.437,0.211,是

乌黑,稍蜷,沉闷,稍糊,稍凹,硬滑,0.666,0.091,否

青绿,硬挺,清脆,清晰,平坦,软粘,0.243,0.267,否

浅白,硬挺,清脆,模糊,平坦,硬滑,0.245,0.057,否

浅白,蜷缩,浊响,模糊,平坦,软粘,0.343,0.099,否

青绿,稍蜷,浊响,稍糊,凹陷,硬滑,0.639,0.161,否

浅白,稍蜷,沉闷,稍糊,凹陷,硬滑,0.657,0.198,否

乌黑,稍蜷,浊响,清晰,稍凹,软粘,0.360,0.370,否

浅白,蜷缩,浊响,模糊,平坦,硬滑,0.593,0.042,否

青绿,蜷缩,沉闷,稍糊,稍凹,硬滑,0.719,0.103,否

2.代码

先定义节点类,这里设计的每个节点包含三个属性:

a: 表示当前用于划分数据集的属性

result: 若当前节点为叶节点,result存储类别

nodes: 为当前节点的子节点列表,列表元素格式为(flag, v, node),flag可以为0、1、2三种值,0和1表示当前用于划分选择的属性是连续值,其中flag为0表示当前元素的node的a属性都小于v,同理,flag为1表示当前元素的node的a属性都大于v,当flag为2,则表示划分选择的属性是离散值,表示当前元素node的a属性等于v。

画图说明比较直观,比如,如果根节点按照“纹理”这个属性划分西瓜,则跟节点的存储结构的是:

import numpy as npimport matplotlib.pyplot as pltclass Node:def __init__(self, a, result, nodes:list):self.a = aself.result = resultself.nodes = nodesdef __init__(self):self.a = Noneself.result = Noneself.nodes = []def is_leaf(self):if len(self.nodes) == 0 or self.nodes == None:return Trueelse:return Falsedef __str__(self):return "划分属性:" + str(self.a) + ' ' + "划分值:" + ','.join([str(vi[1]) for vi in self.nodes]) + ' ' + "结果:" + str(self.result)

读数据函数,这里直接将汉字直接作为x中的值了:

def read_data(dir):xigua = []with open(dir, "r+") as f:for line in f.readlines():xigua.append(line.split(','))x = []y = []for i in range(len(xigua)):x.append(xigua[i][:8])x[i][6] = float(x[i][6])x[i][7] = float(x[i][7])if '是' in xigua[i][8]:y.append(1)else:y.append(0)return x, y

然后是决策树生成代码,一个节点有三种情况会导致划分结束,从而变成叶子节点:

1.数据集全部为一类,不用划分

2.数据集属性全部相同(但不是一类),无法划分,并且划分结果类别是父节点中类别较多的类

3.数据集为空,同样,划分结果类别是父节点中类别较多的类

def tree_generate(x:np.array, y:np.array, A:set):node = Node()if is_one_category(y):node.result = y[0]return nodeelif len(A) == 0 or is_all_same(x):node.result = find_most_category(y)return node# 寻找最佳划分属性,同时返回划分结果best_a, div_result = find_best_a(x, y, A)A1 = A.copy()A1.remove(best_a)node.a = best_afor di in div_result:flag = di[0]v = di[1]dv_x = di[2]dv_y = di[3]new_node = tree_generate(dv_x, dv_y, A1)if len(dv_x) == 0:new_node.is_leaf = Truenew_node.result = find_most_category(y)else:node.nodes.append((flag, v, new_node))return node

然后是寻找最佳划分属性代码,通过找最大的信息增益,然后取对应的属性作为划分属性。另外,因为在计算信息增益的过程中会把数据划分好,所以这里直接就把计算过程划分好的数据保留到best_div_result中了,外层函数就无需再次划分数据了。

def find_best_a(x, y, A):max_gain = 0best_div_result = []for ai in A:t_gain, div_result = gain(x, y, ai) if t_gain > max_gain:best_div_result = div_resultmax_gain = t_gainbest_a = aireturn best_a, best_div_result

然后是计算信息增益的代码,这里首先有个判断,用来分开处理属性是离散值和连续值的情况。

信息增益公式:

def gain(x, y, a):sum_x = len(x)possible_value = set()possible_value_f = []final_div_result = []if type(x[0][a]) == float:sort(x, y, a)for i in range(len(x)-1):possible_value_f.append((x[i][a] + x[i+1][a])/2)max_gain = 0for v in possible_value_f:y_small = []x_small = []y_big = []x_big = []for i in range(len(x)):if x[i][a] < v:x_small.append(x[i])y_small.append(y[i])else:x_big.append(x[i])y_big.append(y[i])t_gain = ent(y) - len(y_small)/sum_x * ent(y_small) - len(y_big)/sum_x * ent(y_big)if t_gain > max_gain:max_gain = t_gain# (flag, v, x, y) : flag为0表示该部分数据被分到小于v的节点上,为1表示该部分数据被分到大于v的节点上,为2表示等于vfinal_div_result = [(0, v, x_small, y_small), (1, v, x_big, y_big)]return max_gain, final_div_resultelse:for xi in x:possible_value.add(xi[a])result = ent(y)for v in possible_value:dv_num = 0dv_x = []dv_y = []for i in range(len(x)):if x[i][a] == v:dv_num += 1dv_y.append(y[i])dv_x.append(x[i])final_div_result.append((2, v, dv_x, dv_y))result -= dv_num/sum_x * ent(dv_y)return result, final_div_result

冒泡排序,因为对于属性是连续值的情况需要取(数据个数-1)个中位数,所以需要先排序每条数据。

def sort(x, y, a):for i in range(len(x)-1):for j in range(len(x)-i-1):if x[j][a] > x[j+1][a]:t = x[j]x[j] = x[j+1]x[j+1] = tt = y[j]y[j] = y[j+1]y[j+1] = t

计算节点信息熵的函数,公式:

def ent(y):y_set = set()for yi in y:y_set.add(yi)result = 0sum_y = len(y)for k in y_set:dk_num = 0for yi in y:if yi == k:dk_num += 1result -= (dk_num/sum_y)*np.math.log2(dk_num/sum_y)return result

其他函数:

# 寻找数据中比较多的类别def find_most_category(y):num = {}for yi in y:if num.get(yi) == None:num[yi] = 1else:num[yi] = num[yi] + 1result_num = 0for k in num.keys():if num[k] > result_num:result_num = num[k]result = kreturn result# 判断每条数据是否属性值全部相同def is_all_same(x):for i in range(len(x)):if np.any(x[i] != x[0]):return Falsereturn True# 数据集是否全部属于一个类别def is_one_category(y):c = y[0]for i in range(len(y)):if y[i] != c:return Falsereturn True# 对生成的决策树进行展示(先序遍历)def show_tree(node:Node, d):print("第",d,"层:")print(node)for nodei in node.nodes:show_tree(nodei[2], d+1)

主函数:

if __name__ == "__main__":x, y = read_data("./xigua.txt")A = list(range(len(x[0])))root = tree_generate(x, y, A)show_tree(root, 1)

3.运行结果

这里没有写画出树的代码,就直接先序遍历顺序打印出来了,同时打印出了节点的层数(根节点是第一层),可以手动画出图。(划分属性是一个数,对应训练集中属性下标)

根据书中对比,可以看到结果是正确的。

本内容不代表本网观点和政治立场,如有侵犯你的权益请联系我们处理。
网友评论
网友评论仅供其表达个人看法,并不表明网站立场。