近似线性可分支持向量机 代码实现

### 定义近似线性可分支持向量机
### 软间隔最大化策略
class Soft_Margin_SVM:### 定义基本参数def __init__(self, kernel=linear_kernel, C=None):# 软间隔svm核函数，默认为线性核函数self.kernel = kernel# 惩罚参数self.C = Cif self.C is not None: self.C = float(self.C)### 定义线性支持向量机拟合方法def fit(self, X, y):# 训练样本数和特征数m, n = X.shape# 基于线性核计算Gram矩阵K = self._gram_matrix(X)# 初始化二次规划相关变量：P/q/G/hP = matrix(np.outer(y,y) * K)q = matrix(np.ones(m) * -1)A = matrix(y, (1, m))b = matrix(0.0)# 未设置惩罚参数时的G和h矩阵if self.C is None:G = matrix(np.diag(np.ones(m) * -1))h = matrix(np.zeros(m))# 设置惩罚参数时的G和h矩阵else:tmp1 = np.diag(np.ones(m) * -1)tmp2 = np.identity(m)G = matrix(np.vstack((tmp1, tmp2)))tmp1 = np.zeros(m)tmp2 = np.ones(m) * self.Ch = matrix(np.hstack((tmp1, tmp2)))# 构建二次规划求解sol = solvers.qp(P, q, G, h, A, b)# 拉格朗日乘子a = np.ravel(sol['x'])# 寻找支持向量spv = a > 1e-5ix = np.arange(len(a))[spv]self.a = a[spv]self.spv = X[spv]self.spv_y = y[spv]print('{0} support vectors out of {1} points'.format(len(self.a), m))# 截距向量self.b = 0for i in range(len(self.a)):self.b += self.spv_y[i]self.b -= np.sum(self.a * self.spv_y * K[ix[i], spv])self.b /= len(self.a)# 权重向量self.w = np.zeros(n,)for i in range(len(self.a)):self.w += self.a[i] * self.spv_y[i] * self.spv[i]### 定义Gram矩阵计算函数def _gram_matrix(self, X):m, n = X.shapeK = np.zeros((m, m))# 遍历计算Gram矩阵for i in range(m):for j in range(m):K[i,j] = self.kernel(X[i], X[j])return K

这段代码定义了一个 近似线性可分支持向量机（SVM） 的实现，采用了 软间隔最大化策略，并通过二次规划（Quadratic Programming, QP）来求解最优分类器。它通过核函数支持线性或非线性分类。下面是对这段代码的详细解释：

1. __init__() - 初始化模型参数

def __init__(self, kernel=linear_kernel, C=None):self.kernel = kernelself.C = Cif self.C is not None: self.C = float(self.C)

• kernel：这是支持向量机的核函数，默认为 linear_kernel（线性核函数）。核函数用于计算两个样本之间的相似性，常用的核函数包括线性核、多项式核、RBF核等。
• C：这是 SVM 的惩罚参数 $C$，用于控制软间隔。C 是 SVM 中的重要超参数，它平衡分类间隔的最大化和误分类样本的容忍度：
  • 较大的 C 倾向于减少误分类样本，但可能会导致过拟合。
  • 较小的 C 允许更多的误分类，以提高模型的泛化能力。

2. fit() - 训练支持向量机

def fit(self, X, y):m, n = X.shapeK = self._gram_matrix(X)P = matrix(np.outer(y, y) * K)q = matrix(np.ones(m) * -1)A = matrix(y, (1, m))b = matrix(0.0)

(1) 输入数据：

• X：训练数据的特征矩阵，形状为 $(m,n)$，其中 $m$ 是样本数，$n$ 是特征数。
• y：标签向量，形状为 $(m,)$，每个样本对应一个标签 y i ∈ { − 1 , 1 } y_i \in \{-1, 1\} yi​∈{−1,1}。

(2) Gram 矩阵的计算：

• K = self._gram_matrix(X)：计算 Gram 矩阵 $K$，表示样本之间的相似性。对于线性核 $k(x_i,x_j)=x_i\cdot x_j$，Gram 矩阵就是输入数据的内积矩阵。

(3) 二次规划的定义：

• P：目标函数的二次项，定义为 $P=y_i{y}_j{K}_{ij}$。
• q：线性项，定义为 $q=-1$ 向量。
• A 和 b：线性等式约束，确保 $\sum {\alpha }_i{y}_i=0$。

3. 处理约束条件：

if self.C is None:G = matrix(np.diag(np.ones(m) * -1))h = matrix(np.zeros(m))
else:tmp1 = np.diag(np.ones(m) * -1)tmp2 = np.identity(m)G = matrix(np.vstack((tmp1, tmp2)))tmp1 = np.zeros(m)tmp2 = np.ones(m) * self.Ch = matrix(np.hstack((tmp1, tmp2)))

(1) 无惩罚参数 $C$：

• 如果 $C$ 没有设置，则这是一个 硬间隔 SVM，没有松弛变量。约束条件为 ${\alpha }_i\ge 0$。

(2) 有惩罚参数 $C$：

• 当设置了惩罚参数 $C$ 时，这是 软间隔 SVM，允许有误分类。约束条件为 $0\le {\alpha }_i\le C$，其中 ${\alpha }_i$ 是拉格朗日乘子。

4. 二次规划求解：

sol = solvers.qp(P, q, G, h, A, b)
a = np.ravel(sol['x'])

通过 solvers.qp() 调用 CVXOPT 库来求解二次规划问题，返回的解 sol['x'] 是拉格朗日乘子 $\alpha$。

5. 支持向量的确定：

spv = a > 1e-5
ix = np.arange(len(a))[spv]
self.a = a[spv]
self.spv = X[spv]
self.spv_y = y[spv]
print('{0} support vectors out of {1} points'.format(len(self.a), m))

通过判断 ${\alpha }_i>1e-5$ 来识别支持向量，这些支持向量会影响最终的分类边界。

6. 计算偏置项 $b$：

self.b = 0
for i in range(len(self.a)):self.b += self.spv_y[i]self.b -= np.sum(self.a * self.spv_y * K[ix[i], spv])
self.b /= len(self.a)

偏置项 $b$ 是通过支持向量的标签和 Gram 矩阵的相似性来计算的，它用于调整决策边界的位置。

7. 计算权重向量 $w$：

self.w = np.zeros(n,)
for i in range(len(self.a)):self.w += self.a[i] * self.spv_y[i] * self.spv[i]

对于线性支持向量机，权重向量 $w$ 是支持向量的线性组合。

8. _gram_matrix() - 计算 Gram 矩阵：

def _gram_matrix(self, X):m, n = X.shapeK = np.zeros((m, m))for i in range(m):for j in range(m):K[i, j] = self.kernel(X[i], X[j])return K

Gram 矩阵计算了每对样本之间的核函数值，用于定义二次规划的目标函数。

---

总结

这段代码实现了软间隔支持向量机的训练过程，主要包括以下步骤：

• 核函数：通过核函数（默认线性核）来计算样本间的相似性。
• 二次规划：构建了二次规划问题，最大化分类间隔，并允许误分类（通过惩罚参数 $C$ 控制）。
• 支持向量：利用拉格朗日乘子 $\alpha$ 识别支持向量，这些向量决定了分类边界。
• 权重与偏置：最终通过支持向量计算分类决策函数的权重 $w$ 和偏置 $b$，用于分类新样本。