问题引入

支持向量机
在这个二维空间中存在两类点，现在需要画一条直线，将这两类点区分开来，并且当有新数据加入时，能根据这条线判断它属于哪一类，应该如何画这条线。

这个问题可以进一步推演到三维空间中，如何用一个二维平面区分两类数据，也可以更进一步推演至高维空间。

那么，以上问题可以被归纳为，为了区分两类数据，NN 为数据的样本数，MM 为维度数，如何设计一个维度为 M−1M-1 的超平面，将两类数据区分开来。

SVM算法

支持向量机（Support Vector Machine，SVM）是一种经典的监督学习算法，用于解决二分类和多分类问题。其核心思想是通过在特征空间中找到一个最优的超平面来进行分类，并且间隔最大。

间隔


上面是两种不同的分类画法，左边的存在数据点与决策边界线相当接近，若有一个新的数据点同样接近该边界线，这样错误的概率就会很大。

而第二种画法，两类数据中所有的点都与边界线有着一定的距离，我们把这个距离称为间隔，这个间隔起着缓冲的作用，把两类数据分隔开来。

间隔距离可以体现出两类数据的差异大小，间隔越大，意味着两类数据差异越大，区分就越容易，因此求解最佳决策边界线的问题就可以转化为求解最大间隔问题。

支持向量


由于上下边界一定会经过一些样本数据点，这些点距离决策边界最近，他们决定了间隔距离，我们称他们为支持向量(Support Vector)

对于图中所示方程，我们分别同时除以 cc

w1cx1+w2cx2+bc=1w1cx1+w2cx2+bc=0w1cx1+w2cx2+bc=−1\frac{w_1}{c}x_1+\frac{w_2}{c}x_2+\frac{b}{c}=1\\\frac{w_1}{c}x_1+\frac{w_2}{c}x_2+\frac{b}{c}=0\\\frac{w_1}{c}x_1+\frac{w_2}{c}x_2+\frac{b}{c}=-1

由于 wc,bc\frac{w}{c},\frac{b}{c} 只是我们求解的两个变量名字，因此将他们替换为 w,bw,b 也不会影响计算

即 $$w_1x_1+w_2x_2+b=1\w_1x_1+w_2x_2+b=0\w_1x_1+w_2x_2+b=-1$$

这样我们就可以将上下两个个方程定义为正负超平面

所有正超平面及其上方的点都属于正类，所有负超平面及其下方的点都属于负类，此时，当有新数据点加入时，我们就可以根据它与决策超平面的相对位置来进行分类

损失因子


若数据中存在异常点，按照之前的方法计算，会导致间隔明显减少，忽略它间隔会变大，那么我们需不需要为这样一个异常值，去牺牲我们的间隔距离呢？

对于这种异常点，我们可以引入损失因子这个概念，所有违背规则的点都会有对应的损失值。

软间隔与硬间隔


假设将间隔比作收入，损失比作成本，那么同时考虑收入与成本，最大化我们的利润，这样的情况下形成的最优解我们称之为“软间隔”，它有一定的容错率，目的是在间隔距离和损失大小之间找到一个平衡。

而之前推导出的间隔则被称为“硬间隔”

升维转化与核技巧(Kernel Trick)

什么是升维转化


如图，显然我们找不到一条直线将其有效区分

但如果我们通过升维转化，就可以在三维空间中进行求解了

所以，对于这些在低纬度下无法区分的数据，我们就可以采用类似的方法，通过合适的维度转化函数，将低纬数据进行升维，然后在高纬度下求解SVM模型

然而，提升维度需要我们有明确的维度转化函数，更多的储存需求以及计算需求

核函数

由于SVM的本质是量化两类数据差异的方法，而核函数能够提供高纬度相似度的测量，通过选取合适的核公式，我们就可以不用知道具体的维度转化函数，直接获取高纬度的数据差异度，从而来进行分类

求解SVM决策超平面

定义

  • 训练数据及标签 (x1,y1),(x2,y2),...(xN,yN)(x_1,y_1),(x_2,y_2),...(x_N,y_N), 其中 xix_i 为 m 维的向量，yiy_i 为标签，其值为 1 或 -1
  • 线性模型：(w,b)(w, b), 其方程为 wTx+b=0w^Tx+b=0（超平面）
  • 一个训练集线性可分是指
    • ∃(w,b)\exists(w,b) 使：
      对 ∀i=1\forall i=1~NN，有：
      若 yi=+1y_i=+1，则 wTxi+b≥0w^Tx_i+b\ge0
      若 yi=−1y_i=-1，则 wTxi+b<0w^Tx_i+b<0
      即 yi(wTxi+b)≥0y_i(w^Tx_i+b)\ge0（公式一）

优化问题

  • 最小化(Minimize)：∣∣w∣∣2||w||^2
  • 限制条件(Subject to)：yi(wTxi+b)≥0,(i=1∼N)y_i(w^Tx_i+b)\ge0,(i=1\sim N)


还是以二维平面为例，我们的目标是求最大间隔距离，我们分别在正负超平面上选取一个点 xm,xnx_m,x_n ，由于他们都位于超平面上，所以满足等式1,2

