浅入浅出:PageRank算法 使用 TextRank 算法为文本生成关键字和摘要 基于物品的协同过滤 如何使用MapReduce实现基于物品的协同过滤(1) 如何使用MapReduce实现基于物品的协同过滤(2) 浅入浅出:K近邻算法 使用mahout下的朴素贝叶斯分类器对新闻分类 使用Affinity Propagation进行聚类 K-medoids聚类 矩阵分解在推荐系统中的应用:NMF和经典SVD实战 使用特征递归消除筛选特征 如何分配权重 比较NMF、PCA和VQ 方差和协方差 基于SVD的协同过滤 逻辑斯谛回归代码实现 隐语义模型和NMF(非负矩阵分解) 使用PCA处理MNIST数据集 使用GBDT选取特征 基于贝叶斯的文本分类系统的数据库设计 在hadoop1.2.1上安装mahout 0.9 Hadoop 2.4 实现Kmeans聚类算法 在Iris数据集上对比PCA、LDA、NMF 基于贝叶斯的文本分类实战 单层决策树 Logistic regression(逻辑斯蒂回归) 基于用户的协同过滤 词袋模型与文档-词矩阵 如何实现拼音与汉字的互相转换 梯度下降法 如何判定相似度 MovieLens数据集介绍 基于KNN的文本分类实战 Jasper文本分类系列博客阅读摘录 使用 Mean Shift进行聚类 朴素贝叶斯的三个常用模型:高斯、多项式、伯努利 使用决策树处理iris数据集 浅入浅出:从Kmeans到Kmeans++ 如何持久化scikit-learn中训练好的模型 浅入浅出:DBSCAN聚类算法(1) 浅入浅出:DBSCAN聚类算法(2) 2015阿里移动推荐算法比赛第一赛季总结 爬山算法 使用朴素贝叶斯分类器划分邮件 层次聚类 基于MapReduce的频繁项集挖掘 搜狗实体关系提取比赛

矩阵分解在推荐系统中的应用:NMF和经典SVD实战


#机器学习


2015-05-25

本文以NMF和经典SVD为例,讲一讲矩阵分解在推荐系统中的应用。

数据

item\user Ben Tom John Freq
item 1 5 5 0 5
item 2 5 0 3 4
item 3 3 4 0 3
item 4 0 0 5 3
item 5 5 4 4 5
item 6 5 4 5 5
user\item item 1 item 2 item 3 item 4 item 5 item 6
Ben 5 5 3 0 5 5
Tom 5 0 4 0 4 4
John 0 3 0 5 4 5
Fred 5 4 3 3 5 5

NMF

关于NMF,在 隐语义模型和NMF(非负矩阵分解) 已经有过介绍。

用户和物品的主题分布

# !/usr/bin/python2.7
# coding: UTF-8
import numpy as np
from sklearn.decomposition import NMF
import matplotlib.pyplot as plt

RATE_MATRIX = np.array(
    [[5, 5, 3, 0, 5, 5],
     [5, 0, 4, 0, 4, 4],
     [0, 3, 0, 5, 4, 5],
     [5, 4, 3, 3, 5, 5]]
)

nmf = NMF(n_components=2)  # 设有2个隐主题
user_distribution = nmf.fit_transform(RATE_MATRIX)
item_distribution = nmf.components_

print '用户的主题分布:'
print user_distribution
print '物品的主题分布:'
print item_distribution

运行后输出:

用户的主题分布:
[[ 2.20884275  0.84137492]
 [ 2.08253282 -0.        ]
 [-0.          3.18154406]
 [ 1.84992603  1.60839505]]
物品的主题分布:
[[ 2.4129931   1.02524235  1.62258152  0.          1.80111078  1.69591943]
 [ 0.0435741   1.13506094  0.          1.54526337  1.21253494  1.48756118]]

可视化物品的主题分布:

# !/usr/bin/python2.7
# coding: UTF-8
import numpy as np
from sklearn.decomposition import NMF
import matplotlib.pyplot as plt

RATE_MATRIX = np.array(
    [[5, 5, 3, 0, 5, 5],
     [5, 0, 4, 0, 4, 4],
     [0, 3, 0, 5, 4, 5],
     [5, 4, 3, 3, 5, 5]]
)

nmf = NMF(n_components=2)
user_distribution = nmf.fit_transform(RATE_MATRIX)
item_distribution = nmf.components_

item_distribution = item_distribution.T
plt.plot(item_distribution[:, 0], item_distribution[:, 1], "b*")
plt.xlim((-1, 3))
plt.ylim((-1, 3))

plt.title(u'the distribution of items (NMF)')
count = 1
for item in item_distribution:
    plt.text(item[0], item[1], 'item '+str(count), bbox=dict(facecolor='red', alpha=0.2),)
    count += 1

plt.show()

结果:

从距离的角度来看,item 5和item 6比较类似;从余弦相似度角度看,item 2、5、6 比较相似,item 1、3比较相似。

可视化用户的主题分布:

# !/usr/bin/python2.7
# coding: UTF-8
import numpy as np
from sklearn.decomposition import NMF
import matplotlib.pyplot as plt

RATE_MATRIX = np.array(
    [[5, 5, 3, 0, 5, 5],
     [5, 0, 4, 0, 4, 4],
     [0, 3, 0, 5, 4, 5],
     [5, 4, 3, 3, 5, 5]]
)

nmf = NMF(n_components=2)
user_distribution = nmf.fit_transform(RATE_MATRIX)
item_distribution = nmf.components_

users = ['Ben', 'Tom', 'John', 'Fred']
zip_data = zip(users, user_distribution)

plt.title(u'the distribution of users (NMF)')
plt.xlim((-1, 3))
plt.ylim((-1, 4))
for item in zip_data:
    user_name = item[0]
    data = item[1]
    plt.plot(data[0], data[1], "b*")
    plt.text(data[0], data[1], user_name, bbox=dict(facecolor='red', alpha=0.2),)

plt.show()

结果:

从距离的角度来看,Fred、Ben、Tom的口味差不多;从余弦相似度角度看,Fred、Ben、Tom的口味还是差不多。

如何推荐

现在对于用户A,如何向其推荐物品呢?

方法1: 找出与用户A最相似的用户B,将B评分过的、评分较高、A没评分过的的若干物品推荐给A。

方法2: 找出用户A评分较高的若干物品,找出与这些物品相似的、且A没评分的若干物品推荐给A。

方法3: 找出用户A最感兴趣的k个主题,找出最符合这k个主题的、且A没评分的若干物品推荐给A。

方法4: 由NMF得到的两个矩阵,重建评分矩阵。例如:

# !/usr/bin/python2.7
# coding: UTF-8
import numpy as np
from sklearn.decomposition import NMF
import matplotlib.pyplot as plt

RATE_MATRIX = np.array(
    [[5, 5, 3, 0, 5, 5],
     [5, 0, 4, 0, 4, 4],
     [0, 3, 0, 5, 4, 5],
     [5, 4, 3, 3, 5, 5]]
)

RATE_MATRIX[1, 2] = 0  # 对评分矩阵略做修改
print '新评分矩阵:'
print RATE_MATRIX

nmf = NMF(n_components=2)
user_distribution = nmf.fit_transform(RATE_MATRIX)
item_distribution = nmf.components_

reconstruct_matrix = np.dot(user_distribution, item_distribution)
filter_matrix = RATE_MATRIX < 1e-6  # 小于0
print '重建矩阵,并过滤掉已经评分的物品:'
print reconstruct_matrix*filter_matrix

运行结果:

新评分矩阵:
[[5 5 3 0 5 5]
 [5 0 0 0 4 4]
 [0 3 0 5 4 5]
 [5 4 3 3 5 5]]
重建矩阵,并过滤掉已经评分的物品:
[[ 0.          0.          0.          0.80443133  0.          0.        ]
 [ 0.          2.19148602  1.73560797  0.          0.          0.        ]
 [ 0.02543568  0.          0.48692891  0.          0.          0.        ]
 [ 0.          0.          0.          0.          0.          0.        ]]

对于Tom(评分矩阵的第2行),其未评分过的物品是item 2、item 3、item 4。item 2的推荐值是2.19148602,item 3的推荐值是1.73560797,item 4的推荐值是0,若要推荐一个物品,推荐item 2。

如何处理有评分记录的新用户

NMF是将非负矩阵V分解为两个非负矩阵W和H:

V = W×H

在本文上面的实现中,V对应评分矩阵,W是用户的主题分布,H是物品的主题分布。

对于有评分记录的新用户,如何得到其主题分布?

方法1: 有评分记录的新用户的评分数据放入评分矩阵中,使用NMF处理新的评分矩阵。

方法2: 物品的主题分布矩阵H保持不变,将V更换为新用户的评分组成的行向量,求W即可。

下面尝试一下方法2。

设新用户Bob的评分记录为:

[5,5,0,0,0,5] 
# !/usr/bin/python2.7
# coding: UTF-8
import numpy as np
from sklearn.decomposition import NMF
import matplotlib.pyplot as plt

RATE_MATRIX = np.array(
    [[5, 5, 3, 0, 5, 5],
     [5, 0, 4, 0, 4, 4],
     [0, 3, 0, 5, 4, 5],
     [5, 4, 3, 3, 5, 5]]
)

nmf = NMF(n_components=2)
user_distribution = nmf.fit_transform(RATE_MATRIX)
item_distribution = nmf.components_

bob = [5, 5, 0, 0, 0, 5]
print 'Bob的主题分布:'
print nmf.transform(bob)

运行结果是:

Bob的主题分布:
[[ 1.37800534  0.69236738]]

经典SVD

关于SVD的一篇好文章:强大的矩阵奇异值分解(SVD)及其应用

相关分析与上面类似,这里就直接上代码了。

# !/usr/bin/python2.7
# coding: UTF-8
import numpy as np
from scipy.sparse.linalg import svds
from scipy import sparse
import matplotlib.pyplot as plt

def vector_to_diagonal(vector):
    """
    将向量放在对角矩阵的对角线上
    :param vector:
    :return:
    """
    if (isinstance(vector, np.ndarray) and vector.ndim == 1) or \
            isinstance(vector, list):
        length = len(vector)
        diag_matrix = np.zeros((length, length))
        np.fill_diagonal(diag_matrix, vector)
        return diag_matrix
    return None

RATE_MATRIX = np.array(
    [[5, 5, 3, 0, 5, 5],
     [5, 0, 4, 0, 4, 4],
     [0, 3, 0, 5, 4, 5],
     [5, 4, 3, 3, 5, 5]]
)

RATE_MATRIX = RATE_MATRIX.astype('float')
U, S, VT = svds(sparse.csr_matrix(RATE_MATRIX),  k=2, maxiter=200) # 2个隐主题
S = vector_to_diagonal(S)

print '用户的主题分布:'
print U
print '奇异值:'
print S
print '物品的主题分布:'
print VT
print '重建评分矩阵,并过滤掉已经评分的物品:'
print np.dot(np.dot(U, S), VT) * (RATE_MATRIX < 1e-6)

运行结果:

用户的主题分布:
[[-0.22279713  0.57098887]
 [-0.51723555  0.4274751 ]
 [ 0.82462029  0.38459931]
 [ 0.05319973  0.58593526]]
奇异值:
[[  6.39167145   0.        ]
 [  0.          17.71392084]]
物品的主题分布:
[[-0.53728743  0.24605053 -0.40329582  0.67004393  0.05969518  0.18870999]
 [ 0.44721867  0.35861531  0.29246336  0.20779151  0.50993331  0.53164501]]
重建评分矩阵,并过滤掉已经评分的物品:
[[ 0.          0.          0.          1.14752376  0.          0.        ]
 [ 0.          1.90208543  0.         -0.64171368  0.          0.        ]
 [ 0.21491237  0.         -0.13316888  0.          0.          0.        ]
 [ 0.          0.          0.          0.          0.          0.        ]]

可视化一下:

经典SVD + 协同过滤

0代表没有评分,但是上面的方法(如何推荐这一节的方法4)又确实把0看作了评分,所以最终得到的只是一个推荐值(而且总体都偏小),而无法当作预测的评分。在How do I use the SVD in collaborative filtering?有这方面的讨论。

SVD简要介绍

SVD的目标是将m*n大小的矩阵A分解为三个矩阵的乘积:

[latex] A = U * S * V^{T} [/latex]

U和V都是正交矩阵,大小分别是m*mn*n。S是一个对角矩阵,大小是m*n,对角线存放着奇异值,从左上到右下依次减小,设奇异值的数量是r

kk<<r

