# 加载一个名为“linear.csv”的数据集，并对其进行可视化处理。

import numpy as np
import matplotlib.pyplot as plt
from matplotlib.colors import ListedColormap
from tqdm import tqdm, trange

- `numpy` 用于数值计算和数据操作。

- `matplotlib.pyplot` 用于数据可视化。

- `matplotlib.colors.ListedColormap` 用于自定义颜色映射。

- `tqdm` 和 `trange` 用于创建进度条。

从名为“linear.csv”的文件中加载数据

data = np.loadtxt('linear.csv', delimiter=',')
print('数据集大小：', len(data))
x = data[:, :2] # 提取数据的前两列，作为特征变量 `x`。
y = data[:, 2] # 提取数据的第三列，作为目标变量 `y`。

# 数据集可视化
plt.figure()
plt.scatter(x[y == -1, 0], x[y == -1, 1], color='red', label='y=-1')
# 绘制标签为 `-1` 的数据点，使用红色表示。
plt.scatter(x[y == 1, 0], x[y == 1, 1], color='blue', marker='x', label='y=1')
# 绘制标签为 `1` 的数据点，使用蓝色并标记为“x”。
plt.xlabel(r'$x_1#39;)
plt.ylabel(r'$x_2#39;)
plt.legend()
plt.show()
plt.savefig('svmPlot.png')

读取一个 CSV 文件，将数据分成特征变量和目标变量，然后用散点图可视化其中的两类数据点。

红色表示标签为 `-1` 的数据点，蓝色表示标签为 `1` 的数据点。

SMO

"""
实现支持向量机（SVM）的序列最小优化（Sequential Minimal Optimization，SMO）算法。
SMO 算法用于解决二次规划问题，从而训练 SVM 模型。
"""

def SMO(x, y, ker, C, max_iter):
    '''
    SMO算法
    x，y：样本的值和类别
    ker：核函数，与线性回归中核函数的含义相同，用于计算样本之间的相似度。
    C：惩罚系数，控制软间隔的惩罚力度。
    max_iter：最大迭代次数
    '''
    # 初始化参数
    m = x.shape[0]
    alpha = np.zeros(m)
		"""
		- `m` 是样本数量。
    - `alpha` 是拉格朗日乘子，初始化为全零数组，长度为样本数量。
		"""
        
    # 预先计算所有向量的两两内积，减少重复计算
    K = np.zeros((m, m))
    for i in range(m):
        for j in range(m):
            K[i, j] = ker(x[i], x[j])
		"""
		- `K` 是预先计算的核矩阵，用于存储样本之间的两两内积（相似度）。
		- 使用双重循环计算并存储所有样本之间的核函数值，减少重复计算。
		"""
    
    for l in trange(max_iter):
        # 开始迭代
        for i in range(m):
            # 有m个参数，每一轮迭代中依次更新
            # 固定参数alpha_i与另一个随机参数alpha_j，并且保证i与j不相等
            j = np.random.choice([l for l in range(m) if l != i])
        		
            """
						- 使用 `trange` 创建带有进度条的迭代次数。
						- 对于每次迭代中的每个样本 `i`：
 					 - 随机选择另一个不同于 `i` 的样本 `j`。

						"""
            
            # 用-b/2a更新alpha_i的值
            eta = K[j, j] + K[i, i] - 2 * K[i, j] # 分母
            e_i = np.sum(y * alpha * K[:, i]) - y[i] # 分子
            e_j = np.sum(y * alpha * K[:, j]) - y[j]
            alpha_i = alpha[i] + y[i] * (e_j - e_i) / (eta + 1e-5) # 防止除以0
            zeta = alpha[i] * y[i] + alpha[j] * y[j]
						"""
						- 计算 `eta`，用于更新 `alpha_i`，防止除以零。
						- 计算误差 `e_i` 和 `e_j`。
						- 根据更新公式计算新的 `alpha_i` 值，并防止除以零。
						- 计算 `zeta`，用于约束 `alpha` 值。
						"""

            # 将alpha_i和对应的alpha_j保持在[0,C]区间
            # 0 <= (zeta - y_j * alpha_j) / y_i <= C
            if y[i] == y[j]:
                lower = max(0, zeta / y[i] - C)
                upper = min(C, zeta / y[i])
            else:
                lower = max(0, zeta / y[i])
                upper = min(C, zeta / y[i] + C)
            alpha_i = np.clip(alpha_i, lower, upper)
            alpha_j = (zeta - y[i] * alpha_i) / y[j]
            
            # 更新参数
            alpha[i], alpha[j] = alpha_i, alpha_j

    return alpha

# 用-b/2a更新alpha_i的值 部分的详细说明

- `eta` 是用于更新 \(\alpha_i\) 的分母，表示 \((x_i - x_j)\) 的平方和。具体计算公式为。

- `K[i, j]` 表示核函数 `ker(x[i], x[j])` 的值，即样本 \(x_i\) 和 \(x_j\) 之间的内积。

- 这个公式的作用是衡量两个样本之间的相似度，确保更新过程中有足够的信息量。

- `e_i` 是误差项，表示当前模型在样本 \(i\) 上的预测误差。

- `np.sum(y * alpha * K[:, i])` 计算所有样本对样本 \(i\) 的贡献。

- `y * alpha` 是每个样本的标签与对应拉格朗日乘子的乘积。

- `K[:, i]` 是核矩阵中第 \(i\) 列，表示所有样本与样本 \(i\) 的内积。

- `e_i` 的计算公式为。

- `e_j` 是误差项，表示当前模型在样本 \(j\) 上的预测误差。

- 计算方式与 `e_i` 相同，只是针对样本 \(j\)。

alpha_i = alpha[i] + y[i] * (e_j - e_i) / (eta + 1e-5) # 防止除以0

- 根据 SMO 算法的更新公式计算新的 \(\alpha_i\) 值。

- 更新公式为，其中 \(\epsilon = 1e-5\) 用于防止除以零。

- `y[i] * (e_j - e_i)` 表示误差差异的影响。

- `eta + 1e-5` 确保分母非零，以避免数值计算中的除零错误。

zeta = alpha[i] * y[i] + alpha[j] * y[j]

- `zeta` 是用于约束 \(\alpha_i\) 和 \(\alpha_j\) 的辅助变量，表示的值。

- 这个变量用于在更新 \(\alpha_i\) 和 \(\alpha_j\) 时保持其线性约束不变，即。

- 这里通过计算 \(\eta\)（分母）、\(e_i\) 和 \(e_j\)（分子）来更新 \(\alpha_i\)。

- `eta` 衡量样本间的相似度，`e_i` 和 `e_j` 表示预测误差。

- `alpha_i` 根据 SMO 更新公式进行调整，并用 `zeta` 变量保持拉格朗日乘子的约束条件。

# 将alpha_i和对应的alpha_j保持在[0,C]区间 部分的详细说明

该部分的目的是在更新 \(\alpha_i\) 和 \(\alpha_j\) 时，确保它们的值在合法范围内（即在 \([0, C]\) 区间内），并满足某些约束条件。

- 首先，根据样本 \(i\) 和 \(j\) 的标签 \(y[i]\) 和 \(y[j]\) 是否相同，来设置 \(\alpha_i\) 的上下限。

- 如果 \(y[i]\) 和 \(y[j]\) 相同，计算 \(\alpha_i\) 的上下限：

- `lower = max(0, zeta / y[i] - C)`：

- `zeta / y[i] - C` 是一个可能的下限，如果它小于零，则取零作为下限。

- `upper = min(C, zeta / y[i])`：

- `zeta / y[i]` 是一个可能的上限，如果它大于 \(C\)，则取 \(C\) 作为上限。

- `else:`：

- 如果 \(y[i]\) 和 \(y[j]\) 不同，计算 \(\alpha_i\) 的上下限：

- `lower = max(0, zeta / y[i])`：

- `zeta / y[i]` 是一个可能的下限，如果它小于零，则取零作为下限。

- `upper = min(C, zeta / y[i] + C)`：

- `zeta / y[i] + C` 是一个可能的上限，如果它大于 \(C\)，则取 \(C\) 作为上限。

这些条件确保 \(\alpha_i\) 的值在合法范围内，并且满足优化问题的约束条件。

alpha_i = np.clip(alpha_i, lower, upper)

- 使用 `np.clip` 函数将 \(\alpha_i\) 的值限制在 `[lower, upper]` 范围内。

- `np.clip` 确保 \(\alpha_i\) 不会超过设定的上下限。

• 如果 alpha_i 中的某个元素小于 lower，则会被替换为 lower；如果大于 upper，则会被替换为 upper；否则保持不变。
• 最终，alpha_i 的值被限制在 [lower, upper] 范围内，并存储回 alpha_i 变量中，以确保更新后的拉格朗日乘子在合法的范围内。

alpha_j = (zeta - y[i] * alpha_i) / y[j]

- 根据更新后的 \(\alpha_i\) 计算相应的 \(\alpha_j\) 值。

- 公式为 ，保证了线性约束条件 的成立。

- 该部分通过比较样本标签来设定 αi\alpha_iαi 的上下限，确保其值在合法范围内。

- 使用 `np.clip` 将 \(\alpha_i\) 的值限制在计算出的上下限之间。

- 最后，根据更新后的 \(\alpha_i\) 计算出对应的 \(\alpha_j\)，以满足优化问题的约束条件。

Ref：

动手学机器学习课程