分类算法学习笔记

# 分类算法的作用

分类是在一群已经知道类别标号的样本中，训练一种分类器，让其能够对某种未知的样本进行分类。分类算法属于一种有监督的学习。分类算法的分类过程就是建立一种分类模型来描述预定的数据集或概念集，通过分析由属性描述的数据库元组来构造模型。分类的目的就是使用分类对新的数据集进行划分，其主要涉及分类规则的准确性、过拟合、矛盾划分的取舍等。

有监督学习和无监督学习的区别
- 有监督学习是指数据集的正确输出已知情况下的一类学习算法。因为输入和输出已知，意味着输入和输出之间有一个关系，监督学习算法就是要发现和总结这种“关系”。
- 无监督学习是指对无标签数据的一类学习算法。因为没有标签信息，意味着需要从数据集中发现和总结模式或者结构。
- 简单来说，是否有监督（supervised），就看输入数据是否有标签（label）

# 交叉验证

# 基本思想

交叉验证的基本思想是把在某种意义下将原始数据(dataset)进行分组，一部分做为训练集(train set)，另一部分做为验证集(validation set or test set)，首先用训练集对分类器进行训练，再利用验证集来测试训练得到的模型(model)，以此来做为评价分类器的性能指标。用交叉验证的目的是为了得到可靠稳定的模型。

# K折交叉验证(K-fold cross-validation)

K折交叉验证就是进行多次train_test_split划分；每次划分时，在不同的数据集上进行训练、测试评估，从而得出一个评价结果；如果是10折交叉验证，意思就是在原始数据集上，进行10次划分，每次划分进行一次训练、评估，最后得到10次划分后的评估结果，一般在这几次评估结果上取平均得到最后的评分。其中，k一般取5或10。

K折交叉验证的步骤：

将原始数据集划分为相等的K部分（“折”）
将第1部分作为测试集，其余作为训练集
训练模型，计算模型在测试集上的准确率
每次用不同的部分作为测试集，重复步骤2和3 K次
将平均准确率作为最终的模型准确率

10折交叉验证

💡 要会给定数据集进行K折交叉验证要会计算模型准确率（每次的准确率、最终的准确率）

# 支持向量机(SVM)

# 基本思想

SVM学习的基本思想是求解能够正确划分训练数据集并且几何间隔最大的分离超平面。对于线性可分的数据集来说，这样的超平面有无穷多个（即感知机），但是几何间隔最大的分离超平面却是唯一的。

SVM基本思想

用我自己的理解，就是找一条线将两个数据集分开，要保证这条线到两边的数据集距离最大。那么，如何才能保证距离最大呢，这就是下面要讨论的难点了。

# 支持向量

在支持向量机中，距离超平面最近的且满足一定条件的几个训练样本点被称为支持向量。

在上图中，处于虚线上的点（即红色的点）我们就将其定义为支持向量。那么，如何得到支持向量到超平面的距离呢？我们引入几何间隔的概念：

$$ \gamma = \frac{y(w^Tx + b)}{||w||_2} = \frac{\gamma^{’}}{||w||_2} $$

一般我们都取函数间隔$\gamma^{’}$为1，这样我们就可以得到支持向量到超平面的距离为$\frac{1}{||w||_2}$，两个支持向量之间的距离为$\frac{2}{||w||_2}$

# SVM模型目标函数

SVM的模型是让所有点到超平面的距离大于一定的距离，也就是所有的分类点要在各自类别的支持向量两边。用数学式子表示为：

$$ max \;\; \frac{1}{||w||_2} \;\; s.t \;\; y_i(w^Tx_i + b) \geq 1 (i =1,2,…m) $$

其中，$||w||_2$为向量$w$的L2范数，即：

$$ ||w||_2=\sqrt{w_1^2+w_2^2} $$

为了去除根号方便计算，我们将原式转化为：

$$ min \;\; \frac{1}{2}||w||_2^2 \;\; s.t \;\; y_i(w^Tx_i + b) \geq 1 (i =1,2,…m) $$

由于目标函数$\frac{1}{2}||w||_2^2$是凸函数，同时约束条件不等式是仿射的，根据凸优化理论，我们可以通过拉格朗日函数将我们的优化目标转化为无约束的优化函数。于是根据拉格朗日乘子法，我们得到：

$$ L(w,b,\alpha) = \frac{1}{2}||w||_2^2 - \sum \limits _{i=1}^{m} \alpha_i [y_i(w^Tx_i + b) - 1] \; 满足\alpha_i \geq 0 $$

其中$\alpha_i$为拉格朗日乘子。

# KKT条件

我们对上面的式子求偏导，可以得到

$$ \frac{\partial L }{\partial w}=0,\frac{\partial L }{\partial b}=0 $$

解得

$$ \boldsymbol{w}=\sum_{i=1}^N{\alpha_iy_i\boldsymbol{x}_{\boldsymbol{i}}} $$

$$ \sum_{i=1}^N{\alpha_iy_i}=0 $$

解方程可得

