一、超平面

超平面不一定是一个面，它是所处向量空间的一个子空间，如立体空间中一个面，二维平面上一条线。它的作用在于将空间中的数据一分为二，达到分类的目的。

1.1 超平面表达式

g ( x ) = w T x + w 0 = 0 g(x) = \mathbf w^T\mathbf x+w_0 = 0\\ g(x)=wTx+w0=0

w = ( w 1 , w 2 , . . . , w l ) T \mathbf w = (w_1,w_2,…,w_l)^T w=(w1,w2,…,wl)T,权向量（超平面法向量）
x = ( x 1 , x 2 , . . . , x l ) T \mathbf x = (x_1,x_2,…,x_l)^T x=(x1,x2,…,xl)T,实例（样本向量)
w 0 w_0 w0,偏移量
在实际中，w确定，因此这个方程代表所有满足的向量x（点）的集合， w T x w^Tx wTx可视为x向w的投影乘以w的模长

这个方程的解读也可以是x向w的投影长度为 − w 0 ∣ ∣ w ∣ ∣ \frac{-w_0}{||w||} ∣∣w∣∣−w0的点集合。

二、线性函数：距离刻画

上面的超平面定义了所有在超平面上的点，那如果是不在超平面上的点与该超平面又有什么关系？

设 x p x_p xp是x在超平面 w T x + w 0 = 0 \mathbf w^T\mathbf x+w_0=0 wTx+w0=0的投影点，得公式如下：
x = x p + ( x − x p ) w T x ∣ ∣ w ∣ ∣ = w T x p ∣ ∣ w ∣ ∣ + w T ( x − x p ) ∣ ∣ w ∣ ∣ , 两边同时乘上 w T ∣ ∣ w ∣ ∣ \mathbf x = \mathbf x_p + (\mathbf x-\mathbf x_p) \\ \frac{\mathbf w^Tx}{||\mathbf w||} = \frac{\mathbf w^T\mathbf x_p}{||\mathbf w||} + \frac{\mathbf w^T(\mathbf x - \mathbf x_p)}{||\mathbf w||}, 两边同时乘上 \frac{\mathbf w^T}{||\mathbf w||} \\ x=xp+(x−xp)∣∣w∣∣wTx=∣∣w∣∣wTxp+∣∣w∣∣wT(x−xp),两边同时乘上∣∣w∣∣wT
可绘出图例如下：
在这里插入图片描述

令 d = w T x p ∣ ∣ w ∣ ∣ , z = w T ( x − x p ) ∣ ∣ w ∣ ∣ 结合 w T x p + w 0 = 0 , 有 d = − w 0 ∣ ∣ w ∣ ∣ , z = w T x + w 0 ∣ ∣ w ∣ ∣ = g ( x ) ∣ ∣ w ∣ ∣ 令d = \frac{\mathbf w^T\mathbf x_p}{||\mathbf w||},z = \frac{\mathbf w^T(\mathbf x - \mathbf x_p)}{||\mathbf w||}\\ 结合\ \mathbf w^T\mathbf x_p + w_0 = 0,\\ 有d = \frac{-w_0}{||\mathbf w||},z = \frac{\mathbf w^T\mathbf x+w_0}{||\mathbf w||} = \frac{g(\mathbf x)}{||\mathbf w||} 令d=∣∣w∣∣wTxp,z=∣∣w∣∣wT(x−xp)结合 wTxp+w0=0,有d=∣∣w∣∣−w0,z=∣∣w∣∣wTx+w0=∣∣w∣∣g(x)
由图可知，z是任意一个向量 x \mathbf x x到超平面的距离。这个距离的作用在于让我们可以调整超平面的位置使得分类更加准确。当 x \mathbf x x方向和 w \mathbf w w一致时，该距离为正值，否则为负值，因此也可以得出结论，超平面一侧的点全是正值，另一侧全是负值，由此可以得到二分类。

这两个概念的确立使得对于数据的分类有了依据，我们说将数据分成不同的两类，自然要有一个分界线（即超平面），而给定一个数据，如何去刻画该数据在超平面的一侧还是另一侧，依靠线性函数的符号（实现了类间分类），数据与分界线的远近由线性函数的绝对值刻画（体现了类内距离）。

三、相似度度量

相似度从几何的角度看就是两个样本点间距离的大小，距离越近，相似度越大。对于这个距离有好几种刻画形式，主要是不同的范式。

