机器学习之

关注
机器学习之www.shan-machinery.com

目录

一、引言

决策树学习采用的是自顶向下的递归方法,其基本思想是以信息熵为度量构造一颗熵值下降最快的树,到叶子节点处,熵值为0。其具有可读性、分类速度快的优点,是一种有监督学习。最早提及决策树思想的是Quinlan在1986年提出的ID3算法和1993年提出的C4.5算法,以及Breiman等人在1984年提出的CART算法。本篇文章主要介绍决策树的基本概念,以及上面这3种常见决策树算法(ID3、C4.5、CART)原理及其代码实现。

二、决策树(ID3、C4.5和CART算法)2.1、决策树是什么

下面主要讨论用与分类的决策树。决策树呈树形结构,在分类问题中,表示基于特征对实例进行分类的过程。学习时,利用训练数据,根据损失函数最小化的原则建立决策树模型;预测时,对新的数据,利用决策模型进行分类。

决策树的分类:决策树可以分为两类,主要取决于它目标变量的类型。

离散性决策树:离散性决策树,其目标变量是离散的,如性别:男或女等;连续性决策树:连续性决策树,其目标变量是连续的,如工资、价格、年龄等;

        决策树相关的重要概念:

(1)根结点(Root Node):它表示整个样本集合,并且该节点可以进一步划分成两个或多个子集。

(2)拆分(Splitting):表示将一个结点拆分成多个子集的过程。

(3)决策结点(Decision Node):当一个子结点进一步被拆分成多个子节点时,这个子节点就叫做决策结点。

(4)叶子结点(Leaf/Terminal Node):无法再拆分的结点被称为叶子结点。

(5)剪枝(Pruning):移除决策树中子结点的过程就叫做剪枝,跟拆分过程相反。

(6)分支/子树(Branch/Sub-Tree):一棵决策树的一部分就叫做分支或子树。

(7)父结点和子结点(Paren and Child Node):一个结点被拆分成多个子节点,这个结点就叫做父节点;其拆分后的子结点也叫做子结点。

2.2、决策树的构造过程

决策树的构造过程一般分为3个部分,分别是特征选择、决策树生产和决策树裁剪。

(1)特征选择:

特征选择表示从众多的特征中选择一个特征作为当前节点分裂的标准,如何选择特征有不同的量化评估方法,从而衍生出不同的决策树,如ID3(通过信息增益选择特征)、C4.5(通过信息增益比选择特征)、CART(通过Gini指数选择特征)等。

目的(准则):使用某特征对数据集划分之后,各数据子集的纯度要比划分钱的数据集D的纯度高(也就是不确定性要比划分前数据集D的不确定性低)

(2)决策树的生成

根据选择的特征评估标准,从上至下递归地生成子节点,直到数据集不可分则停止决策树停止生长。这个过程实际上就是使用满足划分准则的特征不断的将数据集划分成纯度更高,不确定行更小的子集的过程。对于当前数据集的每一次划分,都希望根据某个特征划分之后的各个子集的纯度更高,不确定性更小。

(3)决策树的裁剪

决策树容易过拟合,一般需要剪枝来缩小树结构规模、缓解过拟合。

2.3、决策树的优缺点

决策树的优点:

(1)具有可读性,如果给定一个模型,那么过呢据所产生的决策树很容易推理出相应的逻辑表达。

(2)分类速度快,能在相对短的时间内能够对大型数据源做出可行且效果良好的结果。

决策树的缺点:

(1)对未知的测试数据未必有好的分类、泛化能力,即可能发生过拟合现象,此时可采用剪枝或随机森林。

2.4、ID3算法原理与python代码实现

ID3算法的核心是在决策树各个节点上应用信息增益准则选择特征递归地构建决策树。

2.4.1信息增益

在《最大熵模型学习》一文中,我们提到过熵和条件熵的概念,下面我们在总结一遍。

最大熵模型学习

(1)熵

在信息论中,熵(entropy)是随机变量不确定性的度量,也就是熵越大,则随机变量的不确定性越大。设X是一个取有限个值得离散随机变量,其概率分布为:

