文档介绍：机器学****决策树(ID3)算法及案例
1基本原理
决策树是一个预测模型。它代表的是对象属性与对象值之间的一种映射关系。树中每个 节点表示某个对象，每个分支路径代表某个可能的属性值，每个叶结点则对应从根节点到该 叶节点所经历的路径所表示中则返回参数0，
#如果current_label在字典中则返回current_label对应的value值
label_counts[current_label] = (current_label, 0) + 1
shannon_ent =
for key in label_counts:
prob = float(label_counts[key])/num_entries shannon_ent -= prob*log(prob, 2)
return shannon ent
3、按照给定特征划分数据集。分类算法除了需要测量信息熵，还需要 划分数据集，这就需要对每个特征划分数据集的结果计算一次信息熵, 然后判断按照哪个特征划分数据集是最好的划分方式。
#################################
#功能：划分数据集
#输入变量：data_set, axis, value
#数据集，数据集的特征，特征的值
#输出变量：ret_data_set,划分后的数据集
#################################
def split_data_set(data_set, axis, value):
ret_data_set =[]
for feat_vec in data_set:
if feat_vec[axis] == value:
#把axis特征位置之前和之后的特征值切出来
#没有使用del函数的原因是，del会改变原始数据
reduced_feat_vec = feat_vec[:axis] (feat_vec[axis+l:]) (reduced_feat_vec)
return ret_data_set 4、遍历整个数据集，循环划分数据并计算信息熵，通过计算最大信息 增益来找到最好的特征划分方式。
具体做法是，遍历当前特征中的所有唯一属性值，对每个特征划分一次
数据集，然后计算数据集的新熵值，并对所有唯一特征值得到的熵求和。
最后用所求的和值与原始信息熵相减，计算寻找最大信息增益。
######################################
#功能：选择最好的数据集划分方式
#输入变量：data_set待划分的数据集
#输出变量：best_feature计算得出最好的划分数据集的特征
######################################
def choose_best_feature_to_split(data_set):
num_features = len(data_set[0]) - 1 #最后一个是类别标签，所以特征 属性长度为总长度减1
base_entropy = calc_shannon_ent(data_set) # 计算数据集原始信息熵
best_info_gain =
best_feature = -1
for i in xrange(num_features):
# feat_vec[i]代表第i列的特征值，在for循环获取这一列的所有值
feat_list = [feat_vec[i] for feat_vec in data_set]
unique_vals = set(feat_list) # set函数得到的是一个无序不重复数 据集
new_entropy =
#计算每种划分方式的信息熵
for value in unique_vals:
sub_data_set = split_data_set(data_set, i, value) prob = len(sub_data_set)/float(len(data_set)) new_entropy += prob*calc_shannon_ent(sub_data_set)
info_gain = base_entropy - new_entropy
if info_gain > best_info_gain:
best_info_gain = info_gain
best_feature = i
return best_feature
5递归构建决策树
工作原理：得到原始数据集，然后