1. w1x1m+w2x2m+b=12. w1x1n+w2x2n+b=−11.\ w_1x_{1m}+w_2x_{2m}+b=1\\2.\ w_1x_{1n}+w_2x_{2n}+b=-1

等式1减等式2得

3. w1(x1m−x1n)+w2(x2m−x2n)=2即4. w⃗⋅(x⃗m−x⃗n)=2\\3.\ w_1(x_{1m}-x_{1n})+w_2(x_{2m}-x_{2n})=2\\即4.\ \vec{w}\cdot(\vec{x}_m-\vec{x}_n)=2

同时，我们在决策超平面上取两个点 xo,xpx_o,x_p，那么他们满足如下等式

5. w1x1o+w2x2o+b=06. w1x1p+w2x2p+b=05.\ w_1x_{1o}+w_2x_{2o}+b=0\\6.\ w_1x_{1p}+w_2x_{2p}+b=0

等式5减去等式6得

7. w1(x1o−x1p)+w2(x2o−x2p)=0即8. w⃗⋅(x⃗o−x⃗p)=0\\7.\ w_1(x_{1o}-x_{1p})+w_2(x_{2o}-x_{2p})=0\\即8.\ \vec{w}\cdot(\vec{x}_o-\vec{x}_p)=0

根据等式8可得，w⃗\vec{w} 与 x⃗o−x⃗p\vec{x}_o-\vec{x}_p 垂直，又由于 xo,xpx_o,x_p 位于决策边界上，所以 w⃗\vec{w} 与决策超平面垂直

回到 2 式，我们可以得

∣x⃗m−x⃗n∣∗cosθ∗∣w⃗∣=2∣x⃗m−x⃗n∣∗cosθ=LL=2∣w⃗∣\left\vert \vec{x}_m-\vec{x}_n \right\vert *cos\theta *\left\vert \vec{w}\right\vert=2\\\left\vert \vec{x}_m-\vec{x}_n \right\vert *cos\theta=L\\L=\frac{2}{\left\vert \vec{w}\right\vert}

要求 LL 的最大值，即求 ∣w⃗∣\left\vert \vec{w}\right\vert 的最小值

SVM处理非线性

  • 最小化：∣∣w∣∣22+C∑i=1Nξi,\frac{||w||^2}{2}+C\sum_{i=1}^N\xi_i,，ξi\xi_i 为松弛变量(Slack Variable)
  • 限制条件：
    • 1. yi[wTx+b]≥1−ξi1.~y_i[w^Tx+b]\ge1-\xi_i，(i=1∼N)(i=1\sim N)
    • 2. ξi≥02.~\xi_i\ge0

其中 C∑i=1NξiC\sum_{i=1}^N\xi_i 为正则项(Regulation Term)，CC 为一个事先设定的参数，即惩罚系数

高维映射

函数 ϕ(x)\phi(x) 满足 xx（低维）→ϕ(x)\rightarrow \phi(x)（高维）

此时，限制条件：yi[wTϕ(x)+b]≥1−ξiy_i[w^T\phi(x)+b]\ge1-\xi_i，(i=1∼N)(i=1\sim N)

那么我们要如何选取这个函数呢，SVM给出的是

  • ϕ(x)\phi(x) 是无限维

我们可以不知道无限维 ϕ(x)\phi(x) 的显式表达式，我们只要知道一个核函数 K(x1,x2)=ϕ(x1)Tϕ(x2)K(x_1,x_2)=\phi(x_1)^T\phi(x_2)，则 1 这个优化式仍然可显

常用核函数
  • RbfRbf (高斯核)：K(x1,x2)=e−∣∣x1−x2∣∣22σ2K(x_1,x_2)=e^{-\frac{||x_1-x_2||^2}{2\sigma^2}}
  • PloyPloy (多项式核)：K(x1,x2)=(x1Tx2+1)dK(x_1,x_2)=({x_1}^Tx_2+1)^d
  • LinearLinear (线性内核)：K(x1,x2)=x1Tx2K(x_1,x_2)={x_1}^Tx_2
  • TanhTanh (Tanh核)：K(x1,x2)=tanh(βx1Tx2+b),tanh=ex−e−xex+e−xK(x_1,x_2)=tanh(\beta{x_1}^Tx_2+b),tanh=\frac{e^x-e^{-x}}{e^x+e^{-x}}
