Principal components analysis
这一讲，我们简单介绍Principal Components Analysis(PCA)，这个方法可以用来确定特征空间的子空间，用一种更加紧凑的方式（更少的维数）来表示原来的特征空间。假设我们有一组训练集{x(i);i=1,...m}<script type="math/tex" id="MathJax-Element-110">\{x^{(i)}; i=1,...m \}</script>，含有m个训练样本，每一个训练样本x(i)∈Rn<script type="math/tex" id="MathJax-Element-111">x^{(i)} \in \mathbb{R}^{n}</script>,其中(n≪m<script type="math/tex" id="MathJax-Element-112">n \ll m</script>),每一个n维的训练
样本意味着有n个属性，一般来说，这n个属性里面，会有很多是存在一定相关性的，也就是很多属性是冗余的，这就为特征的降维提供了可能，关键是如何确定多余的属性以及如何进行降维。

PCA为这个问题提供了一种解决途径，在做PCA之前，我们要先对数据做如下的预处理：

1: 求出训练集的均值向量：μ=1m∑mi=1x(i)<script type="math/tex" id="MathJax-Element-113">\mu=\frac{1}{m} \sum_{i=1}^{m}x^{(i)}</script>.

2: 用每一个训练样本减去均值向量，x(i)=x(i)−μ<script type="math/tex" id="MathJax-Element-114">x^{(i)}=x^{(i)}-\mu</script>.

3: 求出变换后的训练集的方差：σ2j=1m∑i(x(i)j)2<script type="math/tex" id="MathJax-Element-115">\sigma_{j}^{2}=\frac{1}{m} \sum_{i} (x_{j}^{(i)})^{2}</script>.

4: 再将训练集的样本做如下替换：x(i)j=x(i)j/σj<script type="math/tex" id="MathJax-Element-116">x_{j}^{(i)}=x_{j}^{(i)} / \sigma_{j}</script>.

上面的第1,2步确保了训练集的均值为0，第3,4步保证了训练集的方差为1，使得训练样本里的不同属性变换到同一个尺度上处理。给定一个单位向量u<script type="math/tex" id="MathJax-Element-117">u</script>和一个点x<script type="math/tex" id="MathJax-Element-118">x</script>，那么该点x<script type="math/tex" id="MathJax-Element-119">x</script>到单位向量的投影的长度为xTu<script type="math/tex" id="MathJax-Element-120">x^{T} u</script>，如果x(i)<script type="math/tex" id="MathJax-Element-121">x^{(i)}</script>是训练集里的一个样本，那么它在u<script type="math/tex" id="MathJax-Element-122">u</script>上的投影长度即为xTu<script type="math/tex" id="MathJax-Element-123">x^{T}u</script>到原点的距离，因此，为了能够让这些投影之间的方差最大，我们希望找到满足如下表达式的单位向量u<script type="math/tex" id="MathJax-Element-124">u</script>。

<script type="math/tex; mode=display" id="MathJax-Element-125">\begin{equation*} \begin{split} \frac{1}{m} \sum_{i=1}^{m} ((x^{(i)})^{T}u)^{2} & = \frac{1}{m} \sum_{i=1}^{m} u^{T}x^{(i)}(x^{(i)})^{T}u \\ & =u^{T} \left( \frac{1}{m} \sum_{i=1}^{m} x^{(i)}(x^{(i)})^{T} \right) u \end{split} \end{equation*}</script>

因为u<script type="math/tex" id="MathJax-Element-126">u</script>是单位向量，所以∥u∥2=1<script type="math/tex" id="MathJax-Element-127">\left \| u \right \|^{2}=1</script>，上式括号中的表达式即为均值为0的协方差矩阵(Σ=1m∑mi=1x(i)(x(i))T<script type="math/tex" id="MathJax-Element-128">\Sigma=\frac{1}{m} \sum_{i=1}^{m} x^{(i)}(x^{(i)})^{T}</script>)，为了使目标函数最大化，则u<script type="math/tex" id="MathJax-Element-129">u</script>应该取Σ<script type="math/tex" id="MathJax-Element-130">\Sigma</script>最大的特征值所对应的特征向量。

总之，我们应该取Σ<script type="math/tex" id="MathJax-Element-131">\Sigma</script>的主特征向量，如果我们希望将原来的数据空间映射到一个低维的子空间，我们可以选择Σ<script type="math/tex" id="MathJax-Element-132">\Sigma</script>的前k个特征向量作为子空间的基向量，那么这k个特征向量u1,u2,...uk<script type="math/tex" id="MathJax-Element-133">u_{1}, u_{2}, ... u_{k}</script>组成了新空间的基向量。那么我们可以将原来的训练样本x(i)<script type="math/tex" id="MathJax-Element-134">x^{(i)}</script>映射到新的特征空间：

<script type="math/tex; mode=display" id="MathJax-Element-81"> y^{(i)}=\begin{bmatrix} u_{1}^{T}x^{(i)} \\ u_{2}^{T}x^{(i)} \\ \vdots \\ u_{k}^{T}x^{(i)} \end{bmatrix} \in \mathbb{R}^{k} </script>

因此，虽然x(i)<script type="math/tex" id="MathJax-Element-82">x^{(i)}</script>是一个n维的向量，但是y(i)<script type="math/tex" id="MathJax-Element-83">y^{(i)}</script>变成了维数更低的向量，所以PCA是一种降维算法，其中特征向量u1,u2,...uk<script type="math/tex" id="MathJax-Element-84">u_{1}, u_{2}, ... u_{k}</script>称为训练集的
前k个主分量。

参考来源：

Andrew Ng, “Machine Learning”, Stanford University.