不知不觉,你是否发现身边的小伙伴们都在疯狂的玩抖音,刷微博,你的购物APP也变得越来越聪明,很了解你想要的东西,就连点个外卖,美团和饿了么都知道你想要吃什么呢?是什么黑科技让这些APP变得如此神通,能深深的吸引着你的目光和味蕾呢?其实,之所以你觉得它越来越聪明越来越懂你,当然少不了你跟它之间的亲密“沟通”,看似不经意的一次点击,一次停留,它都默默的记了下来,等待你的再次临幸。这位神秘的幕后主使就是我们今天要讲的——个性化推荐算法。目前它已经深入到互联网的各类产品中,也经历了数次更新迭代,变得越来越贴心了。接下来,我将通过一个近期我们参加比赛具体讲解一些其中的算法原理。

最近读了项亮博士的《推荐系统实践》,在此对用户行为分析这章做一个总结。

一,常用推荐系统算法总结

这次比赛是由今日头条主办的短视频内容理解与推荐竞赛,我们的成绩在大规模亿级的赛道中拿了第四名,千万级数据规模的赛道中第五名。这也是我们极链AI实验室首次尝试推荐算法。

用户行为介绍

基于用户行为的推荐,在学术界名为协同过滤算法。
协同过滤就是指用户可以齐心协力,通过不断地和网站互动,使
自己的推荐列表能够不断过滤掉自己不感兴趣的物品,从而越来越满足自己的需求。

用户行为在个性化推荐系统中一般分两种——显性反馈行为(explicit
feedback)和隐性反馈 行为(implicit feedback)。

  • 显性反馈行为包括用户明确表示对物品喜好的行为:主要方式就是评分和喜欢/不喜欢;
  • 隐性反馈行为指的是那些不能明确反应用户喜好的行为:最具代表性的隐性反馈行为就是页面浏览行为;

美高梅集团4858 1

反馈除了分为显性和隐性外,还能分为正反馈、负反馈,举例子如下:

美高梅集团4858 2

互联网中的用户行为有很多种,比如浏览网页、购买商品、评论、评分等。要用一个统一的
方式表示所有这些行为是比较困难的,下面是一个表示的可能:

美高梅集团4858 3

1、Itemcf (基于商品的协同过滤)

这个算法是cf中的一种,也是当今很多大型网站都在采用的核心算法之一。对于商城网站(以Amazon为代表,当然也包括京东那种具有搞笑特色的推荐系统在内),影视类推荐,图书类推荐,音乐类推荐系统来说,item的增长速度远不如user的增长速度,而且item之间的相似性远不如user之间的相似性那么敏感,所以可以在离线系统中将item的相似度矩阵计算好,以供线上可以近乎即时地进行推荐。因为这种方法靠的是item之间的相关性进行推荐,所以推荐的item一般都和喜欢的item内容或者特性高度相似,很难推荐出用户潜在喜欢的item,多样性也比较差。

首先,来讲讲什么是推荐算法。推荐算法大致可以分为三类:基于内容的推荐算法,协同过滤推荐算法和混合推荐算法。基于内容的推荐算法,原理是将用户喜欢和自己关注过的Item在内容上类似的Item推荐给用户,比如你看了复仇者联盟1,基于内容的推荐算法发现复仇者联盟2、3、4,这些与你以前观看的item在内容上有很大关联性。协同过滤算法,包括基于用户的协同过滤和基于item的协同过滤,其中基于用户的协同过滤是通过用户之间的相似性,挖掘与用户具有相似兴趣的用户喜欢过的item,比如你的朋友喜欢复仇者联盟,那么就会推荐给你。基于item的协同过滤是找到跟用户喜好最相似的商品,然后推给他。混合推荐算法,则会融合以上方法,以加权或者串联、并联等方式进行建模。常用的包括传统机器学习算法如因子分解机,LR,GBDT,RF和近几年流行起来的DNN和FM结合的算法。

用户行为分析

先定义两个变量:
用户活跃度:用户产生过行为的物品总数
物品流行度:对物品产生过行为的用户总数

而用户活跃度和物品流行度的人数都符合Power Law,也称为长尾分布:

美高梅集团4858 4

用户活跃度和物品流行度的关系是:用户越活跃,越倾向于浏览冷门的物品。

