机器学习(周志华西瓜书) 参考答案 总目录
机器学习(周志华) 参考答案 第四章 决策树
3.试编程实现基于信息熵进行划分选择的决策树算法，并为表4.3中数据生成一棵决策树。
最近在学着用python，所以用py重写了以前的决策树代码，在写的过程中还是发现matlab在矩阵操作上要方便很多。
这次的代码为了更好的适用性直接用原文本作为输入，在这里规定如果样本的某属性值是数字则认定为连续型，其他认为是离散型。
输入的第一行是每个属性的标签，第二行开始是每本个样本具体的属性值，每个属性值由’,’隔开。
在函数传入时有输入是否有序号，用
决策树的属性选择使用了信息增益，没实现其他方法
代码与输入压缩包
输入示例
编号,色泽,根蒂,敲声,纹理,脐部,触感,密度,含糖率,好坏
1,青绿,蜷缩,浊响,清晰,凹陷,硬滑,0.697,0.46,好瓜
2,乌黑,蜷缩,沉闷,清晰,凹陷,硬滑,0.744,0.376,好瓜
3,乌黑,蜷缩,浊响,清晰,凹陷,硬滑,0.634,0.264,好瓜
4,青绿,蜷缩,沉闷,清晰,凹陷,硬滑,0.608,0.318,好瓜
5,浅白,蜷缩,浊响,清晰,凹陷,硬滑,0.556,0.215,好瓜
6,青绿,稍蜷,浊响,清晰,稍凹,软粘,0.403,0.237,好瓜
7,乌黑,稍蜷,浊响,稍糊,稍凹,软粘,0.481,0.149,好瓜
8,乌黑,稍蜷,浊响,清晰,稍凹,硬滑,0.437,0.211,好瓜
9,乌黑,稍蜷,沉闷,稍糊,稍凹,硬滑,0.666,0.091,坏瓜
10,青绿,硬挺,清脆,清晰,平坦,软粘,0.243,0.267,坏瓜
11,浅白,硬挺,清脆,模糊,平坦,硬滑,0.245,0.057,坏瓜
12,浅白,蜷缩,浊响,模糊,平坦,软粘,0.343,0.099,坏瓜
13,青绿,稍蜷,浊响,稍糊,凹陷,硬滑,0.639,0.161,坏瓜
14,浅白,稍蜷,沉闷,稍糊,凹陷,硬滑,0.657,0.198,坏瓜
15,乌黑,稍蜷,浊响,清晰,稍凹,软粘,0.36,0.37,坏瓜
16,浅白,蜷缩,浊响,模糊,平坦,硬滑,0.593,0.042,坏瓜
17,青绿,蜷缩,沉闷,稍糊,稍凹,硬滑,0.719,0.103,坏瓜
决策树输出树的数组结构，节点按树的先根遍历排序，每个节点4个属性值，依次为
- 父节点的index，规定根节点该位置的index指向自己
- 如果节点是叶节点，记录分类；如果是非叶节点，记录当前位置最佳的划分属性标签
- 记录所有的非根节点连接父节点的具体属性值，没有则为空
- 如果该属性是连续属性，则记录阈值，没有则为空。
决策树输出示例
[[0, '纹理', [], []],
[0, '密度', '清晰', []],
[1, '坏瓜', '小于', 0.3815],
[1, '好瓜', '大于', 0.3815],
[0, '触感', '稍糊', []],
[4, '坏瓜', '硬滑', []],
[4, '好瓜', '软粘', []],
[0, '坏瓜', '模糊', []]]然后设计了一个m叉树的绘制算法，并改造成决策树的绘制算法(最好属性的标签在2个字，并没有去根据属性标签的长度动态画方框)，绘图工具使用的是matplotlib。
绘制方法采用层次遍历，自底向上绘制节点，并要求：
- 所有节点与线段之间没有重合
- 每个节点有个最小距离限制
- 如果是非叶节点，则它的位置在它子节点正中间
- 同一层的节点在同一水平线上(这条matlab画的太蛋疼)
生成的树与决策树示例
通过西瓜数据集3得到的决策树树形
通过西瓜数据集3得到的决策树
通过西瓜数据集2得到的决策树
这里画树没去注意树的宽度，可以进一步美化，将相同父节点的节点按子节点顺序排放，让子节点少的节点更靠外。不过没有去实现–
决策树的递归算法与属性选择算法书上讲的很详细，这里不再重复，具体内容看代码注释
# -*- coding: utf-8 -*-
"""
Created on Mon Jan 16 12:01:08 2017
@author: icefire
"""
from dtreeplot import dtreeplot
import math
#属性类
class property:
def __init__(self,idnum,attribute):
self.is_continuity=False #连续型属性标记
self.attribute=attribute #属性标签
self.subattributes=[] #属性子标签
self.id=idnum #属性排在输入文本的第几位
self.index={} #属性子标签的索引值
#决策树生成类
class dtree():
'''
构造函数
filename:输入文件名
haveID:输入是否带序号
property_set：为空则计算全部属性，否则记录set中的属性
'''
def __init__(self,filename,haveID,property_set):
self.data=[]
self.data_property=[]
#读入数据
self.__dataread(filename,haveID)
#判断选择的属性集合
if len(property_set)>0:
tmp_data_property=[]
for i in property_set:
tmp_data_property.append(self.data_property[i])
tmp_data_property.append(self.data_property[-1])
else:
tmp_data_property=self.data_property
#决策树树形数组结构
self.treelink=[]
#决策树主递归
self.__TreeGenerate(range(0,len(self.data[-1])),tmp_data_property,0,[],[])
#决策树绘制
dtreeplot(self.treelink,6,1,-6)
'''
决策树主递归
data_set:当前样本集合
property_set：当前熟悉集合
father:父节点索引值
attribute:父节点连接当前节点的子属性值
threshold:如果是连续参数就是阈值，否则为空
'''
def __TreeGenerate(self,data_set,property_set,father,attribute,threshold):
#新增一个节点
self.treelink.append([])
#新节点的位置
curnode=len(self.treelink)-1
#记录新节点的父亲节点
self.treelink[curnode].append(father)
#结束条件1：所有样本同一分类
current_data_class=self.__count(data_set,property_set[-1])
if(len(current_data_class)==1):
self.treelink[curnode].append(self.data[-1][data_set[0]])
self.treelink[curnode].append(attribute)
self.treelink[curnode].append(threshold)
return
#结束条件2：所有样本相同属性，选择分类数多的一类作为分类
if all(len(self.__count(data_set,property_set[i]))==1 for i in range(0,len(property_set)-1)):
max_count=-1;
for dataclass in property_set[-1].subattributes:
if current_data_class[dataclass]>max_count:
max_attribute=dataclass
max_count=current_data_class[dataclass]
self.treelink[curnode].append(max_attribute)
self.treelink[curnode].append(attribute)
self.treelink[curnode].append(threshold)
return
#信息增益选择最优属性与阈值
prop,threshold = self.__entropy_paraselect(data_set,property_set)
#记录当前节点的最优属性标签与父节点连接当前节点的子属性值
self.treelink[curnode].append(prop.attribute)
self.treelink[curnode].append(attribute)
#从属性集合中移除当前属性
property_set.remove(prop)
#判断是否是连续属性
if(prop.is_continuity):
#连续属性分为2子属性，大于和小于
tmp_data_set=[[],[]]
for i in data_set:
tmp_data_set[self.data[prop.id][i]>threshold].append(i)
for i in [0,1]:
self.__TreeGenerate(tmp_data_set[i],property_set[:],curnode,prop.subattributes[i],threshold)
else:
#离散属性有多子属性
tmp_data_set=[[] for i in range(0,len(prop.subattributes))]
for i in data_set:
tmp_data_set[prop.index[self.data[prop.id][i]]].append(i)
for i in range(0,len(prop.subattributes)):
if len(tmp_data_set[i])>0:
self.__TreeGenerate(tmp_data_set[i],property_set[:],curnode,prop.subattributes[i],[])
else:
#如果某一个子属性不存没有对应的样本，则选择父节点分类更多的一项作为分类
self.treelink.append([])
max_count=-1;
tnode=len(self.treelink)-1
for dataclass in property_set[-1].subattributes:
if current_data_class[dataclass]>max_count:
max_attribute=dataclass
max_count=current_data_class[dataclass]
self.treelink[tnode].append(curnode)
self.treelink[tnode].append(max_attribute)
self.treelink[tnode].append(prop.subattributes[i])
self.treelink[tnode].append(threshold)
#为没有4个值得节点用空列表补齐4个值
for i in range(len(self.treelink[curnode]),4):
self.treelink[curnode].append([])
'''
信息增益算则最佳属性
data_set:当前样本集合
property_set:当前属性集合
'''
def __entropy_paraselect(self,data_set,property_set):
#分离散和连续型分别计算信息增益，选择最大的一个
max_ent=-10000
for i in range(0,len(property_set)-1):
prop_id=property_set[i].id
if(property_set[i].is_continuity):
tmax_ent=-10000
xlist=self.data[prop_id][:]
xlist.sort()
#连续型求出相邻大小值的平局值作为待选的最佳阈值
for j in range(0,len(xlist)-1):
xlist[j]=(xlist[j+1]+xlist[j])/2
for j in range(0,len(xlist)-1):
if(i>0 and xlist[j]==xlist[j-1]):
continue
cur_ent = 0
nums=[[0,0],[0,0]]
for k in data_set:
nums[self.data[prop_id][k]>xlist[j]][property_set[-1].index[self.data[-1][k]]]+=1
for k in [0,1]:
subattribute_sum=nums[k][0]+nums[k][1]
if(subattribute_sum > 0):
p=nums[k][0]/subattribute_sum
cur_ent +=(p*math.log(p+0.00001,2)+(1-p)*math.log(1-p+0.00001,2))*subattribute_sum/len(data_set)
if(cur_ent>tmax_ent):
tmax_ent = cur_ent
tmp_threshold = xlist[j]
if(tmax_ent > max_ent):
max_ent=tmax_ent;
bestprop = property_set[i];
best_threshold = tmp_threshold;
else:
#直接统计并计算
cur_ent=0
nums=[[0,0] for i in range(0,len(property_set[i].subattributes))]
for j in data_set:
nums[property_set[i].index[self.data[prop_id][j]]][property_set[-1].index[self.data[-1][j]]]+=1
for j in range(0,len(property_set[i].subattributes)):
subattribute_sum=nums[j][0]+nums[j][1]
if(subattribute_sum>0):
p=nums[j][0]/subattribute_sum
cur_ent += (p*math.log(p+0.00001,2)+(1-p)*math.log(1-p+0.00001,2))*subattribute_sum/len(data_set)
if(cur_ent > max_ent):
max_ent=cur_ent;
bestprop = property_set[i];
best_threshold = [];
return bestprop,best_threshold
'''
计算当前样本在某个属性下的分类情况
'''
def __count(self,data_set,prop):
out={}
rowdata=self.data[prop.id]
for i in data_set:
if rowdata[i] in out:
out[rowdata[i]]+=1
else:
out[rowdata[i]]=1;
return out
'''
输入数据处理
'''
def __dataread(self,filename,haveID):
file = open(filename, 'r')
linelen=0
first=1;
while 1:
#按行读
line = file.readline()
if not line:
break
line=line.strip('\n')
rowdata = line.split(',')
#如果有编号就去掉第一列
if haveID:
del rowdata[0]
if(linelen==0):
#处理第一行，初始化属性类对象，记录属性的标签
for i in range(0,len(rowdata)):
self.data.append([])
self.data_property.append(property(i,rowdata[i]))
self.data_property[i].attribute=rowdata[i]
linelen=len(rowdata)
elif(linelen==len(rowdata)):
if(first==1):
#处理第二行，记录属性是否是连续型和子属性
for i in range(0,len(rowdata)):
if(isnumeric(rowdata[i])):
self.data_property[i].is_continuity=True
self.data[i].append(float(rowdata[i]))
self.data_property[i].subattributes.append("小于")
self.data_property[i].index["小于"]=0
self.data_property[i].subattributes.append("大于")
self.data_property[i].index["大于"]=1
else:
self.data[i].append(rowdata[i])
else:
#处理后面行，记录子属性
for i in range(0,len(rowdata)):
if(self.data_property[i].is_continuity):
self.data[i].append(float(rowdata[i]))
else:
self.data[i].append(rowdata[i])
if rowdata[i] not in self.data_property[i].subattributes:
self.data_property[i].subattributes.append(rowdata[i])
self.data_property[i].index[rowdata[i]]=len(self.data_property[i].subattributes)-1
first=0
else:
continue
'''
判断是否是数字
'''
def isnumeric(s):
return all(c in "0123456789.-" for c in s)
filename="西瓜3.data"
property_set=range(0,6)
link=dtree(filename,True,property_set)
下面是决策树的绘制类，步骤是：
- 处理决策树生成的数组结构，生成树形结构与层次结构
- 根据层次结构从下往上绘制
- 对于每层，首先求非叶叶节点的初始位置，值为它最边缘两个子节点中间；然后计算非叶节点
- 对于每层第一个非叶节点前和最后一个非叶节点后的节点，直接用最小距离绘制。
- 对于两个非叶节点中间的叶节点，如果两个非叶节点中间足够大，则中间的叶节点均匀分布，否则按最小距离绘制，并记录非叶节点的新位置，计算出相对于初始位置的偏移。
代码如下：
# -*- coding: utf-8 -*-
"""
Created on Sun Jan 15 10:19:20 2017
@author: icefire
"""
import numpy as np
from matplotlib import pyplot as plt
'''
树的节点类
data:树的数组结构的一项，4值
height:节点的高
'''
class treenode:
def __init__(self,data,height):
self.father=data[0] #父节点
self.children=[] #子节点列表
self.data=data[1] #节点标签
self.height=height
self.pos=0; #节点计算时最终位置，计算时只保存相对位置
self.offset=0; #节点最终位置与初始位置的相对值
self.data_to_father=data[2] #链接父节点的属性值
#如果有阈值，则加入阈值
if type(data[3])!=list:
self.data_to_father=self.data_to_father+str(data[3]);
'''
树的绘制类
link:树的数组结构
minspace:节点间的距离
r:节点的绘制半径
lh:层高
'''
class dtreeplot:
def __init__(self,link,minspace,r,lh):
s=len(link)
#所有节点的列表，第一项为根节点
treenodelist=[]
#节点的层次结构
treelevel=[]
#处理树的数组结构
for i in range(0,s):
#根节点的index与其父节点的index相同
if link[i][0]==i:
treenodelist.append(treenode(link[i],0))
else:
treenodelist.append(treenode(link[i],treenodelist[link[i][0]].height+1))
treenodelist[link[i][0]].children.append(treenodelist[i]);
treenodelist[i].father=treenodelist[link[i][0]];
#如果有新一层的节点则新建一层
if len(treelevel)==treenodelist[i].height:
treelevel.append([])
treelevel[treenodelist[i].height].append(treenodelist[i])
#控制绘制图像的坐标轴
self.right=0
self.left=0
#反转层次，从底往上画
treelevel.reverse()
#计算每个节点的位置
self.__calpos(treelevel,minspace)
#绘制树形
self.__drawtree(treenodelist[0] ,r,lh,0)
plt.xlim(xmin=self.left,xmax=self.right+minspace)
plt.ylim(ymin=len(treelevel)*lh+lh/2,ymax=lh/2)
plt.show()
'''
逐一绘制计算每个节点的位置
nodes:节点集合
l,r:左右区间
start:当前层的初始绘制位置
minspace:使用的最小间距
'''
def __calonebyone(self,nodes,l,r,start,minspace):
for i in range(l,r):
nodes[i].pos=max(nodes[i].pos,start)
start=nodes[i].pos+minspace;
return start;
'''
计算每个节点的位置与相对偏移
treelevel：树的层次结构
minspace:使用的最小间距
'''
def __calpos(self,treelevel,minspace):
#按层次画
for nodes in treelevel:
#记录非叶节点
noleaf=[]
num=0;
for node in nodes:
if len(node.children)>0:
noleaf.append(num)
node.pos=(node.children[0].pos+node.children[-1].pos)/2
num=num+1
start=minspace
#如果全是非叶节点，直接绘制
if(len(noleaf))==0:
self.__calonebyone(nodes,0,len(nodes),0,minspace)
else:
start=nodes[noleaf[0]].pos-noleaf[0]*minspace
self.left=min(self.left,start-minspace)
start=self.__calonebyone(nodes,0,noleaf[0],start,minspace)
for i in range(0,len(noleaf)):
nodes[noleaf[i]].offset=max(nodes[noleaf[i]].pos,start)-nodes[noleaf[i]].pos
nodes[noleaf[i]].pos=max(nodes[noleaf[i]].pos,start)
if(i<len(noleaf)-1):
#计算两个非叶节点中间的间隔，如果足够大就均匀绘制
dis=(nodes[noleaf[i+1]].pos-nodes[noleaf[i]].pos)/(noleaf[i+1]-noleaf[i])
start=nodes[noleaf[i]].pos+max(minspace,dis)
start=self.__calonebyone(nodes,noleaf[i]+1,noleaf[i+1],start,max(minspace,dis))
else:
start=nodes[noleaf[i]].pos+minspace
start=self.__calonebyone(nodes,noleaf[i]+1,len(nodes),start,minspace)
'''
采用先根遍历绘制树
treenode:当前遍历的节点
r:半径
lh:层高
curoffset:每层节点的累计偏移
'''
def __drawtree(self,treenode,r,lh,curoffset):
#加上当前的累计偏差得到最终位置
treenode.pos=treenode.pos+curoffset
if(treenode.pos>self.right):
self.right=treenode.pos
#如果是叶节点则画圈，非叶节点画方框
if(len(treenode.children)>0):
drawrect(treenode.pos,(treenode.height+1)*lh,r)
plt.text(treenode.pos, (treenode.height+1)*lh, treenode.data+'=?', color=(0,0,1),ha='center', va='center')
else:
drawcircle(treenode.pos,(treenode.height+1)*lh,r)
plt.text(treenode.pos, (treenode.height+1)*lh, treenode.data, color=(1,0,0),ha='center', va='center')
num=0;
#先根遍历
for node in treenode.children:
self.__drawtree(node,r,lh,curoffset+treenode.offset)
#绘制父节点到子节点的连线
num=num+1
px=(treenode.pos-r)+2*r*num/(len(treenode.children)+1)
py=(treenode.height+1)*lh-r-0.02
#按到圆到方框分开画
if(len(node.children)>0):
px1=node.pos
py1=(node.height+1)*lh+r
off=np.array([px-px1,py-py1])
off=off*r/np.linalg.norm(off)
else:
off=np.array([px-node.pos,-lh+1])
off=off*r/np.linalg.norm(off)
px1=node.pos+off[0]
py1=(node.height+1)*lh+off[1]
#计算父节点与子节点连线的方向与角度
plt.plot([px,px1],[py,py1],color=(0,0,0))
pmx=(px1+px)/2-(1-2*(px<px1))*0.4
pmy=(py1+py)/2+0.4
arc=np.arctan(off[1]/(off[0]+0.0000001))
#绘制文本以及旋转
plt.text(pmx,pmy, node.data_to_father, color=(1,0,1),ha='center', va='center', rotation=arc/np.pi*180)
'''
画圆
'''
def drawcircle(x,y,r):
theta = np.arange(0, 2 * np.pi, 2 * np.pi / 1000)
theta = np.append(theta, [2 * np.pi])
x1=[]
y1=[]
for tha in theta:
x1.append(x + r * np.cos(tha))
y1.append(y + r * np.sin(tha))
plt.plot(x1, y1,color=(0,0,0))
'''
画矩形
'''
def drawrect(x,y,r):
x1=[x-r,x+r,x+r,x-r,x-r]
y1=[y-r,y-r,y+r,y+r,y-r]
plt.plot(x1, y1,color=(0,0,0))