重新整理了PCA相关的原理和推导
从最小二乘出发, 其原理可以描述为: 在数据空间χ中寻找一个超平面, 让数据样本到该超平面的距离平方之和最小.
数据点到超平面距离的计算试为该点向量减该点在超平面上的投影所得向量的长度, 即
dist(xi,plane)=||xi−x^i||2
下标2表示L2范数, 几何解释如图
假设该超平面由d′个标准正交向量张成, 即
plane=span{w1,w2,w3,...,wd′},s.t. wi⋅wj=δij
令
W=[w1,w2,w3,...,wd′],则 PCA的优化目标可表示为
argminW∑i||xi−x^i||22s.t. WTW=I(1)
由线性代数知识可知, 数据点
xi在超平面上的投影可表示为
x^i=∑j=1d′(wTjxi)wj
于是优化目标可写为
argminW∑i||∑j=1d′(wTjxi)wj−xi||22s.t. WTW=I(2)
接下来一步一步分析, 先将距离平方展开:
||xi−x^i||22=(xi−x^i)T(xi−x^i)=xTixi−xTix^i−x^Tixi+x^Tix^i(3)
(3)式第一项是常数, 对(3)式右边最后一项展开:
x^Tix^i=(∑j=1d′(wTjxi)wTj)(∑k=1d′(wTkxi)wj)
注意,
wTjxi是实数, 不参与转置并且可以挪动位置, 注意到
wTjwk=δjk ,当
j=k时等于1, 否则等于0. 展开上式相乘之后只剩下:
∑j=1d′(wTjxi)(wTjxi)
由内积的性质可知
wTjxi=xTiwj,上式最后变为:
∑j=1d′wTjxixTiwj
对(3)式右边第二项展开:
−xTix^i=xTi∑j=1d′(wTjxi)wj=−∑j=1d′wTjxixTiwj
由内积性质可知
xTix^i=x^Tixi, 所以(3)式可写成
||xi−x^i||22=−∑j=1d′wTjxixTiwj+const=−tr(WTxixTiW)+const
tr表示矩阵的迹, 上式展开即可验证. 现对整个样本求和并注意到
∑ixixTi=XXT. 考虑上述结果, 优化目标可写为:
argmaxW tr(WTXXTW)s.t. WTW=I(2)
这里用到了迹和矩阵乘法的线性性质.
现用拉格朗日乘子法求解, 约束条件
WTW=I包含了
d′×d′个等式, 为了说明清楚, 不失一般性,取
d′=2进行推导, 此时拉格朗日函数可写为:
L(w1,w2)=wT1XXTw1+wT2XXTw2+λ11(1−wT1w1)+λ22(1−wT2w2)+λ12wT1w2+λ21wT2w1
对
w1求导并令其等于0得:
∂L∂w1=2XXTw1−2λ11w1+λ12w2+λ21w2=0⃗
重点:要让上式成立, 显然
w1和
w2是不能等于
0⃗ 的, 而且它们
不能共线, 共线了超平面维数就不是
d′了, 这意味着
w1和
w2线性无关. 所以只能是有:
2XXTw1−2λ11w1=0⃗ λ12+λ21=0
从上式可以看出
w1恰好是
XXT对应于
λ11的特征向量, 同理对于
w2,...,wd′. 于是只要求出
XXT最大的前
d′个特征值对应的特征向量, 用它们张成超平面, 将数据向超平面上投影即可完成降维.
注意到这里
XXT恰好是(m-1)倍的中心化数据的协方差矩阵, 推导如下:
cov(xi,xj)=E((xi−x¯i)(xj−x¯j))
用m个样本做估计, 并且注意到中心化, 则有:
x¯i=1m∑k=1mx(k)i=0cov(xi,xj)=1m−1∑k=1mx(k)ix(k)j
即证.
Python实现:
http://blog.csdn.net/u013648367/article/details/53135665
参考资料
[1] 周志华. 机器学习
