svm算法伪代码 python

以下是 SVM 算法的伪代码：

输入：训练数据集 {（x1, y1），（x2, y2），…，（xn, yn）}，其中 xi ∈ R^n，yi ∈ {-1, +1}，i = 1, 2, …, n

输出：最优解 w、b 和拉格朗日乘子 α

1：初始化 αi = 0，i = 1, 2, …, n
2：while 迭代次数小于最大迭代次数 do
3：    for i = 1 to n do
4：        计算 Ei = f(xi) - yi
5：        if ((yi * Ei < -tolerance) and (αi < C)) or ((yi * Ei > tolerance) and (αi > 0)) then
6：            随机选择 j ≠ i
7：            计算 Ej = f(xj) - yj
8：            保存旧的 αi 和 αj
9：            if (yi != yj) then
10：                L = max(0, αj - αi)
11：                H = min(C, C + αj - αi)
12：            else
13：                L = max(0, αi + αj - C)
14：                H = min(C, αi + αj)
15：            if L == H then
16：                continue
17：            计算 η = 2 * xi * xj - xi * xi - xj * xj
18：            if η >= 0 then
19：                continue
20：            更新 αj
21：            if (abs(αj - old_αj) < 0.00001) then
22：                continue
23：            更新 αi
24：            更新 b
25：    end for
26：    if 所有 αi 都满足 KKT 条件 then
27：        break
28：end while
29：计算 w = Σ[1~n] αi * yi * xi
30：返回 w、b 和 α

其中，f(x) 是分类决策函数，tolerance 是容错率，C 是惩罚参数，KKT 条件是指满足以下任何一条的样本点：

- αi = 0，表示该样本点在决策边界之外；
- 0 < αi < C，表示该样本点在决策边界上；
- αi = C，表示该样本点在决策边界之内。