机器学习实战 11- SVD

野性酷女 2021-10-30 02:16 356阅读 0赞

## 1 SVD 相关理论 ##

### 1.1 奇异值分解定义 ###

SVD,即奇异值分解，矩阵论中学过内容，公式为：

![1646215-20190610215214189-1182759864.png][]

用一张图来形象表达一下：

![1646215-20190610215227110-559435851.png][]

其中的奇异值矩阵，奇异值从大到小排列，而且减少的特别快，我们可以用前面最大的k个奇异值来表示这个原有矩阵，且保留大部分信息。如图：

![1646215-20190610215248624-887890576.png][]

### 1.2 与PCA有何勾结 ###

之前我们解释过 PCA ，PCA 的本质就是将原数据投影到低维坐标系中，获取主要信息值，起到降维作用。

究竟 SVD 与其有何关系呢？我们看一下下面的公式推导，就明白了。

![1646215-20190610215319503-1816469885.png][]

由上图可以比较出，PCA 中得到的 P 就是奇异值分解中的 V。

如果需要给列降维到 k ，则：

![1646215-20190610215347528-1916925149.png][]

如果需要给行降维到 k ，则：

![1646215-20190610215401314-385376911.png][]

即**左奇异矩阵负责给行降维，一般用来减小无效样本。**

**右奇异矩阵负责给列降维，一般用来缩减特征。**

### 1.3 优点与用途 ###

优点：

当我们使用PCA的时候，用到协方差矩阵，但是当样本数量m大特征n也大的时候，协方差就不好计算，特征值和特征向量就不易求出。此时如果使用SVD，速度快很多，有人会说，奇异值分解时不也是利用了协方差矩阵么？其实不然这只是求取分解的一种方法，一般会使用迭代的办法，这里不赘述，只需明白它的计算速度远远加快，有兴趣可以看看这两篇文章：