仅仅基于用户行为数据设计的推荐算法一般称为协同过滤算法。
学术界对协同过滤算法
进行了深入研究,提出了很多方法,比如基于邻域的方法( neighborhood-based
)、隐语义模型 ( latent factor model)、基于图的随机游走算法(random
walk on graph)等。

2、Usercf (基于用户的协同过滤)

这个是cf中的另外一种,它的主要特色是可以发现和用户具有同样taste的人,有句俗话叫做观其友知其人,大概也是这个道理吧。找到用户的相似用户,通过相似用户喜欢的item推荐给该用户。因为用户的相似用户群还是比较敏感的,所以要频繁地计算出用户的相似用户矩阵,这样的话运算量会非常大。而且这个算法往往推荐出来的item很多都是大家都喜欢的比较hot的item,有的时候它提供的结果并不是个性化,反而成了大众化的推荐了。用这种算法的web应用一般都是item更新频繁,比如提供资讯类服务的应用(以“指阅”为代表的),或者笑话类推荐(以“冷笑话精选”为代表的)。当然这种算法的一个中间产物—–用户相似度矩阵是一个很有用的东西,社交类的网站可以利用这个中间产物来为用户提供相同品位的好友推荐。

这三种类型的推荐算法各有千秋,内容推荐算法的优点在于可以避免Item的冷启动问题(冷启动:如果一个Item从没有被关注过,其他推荐算法则很少会去推荐,但是基于内容的推荐算法可以分析Item之间的关系,实现推荐),但弊端在于推荐的Item可能会重复,典型的就是新闻推荐,如果你看了一则关于某某明星出轨的新闻,很可能推荐的新闻和你浏览过的,内容一致;协同过滤算法可以随着用户对商品的交互记录增加更准确的捕捉用户行为习惯,进而使得模型能够不花费额外的人工的方式来提高精度(但在初期会面临冷启动问题的困扰)。

基于邻域的算法

基于领域的方法中,主要包括两大类:

  • 基于用户的协同过滤算法,这种算法给用户推荐和他兴趣相似的其他用户喜欢的物品。
  • 基于物品的协同过滤算法,这种算法给用户推荐和他之前喜欢的物品相似的物品。

3、Content_based(基于内容的推荐)

基于内容的推荐,很大程度上是在进行文本挖掘。web应用提供的内容或者爬取的内容在推给用户之前可以做一些挖掘,比如资讯类的应用,将抓取到的资讯,通过文本分析那一套算法提取出每篇资讯的关键词,以及统计频次和逆向文档频率来聚类或者笨一点地话计算出资讯的相似度矩阵,即共同的key
words越多,两篇资讯的相似度越高。当你的用户很少很少,你的显式反馈数据非常非常少的时候,你可以根据用户的浏览或者搜索等等各种行为,来给用户进行推荐。再猥琐一点的话,你可以在用户刚刚注册好你的应用的时候,给他一些提问,比如让他输入一些感兴趣的话题啊,或者对以前看过的电影打分什么的。(当然这些电影都是你从各个簇中随机选取的,要足够多样性)这个算法它好就好在,不需要拿到用户–项目的评分矩阵,只需要知道用户喜欢什么,就可以很快速地推荐给用户十分相关的item。这个算法需要每天都要根据你抓取的资讯,不断地计算item之间的相似性。这个算法有个好处在于可以从容应对上面的两个算法其实都很难应对的问题,就是如果你想推出一个新的item,因为没有一个人有对这个new
item的评分,所以上述的两个算法不可能推荐新的东西给你,但你可以用基于内容的算法将新的item计算出它属于哪个类,然后时不时地推出你的新item,这点对于商城尤其重要。

无论哪种推荐算法,都离不开特征工程、模型学习这两个重要的步骤。接下来,通过比赛这个实例,来讲解每个步骤具体是如何实现的。这次比赛的任务是通过一个视频及用户交互行为数据集对用户兴趣进行建模,然后预测该用户在另一视频数据集上的点击行为。该任务属于机器学习中两个基本任务之一分类,而且是二分类即给给定的数据打标签,0代表unlike,unfinish,1代表like或者finish.

基于用户的协同过滤算法

基于用户的协同过滤算法主要包括两个步骤:
(1) 找到和目标用户兴趣相似的用户集合。
(2)
找到这个集合中的用户喜欢的,且目标用户没有听说过的物品推荐给目标用户。

美高梅集团4858 5

在第一步上计算相似度上,具体算法大概有几种:欧几里得距离,皮尔逊相关系数,Cosine
相似度,Tanimoto 系数。不同相似度衡量方法对于结果会有不同的影响。

4、Knn(邻近算法)

K最近邻(k-Nearest
Neighbor,KNN)分类算法,是一个理论上比较成熟的方法,也是最简单的机器学习算法之一。该方法的思路是:如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别,则该样本也属于这个类别。KNN算法中,所选择的邻居都是已经正确分类的对象。该方法在定类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。
KNN方法虽然从原理上也依赖于极限定理,但在类别决策时,只与极少量的相邻样本有关。由于KNN方法主要靠周围有限的邻近的样本,而不是靠判别类域的方法来确定所属类别的,因此对于类域的交叉或重叠较多的待分样本集来说,KNN方法较其他方法更为适合。

一.特征工程

基于物品的协同过滤算法

基于item的协同过滤,通过用户对不同item的评分来评测 item
之间的相似性,基于item
之间的相似性做出推荐,简单来讲就是:给用户推荐和他之前喜欢的物品相似的物品。

美高梅集团4858 6

5、Slope One

推荐系统的最最本质的事情就是把user-item
rating矩阵中的空白填好,看穿这个本质以后,你可能会觉得问题一下子简单多了,填格子啊?填格子谁不会啊。因此很多高效加搞笑的算法就出来了。slope
one就是其中,说实话,这个算法我自己没有写过,但是看到这个算法怎么实现的,我就觉得应该很好做,而且算起来会很快,但结果肯定不会特别理想。

Slope One的基本概念很简单, 例子1, 用户X, Y和A都对Item1打了分.
同时用户X,Y还对Item2打了分, 用户A对Item2可能会打多少分呢?

User Rating to Item 1 Rating to Item 2

X 5 3

Y 4 3

A 4 ?

根据SlopeOne算法, 应该是:4 – ((5-3) + (4-3))/2 = 2.5.

当然这个只是个算例简单地说明下原理,当user和item都很多的时候,你可以用加权的办法来做。为什么我会感觉这个算法的效果会不理想呢?因为,这个算法总是把你的口味和大众的平均口味作对等,推荐出来的东西很难是非常个性化的。很容易让很多用户的推荐结果趋向一致,也就是大数的平均值,也即大众的平均口味。

众所周知,短视频App中的视频一般都有一个醒目的标题,有一段内容丰富的连续画面,和一段有趣的声音组成,通过nlp,cv,audio等深度学习模型提取这些信息特征就组成了视频item的特征;对于用户来说,用户的身份等组成用户特征,用户点击视频的过程,停留的时间,点赞等行为则构成了基本的交互信息。比赛提供的交互信息字段,我们将它划分为三个部分包括用户信息(user_id,user_city),视频信息(item_id,item_city,author,
songs, duration time)和交互信息(did,
channel)。除此之外,视频特征,音频特征,人脸特征等都属于视频信息。

UserCF和ItemCF的综合比较

美高梅集团4858 7

对于电子商务,用户数量一般大大超过商品数量,此时Item
CF的计算复杂度较低。
在非社交网络的网站中,内容内在的联系是很重要的推荐原则,它比基于相似用户的推荐原则更加有效。比如在购书网站上,当你看一本书的时候,推荐引擎
会给你推荐相关的书籍,这个推荐的重要性进进超过了网站首页对该用户的综合推荐。可以看到,在这种情况下,Item
CF 的推荐成为了引导用户浏觅的重要手段。基于物品的协同
过滤算法,是目前电子商务采用最广泛的推荐算法。
在社交网络站点中,User CF 是一个更丌错的选择,User CF
加上社会网络信息,可 以增加用户对推荐解释的信服程度。

6、Svd(奇异值分解)

