1.决策树基本流程
决策树(decisiontree)是一类常见的机器学习方法.以二分类任务为例,我们希望从给定训练数据集学得一个模型用以对新示例进行分类,这个把样本分类的任务,可看作对“当前样本属于正类吗？”这个问题的“决策”或“判定”过程.顾名思义,决策树是基于树结构来进行决策的,这恰是人类在面临决策问题时一种很自然的处理机制.例如,我们要对“这是好瓜吗?”这样的问题进行决策时,通常会进行一系列的判断或“子决策”:我们先看“它是什么颜色?”,如果是“青绿色”,则我们再看“它的根蒂是什么形态?”,如果是“蟋缩”,我们再判断“它敲起来是什么声音?”,最后,我们得出最终决策:这是个好瓜.
决策树学习的目的是为了产生一棵泛化能力强,即处理未见示例能力强的决策树,其基本流程遵循简单且直观的“分而治之”(divide-and-conquer)策略。
一棵决策树包含一个根结点、若干个内部结点和若干个叶结点;叶结点对应于决策结果,其他每个结点则对应于一个属性测试;每个结点包含的样本集合根据属性测试的结果被划分到子结点中;根结点包含样本全集.从根结点到每个叶结点的路径对应了一个判定测试序列.决策树学习的目的是为了产生一棵泛化能力强,即处理未见示例能力强的决策树,其基本流程避循简单且直观的“分而治之”(divide-and-conquer)策略。
2.剪枝处理
剪枝(pruning)是决策树学习算法对付“过拟合”的主要手段.在决策树学习中,为了尽可能正确分类训练样本,结点划分过程将不断重复,有时会造成决策树分支过多,这时就可能因训练样本学得“太好”了，以致于把训练集自身的一些特点当作所有数据都具有的一般性质而导致过拟合.因此,可通过主动去掉一些分支来降低过拟合的风险,决策树剪枝的基本策略有“预剪枝”(prepruning)和“后剪枝”(postpruming)[Quinlan,1993]预剪枝是指在决策树生成过程中,对每个结点在划分前先进行估计,若当前结点的划分不能带来决策树泛化性能提升,则停止划分并将当前结点标记为叶结点;后剪枝则是先从训练集生成一棵完整的决策树然后自底向上地对非叶结点进行考察,若将该结点对应的子树替换为叶结点能第4章决策树带来决策树泛化性能提升,则将该子树替换为叶结点.
3.缺失值处理
需要解决的两个问题
如何在属性值缺失的情况下进行划分属性选择？ 给定划分属性，若样本在该属性上的值缺失，如何对样本进行划分？
4.多变量决策树
若将每一个树形视为坐标空间中的一个坐标轴，则d个属性描述的样本对应了d维空间中的一个数据点，对样本分类则意味着在这个坐标空间中寻找不同类样本之间的分类边界。
但是其存在一定的缺陷，当分类边界的每一段都与坐标轴平行，这样的分类结果具有很好的解释性，但是如果分类边界过于复杂化，一来会带来开销过大，二来决策树也会很复杂，这就引出了多变量决策树
多变量决策树的结构为二叉树，实际上是多个线性模型的组合。