并行计算奇异值：[https://www.cnblogs.com/zhangchaoyang/articles/2575948.html][https_www.cnblogs.com_zhangchaoyang_articles_2575948.html]

一篇关于奇异值计算的论文：[http://www.cs.utexas.edu/users/inderjit/public\_papers/HLA\_SVD.pdf][http_www.cs.utexas.edu_users_inderjit_public_papers_HLA_SVD.pdf]

用途：

1.  1.  特征降维
    2.  去除噪声
    3.  推荐系统
    4.  信息搜索（潜在语义分析,LSA）

## 2 Python 实例 ##

### 2.1 基于 SVD 的图像压缩 ###

1 from numpy import *
     2 from numpy import linalg as la
     3 
     4 def printMat(inMat,thresh=0.8):
     5     for i in range(32):
     6         for k in range(32):
     7             if float(inMat[i,k])>thresh:
     8                 # pycharm中会自动换行，此处加上 end=‘’ ，以达到效果
     9                 print('1',end='')
    10             else:
    11                 print('0',end='')
    12         print('')
    13 
    14 def imgCompress(numSV=3,thresh=0.8):
    15     my1=[]
    16     for line in open('0_5.txt').readlines():
    17         newRow=[]
    18         for i in range(32):
    19             newRow.append(int(line[i]))
    20         my1.append(newRow)
    21     myMat=mat(my1)
    22     print(myMat)
    23     print("***** original matrix *****")
    24     printMat(myMat,thresh)
    25     U,Sigma,VT=la.svd(myMat)
    26     SigRecon=mat(zeros((numSV,numSV)))
    27     for k in range(numSV):
    28         SigRecon[k,k]=Sigma[k]
    29     reconMat=U[:,:numSV]*SigRecon*VT[:numSV,:]
    30     print("***** reconstructed matrix using %d singular values *****")
    31     printMat(reconMat,thresh)
    32 
    33 imgCompress(2)

![1646215-20190610221751367-839428158.png][]

分析：

1.  1.  左边原始矩阵，右边是奇异值分解后处理矩阵，得到的图像基本一致，可以看到只需要两个奇异值就能相对准确地对图像重建。
    2.  内存使用：原始图像：32\*32=1024，奇异值分解后：2\*32+2+2\*32=130，缩小了将近10倍。

## 2.2 餐馆菜肴推荐引擎 ##

过程：

1.  1.  寻找用户没有评级的菜肴，即在用户-物品矩阵中的 0 值。
    2.  在用户没有评级的所有物品中，对每个物品预计一个可能的评级的分数。（利用相似度进行计算）
    3.  对这些物品的评分从高到低排序，返回前 N 个物品。

程序:

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 from numpy import *
      2 from numpy import linalg as la
      3 import matplotlib.pyplot as plt
      4 
      5 # 1. 输入数据，用户-物品评级矩阵
      6 def loadExData2():
      7     return [[2, 0, 0, 4, 4, 0, 0, 0, 0, 0, 0],
      8             [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 5],
      9             [0, 0, 0, 0, 0, 0, 0, 1, 0, 4, 0],
     10             [3, 3, 4, 0, 3, 0, 0, 2, 2, 0, 0],
     11             [5, 5, 5, 0, 0, 0, 0, 0, 0, 0, 0],
     12             [0, 0, 0, 0, 0, 0, 5, 0, 0, 5, 0],
     13             [4, 0, 4, 0, 0, 0, 0, 0, 0, 0, 5],
     14             [0, 0, 0, 0, 0, 4, 0, 0, 0, 0, 4],
     15             [0, 0, 0, 0, 0, 0, 5, 0, 0, 5, 0],
     16             [0, 0, 0, 3, 0, 0, 0, 0, 4, 5, 0],
     17             [1, 1, 2, 1, 1, 2, 1, 0, 4, 5, 0]]
     18 
     19 # 2. 几种计算相似度的方法，
     20 # 欧式距离
     21 def ecludSim(inA,inB):
     22     return 1.0/(1.0+la.norm(inA-inB))
     23 # 皮尔逊距离
     24 def pearsSim(inA,inB):
     25     if len(inA)<3:
     26         return 1.0
     27     return 0.5+0.5*corrcoef(inA,inB,rowvar=0)[0][1]
     28 # 余弦距离
     29 def cosSim(inA,inB):
     30     num =float(inA.T*inB)
     31     denom=la.norm(inA)*la.norm(inB)
     32     return 0.5+0.5*(num/denom)
     33 
     34 # 3. 计算给定相似度计算方法下的估计评分值
     35 # 指定用户 user 给未评定物品 item 评分
     36 def standEst(dataMat,user,simMeas,item):
     37     n=shape(dataMat)[1]
     38     simTotal=0.0
     39     ratSimTotal=0.0
     40     # 遍历每一个物品，根每一个有过评分的物品比较，计算相似度，推测出评分
     41     for j in range(n):
     42         userRating=dataMat[user,j]
     43         # 如果某个用户没有对这个物品评分，跳过这个值
     44         if userRating==0:
     45             continue
     46         # 比较目标物品和已被评分过的物品重合程度
     47         overLap=nonzero(logical_and(dataMat[:,item].A>0,dataMat[:,j].A>0))[0]
     48         # 如果重合为0，则相似度为0
     49         if len(overLap)==0:
     50             similarity=0
     51         else:
     52             # 如果有重合，基于这些特征重合计算相似度
     53             similarity=simMeas(dataMat[overLap,item],dataMat[overLap,j])
     54             # print("the %d and %d similarity is: %f "%(item,j,similarity))
     55         # 累加相似度
     56         simTotal+=similarity
     57         # 累加相似度和评分的乘积，可以得到评分总和，（归一化的）
     58         ratSimTotal+=similarity*userRating
     59     if simTotal==0:
     60         return 0
     61     else:
     62         return ratSimTotal/simTotal
     63 
     64 # 4. 使用 SVD 降维后进行相似度计算
     65 def svdEst(dataMat,user,simMeas,item):
     66     n=shape(dataMat)[1]
     67     simTotal=0.0
     68     ratSimTotal=0.0
     69     U, Sigma, VT = la.svd(dataMat)
     70     # 取 sigma 前4的值，构建对角矩阵
     71     Sig4=mat(eye(4)*Sigma[:4])
     72     # 将原数据投影到左奇异矩阵上，使其行降维，即减少无效用户
     73     xformedItems=dataMat.T*U[:,:4]*Sig4.I
     74     for j in range(n):
     75         userRating=dataMat[user,j]
     76         if userRating==0 or j==item:
     77             continue
     78         similarity=simMeas(xformedItems[item,:].T,xformedItems[j,:].T)
     79         # print("the %d and %d similarity is: %f "%(item,j,similarity))
     80         simTotal += similarity
     81         # 累加相似度和评分的乘积，可以得到评分总和，（归一化的）
     82         ratSimTotal += similarity * userRating
     83     if simTotal == 0:
     84         return 0
     85     else:
     86         return ratSimTotal / simTotal
     87 
     88 # 5. 推荐引擎，返回得分较高的前 N 个物品
     89 def recommend(dataMat,user,N=3,simMeas=cosSim,estMethod=standEst):
     90     # 寻找未评级的物品
     91     unratedItems=nonzero(dataMat[user,:].A==0)[1]
     92     if len(unratedItems)==0:
     93         return print("you rated everything")
     94     itemScores=[]
     95     for item in unratedItems:
     96         estimatedScore=estMethod(dataMat,user,simMeas,item)
     97         itemScores.append((item,estimatedScore))
     98     return sorted(itemScores,key=lambda jj:jj[1],reverse=True)[:N]
     99 
    100 myMat=mat(loadExData2())
    101 print(recommend(myMat,1,estMethod=svdEst))
    102 print(recommend(myMat,1))
    103 U,Sigma,VT=linalg.svd(myMat)
    104 Sig2=Sigma**2
    105 fig=plt.figure()
    106 ax=fig.add_subplot(111)
    107 ax.pie(Sig2,autopct='%1.1f')
    108 plt.show()

结果：

![1646215-20190610215510823-470716820.png][]

![1646215-20190610215514977-1145746572.png][]

分析：

1.  对奇异值分析可知，前五个值占了绝大部分信息（注意这里与书里有些不一致）
2.  使用SVD分解后的数据推荐引擎更准确

提高构建推荐引擎时的效率：

1.  SVD 大量数据分解速度慢，尽量运行一次或者离线运行。
2.  零元素太多，通过储存非零元素节省资源。
3.  每次需要推荐一个得分时，都需要计算多个物品的相似度，离线计算并保存相似度。
4.  冷启动问题：如何在缺乏数据时给出好的推荐。将推荐看成搜索问题。

# 参考文献： #

1.  奇异值分解与在降维中的应用 [https://www.cnblogs.com/pinard/p/6251584.html][https_www.cnblogs.com_pinard_p_6251584.html]

转载于:https://www.cnblogs.com/Ray-0808/p/11000591.html

[1646215-20190610215214189-1182759864.png]: /images/20211029/776c6b8790094641977a76bed4a02372.png
[1646215-20190610215227110-559435851.png]: /images/20211029/0b110fd6832544dfaa257796c050c5c7.png
[1646215-20190610215248624-887890576.png]: /images/20211029/6d0d6b0de1f44819aaec6e9bebe8f88a.png
[1646215-20190610215319503-1816469885.png]: /images/20211029/97330e2b682446fca416fe0b386188e6.png
[1646215-20190610215347528-1916925149.png]: /images/20211029/151052b6e89b44fdad63ae714d9fab6d.png
[1646215-20190610215401314-385376911.png]: /images/20211029/9b9ccadd2c9f495c8b25e6bd27ff6887.png
[https_www.cnblogs.com_zhangchaoyang_articles_2575948.html]: https://www.cnblogs.com/zhangchaoyang/articles/2575948.html
[http_www.cs.utexas.edu_users_inderjit_public_papers_HLA_SVD.pdf]: http://www.cs.utexas.edu/users/inderjit/public_papers/HLA_SVD.pdf
[1646215-20190610221751367-839428158.png]: /images/20211029/dfa5b11fd64a41a7a7f9d6f2444c8b7c.png
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211029/6b9780e84c6b4f198519433a7e9ad251.png
[1646215-20190610215510823-470716820.png]: /images/20211029/83ad815a790a4689bd9c01f550d3a285.png
[1646215-20190610215514977-1145746572.png]: /images/20211029/fe6d5671eb3a446a895ad9b956d6cd2e.png
[https_www.cnblogs.com_pinard_p_6251584.html]: https://www.cnblogs.com/pinard/p/6251584.html