1.写在前面

最近机器学习课上学了决策树相关知识，对于我之前的理解又加深了一步，故再次总结学习。我之前看的是麦子学院关于决策树的讲解，还有代码实现，当时也做了笔记。有兴趣的可以可以看一下。

2.非线性问题

对于分类问题，如果是可以找出一条直线分开说明是线性可分，其他我们一般称为非线性可分。对于线性不可分数据，采用非线性决策的方法。如图左侧为线性可分，右侧为线性不可分。

2.1 线性扩展的思想

解决非线性问题，我们可以使用线性扩展的思想，也可以采用非线性扩展的思想。在线性扩展方面，我们有

2.2 非线性扩展的思想

一般会用到上面这几种方法，我感觉这几个方法其实还是比较独立的，有时间会把他们都做总结分享。首先介绍一下决策树方法。

3.决策树方法概述

顾名思义，决策树就是一棵树，一颗决策树包含一个根节点、若干个内部结点和若干个叶结点；叶结点对应于决策结果，其他每个结点则对应于一个属性测试；每个结点包含的样本集合根据属性测试的结果被划分到子结点中；根结点包含样本全集，从根结点到每个叶子结点的路径对应了一个判定测试序列。下面直接上个图，让大家看下决策树是怎样决策的（以二元分类为例），图中红线表示给定一个样例（表中数据）决策树的决策过程：

二叉树的直观解释就是提出一个一个的问题，对路径进行搜索分类

 

对于树的结构，我们可以找到哪些优点呢？我们通过上面的介绍可以知道，决策树可以不必测试所有的特征和区域。但是我们会有以下的问题

因此，整个决策树中最重要的四个关键问题就是，问题数+划分选择+决策树生成+剪枝处理，下面将会一一介绍这些东西。

4. 问题树

 

候选问题数: 无论特征值是连续还是离散，确定每个属性所产生的候选问题， 候选的问题总数为  N = ∑Ni 

因为连续属性的可取值数目不再有限，因此不能像前面处理离散属性枚举离散属性取值来对结点进行划分。因此需要连续属性离散化，常用的离散化策略是二分法，这个技术也是C4.5中采用的策略。下面来具体介绍下，如何采用二分法对连续属性离散化：

    
下面举个具体的例子，来看看到底是怎样划分的。

对于数据集中的属性“密度”，决策树开始学习时，根节点包含的17个训练样本在该属性上取值均不同。我们先把“密度”这些值从小到大排序：

根据上面计算Ta的公式，可得：

下面开始计算t 取不同值时的信息增益：