【西瓜书笔记】补充3：树模型补充.md

CART：Classification and Regression Tree. 基础更多集中在CART树模型中。

树模型的基本思路就是对训练集进行划分，使得划分后的集合的纯度变得“更纯”。因此问题的要点在于：

如何定义集合的纯度。（划分前和划分后）如何对集合进行划分。（选择哪个特征和阈值）如何确定叶子节点的值。（决定了预测结果）

CART模型既能解决分类，也能解决回归问题。在面对分类问题的时候，使用熵和GINI指数。在面对回归问题时，使用方差。

GINI指数的公式
Gini ⁡ ( D ) = ∑ k = 1 ∣ Y ∣ ∑ k ′ ≠ k p k p k ′ = ∑ k = 1 ∣ Y ∣ p k ∑ k ′ ≠ k p k ′ = ∑ k = 1 ∣ Y ∣ p k ( 1 − p k ) = 1 − ∑ k = 1 ∣ Y ∣ p k 2 operatorname{Gini}(D)=sum_{k=1}^{|mathcal{Y}|} sum_{k^{prime} neq k} p_{k} p_{k^{prime}}=sum_{k=1}^{|mathcal{Y}|} p_{k} sum_{k^{prime} neq k} p_{k^{prime}}=sum_{k=1}^{|mathcal{Y}|} p_{k}left(1-p_{k}right)=1-sum_{k=1}^{|mathcal{Y}|} p_{k}^{2} Gini(D)=k=1∑∣Y∣​k′​=k∑​pk​pk′​=k=1∑∣Y∣​pk​k′​=k∑​pk′​=k=1∑∣Y∣​pk​(1−pk​)=1−k=1∑∣Y∣​pk2​
这里k表示分类标签的个数。 p k 2 p_{k}^2 pk2​表示有放回地连续两次抽取到第k类样本的概率。那么GINI指数其实就表示从数据集 D D D中随机抽取两个样本，其类别标记不一致的概率，如果值越小，说明当前这个集合的纯度越纯。

熵的公式 p i log ⁡ p i p_{i}log p_{i} pi​logpi​做泰勒展开，就近似于基尼指数。

在回归问题中，就可以这么看：样本越集中，就越纯，样本越散，就越不纯。方差就可以度量集合标签的集中程度。

就是暴力遍历，遍历所有特征，遍历每一个特征的所有阈值。如果变得更纯，划分就是有效的。在所有划分中找到纯度最高的划分。

如果是分类问题，就使用占比方法计算预测值，哪种类别多就说明是这种类别的概率大。比如说一个叶子节点包括7个样本，3个红球，2个蓝球，2个黄球，那么一个新样本落到这个叶子节点后，3/7的概率是红，2/7的概率是蓝，2/7的概率是黄。所以说决策树在分类问题中天生就可以输出概率值，这个概率值其实就是最大似然估计，就是通过频率来估计。

回归问题就使用叶子节点中的均值来计算预测值。有个新样本落入叶子节点，输出值就是均值。

问题：

XGBoost如何定义“纯度”？XGBoost如何对集合进行划分？XGBoost如何确定每个叶子节点的值？

通过数据进行不同的有放回的采样，得到几个不同的子数据集，在这几个子数据集上训练不同的模型，然后得到的模型集中到一块融合。如果模型是决策树，总的模型就是随机森林。

这里的随机有两个方面：

随机采样产生子数据集一个子数据集上，树模型在分裂的时候对特征也会进行随机的选取，从1000个特征中选择100个特征，然后从100个特征中遍历选择最优的一个特征的阈值。

使得树模型之间尽量不一样

跟树模型思路有关系，但是方式已经很不一样了。所以学习路径应该是：

