一、推荐算法概述
对于推荐系统(Recommend System, RS)，从广义上的理解为：为用户(User)推荐相关的商品(Items)。常用的推荐算法主要有：
- 基于内容的推荐(Content-Based Recommendation)
- 协同过滤的推荐(Collaborative Filtering Recommendation)
- 基于关联规则的推荐(Association Rule-Based Recommendation)
- 基于效用的推荐(Utility-Based Recommendation)
- 基于知识的推荐(Knowledge-Based Recommendation)
- 组合推荐(Hybrid Recommendation)
在推荐系统中，最重要的数据是用户对商品的打分数据，数据形式如下所示：
其中，<nobr style="box-sizing: border-box;">U1⋯U5</nobr>表示的是<nobr style="box-sizing: border-box;">5</nobr>个不同的用户，<nobr style="box-sizing: border-box;">D1⋯D4</nobr>表示的是<nobr style="box-sizing: border-box;">4</nobr>个不同的商品，这样便构成了用户-商品矩阵，在该矩阵中，有用户对每一件商品的打分，其中“-”表示的是用户未对该商品进行打分。
在推荐系统中有一类问题是对未打分的商品进行评分的预测。
二、基于矩阵分解的推荐算法
2.1、矩阵分解的一般形式
矩阵分解是指将一个矩阵分解成两个或者多个矩阵的乘积。对于上述的用户-商品矩阵(评分矩阵)，记为<nobr style="box-sizing: border-box;">Rm×n</nobr>。可以将其分解成两个或者多个矩阵的乘积，假设分解成两个矩阵<nobr style="box-sizing: border-box;">Pm×k</nobr>和<nobr style="box-sizing: border-box;">Qk×n</nobr>，我们要使得矩阵<nobr style="box-sizing: border-box;">Pm×k</nobr>和<nobr style="box-sizing: border-box;">Qk×n</nobr>的乘积能够还原原始的矩阵<nobr style="box-sizing: border-box;">Rm×n</nobr>：
<nobr style="box-sizing: border-box;">Rm×n≈Pm×k×Qk×n=R^m×n</nobr>
其中，矩阵<nobr style="box-sizing: border-box;">Pm×k</nobr>表示的是<nobr style="box-sizing: border-box;">m</nobr>个用户与<nobr style="box-sizing: border-box;">k</nobr>个主题之间的关系，而矩阵<nobr style="box-sizing: border-box;">Qk×n</nobr>表示的是<nobr style="box-sizing: border-box;">k</nobr>个主题与<nobr style="box-sizing: border-box;">n</nobr>个商品之间的关系。
2.2、利用矩阵分解进行预测
在上述的矩阵分解的过程中，将原始的评分矩阵<nobr style="box-sizing: border-box;">Rm×n</nobr>分解成两个矩阵<nobr style="box-sizing: border-box;">Pm×k</nobr>和<nobr style="box-sizing: border-box;">Qk×n</nobr>的乘积：
<nobr style="box-sizing: border-box;">Rm×n≈Pm×k×Qk×n=R^m×n</nobr>
那么接下来的问题是如何求解矩阵<nobr style="box-sizing: border-box;">Pm×k</nobr>和<nobr style="box-sizing: border-box;">Qk×n</nobr>的每一个元素，可以将这个问题转化成机器学习中的回归问题进行求解。
2.2.1、损失函数
可以使用原始的评分矩阵<nobr style="box-sizing: border-box;">Rm×n</nobr>与重新构建的评分矩阵<nobr style="box-sizing: border-box;">R^m×n</nobr>之间的误差的平方作为损失函数，即：
<nobr style="box-sizing: border-box;">e2i,j=(ri,j−r^i,j)2=(ri,j−∑k=1Kpi,kqk,j)2</nobr>
最终，需要求解所有的非“-”项的损失之和的最小值：
<nobr style="box-sizing: border-box;">minloss=∑ri,j≠−e2i,j</nobr>
2.2.2、损失函数的求解
对于上述的平方损失函数，可以通过梯度下降法求解，梯度下降法的核心步骤是
- 求解损失函数的负梯度：
<nobr style="box-sizing: border-box;">∂∂pi,ke2i,j=−2(ri,j−∑k=1Kpi,kqk,j)qk,j=−2ei,jqk,j</nobr>
<nobr style="box-sizing: border-box;">∂∂qk,je2i,j=−2(ri,j−∑k=1Kpi,kqk,j)pi,k=−2ei,jpi,k</nobr>
- 根据负梯度的方向更新变量：
<nobr style="box-sizing: border-box;">pi,k′=pi,k−α∂∂pi,ke2i,j=pi,k+2αei,jqk,j</nobr>
<nobr style="box-sizing: border-box;">qk,j′=qk,j−α∂∂qk,je2i,j=qk,j+2αei,jpi,k</nobr>
通过迭代，直到算法最终收敛。
2.2.3、加入正则项的损失函数即求解方法
通常在求解的过程中，为了能够有较好的泛化能力，会在损失函数中加入正则项，以对参数进行约束，加入<nobr style="box-sizing: border-box;">L2</nobr>正则的损失函数为：
<nobr style="box-sizing: border-box;">E2i,j=(ri,j−∑k=1Kpi,kqk,j)2+β2∑k=1K(p2i,k+q2k,j)</nobr>
利用梯度下降法的求解过程为：
- 求解损失函数的负梯度：
<nobr style="box-sizing: border-box;">∂∂pi,kE2i,j=−2(ri,j−∑k=1Kpi,kqk,j)qk,j+βpi,k=−2ei,jqk,j+βpi,k</nobr>
<nobr style="box-sizing: border-box;">∂∂qk,jE2i,j=−2(ri,j−∑k=1Kpi,kqk,j)pi,k+βqk,j=−2ei,jpi,k+βqk,j</nobr>
- 根据负梯度的方向更新变量：
<nobr style="box-sizing: border-box;">pi,k′=pi,k−α(∂∂pi,ke2i,j+βpi,k)=pi,k+α(2ei,jqk,j−βpi,k)</nobr>
<nobr style="box-sizing: border-box;">qk,j′=qk,j−α(∂∂qk,je2i,j+βqk,j)=qk,j+α(2ei,jpi,k−βqk,j)</nobr>
通过迭代，直到算法最终收敛。
2.2.4、预测
利用上述的过程，我们可以得到矩阵<nobr style="box-sizing: border-box;">Pm×k</nobr>和<nobr style="box-sizing: border-box;">Qk×n</nobr>，这样便可以为用户<nobr style="box-sizing: border-box;">i</nobr>对商品<nobr style="box-sizing: border-box;">j</nobr>进行打分：
<nobr style="box-sizing: border-box;">∑k=1Kpi,kqk,j</nobr>
2.3、程序实现
对于上述的评分矩阵，通过矩阵分解的方法对其未打分项进行预测，最终的结果为：
程序代码如下：
#!/bin/python
'''
Date:20160411
@author: zhaozhiyong
'''
from numpy import *
def load_data(path):
f = open(path)
data = []
for line in f.readlines():
arr = []
lines = line.strip().split("\t")
for x in lines:
if x != "-":
arr.append(float(x))
else:
arr.append(float(0))
#print arr
data.append(arr)
#print data
return data
def gradAscent(data, K):
dataMat = mat(data)
print dataMat
m, n = shape(dataMat)
p = mat(random.random((m, K)))
q = mat(random.random((K, n)))
alpha = 0.0002
beta = 0.02
maxCycles = 10000
for step in xrange(maxCycles):
for i in xrange(m):
for j in xrange(n):
if dataMat[i,j] > 0:
#print dataMat[i,j]
error = dataMat[i,j]
for k in xrange(K):
error = error - p[i,k]*q[k,j]
for k in xrange(K):
p[i,k] = p[i,k] + alpha * (2 * error * q[k,j] - beta * p[i,k])
q[k,j] = q[k,j] + alpha * (2 * error * p[i,k] - beta * q[k,j])
loss = 0.0
for i in xrange(m):
for j in xrange(n):
if dataMat[i,j] > 0:
error = 0.0
for k in xrange(K):
error = error + p[i,k]*q[k,j]
loss = (dataMat[i,j] - error) * (dataMat[i,j] - error)
for k in xrange(K):
loss = loss + beta * (p[i,k] * p[i,k] + q[k,j] * q[k,j]) / 2
if loss < 0.001:
break
#print step
if step % 1000 == 0:
print loss
return p, q
if __name__ == "__main__":
dataMatrix = load_data("./data")
p, q = gradAscent(dataMatrix, 5)
'''
p = mat(ones((4,10)))
print p
q = mat(ones((10,5)))
'''
result = p * q
#print p
#print q
print result
其中，利用梯度下降法进行矩阵分解的过程中的收敛曲线如下所示：
'''
Date:20160411
@author: zhaozhiyong
'''
from pylab import *
from numpy import *
data = []
f = open("result")
for line in f.readlines():
lines = line.strip()
data.append(lines)
n = len(data)
x = range(n)
plot(x, data, color='r',linewidth=3)
plt.title('Convergence curve')
plt.xlabel('generation')
plt.ylabel('loss')
show()
