1.特性
优点:可读性、分类速度快
缺点:对未知数据集泛华能力弱，容易发生过拟合现象
特点:划分数据集后，数据纯度变大的过程
分类:离散型决策树、连续型决策树
与KNN的区别:KNN的缺点是无法给出数据内在含义，而决策树在数据形式上易于理解
2.构建过程
创建决策树三个过程:特征选择，建立树、裁剪(解决过拟合现象)
递归选择熵值最大的特征进行分类，以最快速度降低数据集不确定程度
根据特征选择指标的不同，分为ID3/CART/C4.5
（1）计算当前分类信息熵（经验熵）
n:分类次数； p(xi):该分类出现的概率
（2）求当前每个特征分类后的条件熵
条件熵:我们假设以某个特征进行分类(条件概率)，在已知该特征值分类情况下的分类结果Y计算熵（该特征每个取值的概率乘以一直该取值下的信息熵）
（3）求信息增益/信息增益比/基尼系数(增益:衡量划分数据前后信息发生的变化)
信息增益最大(ID3):仅用于二分类离散属性问题
信息增益比最大(C4.5):可处理连续值属性问题(取连续属性中值作为划分标准)
基尼系数最小(CART):CART必须是二叉树，分类和回归都可运用，但更偏向于连续属性，不作对数运算，更加高效:
K:分类类别 |D|样本个数 |Ci|该类别个数
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
