数据挖掘与分析课程笔记（Chapter 21）

数据挖掘与分析课程笔记

• 参考教材：Data Mining and Analysis : MOHAMMED J.ZAKI, WAGNER MEIRA JR.

文章目录

0. 数据挖掘与分析课程笔记（目录）
1. 数据挖掘与分析课程笔记（Chapter 1）
2. 数据挖掘与分析课程笔记（Chapter 2）
3. 数据挖掘与分析课程笔记（Chapter 5）
4. 数据挖掘与分析课程笔记（Chapter 7）
5. 数据挖掘与分析课程笔记（Chapter 14）
6. 数据挖掘与分析课程笔记（Chapter 15）
7. 数据挖掘与分析课程笔记（Chapter 20）
8. 数据挖掘与分析课程笔记（Chapter 21）

---

---

Chapter 21: Support Vector Machines (SVM)

21.1 支撑向量与余量

Set up： D = { ( x i , y i ) } i = 1 n , x i ∈ R d , y i ∈ { − 1 , 1 } \mathbf{D}=\{(\mathbf{x}_i,y_i) \}_{i=1}^n,\mathbf{x}_i \in \mathbb{R}^d,y_i \in \{-1,1 \} D={(xi​,yi​)}i=1n​,xi​∈Rd,yi​∈{−1,1}，仅两类数据。

• 超平面 (hyperplanes，$d-1$ 维)：$h(\mathbf{x}):={\mathbf{w}}^T\mathbf{x}+b=w_1{x}_1+\cdots +w_d{x}_d+b$

  其中，$\mathbf{w}$ 是法向量，$-\frac{b}{w_i}$ 是 $x_i$ 轴上的截距。

• $\mathbf{D}$ 称为是线性可分的，如果存在 $h(\mathbf{x})$ 使得对所有 $y_i=1$ 的点 ${\mathbf{x}}_i$ 有 $h({\mathbf{x}}_i)>0$ ，且对所有 $y_i=-1$ 的点 ${\mathbf{x}}_i$ 有 $h({\mathbf{x}}_i)<0$ ，并将此 $h(\mathbf{x})$ 称为分离超平面。

  Remark：对于线性可分的 $\mathbf{D}$ ，分离超平面有无穷多个。

• 点到超平面的距离：
  x = x p + x r = x p + r ⋅ w ∣ ∣ w ∣ ∣ h ( x ) = h ( x p + r w ∥ w ∥ ) = w T ( x p + r w ∥ w ∥ ) + b = w T x p + b ⏟ h ( x p ) + r w T w ∥ w ∥ = h ( x p ) ⏟ 0 + r ∥ w ∥ = r ∥ w ∥ \mathbf{x}=\mathbf{x}_p+\mathbf{x}_r=\mathbf{x}_p+r\cdot\frac{\mathbf{w}}{||\mathbf{w}||}\\

  h(x)=h(xp+rw‖w‖)=wT(xp+rw‖w‖)+b=wTxp+b⏟h(xp)+rwTw‖w‖=h(xp)⏟0+r‖w‖=r‖w‖" role="presentation">h(x)=h(xp+rw∥w∥)=wT(xp+rw∥w∥)+b=wTxp+bh(xp)+rwTw∥w∥=h(xp)0+r∥w∥=r∥w∥$$\begin{array}{rl}h(\mathbf{x})& =h\left({\mathbf{x}}_p+r\frac{\mathbf{w}}{\Vert \mathbf{w}\Vert }\right)\\ & ={\mathbf{w}}^T\left({\mathbf{x}}_p+r\frac{\mathbf{w}}{\Vert \mathbf{w}\Vert }\right)+b\\ & =\underset{h\left({\mathbf{x}}_p\right)}{\underbrace{{\mathbf{w}}^T{\mathbf{x}}_p+b}}+r\frac{{\mathbf{w}}^T\mathbf{w}}{\Vert \mathbf{w}\Vert }\\ & =\underset{0}{\underbrace{h\left({\mathbf{x}}_p\right)}}+r\Vert \mathbf{w}\Vert \\ & =r\Vert \mathbf{w}\Vert \end{array}$$
  x=xp​+xr​=xp​+r⋅∣∣w∣∣w​h(x)​=h(xp​+r∥w∥w​)=wT(xp​+r∥w∥w​)+b=h(xp​) wTxp​+b​​+r∥w∥wTw​=0 h(xp​)​​+r∥w∥=r∥w∥​

  $\therefore r=\frac{h(\mathbf{x})}{\Vert \mathbf{w}\Vert },|r|=\frac{|h(\mathbf{x}|)}{\Vert \mathbf{w}\Vert }$

故 $\forall {\mathbf{x}}_i\in \mathbf{D}$ 到 $h(\mathbf{x})$ 的距离是 $y_i\frac{h({\mathbf{x}}_i)}{\Vert \mathbf{w}\Vert }$

• 给定线性可分的 $\mathbf{D}$ ，及分离超平面 $h(\mathbf{x})$ ，定义余量：
  δ ∗ = min ⁡ x i { y i ( w T x i + b ) ∥ w ∥ } \delta^*=\min\limits_{\mathbf{x}_i}\{\frac{y_i(\mathbf{w}^T\mathbf{x}_i+b)}{\|\mathbf{w}\|} \} δ∗=xi​min​{∥w∥yi​(wTxi​+b)​}
  即 $\mathbf{D}$ 中点到 $h(\mathbf{x})$ 距离的最小值，使得该 ${\delta }^{\ast }$ 取到的数据点 ${\mathbf{x}}_i$ 被称为支撑向量（可能不唯一）。

