《线性代数及其应用》笔记20.主成分分析法.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "# 主成分分析法\n",
    "$\\quad$我们在介绍[线性变换](《线性代数及其应用》笔记08.矩阵的几何解释-线性变换.ipynb)的时候提及过，矩阵相乘是可以对数据做降维的。pca的目的就是对数据做一次投影，将高维数据投影至低维，同时保持数据集中的对方差贡献最大的特征。\n",
    "## 1.协方差矩阵\n",
    "$\\quad$我们将待处理的数据写成一个矩阵，称之为**观测矩阵**，矩阵中每一行代表一个属性，每一列代表一个观测样本。例如一批数据是关于$N$个大学生的身高和体重的，$\\mathbf{X}_{i}$代表观测向量。那么观测矩阵的形式为：\n",
    "\n",
    "<img src=\"./_image/20_1.png\" width=\"100\" height=\"50\" />  \n",
    "\n",
    "可以看到每个样本均可看成是一个向量$\\mathbf{X}_{i}$，$\\mathbf{X}_{i}=(x_1,…,x_N)$。  \n",
    "$\\quad$令$[\\mathbf{X}_{1} \\cdots \\mathbf{X}_{N}]$是一个$p\\times N$观测矩阵，观测向量的样本均值$M$为：\n",
    "\n",
    "$$\\mathbf{M}=\\frac{1}{N}(\\mathbf{X}_{1}+\\cdots+\\mathbf{X}_{N})$$\n",
    "\n",
    "样本均值是所有数据点的”中心“。对$k=1,\\cdots,N$，令：\n",
    "\n",
    "$$\n",
    "B=\\begin{bmatrix}\\mathbf{X}_{k}-\\mathbf{M} & \\cdots & \\mathbf{X}_{N}-\\mathbf{M}\\end{bmatrix}=\n",
    "\\begin{bmatrix}\\hat{\\mathbf{X}}_{1} & \\cdots & \\hat{\\mathbf{X}}_{N}\\end{bmatrix}\n",
    "$$\n",
    "\n",
    "$B$具有零样本均值，这样的$B$称之为**平均偏差形式**。举例：  \n",
    "\n",
    "<img src=\"./_image/20_4.png\" width=\"400\" height=\"350\" />  \n",
    "\n",
    "$\\quad$**(样本)协方差矩阵**是一个$p\\times p$矩阵$S$，其定义为：\n",
    "\n",
    "$$S=\\frac{1}{N-1}BB^{T}$$\n",
    "\n",
    "$\\quad$其中$S$的对角线元素$s_{ii}$称为$x_i$的**方差**，是用于度量观测矩阵中第$i$种属性$x_i$的分散性。$S$的非对角线元素$s_{ij}$称为$x_i$和$x_j$的**协方差**，协方差描述的是$x_i$和$x_j$同向趋势，如果是同向变化，协方差为正；如果是反向变化，协方差为负。当协方差衡量的是同一属性时，协方差就成了方差。  \n",
    "$\\quad$数据的总方差是指$S$上对角线方差的总和，我们称一个矩阵对角线元素之和为**矩阵的迹**，记作$tr(S)$。    \n",
    "## 2.pca算法流程\n",
    "$\\quad$算法流程：\n",
    "1. 对所有样本进行中心化，并计算协方差矩阵；  \n",
    "2. 对协方差矩阵进行特征值分解；  \n",
    "3. 取前d大的特征值对应的特征向量（主成分）$\\{\\mathbf{u}_{1},\\cdots,\\mathbf{u}_{d}\\}$构成一个投影矩阵$U$；  \n",
    "4. 计算$Y=U^{T}X$完成降维。  \n",
    "\n",
    "pca的目标是对数据做降维，该数据变换需满足以下性质：\n",
    "1. 得到的新属性，两两之间的协方差为0；\n",
    "2. 第一个属性捕获尽量多的数据方差，在满足正交性的前提下，每个后继属性捕获尽可能多的剩余方差。  \n",
    "\n",
    "为啥要捕获尽量多的数据方差呢？因为一组数据中某一个属性如果方差为0，表明该属性没有研究价值；且如果变换后的属性方差尽量大，说明属性本身的蕴含的信息减少的不多。  \n",
    "\n",
    "<img src=\"./_image/20_5.png\" width=\"400\" height=\"350\" />  \n",
    "\n",
    "## 3.pca算法证明\n",
    "$\\quad$我们来推导为啥计算协方差矩阵的特征向量与特征值就可以符合我们所说的性质。要对数据做投影，要找到一组基，基与原数据矩阵作一次矩阵相乘即可完成投影，这组基假定为$U=\\begin{bmatrix}\\mathbf{u}_{1} & \\cdots & \\mathbf{u}_{d}\\end{bmatrix}$，是一个单位正交基，我们所求的即为$U$，下面的证明将会说明$U$如何得到：\n",
    "<img src=\"./_image/20_2.png\" width=\"450\" height=\"400\" />  \n",
    "<img src=\"./_image/20_3.png\" width=\"450\" height=\"400\" />  \n",
    "可以惊奇的发现，这不就是特征值和特征向量吗？因此，我们只需要求出$X$的协方差矩阵的特征值和特征向量，接着对特征值排序，取前$d$个特征向量（主成分）构成$U=\\begin{bmatrix}\\mathbf{u}_{1} & \\cdots & \\mathbf{u}_{d}\\end{bmatrix}$即可完成pca。  \n",
    "## 4.pca与svd\n",
    "$\\quad$设$X$为具有平均偏差形式的矩阵。pca的一个关键步骤就是求出协方差矩阵$\\frac{1}{N-1}XX^{T}$的特征值和特征向量。我们联系前面所学的[奇异值分解](《线性代数及其应用》笔记18.矩阵分解-奇异值分解.ipynb)，对于一个矩阵$X$，可以分解为:\n",
    "\n",
    "$$X=U\\varSigma V^{T}$$\n",
    "\n",
    "代入计算有：\n",
    "\n",
    "$$XX^{T}=(U\\varSigma V^{T})(U\\varSigma V^{T})^{T}=U\\varSigma^{2}U^{T}$$\n",
    "\n",
    "结合对角化的知识，我们可以知道$U$的列向量是$XX^{T}$的特征向量，$\\varSigma^{2}$是$XX^{T}$的非零特征值组成的矩阵。最后再结合回主成分分析法，协方差矩阵$\\frac{1}{N-1}XX^{T}$的特征值和特征向量（主成分）其实为$X$的奇异值的平方、左奇异向量。   \n",
    "$\\quad$故对一份观测矩阵进行pca降维，中心化后为$X$，对$X$进行奇异值分解$X=U\\varSigma V^{T}$，$U$即为主成分，比较奇异值的平方的大小来选取主成分即可完成算法。  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}