LSA和SVD两种矩阵分解

谈谈SVD和LSA











首先SVD和LSA是什么呢&＃xff0c;SVD全称是singular value decomposition&＃xff0c;就是俗称的奇异值分解&＃xff0c;SVD的用处有很多&＃xff0c;比如可以做PCA(主成分分析)&＃xff0c;做图形压缩&＃xff0c;做LSA&＃xff0c;那LSA是什么呢&＃xff0c;LSA全称Latent semantic analysis&＃xff0c;中文的意思是隐含语义分析&＃xff0c;LSA算是topic model的一种&＃xff0c;对于LSA的直观认识就是文章里有词语&＃xff0c;而词语是由不同的主题生成的&＃xff0c;比如一篇文章包含词语计算机&＃xff0c;另一篇文章包含词语电脑&＃xff0c;在一般的向量空间来看&＃xff0c;这两篇文章不相关&＃xff0c;但是在LSA看来&＃xff0c;这两个词属于同一个主题&＃xff0c;所以两篇文章也是相关的。





特征值特征向量





要谈到SVD&＃xff0c;特征值和特征向量是需要首先交代的。具体内容可以在wiki上看&＃xff0c;这里我做个简单的介绍。对于方阵M如果有





M∗v&＃61;λ∗v

v是个向量&＃xff0c;λ是个数&＃xff0c;那么我们称v是M的特征向量&＃xff0c;λ是M的特征值&＃xff0c;并且我们可以对M进行特征分解得到





M&＃61;Q∗Λ∗Q−1

其中Q是特征向量组成的矩阵&＃xff0c;Λ是对角阵&＃xff0c;对角线上的元素就是特征值。对于特征的几何理解就是矩阵M其实是一种线性变换&＃xff0c;而线性变换对于向量的影响有两种&＃xff0c;旋转和拉伸&＃xff0c;而特征向量就是在这种线性变换下方向保持不变的向量&＃xff0c;但是长度还是会作相应的拉伸&＃xff0c;特征值就是拉伸的程度。





从另一个角度说如果我们取特征值比较大的几项&＃xff0c;那么就是对原矩阵做了一种近似。





M≈Q1..k∗Λ1..k∗Q−11..k

这样我们就可以用更少的元素去近似的表示原矩阵&＃xff0c;但是特征分解的限制比较多&＃xff0c;比如要求矩阵必须是方阵





奇异值分解





wiki是个好东西&＃xff0c;你要想深入了解的话&＃xff0c;建议还是去看wiki。奇异值分解是将矩阵变成了这样的形式





M&＃61;U∗Σ∗VT

其中Σ依旧是对角阵&＃xff0c;而U和V是正交矩阵正交矩阵是说U∗UT&＃61;I。





我们还是先回到矩阵是线性变换这个思路上。














如果我们用M去作用空间里的一组基&＃xff0c;那么我们就会得到另一组基&＃xff0c;如上图那样。那么我们旋转一下最初的一组基。














这样我们经过M的变换由一组正交基变换到了另一组正交基上面。也是也就是下面这样。














也就是我们有





M∗v1&＃61;σ1∗u1

M∗v2&＃61;σ2∗u2

并且对于任意一个向量x&＃xff0c;我们有





x&＃61;v1∗(vT1∗x)&＃43;v2∗(vT2∗x)

于是我们可以得到





M∗x&＃61;M∗v1∗(vT1∗x)&＃43;M∗v2∗(vT2∗x)

M∗x&＃61;σ1∗u1∗(vT1∗x)&＃43;σ2∗u2∗(vT2∗x)

M&＃61;σ1∗u1∗vT1&＃43;σ2∗u2∗vT2

M&＃61;U∗Σ∗VT

恩&＃xff0c;我们得到了和特征值和特征向量相似的东西&＃xff0c;SVD分解出来的就是在M的线性变换下&＃xff0c;正交基变换仍是正交基&＃xff0c;而奇异值就是拉伸的程度。其实SVD和特征值和特征向量的关系还是很大的。





M∗MT&＃61;U∗Σ∗VT∗V∗ΣT∗UT

M∗MT&＃61;U∗Σ2∗UT

也就是说SVD求出的是M∗MT和MT∗M的特征向量。同样的得到这SVD分解这种形式后我们就可以利用他来对原数据进行降维操作。














这里我们分别将RBG矩阵进行SVD&＃xff0c;左上角的是原图&＃xff0c;其他的依次是取最大的100个&＃xff0c;50个&＃xff0c;20个&＃xff0c;10个&＃xff0c;5个奇异值做的近似图像。