svd的全称是:Singular Value
Decomposition,翻译过来是奇异值分解,是一种矩阵分解的方法。其实,这个方法是提取一般实矩阵“特征值”的算法,(这里特征值加引号是因为,特征值是针对方阵来定义的,而一般的m*n的实矩阵是没有特征值的。)其实,矩阵就是一个线性变换的表示方法,因为一个向量乘一个矩阵的结果是一个向量,第一个向量通过线性变换来变成第二个向量。线性变换有许多变换方向,比如你可以对一个图像矩阵做伸缩同时也做平移。那么特征值和特征向量又是什么?一个特征向量就是表示其中的一个变换方向,而对应的特征值则表示这个变换方向对于整个线性变换有多么重要。书归正传,那么奇异值又是什么?我觉得奇异值就是特征值从方阵往一般实矩阵的一个推广。你将一个m*n的实矩阵和它的转置相乘,就会得到一个方阵,然后对这个方阵做特征值分解,得到的特征值就是所谓的奇异值的平方。我的意思是说,某种意义上,可以讲奇异值和特征值理解为一回事。那么拿到奇异值又会有什么用呢?拿到奇异值后,我们就可以抓到主要的成分,丢掉次要和非常次要的成分进行分析。也就是说,我们可以对原来的庞大的常常又非常稀疏的矩阵进行降维和分解,而分解后得到的矩阵都是稠密矩阵。最终我们会得到一个表示user特性的矩阵和一个表示item特性的矩阵。拿到这些数据之后,我们就可以进行推荐了,而且也可以很容易地进行聚类分析。这个算法的好处在于,可以解决rating矩阵的稀疏性问题,同时可以降低矩阵的维度,提高运算速度。但它的缺点是付出的空间代价太大。在做svd分解时,你需要先把一个大的rating矩阵分解成三个大的矩阵,这三个矩阵需要存在计算机内存中,然后才能进行降维。其实,svd这个方法的思路和PCA(主成分分析法)很像,抓住主要矛盾,忽略次要矛盾。分解降维后的矩阵非常约等于原来的矩阵。

接下来,信息有了,怎么去挖掘这些信息中隐藏的秘密呢?这就是特征工程的意义所在,尽可能多的挖掘用户和item之间的相关信息,然后将这些信息送入后面的模型进行学习。

隐语义模型(LFM)

隐语义模型最早在文本挖掘领域被提出,用于找到文本的隐含语义。相关的
名词有LSI、pLSA、LDA和Topic Model。

LFM源于对SVD(奇异值分解)方法的改进,传统SVD是线性代数典型问题,但由于计算量太大,实际上只是适用于规模很小的系统,Simon
Funk改迚SVD(Funk-SVD),后来被称为Latent Factor Model。

LFM假设了一个隐含的变量,用户兴趣,看下面的矩阵分解:

美高梅集团4858 8

R 矩阵是 user-item 矩阵,矩阵值 Rij 表示的是 user i 对 item j
的兴趣度,对于其中缺失的值,我们可以先给一个平均值。 LFM
算法从数据集中抽取出若隐变量,作为 user 和 item 之间连接的桥梁,将 R
矩阵表示为 P 矩阵和 Q 矩阵相乘。其中 P 矩阵是 user-topic 矩阵,矩阵值
Pij 表示的是 user i 对 topic j 的兴趣度;Q 矩阵式 topic-item
矩阵,矩阵值 Qij 表示的是 item j 在 topic i 中的权重。

上面这个过程就是一个svd的过程,但是当矩阵太大的时候,svd分解会太慢,于是就有了下面的方法:

美高梅集团4858 9

将矩阵分解转换为一个机器学习问题,我们通过梯度下降的方法去预估Rij,先求导:

美高梅集团4858 10

后更新:

美高梅集团4858 11

上面的算法的超参数有:

  • 隐特征的个数F;
  • 学习速率alpha;
  • 正则化参数lambda;

还有一个没讲到的是,对于Rij,我们现在只有正样本,即user-item中有的我们算Rij=1,我们要去获取负样本,Rij=0的值,负样在选择上秉持的原则是:

  • 对每个用户,要保证正负样本的平衡(数目相似)。
  • 对每个用户采样负样本时,要选取那些很热门,而用户却没有行为的物品。

此处选择采用热门商品的原因是:对于冷门的物
品,用户可能是压根没在网站中发现这个物品,所以谈不上是否感兴趣。

