基于矩阵分解的单类协同过滤推荐算法(可编辑)
基于矩阵分解的单类协同过滤推荐算法
第 卷第 期. .
计 算 机 应 用 研 究 年 月
基于矩阵分解的单类协同过滤推荐算法
李 改 ,李 磊.顺德职业技术学院电子与信息工程系,广东顺德 ; .中山大学信息科学与技术学院,广州 ; .中山大学软件研究所,广州
摘 要:新闻网页和书签的推荐被认为是单类协调过滤问题。通常这类数据是相当稀疏的,仅仅一小部分数据
是正例,在非正例数据中负例和没有标记的正例是混合在一起的,难以区分开来,因此,就如何解释非正例数据
出现了歧义。为了解决该问题,提出了一种加权的带正则化的基于迭代最小二乘法的单类协同过滤算法。即通
过对正例赋予权值 ,负例赋予一个较小的正实数权值来反映数据的正负置信度。在两个真实的实验数据集上
验证了该算法在性能上均优于几个经典的单类协同过滤推荐算法。
关键词:推荐系统;单类协同过滤;矩阵分解;
中图分类号: 文献标志码文章编号: ? ? ?: . /. . ?. . . . , . . ’
. . & ,, , ; .
& , ? , , ; . , ? , , : . ? , . ? ,? . ?. ,’ . ? .: ; ; ;
的评价,形成系统对该指定用户对此信息的喜好程度预 引言
测 。近年来协同过滤的算法在国内外得到了广泛研究,按 处理数据的不同主要分为两类:一类是处理明确的偏好数据, 随着互联网的快速发展,互联网上的数据量急剧增长,从 如评分;另一类则是处理隐式数据,如对网页点击与否。这种 而使得如何快速而高效地从如此浩瀚的数据海洋中获取人们 隐式数据广泛存在于真实世界的应用环境中,如用户是否购买 所需要的信息变得越来越紧迫。在此背景下,推荐系统应运而 过某个商品,用户是否点击过某个网页等。由于这里的信息不 生。推荐系统通过收集和
用户的各种信息来学习用户的 需要用户提供明确的评分,因此相比评分数据更容易获取。该 兴趣和行为模式,根据分析得到的用户兴趣和行为模式,为用 类数据中仅有正例可以明确区分开来,负例不确定,故把该类 户推荐他所需要的服务。这些系统的例子包括卓越亚马逊 问题称为单类协同过滤问题。单类协同过滤的任务 . . 、当当网 . . 为用户推荐各
就是通过分析这些隐式信息来针对特定用户的偏好对推荐对 种其可能喜欢的商品,如书籍、音像、电器、服装等;电影 象集按该用户的喜欢程度排序。尽管这类数据获取很容易,但 出租系统 . . 为用户推荐各种其可能喜欢的电 解释起来却存在着很大的困难。以用户点击网页的数据为例,
影; 、 、 等为用户推荐个性化的新闻和搜索服
这些数据中用户点击过的网页构成的数据可以解释为正例,其
务。推荐系统中运用最广泛的是基于协同过滤的推荐
余数据是负例和漏掉的正例的混合。如何解释这类混合数据,
算法 。 。
以及如何来对解释后的数据进行有效处理,是当前单类协同过
协同过滤的算法核心是分析用户兴趣,在用户群中找到与
滤问题研究的难点所在。目前对该问题的研究还很少。指定用户的相似 兴趣 用户,综合这些相似用户对某一信息
等人 把低秩逼近 技术运用到单类协同过滤问题,把
收稿日期: ? ? ;修回日期:基金项目:国家自然科学基金资助项目,;中山大学高性能与网格
计算平台资助项目
作者简介:李改,男,讲师,博士研究生,主要研究方向为数据挖掘、推荐系统 .;李磊一 ,男,教授,博导,博士,
主要研究方向为数据库、数据挖掘、人工智能.第 期 李 改,等:基于矩阵分解的单类协同过滤推荐算法?
观察到的点击数据作为正例数据,其余的混合数据均作为负例
, ? ~ ,, 、
示用户和推荐对象的特征矩
数据; 提出运用奇异值分解技术来解决该类问
阵, 表示特征个数,一般 , 表示矩阵 的秩,?
题; 等人 提出运用基于的协同过滤算法来解决 , 。
该类问题。
为了找到一个低秩矩阵 来最大程度地逼近矩阵 ,最 本文的主要贡献是:在前人的研究基础上提出一种加权 小化加权的损失函数。
的迭代最小二乘法 来解决单类协同过滤问题,即对明 三 ?,一 确的正例数据赋予权重 ,对于无法解释的混合数据赋予一个 其中: 一 是低秩逼近中常见的平方误差项, 表示各 小于 大于 的正实数权重,进而在真实的数据集上实现本文 个数据点对最小化总的加权的 损失函数的贡献。在 所提出的算法,并将其与几个传统的 算法的性能做比 中,对于正例,设置 ;
对于缺失值,假定所有的缺失
较。实验结果表明, 算法在各个数据集下均优于几个传 值均为负例,其值均设置为 ,即 , 。因为对正例有很高的 统的 算法。 置信度,故对于这类数据的权值设置为 ,即 。与 不同的是,在本算法中不是简单地把所有的混合数据均当成负 相关工作
例,而是在把它们当成负例的同时给这些数据一个小的权值 ? , 。
协同过滤算法的研究数据按不同的系统设计可大致分为 考虑如何有效且快速地求解最优化问题 。
三种数据类型 :
式 可以改写为
评分 数据。在理想情形下,系统会提示用户输
,. , ?
入对不同对象的喜好/厌恶程度。它用分数表示,一般是 ~ 为了防止过拟合,给式 加上正贝 化项,则式 可改写为
星 分 , 星表示非常不喜欢, 星代表非常喜欢。,?,一 ; ; 正负面 /
的评价数据。用
户不给出喜恶程度,只表达是否喜欢。
固定 ,对求导 争 :,得到求解的公式:基于正面反馈 的数据。在一些情况
?,, ? ~
下,不能收集类似前两类的显式评分数据,但是可以收集一些 用户的行为 用户阅读了哪些新闻或购买了哪些产品 ,一般 其中: 表示用户 评过的推荐对象的评分组成的向量,
假设这些行为数据反映了用户的兴趣,因而把这类数据称为基表示一个由
中的元素构成的对角矩阵。
于“正”反馈的数据。
同理,固定 ,可以得到求解 的公式。
当前对于协同过滤算法的研究大多数均集中在对评分数,
, ? , , ? ~
,
据的研究 ,该类数据既有正例数据 高评分点 ,又有负例数 据 低评分点 。对该类问题的研究, 等人提出了
其中:尺表示评过推荐对象 的用户的评分组成的向量, , ? , 等人提出
~ 表示一个由 ,中的元素构成的对角矩阵。
了 和?
在式 中,表示一个 × 的单位矩阵。 , 等人提出了基于式 ,本文提出下面
的加权的基于代正则化的。对于正负面的评价数据,以协同过滤的角度来 交叉最小二乘法 的单类协同过滤推荐算法。首先用均 研究的很少,大多当做两类分类问题来看待 ’ 。
值 为 、偏差为 . 的高斯随机数初始化矩阵 ,然后用式 在现实世界的实际应用中,基于正面反馈 ?更新 ,接着用式 更新 ,直到本
算法计算出的值的数据也广泛存在,当前对该类问题的研究主要也是把 收敛或
迭代次数足够多而结束迭代为止。具体算法描述如下:
算法 基于 的单类协同过滤推荐算法
其看做两类的分类问题,如文献 把该问题当做只有正类的 输入:用户的评分矩阵开,特征个数 。
两类分类问题来看待,提出运用 分类器来解决单类分类 输出:矩阵 的逼近矩阵
问题;文献, 通过 算法来迭代预测负例,从而学习出
用一个小于 的随机数初始化
单类分类器来解决此类单类分类问题。近年来也有些研究者 反复迭代运用式更新 、 ,直到本算法计算出
从协同过滤的角度来解决该类问题。
的值收敛或迭代次数足够多而结束迭代;
基于 的单类协同过滤算法 ,返回矩阵
运用计算得到的 产生 推荐。
. 基于的单类协同过滤算法简介
. 基于的单类协同过滤算法的时间复杂度分析 给定一个矩阵, 一,表示它的一个
为了分析本算法的时间复杂度,假定 表示特征个数, 元素一 表示矩阵开的第 行一,表示矩阵只的第 列, 表 表示算法的迭代次数, 表示用户的个数, 表示推荐对象的 示用户数, 表示推荐对象数 和一个权重矩阵? 个数。以标准的矩阵操作来计算该算法的时间复杂度,分析式 ? 一 表示大于 小于 的正实数 。在这里,希 可知每次更新 ,的一行所需要的时间复杂度的上界为 望找到一个低秩矩阵来逼近矩阵尺。其中: ,分析式 可知每次更新 的一行
所需要的时间复杂? 计 算 机 应 用 研 究 第 卷 个性化排序。这里采用的评估标准是平均 : 度的上界为 ,因此更新 、 所需要的时间复杂度的上 界为 。假定本算法总共迭代 次后停止,则本算法? ; 十 ; 总的运行时间复杂度的上界为/ 。
在这里 是一个指标函数。
综上,可得到有关本算法运行时间复杂度的定理 。 定理 对于 ,每次更新 、 所需要的时间复杂度 的上界为 ,如果算法总共迭代 次后停止,则其总 每个用户的评估对象对为
的运行时间复杂度的上界为 。“ :: ?,/ ,分析算法 可知,该算法的关键是第二步,即反复迭代运 值越高表示该算法的性能越好。由随机模型产生的
用式 更新 、 分析式 可知,每次调用式 值为 . ,最好模型的值为 。对每个实验均反复运只是计算更新矩阵 、 的一行值。因此可对矩阵 、 进
行 次,每次均对每个用户随机选取一个评分点,构成新的训
行分割,分成多个等列长的子矩阵来进行并行运算。故本文所
练集和测试集,最终结果取 次运算结果的平均值。
提出的 协同过滤算法完全可以并行化运算,从而可以解
. 实验结果
决其他单类协同过滤算法难以并行化、可扩展性差的问题,进 算法的参数主要是负例权值参数/和正则化参数
而简化本算法的实现复杂度,提高其运算效率。
。本实验中, 算法的这两个参数在和子数据集上的最优值将通过交叉确认的方式来确定。
实验结果及分析
本实验将分别在 子数据集和完整的 数
本章首先介绍本文实验所采用的数据集及评价标准;接着
据集上把本文所提出的 算法与传统的 、 、基于
以为评价指标,比较了本文所提出的 算法和传统
用户的和基于项目的算法的性能进行比较分析。
的、 、基于用户的和基于项目的算法的性
图 表示在数据集上,本文所提出的 算
能 ,并对结果进行分析。
法与传统的、 、基于用户的和基于项目的
算法的性能对比。图 中横轴表示 、传统的和 . 实验数据集 算法中用户/推荐对象的特征矩阵中特征的个数,特征个数从 在本实验中使用了两个数据集,一个是数据集,一 变化到 ,纵轴表示各个算法的值。通过实验验证, 个是数据集 。 算法在 数据集上取得最优值的负例权值参数 数据集是 对
外发布的一个电影评分数据 . ,正则化参数. 。对于基于用户的和 集 ’” 。这个数据集包括了 、 个用户在对 、 部 基于项目的算法,该实验中的结果取最优值。由于这两 电影的 、 、 个评分。所有的评分值都是 ~ 中的整 种算法的性能与特征矩阵中特征的个数无关,故在各个特征数 数值,其中分数越高表示客户对相应电影的评价越高 越喜 下取值均一致。从图 中可以看出,在各个特征数下,本文所 欢 。这个数据集非常稀疏,有将近 % 的评分值未知。从 提出的 算法几乎均优于传统的 和算法,也优
这个数据集中随机抽取一个包括 个用户、 部电影 于最优的基于用户的和基于项目的算法,并且这种 的子集,总共包含个评分点。该评分子集要求每个用 优势随着特征数的增加越发明显。其中算法的值 户至少评过 部电影,每部电影至少被 个用户评过。这个 随着特征数的增大先增大,而后急速下降。这是由于算
选取的子数据集也非常稀疏,稀疏度为 . %,即仅 . % 法在解决单类协同过滤问题时也出现了过拟合现象。 的项有评分。 数据集是由美国大学的研
究小组创建并维护的 ,其中包括 个用户对 部电 影的条评分记录。所有的评分值也都是 ? 中的整 数值,其中分数越高表示客户对相应电影的评价越高 越喜 欢 。这个数据集也非常稀疏,稀疏度为 . %,即仅 特征数 特征数
图 法与其他经典算法的 图算法与其他经典
. %的项有评分。
比较 /. 数据集 算法的比较子数据集
实验中把选取的子数据集和数据集中
图 表示在子数据集上,本文所提出的算法
评分数值为 ~ 分的数据点均赋值为 ,用于表示正例数据, 与传统的、 、基于用户的和基于项目的算
其余数据点仍为缺失数据,从而把基于评分的数据转变为基于 法的性能对比。坐标轴的定义与图 一致。通过实验验证, 正面反馈的数据。 算法在子数据集上取得最优值的负例权值参数 . 实验的评价方法. ,正则化参数. 。从图 中不难看出,当特征 本文实验采用留一策略作为评价机制,也即从每个用户的 个数大于 后,本文所提出的 算法明显优于传统的 评分历史中随机地选取并移除一个评分点作为测试集 ,余 、 、基于用户
的和基于项目的算法,且随着
下的数据构成训练集 ,这两个集合不相交。在 上训练
特征个数的增大,这种优势愈加明显。在这里基于用户的
出相应的模型,接着在测试集上评估模型预测出的推荐对象的 和基于项目的算法也均取最优值。图 显示在 .