支持向量机Part5—Python实现

1.手写数字识别

今天的目标是实现SVM分类器，并用于手写数字识别。（为简单起见，假设总共有两类数据：6和8，如何对两类数据进行分类？）

2.数据处理

所有的数字图片被分为两类：训练数据和测试数据；

单张图片被处理成以下文本格式：由0和1组成的32*32矩阵；且命名规则为：数字_图片序号（如6_10.txt，数字6的第10张图片）。

6_10.txt

2.1单张图片数据处理

将32*32的图片矩阵转换为1*1024的一维向量。

2.2图片数据集处理

将训练或测试文件夹下所有的图片转换为一个m*n的矩阵（m为数据集中图片张数；n为特征数，这里n=1024），并得到类别标签向量（为便于SVM分类，将数字6、8的类别标签分别定义为1、-1）。

3.实现SVM分类器

3.1核函数

3.1.1线性核函数

3.1.2径向基核函数

3.2创建SVM基类

3.3辅助函数

3.3.1裁剪

3.3.2误差计算：

这里用到了

「分类模型」支持向量机Part4—SMO算法

中的理论推导：

3.4SMO算法内层循环

SMO算法每次选择两个变量进行优化，希望在满足KKT条件下，优化函数取极小值。因此，外层循环优化变量a1：选择违反KKT条件的点；内层循环优化变量a2：哪个a和a1配对能使代价函数达到最小就将其选为a2。

1.外层循环优化变量a1的选择方法在3.5中说明：

当选择好a1后，判断所选择的第一个变量是否违反KKT条件：

2.内层循环优化变量a2的选择方法：

随机选择：保证与选择的第一个优化变量a1不同

选择使|Ei-Ej|最大的j值：

SMO算法内层循环需要用到以下理论推导：

1.计算a_j:

2.计算a的边界：

3.计算b：

SMO算法内层循环代码：

3.5SMO算法外层循环

外层循环优化变量a1的选择方法：

1.遍历所有a可取的值，判断是否违反KKT条件：

2.当有a1/a2被优化时，选择不在边界0/C上的a值，判断其是否违反KKT条件；

SMO算法外层循环代码：

4.训练/测试分类器

实现好SVM分类器后，利用训练数据集训练SVM分类器，并用测试数据集对分类器进行验证。

5.运行结果

最终得到训练数据集与测试数据集的分类错误率分别为：0%/1.0753%。