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

数据挖掘与分析课程笔记

• 参考教材：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 5 Kernel Method：核方法

Example 5.1 略，$\varphi (核映射):{\Sigma }^{\ast }(输入空间)\to {\mathbb{R}}^4(特征空间)$

Def.1. 假设核映射 $\varphi :\mathcal{I}\to \mathcal{F}$，$\varphi$ 的核函数是指 $K:\mathcal{I}\times \mathcal{I}\to \mathbb{R}$ 使得 $\forall ({\mathbf{x}}_i,{\mathbf{x}}_j)\in \mathcal{I}\times \mathcal{I},K({\mathbf{x}}_i,{\mathbf{x}}_j)={\varphi }^T({\mathbf{x}}_i)\varphi ({\mathbf{x}}_j)$

Example 5.2 设 $\varphi :{\mathbb{R}}^2\to {\mathbb{R}}^3$ 使得 $\forall \mathbf{a}=(a_1，a_2),\varphi (\mathbf{a})=(a_1^2,a_2^2,\sqrt{2}{a}_1{a}_2{)}^T$

注意到 $K(\mathbf{a},\mathbf{b})=\varphi (\mathbf{a}{)}^T\varphi (\mathbf{b})=a_1^2{b}_1^2+a_2^2{b}_2^2+2a_1^2{a}_2^2{b}_1^2{b}_2^2$，$K:{\mathbb{R}}^2\times {\mathbb{R}}^2\to \mathbb{R}$

Remark：

1. 分析复杂数据
2. 分析非线性特征（知乎搜核函数有什么作用）

Goal：在未知 $\varphi$ 的情况下，通过分析 $K$ 来分析特征空间 $\mathcal{F}$ 结果。

5.1 核矩阵

设 D = { x 1 , x 2 , … , x n } ⊂ I \mathbf{D}=\left\{\mathbf{x}_{1}, \mathbf{x}_{2}, \ldots, \mathbf{x}_{n}\right\} \subset \mathcal{I} D={x1​,x2​,…,xn​}⊂I，其核矩阵定义为：$\mathbf{K}=[K({\mathbf{x}}_i,{\mathbf{x}}_j){]}_{n\times n}$

Prop. 核矩阵 $\mathbf{K}$ 是对称的且半正定的

Proof. $K({\mathbf{x}}_i,{\mathbf{x}}_j)={\varphi }^T({\mathbf{x}}_i)\varphi ({\mathbf{x}}_j)={\varphi }^T({\mathbf{x}}_j)\varphi ({\mathbf{x}}_i)=K({\mathbf{x}}_j,{\mathbf{x}}_i)$，故对称。

对于 $\forall {\mathbf{a}}^T\in {\mathbb{R}}^n$，
a T K a = ∑ i = 1 n ∑ j = 1 n a i a j K ( x i , x j ) = ∑ i = 1 n ∑ j = 1 n a i a j ϕ ( x i ) T ϕ ( x j ) = ( ∑ i = 1 n a i ϕ ( x i ) ) T ( ∑ j = 1 n a j ϕ ( x j ) ) = ∥ ∑ i = 1 n a i ϕ ( x i ) ∥ 2 ≥ 0

aTKa​=i=1∑n​j=1∑n​ai​aj​K(xi​,xj​)=i=1∑n​j=1∑n​ai​aj​ϕ(xi​)Tϕ(xj​)=(i=1∑n​ai​ϕ(xi​))T(j=1∑n​aj​ϕ(xj​))=∥ ∥​i=1∑n​ai​ϕ(xi​)∥ ∥​2≥0​

5.1.1 核映射的重构

”经验核映射“

已知 D = { x i } i = 1 n ⊂ I \mathbf{D}=\left\{\mathbf{x}_{i}\right\}_{i=1}^{n} \subset \mathcal{I} D={xi​}i=1n​⊂I 与核矩阵 $\mathbf{K}$

目标：寻找 $\varphi :\mathcal{I}\to \mathcal{F}\subset {\mathbb{R}}^n$

首先尝试：$\forall \mathbf{x}\in \mathcal{I},\varphi (\mathbf{x})={\left(K\left({\mathbf{x}}_1,\mathbf{x}\right),K\left({\mathbf{x}}_2,\mathbf{x}\right),\dots ,K\left({\mathbf{x}}_n,\mathbf{x}\right)\right)}^T\in {\mathbb{R}}^n$

检查：${\varphi }^T({\mathbf{x}}_i)\varphi ({\mathbf{x}}_j)?=K({\mathbf{x}}_i,{\mathbf{x}}_j)$

左边 $=\varphi {\left({\mathbf{x}}_i\right)}^T\varphi \left({\mathbf{x}}_j\right)=\sum _{k=1}^{n}K\left({\mathbf{x}}_k,{\mathbf{x}}_i\right)K\left({\mathbf{x}}_k,{\mathbf{x}}_j\right)={\mathbf{K}}_i^T{\mathbf{K}}_j$，${\mathbf{K}}_i$ 代表第 $i$ 行或列要求太高。

考虑改进：寻找矩阵 $\mathbf{A}$ 使得，${\mathbf{K}}_i^T\mathbf{A}{\mathbf{K}}_j=\mathbf{K}\left({\mathbf{x}}_i,{\mathbf{x}}_j\right)$，即 ${\mathbf{K}}^T\mathbf{AK}=\mathbf{K}$

故只需取 $\mathbf{A}={\mathbf{K}}^{-1}$ 即可（ $\mathbf{K}$ 可逆）

若 $\mathbf{K}$ 正定，${\mathbf{K}}^{-1}$ 也正定，即存在一个实矩阵 $\mathbf{B}$ 满足 ${\mathbf{K}}^{-1}={\mathbf{B}}^T\mathbf{B}$

