机器学习:决策树(基本思想、信息熵、构建决策树的问题及思想)
一、决策树思维、决策树算法
1)决策树思维
- 决策树思维是一种逻辑思考方式,逐层的设定条件对事物进行刷选判断,每一次刷选判断都是一次决策,最终得到达到目的;整个思考过程,其逻辑结构类似分叉的树状,因此称为决策树思维;
- 例一:公式招聘时的决策树思维
- 此过程形成了一个树的结构,树的叶子(录用 / 考察)节点位置是做出的决定,也可以理解为是对输出(也就是应聘者的信息)的分类:录用、考察——这样的逻辑思考的过程就叫决策树。
- 树的最高深度:depth == 3,说明最多做出 3 次判断就能得到结果;
2)scikit-learn 中的决策树算法
-
例二:
import numpy as np import matplotlib.pyplot as plt from sklearn import datasets iris = datasets.load_iris() X = iris.data[:, 2:] y = iris.target plt.scatter(X[y==0, 0], X[y==0, 1]) plt.scatter(X[y==1, 0], X[y==1, 1]) plt.scatter(X[y==2, 0], X[y==2, 1]) plt.show()
-
def plot_decision_boundary(model, axis): x0, x1 = np.meshgrid( np.linspace(axis[0], axis[1], int((axis[1]-axis[0])*100)).reshape(-1,1), np.linspace(axis[2], axis[3], int((axis[3]-axis[2])*100)).reshape(-1,1) ) X_new = np.c_[x0.ravel(), x1.ravel()] y_predict = model.predict(X_new) zz = y_predict.reshape(x0.shape) from matplotlib.colors import ListedColormap custom_cmap = ListedColormap(['#EF9A9A','#FFF59D','#90CAF9']) plt.contourf(x0, x1, zz, linewidth=5, cmap=custom_cmap) # 使用 DecisionTreeClassifier 方法对数据分类 from sklearn.tree import DecisionTreeClassifier # 创建决策树的分类器 # 构造决策树时,DecisionTreeClassifier() 方差需要传入两个参数: # 1)max_depth:决策树最高深度; # 2)criterion='entropy':表示“熵”的意思; dt_clf = DecisionTreeClassifier(max_depth=2, criterion='entropy') dt_clf.fit(X, y) plot_decision_boundary(dt_clf, axis=[0.5, 7.5, 0, 3]) plt.scatter(X[y==0, 0], X[y==0, 1]) plt.scatter(X[y==1, 0], X[y==1, 1]) plt.scatter(X[y==2, 0], X[y==2, 1]) plt.show()
3)分析模型的决策边界:得出模型的决策树
4)决策树算法
- 决策树算法是借用了决策树思维解决分类问题(或者回归问题)的算法;
- 决策树算法的特点:
- 非参数学习算法;
- 可以解决分类问题;
- 天然可以解决多分类问题;
- 也可以解决回归问题;(结果是一个数值)
- 具有非常好的可解释性;
二、信息熵
- “信息熵”:随机变量不确定度的度量,是信息论中的代表;
- 特点:熵越大,数据的不确定性越高;熵越小,数据的不确定性越低;
- 不确定性:一组数据的个数一定,元素的种类越少,该组数据的不确定性越高;
1)信息熵的计算:
- Pi:对于一个系统中,有 k 类的信息,每一类信息所占系统的比例,记为 P;
- k 类:比如数据集中样本的总类数;
- 比例:每一类样本数量占总数的多少;
- 公式中的 “-”:由于 Pi < 1,则 log(Pi) < 0,熵的值 H 应该大于 0;
- log(Pi):对数函数的底数可以取2,e或者10,取的底不同,获得的信息熵的结果的单位不同,分别称为:bits, nats 和 bans。
2)实例了解信息熵的计算
-
例一:
- k == 3:共 3 种样本类别;
- P1 == P2 == P3 == 1/3
-
,此处选择的底数是自然对数 e;
- 在这里的计算中,我们求信息熵的底可以用任意值,因为具体在划分的时候,不管底取多少,H这个函数的性质是不会变的。
-
例二:
- k == 3
- P1 == 1/10、P2 == 2/10、P3 == 7/10
-
例三:
3)3 个例子对比分析
- 现象:例一的信息熵 > 例二的信息熵 > 例三的熵
- 结论:
- 确定性:例三 > 例二 > 例一
- 例二中的数据的确定性比例一高更高,因为它有 70% 的数据是同一类型的;
- 信息熵物理上的最小值:Hmin = 0;
三、构建决策树的思路和问题
1)决策树算法的思想
- 解决分类问题时,决策树算法的任务是构造决策树模型,对未知的样本进行分类;
- 决策树算法利用了信息熵和决策树思维:
- 信息熵越小的数据集,样本的确定性越高,当数据集的信息熵为 0 时,该数据集中只有一种类型的样本;
- 训练数据集中有很多类型的样本,通过对数据集信息熵的判断,逐层划分数据集,最终将每一类样本单独划分出来;
- 划分数据集的方式有很多种,只有当按样本类别划分数据集时(也就是两部分数据集中不会同时存在相同类型的样本),划分后的两部分数据集的整体的信息熵最小;反相推断,当两部分数据集的整体的信息熵最小时,则两部分数据集中不会同时存在相同类型的样本;
- 预测:根据模型参数划分结束后,对每个“叶子”节点的样本数据进行投票,规定数量最多的样本的类型为该“叶子”的预测类型;(也就是未知的样本经过逐层决策后到达该“叶子”节点处,则认为该样本的类型为其所处的“叶子”的预测类型)
2)概念
- 根节点:第一次进行划分的节点,拥有全部数据;
- 维度:一般指样本特征;
- 划分点:选定的特征的一个值;(按某特征的值的大小排列数据集样本,根据该特征的值划分数据集)
- 整体的信息熵:节点处的数据集划分为两部分后的信息熵,等于两部分数据集信息熵的和:H总 = H1 + H2;
- H1 = -log(P1) - log(P2) - ... - log(Pk):第一部分数据集*有 k 种样本类型;
3)思路
- 思路:先找到划分一个节点数据集的方法,用此方法,从根节点开始划分数据集,直到所有的数据集不需要再进行划分,此时的决策树为最终的决策树模型;
4)问题
- 节点处的数据集应该按哪个维度的哪个阈值进行划分?
- 怎么判断该数据集不需要再进行划分?
5)解决思想
- 按不同的特征的不同值将数据集划分为两部分,划分的方式有很多种,划分后的两部分数据集的信息熵的总和最小时,对应的划分方式为最佳,此时的特征和该特征的值为最佳;
- 如果一个数据集的信息熵为 0,说明该数据集中只有一类样本,则不再对该数据集进行划分;
- 任务:
- 寻找一种方式——为每一个节点处选取一个维度,维度上选取一个值,根据这个维度和取值对数据进行划分,划分以后使得整个系统的信息熵最低;
- 方法:
- 对所有的划分可能性进行搜索,比较每一种方式所得的系统整体的信息熵,最低的信息熵对应的划分方式就是该节点最终的结构;
- 按此思路和方式,确定决策树的每一个节点,进而确定决策树的最终结构;
- 在极端情况下:
- 如下图,A、B、C 3 个叶子节点处,每个叶子节点中的数据都只属于 A、B、C 它们本身;此时整个系统的信息熵就达到了 0(每处叶子种只有一类样本,信息熵为 0,因此整体系统的信息熵也是 0);
6)计算二分类结果的整体的信息熵
- 二分类的信息熵计算:
-
,x 表示其中一类样本的比例;
- 绘制此函数的图像:x 的取值范围定义为:[0.01,0.99]
-
import numpy as np import matplotlib.pyplot as plt # np.log(p):此时的 p 不仅可以是一个数,还能是一个向量; # 当 p 传入的是数组时,可以一次性计算出数组中所有元素的信息熵,再以数组的形式返回; def entropy(p): return -p * np.log(p) - (1-p) * np.log(1-p) x = np.linspace(0.01, 0.99, 200) plt.plot(x, entropy(x)) plt.show()
- 当 x = 0.5 时,H 最大;
- 相对于 0.5,无论 x 值偏大或者偏小,H 值都降低,因为无论 x 值偏向哪一类,数据集中的样本都更集中于一类样本,数据集的确定性就会偏高。
四、老师答疑
- 问(一):决策树模型中,每个节点处的数据集划分到最后,得到的“叶端”数据集中一定只包含一种类型的样本吗?
- 老师:是的!如果你不规定最高决策树深度,节点划分最小样本数等信息的话,最终没一个叶子节点又有可能包含一类样本信息,即信息熵为0:)但是,对于正常的数据,这样做近乎一定过拟合。关于我说的这些参数,后续课程会有介绍:)
- 问(二):如果最终所有决策树模型的“叶端”的数据集中只包含一种类型的样本,所有的“叶端”数据集对应的样本类型当中,有没有相同的类型?
-
老师:可能!举一个实际的例子(不一定科学),判断一个肿瘤是良性还是恶性,有肿瘤的长度和宽度两个指标,可能得到的决策树是这样的:有两个叶子节点对应的样本是良性的;你可以想象,在更复杂的场景下,样本的特征更多,决策树的层数更高,叶子节点更多,势必有很多叶子节点最终的类别是一样的;
肿瘤样本 / \ 长度>10? 长度 <= 10 / \ (良性) 宽度 < 10 宽度 >= 10 (良性) (恶性)
- 问(三):我们对节点数据集划分时,是不是“只有当按样本类别划分数据集时(也就是划分后的两部分数据集中不会同时存在相同类型的样本),划分后的两部分数据集的整体的信息熵最小?”
- 老师:是这样的,但是对于很多数据,在初始化分的时候,会不存在这样的划分(如果只基于一个特征和一个固定值进行划分的话)。通常划分后的两部分数据集,依然都每个样本的数据各有一些,所以还需要到下一层继续划分。
- 问(四):在根据某一特征对样本进行分类时,有没有可能是:特质值在区间 [a, b] U [c, d] 上的样本定义为一个类别?
- 老师:有可能,但根据我们的算法,还是会先选择一个分割点,另一个分割点在后续的划分时出现,所以有了2)的情况。
-
结论:
- 决策树模型中,每个节点处的数据集划分到最后,得到的“叶端”数据集中不一定只包含一种类型的样本;
- 所有的“叶端”数据集对应的样本类型当中,有些实际业务中存在相同的类型。
- 对节点数据集划分时,只有当按样本类别划分数据集时(也就是划分后的两部分数据集中不会同时存在相同类型的样本),划分后的两部分数据集的整体的信息熵最小。
- 在根据特征进行样本分类时,有些类型的样本之间存在关联,如问(二)中,老师举例的肿瘤案例:长度 <= 10 的全是良性肿瘤,长度 > 10 的有些是良性肿瘤有些是恶性肿瘤。