PCA主成分分析降维的理解

西瓜书的说明

数据$x_i$原始维度为d（d*1的矩阵），需要使其降维到d’维的$z_i$。如果当一系列样本点$X=(x_1,x_2,…,x_m)$（显然$X$为一个d*m的矩阵）距离要降维到的超平面足够近（符合降维需求），并使X中每个样本降维后足够分散（否则降维就没有什么意义了）。为了方便讨论，不妨使$X$已中心化，即$\sum_ix_i=0$。

所以我们需要找到一个合适的d*d的变换矩阵$W=(w_1,w_2,…,w_d)$对样本点进行坐标系变换，使其映射到d维空间（同等维度），$w_i$为标准正交基向量，即$w_i^Tw_i=1$（显然$W^TW=I_d$）且当$i\neq j$时$w_i^Tw_j=0$。将$x_i$被变换到这个新坐标系后得到一个在新的坐标系下的的d维数据$y_i=(y_{i1};y_{i2};…;y_{id})$，$y_{ij}=w_j^Tx_i$，$y_i=W^Tx_i$。

若丢弃$y_i$其中的一些维度。可以得到$z_i=(z_{i1};z_{i2};…;z_{id‘})$，$z_i=W^Tx_i$（此处的$W=(w_1,w_2,…,w_d’)$是上面的d*d矩阵$W$去除相应维度得到的d*d’矩阵，之后的$W$以d*d’维度的为准），$d’<d$，则基于投影重构的n维新样本点为$\hat{x_i}=\sum_{j=1}^{d’}z_{ij}w_j=Wz_i$。

或者可以更简练地说

找到一个合适的d*d’的变换矩阵$W=(w_1,w_2,…,w_{d’})$对样本点进行降维映射（或者说投影），使原始维度为d的数据$x_i$映射为d’维的$z_i$。和上面一样，也可以得到

$$
w_i^Tw_i=1\
W^TW=I_{d’}\
w_i^Tw_j=0,i\neq j\
z_i=W^Tx_i\
\hat{x_i}=\sum_{j=1}^{d’}z_{ij}w_j=Wz_i
$$

举个降维投影的例子

举个从二维空间投影到一维空间的例子。比如有个代表$(0,1)$的2*1的二维列向量
$$
x=\left[ \begin{array}{cc}
0\
1
\end{array}
\right ]
$$
要将它投影到一个在二维的超平面（也就是一条直线）上成为一个一维数据。假设超平面的向量为$(\frac{\sqrt 3}{2},\frac{1}{2})$，也就是一个与x轴正方向成$30^\circ$的直线，那么投影矩阵即为超平面的列向量表示
$$
W=\left[ \begin{array}{cc}
\frac{\sqrt 3}{2}\
\frac{1}{2}
\end{array}
\right ]
$$
投影后得到的一维向量为
$$
z=W^Tx=\left[ \begin{array}{cc}
\frac{\sqrt 3}{2}, \frac{1}{2}
\end{array}
\right ]
\left[ \begin{array}{cc}
0\
1
\end{array}
\right ]
=[\frac{1}{2}]
$$
映射回二维空间
$$
\hat{x}=Wz=
\left[ \begin{array}{cc}
\frac{\sqrt 3}{2}\
\frac{1}{2}
\end{array}
\right ]
[\frac{1}{2}]
=
\left[ \begin{array}{cc}
\frac{\sqrt 3}{4}\
\frac{1}{4}
\end{array}
\right ]
$$
直观上可以理解为，通过$(0,1)$（也就是$x$)向一个途径$(0,0)$与$(\frac{\sqrt 3}{2},\frac{1}{2})$（也就是$W$）的直线做垂线，从$(0,0)$到垂足的距离为$\frac{1}{2}$（也就是$z$），垂足坐标为$(\frac{\sqrt 3}{4},\frac{1}{4})$（也就是$\hat{x}$）

开始推导

由于样本点距离要降维到的超平面足够近，也就是说原样本点$x_i$和重构后的样本点$\hat{x_i}$之间的距离应尽可能小。换句话说，也就是要最小化所有样本的总距离差$\sum_{i=1}^{m}||\hat{x_i}-x_i||2$，即最小化$\sum{i=1}^{m}\left|WW^Tx_i-x_i\right|2$，即最小化
$$
\sum{i=1}^{m}\left|\sum_{j=1}^{d’}z_{ij}w_j-x_i\right|_2
$$

推导部分由于忘记了大量包括但不限于如何处理转置的矩阵乘法展开之类的线代知识，只能看着南瓜书上对10.14式的推导一边惊叹一边无地自容……总之可推出上式等于
$$
-\sum_{i=1}^{m}z_i^Tz_i+\sum_{i=1}^{m}x_i^Tx_i
$$
其中$\sum_{i=1}^{m}x_i^Tx_i$为一个常数（取决于样本集而非模型），所以上式可写为
$$
const-\sum_{i=1}^{m}z_i^Tz_i
$$
将$z_i=W^Tx_i$代入可化为
$$
const-\left(W^T\left(\sum_{i=1}^{m}x_ix_i^T\right)W\right)^T
$$
所以目标为最小化

$$
-\left(W^T\left(\sum_{i=1}^{m}x_ix_i^T\right)W\right)^T\
s.t. W^TW=I
$$

设
$$
f(W)=-\left(W^T\left(\sum_{i=1}^{m}x_ix_i^T\right)W\right)^T\
g(W)=(W^TW-I)^T
$$

