一. 决策树
1. 概念： 决策树学习是根据数据的属性采用树状结构建立的一种决策模型，可以用此模型解决分类和回归问题。常见的算法包括 CART(Classification And Regression Tree), ID3, C4.5等。
优点
- 易于理解和解释，甚至比线性回归更直观；
- 与人类做决策思考的思维习惯契合；
- 模型可以通过树的形式进行可视化展示；
- 可以直接处理非数值型数据，不需要进行哑变量的转化，甚至可以直接处理含缺失值的数据；
缺点：
- 对于有大量数值型输入和输出的问题，决策树未必是一个好的选择；
- 产生过拟合
- 特别是当数值型变量之间存在许多错综复杂的关系，如金融数据分析；
- 决定分类的因素取决于更多变量的复杂组合时；
- 模型不够稳健，某一个节点的小小变化可能导致整个树会有很大的不同。
二. 决策树算法
1. 概念：决策树算法主要是指决策树进行创建中进行树分裂(划分数据集)的时候选取最优特征的算法，他的主要目的就是要选取一个特征能够将分开的数据集尽量的规整，也就是尽可能的纯. 最大的原则就是: 将无序的数据变得更加有序
2. 决策树学习算法主要由三部分构成:
- 特征选择
- 决策树生成
- 决策树的剪枝
三. 特征选择
信息熵
熵(entropy)概念最早来源于统计热力学，它是热力学系统混乱程度的一种度量。系统的混乱程度越低，其熵值就越小。 定义9-2 设δ为可取n个离散数值的随机变量，它取δi的概率为p(δi) (i=1,2,…,n)，则我们定义 
为随机变量的信息熵(Information Entropy)。 样本数据集S的任一属性A都可看作一个随机变量，假设其取值为{a1, a2 ,…, an}，则E(A)就是属性A所有取值的信息熵，其熵值越小所蕴含的不确定信息越小，越有利于数据的分类。
信息增益(information gain)
增益比率(gain ratio)
基尼不纯度(Gini impurity)
2. 代码实现
ID3算法为例 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22# 为所有可能的分类创建字典
def uniquecounts(rows):
results = {}
for row in rows:
# 计数结果在最后一列
r = row[len(row)-1]
if r not in results:results[r] = 0
results[r]+=1
return results # 返回一个字典
# 熵
def entropy(rows):
from math import log
log2 = lambda x:log(x)/log(2)
results = uniquecounts(rows)
# 开始计算熵的值
ent = 0.0
for r in results.keys():
p = float(results[r])/len(rows)
# 以2为底求对数
ent = ent - p*log2(p)
return ent
四. 决策树的生成
1. 经典的实现算法：
- ID3算法
- C4.5算法
- CART算法
2. ID3的算法思想（依据信息增益进行特征选取和分裂）
- 从根节点开始，选择信息增益最大的特征作为结点的特征，并由该特征的不同取值构建子节点
- 对子节点递归地调用以上方法，构建决策树
- 直到所有特征的信息增益均很小或者没有特征可选时为止。
1
2
3
4
5
6
7
8
9
10
11
12
13// 算法框架如下
class DecisionTree(object):
def fit(self, X, y):
# 依据输入样本生成决策树
self.root = self._build_tree(X, y)
def _build_tree(self, X, y, current_depth=0):
#1. 选取最佳分割特征，生成左右节点
#2. 针对左右节点递归生成子树
def predict_value(self, x, tree=None):
# 将输入样本传入决策树中，自顶向下进行判定
# 到达叶子节点即为预测值
3. C4.5算法
- C4.5算法与ID3算法的区别主要在于它在生产决策树的过程中，使用信息增益比来进行特征选择。
4. CART算法
- CART假设决策树是一个二叉树，它通过递归地二分每个特征，将特征空间划分为有限个单元，并在这些单元上确定预测的概率分布。
- CART算法中，对于回归树，采用的是平方误差最小化准则；对于分类树，采用基尼指数最小化准则。
- 平方误差最小化
- 基尼指数
五. 决策树的剪枝
1. 过拟合问题的解决方法：
- 当熵减少的数量小于某一个阈值时，就停止分支的创建。这是一种贪心算法。（限制Gain的阈值）
- 先创建完整的决策树，然后再尝试消除多余的节点，也就是采用减枝的方法。
六. 完整代码
- 完整代码