加入收藏 | 设为首页 |

鲫鱼的做法-从原理到完成,详解根据朴素ML思维的协同过滤引荐算法

海外新闻 时间: 浏览:141 次

作者丨gongyouliu

修改丨Zandy

来历 | 大数据与人工智能(ID: ai-big-data)

作者在《》、《》这两篇文章中介绍了几种经典的协同过滤引荐算法。咱们在本篇文章中会持续介绍三种思路十分简略朴素的协同过滤算法,这几个算法的原理简略,简略了解,也易于工程完结,十分合适咱们快速建立引荐算法原型,并快速上线到实在事务场景中,作为其他更杂乱算法的baseline。

详细来说,咱们在本篇文章中会介绍运用相关规矩、朴素贝叶斯(naive bayes)、聚类三类机器学习算法来做引荐的办法。而且还会介绍3个根据这三类算法中心思维的工业级引荐体系,这3个引荐体系被YouTube和Google别离用于视频和新闻引荐中(其间会介绍Google News的两个引荐算法),在YouTube和Google News前期产品中得到选用,而且在其时状况下作用是十分不错的,值得咱们深化了鲫鱼的做法-从原理到完成,详解根据朴素ML思维的协同过滤引荐算法解和学习。

一、根据相关规矩的引荐算法

相关规矩是数据发掘范畴十分经典的算法,该算法来历于一个实在的事例:“啤酒与尿布”的故事。该故事发作在20世纪90年代的美国沃尔玛超市中,沃尔玛的超市管理人员剖析出售数据时发现了一个令人难以相信的现象:在某些特定的状况下,“啤酒”与“尿布”两件看上去毫无联络的产品会常常呈现在同一个购物篮(用户一次购物所买的一切产品形象地称为一个购物篮)中,这种一起的出售现象引起了管理人员的留意,经过后续查询发现,这种现象呈现在年青的父亲身上。

在美国有婴儿的家庭中,一般是母亲在家中照看婴儿,年青的父亲前去超市购买尿布。父亲在购买尿布的一起,往往会趁便为自己购买啤酒,这样就会呈现啤酒与尿布这两件看上去不相干的产品常常会呈现在同一个购物篮的现象。

沃尔玛发现了这总一起的现象,开端在卖场测验将啤酒与尿布摆放在相同的区域,让年青的父亲能够便利地一起找到这两件产品,并很快地完结购物;这样做沃尔玛超市就让这些客户一次购买了两件产品、而不是一件,然后取得了很好的产品出售收入,这便是“啤酒与尿布”故事的由来。

下面咱们给出相关规矩的界说,假定是一切标的物的调集(关于沃尔玛超市来说,便是一切的产品调集)。相关规矩一般表明为的办法,其间的子集,而且。相关规矩表明假如在用户的购物篮中,那么用户有很大概率一起购买了。经过界说相关规矩的衡量目标,一些常用的相关规矩算法(如Apriori)能够自动地发现一切相关规矩。

相关规矩的衡量目标主要有支撑度(support)相信度(confidence)两个,支撑度是指一切的购物篮中包括的购物篮的份额(即一起呈现在一次买卖中的概率),而相信度是指包括的购物篮中一起也包括的份额(即在给定的状况下,呈现的条件概率)。它们的界说如下:

支撑度越大,包括的买卖样本越多,阐明相关规矩有更多的样原本支撑,“根据”愈加充沛。相信度越大,咱们更有掌握从包括的买卖中推断出该买卖也包括。相关规矩发掘中,咱们需求发掘出支撑度和相信度大于某个阈值的相关规矩,这样的相关规矩才更可信,更有说服力,泛化才干也更强。

有了相关规矩的界说,下面咱们来解说怎样将相关规矩用于个性化引荐中。关于引荐体系来说,一个购物篮便是用户操作过的一切标的物的调集。相关规矩 表明的意思是:假如用户操作过 中的一切标的物,那么用户很或许喜爱 中的标的物。有了这些阐明,那么运用相关规矩为用户 生成引荐的算法流程如下(假定 一切操作过的标的物调集为 ):

1. 发掘出一切满意必定支撑度和相信度(支撑度和相信度大于某个常数)的相关规矩

2. 从1中一切的相关规矩中筛选出一切满意的相关规矩

3. 为用户生成引荐候选集,详细核算如下:

行将一切满意2的相关规矩中的兼并,并剔除去用户现已操作过的标的物,这些标的物便是待引荐给用户的。

