题解|Pegasos核SVM实现

Pegasos核SVM实现（Pegasos Kernel SVM Implementation）是SVM的一种实现方式。 Pegasos是一种高效的支持向量机（SVM）实现，具有以下特点：

随机梯度下降：Pegasos使用随机梯度下降（SGD）方法进行优化，适合大规模数据集。
核函数支持：支持线性核和RBF核，能够处理非线性可分问题。
正则化：通过引入正则化参数（lambda_val）来防止过拟合，提高模型的泛化能力。
权重更新：仅对不满足约束条件的样本进行权重更新，减少计算量。
迭代更新：通过多次迭代更新权重和偏置，逐步收敛到最优解。本题大体上也和SGD的实现方式相同，不过有线性核和RBF核两种核函数。线性核的公式为

K(x, y) = x \cdot y

RBF核的公式为

K(x, y) = e^{-\frac{||x - y||^2}{2\sigma^2}}

其次，也不需要进行梯度下降，而是做权重更新。在本题中，权重更新公式为

\alpha_i = \alpha_i \eta * (y_i - \lambda * \alpha_i)

b = b \eta * y_i

其中，lambda_val为正则化参数，用于防止过拟合，eta为学习率，用于控制权重更新的步长。此外，本题只需要对不满足约束条件的样本进行权重更新，因此需要遍历所有样本。

标准代码如下

def linear_kernel(x, y):
    return np.dot(x, y)

def rbf_kernel(x, y, sigma=1.0):
    return np.exp(-np.linalg.norm(x-y)**2 / (2 * (sigma ** 2)))

def pegasos_kernel_svm(data, labels, kernel='linear', lambda_val=0.01, iterations=100, sigma=1.0):
    n_samples = len(data)
    alphas = np.zeros(n_samples)
    b = 0

    for t in range(1, iterations + 1):
        for i in range(n_samples):
            eta = 1.0 / (lambda_val * t)
            if kernel == 'linear':
                kernel_func = linear_kernel
            elif kernel == 'rbf':
                kernel_func = lambda x, y: rbf_kernel(x, y, sigma)
    
            decision = sum(alphas[j] * labels[j] * kernel_func(data[j], data[i]) for j in range(n_samples)) + b
            if labels[i] * decision < 1:
                alphas[i] += eta * (labels[i] - lambda_val * alphas[i])
                b += eta * labels[i]

    return np.round(alphas,4).tolist(), np.round(b,4)