Mercer`s Theorem

K(x1,x2)K(x_1,x_2) 能写成 ϕ(x1)Tϕ(x2)\phi(x_1)^T\phi(x_2) 的充要条件：

  • K(x1,x2)=K(x2,x1)K(x_1,x_2)=K(x_2,x_1)（交换性）
  • ∀ci,xi\forall c_i,x_i，有：（半正定性）
    ∑i=1N∑j=1NcicjK(xi,xj)≥0\sum_{i=1}^N\sum_{j=1}^Nc_ic_jK(x_i,x_j)\ge0

优化理论

原问题(Prime Problem)
  • 最小化：f(w)f(w)
  • 限制条件：
    • gi(w)≤0,(i=1∼K)g_i(w)\le0,(i=1\sim K)
    • hi(w)=0,(i=1∼M)h_i(w)=0,(i=1\sim M)
对偶问题(Dual Problem)
  • 定义：

L(w,α,β)=f(w)+∑i=1Kαigi(w)+∑i=1Mβihi(w)=f(w)+αTg(w)+βTh(w)L(w,\alpha,\beta)=f(w)+\sum_{i=1}^K\alpha_ig_i(w)+\sum_{i=1}^M\beta_ih_i(w)\\=f(w)+\alpha^Tg(w)+\beta^Th(w)

  • 对偶问题定义：

    • 最大化：θ(α,β)=min所有w(L(w,α,β))\theta(\alpha,\beta)=min_{所有w}(L(w,\alpha,\beta))
    • 限制条件：αi≥0,(i=1∼K)\alpha_i\ge0,(i=1\sim K)

  • 定理：如果 w∗w^* 是原问题的解，而 α∗,β∗\alpha^*,\beta^* 是对偶问题的解，则有 f(w∗)≥θ(α∗,β∗)f(w^*)\ge\theta(\alpha^*,\beta^*)

    • 证明：
      θ(α∗,β∗)=min(L(w,α∗,β∗))≤L(w∗,α∗,β∗)=f(w∗)+∑i=1Kαi∗g(w∗)+∑i=1Mβi∗f(w∗)\theta(\alpha^*,\beta^*)=min(L(w,\alpha^*,\beta^*))\le L(w^*,\alpha^*,\beta^*)=f(w^*)+\sum_{i=1}^K\alpha_i^*g(w^*)+\sum_{i=1}^M\beta_i^*f(w^*)
      因为 w∗w^* 满足原问题的限制条件，即 gi(w∗)≤0,hi(w∗)=0g_i(w^*)\le0,h_i(w^*)=0
      同理 αi≥0\alpha_i\ge0
      从而推出 L(w∗,α∗,β∗)≤f(w∗)L(w^*,\alpha^*,\beta^*)\le f(w^*)
      即 θ(α∗,β∗)≤f(w∗)\theta(\alpha^*,\beta^*)\le f(w^*)

定义：G=f(w∗)−θ(α∗,β∗)≥0G=f(w^*)-\theta(\alpha^*,\beta^*)\ge0，GG 叫做原问题与对偶问题的间距(Duality Gap)

对于某些特定的优化问题，可以证明间距 G=0G=0

强对偶定理：若 f(w)f(w) 为凸函数，且 g(w)=Aw+b,h(w)=Cw+dg(w)=Aw+b,h(w)=Cw+d, 则此优化问题的原问题的与对偶问题间距为0，即 f(w∗)=θ(α∗,β∗)f(w^*)=\theta(\alpha^*,\beta^*)

若满足强对偶定理，则对 ∀i=1∼K\forall i=1\sim K(KKT条件)，αi=0\alpha_i=0 或 gi∗(w∗)=0g_i^*(w^*)=0

SVM原问题转化为对偶问题

原问题
  • 最小化：∣∣w∣∣2w+C∑i=1Nξi\frac{||w||^2}{w}+C\sum_{i=1}^N\xi_i
  • 限制条件：
    • yi[wTϕ(xi)+b]≥1−ξiy_i[w^T\phi(x_i)+b]\ge1-\xi_i
    • ξi≥0\xi_i\ge0

为了使其和上面的形式对应，我们可以稍作修改

  • 最小化：∣∣w∣∣2w−C∑i=1Nξi\frac{||w||^2}{w}-C\sum_{i=1}^N\xi_i
  • 限制条件：
    • yi[wTϕ(xi)+b]≥1+ξi⇒1+ξi−yiwTϕ(xi)−yib≤0y_i[w^T\phi(x_i)+b]\ge1+\xi_i\Rightarrow1+\xi_i-y_iw^T\phi(x_i)-y_ib\le0
    • ξi≤0,(i=1∼K)\xi_i\le0,(i=1\sim K)

即将 2K2K 个 gig_i 分为了两部分，没有 hih_i

对偶问题
  • 最大化：θ(α,β)=minw,ξi,b(L(w,ξi,b)=∣∣w∣∣22−C∑i=1Nξi+∑i=1Nβiξi+∑i=1Nαi[1+ξi−yiwTϕ(xi)−yib])\theta(\alpha,\beta)=min_{w,\xi_i,b}(L(w,\xi_i,b)=\frac{||w||^2}{2}-C\sum_{i=1}^N\xi_i+\sum_{i=1}^N\beta_i\xi_i+\sum_{i=1}^N\alpha_i[1+\xi_i-y_iw^T\phi(x_i)-y_ib])
  • 限制条件：
    • α≥0,(i=1∼N)\alpha\ge0,(i=1\sim N)
    • βi≥0\beta_i\ge0

对 LL 求极值，我们可以用拉格朗日乘子法，令 ∂L∂w=0,∂L∂ξi=0,∂L∂b=0\frac{\partial L}{\partial w}=0,\frac{\partial L}{\partial\xi_i}=0,\frac{\partial L}{\partial b}=0 得到

w−∑i=1Nαiyiϕ(xi)=0−C+βi+αi=0−∑i=1Nαiβi=0w-\sum_{i=1}^N\alpha_iy_i\phi(x_i)=0\\-C+\beta_i+\alpha_i=0\\-\sum_{i=1}^N\alpha_i\beta_i=0

先代入第二三个等式

θ(α,β)=min(∣∣w∣∣22+∑i=1Nαi[1−yiwTϕ(xi)−yib])=min(∣∣w∣∣22+∑i=1Nαi[1−yiwTϕ(xi)]\theta(\alpha,\beta)=min(\frac{||w||^2}{2}+\sum_{i=1}^N\alpha_i[1-y_iw^T\phi(x_i)-y_ib])=min(\frac{||w||^2}{2}+\sum_{i=1}^N\alpha_i[1-y_iw^T\phi(x_i)]

12∣∣w∣∣2=12(∑i=1Nαiyiϕ(xi))T(∑j=1Nαiyiϕ(xi))=12∑i=1N∑j=1Nαiαjyiyjϕ(xi)Tϕ(xj)=12∑i=1N∑j=1NαiαjyiyjK(xi,xj)\frac{1}{2}||w||^2=\frac{1}{2}(\sum_{i=1}^N\alpha_iy_i\phi(x_i))^T(\sum_{j=1}^N\alpha_iy_i\phi(x_i))=\frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_j\phi(x_i)^T\phi(x_j)\\=\frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_jK(x_i,x_j)

−∑i=1NαiyiwTϕ(xi)=−∑i=1Nαiyi(∑j=1Nαjyjϕ(xj))ϕ(xi)=−∑i=1N∑j=1Nαiαjyiyjϕ(xj)Tϕ(xi)=−∑i=1N∑j=1NαiαjyiyjK(xi,xj)-\sum_{i=1}^N\alpha_iy_iw^T\phi(x_i)=-\sum_{i=1}^N\alpha_iy_i(\sum_{j=1}^N\alpha_jy_j\phi(x_j))\phi(x_i)\\=-\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_j\phi(x_j)^T\phi(x_i)\\=-\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_jK(x_i,x_j)

  • 最大化：θ(α)=∑i=1Nαi−12∑i=1N∑j=1NαiαjyiyjK(xi,xj)\theta(\alpha)=\sum_{i=1}^N\alpha_i-\frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_jK(x_i,x_j)
  • 限制条件：
    • αi≥0,β≥0,αi+βi=C⇒0≤αi≤C\alpha_i\ge0,\beta\ge0,\alpha_i+\beta_i=C\Rightarrow0\le\alpha_i\le C
    • ∑i=1Nαiyi=0\sum_{i=1}^N\alpha_iy_i=0

可用 SMO 算法求解 α\alpha

测试流程

虽然现在已经转化为了对偶问题，但是我们要求的是 w,bw,b，而 ww 的求法又会引入 ϕ(x)\phi(x)，实际上，对于一个测试样本 XX，我们不需要知道 ww 具体为何值，对于一个样本 xx

  • 若 wTϕ(x)+b≥0w^T\phi(x)+b\ge0，则 y=+1y=+1
  • 若 wTϕ(x)+b≤0w^T\phi(x)+b\le0，则 y=−1y=-1

而 wTϕ(x)=∑i=1N[αiyiϕ(xi)]Tϕ(x)=∑i=1Nαiyiϕ(xi)Tϕ(x)=∑i=1NαiyiK(xi,x)w^T\phi(x)=\sum_{i=1}^N[\alpha_iy_i\phi(x_i)]^T\phi(x)=\sum_{i=1}^N\alpha_iy_i\phi(x_i)^T\phi(x)=\sum_{i=1}^N\alpha_iy_iK(x_i,x)，仍然跟 ϕ(x)\phi(x) 无关

而对于 bb，我们根据 KKT 条件
∀i=1∼N\forall i=1\sim N

  • 要么 βi=0\beta_i=0，要么 ξi=0\xi_i=0
  • 要么 αi=0\alpha_i=0，要么 1+ξi−yiwTϕ(xi)−yib=01+\xi_i-y_iw^T\phi(x_i)-y_ib=0

取 0<αi<C⇒βi=C−αi>00<\alpha_i<C\Rightarrow \beta_i=C-\alpha_i>0

此时 β≠0⇒ξi=0\beta \ne0\Rightarrow \xi_i=0；αi≠0⇒1+ξi−yiwTϕ(xi)−yib=0\alpha_i\ne0\Rightarrow 1+\xi_i-y_iw^T\phi(x_i)-y_ib=0

b=1−yiwTϕ(xi)yi=1−yi∑j=1NαjyjK(xi,xj)yib=\frac{1-y_iw^T\phi(x_i)}{y_i}=\frac{1-y_i\sum_{j=1}^N\alpha_jy_jK(x_i,x_j)}{y_i}

总结

训练流程

  • 输入{(xi,yi)}i=1∼N\{(x_i,y_i)\}_i=1\sim N（解优化问题）
    最大化：θ(α)=∑i=1Nαi−12αiαjyiyjK(xi,xj)\theta(\alpha)=\sum_{i=1}^N\alpha_i-\frac{1}{2}\alpha_i\alpha_jy_iy_jK(x_i,x_j)
    限制条件:
    • 0≤α≤C0\le\alpha\le C
    • ∑i=1Nαiyi=0\sum_{i=1}^N\alpha_iy_i=0
      计算 bb，找一个 0<αi<C0<\alpha_i<C，b=1−yiwTϕ(xi)yi=1−yi∑j=1NαjyjK(xi,xj)yib=\frac{1-y_iw^T\phi(x_i)}{y_i}=\frac{1-y_i\sum_{j=1}^N\alpha_jy_jK(x_i,x_j)}{y_i}

测试流程

  • 输入测试样本 xx
    • 若 ∑i=1NαiyiK(xi,x)+b≥0\sum_{i=1}^N\alpha_iy_iK(x_i,x)+b\ge0，则 y=+1y=+1
    • 若 ∑i=1NαiyiK(xi,x)+b<0\sum_{i=1}^N\alpha_iy_iK(x_i,x)+b<0，则 y=−1y=-1

ROC曲线

  • 混淆矩阵

  • 四个概率的TP，FP，TN，FN的关系
    1. TP+FN=1
    2. FP+TN=1
    3. 对于同一个系统来说，若TP增加，则FP也增加

ROC曲线

  • 等错误率(Equal Error Rate,EER)是两类错误FP和FN相等时的错误率，可以直观的表示系统性能

支持向量机的应用

兵王问题

  • 国际象棋中黑方只剩一个王，白方剩一个兵一个王
  • 两种可能：
    • 白方将死黑方，获胜
    • 和棋

用SVM解兵王问题

样本解释

  • draw：双方棋子在这个位置上，双方平局
  • six：双方棋子在这个位置上，在方都不犯错的情况下，六步后黑方被白方将死
  • fifteen：双方棋子在这个位置上，在方都不犯错的情况下，十五步后黑方被白方将死

求解过程

  • 总样本数 28056，其中正样本 2796，负样本 25260

  • 随机取 5000 个样本训练，其余测试

  • 样本归一化，在训练样本上，求出每个维度的均值和方差，在训练和测试样本上同时归一化

    newX=X−mean(Xstd(X)newX=\frac{X-mean(X}{std(X)}

  • 高斯核

    • 5−foldcrossvalidation5-fold cross validation，在 CScale=[2−5,215];gamma=[2−15,23];CScale=[2^{-5},2^{15}];gamma=[2^{-15},2^3];上遍历求识别率的最大值
训练所用工具包

数据处理

  • 由于数据集中给出来的坐标包含字母，机器无法识别，所以我们需要将其转化为数字
  • 对于 draw 我们将其赋值 +1，其他的则为 -1
  • 将数据集的 20%20\% 用于训练，剩下的用于测试
  • 在训练样本上求出每个维度的均值和标准差，在训练和测试样本上同时归一化
import numpy as np
import pandas as pd
from sklearn.model_selection import train_test_split
from sklearn.preprocessing import StandardScaler

def replace_letters_with_numbers(input_file):
    # 定义映射表，将a-h映射到1-8
    mapping = {'a': '1', 'b': '2', 'c': '3', 'd': '4', 
               'e': '5', 'f': '6', 'g': '7', 'h': '8'}
    
    # 打开输入文件进行读取
    with open(input_file, 'r') as infile:
        lines = infile.readlines()
    
    # 存储结果行
    result = []
    
    # 对每一行进行处理
    for line in lines:
        # 移除换行符并按逗号分割字段
        fields = line.strip().split(',')
        
        # 对最后一个字段之前的字段进行字母替换
        for i in range(len(fields) - 1):
            for letter, number in mapping.items():
                fields[i] = fields[i].replace(letter, number)
        
        # 检查最后一个字段是否为 'draw'，并根据条件进行替换
        if fields[-1].strip().lower() == 'draw':
            fields[-1] = '1'
        else:
            fields[-1] = '-1'
        
        # 将处理后的行拼接回字符串
        result.append(','.join(fields))
    
    # 将处理后的数据转化为pandas DataFrame
    processed_data = [line.split(',') for line in result]
    df = pd.DataFrame(processed_data, dtype=np.float32)  # 转为浮点型，方便后续归一化操作
    
    return df

def process_and_split_data(df):
    # 划分特征和目标
    X = df.iloc[:, :-1]  # 前n-1列为特征
    y = df.iloc[:, -1]   # 最后一列为目标

    # 划分训练集和测试集，测试集占比80%
    X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.8, random_state=42)

    # 创建MinMaxScaler对象
    scaler = StandardScaler()

    # 对训练数据进行归一化
    X_train_scaled = scaler.fit_transform(X_train)

    # 对测试数据进行归一化
    X_test_scaled = scaler.transform(X_test)

    # 返回处理后的数据
    return X_train_scaled, X_test_scaled, y_train, y_test

# 运行流程
input_file = 'krkopt.data'  

# 替换字母并转换为数字
df = replace_letters_with_numbers(input_file)

# 划分数据集并进行归一化
X_train_scaled, X_test_scaled, y_train, y_test = process_and_split_data(df)

train_data_scaled = pd.DataFrame(X_train_scaled)
test_data_scaled = pd.DataFrame(X_test_scaled)

train_data_scaled.to_csv('train_scaled.csv', index=False)
test_data_scaled.to_csv('test_scaled.csv', index=False)

训练模型及参数设置

  • 常用的 LibSVM 参数

    1. -s : SVM 类型 这个参数定义了你要使用的 SVM 类型。LibSVM 支持多种不同类型的 SVM，可以处理分类、回归以及分布估计问题。

      常用的 -s 参数值：

      • 0：C-SVC（分类任务的标准C-SVM）
      • 1：ν-SVC（分类任务的另一种形式，使用 ν 来控制支持向量）
      • 2：ε-SVR（回归任务，支持向量回归）
      • 3：ν-SVR（回归任务的另一种形式）
      • 4：一类 SVM（用于分布估计或异常检测）

      示例：-s 0 表示使用 C-SVC 类型的 SVM（最常见的分类SVM）。

    2. -t : 核函数类型 核函数将输入特征映射到更高维度的空间，以解决线性不可分问题。不同的核函数可以适应不同的数据分布。

      常用的 -t 参数值：

      • 0：线性核（Linear Kernel）
      • 1：多项式核（Polynomial Kernel）
      • 2：径向基核（RBF Kernel, Radial Basis Function）
      • 3：Sigmoid 核

      示例：-t 2 表示使用 RBF 核函数（最常用的核函数之一）。

    3. -c : 惩罚系数 C C 是 SVM 的惩罚参数，用于控制模型的复杂度与错误分类的平衡。C 值越大，模型越倾向于拟合训练数据，惩罚错误分类的程度越高；C 值越小，模型越宽松，容忍更多的错误分类。

      • C 值较大：模型复杂度较高，容易过拟合。
      • C 值较小：模型复杂度较低，容易欠拟合。

      示例：-c 1 表示惩罚系数为 1（这是默认值）。

    4. -g : γ（Gamma）参数 γ 是 RBF 核、多项式核和 Sigmoid 核中的一个重要参数，决定了单个训练样本的影响范围。Gamma 值越大，训练样本的影响范围越小，模型越复杂；Gamma 值越小，训练样本的影响范围越大，模型越简单。

      • 适用于核函数 -t 1（多项式核）、-t 2（RBF 核）、-t 3（Sigmoid 核）。
      • Gamma 是控制非线性映射的超参数，较小的值可能导致欠拟合，而较大的值则可能导致过拟合。

      示例：-g 0.1 表示 Gamma 参数为 0.1。

    5. -d : 多项式核的度 这个参数是多项式核的专用参数，它决定了多项式核的阶数。它仅在使用 -t 1（多项式核）时有效。

      示例：-d 3 表示使用三次多项式核。

    6. -r : 多项式核的系数 当使用多项式核（-t 1）时，-r 参数用于控制核函数中的偏置项。

      示例：-r 1 表示多项式核函数中的偏置系数为 1。

    7. -n : ν 参数 这个参数在 ν-SVC、ν-SVR 和一类 SVM 中使用，它控制模型中的支持向量个数。值域在 (0, 1) 之间。

      • 在 ν-SVC 中，ν 代表支持向量所占的比例。
      • 在 ν-SVR 中，ν 是控制容忍误差的参数。

      示例：-n 0.5 表示使用 0.5 作为 ν 值。

    8. -p : ε 参数（ε-SVR） 这个参数用于回归问题中的 ε-SVR。它控制模型对目标值误差的容忍度，即如果预测值和实际值之间的差距小于 ε，误差将被忽略。

      示例：-p 0.1 表示 ε 为 0.1。

    9. -h : 启用/禁用启发式收敛 -h 参数用于加速训练过程，默认为 1，表示启用启发式收敛。启发式收敛能够在大多数情况下加速模型的训练，但有时也可能影响模型的最终准确性。

      • -h 0：禁用启发式收敛。
      • -h 1：启用启发式收敛。

      示例：-h 0 表示禁用启发式收敛。

    10. -b : 是否输出概率估计 默认情况下，LibSVM 只输出分类决策值。如果你希望输出概率估计，可以设置 -b 1。

      示例：-b 1 表示启用概率估计（SVM 支持二分类和多分类的概率估计）。

    11. -m : 内存限制（MB） 用于设置最大训练过程中使用的内存量，默认值是 100MB。对于非常大的数据集，内存可能会成为瓶颈，因此可以通过调整这个参数限制内存的使用。

      示例：-m 200 表示允许最大内存为 200MB。

    12. -v : 交叉验证 -v 参数用于设置 k-fold 交叉验证的 k 值。如果设置该参数，LibSVM 将执行 k 折交叉验证，并输出交叉验证的结果，而不是训练一个最终模型。

      示例：-v 5 表示执行 5 折交叉验证。

    13. -w : 类别权重 在类别不平衡问题中，LibSVM 提供了权重调整。-w 参数可以为每个类别指定不同的权重，使得模型在处理不平衡数据时更倾向于少数类。权重的格式是 -wlabel=value，其中 label 是类标签，value 是权重值。

      示例：-w1 1 -w-1 5 表示将正类（1）的权重设置为 1，负类（-1）的权重设置为 5。

训练代码

def TrainModelSVM(data, label, iter, model_file):
    '''
    data: 数据
    label: 标签
    iter: 训练次数
    model_file: 模型的保存位置
    '''
    
    # 将数据转换成list型的数据。因为在svm的函数中好像只能传入list型的数据进行训练使用
    X = data.tolist()
    Y = label.tolist()
    
    CScale = [-5, -3, -1, 1, 3, 5, 7, 9, 11, 13, 15]     # 参数C的取值为2^C
    gammaScale = [-15, -13, -11, -9, -7, -5, -3, -1, 1, 3]   # 参数γ的取值为2^γ
    cnt = iter
    step = 2  # 用于重新生成CScale和gammaScale序列
    maxACC = 0         # 训练过程中的最大正确率
    bestACC_C = 0      # 训练过程中的最优参数C
    bestACC_gamma = 0  # 训练过程中的最优参数γ
    prob = svm_problem(Y, X)  # 传入数据
    
    while(cnt):
        # 用传入的参数序列进行训练，返回的是此次训练的最高正确率、最优参数C、最优参数γ
        maxACC_train, maxACC_C_train, maxACC_gamma_train = TrainModel(CScale, gammaScale, prob)   # prob为训练集合对应的标签
        # 数据更新
        if(maxACC_train > maxACC):
            maxACC = maxACC_train
            bestACC_C = maxACC_C_train
            bestACC_gamma = maxACC_gamma_train
            
        # 根据返回的参数重新生成CScale序列和gammaScale序列用于再次训练，下一次训练的C参数和γ参数的精度会比之前更高
        # step就是CScale序列和gammaScale序列相邻两个数之间的间隔
        new_step = step*2/10
        CScale = getNewList(maxACC_C_train - step, maxACC_C_train + step + new_step, new_step)
        gammaScale = getNewList(maxACC_gamma_train - step, maxACC_gamma_train + step + new_step, new_step)
        cnt -= 1
        
    # 获得最优参数后计算出对应的C和γ，并且训练获得最优模型
    C = pow(2, bestACC_C)
    gamma = pow(2, bestACC_gamma)
    param = svm_parameter('-t 2 -c ' + str(C) + ' -g ' + str(gamma))
    model = svm_train(prob, param)    # 准确率
    svm_save_model(model_file, model) # 保存模型
    return model

CScale：参数 C 的初始搜索范围。C 是 SVM 的惩罚系数，用来控制模型对误分类的容忍度，值越大表示模型越不容忍误分类，越容易过拟合。C 的值是 2 的指数形式

  • CScale = [-5, -3, -1, 1, 3, 5, 7, 9, 11, 13, 15]，表示 C 参数会取值 2^-5, 2^-3, … 2^15。

gammaScale：参数 γ 的初始搜索范围，γ 是 RBF 核中的参数，用来控制单个训练样本的影响范围。γ 的值也是 2 的指数形式。

  • gammaScale = [-15, -13, -11, -9, -7, -5, -3, -1, 1, 3]，表示 γ 参数会取值 2^-15, 2^-13, … 2^3
迭代搜索

在每次迭代中，函数会通过 TrainModel(CScale, gammaScale, prob) 对当前的 C 和 γ 参数组合进行训练，找到当前迭代中的最佳参数组合和最高的准确率。

  • 精度调整：在每次找到当前最优参数后，函数会通过 getNewList 函数根据当前最优的 C 和 γ 生成新的搜索范围，缩小步长以精细搜索最佳参数。step 是调整搜索范围的关键，new_step 是通过减少步长进行更精确的搜索。

完整代码

import numpy as np
import pandas as pd
from sklearn.model_selection import train_test_split
from sklearn.preprocessing import StandardScaler
from libsvm.svmutil import *
from sklearn.metrics import roc_curve, auc

def replace_letters_with_numbers(input_file):
    # 定义映射表，将a-h映射到1-8
    mapping = {'a': '1', 'b': '2', 'c': '3', 'd': '4', 
               'e': '5', 'f': '6', 'g': '7', 'h': '8'}
    
    # 打开输入文件进行读取
    with open(input_file, 'r') as infile:
        lines = infile.readlines()
    
    # 存储结果行
    result = []
    
    # 对每一行进行处理
    for line in lines:
        # 移除换行符并按逗号分割字段
        fields = line.strip().split(',')
        
        # 对最后一个字段之前的字段进行字母替换
        for i in range(len(fields) - 1):
            for letter, number in mapping.items():
                fields[i] = fields[i].replace(letter, number)
        
        # 检查最后一个字段是否为 'draw'，并根据条件进行替换
        if fields[-1].strip().lower() == 'draw':
            fields[-1] = '1'
        else:
            fields[-1] = '-1'
        
        # 将处理后的行拼接回字符串
        result.append(','.join(fields))
    
    # 将处理后的数据转化为pandas DataFrame
    processed_data = [line.split(',') for line in result]
    df = pd.DataFrame(processed_data, dtype=np.float32)  # 转为浮点型，方便后续归一化操作
    
    return df

def process_and_split_data(df):
    # 划分特征和目标
    X = df.iloc[:, :-1]  # 前n-1列为特征
    y = df.iloc[:, -1]   # 最后一列为目标

    # 划分训练集和测试集，测试集占比80%
    X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.8, random_state=42)

    # 创建MinMaxScaler对象
    scaler = StandardScaler()

    # 对训练数据进行归一化
    X_train_scaled = scaler.fit_transform(X_train)

    # 对测试数据进行归一化
    X_test_scaled = scaler.transform(X_test)

    # 返回处理后的数据
    return X_train_scaled, X_test_scaled, y_train, y_test


def TrainModel(CScale, gammaScale, prob):
    '''
    CScale: 参数C的取值序列
    gammaScale: 参数γ的取值序列
    prob: 训练集合对应的标签
    '''
    maxACC = 0             # 最高正确率
    maxACC_C = 0           # 最优参数C
    maxACC_gamma = 0       # 最优参数γ
 
    # 嵌套循环
    for C in CScale:
        C_ = pow(2, C)  # 2的C次方
        for gamma in gammaScale:
            gamma_ = pow(2, gamma)  # 2的gamma次方
            
            # 设置训练的参数，其中-q表示静默模式，不输出训练过程信息
            param = svm_parameter('-t 2 -c ' + str(C_) + ' -g ' + str(gamma_) + ' -v 5 -q')
            ACC = svm_train(prob, param)  # 进行训练，但是传回的不是训练模型而是5折交叉验证的准确率
            
            # 更新数据
            if (ACC > maxACC):
                maxACC = ACC
                maxACC_C = C
                maxACC_gamma = gamma
                
    return maxACC, maxACC_C, maxACC_gamma

def getNewList(L, U, step):   
    l = []
    while(L < U):
        l.append(L)
        L += step
    return l

def TrainModelSVM(data, label, iter, model_file):
    
    # 将数据转换成list型的数据。因为在svm的函数中好像只能传入list型的数据进行训练使用
    X = data.tolist()
    Y = label.tolist()
    
    CScale = [-5, -3, -1, 1, 3, 5, 7, 9, 11, 13, 15]     # 参数C的取值为2^C
    gammaScale = [-15, -13, -11, -9, -7, -5, -3, -1, 1, 3]   # 参数γ的取值为2^γ
    cnt = iter
    step = 2  # 用于重新生成CScale和gammaScale序列
    maxACC = 0         # 训练过程中的最大正确率
    bestACC_C = 0      # 训练过程中的最优参数C
    bestACC_gamma = 0  # 训练过程中的最优参数γ
    prob = svm_problem(Y, X)  # 传入数据
    
    while(cnt):
        # 用传入的参数序列进行训练，返回的是此次训练的最高正确率、最优参数C、最优参数γ
        maxACC_train, maxACC_C_train, maxACC_gamma_train = TrainModel(CScale, gammaScale, prob)   # prob为训练集合对应的标签
        # 数据更新
        if(maxACC_train > maxACC):
            maxACC = maxACC_train
            bestACC_C = maxACC_C_train
            bestACC_gamma = maxACC_gamma_train
            
        # 根据返回的参数重新生成CScale序列和gammaScale序列用于再次训练，下一次训练的C参数和γ参数的精度会比之前更高
        # step就是CScale序列和gammaScale序列相邻两个数之间的间隔
        new_step = step*2/10
        CScale = getNewList(maxACC_C_train - step, maxACC_C_train + step + new_step, new_step)
        gammaScale = getNewList(maxACC_gamma_train - step, maxACC_gamma_train + step + new_step, new_step)
        cnt -= 1
        
    # 获得最优参数后计算出对应的C和γ，并且训练获得最优模型
    C = pow(2, bestACC_C)
    gamma = pow(2, bestACC_gamma)
    param = svm_parameter('-t 2 -c ' + str(C) + ' -g ' + str(gamma))
    model = svm_train(prob, param)    # 准确率
    svm_save_model(model_file, model) # 保存模型
    return model

def main():
    mode_file = r"C:\Users\24843\Desktop\python\model.file"   # 训练模型保存的位置
    
    # 运行流程
    input_file = 'krkopt_raw.data'  

    # 替换字母并转换为数字
    df = replace_letters_with_numbers(input_file)

    # 划分数据集并进行归一化
    X_train_scaled, X_test_scaled, y_train, y_test = process_and_split_data(df)

    iter = 2

    if (input("是否需要进行训练？") == 'y'):  # 如果输入y就会进行训练，否则就可以直接使用之前训练完成的模型
        model = TrainModelSVM(X_train_scaled, y_train, iter, mode_file)  # 传入输入数据、标签进行模型的训练
    else:
        model = svm_load_model(mode_file)  # 直接加载现有模型
        
    X = X_test_scaled.tolist()  # 将测试集的坐标转换成list
    Y = y_test.tolist()  # 将测试集的标签转换成list
    # print(Y[:])
    p_labs, p_acc, p_vals = svm_predict(Y, X, model)   # 依次返回：预测的标签、预测的准确率、预测的概率估计值
    fpr, tpr, threshold = roc_curve(y_test, p_labs)  # 计算真正率tpr和假正率fpr
    roc_auc = auc(fpr, tpr)  # 计算auc的值，auc就是曲线包围的面积，越大越好
    print(roc_auc)

if __name__ == "__main__":
    main()