CWYAlpha

Just another WordPress.com site

Thought this was cool: 谈谈SVD和LSA

leave a comment »


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

特征值特征向量

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

M*v=\lambda*v的特征向量。同样的得到这SVD分解这种形式后我们就可以利用他来对原数据进行降维操作。

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

  1. # -*- coding: utf-8 -*-
  2.  
  3. fromscipyimportlinalg, dot
  4. fromPILimportImage
  5.  
  6. defmain(num=5):
  7.     im = Image.open(‘ai.jpg’)
  8.     pix = im.load()
  9.     ma =[[],[],[]]
  10.    forxinxrange(im.size[0]):
  11.        foriinxrange(3):
  12.             ma[i].append([])
  13.        foryinxrange(im.size[1]):
  14.            foriinxrange(3):
  15.                 ma[i][-1].append(pix[x, y][i])
  16.    foriinxrange(3):
  17.         u, s, v = linalg.svd(ma[i])
  18.         u = u[:, :num]
  19.         v = v[:num, :]
  20.         s = s[:num]
  21.         ma[i]= dot(dot(u, linalg.diagsvd(s, num, num)), v)
  22.    forxinxrange(im.size[0]):
  23.        foryinxrange(im.size[1]):
  24.             ret =[]
  25.            foriinxrange(3):
  26.                 tmp =int(ma[i][x][y])
  27.                iftmp<0:
  28.                     tmp =0
  29.                iftmp>255:
  30.                     tmp =255
  31.                 ret.append(tmp)
  32.             pix[x, y]=tuple(ret)
  33.     im.show()
  34.     im.save(‘test.jpg’)
  35.  
  36. if__name__ ==’__main__’:
  37.     main()

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

隐含语义分析

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

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

  1. # -*- coding: utf-8 -*-
  2.  
  3. importos
  4. importre
  5. importheapq
  6. importcodecs
  7. frommathimportlog
  8. fromscipyimportlinalg
  9.  
  10. importunigram_good_turing as seg
  11.  
  12. seg.init()
  13.  
  14. deftfidf(docs):
  15.     doclen =len(docs)+1.0
  16.    fordocindocs:
  17.         wordtotal =sum(doc.values())+0.0
  18.        forwordindoc:
  19.             tf = doc[word]/wordtotal
  20.             idf = log(doclen/(sum([wordintmpfortmpindocs])+1))
  21.             doc[word]= tf*idf
  22.    returndocs
  23.  
  24. defsolve(data):
  25.     re_zh, re_other =re.compile(ur”([\u4E00-\u9FA5]+)”),re.compile(ur”[^a-zA-Z0-9+#\n]”)
  26.     blocks = re_zh.split(data)
  27.    foriteminblocks:
  28.        ifre_zh.match(item):
  29.            foriinseg.solve(item):
  30.                yieldi
  31.        else:
  32.             tmp = re_other.split(item)
  33.            forxintmp:
  34.                ifx!=”:
  35.                    pass
  36.  
  37. defshow(dic, p):
  38.     p =heapq.nlargest(10,enumerate(p), key=lambdax:x[1])
  39.    print’ ‘.join(map(lambdax:dic[x[0]], p))
  40.  
  41. defmain():
  42.     names =os.listdir(‘text’)
  43.     dic ={}
  44.     cnt =0
  45.     ma =[]
  46.    fornameinnames:
  47.         data =codecs.open(‘text/’+name,’r’,’utf-8′).read()
  48.         doc ={}
  49.        forwordinsolve(data):
  50.            ifnotwordindic:
  51.                 dic[word]= cnt
  52.                 cnt +=1
  53.             tmp = dic[word]
  54.            iftmpnotindoc:
  55.                 doc[tmp]=0
  56.             doc[tmp]+=1
  57.         ma.append(doc)
  58.     ma = tfidf(ma)
  59.     ret =[]
  60.    foriteminma:
  61.         tmp =[]
  62.        foriinxrange(cnt):
  63.            ifiinitem:
  64.                 tmp.append(item[i])
  65.            else:
  66.                 tmp.append(0)
  67.         ret.append(tmp)
  68.     u, s, v = linalg.svd(ret)
  69.    foriinxrange(10):
  70.         show(dict(zip(dic.values(), dic.keys())),list(v[i]))
  71.  
  72. if__name__ ==’__main__’:
  73.     main()

用来计算我博客的文章,可以得到如下的一些相关词语。

异 石子 或 次 制 游戏 先手 堆 必胜 数

熵 信息 香 农 公式 变量 石子 衡量 那篇 压缩

密钥 公钥 加密 欧拉 解密 别人 选出 数论 非对称

我猜您可能还会喜欢:


0

   

0

IT 牛人博客聚合网站(udpwork.com) 聚合
|
评论: 0
|
10000+ 本编程/Linux PDF/CHM 电子书下载

from IT牛人博客聚合网站: http://www.udpwork.com/item/8709.html

Written by cwyalpha

十一月 24, 2012 在 3:27 下午

发表在 Uncategorized

发表评论

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s

%d 博主赞过: