04-0003 KPCA算法

1.KPCA简述

当数据在低维空间不是线性可分的时候，转化到高维的空间可能就变成了线性可分的，这个过程用到了KPCA算法，也就是将数据才能从低维非线性，转化为高维线性可分数据的一种算法。
[注：这里的高维空间下的线性可分，此时的线性说的是一个超平面。我的理解。 ]

如下图，在二维空间中星星与红点是线性不可分的，如果将其分开，需要一个非线性的曲线[椭圆]，但是非线性的曲线在构建的时候是不容易构建的。
所以这个时候就有了升维的 骚 操作，能够将一个非线性的区域，转化为高维空间下的一个超平面。高维空间下的一个平面压扁之后，被曲化。
[注：这种感觉好像是《三体》里面的降维打击一般，三维立体的生物被降维打击之后，就会平面化，本来可分的内脏器官之类的东西，就会乱成一团。 ]

低维线性不可分，到高维线性可分

2.核函数

什么是核函数呢？

支持向量机通过某非线性变换 φ( x) ，将输入空间映射到高维特征空间。特征空间的维数可能非常高。如果支持向量机的求解只用到内积运算，而在低维输入空间又存在某个函数 K(x, x′) ，它恰好等于在高维空间中这个内积，即K( x, x′) =<φ( x) ⋅φ( x′) > 。那么支持向量机就不用计算复杂的非线性变换，而由这个函数 K(x, x′) 直接得到非线性变换的内积，使大大简化了计算。这样的函数 K(x, x′) 称为核函数。

首先核函数，也是一个函数，与高数中所认知的函数是一样的，用于做某种变换。从一个集合到另一个集合的变化。

比如，是从集合A，到集合B的一种函数：A–>B，如下图：

[映射两边的集合数据可以是不一致的，经过核函数K的变换之后，可以将一个二维的数据转化为一个三维的数据。能够完成数据的升维。]

几种不同的核函数：
.
1.Linear Kernel [线性核函数]

线性核是最简单的核函数，核函数的数学公式如下：
$$k(x,y)=<x,y>$$
或
$$k(x,y)=x^{t}y$$
如果我们将线性核函数应用在KPCA中，我们会发现，推导之后和原始PCA算法一模一样，很多童鞋借此说“kernel is shit！！！”，这是不对的，这只是线性核函数偶尔会出现等价的形式罢了。

2.Polynomial Kernel [多项式核函数]

多项式核实一种非标准核函数，它非常适合于正交归一化后的数据，其具体形式如下：
$$k(x,y)=(a{x}^{t}y+c{)}^d$$
这个核函数是比较好用的，就是参数比较多，但是还算稳定。

3.Gaussian Kernel [高斯核函数]

这里说一种经典的鲁棒径向基核，即高斯核函数，鲁棒径向基核对于数据中的噪音有着较好的抗干扰能力，其参数决定了函数作用范围，超过了这个范围，数据的作用就“基本消失”。高斯核函数是这一族核函数的优秀代表，也是必须尝试的核函数，其数学形式如下：
$$k(x,y)=e^{-\frac{||x-y|{|}^2}{2{\sigma }^2}}$$
虽然被广泛使用，但是这个核函数的性能对参数十分敏感，以至于有一大把的文献专门对这种核函数展开研究，同样，高斯核函数也有了很多的变种，如指数核，拉普拉斯核等。

4.Exponential Kernel [指数核函数]

指数核函数就是高斯核函数的变种，它仅仅是将向量之间的L2距离调整为L1距离，这样改动会对参数的依赖性降低，但是适用范围相对狭窄。其数学形式如下：
$$k(x,y)=e^{-\frac{||x-y||}{2{\sigma }^2}}$$

5.Laplacian Kernel [拉普拉斯核函数]

拉普拉斯核完全等价于指数核，唯一的区别在于前者对参数的敏感性降低，也是一种径向基核函数，数学形式如下：
$$k(x,y)=e^{-\frac{||x-y||}{\sigma }}$$

6.ANOVA Kernel [ANOVA 核]

ANOVA 核也属于径向基核函数一族，其适用于多维回归问题，数学形式如下：
$$k(x,y)=(e^{-\sigma (x^k-y^k{)}^2}{)}^d$$

7.Sigmoid Kernel [Sigmoid 核]

Sigmoid 核来源于神经网络，现在已经大量应用于深度学习，是当今机器学习的宠儿，它是S型的，所以被用作于“激活函数”，数学形式如下：
$$k(x,y)=tanh(a{x}^{t}y+c)$$

8.Rational Quadratic Kernel [二次有理核]

二次有理核完完全全是作为高斯核的替代品出现，如果你觉得高斯核函数很耗时，那么不妨尝试一下这个核函数，顺便说一下，这个核函数作用域虽广，但是对参数十分敏感，慎用，数学形式如下：
$$k(x,y)=1-\frac{||x-y|{|}^2}{||x-y|{|}^2+c}$$

9.Multiquadric Kernel [多元二次核]

多元二次核可以替代二次有理核，它是一种非正定核函数，数学形式如下：
$$k(x,y)=(||x-y|{|}^2+c^2{)}^{0.5}$$

10.Inverse Multiquadric Kernel [逆多元二次核]

顾名思义，逆多元二次核来源于多元二次核，这个核函数我没有用过，但是据说这个基于这个核函数的算法，不会遇到核相关矩阵奇异的情况，数学形式如下：
$$k(x,y)=(||x-y|{|}^2+c^2{)}^{-0.5}$$

11.Circular Kernel

数学形式如下：
$$k(x,y)=\frac{2}{\pi }arccos(-\frac{||x-y||}{\sigma })-\frac{2}{\pi }\frac{||x-y||}{\sigma }(1-\frac{||x-y|{|}^2}{\sigma }{)}^{0.5}$$

12.Spherical Kernel

数学形式如下：
$$k(x,y)=1-\frac{3}{2}\frac{||x-y||}{\sigma }+\frac{1}{2}(\frac{||x-y|{|}^2}{\sigma }{)}^3$$

13.Wave Kernel

数学形式如下：
$$k(x,y)=\frac{\theta }{||x-y||}sin(\frac{||x-y||}{\theta })$$

14.Triangular Kernel [三角核函数]

三角核函数感觉就是多元二次核的特例，数学公式如下：
$$k(x,y)=-||x-y|{|}^d$$

15.Log Kernel [ 对数核]

对数核一般在图像分割上经常被使用，数学形式如下：
$$k(x,y)=-log(1+||x-y|{|}^d)$$

16.Spline Kernel

数学形式如下：
$$k(x,y)=1+x^{t}y+x^{t}ymin(x,y)-\frac{x+y}{2}min(x,y{)}^2+\frac{1}{3}min(x,y{)}^3$$

17.Bessel Kernel

数学形式如下：
$$k(x,y)=\frac{J_{v+1}(\sigma ||x-y||)}{||x-y|{|}^{-n(v+1)}}$$

18.Cauchy Kernel [ 柯西核]

柯西核来源于神奇的柯西分布，与柯西分布相似，函数曲线上有一个长长的尾巴，说明这个核函数的定义域很广泛，言外之意，其可应用于原始维度很高的数据上，数学形式如下：
$$k(x,y)=\frac{1}{||x-y|{|}^2/\sigma +1}$$

19.Chi-Square Kernel [ 卡方核]

卡方核，这是我最近在使用的核函数，让我欲哭无泪，在多个数据集上都没有用，竟然比原始算法还要差劲，不知道为什么文献作者首推这个核函数，其来源于卡方分布，数学形式如下：
$$k(x,y)=1-\sum _{k=1}^n\frac{(x_k-y_k{)}^2}{0.5(x_k+y_k)}$$
它存在着如下变种：
$$k(x,y)=\frac{x^{t}y}{||y+y|{|}_z}$$
其实就是上式减去一项得到的产物，这个核函数基于的特征不能够带有赋值，否则性能会急剧下降，如果特征有负数，那么就用下面这个形式：
$$sign(x^{t}y)k(|x|,|y|)$$

20.Histogram Intersection Kernel [ 直方图交叉核]

直方图交叉核在图像分类里面经常用到，比如说人脸识别，适用于图像的直方图特征，例如extended LBP特征其数学形式如下，形式非常的简单，数学形式如下：
$$k(x,y)=\sum _{k=1}^{n}min(x_k,y_k)$$

21.Generalized Histogram Intersection [广义直方图交叉核]

顾名思义，广义直方图交叉核就是上述核函数的拓展，形式如下：
$$k(x,y)=\sum _{k=1}^{n}min(|x_k{|}^{\alpha },|y_k{|}^{\beta })$$