4. 关于3中的候选引荐集,能够依照该标的物地点相关规矩的相信度的巨细降序摆放,关于多个相关规矩生成相同的候选引荐标的物的,能够用户相信度最大的那个相关规矩的相信度。除了能够选用相信度外,也能够用户支撑度和相信度的乘积作为排序根据。

5. 关于4中排序好的标的物,能够取topN作为引荐给用户的引荐成果。

根据相关规矩的引荐算法思路十分简略朴素,算法也易于完结,Spark Mllib中有相关规矩的两种散布式完结FP-Growth和PrefixSpan,咱们能够直接拿来运用(关于这两个完结的详细细节,能够阅览参阅文献10、1鲫鱼的做法-从原理到完成,详解根据朴素ML思维的协同过滤引荐算法1、12)。

关于相关规矩算法介绍及怎样运用相关规矩用于个性化引荐,读者还能够阅览参阅文献4、5、6、7、8、9。运用相关规矩做引荐,是从用户的过往行为中发掘用户的行为方式,并用于引荐,只用到了用户的行为数据,因而运用相关规矩做引荐也是一种协同过滤算法。

二、根据naive bayes的引荐算法

运用概率办法来构建算法模型为用户做引荐,能够将猜测评分问题当作一个分类问题,将或许的评分离散化为有限个离散值(比方1、2、3、4、5总共5个可行的分值),那么猜测用户对某个标的物的评分,就转化为用户在该标的物上的分类了(比方分为1、2、3、4、5个类别,这儿不考虑不同类之间的有序联络)。在本节咱们就运用最简略的贝叶斯分类器来进行个性化引荐。

假定总共有k个不同的猜测评分,咱们记为,一切用户对标的物的评分构成用户行为矩阵,该矩阵的-元素记为,便是用户对标的物的评分,取值为评分调集中的某个元素。下面咱们来解说怎样运用贝叶斯公式来为用户做引荐。

假定用户有过评分的一切标的物记为。现在咱们需求猜测用户对未评分的标的物的评分()。咱们能够将这个进程了解为在用户现已有评分记载的条件下,用户对新标的物的评分取调集中某个值的条件概率:

条件概率,表明的是在工作发作的状况下工作发作的概率,由闻名的贝叶斯定理,条件概率能够经过如下公式来核算:

因而,回到咱们的引荐问题,,咱们有

咱们需求确认详细值,让上式左面的的值最大,这个最大的值就能够作为用户对未评分的标的物的评分(=)。咱们留意到上式中右边的分母的值与详细的无关,因而右边分子的值的巨细才终究决议公式左面的值的相对巨细,根据该调查,咱们能够将上式记为:

现在的问题便是怎样估量上式右边项的值,实践上根据用户评分矩阵,这些项的值是比较简略估量出来的,下面咱们就来估量这些值。

  • 估量

估量

其实是的先验概率,咱们能够用对标的物评分为的用户的份额来估量该值,即

这儿分母是一切对标的物有过评分的用户,而分子是对标的物评分为的用户。

  • 估量

估量

要估量,咱们需求做一个朴素的假定,即条件无关性假定:用户一切的评分是独立无关的,也便是不同的评分之间是没有相关的,互不影响(该假定便是该算法叫做naive bayes的由来)。实践上,同一用户对不同标的物评分或许是有必定相关的,在这儿做这个假定是为了核算便利,在实践运用naive bayes做引荐时作用仍是很不错的,泛化才干也能够。有了条件无关性假定,就能够用如下公式来估量了:

而、可用一切对标的物评分为的用户中对标的物评分为的份额来估量。即

有了上面的两个估量,那么咱们运用naive bayes核算用户对标的物的评分概率问题终究能够表明为

公式1:用户对标的物评分的概率估量

有了上式,一般来说,咱们能够选用两种办法来估量的值。

1. 类似极大似然的思路估量

该办法便是用,使得 取值最大的p对应的作为的估量值,即

该办法仅仅将用户对标的物的评分看为类别变量而疏忽详细评分的数值,而下面的办规律运用了评分的详细数值。

2.选用加权均匀来估量

用户对标的物的估量能够取中的任一值,根据上面的公式1,取每一个值都有一个概率估量,那么最天然的办法是能够用这个概率作为权重,运用加权均匀来估量,详细的估量公式如下:

有了用户对标的物评分的估量,那么引荐便是顺其天然的工作了。详细来说,咱们能够核算出用户对一切未评分标的物的估量值,再依照估量值的巨细降序取topK作为给用户的引荐。这儿阐明一下,关于选用极大似然思路的估量(即上面的第一种估量办法),因为该办法是将评分当作类别变量,那么必定有许多标的物的估量值是相同的,这时假如咱们需求再差异这些评分相同的标的物的话,能够选用估量该值时的概率巨细再进行二次排序。

