<commit_before>---
layout: post
title: 数据分类：决策树
categories: [机器学习]
tags: 决策树
---

## 背景

决策树(decision tree)是一种基本的分类和**回归**(后面补充一个回归的例子?)方法，它呈现的是一种树形结构，可以认为是if-then规则的集合。其其主要优点是模型具有很好的**可读性**，且**分类速度快**；缺点是可能会产生过度匹配的问题(所以一般都会有决策树的剪枝过程)。决策树在学习时，利用训练数据，根据损失函数最小化原则建立决策树模型，其学习过程包括3个步骤：特征选择、决策树生成和决策树修剪。决策树学习的思想来源主要有Quinlan在1986年提出的ID3算法和1993年提出的C4.5算法，以及由Breiman等人在1986年提出的CART算法。

决策树在现实生活中，已得到了很广泛的应用，举两个很常见的例子：

- 猜测人物，游戏的规则很简单：参与游戏的一方在脑海里想某个人，然后游戏页面一次一个选择选项陆续让你回答，比如，"这个人是在现代还是古代?"，一般问题的答案只能回答是还是不是，最后根据你一系列的回答便可以对你所想的某个人做出推断，比如你所想的这个人是你老爸。

- 投资指导或贷款申请。比如炒股，通过app新开账户后，有的会给出一个投资建议的指导，在生成这份指导建议前，会让你对某些问题(一般几个)进行回答，然后根据你的回答，生成一份对你投资类型的判断，开过这类账户的用户应该都有这个体验。另外一个就是贷款申请，会根据你的年龄、有无工作、是否有房子、信贷情况指标来决定是否给你贷款。

实际上，近来的调查研究表明决策树也是**最经常**使用的数据挖掘算法。接下来，按决策树的学习步骤先介绍决策树模型定义，然后介绍特征选择、决策树生成以及决策树的剪枝，最后编码测试一个实际的例子。

## 决策树模型定义

决策树模型是一种描述对实例进行分类的树形结构，它有结点(node)和有向边(directed edge)组成，结点有两种类型：内部结点(internal node)和叶结点(leaf node)。内部结点表示一个特征或者属性，叶结点表示一个类别。

在用决策树进行预测时，对于输入的某个样本$x_{test}$，从根结点开始，对$x_{test}$的某一个特征进行测试，根据测试的结果，将$x_{test}$分配分配到其子结点；然后递归的进行下一个规则的判断，直到到达叶结点，最后将$x_{test}$分配到叶结点的类中。

