python实现svm
CVXOPT is a free python package that is widely used in solving the convex optimization problem. In this article, I will first introduce the use of CVXOPT in quadratic programming, and then discuss its application in implementing Support Vector Machine (SVM) by solving the dual optimization problem.
CVXOPT是一个免费的python软件包，广泛用于解决凸优化问题。 在本文中，我将首先介绍CVXOPT在二次编程中的用途，然后通过解决双重优化问题来讨论其在实现支持向量机(SVM)中的应用。
To understand how to use CVXOPT, we need to know its standard form and apply it to each individual question. According to CVXOPT API, we can solve the optimization problem in this form:
要了解如何使用CVXOPT，我们需要了解其标准格式并将其应用于每个单独的问题。 根据CVXOPT API，我们可以通过以下形式解决优化问题：
standard form 标准格式It is solving a minimization problem, with two types of linear constraints. One is an inequality constraint, and another is an equality constraint. To use the package to solve for the best x, that minimizing the object function, under the linear constraints, we just need to transform the specific question to identify matrics P, q, G, h, A, b.
它正在解决具有两种线性约束的最小化问题。 一个是不平等约束，另一个是平等约束。 为了使用包来求解最佳x，从而在线性约束下最小化目标函数，我们只需要变换特定问题即可识别矩阵P，q，G，h，A，b。
Let’s take a simple example from here:
让我们从这里举一个简单的例子：
an example 一个例子In this example, we have two variables we need to solve for optimization, which is x1 and x2. First, look at the objective function 2x1² +x2² +x1x2+x1+x2, we can rewrite it as its matrix form:
在此示例中，我们需要求解两个变量以进行优化，分别是x1和x2。 首先，查看目标函数2x1²+x2²+ x1x2 + x1 + x2，我们可以将其重写为矩阵形式：
P is the matrix that captures the two-dimensions’ coefficients. Thus we look at the coefficients of x1², x2², and x1x2 to construct P. Taking into consideration the 1/2 in front, P is:
P是捕获二维系数的矩阵。 因此，我们看一下x1²，x2²和x1x2的系数来构造P。考虑到前面的1/2，P为：
And q is the matrix for x1 and x2, which is:
q是x1和x2的矩阵，即：
The next step is to build the linear constraints, lets start with the inequality to find out G and h. The standard form has equality with the less-than sign, while in the question, we have the larger-than sign. Thus, we need to transform the question by multiply negative one on both sides, we will get:
下一步是建立线性约束，让我们从不等式开始找出G和h。 标准形式与小于号相等，而在问题中，我们具有大于号。 因此，我们需要通过在两边都乘以负数来变换问题，我们将得到：
-x1 ≤ 0
-x1≤0
-x2 ≤ 0
-x2≤0
The corresponding G and h is:
相应的G和h为：
And A, b is straightforward:
A，b很简单：
A is a diagonal matrix and b is a scalar.
A是对角矩阵，b是标量。
With this example, I illustrate how we can transform a practical question to match the standard form of the CVXOPT package and find all the matrice to solve the optimization problem.
在此示例中，我说明了如何转换一个实际问题以匹配CVXOPT软件包的标准形式，并找到所有矩阵来解决优化问题。
One application of using the CVXOPT package from python is to implement SVM from scratch. Support Vector Machine is a supervised machine learning algorithm that is usually used for binary classification problems, although it is also possible to use it to solve multi-classification problems and regression problems. We define the cost function of the soft margin binary class linear SVM as:
使用来自python的CVXOPT软件包的一个应用是从头开始实现SVM。 支持向量机是一种有监督的机器学习算法，通常用于二进制分类问题，尽管也可以使用它来解决多分类问题和回归问题。 我们将软裕度二进制类别线性SVM的成本函数定义为：
This is the primal problem. The soft margin means that we are allowing some support vectors to across the hyperplane and be assigned to the wrong classes when finding the maximal margin.
这是首要问题。 软边距意味着我们允许某些支持向量穿过超平面，并在找到最大边距时被分配给错误的类。
The support vectors that cross the hyperplane is called slacks. C is a constant, which is a hyper-parameter that defines the “cost” of the slacks. When C is small, it is efficient to allow more points into the margin to achieve a larger margin. Larger C will produce boundaries with fewer support vectors. By increasing the number of support vectors, SVM reduces its variance since it depends less on any individual observation. Reducing variance makes the model more generalized. Thus, decreasing C will increase the number of support vectors and reduce over-fitting.
穿过超平面的支持向量称为松弛。 C是一个常数，它是定义松弛的“成本”的超参数。 当C较小时，允许有更多点进入边距以实现更大的边距是有效的。 C越大，边界越少，支持向量也越少。 通过增加支持向量的数量，SVM减少了方差，因为它较少依赖于任何单独的观察。 减少方差使模型更通用。 因此，降低C将增加支持向量的数量并减少过度拟合。
In solving the primal problem, we are minimizing the cost function regarding both w and b. We can rewrite the constrained optimization problem as the primal Lagrangian function with Lagrange multipliers \alpha_i ≥0 and \mu_i ≥ 0 for our two constraints, and get the following:
在解决原始问题时，我们将w和b的成本函数最小化。 对于两个约束，我们可以用拉格朗日乘数\ alpha_i≥0和\ mu_i≥0将约束优化问题重写为原始拉格朗日函数，并得到以下结果：
Instead of minimizing over w and b, subject to constraints involving \alpha, we can maximize over \alpha subject to the relations obtained previously for w and b. This is called the dual Lagrangian formulation:
代替最小化w和b，受涉及\ alpha的约束，我们可以最大化\ alpha受先前为w和b获得的关系。 这称为双重拉格朗日公式：
the dual problem for SVM 支持向量机的双重问题Where x are the features and y is the target value. y is defined as 1 for the positive class and -1 for the negative class. In this article, we will show the soft margin implementation of binary class linear SVM by solving the dual problem.
其中x是特征，y是目标值。 y被定义为1(对于正类)和-1(对于负类)。 在本文中，我们将通过解决对偶问题来说明二进制类线性SVM的软边距实现。
First, we need to rewrite the objective function from maximizing to minimizing and rewrite the linear constraints to fit the CVXOPT package. Let’s define a matrix H, which equals to:
首先，我们需要从最大化到最小化重写目标函数，并重写线性约束以适合CVXOPT软件包。 让我们定义一个矩阵H，它等于：
We can rewrite the optimizing problem as:
我们可以将优化问题重写为：
times -1:
-1：
From here, it is clear what are P, q, G, h, A, and b. Suppose we have m features, and n observations. P is the same as H with size equals to m*m; q is a m*1 vector of -1s; G vertically combines two m*m diagonal matrics. The top diagonal value is -1 and the bottom diagonal value is 1. h is a 2m*1 vector with m zeros on the top, and m Cs on the bottom. A is the target value vector y transposed and b is a scaler that equals to 0. Here is a python implementation using Numpy and CVXOPT. We can find more details on this website.
从这里可以清楚地知道P，q，G，h，A和b是什么。 假设我们有m个特征和n个观测值。 P与H相同，大小等于m * m； q是-1s的am * 1向量； G垂直组合两个m * m对角矩阵。 顶部对角线值为-1，底部对角线值为1。h是2m * 1向量，顶部m个零，底部m Cs。 A是目标值向量y的转置，b是等于0的缩放器。这是使用Numpy和CVXOPT的python实现。 我们可以在该网站上找到更多详细信息。
Furthermore, we can check the accuracy of the implementation with this function here:
此外，我们可以在此处使用此功能检查实现的准确性：
Hope this article helps you understand the implementation of CVXOPT and SVM. If you are interested, you can use some dataset to test the SVM implementation here and compare it with the scikit-learn package from Python.
希望本文能帮助您了解CVXOPT和SVM的实现。 如果您有兴趣，可以在此处使用一些数据集来测试SVM实现，并将其与Python中的scikit-learn包进行比较。
Thank you for reading!
感谢您的阅读！
Did you know that we have three publications and a YouTube channel? Find links to everything at plainenglish.io!
您知道我们有三个出版物和一个YouTube频道吗？ 在plainenglish.io上找到所有内容的链接！
翻译自: https://medium.com/python-in-plain-english/introducing-python-package-cvxopt-implementing-svm-from-scratch-dc40dda1da1f
python实现svm
相关资源：python svm算法源码