python实现决策树分类

上一篇博客主要介绍了决策树的原理，这篇主要介绍他的实现，代码环境python 3.4，实现的是ID3算法，首先为了后面matplotlib的绘图方便，我把原来的中文数据集变成了英文。

原始数据集：

变化后的数据集在程序代码中体现，这就不截图了

构建决策树的代码如下：

#coding :utf-8'''2017.6.25 author :Erin    function: "decesion tree" ID3   '''import numpy as npimport pandas as pdfrom math import logimport operator def load_data():  #data=np.array(data) data=[['teenager' ,'high', 'no' ,'same', 'no'],   ['teenager', 'high', 'no', 'good', 'no'],   ['middle_aged' ,'high', 'no', 'same', 'yes'],   ['old_aged', 'middle', 'no' ,'same', 'yes'],   ['old_aged', 'low', 'yes', 'same' ,'yes'],   ['old_aged', 'low', 'yes', 'good', 'no'],   ['middle_aged', 'low' ,'yes' ,'good', 'yes'],   ['teenager' ,'middle' ,'no', 'same', 'no'],   ['teenager', 'low' ,'yes' ,'same', 'yes'],   ['old_aged' ,'middle', 'yes', 'same', 'yes'],   ['teenager' ,'middle', 'yes', 'good', 'yes'],   ['middle_aged' ,'middle', 'no', 'good', 'yes'],   ['middle_aged', 'high', 'yes', 'same', 'yes'],   ['old_aged', 'middle', 'no' ,'good' ,'no']] features=['age','input','student','level'] return data,features def cal_entropy(dataSet): ''' 输入data ,表示带最后标签列的数据集 计算给定数据集总的信息熵 {'是': 9, '否': 5} 0.9402859586706309 '''  numEntries = len(dataSet) labelCounts = {} for featVec in dataSet:  label = featVec[-1]  if label not in labelCounts.keys():   labelCounts[label] = 0  labelCounts[label] += 1 entropy = 0.0 for key in labelCounts.keys():  p_i = float(labelCounts[key]/numEntries)  entropy -= p_i * log(p_i,2)#log(x,10)表示以10 为底的对数 return entropy def split_data(data,feature_index,value): ''' 划分数据集 feature_index：用于划分特征的列数，例如“年龄” value:划分后的属性值：例如“青少年” ''' data_split=[]#划分后的数据集 for feature in data:  if feature[feature_index]==value:   reFeature=feature[:feature_index]   reFeature.extend(feature[feature_index+1:])   data_split.append(reFeature) return data_splitdef choose_best_to_split(data):  ''' 根据每个特征的信息增益，选择最大的划分数据集的索引特征 '''  count_feature=len(data[0])-1#特征个数4 #print(count_feature)#4 entropy=cal_entropy(data)#原数据总的信息熵 #print(entropy)#0.9402859586706309  max_info_gain=0.0#信息增益最大 split_fea_index = -1#信息增益最大，对应的索引号  for i in range(count_feature):    feature_list=[fe_index[i] for fe_index in data]#获取该列所有特征值  #######################################  '''  print('feature_list')  ['青少年', '青少年', '中年', '老年', '老年', '老年', '中年', '青少年', '青少年', '老年',  '青少年', '中年', '中年', '老年']  0.3467680694480959 #对应上篇博客中的公式 =（1）*5/14  0.3467680694480959  0.6935361388961918  '''  # print(feature_list)  unqval=set(feature_list)#去除重复  Pro_entropy=0.0#特征的熵  for value in unqval:#遍历改特征下的所有属性   sub_data=split_data(data,i,value)   pro=len(sub_data)/float(len(data))   Pro_entropy+=pro*cal_entropy(sub_data)   #print(Pro_entropy)     info_gain=entropy-Pro_entropy  if(info_gain>max_info_gain):   max_info_gain=info_gain   split_fea_index=i return split_fea_index    ##################################################def most_occur_label(labels): #sorted_label_count[0][0] 次数最多的类标签 label_count={} for label in labels:  if label not in label_count.keys():   label_count[label]=0  else:   label_count[label]+=1  sorted_label_count = sorted(label_count.items(),key = operator.itemgetter(1),reverse = True) return sorted_label_count[0][0]def build_decesion_tree(dataSet,featnames): ''' 字典的键存放节点信息，分支及叶子节点存放值 ''' featname = featnames[:]    ################ classlist = [featvec[-1] for featvec in dataSet] #此节点的分类情况 if classlist.count(classlist[0]) == len(classlist): #全部属于一类  return classlist[0] if len(dataSet[0]) == 1:   #分完了,没有属性了  return Vote(classlist)  #少数服从多数 # 选择一个最优特征进行划分 bestFeat = choose_best_to_split(dataSet) bestFeatname = featname[bestFeat] del(featname[bestFeat])  #防止下标不准 DecisionTree = {bestFeatname:{}} # 创建分支,先找出所有属性值,即分支数 allvalue = [vec[bestFeat] for vec in dataSet] specvalue = sorted(list(set(allvalue))) #使有一定顺序 for v in specvalue:  copyfeatname = featname[:]  DecisionTree[bestFeatname][v] = build_decesion_tree(split_data(dataSet,bestFeat,v),copyfeatname) return DecisionTree