NFM

2018年1月3日 0 条评论 97 次阅读 0 人点赞

非负矩阵分解,由于不让使用封装好的包,所以项目功能比较简单,最重要的是我辛辛苦苦把他改成论文了。

代码依然托管在github

摘要

NMF,非负矩阵分解,就是将大矩阵分解成两个小矩阵,使得这两个小矩阵相乘后能够还原到大矩阵。而非负表示分解的矩阵都不包含负值。从应用的角度来说,矩阵分解能够用于发现两种实体间的潜在特征,一个最常见的应用就是协同过滤中的预测打分值。

为用户推荐电影是一个非常现实并且有意义的实例。数据集包含有用户和电影两个集合。给出每个用户对部分电影的打分,我们希望预测该用户对其他没看过电影的打分值,这样可以根据打分值为其做出推荐。用户和电影的关系,可以用一个矩阵来表示,每一行表示用户,每一列表示电影,每个元素的值表示用户对已经看过的电影的打分。

本文通过对MovieLens推荐系统中的一个数据集进行非负矩阵分解,发现一些用户打分的潜在特征。对非负矩阵分解算法进行了设计。使用python对其进行编程与实现。对分解矩阵的实际意义作出了说明。通过还原矩阵与原矩阵的对比验证算法的有效性。并对未打分的空缺值进行了预测。

算法部分

NMF,非负矩阵分解,它的目标很明确,就是将大矩阵分解成两个小矩阵,使得这两个小矩阵相乘后能够还原到大矩阵。而非负表示分解的矩阵都不包含负值。

首先,我们定义U集合,D集合,R = U * D集合。我们的目标是,找到两个矩阵P和Q,使得它们相乘近似等于R。即:

现在我们就来计算P和Q。最简单的方法就是梯度下降,该方法先初始化P和Q为特定的值,计算它们的乘积与真实矩阵的误差,然后通过迭代,逐渐减小误差直至收敛。

由于误差可大可小,这里使用平方根误差(squared error)来计算,计算公式如下:

即循环地计算每一条目的误差,最后相加。

为了最小化误差,我们需要知道怎么改变Pij和Qkj的值(在梯度下降中表现为下降的方向)。我们对这个公式求偏微分,即得:

 

计算出梯度之后,我们逐步更新Pik和Qkj:

上面公式中,为梯度下降常数,通常取一个较小的值(防止无法收敛),如0.0002。

我们输入的数据是所有已评分的数据(或它的子集),即训练集,而并不包含未评分的数据。因此,它能够对未评分的做出不等于0的预测。

通过上面的更新规则,我们就可以逐步减小误差,直至收敛:

 

 

规范化

上面的算法只是最简单的一个实现,实际使用中可能复杂得多。一个最常见的修改就是引入规范化,以防止过度拟合。这通过加入另外一个参数来修改误差公式:

 

参数用来控制用户特征向量与条目特征向量的比例,以避免出现特征向量中出现特别大的值。实际应用中,通常设置为0~0.02之间的值。因此更新公式变成:

 

程序部分

使用python定义matrix_factorisation类实现非负矩阵分解,代码如图一

图一

应用部分

从应用的角度来说,矩阵分解能够用于发现两种实体间的潜在特征,一个最常见的应用就是协同过滤中的预测打分值,而从协同过滤的这个角度来说,非负也很容易理解:打分都是正的,不会出现负值。

在例如MovieLens这样的推荐系统中,有用户和电影两个集合。给出每个用户对部分电影的打分,我们希望预测该用户对其他没看 过电影的打分值,这样可以根据打分值为其做出推荐。用户和电影的关系,可以用一个矩阵来表示,每一行表示用户,每一列表示电影,每个元素的值表示用户对已 经看过的电影的打分,矩阵看起来如表一:

 
  D1 D2 D3 D4
U1 5 3 - 1
U2 4 - - 1
U3 1 1 - 5
U4 1 - - 4
U5 - 1 5 4

表一

而使用矩阵分解来预测评分的思想来源于,我们可以通过矩阵分解来发现一些用户打分的潜在特征。比如两个人都喜欢某一演员,那他们就倾向于给TA演的电影打高分;或者两个人都喜欢动作片。假如我们能够发现这些特征,我们就能够预测特定用户对特定电影的打分。

为了发现不同的特征,我们假设特征的数量少于用户和电影的数量。

假设我们需要寻找K个特征,则我们的目标是,找到两个矩阵P和Q,使得它们相乘近似等于R。

这样P的每一行表示用户,每一列表示一个特征,它们的值表示用户与某一特征的相关性,值越大,表明特征越明显。同理,Q的每一行表示电影,每一列表示电影与特征的关联。最后为了预测用户ui对特定电影dj的评分,我们可以直接计算ui和dj对应的特征向量的点积,即:

 

实现代码如下图二:

 

图二

结果的解释

通过非负矩阵分解,找到两个矩阵P和Q,使得它们相乘近似等于R。这样P的每一行表示用户,每一列表示一个特征,它们的值表示用户与某一特征的相关性,值越大,表明特征越明显。矩阵如图三。

图三

同理,Q的每一行表示电影,每一列表示电影与特征的关联。它们的值表示电影与某一特征的相关性,值越大,表明特征越明显。矩阵如图四。

图四

还原矩阵如表二

 
  D1 D2 D3 D4
U1 5.02 2.85 5.26 0.99
U2 3.94 2.24 4.28 0.99
U3 1.10 0.71 4.40 4.96
U4 0.94 0.61 3.58 3.97
U5 2.31 1.38 4.87 4.03

表二

还原矩阵及预测值如图五所示。

图五

可以看到,还原后的矩阵跟原矩阵很接近,如图六所示。

图六

可以看到,还原后的矩阵跟原矩阵很接近,并且对原来空缺的值作出了预测。在这个例子中,我们可以看到U1和U2口味比较接近,他们与特征值1的相关性强,而U3,U4,U5则与特征值2的相关性较强。

通过实例测试,此nmf算法有效。能在较小的误差范围内获得还原矩阵。并对原来的空缺值进行预测。但在算法逻辑与效率上还存在很大的提升空间。

由于数据较少,只去两个特征值进行模拟与测试。算法在分解效率上的问题难以发现。由于数据集缺少标签,特征值显示意义难以定义。空缺值无相应数据,对空缺值预测精确程度难以分析。希望在今后的学习中通过更多的数据集完善代码。

 

lyssom

这个人太懒什么东西都没留下

文章评论(0)