奇异值分解：SVD（singular value decomposition）
1.1 SVD的应用
利用SVD我们能用小的多的数据来表示原始的数据集。这样做，实际上是去除了噪声和冗余信息。我们是从数据中抽取信息。基于这个视角，我们可以把SVD看成从噪声数据中提取相关特征。
先来学习SVD是如何通过隐性语义索引应用于搜索和信息检索领域的。然后，再介绍SVD在推荐系统中的应用。
1.1.1 隐性语义索引
最早的SVD应用之一就是信息检索。我们称利用SVD的方法为隐性语义索引（latent semantic indexing，LSI）或隐性语义分析（latent semantic analysis，LSA）。
在LSI中，一个矩阵是由文档和词语组成的。当我们在该矩阵上应用SVD时，就会构建出多个奇异值。这些奇异值代表了文档中的主题或概念，这一特点可以用于更高效的文档搜索。当我们从上千篇相似的文档中抽取概念，那么同义词就会映射为同一概念。
1.1.2 推荐系统
SVD的另一个应用就是推荐系统。利用SVD从数据中构建一个主题空间，然后在该空间下计算相似度。
上图中的矩阵是餐馆的菜和品菜师对这些菜的意见构成的。菜的评级由1-5，如果没有尝过，则为0。
我们对上述矩阵进行SVD处理，会得到两个奇异值。因此就仿佛有两个概念主题与此数据集相关。观察右图的阴影部分，前三人只对烤牛肉和手撕猪肉进行了评级，而对前三样菜没有评级。烤牛肉与手撕猪肉都是美式烧烤店才有的菜，其他的只有在日式餐馆中才有。
我们可以把奇异值想象成一个新的空间，与上面的五维或七维空间不同，我们的最终空间只有二维。这二维分别对用图中两个部分，我们可以基于每个组的共同特征来命名这二维，比如我们得到的 美式BBQ 和 日式食品 这二维。
推荐引擎中可能会有噪声数据，比如某个人对某些菜的评级就可能存在噪声，并且推荐系统也能将数据抽取为这些基本主题。基于这些主题，推荐系统就能取得比原始数据更好的推荐效果。
1.2 矩阵分解
矩阵分解可以将矩阵分解为新的易于处理的形式，这种新的形式就是两个或则多个矩阵的乘积。
不同的矩阵分解技术具有不同的性质，其中有些更适合于某个应用。最常见的分解技术就是SVD。SVD将原始数据集分解为U,
和V.T。如果原始数据是m行n列，那么U ,
和V.T就分别是(m,m) (m,n) (n,n)。
上述分解中会构建一个矩阵
，该矩阵只有对角元素，其他均值为0。另一个惯例就是，
的对角元素是从大到小排列的。这些对角元素称为 奇异值（singular value），它们对应了原始数据集的奇异值。之前的PCA技术，我们得到的是矩阵的特征值，它们告诉我们矩阵的重要特征。
中的奇异值也是如此。奇异值与特征值是有关系的。这里的奇异值就是矩阵
特征值的平方根。
在科学和工程中有这么一个普遍事实：在某个奇异值的数目之后，其他的奇异值都是0。这就意味着数据集中只有r个重要特征，而其他特征都是噪声或则冗余特征。
1.3 利用python实现SVD
Numpy有一个linalg的线性代数工具箱，可以用来实现矩阵的SVD处理。
from numpy import *
U, Sigma, VT = linalg.svd([[1,1],[7,7]])
在更大的数据集上进行计算：
def loadExData():
return[[0, 0, 0, 2, 2],
[0, 0, 0, 3, 3],
[0, 0, 0, 1, 1],
[1, 1, 1, 0, 0],
[2, 2, 2, 0, 0],
[5, 5, 5, 0, 0],
[1, 1, 1, 0, 0]]
Data = loadExData()
U, Sigma, VT = linalg.svd(Data)
Sigma
前三（二？）个值比后面的大得多。于是将后面两个值去掉。
我们的原始数据集就可以用下面的结果来近似了：
利用前三个奇异值来近似我们原来的矩阵。保留奇异值的数目一个典型方法就是保留矩阵中90%的能量信息。
总的能量信息为所有的奇异值平方求和，将奇异值的平方和累加到总值得90%即可。
现在我们用一个小很多的矩阵近似了原来的数据集，现在我们讨论一个SVD应用最广泛的例子----推荐引擎。
1.4 基于协同过滤的推荐引擎
使用 协同过滤（collaborative filtering) 的方法，通过将用户和其他用户的数据进行对比来实现推荐的。
当知道了两个用户或则两个物品之间的相似度之后，就可以利用已有的数据来预测未知用户的喜好。例如对用户推荐电影，推荐引擎会把用户没看过的电影与用户看过的电影之间计算相似度，如果相似度很高就会认为用户会喜欢这部电影。
1.4.1 相似度计算
物品之间相似度的定量方法。我们不利用专家所给的重要属性来描述物品从而计算他们之间的相似度，而是利用用户对他们的意见来计算相似度。这就是协同过滤中所使用的方法。它并不关心物品的描述属性，而是严格地计算许多用户的观点来计算相似度。 下图给出了一些用户对菜肴评级信息组成的矩阵。
计算一下手撕猪肉和烤牛肉之间的相似度。一开始使用欧氏距离计算：
手撕猪肉和鳗鱼饭之间的欧氏距离：
因为手撕猪肉到烤牛肉之间的距离小于鳗鱼饭，所以我们认为手撕猪肉与烤牛肉更相似。
我们希望相似度在0到1之间变化，并且物品对越相似，它们的相似度也越大。我们可以利用 ‘相似度=1/（1+距离）’这样的公式来计算相似度。当距离为0时，相似度为1，距离很大时，相似度就接近0。
第二种计算方法叫做 皮尔逊相关系数（pearson correlation）。我们在第八章度量回归方程的精度时曾用到这个量，它度量的是两个向量之间的相似度。该方法的优势在于，它对用户的评级的量级并不敏感。比如全是5分和全是1分，皮尔逊相关系数会认为这两个向量是相等的。在Numpy中，皮尔逊相关系数的计算是由函数corrcoef（）进行的。皮尔逊相关系数的取值在-1到1之间，通过0.5+0.5*corrcoef（）这个函数把取值范围归一化到0-1之间。
另一种常用的距离计算方法就是 余弦相似度（cosine similarity），其计算的是两个向量的夹角的余弦值。如果夹角是90度，则相似度为0；如果两个向量的方向相同，则相似度为1.0。同皮尔逊县相关系数一样取值在-1到+1之间。计算余弦相似度，我们采用：
同样，numpy的线性代数工具箱中提供了范数计算方法linalg.norm()。
相似度计算：
from numpy import *
from numpy import linalg as la
def ecludSim(inA, inB):
return 1.0/(1.0 + la.norm(inA - inB)) # 基于欧氏距离的相似度（0-1）
def pearsSim(inA, inB):
if len(inA) < 3:
return 1.0
return 0.5 + 0.5*corrcoef(inA, inB, rowvar = 0)[0][1] # 皮尔逊相关系数（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) # 余弦相似度（0-1）
计算结果：
上面的相似度计算都是假设数据采用了列向量方式进行表示，暗示我们将利用基于物品的相似度计算方法。
1.4.2 基于物品的相似度还是基于用户的相似度
对于大多数产品导向的推荐引擎而言，用户的数量往往远远大于物品的数量，所以一般计算基于物品的相似度。
1.4.3 推荐引擎评价
交叉测试：将某些已知的评分值去掉，然后对他们进行预测，最后计算预测值和真实值之间的差异。
通常的指标为：最小均方根误差（RMSE， root mean squared error）。首先计算均方误差的平均值再取其平方根。
1.5 示例：餐馆菜肴推荐引擎
构建一个基本的推荐引擎，它能够寻找用户没有尝过的菜肴。
- 寻找用户没有评级的菜, 即在用户-物品矩阵中的0值;
- 在用户没有评级的所有物品中,对每个物品预计一个可能的评级分数.
- 对这些物品的评分从高到低进行排序,返回前n个物品
1.5.1
基于物品相似度的推荐引擎：
# 用来计算在给定相似度计算方法的条件下，用户对物品的估计评分值
# 参数：数据矩阵、用户编号、物品编号、相似度计算方法，矩阵采用图1和图2的形式
# 即行对应用户、列对应物品
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]
# 如果某个物品评分值为0，意味着用户没有对该物品评分，跳过
# print('item:',dataMat[:, item])
# print('j:',dataMat[:,j])
if userRating == 0 : continue
# 寻找两个用户都评级的物品，变量overLap给出的是两个物品当中已经被评分的那个元素
overLap = nonzero(logical_and(dataMat[:, item].A>0, dataMat[:, j].A>0))[0]
# 若两者没有任何重合元素，则相似度为0且中止本次循环
# print('overlap:',overLap)
if len(overLap) == 0 : similarity = 0
# 如果存在重合的物品，则基于这些重合物品计算相似度
else : similarity = simMeas(dataMat[overLap, item], dataMat[overLap, j])
# print 'the %d and %d similarity is : %f' % (item, j, similarity)
# 随后相似度不断累加
simTotal += similarity
ratSimTotal += similarity * userRating
if simTotal == 0 : return 0
# 通过除以所有的评分总和，对上述相似度评分的乘积进行归一化。这使得评分值在0-5之间，
# 而这些评分值则用于对预测值进行排序
else : return ratSimTotal/simTotal
# 推荐引擎，会调用standEst()函数，产生最高的N个推荐结果。
# 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 :
# 对于每个未评分物品，通过调用standEst()来产生该物品的预测评分。
estimatedScore = estMethod(dataMat, user, simMeas, item)
# 该物品的编号和估计得分值会放在一个元素列表itemScores
itemScores.append((item, estimatedScore))
# 寻找前N个未评级物品
return sorted(itemScores, key=lambda jj : jj[1], reverse=True)[:N]
我们修改矩阵实例然后尝试使用这个推荐引擎：
尝试使用不同的相似度计算方法来验证：
给用户2（对应矩阵第三行）推荐了物品2（对应矩阵第3列）和物品1（对应矩阵第2列）以及他们相似度的值。
现在我们了解了如何根据基于物品的相似度计算方法来进行推荐的过程，下面将使用SVD应用在推荐中。
1.5.2 利用SVD提高推荐效果
实际的数据集要比我们刚才用于测试的矩阵稀疏的多。
计算该矩阵的SVD来了解到底需要多少维的特征。
def loadExData2():
return[[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]]
U, Sigma, VT = la.svd(mat(loadExData2()))
Sigma
计算出的Sigma：
我们看看有多少的奇异值能达到总能量的90%。首先对Sigma中的值求平方：
总能量：
总能量的90%
计算前三个元素所包含的能量：
包含的能量高于总能量的90%了。就将一个11维的矩阵转换为3维的矩阵了。
下面对转换后的三维空间构造一个相似度计算函数。利用SVD将所有的菜肴映射到一个低维空间中去。在低维空间下，就可以利用前面相同的方法进行推荐。
def svdEst(dataMat, user, simMeas, item):
n = shape(dataMat)[1]
simTotal = 0.0; ratSimTotal = 0.0
U,Sigma,VT = la.svd(dataMat) # SVD分解 此时Sigma简写为行向量
Sig4 = mat(eye(4)*Sigma[:4]) # 转化为4*4的对角矩阵
xformedItems = dataMat.T * U[:,:4] * Sig4.I #create transformed items
# 在对应的行上进行遍历
for j in range(n):
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
程序的执行效果：
1.5.3 构建推荐引擎面临的挑战
推荐引擎面临的另一个问题就是如何在缺乏数据时给出好的推荐。这称为冷启动（cold-start）问题：用户不会喜欢一个无效的物品，而用户不喜欢的物品又无效。
冷启动的解决方案，就是将推荐问题看成搜索问题。在内部表现上，不同的解决办法有所不同，但是对用户而言却是透明的。为了将推荐问题看成搜索问题，我们可能要使用所推荐物品的属性。
例如在菜肴参观的例子中，我们可以通过各种标签标记采样，如：素食、美式BBQ、价格很贵等。同时也将这些属性作为相似度计算所需要的数据，这称为 基于内容（content-based）推荐。
1.6 基于SVD的图像压缩
使用SVD对数据降维，从而实现图像的压缩。
# 原始图像大小 32*32=1024
# 打印矩阵
def printMat(inMat, thresh=0.8):
for i in range(32):
for k in range(32):
if float(inMat[i,k]) > thresh:
#print (1)
inMat[i,k] = 1
else:
#print (0)
inMat[i,k] = 0
# 基于任意的奇异值数目来重构图像
def imgCompress(numSV=3, thresh=0.8):
myl = []
for line in open('0_5.txt').readlines():
newRow = []
for i in range(32):
newRow.append(int(line[i]))
myl.append(newRow)
myMat = mat(myl)
print ("****original matrix******")
printMat(myMat, thresh)
print (myMat)
U,Sigma,VT = la.svd(myMat)
SigRecon = mat(zeros((numSV, numSV)))
for k in range(numSV): # Sigma对角矩阵
SigRecon[k,k] = Sigma[k]
reconMat = U[:,:numSV]*SigRecon*VT[:numSV,:]
print ("****reconstructed matrix using %d singular values******" % numSV)
printMat(reconMat, thresh)
print(reconMat)
观察该函数的运行结果可以看到，只需要两个奇异值就可以实现对图像的重构。我们总计需要多少个0.1数字来重构数据呢？U和V.T都是32*2的矩阵，有两个奇异值。因此总计的数目为64+64+2=130，与原数目1024相比，我们获得了几乎10倍的压缩比。
1.7 小结
可以利用SVD逼近矩阵并从中提取到重要的特征。通过保留90%的能量可以得到重要特征并且去掉噪声。
推荐引擎将物品推荐给用户，协同过滤则是一种基于用户喜好或行为数据的推荐的实现方法，核心是相似度的计算方法。通过在低维空间下计算相似度，SVD提高了推荐引擎的效果。
在大数据集上，SVD的计算和推荐可以通过离线方式进行SVD分解和相似度计算，是一种减少冗余计算和推荐所需的时间的办法。