1、算法原理

1.1 ID3（多叉树分类）

信息熵：$Ent(D)=-{\sum }_{i=1}^n{p}_{i}log{p}_i$其中n为类别，$p_i$为每个类别的概率，$D$为某个特征，越小越确定

信息增益：$Gain(D,a)=Ent(D)=-{\sum }_{v=1}^v\frac{|D^v|}{|D|}Ent(D^v)$越大纯度提升越大，所以分裂$argmaxGain(D,a)$

eg.15个样本，9个1和6个0；有个特征A（取值$A_1$、$A_2$、$A_3$，其中$A_1$（3个1，2个0），其中$A_2$（2个1，3个0）其中$A_3$（4个1，1个0））

$Ent(A)=-(\frac{9}{15}\ast lo{g}_2\frac{9}{15}+\frac{6}{15}\ast lo{g}_2\frac{6}{15})=0.971$

$Gain(A,a)=0.971-(\frac{5}{15}Ent(A1)+\frac{5}{15}Ent(A2)+\frac{5}{15}Ent(A3))=0.083$

• ID3在相同条件下取值较多的比较少的信息增益要大（2个值为$\frac{1}{2}$,3个值为$\frac{1}{3}$，但是3个信息增益会更大）
• ID3没有考虑连续特征
• ID3对缺失值未考虑

需要惩罚取值较多的信息增益，引出了信息增益率，即C4.5的算法

1.2 C4.5（多叉树分类）

$IV(a)=-{\sum }_{v=1}^v\frac{|D^v|}{|D|}lo{g}_2\frac{|D^v|}{|D|}$ 特征取值越多，$IV(a)$越大

信息增益率：$Gain\_ratio(D,a)=\frac{Gain(D,a)}{IV(a)}$ argmax$Gain\_ratio(D,a)$

• 如果为连续型变量，先从大到小排序，分别取2个中值（均值）作为划分点计算

引出了分类+回归的决策树

1.3 Cart（二叉树分类+回归）

$Gini(D)=1-{\sum }_{i=1}^n{p}_i^2$ 反映随机抽2个样本，不一致的概率，越小越好（越纯）

$Gin{i}_{split}(D)=1-{\sum }_{v=1}^v\frac{|D^v|}{|D|}Gini(D^v)$

eg.Age(youth(5)、middle(5)、senior(4))，以youth(5)和middle+senior(9)分割为例：

$Gin{i}_{split}(Age)=\frac{5}{14}[1-[(\frac{3}{5}{)}^2+(\frac{2}{5}{)}^2]]+\frac{9}{14}[1-[(\frac{2}{9}{)}^2+(\frac{7}{9}{)}^2]]=0.39$
如果为连续性变量处理方式与C4.5相同

回归mse：

• 根据每一个连续值作为划分点（或用分类的方式取均值作为划分点），将其划分$S_1$、$S_2$
• 计算每个分支（$S_1$、$S_2$）的均值。 $mean=\frac{sum(s_1或s_2里真实值)}{该集合样本总数}$即为该分支的预测值
• 计算$S_1$、$S_2$的mse的和。 $mse=(该集合每一个样本真实值-mean{)}^2$

注：实践证明$Gini$和$Gain$效果差不多

2、ID3、C4.5与Cart比较

• ID3、C4.5与Cart特征选择只选一个特征。但大多数由一组特征决定。这样得到的决策树更准确（oc1）
• 样本发生一点改变，树的结构可能会发生剧烈的变化

3、算法优缺点

一、优点：

• 简单直观，生成的决策树可解释性强
• 不需要数据预处理（例如归一化处理，但封装的scikit-learn需要处理缺失值与字符型变量）
• 可以处理多维度多分类问题

一、缺点：

• 容易过拟合
• 样本发生改变可能导致完全不同的树
• 样本不平衡时，树会偏向于类别较多的一类

4、算法需要注意的点

决策树的构建过程中出现过拟合的原因及解决方法
原因：

• 在构建过程中没有进行合理的限制（如树的深度等）
• 样本中有噪声数据，没有进行有效的剔除
• 变量较多也容易产生过拟合

解决方法： 剪枝、限制深度、RF、正则化等

决策树如何处理缺失值
1、使用权重方法重构。（可认为以前1$\ast Gain$，现在无缺失比率$\ast Gain$）训练时特征出现缺失怎么处理（划分）即不考虑缺失，然后重赋权重
2、将缺失（划分变量）的样本中分别放到不同分支再进行分支。缺失变量样本的归属分支问题
3、同时探查所有分支，然后算每个类别的概率，取概率最大的类别赋值该样本。测试集中缺失处理

决策树递归终止的条件
1、所有子集被正确分类；2、没有合适的特征选择或信息增益(信息增益率/Gini)很小

决策树的变量重要性
如样本分裂占比$\ast$Gini/信息增益比

5、python代码实现

5.1导入相关包

import numpy as np
import pandas as pd
from sklearn.preprocessing import LabelEncoder #分类变量编码包
from sklearn.model_selection import train_test_split
from sklearn.tree import DecisionTreeClassifier
import variable_iv as vi
import Logistic_model as lm

