机器学习算法-决策树
1.K-近邻算法
（略）
2.线性回归
（略）
3.逻辑回归
（略）
4.决策树
4.1决策树算法简介
- 什么是决策树
决策树：是一种树形结构，其中每个内部节点表示一个属性上的判断，每个分支代表一个判断结果的输出，最后每个叶节点台标一种分类结果，本质是一棵由多个判断节点组成的树。
4.2决策树分类原理
1、熵
1.1概念
物理学上，熵Entropy是“混乱”程度的量度。
系统越有序，熵值越低；系统混乱或者分散，熵值越高
1948年香农提出了信息熵（Entropy）的概念。
- 信息理论：
1、从信息的完整性熵进行描述：
当系统的有序状态一致时，数据越集中的地方熵值越小，数据越分散的地方熵值越大。
2、从信息有序性上进行描述：
当数据量一致时，系统越有序，熵值越低；系统越混乱或者分散，熵值越高
“信息熵”(information entropy)时度量样本集合纯度最常用的一种指标。
假定当前样本集合D中第k类样本所占比例为pk（k=1,2,…|y|),
pk=\frac{C^K}{D},D为样本的所有数量， C^k 为第k类样本的数量。
D的信息熵定义为（log是以2为底，lg是以10为底）
Ent(D)=-\sum_{k=1}^{n}\frac{C^k}{D}log\frac{C^k}{D}=-\sum_{k=1}^np_klog_2p_k\
=-p_1log_2p_1-p_2log_2p_2-…-p_nlog_2p_n\
其中：Ent（D）的值越小，则D的纯度越高。
1.2案例
假定有16支球队，可以问4次来得到最后的答案。
二分法
信息熵等于4
Ent（D）=-(p1 * logp1+p2 * logp2 +…+ p16 * logp16)
其中p1,…p16分别是这16支球队夺冠的概率。
当每只球队夺冠概率相等都是1/16的时候：
Ent（D）= – (16 * 1/16 * log 1/16 ) = 4
篮球比赛里，有4个球队（ABCD），获胜概率分别为（1/2,1/4,1/8,1/8)
求Ent（D）
答案
\begin{aligned}Ent(D)&=-[\frac{1}{2}log_2(\frac{1}{2})+\frac{1}{4}log_2(\frac{1}{4})+\frac{1}{8}log_2(\frac{1}{8})+\frac{1}{8}log_2(\frac{1}{8})]\
&=\frac{1}{2}log_22+\frac{1}{4}log_24+\frac{1}{8}log_28+\frac{1}{8}log_28\
&=(\frac{1}{2}+\frac{1}{2}+\frac{3}{8}+\frac{3}{8})log_22\
&=\frac{7}{4}
\end{aligned}
2 决策树的划分依据一—-信息增益
2.1 概念
信息增益： 以某特征划分数据集前后的熵的差值。熵可以表示样本集合的不确定性，熵越大，样本的不确定性就越大。因此 可以使用划分前后集合熵的差值来衡量使用当前特征对于样本集合D划分效果的好坏。
信息增益=entroy(前)-entory(后)
注：信息增益表示得知特征X的信息而使得类Y的信息熵减少的程度。
- 定义公式
-
假定离散属性a有V个可能的取值
a^1,a^2,…,a^V
若使用a来对样本集D进行划分，则会产生V个分支节点。
\begin{array}{l}\
其中第V个分支节点包含了D中所有的属性a上取值为a^v的样本，记为D^v,\
我们可根据前面给出的信息熵公式计算出D^v的信息熵，再考虑到不同的分支\
所包含的样本不同，给分支节点赋予权重\frac{|D^v|}{|D|}
\end{array}
即样本数越多的分支节点的影像越大，于是可计算出用属性a对样本集D进行划分所获得的“信息增益”（information gain）
特征a对训练数据集D的信息增益Gain（D,a),定义为集合D的信息熵Ent（D）与给定特征a条件下D的信息条件熵Ent(D|a)之差，即公式为：
Gain(D,a)=Ent(D)-Ent(D|a)=Ent(D)-\sum_{v=1}^V\frac{D^V}{D}Ent(D^v)
公式的详细解释：
信息熵的计算:
Ent(D)=-\sum_{k=1}^{n}\frac{C^k}{D}log\frac{C^k}{D}
条件熵的计算：
Ent(D,a)=\sum_{v=1}^V\frac{D^v}{D}Ent(D^v)=-\sum_{v=1}^V\frac{D^v}{D}\sum_{k=1}^{K}\frac{C^{kv}}{D_v}log\frac{C^{kv}}{D_v}
其中：
\begin{array}{l}\
D^v表示a属性中第v分支节点包含的样本数\
C^{kv}表示a属性中第v个分支节点包含的样本数中，第k个列被下包含的言版本数\
\end{array}
一般而言，信息增益越大，则意味着使用属性a来进行划分所获得的“纯度提升”越大。因此我们可用信息增益来进行决策树的划分属性选择，著名的ID3决策树学习算法【Quinlan，1986】就是以信息增益为准则来划分属性的。
3决策树的划分依据二—-信息增益率
3.1概念
增益率：增益率是用前面的信息增益Grain(D,a)和属性a对应的“固有值”（intrinsic value）【Quinlan，1993J的比值来共同定义的。
Grain_ratio(D,a)=\frac{Grain(D,a)}{IV(a)}
其中：
IV(a)=-\sum_{v=1}^V\frac{D^v}{D}log\frac{D^v}{D}
属性a的可能取值数目越多（即V越大），则IV (a)的值通常会越大。
3.2案例
3.2.1 案例一
4.3cart剪枝
1 为什么要剪枝
随着树的增长，在训练集的精度是单调上升的，然后在独立测试样例熵测出的精度先上升后下降
出现这种情况的原因：
- 原因1：噪声、样本冲突，即错误的样本数据。
- 原因2：特征即属性不能完全座位分类标准。
- 原因3：巧合的规律性，数据量不够大。
剪枝（pruning)是决策树学习算法对付“过拟合”的主要手段。
2 常用的剪枝方法
决策树剪枝的基本策略是“预剪枝”（pre-pruning)和“后剪枝”（post_pruning)
- 预剪枝是指在决策树生成过程中，对每个节点在划分前后进行估计，若当前节点的划分不能带来决策树泛化性能提升，则停止划分并将当前节点标记为叶节点。
- 后剪枝则是先从训练集生成一棵完整的决策树，然后自底向上对非叶节点进行考察，若将该节点对应的子树替换为叶节点能带来决策树泛化性能提升，则将该子树替换为叶节点。
3 小结
- 剪枝原因
-
常用剪枝方法
4.4特征工程-特征提取
4 小结
-
特征提取
- 将任意数据（如文本或图像）转换为可用于机器学习的数字特征
- 特征提取分类
- 字典特征提取（特征离散化）
- 文本特征提取
- 图像特征提取
- 字典特征提取
- 字典特征提取就是对类别型数据进行转换
- api:sklearn.feature_extraction.DictVectorizer(sparse=True,…)
- aparse矩阵
- 1.节省内容
- 2.提高读取效率
- 注意：
- 对于特征当中存在类别信息的我们都会做one-hot编码处理
- 文本特征提取（英文）
- api:sklearn.feature_extraction.text.CountVectorizer(stop_words=[])
- stop_words — 停用词
- 注意: 没有sparse这个参数
- 单个字母，标点符号不做统计
- 文本特征提取（中文）
- 注意：
- 1、在中文文本特征提取之前，需要对句子（文章）进行分词（jieba)
- 2、里面依旧可以使用停用词，进行词语的限制
- dlfidf
- 主要思想
- 如果某个词或短语在一篇文章中出现的概率高，并且在其他文章中很少出现，则认为此词或者短语具有很好的
- 类别区分能力，适合来分类
- tfidf
- tf — 词频
- id — 逆向文章频率
- api:sklearn.feature_extraction.text.TfidVectorizer
- 注意：
- 分类机器学习算法进行文章分类中前期数据处理
4.5决策树算法api
- class sklearn.tree.DecisionTreeClassifier(criterion=’gini’,max_depth=None,random_state=None)
- criterion
-
特征选择标准
-
“gini”或者“entropy”,前者台标基尼系数，后者台标信息增益。默认“gini”,即CART算法。
-
min_samples_split
-
内部节点再划分所需最小样本数
-
min_samples_leaf
-
叶子节点最少样本数
-
max_depth
-
决策树最大深度
-
模型样本量多时推荐设置，一般可取值10-100
-
random_state
-
随机数种子
4.6案例:泰塔尼克号乘客生存预测
1、案例背景
案例：https://www.kaggle.com/c/titanic/overview
数据：http://biostat.mc.vanderbilt.edu/wiki/pub/Main/DataSets/titanic.txt
以上连接无法访问了！
如下方式找到：
https://www.kaggle.com/code/alexisbcook/titanic-tutorial
https://www.kaggle.com/c/titanic/data
注册kaggle不显示验证码（Captcha must be filled out）如何解决？
https://blog.csdn.net/m0_51536175/article/details/130425157
4.2 网站显示结果
- http://webgraphviz.com
5决策树总结
- 优点
- 简单的理解和解释，树木可视化
- 缺点
- 决策树学习者可以创建不能很好地推广数据的过于复杂的树，容易发生过拟合
- 改进
- 减枝cart算法
- 随机森林（集成学习的一种）
4.7 回归决策树
1、原理概述
不管回归决策树还是分类决策树，都会存在两个核心问题：
- 如何选择划分点
- 如何决定叶节点的输出值
2、算法描述
- 输入：训练数据集D
-
输出：回归树f(x)
-
在训练数据集所在的输入空间中，递归的将每个区域划分为两个子区域并决定每个子区域熵的输出值，构建二叉决策树
- (1)选择最优切分特征j与切分点s，求解
min_{j,s}[min_{c1}\sum_{x_i\in R_1(j,s)}(y_i-c_1)^2+min_{c2}\sum_{x_i\in R_2(j,s)}(y_i-c_2)^2]\
遍历特征j，对固定的切分特征j扫描切分点s，选择使得上式达到最小值的对（j,s)
- (2)用选定的对（j,s)划分区域并决定相应的输出值：
R_1(j,s)=x|x^{(j)}\le s,R_2(j,s)=x|x^{(j)}>s\
\hat{c}_m=\frac{1}{N}\sum_{x1\in R_m(j,s)}y_i,x\in R_m,m=1,2- (3)继续对两个子区域调用步骤（1）和（2），直到满足停止条件。
- (4)将输入空间划分为M个区域R1，R2，。。。Rm，生成决策树：
f(x)=\sum_{m=1}^M\hat{c}_mI(x\in R_m)
3、简单实例
3.1实例计算过程
3.2回归决策树和线性回归对比
code
import numpy as np
import matplotlib.pyplot as plt
from sklearn.tree import DecisionTreeRegressor
from sklearn import linear_model
# 生成数据
x = np.array(list(range(1, 11))).reshape(-1, 1)
y = np.array([5.56, 5.70, 5.91, 6.40, 6.80, 7.05, 8.90, 8.70, 9.00, 9.05])
# 训练模型
model1 = DecisionTreeRegressor(max_depth=1)
model2 = DecisionTreeRegressor(max_depth=3)
model3 = linear_model.LinearRegression()
model1.fit(x, y)
model2.fit(x, y)
model3.fit(x, y)
# 模型预测
# 生成1000个数
X_test = np.arange(0.0, 10.0, 0.01).reshape(-1, 1)
print(X_test.shape)
y_1 = model1.predict(X_test)
y_2 = model2.predict(X_test)
y_3 = model3.predict(X_test)
# 结果可视化
plt.figure(figsize=(10, 6), dpi=100)
plt.scatter(x, y, label="data")
plt.plot(X_test, y_1, label="max_depth=1")
plt.plot(X_test, y_2, label="max_depth=3")
plt.plot(X_test, y_3, label="liner regression")
plt.xlabel("data")
plt.ylabel("target")
plt.title("Decision Tree Regression")
plt.legend()
plt.show()