22.Generalized T-Student Kernel [TS核]

TS核属于mercer核，其数学形式如下，这个核也是经常被使用的，数学形式如下：
$$k(x,y)=\frac{1}{1+||x-y|{|}^d}$$
23.贝叶斯公式Bayesian Kernel [贝叶斯核函数]
因为找不到贝叶斯核函数的形式，所以这里补充为贝叶斯公式，数学形式如下：
$$P(B_i|A)=\frac{P(B_i)P(A|B_i)}{{\sum }_{j=1}^{n}P(B_j)P(A|B_j)}$$

输入公式的我感觉快要爆炸了！ 上面第19个方程的第二种形式，不知道下标是什么，就写了一个Z

以下两个链接是我在输入公式的时候参考的链接：
Cmd Markdown 公式指导手册
使用CSDN的markdown编辑器插入数学公式

3.KPCA推导

注：以上为老师讲课时的PPT，直接拿来，多有得罪。使用了引用的格式，表示不是自己亲手制作的。
老师是会津大学裴岩(ペイ イ エン )。数据可视化着实教会了我很多东西，再次感谢。

1.关于以上PPT，跟着一步步推导即可，推导的过程注意矩阵形式的变化，不是很困难，而且我把当时我学习KPCA时浏览过的帖子放在下面，若是看不懂PPT可以去看链接的帖子。

2.KPCA困难之处在于：最后要得到的高维空间的数据是什么样子的，一般认为，KPCA就是对归一化的核矩阵进行PCA的操作，这么说没有错，但是最后得到的高维空间的数据跟PCA的不尽相同。

3.在这里，KPCA的最后一步，也就是PPT的最后一页，可以看到多处了λ的一项，而且最后这一步的表达不是完整的数据空间，只是其中的一行或者一列数据。最后的x’，可以是(x1,x2,······,xn)中的任何一个x，所以需要有这么多个列，然后变成一个新的矩阵，用这个矩阵才能得到最终的新数据。其中的u也不能仅仅当做一列数据，要对u的每一列都做变换 [1/(λ)^1/2 * u转置] 才可以。

核主成分分析的公式推导过程
核主成分分析（Kernel-PCA）
核PCA与PCA的精髓和核函数的映射实质

4.KPCA步骤

1. 通过核函数(线性核，多项式核，高斯核，指数核)计算出核矩阵K [设原始数据有m行，n列，则每一行看成X，跟自身及其他m-1行运算，得到m*m的矩阵]
2. 对于核矩阵K进行归一化，得到zero_k
3. 计算K的特征值特征向量data_e，data_v
4. 从对角阵data_e中提取特征值，并且赋值给data_e，对于data_e进行排序
5. 根据特征值矩阵data_e，对于特征向量矩阵data_v排序
6. 对于新排序的data_v的每一行除以对应行的data_e的值，赋值给新的矩阵v
7. 用归一化的核矩阵zero_k*v得到新的数据data_all
8. 此时的data_all的每个维度已经排好序，取一二列，就是第一第二主成分
9. [KPCA中的核矩阵与PCA中的协方差矩阵相比较，对于前者的处理多了一个步骤6]

5.KPCA数据

数据即是鸢尾花的150个数据，从MATLAB网站上可以找到，上一篇帖子里也有。
鸢尾花数据

6.KPCA代码

这里的代码使用的是高斯核函数。
将KPCA封装成了一个函数，返回处理好矩阵，没有舍弃任何维度。
绘制表格是一个函数，将三类数据分别绘制，便于观察。
第一个for循环是为了绘制不同σ值下的图表，一个figure9个图
可以选择性进行多次KPCA的处理
代码可以直接保存使用，至少在我的电脑上是可以运行的。

clc;
oridata=load('C:\Users\31386\Desktop\iris.csv');
data=oridata(:,2:5);
coldata=oridata(:,1);%先把第一列取出来
sigma=[3 3.5 4 4.5 5 5.5 5 10 100];%设置不同的σ的值

%利用不同的sigma值，绘制9个小图，在同一个figure里面
figure();
for i =1:9
    data_new=kpcafun(data,sigma(i));
    data_dif=[coldata,data_new(:,1:4)];
    %可选择性注释以下两行
    data_new=kpcafun(data_dif,sigma(i));
    data_dif=[coldata,data_new(:,1:4)];
    %可选择性注释以下两行
    data_new=kpcafun(data_dif,sigma(i));
    data_dif=[coldata,data_new(:,1:2)];
    
    hold on
    subplot(3,3,i)
    plottitle=['sigma=',num2str(sigma(i))];
    title(plottitle); 
    xlabel('X');
    ylabel('Y');

    paint(data_dif);