$$ \begin{cases} \alpha_i\geq 0 \\ y_i(\overrightarrow{w_i}\cdot \overrightarrow{x_i}+b)-1\geq 0 \\ \alpha_i(y_i(\overrightarrow{w_i}\cdot\overrightarrow{x_i}+b)-1)=0 \end{cases} $$

上面的式子即为KKT条件

# SVM对偶性

现在我们令

$$ \theta \left( \boldsymbol{w} \right) =\underset{\alpha _{_i}\ge 0}{\max}\ L\left( \boldsymbol{w,}b,\boldsymbol{\alpha } \right) $$

当样本点不满足约束条件时，即在可行解区域外$y_i\left(\boldsymbol{w}\cdot \boldsymbol{x}_{\boldsymbol{i}}+b\right)<1$。此时，将$\alpha_i$设置为无穷大，则$\theta \left( \boldsymbol{w} \right)$也为无穷大。

当样本点不满足约束条件时，即在可行解区域内$y_i\left(\boldsymbol{w}\cdot \boldsymbol{x}_{\boldsymbol{i}}+b\right)\ge1$。此时，$\theta \left( \boldsymbol{w} \right)$为原函数本身。

于是，将两种情况合并起来就可以得到我们新的目标函数：

$$ \theta \left( \boldsymbol{w} \right) =\begin{cases} \frac{1}{2}\lVert \boldsymbol{w} \rVert ^2\ ,\boldsymbol{x}\in \text{可行区域}\\ +\infty \ \ \ \ \ ,\boldsymbol{x}\in \text{不可行区域}\\ \end{cases} $$

于是原约束问题就等价于：

$$ \underset{\boldsymbol{w,}b}{\min}\ \theta \left( \boldsymbol{w} \right) =\underset{\boldsymbol{w,}b}{\min}\underset{\alpha _i\ge 0}{\max}\ L\left( \boldsymbol{w,}b,\boldsymbol{\alpha } \right) $$

由上小节，我们可以知道该函数满足拉格朗日函数对偶性：

优化问题是凸优化问题
满足KKT条件

于是，我们可以将其最小和最大的位置交换一下，这样就变成了：

$$ \underset{\alpha _i\ge 0}{\max}\underset{\boldsymbol{w,}b}{\min}\ L\left( \boldsymbol{w,}b,\boldsymbol{\alpha } \right) $$

从上式中，我们可以先求优化函数对于$w$和$b$的极小值。接着再求拉格朗日乘子$\alpha$的极大值。

通过在上节中由偏导推出的两个式子，我们得到了$w$和$\alpha$的关系，就可以带入优化函数$L(w,b,\alpha)$消去$w$了

此时原式为

我们对目标式子加一个负号，将求解极大转换为求解极小

# SVM核（Kernel）方法

# 基本概念

在上节我们推导出的式子中，我们可以看到上式低维特征仅仅以内积$x_i \bullet x_j$ 的形式出现，如果我们定义一个低维特征空间到高维特征空间的映射$T$，将所有特征映射到一个更高的维度，让数据线性可分，我们就可以求出分离超平面和分类决策函数了。

但是，将数据从低维映射到高维，将会大大增加计算的复杂度，如果遇到无穷维的情况，就根本无从计算了。这时，就需要引入核函数了。

我们定义果存在函数$K(x,z)$，对于任意$x, z$ ，都有：

$$ K(x, z) = T(x) \bullet T(z) $$

那么我们就称$K(x, z)$为核函数。

通过核函数，就避免了在刚才我们提到了在高维维度空间计算内积的恐怖计算量。也就是说，我们可以好好享受在高维特征空间线性可分的红利，却避免了高维特征空间恐怖的内积计算量。

下面我们来看看常见的核函数, 选择这几个核函数介绍是因为scikit-learn中默认可选的就是下面几个核函数。

# 线性核函数（Linear Kernel）

其实就是线性可分SVM，表达式为：

$$ K(x, z) = x \bullet z $$

也就是说，线性可分SVM我们可以和线性不可分SVM归为一类，区别仅仅在于线性可分SVM用的是线性核函数。

# 多项式核函数（Polynomial Kernel）

多项式核函数是线性不可分SVM常用的核函数之一，表达式为：

$$ K(x, z) = （\gamma x \bullet z + r)^d $$

其中，$\gamma, r,d$都需要自己调参定义。

# 高斯核函数（Gaussian Kernel）

在SVM中也称为径向基核函数（Radial Basis Function,RBF），它是非线性分类SVM最主流的核函数。libsvm默认的核函数就是它。表达式为：

$$ K(x, z) = exp(-\gamma||x-z||^2) $$

其中，$\gamma$大于0，需要自己调参定义。

💡 高斯核函数很重要，一定要记住

# Sigmoid核函数

也是线性不可分SVM常用的核函数之一，表达式为：

$$ K(x, z) = tanh（\gamma x \bullet z + r) $$

其中，$\gamma, r$都需要自己调参定义。

# SVM软间隔