选用贝叶斯办法来做引荐会存在一些问题,详细来说,咱们在估量和估量时,因为样本数据稀少,导致无法进行估量或许估量值不行鲁棒性的问题。比方在估量时,咱们用公式

来估量,从该式能够看到,假如无用户或许很少用户对标的物有评分(这种状况是存在的,如 是新参加的标的物或许是冷门标的物),这时或许会呈现用 来估量的状况,即便不是 ,当分子分母都很小时,估量值动摇会很大,不行鲁棒,对估量成果影响很大。一般咱们能够选用拉普拉斯滑润(Laplacian smoothing)的办法来处理,得到愈加安稳的估量值。

针对上面这个比方,咱们来说下怎样运用拉普拉斯滑润来处理:假定是对标的物评别离离为的用户数,那么上面的估量便是

添加拉普拉斯滑润后的估量公式便是

从这个公式能够看出,当没有用户对标的物评过分时,就用 来估量,这是在没有已知信息的状况下比较合理的估量。上式中是润滑化因子,值越大,估量越润滑(鲁棒性越好),这时公式对数据就不行灵敏。关于的估量,也能够选用相同的办法,这儿不再赘述。

到此为止,咱们讲完了怎样运用naive bayes来为用户做引荐的办法,该办法也是只运用了用户的操作行为矩阵,所以也是一种协同过滤算法。

naive bayes办法是一个十分简略直观的办法,工程完结也十分简略,也易于并行化。它对噪音有必定的“免疫力”,不太会遭到单个评分禁绝的影响,而且也不易于过拟合(个人觉得前面介绍的条件无关性假定是泛化才干强的主要原因),一般状况下猜测作用还不错,而且当用户行为不多时,也能够运用(需求运用拉普拉斯滑润来处理),而不像矩阵分化等算法,需求许多的用户行为才干进行引荐。

读者能够从从参阅文献13、14、15、16中了解更多关于怎样运用贝叶斯及其他概率办法来做引荐的计划。

三、根据聚类的引荐算法

根据聚类来做引荐有两种可行的计划,一种是将用户聚类,别的一种是将标的物聚类。下面来简略描绘一下怎样根据这两种聚类来做引荐。

1.根据用户聚类的引荐

假如咱们将一切用户聚类了,就能够将该用户地点类别的其他用户操作过的标的物(可是该用户没有操作行为)引荐给该用户。详细核算公式如下,其间是给用户u的引荐,是用户地点的聚类,别离是用户的操作前史调集。

那么怎样对用户聚类呢?可行的计划主要有如下几类:

(1) 根据用户的人口核算学特征对用户聚类

用户的年纪、性别、地域、家庭组成、学历、收入等信息都能够作为一个特征,类别特征能够选用one-hot编码,一切特征终究都能够转化为数值的,终究取得用户特征的向量表明,经过Kmeans聚类算法来对用户聚类。

(2) 根据用户行为对用户聚类

比方选用矩阵分化就能够取得用户的嵌入表明,用户操作行为矩阵的行向量也是用户的一种向量表明,再运用Kmeans对用户进行聚类。

(3) 根据交际联络对用户聚类

假如是交际产品,用户之间的交际链条能够构成一个用户联络图,该交际图中一切的联通区域就形成了用户的一种聚类。这种引荐其实便是将你的老友喜爱的标的物引荐给你。

2.根据标的物聚类引荐

假如有了标的物的聚类,引荐就好办了。从用户前史行为中的标的物地点的类别挑选用户有操作行为的标的物引荐给该用户,这种引荐办法是十分直观天然的。详细核算公式如下,其间是给用户的引荐,是用户的前史操作行为调集,是标的物地点的聚类。

一起,有了标的物聚类,咱们还能够做标的物相关标的物的相关引荐,详细做法是将标的物A地点类别中的其他标的物作为相关引荐成果。

那么怎样对标的物聚类呢?可行的办法有运用标的物的metadata信息,选用TF-IDF、LDA、Word2vec等办法取得标的物的向量表明,再运用Kmeans聚类。详细鲫鱼的做法-从原理到完成,详解根据朴素ML思维的协同过滤引荐算法的完结细节这儿不介绍,感爱好的读者能够自行查找相关资料做深化学习,作者在《根据内容的引荐算法》这篇文章中也做了比较详细的介绍。别的,也能够根据用户的前史操作行为,取得标的物的嵌入表明(矩阵分化、item2vec等算法),用户行为矩阵的列向量也是标的物的一种向量表明。

