分类算法
上一节介绍了线性回归，线性回归是一种经典的回归算法，它可以根据一系列自变量来预测因变量的值。
分类(classification)也是一种常见的需求。分类问题并不要求预测具体的值，而是需要判断样本属于的类别。例如分析一株植物属于哪个物种，或者判断一封邮件是否是垃圾邮件等。分类问题的因变量是离散的，因此无法通过简单的计算阐述结果。
二分类是比较常见的一种分类情况，二分类下每个样本只有两种分类情况（例如某件事是否会发生），因此可以使用布尔值 0 和 1 来描述分类。类似地有多分类，每个样本有多种分类情况。
有许多经典的算法都可以处理分类问题，本节介绍最简单的分类算法之一：逻辑回归。
逻辑回归
逻辑回归的概念
首先先看一个典型的分类场景。假设有如下的一系列数据，横坐标代表样本某个特征的值，纵坐标代表样本的分类，并且是离散的：
在以上示例中，可以很明显看到分类为“ 0 ”的样本特征变量的值都小于 300 ，而分类为“ 1 ”的样本特征变量的都大于 300 。那么就可以用特征变量的值是否大于 300 作为样本分类的依据。
但在稍微复杂一点的场景中，这种简单的逻辑就会失效。例如，考虑以下数据：
在 300 附近，样本可能属于分类“ 0 ”也可能属于分类“ 1 ”。但是数据仍然具有这样的规律：当特征变量的值小于 300 较多时，该样本属于分类“ 0 ”；当特征变量的值大于 300 较多时，它属于分类“ 1 ”；但特征变量的值在 300 附近时，它同时可能属于其中的任何一个分类。
那么此时就无法直接确定某些范围样本的分类了。相比起死板地直接分为两类（硬分类），可以使用另一种思路解决这个问题：确定样本属于分类的概率（软分类）。显然，远大于 300 的样本属于分类“ 1 ”的概率更大，远小于 300 的样本属于分类“ 0 ”的概率更大，而接近 300 的样本属于两个样本的概率相差不大。
这就是逻辑回归(logistic regression)的基本思路。逻辑回归通过建立一条 \\( y \\) 值分布在 0~1 之间的函数来计算样本的分类概率：\\( y \\) 值表示样本属于分类“ 1 ”的概率，那么 \\( 1-y \\) 就表示样本属于分类“ 0 ”的概率，从而将分类问题转换为回归问题。最终样本的分类也容易确定：如果 \\( y > 0.5 \\) ，那么说明样本更可能属于分类“ 1 ”，反之说明样本更可能属于分类“ 0 ”。
可以使用线性回归拟合一条范围在 0~1 内的直线作为概率函数，类似这样：
但是直线比较僵硬，不但不能表示在分界区域概率密度的变化过程，还要在两端将其约束到 0~1 的范围内。一般来说，逻辑回归最常用的概率函数为 sigmoid 函数，这个函数的表达式为：
该函数的特点是当 \\( y \\) 离 0 较远时，\\( f(y) \\) 值十分趋近 0 或 1 ；而当 \\( y \\) 接近 0 时，函数由 0 到 1 有一个较为平缓的过渡。并且该函数是中心对称的，因此比较贴近真实情况下的概率分布。
逻辑回归使用 sigmoid 函数是经过严格推导后得到的结果，这个 Quora 上的回答从概率分布的角度解释了为什么。
决策边界
注意到 sigmoid 函数在 \\( y=0 \\) 处取得概率 0.5 ，而在两端概率分别小于 0.5 和大于 0.5 ，因此可以说 \\( y=0 \\) 是一个决策边界(decision boundary)，位于边界两端的样本将会被分到不同的类别。
在实际应用中，\\( y=0 \\) 并不一定就是区分两个类别的边界条件，而且特征变量的个数也不止一个。这个时候可以使用换元法将自变量变换到实际模型中，由实际情况下的特征变量及其参数组合确定：
那么实际情况下的概率 \\( h_\theta(y) \\) 将由以下公式确定：
此时 \\( \boldsymbol{\theta}^T \boldsymbol{x} = 0 \\) 就是实际情况的一个决策边界：当 \\( \boldsymbol{\theta}^T \boldsymbol{x} > 0 \\) 时，可以预测样本属于类别“ 1 ”；当 \\( \boldsymbol{\theta}^T \boldsymbol{x} < 0 \\) 时，则可以预测样本属于类别“ 0 ”。
通过取用合适的参数 \\( \boldsymbol{\theta} \\) ，可以得到不同的决策边界，从而适应不同的实际情况。例如，对于以下具有两个特征的数据集：
可以看出，在这个二维平面上可以作出这样一条直线 \\( \theta_2x_2+\theta_1x_1+\theta_0=0 \\) ，将两种类别的样本分隔在直线两侧，就像这样：
但有时候边界可能比较复杂，并不能用直线描述，例如：
那么这个时候，可以像在线性回归中处理非线性数据一样，通过引入非线性特征项，在平面上使用曲线例如二次多项式曲线 \\( \theta_2x_2+\theta_{12}x_1^2+\theta_{11}x_1+\theta_0=0 \\) 作为决策边界，将两种类别的样本分隔在曲线两侧，就像这样：
这也就说明了线性回归和逻辑回归之间的联系：线性回归主要是拟合实际的数据，而逻辑回归主要是拟合实际的决策边界。逻辑回归模型可以通过设计复杂的曲线，来表达复杂的决策边界，从而适应各种复杂的模型。
代价函数
代价函数的概念
以上基本已经介绍了逻辑回归模型的基本概念，但是目前还有一个问题没有解决，那就是参数 \\( \boldsymbol{\theta} \\) 还没有确定。
在线性回归中，确定参数的方式是让拟合的直线最贴近原始的数据，使预测值和真实值的差异（即残差）平方和最小。之所以要附加一个平方，是因为残差可正可负，通过平方可以消除符号带来的影响。
使用残差平方和，可以建立一个具体的指标来描述数据和模型的拟合程度：当残差平方和最小，说明预测值和真实值的差异最小，回归直线的拟合更好。并且这个指标是具体的，易于通过程序计算最小值。
这种衡量模型与实际样本误差指标的函数称为成本函数或代价函数(cost function)，当代价函数取值最小时，说明模型与实际值的误差就最小，那么模型拟合效果就最好。
为了确定最好的逻辑回归模型，也需要一个类似的代价函数去描述它的误差。类似线性回归，同样可以使用预测值和真实值的差值作为样本的误差，只不过预测值是连续的概率，而真实值是连续的类型。这样，每个样本的代价函数定义为：
逻辑回归计算的概率是相对类型“ 1 ”而言的，因此对于类型“ 0 ”的概率要用 1 减去该值。取对数的原因是为了让概率接近 1（与实际分类结果接近）时，误差将变得很小；而概率接近 0（完全分错类了）时，误差将变得非常大，从而防止为了让边界上的一些样本取得更大的概率错误地挪动边界，而将某个样本置于明显错误的位置的情况。最后考虑到误差越小，代价函数也应该越小，再给对数结果取相反值。
最终整个模型的代价函数是每个样本代价函数的和，有时再除去样本个数：
为了让模型最贴近实际样本，需要让代价函数最小，也就是让代价函数的导数等于 0 。但是没有直接得出结果的公式（闭式解），因此需要别的方法来得出最小值。下面介绍一个使用最广泛的方法：梯度下降法。
梯度下降
假设一个人被困在遍布密林的深山中，无法判断当前所处的位置，那么快速下山的一种策略就是沿着最陡的方向下坡。这就是梯度下降(gradient descent)法的基本原理：通过计算当前参数 \\( \boldsymbol{\theta} \\) 下代价函数的局部梯度，并不断沿着降低梯度的方向调整参数 \\( \boldsymbol{\theta} \\) ，直到梯度降为 0 ，说明代价函数取得极小值：
第一个 \\( \boldsymbol{\theta} \\) 值可以随机选择，每次执行梯度下降都会使代价函数降低一些。最终收敛得到一个极小值：
不同的梯度下，参数沿着能让代价函数下降方向改变的步长也不一样：如果梯度较平缓，那么步长应该小一些，以免错过了极小值。步长的改变量取决于学习率(learning rate)，学习率越高则参数的改变程度也越大，具体由以下公式确定：
可以看出，学习率对梯度下降结果很重要：低下的学习率将会使算法需要太多次迭代才能达到极值点，而过高的学习率则可能使算法直接越过极值点到达对坡面，甚至在这一过程中发散而永远无法到达极值点：
并且梯度下降得到的是极值点，但未必是最值点，下图展示了这种情况：
这就要求代价函数尽量是一个凸(convex)函数，它的极值就是最值。凸函数也便于自动计算合适的学习率。可以证明逻辑回归的代价函数是一个凸函数，它求偏导的结果如下：（省略过程）
因此逻辑回归可以很好地使用梯度下降算法得到具有最小误差的最好模型。下图展示了一个逻辑回归模型是如何从最开始的随机参数，经由梯度下降收敛到最优参数的：
总的来说，梯度下降是一种非常通用的优化算法，适用于很多找最优解的问题中。梯度下降也有许多改进版本，进一步拓宽了它的适用范围。
正则化下的逻辑回归模型
在线性回归模型中介绍过在拟合现有数据时可能因为设置太高次项而导致的过拟合问题，在逻辑回归中也可能存在这种情况。例如，以下是某个逻辑回归模型中因为异常数据而带来的过拟合：
这个决策边界显然是不合理的。可以像线性回归一样给代价函数加上正则化约束项，从而防止决策边界取得过大的参数而过于复杂。
具体来说，常用的正则化项有如下两个：
- L1 正则化项：\\( \displaystyle{\frac{\alpha}{2n}\sum_{j=0}^{n}\theta_j^2} \\)
- L2 正则化项：\\( \displaystyle{\frac{\alpha}{2n}\sum_{j=0}^{n}|\theta_j|} \\)
这实际上就是线性回归中介绍的岭回归和 LASSO 回归使用的正则化项。以下是使用正则化项后的模型，可以看到过拟合的情况明显改善了很多：
Scikit-Learn中的逻辑回归模型
最后简单介绍使用 Scikit-Learn 建立逻辑回归模型的方法，它和线型回归模型遵循同样的接口，例如建立模型：
LogisticRegression()
以及对新的样本作出预测，由于逻辑回归是解决分类问题，因此预测得到的是一个离散的结果：
逻辑回归的特点就是使用概率确定所属的分类，在代码中可以使用 .predict_proba() 方法来获取这个概率：
相比线性回归，逻辑回归模型多了很多超参数，其中许多参数都涉及本文介绍的内容，接下来介绍其中的一部分：
penalty="l2",
l1_ratio=None,
C=1.0,
tol=1e-4,
max_iter=100,
verbose=0,
multi_class="auto"
)
参数 penalty 指定使用的正则化项，如果设置为 "none" 代表不使用正则化。除了前面介绍的 "l1" 和 "l2" 两种正则化之外，还可以使用一种称为“弹性网络” "elasticnet" 的正则化项，它是 L1 和 L2 的混合形式，参数 l1_ratio 就控制着这种混合比例。参数 C 是大于 0 的正则化强度，但注意它不是系数，在这里值越小代表正则化效果越强。
前文介绍了逻辑回归使用梯度下降的方式优化系数。但浮点运算并不是完全精确的，往往不会出现导数正好为 0 的情况。参数 tol 决定了它的收敛条件：如果相邻两次计算的步长小于这个值，说明结果已经足够精确，可以不继续算下去。如果达到了 max_iter 代表的最大迭代次数还是无法找到这样一个收敛条件，那么说明模型可能存在问题，则停止继续计算。
verbose 是一个较为通用的参数，启用后会输出一些运算过程信息，并且数字越大，信息也越多。
以上介绍的逻辑回归只能处理二分类问题，但无法解决多个分类的情况，原因在于所使用的概率函数不能同时描述多个分类的概率。如果尝试使用 Scikit-Learn 中的逻辑回归模型处理多分类问题，会发现它仍然可以正常工作并得到较为正确的结果：
参数 multi_class 就是为了解决多分类问题而设置的。接下来介绍如何使用逻辑回归处理多分类问题。
多分类下的逻辑回归
一对多方法
为了实现多分类，可以使用一种简单的变换方法：将多分类模型转换为多个二分类模型。具体来说，假设有 A 、B 、C 三个分类，那么可以使用以下三个模型描述它：
- 属于(1)和不属于(0)分类 A
- 属于(1)和不属于(0)分类 B
- 属于(1)和不属于(0)分类 C
可以单独建立这几个二分类模型，对于每个模型都将另外两类看成一个整体，然后组合它们得到的结果：如果在模型 1 中“属于(1)”的分数比模型 2 和 3 的“属于(1)”都高，那么说明更可能属于分类 A 。
这等价于参数 multi_class="ovr" 。
softmax回归
还有一种方法也可以处理多分类情况：既然之前使用的概率函数不能同时描述多个分类的概率，那么也可以更换一个概率函数。具体说来，可以将概率函数转换为更贴近概率定义的分数形式：
这种形式的逻辑回归称为 softmax 回归，它本质上是逻辑回归的推广形式。对于每一个类别，softmax 回归都使用不同的参数去表示它的概率形式：
这等价于参数 multi_class="multinomial" 。但很明显，这种新的概率函数不能再用之前的代价函数去描述它的误差了，并且新的代价函数也不能像之前的函数那么定义：概率最多就为 1 ，根据无法表达与类别“ 2 ”的误差。一般来说，softmax 回归使用交叉熵作为它的代价函数，其公式如下：
注意这里使用参数矩阵 \\( \boldsymbol{\Theta} \\) 来存储每个类别的参数向量 \\( \boldsymbol{\theta} \\) 。如果想知道为什么 softmax 回归这样定义以及为什么使用交叉熵作为代价函数，请参阅相关资料。
总的来说，逻辑回归作为一种简单的分类算法，模型简单且数学上易于分析，具有运算速度快，对预处理要求少，可以得出概率便于进一步分析等优点。不过逻辑回归的实际分类准确率并不高，特别是可能无法处理一个分类形成多个群落的情况，因此一般只用于处理简单的分类问题。