逻辑回归

逻辑回归 ( Logistic Regression ) 的名字里虽然带有Regression, 但是它其实是一个经典的二元分类算法，并非预测连续数值的回归模型。

在之前提到的Perceptron和Adaline中，我们的核心一直是计算特征与权重的线性组合，也就是Net Input， $z = w^Tx$。在Adaline中，激活函数 $\phi(z)$实际上就是 $z$本身。这意味着我们实际上在用 $w^Tx$ 直接拟合连续的标签值。但是当我们的任务是去分类并希望得到一个概率时，矛盾就产生了：线性组合的取值是整个实数轴，但是概率是限制在 $(0, 1)$ 之间的。因此如果我们强行说 $w^Tx$ 就是概率，当特征值 $x$很大的时候，你可能会算出一个等于10或者等于100的概率，而这在数学上是完全不可能出现的。

所以总的来说，在机器学习的分类任务中，我们面临一个根本性的矛盾，那就是我们的线性模型输出 $z = w^Tx$ 是一个可以在全实数范围内任意游走的数值，但是我们往往渴望一个概率值的预测结果，而概率值很明显，是被严格限制在0和1之间的。为了连接这两个截然不同的区间，我们需要使用一些精妙的数学方法。

逻辑回归的计算

在逻辑回归中，我们使用 Logit Function 来实现空间的拉伸。他接受一个从0到1的概率值 $p$，通过计算对数来将这个0-1的区间映射到整个无穷大的数轴上面。这也就意味着如果你有一个概率，那么Logit就能够告诉你它在实数轴上对应哪个点。

我们不是直接把线性组合 $z = w^Tx$ 丢进logit里面去直接压缩，而是定义了一种概率的某种变换，我们叫做 对数几率 (Log-odds) 变换。换句话说，逻辑回归的灵魂等式实际上就是：

$$logit(p) = w^Tx$$

因此我们不是在拟合概率本身，而是在拟合那个被Logit函数拉直到全实数范围的概率变换体。

然而在实际预测中我们的模型会优先算出来 $z$，也就是那个不受限的实数，而我们要做的是把这个数压回概率区间。很简单，我们只需要找到Logit函数的反函数就可以了。那么Logit的反函数是什么？是Sigmoid函数：

$$\phi(z) = \frac{1}{1 + e^{-z}}$$

Sigmoid函数正好做了Logit的反面工作：接受任何实数输入 $z$，然后将其平滑挤压到0-1的区间内。Sigmoid函数的特征是：当 $z$趋于正无穷时，输出趋近于1；反之当 $z$趋向于负无穷，输出趋近于0。

因此如果我们想要得到概率值，则在 $logit(p)$ 的基础上，通过代数反求就可以知道：

$$p = \phi(w^Tx)$$

而这里的 $\phi(z)$ 正是Sigmoid。

如果你把这两个函数画在同一页里看，会非常有画面感：Sigmoid是一条平滑的S形曲线，中间在 $z=0$ 处穿过0.5，左边无限贴近0，右边无限贴近1；而Logit刚好反过来，在 $p \to 0$ 和 $p \to 1$ 的两端会向负无穷和正无穷发散，中间在 $p=0.5$ 的时候等于0。也就是说，Sigmoid负责“把实数压成概率”，Logit负责“把概率拉回实数轴”。这对互逆关系就是逻辑回归最核心的变换齿轮。

逻辑回归的训练

在之前的Adaline中，我们通过最小化误差平方和来更新权重。但是在这里由于我们输出的是概率，因此我们引入了一个更符合统计直觉的目标：最大似然估计 (Maximum Likelihood Estimation, MLE)。

想象一下我们有一堆鸢尾花数据，那么Likelihood $L(w)$的物理意义是，在特定的权重 $w$下，这组观测数据出现的总概率是多少。而我们的目标是通过不断调整 $w$，来让这个 $L(w)$达到最大。这意味着我们要让模型最大化地解释当前已经发生的数据，而这就是MLE。具体可以阅读我之前写过的这篇文章：

