决策表（决策树）回归vs 回溯

决策树）回归vs 回溯"/>

决策表（决策树）回归vs 回溯

一：回溯法

1.概念
回溯法也称试探法，它的基本思想是:从问题的某一种状态(初始状态)出发，搜索从这种状态出发所能达到的所有"状态"，当一条路走到"尽头"的时候(不能再前进)，再后退一步或若干步，从另一种可能"状态"出发，继续搜索，直到所有的"路径"(状态)都试探过。这种不断"前进"、不断"回溯"寻找解的方法，就称作"回溯法"。
2.步骤
用回溯算法解决问题的一般步骤为:
一、定义一个解空间，它包含问题的解。
二、利用适于搜索的方法组织解空间。
三、利用深度优先法搜索解空间。
四、利用限界函数避免移动到不可能产生解的子空间。问题的解空间通常是在搜索问题的解的过程中动态产生的，这是回溯算法的一个重要特性。

回溯法是一个既带有系统性又带有跳跃性的的搜索算法。它在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树。算法搜索至解空间树的任一结点时，总是先判断该结点是否肯定不包含问题的解。如果肯定不包含，则跳过对以该结点为根的子树的系统搜索，逐层向其祖先结点回溯。否则，进入该子树，继续按深度优先的策略进行搜索。回溯法在用来求问题的所有解时，要回溯到根，且根结点的所有子树都已被搜索遍才结束。而回溯法在用来求问题的任一解时，只要搜索到问题的一个解就可以结束。这种以深度优先的方式系统地搜索问题的解的算法称为回溯法，它适用于解一些组合数较大的问题.
回溯是一种常用的调试方法,当调试小程序时这种方法是非常有效的,具体做法是,从发现症状的地方开始,人工沿程序的控制流往回追踪分析源程序代码,直到找出错误原因为止.随着程序规模的扩大,应该回溯的路径数目也变得越来越大,以至彻底回溯是不可能的.
回溯法按深度优先策略搜索问题的解空间树。首先从根节点出发搜索解空间树，当算法搜索至解空间树的某一节点时，先利用剪枝函数判断该节点是否可行（即能得到问题的解）。如果不可行，则跳过对该节点为根的子树的搜索，逐层向其祖先节点回溯；否则，进入该子树，继续按深度优先策略搜索。
回溯法的基本行为是搜索，搜索过程使用剪枝函数来为了避免无效的搜索。剪枝函数包括两类：1. 使用约束函数，剪去不满足约束条件的路径；2.使用限界函数，剪去不能得到最优解的路径。
问题的关键在于如何定义问题的解空间，转化成树（即解空间树）。解空间树分为两种：子集树和排列树。两种在算法结构和思路上大体相同。

应用
当问题是要求满足某种性质（约束条件）的所有解或最优解时，往往使用回溯法。

二：回归

回归测试是指修改了旧代码后，重新进行测试以确认修改没有引入新的错误或导致其他代码产生错误。自动回归测试将大幅降低系统测试、维护升级等阶段的成本。回归测试作为软件生命周期的一个组成部分，在整个软件测试过程中占有很大的工作量比重，软件开发的各个阶段都会进行多次回归测试。在渐进和快速迭代开发中，新版本的连续发布使回归测试进行的更加频繁，而在极端编程方法中，更是要求每天都进行若干次回归测试。因此，通过选择正确的回归测试策略来改进回归测试的效率和有效性是非常有意义的。
回归测试的场景：
1.开发修改完bug之后：
a.测试同学需要将之前发现bug的用例再次执行一遍，已验证此问题已经修复，然后关闭对应的bug单，写明必要备注
b.验证其他和此bug有依赖关系的场景用例是否正常
2.迭代上线前：
每个迭代不同模块肯定有很多不同类型的bug,在前面场景1中都是零零散散的回归了开发修复的bug，等到最后上线时，往往我们会再进行一次回归测试
范围：本次迭代全部场景
方法：抽取其中部分用例做为回归测试用例
执行：再次执行抽取的测试用例，记录结果
抽取回归测试用例技巧：
1、如果系统目前为止已经比较稳定，那回归测试的用例，可以根据8/2原则来挑选（80%的缺陷出现在20%的功能模块中），可以根据各模块缺陷的情况，将出现问题较多的模块进行执行用例；其他缺陷不多的模块，可以将缺陷相应的功能点进行用例执行；
2、业务程度较复杂的，用户使用较频繁的功能模块进行回归测试；
3、开发近期对某个功能模块进行了小功能的修改时，也需要进行回归测试，因为开发进行功能点修改或者优化时，不怕一万就怕万一，所以进行回归测试，保守一点。