参阅文献17、18、19、20有更多关于怎样用聚类来做引荐的算法,感爱好的读者能够参阅学习。

到此为止,咱们讲完了根据相关规矩、naive bayes、聚类做个性化引荐的办法。下面咱们就根据这几个办法的思维来介绍三个工业级的引荐引擎,供咱们学习参阅,一起也期望凭借这几个工业级引荐体系的介绍加深咱们对这三个办法的思路的了解。

四、You Tube根据相关规矩思路的视频引荐算法

该算法建立在一个根本假定根底之上:假如用户喜爱种子视频,那么用户喜爱与种子视频 类似的候选视频的概率必定很大,候选视频越类似,那么用户喜爱候选视频的概率也越大。那么剩余便是怎样处理这两个问题了,一是怎样核算两个视频的类似度,二是怎样挑选种子视频,下面咱们来别离介绍。一起,咱们也会介绍终究怎样给用户生成个性化引荐。

1.核算两个视频的类似度(相关度)

该算法是运用相关规矩的思路,在必定时刻内(比方24小时内)核算两两被用户一起播映过的视频对 ,将播映次数计为,那么候选视频的类似度能够表明如下:

其间是一个归一化常数,会归纳考虑种子视频与候选视频的“大局盛行度”,假如咱们别离记、为视频、在上面的一段时刻内总的播映次数。那么咱们能够界说

该归一化函数是十分直观简略的,用其他归一化函数也是能够的。假如用该归一化函数的话,对一切候选视频来说,是相同的,所以能够疏忽,其实咱们是用候选视频的“大局盛行度”来归一化。在分母中,这阐明越大的视频,与种子视频的类似度会更小,该归一化办法愈加倾向于偏冷门的候选视频。

上面仅仅一个十分简略的描绘和核算公式,咱们也能够将视频的metadata、观看时刻等信息整合进来核算类似度。别的,还需求处理脏的播映行为数据。

2.根据单个种子视频生成候选视频集

根据类似度核算公式,咱们能够挑选出种子视频的最类似的topN候选集,一般咱们会确认一个最小的阈值,需求类似度大于该阈值才会选出来,这也是为了防止挑选许多只需很少播映量的视频(这时种子视频和候选视频被一起播映的次数也很小)导致引荐成果太差。

根据上述从种子视频挑选候选视频的规矩能够当作将一切视频调集形成了一个有向图,关于任何一个视频对,假如(候选视频在种子视频的类似视频列表会集),那么存在一条从的边,边的权重为

运用该办法为种子视频生成的视频候选集,能够作为视频的相关引荐,为种子视频引荐相关的视频。

3.根据用户行为为用户出产引荐候选集

上面讲到了单个视频怎样生成候选集,那么关于单个用户也是很简略选用上面的办法生成引荐候选集的。咱们能够将用户播映过的视频或许清晰表明过喜爱的视频作为初始种子视频集。

关于初始种子集,咱们能够选用如下办法来生成候选集:

根据上面视频的有向图解说,咱们能够沿着调集的有向边向外拓宽,关于恣意的种子视频(),咱们考虑它的相关视频集。咱们将一切经过这种办法拓宽出的视频集记为,那么咱们有

一般状况下,咱们核算出就满足咱们取得比较多的、作用还能够的、有必定多样性的引荐候选集了。但实践上,经过这种办法生成的引荐候选集品种比较狭隘,跟用户的爱好太类似。这种办法尽管生成了用户或许感爱好的视频,可是或许用户没有太多惊喜,会让用户沉浸在比较小的视频范围内,就像进入了一个漩涡中,无法发现更大更精彩的国际。

为了拓宽用户的候选引荐集的空间,处理上述越推越窄的问题,咱们能够沿着种子视频集 地点的视频有向图进行n次向外拓宽(用图论的术语,便是n次传递闭包),咱们记为经过种子会集的某个种子视频经过不超越n次路由可达的一切视频组成的调集,那么咱们有

留意,,上面的公式也跟前面说到的的公式是兼容的。那么咱们终究生成的引荐候选集便是

一般N很小(拓宽很少的几步)时就能够取得十分多具有多样性的引荐成果,即便对种子集很小的用户也是如此。经过上述途径拓宽,咱们能够为每个候选的引荐视频相关一个种子视频(经过上述拓宽,从某个种子视频到候选视频的途径就将候选视频相关到了种子视频),该种子视频既可用于后边的引荐成果排序,还能够作为引荐解说(例如假如候选视频是经过种子视频取得的,咱们能够用“因为你喜爱/看过”来作为引荐解说鲫鱼的做法-从原理到完成,详解根据朴素ML思维的协同过滤引荐算法语,是经过多步类似链接在一起的,它们多少是有一些类似性的,用户从这两个视频中是能够直接感知到这品种似的,所以该引荐理由是有必定说服力的)。

