影楼网站模版,网址导航怎么删除,怎么搞到网站,制作照片视频的软件5.1 决策树模型与学习 说起决策树来#xff0c;它不是一般的树#xff0c;而是有理想有抱负的树#xff0c;那么为什么这么讲呐#xff1f;
5.1.1 思维模式 人类有两大逻辑思维#xff1a;归纳法和演绎法。决策树是为了实现某一个目标而构建的树形结构。 我想看…5.1 决策树模型与学习 说起决策树来它不是一般的树而是有理想有抱负的树那么为什么这么讲呐
5.1.1 思维模式 人类有两大逻辑思维归纳法和演绎法。决策树是为了实现某一个目标而构建的树形结构。 我想看一下情人节这一天大家是怎么过的以这个例子为例建立一棵决策树 由于是情人节我们首先需要考虑的是是否是单身。 如果不是单身那么当天的活动安排就要将对方考虑在内如果对方需要陪伴那么就是各种花式虐狗行为了如果不需要陪伴就要看你当天是否有任务如果有任务我们就安排去学习没有任务的话就安排一些娱乐活动了比如男生喜欢打游戏女生则刷刷剧。 如果是单身可能会考虑提升自我想提升自我的小伙伴可能会考虑内修还是外练想要内在气质提升就可能会去学习想提升外在就可能去运动还有一些在情人节不想提升自己的小伙伴可能会去娱乐。 以上就是一棵决策树当然这是我们主观构造的决策树现实生活中可能会更加复杂。kd树是二叉树而决策树是多叉树。 现在我们看一个客观的例子这是一个是否可以放贷款的例子 5.1.2 模式结构 分类决策树模型是一种描述对实例进行分类的树形结构。 决策树由结点和有向边组成结点又有内部结点和叶结点组成其中内部结点用圆圈表示叶结点用方框表示。内部结点表示特征或属性叶结点表示类别。 决策树是通过一系列规则if-then对数据进行分类的过程。其实从本质上来说决策树就是从根节点到叶节点的过程。从根节点出发到叶节点所经过的称为路径而这条路径就对应着一条规则这条规则是用if-then组成的。 先判断是否是单身如果不是的话看对方是否需要陪伴如果不需要陪伴看你是否有任务如果有任务的话就得到一个学习的活动安排。 我们现在看一下是不是每一个叶节点都对应着一个规则呢是的每一个叶节点都对应着一个规则而且每一个叶节点所对应的规则都不一样。一个叶节点或一个类它可能对应多条路径但是每一个实例都对应着一条路径。 If-then规则是互斥且完备的。互斥是指这个属性所分的叉它是互相之间没有交集完备是指分完地叉合在一起是合集。 构建决策树的规则如下 5.1.3 条件概率分布 对于决策树而言表示给定特征条件下类的条件概率分布P(Y|X)这就是说决策树可以表示成在给定的特征条件下类的条件概率分布而条件概率分布对应着特征空间的一个划分如果我们有十个条件概率分布对应着特征空间的十个划分其实就相当于我们构建了十棵决策树至于哪一棵决策树表现更好就要看决策树学习了。 特征空间是由特征向量组成的而特征向量用来表示输入的每一个实例所以一般情况下我们可以认为输入空间与特征空间是相同的。比如说下图中所表示的特征空间是。我们想要得到一个决策树就需要将这个特征空间划分出来划分完成后就得到了一个完整的条件概率分布了。 在划分时我们所得到的单元或区域是互不相交的而且这些单元或者区域合在一起就是我们的整个特征空间。 我们在讲决策树的规则时是这样解释路径的互斥和完备的而且恰好这里的每一个单元其实就是对应着我们之前讲的if-then规则的集合所组成的一条路径一个单元对应着一条路径。 假如说我们现在已经完成了对特征空间的划分将其划分为一个又一个的小单元或小区域可是每个单元或者区域它所对应的类别是怎么确定的呐比如说某个单元c的条件概率满足时认为该单元属于正类;某个单元c的条件概率满足时认为该单元属于负类。 我们现在由刚才看到的一个平面图变换成一个立体图形来看 这个立体图形中包含了y1的条件概率我们看一下对于用红色记号标记的区域而言y1的条件概率是大于0.5这个区域就是正类对于用蓝色记号标记的区域而言y1的条件概率是小于0.5这个区域就是负类对于黑色记号标记的区域而言y1的条件概率是大于0.5这个区域就是正类。 现在我们一直讲的是两个类别的分类所以只需要与0.5比大小就可以了如果我们分了多个类我们只需呀看一下它们分别的条件概率哪一个类的条件概率大那么就属于哪一个类。 假如我们将特征空间划分成四个单元这四个单元命名如下 这四个单元在决策树中如下 这就说明对于决策树而言特征空间中所划分的每一个单元都对应着决策树中的一条路径决策树的条件概率分布由各个单元给定条件下类的条件概率分布组成。
5.1.4 决策树学习 已知训练集其中i1,2,...,N 目的构造决策树并对实例正确分类 我们看一个贷款申请的例子 在这个例子中我们发现有三个特征n3年收入、房产、婚姻状况两种类别k2可以偿还、无法偿还。假如我们现在已经根据数据集T得到了这棵决策树现在我们判一下实例年收入为75万为无房产婚姻状况为单身。对于这个实例而言我们根据决策树可以得到的类别是无法偿还。 构造决策树过程中产生的问题有
1.我们根据同一个训练数据集可以构造出几种决策树
2.在构造决策树过程中以首选哪一个特征进行分类第二个、第三个特征又是怎么确定的
3.如果我们有一个复杂的决策树我们应该怎么办 决策树的本质就是从训练数据集T中归纳出一组分类规则这组规则要与训练数据集不相矛盾。我们可能能训练出无穷多个条件概率模型一棵好的决策树与训练数据矛盾较小对已知数据的拟合能力强同时具有很好的泛化能力对未知数据的预测能力。 我们怎样训练出一个模型呐它的策略就是通过最小化损失函数来实现而有可能是有无穷多个决策树决策树树与决策树之间是有区别的也就是每次选择的特征可能不一样。如何选择最优特征就是特征选择递归选择最优特征将要面临的问题。当对应特征空间有了基本划分直到所有的训练子集被基本正确划分类就停止我们的算法之所以这里强调“基本正确分类”而不是“全部正确分类”其实就是为了避免过拟合为了平衡拟合能力和泛化能力。如果决策树过于枝繁叶茂为了避免过拟合具有更好的泛化能力就需要剪枝。 剪枝可以分为预剪枝和后剪枝。预剪枝比如我们要经营一片果园我们的目的是想结果所以果农通常需要修剪果树使果树不要过高。这样既利于果子得到充足的营养又避免果树过高而难以采摘这是在树成长前剪枝。后剪枝园艺工人为大树修剪特定的形状这是在树成长后进行剪枝。
5.2 特征选择 我们为什么要对决策树进行特征选择我们怎样选择出最优的特征
5.2.1 特征选择问题 我们来看一个例子这是一个由15个样本组成的贷款申请训练数据。数据包括贷款申请人的4个特征第1个特征是年龄有3个可能值青年中年老年第2个特征是有工作有2个可能值是否第3个特征是有自己的房子有两个可能值是否第4个特征是信贷情况有两个可能值非常好好一般。有两个类别可能值为是否。 希望通过对所给的训练数据学习一个贷款申请的决策树用以对未来的贷款申请进行分类即当新的客户提出贷款申请时根据申请人的特征利用决策树决定是否批准贷款申请。 如果我们第一个特征选择年龄的话可以得到下面这样的决策树 如果以有无工作这个特征作为第一个特征构建决策树绘制出来的决策树如下 根据上面这两个决策树我们发现当我们逊选择不同的特征作为决策树的第一个特征进行构建所构建出来的决策树是不一样的。当选择年龄作为决策树的一个个特征我们发现决策树比较复杂当选择有无工作作为决策树的第一个特征我们发现构建的决策树比较简单。那么我们该如何选择最优特征呐
5.2.2 信息增益 信息增益由熵构建而成熵用来表示随机变量的不确定性。如果随机变量有n个取值的话每个取值所对应的概率是那么这个随机变量x的熵由于此处的熵是和随机变量x的分布有关系所以也可以表示成这个p就对应着随机变量的分布。 当随机变量的取值等概率分布的时候相应的熵最大。为什么随机变量的取值等概率分布的时候最大呐我们通过一个简答的例子计算一下。 假如我们此处的随机变量只有两个取值一个是1一个是0x取1的概率是p取0的概率是q1-p这个随机变量x所对应的熵绘制p和H(p)的图形如下 当p0.5时熵取最大值H(p)1除了通过图像的方式知道最大值还可以通过求导的方式得到最大值。当是凹函数时可以用求导的方式取得最大值当时凸函数时可以用求导的方式得到最小值。 条件熵。当熵和条件熵中的概率是由数据估计得到时则为经验熵和经验条件熵当熵和条件熵中的概率对应着真是分布的时候那就是理性熵和真是条件熵。信息增益就是熵减去条件熵而熵和条件熵都是根据训练数据集计算出来的经验熵和经验条件熵即。 为什么用这样一个差值代表信息增益上式所对应的D就是训练数据集H(D)是我们在不知道任何信息的情况下得到的熵假如我们知道x的某个特征信息A在已知特征信息的情况下训练数据集有了一个重新的分类此时所对应的熵就是根据这个特征信息A而发生的变化。变化越大就说明由于增加了A特征而更加确定。因此哪一个特征所带来的信息增益越大就应该选择哪一个特征作为最优特征。这就是信息增益的作用。 我们具体看一下怎样对信息增益进行求解
我们现在知道训练数据集D和特征A期望得到特征A关于D的信息增益g(D,A)。首先计算经验熵再计算经验条件熵信息增益就是经验熵减去经验条件熵。 现在通过例题看一下信息增益的计算继续以贷款例子为例 经验熵公式为
我们把这个训练集记作D其中包含15个样本如果不加任何特征的话我们最终想分为两个类别不同意贷款同意贷款所以类别 K2对应不附加任何特征的情况下它所分的类别。假如对应不同意贷款我们发现其中包含了6个样本对应着同意贷款包含9个样本。这里的经验熵是根据训练数据集计算出来的也就是说这个概率是根据D得到的。根据这个训练集得到的不同意贷款的概率是同意贷款的概率是所以此处的经验熵这是不加任何特征的情况下所得到的训练数据集的熵。 接下来我们分别看一下当我们加上特征的时候所得到的经验熵是多少这时候计算的就是经验条件熵。假如说我们现在加入年龄这一个特征我们发现根据年龄这一个特征可以将原本的训练数据集D划分为3个子集有5个青年子集其中有3个样本是不同意贷款2个样本是同意贷款5个中年子集其中有2个样本是不同意贷款3个样本是同意贷款5个老年子集其中有1个样本是不同意贷款4个样本是同意贷款。具体如下表 下面我们就可以计算经验条件熵了。经验条件熵就是在给定特征A后所得到的n个子集每个子集计算它的熵然后进行加权求和。那么我们在给定年龄这个特征的时候它划分出3个子集所以n3每个权重就是中所包含的样本个数与训练数据集D中样本个数的比例。 下面我们看一下“有工作”这一个特征。我们可以将训练数据集分成2个子集 对应有工作有5个样本个数对应无工作有10个样本个数。 下面我们看一下“有工房子”这一个特征。我们可以将训练数据集分成2个子集
对应有自己的房子有6个样本个数对应没有自己的房子有9个样本个数。 下面我们看一下“信贷情况”这一个特征。我们可以将训练数据集分成3个子集
对应信贷情况非常好有4个样本个数对应信贷情况好有6个样本个数对应信贷情况一般有5个样本个数。 因此相应的信息熵、信息经验熵、信息增益如下 5.2.3 信息增益比 除了信息增益还可以通过信息增益比来选择最优特征。为什么有了信息增益还要定义一个信息增益比这是因为信息增益有时候更倾向于选择具有更多取值的特征比如说信贷情况有3个取值有工作有两种取值那么这时候信贷情况的取值个数是多于有工作的取值个数的。由于信贷情况的取值个数较多有可能由于这个原因造成它的信息增益是大于有工作的。信息增益比就可以降低由于特征取值较多所造成影响。信息增益比就是在信息增益的基础上增加一个惩罚项。这个惩罚项就是训练数据集D关于特征A的熵的倒数信息增益比是 算出的信息增益比如下 对比“有工作”和“信贷情况” 这两个特征的信息增益我们会选择信息增益较大的“信贷情况”作为最优特征也就是选择信贷情况这个值可以带来更大的确定性如果引入信息增益比来消除特征个数的不同所带来的影响这时候选择“有工作”这个特征来作为最优特征。 对于信息增益和信息增益比这两个孰优孰劣信息增益的缺点是倾向于选择取值较多的特征而信息增益比倾向于选择取值较少的特征。选择哪一个需要根据实际情况而定。
5.3 决策树的生成
5.3.1 ID3算法 ID3算法是使用信息增益进行特征选择。 ID3算法如下
输入训练数据集D、特征集A、阈值
输出决策树T
1判断T是否需要选择特征生成决策树。 不需要进行特征选择 ①如果所有的实例点都属于同一个类则T是单结点树记录实例类别以此作为该节点的类标记。例如现在有10天的天气数据 每一天的数据包含了湿度、温度、风力等特征但是这10天都是晴天也及时这些实例点都属于同一类。 ②当特征集时则T是单结点树记录实例个数最多类别以此作为该节点的类标记。假如现在有10天的天气数据其中8天是晴天2天不是晴天除此之外没有关于天气的任何特征数据。没有特征。自然就不需要特征选择了。 需要进行特征选择就计算A中各特征的信息增益并选择信息增益最大的特征: ①若的信息增益小于则说明这个特征并不会给分类带来更多的确定性也就是说它并没有有助于分类。既然这个信息增益最大的特征对分类都没有很大的帮助就更别说其他特征了。这时我们可以认为这棵决策树是一个单结点树记录D中实例点个数最多类别以此作为该结点的类标记。 ②若的信息增益大于我们可以将训练数据集D根据这个特征的所有可能取值划分为若干个非空子集将中实例个数最多的类别作为标记构建子节点
2第i个子节点以为训练集为特征集合递归地调用以上步骤直到为单一结点后停止。 下面我们看一个例子 这是一个贷款申请的数据集。这个数据集中包含了15个训练样本其中有9个是同意贷款6个是不同意贷款这说明所有的实例点并不属于同一个类这个训练样本集包含了4个特征说明特征集A不是空集因此这并不是一个单节点的决策树我们需要进行下一步的判断。 接下来我们计算每一个特征所对应的信息增益 我们发现这里的信息增益值是比较大的也就是说即使我们人为的给定一个阈值比如那么这里的四个信息增益值没有一个是小于阈值的所以依然不可以认为这是一个单节点的决策树我们需要选择信息增益最大的进行决策树的生成。 这里信息增益最大的特征是“有自己的房子”我们现在就将根节点确定下来了。 当“有自己的房子”将整个训练集D划分为和时中的所有实例都是同意贷款的而中有6个是同意贷款的3个不同意贷款。 我们画一个这个决策树如下 根节点处就是有自己的房子如果有自己的房子那么所对应到的所有实例都是同意贷款那么就得到一个叶子结点同意贷款的类别但如果没有自己的房子这时候所对应的既有同意贷款又有不同意贷款我们就需要根据特征选择来找到这个内部结点所对应的特征。 下面我们就以作为新的训练数据集作为新的特征集来计算各个特征的信息增益。 计算的信息增益。其中
经验熵
经验条件熵
信息增益为0.251 我们接下来算一下第二个特征也就是对“有工作”这个特征而言 经验条件熵
信息增益为0.918 接下来计算“信贷情况”这个特征的经验条件熵
经验条件熵
信息增益为0.474 现在我们整理一下 我们发现“有工作”这个特征所对应的信息增益最大所以我们接下来的内部节点就对应着“有工作”这个特征相应的决策树如下 我们发现对于这个例题而言整棵决策树只用了两个特征这是因为我们在选择了第二个特征后所得到的两个小子集都是同属于同一类别的所以就停止了。
5.3.2 C4.5算法 C4.5算法是使用信息增益比进行特征选择。C4.5算法是非常有名的算法。 C4.5算法就是将上述ID3算法的信息增益改成信息增益比。使用信息增益比来构建决策树它可以克服之前信息增益选择特征时可能会偏向取值较多的特征的问题而且相较于ID3算法C4.5算法不仅可以处理离散型的描述特征还可以处理连续型的。所以说C4.5算法在继承ID3算法的一些优点外还有自己的优点。不过C4.5算法也有一定的缺点信息增益比的计算麻烦尤其实是在处理连续型变量时。因此C4.5算法虽然解释起来比较容易但是在决策树的生成过程中需要对数据进行多次的顺序扫描和排序导致算法的低效性。也就是说当我们的数据量非常大时这个程序很难运行。