• 标准超平面：对 $\forall h(\mathbf{x})={\mathbf{w}}^T\mathbf{x}+b$，以及任意 s ∈ R ∖ { 0 } s\in \mathbb{R}\setminus \{0\} s∈R∖{0}，$s({\mathbf{w}}^T\mathbf{x}+b)=0$ 与 $h(\mathbf{x})=0$ 是同一超平面。

  设 ${\mathbf{x}}^{\ast }$ 是支撑向量，若 $s{y}^{\ast }({\mathbf{w}}^T{\mathbf{x}}^{\ast }+b)=1(1)$ ，则称 $sh(\mathbf{x})=0$ 是标准超平面。

  由 $(1)$ 可得：$s=\frac{1}{y^{\ast }({\mathbf{w}}^T{\mathbf{x}}^{\ast }+b)}=\frac{1}{y^{\ast }h({\mathbf{x}}^{\ast })}$

  此时，对于 $sh(\mathbf{x})=0$ ，余量 ${\delta }^{\ast }=\frac{y^{\ast }h({\mathbf{x}}^{\ast })}{\Vert \mathbf{w}\Vert }=\frac{1}{\Vert \mathbf{w}\Vert }$

事实：如果 ${\mathbf{w}}^T\mathbf{x}+b=0$ 是标准超平面，对 $\forall {\mathbf{x}}_i$ ，一定有 $y_i({\mathbf{w}}^T{\mathbf{x}}_i+b)\ge 1$

21.2 SVM: 线性可分情形

目标：寻找标准分离超平面使得其余量最大，即 h ∗ = arg ⁡ max ⁡ w , b { 1 w } h^*=\arg\max\limits_{\mathbf{w},b}\{\frac{1}{\mathbf{w}} \} h∗=argw,bmax​{w1​}

转为优化问题：
min ⁡ w , b   { ∥ w ∥ 2 2 } s.t.  y i ( w T x i + b ) ≥ 1 , ∀ ( x i , y i ) ∈ D

​w,bmin​ {2∥w∥2​}s.t. yi​(wTxi​+b)≥1,∀(xi​,yi​)∈D​
引入 Lagrange 乘子 ${\alpha }_i\ge 0$ 与 KKT 条件：
$${\alpha }_i(y_i({\mathbf{w}}^T{\mathbf{x}}_i+b)-1)=0$$
定义：
$$L(\mathbf{w})=\frac{1}{2}\Vert \mathbf{w}{\Vert }^2-\sum _{i=1}^n{\alpha }_i(y_i({\mathbf{w}}^T{\mathbf{x}}_i+b)-1)(2)$$

∂ ∂ w L = w − ∑ i = 1 n α i y i x i = 0   ( 3 ) ∂ ∂ b L = ∑ i = 1 n α i y i = 0   ( 4 )

∂w∂​L=w−i=1∑n​αi​yi​xi​=0 (3)∂b∂​L=i=1∑n​αi​yi​=0 (4)​

将 (3)(4) 代入 (2) 得：
L d u a l = 1 2 w T w − w T ( ∑ i = 1 n α i y i x i ⏟ w ) − b ∑ i = 1 n α i y i ⏟ 0 + ∑ i = 1 n α i = − 1 2 w T w + ∑ i = 1 n α i = ∑ i = 1 n α i − 1 2 ∑ i = 1 n ∑ j = 1 n α i α j y i y j x i T x j

Ldual​​=21​wTw−wT(w i=1∑n​αi​yi​xi​​​)−b0 i=1∑n​αi​yi​​​+i=1∑n​αi​=−21​wTw+i=1∑n​αi​=i=1∑n​αi​−21​i=1∑n​j=1∑n​αi​αj​yi​yj​xiT​xj​​
故对偶问题为：
max ⁡ α L d u a l = ∑ i = 1 n α i − 1 2 ∑ i = 1 n ∑ j = 1 n α i α j y i y j x i T x j s.t.  ∑ i = 1 n α i y i = 0 , α i ≥ 0 , ∀ i

maxαLdual=∑i=1nαi−12∑i=1n∑j=1nαiαjyiyjxiTxjs.t. ∑i=1nαiyi=0,αi≥0,∀i" role="presentation">maxαLdual=∑i=1nαi−12∑i=1n∑j=1nαiαjyiyjxTixjs.t. ∑i=1nαiyi=0,αi≥0,∀i$$\begin{array}{rl}& \underset{\alpha }{max}{L}_{dual}=\sum _{i=1}^n{\alpha }_i-\frac{1}{2}\sum _{i=1}^n\sum _{j=1}^n{\alpha }_i{\alpha }_j{y}_i{y}_j{\mathbf{x}}_i^T{\mathbf{x}}_j\\ & \text{s.t.}\sum _{i=1}^n{\alpha }_i{y}_i=0,{\alpha }_i\ge 0,\mathrm{\forall }i\end{array}$$

​αmax​Ldual​=i=1∑n​αi​−21​i=1∑n​j=1∑n​αi​αj​yi​yj​xiT​xj​s.t. i=1∑n​αi​yi​=0,αi​≥0,∀i​
利用二次规划解出 Dual：${\alpha }_1,\cdots ,{\alpha }_n$

代入 (3) 可得：$\mathbf{w}=\sum _{i=1}^n{\alpha }_i{y}_i{\mathbf{x}}_i$

使得 ${\alpha }_i>0$ 的数据 ${\mathbf{x}}_i$ 给出支撑向量。

对于每一个支撑向量：$y_i({\mathbf{w}}^T{\mathbf{x}}_i+b)-1\Rightarrow b=\frac{1}{y_i}-{\mathbf{w}}^T{\mathbf{x}}_i$

取 b = a v g α i > 0 { b i } b=\mathop{avg}_{\alpha_i>0}\{b_i\} b=avgαi​>0​{bi​}

---