主成分分析
线性代数概念复习向量的内积基协方差矩阵实对称矩阵特征值和特征向量主成分分析的计算步骤本文不会深究原理,如果有时间我会把原理补上,这篇文章主要是讲主成分分析的计算步骤。
在开始详细介绍PCA算法前,我们先来复习一下线性代数中几个重要的概念
线性代数概念复习
向量的内积
假设a⃗=[a1a2...an]\vec{a}=\begin{bmatrix} a_1 \\ a_2 \\ ...\\a_n \end{bmatrix}a=⎣⎢⎢⎡a1a2...an⎦⎥⎥⎤,b⃗=[a1a2...an]\vec{b}=\begin{bmatrix} a_1 \\ a_2 \\ ...\\a_n \end{bmatrix}b=⎣⎢⎢⎡a1a2...an⎦⎥⎥⎤
那么
a⃗⋅b⃗=a1b1+a2b2+...+anbn\vec{a}\cdot\vec{b}=a_1b_1+a_2b_2+...+a_nb_na⋅b=a1b1+a2b2+...+anbn
a⃗\vec{a}a的模记为:∣a⃗∣=a⃗⋅a⃗|\vec{a}|=\sqrt{\vec{a}\cdot \vec{a}}∣a∣=a⋅a
a⃗⋅b⃗=∣a⃗∣∣b⃗∣cosθ\vec{a}\cdot\vec{b}=|\vec{a}||\vec{b}|cos\thetaa⋅b=∣a∣∣b∣cosθ
假设b⃗\vec{b}b的模为1,即单位向量,那么a⃗⋅b⃗=∣a⃗∣cosθ\vec{a}\cdot\vec{b}=|\vec{a}|cos\thetaa⋅b=∣a∣cosθ,实际上,内积就是a⃗\vec{a}a在b⃗\vec{b}b方向上的投影的长度。
如果a⃗⋅b⃗=0\vec{a}\cdot\vec{b}=0a⋅b=0,表示a⃗\vec{a}a和b⃗\vec{b}b正交,也就是线性无关。
基
在线性代数中,基(也称为基底)是描述、刻画向量空间的基本工具。向量空间的基是它的一个特殊的子集,基的元素称为基向量。向量空间中任意一个元素,都可以唯一地表示成基向量的线性组合。如果基中元素个数有限,就称向量空间为有限维向量空间,将元素的个数称作向量空间的维数。
向量空间V的一组向量若满足
1)线性无关
2)V中任一向量可由此向量线性表出,则称该组向量V中的一个基(亦称基底)。
一个向量空间的基有很多,但每个基所含向量个数却是个定数。
例如
上图的一组基是(1,0)(1, 0)(1,0)和(0,1)(0, 1)(0,1),向量a⃗=(3,2)=3(1,0)+2(0,1)\vec{a}=(3, 2) = 3(1, 0)+2(0, 1)a=(3,2)=3(1,0)+2(0,1)
假设又有一组新的基(0.5,0.5)(0.5, 0.5)(0.5,0.5)和(−0.5,0.5)(-0.5, 0.5)(−0.5,0.5),那么原来的向量a⃗\vec{a}a应该怎么表示?
a⃗\vec{a}a在新的基(0.5,0.5)(0.5, 0.5)(0.5,0.5)上的投影为(0.5,0.5)⋅(3,2)T=2.5(0.5, 0.5) \cdot (3, 2)^T=2.5(0.5,0.5)⋅(3,2)T=2.5,在(0.5,−0.5)(0.5, -0.5)(0.5,−0.5)上的投影为(−0.5,0.5)⋅(3,2)T=−0.5(-0.5, 0.5) \cdot (3, 2)^T=-0.5(−0.5,0.5)⋅(3,2)T=−0.5,所以a⃗\vec{a}a在新的基上为(2.5,−0.5)(2.5, -0.5)(2.5,−0.5)
也可以用矩阵计算:
[0.50.5−0.50.5][32]=[2.5−0.5]\begin{bmatrix} 0.5 & 0.5 \\ -0.5 & 0.5 \end{bmatrix}\begin{bmatrix} 3\\ 2 \end{bmatrix}=\begin{bmatrix} 2.5\\ -0.5 \end{bmatrix}[0.5−0.50.50.5][32]=[2.5−0.5]
假设[p1p2...pr]\begin{bmatrix} p_1\\ p_2\\...\\p_r \end{bmatrix}⎣⎢⎢⎡p1p2...pr⎦⎥⎥⎤是n组新的基,[a1a2...am]\begin{bmatrix} a_1& a_2&...&a_m \end{bmatrix}[a1a2...am]是m个样本,那么m个样本在n组基表达为:
[p1p2...pr][a1a2...am]=[p1a1p1a2...p1amp2a1p2a2...p2am............pra1pra2...pram]r×m\begin{bmatrix} p_1\\ p_2\\...\\p_r \end{bmatrix} \begin{bmatrix} a_1& a_2&...&a_m \end{bmatrix}= \begin{bmatrix} p_1a_1& p_1a_2&...&p_1a_m \\p_2a_1& p_2a_2&...&p_2a_m \\...& ...&...&... \\p_ra_1& p_ra_2&...&p_ra_m \end{bmatrix}_{r\times m}⎣⎢⎢⎡p1p2...pr⎦⎥⎥⎤[a1a2...am]=⎣⎢⎢⎡p1a1p2a1...pra1p1a2p2a2...pra2............p1amp2am...pram⎦⎥⎥⎤r×m
协方差矩阵
假设两个向量x和y,他们的协方差的公式为:
Cov(x,y)=Σi=1n(xi−xˉ)(yi−yˉ)nCov(x,y)=\frac{\Sigma_{i=1}^n(x_i-\bar{x})(y_i-\bar{y})}{n}Cov(x,y)=nΣi=1n(xi−xˉ)(yi−yˉ)
也可以写成:
Cov(x,y)=E[(x−E[x])(y−E[y])]Cov(x,y)=E[(x-E[x])(y-E[y])]Cov(x,y)=E[(x−E[x])(y−E[y])]
=E[xy]−2E[y]E[x]+E[x]E[y]=E[xy]−E[x][y]=E[xy]-2E[y]E[x]+E[x]E[y]=E[xy]-E[x][y]=E[xy]−2E[y]E[x]+E[x]E[y]=E[xy]−E[x][y]
协方差矩阵为:
C=[Cov(x,x)Cov(x,y)Cov(x,z)Cov(y,x)Cov(y,y)Cov(y,z)Cov(z,x)Cov(z,y)Cov(z,z)]C=\begin{bmatrix} Cov(x,x) & Cov(x,y) & Cov(x,z) \\ Cov(y,x) & Cov(y,y) & Cov(y,z) \\ Cov(z,x) & Cov(z,y) & Cov(z,z) \end{bmatrix}C=⎣⎡Cov(x,x)Cov(y,x)Cov(z,x)Cov(x,y)Cov(y,y)Cov(z,y)Cov(x,z)Cov(y,z)Cov(z,z)⎦⎤
其中Cov(x,x)=Var(x)Cov(x,x)=Var(x)Cov(x,x)=Var(x),Cov(x,y)=Cov(y,x)Cov(x,y)=Cov(y,x)Cov(x,y)=Cov(y,x)
实对称矩阵
我们可以看到,协方差矩阵是一个实对称矩阵。
1.实对称矩阵AAA的不同特征值对应的特征向量是正交的。
2.实对称矩阵AAA的特征值都是实数,特征向量都是实向量。
3.n阶实对称矩阵AAA必可相似对角化,且相似对角阵上的元素即为矩阵本身特征值。
特征值和特征向量
设AAA是n阶方阵,若存在数λ\lambdaλ和非零向量xxx,使得Ax=λxAx=\lambda xAx=λx,则称:
λ\lambdaλ是AAA的一个特征值
xxx是AAA是对应的λ\lambdaλ的特征向量。
因为Ax=λx⇒(A−λE)x=0Ax=\lambda x \Rightarrow (A-\lambda E)x=0Ax=λx⇒(A−λE)x=0,因为xxx是非零向量,所以∣A−λE∣=0|A-\lambda E|=0∣A−λE∣=0
下面直接用一个例子来说明如何求特征值和特征向量。
例:求A=[−110−430102]A=\begin{bmatrix} -1 & 1 & 0 \\ -4 & 3 & 0 \\ 1 & 0 & 2 \end{bmatrix}A=⎣⎡−1−41130002⎦⎤的特征值和特征向量。
解:先求特征值,相当于求:
∣A−λE∣=∣−1−λ10−43−λ0102−λ∣=(2−λ)(λ−1)2=0|A-\lambda E|=\begin{vmatrix} -1-\lambda & 1 & 0 \\ -4 & 3-\lambda & 0 \\ 1 & 0 & 2 -\lambda \end{vmatrix}=(2-\lambda)(\lambda-1)^2=0∣A−λE∣=∣∣∣∣∣∣−1−λ−4113−λ0002−λ∣∣∣∣∣∣=(2−λ)(λ−1)2=0
所以特征值为λ=2,1\lambda=2,1λ=2,1
当λ=2\lambda=2λ=2时,(A−2E)x=0(A-2E)x=0(A−2E)x=0
⇒[−310−410100]x=0\Rightarrow \begin{bmatrix} -3 & 1 & 0 \\ -4 & 1 & 0 \\ 1 & 0 & 0 \end{bmatrix}x=0⇒⎣⎡−3−41110000⎦⎤x=0
矩阵行简化阶梯型求解方程:
⇒[−310∣0−410∣0100∣0]\Rightarrow \begin{bmatrix} -3 & 1 & 0 &\big|&0 \\ -4 & 1 & 0&\big|&0 \\ 1 & 0 & 0 &\big|&0 \end{bmatrix}⇒⎣⎡−3−41110000∣∣∣∣∣∣000⎦⎤
⇒[−310∣0−410∣0100∣0]\Rightarrow \begin{bmatrix} -3 & 1 & 0 &\big|&0 \\ -4 & 1 & 0&\big|&0 \\ 1 & 0 & 0 &\big|&0 \end{bmatrix}⇒⎣⎡−3−41110000∣∣∣∣∣∣000⎦⎤
⇒[100∣0010∣0000∣0]\Rightarrow \begin{bmatrix} 1 & 0 & 0 &\big|&0 \\ 0 & 1 & 0&\big|&0 \\ 0 & 0 & 0 &\big|&0 \end{bmatrix}⇒⎣⎡100010000∣∣∣∣∣∣000⎦⎤
⇒x1=0,x2=0\Rightarrow x_1 = 0, x_2 = 0⇒x1=0,x2=0
得基础解系:
p1=[001]p_1=\begin{bmatrix} 0 \\ 0 \\ 1 \end{bmatrix}p1=⎣⎡001⎦⎤
当λ=1\lambda=1λ=1时,(A−2E)x=0(A-2E)x=0(A−2E)x=0
⇒[−210−41]x=0\Rightarrow \begin{bmatrix} -2 & 1 & 0 \\ -4 & 2 & 0 \\ 1 & 0 & 1 \end{bmatrix}x=0⇒⎣⎡−2−41120001⎦⎤x=0
矩阵行简化阶梯型求解方程:
⇒[−210∣0−420∣0101∣0]\Rightarrow \begin{bmatrix} -2 & 1 & 0 &\big|&0 \\ -4 & 2 & 0&\big|&0 \\ 1 & 0 & 1 &\big|&0 \end{bmatrix}⇒⎣⎡−2−41120001∣∣∣∣∣∣000⎦⎤
⇒[101∣0012∣0000∣0]\Rightarrow \begin{bmatrix} 1 & 0 & 1 &\big|&0 \\0 & 1 & 2&\big|&0 \\ 0 & 0 & 0 &\big|&0 \end{bmatrix}⇒⎣⎡100010120∣∣∣∣∣∣000⎦⎤
⇒x1+x3=0,x2+2x3=0\Rightarrow x_1 +x_3= 0, x_2 +2x_3= 0⇒x1+x3=0,x2+2x3=0
得基础解系:
p2=[−1−21]p_2=\begin{bmatrix} -1 \\ -2 \\1 \end{bmatrix}p2=⎣⎡−1−21⎦⎤
主成分分析的计算步骤
主成分分析的主要步骤为:
原始数据减去平均值,使数据的均值变为0计算协方差矩阵计算协方差矩阵的特征值和特征向量将特征值从大到小排序保留最前面的k个特征向量将数据转换到上述k个特征向量构建的新空间中。
下面我们直接用实际例子来看主成分分析的计算步骤。
例子:求A=[00131−4−2−2−1−1]A=\begin{bmatrix} 0&0&1&3&1 \\ -4 &-2&-2&-1&-1\end{bmatrix}A=[0−40−21−23−11−1]的主成分
解:
可以看到原始数据是一个2维数组,共有5个样本。
1. 原始数据减去平均值,使数据的均值变为0
第一个变量的均值为1,第二个变量的均值是-2,分别减去均值后,得到如下数据,后面的计算都会基于下面的矩阵进行计算:
A′=[−1−1020−20011]A'=\begin{bmatrix} -1&-1&0&2&0 \\ -2 &0&0&1&1\end{bmatrix}A′=[−1−2−10002101]
2. 计算协方差矩阵
协方差的计算公式为: Cov(x,y)=Σi=1n(xi−xˉ)(yi−yˉ)nCov(x,y)=\frac{\Sigma_{i=1}^n(x_i-\bar{x})(y_i-\bar{y})}{n}Cov(x,y)=nΣi=1n(xi−xˉ)(yi−yˉ)
由第一步我们已经知道xˉ=0,yˉ=0\bar{x}=0,\bar{y}=0xˉ=0,yˉ=0,所以:Cov(x,y)=Σi=1nxiyinCov(x,y)=\frac{\Sigma_{i=1}^nx_iy_i}{n}Cov(x,y)=nΣi=1nxiyi
所以协方差矩阵C=A′A′T=15[−1−1020−20011][−1−2−10002101]=[65454565]C=A'A'^T=\frac{1}{5}\begin{bmatrix} -1&-1&0&2&0 \\ -2 &0&0&1&1\end{bmatrix} \begin{bmatrix} -1&-2\\ -1&0\\ 0&0\\ 2&1\\ 0&1\end{bmatrix} =\begin{bmatrix} \frac{6}{5}&\frac{4}{5}\\ \frac{4}{5}&\frac{6}{5}\\ \end{bmatrix}C=A′A′T=51[−1−2−10002101]⎣⎢⎢⎢⎢⎡−1−1020−20011⎦⎥⎥⎥⎥⎤=[56545456]
3. 计算协方差矩阵的特征值和特征向量
∣C−λE∣=∣65−λ454565−λ∣=(65−λ)2−(45)2=(65−λ−45)(65−λ+45)=0|C-\lambda E|=\begin{vmatrix} \frac{6}{5}-\lambda&\frac{4}{5}\\ \frac{4}{5}&\frac{6}{5}-\lambda\\ \end{vmatrix}=(\frac{6}{5}-\lambda)^2-(\frac{4}{5})^2=(\frac{6}{5}-\lambda-\frac{4}{5})(\frac{6}{5}-\lambda+\frac{4}{5})=0∣C−λE∣=∣∣∣∣56−λ545456−λ∣∣∣∣=(56−λ)2−(54)2=(56−λ−54)(56−λ+54)=0
所以特征值为λ1=2,λ2=25\lambda_1=2,\lambda_2=\frac{2}{5}λ1=2,λ2=52
当λ=2\lambda=2λ=2时,(C−2E)x=0(C-2E)x=0(C−2E)x=0
⇒[−454545−45]x=0\Rightarrow \begin{bmatrix}- \frac{4}{5} & \frac{4}{5} \\ \frac{4}{5} & -\frac{4}{5} \end{bmatrix}x=0⇒[−545454−54]x=0
矩阵行简化阶梯型求解方程:
⇒[−4545∣045−45∣0]\Rightarrow \begin{bmatrix} - \frac{4}{5} & \frac{4}{5} &\big|&0 \\ \frac{4}{5} & -\frac{4}{5}&\big|&0 \end{bmatrix}⇒[−545454−54∣∣∣∣00]
⇒[1−1∣000∣0]\Rightarrow \begin{bmatrix} 1 &-1 &\big|&0 \\ 0& 0&\big|&0 \end{bmatrix}⇒[10−10∣∣∣∣00]
⇒x1−x2=0\Rightarrow x_1 -x_2= 0⇒x1−x2=0
得基础解系:
p1=[11]p_1=\begin{bmatrix} 1 \\1 \end{bmatrix}p1=[11]
当λ=25\lambda=\frac{2}{5}λ=52时,(C−25E)x=0(C-\frac{2}{5}E)x=0(C−52E)x=0
⇒[45454545]x=0\Rightarrow \begin{bmatrix} \frac{4}{5} & \frac{4}{5} \\ \frac{4}{5} & \frac{4}{5} \end{bmatrix}x=0⇒[54545454]x=0
矩阵行简化阶梯型求解方程:
⇒[4545∣04545∣0]\Rightarrow \begin{bmatrix} \frac{4}{5} & \frac{4}{5} &\big|&0 \\ \frac{4}{5} & \frac{4}{5}&\big|&0 \end{bmatrix}⇒[54545454∣∣∣∣00]
⇒[11∣000∣0]\Rightarrow \begin{bmatrix} 1 &1 &\big|&0 \\ 0& 0&\big|&0 \end{bmatrix}⇒[1010∣∣∣∣00]
⇒x1+x2=0\Rightarrow x_1 +x_2= 0⇒x1+x2=0
得基础解系:
p2=[1−1]p_2=\begin{bmatrix} 1 \\-1 \end{bmatrix}p2=[1−1]
因为基的模都是1,所以:
p1′=p1∣p1∣=12[111]=[1212]p_1'=\frac{p_1}{|p_1|}=\frac{1}{\sqrt{2}}\begin{bmatrix} 1 \\11 \end{bmatrix}=\begin{bmatrix} \frac{1}{\sqrt{2}} \\\frac{1}{\sqrt{2}} \end{bmatrix}p1′=∣p1∣p1=21[111]=[2121]
p2′=p2∣p2∣=12[1−1]=[12−12]p_2'=\frac{p_2}{|p_2|}=\frac{1}{\sqrt{2}}\begin{bmatrix} 1 \\-1 \end{bmatrix}=\begin{bmatrix} \frac{1}{\sqrt{2}} \\-\frac{1}{\sqrt{2}} \end{bmatrix}p2′=∣p2∣p2=21[1−1]=[21−21]
4. 将特征值从大到小排序
所以特征值为λ1=2,λ2=25\lambda_1=2,\lambda_2=\frac{2}{5}λ1=2,λ2=52,λ1>λ2\lambda_1>\lambda_2λ1>λ2
5. 保留最前面的k个特征向量
在这个例子中,我们只保留一个特征向量,即λ1=2\lambda_1=2λ1=2对应的p1′=[1212]p_1'=\begin{bmatrix} \frac{1}{\sqrt{2}} \\\frac{1}{\sqrt{2}} \end{bmatrix}p1′=[2121]
6. 将数据转换到上述k个特征向量构建的新空间中。
数据转化为Y=p1′TA′=[1212][−1−1020−20011]=[−32−12032−12]Y=p_1'^TA'= \begin{bmatrix} \frac{1}{\sqrt{2}} &\frac{1}{\sqrt{2}} \end{bmatrix} \begin{bmatrix} -1&-1&0&2&0 \\ -2 &0&0&1&1\end{bmatrix}= \begin{bmatrix} -\frac{3}{\sqrt{2}}&-\frac{1}{\sqrt{2}}&0&\frac{3}{\sqrt{2}}&-\frac{1}{\sqrt{2}} \end{bmatrix}Y=p1′TA′=[2121][−1−2−10002101]=[−23−21023−21]