# -*- coding: utf-8 -*-from scipy import linalg, dot
from PIL import Imagedef main(num&＃61;5):im &＃61; Image.open(&＃39;ai.jpg&＃39;)pix &＃61; im.load()ma &＃61; [[], [], []]for x in xrange(im.size[0]):for i in xrange(3):ma[i].append([])for y in xrange(im.size[1]):for i in xrange(3):ma[i][-1].append(pix[x, y][i])for i in xrange(3):u, s, v &＃61; linalg.svd(ma[i])u &＃61; u[:, :num]v &＃61; v[:num, :]s &＃61; s[:num]ma[i] &＃61; dot(dot(u, linalg.diagsvd(s, num, num)), v)for x in xrange(im.size[0]):for y in xrange(im.size[1]):ret &＃61; []for i in xrange(3):tmp &＃61; int(ma[i][x][y])if tmp <0:tmp &＃61; 0if tmp > 255:tmp &＃61; 255ret.append(tmp)pix[x, y] &＃61; tuple(ret)im.show()im.save(&＃39;test.jpg&＃39;)if __name__ &＃61;&＃61; &＃39;__main__&＃39;:main()





如果对矩阵先进行归一化&＃xff0c;再SVD就是PCA的形式了&＃xff0c;这种形式可以用方差最大化或者误差最小化来求得&＃xff0c;具体可以去看PCA相关的东西。所以和scturtle讨论了下直接SVD的意义&＃xff0c;但是最后也没得出什么结论。。。





隐含语义分析





终于讲到最后的隐含语义分析了&＃xff0c;首先我们构造文本和词语的矩阵&＃xff0c;也就是对于矩阵来说每一个向量表示一篇文章&＃xff0c;每个向量里就是单词的出现次数(更好的是每个是单词的tf/idf值&＃xff0c;tf/idf不在赘述&＃xff0c;具体可以看wiki)。那么SVD分解之后&＃xff0c;我们就得到了降维的矩阵&＃xff0c;就是下面这个样子













就是说原来我们有1000000篇文章&＃xff0c;总共有500000个单词&＃xff0c;我们保留最大的100个来做降维&＃xff0c;于是现在我们可以这样理解&＃xff0c;我们保留了100个主题&＃xff0c;其中U是文章对应的主题分布&＃xff0c;而V则是主题对应的词语的分布&＃xff0c;这样&＃xff0c;我们可以减少噪音&＃xff0c;并且这样计算文章间的相关性也更加合理&＃xff0c;并且可以把相关的单词聚合到一起。代码如下

# -*- coding: utf-8 -*-import os
import re
import heapq
import codecs
from math import log
from scipy import linalgimport unigram_good_turing as segseg.init()def tfidf(docs):doclen &＃61; len(docs)&＃43;1.0for doc in docs:wordtotal &＃61; sum(doc.values())&＃43;0.0for word in doc:tf &＃61; doc[word]/wordtotalidf &＃61; log(doclen/(sum([word in tmp for tmp in docs])&＃43;1))doc[word] &＃61; tf*idfreturn docsdef solve(data):re_zh, re_other &＃61; re.compile(ur"([\u4E00-\u9FA5]&＃43;)"), re.compile(ur"[^a-zA-Z0-9&＃43;#\n]")blocks &＃61; re_zh.split(data)for item in blocks:if re_zh.match(item):for i in seg.solve(item):yield ielse:tmp &＃61; re_other.split(item)for x in tmp:if x !&＃61; &＃39;&＃39;:passdef show(dic, p):p &＃61; heapq.nlargest(10, enumerate(p), key&＃61;lambda x:x[1])print &＃39; &＃39;.join(map(lambda x:dic[x[0]], p))def main():names &＃61; os.listdir(&＃39;text&＃39;)dic &＃61; {}cnt &＃61; 0ma &＃61; []for name in names:data &＃61; codecs.open(&＃39;text/&＃39;&＃43;name, &＃39;r&＃39;, &＃39;utf-8&＃39;).read()doc &＃61; {}for word in solve(data):if not word in dic:dic[word] &＃61; cntcnt &＃43;&＃61; 1tmp &＃61; dic[word]if tmp not in doc:doc[tmp] &＃61; 0doc[tmp] &＃43;&＃61; 1ma.append(doc)ma &＃61; tfidf(ma)ret &＃61; []for item in ma:tmp &＃61; []for i in xrange(cnt):if i in item:tmp.append(item[i])else:tmp.append(0)ret.append(tmp)u, s, v &＃61; linalg.svd(ret)for i in xrange(10):show(dict(zip(dic.values(), dic.keys())), list(v[i]))if __name__ &＃61;&＃61; &＃39;__main__&＃39;:main()