admin 管理员组文章数量: 1086019
线性子空间模型 linear subspace model
原文转自.html
针对数据处理得线性模型：线性子空间模型
目的：寻找数据得现行表示。为什么要寻找线性表示？
对于一个数据集，如果我们能够找到一组最小得向量基，让其他得所有数据可以表示为该向量得线性组合，就可以有效减少存储空间。可以理解为江源数据的高纬度空间减小到一个子空间，而且该子空间得纬度为最小向量基得个数。
子空间模型可以用来进行对向量数据的搜索。其实就是涉及到计算similarity，这在clustering等很多领域都有用。文中举一个例子是关于图像处理方面得project dectection。
在寻找向量基的过程中，我们也需要用到PCA，principal component analysis，在此一并做简单介绍。后续将说明PCA在clustering得用法。
1.首先讲讲为什么要用到子空间模型。
对于高维数据而言（图像，音乐等），如果我们能够用参数化得模型来近似：
I(x)=g(x,a)，其中a为低维度得参数向量
那么我们可以对数据集进行：减少数据集得维度（压缩）、创造一些新的应用（密度分析）、detection/recognition。
对于图像而言，其存储所有得图片，我们更希望把他们放到低维得空间，进行存储。这就是子空间得概念。
2.下面介绍线性子空间模型得理论知识
- 首先假设每个数据向量都能表示为其他基向量得线性组合：
I(x)=m(x)+∑a[k]b[k](x)
其中m(x)为所有数据向量得mean。a=(a1,a2,...,ak)为子空间参数subspace coefficients。bk(x)为基向量basis，也就是我们要找的低维表示。
换一种表示法。令B=[b1,b2,...mbk]，上式即为I=m+B a，其中I,m,a都为向量。
注意到m为mean，我们可以假设m=0(只需令I=I-m即可)，这样I= B a。
下面的问题就是如何得到这组向量基，即如何得到B。
- 我们假设这组向量基都是基于正交单位向量：
||bk||[2]=1,bjTbk=δjk。
那么这种情况下得子空间参数：
子空间参量即为a=BTI，这组子空间参量可以令SSE（sum of sqaured errors）最小：
min[a]||I-Ba||[2]2
因为此时，带入a，可以得到BBT=1,于是SSE=0.可见，只有正交得基底满足这样得性质。
这个性质线性代数里面也会有，比较好理解。
那么对于一个数据集{I1},l=1,...,L,L>>k，假设每个数据的维度为N2，选择向量基B时，我们只需要考虑如何让SSE最小：
- 上面的SSE很难解，如何才能解出B呢？下面介绍PCA Principal Components Analysis
定理：对于上式中的正交B，可以通过矩阵C的前k个eigenvector给出，C矩阵为数据的互相关矩阵：
C=1/L Σl Il IlT
求解C的eigenvector，为：
CU= UD，其中U=[u1,u2,...,uN2] ，D=diag(d1,d2,...,dN2)，同时d1 >= d2 >= ... >= dN2.
其中，最优的基底为bj=uj, j=1,...,k.
证明：我们需要得到B来使得对子空间近似得到的平方误差最小：
E=Σl mina ||Il -Ba ||22
由于我们假设B正交，而且a=BTI，这样
E=Σl mina ||Il -Ba ||22=Σl||I-BBTI||22
令A=[I1, I2, ..., IL]，于是
E=Σl||I-BBTI||22=||A-BBTA||F2=trace[AAT]-trace[BTAATB]
其中||*||F为Frobenius Norm，为矩阵norm的一种，||A||F2=trace[A*A]，其中A*为A的conjugate transpose，如果A为实矩阵，A*=AT。最后一步用到了BTB=1，trace[A]=trace[AT]，trace[BTAATB]=trace[ATBBTA]。trace[A]为矩阵A的对角元素和。
详情可见wikipedia【】
为了最小化E，我们只需最大化最后一项
El=trace[BTAATB]
由于C=1/L Σl Il IlT=1/L AAT，对C做SVD分解，可以得到C=UDUT。
这样E=trace[BTUDTTB]，其中U为正交，D为对角阵。
下面只需要证明我们想选择B，使得矩阵的trace是D的前k个对角元。
首先，BTU的秩rank必须要为k，因为B的rank为k。同时，D的对角元是有序的。同时trace在矩阵旋转的情况下是不变的。所以，我们希望得到的最大的长度为k的trace，就需要选择B，使得B和U组合后，能让得到的trace为D的前k行。这样就是说，让B的每行为U的前k个正交列。（这个证明比较牵强，但先到这里，详细讲PCA的时候，会通过另外一个角度来证明。）
这样，我们有了得到B的完整方法。
整个得到线性子空间的方法如下：
a. 得到数据，表示为vector形式，减去mean。注意，这个mean是对data关于每个维度的mean，所以维度和data是一样的。
b. 计算协方差矩阵covariance matrix C。
c. 计算C的eigenvector和eigenvalue。
d. 选取向量基。
- 其他
将数据映射到subspace上会有损失。损失即为剩下的eigenvalues的和。
得到的子空间中，第一个分量上数据将得到最大的方差。这个方差为第一个eigenvalue。这个结论将在下篇仔细说明。
问题：k为提前设定好？
本文标签： 线性子空间模型 linear subspace model
版权声明：本文标题：线性子空间模型 linear subspace model 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.roclinux.cn/b/1686559271a10232.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论