有时候本来数据的确是可分的，也就是说可以用线性分类SVM的学习方法来求解，但是却因为混入了异常点，导致不能线性可分，比如下图

有异常点的数据

这种情况下，SVM引入了软间隔最大化的方法来解决。

SVM对训练集里面的每个样本$(x_i,y_i)$引入了一个松弛变量$\xi_i \geq 0$,使函数间隔加上松弛变量大于等于1，也就是说：

$$ y_i(w\bullet x_i +b) \geq 1- \xi_i $$

对比硬间隔最大化，可以看到我们对样本到超平面的函数距离的要求放松了，之前是一定要大于等于1，现在只需要加上一个大于等于0的松弛变量能大于等于1就可以了。当然，松弛变量不能白加，这是有成本的，每一个松弛变量$\xi_i$, 对应了一个代价$\xi_i$，这个就得到了我们的软间隔最大化的SVM学习条件如下：

$$ min\;\; \frac{1}{2}||w||_2^2 +C\sum\limits{i=1}^{m}\xi_i $$

$$ s.t. \;\; y_i(w^Tx_i + b) \geq 1 - \xi_i \;\;(i =1,2,…m) $$

$$ \xi_i \geq 0 \;\;(i =1,2,…m) $$

这里，$C>0$为惩罚参数，可以理解为我们一般回归和分类问题正则化时候的参数。$C$越大，对误分类的惩罚越大，$C$越小，对误分类的惩罚越小。

也就是说，我们希望$\frac{1}{2}||w||_2^2$尽量小，误分类的点尽可能的少。C是协调两者关系的正则化惩罚系数。在实际应用中，需要调参来选择。

# SVM编程实现

 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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74


%% 生成测试数据
classCount= 2;
p= 100;
bound =[0 10];
data =[...
    [2,2]+ randn(p,2),-1*ones(p,1);...
    [6,6]+ randn(p,2),+1*ones(p,1);...
    ];
X= data(:,1:end-1);
Y = data(:,end);
%% 显示生成的测试数据
figure(1)
clf;
gscatter(X(:,1), X(:,2), Y, 'rb', 'X+');
legend({'分类-1', '分类+1'});
title("原始数据散点图");
xlim(bound);
ylim(bound);
%% 拆分训练集和测试集
trainIndex = (mod(1:size(X,1),3)==1);
testIndex = ~trainIndex;

Xtrain=X(trainIndex,:);
Ytrain=Y(trainIndex,:);
Xtest=X(testIndex,:);
Ytest=Y(testIndex,:);
%% 将拆分的结果展示
figure(2)
clf;
hold on;
gscatter(Xtrain(:,1),Xtrain(:,2),Ytrain,'rb','X+');
scatter(Xtest(:,1),Xtest(:,2),'k.');
hold off;
legend({'分类-1','分类+1','测试数据'});
title("划分测试数据后的散点图");
xlim(bound);
ylim(bound);
%% 使用SVM进行训练
svm=fitcsvm(Xtrain,Ytrain);
%% 展示SVM训练的结果
figure(3)
clf; 
gscatter(Xtrain(:,1), Xtrain(:, 2), Ytrain, 'rb', 'X+');
hold on; 
gscatter(svm.SupportVectors(:,1), svm.SupportVectors(:,2),svm.SupportVectorLabels,'rb','oo',13);
xg = bound;
yg = [-svm.Bias/svm.Beta(2) -svm.Beta(1)/svm.Beta(2) * bound(2)-svm.Bias/svm.Beta(2)];
plot(xg, yg, 'g', 'Linewidth', 2);
delta = -svm.Beta(1)/svm.Beta(2)*svm.SupportVectors(1,1)-svm.SupportVectors(1,2)-svm.Bias/svm.Beta(2);
plot(xg, yg-delta, '--g', 'LineWidth', 2); 
plot(xg, yg+delta, '--g', 'LineWidth', 2); 
hold off;
xlim(bound);
ylim(bound);
legend({'分类-1', '分类+1', '支持向量-1', '支持向量+1', '超平面', '超平面-1', '超平面+1'});
title("SVM训练后的散点图");
%% 使用训练好的模型进行预测
Ypred = predict(svm, Xtest);
%% 绘制预测后的结果
figure(4)
clf; 
gscatter(Xtest(:,1), Xtest(:, 2), Ypred, 'rb', 'X+');
hold on;
g = gscatter(svm.SupportVectors(:,1), svm.SupportVectors(:,2), svm.SupportVectorLabels, 'rb','oo',13);
plot(xg, yg, 'g', 'Linewidth', 2);
plot(xg, yg-delta, '--g', 'Linewidth', 2);
plot(xg, yg+delta, '--g', 'Linewidth', 2);
hold off;
xlim(bound);
ylim(bound);
legend({'分类-1', '分类+1', '支持向量-1', '支持向量+1', '超平面', '超平面-1', '超平面+1'});
title("SVM预测后的散点图");
%% 计算误差
fprintf('正确率为：%.2f%%\n',(sum(Ypred==Ytest)/numel(Ytest)).*100);