支持向量机实现与可视化

一、项目简述

二、算法设计

支持向量机（SVM）

1. 目标：在特征空间中找到一个分割超平面，使得不同类别的数据点间隔最大化。这个超平面可以表示为 ，其中 是超平面的法向量， 是偏置项。

2. 优化问题：寻找 w 和 b 使得 最小化，同时满足所有数据点的约束条件

拉格朗日乘子法

1. 转换：使用拉格朗日乘子法将原始问题转换为无约束优化问题。拉格朗日函数定义为：
这里的是拉格朗日乘子。

2. 对偶问题：通过拉格朗日对偶性，可以将问题转化为关于的优化问题：

KKT条件

1. 核心思想：KKT（Karush-Kuhn-Tucker）条件是求解约束优化问题的关键条件，特别是在SVM中使用SMO算法时。在SVM的背景下，KKT条件提供了一种检验当前解是否为最优解的方式。在本项目中需要检验KKT条件以得知所求解准确性、算法的优越性。

2. 具体形式：在本项目中，其具体形式如下：
• 对偶问题的约束：即有



将其代入目标函数，上述问题又可以转化为



其中是核函数，可用于处理非线性特征。
• 乘子非负性：所有的拉格朗日乘子必须是非负的。
• 原始问题的约束：所有数据点必须位于由超平面正确划分的一侧。
• 互补松弛性：对于每个乘子，要么它是零，要么相应的数据点恰好在边缘上（也就是说，该数据点是支持向量）。

序列最小优化（SMO）算法

1. 核心思想：SMO算法是解决SVM对偶问题的关键。它将大规模的二次规划问题分解为多个小规模的二次规划问题。每次只选择一对 和 进行优化，这大大简化了计算过程。

2. 优化步骤：
1. 选择一对拉格朗日乘子 和 进行优化。这对乘子通常是违反KKT条件最严重的乘子。
2. 计算这对乘子的约束界限和，以确保新的乘子满足约束条件。
3. 优化选定的乘子，使得对偶目标函数最大化。这涉及到解一个简化的一维优化问题，该问题只在乘子的可能范围内搜索最优值。
4. 更新乘子和，同时更新模型的偏置项以及其他依赖于乘子的模型参数。
5. 重复以上步骤，直到所有乘子满足KKT条件（项目中选用的是 ），或者达到预先设定的最大迭代次数。

3. 在具体实践上，将KKT条件转换为以下的情况：
1. 如果 ，则;
2. 如果，则；
3. 如果，则 。

三、代码实现

环境配置

• 开发语言：Python 3.8

• 主要依赖库：
• numpy：用于高效的数值计算。
• matplotlib：用于绘制数据点和分类超平面。
• sklearn：提供SVM标准分类器的实现（用于比较效果）。
• PyQt5：用于构建图形用户界面。

功能模块

• 数据生成：根据用户输入的参数，利用numpy库生成满足特定分布的数据集。

• SVM模型训练：实现了一个自定义的SVM训练算法，并提供了sklearn的SVM实现作为参考。

• 可视化界面：使用PyQt5构建GUI，允许用户输入参数并触发模型训练和可视化过程。

• 结果展示：使用matplotlib展示SVM分类结果和超平面，并提供了模型收敛过程的动态图表。

核心代码

使用步骤

1. 使用以下两种方式之一启动应用程序。
• 点击 main.exe （运行有亿点点缓慢）
• 在终端输入以下指令

2. 在GUI中输入数据生成和SVM训练的参数，不输入则使用默认参数。
这里的参数包含如下
• 数据集相关参数：特征维度、数据集大小、散点到原平面的最小距离、散点的分散程度
• 自定义SVM相关参数：最大迭代次数、正则化常数、\alpha 最终收敛值

3. 点击“Run SVM”按钮以生成数据并训练模型。

4. 观察并分析在不同参数设置下SVM分类超平面的变化。

5. 对比自定义SVM算法与sklearn库中SVM算法的分类结果。

四、实验结果

五、参考资料

1. https://www.bilibili.com/video/BV1HP4y1Y79e/?spm_id_from=333.337.search-card.all.click&vd_source=54848bbaacc95a6670b0f8ac0228b019

2. https://zhuanlan.zhihu.com/p/90405814

3. https://blog.csdn.net/z962013489/article/details/82499063

4. https://blog.csdn.net/z962013489/article/details/82559626

5. https://blog.csdn.net/z962013489/article/details/82622036

6. https://github.com/LasseRegin/SVM-w-SMO