提到的 $L(w)$ 就是：

$$L(w) = P(y | x; w) = \prod_{i = 1}^n P(y^{(i)} | x^{(i)}; w) = \prod_{i = 1}^n (\phi(z^{(i)}))^{y^{(i)}} (1 - \phi(z^{(i)}))^{1 - y^{(i)}}$$

然而在数学实现上直接对一连串的概率做乘法运算不仅计算量大，而且还特别容易产生数值下溢。因此我们会将这个似然函数取自然对数，得到 Log-Likelihood Function ，这样原本的复杂联乘运算就变成了简单的求和运算：

$$l(w) = \log L(w) = \sum_{i = 1}^n [y^{(i)} \log(\phi(z^{(i)})) + (1 - y^{(i)}) \log(1 - \phi(z^{(i)}))]$$

所以我们只需要最大化个样本预测正确的对数概率之和就可以了，因为对数函数单调递增，所以在数学上这和直接最大化原始的似然函数是完全等价的。

更有趣的是，由于我们想要像Adaline那样同样使用梯度下降来最小化误差，这里我们给函数加一个负号，从而定义了逻辑回归的代价函数 $J(w)$，也叫交叉熵损失 (Cross-Entropy Loss)：

$$J(w) = \sum_{i = 1}^n [-y^{(i)} \log(\phi(z^{(i)})) - (1 - y^{(i)}) \log(1 - \phi(z^{(i)}))]$$

当真实标签 $y = 1$的时候，如果模型预测的概率 $\phi(z)$ 接近1，代价 $J$就会特别小。但如果模型预测接近0，则代价就会爆炸式增长，就如同这张图所示：

假如我们有一个真实标签为 $y = 1$ 的数据，而模型说我有99%的信心说这是1，也就是 $\phi(z) = 0.99$。那么我们根本不需要惩罚他啊，代价函数的值接近于零。但如果模型说我觉得有 1% 的可能性这是 $y = 1$，那么这是一个严重的误判。为了能够让模型记住这个教训，我们需要给它一个巨大的惩罚。这个机制不仅要求逻辑回归预测正确，还要求模型在正确的方向上尽可能自信。

进步了吗？进步在哪？

逻辑回归相比于感知机和Adaline要更强大，但是强大在哪？

我们知道在感知机中，通过引入偏置项 $w_0$， 我们让模型在全实数空间的Net Input $z = w^Tx$ 上寻找一个过原点的切割点。由于 $w_0$ 吸收了阈值 $\theta$，所以我们可以说，决策的分界点就是 $z = 0$。这意味着如果 $z > 0$，那么感知机就会通过阶跃函数直接将结果判断为正类。而Adaline虽然在训练阶段使用线性激活函数 $\phi(z) = z$ 来计算误差平方和来优化权重，但是在最好的决策阶段，它依然套用相同的阈值逻辑，还是以 $z = 0$ 作为分界线。

但是逻辑回归通过logit和Sigmoid这一套下来我们将 $z$ 转换成了概率。这意味着不仅模型能够告诉你类别，我们还能知道模型对于他的判断有多大把握。例如，当 $\phi(z) = 0.8$ 的时候，这可能意味着样本有 80%的概率属于A。

除了能够返还概率，Sigmoid还能够帮助构造一个更稳健的模型。例如感知机里只要样本被正确分类，样本距离决策边界的距离远近都不会触发模型去微调权重，而是只有错了再触发更新。这就导致感知机的收敛极度依赖数据是否线性可分。而逻辑回归使用Sigmoid，我们得到的代价函数Log-likelihood是连续且处处可导的。这意味着即使样本分类正确，模型依然会为了提高概率信心来继续微调权重，来找到泛化能力更强的边界。