故经验核函数可定义为：
$$\varphi (\mathbf{x})=\mathbf{B}\cdot {\left(K\left({\mathbf{x}}_1,\mathbf{x}\right),K\left({\mathbf{x}}_2,\mathbf{x}\right),\dots ,K\left({\mathbf{x}}_n,\mathbf{x}\right)\right)}^T$$
检查：${\varphi }^T({\mathbf{x}}_i)\varphi ({\mathbf{x}}_j)=(\mathbf{B}{\mathbf{K}}_i{)}^T(\mathbf{B}{\mathbf{K}}_j)={\mathbf{K}}_i^T{\mathbf{K}}^{-1}{\mathbf{K}}_j=({\mathbf{K}}^T{\mathbf{K}}^{-1}\mathbf{K}{)}_{i,j}=K({\mathbf{x}}_i,{\mathbf{x}}_j)$

5.1.2 特定数据的海塞核映射

对于对称半正定矩阵 ${\mathbf{K}}_{n\times n}$，存在分解
K = U ( λ 1 0 ⋯ 0 0 λ 2 ⋯ 0 ⋮ ⋮ ⋱ ⋮ 0 0 ⋯ λ n ) U T = U Λ U T \mathbf{K}=\mathbf{U}\left(

\right)\mathbf{U}^{T}=\mathbf{U}\boldsymbol{\Lambda}\mathbf{U}^{T} K=U⎝ ⎛​λ1​0⋮0​0λ2​⋮0​⋯⋯⋱⋯​00⋮λn​​⎠ ⎞​UT=UΛUT
${\lambda }_i$ 为特征值， U = ( ∣ ∣ ∣ u 1 u 2 ⋯ u n ∣ ∣ ∣ ) \mathbf{U}=\left(

∣∣∣u1u2⋯un∣∣∣" role="presentation">∣u1∣∣u2∣⋯∣un∣$$\begin{array}{cccc}\mid & \mid & & \mid \\ {\mathbf{u}}_1& {\mathbf{u}}_2& \cdots & {\mathbf{u}}_n\\ \mid & \mid & & \mid \end{array}$$

\right) U=⎝ ⎛​∣u1​∣​∣u2​∣​⋯​∣un​∣​⎠ ⎞​ 为单位正交矩阵，${\mathbf{u}}_i={\left(u_{i1},u_{i2},\dots ,u_{in}\right)}^T\in {\mathbb{R}}^n$ 为特征向量，即
K = λ 1 u 1 u 1 T + λ 2 u 2 u 2 T + ⋯ + λ n u n u n T K ( x i , x j ) = λ 1 u 1 i u 1 j + λ 2 u 2 i u 2 j ⋯ + λ n u n i u n j = ∑ k = 1 n λ k u k i u k j \mathbf{K}=\lambda_{1} \mathbf{u}_{1} \mathbf{u}_{1}^{T}+\lambda_{2} \mathbf{u}_{2} \mathbf{u}_{2}^{T}+\cdots+\lambda_{n} \mathbf{u}_{n} \mathbf{u}_{n}^{T}\\

K(xi,xj)=λ1u1iu1j+λ2u2iu2j⋯+λnuniunj=∑k=1nλkukiukj" role="presentation">K(xi,xj)=λ1u1iu1j+λ2u2iu2j⋯+λnuniunj=∑k=1nλkukiukj$$\begin{array}{rl}\mathbf{K}\left({\mathbf{x}}_i,{\mathbf{x}}_j\right)& ={\lambda }_1{u}_{1i}{u}_{1j}+{\lambda }_2{u}_{2i}{u}_{2j}\cdots +{\lambda }_n{u}_{ni}{u}_{nj}\\ & =\sum _{k=1}^n{\lambda }_k{u}_{ki}{u}_{kj}\end{array}$$

K=λ1​u1​u1T​+λ2​u2​u2T​+⋯+λn​un​unT​K(xi​,xj​)​=λ1​u1i​u1j​+λ2​u2i​u2j​⋯+λn​uni​unj​=k=1∑n​λk​uki​ukj​​
定义海塞映射：
$$\forall {\mathbf{x}}_i\in \mathbf{D},\varphi \left({\mathbf{x}}_i\right)={\left(\sqrt{{\lambda }_1}{u}_{1i},\sqrt{{\lambda }_2}{u}_{2i},\dots ,\sqrt{{\lambda }_n}{u}_{ni}\right)}^T$$
检查：
ϕ ( x i ) T ϕ ( x j ) = ( λ 1 u 1 i , … , λ n u n i ) ( λ 1 u 1 j , … , λ n u n j ) T = λ 1 u 1 i u 1 j + ⋯ + λ n u n i u n j = K ( x i , x j )

ϕ(xi)Tϕ(xj)=(λ1u1i,…,λnuni)(λ1u1j,…,λnunj)T=λ1u1iu1j+⋯+λnuniunj=K(xi,xj)" role="presentation">ϕ(xi)Tϕ(xj)=(λ1−−√u1i,…,λn−−√uni)(λ1−−√u1j,…,λn−−√unj)T=λ1u1iu1j+⋯+λnuniunj=K(xi,xj)$$\begin{array}{rl}\varphi {\left({\mathbf{x}}_i\right)}^T\varphi \left({\mathbf{x}}_j\right)& =\left(\sqrt{{\lambda }_1}{u}_{1i},\dots ,\sqrt{{\lambda }_n}{u}_{ni}\right){\left(\sqrt{{\lambda }_1}{u}_{1j},\dots ,\sqrt{{\lambda }_n}{u}_{nj}\right)}^T\\ & ={\lambda }_1{u}_{1i}{u}_{1j}+\cdots +{\lambda }_n{u}_{ni}{u}_{nj}=K\left({\mathbf{x}}_i,{\mathbf{x}}_j\right)\end{array}$$

ϕ(xi​)Tϕ(xj​)​=(λ1​ ​u1i​,…,λn​ ​uni​)(λ1​ ​u1j​,…,λn​ ​unj​)T=λ1​u1i​u1j​+⋯+λn​uni​unj​=K(xi​,xj​)​
注意：海塞映射中仅对 $\mathbf{D}$ 中的数 ${\mathbf{x}}_i$ 有定义。

5.2 向量核函数

${\mathbb{R}}^d\times {\mathbb{R}}^d\to \mathbb{R}$

典型向量核函数：多项式核

$\forall \mathbf{x},\mathbf{y}\in {\mathbb{R}}^d,K_q(\mathbf{x},\mathbf{y})=\varphi (\mathbf{x}{)}^T\varphi (\mathbf{y})={\left({\mathbf{x}}^T\mathbf{y}+c\right)}^q$，其中 $c\ge 0$

若 $c=0$，齐次，否则为非齐次。

问题：构造核映射 $\varphi :{\mathbb{R}}^d\to \mathcal{F}$，使得 $K_q(\mathbf{x},\mathbf{y})=\varphi (\mathbf{x}{)}^T\varphi (\mathbf{y})$

注：$q=1,c=0,\varphi (\mathbf{x})=\mathbf{x}$

示例：$q=2,d=2$

高斯核自读

5.3 特征空间中基本核运算

$\varphi :\mathcal{I}\to \mathcal{F},K:\mathcal{I}\times \mathcal{I}\to \mathbb{R}$

• 向量长度：$\Vert \varphi (\mathbf{x}){\Vert }^2=\varphi (\mathbf{x}{)}^T\varphi (\mathbf{x})=K(\mathbf{x},\mathbf{x})$

• 距离：
  ∥ ϕ ( x i ) − ϕ ( x j ) ∥ 2 = ∥ ϕ ( x i ) ∥ 2 + ∥ ϕ ( x j ) ∥ 2 − 2 ϕ ( x i ) T ϕ ( x j ) = K ( x i , x i ) + K ( x j , x j ) − 2 K ( x i , x j )

  ‖ϕ(xi)−ϕ(xj)‖2=‖ϕ(xi)‖2+‖ϕ(xj)‖2−2ϕ(xi)Tϕ(xj)=K(xi,xi)+K(xj,xj)−2K(xi,xj)" role="presentation">∥ϕ(xi)−ϕ(xj)∥2=∥ϕ(xi)∥2+∥ϕ(xj)∥2−2ϕ(xi)Tϕ(xj)=K(xi,xi)+K(xj,xj)−2K(xi,xj)$$\begin{array}{rl}{\Vert \varphi \left({\mathbf{x}}_i\right)-\varphi \left({\mathbf{x}}_j\right)\Vert }^2& ={\Vert \varphi \left({\mathbf{x}}_i\right)\Vert }^2+{\Vert \varphi \left({\mathbf{x}}_j\right)\Vert }^2-2\varphi {\left({\mathbf{x}}_i\right)}^T\varphi \left({\mathbf{x}}_j\right)\\ & =K\left({\mathbf{x}}_i,{\mathbf{x}}_i\right)+K\left({\mathbf{x}}_j,{\mathbf{x}}_j\right)-2K\left({\mathbf{x}}_i,{\mathbf{x}}_j\right)\end{array}$$
  ∥ϕ(xi​)−ϕ(xj​)∥2​=∥ϕ(xi​)∥2+∥ϕ(xj​)∥2−2ϕ(xi​)Tϕ(xj​)=K(xi​,xi​)+K(xj​,xj​)−2K(xi​,xj​)​

$2K\left(\mathbf{x},\mathbf{y}\right)={\Vert \varphi \left(\mathbf{x}\right)\Vert }^2+{\Vert \varphi \left(\mathbf{y}\right)\Vert }^2-{\Vert \varphi \left(\mathbf{x}\right)-\varphi \left(\mathbf{y}\right)\Vert }^2$

代表 $\varphi \left(\mathbf{x}\right)$ 与 $\varphi \left(\mathbf{y}\right)$ 的相似度

• 平均值：${\mathbf{\mu }}_{\varphi }=\frac{1}{n}\sum _{i=1}^n\varphi \left({\mathbf{x}}_i\right)$
  ∥ μ ϕ ∥ 2 = μ ϕ T μ ϕ = ( 1 n ∑ i = 1 n ϕ ( x i ) ) T ( 1 n ∑ j = 1 n ϕ ( x j ) ) = 1 n 2 ∑ i = 1 n ∑ j = 1 n ϕ ( x i ) T ϕ ( x j ) = 1 n 2 ∑ i = 1 n ∑ j = 1 n K ( x i , x j )

  ‖μϕ‖2=μϕTμϕ=(1n∑i=1nϕ(xi))T(1n∑j=1nϕ(xj))=1n2∑i=1n∑j=1nϕ(xi)Tϕ(xj)=1n2∑i=1n∑j=1nK(xi,xj)" role="presentation">∥μϕ∥2=μTϕμϕ=(1n∑i=1nϕ(xi))T(1n∑j=1nϕ(xj))=1n2∑i=1n∑j=1nϕ(xi)Tϕ(xj)=1n2∑i=1n∑j=1nK(xi,xj)$$\begin{array}{rl}{\Vert {\mathit{\mu }}_{\varphi }\Vert }^2& ={\mathit{\mu }}_{\varphi }^T{\mathit{\mu }}_{\varphi }\\ & ={\left(\frac{1}{n}\sum _{i=1}^n\varphi \left({\mathbf{x}}_i\right)\right)}^T\left(\frac{1}{n}\sum _{j=1}^n\varphi \left({\mathbf{x}}_j\right)\right)\\ & =\frac{1}{n^2}\sum _{i=1}^n\sum _{j=1}^n\varphi {\left({\mathbf{x}}_i\right)}^T\varphi \left({\mathbf{x}}_j\right)\\ & =\frac{1}{n^2}\sum _{i=1}^n\sum _{j=1}^{n}K\left({\mathbf{x}}_i,{\mathbf{x}}_j\right)\end{array}$$
  ∥ ∥​μϕ​∥ ∥​2​=μϕT​μϕ​=(n1​i=1∑n​ϕ(xi​))T(n1​j=1∑n​ϕ(xj​))=n21​i=1∑n​j=1∑n​ϕ(xi​)Tϕ(xj​)=n21​i=1∑n​j=1∑n​K(xi​,xj​)​

