1.特性

优点:可读性、分类速度快

缺点:对未知数据集泛华能力弱，容易发生过拟合现象

特点:划分数据集后，数据纯度变大的过程

分类:离散型决策树、连续型决策树

与KNN的区别:KNN的缺点是无法给出数据内在含义，而决策树在数据形式上易于理解

2.构建过程

创建决策树三个过程:特征选择，建立树、裁剪(解决过拟合现象)

递归选择熵值最大的特征进行分类，以最快速度降低数据集不确定程度

根据特征选择指标的不同，分为ID3/CART/C4.5

（1）计算当前分类信息熵（经验熵）

$H = -\sum_{i=1}^np(xi)\log_2 p(xi)$ n:分类次数； p(xi):该分类出现的概率

（2）求当前每个特征分类后的条件熵

$H(Y|X) = \sum_{i=1}^np(xi)H(Y|X=xi)$

条件熵:我们假设以某个特征进行分类(条件概率)，在已知该特征值分类情况下的分类结果Y计算熵（该特征每个取值的概率乘以一直该取值下的信息熵）

（3）求信息增益/信息增益比/基尼系数(增益:衡量划分数据前后信息发生的变化)

信息增益最大(ID3):仅用于二分类离散属性问题

$g(D,A) = H(D) - H(D|A)$

信息增益比最大(C4.5):可处理连续值属性问题(取连续属性中值作为划分标准)

$g_{R}(D,A) = \frac{g(D,A)}{H( D)}$

基尼系数最小(CART):CART必须是二叉树，分类和回归都可运用，但更偏向于连续属性，不作对数运算，更加高效:

$Gini(D) = 1 - \sum_{i=1}^n \frac{(|C_{i} |}{| D|})^2$ K:分类类别 |D|样本个数 |Ci|该类别个数

$Gini(D,A) = \frac{|D1|}{D} Gini(D1) + \frac{|D2|}{D} Gini(D2)$ D1 D2为该特征的分类，CART都是二分

（4）择信息增益/信息增益比最大的特征进行当次划分，然后取出该列特征。

（5）对于整棵树的构造，使用递归原则处理数据集

3.几种衡量对比

4.剪枝

剪枝:考虑决策树的复杂度，不出现过拟合现象，对决策树进行修剪；从已经生成的树上裁掉一些子树或叶节点，并将其根节点或父节点作为新的叶子节点，从而简化分类树模型

1.预剪枝:构造结点钱判断是否构建该结点对泛化能力有所提升，运算简单但可能欠拟合，适用于大规模问题

四种简单方式判断:

(1) 决策树到达一定高度

(2) 结点下的实例少于一定个数

(3)信息增益、信息增益比低于某个阈值

2.后剪枝:先构建整树，自底向上对非叶节点进行泛化能力判断，通过极小化决策树整体的损失函数或代价函数来实现的

后剪枝CCP:（CART/GBDT中所用的剪枝方法），代价复杂度剪枝

依次剪枝计算误差，选择误差最小的那棵树

注:关于剪枝部分以后来补充

5.基本代码实现(来自机器学习实战)

（1）计算香农熵

from math import log

from numpy import *

# 给定样本集，计算该样本集的熵，样本集最后一列为分类

def cal_entropy(data):

# 样本个数

entries_num = len(data)

# 存储每个分类出现的次数

label_count = {}

for vec in data:

cur_label = vec[-1]

label_count[cur_label] = label_count.get(cur_label,0) + 1

# 熵

Entropy = 0.0

# 计算信息熵

for key in label_count:

prob = float(label_count[key]) / entries_num

Entropy += prob * math.log(prob, 2) #此处使用numpy.math

return (0-Entropy)

（2）计算信息增益，给出最优特征

# -*- coding: utf-8 -*-

from Cal_Entropy import *

# 返回拆分后的数据集

def Split_Data(dataset, axis, value):

new_subset = []

for vec in dataset:

if vec[axis] == value:

feature_split = vec[:axis]

feature_split.extend(vec[axis + 1:])

new_subset.append(feature_split)

return new_subset

# 传入数据集，返回最优特征(计算每个特征信息增益)

def Split_by_entropy(dataset):

# 记录当前有多少个特征

feature_num = len(dataset[0]) - 1

# 当前数据集信息熵

ent_old = cal_entropy(dataset)

# 最大信息增益

best_gain = 0.0

# 最好特征列

best_feature = -1

# 对每一个特征进行遍历

for i in range(feature_num):

feature_list = [x[i] for x in dataset]

uniVal = set(feature_list)

ent_new = 0.0

for value in uniVal:

sub_set = Split_Data(dataset, i, value)

prob = len(sub_set) / float(len(dataset))

ent_new += prob * (0 - cal_entropy(sub_set))

Info_gain = ent_old - ent_new

if(Info_gain > best_gain):

best_gain = Info_gain

best_feature = i

return best_feature

（3）主函数，递归构建决策树

# -*- coding: utf-8 -*-

import operator

from Split_by_entropy import *

# 该方法输入一组分类值，返回最多的分类结果

def Majority_vote(classList):

classcount = {}

for vote in classList:

classcount[vote] = classcount.get(vote,0) + 1

sorted_count = sorted(classcount.items(), key = operator.itemgetter(1),reverse = True)

return sorted_count[0][0]

# 该方法用于递归构建决策树

def Create_Tree(dataset,labels):

# 分类结果集

classList = [x[-1] for x in dataset]

# 如果该结点下所有数据都为同一分类，则返回该分类作为最终分类

if classList.count(classList[0]) == len(classList):

return classList[0]

# 如果已经分到最后一个特征但是该特征下还是有多个分类，选择最多的那个分类作为最终分类

if len(dataset[0]) == 1:

return Majority_vote(classList)

# 通过计算每个特征信息增益，选择最优特征及特征名

best_feature = Split_by_entropy(dataset)

best_labels = labels[best_feature]

# 特征列表删除该特征(已经进行了分类)

subLabels=labels[:]

del(subLabels[best_feature])

myTree = {best_labels:{}}

# 选取数据集中最优特征列去重后进行分类，继续递归生成子树

f_val = [x[best_feature] for x in dataset]

uni_val = set(f_val)

for value in uni_val:

# 递归创建子树并返回

myTree[best_labels][value] = Create_Tree(Split_Data(dataset\

,best_feature,value), subLabels)

return myTree

决策树算法