所以，如果我们想要自己实现逻辑回归，只需要将Adaline的代码的激活函数替换为Sigmoid，然后再把原来衡量物理距离的误差平方和替换为基于对数似然的交叉熵损失就ok了。

调优与评估

我们知道了如何训练一个逻辑回归模型，但是我们需要考虑如何解决过拟合和欠拟合的问题。

我相信这两个概念应该很容易理解。一个死刷题拿满分的学生不一定能够在未来的考试中一定取得好成绩。这就是过拟合 (Overfitting)，模型可能因为参数过多或者逻辑过于复杂，导致它记住了训练数据中的噪点或偶然误差，而导致它在新数据上面的泛化能力极差。这在统计学上我们也叫做 高方差 (High Variance)

反之，欠拟合就是一个大脑皮层褶皱被拉平的学生，无论怎么学习都抓不住重点。模型可能因为过于简单，无法捕捉到数据后面的核心规律，表现为训练误差和测试误差都很高。

因此，找到一个好的模型应该秉承中庸之道，找到一个良好的折中点，让模型复杂度和泛化力之间达成和谐。

为了解决过拟合的问题，我们引入了 正则化 (Regularization)这个概念，来帮助我们控制参数权重 $w$ 的数值。想象一下一个权重 $w$ 的数值变得极其巨大，意味着模型可能对某个特征产生了过度的依赖，而这往往是过拟合的先兆。因此我们使用L2 Regularization，在原有的代价函数后面加一个惩罚项来计算权重向量长度的平方：$\frac{\lambda}{2} ||w||^2$ 来惩罚那些极端的参数：

现在我们的代价函数就是两个人物的结合体：

$$J(w) = \sum_{i = 1}^n [\text{Original Loss}] + \frac{\lambda}{2} \sum_{j = 1}^m w_j^2$$

参数 $\lambda$ 叫做正则化参数，来控制正则化力度。 $\lambda$ 越大惩罚越重，模型就更倾向于使用简单的逻辑来抑制过拟合。反之如果 $\lambda$ 太小，限制不够严厉，模型就会重新陷入过拟合的问题。

这意味着在训练过程中模型要面临两个任务。首先为了尽可能最小化原始代价，要尽可能预测准确；其次为了保证模型足够简单，我们的权重也要尽可能小。

在Scikit-Learn里面我们一般使用参数 $C$来调节标准化力度，而C不是什么新的概念，而是被定义为 $\lambda$ 的倒数： $C = 1 / \lambda$。这意味着如果我们减小C的数值，我们实际上是在增加正则化的强度。

支持向量机 (SVM)

逻辑回归中我们尝试最大化解释数据的概率，但是在SVM这里我们要寻找最宽的安全距离。

SVM被视为感知机的升级版。感知机只要找到一条线把数据分开就大功告成了，哪怕这条线紧贴着某个样本。但是SVM追求的是最大化间隔。

想象有一条公路要把两类样本分开，这条公路就是我们的决策边界。SVM的目标是不仅修好这条路，还要让路的宽度尽可能宽，直到我们碰到最近的那几个样本为止。这些决定了路有多宽的边界样本，我们就叫做 支持向量 (Supporting Vectors)。

一旦这条最宽的公路被确定，公路以外的其他样本无论怎么增加，都不会影响这条边界的位置。这意味着SVM是一种对局部边界极其敏感，同时对全局噪声感知不强的算法。

决策规则

想象我们现在在一个由两个特征数据库组成的二维平面上。

在数学上，任何一条直线都可以写成这样的形式：

$$w_1x_1 + w_2x_2 + w_0 = 0$$

而这实际上就是我们在感知机学过的 $w^Tx + w_0 = 0$ 的展开表达。因此当我们在图像上使用一条线来分割两类样本时，我们实际上就是找到了一条特定的线，能够用线性组合来表示，同时这条线也是所有能够使得Net Input $z$ 恰好等于0的点 $(x_1, x_2)$的集合。