• 总方差：${\sigma }_{\varphi }^2=\frac{1}{n}\sum _{i=1}^n{\Vert \varphi \left({\mathbf{x}}_i\right)-{\mathbf{\mu }}_{\varphi }\Vert }^2$，$\forall {\mathbf{x}}_i$
  ∥ ϕ ( x i ) − μ ϕ ∥ 2 = ∥ ϕ ( x i ) ∥ 2 − 2 ϕ ( x i ) T μ ϕ + ∥ μ ϕ ∥ 2 = K ( x i , x i ) − 2 n ∑ j = 1 n K ( x i , x j ) + 1 n 2 ∑ s = 1 n ∑ t = 1 n K ( x s , x t )

  ‖ϕ(xi)−μϕ‖2=‖ϕ(xi)‖2−2ϕ(xi)Tμϕ+‖μϕ‖2=K(xi,xi)−2n∑j=1nK(xi,xj)+1n2∑s=1n∑t=1nK(xs,xt)" role="presentation">∥ϕ(xi)−μϕ∥2=∥ϕ(xi)∥2−2ϕ(xi)Tμϕ+∥μϕ∥2=K(xi,xi)−2n∑j=1nK(xi,xj)+1n2∑s=1n∑t=1nK(xs,xt)$$\begin{array}{rl}{\Vert \varphi \left({\mathbf{x}}_i\right)-{\mathit{\mu }}_{\varphi }\Vert }^2& ={\Vert \varphi \left({\mathbf{x}}_i\right)\Vert }^2-2\varphi {\left({\mathbf{x}}_i\right)}^T{\mathit{\mu }}_{\varphi }+{\Vert {\mathit{\mu }}_{\varphi }\Vert }^2\\ & =K\left({\mathbf{x}}_i,{\mathbf{x}}_i\right)-\frac{2}{n}\sum _{j=1}^{n}K\left({\mathbf{x}}_i,{\mathbf{x}}_j\right)+\frac{1}{n^2}\sum _{s=1}^n\sum _{t=1}^{n}K\left({\mathbf{x}}_s,{\mathbf{x}}_t\right)\end{array}$$
  ∥ ∥​ϕ(xi​)−μϕ​∥ ∥​2​=∥ϕ(xi​)∥2−2ϕ(xi​)Tμϕ​+∥ ∥​μϕ​∥ ∥​2=K(xi​,xi​)−n2​j=1∑n​K(xi​,xj​)+n21​s=1∑n​t=1∑n​K(xs​,xt​)​

  σ ϕ 2 = 1 n ∑ i = 1 n ∥ ϕ ( x i ) − μ ϕ ∥ 2 = 1 n ∑ i = 1 n ( K ( x i , x i ) − 2 n ∑ j = 1 n K ( x i , x j ) + 1 n 2 ∑ s = 1 n ∑ t = 1 n K ( x s , x t ) ) = 1 n ∑ i = 1 n K ( x i , x i ) − 2 n 2 ∑ i = 1 n ∑ j = 1 n K ( x i , x j ) + 1 n 2 ∑ s = 1 n ∑ t = 1 n K ( x s , x t ) = 1 n ∑ i = 1 n K ( x i , x i ) − 1 n 2 ∑ i = 1 n ∑ j = 1 n K ( x i , x j )

  σϕ2=1n∑i=1n‖ϕ(xi)−μϕ‖2=1n∑i=1n(K(xi,xi)−2n∑j=1nK(xi,xj)+1n2∑s=1n∑t=1nK(xs,xt))=1n∑i=1nK(xi,xi)−2n2∑i=1n∑j=1nK(xi,xj)+1n2∑s=1n∑t=1nK(xs,xt)=1n∑i=1nK(xi,xi)−1n2∑i=1n∑j=1nK(xi,xj)" role="presentation">σ2ϕ=1n∑i=1n∥ϕ(xi)−μϕ∥2=1n∑i=1n(K(xi,xi)−2n∑j=1nK(xi,xj)+1n2∑s=1n∑t=1nK(xs,xt))=1n∑i=1nK(xi,xi)−2n2∑i=1n∑j=1nK(xi,xj)+1n2∑s=1n∑t=1nK(xs,xt)=1n∑i=1nK(xi,xi)−1n2∑i=1n∑j=1nK(xi,xj)$$\begin{array}{rl}{\sigma }_{\varphi }^2& =\frac{1}{n}\sum _{i=1}^n{\Vert \varphi \left({\mathbf{x}}_i\right)-{\mathit{\mu }}_{\varphi }\Vert }^2\\ & =\frac{1}{n}\sum _{i=1}^n\left(K\left({\mathbf{x}}_i,{\mathbf{x}}_i\right)-\frac{2}{n}\sum _{j=1}^{n}K\left({\mathbf{x}}_i,{\mathbf{x}}_j\right)+\frac{1}{n^2}\sum _{s=1}^n\sum _{t=1}^{n}K\left({\mathbf{x}}_s,{\mathbf{x}}_t\right)\right)\\ & =\frac{1}{n}\sum _{i=1}^{n}K\left({\mathbf{x}}_i,{\mathbf{x}}_i\right)-\frac{2}{n^2}\sum _{i=1}^n\sum _{j=1}^{n}K\left({\mathbf{x}}_i,{\mathbf{x}}_j\right)+\frac{1}{n^2}\sum _{s=1}^n\sum _{t=1}^{n}K\left({\mathbf{x}}_s,{\mathbf{x}}_t\right)\\ & =\frac{1}{n}\sum _{i=1}^{n}K\left({\mathbf{x}}_i,{\mathbf{x}}_i\right)-\frac{1}{n^2}\sum _{i=1}^n\sum _{j=1}^{n}K\left({\mathbf{x}}_i,{\mathbf{x}}_j\right)\end{array}$$
  σϕ2​​=n1​i=1∑n​∥ ∥​ϕ(xi​)−μϕ​∥ ∥​2=n1​i=1∑n​(K(xi​,xi​)−n2​j=1∑n​K(xi​,xj​)+n21​s=1∑n​t=1∑n​K(xs​,xt​))=n1​i=1∑n​K(xi​,xi​)−n22​i=1∑n​j=1∑n​K(xi​,xj​)+n21​s=1∑n​t=1∑n​K(xs​,xt​)=n1​i=1∑n​K(xi​,xi​)−n21​i=1∑n​j=1∑n​K(xi​,xj​)​

  $\frac{1}{n}\sum _{i=1}^{n}K\left({\mathbf{x}}_i,{\mathbf{x}}_i\right)$ 是 $\mathbf{K}$ 对角线平均值，$\frac{1}{n^2}\sum _{i=1}^n\sum _{j=1}^{n}K\left({\mathbf{x}}_i,{\mathbf{x}}_j\right)$ 是 $\mathbf{K}$ 所有元的平均值。