下图是决策树的示意图，图中的方框表示内部结点，圆型表示叶结点，即所属的类别。
![drawing](http://i300.photobucket.com/albums/nn17/willard-yuan/blog/Screen%20Shot%202015-10-23%20at%2023.55.27_zps5youxktx.png)
再举个具体的例子：
![drawing](http://i300.photobucket.com/albums/nn17/willard-yuan/blog/Screen%20Shot%202015-10-24%20at%2000.06.52_zpscvm4idpn.png)
上面，将邮件按重要性分成了3类：即无聊时阅读的邮件、需要即使处理的邮件以及无需阅读的垃圾邮件。

在前面**背景**中讲到，可以认为决策树是if-then规则的集合。从上面给出的两个图示也可以很明显的得到这样的结论。决策树转换成if-then规则的过程是这样的：由决策树的根结点的每一条路径构建一条规则，路径上内部结点的特征对应着规则的条件，叶结点对应的是规则的结论。由于决策树在对测试样本进行类别判定时，经过的判别路径（规则）只有一条，且判定的结果一定是属于叶结点中的某个，所以可以得出一个重要的性质：决策树的路径是**完备且互斥**的。也就是每一个实例都只能被一条路径（对应的规则子集）所覆盖（或满足）。

## 决策树学习

对于给定的数据集`\( D={\{(x_1, y_1),(x_2, y_2),...,(x_N, y_N) \}} \)`共N个样本，`\( x_i=(x_i^{(1)},x_i^{(2)},...,x_i^{(n)})^T \)`为样本$i$对应的$n$个特征，比如前面所举的贷款的例子，年龄、有无工作、是否有房子、信贷情况4个特征，$y\in{\{1,2,...,K\}}$为类标记，决策树学习的目标就是要根据给定的训练集构造一个决策树模型，是它能对未知样本进行正确的分类。

决策树从本质上来说，是从训练数据中归纳出一组分类规则，与训练数据集不相矛盾的决策树(即能对训练数据进行正确分类的决策树)可能有多个，也可能没有，我们需要的是一个与训练数据矛盾最小的决策树，同时又具备很好的泛化能力。决策树学习用损失函数表示这一目标，其损失函数通常是正则化的极大似然函数，学习的策略是使损失函数最小化。由于从所有可能的决策树中选取最优决策树是一个NP问题(?)，所以一般采用启发式方法，近似去求解这一问题，不过这样得到的决策树是次优解。

具体地，先开始构建根结点，将所有的训练数据都放在根结点，选择一个最优特征(这个最优特征按照什么标准进行选择?)，按照这一特征将训练数据集分割成子集，使得各个子集有一个在当前条件下分类是最好的(数据经过分类后更有序，信息熵最小)，如果这些子集基本已经能够被准确分类，那么就可以构建叶结点了，并将这些子集分到对应的叶结点中去，如果还有子集不能被正确分类，那么就继续对这些子集选择新的最优特征，继续对其进行分割，如此递归的进行下去，直到所有训练数据的子集基本被准确分类，或者没有合适的特征为止。

前面我们提到，决策树有可能出现过度匹配的问题，即决策树在训练数据集上有很好的分类精度，但是在测试数据上可能表现得很糟糕，这种情况就是所谓的过度匹配(过拟合)现象。为了削减这种现象，需要对已生成的树进行剪枝，将树变得更简单，从而使它具有更好的泛化能力。具体地，**就是去掉过于细节的叶结点，使其回退到父结点，甚至是更高的结点，然后将父结点或更高的结点改为新的叶结点**。

如果特征数目很多，可以先进行特征选择，去除部分冗余特征，只留下对训练数据有较好的分类能力的特征。

需要注意的是，决策树的生成对应于模型的局部选择，决策树的剪枝对应于模型的全局选择，即生成时只考虑了局部最优，而剪枝则考虑了全局最优。

在上面进行最优特征选择的时候，我们引出了这样一个问题，即"这个最优特征是按照什么标准选择出来的?"，为了回答这个问题，我们对这个问题进行详细的论述。

## 特征选择问题

特征选择是决定用哪个特征来决定划分特征空间。每次划分的时候，我们只选取一个特征属性，如果选取的训练集$D$中有$n$个特征，第一次选择哪个特征作为划分数据集的参考属性呢？

比如下表包含了5个海洋动物，特征包括：不浮出水面是否可以生存，是否有脚蹼。这5个海洋动物可以分成两类：鱼类和非鱼类。现在在构建根结点时，我们是选择第一个特征属性呢还是选择第二个特征属性划分数据。为了对这个问题的标准进行定量度量，我们选取信息增益或信息增益比作为我们选取特征的准则。
![](http://i300.photobucket.com/albums/nn17/willard-yuan/blog/Screen%20Shot%202015-10-24%20at%2010.39.57_zps3iqdbwe9.png)
划分数据数据集的大原则是：将无序的数据变得更加有序。度量数据杂乱无章程度的一种方法就是使用信息论中的信息熵，在划分数据之前和之后信息发生的变化称为信息增益，通过计算每个特征划分数据集获得的信息增益，获得信息增益最大的特征就是当前数据集下最好的用于划分数据最好的特征。

### 信息增益

在信息论和概率统计中，熵是表示随机变量不确定性的度量，熵越大，表示数据越杂乱无章，反之，则说明数据越有序。设$X$是一个取有限个值的离散随机变量，其概率分布为：

$$
P(X = x_i) = p_i, i = 1, 2, ...,n
$$

则随机变量$X$的熵定义为：

$$
\begin{aligned}
H(X) = - \sum_{i=1}^{n}p_ilogp_i
\end{aligned}
$$

若$p_i=0$，则定义$0log0=0$，上式中的对数底数通常以2为底或以e为底，这是熵的单位分别称为比特(bit)或纳特(nat)。由上式熵的定义式可知，熵只依赖于$X$的分布，而与$X$的取值无关，所以也可将$X$的熵$H(X)$记为$H(p)$。同时，从定义可以验证，$0<=H(p)<=logn$。当随机变量只取两个值，比如0、1时，即$X$服从0-1分布时，熵为：

$$
\begin{aligned}
H(p)=-plog_2p-(1-p)log_2(1-p)
\end{aligned}
$$

我们可以用pyhon画出熵$H(x)$随概率$p$变化的曲线：

```python
import numpy as np

p = np.linspace(0.,1.,11)
print p

Hp = -p*np.log2(p)-(1-p)*np.log2(1-p)
Hp[0] = Hp[-1] = 0
print Hp

%matplotlib inline
import matplotlib
from pylab import *
import matplotlib.pyplot as plt

fig = plt.figure()
ax = fig.gca()
ax.set_xticks(p)
plt.plot(p,Hp)
grid(True)
plt.xlabel('$p$')
plt.ylabel('$H(p)$')

plt.show()
```

运行上面代码，可以得到下图：
![](http://i300.photobucket.com/albums/nn17/willard-yuan/download_zps9lv2ptzd.png)
可以看到，但$p=1-p=0.5$时，即取0或1的概率都是0.5时，熵最大，随机变量不确定性最大。

在了解了信息熵的定义后，我们半手工计算一下前面海洋生物数据集上的信息熵：

```python
marineEnt = -0.4*np.log2(0.4)-0.6*np.log2(0.6)
print "the entropy of the marine organism: %.20f" % marineEnt
# the entropy of the marine organism: 0.97095059445466858072
```
上面显示在海洋生物数据集上的信息熵为0.97095059445466858072。下面对于对计算信息熵进行完整的编码，使得其能够更方便计算某个数据集的信息熵，具体如下：

```
def creatData():
    dataSet = [[1, 1, 'yes'], [1, 1, 'yes'], [1, 0, 'no'], [0, 1, 'no'], [0, 1, 'no']]
    labels = ['no surfacing', 'flippers']
    return dataSet, labels

myData, labels = creatData()
print myData<commit_msg>fix error in new post<commit_after>---
layout: post
title: 数据分类：决策树
categories: [机器学习]
tags: 决策树
---

## 背景

决策树(decision tree)是一种基本的分类和**回归**(后面补充一个回归的例子?)方法，它呈现的是一种树形结构，可以认为是if-then规则的集合。其其主要优点是模型具有很好的**可读性**，且**分类速度快**；缺点是可能会产生过度匹配的问题(所以一般都会有决策树的剪枝过程)。决策树在学习时，利用训练数据，根据损失函数最小化原则建立决策树模型，其学习过程包括3个步骤：特征选择、决策树生成和决策树修剪。决策树学习的思想来源主要有Quinlan在1986年提出的ID3算法和1993年提出的C4.5算法，以及由Breiman等人在1986年提出的CART算法。

决策树在现实生活中，已得到了很广泛的应用，举两个很常见的例子：

- 猜测人物，游戏的规则很简单：参与游戏的一方在脑海里想某个人，然后游戏页面一次一个选择选项陆续让你回答，比如，"这个人是在现代还是古代?"，一般问题的答案只能回答是还是不是，最后根据你一系列的回答便可以对你所想的某个人做出推断，比如你所想的这个人是你老爸。

- 投资指导或贷款申请。比如炒股，通过app新开账户后，有的会给出一个投资建议的指导，在生成这份指导建议前，会让你对某些问题(一般几个)进行回答，然后根据你的回答，生成一份对你投资类型的判断，开过这类账户的用户应该都有这个体验。另外一个就是贷款申请，会根据你的年龄、有无工作、是否有房子、信贷情况指标来决定是否给你贷款。

实际上，近来的调查研究表明决策树也是**最经常**使用的数据挖掘算法。接下来，按决策树的学习步骤先介绍决策树模型定义，然后介绍特征选择、决策树生成以及决策树的剪枝，最后编码测试一个实际的例子。

## 决策树模型定义

决策树模型是一种描述对实例进行分类的树形结构，它有结点(node)和有向边(directed edge)组成，结点有两种类型：内部结点(internal node)和叶结点(leaf node)。内部结点表示一个特征或者属性，叶结点表示一个类别。

在用决策树进行预测时，对于输入的某个样本$x_{test}$，从根结点开始，对$x_{test}$的某一个特征进行测试，根据测试的结果，将$x_{test}$分配分配到其子结点；然后递归的进行下一个规则的判断，直到到达叶结点，最后将$x_{test}$分配到叶结点的类中。

下图是决策树的示意图，图中的方框表示内部结点，圆型表示叶结点，即所属的类别。
![drawing](http://i300.photobucket.com/albums/nn17/willard-yuan/blog/Screen%20Shot%202015-10-23%20at%2023.55.27_zps5youxktx.png)
再举个具体的例子：
![drawing](http://i300.photobucket.com/albums/nn17/willard-yuan/blog/Screen%20Shot%202015-10-24%20at%2000.06.52_zpscvm4idpn.png)
上面，将邮件按重要性分成了3类：即无聊时阅读的邮件、需要即使处理的邮件以及无需阅读的垃圾邮件。

在前面**背景**中讲到，可以认为决策树是if-then规则的集合。从上面给出的两个图示也可以很明显的得到这样的结论。决策树转换成if-then规则的过程是这样的：由决策树的根结点的每一条路径构建一条规则，路径上内部结点的特征对应着规则的条件，叶结点对应的是规则的结论。由于决策树在对测试样本进行类别判定时，经过的判别路径（规则）只有一条，且判定的结果一定是属于叶结点中的某个，所以可以得出一个重要的性质：决策树的路径是**完备且互斥**的。也就是每一个实例都只能被一条路径（对应的规则子集）所覆盖（或满足）。

## 决策树学习

对于给定的数据集`\( D={\{(x_1, y_1),(x_2, y_2),...,(x_N, y_N) \}} \)`共N个样本，`\( x_i=(x_i^{(1)},x_i^{(2)},...,x_i^{(n)})^T \)`为样本$i$对应的$n$个特征，比如前面所举的贷款的例子，年龄、有无工作、是否有房子、信贷情况4个特征，$y\in{\{1,2,...,K\}}$为类标记，决策树学习的目标就是要根据给定的训练集构造一个决策树模型，是它能对未知样本进行正确的分类。

决策树从本质上来说，是从训练数据中归纳出一组分类规则，与训练数据集不相矛盾的决策树(即能对训练数据进行正确分类的决策树)可能有多个，也可能没有，我们需要的是一个与训练数据矛盾最小的决策树，同时又具备很好的泛化能力。决策树学习用损失函数表示这一目标，其损失函数通常是正则化的极大似然函数，学习的策略是使损失函数最小化。由于从所有可能的决策树中选取最优决策树是一个NP问题(?)，所以一般采用启发式方法，近似去求解这一问题，不过这样得到的决策树是次优解。

具体地，先开始构建根结点，将所有的训练数据都放在根结点，选择一个最优特征(这个最优特征按照什么标准进行选择?)，按照这一特征将训练数据集分割成子集，使得各个子集有一个在当前条件下分类是最好的(数据经过分类后更有序，信息熵最小)，如果这些子集基本已经能够被准确分类，那么就可以构建叶结点了，并将这些子集分到对应的叶结点中去，如果还有子集不能被正确分类，那么就继续对这些子集选择新的最优特征，继续对其进行分割，如此递归的进行下去，直到所有训练数据的子集基本被准确分类，或者没有合适的特征为止。

前面我们提到，决策树有可能出现过度匹配的问题，即决策树在训练数据集上有很好的分类精度，但是在测试数据上可能表现得很糟糕，这种情况就是所谓的过度匹配(过拟合)现象。为了削减这种现象，需要对已生成的树进行剪枝，将树变得更简单，从而使它具有更好的泛化能力。具体地，**就是去掉过于细节的叶结点，使其回退到父结点，甚至是更高的结点，然后将父结点或更高的结点改为新的叶结点**。

如果特征数目很多，可以先进行特征选择，去除部分冗余特征，只留下对训练数据有较好的分类能力的特征。

需要注意的是，决策树的生成对应于模型的局部选择，决策树的剪枝对应于模型的全局选择，即生成时只考虑了局部最优，而剪枝则考虑了全局最优。

在上面进行最优特征选择的时候，我们引出了这样一个问题，即"这个最优特征是按照什么标准选择出来的?"，为了回答这个问题，我们对这个问题进行详细的论述。

## 特征选择问题

特征选择是决定用哪个特征来决定划分特征空间。每次划分的时候，我们只选取一个特征属性，如果选取的训练集$D$中有$n$个特征，第一次选择哪个特征作为划分数据集的参考属性呢？

比如下表包含了5个海洋动物，特征包括：不浮出水面是否可以生存，是否有脚蹼。这5个海洋动物可以分成两类：鱼类和非鱼类。现在在构建根结点时，我们是选择第一个特征属性呢还是选择第二个特征属性划分数据。为了对这个问题的标准进行定量度量，我们选取信息增益或信息增益比作为我们选取特征的准则。
![](http://i300.photobucket.com/albums/nn17/willard-yuan/blog/Screen%20Shot%202015-10-24%20at%2010.39.57_zps3iqdbwe9.png)
划分数据数据集的大原则是：将无序的数据变得更加有序。度量数据杂乱无章程度的一种方法就是使用信息论中的信息熵，在划分数据之前和之后信息发生的变化称为信息增益，通过计算每个特征划分数据集获得的信息增益，获得信息增益最大的特征就是当前数据集下最好的用于划分数据最好的特征。

### 信息增益

在信息论和概率统计中，熵是表示随机变量不确定性的度量，熵越大，表示数据越杂乱无章，反之，则说明数据越有序。设$X$是一个取有限个值的离散随机变量，其概率分布为：

$$
P(X = x_i) = p_i, i = 1, 2, ...,n
$$

则随机变量$X$的熵定义为：

$$
\begin{aligned}
H(X) = - \sum_{i=1}^{n}p_ilogp_i
\end{aligned}
$$

若$p_i=0$，则定义$0log0=0$，上式中的对数底数通常以2为底或以e为底，这是熵的单位分别称为比特(bit)或纳特(nat)。由上式熵的定义式可知，熵只依赖于$X$的分布，而与$X$的取值无关，所以也可将$X$的熵$H(X)$记为$H(p)$。同时，从定义可以验证，$0<=H(p)<=logn$。当随机变量只取两个值，比如0、1时，即$X$服从0-1分布时，熵为：

$$
\begin{aligned}
H(p)=-plog_2p-(1-p)log_2(1-p)
\end{aligned}
$$

我们可以用pyhon画出熵$H(x)$随概率$p$变化的曲线：

```python
import numpy as np

p = np.linspace(0.,1.,11)
print p

Hp = -p*np.log2(p)-(1-p)*np.log2(1-p)
Hp[0] = Hp[-1] = 0
print Hp

%matplotlib inline
import matplotlib
from pylab import *
import matplotlib.pyplot as plt

fig = plt.figure()
ax = fig.gca()
ax.set_xticks(p)
plt.plot(p,Hp)
grid(True)
plt.xlabel('$p$')
plt.ylabel('$H(p)$')

plt.show()
```

运行上面代码，可以得到下图：
![](http://i300.photobucket.com/albums/nn17/willard-yuan/download_zps9lv2ptzd.png)
可以看到，但$p=1-p=0.5$时，即取0或1的概率都是0.5时，熵最大，随机变量不确定性最大。

在了解了信息熵的定义后，我们半手工计算一下前面海洋生物数据集上的信息熵：

```python
marineEnt = -0.4*np.log2(0.4)-0.6*np.log2(0.6)
print "the entropy of the marine organism: %.20f" % marineEnt
# the entropy of the marine organism: 0.97095059445466858072
```
上面显示在海洋生物数据集上的信息熵为0.97095059445466858072。下面对于对计算信息熵进行完整的编码，使得其能够更方便计算某个数据集的信息熵，具体如下：

```python
def creatData():
    dataSet = [[1, 1, 'yes'], [1, 1, 'yes'], [1, 0, 'no'], [0, 1, 'no'], [0, 1, 'no']]
    labels = ['no surfacing', 'flippers']
    return dataSet, labels

myData, labels = creatData()
print myData
{'fraction_non_alphanumeric': 0.15962054031759126, 'fraction_numerical': 0.04516395133017117, 'mean_word_length': 11.778656126482213, 'pattern_counts': {'":': 0, '<': 7, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '6699343', 'n_tokens_mistral': 8090, 'n_tokens_neox': 9183, 'n_words': 320}