4.引荐成果排序

经过上面3中的介绍,咱们能够为用户生成引荐候选集了,那么这些候选会集的视频怎样引荐给用户呢?也即咱们怎样摆放这些候选视频呢?咱们需求将用户更乐意点击的排在前面。

咱们能够从视频质量、用户对视频的偏好度、多样性等几个维度来考虑。

频质量是指视频本身的吸引力,比方视频的海报清晰度、视频播映次数、视频被点赞的次数、视频被转载的次数、视频被保藏的次数等。这些不同维度的视频质量,咱们能够经过打分取得一个固定的质量得分,详细打分办法能够多种多样,这儿不再细说。咱们这儿记视频的质量为

经过前面的介绍咱们知道每个候选视频是经过某个种子沿着有向图经过若干步的拓宽取得的。如下图,假定候选视频是经过种子视频经过k步取得,下图中箭头上方的是相邻两个视频的类似度。

那么用户对视频的偏好度能够用如下公式来核算

其间,是用户对视频的偏好度及它本身的受欢迎程度,咱们能够经过用户播映的时长或许总播映量等数值来衡量。

假如从有多条途径,能够挑选最短的途径,这是因为咱们是一步一步拓宽获取候选集的,当某个视频被某一步拓宽到了,后边再拓宽到它时,前面现已核算了,一切在这一步就疏忽掉。

有了上面介绍的候选视频得分及用户对视频的偏好度,咱们能够用下面公式来核算用户对视频终究的评分:

经过将一切候选视频依照上述公式降序摆放就能够得到候选视频的排序了。运用上面公式,间隔用户种子视频集越远,经过公式

的类似性连乘得到的值也越小,那么就有或许排在后边了。那么咱们怎样处理这个问题取得多样性呢?一般咱们能够经过约束由同一种子视频生成的候选视频的数量来取得多样性(因为同一种子视频生成的视频多少是有一些类似度的),或许约束由同一途径发作视频数量(比方由同一个用户上传的视频)。经过在上述排好序的引荐列表中,剔除去部分由同一种子视频生成的视频或许同一途径发作的视频,就能够取得终究的引荐成果。

上面介绍的便是YouTube根据视频被用户一起观看的次数取得视频之间的类似度,从而经过视频类似度传递取得终究引荐的办法。该办法本质上便是相关规矩的思路,只用到了用户的播映办法信息,因而也是一种协同过滤算法。

五、Goodle News根据贝叶斯结构引荐算法

前面第二节简略讲了怎样运用naive bayes算法来为用户生成个性化引荐,在这一节咱们解说Google News运用贝叶斯结构来做引荐的办法。Google的这篇文章(参阅文献2)选用别的的思路,根据用户曩昔看新闻的前史行为运用贝叶斯结构来猜测用户其时对新闻的爱好,再结合协同过滤来做引荐。下面咱们来解说该篇文章的中心思维。

1.根据用户曩昔的行为来剖析用户的爱好点

首要将一切新闻依照事前确认好的类别分红若干类(主题):,如“国际”、“体育”、“文娱”等类别。

首要核算某个用户在某段时刻周期(比方依照一个月一个周期等)内的点击行为在上述类别上的散布,记为

公式1:用户u在时刻周期t内的行为在新闻主题上的散布

这儿,代表用户在时刻周期内点击主题类别 的次数。是该用户在这段时刻周期内点击新闻的总数量。表明用户在时刻周期内涵各个新闻主题类别上的时刻花费散布,反映了用户的爱好散布。

新闻是有地域差异性的,相同地,类似单个用户的爱好偏好散布,咱们能够核算某个国家或许某个区域的一切用户点击行为的整体在时刻周期内涵上述新闻主题上的散布。咱们将该散布记为。核算办法和上面单个用户相同,将该国家或区域一切用户当成一个整体来核算。

该文章经过许多的数据剖析,终究得到如下4个定论,后边的贝叶斯结构也是根据这几个定论来打开的。细节的剖析读者能够阅览参阅文献2。

(1) 用户的爱好的确跟着时刻改变;

(2) 大众对新闻的点击散布反映了爱好的发展趋势,并遭到重大工作(如国际杯等)的影响;