而我们的权重向量 $w$ 在集合上就是垂直于这条决策边界的法向量，你可以在图中看到他们很明显地垂直。$w$指向的方向就是模型认为正类特征最强的方向。因此当你拿取一个样本的特征向量 $x$ 与 $w$ 做内积 ($w^Tx$) 的时候，我们实际上是正在计算这个样本在 $w$ 方向上的标量投影。加上偏置 $w_0$ 之后，如果结果大于0，那么样本就落在了决策边界的上方或者前方，反之小于0就落在下方或者后方。

因此在这个图上，我们可以把决策边界看成一条代表海拔为0的线。而 $w^Tx + w_0$ 就像是地理上的等高线函数，可以为平面上的每一个点都计算出一个海拔高度。

而SVM的决策规则就是：如果样本海拔大于0，就属于正类；反之小于0就是负类。同时由于我们刚才讲过的最大宽度要求，我们还人为规定了“路肩宽度”，也就是属，只有海拔达到1才能算100%正类，低于-1才算是稳稳的负类，而中间这段 $[-1, 1]$的区域就是我们要最大化的间隔。

马路要有多宽？

由于 $w$ 垂直于路面，我们只需要计算一个在正路肩上的样本 $x_{+}$ 和一个在负路肩上的样本 $x_{-}$ 在 $w$ 方向上的投影差即可。这样即便正负样本是斜着过马路的，也可以计算出来这两个样本在垂直方向的长度是多少。

为了只测量长度而不改变数值的级数，我们需要使用 $w$ 方向上的单位向量来计算。因此，宽度的代数表达式可以写为：

$$\text{Width} = (x_{+} - x_{-})^T \frac{w}{||w||}$$

展开，即可得到：

$$\text{Width} = \frac{w^Tx_{+} - w^Tx_{-}}{||w||}$$

由于我们刚才所说，对于正侧路肩上的样本，我们必须满足 $w^Tx_{+} + w_0 = 1$ 的关系，也就是 $w^Tx_{+} = 1 - w_0$。负侧同理，因此我们可以将这两个等式带入刚才的宽度公式中，就可以得到：

$$\text{Width} = \frac{(1 - w_0) - (-1 - w_0)}{||w||} = \frac{2}{||w||}$$

你会发现整个马路的宽度仅仅取决于权重向量 $w$的模长。因此为了让马路越秀越宽，我们就必须让 $||w||$ 越小越好。在实操时我们实际上会最小化 $\frac{1}{2}||w||^2$，因为 $||w||$ 包含根号，求导会非常麻烦，而 $\frac{1}{2}||w||^2$ 的导数刚好是 $w$，这就使得后续求解过程变得更丝滑。

然而这场优化并非漫无目的，你不能为了极致的宽度来导致数据点真正进入路肩以内。因此我们必须引入一组约束条件：

$$y^{(i)}(w^Tx^{(i)} + w_0) \ge 1$$

且对于所有样本 $i$ 必须成立。这样SVM就可以找到一组能够让权重向量最短的参数，同时保证每一个样本都落在正确路肩以外。

SVM的训练

假设我们发现数据中存在一个离群点，或者数据本身并非线性可分，我们该怎么办？这样的话我们刚才提出的优化方式就不行了，因为在绝对零容忍的要求之下，算法是不可能找到一个能够让所有样本都乖乖呆在马路正确一边外面的解。因此我们需要借助统计建模的力量，希望模型本身具备一定容错率。

在这里我们引入一个新的优化方式，叫做 Soft Margin Classification。我们不再追求绝对的正确分类，反倒是在拉大马路宽度的同时，允许违规行为，但是尽量减少。我们的目标和之前一样，也是找到一个最佳的平衡点。

