Differences

This shows you the differences between two versions of the page.

--- keynote:2011-lesson02 [2011/06/24 11:11]
11021008 [主成分分析（PCA）]
+++ keynote:2011-lesson02 [2023/08/19 21:02] (current)
@@ Line 1: / Line 1: @@
+====== 第二课 主成分分析 ======
+===== 回归复习：多项式拟合计算 =====
+问题描述：给出包含$n$对采样点的集合，找到一个M阶多项式函数$y(x) = \sum_{j=0}^{M}{w_jx^j}$，使其与原采样点集合拟合
+若令$\mathbf{p}(x) = \left(x^0, x^1, \cdots, x^M\right)$，
+$\mathbf{w}(x) = \left(\matrix{w_0\\w_1\\\vdots\\w_M}\right)$，
+$\mathbf{y} = \left(\matrix{y_1\\y_2\\\vdots\\y_n}\right)$，
+则对于每一采样点$(x_j, y_j)$，所求的多项式函数取值为$y_j = \mathbf{p}(x_j)\cdot \mathbf{w}$，
+设$\mathbf{P}(\mathbf{x}) = \left(\matrix{\mathbf{p}(x_1)\\\mathbf{p}(x_2)\\\vdots\\\mathbf{p}(x_n)}\right)$，
+使得函数$y(x)$与采样点集合拟合最好（公式1）：
+\[\underset{\mathbf{w}}{\mathrm{argmin}}\|\mathbf{y}-\mathbf{P}(\mathbf{x})\cdot \mathbf{w}\|^2\]
+利用最小二乘法可求得$\mathbf{w}$：
+\[\mathbf{w} = (\mathbf{P}^\mathrm{T}\mathbf{P})^{-1}\mathbf{P}^\mathrm{T}\mathbf{y}\]
+===== 回归复习：基函数 =====
+若将上述$\mathbf{p}(x)$中各项$x^i$换成任意的函数$h_j(x)$，即构成$\mathbf{h} = \left(h_1(x), h_2(x), \cdots, h_M(x)\right)$，
+这些$h_j(x)$就称为基函数
+如傅立叶变换中的基函数为：$h_j(x) = \left\{\begin{array}{ll}\cos(jx/2) & j是偶数\\\sin((j+1)x/2) & j是奇数\end{array}\right.$
+  * 将傅立叶变换中的$e$展开，积分号看为连加号，则变为$f(x) = \sum{w_jh_j(x)}$，其中的$h_j(x)$就是上面定义的基函数
+  * 不同的变换操作（如傅立叶变换、余弦变换、小波变换）只是使用的基函数不同
+  * 若基函数是正交的，即${\mathbf{H}^\mathrm{T}\mathbf{H} = 1}$，则上述公式1变为$\mathbf{w} = \mathbf{H}^\mathrm{T}\mathbf{y}$，因此计算$\mathbf{w}$更简便
+===== 回归复习：奇异值分解(SVD) =====
+==== 理论描述 ====
+假设''M''是一个''m×n''阶矩阵，其中的元全部属于域
+''K''，也就是实数域或复数域。如此则存在一个分解使得
+:<math>M = U \∑ V^*, \,</math>
+其中''U''是''m×m''阶酉矩阵；Σ是半正定''m×n''阶对角矩阵；而''V
+*''，即''V''的共轭转置，是''n×n''阶酉矩阵。这样的分解就称作''M''的'''奇异值分解'''。
+Σ对角线上的元素Σ<sub>''i'',''i''</sub>即为''M''的'''奇异值'''。
+常见的做法是为了奇异值由大而小排列。如此Σ便能由''M''唯一确定了。 (虽然''U''和''V''仍然不能确定。)
+==== 直观的解释 ====
+在矩阵''M''的奇异值分解中
+: <math>M = U\Sigma V^*, \,</math>
+* ''V''的列(columns)组成一套对''M''的正交"输入"或"分析"的基向量。这些向量是''M*M''的特征向量。
+* ''U''的列(columns)组成一套对''M''的正交"输出"的基向量。这些向量是''MM*''的特征向量。
+* Σ对角线上的元素是奇异值，可视为是在输入与输出间进行的纯量的"膨胀控制"。这些是''MM*''及''M*M''的特征值，并与''U''和''V''的行向量相对应。
+==== 几何意义 ====
+因为''U'' 和''V'' 向量都是单位化的向量,
+我们知道''U''的列向量''u''<sub>1</sub>,...,''u<sub>m</sub>''组成了''K''<sup>''m''</sup>空间的一组标准正交基。同样，''V''的列向量''v''<sub>1</sub>,...,''v<sub>n</sub>''也组成了''K''<sup>''n''</sup>空间的一组标>准正交基(根据向量空间的标准点积法则).
+线性变换''T'': ''K''<sup>''n''</sup> →
+''K''<sup>''m''</sup>，把向量''x''变换为''Mx''。考虑到这些标准正交基，这个变换描述起来就很简单了:
+''T''(''v<sub>i</sub>'') = ''σ<sub>i</sub> u<sub>i</sub>'', for ''i'' = 1,...,min(''m'',''n''),
+其中''σ<sub>i</sub>'' 是对角阵Σ中的第''i''个元素; 当''i'' > min(''m'',''n'')时，''T''(''v''<sub>''i''</sub>) =
+。
+这样，SVD理论的几何意义就可以做如下的归纳：对于每一个线性映射''T'': ''K''<sup>''n''</sup> →
+''K''<sup>''m''</sup>，''T''把''K''<sup>''n''</sup>的第''i''个基向量映射为''K''<sup>''m''</sup>的第''i''个基向量的非负倍数,然后将余下的基向量映射为零向量。对照这些基向量，映射''T''就可以表示为一个非负对角阵。
+==== 应用 ====
+=== 求伪逆 ===
+奇异值分解可以被用来计算矩阵的伪逆。若矩阵 ''M'' 的奇异值分解为 <math> M = U\Sigma V^*</math>，那么 ''M''
+的伪逆为
+:<math> M^+ = V \Sigma^+ U^*, \,</math>
+其中 Σ<sup>+</sup>
+是将Σ转置，并将其主对角线上每个非零元素都求倒数得到的。求伪逆通常可以用来求解线性最小平方问题。
+=== 平行奇异值模型 ===
+把频率选择性衰落信道进行分解.
+=== 值域、零空间和秩 ===
+=== 矩阵近似值 ===
+奇异值分解在统计中的主要应用为主成分分析（PCA），它是一种数据分析方法，用来找出大量数据中所隐含的“模式”,它可以用在模式识别，数据压缩等方面。PCA算法的作用是把数据集映射到低维空间中去。
+数据集的特征值（在SVD中用奇异值表征）按照重要性排列，降维的过程就是舍弃不重要的特征向量的过程，而剩下的特征向量张成空间为降维后的空间。
+===== 主成分分析（PCA）=====
+主成分分析是一种通过线性变换将高维的数据投影到低维空间中的方法，这一方法的目标在于寻找在最小均方意义下能够代表原始数据的投影方法。
+假设有n个d维的样本$\mathbf{x_1}$，$\mathbf{x_2}$，...，$\mathbf{x_n}$，如何能够用仅仅一个d维向量$\mathbf{x_0}$来最好的代表这n个样本，或者更确切的说我们希望这个代表向量$\mathbf{x_0}$和各个样本的距离平方之和越小越好。定义平方误差准则函数$J_0(\mathbf{x_0})$如下:
+\[J_0(\mathbf{x_0})=\sum_{k=1}^{n}||\mathbf{x_0}-\mathbf{x_k}||^2\]
+我们要寻找能够使得$J_0(\mathbf{x_0})$最小化的那个d维向量的$\mathbf{x_0}$。容易想到，这个$\mathbf{x_0}$就是样本均值$\mathbf{x_m}$
+样本均值是样本数据集的零维表达。它非常简单，但是缺点是不能反映样本之间的不同。通过把全部样本向通过样本均值的一条直线作投影我们能够得到代表全部样本的一个一维向量。让$\mathbf{e}$表示这条通过样本均值的直线上的单位向量，那么这条直线的方程可以表示为
+\[\mathbf{x}=\mathbf{m}+w\mathbf{e}\]
+其中w为一个实数的标量，表示直线上的某个点离开$\mathbf{m}$的距离。如果用$\mathbf{x}=\mathbf{m}+w_k\mathbf{e}$表示$\mathbf{x_k}$，那么通过最小化平方误差准则函数，我们能到得到一组最优的w<sub>k</sub>的集合，其过程如下：
+\[J_1(w_1,...,w_n,\mathbf{e})=\sum_{k=1}^n||(\mathbf{m}+w_k\mathbf{e})-
+\mathbf{x}_k||^2
+=\sum_{k=1}^{n}w_k^2-2\sum_{k=1}^{n}w_k\mathbf{e}^t(\mathbf{x}_k-\mathbf
+{m})+\sum_{k=1}^{n}||\mathbf{x}_k-\mathbf{m}||^2\]
+通过对w<sub>k</sub>求偏导，并且令结果为0，我们得到
+\[w_k=\mathbf{e}^t(\mathbf{x}_k-\mathbf{m})\]
+从几何上说，这个结果告诉我们只需要把向量$\mathbf{x}_k$向通过样本均值的直线$\mathbf{e}$作垂直投影就能够得到最小方差结果。如何找到直线$\mathbf{e}$的最优方向。问题的求解过程引入了所谓的“散布矩阵”(Scatter matrix)
+\[\mathbf{S}=\sum_{k=1}^{n}(\mathbf{x}_k-\mathbf{m})(\mathbf{x}_k-\mathbf
+{m})^t\]
+事实上这个矩阵就是样本协方差矩阵的n-1倍。把根据以上的公式得到的w<sub>k</sub>
+代入$J_1(w_1,...,w_n,\mathbf{e})$我们得到
+\[J_1(\mathbf{e})=\sum_{k=1}^{n}w_k^2-2\sum_{k=1}^{n}w_k\mathbf{e}^t(\mathbf
+{x}_k-\mathbf{m})+\sum_{k=1}^{n}||\mathbf{x}_k-\mathbf{m}||^2=-\sum_{k=1}^n
+[\mathbf{e}^t(\mathbf{x}_k-\mathbf{m})]^2+\sum_{k=1}^{n}||\mathbf{x}_k-
+\mathbf{m}||^2
+=-\mathbf{e}^t\mathbf{S}\mathbf{e}+\sum_{k=1}^{n}||\mathbf{x}_k-\mathbf{m}||
+^2
+\]
+在上式中显然使得J<sub>1</sub>最小的那个向量$\mathbf{e}$，能够使$\mathbf{e}^t\mathbf{S}\mathbf{e}$最大。我们使用拉格朗日乘子法来最大化$\mathbf{e}^t\mathbf{S}\mathbf{e}$，约束条件为等式$||\mathbf{e}||=1$。用λ表示拉格朗日乘子，有
+\[u=\mathbf{e}^t\mathbf{S}\mathbf{e}-\lambda(\mathbf{e}^t\mathbf{e}-1)\]
+对$\mathbf{e}$求偏导，并且令结果为0，得到$\mathbf{e}$必须为散布矩阵的特征向量:
+\[\mathbf{S}\mathbf{e}=\lambda\mathbf{e}\]
+所以为了最大化$\mathbf{e}^t\mathbf{S}\mathbf{e}$，我们选取散布矩阵最大特征值对应的那个特征向量作为投影直线$\mathbf{e}$的方向。这一结论可以立刻从一维空间的映射推广到p为空间的映射：
+\[\mathbf{x}=\mathbf{m}+\sum_{i=1}^{p}w_i\mathbf{e}\]
+其中p≤d。可以证明新的误差准则函数
+\[J_p=\sum_{k=1}^{n}||(\mathbf{m}+\sum_{i=1}^{p}w_{ki}\mathbf{e}_i)-\mathbf{x}_k||^2\]
+在向量$\mathbf{e}_1$，$\mathbf{e}_2$，...，$\mathbf{e}_p$为散布矩阵的p个最大特征值对应的特征向量的时候取到最小值。因为散布矩阵是实对称矩阵，因此这些特征向量都是正交的。这些特征向量构成了代表任一向量$\mathbf{x}$的基向量。系数w<sub>k</sub>就是向量$\mathbf{x}$对应于基$\mathbf{e}_i$的系数，被称为主成分。从几何上说，样本点$\mathbf{x}_1$，...，$\mathbf{x}_n$在d维空间形成了一个d维椭球形状的云团，那么散布矩阵的特征向量就是这个云团的主轴。主成分分析通过提取云团散布最大的那些方向的方法，达到对特征空间进行降维的目的。
+===== 本章贡献者 =====
+<note important> 本节编撰作者(请大家在这里报到)：
+  * [[xxxx@xxx.xxx|俞立呈]] (ID: 11021007)，   编写了回归复习等内容
+  * [[ltnwgl@gmail.com|王耿亮]] (ID: 11021009)，   编写了奇异值分解
+  * [[litaozju@zju.edu.cn|李涛]] (ID: 11021008)，   编写了主成分分析
+  * [[xxxx@xxx.xxx|AuthorName4]] (ID: xxxxxxxxx)，   编写了...
+  * [[xxxx@xxx.xxx|AuthorName5]] (ID: xxxxxxxxx)，   编写了...
+  * [[xxxx@xxx.xxx|AuthorName6]] (ID: xxxxxxxxx)，   编写了...
+浙江大学2008-2011版权所有，如需转载或引用，请与[[zhx@cad.zju.edu.cn | 编者联系]]。
+</note>

Applied Mathematics for Computer Science

User Tools

Site Tools

Differences

Page Tools