(3) 不同国家/区域对新闻的偏好是不相同的,存在不同的发展趋势;

(4) 从某种程度上说,单个用户的爱好改变趋势是遭到该用户地点国家/区域的新闻趋势改变影响的;

有了上面的根本概念和开始数据剖析得到的定论作为根底,下面咱们来阐明怎样用贝叶斯结构来为用户的爱好建模。

2.运用贝叶斯结构来建模用户的爱好

咱们能够将用户的爱好分为两种:一种是用户的实在爱好,一种是会遭到国家/区域大的爱好趋势影响的暂时爱好。用户的实在爱好是由用户的性别、年纪、受教育程度、专业等决议的,它是相对安稳的,不太会跟着时刻而急剧改变。另一方面,当用户觉得要读什么新闻时,是会遭到用户地点区域新闻趋势的影响的,这种影响是短期的,是跟着时刻改变的。

根据用户点击行为方式和用户地点地集体的行为模型,能够经过贝叶斯结构能够很好地猜测用户其时对新闻的爱好,详细能够经过如下三个进程来取得用户的其时爱好。

(1) 猜测用户在某个时刻周期内的实在爱好

关于特定时刻周期内的某个用户是用户对一切新闻主题上的点击散布,是用户地点地域整体用户的爱好散布,代表的是爱好趋势。咱们期望学习用户的从呈现出的而不会遭到搅扰的实在爱好。

咱们用

来表明用户在新闻主题上的实在爱好,它是一个条件概率,表明在新闻主题为的条件下,用户进行点击的概率。运用贝叶斯公式,咱们能够选用下式来核算

公式2:用户点击归于主题的文章的概率

上式中

是用户点击的一切新闻中该新闻归于主题的概率,它能够从用户的点击散布中预算出(拜见上面的公式1,能够用的第i个重量来预算)。

而是新闻归于主题的先验概率,也便是在时刻周期内一切发布的新闻归于类别的份额,它与用户地点地域的新闻改变趋势相关,如有有更多的有关主题的新闻工作发作,那么关于主题的新闻就会越多。咱们能够用整体散布中的第i个重量来近似估量。

是用户点击任何一个类别的文章的先验概率,与详细的文章主题无关。

从上面公式2知道,表明用户对主题的感爱好程度,不同于该区域其他用户的爱好。假如用户读了许多体育类的新闻,而许多其他用户也读了体育类新闻,这或许是有一些体育相关抢手工作引起的。相反,假如该用户阅览了许多体育新闻而该区域其他用户很少读体育新闻,这就代表的是用户真的对体育感爱好。

(2) 结合用户在不一起间周期的爱好,取得用户精确的与时刻无关的实在爱好

上面(1)中核算了用户在一个时刻周期内的爱好偏好,咱们能够将用户在曩昔核算周期内一切时刻周期的爱好归并起来取得用户归纳的对新闻类别的实在爱好偏好,详细拜见下面公式的核算逻辑。

上式中是用户在时刻周期内总的新闻播映量。咱们能够假定用户在一切时刻周期内点击一篇新闻的先验概率是固定不变的,也即假定上式中的与时刻周期无关,咱们记为。那么上式能够改写为下面的

公式3:用户在曩昔核算周期内一切时刻段的归纳爱好

上面的公式3便是用户的实在爱好,该爱好其实是用户在多个时刻周期内的爱好的某种加权均匀。

(3) 结合用户实在爱好和其时的新闻趋势,猜测用户其时的爱好

如前面所说,用户的爱好能够分化为两部分,一部分是用户长时刻的的实在爱好,别的一部分是遭到其时趋势影响的短期爱好。(1)、(2)根据用户曩昔的点击播映行为核算出了用户的长时刻的实在爱好。为了衡量用户其时对新闻的短期爱好,咱们用用户地点地域的一切用户在一个较短时刻段(比方曩昔一个小时)的整体点击散布来描写(用

来表明),因为地点地域有许多用户,在这段较短时刻内也有满足多的数据来精确核算出哪些新闻主题是抢手的。

咱们的终究目标是猜测用户在将来一段时刻的点击散布,相同地,咱们能够用贝叶斯公式得到下面的核算公式:

咱们用用户的实在爱好(公式3)来估量

,而且假定用户点击任何一篇新闻的概率为常数,不受时刻影响(即假定

=),那么上式就能够表明为(将公式3代入进来)

咱们能够在上式中加上一个虚拟点击项,它跟其时新闻趋势的概率散布

同散布,那么用户在未来短时刻内对新闻的爱好偏好概率终究变为