在数学实现上，我们为每一个样本都引入一个松弛变量，我们记作 $\xi$ 。如果样本老老实实呆在正确路肩之外，那么这个样本的 $\xi = 0$，而如果它因为某种原因踩在了马路上，甚至跨到了马路对面，我们就需要使用 $\xi$ 记录它的违规程度。

如何衡量 $\xi$ 的值？衡量一个点错没错或者错了多少，参照物不是那条马路中间的中线，而是海拔为正负1的路肩。我们可以把每一个样本 $i$ 的违规程度 $\xi^{(i)}$ 看作是一把从路肩向内延伸的刻度尺，我们叫它Hinge Loss，计算逻辑如下：

$$\xi^{(i)} = \text{max}(0, 1 - y^{(i)}(w^Tx^{(i)} + w_0))$$

这意味着系统会自动对比这个样本的实际海拔和它应该呆在的海拔之间的差距。具体可以分为三个情况：

• 完全合规。如果一个正类样本的海拔 $\ge$ 1，负类样本相反，那么说明这个样本处于正确的位置。此时 $y^{(i)}z \ge 1$，公式计算出的结果是 0 或者负数。但是在 $\text{max}$ 的作用下，会被锁定为0。
• 路肩内部正确侧。如果一个样本的海拔是0.5，正好处于路肩和中线之间，虽然说还没有跨过中线，但是已经入侵了安全距离。此时 $y^{(i)}z = 0.5$ ，根据公式可以算出 $\xi^{(i)}$ = 1 - 0.5 = 0.5。即便在分类上是对的，仍然是会贡献一个正的惩罚值。所以SVM不仅要分类正确，还要考虑距离。
• 错误一侧说明海拔为负数， 对于海拔为 -0.5 的样本，$y^{(i)}z = -0.5$。所以 $\xi^{(i)} = 1 - (-0.5) = 1.5$。值轻松超过1。因此一旦样本跨越越策边界，那么它的惩罚 $\xi$ 会随着它的偏离目标的距离线性增长。

总的来说 $\xi$衡量的不是样本离马路中线有多远，而是衡量它离本应该待的路边有多远。

因此，我们最后的优化目标是最小化这样一个综合代价：

$$\text{Cost} = \frac{1}{2}||w||^2 + C\sum_i \xi^{(i)}$$

如果我们把参数C设置的很大，那么我们对违规极其严厉。模型会变回几乎不容忍任何错误的训练风格，也就是上一部分我们提到的那样。相反，如果我们减小C的数值，那么模型就会在分类错误上面表现的更加宽容，从而换取更宽的路面宽度。我们做的本质上还是在平衡偏差和方差：减小C会增加模型的偏差，但是能够降低模型对噪声的敏感度，从而提升模型的泛化能力。

核支持向量机

我们一直尝试在现有的特征空间里面画直线。但如果数据无法线性可分，例如环形分布，那么在二维平面上无论我们怎么画直线，我们都不可能实现完美的分类。这时候我们需要做的是采用“降维打击”的反策略：我们来玩玩升维打击。

所谓核支持向量机（Kernel SVM），核心思想其实一句话就能说清：我们不在原空间里硬画直线，而是先把数据映射到更高维的特征空间，再在那个空间里画一条线性可分的超平面。

但是这里有个现实问题：如果我们真的把每个样本都显式映射到高维，计算量会直接爆炸。于是核技巧（Kernel Trick）登场了。它告诉我们：SVM训练里真正需要的不是样本坐标本身，而是样本两两之间的内积。只要我们能直接定义一个核函数 $K(x_i, x_j)=\phi(x_i)^T\phi(x_j)$，就等价于“在高维空间做了内积”，却不需要真的把 $\phi(x)$ 算出来。

常见核函数大概有三类：

• 线性核：适合本来就接近线性可分的数据，速度快、可解释性强。
• 多项式核：可以学到特征之间的组合关系，比如二次、三次交互。
• RBF核（高斯核）：最常用，能构造非常灵活的非线性边界，适合边界弯弯绕绕的数据。