end

%绘制图表
function []=paint(data_dif)
[a b]=size(data_dif);
for i=1:a
    hold on
    if data_dif(i,1)==0
        plot(data_dif(i,2),data_dif(i,3),'r.','markersize',7);
    elseif data_dif(i,1)==1
        plot(data_dif(i,2),data_dif(i,3),'g.','markersize',7);
    elseif data_dif(i,1)==2
        plot(data_dif(i,2),data_dif(i,3),'b.','markersize',7);
    end
end
end

function [data_new]=kpcafun(data,sigma)
[a b]=size(data);
k=ones(a,a);
zero_m=ones(a,a)/a;%用于中心化

%求出核矩阵
for i=1:a
    x=data(i,:);
    for j=1:a
        y=data(j,:);
        k(i,j)=exp(-norm(x-y)^2 / (2*sigma^2));
    end
end

%核矩阵中心化得到新的矩阵
zero_k=k-zero_m*k-k*zero_m+zero_m*k*zero_m;

% 计算特征值与特征向量  data_v特征向量 data_e特征值
[data_v,data_e]=eig(zero_k); %data_e是一个对角阵
data_e=diag(data_e);

%排序
[dump,index]=sort(data_e,'descend');
data_e=data_e(index);
v=data_v(:,index);
% v=fliplr(data_v);%这种写法是不对的，当时因为这种写法使得结果异常

%取第一第二主成分
for i=1:a
    v(:,i)=v(:,i)/sqrt(data_e(i));
end
% data_all=v'*zero_k;
data_all=zero_k*v;
% data_all=data_all';
data_new=data_all;

end
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80

7.KPCA结果

1.进行一次KPCA
.

2.进行两次KPCA
.

3.进行三次KPCA
.

8.个人の理解

我感觉写着一篇要死了

刚开始学的时候，线性代数已经忘记了一部分，对于矩阵相关的只是也是云里雾里，机器学习的诸多算法，算法自身的推导过程并不是很难，唯一困难的地方就会矩阵变来变去，最后变成了一种人脑不能理解的形式，但总是有人可以理解的， 至少对于PCA、KPCA我现在是能够理解的，推导过程之中，想要的东西还有其中已知的量是一个什么样子的矩阵，是大概能够明白的。
KPCA是将低维非线性可分的数据转化为高维线性可分的数据，这个算法教给我的是一种思维的方式，倘若低维不可解的时候，可以不惜浪费计算量，将其升维，会发现问题变得很简单，就像下面这一道数学题一样：

计算：
$${\int }_{-\infty }^{+\infty }{e}^{-x^2}\mathrm{d}x$$
[偶函数，高斯曲线，一维不可解，有原函数，并不代表原函数可以写出来 ]
.
显然，有：
$${\int }_{-\infty }^{+\infty }{e}^{-x^2}\mathrm{d}x={\int }_{-\infty }^{+\infty }{e}^{-y^2}\mathrm{d}y$$
则：
$$I^2={\int }_{-\infty }^{+\infty }{e}^{-x^2}\mathrm{d}x{\int }_{-\infty }^{+\infty }{e}^{-y^2}\mathrm{d}y$$
$$={\iint }_D{e}^{-(x^2+y^2)}\mathrm{d}\sigma$$
$$={\int }_0^{2\pi }\theta \mathrm{d}\theta {\int }_0^{+\infty }{e}^{-r^2}r\mathrm{d}r$$
$$=2\pi \cdot \frac{1}{2}{\int }_0^{+\infty }{e}^{-r^2}\mathrm{d}{r}^2$$
$$=\pi$$
所以：
$$I=\sqrt{\pi }$$

我觉的上面的不定积分题目，与KPCA有异曲同工之妙。
2019年4月19日：
本来觉得没有希望的面试，竟然通过了，我说了我要文案策划，我把自己压箱底的诗词都拿了出来，最后问了一句，你高数多少，变成了数值策划 ，(づ｡◕‿‿◕｡)づ
写首诗吧：
$$乐也风吹柳，道也江畔走，来去无归处，罢撵足下狗。$$