Hans Journal of Data Mining 数据挖掘, 2013, 3, 12-17 http://dx.doi.org/10.12677/hjdm.2013.31003 Published Online January 2013 (http://www.hanspub.org/journal/hjdm.html) One Class Collaborative Filtering Algorithm Based on Transfer Learning Shengmei Luo1, Yu nzhe n Lin2, Xi aow ei Ye1, Hailong Wen2 1ZTE Corporation, Nanjing 2School of Software, Tsinghua University, Beijing Email: luo.shengmei@zte.com.cn, ynlnlyz@126.com, ye.xiaowei@zte.com.cn, youxiabsyw@gmail.com Received: Nov. 22nd, 2012; revised: Dec. 20th, 2012; accepted: Dec. 28th, 2012 Abstract: Collaborative filtering is a useful algorithm for problems of personalized recommendation. For these prob- lems, there are many mature collaborative filtering algorithms. One class collaborative filtering is a new field of per- sonalized recommendation. Because of its data characteristics, common collaborative filtering algorithms have a lot of defects in the field of one class collaborative filtering. We studied the algorithm based on weighted matrix decomposi- tion, and optimized this algorithm by transfer learning. We prove the improvement of this optimization by experiments. Keywords: Recommendation; Collaborativ e Filtering; One Class; Transfer Learning 基于迁移学习的单类协同过滤算法 罗圣美 1,林运祯 2,叶小伟 1,文海龙 2 1中兴通讯,南京 2清华大学软件学院,北京 Email: luo.shengmei@zte.com.cn, ynlnlyz@126.com, ye.xiaowei@zte.com.cn, youxiabsyw@gmail.com 收稿日期:2012 年11 月22 日;修回日期:2012 年12 月20 日;录用日期:2012 年12 月28 日 摘 要:协同过滤算法是现在个性化推荐领域流行的算法。对常见的推荐问题,协同过滤算法已有成熟的实现。 单类协同过滤问题是推荐领域的一个新问题,其数据特征导致其不适用于常见的协同过滤算法。本文研究了基 于加权矩阵分解的单类协同过滤算法,并对其进行基于迁移学习的改进。通过在真实数据集上的验证,证明其 效果优于传统的单类协同过滤算法。 关键词:推荐系统;协同过滤;单类;迁移学习 1. 引言 随着互联网的发展,很多有一定规模的公司都积 累了大量的用户数据,如何利用这些数据找出用户的 使用倾向成为商家的迫切需求;同时,作为普通用户, 如何从互联网的海量数据当中找出自己最需要的内 容,也是用户的急切需要。这些事实成为推动推荐技 术发展的主要助力。 而无论对于企业还是用户而言,对每个用户产生 针对其使用特点的个性化推荐都是远远优于给所有 用户同样的推荐内容的。因此,个性化推荐成为推荐 技术的主要发展方向。对于个性化推荐,各种成熟的 协同过滤算法是其主要实现方式。 在个性化推荐问题当中,有一类特殊协同过滤问 题。其数据集的用户和项之间缺乏或者完全没有打分 数据,而只有二值化的点击数据(如对于新闻网站,用 户只有点击与否的二值数据;对视频网站,用户只有 观看与否的二值数据;都缺乏数值化的打分数据)。这 种情况,被称作“单类协同过滤”。单类协同过滤问 Copyright © 2013 Hanspub 12 基于迁移学习的单类协同过滤算法 题近年来得到了广泛的研究。 本文针对单类协同过滤问题,提出了一种基于迁 移学习的单类协同过滤算法。并在实际数据集上对其 进行了验证。实验结果表明,该算法的效果优于传统 的协同过滤算法,以及基于权值矩阵分解的单类协同 过滤算法。 2. 背景算法 2.1. 单类协同过滤的基础算法 单类协同过滤问题,有几种直观的解决方式,一 种是在数据集中标注负评分值的样本,或是引入其他 数据来源的评分,从而将其转化为传统的协同过滤问 题。但这种方法通常是需要人工实现的。并且由于难 以找到合理的新数据来源,实现的难度很大。 另一种方法是把所有的丢失数据(即用户没有正 面操作(如点击、观看)的样本)当作负样本(AMAN, All Mssing Are Negative),然后通过协同过滤算法进行计 算。这种方法较容易被实现。 在AMAN 的前提下,大多数传统的协同过滤算 法能够直接应用:在 AMAN 基础上可实现基于矩阵 分解的协同过滤算法,如奇异值分解(SVD)等,还可 实现基于用户相似度和项相似度的协同过滤方法。例 如,AMAN的基于 SVD 分解的执行过程是: 1) 从用户的浏览数据提取评分矩阵 R。在矩阵 R 中,用户有浏览记录的项的评分设为 1,其余设为 0。 2) 对矩阵 R进行 SVD 分解,得到分解结果 R = USV。 3) 对目标用户 u,将矩阵 U的第 u行与 V中不 在u的浏览列表中的项目的第 i行进行相乘,即得到 用户 u对项 i的评分结果。对评分结果进行排序,取 前K个推荐结果,得到 TopK推荐。 还有一种方法是,把丢失数据当成未知(AMAU, All Mssing Are Unknown),亦即忽略所有的丢失数据 并把正样本通过分类或预测算法进行预测,将单类协 同过滤分问题转化为分类或预测问题。以贝叶斯分类 为例,算法过程为: 1) 记录用户对项的浏览记录,储存成用户–项的 浏览向量。 2) 预测用户 u对项 i是否应推荐时,构建分类数 为两类(推荐或不推荐)的贝叶斯分类器,训练数据为 除用户 u外的用户的浏览向量,以及这些用户是否浏 览了 i。测试数据为用户 u的浏览向量。 3) 通过分类器得出用户 u对i是否应推荐。 2.2. 基础算法的局限性 对AMAN 而言,其思路符合基本的协同过滤思 想。但因为有些丢失数据实际上是正样本,其推荐结 果可能会有偏向性。而对于 AMAU,其实现过程无视 所有的丢失数据并把正样本通过分类算法进行预测, 这种方法会产生一些无意义的结果,亦即所有对丢失 数据的预测都是正面的,没有区分性。所有的丢失数 据都是负样本(AMAN)和所有丢失数据都是未知的 (AMAU)是这个问题的两种极端的解决方法。 3. 相关算法的改进 3.1. 单类协同过滤的数据集特征 单类协同过滤的数据集的数据特征是其可供学 习的数据极少。常见推荐算法的主要制约就是数据的 稀疏性。而单类协同过滤问题的数据取值范围较一般 的协同过滤问题大大缩小,因而数据包含的信息也较 少。这是单类协同过滤问题面临的瓶颈。 3.2. 单类协同过滤的优化方向 针对单类协同过滤的数据特点,可以得出的主要 优化方向有两个: 1) 从待推荐数据集中挖掘隐含信息。 无论是 AMAU 的分类思想,还是 AMAN 比较用 户或项间的相似度的思想,都是直接利用数据集内个 体与个体的相似度,使用相似度进行计算,从而赋予 待评分项评分。从稀疏数据中挖掘信息的一个通用方 法是矩阵分解。但直接将 SVD 分解应用在单类协同 过滤上,没有将丢失项与该项对应的用户或项的潜在 信息结合起来。因而可以考虑针对用户或项的已有信 息(如评分的数目)给予丢失项以一定的权值,从而改 善矩阵分解的效果。 2) 将来自别的数据集的信息引入待推荐数据集。 针对单类协同过滤数据集的稀疏性,可以考虑从 别的数据集引入信息到现有数据集,以增加矩阵分解 时可以利用的信息。可行的方法有结合基于内容的推 荐、结合用户信息、以及通过迁移学习引入等。 Copyright © 2013 Hanspub 13 基于迁移学习的单类协同过滤算法 3.3. 基于加权矩阵分解的算法 单类协同过滤问题中,常用“1”用来表示有记 录的样本,“0”用来表示没有记录的缺失数据。然而, 因为缺失项中可能有隐含的正样本,这样的处理方式 可能会有遗漏。因此,可以赋予通过给丢失项以低的 权重来处理这个问题。这个思想是以从数据集中挖掘 隐含信息来优化单类协同过滤问题的。由这个思想, 可以导出基于加权矩阵分解的单类协同过滤算法 (wALS)[1]。 加权矩阵分解的基本思想是,将原评分矩阵 R分 解成两个秩较低的矩阵 U和V。使 U和V的乘积尽 量逼近 R,再用 U和V所蕴含的特征向量来计算推荐 结果。而加权指的是在进行 U和V的乘积对 R的逼 近时,根据原评分矩阵的特性,给予逼近时用来比较 的项一定的权重,从而在逼近时改善丢失项的处理[1]。 给定与 m个用户及 n个项相关的评分矩阵 以及相应的权值矩阵 ,加权低秩逼近的目标是用一个低 秩的矩阵 来使目标函数 * *0,1 mn ij mn RR + mn ij mn W WR =ij mn XX L X 最小化,其 中: 2 =ij ijij ij L XWRX 并使用 X矩阵作为推荐结果。 在这个目标函数 L X 中, 是在低秩 逼近中常见的误差项,而Wij 反映了最小化该项对目 标函数的贡献。在单类协同过滤问题中,为有评分的 正样本设置 。对没有评分的丢失项,设置 。因为在 处的样本有较高的可信度,设 置其相应的Wij 为1。作为对比,减低“负”样本的权 值。通常在 处设置 2 ji ij RX 1 ij R ij R 0 ij R 0 ij R0 0,1 ij W。 首先处理如何使目标函数最小化的问题。 对X进行分解,令 T X UV ,其 中有dm UR和 。通常 d远小于矩阵 R的秩。为了避免过拟 合,加入正则化项,有: dn UR . 222 . ,= + j T ij iji F F ij LV UVW RUUV 或者: . 22 2 .. ,= + j T ijijiij FF ij L UVWR UVUV 在上述两个公式中, 是正则化项的参数,在不 同的情况下, 由交叉校验决定。 对L分别求对 U或V的偏导数,并令偏导数为 0, 可得 U和V的迭代更新公式: 1 ... . – +,1 T iii iij j im URWVVW WI nn i WR是将向量 包含的值放置在一个零矩 阵的对角线上而生成的对角矩阵。I是d维的单位矩 阵。 .i W 1 .. – .. ,1 TT jjJ Jij i jn VRWUUWUWI * .mm JWR是将向量 . j W包含的值放置在一个 零矩阵的对角线上而生成的对角矩阵。 基于以上公式,就得到基于迭代的 wALS 算法 [2-4]。 算法过程: 输入:评分 R、权重、特征数 d 输出:秩为 d的矩阵 U和V 随机初始化 V 重复以下过程: 对所有 Ui.,通过迭代公式更新之 对所有 Vj.,通过迭代公式更新之 直至收敛 返回 U和V 分解后,得到的子矩阵中,有包含用户侧的潜在 语义信息的矩阵 U,以及包含项侧的潜在语义信息的 矩阵 V。U中的每一行表示用户潜在倾向。对目标用 户u,将 U的第 u行与 V中未被推荐的项目的第 i行 进行相乘,即得到用户u对项 i的评分结果。对评分 结果进行排序,取前 K个推荐结果,得到 TopK推荐。 3.4. wALS算法的分析与改进 . wALS 算法通过挖掘评分矩阵的潜在数据,将丢 失项赋予不同的权值,从而在逼近时提高了合理性。 但在数据量较大时,这个算法的执行效率会成为其瓶 颈。为了提高这个算法的执行效率,R. Pan等人提出 了基于将权值矩阵进行分解的优化算法[5],提高了算 法的执行速度。Yifan Hu等人提出了一种基于置信度 的加权矩阵分解协同过滤算法[6],并对其进行了执行 Copyright © 2013 Hanspub 14 基于迁移学习的单类协同过滤算法 效率上的优化。本文主要侧重于从准确率上对 wALS 算法进行进一步的优化。本文的基于迁移学习的优化 方法,亦可以应用在 R. Pan和Yifan Hu等的在效率上 改进后的 wALS 算法上。 3.5. 权值策略的选取 wALS 算法过程中,W矩阵的生成方法是一个关 键因素。正样本有相对高的可信度,因此可让 1 ij R处 。丢失项大多数都应是负样本,所以应该给予 “负”样本更低的权值[1]。对包含加权矩阵的 F范式 最优化问题,可通过上文求导数的方法解决, [7]中有 详细描述。 1 ij W 有三种朴素的权重策略,第一个权值策略认为一 个丢失项是负样本的可能性在任何条件下都是相同 的。第二种权值策略认为如果一个用户有较多的正样 本,他有可能不喜欢这些样本以外的项,那么他的丢 失项就更有可能是负样本。第三种权值策略认为如果 一个项有较少的正样本,那么与这个项相关的丢失项 就更有可能是负样本。如表 1。 3.6. 基于迁移学习的优化 基于 wALS的单类协同过滤算法虽然优于其他朴 素的单类协同过滤算法,但往往受制于数据的稀疏而 难以达到很好的效果。单类数据(例如新闻的浏览推荐) 因其是点击类型的数据,往往有较多的辅助数据可以 使用。例如,在用户侧可以使用用户其他操作的数据 (如对视频的观看)作为辅助,项一侧也可以使用诸如 新闻的互相引用的数据[8]。可以通过迁移学习的方式, 将这些辅助数据引入到wALS 算法中。这种优化方式 的思想是将来自别的数据集的信息引入数据集的优 化思想。 除迁移学习之外,Li等人提出了通过提取用户信 息对单类协同过滤算法进行优化的方法[9]。但这种方 法的限制条件较严格,需要推荐目标领域能挖掘到丰 Table 1. Weighting strategies 表1. 权重取值策略表 正样本 “负”样本 标准 1 ij W ij W 偏向用户 1 ij W ij ij j WR∝ 偏向项 1 ij W iij j i m WR∝ 富的用户特征。 将迁移学习应用到 wALS 算法中,需要一个目标 矩阵。目标推荐领域用以进行最终的推荐工作,而辅 推荐领域(评分矩阵)和一或两个辅助推荐领域(评分 助推荐领域则提供相关的迁移知识。 一般而言,辅助领域分为用户侧的辅助领域和项 侧的辅助领域。用户侧的辅助领域与目标推荐领域拥 有相同的用户集合,而项集合不同。项侧的辅助领域 与目标推荐领域拥有相同的项的集合,而用户集合不 同。例如,目标矩阵可以是某个网站 a的用户群对该 网站图书类商品的评分,而用户侧的辅助领域可以是 a网站的用户群对该网站音乐类商品的评分,项侧的 辅助领域可以是网站 b的用户群对与 a网站图书类商 品的相同商品的集合的评分。 要将辅助领域的知识迁移到目标领域,就必须借 助矩阵分解的方法。从用户辅助领域得到用户侧的知 识,而从项侧的领域得到项侧的知识。 基于加权矩阵分解的协同过滤是要求使以下目 标函数最小化: . 2 . ,ij ij ij T ij L UVW RUV 其中 W为权值矩阵;U矩阵和 V矩阵分别表达了用 户层面和项层面的潜在特征。 对目标推荐领域,有用户–项的评分矩阵 R,而 对辅助推荐领域,也有用户–项的评分矩阵 和 ,对他们分别进行 SVD 分解,使 1 R 2 R 111 1 R UBV, 222 2 R UBV。设领域 1为用 户方面的辅助领域,领域2为项方面的辅助领域,则 可取 和参与目标推荐领域的推荐工作,将其 作为目标函数的补偿项,代替原来的正则化项。将目 标函数修正为: 1 U 2 V 1 . 2 2 2 2 2 ,+ 2 u ij ij ij j v F T i F L UVW RUVU UVV 或者 2 .. 21 .. . 22 . ,2 2jj Tu ijiji ji ij v iF F L UVWR UVU UVV Copyright © 2013 Hanspub 15 基于迁移学习的单类协同过滤算法 在更新 U、V时,可求得目标函数对 U的偏导数 为: .. 1 , 1 2 +, 2 1,1 T i jijijjk j ik uijik ik j L im kd UV WUV RV U WUU 其中,对 U的第 i行.的导数认为是: i U . 1 .1 .. . ,, 11 ,, 22 2 2 i ii Tu ii ij j u iI ij j LLL, id I UVUV UV UUU UVWVW RWV UWI 令偏导为 0,即可求得在该迭代中 U、V的值。 (1) . ... 1 . 2 2 i u iiI ij j Tu Iij j URWVU WI VWVW I 而V的处理过程与 U是对称的。 4. 实验及实验结果 4.1. 数据集的选取 针对单类协同过滤问题,我们选取了Movielens 数据集进行测试。 Movielens 数据集[10],是一个在协同过滤领域被 广泛应用的数据集。该数据集来自 GroupLens 收集的 用户对电影的评分。我们使用的数据集是Movielens 的一部分,包含 943 个项和 1682 个用户,用户对项 有1~5的整数评分。评分数共 100,000个。为了使该 数据集单类化,我使们用了如下策略:将评分4和评 分5的评分视为 1,其余视为丢失项。 为了取得迁移学习的辅助数据,将原始数据集分 为四份。用来进行实验的部分包括原始数据集的一半 用户和一半项;用原始数据集中与实验部分具有相同 用户,但项不同的部分作为用户侧辅助数据;用原始 数据集中与实验部分具有相同项,但用户不同的部分 作为项侧辅助数据。将辅助数据的评分矩阵进行SVD 分解,并将相应的辅助 U和V矩阵传入实验数据的推 荐过程。 4.2. 实验设置与评价标准 实验采用交叉验证法对结果进行验证。数据集以 80/20的比例被分为训练集和测试集。对数据集进行 多次采样,并计算结果的平均值。 测试集的评价使用了基于 MAP 和HLU的方法。 基于 HLU 的误差度量对位于较前的推荐项的对 错赋予较大的权值。在进行 Top-N 推荐时,用户比较 关心推荐结果的头几项是否正确,而对推荐结果较靠 后的项的正误并不关心。基于HLU 的误差度量使用 了这样的权值策略:排名第一的资源权值为1/2,排 名第二的资源权值为 1/4,其次为1/8,等等。这种评 价方式突出了推荐项真实的重要性。 HLU 定义如下公式: max u u u u R RR u R是对于用户u的HLU 效应值,是对该用 户当,所有的正确推荐结果都在推荐结果列表顶部时 达到的最大效应值。 的定义如下: max u R u R -1 -1 2j j u j R 当排在第 j个的项是正确结果时为 1,否 则为 0。是用以调整结果数量级的参数。 j MAP(平均准确率均值)是平均准确率(AP)的对 于所有用户的均值,其思想与 HLU 类似,排名较前 的项具有较大的权重。 对特定用户的 AP 通过以下公式计算: =1 p rec pref AP100# N i u ii i是在推荐结果列表中的位置,而 N是推荐项的总数。 p rec i是(被用户所喜欢的)从1到i的列表的一部分 的准确度, p ref i是一个二元标志符,当用户喜欢第 i个项时其为 1,否则为 0。 4.3. 参与实验的算法 参与实验的算法有以下几种: Copyright © 2013 Hanspub 16 基于迁移学习的单类协同过滤算法 Copyright © 2013 Hanspub 17 1) AMAU策略的基于流行度的分类推荐算法。对 特定用户的推荐是除该用户已有评分项外最流行的项。 2) AMAN策略。有基于用户相似度的协同过滤算 法、基于项相似度的协同过滤算法以及基于 SVD矩 阵分解的协同过滤算法。这些算法的介绍详见 2.1 节。 3) wALS算法,分别是权值偏向用户的 wALS 算 法、权值偏向项的wALS 算法、标准权值策略的 wALS 算法。 4) 基于迁移学习的单类协同过滤算法。 4.4. 实验结果及分析 各个方法的结果对比(见表2)。 从实验结果看,AMAN 的几种方法对单类协同过 滤问题基本是无意义的。这也说明了单类协同过滤问 题的特殊性,亦即其数据集可用数据十分稀疏。这种 特性使传统的协同过滤算法在单类协同过滤问题上 很难起作用。也证明了单类协同过滤问题亟待更多有 效的算法。 wALS 算法在不同的权值策略下有截然不同的表 现。这说明 wALS 算法的效果对权值策略较为敏感。 因选择何种权值策略与使用的数据集密切相关,因此 在实际生产中使用wALS算法时需要对多种权值策略 进行测试。 Table 2. Experimental result 表2. 实验结果表 HLU MAP AMAN–用户 0.0 0.0 AMAN–项 0.0 0.0 AMAU 3.13 3.23 AMAN-SVD 0.07 0.35 wALS–标准 7.56 9.40 wALS–项 13.31 10.86 wALS–用户 2.98 3.29 迁移学习–用户 25.16 11.92 迁移学习–项 27.09 11.33 实验结果表明,迁移学习对推荐结果有了一定程 度的提高。 5. 结论 本文提出的基于迁移学习的单类协同过滤算法, 通过实验得到了预期的结果,从而验证了算法的优越 性。该算法针对单类协同过滤数据集的特征,从数据 集中挖掘隐藏信息及将来自别的数据集的信息引入 数据集两方面进行了优化,是一种较高效的协同过滤 算法。但算法仍需在结合用户信息、结合基于内容的 推荐等方面进行进一步的优化。 参考文献 (References) [1] R. Pan, Y. Zhou, B. Cao, N. N. Liu, R. M. Lukose, M. Scholz and Q. Yang. One-class col laborative filtering . IEEE Int ern at io nal Conference on Data Mining, 15-19 December 2008: 502-511. [2] N. D. Buono, T. Politi. A continuous technique for the weighted low-rank approximation problem. Lecture Notes in Computer Science, 2007, 3044: 988-997. [3] S. Oh. Matrix completion: Fundamentak limits and efficient al- gorithms. Stanford University, 2010. [4] P. Turney. Thumbs up or thumbs down? Semantic orientation applied to unsupervised classification of re vi ew s. New Brunswick: Proceedings of the 40th Annual Meeting of the Association of Computational Linguistics, July 2002: 417-424. [5] R. Pan, M. Scholz. Mind the gaps: Weighting the unknown in large-scale one-class collaborative filtering. Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2009: 667-676. [6] Y. Hu, Y. Koren and C. Volinsky. Collaborative filtering for im- plicit feedback datasets. Proceedings of the 2008 8th IEEE In- ternational Conference on Data Mining, 2008: 263-272. [7] N. Srebro, T. Jaakkola. Weighted low-rank approximations. Pro- ceedings of the 20th International Conference on Machine Learning, 2003. [8] W. Pan, E. W. Xiang, N. N. Liu and Q. Yang. Transfer learning in collaborative filtering for sparsity reduction. Proceedings of the Twenty-Fourth AAAI Conference on Artificial Intelligence (AAAI-10), 2010 [9] Y. Li, J. Hu, C. X. Zhai and Y. Chen. Improving one-class collaborative fi ltering by inco rporating rich user information. Pro- ceedings of the 19th ACM International Conference on Informa- tion and Knowledge Management, 2010: 959-968. [10] http://www.grouplens.org/node/73 |