你可以把核函数理解成“相似度放大器”：它不是直接看两点在原空间的直线距离，而是用一种更聪明的方式去度量它们在隐式高维空间里到底像不像。这样一来，原本在二维里画不直的边界，在高维里可能就是一刀切。

当然，核SVM不是无脑强。参数选不好一样会翻车。比如RBF里的 $\gamma$ 太大，模型会变得非常敏感，边界抖得像锯齿，容易过拟合；$\gamma$ 太小，边界又太平滑，容易欠拟合。同时参数 $C$ 依然控制“严格执法”还是“适度容错”。所以实战里一般会用交叉验证一起调 $C$ 和 $\gamma$，找一个泛化最稳的平衡点。

决策树学习

相比之前那些黑盒一般的数学映射，决策树学习的关键在于可解释性。它就像我们日常生活中做决策那样，通过提出一系列又简至深的问题来不断缩小范围，最终将复杂的样本群逐步拆解成整齐划一的小组或者个体。

决策树学习使用数结构，从根出发签出下面的子节点。而我们的终极目标是让每一个叶子节点都达到纯净的状态，也就是说，该节点内的样本全部都属于同一个类别。

但是如果我们允许这棵树毫无节制地生长下去，那么模型就会为了完美分类训练集中的每一个孤立噪点而变得极其复杂，从而形成一个非常深的数，这就是决策树学习中的过拟合。因此为了让模型具备更好的泛化能力，我们通常需要进行剪枝(Pruning)操作，比如设定最大深度来强迫📖停止生长。有关剪枝的内容会在后面继续讲解。

决策树如何切分问题？

由于决策树通过一系列针对特征的问题来拆分数据，那么在数以百计的特征和切分点中，哪一个才是含金量最高的问题？我们该如何切分问题，来让每个节点下面的节点剩下的数据尽可能更有意义？

为了量化这种含金量，我们引入一个概念：基尼不纯度 (Gini Impurity)。

$$I_G(t) = 1 - \sum_{i = 1}^c p(i | t)^2$$

这里的 $p(i | t)$ 代表在节点 $t$中属于第 $i$ 类样本的比例。

基尼不纯度有点像是量化“随机盲猜的挫败感”的量。如果你面前有一个果篮，代表一个节点，里面混杂苹果，梨和葡萄。如果你闭着眼睛从篮子里随机摸出一个水果，并根据篮子里水果的整体比例猜一个标签，那么你猜错的概率就是这个节点的基尼不纯度。

具体来说如果篮子里面全部都是苹果，也就是说这个节点达到了纯净状态，无论你怎么摸，怎么猜你都不可能会猜错，因此你的挫败感为0，基尼不纯度也等于0。然而如果篮子里面各种水果混杂，你猜错的可能性会很大，基尼不纯度也会变大。

因此决策树的生长目标非常单纯，在每个节点都尽全力寻找一个拆分方式，使得拆分后产生的子节点比父节点更“纯”，也就是尽可能让基尼不纯度一直下降。

理解这些后回去看一看公式。 $\sum p(i | t)^2$ 实际上是在计算“连续两次摸到同一类水果”的概率。如果某类样本占据了绝对优势，那么这个平方和就会非常接近1。用1减去这个数得到的基尼不纯度就会非常小，接近0。反之同理，如果各个种类平分秋色，那么不纯度就会变高。

引导决策树

知道决策树如何衡量节点纯度，我们就需要知道纯度如何影响决策树的决策。

在决策时进行每一次分裂的时候，它会计算Information Gain：

$$\text{Information Gain}(\text{Parent}) = I(\text{Parent}) - \sum \frac{N_j}{N_p}I(\text{Child}_j)$$