MinkovskiMetric 闵氏距离(p-范数)
D ( x , y ) = [ ∑ i ∣ x i − y i ∣ p ] 1 p D(\mathbf x,\mathbf y) = [\sum_i|x_i-y_i|^p]^{\frac{1}{p}} D(x,y)=[i∑∣xi−yi∣p]p1
欧式距离（p=2的特殊情况，2范数）
D ( x , y ) = [ ( x − y ) T ( x − y ) ] = [ ∑ i ∣ x i − y i ∣ 2 ] D(\mathbf x,\mathbf y) = \sqrt{[(\mathbf x- \mathbf y)^T(\mathbf x - \mathbf y)]} = \sqrt{[\sum_i|x_i-y_i|^2]} D(x,y)=[(x−y)T(x−y)]=[i∑∣xi−yi∣2]
曼哈顿距离（p=1的特殊情况，1范数）
D ( x , y ) = ∑ i ∣ x i − y i ∣ D(\mathbf x, \mathbf y) = \sum_i|x_i-y_i| D(x,y)=i∑∣xi−yi∣
Chobychev距离（p= ∞ \infty ∞）
D ( x , y ) = max ⁡ i ∣ x i − y i ∣ D(\mathbf x, \mathbf y) = \max_i|x_i-y_i| D(x,y)=imax∣xi−yi∣

为什么要有这么多种距离？

大部分情况下，一般欧式距离使用的情况较多，我们对于二维平面中的两个点，想要刻画他们的远近往往用欧式距离即可。但设想这样一种情况，假设两个点不能直达（最常见的就是生活中的街道，必须沿街道行走），这个时候用欧式距离刻画两点距离就显得不合理。

下图为四种不同距离描述下所有到原点相同距离的点构成的图形。

四、分类问题

4.1 定义

书本定义：

根据给定数据集 T = { ( x 1 , y 1 ) , . . . , ( x l , y l ) ) } T=\{(\mathbf x_1,y_1),…,(\mathbf x_l,y_l))\} T={ (x1,y1),…,(xl,yl))}，其中 x i ∈ C = R n , y i ∈ Y = 1 , 2 , 3 , . . . , m x_i\in C=R^n,y_i \in Y= {1,2,3,…,m} xi∈C=Rn,yi∈Y=1,2,3,…,m，要求寻找C上的决策函数 g ( x ) : C → Y g(\mathbf x):C\to Y g(x):C→Y
含义解析

数据集中一个组合是一条数据， x i \mathbf x_i xi表数据特征， y i y_i yi表数据的分类结果，基于已有的 l l l条数据，训练一个从n维空间数据C到分类结果集合Y的映射函数 g ( x ) g(\mathbf x) g(x)，使得在随意给定一个新的数据 ( x k , y k ) (\mathbf x_k,y_k) (xk,yk)， g ( x k ) = y k ′ （预期结果） g(\mathbf x_k)=y_k’（预期结果） g(xk)=yk′（预期结果）就是其分类的结果，分类的目的就是使 y k ′ y_k’ yk′(预期结果)与 y k y_k yk（实际结果）尽可能相同。

4.2 评估方法

其实就是分训练集和测试集，训练集用于训练得到决策函数，测试集用于测试决策函数的好坏。主要包含两种方法

交叉验证法
交叉验证法就是将数据分成两类（训练、测试），进行交叉验证，其中可以简单按比例划分（8:1，10:1等），也可以分成k类，其中1类做测试，剩余k-1类做训练，每一类训练集进行一次测试，最后取平均
自助法
取m个随机样本，构成集合D，剩余除D以外的用于测试。

核心是训练+测试

4.3 性能评价

有了测试作为评估，自然要考虑测试结果的好坏，直观来说，一般是预期与实际越相符，决策函数越好。这是采用错误率和精度作为评价标准：

错误率与准确率
所谓错误率即分类错误的样本站总样本数的比例，定义如下：
E ( f ; D ) = 1 m ∑ i = 1 m h ( ( f ( x i ) ≠ y i ) ) h ( x ) = { 1 if x i s t r u e 0 else E(f;D) = \frac{1}{m}\sum_{i=1}^mh((f(\mathbf x_i)\ne y_i))\\ h(x) = \begin{cases} 1 &\text{if } x \ is\ true \\ 0 &\text{else } \end{cases} E(f;D)=m1i=1∑mh((f(xi)=yi))h(x)={ 10if x is trueelse
准确率相对于错误率，等于1-错误率，定义如下：
a c c ( f ; D ) = 1 m ∑ i = 1 m h ( f ( x i ) = y i ) = 1 − E ( f ; D ) acc(f;D) = \frac{1}{m}\sum_{i=1}^mh(f(\mathbf x_i)=y_i) \\ =1-E(f;D) acc(f;D)=m1i=1∑mh(f(xi)=yi)=1−E(f;D)
以上为针对离散型分布数据，连续型分布数据(设密度函数为 p ( x ) p(\mathbf x) p(x))的E与acc如下：
E ( f ; D ) = ∫ x ∈ D h ( f ( x ) ≠ y ) p ( x ) d x a c c ( f ; D ) = ∫ x ∈ D h ( f ( x ) = y ) p ( x ) d x = 1 − E ( f ; D ) E(f;D) = \int_{x\in D}h(f(\mathbf x) \ne y)p(\mathbf x)d\mathbf x\\ acc(f;D) = \int_{x\in D}h(f(\mathbf x) = y)p(\mathbf x)d\mathbf x\\ =1-E(f;D) E(f;D)=∫x∈Dh(f(x)=y)p(x)dxacc(f;D)=∫x∈Dh(f(x)=y)p(x)dx=1−E(f;D)
错误率和准确率本质上可看作一个东西，但是错误率只让我们知道了有多少样本被判别错误（例如正判成负，负判成正，都属于判别错误），但有的时候往往我们更关心判别为正的数据，因为正项数据对我们有利。这时候就需要用到查准率(precision)和查全率(recall)。

这里举一个例子，假设判定地震是否发生，我们测得决策函数的精度在99%，即对100次测验，有99次预测成功，但是这99次我们不知道发生有多少次，不发生有多少次。假设99次均为不发生。说明你这个决策函数测地震不发生很准，但是发生的情况你测不准（容易出错），这就没有意义，因为我们更关心地震发生的情况。
查准率（精度，precison）、查全率（召回率,recall）和 F 1 , F β F1,F_{\beta} F1,Fβ
查准率和查全率更适宜被应用于类似这样的场景，如“查出的信息中有多少是用户感兴趣的”或“用户感兴趣的信息查出了多少”。在此基础上，我们引入“真正例（TP，预测结果为正，真实为正）”，“假正例（FP，预测结果正，真实为反）”，“真反例（TN，预测结果为反，真实为反）”，“假反例（FN，预测结果为反，真实为正）”的概念，由四者构成混淆矩阵如下：

由此我们得到查准率P和查全率R的定义如下：
P = T P T P + F P R = T P T P + F N P = \frac{TP}{TP+FP}\\ R = \frac{TP}{TP+FN} P=TP+FPTPR=TP+FNTP
从公式中可以看出查准率在于找出所有正例中真实为正的比例（将正例比做用户感兴趣内容，即所有决策函数认为用户感兴趣的内容中用户真正感兴趣的比例），查全率在于刻画有多少真实为正的内容被我们所找出（即决策函数挖掘出的用户真正感兴趣的内容占所有用户会感兴趣内容的比例）。

事实上这两者存在矛盾性，如果我们想让尽可能多的用户感兴趣的内容被选上（提高查全率），那么必然会选上许多把握不大的内容（查准率下降）；如果我们想让我们选出的东西用户必然会感兴趣（提高查准率），那么必然要放弃那些把握不大的内容，就会导致漏掉许多可能感兴趣的内容（查全率下降）。
- P-R曲线
  我们根据学习器的预测结果对样本进行排序，将“最有可能为正例”的样本放在前面，“最不可能是正例的”样本放在最后，遍历这些样本，过程中不断计算当前的查准率和查全率（很显然一开始查准率很高，查全率会很低），得到P-R曲线如下：
A，B，C为三个不同的学习器，很显然A，B的性能要优于C，因为在任何情况下他们的查全率和查准率都要比C高。

A，B的性能不好比较，因此需要引入另一个度量平衡点（查准率=查全率时的取值），粗略地认为，既然无法保证两者都好，就取一个两者都尽量好的位置作为学习器的代表位置，进而比较A与B的性能差异。但更常用的是 F 1 F_1 F1度量：
F 1 = 2 1 P + 1 R F_1 = \frac{2}{\frac{1}{P}+\frac{1}{R}} F1=P1+R12
F 1 F_1 F1度量本身求两者的调和平均，这个比简单地取两者相等位置等有说服力。但在实际应用中，我们不一定要取两者都好的情况，例如b站给用户推荐视频，肯定是希望选出的视频都是用户感兴趣的，这个时候查准率比查全率更重要。而如警方的逃犯信息检索系统，肯定希望不要漏抓一个逃犯，此时查全率更重要。所以这个时候就要根据实际需求进行选择，所以引入 F β F_{\beta} Fβ度量：
F β = 1 + β 2 β 2 R + 1 P F_{\beta} = \frac{1+\beta^2}{\frac{\beta^2}{R}+\frac{1}{P}} Fβ=Rβ2+P11+β2
其中 β \beta β度量了查全率对于查准率的重要性，当 β = 1 \beta=1 β=1即退化为 F 1 F_1 F1度量，当 β > 1 \beta >1 β>1，说明查全率权重更大（更重要），当 0 < β < 1 0<\beta<1 0<β<1，说明查准率权重更大（更重要）。

查全率和查准率是十分重要的概念，相对于错误率描述你学习器的直观判别能力，查全率和查准率能够描述你学习器的是否有意义。如果判断不重要的事一判一个准，判断重要的事老是判错，准确率高与否也就失去了意义。
真正例率(TPR)，假正例率(FPR)
前面P,R能够较好地体现正例样本被划分正确的效果，但我们较为关心分类对正例效果的影响时，就倾向于使用这两者。但当正例和负例样本分布均匀，两者均是我们期望能较好划分的目标时（例如男女划分），那么P，R就显得力不从心了，因此需要TPR(所有实际为正例的样本中被正确判断成正例的比例)，FPR（在所有实际为负例的样本中被错误判断成正例的比例） 以及 ROC曲线（以FPR为横轴，TPR为纵轴的曲线）和AUC（ROC曲线与横轴围成的面积） 来体现了。
T P R = T P T P + F N F P R = F P T N + F P TPR = \frac{TP}{TP+FN}\\ FPR = \frac{FP}{TN+FP} TPR=TP+FNTPFPR=TN+FPFP
很显然，TPR就是R（召回率）,而FPR则从侧面体现了负例被划分成正例的程度，可以理解为模型成本，将模型比作一台过滤器，FPR就是模型过滤错误掺入杂质的比例。很显然我们希望TPR越大越好，FPR越小越好。为了同时体现这两点，引入了ROC曲线，如下图。

要体现上面两点，就是要让曲线尽可能上凸。为此我们需要一个定量的标准去计算这个凸度，因此又引入了AUC，它时图中绿色阴影区域的面积，显然面积越大，效果越好。

一个良好的分类器，其ROC曲线必然时在y=x之上的，否则相当于大部分负例被当成了正例，效果极差。

关于分类评价指标更多的还可以看知乎上一篇比较好的回答

五、线性分类问题

上面我们讨论了一般分类问题需要考虑的部分基础知识（还有些不常用的后续添加），本节考虑分类问题中的线性分类。

所谓线性分类，就是透过特征的线性组合来作出分类决策。对象的特征通常描述为特征值，在向量空间中则是特征向量。如果两类数据可以通过一个线性平面划分，则其分类属于线性分类问题。

在这里插入图片描述

5.1 线性判别函数

线性判别函数即决策函数，在上文中已提过，其表达形式如下：
g ( x ) = ∑ i w i x i + w 0 = w T x + w 0 g(\mathbf x) = \sum_iw_ix_i + w_0 = \mathbf w^T \mathbf x + w_0 g(x)=i∑wixi+w0=wTx+w0
这个式子很容易联想到超平面（分类界）：
g ( x ) = w T x + w 0 = 0 g(\mathbf x) =\mathbf w^T \mathbf x + w_0 = 0 g(x)=wTx+w0=0
由此对于每一个给定的特征向量 x = ( x 1 , x 2 , . . . , x n ) \mathbf x=(x_1,x_2,…,x_n) x=(x1,x2,…,xn)，我们只需代入线性判别函数，观察其结果正负号即可，如下：
x ∈ { ω 1 if w T x + w 0 > 0 ω 2 if w T x + w 0 < 0 \mathbf x\in \begin{cases} \omega_1 &\text{if } \mathbf w^Tx+w_0>0\\ \omega_2 &\text{if } \mathbf w^Tx+w_0 <0 \\end\{cases\} x∈\{ ω1ω2if wTx\+w0>0if wTx+w0<0

5.2 线性分类器

由给定训练样本 { ( x 1 , y 1 ) , . . . , ( x n , y n ) } \{(\mathbf x_1,y_1),…,(\mathbf x_n,y_n)\} { (x1,y1),…,(xn,yn)}，求得线性判别函数（决策函数） g ( x ) g(\mathbf x) g(x),实际上是求 w , w 0 \mathbf w,w_0 w,w0的过程，我们要找满足以下条件的 w , w 0 \mathbf w,w_0 w,w0：
w T x i + w 0 ≥ 0 , f o r e a c h y i = + 1 w T x i + w 0 ≤ 0 , f o r e a c h y i = − 1 \mathbf w^T\mathbf x_i + w_0 \ge0,for \ each \ y_i=+1\\ \mathbf w^T \mathbf x_i+w_0 \le0,for \ each\ y_i = -1 wTxi+w0≥0,for each yi=+1wTxi+w0≤0,for each yi=−1
关于这样的 w , w 0 \mathbf w,w_0 w,w0参数的寻找，就有很多的线性分类器可用，如感知机,线性鉴别分析,Logistic模型等。