决策树学习笔记

1、决策树的概念

    顾名思义，决策树是用来：根据已知的若干条件，来对事件作出判断。从根节点到叶子节点，是将不同特征不断划分的过程，最后将类别分出。

    在理论学习前，先了解下面一个例子：

    如下图所示，根据“不浮出水面是否可以生存”和“是否有脚蹼”两种特征来判断该海洋动物是否鱼类。图中有5个样本，样本中有两种是鱼类，三种不是鱼类。

    可建立的特征向量如下：

_data_set = [[1, 1, "yes"],[1, 1, "yes"],[1, 0, "no"],[0, 1, "no"],[0, 1, "no"]]_labels = ["no surfacing", "flippers"]

    _labels储存的是特征的实际含义，在建立决策树时作为分类节点名称存在，no surfaciing就是不需要浮出水面是否可以生存。最后一列储存的是对应特征向量的标签。后续的代码中都遵循这一约定。

 2、用ID3算法来构造决策树

    ID3算法将信息增益做贪心算法来划分算法，总是挑选是的信息增益最大的特征来划分数据，使得数据更加有序。

    2.1信息增益

    熵：熵是信息的期望，一般表示信息的混乱、无序程度

    信息的定义如下：

    于是信息的期望，熵的定义为：

                                        

    信息增益指的是熵减小的量，也就是，数据集变得有序了多少。

    下面给出熵的计算代码，直接输入上面给出的数据集可以得到信息熵

# 计算香农熵
def calc_shannon_ent(dataset):n = len(dataset)label_counts = {}# 统计每个类别出现的次数for feature in dataset:label = feature[-1]if label not in label_counts:label_counts[label] = 0     # 创建该元素并清零label_counts[label] += 1entropy = 0for key in label_counts:p = float(label_counts[key]) / n  # 计算类概率，或者说类在所有数据中的比例entropy -= p * log(p, 2)return entropy

    再次注意：特征向量最后一维是类别标签

    2.2数据集划分

    构造树的过程中，要将数据进行划分，为了方便，写一个子函数专门做数据划分，划分的原则是：挑出指定维度上和指定值相等的所有特征向量，并将该维去除后返回

# 在axis维度上对dataset进行划分，抽取axis维度上等于value的特征,这里没有用pandas，否则不需要这么麻烦
def splite_dataset(dataset, axis, value):splt_dset = []for f in dataset:if f[axis] == value:reduce_fv = f[:axis]reduce_fv.extend(f[axis+1:])splt_dset.append(reduce_fv)return splt_dset

    2.3选择最好的划分特征

    遍历每一个特征，尝试使用每一个特征划分数据集，并计算对应的信息增益，选择最大的那一个特征来划分数据。值得注意的是，这里并不是使用二分类划分，而是，对应的特征有多少个值就将数据集划分为几个子集。在海洋动物的例子中，只是恰好两个特征都只有两个值。

# 通过遍历所有的特征，求取熵最小的划分方式
# 返回划分数据最好的特征，和最大的信息增益
def min_entropy_split_feature(dataset):f_n = len(dataset[0]) - 1base_entropy = calc_shannon_ent(dataset)best_info_gain = 0.0#print("entropy calc:"+str(dataset))best_feature = -1for i in range(f_n):f_list = [feature[i] for feature in dataset]unique_values = set(f_list)new_entropy = 0.0for value in unique_values:sub_dataset = splite_dataset(dataset, i, value)pro = len(sub_dataset) / float(len(dataset))new_entropy += pro * calc_shannon_ent(sub_dataset)info_gain = base_entropy - new_entropy  # 信息增益是信息熵的减小量if info_gain > best_info_gain:best_info_gain = info_gainbest_feature = ireturn best_feature, best_info_gain

    2.4递归构建决策树

    2.3中给出了划分数据集的方法，可以使得数据局部整体上最有序，划分得到若干个子数据集中依然可以继续划分，使用同样的方法使得子数据集最有序，依次递归进行，直到最底层子数据集中只有一个类别

# 递归构建决策树
def create_tree(dataset, __labels):labels = __labels.copy()classlist = [f[-1] for f in dataset]# 只剩下一个类了，因此返回类名称if classlist.count(classlist[0]) == len(classlist):return classlist[0]# 数据集中只剩下最后一列了，也就是所有的特征都用完了，没法再向下分类了# 这时候如果数据集中有多个类，那就认为是出现最多的那个类# 实际中应该是，所给定的特征无法将数据进行完全分类导致的if len(dataset[0]) == 1:# print("******")return majority_cnt(classlist)bestfeature = min_entropy_split_feature(dataset)[0]# if bestfeature >= len(labels):#     print("**************index out of range")#     print(dataset)#     print(labels)#     print(bestfeature)bestf_label = labels[bestfeature]newtree = {bestf_label: {}}del labels[bestfeature]f_values = [f[bestfeature] for f in dataset]  # 找出bestfeature全部取值unique_f_values = set(f_values)for v in unique_f_values:sublabels = labels[:]_splitedtree = splite_dataset(dataset, bestfeature, v)# print("xxxxxxxxxxxxxx seperate:")# print("best fv:" + str(bestfeature) + " v:" + str(v))# print(_splitedtree)# print(labels)newtree[bestf_label][v] = create_tree(_splitedtree.copy(), sublabels)return newtree

    上面还用了一个子函数，是当数据集只剩下一列（最后一列，也就是类别），但是无法完全分类，就返回剩下的数据集中出现最多的那个类别

# 计算数据集中的主要类别，这里计算是鱼的多还是不是鱼的多，其实就是判断yes多还是no多
# 其他应用中可能会出现多个类别标签，因此这是一个通用函数
def majority_cnt(classlist):classcount = {}for label in classlist:if label not in classcount.keys():  # 字典的键中不包含labelclasscount[label] = 0classcount[label] += 1# classcount.items()是以list形式返回字典的键值：dict_items([('yes', 2), ('no', 4)])# key中指定值获取函数，x[1]表示用键值对第二个参数来排序# reverse表示降序排序，默认是ascendingsorted_class_count = sorted(classcount.items(), key=lambda x: x[1], reverse=True)return sorted_class_count[0][0]  # 返回出现次数最多的类的标签

    最后构建得到的决策树输入所示：

                            

3、用决策树来做分类

    上面构造了决策树，通过使用create_tree方法可以得到字典储存的决策树。输入一个新的特征向量，利用决策树，沿着树从上到下，可以得到分类。下面给出分类代码：

# 用构建好的决策树来进行分类
def classify(input_tree, feature_labels, test_fv):classlabel = "none"first_label = list(input_tree.keys())[0]  # 获取输入字典中的第一个键new_dict = input_tree[first_label]        #feature_index = feature_labels.index(first_label)  # 获取first_label是第几个特征for key in new_dict.keys():if test_fv[feature_index] == key:  # 注意，key是特征的值if type(new_dict[key]).__name__ == "dict":classlabel = classify(new_dict[key], feature_labels, test_fv)else:classlabel = new_dict[key]return classlabel

    对于数据集来说，字典的根节点总是储存了本次划分数据集的特征，因此代码中总是先获取树根键值，然后根据该键获取特征编号index，在for循环中，遍历该特征的所有取值，计算得到子数据集进行递归，如果子数据集已经不是一个字典，则认为遍历已经到达最底层，最底层储存了类别标签，返回类别标签，完成分类。

4总结

    构建决策树可以用来做分类，其他用途尚不清楚。使用了贪心法，每次划分都是选择信息增益最大的，推测这样不一定能得到全局最大增益。除了ID3算法构造决策树，较为流行的还有C4.5和CART算法，后面继续学习。

    决策树做分类似乎只能对简单特征分类，如果出现长度、宽度、距离等浮点数据时候无法分类，暂时不知道怎么处理。

参考文献：《机器学习实战》