解读python如何实现决策树算法
数据描述
每条数据项储存在列表中，最后一列储存结果
多条数据项形成数据集
data=[[d1,d2,d3...dn,result], [d1,d2,d3...dn,result], . . [d1,d2,d3...dn,result]]
决策树数据结构
classDecisionNode: '''决策树节点 ''' def__init__(self,col=-1,value=None,results=None,tb=None,fb=None): '''初始化决策树节点 args： col--按数据集的col列划分数据集 value--以value作为划分col列的参照 result--只有叶子节点有，代表最终划分出的子数据集结果统计信息。｛‘结果'：结果出现次数｝ rb,fb--代表左右子树 ''' self.col=col self.value=value self.results=results self.tb=tb self.fb=fb
决策树分类的最终结果是将数据项划分出了若干子集，其中每个子集的结果都一样，所以这里采用｛‘结果'：结果出现次数｝的方式表达每个子集
defpideset(rows,column,value):
'''依据数据集rows的column列的值，判断其与参考值value的关系对数据集进行拆分
返回两个数据集
'''
split_function=None
#value是数值类型
ifisinstance(value,int)orisinstance(value,float):
#定义lambda函数当row[column]>=value时返回true
split_function=lambdarow:row[column]>=value
#value是字符类型
else:
#定义lambda函数当row[column]==value时返回true
split_function=lambdarow:row[column]==value
#将数据集拆分成两个
set1=[rowforrowinrowsifsplit_function(row)]
set2=[rowforrowinrowsifnotsplit_function(row)]
#返回两个数据集
return(set1,set2)
defuniquecounts(rows):
'''计算数据集rows中有几种最终结果，计算结果出现次数，返回一个字典
'''
results={}
forrowinrows:
r=row[len(row)-1]
ifrnotinresults:results[r]=0
results[r]+=1
returnresults
defginiimpurity(rows):
'''返回rows数据集的基尼不纯度
'''
total=len(rows)
counts=uniquecounts(rows)
imp=0
fork1incounts:
p1=float(counts[k1])/total
fork2incounts:
ifk1==k2:continue
p2=float(counts[k2])/total
imp+=p1*p2
returnimp
defentropy(rows):
'''返回rows数据集的熵
'''
frommathimportlog
log2=lambdax:log(x)/log(2)
results=uniquecounts(rows)
ent=0.0
forrinresults.keys():
p=float(results[r])/len(rows)
ent=ent-p*log2(p)
returnent
defbuild_tree(rows,scoref=entropy):
'''构造决策树
'''
iflen(rows)==0:returnDecisionNode()
current_score=scoref(rows)
#最佳信息增益
best_gain=0.0
#
best_criteria=None
#最佳划分
best_sets=None
column_count=len(rows[0])-1
#遍历数据集的列，确定分割顺序
forcolinrange(0,column_count):
column_values={}
#构造字典
forrowinrows:
column_values[row[col]]=1
forvalueincolumn_values.keys():
(set1,set2)=pideset(rows,col,value)
p=float(len(set1))/len(rows)
#计算信息增益
gain=current_score-p*scoref(set1)-(1-p)*scoref(set2)
ifgain>best_gainandlen(set1)>0andlen(set2)>0:
best_gain=gain
best_criteria=(col,value)
best_sets=(set1,set2)
#如果划分的两个数据集熵小于原数据集，进一步划分它们
ifbest_gain>0:
trueBranch=build_tree(best_sets[0])
falseBranch=build_tree(best_sets[1])
returnDecisionNode(col=best_criteria[0],value=best_criteria[1],
tb=trueBranch,fb=falseBranch)
#如果划分的两个数据集熵不小于原数据集，停止划分
else:
returnDecisionNode(results=uniquecounts(rows))
defprint_tree(tree,indent=''):
iftree.results!=None:
print(str(tree.results))
else:
print(str(tree.col)+':'+str(tree.value)+'?')
print(indent+'T->',end='')
print_tree(tree.tb,indent+'')
print(indent+'F->',end='')
print_tree(tree.fb,indent+'')
defgetwidth(tree):
iftree.tb==Noneandtree.fb==None:return1
returngetwidth(tree.tb)+getwidth(tree.fb)
defgetdepth(tree):
iftree.tb==Noneandtree.fb==None:return0
returnmax(getdepth(tree.tb),getdepth(tree.fb))+1
defdrawtree(tree,jpeg='tree.jpg'):
w=getwidth(tree)*100
h=getdepth(tree)*100+120
img=Image.new('RGB',(w,h),(255,255,255))
draw=ImageDraw.Draw(img)
drawnode(draw,tree,w/2,20)
img.save(jpeg,'JPEG')
defdrawnode(draw,tree,x,y):
iftree.results==None:
#Getthewidthofeachbranch
w1=getwidth(tree.fb)*100
w2=getwidth(tree.tb)*100
#Determinethetotalspacerequiredbythisnode
left=x-(w1+w2)/2
right=x+(w1+w2)/2
#Drawtheconditionstring
draw.text((x-20,y-10),str(tree.col)+':'+str(tree.value),(0,0,0))
#Drawlinkstothebranches
draw.line((x,y,left+w1/2,y+100),fill=(255,0,0))
draw.line((x,y,right-w2/2,y+100),fill=(255,0,0))
#Drawthebranchnodes
drawnode(draw,tree.fb,left+w1/2,y+100)
drawnode(draw,tree.tb,right-w2/2,y+100)
else:
txt='\n'.join(['%s:%d'%vforvintree.results.items()])
draw.text((x-20,y),txt,(0,0,0))
对测试数据进行分类（附带处理缺失数据）
defmdclassify(observation,tree):
'''对缺失数据进行分类
args：
observation--发生信息缺失的数据项
tree--训练完成的决策树
返回代表该分类的结果字典
'''
#判断数据是否到达叶节点
iftree.results!=None:
#已经到达叶节点，返回结果result
returntree.results
else:
#对数据项的col列进行分析
v=observation[tree.col]
#若col列数据缺失
ifv==None:
#对tree的左右子树分别使用mdclassify，tr是左子树得到的结果字典，fr是右子树得到的结果字典
tr,fr=mdclassify(observation,tree.tb),mdclassify(observation,tree.fb)
#分别以结果占总数比例计算得到左右子树的权重
tcount=sum(tr.values())
fcount=sum(fr.values())
tw=float(tcount)/(tcount+fcount)
fw=float(fcount)/(tcount+fcount)
result={}
#计算左右子树的加权平均
fork,vintr.items():
result[k]=v*tw
fork,vinfr.items():
#fr的结果k有可能并不在tr中，在result中初始化k
ifknotinresult:
result[k]=0
#fr的结果累加到result中
result[k]+=v*fw
returnresult
#col列没有缺失，继续沿决策树分类
else:
ifisinstance(v,int)orisinstance(v,float):
ifv>=tree.value:branch=tree.tb
else:branch=tree.fb
else:
ifv==tree.value:branch=tree.tb
else:branch=tree.fb
returnmdclassify(observation,branch)
tree=build_tree(my_data)
print(mdclassify(['google',None,'yes',None],tree))
print(mdclassify(['google','France',None,None],tree))
决策树剪枝
defprune(tree,mingain): '''对决策树进行剪枝 args： tree--决策树 mingain--最小信息增益 返回 ''' #修剪非叶节点 iftree.tb.results==None: prune(tree.tb,mingain) iftree.fb.results==None: prune(tree.fb,mingain) #合并两个叶子节点 iftree.tb.results!=Noneandtree.fb.results!=None: tb,fb=[],[] forv,cintree.tb.results.items(): tb+=[[v]]*c forv,cintree.fb.results.items(): fb+=[[v]]*c #计算熵减少情况 delta=entropy(tb+fb)-(entropy(tb)+entropy(fb)/2) #熵的增加量小于mingain，可以合并分支 ifdelta