# 将指定特征值等于 value 的行剩下列作为子数据集defsplit_data_set(data_set,index,value):""" (通过遍历 data_set 数据集，求出 index 对应的 column 列的值为 value 的行) 就是依据 index 列进行分类，如果index列的数据等于 value 的时候，就要将 index 划分到我们创建的新的数据集中 :param data_set: 数据集 待划分的数据集 :param index: 每一行的 index 列 划分数据集的特征 :param value: index 列对应的 value 值 需要返回的特征的值 :return: ret_data_set 指定特征值等于 value 的行剩下列(不包含值等于该 value 的列)作为子数据集 """ ret_data_set = []for feat_vec in data_set:# index 列为 value 的数据集[该数据集需要排除 index 列]# 判断 index 列的值是否为 valueif feat_vec[index]== value:# chop out index used for splitting# [:index]表示前 index 行，即若 index 为 2，就是取 feat_vec 的前 2 行 reduced_feat_vec = feat_vec[:index]''' 请百度查询一下: extend和append的区别 music_media.append(object) 向列表中添加一个对象object music_media.extend(sequence) 把一个序列seq的内容添加到列表中 (跟 += 在list运用类似， music_media += sequence) 1、使用append的时候，是将object看作一个对象，整体打包添加到music_media对象中。 2、使用extend的时候，是将sequence看作一个序列，将这个序列和music_media序列合并，并放在其后面。 music_media = [] music_media.extend([1,2,3]) print music_media #结果: #[1, 2, 3] music_media.append([4,5,6]) print music_media #结果: #[1, 2, 3, [4, 5, 6]] music_media.extend([7,8,9]) print music_media #结果: #[1, 2, 3, [4, 5, 6], 7, 8, 9] '''# 取 index+1 行开始，后面的所有行数据 reduced_feat_vec.extend(feat_vec[index +1:])# 收集结果值 index 列为 value 的行[该行需要排除 index 列] ret_data_set.append(reduced_feat_vec)return ret_data_set
选择信息增益最大的特征列
defchoose_best_feature_to_split(data_set):""" :param data_set: 数据集 :return: best_feature 最优的特征列 """# 求第一行有多少列的 Feature, 最后一列是 label 列 num_features =len(data_set[0])-1# 数据集的原始信息熵 base_entropy =calc_shannon_ent(data_set)# 最优的信息增益值, 和最优的 feature 编号 best_info_gain, best_feature =0.0,-1# iterate over all the featuresfor i inrange(num_features):# create a list of all the examples of this feature# 获取对应的 feature 下的所有数据 feat_list = [example[i]for example in data_set]# get a set of unique values# 获取剔重后的集合，使用set对list数据进行去重 unique_vals =set(feat_list)print("unique_vals:", unique_vals)# 创建一个临时的信息熵 new_entropy =0.0# 遍历某一列的 value 集合，计算该列的信息熵# 遍历当前特征中的所有唯一属性值，对每个唯一属性值划分一次数据集，计算数据集的新熵值，并对所有唯一特征值得到的熵求和。for val in unique_vals: sub_data_set =split_data_set(data_set, i, val)# 计算概率 prob =len(sub_data_set)/float(len(data_set))print("prob:", prob)# 计算信息熵 new_entropy += prob *calc_shannon_ent(sub_data_set)print("new_entropy:", new_entropy)# gain[信息增益]: 划分数据集前后的信息变化， 获取信息熵最大的值# 信息增益是熵的减少或者是数据无序度的减少。最后，比较所有特征中的信息增益，返回最好特征划分的索引值。 info_gain:float= base_entropy - new_entropyprint('info_gain=', info_gain, 'best_feature=', i, base_entropy, new_entropy)if info_gain > best_info_gain: best_info_gain = info_gain best_feature = ireturn best_feature
构建决策树
defcreate_tree(data_set,labels):""" :param data_set: 数据集 :param labels: label 标签 :return: 返回决策树 """ class_list = [example[-1]for example in data_set]# 如果数据集的最后一列的第一个值出现的次数=整个集合的数量，也就说只有一个类别，就只直接返回结果就行# 第一个停止条件: 所有的类标签完全相同，则直接返回该类标签。# count() 函数是统计括号中的值在list中出现的次数if class_list.count(class_list[0])==len(class_list):return class_list[0]# 如果数据集只有 1 列，那么最初出现 label 次数最多的一类，作为结果# 第二个停止条件: 使用完了所有特征，仍然不能将数据集划分成仅包含唯一类别的分组。iflen(data_set[0])==1:returnmajority_cnt(class_list)# 选择最优的列，得到最优列对应的label含义 best_feat =choose_best_feature_to_split(data_set)# 获取label的名称 best_feat_label = labels[best_feat]# 初始化myTree my_tree ={best_feat_label:{}}# 注: labels列表是可变对象，在PYTHON函数中作为参数时传址引用，能够被全局修改# 所以这行代码导致函数外的同名变量被删除了元素，造成例句无法执行，提示'no surfacing' is not in listdel (labels[best_feat])# 取出最优列，然后它的branch做分类 feat_vals = [example[best_feat]for example in data_set] unique_vals =set(feat_vals)for val in unique_vals:# 求出剩余的标签label sub_labels = labels[:]# 遍历当前选择特征包含的所有属性值，在每个数据集划分上递归调用函数create_tree() my_tree[best_feat_label][val] =create_tree(split_data_set(data_set, best_feat, val), sub_labels)# print('myTree', val, my_tree)return my_tree
