Part1-降维
目标1：数据压缩
二维降为一维
如图，假设我们收集了这样一个数据集，它有很多特征，图中画出了其中两个，其对应的是同一物体的英寸长度和厘米长度，它们都表示基本长度，因此我们可能需要把数据减少到一维。
三维降到二维
如图，降维方法就是把所有数据都投影到一个二维平面上
目标2：数据可视化
假设我们收集了许多统计数据的大数据集，如图是全世界各个国家的情况。假设有这样一个巨大数据集，每个国家有50个特征，\(x\in \mathbb R^{50}\)
那么，有什么方法可以让我们更好地理解这些数据呢？如何可视化这些数据？
为了将数据在平面上进行展示， 就需要将数据从50维降低到2维，这样就可以画一个二维图来表示它
主成分分析问题陈述
对于降维问题，目前较流行、常用的算法是主成分分析方法(Principal components analysis, PCA)
PCA问题的公式描述，换句话说，我们会试着用公式准确地表述PCA的用途。
如图，假设有一个像这样的数据集
这是一个\(x \in \mathbb R^2\)数据集，假如我们想对数据进行降维，从二维降到一维，也就是找一条好的投影这些数据的直线，在应用PCA之前，常规的做法是对于每个点到这条直线的距离，先进行均值归一化和特征规范化，使得各特征量均值为0，并且在其数值可比较的范围内。而PCA就是用来找一条这样的让每个点到其距离和最小的直线。
正式的说，就是：我们要试着找一个向量，假设是向量\(u^{(i)} \in \mathbb R^n\)，要找一个数据投影后能够最小化投影误差的方向。
更通常的，我们会有N维数据，并且想将其降到K维：找k个向量\(u^{(1)},u^{(2)},\cdots,u^{(k)}\)，然后将这些数据投影到这k个向量展开的线性子空间上，然后最小化投影误差
注：PCA不是线性回归，尽管它们看上去有一些相似。但我们处理线性回归时，当给定某个输入特征量x时，用来预测出变量y的值，因此，在线性回归中，我们要做的是拟合一条直线来最小化点和直线之间的平方误差，所以要最小化的是图中的蓝线之和的平方。而在处理PCA中，要最小化的是图中绿色线长度和的平方，它们是正交距离。
此外，线性回归需要用一些特征去预测一个结果，而PCA是同等对待所有特征
PCA算法
数据预处理
训练集：\(x^{(1)},x^{(2)},\cdots,x^{(m)}\)
预处理（特征绽放/均值标准化）：
\(\mu_j = \frac{1}{m}\sum_{i=1}^m x_j^{(i)}\)
使用\(x_j-\mu_j\)代替每个\(x_j^{(i)}\)
如果不同特征尺度有较大的不同，则需要对每个特征进行缩放\(x_j^{(i)}:=\frac{x_j^{(i)}-\mu_j}{s_j}\)(\(s_j\)是特征j的标准偏差)
PCA算法
将数据从n维降低到k维
计算协方差：\(\Sigma = \frac{1}{m} \sum_{i=1}^n (x^{(i)})(x^{(i)})^T\)
计算矩阵\(\Sigma\)的特征向量：\([U,S,V]=svd(\Sigma)\)
\(svd\)代表奇异值分解(Singular value decomposition)，这是一个更加高级的分解算法，也是一个高级的线性代数的应用。
\(\Sigma\)是一个\(n \times n\)的矩阵，三个输出\(U,S,V\)，通常需要的是\(U\)，这个\(U\)矩阵也是一个\(n\times n\)的矩阵
\(U = \left[ \begin{matrix} | & | & \cdots &| \\ u^{(1)} & u^{(2)} & \cdots & u^{(n)} \\ | & | & \cdots & |\end{matrix} \right]\)
如果想降维到k维，则我们需要取得\(u^{(1)}\)到\(u^{(k)}\)向量作为投影数据的方向
\(z=\left[ \begin{matrix} | & | & \cdots &| \\ u^{(1)} & u^{(2)} & \cdots & u^{(k)} \\ | & | & \cdots & |\end{matrix} \right]^TX\)
\(z\in R^{k\times 1}\)
总结
为了确保每个特征都是均值为0的，我们需要进行均值标准化，在均值标准化后，任选特征缩放，预处理完成后，我们计算协方差：
\(\Sigma = \frac{1}{m} \sum_{i=1}^m (x^{(i)})(x^{(i)})^T\)
\([U,S,V]=svd(\Sigma)\)
\(U_{reduce}=U[:, 1:k]\)
\(z=U_{reduce}^Tx\)
压缩重构
\(z=U_{reduce}^Tx\)
而如果给定一个\(z^{(i)}\)，我们怎么回到原来的二维空间？
\(z\in \mathbb R \rightarrow x\in \mathbb R^2\)
\(X_{approx}=U_{reduce}\cdot z\)
\(X \approx X_{approx}\)
选择主成分的数量
\(均方投影误差:\frac{1}{m}\sum_{i=1}^m||x^{(i)}-x^{(i)}_{approx}||^2\)
\(数据总差异:\frac{1}{m}\sum_{i=1}^m ||x^{(i)}||^2\)
通常，选择使得下式成立的最小\(k\)
\(\frac{\frac{1}{m}\sum_{i=1}^m||x^{(i)}-x_{approx}^{(i)}||^2}{\frac{1}{m}\sum_{i=1}^m||x^{(i)}||^2} \le 0.01\ (1\%)\)
或者说是99%的方差被保留下来了
算法：
尝试\(k=1\)的PCA
计算：\(U_{reduce},z^{(1)},z^{(2)},\cdots,z^{(m)},x_{approx}^{(1)},\cdots,x_{approx}^{(2)}\)
检查：\(\frac{\frac{1}{m}\sum_{i=1}^m||x^{(i)}-x_{approx}^{(i)}||^2}{\frac{1}{m}\sum_{i=1}^m||x^{(i)}||^2} \le 0.01?\)
如果不成立，则换\(k=2\)，如此继续，找到使不等式成立的最小k
但是，显然，这个算法效率并不高，好在SVD已经给了我们更容易计算的数值：
\([U,S,V]=svd(\Sigma)\)
其中的S是一个对角矩阵：\(S = \left[ \begin{matrix} s_{11} & & & \\ & s_{22} & & \\ & & \cdots & \\ & & & s_{nn} \end{matrix} \right]\)
然后，对于给定的k，就可以这样写不等式：
\(1-\frac{\sum_{i=1}^k S_{ii}}{\sum_{i=1}^nS_{ii}} \le 0.01 \Leftrightarrow \frac{\sum_{i=1}^k S_{ii}}{\sum_{i=1}^nS_{ii}} \ge 0.99\)
总结：
- \([U,S,V]=svd(\Sigma)\)
- 选择使如下不等式成立的最小\(k\)值：\(\frac{\sum_{i=1}^k S_{ii}}{\sum_{i=1}^nS_{ii}} \ge 0.99\)
PCA应用中的建议
加速监督学习
我们经常使用PCA对监督学习进行加速，假设有一个监督学习问题，如下：
\((x^{(1)},y^{(1)}),(x^{(2)},y^{(2)}),\cdots,(x^{(m)},y^{(m)})\)
假设其中的\(x^{(i)}\)具有很高的维度，则可以使用PCA减少数据的维度，从而使得算法运行更加高效：
抽取输入\(x\)得到：
未标签数据集：\(x^{(1)},x^{(2)},\cdots,x^{(m)} \in \mathbb R^{10000}\)
经过PCA算法后得到：
数据的低维表示：\(z^{(1)},z^{(2)},\cdots,z^{(m)} \in \mathbb R^{1000}\)
新的训练集：
\((z^{(1)},y^{(1)}),(z^{(2)},y^{(2)}),\cdots,(z^{(m)},y^{(m)})\)
注：映射\(x^{(i)} \to z^{(i)}\)只能通过在训练集上运行PCA来定义，而通过学习PCA得到的参数，我们应该只在训练集上拟合，而不是在交叉验证集或测试集上，而定义后的映射，则可以应用到交叉验证集和测试集上
PCA的应用
- 压缩
- 降低存储数据所需内存或硬盘空间
- 加速算法学习
- 可视化
PCA的错误使用：预防过拟合
使用\(z^{(i)}\)代替\(x^{(i)}\)来降低特征数量\(k<n\)
因此，更少的特征，更少可能的过拟合
这样，或许表现上看是有用的，但是它并不是一个好的解决过拟合的方法
相反，如果想解决过拟合，还是使用正则化来处理更好。
PCA有时会被滥用
机器学习系统的设计：
- 获得训练集
- 运行PCA
- 尝试逻辑回归
- 测试测试集
然而，在写下这样一个包含PCA的项目计划之前，应该先问一问，如果不使用PCA而是直接去进行会怎样？
在实现PCA之前 ，应该首先直接做我们想做的事首先考虑使用最原始的数据\(x^{(i)}\)，只要这么做不能达到目的时才考虑使用PCA和\(z^{(i)}\)，不要一开始就花大量时间去应用PCA。