公式4:用户其时对新闻主题的爱好偏好概率

上式中的便是虚拟点击数(在参阅文献2中取值为10),它能够当作是一个润滑化的因子,当某个用户只需十分少的点击前史时,这时是用户其时的新闻趋势(

)来预估该用户的点击概率,这在没有太多该用户前史数据的状况下是一个合理的估量。当

远远大于时,上式就能够疏忽,还原为用户实在的点击散布预估。

上述预估用户将来段时刻内的爱好散布的办法的一个重要长处是,咱们能够增量地核算用户的点击散布。咱们能够将曩昔每个时刻周期对应的

的值事前存起来,当更新用户的爱好偏好概率时,只需求将最近一个时刻周期的值核算出,运用上面的公司4及预先存下来的曩昔时刻段的值就能够得到用户最新的爱好偏好散布。

3.为用户做个性化引荐

为了对引荐候选集进行排序取得终究的引荐成果,该引荐算法核算出两个核算量:一个是,称之为信息过滤得分,别的一个是,即协同过滤得分(运用协同过滤算法猜测的用户对新闻的得分,能够运用参阅文献3中的办法得到)。其间的核算进程是这样的,先取得该文章的类别,再根据上面的公式4得到用户对类别的的偏好概率,该值作为的值。咱们将这两个得分相乘,终究运用如下的公式来核算用户对某个新闻的爱好得分。

终究根据上述公式核算出该用户对一切新闻的得分,取得分最高的topN作为终究的引荐成果。该办法经过在Google news上验证,比独自选用协同过滤有更好的猜测作用。

该办法运用用户曩昔及用户地点区域的点击行为来猜测用户其时对新闻的偏好概率,再与协同过滤结合进行终究的引荐。猜测用户爱好偏好概率的进程只用到了用户及用户地点地域整体用户对新闻的点击数据,因而也是一种协同过滤办法。细节的完结计划,读者能够阅览参阅文献2进行进一步了解。

六、Goodle News根据用户聚类的引荐算法

参阅文献3中运用了3种模型来预估一个用户对一个新闻的评分,终究经过加权均匀取得用户对新闻的终究评分,其间第三种办法covisitation的思维咱们在《协同过滤引荐算法》第六节“近实时协同过滤算法的工程完结“有详细解说,本质上是一种相关规矩的思路,咱们这儿不再介绍。别的两种算法别离是根据MinHash和PLSI聚类的办法,在这儿咱们只介绍MinHash算法,PLSI算法读者能够自行阅览参阅文献3来了解。

1.根据MinHash聚类

关于用户,他的点击前史记为。那么两个用户的类似度能够用Jaccard系数来表明:

有了两个用户之间的类似度,咱们能够十分办法化地将类似用户点击过的新闻经过上面的类似度加权引荐给用户。可是用户数和新闻数都是天文数字,无法在极短时刻内为许多用户完结核算。这时,咱们能够选用LSH(Locality Sensitive Hashing)的思路来核算,大大削减核算杂乱度。

LSH的中心思维是,关于一组数据(关于咱们这个场景来说,这一组数据便是用户的前史点击记载),咱们能够用一组哈希函数来取得哈希值,假如两组数据十分类似,那么哈希值抵触的概率也越大,而抵触率是等于这两组数据的类似度的。当咱们用Jaccard系数来核算用户点击前史的类似度时,这时的LSH就叫做MinHash。

咱们先来阐明怎样为一个用户核算hash值,一切新闻集为,咱们对调集进行一次随机置换,置换后的有序调集记为(),咱们核算用户的哈希值为

能够证明(有爱鲫鱼的做法-从原理到完成,详解根据朴素ML思维的协同过滤引荐算法好的读者能够自行证明,或许参阅相关参阅文献),两个用户的哈希值抵触(值相同)的概率便是用Jaccard系数核算的类似度。所以咱们能够将MinHash认为是一种概率聚类办法,对应的哈希值便是一个类:,一切哈希值为的用户聚为一类

咱们能够取个置换(即个哈希函数),将这个哈希函数得到的哈希值拼接起来,那么两个用户个拼接的哈希值相同的概率就等于。很显然,经过将个哈希值拼接起来得到的聚类更精密(个哈希值都持平的用户必定更少,所以类更小,更精密),而且类似度也会更高。从找用户最近的范畴(最类似的用户)的视点来看,将个哈希值拼接起来的办法的精准度更高,可是召回率更低(聚类更小了,因而召回的新闻更少了,所以一般召回率就降低了),为了提高召回率,取得更多的类似用户,咱们能够将这个进程并行进行次,终究每个用户取得个聚类,相当于进行了次召回,在论文中作者主张取2到4,取10到20。