使用拉格朗日乘子法，若要使$f(x)$最小同时满足$g(x)=0$，取$d’*d’$对角矩阵$\Lambda$定义拉格朗日函数
$$
L(W,\Lambda)=f(W)+g(W)\Lambda
$$
即
$$
L(W,\Lambda)=-\left(W^T\left(\sum_{i=1}^{m}x_ix_i^T\right)W\right)^T+\left(\Lambda^T(W^TW-I)\right)^T
$$

令对$W$求微分结果为0，利用矩阵微分公式$\frac{\partial}{\partial X}(X^TBX)^T=BX+B^TX$与$\frac{\partial}{\partial X}(BX^TX)^T=XB^T+XB$可得到
$$
\frac{\partial L}{\partial W}=-2(XX^TW)+W\Lambda^T+W\Lambda=-2(XX^TW)+2W\Lambda=0
$$

即
$$
XX^TW=W\Lambda
$$
展开即得
$$
XX^Tw_i=\lambda_i w_i
$$
此式为矩阵特征值和特征向量的定义式，其中$\lambda_i,w_i$分别表示矩阵$XX^T$的特征值和单位特征向量 。取前d’大的特征值对应的单位特征向量即可得到$W$

把一个jpg变成png，让它的部分元素可以随背景改变颜色

在线版

https://laurence-042.github.io/color-change-image/

这个应用已更新到可以正式使用的程度，进行恰当标记后处理得到的图片中，被标记区域的颜色将随背景颜色变化而变化，而且会一定程度上地保留变色区域的阴影高光与花纹。具体保留效果取决于原图相应区域的颜色，颜色越接近平和的灰色效果越好。

这个应用的功能包括：

  • 使用二次贝塞尔曲线标记选区，可调阈值的相似颜色标记选区。
  • 将选区作为加工范围，或者使用选区操作蒙版后将蒙版作为加工范围。
  • 使用RGB色域修改输出图片的背景色，作为变色图效果的预览。
  • 使用内置的几个背景图片作为输出图片的预览背景。
  • 使用本机上传图片作输出图片的预览背景。

个人感觉现在唯一的更新点差不多就是“将输出图片png和背景一起导出为jpg”，但由于几种背景的显示逻辑不同，这个功能做起来挺麻烦的，所以短期内不准备继续更新这个应用了。除此之外，一开始我只准备让这个应用可以处理整张图就行，后来的加工区域标记功能全是半路加上的，所以这个项目的代码结构非常糟糕，我不想再被自己的代码恶心了（这个是不更新主要原因）

如果你对这个玩具的灵感来源与原理感兴趣

灵感来源

实际上，这个项目的灵感来源是半年前QQ群里刷屏的几张图，其特点是图片中的元素（比如丝袜，衣服之类的）的颜色会随着聊天气泡的颜色（也就是背景色）变化。比如说那张丝袜图，如果聊天气泡是黑色的，丝袜就是黑色的；聊天气泡是白色的，丝袜就是白色的。

关键是，变色部分的阴影是被完美地保留了的，这不是简单的抠图所能做出来的。我猜想可能是画师在画图时预先设定了一个背景色，然后将阴影之类的上完色之后去除背景色，并以png格式导出的方式做出来的。

但我觉得我们可以自己动手试着做一个工具出来，使其可以自动将正常的jpg加工成那种变色图。就这样，这个纯属娱乐的项目就开工了。

思路

如果纯色底图A加上带透明通道的图B可以得到很和谐的图C，那么可不可以把现有的无透明通道的图C拆成纯色底图A与透明通道图B？

如果已知一个图片的长宽，那么就能把图片转成一维点阵向量的形式（就像二维数组在内存中的真实存放方式是按行拼接在一起的一维数组一样），那么就是向量分析了。A为元素为三维向量（RGB）的N维向量（N为长宽乘积），B为元素为四维向量（RGBA）的N维向量，C为元素为三维向量的N维向量。为了方便起见，我们将三维向量RGB当作Alpha值为1的RGBA，这样ABC的形式都一样了。

假设abc为ABC中位置相同的三个元素，下标的RGBA分辨代表红绿蓝透明通道，根据叠加的原理，我们可以得到

与的计算方式同

将带入上式可以得到

显然叠加是毫无悬念了，但如果我们要拆分，信息是否足够？

这个式子中的已知量有目标颜色，希望拆出的颜色，但都是未知量，它绝对没有一个唯一解。

这似乎很令人沮丧，这表示我们没有唯一的拆分方案。但是如果我们给它加一点限制呢？

把R通道的公式变一下形

显然，b的色彩约浓烈，其Alpha值越小，透明度越高。所以如果我们总是要求b的透明度尽可能高，那么就应该使尽可能大，比如当c的通道大于a的时直接设为255，否则设为0，来试一下？

于是这个项目就这么被写出来了。不过当它把某个通道值非常极端（比如0或255这样的）的颜色当作A图的颜色进行处理时，效果很不理想，几乎纯黑也不咋样，只有对非常适中的颜色效果才比较好。

举例来说的话，p站id为59851275的那个作品的整体构图和衣服颜色就很适合进行处理，而69740563这样稍显复杂且衣服颜色过渡很柔和的就无法得到预期的效果了。

附言

顺便一提，我按照Python3，C++，Java，JavaScript的顺序用同样的算法实现了四版的程序。

处理同一张图片的用时如下：

  • Python3：40+分钟
  • C++：Debug版29秒，Release版2秒
  • Java：28秒
  • JavaScript：7秒

说实话，我以前一直以为Python3和JS速度差不多，而且都远低于Java来着……不过也可能是因为其他三版用的都是OpenCV，而JS用的是Canvas的ImageData的缘故？下次我试图写点计算量不小的玩具时也许会优先考虑JS了。