实现线性核函数的svm

以下是一个简单的Python代码实现线性核函数的SVM：

import numpy as np
from cvxopt import matrix, solvers

class SVM:
    def __init__(self, C=1.0):
        self.C = C
        self.kernel = self.linear_kernel

    def fit(self, X, y):
        n_samples, n_features = X.shape

        # Gram matrix
        K = np.zeros((n_samples, n_samples))
        for i in range(n_samples):
            for j in range(n_samples):
                K[i,j] = self.kernel(X[i], X[j])

        P = matrix(np.outer(y, y) * K)
        q = matrix(np.ones(n_samples) * -1)
        A = matrix(y, (1, n_samples))
        b = matrix(0.0)

        if self.C is None:
            G = matrix(np.identity(n_samples) * -1)
            h = matrix(np.zeros(n_samples))
        else:
            G_max = np.identity(n_samples) * -1
            G_min = np.identity(n_samples)
            G = matrix(np.vstack((G_max, G_min)))
            h_max = matrix(np.zeros(n_samples))
            h_min = matrix(np.ones(n_samples) * self.C)
            h = matrix(np.vstack((h_max, h_min)))

        # Solve QP problem
        solution = solvers.qp(P, q, G, h, A, b)

        # Lagrange multipliers
        a = np.ravel(solution['x'])

        # Support vectors have non zero lagrange multipliers
        sv = a > 1e-5
        ind = np.arange(len(a))[sv]
        self.a = a[sv]
        self.sv = X[sv]
        self.sv_y = y[sv]
        print("%d support vectors out of %d points" % (len(self.a), n_samples))

        # Intercept
        self.b = 0
        for n in range(len(self.a)):
            self.b += self.sv_y[n]
            self.b -= np.sum(self.a * self.sv_y * K[ind[n],sv])
        self.b /= len(self.a)

    def predict(self, X):
        y_predict = np.zeros(len(X))
        for i in range(len(X)):
            s = 0
            for a, sv_y, sv in zip(self.a, self.sv_y, self.sv):
                s += a * sv_y * self.kernel(X[i], sv)
            y_predict[i] = s
        return np.sign(y_predict + self.b)

    def linear_kernel(self, x1, x2):
        return np.dot(x1, x2)

在这个代码中，我们使用了cvxopt库来解决二次规划问题。在fit函数中，我们首先计算Gram矩阵，然后构造QP问题的P、q、A、b、G和h矩阵。然后，我们使用cvxopt的qp函数来解决QP问题，并得到拉格朗日乘数a。我们选择拉格朗日乘数大于1e-5的样本点作为支持向量。最后，我们计算截距b并保存模型参数。

在predict函数中，我们使用保存的支持向量和拉格朗日乘数来预测新的样本点的类别。

我们可以使用以下代码来测试这个SVM分类器：

import matplotlib.pyplot as plt
from sklearn.datasets import make_blobs

X, y = make_blobs(n_samples=100, centers=2, random_state=42)

fig, ax = plt.subplots()
ax.scatter(X[:,0], X[:,1], c=y)

svm = SVM()
svm.fit(X, y)

# plot support vectors
ax.scatter(svm.sv[:,0], svm.sv[:,1], s=100, facecolors='none', edgecolors='k')

# plot decision boundary
xlim = ax.get_xlim()
ylim = ax.get_ylim()
xx = np.linspace(xlim[0], xlim[1], 30)
yy = np.linspace(ylim[0], ylim[1], 30)
YY, XX = np.meshgrid(yy, xx)
xy = np.vstack([XX.ravel(), YY.ravel()]).T
Z = svm.predict(xy).reshape(XX.shape)
ax.contour(XX, YY, Z, colors='k', levels=[-1, 0, 1], alpha=0.5, linestyles=['--', '-', '--'])
ax.set_title("Linear SVM")
plt.show()

这个代码将生成一个随机的二分类数据集，并训练一个线性核函数的SVM来分类。它还将绘制决策边界和支持向量。