文章目录
一、什么是决策树二、树结构三、特征选择3.1 熵3.2 条件熵3.3 信息增益3.4 信息增益率3.5 基尼系数3.6 相对熵(KL散度)3.7 交叉熵
四、连续值处理
一、什么是决策树
决策树又称为判定树，属于有监督学习算法，是数据挖掘技术中的一种重要的分类与回归方法，它是一种以树结构(包括二叉树和多叉树)形式来表达的预测分析模型。决策树算法包括ID3、ID4.5、CART树，本文主要讲述CART树的原理及应用。
二、树结构
决策树由节点和分支组成。节点有三种类型:根节点，内部节点和叶节点。-般的，一棵决策树包含一个根节点，若干个内部节点和若干个叶节点。分支:用于连接各个节点。
三、特征选择
特征选择 是决定用哪个特征来划分特征空间。特征选择表示从众多 的特征中选择-个特征作为当前节点分裂的标准。如何选择特征有 不同的量化评估方法，从而衍生出不同的决策树。参考链接
那么特征选择的准则是什么?什么样的划分属性是最优的? 我们希望决策树的内部节点所包含的样本尽可能属于同一类别，即节点的纯度”越来越高，可以高效地从根结点到达叶节点，得到决策结果。接下来我们地特征选择的一些基础概念进行讲解。常见决策树算法
3.1 熵
在信息论和概率统计中，熵(entropy)是表示随机变量不确定性的度量，熵越大，随机变量的不确定性越大。设X是一个取有限值的离散随机变量，其概率分布为： 则随机变量X的熵定义： 为了能够更好地理解熵的意义，举一个例子来说明。A集合：[1,2,3,1,1,4,5]，B集合：[1,1,1,1,1,1,2]，A集合的熵更大。我们可以画出函数 h（p）=p*logp的图像，代码如下：
import matplotlib.pyplot as plt
import numpy as np
p=np.linspace(0,1,100)
h=-p*np.log(p)
plt.figure(figsize=(10,7),dpi=450)
plt.plot(p,h)
plt.xlabel('p')
plt.ylabel('h(p)')
plt.title('h(p)=-p*logp')
plt.show()
图像如下： 再举个例子，现在我们假设随机变量X有N种可能，且每种可能发生的概率均为1/N,即p=1/N，那么我们此时的熵：H(X)=-N * 1/N * log(1/N)=logN，这就是我们的对数函数，且定义域N>=1,这是一个单调递增函数，即随着随机变量X的可能N越多，随机变量X的熵越大，则随机变量X的不确定性越大（这很好理解，猜抛硬币的正反面和猜大乐透号码，肯定是大乐透号码不确定性大得多）。logN图像如下： 大家如果有兴趣的话，可以去了解下关于信息熵的数学证明-信息熵数学证明。 在这里可以联想到一个问题：假设随机变量X有N种可能，随机变量Y有M种可能，那么是否存在H（1，…，N）=H（1，…，M）,举个简单的例子，是否存在H（x,y,z）=H（0.5,0.5）=log2，其中x+y+z=1，且0 from sympy import * #import numpy as np from sympy import symbols, solve , log x = Symbol('x') y = Symbol('y') z=Symbol('z') fun1=x+y+z-1 fun2=-x*log(x)-y*log(y)-z*log(z)-log(2) print(solve([fun1,fun2], [x,y])) 得到的结果，表示无解（具体原因未知）： NotImplementedError: could not solve -ylog(y) - zlog(z) - (-y - z + 1)*log(-y - z + 1) - log(2) 现在换一种解法对其进行求解，代码如下： import numpy as np n=np.arange(0,1,0.005) h1=np.log(2) for i in n: for j in n: for k in n: h=-i*np.log(i)-j*np.log(j)-k*np.log(k) if abs(h1-h)<=0.00001 and (i+j+k)==1: print(i,j,k,h,h1,h1-h) 输出结果： 0.005 0.38 0.615 0.6931453186851941 0.6931471805599453 1.8618747511522926e-06 0.005 0.615 0.38 0.6931453186851941 0.6931471805599453 1.8618747511522926e-06 0.06 0.185 0.755 0.6931568769263072 0.6931471805599453 -9.696366361944264e-06 0.06 0.755 0.185 0.6931568769263072 0.6931471805599453 -9.696366361944264e-06 0.185 0.06 0.755 0.6931568769263072 0.6931471805599453 -9.696366361944264e-06 0.185 0.755 0.06 0.6931568769263072 0.6931471805599453 -9.696366361944264e-06 0.38 0.005 0.615 0.6931453186851941 0.6931471805599453 1.8618747511522926e-06 0.38 0.615 0.005 0.6931453186851941 0.6931471805599453 1.8618747511522926e-06 0.615 0.005 0.38 0.6931453186851941 0.6931471805599453 1.8618747511522926e-06 0.615 0.38 0.005 0.6931453186851941 0.6931471805599453 1.8618747511522926e-06 0.755 0.06 0.185 0.6931568769263072 0.6931471805599453 -9.696366361944264e-06 0.755 0.185 0.06 0.6931568769263072 0.6931471805599453 -9.696366361944264e-06 由输出结果我们可以看出，当x,y,z=0.005,0.38,0.615或0,06,0.185,0.755时,H（0.005,0.38,0.615）与H（0.5,0.5）之间的误差是非常小的，即此时两个随机变量的信息熵几乎相等。是否能以此进行升维、降维？ 3.2 条件熵 设有随机变量(X,Y)，条件熵H(Y|X)表示在已知随机变量X的条件下随机变量Y的不确定性。随机变量X给定的条件下随机变量Y的条件熵H(Y|X)定义为X给定条件下Y的条件概率分布的熵对X的数学期望。其公式如下： 其中： 下面我们举例进行说明，数据如下参考链接： 设随机变量Y={嫁，不嫁}，我们可以统计出，嫁的个数为6/12 = 1/2；不嫁的个数为6/12 = 1/2。那么Y的熵，根据熵的公式来算，可以得到H（Y） = -1/2log1/2 -1/2log1/2=log2。 为了引出条件熵，我们现在还有一个变量X，代表长相是帅还是不帅，当长相是不帅的时候，统计如下红色所示： 可以得出，当已知不帅的条件下，满足条件的只有4个数据了，这四个数据中，不嫁的个数为1个，占1/4；嫁的个数为3个，占3/4，那么此时： H（Y|X = 不帅） = -1/4 * log1/4-3/4 * log3/4 p(X = 不帅) = 4/12 = 1/3 同理我们可以得到，当已知帅的条件下，满足条件的有8个数据了，这8个数据中，不嫁的个数为5个，占5/8；嫁的个数为3个，占3/8，那么此时有： H（Y|X = 帅） = -5/8 * log5/8-3/8 * log3/8 p(X = 帅) = 8/12 = 2/3 有了上面的铺垫之后，我们终于可以计算我们的条件熵了，要计算随机变量X=长相给定的条件下随机变量Y的条件熵H（Y|X = 长相），根据上述公式我们可以得出： H（Y|X=长相） = p(X =帅)*H（Y|X=帅）+p(X =不帅)*H（Y|X=不帅） 即：H（Y|X=长相） =2/3 *（-5/8log5/8-3/8log3/8）+1/3 *（-1/4log1/4-3/4log3/4）=0.5954 注：对数计算这里都以e为底的，下面的计算也是如此，且定义0*log 0 = 0 。 3.3 信息增益 信息增益表示得知特征X的信息而使得类Y的信息的不确定性减少程度。特征A对训练数据集D的信息增益g(D,A),为集合D的熵H(D)与特征A给定条件下D的条件熵H(D|A)之差，即： 我们还是以上面的12条样本集合为例（对应公式中的集合D），计算各个特征的信息增益。参考计算信息增益 对样本数据进行分组统计，我们可以得到一下数据： 从上面的统计数据我们可以计算出整体熵和各个特征对应的条件熵，由于上面我们已经计算了长相条件下的条件熵，在此计算性格的条件熵。 首先计算整体熵为： H（D）=-1/2 * log(1/2)-1/2 * log(1/2)=0.693 其次计算性格特征不同特征值的条件熵： H（D|A(性格)=‘不好’）=4/12 * (-1/4 * log(1/4)-3/4 * log(3/4)）=0.187 H（D|A(性格)=‘好’）=6/12 * (-3/6* log(3/6)-3/6 * log(3/6))=0.346 H（D|A(性格)=‘很好’）=2/12 * (-2/2* log(2/2)-0/2 * log(0/2))=0 则性格特征的条件熵为： H（D|A=性格）= 0.187+0.346+0 = 0.533 由此得出性格特征的信息增益为： g(D,A=性格) = H(D)-H(D|A=性格) = 0.693-0.533 = 0.460 其他特征信息增益可自行计算。 3.4 信息增益率 特征A对训练数据集D的信息增益率gR(D,A)定义为其信息增益g(D,A)与训练数据集D关于特征A的值的熵HA(D)之比，即： 注意区别H(D|A)、HA(D) 我们继续使用上述样本来计算特征的信息增益率。参考链接 上面我们已经计算出了性格特征的信息增益： g(D,A=性格) = 0.460 那么依据公式，只要计算HA(D)就可以求出性格特征的信息增益率，HA(D)即为特征A的熵，那么： HA(D)=-4/12 * log(4/12)-6/12 * log(6/12)-2/12 * log(2/12)=1.011 最后有，性格特征的信息增益率得： gR(D,A=性格) =g(D,A=性格) / HA(D)=0.46/1.011=0.455 注：信息增益率相当于是给信息增益增加了一个惩罚项，因为信息增益更偏向于选择特征值较多的特征（比较极端的例子就是，当一个特征的特征值和样本数量一样多的时候，如上面的序号作为特征的话，该特征的条件熵即为0，它的信息增益即为整体熵）。 3.5 基尼系数 基尼指数Gini(D)表示集合D不确定性，基尼指数Gini(D，A=a)表示集合D经A=a分割后的不确定性(类似于熵)，基尼指数越小，样本的不确定性越小。 分类问题中，假设有K个类，样本点属于第k类的概率为pk,则概率分布的基尼指数定义为： 如果样本集合D根据特征A是否取某一可能值a被分割成D1和D2两部分，即： 则在特征A的条件下,集合D的基尼指数定义为： 还是以上面样本为例计算各特征的基尼系数。参考链接 还是以性格特征为例计算，其包含三个特征值，即可将样本分成三份。首先根据上面公式计算出概率分布的基尼指数： Gini(D1:不好)=1-（1/4 * 1/4+3/4 * 3/4）=0.375 Gini(D2:好)=1-（3/6 * 3/6+3/6 * 3/6）=0.5 Gini(D3:很好)=1-（2/2 * 2/2+0/2 * 0/2）=0 从而得出在性格特征条件下，样本集合D的基尼系数为： Gini(D,A=‘性格’)=4/12 * 0.375+6/12 * 0.5+2/12 * 0=0.375 总结：基尼系数越低表示系统的混乱程度越低（纯度越高），区分度越高，越适合用于分类预测。 3.6 相对熵(KL散度) 相对熵可以用来衡量两个概率分布之间的差异，上面公式的意义就是求 p 与 q之间的对数差在 p上的期望值: 3.7 交叉熵 交叉熵和熵的定义类似，不同的是，熵只涉及一个随机变量的概率分布，而交叉熵涉及两个随机变量概率分布。 对于离散型随机变量，交叉熵定义为： 其中x为离散型随机变量，p(x)和q(x)是它的两个概率分布。交叉熵衡量了两个概率分布的差异。其值越大，两个概率分布相差越大；其值越小，则两个概率分布的差异越小。 对于连续型随机变量，交叉熵定义为: 如果两个概率分布完全相等，则交叉熵退化成熵，此时交叉熵有极小值。详细解答及证明：熵和交叉熵 四、连续值处理 连续值的选取不再是简单的有限的1，2，3等等，无法用暴力枚举的方式计算。因此第一步就是要把连续值进行离散化，常用的离散化策略是二分法。参考链接 第一步：将连续属性 a 在样本集 D 上出现 n 个不同的取值从小到大排列，记为 a 1 , a 2 , …, an。基于划分点t，可将D分为子集Dt +和Dt-，其中Dt-包含那些在属性a上取值不大于t的样本，Dt+包含那些在属性 a上取值大于t的样本。考虑包含n-1个元素的候选划分点集合即把区间[a i , a i-1) 的中位点 (a i+a i-1)/2作为候选划分点 第二步：采用离散属性值方法，计算这些划分点的增益，选取最优的划分点进行样本集合的划分：其中Gain(D, a, t)是样本集D基于划分点 t 二分后的信息增益，于是， 就可选择使Gain(D, a, t)最大化的划分点。还可以使用信息增益率或基尼系数进行划分。 以西瓜书为例，数据如下： 以密度为例： 步骤一:首先将密度的特征值从小到大进行排序 0.2430 0.2450 0.3430 0.3600 0.4030 0.4370 0.4810 0.5560 0.5930 0.6080 0.6340 0.6390 0.6570 0.6660 0.6970 0.7190 0.7740 取相邻两个数的平均值，17个数据将会有16个结果： 候选值：0.2440 0.2940 0.3515 0.3815 0.4200 0.4590 0.5185 0.5745 0.5855 0.6210 0.6365 0.6480 0.6615 0.7080 0.7465 步骤二:计算各候选值的增益 推荐链接
发表评论