import os
os.chdir('E:/wyz/Desktop/cart/')
os.environ["PATH"] += os.pathsep + 'D:/Program Files (x86)/Graphviz2.38/bin/'#决策树可视化的包

5.2 读取数据并数据处理

data = pd.read_excel('ceshi.xlsx',sheet_name = 'Sheet2')
#分类变量编码
from sklearn.preprocessing import LabelEncoder
le = LabelEncoder()
str_variable = list(data.dtypes[data.dtypes.values == object].index)
for col in str_variable:    
    data[col] = le.fit_transform(data[col].astype(str))
#在单变量分析的基础上填充缺失值（看哪一组的1的比率最接近于缺失值的那一组）
data['var1'] = data['var1'].fillna(0.42089)
data['var2'] = data['var2'].fillna(125.854)
#划分数据集
y = data_model['target']
x = data_model.drop('target', axis=1)
x_train, x_test, y_train, y_test = train_test_split(x, y,random_state=0,train_size=0.7)

5.3 模型训练

#建立模型(min_samples_leaf和min_samples_split需要慎重选择)（和传统决策树有很大区别）
model_tree = DecisionTreeClassifier(
             criterion='gini',#划分标准
             splitter='best',#特征划分标准
             max_depth=3,#树的最大深度
             min_samples_split=20,#划分所需要的最小样本数
             min_samples_leaf=10,#分到每个叶子最小样本数
             max_features=None,#用于参与划分的变量个数 
             max_leaf_nodes=None,#最大叶子节点数 
             min_impurity_decrease=0.0,#节点划分最小不纯度 
             min_weight_fraction_leaf=0.0,#叶子节点最小的样本权重和
             presort=False,#进行拟合前是否预分数据来加快树的构建
             random_state=None, 
             )#建模要class_weight='balanced'
model_tree.fit(x_train, y_train)

5.4 评估指标

test_proba = pd.DataFrame(model_tree.predict_proba(x_test))[1].values#预测为0的概率
print('测试集AUC: %.4f'%roc_auc_score(y_test,test_proba))#AUC，预测为概率

#变量重要性（是由该节点样本占总体样本*gini的减少量）
importances = list(model_tree.feature_importances_)
print(importances)

#输出变量重要的前几个变量（求最大的三个索引nsmallest与nlargest相反求最小）
import heapq
imp_index = list(map(importances.index, heapq.nlargest(3,importances)))
var_imp = []
for i in imp_index:
    var_imp.append(list1[i])
print(var_imp)

5.4 决策树以图的形式输出

#解决中文乱码问题(含中文的输出方式)
from sklearn.externals.six import StringIO
import pydotplus
from IPython.display import Image
dot_data = StringIO()
#决策树图
list1 = ['var1','var2','var3','var4','var5','var6']
tree.export_graphviz(model_tree, out_file=dot_data,  
                                    feature_names=list1,
                                    filled=True, rounded=True, 
                                    special_characters=True)
graph = pydotplus.graph_from_dot_data(dot_data.getvalue().replace( 'helvetica' ,' "Microsoft YaHei" '))
graph.write_png("result1.png")#将图画出来
#https://blog.csdn.net/qq_39386012/article/details/83857609#commentBox
Image(graph.create_png())#在jupter中可视化出来

from sklearn import tree
import pydotplus
#决策树图(不含含中文的输出方式)
list1 = ['var1','var2','var3','var4','var5','var6']
dot_data = tree.export_graphviz(model_tree, out_file=None,  
                                    feature_names=list1,
                                    filled=True, rounded=True, 
                                    special_characters=True)
graph = pydotplus.graph_from_dot_data(dot_data) 
graph.write_png("result2.png")#将图画出来

决策树参数详解

决策树调参注意事项

• 当样本少数量但是样本特征非常多的时候，决策树很容易过拟合，一般来说，样本数比特征数多一些会比较容易建立健壮的模型
• 如果样本数量少但是样本特征非常多，在拟合决策树模型前，推荐先做维度规约，比如主成分分析（PCA），特征选择（Losso）或者独立成分分析（ICA）。这样特征的维度会大大减小。再来拟合决策树模型效果会好。
• 推荐多用决策树的可视化，同时先限制决策树的深度（比如最多3层），这样可以先观察下生成的决策树里数据的初步拟合情况，然后再决定是否要增加深度。
• 在训练模型先，注意观察样本的类别情况（主要指分类树），如果类别分布非常不均匀，就要考虑用class_weight来限制模型过于偏向样本多的类别。
• 决策树的数组使用的是numpy的float32类型，如果训练数据不是这样的格式，算法会先做copy再运行。
• 如果输入的样本矩阵是稀疏的，推荐在拟合前调用csc_matrix稀疏化，在预测前调用csr_matrix稀疏化。

最后

以上就是单身乌冬面为你收集整理的决策树原理详解及python代码实现1、算法原理2、ID3、C4.5与Cart比较3、算法优缺点4、算法需要注意的点5、python代码实现的全部内容，希望文章能够帮你解决决策树原理详解及python代码实现1、算法原理2、ID3、C4.5与Cart比较3、算法优缺点4、算法需要注意的点5、python代码实现所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。