7、聚类算法

这里用到的聚类算法,是用来降低维度以及为并行计算作准备的。拿到rating矩阵之后,可以通过这些评分将用户自然地聚成几簇,然后用上述的算法对各个簇做推荐算法并行计算,充分地利用好所有计算资源。当然你也可以在svd分解之后,拿到user和item矩阵之后,对这两个矩阵分别作聚类分析,你可以得到user的簇以及item的簇。这样的结果会非常有意义,你可以作好友推荐,相似item推荐等等。在基于内容的算法中,因为很多资讯之间并不是那么的相关,把他们都相互计算相似度,会得到很多的0,所以没有必要。因此可以在计算之前,对整个item做个聚类,然后分别对各簇来做相似度计算。聚类算法中,我用过性能最好的也是最简单的就是k-means。

比赛初期,主办方提供了一个简单的特征构建和模型训练的框架,上文提过的FM算法,公式如下:

总结

本文首先介绍了用户行为的基本概念,介绍了显性反馈行为和隐性反馈行为,以及正反馈和负反馈,接着介绍了两大类推荐算法:基于领域的算法和隐语义模型,下面一篇会通过Surprise库来用今天介绍的算法来解决一些实际问题。

8、组合算法

任何一个算法都有它独特的优势和固有的缺陷,因此单用一个算法的web应用很少,往往是将各种算法组合起来用。

一种方式是:将多种算法计算出来的结果,加权之后排序推荐给用户。

一种方式是:将多种算法计算出来的结果,各取前几个推荐给用户,这样做的好处是结果很丰富多彩。

一种方式是:用svd算法填充后的矩阵作为输入,用普通cf做计算来输出,然后排序推荐。这种叫做层次推荐,可以得到两种方法的好处。

一种方式是:对新用户做基于内容的推荐,因为新用户没有任何评分数据,对老用户用cf来做。

… …

美高梅集团4858 12

参考

使用 LFM(Latent factor model)隐语义模型进行 Top-N
推荐
推荐系统实践

二,性能评价

该算法利用交互信息,构建矩阵,通过因子分解,来挖掘信息的交互特征。其中x代表特征属性,y是预测结果,n就是特征的交互阶数,阶数越高,求解越难。因为特征x分为category特征和numeric特征两种,category特征需要进行one-hot编码,一旦进行交互,特征的维度将会非常高,使得计算机的算力不够。实际应用中,一般只取二阶特。那么,还有其他方法去挖掘更多更深的交互信息吗?别急,下面我会介绍比赛中我们尝试的重要的特征工程方法。

1. 训练集大小对于推荐性能的影响

使用SlopeOne算法,每次随机选取6%的用户预测其喜好,进行5次实验,取MAE的均值,得到下表:

训练集大小(%)

MAE

90

0.71718149

70

0.73005925

50

0.77483222

30

0.83092947

10

0.98020104

绘制成折线图,如下图所示:

美高梅集团4858 13

由此可知,训练集越大,则推荐的准确率越高。

推荐算法的数据记录的是用户的历史行为信息,而数据的先后顺序反映了时间信息,那么利用所有的历史数据去计算未来的行为的特征生成我们暂时称之为全局特征,只利用一部分历史数据来计算特征的生成方式我们称之为局部特征。

2. 不同相似度度量对性能的影响

使用ItemCF算法,训练集大小为数据集的90%,每次随机选取30%的用户预测其喜好,进行5次实验,取MAE的均值,得到下表:

相似度度量方法

MAE

皮尔逊相关系数

0.86158483

曼哈顿距离

0.82744657

欧几里德距离

0.80844643

对数似然值相似度

0.80750607

Jaccard相似度

0.78540776

余弦相似度

0.81422523

绘制成直方图,如下图:

美高梅集团4858 14

由此可知,Jaccard相似度的性能略好于其他几种相似度,但是优势很小。使用不同相似度度量方法差别不大。

基于全局的特征

3. 不同推荐算法的性能

使用皮尔逊相关系数作为相似度,训练集大小为数据集的90%,每次随机选取6%的用户预测其喜好,进行5次实验,取MAE的均值。其中KNN算法取近邻大小为5;EM算法的学习速度为0.005,过度拟合值为0.02,随机噪声值为0.005,EM的迭代次数为20。得到下表:

推荐算法

MAE

ItemCF

0.86158483

UserCF

1.03740876

Slope One

0.71718149

KNN(k = 5)

0.83184328

SVD

(Compute SVD using EM Algorithm:

learning rate = 0.005,

overfitting prevention = 0.02,

random noise = 0.005,

epoch = 20)

0.70493273

绘制成直方图,如下图:

美高梅集团4858 15

由此可知,SVD和Slope
One算法的推荐结果最为精确,UserCF最差。这个数据和推荐系统相关著作中的结论是吻合的。

此外,在内存方面,Slope
One最占内存,1G内存下最多只能处理6%左右的用户。而其他算法均能轻松地处理30%以上的用户量。

在速度方面,SVD速度最快,处理每个用户的平均时间约为4ms,Slope
One的平均时间约为30ms,ItemCF和UserCF的平均处理时间都在10ms左右。KNN的速度是最慢的,平均处理时间约为100ms。

基于全局的特征我们主要从svd分解、统计特性、和时间相关特征,三个方面去考虑进行特征提取。

svd分解特征,提到svd,想到最多的自然是特征降维,主成分分析,那么利用svd将高维的交互特征进行降维,就可以输入模型进行训练了,比如用户和item,构造一个user-item矩阵,矩阵的每个元素代表了该用户和该item间是否有交互,有的话就是1,没有的话就是0,这个矩阵是一个极其稀疏的高维矩阵(比赛中赛道二7w*400w),通过svd分解,提取前n个主成分组成稠密特征,输入模型中训练,可以大大减少计算量。对于比赛提供的特征,我们进行了user-item,user-author,user-title的svd分解。统计特征,之所以称统计特征,是因为所有的计算涉及的都是常用的统计方法,包括求均值,方差,以及用户特征和item特征之间的条件概率P,
P(channel|uid), P(did|item_id), P(channel|item_id), P(item_author|
uid), P(item_city|uid), P(uid_city|item_id)
等。时间相关特征,这些特征主要挖掘用户某个时间段内观看视频的频率,从而得到用户在时间维度上的爱好。具体的,就是定义一个时间长度,比如1000,5000,10000等等,然后统计该段时间内用户或者item出现的频率。基于局部的特征

局部特征的构造,是根据时间顺序,划分出一部分作为历史数据,另一部分作为训练数据,通过历史数据构造特征组合(只针对category),并统计训练数据需要的信息,如图1所示,按照时间的远近,靠近测试数据的30%数据作为训练数据,前面70%数据作为历史数据,可以去除最后5%的数据之后多次划分,训练多模型来提升效果。根据马尔可夫理论,当前的状态一般只和前面一个状态相关,这也是为何如此划分数据集的依据。提取的特征描述如表格1所示。

美高梅集团4858 16

图1.局部特征构造示意图

Tabel 1:local feature deion

美高梅集团4858 17

上述所有特征中,mean和regression只针对目标finish和like进行计算,这些特征只记录了用户的历史行为,count_from_past,
count, count_from_future,
这些特征从时间角度上统计了用户从历史-现在-未来的行为。matrix_factorization
特征是通过FM算法计算的只利用user和item信息的一个特征,这样即利用了fm的信息,计算量又小。

二.模型训练

特征构造完成后,后续的任务就可以交给强大的机器学习算法来进行训练。常用的算法有基于boost算法的决策树和dnn算法(比赛中我们仅使用了前面的算法,是因为dnn的算法在增加全局特征后有提升的,但是和其他模型的结果进行融合后并没有提升,而且也没有boost的效果好)。如图2所示,针对不同特征使用不同的训练器训练流程,feature0代表局部特征,feature1代表全局特征,最后将两个框架的结果进行融合。每个阶段的比赛成绩如表2所示,只列出来赛道二中的部分成绩,“——”代表没有进行该项实验,由于全局特征在like任务的表现一直不理想,所以基于该特征的xdeepfm并未进行实验。中间关于参数选择和特征选择的成绩未列出。Final是最终提交的public成绩。

美高梅集团4858 18

图2 模型训练示意图

Tabel2:比赛数据

美高梅集团4858 19

相关文章

网站地图xml地图