本博文内容：
- SVD矩阵分解
- 推荐引擎
- 利用SVD提升推荐引擎的性能。
提取这些信息的方法称为奇异值分解（Singular Value Decomposition，SVD）。从生物信息学 到金融学等在内的很多应用中，SVD都是提取信息的强大工具。
本章将介绍SVD的概念及其能够进行数据约简的原因。然后，我们将会介绍基于Python的 SVD实现以及将数据映射到低维空间的过程。再接下来，我们就将学习推荐引擎的概念和它们的 实际运行过程。为了提高SVD的精度，我们将会把其应用到推荐系统中去，该推荐系统将会帮助 人们寻找到合适的餐馆。最后，我们讲述一个SVD在图像压缩中的应用例子。
14.1 SVD 的应用
?利用SVD实现，我们能够用小得多的数据集来表示原始数据集。这样做，实际上是去除了噪 声和冗余信息。当我们试图节省空间时，去除噪声和冗余信息就是很崇高的目标了，但是在这里我 们则是从数据中抽取信息。基于这个视角，我们就可以把SVD看成是从有噪声数据中抽取相关特征。
14.1.1 隐性语义索引
最早的SVD应用之一就是信息检索。我们称利用SVD的方法为隐性语义索引（Latent Semantic Indexing，LSI）或隐性语义分析（Latent Semantic Analysis，LSA）
在LSI中，一个矩阵是由文档和词语组成的。当我们在该矩阵上应用SVD时，就会构建出多 个奇异值。这些奇异值代表了文档中的概念或主题，这一特点可以用于更高效的文档搜索。在词 语拼写错误时，只基于词语存在与否的简单搜索方法会遇到问题。简单搜索的另一个问题就是同 义词的使用。这就是说，当我们查找一个词时，其同义词所在的文档可能并不会匹配上。如果我 们从上千篇相似的文档中抽取出概念，那么同义词就会映射为同一概念。
14.1.2 推荐系统
SVD的另一个应用就是推荐系统。简单版本的推荐系统能够计算项或者人之间的相似度。更先进的方法则先利用SVD从数据中构建一个主题空间，然后再在该空间下计算其相似度。
??????????
?SVD是矩阵分解的一种类型，而矩阵分解是将数据矩阵分解为多个独立部分的过程。接下来我们首先介绍矩阵分解。
不同的矩阵分解技术具有不同的性质，其中有些更适合于某个应用，有些则更适合于其他应 用。最常见的一种矩阵分解技术就是SVD。SVD将原始的数据集矩阵Data分解成三个矩阵U、Σ 和VT 。如果原始矩阵Data是m行n列，那么U、Σ和VT 就分别是m行m列、m行n列和n行n列。
奇异值（Singular Value）
14.3 利用Python 实现SVD
def loadExData():
return [[1, 1, 1, 0, 0],
[2, 2, 2, 0, 0],
[1, 1, 1, 0, 0],
[5, 5, 5, 0, 0],
[1, 1, 0, 2, 2],
[0, 0, 0, 3, 3],
[0, 0, 0, 1, 1]]
?
我们是如何知道仅需保留前3个奇异值的呢？确定要保留的奇异值的数目有很多启发式的策 略，其中一个典型的做法就是保留矩阵中90%的能量信息。为了计算总能量信息，我们将所有的 奇异值求其平方和。于是可以将奇异值的平方和累加到总值的90%为止。另一个启发式策略就是， 当矩阵上有上万的奇异值时，那么就保留前面的2000或3000个。尽管后一种方法不太优雅，但是 在实际中更容易实施。之所以说它不够优雅，就是因为在任何数据集上都不能保证前3000个奇异 值就能够包含90%的能量信息。但在通常情况下，使用者往往都对数据有足够的了解，从而就能 够做出类似的假设了。 现在我们已经通过三个矩阵对原始矩阵进行了近似。我们可以用一个小很多的矩阵来表示一 个大矩阵。有很多应用可以通过SVD来提升性能。下面我们将讨论一个比较流行的SVD应用的例 子——推荐引擎。
14.4 基于协同过滤的推荐引擎
唯一所需要的数学方法就是相似度的计算
我们首 先讨论物品之间的相似度计算，然后讨论在基于物品和基于用户的相似度计算之间的折中。最后， 我们介绍推荐引擎成功的度量方法。
14.4.1 相似度计算
第一种我们可以用“相似度=1/(1+距离)”这样的算式来计算相似度。当距离为0时， 相似度为1.0。如果距离真的非常大时，相似度也就趋近于0。
第二种计算距离的方法是皮尔逊相关系数（Pearson correlation）。
另一个常用的距离计算方法就是余弦相似度（cosine similarity），其计算的是两个向量夹角的 余弦值。如果夹角为90度，则相似度为0；如果两个向量的方向相同，则相似度为1.0。同皮尔逊
相关系数一样，余弦相似度的取值范围也在?1到+1之间，因此我们也将它归一化到0到1之间。
from numpy import *
from numpy import linalg as la
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)?程序中的3个函数就是上面提到的几种相似度的计算方法。为了便于理解，NumPy的线性代 数工具箱linalg被作为la导入，函数中假定inA和inB都是列向量。perasSim()函数会检查是否 存在3个或更多的点。如果不存在，该函数返回1.0，这是因为此时两个向量完全相关。
14.4.2 基于物品的相似度还是基于用户的相似度？
我们计算了两个餐馆菜肴之间的距离，这称为基于物品（item-based）的相似度。另一种计 算用户距离的方法则称为基于用户（user-based）的相似度。
14.4.3 推荐引擎的评价
如何对推荐引擎进行评价呢？此时，我们既没有预测的目标值，也没有用户来调查他们对预 测的满意程度。这里我们就可以采用前面多次使用的交叉测试的方法。具体的做法就是，我们将 某些已知的评分值去掉，然后对它们进行预测，最后计算预测值和真实值之间的差异。 通常用于推荐引擎评价的指标是称为最小均方根误差（Root Mean Squared Error，RMSE）的 指标，它首先计算均方误差的平均值然后取其平方根。如果评级在1星到5星这个范围内，而我们 得到的RMSE为1.0，那么就意味着我们的预测值和用户给出的真实评价相差了一个星级。
14.5 示例，餐馆菜肴推荐引擎
14.5.1 推荐未尝过的菜肴
推荐系统的工作过程是：给定一个用户，系统会为此用户返回N个最好的推荐菜。为了实现 这一点，则需要我们做到：
(1) 寻找用户没有评级的菜肴，即在用户－物品矩阵中的0值；
(2) 在用户没有评级的所有物品中，对每个物品预计一个可能的评级分数。这就是说，我们 认为用户可能会对物品的打分（这就是相似度计算的初衷）；
(3) 对这些物品的评分从高到低进行排序，返回前N个物品。
# Item-based recommendation engine
# calculates the estimated rating a user would give an item for a given similarity measure.
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]
if userRating == 0:
continue
overLap = nonzero(logical_and(dataMat[:,item].A>0,dataMat[:,j].A>0))[0] # Find items rated by both users
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
else:
return ratSimTotal/simTotal
# recommend() is the recommendation engine
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]
15.5.2 利用SVD提高推荐的效果。
实际的数据集会比我们用于展示recommend()函数功能的myMat矩阵稀疏得多。
def loadExData():
return [[1, 1, 1, 0, 0],
[2, 2, 2, 0, 0],
[1, 1, 1, 0, 0],
[5, 5, 5, 0, 0],
[1, 1, 0, 2, 2],
[0, 0, 0, 3, 3],
[0, 0, 0, 1, 1]]
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]]
from numpy import *
from numpy import linalg as la
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)
# Item-based recommendation engine
# calculates the estimated rating a user would give an item for a given similarity measure.
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]
if userRating == 0:
continue
overLap = nonzero(logical_and(dataMat[:,item].A>0,dataMat[:,j].A>0))[0] # Find items rated by both users
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
else:
return ratSimTotal/simTotal
# recommend() is the recommendation engine
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]
?我们可以将一个11维的矩阵转换成一个3维的矩阵。 下面对转换后的三维空间构造出一个相似度计算函数。我们利用SVD将所有的菜肴映射到一个低 维空间中去。在低维空间下，可以利用前面相同的相似度计算方法来进行推荐。我们会构造出一 个类似于程序清单14-2中的standEst()函数。
def svdEst(dataMat, user, simMeas, item):
n = shape(dataMat)[1]
simTotal = 0.0
ratSimTotal = 0.0
U,Sigma,VT = la.svd(dataMat)
Sig4 = mat(eye(4)*Sigma[:4])
xformedItems = dataMat.T * U[:,:4] * Sig4.I
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?
14.5.3 构建推荐引擎面临的挑战
推荐引擎面临的另一个问题就是如何在缺乏数据时给出好的推荐。这称为冷启动（cold-start） 问题，处理起来十分困难。冷启动问题的解决方案，就是将推荐看成是搜索问题。在内部表现上，不同的解决办法虽然 有所不同，但是对用户而言却都是透明的。为了将推荐看成是搜索问题，我们可能要使用所需要 推荐物品的属性。在餐馆菜肴的例子中，我们可以通过各种标签来标记菜肴，比如素食、美式BBQ、 价格很贵等。同时，我们也可以将这些属性作为相似度计算所需要的数据，这被称为基于内容 （content-based）的推荐。可能，基于内容的推荐并不如我们前面介绍的基于协同过滤的推荐效果 好，但我们拥有它，这就是个良好的开始。
?14.6 示例： 基于SVD 的图像压缩
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)
U,Sigma,VT = la.svd(myMat)
SigRecon = mat(zeros((numSV,numSV)))
for k in range(numSV):
SigRecon[k,k] = Sigma[k]
reconMat = U[:,:numSV]*SigRecon*VT[:numSV,:]
print("****reconstrated matrix using %d singular values******"% numSV)
printMat(reconMat, thresh)
14.7 Summary
SVD是一种强大的降维工具，我们可以利用SVD来逼近矩阵并从中提取重要特征。通过保留 矩阵80%～90%的能量，就可以得到重要的特征并去掉噪声。SVD已经运用到了多个应用中，其 中一个成功的应用案例就是推荐引擎。 推荐引擎将物品推荐给用户，协同过滤则是一种基于用户喜好或行为数据的推荐的实现方法。协同过滤的核心是相似度计算方法，有很多相似度计算方法都可以用于计算物品或用户之间 的相似度。通过在低维空间下计算相似度，SVD提高了推荐系引擎的效果。 在大规模数据集上，SVD的计算和推荐可能是一个很困难的工程问题。通过离线方式来进行 SVD分解和相似度计算，是一种减少冗余计算和推荐所需时间的办法。在下一章中，我们将介绍 在大数据集上进行机器学习的一些工具。