针对GBDT，假设我们有三棵树
f 1 ( x ) + f 2 ( x ) + f 3 ( x ) f_{1}(x)+f_{2}(x)+f_{3}(x) f1​(x)+f2​(x)+f3​(x)
我们定义
f i ‾ ( g ( x ) ) = f i ( x ) + g ( x ) overline{f_{i}}(g(x))=f_{i}(x)+g(x) fi​​(g(x))=fi​(x)+g(x)
所以有
f 2 ‾ ( f 1 ( x ) ) = f 2 ( x ) + f 1 ( x ) f 3 ‾ ( f 2 ‾ ( f 1 ( x ) ) ) = f 3 ( x ) + f 2 ‾ ( f 1 ( x ) ) = f 3 ( x ) + f 2 ( x ) + f 1 ( x ) begin{aligned} overline{f_{2}}left(f_{1}(x)right) &=f_{2}(x)+f_{1}(x) \ overline{f_{3}}left(overline{f_{2}}left(f_{1}(x)right)right) &=f_{3}(x)+overline{f_{2}}left(f_{1}(x)right) \ &=f_{3}(x)+f_{2}(x)+f_{1}(x) end{aligned} f2​​(f1​(x))f3​​(f2​​(f1​(x)))​=f2​(x)+f1​(x)=f3​(x)+f2​​(f1​(x))=f3​(x)+f2​(x)+f1​(x)​
f 3 ‾ ( f 2 ‾ ( f 1 ( x ) ) ) overline{f_{3}}left(overline{f_{2}}left(f_{1}(x)right)right) f3​​(f2​​(f1​(x)))这个东西其实很像神经网络。区别在于，神经网络可以直接从最后层往最前层进行反向传播，一次性更新参数。GBDT只能每一层算一个梯度，不是一次性从后往前更新：f1固定了，再用梯度计算f2；f2固定了，再用梯度计算f3；f3计算出来了，固定，再用梯度计算f4。GDBT拟合性就不如神经网络。

DeepForest

能在多项式(polynomial)的时间复杂度内求解，就叫p问题。比如说N个数字的全排列就不是P问题， 因为N的阶乘不是个多项式时间内解决的问题。

NP问题是在多项式时间内验证这个解对不对。一个是求解，一个是验证。如果一个问题能求解，那就能验证。但是如果一个问题能在多项式时间内验证，是不是一定能够被求解呢?这就叫NP问题是不是等于P问题。

现在大部分人认为NP问题不等于P问题。

NP难：没办法在多项式时间内求解。