在实践的工程实践上,因为新闻数量太大,进行置换操作耗时很大,能够选用简化的思路(精度会打扣头),关于上面说到的个哈希函数(置换),咱们事前取个独立的随机种子值与之一一对应,每个随机种子便是哈希函数的代替。关于每个新闻及每个种子值,咱们运用该种子值和该新闻的Id(是整数值),运用一个特定的哈希函数核算出一个哈希值,该哈希值作为运用前面讲的经过置换后该新闻的下标,那么选用这种办法后用户 的哈希核算公式如下:

该办法不需求对新闻集进行置换,会大大削减核算量,而且只需这个特定哈希函数的取值范围在0到之间,那么抵触概率就会比较小,经过这种近似的MinHash值与实在的MinHash值性质近似。

上面解说了MinHash聚类的算法完结细节,详细工程完结时是能够用Hadoop或许Spark等散布式核算渠道来并行核算的,这儿不细说。咱们能够将每个用户的聚类及每个聚类包括的用户用倒排索引表的格局存储起来,便利后边做引荐时查阅。

2.根据聚类为用户做引荐

有了用户的聚类,咱们能够选用如下进程来为单个用户生成个性化引荐,每个用户的引荐战略是相同的,所以能够选用散布式核算渠道Spark等东西来并行化处理。

(1) 核算出用户对新闻的评分

(2) 核算出用户对一切新闻的评分

(3) 将一切新闻评分降序摆放,取topK作为该用户的引荐

上面的(2)、(3)是十分简略的处理,咱们要点来说一下(1),怎样核算用户对新闻的评分。首要咱们能够得到用户所属的一切类别,关于每个类别,取出该类别中一切的用户对新闻的点击次数之和(咱们能够事前将每个类别中用户点击过的新闻及次数存储起来,便利查找),再除以该类别一切点击之和,得到该类别对新闻的评分,那么用户所属的类别对新闻的总评分为:

这儿的便是刚刚说到的类中一切用户对新闻点击次数之和,是类一切用户的一切点击次数之和。咱们用上式核算出的来表明用户对新闻的评分。

至此,根据我自己的了解,简略介绍完了Google News根据用户聚类的引荐算法。该办法也只用到了用户及其他用户的新闻点击行为,因而也是一种协同过滤算法,该算法的细节读者能够阅览参阅文献3。参阅文献17、18、19、20有更多关于怎样用聚类来做引荐的算法,感爱好的读者能够参阅学习。

总结

本文解说了相关规矩、朴素贝叶斯、聚类等三类根底机器学习算法怎样用于个性化引荐的理论知识。一起从算法原理和工程完结的视点简略总结了YouTube和Google News的三篇别离选用相关规矩、朴素贝叶斯、聚类思路来做引荐的论文。这几篇论文有很强的工程指导意义,值得咱们学习。

尽管这些算法原理简略、简略了解,看起来不那么巨大上,可是这些算法却在工业界有过十分好的使用,在其时算是十分优异的算法。这些算法现在或许看起来太简略了,也或许不会用在现在的引荐体系上,但它们朴素的思维下面包含的是深入的道理,值得咱们引荐从业者学习、考虑、学习,期望读者能够很好地了解它们,并吸收这些朴素思维背面的精华。

参阅文献

1.The YouTube Video Recommendation System

2.Personalized News Recommendation Based on Click Behavior

3.Google news personalization: Scalable online collaborative flitering

4.Robustness of collaborative recommendation based on association rule mining

5.Analysis of recommendation algorithms for e-commerce

6.Fast algorithms for mining association rules

7.Efficient adaptive-support association rule mining for recommender systems

8.Mining navigation history for recommendation

9.Collaborative filtering by mining association rules from user acess sequences

10.Mining frequent patterns without candidate generation

11.Pfp: parallel fp-growth for query recommendation

12.Mining sequential patterns by pattern-growth: the PrefixSpan approach

13.Empirical analysis of predictive algorithms for collaborative filtering

14.A Bayesian model for collaborative filtering

15.Collaborative filtering with the simple Bayesian classifier

16.Probabilistic memory-based collaborative filtering

17.Clustering methods for宋金庚 collaborative filtering

18.Rectree: A efficient collaborative filtering method

19.Scalable collaborative filtering using cluster-based smoothing

20.Latent class models for collaborative filtering

(*本文为AI科技大本营转载文章,转载请联络作者)

你点的每个“在看”,我都仔细当成了喜爱