• 中心化核矩阵：令 $\hat{\varphi }\left({\mathbf{x}}_i\right)=\varphi \left({\mathbf{x}}_i\right)-{\mathbf{\mu }}_{\varphi }$

  中心核函数 $\hat{K}\left({\mathbf{x}}_i,{\mathbf{x}}_j\right)=\hat{\varphi }{\left({\mathbf{x}}_i\right)}^T\hat{\varphi }\left({\mathbf{x}}_j\right)$
  K ^ ( x i , x j ) = ( ϕ ( x i ) − μ ϕ ) T ( ϕ ( x j ) − μ ϕ ) = ϕ ( x i ) T ϕ ( x j ) − ϕ ( x i ) T μ ϕ − ϕ ( x j ) T μ ϕ + μ ϕ T μ ϕ = K ( x i , x j ) − 1 n ∑ k = 1 n ϕ ( x i ) T ϕ ( x k ) − 1 n ∑ k = 1 n ϕ ( x j ) T ϕ ( x k ) + ∥ μ ϕ ∥ 2 = K ( x i , x j ) − 1 n ∑ k = 1 n K ( x i , x k ) − 1 n ∑ k = 1 n K ( x j , x k ) + 1 n 2 ∑ s = 1 n ∑ t = 1 n K ( x s , x t )

  K^(xi,xj)=(ϕ(xi)−μϕ)T(ϕ(xj)−μϕ)=ϕ(xi)Tϕ(xj)−ϕ(xi)Tμϕ−ϕ(xj)Tμϕ+μϕTμϕ=K(xi,xj)−1n∑k=1nϕ(xi)Tϕ(xk)−1n∑k=1nϕ(xj)Tϕ(xk)+‖μϕ‖2=K(xi,xj)−1n∑k=1nK(xi,xk)−1n∑k=1nK(xj,xk)+1n2∑s=1n∑t=1nK(xs,xt)" role="presentation">K^(xi,xj)=(ϕ(xi)−μϕ)T(ϕ(xj)−μϕ)=ϕ(xi)Tϕ(xj)−ϕ(xi)Tμϕ−ϕ(xj)Tμϕ+μTϕμϕ=K(xi,xj)−1n∑k=1nϕ(xi)Tϕ(xk)−1n∑k=1nϕ(xj)Tϕ(xk)+∥μϕ∥2=K(xi,xj)−1n∑k=1nK(xi,xk)−1n∑k=1nK(xj,xk)+1n2∑s=1n∑t=1nK(xs,xt)$$\begin{array}{rl}\hat{K}\left({\mathbf{x}}_i,{\mathbf{x}}_j\right)& ={\left(\varphi \left({\mathbf{x}}_i\right)-{\mathit{\mu }}_{\varphi }\right)}^T\left(\varphi \left({\mathbf{x}}_j\right)-{\mathit{\mu }}_{\varphi }\right)\\ & =\varphi {\left({\mathbf{x}}_i\right)}^T\varphi \left({\mathbf{x}}_j\right)-\varphi {\left({\mathbf{x}}_i\right)}^T{\mathit{\mu }}_{\varphi }-\varphi {\left({\mathbf{x}}_j\right)}^T{\mathit{\mu }}_{\varphi }+{\mathit{\mu }}_{\varphi }^T{\mathit{\mu }}_{\varphi }\\ & =K\left({\mathbf{x}}_i,{\mathbf{x}}_j\right)-\frac{1}{n}\sum _{k=1}^n\varphi {\left({\mathbf{x}}_i\right)}^T\varphi \left({\mathbf{x}}_k\right)-\frac{1}{n}\sum _{k=1}^n\varphi {\left({\mathbf{x}}_j\right)}^T\varphi \left({\mathbf{x}}_k\right)+{\Vert {\mathit{\mu }}_{\varphi }\Vert }^2\\ & =K\left({\mathbf{x}}_i,{\mathbf{x}}_j\right)-\frac{1}{n}\sum _{k=1}^{n}K\left({\mathbf{x}}_i,{\mathbf{x}}_k\right)-\frac{1}{n}\sum _{k=1}^{n}K\left({\mathbf{x}}_j,{\mathbf{x}}_k\right)+\frac{1}{n^2}\sum _{s=1}^n\sum _{t=1}^{n}K\left({\mathbf{x}}_s,{\mathbf{x}}_t\right)\end{array}$$
  K^(xi​,xj​)​=(ϕ(xi​)−μϕ​)T(ϕ(xj​)−μϕ​)=ϕ(xi​)Tϕ(xj​)−ϕ(xi​)Tμϕ​−ϕ(xj​)Tμϕ​+μϕT​μϕ​=K(xi​,xj​)−n1​k=1∑n​ϕ(xi​)Tϕ(xk​)−n1​k=1∑n​ϕ(xj​)Tϕ(xk​)+∥ ∥​μϕ​∥ ∥​2=K(xi​,xj​)−n1​k=1∑n​K(xi​,xk​)−n1​k=1∑n​K(xj​,xk​)+n21​s=1∑n​t=1∑n​K(xs​,xt​)​
  故
  K ^ = K − 1 n 1 n × n K − 1 n K 1 n × n + 1 n 2 1 n × n K 1 n × n = ( I − 1 n 1 n × n ) K ( I − 1 n 1 n × n )
  K^=K−1n1n×nK−1nK1n×n+1n21n×nK1n×n=(I−1n1n×n)K(I−1n1n×n)" role="presentation">K^=K−1n1n×nK−1nK1n×n+1n21n×nK1n×n=(I−1n1n×n)K(I−1n1n×n)$$\begin{array}{rl}\hat{\mathbf{K}}& =\mathbf{K}-\frac{1}{n}{\mathbf{1}}_{n\times n}\mathbf{K}-\frac{1}{n}\mathbf{K}{\mathbf{1}}_{n\times n}+\frac{1}{n^2}{\mathbf{1}}_{n\times n}\mathbf{K}{\mathbf{1}}_{n\times n}\\ & =\left(\mathbf{I}-\frac{1}{n}{\mathbf{1}}_{n\times n}\right)\mathbf{K}\left(\mathbf{I}-\frac{1}{n}{\mathbf{1}}_{n\times n}\right)\end{array}$$
  K^​=K−n1​1n×n​K−n1​K1n×n​+n21​1n×n​K1n×n​=(I−n1​1n×n​)K(I−n1​1n×n​)​
  注意：$1_{n\times n}$ 为全1矩阵，左乘之后每个元素为之前所在列的列和，右乘之和每个元素为之前所在行的行和，左右都乘之后每个元素即为原来所以元素之后。