左边的Information Gain也可以写成 $IG(Parent)$， 那么左边的这个 $I(Parent)$ 代表父节点在拆分之前的混乱程度，而减号右边的部分代表拆分之后所有子节点的残留混乱度之和。因此这两者之间的差值就是我们通过这次拆分消除掉的混乱度，也就是我们获得的信息收益。

同时你发现我们会对子节点的残留加权求和。这反映了一个节点的纯度贡献必须包含其样本的数量挂钩。假如我们把100个样本分成两组，左边是一组拥有99个样本的大杂烩，而右边是一个已经提纯的节点，实际上这个纯净节点对全局分类的贡献微乎其微。因此公式要求我们计算子节点不纯度的加权平均值。只有包含大量样本的子节点都变得非常纯净时，这个加权后的数值才会显著变小，从而使得Information Gain达到最大。

也就是说，算法会对比父节点的不纯度与它所有子节点的不纯度的加权平均值。如果某次分裂能够让整体不纯度大幅下降，也就是Information Gain最大化，那么这个特征和对应的切分点就会被采纳。

就例如我们现在在父节点上有一个数据表：

我们需要盯着这些样本的标签来看，因为不纯度衡量的是结果的纯净度而并非原因的复杂性。在这个包含五个样本的集合中，我们观察到有两个苹果，两个葡萄和一个柠檬。如果我们闭着眼睛从集合中随机抽取一个样本，抽到苹果的概率 $p = 2/5$ ，也就是0.4，同理，葡萄0.4，柠檬0.2。

还记得之前的 $I_G$ 公式吗： $I_G(t) = 1 - \sum p(i | t)^2$， 计算过程实际上是询问，如果我们根据当前的类别比例随机给样本贴标签，我们贴对的综合概率是多少？因此我们计算每个类别概率的平方求和：

$$0.4^2 + 0.4^2 + 0.2^2 = 0.16 + 0.16 + 0.04 = 0.36$$

随后我们用一减去0.36，得到基尼不纯度0.64。我们得到了父节点的值，重复对父节点的子节点们进行计算，然后套用Information Gain的公式计算就好。

除了使用不纯度来主导计算Information Gain，我们还可以使用 熵 (Entropy) 和 分类错误率 (Classification Error) 。

熵在信息论中用来衡量系统的不确定性，定义为：

$$I_H(t) = - \sum_{i=1}^c p(i|t)\log_2 p(i|t)$$

这里的 $p(i|t)$ 依然是第 $i$ 类样本在节点 $t$ 中的占比。

分类错误率比较简单直白：

$$1 - \text{max}{p(i|t)}$$

即是1减去当前节点中占比最大的那一类的比例。

所以我们什么时候用熵，什么时候用基尼不确定度？基尼的目标是最小化随机分类错误的概率，而熵更侧重于最大化“互信息”，也就是说减少对系统状态的未知感。

在实际工程运用中，两者的表现一般来讲比较接近。而由于基尼在计算时需要做平方运算，但是熵需要计算对数，因此计算基尼系数的速度往往会稍快一些。因此在训练大规模数据集的时候，基尼系数往往是默认首选。然而熵对概率分布的变化有时候比基尼系数更敏感一些，所以在某些特定场景下可能会产生更平衡的结果。

那么分类错误率呢？分类错误率的曲线看起来像是一个尖锐的三角形，而基尼和熵是圆润的弧线。这意味着当类别比例发生微小变化的时，基尼和熵导致的坡度变化会很明显，能够带给优化算法清晰的信号。而分类错误率在很多区域的坡度是恒定的，甚至某些方案下数值不会发生任何改变，从而导致Information Gain为0。

所以分类错误率不适合长数，反而我们使用它来剪枝。

随机森林

一颗决策树是对于当前数据集的专家，但是如果这个专家比较偏执怎么办？

随机森林引入了所谓群体智慧的概念，是一场集思广益的民主投票。我们通过构建多个彼此不同的深层决策树让它们共同协作，利用群体智慧来抵消个体的过拟合偏见。