西瓜书35页，从AUC讨论到了“排序”损失，也就是书中式(2.21)：
ℓ rank  = 1 m + m − ∑ x + ∈ D + ∑ x − ∈ D − ( I ( f ( x + ) < f ( x − ) ) + 1 2 I ( f ( x + ) = f ( x − ) ) ) ell_{text {rank }}=frac{1}{m^{+} m^{-}} sum_{boldsymbol{x}^{+} in D^{+}} sum_{boldsymbol{x}^{-} in D^{-}}left(mathbb{I}left(fleft(boldsymbol{x}^{+}right) 假设我们有5个样本，三个正样本，两个负样本。 m + = 3 , m − = 2 m^{+}=3, m^{-}=2 m+=3,m−=2。我们对正负样本两两组合，就有6种组合，所以 m + m − = 6 m^{+} m^{-}=6 m+m−=6。等式右边括号里的内容就是找到这6个组合中，有多少个是满足正样本的预测值小于负样本的预测值（或者等于），也就是不好的预测。

所以，从6种组合中，随机抽一个正负样本对，正样本预测值大于负样本预测值，正样本排在负样本之前的概率就是 1 − l 1-l 1−l。完美的排序就是- -+++。

那为何与AUC有关？AUC就等于 1 − l 1-l 1−l，AUC表达的物理含义就是随机抽一个正负样本对，正样本预测值大于负样本预测值的概率。

我们回看AUC的图，也就是ROC曲线图。

（source:https://medium.datadriveninvestor.com/understanding-auc-roc-clearly-explained-74c53d292a02）

纵坐标和横坐标分别是真正率和假正率:
y ( t ) = T P R = T P T P + F N x ( t ) = F P R = F P T N + F P begin{aligned} &y(t)=mathrm{TPR}=frac{T P}{T P+F N} \ &x(t)=mathrm{FPR}=frac{F P}{T N+F P} end{aligned} ​y(t)=TPR=TP+FNTP​x(t)=FPR=TN+FPFP​​
它们表示当我们选择一个阈值 t t t的时候，TP和FP分别为多少。对应AUC和ROC曲线来说，就是通过改变阈值 t t t得到了一条曲线，因为一个阈值 t t t，对应一个坐标对 ( x ( t ) , y ( t ) ) (x(t), y(t)) (x(t),y(t))。然后我们做一个变量替换， N + ( t ) = T P N^{+}(t)=TP N+(t)=TP表示预测值大于 t t t的正样本数量， N − ( t ) = F P N^{-}(t)=FP N−(t)=FP表示预测值大于 t t t的负样本数量。 N + , N − N^{+},N^{-} N+,N−分别表示总的正负样本个数。所以
y ( t ) = T P R = N + ( t ) N + x ( t ) = F P R = N − ( t ) N − begin{aligned} &y(t)=mathrm{TPR}=frac{N^{+}(t)}{N^{+}} \ &x(t)=mathrm{FPR}=frac{N^{-}(t)}{N^{-}} end{aligned} ​y(t)=TPR=N+N+(t)​x(t)=FPR=N−N−(t)​​
假如说我们的分类器是个随机预测的模型，那么应该有
N + N − = N + ( t ) N − ( t ) ⇒ N + ( t ) N + = N − ( t ) N − frac{N^{+}}{N^{-}}=frac{N^{+}(t)}{N^{-}(t)}Rightarrowfrac{N^{+}(t)}{N^{+}}=frac{N^{-}(t)}{N^{-}} N−N+​=N−(t)N+(t)​⇒N+N+(t)​=N−N−(t)​
也就是说，无论 t t t值如何变化，只要分类器是随机预测，那么对应的ROC曲线应该是一条对角直线。

现在我们来证明，AUC就是随机从正负样本中选取一堆正负样本对，正样本预测值大于负样本预测值的概率。

假设我们随机选了一个负样本 S − S^{-} S−,它的预测值在 t t t和 t + Δ t t+Delta t t+Δt之间的概率是
P ( t < S − < t + Δ t ) = P ( S − > t + Δ t ) − P ( S − > t ) = N − ( t + Δ t ) N − − N − ( t ) N − = x ( t + Δ t ) − x ( t ) = Δ x ( t ) begin{aligned} &P(tt+Delta tright)-P(S^{-}>t)\ =&frac{N^{-}(t+Delta t)}{N^{-}}-frac{N^{-}(t)}{N^{-}}\ =&x(t+Delta t)-x(t)\ =&Delta x(t) end{aligned} ====​P(tt+Δt)−P(S−>t)N−N−(t+Δt)​−N−N−(t)​x(t+Δt)−x(t)Δx(t)​
那么随机从正负样本中选取一堆正负样本对，正样本预测值大于负样本预测值的概率就是
P ( S + > S − ) = ∑ P ( S + > S − ∣ t ≤ S − ≤ t + Δ t ) P ( t ≤ S − ≤ t + Δ t ) = ∑ P ( S + > t ) ⋅ Δ x ( t ) = ∑ y ( t ) ⋅ Δ x ( t ) = ∫ y ( t ) d x ( t ) = A U C begin{aligned} &P(S^{+}>S^{-})\ =&sum P(S^{+}>S^{-}|tleq S^{-}leq t+Delta t)P(tleq S^{-}leq t+Delta t)\ =&sum P(S^{+}>t)cdotDelta x(t)\ =&sum y(t)cdot Delta x(t)\ =&int y(t)dx(t)\ =&AUC end{aligned} =====​P(S+>S−)∑P(S+>S−∣t≤S−≤t+Δt)P(t≤S−≤t+Δt)∑P(S+>t)⋅Δx(t)∑y(t)⋅Δx(t)∫y(t)dx(t)AUC​
这里我们利用了条件概率公式，并同时考虑所有 t t t可能的取值。于是我们证明了
A U C = 1 − ℓ AUC=1-ell AUC=1−ℓ

评估函数可能使我们最终的目标，损失函数是我们要优化的东西。评估函数有可能不可微分，所有需要用损失函数来做替代。我们要尽量选择损失函数与评估函数接近。

在分类问题中，如果是二分类问题，可以用F1-score： F 1 = 2 × P × R P + R F 1=dfrac{2 times P times R}{P+R} F1=P+R2×P×R​. 如果是多分类问题，可以用micro-F1和macro-F1。但是如果使用micro-F1，它分数足够高可能并不是因为各个类别都预测得很准，只是因为把数量最多的类别预测的很好。如果使用macro-F1，就会考虑类别不均衡，如果数量少的类别预测得不好，分数就不会很好。

在回归问题中，MSE不是一个很好的评估指标，因为没有一个合适的数值参考判断好坏。可以用 r 2 r^{2} r2，这个指标的物理含义是用最简单的均值模型来做对比。如果模型预测相比均值模型对比更好的话， r 2 r^{2} r2就靠近1。如果是时序预测模型，就用其他的指标，比如WRMSSE。

查全率和查准率很难兼得。假设我们有1000个样本，100个正样本，900个负样本。如果我预测出了90个正样本，查全率就是90%。如果我预测出的10个正样本中8个是真的正样本，那么查准率就是80%。如果我为了100%的查全率，我可以预测1000个样本都是正样本，但是查准率就只有100/1000=10%。如果我为了保证100%的查准率，可以只预测一个正样本，但是查全率就只有1/100=1%。所以一般要考虑适中指标F1-score，或者加了权重的F1-score。