• 归一化核矩阵

  ${\mathbf{K}}_n\left({\mathbf{x}}_i,{\mathbf{x}}_j\right)=\frac{\varphi {\left({\mathbf{x}}_i\right)}^T\varphi \left({\mathbf{x}}_j\right)}{\Vert \varphi \left({\mathbf{x}}_i\right)\Vert \cdot \Vert \varphi \left({\mathbf{x}}_j\right)\Vert }=\frac{K\left({\mathbf{x}}_i,{\mathbf{x}}_j\right)}{\sqrt{K\left({\mathbf{x}}_i,{\mathbf{x}}_i\right)\cdot K\left({\mathbf{x}}_j,{\mathbf{x}}_j\right)}}$

  令 W = diag ⁡ ( K ) = ( K ( x 1 , x 1 ) 0 ⋯ 0 0 K ( x 2 , x 2 ) ⋯ 0 ⋮ ⋮ ⋱ ⋮ 0 0 ⋯ K ( x n , x n ) ) \mathbf{W}=\operatorname{diag}(\mathbf{K})=\left(

  K(x1,x1)0⋯00K(x2,x2)⋯0⋮⋮⋱⋮00⋯K(xn,xn)" role="presentation">K(x1,x1)0⋮00K(x2,x2)⋮0⋯⋯⋱⋯00⋮K(xn,xn)$$\begin{array}{cccc}K\left({\mathbf{x}}_1,{\mathbf{x}}_1\right)& 0& \cdots & 0\\ 0& K\left({\mathbf{x}}_2,{\mathbf{x}}_2\right)& \cdots & 0\\ ⋮& ⋮& \ddots & ⋮\\ 0& 0& \cdots & K\left({\mathbf{x}}_n,{\mathbf{x}}_n\right)\end{array}$$
  \right) W=diag(K)=⎝ ⎛​K(x1​,x1​)0⋮0​0K(x2​,x2​)⋮0​⋯⋯⋱⋯​00⋮K(xn​,xn​)​⎠ ⎞​，则 ${\mathbf{W}}^{-1/2}\left({\mathbf{x}}_i,{\mathbf{x}}_i\right)=\frac{1}{\sqrt{K\left({\mathbf{x}}_i,{\mathbf{x}}_i\right)}}$，

  ${\mathbf{K}}_n={\mathbf{W}}^{-1/2}\cdot \mathbf{K}\cdot {\mathbf{W}}^{-1/2}$

  矩阵左乘右乘对角阵的性质。

5.4 复杂对象的核

5.4.1 字串的谱核

