SVD算法来简化数据
1.SVD简介
SVD(Singular Value Decomposition)，奇异值分解，也就是将一个矩阵进行分解，然后从分解后的矩阵上对数据进行分析。矩阵分解可以将原始矩阵表示成新的易于处理的形式，这种新的形式是两个或者多个矩阵的乘积，如下形式：
如式1，将原始矩阵分解为三个矩阵相乘的形式，其中中间的Σ只有对角元素。其他元素都为0，并且对角元素是从大到小排列的，这些元素成为奇异值，也就是原始数据矩阵的奇异值。我们可以利用这些奇异值对数据进行降维，从而用更小的数据集来表示原始数据，并且这些降维后的数据往往保留了80%~90%的原始信息，也就相当于用较小的数据量包含的大部分的信息，从而去掉了那些冗余和噪声信息。
2.奇异值与特征值
特征值分解和奇异值分解，两者有着紧密的联系，其目的都是一样的都是提取一个矩阵的最重要的特征。
先说特征值分解。特征值分解我在另一篇文章《PCA算法来简化数据》中有简单的介绍，但是没有提到分解的概念，只提到了降维的概念，其实目的都是一样的：
如式2所示，我们将A分解为三个矩阵的乘积的形式，其中Q是A对应的特征向量组成的矩阵，Σ是对应的特征值组成的对角矩阵。我们在对其进行特征值分解的时候，都需要求解方阵A的特征值和特征向量，然后对特征值以及对应的特征向量进行排序，然后取出前几个占比比较大的维度（方向）对原始矩阵A进行降维，也就是提取这个矩阵最重要的特征（此特征非A中对应的特征值的特征，只是表示矩阵A变化的特征，具体参考《PCA算法来简化数据》）。
特征值降维可以大大的降低数据的维度，但是它也有自己的局限性，比如说它要求矩阵A必须是方阵。
下面说奇异值分解。我们看公式1，我们将原始矩阵分成了三个矩阵相乘的形式，但是此时的A不是方阵，所以说奇异值分解适用于任何矩阵。其中U是一个m×m的正交矩阵，里面的向量成为左奇异向量，V是一个n×n的正交矩阵，里面的向量称为有奇异向量。但是这两个正交矩阵是怎么来的呢？
我们用矩阵A乘以矩阵A的转置，得到一个m×m的方阵，然后对这个方阵进行特征值分解：
这就又回到了特征值和特征向量的概念，λ是特征值，u是特征向量,也就是我们说的左奇异向量，然后所有的特征向量组成了m×m的正交矩阵。
同理们用矩阵A的转置乘以矩阵A,然后就得到了一个n×n的方阵，然后进行特征值分解就得到了一个n×n的正交矩阵V，里面的向量就是右奇异向量。
另外我们也可以得出下列公式：
其中σ就是奇异值，u是左奇异向量，v是右奇异向量。奇异值σ和特征值类似，也是在Σ矩阵中从大到小的对角矩阵，而且σ的减少特别的快，在很多情况下，前10%甚至1%的奇异值的和就占了全部的奇异值之和的99%以上了。也就是说，我们也可以用前r大的奇异值来近似描述矩阵，这里定义一下部分奇异值分解：
我们将式1矩阵分解中的右侧部分的n变成了r，这就是降维了，降维的过程和特征值特征向量的降维类似，我们这里取的是奇异值的前r个，然后可能包含了大部分的信息，所以就只保留了前r个特征来表示矩阵A，近似等于原矩阵。由于分解后的三个矩阵维度相对较小，所以我们就可以用保存更小的三个矩阵(U,Σ,V)近似替代原矩阵即可。如图1所示：
图1
3.SVD的应用
我们前面介绍了，SVD对数据进行降维就是先对矩阵进行矩阵分解，然后取主要的奇异值对矩阵进行降维，一是减少了数据量，并且还去除了噪声和冗余数据。其主要应用可以用于推荐系统和隐性语义检索（LSI）。
我们先介绍这个推荐系统的，后面还会通过python代码进行一个例子的说明。
推荐系统需要计算特征值之间的相似度，相似度的计算主要有三种方式：
- 计算属性之间的欧氏距离，即两个点之间的距离公式。我们用“相似度=1/(1+距离)”这样的方式垃圾算相似度。当距离为0的时候，相似度为1.0，当相似度非常大的时候，相似度也就趋近于0。
- 第二个是皮尔逊相关系数。皮尔逊相关系数的取值范围从-1到+1，我们通过0.5*0.5*corrcoef()这个函数计算，并且将其取值范围规划到0到1之间。
- 余弦相似度。其计算的是两个向量夹角的余弦值。如果夹角度数为90度，则相似度为0，如果两个向量的方向相同，则相似度为1.0。同皮尔逊相关系数一样，余弦相似度的取值范围也在-1到+1之间，因此我们也将它归一化到0和1之间。我们将两个向量A和B的余弦相似度的定义如下：
下面我们通过代码来看相似度的计算
def ecludSim(inA,inB):
return 1.0/(1.0 + la.norm(inA - inB))
def pearsSim(inA,inB):
if len(inA) < 3 : return 1.0
return 0.5+0.5*corrcoef(inA, inB, rowvar = 0)[0][1]
def cosSim(inA,inB):
num = float(inA.T*inB)
denom = la.norm(inA)*la.norm(inB)
return 0.5+0.5*(num/denom)
函数ecludSim是通过欧式距离来计算相似度，pearsSim是通过皮尔逊相关系数计算相似度，cosSim是通过余弦相似度来计算相似度。这三个函数都是计算两个特征之间的相似度，也就是说输入参数都是两个向量。
下面我们通过一个餐馆才要推荐的例子，来看一下推荐。
推荐系统的工作过程：给定一个用户，系统会为此用户返回N个最好的推荐菜。为了实现这一点，则需要我们做到：
- 寻找用户没有评级的菜肴，即在用户和物品的矩阵中的0值。数据集如下：
[4, 4, 0, 2, 2], [4, 0, 0, 3, 3], [4, 0, 0, 1, 1], [1, 1, 1, 0, 0], [2, 2, 2, 0, 0], [5, 5, 5, 0, 0], [1, 1, 1, 0, 0]
每一行是每个用户对每个菜品的评分。
- 用户没有经济的所有物品中，对每个物品预计一个可能的评分数。这就是说，我们认为用户可能会对物品的打分（这就是相似度计算的初衷）。
- 对这些物品的评分从高到低，返回前N个物品。
下面通过代码来分析这个过程：
''' dataMat:数据矩阵 user:用户编号 simMeas计算相似度的方法，就如上面的三种方法 item:商品编号 ''' def standEst(dataMat, user, simMeas, item): n = shape(dataMat)[1] #数据的商品的个数 simTotal = 0.0; ratSimTotal = 0.0 for j in range(n): userRating = dataMat[user,j] #用户对第j个商品的评分 if userRating == 0: continue #如果评分为0，说明没有评分，跳过此次循环 overLap = nonzero(logical_and(dataMat[:,item].A>0, \ dataMat[:,j].A>0))[0] #挑出所有对商品item和j都有评价的用户 if len(overLap) == 0: similarity = 0 else: similarity = simMeas(dataMat[overLap,item], \ dataMat[overLap,j]) #计算商品item和j的相似度 print 'the %d and %d similarity is: %f' % (item, j, similarity) simTotal += similarity #商品的相似度之和 ratSimTotal += similarity * userRating #相似度乘以评分然后求和 if simTotal == 0: return 0 else: return ratSimTotal/simTotal
上面的函数是没有进行降维的计算相似度计算的方法，下面是入口函数：
''' dataMat：数据 user:用户编号 N:返回的前N个推荐个数，默认为3 simMeas：相似度计算方法，默认预先计算方法 estMethod:计算推荐度的方法 ''' def recommend(dataMat, user, N=3, simMeas=cosSim, estMethod=standEst): unratedItems = nonzero(dataMat[user,:].A==0)[1]#查找用户没有评价过的商品 if len(unratedItems) == 0: return 'you rated everything' itemScores = [] for item in unratedItems: #循环用户未评价过的商品 estimatedScore = estMethod(dataMat, user, simMeas, item) #计算用户未评价过的商品和其他评级过的商品之间的相似度信息 itemScores.append((item, estimatedScore)) return sorted(itemScores, key=lambda jj: jj[1], reverse=True)[:N] #对相似度信息进行排序，并返回前N个推荐值
总体来说这个方法计算某个用户所有未评价过的商品和其他商品的相似度，然后返回相似度排名，取前N个商品推荐。函数recommend中计算推荐度相关的函数用的是standEst，这个函数名是可以作为estMethod参数传过去的。下面给出SVD降维的推荐方法，用的函数如下：
def svdEst(dataMat, user, simMeas, item): n = shape(dataMat)[1] simTotal = 0.0; ratSimTotal = 0.0 U,Sigma,VT = la.svd(dataMat) #分解矩阵 U:左奇异矩阵，Sigma:奇异值矩阵，VT:右奇异矩阵的转置 Sig4 = mat(eye(4)*Sigma[:4]) # 我感觉这里应该是取了前4个奇异值 xformedItems = dataMat.T * U[:,:4] * Sig4.I #对数据进行降维 for j in range(n): #这个循环就是计算商品item和每个其他评价过的商品相似度，但请注意这里用到的额是降维后的数据 userRating = dataMat[user,j] if userRating == 0 or j==item: continue similarity = simMeas(xformedItems[item,:].T,\ xformedItems[j,:].T) print 'the %d and %d similarity is: %f' % (item, j, similarity) simTotal += similarity ratSimTotal += similarity * userRating if simTotal == 0: return 0 else: return ratSimTotal/simTotal
其这里用到的矩阵的数据如下：
[0, 0, 0, 0, 0, 4, 0, 0, 0, 0, 5], [0, 0, 0, 3, 0, 4, 0, 0, 0, 0, 3], [0, 0, 0, 0, 4, 0, 0, 1, 0, 4, 0], [3, 3, 4, 0, 0, 0, 0, 2, 2, 0, 0], [5, 4, 5, 0, 0, 0, 0, 5, 5, 0, 0], [0, 0, 0, 0, 5, 0, 1, 0, 0, 5, 0], [4, 3, 4, 0, 0, 0, 0, 5, 5, 0, 1], [0, 0, 0, 4, 0, 4, 0, 0, 0, 0, 4], [0, 0, 0, 2, 0, 2, 5, 0, 0, 1, 2], [0, 0, 0, 0, 5, 0, 0, 0, 0, 4, 0], [1, 0, 0, 0, 0, 0, 0, 1, 2, 0, 0]
每一行还是用户对每一件商品的评价分数。我们给出svdEst函数中降维后的xformedItems数据形式可能，可能帮助理解：
[[-0.45137416 0.03084799 -0.00290108 0.01189185]
[-0.36239706 0.02584428 -0.00189127 0.01348796]
[-0.46879252 0.03296133 -0.00281253 0.01656192]
[-0.01007685 -0.34024331 -0.22728592 0.14546051]
[-0.01567036 -0.38750193 0.61197998 -0.17137451]
[-0.01664563 -0.52000097 -0.3608907 -0.14984063]
[-0.00474684 -0.18887149 -0.00924222 0.94228361]
[-0.46712774 0.00389831 0.03349951 -0.02080674]
[-0.47223188 0.02853952 -0.00504059 0.00160266]
[-0.01591788 -0.39205093 0.55707516 0.04356321]
[-0.0552444 -0.52034959 -0.36330956 -0.19023805]]
从代码中来看，我们是取的每一行的数据计算两行数据之间的相似度，所以降维后，属性值并没有减少，只是每个商品取得样本数少了（个人理解）。
下面我们来看隐性语义检索。这部分内容，我直接引用网上别人的一个例子，文章后面会给出相应的文章参考地址：
奇异值与潜在语义索引LSI：
潜在语义索引（Latent Semantic Indexing）与PCA不太一样，至少不是实现了SVD就可以直接用的，不过LSI也是一个严重依赖于SVD的算法，之前吴军老师在矩阵计算与文本处理中的分类问题中谈到：
“三个矩阵有非常清楚的物理含义。第一个矩阵X中的每一行表示意思相关的一类词，其中的每个非零元素表示这类词中每个词的重要性（或者说相关性），数值越大越相关。最后一个矩阵Y中的每一列表示同一主题一类文章，其中每个元素表示这类文章中每篇文章的相关性。中间的矩阵则表示类词和文章雷之间的相关性。因此，我们只要对关联矩阵A进行一次奇异值分解，w 我们就可以同时完成了近义词分类和文章的分类。（同时得到每类文章和每类词的相关性）。”
上面这段话可能不太容易理解，不过这就是LSI的精髓内容，我下面举一个例子来说明一下，下面的例子来自LSA tutorial，具体的网址我将在最后的引用中给出：
这就是一个矩阵，不过不太一样的是，这里的一行表示一个词在哪些title中出现了（一行就是之前说的一维feature），一列表示一个title中有哪些词，（这个矩阵其实是我们之前说的那种一行是一个sample的形式的一种转置，这个会使得我们的左右奇异向量的意义产生变化，但是不会影响我们计算的过程）。比如说T1这个title中就有guide、investing、market、stock四个词，各出现了一次，我们将这个矩阵进行SVD，得到下面的矩阵：
左奇异向量表示词的一些特性，右奇异向量表示文档的一些特性，中间的奇异值矩阵表示左奇异向量的一行与右奇异向量的一列的重要程序，数字越大越重要。
继续看这个矩阵还可以发现一些有意思的东西，首先，左奇异向量的第一列表示每一个词的出现频繁程度，虽然不是线性的，但是可以认为是一个大概的描述，比如book是0.15对应文档中出现的2次，investing是0.74对应了文档中出现了9次，rich是0.36对应文档中出现了3次；
其次，右奇异向量中一的第一行表示每一篇文档中的出现词的个数的近似，比如说，T6是0.49，出现了5个词，T2是0.22，出现了2个词。
然后我们反过头来看，我们可以将左奇异向量和右奇异向量都取后2维（之前是3维的矩阵），投影到一个平面上，可以得到：
在图上，每一个红色的点，都表示一个词，每一个蓝色的点，都表示一篇文档，这样我们可以对这些词和文档进行聚类，比如说stock 和 market可以放在一类，因为他们老是出现在一起，real和estate可以放在一类，dads，guide这种词就看起来有点孤立了，我们就不对他们进行合并了。按这样聚类出现的效果，可以提取文档集合中的近义词，这样当用户检索文档的时候，是用语义级别（近义词集合）去检索了，而不是之前的词的级别。这样一减少我们的检索、存储量，因为这样压缩的文档集合和PCA是异曲同工的，二可以提高我们的用户体验，用户输入一个词，我们可以在这个词的近义词的集合中去找，这是传统的索引无法做到的。
参考：
https://mp.weixin.qq.com/s/Dv51K8JETakIKe5dPBAPVg
隐性语义索引、部分图及内容：
https://www.cnblogs.com/LeftNotEasy/archive/2011/01/19/svd-and-applications.html
代码：
《机器学习实战》第14章