则随机变量X的熵定义为:

(2)条件熵

设有随机变量(X, Y),其联合概率分布为:

条件熵H(Y|X)表示在已知随机变量X的条件下,随机变量Y的不确定性。随机变量X给定的条件下随机变量Y的条件熵H(Y|X),定义为X给定条件下Y的条件概率分布的熵对X的数学期望:

当熵和条件熵中的概率由数据估计得到时(如极大似然估计),所对应的熵与条件熵分别称为经验熵和经验条件熵。

(3)信息增益

定义:信息增益表示由于得知特征A的信息后儿时的数据集D的分类不确定性减少的程度,定义为:

Gain(D,A) = H(D) – H(D|A)

             即集合D的经验熵H(D)与特征A给定条件下D的经验条件熵H(H|A)之差。

理解:选择划分后信息增益大的作为划分特征,说明使用该特征后划分得到的子集纯度越高,即不确定性越小。因此我们总是选择当前使得信息增益最大的特征来划分数据集。

缺点:信息增益偏向取值较多的特征(原因:当特征的取值较多时,根据此特征划分更容易得到纯度更高的子集,因此划分后的熵更低,即不确定性更低,因此信息增益更大)

2.4.2 ID3算法

输入:训练数据集D,特征集A,阈值ε;

输出:决策树T.

Step1:若D中所有实例属于同一类,则T为单结点树,并将类作为该节点的类标记,返回T;

Step2:若A=Ø,则T为单结点树,并将D中实例数最大的类作为该节点的类标记,返回T;

Step3:否则,2.1.1(3)计算A中个特征对D的信息增益,选择信息增益最大的特征

Step4:如果的信息增益小于阈值ε,则T为单节点树,并将D中实例数最大的类作为该节点的类标记,返回T

Step5:否则,对的每一种可能值,依将D分割为若干非空子集,将中实例数最大的类作为标记,构建子结点,由结点及其子树构成树T,返回T;

Step6:对第i个子节点,以为训练集,以为特征集合,递归调用Step1~step5,得到子树,返回

2.4.3 python代码实现

接下来我们通过下面这组数据作为测试样本

