决策树（DecisionTree）简介
决策树(Decision Tree)及其变种是另⼀类将输⼊空间分成不同的区域，每个区域有独⽴参数的算法。决策树分类算法是⼀种基于实例的归纳学习⽅法，它能从给定的⽆序的训练样本中，提炼出树型的分类模型。树中的每个⾮叶⼦节点记录了使⽤哪个特征来进⾏类别的判断，每个叶⼦节点则代表了最后判断的类别。根节点到每个叶⼦节点均形成⼀条分类的路径规则。⽽对新的样本进⾏测试时，只需要从根节点开始，在每个分⽀节点进⾏测试，沿着相应的分⽀递归地进⼊⼦树再测试，⼀直到达叶⼦节点，该叶⼦节点所代表的类别即是当前测试样本的预测类别。
卫浴排行榜与其它机器学习分类算法相⽐较，决策树分类算法相对简单，只要训练样本集合能够使⽤特征向量和类别进⾏表⽰，就可以考虑构造决策树分类算法。预测分类算法的复杂度只与决策树的层数有关，是线性的，数据处理效率很⾼，适合于实时分类的场合。
机器学习中，决策树是⼀个预测模型。它代表的是对象属性与对象值之间的⼀种映射关系。树中每个节点表⽰某个对象，⽽每个分⽀叉路径则代表某个可能的属性值，⽽每个叶节点则对应从根节点到该叶节点所经历的路径所表⽰的对象的值。决策树仅有单⼀输出，若欲有复数输出，可以建⽴独⽴的决策树以处理不同输出。数据挖掘中决策树是⼀种经常要⽤到的技术，可以⽤于分析数据，同样也可以⽤来作预测。从数据产⽣决策树的机器学习技术叫做决策树学习，通俗说就是决策树。
决策树算法包括训练和测试两个阶段：在训练阶段，需要采⽤⼀定的标准和规则分割训练样本集为⼏个⼦集，然后再以相同的规则去分割每个⼦集，递归这个过程，直到每个⼦集只含有属于同⼀类的样本时停⽌。训练过程中，每个分割节点需要保存好分类的属性号。在测试阶段中，将测试样本从根节点开始进⾏判别，看该样本属于哪个⼦节点，同样递归地执⾏下去，直到该样本被分到叶节点中为⽌，⽽此时该样本就属于当前叶节点的类别。
痔疮传不传染
由于决策树分类⽅法的不稳定性，在训练样本集中的样本数量较少时，样本集中较⼩的变动也可能会导致决策树结构发⽣很⼤变化。提⾼决策树分类的稳定性，可以采⽤Bagging技术。让决策树算法进⾏多轮的训练，对测试样本的类别预测采⽤投票的⽅式进⾏。运动比赛
360tray决策树的树枝节点表⽰属性，也叫决策节点；树叶节点表⽰类标签，也叫决策结果。决策树是由从上到下的根节点依次延伸⽽成，依据属性阈值的差异性延伸到各个地⽅直⾄下⼀个属性节点，⼀直延长到最后的叶⼦节点完成预测。
决策树是⼀种树形结构，它主要有三种不同的节点：决策节点：它表⽰的是⼀个中间过程，主要是⽤来与⼀个数据集中各个属性的取值作对⽐，以此来判断下⼀步的决策⾛向趋势。状态节点：代表备选⽅案的期望值，通过各个状态节点的对⽐，可以选出最佳的结果。结果节点：它代表的是该类最终属于哪⼀个类别，同时也可以很清晰的看出该模型总共有多少个类别。最终，⼀个数据实例根据各个属性的取值来得到它的决策节点。推广专员
统计学，数据挖掘和机器学习中的决策树训练，使⽤决策树作为预测模型来预测样本的类标。这种决策树也称作分类数或回归数。在这些树的结构⾥，叶⼦节点给出类标⽽内部节点代表某个属性。
决策树学习：根据数据的属性采⽤树状结构建⽴决策模型。决策树模型常常⽤来解决分类和回归问题。机器学习中决策树是⼀个预测模型，它表⽰对象属性和对象值之间的⼀种映射，树中的每⼀个节点表⽰对象属性的判断条件，其分⽀表⽰符号节点条件的对象。树的叶节点表⽰对象所属的预测结果。中国科技开发院
决策树是⼀种监督学习。根据决策树的结构决策树可分为⼆叉决策树和多叉树，例如有的决策树算法只产⽣⼆叉树(其中，每个内部节点正好分叉出两个分⽀)，⽽另外⼀些决策树算法可能产⽣⾮⼆叉树。
决策树是从有类别名称的训练数据集中学习得到的决策树。它是⼀种树形结构的判别树，树内部的每个⾮叶⼦节点表⽰在某个属性的判别条件，每个分⽀表⽰该判别条件的⼀个输出，⽽每个叶⼦节点表⽰⼀个类别名称。树的⾸个节点是跟节点。
在决策树模型构建完成后，应⽤该决策模型对⼀个给定的但类标号未知的元组X进⾏分类是通过测试该元组X的属性值，得到⼀条由根节点到叶⼦节点的路径，⽽叶⼦节点就存放着该元组的类预测。这样就完成了⼀个未知类标号元组数据的分类，同时决策树也可以表⽰成分类规则。
决策树分量算法有构造速度快、结构明显、分类精度⾼等优点。决策树是以实例(Instance)为核⼼的归纳分类⽅法。它从⼀组⽆序的、⽆特殊领域知识的数据集中提取出决策树表现形式的分类规则，包含了分⽀节点、叶⼦节点和分⽀结构。它采⽤⾃顶向下的递归⽅式构造树状结构，在决策时分⽀节点进⾏基于属性值的分类选择，分⽀节点覆盖了可能的分类结果，最终分⽀节点连接了代表分类结果的叶⼦节点。分类过程中经过的连接节点代表了⼀条分类模式，⽽这些分类模式的集合就组成了决策树的框架。
决策树是⼀种以归纳学习为基础的分类算法，它主要包括两个阶段：构造和剪枝。决策树的构建过程是⼀种⾃顶向下、递归分治的过程，从决策表创建决策树的关键步骤就是选择分⽀属性和划分样本集。决策树的剪枝是使决策树停⽌分裂的⽅法之⼀。先剪枝是在决策树⽣成的过程中同时完成剪枝操作，提前停⽌节点的分类。选择合适的测度值是先剪枝算法的关键。先剪枝算法避免了⽆谓的计算量浪费并且可以直接⽣成最终的分类数，因此被普遍采⽤。后剪枝算法是在决策树⾃由⽣长之后，通过指定相应测度值进⾏从分⽀到叶⼦节点的替换。后剪枝策略会加⼤决策树算法的计算量，但分类结果稍微准确。
决策树的剪枝：剪枝是决策树停⽌分⽀的⽅法之⼀，剪枝⼜分预先剪枝和后剪枝两种。后剪枝的计算量代价⽐预剪枝⽅法⼤得多，特别是在⼤样本集中，不过对于⼩样本的情况，后剪枝⽅法还是优于预剪枝⽅法的。
常见决策树分类算法：
(1)、CLS算法：是最原始的决策树分类算法，基本流程是，从⼀棵空数出发，不断的从决策表选取属性加⼊数的⽣长过程中，直到决策树可以满⾜分类要求为⽌。CLS算法存在的主要问题是在新增属性选取时有很⼤的随机性。
(2)、ID3算法：对CLS算法的最⼤改进是摒弃了属性选择的随机性，利⽤信息熵的下降速度作为属性选择的度量。ID3是⼀种基于信息熵的决策树分类学习算法，以信息增益和信息熵，作为对象分类的衡量标准。ID3算法结构简单、学习能⼒强、分类速度快适合⼤规模数据分类。但同时由于信息增益的不稳定性，容易倾向于众数属性导致过度拟合，算法抗⼲扰能⼒差。
ID3算法的核⼼思想：根据样本⼦集属性取值的信息增益值的⼤⼩来选择决策属性(即决策树的⾮叶⼦结点)，并根据该属性的不同取值⽣成决策树的分⽀，再对⼦集进⾏递归调⽤该⽅法，当所有⼦集的数据都只包含于同⼀个类别时结束。最后，根据⽣成的决策树模型，对新的、未知类别的数据对象进⾏分类。
ID3算法优点：⽅法简单、计算量⼩、理论清晰、学习能⼒较强、⽐较适⽤于处理规模较⼤的学习问题。
ID3算法缺点：倾向于选择那些属性取值⽐较多的属性，在实际的应⽤中往往取值⽐较多的属性对分类没有太⼤价值、不能对连续属性进⾏处理、对噪声数据⽐较敏感、需计算每⼀个属性的信息增益值、计算代价较⾼。
(3)、C4.5算法：基于ID3算法的改进，主要包括：使⽤信息增益率替换了信息增益下降度作为属性选择的标准；在决策树构造的同时进⾏剪枝操作；避免了树的过度拟合情况；可以对不完整属性和连续型数据进⾏处理；使⽤k交叉验证降低了计算复杂度；针对数据构成形式，提升了算法的普适性。
(4)、SLIQ算法：该算法具有⾼可扩展性和⾼可伸缩性特质，适合对⼤型数据集进⾏处理。
(5)、CART(Classification and RegressionTrees, CART)算法：是⼀种⼆分递归分割技术，把当前样本划分为两个⼦样本，使得⽣成的每个⾮叶⼦节点都有两个分⽀，因此，CART算法⽣成的决策树是结构简洁的⼆叉树。
分类回归树算法(Classification and Regression Trees，简称CART算法)是⼀种基于⼆分递归分割技术的算法。该算法是将当前的样本集，分为两个样本⼦集，这样做就使得每⼀个⾮叶⼦节点最多只有两个分⽀。因此，使⽤CART算法所建⽴的决策树是⼀棵⼆叉树，树的结构简单，与其它决策树算法相⽐，由该算法⽣成的决策树模型分类规则较少。
CART分类算法的基本思想是：对训练样本集进⾏递归划分⾃变量空间，并依次建⽴决策树模型，然后采⽤验证数据的⽅法进⾏树枝修剪，从⽽得到⼀颗符合要求的决策树分类模型。
CART分类算法和C4.5算法⼀样既可以处理离散型数据，也可以处理连续型数据。CART分类算法是根据基尼(gini)系数来选择测试属
性，gini系数的值越⼩，划分效果越好。设样本集合为T，则T的gini系数值可由下式计算：
其中，p j是指类别j在样本集T中出现的概率。若我们将T划分为T1、T2两个⼦集，则此次划分的gini系数的值可由下式计算：
其中，s为样本集T中总样本的个数，s1为属于⼦集T1的样本个数，s2为属于⼦集T2的样本个数。
CART算法优点：除了具有⼀般决策树的⾼准确性、⾼效性、模式简单等特点外，还具有⼀些⾃⾝的特点。如，CART算法对⽬标变量和预测变量在概率分布上没有要求，这样就避免了因⽬标变量与预测变量概率分布的不同造成的结果；CART算法能够处理空缺值，这样就避免了因空缺值造成的偏差；
丁香功效和作用CART算法能够处理孤⽴的叶⼦结点，这样可以避免因为数据集中与其它数据集具有不同的属性的数据对进⼀步分⽀产⽣影响；CART算法使⽤的是⼆元分⽀，能够充分地运⽤数据集中的全部数据，进⽽发现全部树的结构；⽐其它模型更容易理解，从模型中得到的规则能获得⾮常直观的解释。
CART算法缺点：CART算法是⼀种⼤容量样本集挖掘算法，当样本集⽐较⼩时不够稳定；要求被选择的属性只能产⽣两个⼦结点，当类别过多时，错误可能增加得⽐较快。
以上内容主要摘⾃：
1、《基于决策树的档案⽂本⾃动分类算法研究》，云南⼤学，硕论，2015
陈武帝2、《⼀种改进的决策树分类算法》，华中师范⼤学，硕论，2016
3、《⾯向离散属性的决策树分类⽅法研究》，⼤连海事⼤学，硕论，2017