三：决策表

1.定义
决策表又称判断表，是一种呈表格状的图形工具，适用于描述处理判断条件较多，各条件又相互组合、有多种决策方案的情况。精确而简洁描述复杂逻辑的方式，将多个条件与这些条件满足后要执行动作相对应。但不同于传统程序语言中的控制语句，决策表能将多个独立的条件和多个动作直接的联系清晰的表示出来。
2：结构
决策表一般分为4个部分。 每个条件对应一个变量、关系或预测，"候选条件"就是它们所有可能的值;动作指要执行的过程或操作;动作入口指根据该入口所对应的候选条件集，是否或按怎样的顺序执行动作。 许多决策表在候选条件中使用"不关心"符号来化简决策表，尤其是当某一条件对应要执行的动作影响很小时。有时，所有的条件在开始时都被认为是重要的，但最后却发现没有一个条件对执行的动作有影响，都是无关的条件。

在这4个部分的基础上，决策表根据候选条件和动作入口的表现方法的变化而变化。有些决策表使用true/false作为候选条件值(类似与if-then-else)，有些使用数字(类似于switch-case)，有些甚至使用模糊值或概率值。对应动作入口，可以简单的表示为动作是否执行(检查动作执行)，或更高级些，罗列出要执行的动作(为执行的动作排序)。
3：优点
决策表能罗列出所有的可能情况，并清晰的指出相应的处理方式，用户不需要考虑其中的逻辑关系就能一眼看出其中什么样的动作对应什么样的情况，这比程序语言中层层嵌套的逻辑语句要强多了。而所有可能情况的平面罗列，也能避免在程序语言编写中，因为逻辑上的层层嵌套而产生遗漏，尤其在if-then-else结构中else部分是可选的情况下。
因为逻辑控制在编程中的重要地位，决策表成为设计逻辑控制时十分重要的一个工具。

四：决策树

1：定义
决策树(Decision Tree)是在已知各种情况发生概率的基础上，通过构成决策树来求取净现值的期望值大于等于零的概率，评价项目风险，判断其可行性的决策分析方法，是直观运用概率分析的一种图解法。由于这种决策分支画成图形很像一棵树的枝干，故称决策树。在机器学习中，决策树是一个预测模型，他代表的是对象属性与对象值之间的一种映射关系。Entropy = 系统的凌乱程度，使用算法ID3, C4.5和C5.0生成树算法使用熵。这一度量是基于信息学理论中熵的概念。

决策树是一种树形结构，其中每个内部节点表示一个属性上的测试，每个分支代表一个测试输出，每个叶节点代表一种类别。

分类树(决策树)是一种十分常用的分类方法。他是一种监管学习，所谓监管学习就是给定一堆样本，每个样本都有一组属性和一个类别，这些类别是事先确定的，那么通过学习得到一个分类器，这个分类器能够对新出现的对象给出正确的分类。这样的机器学习就被称之为监督学习。
2：组成
（1）决策点，是对几种可能方案的选择，即最后选择的最佳方案。以决策树根部的决策点为最终决策方案。
（2）状态节点，代表备选方案的经济效果(期望值)，通过各状态节点的经济效果的对比，按照一定的决策标准就可以选出最佳方案。由状态节点引出的分支称为概率枝，概率枝的数目表示可能出现的自然状态数目每个分枝上要注明该状态出现的概率。
（3）结果节点，将每个方案在各种自然状态下取得的损益值标注于结果节点的右端。
3：优点
决策树易于理解和实现，人们在在学习过程中不需要使用者了解很多的背景知识，这同时是它的能够直接体现数据的特点，只要通过解释后都有能力去理解决策树所表达的意义。
对于决策树，数据的准备往往是简单或者是不必要的，而且能够同时处理数据型和常规型属性，在相对短的时间内能够对大型数据源做出可行且效果良好的结果。
易于通过静态测试来对模型进行评测，可以测定模型可信度;如果给定一个观察的模型，那么根据所产生的决策树很容易推出相应的逻辑表达式。
4:缺点
1)对连续性的字段比较难预测。
2)对有时间顺序的数据，需要很多预处理的工作。
3)当类别太多时，错误可能就会增加的比较快。
4)一般的算法分类的时候，只是根据一个字段来分类。