序号不浮出水面是否可以生存是否有脚蹼是否属于鱼类1是是是2是是是3是否否4否是否5否是否文件名:id3.py# -*- coding: utf-8 -*-from math import logimport operatorimport tree_plotterdef create_data_set():"""创建样本数据:return:"""data_set = [[1, 1, 'yes'], [1, 1, 'yes'], [1, 0, 'no'], [0, 1, 'no'], [0, 1, 'no']]labels = ['no surfacing', 'flippers']return data_set, labelsdef calc_shannon_ent(data_set):"""计算信息熵:param data_set: 如: [[1, 1, 'yes'], [1, 1, 'yes'], [1, 0, 'no'], [0, 1, 'no'], [0, 1, 'no']]:return:"""num = len(data_set)# n rows# 为所有的分类类目创建字典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] = 0label_counts[current_label] += 1# 计算香浓熵shannon_ent = 0.0for key in label_counts:prob = float(label_counts[key]) / numshannon_ent = shannon_ent - prob * log(prob, 2)return shannon_entdef split_data_set(data_set, axis, value):"""返回特征值等于value的子数据集,切该数据集不包含列(特征)axis:param data_set:待划分的数据集:param axis: 特征索引:param value: 分类值:return:"""ret_data_set = []for feat_vec in data_set:if feat_vec[axis] == value:reduce_feat_vec = feat_vec[:axis]reduce_feat_vec.extend(feat_vec[axis + 1:])ret_data_set.append(reduce_feat_vec)return ret_data_setdef choose_best_feature_to_split(data_set):"""按照最大信息增益划分数据:param data_set: 样本数据,如: [[1, 1, 'yes'], [1, 1, 'yes'], [1, 0, 'no'], [0, 1, 'no'], [0, 1, 'no']]:return:"""num_feature = len(data_set[0]) - 1 # 特征个数,如:不浮出水面是否可以生存和是否有脚蹼base_entropy = calc_shannon_ent(data_set) # 经验熵H(D)best_info_gain = 0best_feature_idx = -1for feature_idx in range(num_feature):feature_val_list = [number[feature_idx] for number in data_set]# 得到某个特征下所有值(某列)unique_feature_val_list = set(feature_val_list)# 获取无重复的属性特征值new_entropy = 0for feature_val in unique_feature_val_list:sub_data_set = split_data_set(data_set, feature_idx, feature_val)prob = len(sub_data_set) / float(len(data_set)) # 即p(t)new_entropy += prob * calc_shannon_ent(sub_data_set) #对各子集香农熵求和info_gain = base_entropy - new_entropy # 计算信息增益,g(D,A)=H(D)-H(D|A)# 最大信息增益if info_gain > best_info_gain:best_info_gain = info_gainbest_feature_idx = feature_idxreturn best_feature_idxdef majority_cnt(class_list):"""统计每个类别出现的次数,并按大到小排序,返回出现次数最大的类别标签:param class_list: 类数组:return:"""class_count = {}for vote in class_list:if vote not in class_count.keys():class_count[vote] = 0class_count[vote] += 1sorted_class_count = sorted(class_count.items(), key=operator.itemgetter(1), reversed=True)print sorted_class_count[0][0]return sorted_class_count[0][0]def create_tree(data_set, labels):"""构建决策树:param data_set: 数据集合,如: [[1, 1, 'yes'], [1, 1, 'yes'], [1, 0, 'no'], [0, 1, 'no'], [0, 1, 'no']]:param labels: 标签数组,如:['no surfacing', 'flippers']:return:"""class_list = [sample[-1] for sample in data_set] # ['yes', 'yes', 'no', 'no', 'no']# 类别相同,停止划分if class_list.count(class_list[-1]) == len(class_list):return class_list[-1]# 长度为1,返回出现次数最多的类别if len(class_list[0]) == 1:return majority_cnt((class_list))# 按照信息增益最高选取分类特征属性best_feature_idx = choose_best_feature_to_split(data_set)# 返回分类的特征的数组索引best_feat_label = labels[best_feature_idx]# 该特征的labelmy_tree = {best_feat_label: {}}# 构建树的字典del (labels[best_feature_idx])# 从labels的list中删除该label,相当于待划分的子标签集feature_values = [example[best_feature_idx] for example in data_set]unique_feature_values = set(feature_values)for feature_value in unique_feature_values:sub_labels = labels[:]# 子集合# 构建数据的子集合,并进行递归sub_data_set = split_data_set(data_set, best_feature_idx, feature_value) # 待划分的子数据集my_tree[best_feat_label][feature_value] = create_tree(sub_data_set, sub_labels)return my_treedef classify(input_tree, feat_labels, test_vec):"""决策树分类:param input_tree: 决策树:param feat_labels: 特征标签:param test_vec: 测试的数据:return:"""first_str = list(input_tree.keys())[0]# 获取树的第一特征属性second_dict = input_tree[first_str]# 树的分子,子集合Dictfeat_index = feat_labels.index(first_str)# 获取决策树第一层在feat_labels中的位置for key in second_dict.keys():if test_vec[feat_index] == key:if type(second_dict[key]).__name__ == 'dict':class_label = classify(second_dict[key], feat_labels, test_vec)else:class_label = second_dict[key]return class_labeldata_set, labels = create_data_set()decision_tree = create_tree(data_set, labels)print "决策树:", decision_treedata_set, labels = create_data_set()print "(1)不浮出水面可以生存,无脚蹼:", classify(decision_tree, labels, [1, 0])print "(2)不浮出水面可以生存,有脚蹼:", classify(decision_tree, labels, [1, 1])print "(3)不浮出水面可以不能生存,无脚蹼:", classify(decision_tree, labels, [0, 0])tree_plotter.create_plot(decision_tree)

画图程序,tree_plotter.py:

import matplotlib.pyplot as pltdecision_node = dict(boxstyle="sawtooth", fc="0.8")leaf_node = dict(boxstyle="round4", fc="0.8")arrow_args = dict(arrowstyle="https://www.shan-machinery.com