决策树理论
1.1、计算信息熵（经验熵）# 计算给定数据集的熵
def calc_shannon_entropy(data_set):
# 数据集行数
num_entries = len(data_set)
# 类标签 字典
label_counts = {}
# 遍历数据集, 记录每个标签的数量
for feat_vec in data_set:
# 最后一列为类标签
current_label = feat_vec[-1]
if current_label not in label_counts.keys():
label_counts[current_label] = 0
label_counts[current_label] += 1
shannon_entropy = 0.0
for key in label_counts:
# 计算每种类别的概率
prob = float(label_counts[key]) / num_entries
shannon_entropy -= prob * log(prob, 2)
# 返回香农熵
return shannon_entropy
1.2、创建测试数据
def create_data_set():
data_set = [[1, 1, 'yes'],
[1, 1, 'yes'],
[1, 0, 'no'],
[0, 1, 'no'],
[0, 1, 'no']]
inner_labels = ['no surfacing', 'flippers']
return data_set, inner_labels
1.3、计算条件熵
接下来我们需要计算条件熵，以便能够计算信息增益，计算之前我们需要划分数据集，如选取年龄属性且为青年划分数据集
1.3.1、划分数据集
给定特征划分数据集
划分数据子集伪代码如下划分数据子集（数据集，特征编号，特征值）
遍历数据集
如果数据向量中划分特征的值=特征值
从向量中取不包含该特征的子向量作为子集的一个向量
返回子集
为什么返回的子集不包含选取的特征，因为需要计算不包含该特征下的熵，条件熵的计算。
#输入：数据集、axis代表第几个特征、value代表该特征所对应的值
#输出：划分后的数据集
# 按照某个特征划分数据集， 需要将所有元素抽出来
def split_data_set(data_set, axis, value):
# 声明新的列表， 以便不改动原数据集
ret_data_set = []
for featVec in data_set:
if featVec[axis] == value: # 比较特征值， 即该特征 每个分类的子集
# 将 特征列之外的数据保存到reduced_feat_vec
reduced_feat_vec = featVec[:axis]
reduced_feat_vec.extend(featVec[axis + 1:])
ret_data_set.append(reduced_feat_vec)
return ret_data_set
#### 测试
# 主函数
if __name__ == '__main__':
data_set, labels = create_data_set()
shannonEnt = calc_shannon_entropy(data_set)
print('熵: ', shannonEnt)
print(split_data_set(data_set, 0, 1))
print(split_data_set(data_set, 0, 0))
1.4、寻找数据集的最佳划
寻找数据集的最佳划分
伪代码如下：
寻找最佳划分特征(数据集)
计算数据集的熵
遍历数据集每个特征
计算当前特征的取值域
遍历当前特征的取值域
根据当前值划分子集
累加划分该子集的概率和该自己的熵的乘积
该特征划分信息增益=数据集的熵-累加结果
比较每个特征信息增益，记录最大的信息增益和特征编号
返回最好特征编号
代码实现：
def choose_best_feature_to_split(data_set):
'''
使用熵原则进行数据集划分
@信息增益:info_gain = old -new
@最优特征：best_feature
@类别集合：uniVal
'''
# 特征数量， 除掉最后一列(分类)
num_features = len(data_set[0]) - 1
# 计算信息熵
base_entropy = calc_shannon_entropy(data_set)
# 计算信息增益
best_info_gain = 0.0;
# 最佳特征
best_feature = -1
for i in range(num_features): # 遍历每个特征
# 第i个特征的样本集合
feat_list = [example[i] for example in data_set]
# 该特征子集取值 如 年龄分： 青年， 中年， 老年三个子集
unique_vals = set(feat_list)
new_entropy = 0.0
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_entropy(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
注意：这里数据集需要满足以下两个条件：所有的列元素都必须具有相同的数据长度数据的最后一列或者每个实例的最后一个元素是当前实例的类别标签。
1.5、构建决策树
Python用字典类型来存储树的结构 返回的结果是myTree-字典
创建树（数据集）
如果数据集中只包含一种分类类别
返回该类别
如果数据集中没有特征值了
返回数据集中类别数量最多的类别
寻找数据集中最佳的划分子集的特征
将该特征名作为树节点
遍历该特征的每种特征值
以当前的特征值划分子集
以子集为参数递归调用创建树（）方法
将递归调用的结果作为树节点的一个分支
返回树
# 构建决策树
def create_tree(data_set, labels):
print("data_set", data_set)
print("labels", labels)
# 类标签
class_list = [example[-1] for example in data_set]
# 只有一个分类
if class_list.count(class_list[0]) == len(class_list):
return class_list[0]
# 没有特征值
if len(data_set[0]) == 1:
# 返回数据集中类别数量最多的类别
return majorityCnt(class_list)
# 最优特征编号
best_feat = choose_best_feature_to_split(data_set)
# 将该特征作为树节点
best_feat_label = labels[best_feat]
my_tree = {best_feat_label: {}}
##此位置书上写的有误，书上为del(labels[bestFeat])
##相当于操作原始列表内容，导致原始列表内容发生改变
##按此运行程序，报错'no surfacing'is not in list
##以下代码已改正
#复制当前特征标签列表，防止改变原始列表的内容
subLabels = labels[:]
del (subLabels[best_feat])
# 最优特征的值集合
featValues = [example[best_feat] for example in data_set]
print("最优特征", best_feat,", 最优特征的值集合", featValues)
unique_vals = set(featValues)
for value in unique_vals:
# 以当前的特征值划分子集
# 以子集为参数递归调用创建树（）方法
# 将递归调用的结果作为树节点的一个分支
subLabels = labels[:]
my_tree[best_feat_label][value] = create_tree(split_data_set(data_set, best_feat, value), subLabels)
return my_tree
# 其中当所有的特征都用完时，采用多数表决的方法来决定该叶子节点的分类，
# 即该叶节点中属于某一类最多的样本数，那么我们就说该叶节点属于那一类！。
def majorityCnt(class_list):
# 创建一个空的字典
class_count = {}
for vote in class_list:
if vote not in class_count.keys(): class_count[vote] = 0
class_count[vote] += 1
# 排序 数量最多的类别， 从大到小排列
sorted_class_count = sorted(class_count.iteritems(), key=operator.itemgetter(1), reverse=True)
# 返回数量最多的类别
return sorted_class_count[0][0]
### 测试
# 主函数
if __name__ == '__main__':
data_set, labels = create_data_set()
my_tree = create_tree(data_set, labels)
print("myTree==>" , my_tree)
我们将上述方法进行封装得到如下函数：
输入：决策树、构建树的类别标签向量（用于确定特征在数据集中的位置）、待分类样本
输出：叶子节点所属类别
构造决策树是一个很耗时的任务。为了节省计算时间，最好能够在每次执行分类时调用已经构造好的决策树。为了解决这个问题，需要使用python模块pickle序列化对象，序列化对象可以在磁盘上保存对象，并在需要的时候读取出来。
def store_tree(input_tree, filename):
import pickle
fw = open(filename, 'wb')
pickle.dump(input_tree, fw)
fw.close()
def grab_tree(filename):
import pickle
fr = open(filename, 'rb')
return pickle.load(fr)
