算法原理
部分数据在低维度线性不可分，但映射到高维度时就可以实现线性划分。通过使用核的技巧就可以实现映射$x_i
ightarrow phi_{x_i} $，并在映射得到的新的特征空间进行主成分分析。
推导方法1[1]
推导建立在PCA的基础上的。需要先掌握PCA。可以参考前一篇博客
假设在特征空间数据的均值为：
[mu = frac{1}{n} sum _{i=1} ^n phi(x_i)= 0
]
有方差：
[C = frac{1}{n} sum _{i=1} ^n phi(x_i) phi(x_i)^ T
]
和PCA相类似， 特征向量为：
[egin{align} Cv = lambda v end{align}
]
因为不知道(phi)的形式是怎么样的，并不能直接通过特征分解求(v)。
可以证明(v)可以表示成高维特征的线性组合
[v_j = sum _{i=1} ^n alpha _{ji} phi(x_i)
]
所以求特征向量等价于求因子(alpha_{ji})
通过将(C, v)的表达式代入(1)中可以得到：
[egin{align}K alpha_j = n lambda_j alpha_j end{align}
]
其中(K)是一个核函数，(k(x_i, x_j) = phi (x_i)^T phi (x_i), K
eq C)对于特定的数据，可认为是已知的。由(2) $alpha _j (是)K(的特征向量， 下面求其约束。注意这里并不是要求其长度为1。 特征向量)v_j$是一个单位向量,
由
[v_j^T v_j = 1
]
代入(v_j)有
[sum _{k=1} ^n sum _{l=1} ^n alpha _{jl} alpha _{jk} phi(x_l)^T phi(x_k)= 1
]
即
[alpha _j ^T K alpha _j = 1
]
代入(2)得到
[lambda _j n alpha _j ^T alpha _j = 1 , forall j
]
以上就是其长度约束。
对于新的数据x，它在主成分的投影坐标为
[phi (x)^T v_j = sum _{i=1} ^n alpha _{ji} phi (x)^T phi (x_i) = sum _{i=1} ^n alpha _{ji}K(x, x_j)
]
由以上投影坐标可以求。
一般情况下，特征空间的均值不是0。可以将特征中心化。
[hat phi (x_i) = phi(x_i) - frac{1}{n} sum _{k=1} ^n phi(x_k)
]
相应的核也变成了
[hat K(x_i, x_j) = K(x_i, x_j) - frac{1}{n} sum _{k=1} ^n K(x_i, x_k) - frac{1}{n} sum _{k=1} ^n K(x_j, x_k)+ frac{1}{n^2} sum _{l= 1, k=1} ^n K(x_l, x_k)
]
矩阵形式：
[hat K (x_i , x_j) = K - 2 1_{1/n}K + 1 _{1/n }K 1_{1/n}
]
(1_{1/n})表示所有元素为1的矩阵。
KPCA的算法流程
- 选择一个核
- 由(3)建立一个归一化核矩阵
- 求特征值分解
[hat K alpha _i = lambda _i alpha _i
]
- 对于新的数据点在主成分的投影为
[y_i = sum _{i=1} ^n alpha _{ji}K(x, x_i), j = 1, ···d
]
推导方法2[2]
假设数据均值为0时，有协方差矩阵，
[C = frac{1}{n}X^T X = frac{1}{N}
egin{bmatrix} phi(x_1),...phi(x_n) end{bmatrix}
egin{bmatrix} phi(x_1)^T \
vdots \
phi(x_n)^T end{bmatrix}]
(X)认为是数据在特征空间的表示。因为不知道(phi)的形式，所以希望转换成可以用kernel K表示形式
[K = X X^T = egin{bmatrix} phi(x_1)^T phi(x_1) & dots & phi(x_1)^T phi(x_n)\
vdots & dots & vdots\
phi(x_n)^Tphi(x_1) & dots & phi(x_n)^T phi(x_n)end{bmatrix}
\= egin{bmatrix} kappa(x_1, x_1) & dots & kappa(x_1, x_n) \
vdots & dots & vdots\
kappa(x_n, x_1) & dots & kappa(x_n, x_n) end{bmatrix}
]
从kernel矩阵的特征方程(逆向推理)出发：
[ X X^T u = lambda u
]
两边左乘(X^T)，整理得到
[ X^T X (X^T u) = lambda (X^T u)
]
可以看出(X^T u)是(C)的特征向量，因为其受到其为单位向量的约束，有：
[v = frac{1}{||X^T u||}X^T u = frac{1}{sqrt{u ^T X X^T u}}X^T u \
=frac{1}{sqrt{u^T lambda u}}X^T u = frac{1}{sqrt{ lambda}}X^T u]
这里令(u)也是单位向量。特征向量还是和(X)直接相关，仍然是未知的。
直接考虑在特征空间投影之后的坐标(高中向量知识)：
[v ^T phi(x') = (frac{1}{sqrt{ lambda}}X^T u)^T phi(x') = frac{1}{sqrt{ lambda}}u^T X phi(x') \
= frac{1}{sqrt{ lambda}}u^T
egin{bmatrix} phi(x_1)^T \
vdots \
phi(x_n)^T end{bmatrix}
phi(x') = frac{1}{sqrt{ lambda}}u^T
egin{bmatrix} kappa(x_1, x') \
vdots \
kappa(x_n, x') end{bmatrix}
]
最想要知道的正好是可以计算的。
题外话
特征空间的向量(v)可以用特征空间的数据线性表示。因为
[ v=frac{1}{sqrt{ lambda}}X^T u = frac{1}{sqrt{ lambda}}egin{bmatrix} phi(x_1),...phi(x_n) end{bmatrix} u
\ = frac{1}{sqrt{ lambda}} sum _{i=1} ^n u_i phi(x_i) = sum_{i=1} ^n alpha_i phi(x_i)]
KPCA的算法流程
- 选择一个核
- 建立一个归一化核矩阵
- 求特征值分解
[K u = lambda u
]
- 对于新的数据点在主成分的投影为
[v= frac{1}{sqrt{ lambda}}u^T
egin{bmatrix} kappa(x_1, x') \
vdots \
kappa(x_n, x') end{bmatrix}]
参考文献
[1]. http://www.cs.haifa.ac.il/~rita/uml_course/lectures/KPCA.pdf
[2]. https://www.youtube.com/watch?v=G2NRnh7W4NQ