python实现基于信息增益的决策树归纳
本文实例为大家分享了基于信息增益的决策树归纳的Python实现代码，供大家参考，具体内容如下
#-*-coding:utf-8-*-
importnumpyasnp
importmatplotlib.mlabasmlab
importmatplotlib.pyplotasplt
fromcopyimportcopy
#加载训练数据
#文件格式：属性标号，是否连续【yes|no】，属性说明
attribute_file_dest='F:\\bayes_categorize\\attribute.dat'
attribute_file=open(attribute_file_dest)
#文件格式：rec_id,attr1_value,attr2_value,...，attrn_value,class_id
trainning_data_file_dest='F:\\bayes_categorize\\trainning_data.dat'
trainning_data_file=open(trainning_data_file_dest)
#文件格式：class_id,class_desc
class_desc_file_dest='F:\\bayes_categorize\\class_desc.dat'
class_desc_file=open(class_desc_file_dest)
root_attr_dict={}
forlineinattribute_file:
line=line.strip()
fld_list=line.split(',')
root_attr_dict[int(fld_list[0])]=tuple(fld_list[1:])
class_dict={}
forlineinclass_desc_file:
line=line.strip()
fld_list=line.split(',')
class_dict[int(fld_list[0])]=fld_list[1]
trainning_data_dict={}
class_member_set_dict={}
forlineintrainning_data_file:
line=line.strip()
fld_list=line.split(',')
rec_id=int(fld_list[0])
a1=int(fld_list[1])
a2=int(fld_list[2])
a3=float(fld_list[3])
c_id=int(fld_list[4])
ifc_idnotinclass_member_set_dict:
class_member_set_dict[c_id]=set()
class_member_set_dict[c_id].add(rec_id)
trainning_data_dict[rec_id]=(a1,a2,a3,c_id)
attribute_file.close()
class_desc_file.close()
trainning_data_file.close()
class_possibility_dict={}
forc_idinclass_member_set_dict:
class_possibility_dict[c_id]=(len(class_member_set_dict[c_id])+0.0)/len(trainning_data_dict)
#等待分类的数据
data_to_classify_file_dest='F:\\bayes_categorize\\trainning_data_new.dat'
data_to_classify_file=open(data_to_classify_file_dest)
data_to_classify_dict={}
forlineindata_to_classify_file:
line=line.strip()
fld_list=line.split(',')
rec_id=int(fld_list[0])
a1=int(fld_list[1])
a2=int(fld_list[2])
a3=float(fld_list[3])
c_id=int(fld_list[4])
data_to_classify_dict[rec_id]=(a1,a2,a3,c_id)
data_to_classify_file.close()
'''
决策树的表达
结点的需求：
1、指示出是哪一种分区一共3种一是离散穷举二是连续有分裂点三是离散有判别集合零是叶子结点
2、保存分类所需信息
3、子结点列表
每个结点用Tuple类型表示
元素一是整形，取值123分别对应两种分裂类型
元素二是集合类型对于1保存所有的离散值对于2保存分裂点对于3保存判别集合对于0保存分类结果类标号
元素三是dictkey对于1来说是某个的离散值对于23来说只有12两种对于2来说1代表小于等于分裂点
对于3来说1代表属于判别集合
'''
#对于一个成员列表，计算其熵
#公式为Info_D=-sum(pi*log2(pi))pi为一个元素属于Ci的概率，用|Ci|/|D|计算，对所有分类求和
defget_entropy(member_list):
#成员总数
mem_cnt=len(member_list)
#首先找出member中所包含的分类
class_dict={}
formem_idinmember_list:
c_id=trainning_data_dict[mem_id][3]
ifc_idnotinclass_dict:
class_dict[c_id]=set()
class_dict[c_id].add(mem_id)
tmp_sum=0.0
forc_idinclass_dict:
pi=(len(class_dict[c_id])+0.0)/mem_cnt
tmp_sum+=pi*mlab.log2(pi)
tmp_sum=-tmp_sum
returntmp_sum
defattribute_selection_method(member_list,attribute_dict):
#先计算原始的熵
info_D=get_entropy(member_list)
max_info_Gain=0.0
attr_get=0
split_point=0.0
forattr_idinattribute_dict:
#对于每一个属性计算划分后的熵
#信息增益等于原始的熵减去划分后的熵
info_D_new=0
#如果是连续属性
ifattribute_dict[attr_id][0]=='yes':
#先得到memberlist中此属性的取值序列，把序列中每一对相邻项的中值作为划分点计算熵
#找出其中最小的，作为此连续属性的划分点
value_list=[]
formem_idinmember_list:
value_list.append(trainning_data_dict[mem_id][attr_id-1])
#获取相邻元素的中值序列
mid_value_list=[]
value_list.sort()
#printvalue_list
last_value=None
forvalueinvalue_list:
ifvalue==last_value:
continue
iflast_valueisnotNone:
mid_value_list.append((last_value+value)/2)
last_value=value
#printmid_value_list
#对于中值序列做循环
#计算以此值做为划分点的熵
#总的熵等于两个划分的熵乘以两个划分的比重
min_info=1000000000.0
total_mens=len(member_list)+0.0
formid_valueinmid_value_list:
#小于mid_value的mem
less_list=[]
#大于
more_list=[]
fortmp_mem_idinmember_list:
iftrainning_data_dict[tmp_mem_id][attr_id-1]<=mid_value:
less_list.append(tmp_mem_id)
else:
more_list.append(tmp_mem_id)
sum_info=len(less_list)/total_mens*get_entropy(less_list)\
+len(more_list)/total_mens*get_entropy(more_list)
ifsum_infomax_info_Gain:
max_info_Gain=info_Gain
attr_get=attr_id
#如果是离散的
#print'attr_get'+str(attr_get)
ifattribute_dict[attr_get][0]=='no':
return(1,attr_get,split_point)
else:
return(2,attr_get,split_point)
#第三类先不考虑
defget_decision_tree(father_node,key,member_list,attr_dict):
#最终的结果是新建一个结点，并且添加到father_node的sub_node_dict，对key为键
#检查memberlist如果都是同类的，则生成一个叶子结点，set里面保存类标号
class_set=set()
formem_idinmember_list:
class_set.add(trainning_data_dict[mem_id][3])
iflen(class_set)==1:
father_node[2][key]=(0,(1,class_set),{})
return
#检查attribute_list，如果为空，产生叶子结点，类标号为memberlist中多数元素的类标号
#如果几个类的成员等量，则打印提示，并且全部添加到set里面
ifnotattr_dict:
class_cnt_dict={}
formem_idinmember_list:
c_id=trainning_data_dict[mem_id][3]
ifc_idnotinclass_cnt_dict:
class_cnt_dict[c_id]=1
else:
class_cnt_dict[c_id]+=1
class_set=set()
max_cnt=0
forc_idinclass_cnt_dict:
ifclass_cnt_dict[c_id]>max_cnt:
max_cnt=class_cnt_dict[c_id]
class_set.clear()
class_set.add(c_id)
elifclass_cnt_dict[c_id]==max_cnt:
class_set.add(c_id)
iflen(class_set)>1:
print'morethanoneclass!'
father_node[2][key]=(0,(1,class_set),{})
return
#找出最好的分区方案，暂不考虑第三种划分方法
#比较所有离散属性和所有连续属性的所有中值点划分的信息增益
split_criterion=attribute_selection_method(member_list,attr_dict)
#printsplit_criterion
selected_plan_id=split_criterion[0]
selected_attr_id=split_criterion[1]
#如果采用的是离散属性做为分区方案，删除这个属性
new_attr_dict=copy(attr_dict)
ifattr_dict[selected_attr_id][0]=='no':
delnew_attr_dict[selected_attr_id]
#建立一个结点new_node，father_node[2][key]=new_node
#然后对newnode的每一个key,sub_member_list，
#调用get_decision_tree(new_node,new_key,sub_member_list,new_attribute_dict)
#实现递归
ele2=(selected_attr_id,set())
#如果是1,ele2保存所有离散值
ifselected_plan_id==1:
formem_idinmember_list:
ele2[1].add(trainning_data_dict[mem_id][selected_attr_id-1])
#如果是2，ele2保存分裂点
elifselected_plan_id==2:
ele2[1].add(split_criterion[2])
#如果是3则保存判别集合，先不管
else:
print'notcompleted'
pass
new_node=(selected_plan_id,ele2,{})
father_node[2][key]=new_node
#生成KEY，并递归调用
ifselected_plan_id==1:
#每个attr_value是一个key
attr_value_member_dict={}
formem_idinmember_list:
attr_value=trainning_data_dict[mem_id][selected_attr_id-1]
ifattr_valuenotinattr_value_member_dict:
attr_value_member_dict[attr_value]=[]
attr_value_member_dict[attr_value].append(mem_id)
forattr_valueinattr_value_member_dict:
get_decision_tree(new_node,attr_value,attr_value_member_dict[attr_value],new_attr_dict)
pass
elifselected_plan_id==2:
#key只有12,小于等于分裂点的是1，大于的是2
less_list=[]
more_list=[]
formem_idinmember_list:
attr_value=trainning_data_dict[mem_id][selected_attr_id-1]
ifattr_value<=split_criterion[2]:
less_list.append(mem_id)
else:
more_list.append(mem_id)
#iflen(less_list)!=0:
get_decision_tree(new_node,1,less_list,new_attr_dict)
#iflen(more_list)!=0:
get_decision_tree(new_node,2,more_list,new_attr_dict)
pass
#如果是3则保存判别集合，先不管
else:
print'notcompleted'
pass
defget_class_sub(node,tp):
#
attr_id=node[1][0]
plan_id=node[0]
key=0
ifplan_id==0:
returnnode[1][1]
elifplan_id==1:
key=tp[attr_id-1]
elifplan_id==2:
split_point=tuple(node[1][1])[0]
attr_value=tp[attr_id-1]
ifattr_value<=split_point:
key=1
else:
key=2
else:
print'error'
returnset()
returnget_class_sub(node[2][key],tp)
defget_class(r_node,tp):
#tp为一组属性值
ifr_node[0]!=-1:
print'error'
returnset()
if1inr_node[2]:
returnget_class_sub(r_node[2][1],tp)
else:
print'error'
returnset()
if__name__=='__main__':
root_node=(-1,set(),{})
mem_list=trainning_data_dict.keys()
get_decision_tree(root_node,1,mem_list,root_attr_dict)
#测试分类器的准确率
diff_cnt=0
formem_idindata_to_classify_dict:
c_id=get_class(root_node,data_to_classify_dict[mem_id][0:3])
iftuple(c_id)[0]!=data_to_classify_dict[mem_id][3]:
printtuple(c_id)[0]
printdata_to_classify_dict[mem_id][3]
print'different'
diff_cnt+=1
printdiff_cnt
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持毛票票。