ng-决策树
特征选择算法
我们希望选择具有良好分类能力的特征，为此我们引入信息增益来衡量不纯度
设X是取有限个值的随机变量，则概率分布为
P(X = xi) = pi, i = 1, 2, ⋯, n
定义随机变量X的熵为 $$H(X)=-\sum_{i=1}^np_i\log p_i$$
log以2为底时，熵的单位是比特，以e为底时，熵的单位是纳特。
若随机变量只取两个值(伯努利分布)，熵可以写为关于p的函数 H(p) = −plog p − (1 − p)log (1 − p)
Information gain信息增益
一般的，定义 (信息增益) 特征A对训练数据集D的信息增益g(D, A),定义为集 合D的经验熵H(D)与特征A给定条件下D的经验条件熵H(D|A)之差，即 g(D, A) = H(D) − H(D|A)
- 在决策树的二叉树场景下，上式可写为 = H(p1root) − (wleftH(p1left) + wrightH(p1right))
我们总是选择信息增益更大的决策A用于树的生成。
数学描述
设训练数据集为D,|D|表示其样本容量，即样本个数。设有K个类Ck, k= 1, 2, ⋯, K,|Ck|为属于类Ck的样本个数，∑|Ck| = |D|。设特征A有n个不同的 k = 1 取值{a1, a2, ⋯, an},根据特征A的取值将D 划 分 为 n个子集D1, D2, ⋯, Dn, |Di| 为Di的样本个数，$\sum_i^n|D_i|=|D|$。记子集Di中属于类Ck的样本的集合为Dik,即 i = 1 Dik = Di ∩ Ck, |Dik|为Dik 的样本个数。于是信息增益的算法如下。
(1)计算数据集D的经验熵H(D)，这代表原始数据集的混乱程度（直接按照将要预测特征求熵） $$H(D)=-\sum_{k=1}^K\frac{|C_k|}{|D|}\log_2\frac{|C_k|}{|D|}$$ (2)计算特征A对数据集D的经验条件熵H(D|A) $$H(D|A)=\sum_{i=1}^n\frac{|D_i|}{|D|}H(D_i)=-\sum_{i=1}^n\frac{|D_i|}{|D|}\sum_{k=1}^K\frac{|D_{ik}|}{|D_i|}\log_2\frac{|D_{ik}|}{|D_i|}$$ (3)计算信息增益 g(D, A) = H(D) − H(D|A)
- 引入信息增益比 $$g_R(D,A)=\frac{g(D,A)}{H_A(D)}$$ 其中，$H_A(D)=-\sum_{i=1}^n\frac{|D_i|}{|D|}\log_2\frac{|D_i|}{|D|},n$是特征A取值的个数。 这是为因为在决策过程中，算法直接使用信息增益，会导致进行决策倾向于选择分类特征较多的节点，为此引入信息增益比来规避这一问题。
ID3算法->C4.5算法
用于生成树
剪枝算法
决策树的剪枝往往通过极小化决策树整体的损失函数(loss function)或代价函数(cost function)来实现。设树T的叶结点个数为|T|,t是树T的叶结点，该叶结点有Nt个样本点，其中k类的样本点有Ntk个，k = 1, 2, ⋯, K,Ht(T)为叶结点t 上的经验熵，α ≥ 0为参数，则决策树学习的损失函数可以定义为
$$C_\alpha(T)=\sum_{t=1}^{|T|}N_tH_t(T)+\alpha|T|$$ 其中经验熵为 $$H_t(T)=-\sum_k\frac{N_{tk}}{N_t}\log\frac{N_{tk}}{N_t}$$ 在损失函数中，将式(5.11)右端的第 1 项记作 $$C(T)=\sum_{t=1}^{|T|}N_tH_t(T)=-\sum_{t=1}^{|T|}\sum_{k=1}^KN_{tk}\log\frac{N_{tk}}{N_t}$$ ### 这时有 Cα(T) = C(T) + α|T|
α的大小决定了我们对树的复杂程度的控制。我们为了防止过拟合，需要在C（T）和
T之间取舍。
剪枝算法的基本思路就是，从叶节点自下而上的剪枝，如果剪枝后的惩罚函数变小了，则返回剪枝之后的树继续进行剪枝。
CART算法
回归树算法
本质上实在构建一个及其细分的分段函数用于回归算法，每次分段遵循最小的残差平方和进行。
采用启发式的方法，选择第j个变量x(j)
和它取的值s,作为切分变量(splitting
variable)和切分点(splitting
point),并定义两个区域（事实上遍历j的思路有很多）： R1(j, s) = {x|x(j) ≤ s} 和 R2(j, s) = {x|x(j) > s}
然后寻找最优切分变量j和最优切分点s。具体地，求解 minj, s[minc1∑xi ∈ R1(j, s)(yi − c1)2 + minc2∑xi ∈ R2(j, s)(yi − c2)2]
算法如下：
(1)选择最优切分变量j与切分点s,求解 minj, s[minc1∑xi ∈ R1(j, s)(yi − c1)2 + minc2∑xi ∈ R2(j, s)(yi − c2)2]
遍历变量j,对固定的切分变量j扫描切分点s,选择使上式达到最小值的对
(2)用选定的对(j, s)划分区域并决定相应的输出值：
R1(j, s) = {x|x(j) ≤ s}, R2(j, s) = {x|x(j) > s}
$$\hat{c}_m=\frac1{N_m}\sum_{x_i\in
R_m(j,s)}y_i,\quad x\in R_m,\quad m=1,2$$
(3)继续对两个子区域调用步骤
(1),(2),直至满足停止条件。(4)将输入空间划分为M个区域R1, R2, ⋯, RM,生成决策树：
$$f(x)=\sum_{m=1}^M\hat{c}_mI(x\in
R_m)$$
分类树算法
使用基尼指数作为划分标准，其实和上文的熵趋势上一样。
基尼指数
$$\mathrm{Gini}(p)=\sum_{k=1}^Kp_k(1-p_k)=1-\sum_{k=1}^Kp_k^2$$
对于给定的样本，基尼指数为 $$\mathrm{Gini}(D)=1-\sum_{k=1}^K\left(\frac{|C_k|}{|D|}\right)^2$$
one-hot编码
也可以用到神经网络，逻辑回归等领域， 
决策树可以处理连续值特征,方法是在每个节点上考虑不同的阈值进行划分,计算信息增益,选择能提供最大信息增益的阈值进行分割。这样可以递归地构建决策树的其余部分。此外,决策树算法还可以扩展到回归问题,预测数字输出。
实战：预测天气
代码分两个模块 - 数据分析 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44## 基础函数库
import numpy as np
import pandas as pd
## 绘图函数库
import matplotlib.pyplot as plt
import seaborn as sns
data = pd.read_csv('../data/weather.csv')
# data.info()
data = data.fillna(-1)
#k考察数据整体
def overview():
global data
data.info()
data.describe()
numerical_features = [x for x in data.columns if data[x].dtype == np.float64]
category_features = [x for x in data.columns if data[x].dtype != np.float64 and x != 'RainTomorrow']
# 画箱线图函数
def boxlinegraph():
global numerical_features
global category_features
for col in data[numerical_features].columns:
if col != 'RainTomorrow':
sns.boxplot(x='RainTomorrow', y=col, saturation=0.5, palette='pastel', data=data)
plt.title(col)
plt.show()
## 把所有的相同类别的特征编码为同一个值
def get_mapfunction(x):
mapp = dict(zip(x.unique().tolist(),
range(len(x.unique().tolist())))) # 将这些独特的值与一个范围（从0开始，长度为独特值的数量）配对，创建一个元组列表。每个独特值对应一个唯一的整数。
def mapfunction(y):
if y in mapp:
return mapp[y]
else:
return -1
return mapfunction
for i in category_features:
data[i] = data[i].apply(get_mapfunction(data[i]))
boxlinegraph()1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54import pandas as pd
import numpy as np
from sklearn.model_selection import train_test_split
from xgboost.sklearn import XGBClassifier
import matplotlib.pyplot as plt
import seaborn as sns
data = pd.read_csv('../data/weather.csv')
# data.info()
data = data.fillna(-1)
numerical_features = [x for x in data.columns if data[x].dtype == np.float64]
category_features = [x for x in data.columns if data[x].dtype != np.float64 ]
def get_mapfunction(x):
mapp = dict(zip(x.unique().tolist(),
range(len(x.unique().tolist())))) # 将这些独特的值与一个范围（从0开始，长度为独特值的数量）配对，创建一个元组列表。每个独特值对应一个唯一的整数。
def mapfunction(y):
if y in mapp:
return mapp[y]
else:
return -1
return mapfunction
for i in category_features:
data[i] = data[i].apply(get_mapfunction(data[i]))
## 选择其类别为0和1的样本 （不包括类别为2的样本）
data_target_part = data['RainTomorrow']
data_features_part = data[[x for x in data.columns if x != 'RainTomorrow']]
## 测试集大小为20%， 80%/20%分
x_train, x_test, y_train, y_test = train_test_split(data_features_part, data_target_part, test_size = 0.2, random_state = 2020)
## 定义 XGBoost模型
clf = XGBClassifier()
# 在训练集上训练XGBoost模型
clf.fit(x_train, y_train)
## 在训练集和测试集上分布利用训练好的模型进行预测
train_predict = clf.predict(x_train)
test_predict = clf.predict(x_test)
from sklearn import metrics
## 利用accuracy（准确度）【预测正确的样本数目占总预测样本数目的比例】评估模型效果
print('The accuracy of the Logistic Regression is:',metrics.accuracy_score(y_train,train_predict))
print('The accuracy of the Logistic Regression is:',metrics.accuracy_score(y_test,test_predict))
## 查看混淆矩阵 (预测值和真实值的各类情况统计矩阵)
confusion_matrix_result = metrics.confusion_matrix(test_predict,y_test)
print('The confusion matrix result:\n',confusion_matrix_result)
# 利用热力图对于结果进行可视化
plt.figure(figsize=(8, 6))
sns.heatmap(confusion_matrix_result, annot=True, cmap='Blues')
plt.xlabel('Predicted labels')
plt.ylabel('True labels')
plt.show()