这意味着，即便森林中的每一棵树单独拿出来都有很高的方差，但通过平均化的处理，整体模型会变得非常稳健，从而在没见过的测试数据集上表现出更好的泛化性能。

那么我们如何确保森林里的每一棵树不会异口同声地反同一个错误？

与其说我们把所有数据同样为给每一棵树，我们从原始训练集中随机的，有放回地抽 $n$ 个样本喂给不同的树来训练。由于是有放回的抽取，有些样本会被反复选中，当然也有些可能不会出现在某些决策树的视野里。这叫做 自助采样 (Bootstrap Sampling) 。采样量大小 $n$ 会决定个体之间的差异性大小。比如 $n$很大，那么树就会长的越来越像，森林也就失去了群体智慧的优势，变得容易过拟合。

接下来在每个树的每个节点寻找最佳切分特征的时候，我们不再从所有的特征中筛选，而是随机选择其中的 $d$ 个特征。模型只能从这几个特征里面挑选他们的切分特征。这意味着即使某个特征在全局上非常有统治力，由于随机抽样待的限制，某些节点上我们没办法100%选用这些特征，从而给了其他特征表现的机会。这种随机性就是为什么随机森林叫做随机森林。

KNN

KNN是目前我们学到的机器学习算法中最直观，最符合人类社交直觉的算法。

刚才说到的SVM和逻辑回归是通过使用复杂的计算来划定边界，那么KNN就是“物以类聚，人以群分”。看这个图：

我们想要判断一个位置样本属于哪一类的时候，不需要去训练一个复杂的数学模型，而是直接观察它在特征空间内最靠近的 $k$ 个邻居是谁。如果邻居大多数都是三角形，那么这个问好也有很大概率是个三角形。

因此我们说KN N是一个基于内存的模型，或者说是一个惰性学习者。因为它在训练阶段几乎不做任何实质性的计算，只是单纯的把数据存起来，然后把所有的推理工作推迟到分类阶段。

KNN的工作原理

既然KN N需要找到最近的邻居，首先我们要知道KNN如何衡量样本之间的距离。介绍闵科夫斯基距离：

$$d(x^{(i)}, x^{(i)}) = \sqrt[p]{\sum_k |x_k^{(i)} - x_k^{(j)}|^p}$$

这个公式实际上是欧几里得距离和曼哈顿距离的母体。当参数 $p = 2$的时候，这个公式计算的就是欧几里得距离（直线距离）；当 $p = 1$的时候就变成了曼哈顿距离。我们在KNN中，一般设置 $p = 2$。

随后我们还需要对数据做标准化。由于KNN完全依赖距离来做决策，如果我们的特征两极不同意，那么数值较大的特征会完全主导距离计算。

完成这些步骤后，当我们需要预测一个位置的数据点类型的时候，就找到他的邻居计算就可以了。

但是KNN有一个问题。随着特征维度的增加，高维空间会变得极其稀疏。这意味着即便我们找到了最近的邻居，它在物理距离上也可能会离我们非常遥远。

想想你在一个楼道走廊里面找邻居，因为大家挨着很近，一般来讲邻居之间也会走得很近。但如果同样数量的业主分到一个高维度里，这个空间的体积会变得非常大，而由于样本没有增加，整个空间就变得很稀疏，就像宇宙一样。所以即便你已经找到了离你最近的邻居，这个邻居在物理距离上已经离你非常遥远了。由于足够遥远，邻居与你实际上已经完全并不具备任何相似性，而是在宇宙里恰好离你近一些的陌生人。

所以如果算法强行依据这个陌生人的标签来做预测，那么它实际上是在拟合一种随机的噪声，而不是真正的数据模式。这种对于远距离样本的盲目跟从，会导致过拟合的出现。所以这就是为什么我们要在KNN之前还要做一步特征选择或者降维来让数据脱水。

有关降维和PCA的内容我们会在后面的章节展开的。