决策树

1. 决策树的原理

决策树（decision tree）是一个树结构（可以是二叉树或非二叉树）。其每个非叶子节点表示一个特征属性上的测试，每个分支代表这个特征属性在某个值域上的输出，而每个叶子节点存放一个类别。使用决策树进行决策的过程就是从根节点开始，测试待分类项中相应的特征属性，并按照其值选择输出分支，直到到达叶子节点，将叶子节点存放的类别作为决策结果。

2. 决策树的优缺点

优点：

计算复杂度不高，输出结果易于理解，对中间值的缺失不敏感，可以处理不相关特征数据。既能用于分类，也能用于回归

缺点：

可能会产生过拟合

3. 决策树的构造

注意：分类解决离散问题，回归解决连续问题

不同于逻辑斯蒂回归和贝叶斯算法，决策树的构造过程不依赖领域知识，它使用属性选择度量来选择将元组最好地划分成不同的类的属性。所谓决策树的构造就是进行属性选择度量确定各个特征属性之间的拓扑结构。

构造决策树的关键步骤是分裂属性。所谓分裂属性就是在某个节点处按照某一特征属性的不同划分构造不同的分支，其目标是让各个分裂子集尽可能地“纯”。尽可能“纯”就是尽量让一个分裂子集中待分类项属于同一类别。分裂属性分为三种不同的情况：

1. 属性是离散值且不要求生成二叉决策树。此时用属性的每一个划分作为一个分支。

2. 属性是离散值且要求生成二叉决策树。此时用数学划分一个子集进行测试，按照“属于此子集”和“不属于此子集”分成两个分支。

3. 属性是连续值。此时确定一个值作为分裂点split_point，按照 > split_point和 <= split_point生成两个分支。

构造决策树的关键内容是进行属性选择度量，属性选择度量是一种选择分裂准则，它决定了拓扑结构及分裂点split_point的选择。

属性选择度量算法有很多，一般使用自顶而下递归分治法，并采用不回溯的贪心策略。

ID3算法

划分数据集的大原则是：将无序的数据变得更加有序。

信息的定义。如果待分类的事物可能划分在多个分类之中，则符号x的信息定义为：

$l(x_{i} ) = -\log_2 p(x_{i} )$

熵定义为信息的期望值。计算所有类别所有可能值包含的信息期望值，计算公式如下：

$H = - \sum_{i=1}^n p(x_{i} )\log_2 p(x_{i} )$

其中n是分类的数目。

在决策树当中，设D为用类别对训练元组进行的划分，则D的熵(entropy)表示为：

$info(D) = - \sum_{i=1}^m p_{i}\log_2 (p_{i} )$

其中pi表示第i个类别在整个训练元组中出现的概率，可以用属于此类别元素的数量除以训练元组元素总数量作为估计。熵的实际意义表示的是D中元组的类标号所需要的平均信息量。

假设将训练元组D按属性A进行划分，则A对D划分的期望信息为：

$info_{A} (D) = \sum_{j=1}^\upsilon \frac{|D_{j} |}{|D|} info(D_{j} )$

信息增益即为两者的差值：

$gain(A) = info(D) - info_{A}(D)$

ID3的优缺点：

优点：原理简单

缺点：

1. 存在大量对数运算，对计算机不太友好

2. 会存在优先对比较离散的特征进行划分的毛病，容易造成误差

C4.5算法：

是对ID3的改进算法，改进了缺点中的第二点。

C4.5在ID3计算信息增益的基础上除上特征本身的信息熵，变成信息增益率。

CART算法（Classification and Regression Tree 分类和回归树）：

基尼不纯度：gini impurity

基尼系数和信息熵表达的含义相似：越大代表不确定性越大，越小越确定。但是范围在0到1之间。

ID3和C4.5只能做分类问题，CART可以做回归树，并且CART的树是二叉树，基尼系数的计算公式如下：