考虑字符集 $\Sigma$ （有限），定义 $l$-谱特征映射：
$${\varphi }_l:{\Sigma }^{\ast }\to {\mathbb{R}}^{|\Sigma {|}^l},\forall \mathbf{x}\in {\Sigma }^{\ast },{\varphi }_l(\mathbf{x})={\left(\cdots ,\#(\alpha ),\cdots \right)}^T$$
其中 $\#(\alpha )$ 代表长度为 $l$ 的子字串在 $\mathbf{x}$ 中出现的次数。

$l$-谱核函数：${\mathbf{K}}_l:{\Sigma }^{\ast }\times {\Sigma }^{\ast }\to \mathbb{R}$，${\mathbf{K}}_l(\mathbf{x},\mathbf{y})={\varphi }_l(\mathbf{x}{)}^T{\varphi }_l(\mathbf{y})$

谱核函数：计算 $l=0$ 到 $l=\infty$

5.4.2 图顶点的扩散核

• 图：图 $G=(V,E)$ 是指一个集合对，其中 V = { v 1 , ⋯   , v n } V=\{v_1,\cdots,v_n\} V={v1​,⋯,vn​} 为顶点集，$E=\{(v_i,v_j)\}$ 为边集。现只考虑无向简单（没有自己到自己的边）图。

• 邻接矩阵：图的邻接矩阵 $A(G):=[A_{ij}{]}_{n\times n}$，其中 A i j = { 1 , ( v i , v j ) ∈ E 0 , ( v i , v j ) ∉ E A_{ij}=\left\{

  1,(vi,vj)∈E0,(vi,vj)∉E" role="presentation">1,(vi,vj)∈E0,(vi,vj)∉E$$\begin{array}{c}1,(v_i,v_j)\in E\\ 0,(v_i,v_j)\notin E\end{array}$$
  \right. Aij​={1,(vi​,vj​)∈E0,(vi​,vj​)∈/E​

• 度矩阵：$\Delta (G):=diag(d_1,\cdots ,d_n)$，其中 $d_i$ 代表顶点 $v_i$ 的度，即与 $v_i$ 相连的边的数目。

• 拉普拉斯矩阵：$L(G):=A(G)-\Delta (G)$

  负拉普拉斯矩阵：$L(G):=-L(G)$

  它们是实对称

常用图的对称相似性矩阵 $\mathbf{S}$ 是指 $A(G)$，$L(G)$ 或 $-L(G)$。

问题：如何定义图顶点的核函数？（ $\mathbf{S}$ 并不一定是半正定）

- 幂核函数

以 ${\mathbf{S}}^t$ 作为核矩阵， $\mathbf{S}$ 是对称的，$t$ 为正整数

考虑 ${\mathbf{S}}^2$：${\mathbf{S}}^2(x_i,x_j)=\sum _{k=1}^n{S}_{ik}{S}_{kj}$

此公式说明 ${\mathbf{S}}^2$ ( ${\mathbf{S}}^l$) 的几何意义：顶点间长度为 $2$ $(l)$ 的路径，描述顶点的相似性。

考虑 ${\mathbf{S}}^l$ 的特征值：设 $\mathbf{S}$ 的特征值为 ${\lambda }_1,\cdots ,{\lambda }_n\in \mathbb{R}$，则
S = U ( λ 1 0 ⋯ 0 0 λ 2 ⋯ 0 ⋮ ⋮ ⋱ ⋮ 0 0 ⋯ λ n ) U T = ∑ i = 1 n λ i u i u i T \mathbf{S}=\mathbf{U}\left(

\right)\mathbf{U}^{T}=\sum_{i=1}^{n} \lambda_{i}\mathbf{u}_{i} \mathbf{u}_{i}^{T} S=U⎝ ⎛​λ1​0⋮0​0λ2​⋮0​⋯⋯⋱⋯​00⋮λn​​⎠ ⎞​UT=i=1∑n​λi​ui​uiT​
其中 $\mathbf{U}$ 是以相应特征向量为列的正交矩阵， U = ( ∣ ∣ ∣ u 1 u 2 ⋯ u n ∣ ∣ ∣ ) \mathbf{U}=\left(

∣∣∣u1u2⋯un∣∣∣" role="presentation">∣u1∣∣u2∣⋯∣un∣$$\begin{array}{cccc}\mid & \mid & & \mid \\ {\mathbf{u}}_1& {\mathbf{u}}_2& \cdots & {\mathbf{u}}_n\\ \mid & \mid & & \mid \end{array}$$

\right) U=⎝ ⎛​∣u1​∣​∣u2​∣​⋯​∣un​∣​⎠ ⎞​
S l = U ( λ 1 l 0 ⋯ 0 0 λ 2 l ⋯ 0 ⋮ ⋮ ⋱ ⋮ 0 0 ⋯ λ n l ) U T \mathbf{S}^l=\mathbf{U}\left(

λ1l0⋯00λ2l⋯0⋮⋮⋱⋮00⋯λnl" role="presentation">λl10⋮00λl2⋮0⋯⋯⋱⋯00⋮λln$$\begin{array}{cccc}{\lambda }_1^l& 0& \cdots & 0\\ 0& {\lambda }_2^l& \cdots & 0\\ ⋮& ⋮& \ddots & ⋮\\ 0& 0& \cdots & {\lambda }_n^l\end{array}$$

\right)\mathbf{U}^{T} Sl=U⎝ ⎛​λ1l​0⋮0​0λ2l​⋮0​⋯⋯⋱⋯​00⋮λnl​​⎠ ⎞​UT
${\lambda }_1^l,\cdots ,{\lambda }_n^l$ 是 ${\mathbf{S}}^l$ 的特征值。

故若 $l$ 是偶数，${\mathbf{S}}^l$ 半正定。

- 指数扩散核函数

以 $\mathbf{K}:=e^{\beta \mathbf{S}}$ 为核矩阵，其中 $\beta >0$ 为阻尼系数。（泰勒展开：$e^{\beta x}=\sum _{l=0}^{\infty }\frac{1}{l!}{\beta }^l{x}^l$）
e β S = ∑ l = 0 ∞ 1 l ! β ′ S l = I + β S + 1 2 ! β 2 S 2 + 1 3 ! β 3 S 3 + ⋯ = ( ∑ i = 1 n u i u i T ) + ( ∑ i = 1 n u i β λ i u i T ) + ( ∑ i = 1 n u i 1 2 ! β 2 λ i 2 u i T ) + ⋯ = ∑ i = 1 n u i ( 1 + β λ i + 1 2 ! β 2 λ i 2 + ⋯   ) u i T = ∑ i = 1 n u i e β λ i u i T = U ( e β λ 1 0 ⋯ 0 0 e β λ 2 ⋯ 0 ⋮ ⋮ ⋱ 0 0 0 ⋯ e β λ n ) U T

eβS​=l=0∑∞​l!1​β′Sl=I+βS+2!1​β2S2+3!1​β3S3+⋯=(i=1∑n​ui​uiT​)+(i=1∑n​ui​βλi​uiT​)+(i=1∑n​ui​2!1​β2λi2​uiT​)+⋯=i=1∑n​ui​(1+βλi​+2!1​β2λi2​+⋯)uiT​=i=1∑n​ui​eβλi​uiT​=U⎝ ⎛​eβλ1​0⋮0​0eβλ2​⋮0​⋯⋯⋱⋯​000eβλn​​⎠ ⎞​UT​
故 $\mathbf{K}$ 的特征值 $e^{\beta {\lambda }_1},\cdots ,e^{\beta {\lambda }_n}$ 完全非负， $\mathbf{K}$ 为半正定。

- 纽因曼扩散核函数

以 $\mathbf{K}=\sum _{l=0}^{\infty }{\beta }^l{\mathbf{S}}^l$ 为核矩阵，注意到
K = I + β S + β 2 S 2 + β 3 S 3 + ⋯ = I + β S ( I + β S + β 2 S 2 + ⋯   ) = I + β S K

K​=I+βS+β2S2+β3S3+⋯=I+βS(I+βS+β2S2+⋯)=I+βSK​
故
K − β S K = I ( I − β S ) K = I K = ( I − β S ) − 1

K−βSK=I(I−βS)K=IK=(I−βS)−1" role="presentation">K−βSK(I−βS)KK=I=I=(I−βS)−1$$\begin{array}{rl}\mathbf{K}-\beta \mathbf{S}\mathbf{K}& =\mathbf{I}\\ (\mathbf{I}-\beta \mathbf{S})\mathbf{K}& =\mathbf{I}\\ \mathbf{K}& =(\mathbf{I}-\beta \mathbf{S}{)}^{-1}\end{array}$$

K−βSK(I−βS)KK​=I=I=(I−βS)−1​
在 $\mathbf{I}-\beta \mathbf{S}$ 可逆的前提下
K = ( U U T − U ( β Λ ) U T ) − 1 = ( U ( I − β Λ ) U T ) − 1 = U ( I − β Λ ) − 1 U T = U ( 1 1 − β λ 1 0 ⋯ 0 0 1 1 − β λ 2 ⋯ 0 ⋮ ⋮ ⋱ 0 0 0 ⋯ 1 1 − β λ n ) U T

K=(UUT−U(βΛ)UT)−1=(U(I−βΛ)UT)−1=U(I−βΛ)−1UT=U(11−βλ10⋯0011−βλ2⋯0⋮⋮⋱000⋯11−βλn)UT" role="presentation">K=(UUT−U(βΛ)UT)−1=(U(I−βΛ)UT)−1=U(I−βΛ)−1UT=U⎛⎝⎜⎜⎜⎜⎜⎜⎜11−βλ10⋮0011−βλ2⋮0⋯⋯⋱⋯00011−βλn⎞⎠⎟⎟⎟⎟⎟⎟⎟UT$$\begin{array}{rl}\mathbf{K}& ={\left(\mathbf{U}{\mathbf{U}}^T-\mathbf{U}(\beta \mathbf{\Lambda }){\mathbf{U}}^T\right)}^{-1}\\ & ={\left(\mathbf{U}(\mathbf{I}-\beta \mathbf{\Lambda }){\mathbf{U}}^T\right)}^{-1}\\ & =\mathbf{U}(\mathbf{I}-\beta \mathbf{\Lambda }{)}^{-1}{\mathbf{U}}^T\\ & =\mathbf{U}\left(\begin{array}{cccc}\frac{1}{1-\beta {\lambda }_1}& 0& \cdots & 0\\ 0& \frac{1}{1-\beta {\lambda }_2}& \cdots & 0\\ ⋮& ⋮& \ddots & 0\\ 0& 0& \cdots & \frac{1}{1-\beta {\lambda }_n}\end{array}\right){\mathbf{U}}^T\end{array}$$

K​=(UUT−U(βΛ)UT)−1=(U(I−βΛ)UT)−1=U(I−βΛ)−1UT=U⎝ ⎛​1−βλ1​1​0⋮0​01−βλ2​1​⋮0​⋯⋯⋱⋯​0001−βλn​1​​⎠ ⎞​UT​
要想其半正定，故有：
( 1 − β λ i ) − 1 ≥ 0 1 − β λ i ≥ 0 β λ i ≤ 1

(1−βλi)−1≥01−βλi≥0βλi≤1" role="presentation">(1−βλi)−11−βλiβλi≥0≥0≤1$$\begin{array}{rl}{\left(1-\beta {\lambda }_i\right)}^{-1}& \ge 0\\ 1-\beta {\lambda }_i& \ge 0\\ \beta {\lambda }_i& \le 1\end{array}$$

(1−βλi​)−11−βλi​βλi​​≥0≥0≤1​

---