手动实现硬间隔支持向量机

### 手动实现硬间隔支持向量机（Hard Margin SVM） 硬间隔支持向量机是一种用于线性可分数据的分类算法。它的核心思想是找到一个最优超平面，使得两类数据被完全分开的同时，最大化距离超平面最近的数据点之间的间隔[^3]。 以下是手动实现硬间隔支持向量机的过程： #### 数据准备 假设输入数据为 \( X \in \mathbb{R}^{n \times d} \)，其中 \( n \) 表示样本数量，\( d \) 表示特征维度；标签为 \( y \in \{-1, 1\}^n \)。目标是最小化以下优化问题的目标函数并满足约束条件： \[ \min_{w,b} \frac{1}{2}\| w \| ^2 \] 受制于： \[ y_i (w^\top x_i + b) \geq 1, \quad i=1,\dots,n. \] --- #### 实现步骤 通过拉格朗日乘子法可以将原始问题转化为对偶形式，并利用二次规划求解权重参数 \( w \) 和偏置项 \( b \)[^1]。 ##### 对偶问题推导 定义拉格朗日函数如下： \[ L(w, b, \alpha) = \frac{1}{2} \| w \|^2 - \sum_{i=1}^n \alpha_i [y_i (w^\top x_i + b) - 1], \] 其中 \( \alpha_i \geq 0 \) 是拉格朗日乘子。通过对 \( w \) 和 \( b \) 进行偏导数计算得到 KKT 条件下的解析表达式： \[ w = \sum_{i=1}^n \alpha_i y_i x_i, \] 以及对于任意支持向量成立的关系式： \[ b = y_k - \sum_{j=1}^n \alpha_j y_j x_j^\top x_k, \quad k \text{ is a support vector}. \] 最终对偶问题是最大化的凸二次规划问题： \[ \max_\alpha \sum_{i=1}^n \alpha_i - \frac{1}{2} \sum_{i,j=1}^n \alpha_i \alpha_j y_i y_j x_i^\top x_j, \] 受制于： \[ \alpha_i \geq 0, \quad \forall i, \] 和 \[ \sum_{i=1}^n \alpha_i y_i = 0. \] --- #### Python代码实现 下面是一个简单的硬间隔支持向量机的手动实现代码： ```python import numpy as np from cvxopt import matrix, solvers class HardMarginSVM: def __init__(self): self.alpha = None self.support_vectors = None self.b = None def fit(self, X, y): m, n = X.shape # Convert labels to double and ensure they are either -1 or 1 y = y.reshape(-1, 1) * 1.0 # Compute the Gram Matrix K = np.dot(X, X.T) # Define QP parameters P = matrix(np.outer(y, y) * K) q = matrix(-np.ones((m, 1))) G = matrix(-np.eye(m)) h = matrix(np.zeros(m)) A = matrix(y.reshape(1, -1).astype('float')) b = matrix(np.zeros(1)) # Solve QP problem solution = solvers.qp(P, q, G, h, A, b) # Extract alpha values from the solution alphas = np.array(solution['x']) # Find support vectors where alpha > threshold sv_indices = ((alphas > 1e-5).flatten()) ind = np.arange(len(alphas))[sv_indices] self.alpha = alphas[sv_indices] self.support_vectors = X[ind] self.sv_labels = y[ind] # Calculate bias term using first support vector self.b = np.mean([yi - sum(a*yj*K[i][j] for j,(a,yj) in enumerate(zip(self.alpha,self.sv_labels))) for i, yi in zip(ind, self.sv_labels)]) def predict(self, X_test): result = [] for xi in X_test: prediction = sum(alpha * yi * np.dot(xi, xj) for (alpha, yi, xj) in zip(self.alpha, self.sv_labels, self.support_vectors)) + self.b result.append(np.sign(prediction)) return np.array(result) ``` --- #### 使用说明 要使用上述类进行预测，请按照以下方式操作： ```python # Example usage of HardMarginSVM class X_train = np.array([[1, 2], [2, 3], [3, 3], [-1, -1], [-2, -2]]) y_train = np.array([1, 1, 1, -1, -1]) svm_model = HardMarginSVM() svm_model.fit(X_train, y_train) X_test = np.array([[0, 0], [4, 4]]) predictions = svm_model.predict(X_test) print(predictions) ``` --- #### 注意事项 由于硬间隔支持向量机仅适用于线性可分的情况，在实际应用中可能需要考虑软间隔支持向量机或其他改进版本。