上海个人网站备案,网站百度排名优化,微信公众平台小程序管理在哪里,如何将音乐上传到wordpress决策树原理
决策树是从训练数据中学习得出一个树状结构的模型。 决策树属于判别模型。 决策树是一种树状结构#xff0c;通过做出一系列决策#xff08;选择#xff09;来对数据进行划分#xff0c;这类似于针对一系列问题进行选择。决策树的决策过程就是从根节点开始通过做出一系列决策选择来对数据进行划分这类似于针对一系列问题进行选择。决策树的决策过程就是从根节点开始测试待分类项中对应的特征属性并按照其值选择输出分支直到叶子节点将叶子节点的存放的类别作为决策结果。 以下小美相亲的例子就是决策树 决策树算法是一种归纳分类算法它通过对训练集的学习挖掘 出有用的规则用于对新数据进行预测。 决策树算法属于监督学习方法。 决策树归纳的基本算法是贪心算法自顶向下来构建决策树。 贪心算法在每一步选择中都采取在当前状态下最好/优的选择。 在决策树的生成过程中分割方法即属性选择的度量是关键。
决策树的优点 推理过程容易理解计算简单可解释性强。 比较适合处理有缺失属性的样本。 可自动忽略目标变量没有贡献的属性变量也为判断属性变量的重要性 减少变量的数目提供参考。决策树的缺点 容易造成过拟合需要采用剪枝操作。 忽略了数据之间的相关性。 对于各类别样本数量不一致的数据信息增益会偏向于那些更多数值的特征。决策树的三种基本类型 建立决策树的关键即在当前状态下选择哪个属性作为分类依据。根据不同的目标函数 建立决策树主要有以下三种算法 ID3(IterativeDichotomiser)、C4.5、CART(Classification And Regression Tree)。
ID3算法
ID3 算法最早是由罗斯昆J. Ross Quinlan于1975年提出的一种决策树构建算法算法的核心是“信息熵”期望信息越小信息熵越大样本纯度越低。。 ID3 算法是以信息论为基础以信息增益为衡量标准从而实现对数据的归纳分类。 ID3 算法计算每个属性的信息增益并选取具有最高增益的属性作为给定的测试属性。
ID3算法的大致步骤
初始化特征集合和数据集合计算数据集合信息熵和所有特征的条件熵选择信息增益最大的特征作为当前决策节点更新数据集合和特征集合删除上一步使用的特征并按照特征值来划分不同分支的数据集合重复 23 两步若子集值包含单一特征则为分支叶子节点
ID3算法的缺点 ID3 没有剪枝策略容易过拟合 信息增益准则对可取值数目较多的特征有所偏好类似“编号”的特征其信息增益接近于 1 只能用于处理离散分布的特征 没有考虑缺失值
C4.5算法
C4.5 算法是 Ross 对 ID3 算法的改进。 用信息增益率来选择属性。ID3选择属性用的是子树的信息增益而C4.5用的是信息增益率。 在决策树构造过程中进行剪枝。 对非离散数据也能处理。 能够对不完整数据进行处理。
过拟合的原因 为了尽可能正确分类训练样本节点的划分过程会不断重复直到不能再分这样就可能对训练样本学习的“太好”了把训练样本的一些特点当做所有数据都具有的一般性质从而导致过拟合。 剪枝的基本策略有“预剪枝”prepruning和“后剪枝”post-pruning通过剪枝处理去掉一些分支来降低过拟合的风险。
预剪枝prepruning
预剪枝不仅可以降低过拟合的风险而且还可以减少训练时间但另一方面它是基于“贪心”策略会带来欠拟合风险。
剪枝策略 在节点划分前来确定是否继续增长及早停止增长 主要方法有 • 节点内数据样本低于某一阈值 • 所有节点特征都已分裂 • 节点划分前准确率比划分后准确率高。
后剪枝
在已经生成的决策树上进行剪枝从而得到简化版的剪枝决策树。后剪枝决策树通常比预剪枝决策树保留了更多的分支。一般情况下后剪枝的欠拟合风险更小泛化性能往往优于预剪枝决策树
剪枝方法 在已经生成的决策树上进行剪枝从而得到简化版的剪枝决策树。 C4.5 采用的悲观剪枝方法用递归的方式从低往上针对每一个非叶子节点评估用一个最佳叶子节点去代替这课子树是否有益。如果剪枝后与剪枝前相比其错误率是保持或者下降则这棵子树就可以被替换掉。C4.5 通过训练数据集上的错误分类数量来估算未知样本上的错误率。 后剪枝决策树的欠拟合风险很小泛化性能往往优于预剪枝决策树。 缺点 • 剪枝策略可以再优化 • C4.5 用的是多叉树用二叉树效率更高 • C4.5 只能用于分类 • C4.5 使用的熵模型拥有大量耗时的对数运算连续值还有排序运算 • C4.5 在构造树的过程中对数值属性值需要按照其大小进行排序从中选择一个分割点所以只适合于能够驻留于内存的数据集当训练集大得无法在内存容纳时程序无法运行。
CART算法
Classification and Regression Tree (CART) 是决策树的一种。 用基尼指数来选择属性分类或用均方差来选择属性回归。 顾名思义CART算法既可以用于创建分类树也可以用于创建回归树两者在构建的过程中稍有差异。 如果目标变量是离散的称为分类树。 如果目标变量是连续的称为回归树。
CART算法——分类 例子
CART算法——回归
用均方差来选择属性 对于连续值的处理CART 分类树采用基尼系数的大小来度量特征的各个划分点。 对于任意划分特征 对应的任意划分点 两边划分成的数据集 1和2 求出使1和2各自集合的均方差最小同时 1和2的均方差之和最小所对应的特征和特征值划分点。表达式为 其中1为1数据集的样本输出均值2为2 数据集的样本输出均值。
预测方式 对于决策树建立后做预测的方式上面讲到了 CART 分类树采用叶子节点里概率最大的类别作为当前节点的预测类别。 而回归树输出不是类别它采用的是用最终叶子的均值或者中位数来预测输出结果
CART算法采用一种“基于代价复杂度的剪枝”方法进行后剪枝这种方法会生成一系列树每个树都是通过将前面的树的某个或某些子树替换成一个叶节点而得到的这一系列树中的最后一棵树仅含一个用来预测类别的叶节点。然后用一种成本复杂度的度量准则来判断哪棵子树应该被一个预测类别值的叶节点所代替。 这种方法需要使用一个单独的测试数据集来评估所有的树根据它们在测试数据集熵的分类性能选出最佳的树。
CART剪枝具体流程: (1)计算每一个结点的条件熵 (2)递归的从叶子节点开始往上遍历,减掉叶子节点,然后判断损失函数的值是否减少,如果减少,则将父节点作为新的叶子节点 (3)重复(2),直到完全不能剪枝.
决策树的差异
划分标准的差异 ID3 使用信息增益偏向特征值多的特征C4.5 使用信息增益率克服信息增益的缺点偏向于特征值小的特征CART 使用基尼指数克服, C4.5 需要求 log 的巨大计算量偏向于特征值较多的特征。使用场景的差异 ID3 和 C4.5 都只能用于分类问题CART 可以用于分类和回归问题ID3 和 C4.5 是多叉树速度较慢CART 是二叉树计算速度很快样本数据的差异 ID3 只能处理离散数据且缺失值敏感C4.5 和 CART 可以处理连续性数据且有多种方式处理缺失值从样本量考虑的话小样本建议 C4.5、大样本建议 CART。C4.5 处理过程中需对数据集进行多次扫描排序处理成本耗时较高而 CART 本身是一种大样本的统计方法小样本处理下泛化误差较大 样本特征的差异 ID3 和 C4.5 层级之间只使用一次特征CART 可多次重复使用特征剪枝策略的差异 ID3 没有剪枝策略C4.5 是通过悲观剪枝策略来修正树的准确性而 CART 是通过代价复杂度剪枝
