本文實例為大家分享了基于信息增益的決策樹歸納的Python實現代碼，供大家參考，具體內容如下

# -*- coding: utf-8 -*-import numpy as npimport matplotlib.mlab as mlabimport matplotlib.pyplot as pltfrom copy import copy #加載訓練數據#文件格式：屬性標號，是否連續【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_idtrainning_data_file_dest = 'F://bayes_categorize//trainning_data.dat'trainning_data_file = open(trainning_data_file_dest) #文件格式：class_id,class_descclass_desc_file_dest = 'F://bayes_categorize//class_desc.dat'class_desc_file = open(class_desc_file_dest)  root_attr_dict = {}for line in attribute_file :  line = line.strip()  fld_list = line.split(',')  root_attr_dict[int(fld_list[0])] = tuple(fld_list[1:]) class_dict = {}for line in class_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 = {}for line in trainning_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])    if c_id not in class_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 = {}for c_id in class_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 = {}for line in data_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保存分類結果類標號元素三是dict key對于1來說是某個的離散值 對于23來說只有12兩種 對于2來說1代表小于等于分裂點對于3來說1代表屬于判別集合'''   #對于一個成員列表，計算其熵#公式為 Info_D = - sum(pi * log2 (pi)) pi為一個元素屬于Ci的概率，用|Ci|/|D|計算 ，對所有分類求和def get_entropy( member_list ) :  #成員總數  mem_cnt = len(member_list)  #首先找出member中所包含的分類  class_dict = {}  for mem_id in member_list :    c_id = trainning_data_dict[mem_id][3]    if c_id not in class_dict :      class_dict[c_id] = set()    class_dict[c_id].add(mem_id)    tmp_sum = 0.0  for c_id in class_dict :    pi = ( len(class_dict[c_id]) + 0.0 ) / mem_cnt    tmp_sum += pi * mlab.log2(pi)  tmp_sum = -tmp_sum  return tmp_sum     def attribute_selection_method( member_list , attribute_dict ) :  #先計算原始的熵  info_D = get_entropy(member_list)    max_info_Gain = 0.0  attr_get = 0  split_point = 0.0  for attr_id in attribute_dict :    #對于每一個屬性計算劃分后的熵    #信息增益等于原始的熵減去劃分后的熵    info_D_new = 0    #如果是連續屬性    if attribute_dict[attr_id][0] == 'yes' :      #先得到memberlist中此屬性的取值序列，把序列中每一對相鄰項的中值作為劃分點計算熵      #找出其中最小的，作為此連續屬性的劃分點      value_list = []      for mem_id in member_list :        value_list.append(trainning_data_dict[mem_id][attr_id - 1])            #獲取相鄰元素的中值序列      mid_value_list = []      value_list.sort()      #print value_list      last_value = None      for value in value_list :        if value == last_value :          continue        if last_value is not None :          mid_value_list.append((last_value+value)/2)        last_value = value      #print mid_value_list      #對于中值序列做循環      #計算以此值做為劃分點的熵      #總的熵等于兩個劃分的熵乘以兩個劃分的比重      min_info = 1000000000.0      total_mens = len(member_list) + 0.0      for mid_value in mid_value_list :        #小于mid_value的mem        less_list = []        #大于        more_list = []        for tmp_mem_id in member_list :          if trainning_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)                if sum_info < min_info :          min_info = sum_info          split_point = mid_value                info_D_new = min_info    #如果是離散屬性    else :      #計算劃分后的熵      #采用循環累加的方式      attr_value_member_dict = {} #鍵為attribute value , 值為memberlist      for tmp_mem_id in member_list :        attr_value = trainning_data_dict[tmp_mem_id][attr_id - 1]        if attr_value not in attr_value_member_dict :          attr_value_member_dict[attr_value] = []        attr_value_member_dict[attr_value].append(tmp_mem_id)      #將每個離散值的熵乘以比重加到這上面      total_mens = len(member_list) + 0.0      sum_info = 0.0      for a_value in attr_value_member_dict :        sum_info += len(attr_value_member_dict[a_value])/total_mens /        * get_entropy(attr_value_member_dict[a_value])            info_D_new = sum_info        info_Gain = info_D - info_D_new    if info_Gain > max_info_Gain :      max_info_Gain = info_Gain      attr_get = attr_id    #如果是離散的  #print 'attr_get ' + str(attr_get)  if attribute_dict[attr_get][0] == 'no' :    return (1 , attr_get , split_point)  else :      return (2 , attr_get , split_point)  #第三類先不考慮 def get_decision_tree(father_node , key , member_list , attr_dict ) :  #最終的結果是新建一個結點，并且添加到father_node的sub_node_dict，對key為鍵  #檢查memberlist 如果都是同類的，則生成一個葉子結點，set里面保存類標號  class_set = set()  for mem_id in member_list :    class_set.add(trainning_data_dict[mem_id][3])  if len(class_set) == 1 :    father_node[2][key] = (0 , (1 , class_set) , {} )    return    #檢查attribute_list，如果為空，產生葉子結點，類標號為memberlist中多數元素的類標號  #如果幾個類的成員等量，則打印提示，并且全部添加到set里面  if not attr_dict :    class_cnt_dict = {}    for mem_id in member_list :      c_id = trainning_data_dict[mem_id][3]      if c_id not in class_cnt_dict :        class_cnt_dict[c_id] = 1      else :        class_cnt_dict[c_id] += 1            class_set = set()    max_cnt = 0    for c_id in class_cnt_dict :      if class_cnt_dict[c_id] > max_cnt :        max_cnt = class_cnt_dict[c_id]        class_set.clear()        class_set.add(c_id)      elif class_cnt_dict[c_id] == max_cnt :        class_set.add(c_id)        if len(class_set) > 1 :      print 'more than one class !'        father_node[2][key] = (0 , (1 , class_set ) , {} )    return    #找出最好的分區方案 ， 暫不考慮第三種劃分方法  #比較所有離散屬性和所有連續屬性的所有中值點劃分的信息增益  split_criterion = attribute_selection_method(member_list , attr_dict)  #print split_criterion  selected_plan_id = split_criterion[0]  selected_attr_id = split_criterion[1]    #如果采用的是離散屬性做為分區方案，刪除這個屬性  new_attr_dict = copy(attr_dict)  if attr_dict[selected_attr_id][0] == 'no' :    del new_attr_dict[selected_attr_id]    #建立一個結點new_node，father_node[2][key] = new_node  #然后對new node的每一個key , sub_member_list，  #調用 get_decision_tree(new_node , new_key , sub_member_list , new_attribute_dict)  #實現遞歸  ele2 = ( selected_attr_id , set() )  #如果是1 , ele2保存所有離散值  if selected_plan_id == 1 :    for mem_id in member_list :      ele2[1].add(trainning_data_dict[mem_id][selected_attr_id - 1])  #如果是2，ele2保存分裂點  elif selected_plan_id == 2 :    ele2[1].add(split_criterion[2])  #如果是3則保存判別集合，先不管  else :    print 'not completed'    pass      new_node = ( selected_plan_id , ele2 , {} )  father_node[2][key] = new_node    #生成KEY，并遞歸調用  if selected_plan_id == 1 :    #每個attr_value是一個key    attr_value_member_dict = {}    for mem_id in member_list :      attr_value = trainning_data_dict[mem_id][selected_attr_id - 1 ]      if attr_value not in attr_value_member_dict :        attr_value_member_dict[attr_value] = []      attr_value_member_dict[attr_value].append(mem_id)    for attr_value in attr_value_member_dict :      get_decision_tree(new_node , attr_value , attr_value_member_dict[attr_value] , new_attr_dict)    pass  elif selected_plan_id == 2 :    #key 只有12 , 小于等于分裂點的是1 ， 大于的是2    less_list = []    more_list = []    for mem_id in member_list :      attr_value = trainning_data_dict[mem_id][selected_attr_id - 1 ]      if attr_value <= split_criterion[2] :        less_list.append(mem_id)      else :        more_list.append(mem_id)    #if len(less_list) != 0 :    get_decision_tree(new_node , 1 , less_list , new_attr_dict)    #if len(more_list) != 0 :    get_decision_tree(new_node , 2 , more_list , new_attr_dict)    pass  #如果是3則保存判別集合，先不管  else :    print 'not completed'    pass  def get_class_sub(node , tp ) :  #  attr_id = node[1][0]  plan_id = node[0]  key = 0  if plan_id == 0 :    return node[1][1]  elif plan_id == 1 :    key = tp[attr_id - 1]  elif plan_id == 2 :    split_point = tuple(node[1][1])[0]    attr_value = tp[attr_id - 1]    if attr_value <= split_point :      key = 1    else :      key = 2  else :    print 'error'    return set()      return get_class_sub(node[2][key] , tp ) def get_class(r_node , tp) :  #tp為一組屬性值  if r_node[0] != -1 :    print 'error'    return set()    if 1 in r_node[2] :    return get_class_sub(r_node[2][1] , tp)  else :    print 'error'    return set()    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  for mem_id in data_to_classify_dict :    c_id = get_class(root_node , data_to_classify_dict[mem_id][0:3])    if tuple(c_id)[0] != data_to_classify_dict[mem_id][3] :      print tuple(c_id)[0]      print data_to_classify_dict[mem_id][3]      print 'different'      diff_cnt += 1  print diff_cnt