取得[latex]U[/latex]的前k列得到[latex]U_{k}[/latex],[latex]S[/latex]的前k个奇异值对应的方形矩阵得到[latex]S_{k}[/latex],[latex]V^{T}[/latex]的前k行得到[latex]V^{T}_{k}[/latex],于是有

[latex] A_{k} = U_{k} * S_{k} * V^{T}_{k} [/latex]

[latex]A_{k}[/latex]可以认为是[latex]A[/latex]的近似。

下面的算法将协同过滤和SVD结合了起来。

Item-based Filtering Enhanced by SVD

这个算法来自下面这篇论文:

Vozalis M G, Margaritis K G. Applying SVD on Generalized Item-based Filtering[J]. IJCSA, 2006, 3(3): 27-51.

1、 设评分矩阵为R,大小为m*n,m个用户,n个物品。R中元素[latex]r_{ij}[/latex]代表着用户[latex]u_{i}[/latex]对物品[latex]i_{j}[/latex]的评分。

2、 预处理R,消除掉其中未评分数据(即值为0)的评分。

  • 计算R中每一行的平均值(平均值的计算中不包括值为0的评分),令[latex]R_{filled-in}=R[/latex],然后将[latex]R_{filled-in}[/latex]中的0设置为该行的平均值。
  • 计算R中每一列的平均值(平均值的计算中不包括值为0的评分)[latex]r_{i}[/latex],[latex]R_{filled-in}[/latex]中的所有元素减去对应的[latex]r_{i}[/latex],得到正规化的矩阵[latex]R_{norm}[/latex]。(norm,即normalized)。

3、 对[latex]R_{norm}[/latex]进行奇异值分解,得到: [latex] R_{norm} = U * S * V^{T} [/latex]

4、 设正整数k,取得[latex]U[/latex]的前k列得到[latex]U_{k}[/latex],[latex]S[/latex]的前k个奇异值对应的方形矩阵得到[latex]S_{k}[/latex],[latex]V^{T}[/latex]的前k行得到[latex]V^{T}_{k}[/latex],于是有

[latex] R_{red} = U_{k} * S_{k} * V^{T}_{k} [/latex]

red,即dimensionality reduction中的reduction。可以认为k是指最重要的k个主题。定义[latex]R_{red}[/latex]中元素[latex]rr_{ij}[/latex]用户i对物品j在矩阵[latex]R_{red}[/latex]中的值。

5、 [latex] U_{k} * S_{k}^{\frac{1}{2}}[/latex],是用户相关的降维后的数据,其中的每行代表着对应用户在新特征空间下位置。[latex] S_{k}^{\frac{1}{2}}*V^{T}_{k}[/latex],是物品相关的降维后的数据,其中的每列代表着对应物品在新特征空间下的位置。

[latex] S_{k}^{\frac{1}{2}}*V^{T}_{k}[/latex]中的元素[latex]mr_{ij}[/latex]代表物品j在新空间下维度i中的值,也可以认为是物品j属于主题i的程度。(共有k个主题)。

6、 获取物品之间相似度。

  • 根据[latex] S_{k}^{\frac{1}{2}}*V^{T}_{k}[/latex]计算物品之间的相似度,例如使用余弦相似度计算物品j和f的相似度:
  • 相似度计算出来后就可以得到每个物品最相似的若干物品了。

7、 使用下面的公式预测用户a对物品j的评分:

这个公式里有些变量的使用和上面的冲突了(例如k)。 [latex]l[/latex]是指取物品j最相似的[latex]l[/latex]个物品。 [latex]mr_{ij}[/latex]代表物品j在新空间下维度i中的值,也可以认为是物品j属于主题i的程度。 [latex]sim_{jk}[/latex]是物品j和物品k的相似度。 [latex]R_{red}[/latex]中元素[latex]rr_{ak}[/latex]是用户a对物品k在矩阵[latex]R_{red}[/latex]中对应的评分。[latex]\bar{r_{a}}[/latex]是指用户a在评分矩阵[latex]R[/latex]中评分的平均值(平均值的计算中不包括值为0的评分)。

参考

SVD Recommendation System in Ruby 这篇文章使用的数据来自该链接,里面处理新用户的方法表示没看懂。

How do I use the SVD in collaborative filtering?

Vozalis M G, Margaritis K G. Applying SVD on Generalized Item-based Filtering[J]. IJCSA, 2006, 3(3): 27-51.



( 本文完 )