32个基本算法

1、A* 搜索算法

—图形搜索算法,从给定起点到给定终点计算出路径。其中使用了一种启发式的估算,为每个节点估算通过该节点的最佳路径,并以之为各个地点排定次序。算法以得到的次序访问这些节点。因此,A*搜索算法是最佳优先搜索的范例。

2、集束搜索(又名定向搜索,Beam Search)——最佳优先搜索算法的优化。使用启发式函数评估它检查的每个节点的能力。不过,集束搜索只能在每个深度中发现最前面的m个最符合条件的节点,m是固定数字——集束的宽度。

3、二分查找(Binary Search)——在线性数组中找特定值的算法,每个步骤去掉一半不符合要求的数据。

4、分支界定算法(Branch and Bound)——在多种最优化问题中寻找特定最优化解决方案的算法,特别是针对离散、组合的最优化。

5、Buchberger算法——一种数学算法,可将其视为针对单变量最大公约数求解的欧几里得算法和线性系统中高斯消元法的泛化。

6、数据压缩——采取特定编码方案,使用更少的字节数(或是其他信息承载单元)对信息编码的过程,又叫来源编码。

7、Diffie-Hellman密钥交换算法——一种加密协议,允许双方在事先不了解对方的情况下,在不安全的通信信道中,共同建立共享密钥。该密钥以后可与一个对称密码一起,加密后续通讯。

8、Dijkstra算法——针对没有负值权重边的有向图,计算其中的单一起点最短算法。

9、离散微分算法(Discrete differentiation)。

10、动态规划算法(Dynamic Programming)——展示互相覆盖的子问题和最优子架构算法

11、欧几里得算法(Euclidean algorithm)——计算两个整数的最大公约数。最古老的算法之一,出现在公元前300前欧几里得的《几何原本》。

12、期望-最大算法(Expectation-maximization algorithm,又名EM-Training)——在统计计算中,期望-最大算法在概率模型中寻找可能性最大的参数估算值,其中模型依赖于未发现的潜在变量。EM在两个步骤中交替计算,第一步是计算期望,利用对隐藏变量的现有估计值,计算其最大可能估计值;第二步是最大化,最大化在第一步上求得的最大可能值来计算参数的值。

13、快速傅里叶变换(Fast Fourier transform,FFT)——计算离散的傅里叶变换(DFT)及其反转。该算法应用范围很广,从数字信号处理到解决偏微分方程,到快速计算大整数乘积。

14、梯度下降(Gradient descent)——一种数学上的最优化算法。

15、哈希算法(Hashing)。

16、堆排序(Heaps)。

17、Karatsuba乘法——需要完成上千位整数的乘法的系统中使用,比如计算机代数系统和大数程序库,如果使用长乘法,速度太慢。该算法发现于1962年。

18、LLL算法(Lenstra-Lenstra-Lovasz lattice reduction)——以格规约(lattice)基数为输入,输出短正交向量基数。LLL算法在以下公共密钥加密方法中有大量使用:背包加密系统(knapsack)、有特定设置的RSA加密等等。

19、最大流量算法(Maximum flow)——该算法试图从一个流量网络中找到最大的流。它优势被定义为找到这样一个流的值。最大流问题可以看作更复杂的网络流问题的特定情况。最大流与网络中的界面有关,这就是最大流-最小截定理(Max-flow min-cut theorem)。Ford-Fulkerson 能找到一个流网络中的最大流。

20、合并排序(Merge Sort)。

21、牛顿法(Newton’s method)——求非线性方程(组)零点的一种重要的迭代法。

22、Q-learning学习算法——这是一种通过学习动作值函数(action-value function)完成的强化学习算法,函数采取在给定状态的给定动作,并计算出期望的效用价值,在此后遵循固定的策略。Q-leanring的优势是,在不需要环境模型的情况下,可以对比可采纳行动的期望效用。

23、两次筛法(Quadratic Sieve)——现代整数因子分解算法,在实践中,是目前已知第二快的此类算法(仅次于数域筛法Number Field Sieve)。对于110位以下的十位整数,它仍是最快的,而且都认为它比数域筛法更简单。

24、RANSAC——是“RANdom SAmple Consensus”的缩写。该算法根据一系列观察得到的数据,数据中包含异常值,估算一个数学模型的参数值。其基本假设是:数据包含非异化值,也就是能够通过某些模型参数解释的值,异化值就是那些不符合模型的数据点。

25、RSA——公钥加密算法。首个适用于以签名作为加密的算法。RSA在电商行业中仍大规模使用,大家也相信它有足够安全长度的公钥。

26、Sch?nhage-Strassen算法——在数学中,Sch?nhage-Strassen算法是用来完成大整数的乘法的快速渐近算法。其算法复杂度为:O(N log(N) log(log(N))),该算法使用了傅里叶变换。

27、单纯型算法(Simplex Algorithm)——在数学的优化理论中,单纯型算法是常用的技术,用来找到线性规划问题的数值解。线性规划问题包括在一组实变量上的一系列线性不等式组,以及一个等待最大化(或最小化)的固定线性函数。

28、奇异值分解(Singular value decomposition,简称SVD)——在线性代数中,SVD是重要的实数或复数矩阵的分解方法,在信号处理和统计中有多种应用,比如计算矩阵的伪逆矩阵(以求解最小二乘法问题)、解决超定线性系统(overdetermined linear systems)、矩阵逼近、数值天气预报等等。

29、求解线性方程组(Solving a system of linear equations)——线性方程组是数学中最古老的问题,它们有很多应用,比如在数字信号处理、线性规划中的估算和预测、数值分析中的非线性问题逼近等等。求解线性方程组,可以使用高斯—约当消去法(Gauss-Jordan elimination),或是柯列斯基分解( Cholesky decomposition)。

30、Strukturtensor算法——应用于模式识别领域,为所有像素找出一种计算方法,看看该像素是否处于同质区域( homogenous region),看看它是否属于边缘,还是是一个顶点。

31、合并查找算法(Union-find)——给定一组元素,该算法常常用来把这些元素分为多个分离的、彼此不重合的组。不相交集(disjoint-set)的数据结构可以跟踪这样的切分方法。合并查找算法可以在此种数据结构上完成两个有用的操作:

查找:判断某特定元素属于哪个组。

合并:联合或合并两个组为一个组。

32、维特比算法(Viterbi algorithm)——寻找隐藏状态最有可能序列的动态规划算法,这种序列被称为维特比路径,其结果是一系列可以观察到的事件,特别是在隐藏的Markov模型中。

热度算法和个性化推荐

1. 算法的发展阶段

个性化推荐不是产品首次发布时就能带的,无论是基于用户行为的个性化,还是基于内容相似度的个性化,都建立在大量的用户数和内容的基础上。产品发布之初,一般两边的数据都有残缺,因此个性化推荐也无法开展。

所以在产品发展的初期,推荐内容一般采用更加聚合的“热度算法”,顾名思义就是把热点的内容优先推荐给用户。虽然无法做到基于兴趣和习惯为每一个用户做到精准化的推荐,但能覆盖到大部分的内容需求,而且启动成本比个性化推荐算法低太多。

因此内容型产品,推荐在发布初期用热度算法实现冷启动,积累了一定量级以后,才能逐渐开展个性化推荐算法。

2. 热度算法

2.1 热度算法基本原理

需要了解的是,热度算法也是需要不断优化去完善的,基本原理:

新闻热度分 = 初始热度分 + 用户交互产生的热度分 – 随时间衰减的热度分

Score = S0 + S(Users) – S(Time)

新闻入库后,系统为之赋予一个初始热度值,该新闻就进入了推荐列表进行排序;随着新闻不断被用户点击阅读,收藏,分享等,这些用户行为被视作帮助新闻提升热度,系统需要为每一种新闻赋予热度值;同时,新闻是有较强时效性的内容,因此新闻发布之后,热度必须随着新闻变得陈旧而衰减。

新闻的热度就在这些算法的综合作用下不断变化,推荐列表的排序也就不断变化。

2.2 初始热度不应该一致

上面的算法为每一条入库的新闻赋予了同样的热度值,但在现实使用后发现行不通,例如娱乐类别比文化类别受欢迎程度本身就高很多;或者突发了严重的灾害或事故;或是奥运会期间,体育类别的关注度突然高了起来;而此时如果还是每条新闻给同样的热度就不能贴合实际了。

解决办法就是把初始热度设置为变量:

(1)按照新闻类别给予新闻不同的初始热度,让用户关注度高的类别获得更高的初始热度分,从而获得更多的曝光,例如:

(2)对于重大事件的报道,如何让它入库时就有更高的热度,我们采用的是热词匹配的方式。

即对大型新闻站点的头条,Twitter热点,竞品的头条做监控和扒取,并将这批新闻的关键词维护到热词库并保持更新;每条新闻入库的时候,让新闻的关键词去匹配热词库,匹配度越高,就有越高的初始热度分。

这样处理后,重大事件发生时,Twitter和门户网站的争相报道会导致热词集中化,所有匹配到这些热词的新闻,即报道同样事件的新闻,会获得很高的初始热度分。

2.3 用户行为分规则不是固定不变的

解决了新闻入库的初始分之后,接下来是新闻热度分的变化。先要明确用户的的哪些行为会提高新闻的热度值,然后对这些行为赋予一定的得分规则。例如对于单条新闻,用户可以点击阅读(click),收藏(favor),分享(share),评论(comment)这四种行为,我们为不同的行为赋予分数,就能得到新闻的实时用户行为分为:

S(Users) = 1*click + 5*favor + 10*comment + 20*share

这里对不同行为赋予的分数为1,5,10,20,但这个值不能是一成不变的;当用户规模小的时候,各项事件都小,此时需要提高每个事件的行为分来提升用户行为的影响力;当用户规模变大时,行为分也应该慢慢降低,因此做内容运营时,应该对行为分不断调整。

当然也有偷懒的办法,那就是把用户规模考虑进去,算固定用户数的行为分,即:

S(Users) = (1*click + 5*favor + 10*comment + 20*share)/DAU * N(固定数)

这样就保证了在不同用户规模下,用户行为产生的行为分基本稳定。

2.4 热度随时间的衰减不是线性的

由于新闻的强时效性,已经发布的新闻的热度值必须随着时间流逝而衰减,并且趋势应该是衰减越来越快,直至趋近于零热度。换句话说,如果一条新闻要一直处于很靠前的位置,随着时间的推移它必须要有越来越多的用户来维持。

我们要求推荐给用户的新闻必须是24h以内,所以理论上讲,衰减算法必须保证在24h后新闻的热度一定会衰减到很低,如果是线性衰减,当某些新闻突然有大量用户阅读,获得很高的热度分时,可能会持续排名靠前很久,让用户觉得内容更新过慢。

参考牛顿冷却定律,时间衰减因子应该是一个类似于指数函数:

T(Time) = e ^ (k*(T1 – T0)) 

其中T0是新闻发布时间,T1是当前时间。

而由于热度的发展最终是一个无限趋近于零热度的结果,最终的新闻的热度算法也调整为:

Score = ( S0(Type) + S(Users) ) / T(Time)

2.5 其他影响因素

很多新闻产品会给用户“赞”,“踩”或“不在推荐此类”的选项,这些功能不仅适用于个性化推荐,对热度算法也有一定的作用。

新闻的推送会造成大量的打开,在计算热度的时候需要排除掉相关的影响。类似于这样的因素,都会对热度算法产生影响,因此热度算法上线后,依然需要不断地“调教”。建议把所有的调整指标做成可配项,例如初始热度分,行为事件分,衰减因子等,从而让产品和运营能实时调整和验证效果,达到最佳状态。

3. 基于内容的推荐算法

现在,你的内容产品顺利度过了早期阶段,拥有了几万甚至十几万级别的日活。这时候,你发现热度算法导致用户的阅读内容过于集中,而个性化和长尾化的内容却鲜有人看,看来是时候开展个性化推荐,让用户不仅能读到大家都喜欢的内容,也能读到只有自己感兴趣的内容。

个性化推荐一般有两种通用的解决方案,一是基于内容的相关推荐,二是基于用户的协同过滤。由于基于用户的协同过滤对用户规模有较高要求,因此更多使用基于内容的相关推荐来切入。

这里引入一个概念叫“新闻特征向量”来标识新闻的属性,以及用来对比新闻之间的相似度。我们把新闻看作是所有关键词(标签)的合集,理论上,如果两个新闻的关键词越类似,那两个新闻是相关内容的可能性更高。 新闻特征向量是由新闻包含的所有关键词决定的。得到新闻特征向量的第一步,是要对新闻内容进行到关键词级别的拆分。

3.1 分词

分词需要有两个库,即正常的词库和停用词库。正常词库类似于一本词典,是把内容拆解为词语的标准;停用词库则是在分词过程中需要首先弃掉的内容。

停用词主要是没有实际含义的,例如“The”,“That”,“are”之类的助词;表达两个词直接关系的,例如“behind”,“under”之类的介词,以及很多常用的高频但没有偏向性的动词,例如“think”“give”之类。显而易见,这些词语对于分词没有任何作用,因此在分词前,先把这些内容剔除。

剩下对的内容则使用标准词库进行拆词,拆词方法包含正向匹配拆分,逆向匹配拆分,最少切分等常用算法,这里不做展开。

因为网络世界热词频出, 标准词库和停用词库也需要不断更新和维护,例如“蓝瘦香菇”,“套路满满”之类的词语,可能对最终的效果会产生影响,如果不及时更新到词库里,算法就会“一脸懵逼”了。

因此,推荐在网上查找或购买那些能随时更新的词库,各种语种都有。

3.2 关键词指标

前面已经说过,新闻特征向量是该新闻的关键词合集,那关键词的重合度就是非常重要的衡量指标了。

那么问题来了,如果两条新闻的关键词重合度达到80%,是否说明两条新闻有80%的相关性呢?

其实不是,举个例子:

(1)一条“广州摩拜单车投放量激增”的新闻,主要讲摩拜单车的投放情况,这篇新闻里“摩拜单车”是一个非常高频的词汇,新闻在结尾有一句“最近广州天气不错,大家可以骑单车出去散心”。因此“广州天气”这个关键词也被收录进了特征向量。

(2)另外一条新闻“广州回南天即将结束,天气持续好转”,这篇新闻结尾有一句“天气好转,大家可以骑个摩拜单车出门溜溜啦”,新闻里面“广州天气”是非常高频的词汇,“摩拜单车”尽管被收录,但只出现了一次。

这两个新闻的关键词虽然类似,讲的却是完全不同的内容,相关性很弱。如果只是看关键词重合度,出现错误判断的可能性就很高;所以特征向量还需要有第二个关键词的指标,叫新闻内频率,称之为TF(Term Frequency),衡量每个关键词在新闻里面是否高频。

那么问题来了,如果两条新闻的关键词重合度高,新闻中关键词的频率也相差无几,是否说明相关性很强呢?

理论上是的,但又存在另外一种情况:如果我们新闻库里所有的新闻都是讲广州的,广州天气,广州交通,广州经济,广州体育等,他们都是讲广州相关的情况,关键词都包含广州,天河,越秀,海珠(广州各区)等,并且有着类似的频率,因此算法很容易将它们判断为强相关新闻;从地域角度讲,这种相关性确实很强,但从内容类别层面,其实没有太多相关性,如果我是一个体育迷,你给我推荐天气,交通之类的内容,就没多大意义了。

因此引入第三个关键词的指标,即关键词在在所有文档中出现的频率的相反值,称之为IDF(Inverse Document Frequency)。为什么会是相反值?因为一个关键词在某条新闻出现的频率最大,在所有文档中出现的频率越小,该关键词对这条新闻的特征标识作用越大。

这样每个关键词对新闻的作用就能被衡量出来即TFIDF=TF * IDF,这也就是著名的TF-IDF模型。

3.3 相关性算法

做完分词和关键词指标后,每一篇新闻的特征就能用关键词的集合来标识了:

其中word0,1,2……n是新闻的所有关键词,tfidf0,1,2……n则是每个关键词的tfidf值。

两个新闻的相似度就能通过重合的关键词的tfidf值来衡量了。根据之前所学的知识,几何中夹角余弦可以用来衡量两个向量的方向的差异性,因此在我们的算法中使用夹角余弦来计算新闻关键词的相似度。夹角越小,相似度越高。

有了关键词和各关键词的tfidf之后,就可以计算新闻的相似度了。假设两条新闻的特征列表如下:

可以看到两条新闻有5个重合的关键词:广州,摩拜单车,太阳,天河和市长,因此两条新闻的相关性由这5个关键词决定,计算方式如下:

得出两条新闻的相关性最终值;用同样的方法能得出一条新闻与新闻库里面所有内容的相关性。

3.4 用户特征

得到新闻特征以后,还需要得到用户特征才能对两者进行匹配和推荐,那怎么获得用户特征呢?

需要通过用户的行为来获得,用户通过阅读,点赞,评论,分享来表达自己对新闻内容的喜爱;跟热度排名类似,我们对用户的各种行为赋予一定的“喜爱分”,例如阅读1分,点赞2分,评论5分等,这样新闻特征跟用户行为结合后,就能得到用户的特征分。

而随着用户阅读的新闻数越来越多,该用户的标签也越来越多,并且越发精准。

从而当我们拿到新闻的特征后,就能与用户的关键词列表做匹配,得出新闻与用户阅读特征的匹配度,做出个性化推荐。

3.5 其他运用

除了个性化推荐,基于内容的相关性算法能精准地给出一篇新闻的相关推荐列表,对相关阅读的实现非常有意义。此外,标签系统对新闻分类的实现和提升准确性,也有重要的意义。

3.6 优缺点

基于内容的推荐算法有几个明显优点:

  1. 对用户数量没有要求,无论日活几千或是几百万,均可以采用;因此个性化推荐早期一般采用这种方式;
  2. 每个用户的特征都是由自己的行为来决定的,是独立存在的,不会有互相干扰,因此恶意刷阅读等新闻不会影响到推荐算法。

而最主要的缺点就是确定性太强了,所有推荐的内容都是由用户的阅读历史决定,所以没办法挖掘用户的潜在兴趣;也就是由于这一点,基于内容的推荐一般与其他推荐算法同时存在。

4. 基于用户的协同推荐

终于,经过团队的努力,你的产品已经有了大量活跃用户了,这时候你开始不满足于现有的算法。虽然基于内容的推荐已经很精准了,但总是少了那么一点性感。因为你所有给用户的内容都是基于他们的阅读习惯推荐的,没能给用户“不期而遇”的感觉。

于是,你就开始做基于用户的协同过滤了。

基于用户的协同过滤推荐算法,简单来讲就是依据用户A的阅读喜好,为A找到与他兴趣最接近的群体,所谓“人以群分”,然后把这个群体里其他人喜欢的,但是A没有阅读过的内容推荐给A;举例我是一个足球迷,系统找到与我类似的用户都是足球的重度阅读者,但与此同时,这些“足球群体”中有一部分人有看NBA新闻的习惯,系统就可能会给我推荐NBA内容,很可能我也对NBA也感兴趣,这样我在后台的兴趣图谱就更完善了。

4.1 用户群体划分

做基于用户的协同过滤,首先就要做用户的划分,可以从三方面着手:

(1)外部数据的借用

这里使用社交平台数据的居多,现在产品的登录体系一般都借用第三方社媒的登录体系,如国外的Facebook、Twitter,国内的微信、微博,借用第三方账户的好处多多,例如降低门槛,方便传播等,还能对个性化推荐起到重要作用。因为第三方账户都是授权获取部分用户信息的,往往包括性别,年龄,工作甚至社交关系等,这些信息对用户群划分很有意义。

此外还有其他的一些数据也能借用,例如IP地址,手机语种等。

使用这些数据,你很容易就能得到一个用户是北京的还是上海的,是大学生还是创业者,并依据这些属性做准确的大类划分。比如一篇行业投资分析出来后,“上海创业圈”这个群体80%的用户都看过,那就可以推荐给剩下的20%。

(2)产品内主动询问

常见在产品首次启动的时候,弹框询问用户是男是女,职业等,这样能对内容推荐的冷启动提供一些帮助。但总体来说,性价比偏低,只能询问两三个问题并对用户的推荐内容做非常粗略的划分,同时要避免打扰到用户;这种做法算是基于用户个性化的雏形。

(3)对比用户特征

前文已经提到过,新闻的特征加用户的阅读数据能得到用户的特征,那就可以通过用户特征的相似性来划分群体。

4.2 内容推荐实施

我们结合一个很小的实例来了解用户协同过滤的原理,包括如何计算用户之间的相似性和如何做出推荐。假设有A、B、C、D和E共5个用户,他们各自阅读了几篇新闻并做出了阅读,赞,收藏,评论,分享操作,我们对这几种行为赋予的分数分别为1分、2分、3分、4分和5分,这样用户对每条新闻都有自己的得分,其中“-”表示未阅读,得分如下:

接下来,我们需要给用户E推荐4,5,6中的哪一篇?

用户的阅读特征向量由用户所有的阅读数据决定,我们以用户E阅读过的新闻数据作为参考标准,来找到与E最相似的用户。

多维向量的距离需要通过欧几里得距离公式来计算,数值越小,向量距离约接近。

算出结果:

  • distance(E,A)=4.123 (用户A没有阅读news2,因此news2的数据不能用来计算与用户E的相似度,这里取1,3)
  • distance(E,B)=3.162
  • distance(E,C)=3.742
  • distance(E,D)=1.414

因此得出结果:用户D是与用户E阅读喜好最接近的那个,应该优先归为同一类用户。最终结论根据用户D的阅读数据,优先推荐news4。

4.3 内容选取

我们通过阅读特征向量把用户做群体划分后,接下来就是如何获取新闻推荐的优先级。上面的例子里面只需要选出一个相似用户,并且用户A,B,C,D都只阅读news4,5,6中的一条,所以比较简单,但现实情况中,同一个用户群体阅读的新闻多且随机,用户交互更是错综复杂,如何得出推荐新闻的优先级呢?

假设用户X在系统归属于群体A,这个群体有n个用户,分别为A0,A1,A2……An,这些用户的集合用S(X,n)表示。

  1. 首先,我们需要把集合中所有用户交互过(阅读,评论等)的新闻提取出来;
  2. 需要剔除掉用户X已经看过的新闻,这些就不用再推荐了,剩下的新闻集合有m条,用N(X,m)来表示;
  3. 对余下的新闻进行评分和相似度加权的计算,计算包括两部分,一是用户X与S(X,n) 每一个用户的相似性,二是每个用户对新闻集N(X,m)中每条新闻的喜好,这样就能得到每条新闻相对于用户X的最终得分;
  4. 将N(X,m)中的新闻列表按照得分高低的顺序推荐给用户。

4.4 优缺点

相比于基于内容的推荐算法,基于用户的协同过滤同样优缺点明显。

优点主要在于对分词等算法的精确度无太大要求,推荐都是基于用户的行为数据去不断学习和完善;同时能发现用户的潜在阅读兴趣,能“制造惊喜”。

而缺点则是启动的门槛高,用户量不够时几乎无法开展;并且学习量不够时推荐结果较差。

转载:http://www.woshipm.com/pmd/723735.html

基于内容推荐算法

CollaborativeFilteringRecommendations(协同过滤,简称CF)是目前最流行的推荐方法,在研究界和工业界得到大量使用。但是,工业界真正使用的系统一般都不会只有CF推荐算法,Content-basedRecommendations(CB)基本也会是其中的一部分。

CB应该算是最早被使用的推荐方法吧,它根据用户过去喜欢的产品(本文统称为item),为用户推荐和他过去喜欢的产品相似的产品。例如,一个推荐饭店的系统可以依据某个用户之前喜欢很多的烤肉店而为他推荐烤肉店。CB最早主要是应用在信息检索系统当中,所以很多信息检索及信息过滤里的方法都能用于CB中。

CB的过程一般包括以下三步:

1.ItemRepresentation:为每个item抽取出一些特征(也就是item的content了)来表示此item;

2.ProfileLearning:利用一个用户过去喜欢(及不喜欢)的item的特征数据,来学习出此用户的喜好特征(profile);

3.RecommendationGeneration:通过比较上一步得到的用户profile与候选item的特征,为此用户推荐一组相关性最大的item。

[3]中对于上面的三个步骤给出一张很细致的流程图(第一步对应着ContentAnalyzer,第二步对应着ProfileLearner,第三步对应着FilteringComponent):

举个例子说明前面的三个步骤。对于个性化阅读来说,一个item就是一篇文章。根据上面的第一步,我们首先要从文章内容中抽取出代表它们的属性。常用的方法就是利用出现在一篇文章中词来代表这篇文章,而每个词对应的权重往往使用信息检索中的tf-idf来计算。比如对于本文来说,词“CB”、“推荐”和“喜好”的权重会比较大,而“烤肉”这个词的权重会比较低。利用这种方法,一篇抽象的文章就可以使用具体的一个向量来表示了。第二步就是根据用户过去喜欢什么文章来产生刻画此用户喜好的profile了,最简单的方法可以把用户所有喜欢的文章对应的向量的平均值作为此用户的profile。比如某个用户经常关注与推荐系统有关的文章,那么他的profile中“CB”、“CF”和“推荐”对应的权重值就会较高。在获得了一个用户的profile后,CB就可以利用所有item与此用户profile的相关度对他进行推荐文章了。一个常用的相关度计算方法是cosine。最终把候选item里与此用户最相关(cosine值最大)的N个item作为推荐返回给此用户。

接下来我们详细介绍下上面的三个步骤。

一.ItemRepresentation

真实应用中的item往往都会有一些可以描述它的属性。这些属性通常可以分为两种:结构化的(structured)属性与非结构化的(unstructured)属性。所谓结构化的属性就是这个属性的意义比较明确,其取值限定在某个范围;而非结构化的属性往往其意义不太明确,取值也没什么限制,不好直接使用。比如在交友网站上,item就是人,一个item会有结构化属性如身高、学历、籍贯等,也会有非结构化属性(如item自己写的交友宣言,博客内容等等)。对于结构化数据,我们自然可以拿来就用;但对于非结构化数据(如文章),我们往往要先把它转化为结构化数据后才能在模型里加以使用。真实场景中碰到最多的非结构化数据可能就是文章了(如个性化阅读中)。下面我们就详细介绍下如何把非结构化的一篇文章结构化。

如何代表一篇文章在信息检索中已经被研究了很多年了,下面介绍的表示技术其来源也是信息检索,其名称为向量空间模型(VectorSpaceModel,简称VSM)。

记我们要表示的所有文章集合为,而所有文章中出现的词(对于中文文章,首先得对所有文章进行分词)的集合(也称为词典)为。也就是说,我们有N篇要处理的文章,而这些文章里包含了n个不同的词。我们最终要使用一个向量来表示一篇文章,比如第j篇文章被表示为,其中表示第1个词在文章j中的权重,值越大表示越重要;中其他向量的解释类似。所以,为了表示第j篇文章,现在关键的就是如何计算各分量的值了。例如,我们可以选取为1,如果词出现在第j篇文章中;选取为0,如果未出现在第j篇文章中。我们也可以选取为词出现在第j篇文章中的次数(frequency)。但是用的最多的计算方法还是信息检索中常用的词频-逆文档频率(termfrequency–inversedocumentfrequency,简称tf-idf)。第j篇文章中与词典里第k个词对应的tf-idf为:

其中是第k个词在文章j中出现的次数,而是所有文章中包括第k个词的文章数量。

最终第k个词在文章j中的权重由下面的公式获得:

做归一化的好处是不同文章之间的表示向量被归一到一个量级上,便于下面步骤的操作。

二.ProfileLearning

假设用户u已经对一些item给出了他的喜好判断,喜欢其中的一部分item,不喜欢其中的另一部分。那么,这一步要做的就是通过用户u过去的这些喜好判断,为他产生一个模型。有了这个模型,我们就可以根据此模型来判断用户u是否会喜欢一个新的item。所以,我们要解决的是一个典型的有监督分类问题,理论上机器学习里的分类算法都可以照搬进这里。

下面我们简单介绍下CB里常用的一些学习算法:

1.最近邻方法(k-NearestNeighbor,简称kNN)

对于一个新的item,最近邻方法首先找用户u已经评判过并与此新item最相似的k个item,然后依据用户u对这k个item的喜好程度来判断其对此新item的喜好程度。这种做法和CF中的item-basedkNN很相似,差别在于这里的item相似度是根据item的属性向量计算得到,而CF中是根据所有用户对item的评分计算得到。

对于这个方法,比较关键的可能就是如何通过item的属性向量计算item之间的两两相似度。[2]中建议对于结构化数据,相似度计算使用欧几里得距离;而如果使用向量空间模型(VSM)来表示item的话,则相似度计算可以使用cosine。

2.Rocchio算法

Rocchio算法是信息检索中处理相关反馈(RelevanceFeedback)的一个著名算法。比如你在搜索引擎里搜“苹果”,当你最开始搜这个词时,搜索引擎不知道你到底是要能吃的水果,还是要不能吃的苹果,所以它往往会尽量呈现给你各种结果。当你看到这些结果后,你会点一些你觉得相关的结果(这就是所谓的相关反馈了)。然后如果你翻页查看第二页的结果时,搜索引擎可以通过你刚才给的相关反馈,修改你的查询向量取值,重新计算网页得分,把跟你刚才点击的结果相似的结果排前面。比如你最开始搜索“苹果”时,对应的查询向量是{“苹果”:1}。而当你点击了一些与Mac、iPhone相关的结果后,搜索引擎会把你的查询向量修改为{“苹果”:1,“Mac”:0.8,“iPhone”:0.7},通过这个新的查询向量,搜索引擎就能比较明确地知道你要找的是不能吃的苹果了。Rocchio算法的作用就是用来修改你的查询向量的:{“苹果”:1}–>{“苹果”:1,“Mac”:0.8,“iPhone”:0.7}。

在CB里,我们可以类似地使用Rocchio算法来获得用户u的profile

其中表示itemj的属性,分别表示已知的用户u喜欢与不喜欢的item集合;而为正负反馈的权重,它们的值由系统给定。

在获得后,对于某个给定的itemj,我们可以使用的相似度来代表用户u对j的喜好度。

Rocchio算法的一个好处是可以根据用户的反馈实时更新,其更新代价很小。

正如在本节开头所说,本节要解决的是一个典型的有监督分类问题。所以各种有效的分类机器学习算法都可以用到这里,下面列举几个常用的分类算法:

3.决策树算法(DecisionTree,简称DT)

当item的属性较少而且是结构化属性时,决策树一般会是个好的选择。这种情况下决策树可以产生简单直观、容易让人理解的结果。而且我们可以把决策树的决策过程展示给用户u,告诉他为什么这些item会被推荐。但是如果item的属性较多,且都来源于非结构化数据(如item是文章),那么决策树的效果可能并不会很好。

4.线性分类算法(LinearClassifer,简称LC)

对于我们这里的二类问题,线性分类器(LC)尝试在高维空间找一个平面,使得这个平面尽量分开两类点。也就是说,一类点尽可能在平面的某一边,而另一类点尽可能在平面的另一边。

仍以学习用户u的分类模型为例。表示itemj的属性向量,那么LC尝试在空间中找平面,使得此平面尽量分开用户u喜欢与不喜欢的item。其中的就是我们要学习的参数了。最常用的学习的方法就是梯度下降法了,其更新过程如下:

其中的上角标t表示第t次迭代,表示用户u对itemj的打分(例如喜欢则值为1,不喜欢则值为-1)。为学习率,它控制每步迭代变化多大,由系统给定。

和Rocchio算法一样,上面更新公式的好处就是它可以以很小的代价进行实时更新,实时调整用户u对应的

说到这里,很多童鞋可能会想起一些著名的线性分类器:LogisticRegression和LinearSVM等等,它们当然能胜任我们这里的分类任务。[2]中提到LinearSVM用在文本分类上能获得相当不错的效果:)。

如果item属性[5]的每个分量都是0/1取值的话(如item为文章,[5]的第k个分量为1表示词典中第k个词在itemj中,为0表示第k个词不在itemj中),那么还有一种很有意思的启发式更新的算法:Winnow算法。[4]中就是使用Winnow算法来获得userprofile的。

5.朴素贝叶斯算法(NaiveBayes,简称NB)

NB算法就像它的简称一样,牛逼!NB经常被用来做文本分类,它假设在给定一篇文章的类别后,其中各个词出现的概率相互独立。它的假设虽然很不靠谱,但是它的结果往往惊人地好。再加上NB的代码实现比较简单,所以它往往是很多分类问题里最先被尝试的算法。我们现在的profilelearning问题中包括两个类别:用户u喜欢的item,以及他不喜欢的item。在给定一个item的类别后,其各个属性的取值概率互相独立。我们可以利用用户u的历史喜好数据训练NB,之后再用训练好的NB对给定的item做分类。NB的介绍很多,这里就不再啰嗦了,有不清楚的童鞋可以参考NBWiki,或者[1-3]。

三.RecommendationGeneration

如果上一步ProfileLearning中使用的是分类模型(如DT、LC和NB),那么我们只要把模型预测的用户最可能感兴趣的n个item作为推荐返回给用户即可。而如果ProfileLearning中使用的直接学习用户属性的方法(如Rocchio算法),那么我们只要把与用户属性最相关的n个item作为推荐返回给用户即可。其中的用户属性与item属性的相关性可以使用如cosine等相似度度量获得。

下面说说CB的优缺点。

CB的优点:

1.用户之间的独立性(UserIndependence):既然每个用户的profile都是依据他本身对item的喜好获得的,自然就与他人的行为无关。而CF刚好相反,CF需要利用很多其他人的数据。CB的这种用户独立性带来的一个显著好处是别人不管对item如何作弊(比如利用多个账号把某个产品的排名刷上去)都不会影响到自己。

2.好的可解释性(Transparency):如果需要向用户解释为什么推荐了这些产品给他,你只要告诉他这些产品有某某属性,这些属性跟你的品味很匹配等等。

3.新的item可以立刻得到推荐(NewItemProblem):只要一个新item加进item库,它就马上可以被推荐,被推荐的机会和老的item是一致的。而CF对于新item就很无奈,只有当此新item被某些用户喜欢过(或打过分),它才可能被推荐给其他用户。所以,如果一个纯CF的推荐系统,新加进来的item就永远不会被推荐:(。

CB的缺点:

1.item的特征抽取一般很难(LimitedContentAnalysis):如果系统中的item是文档(如个性化阅读中),那么我们现在可以比较容易地使用信息检索里的方法来“比较精确地”抽取出item的特征。但很多情况下我们很难从item中抽取出准确刻画item的特征,比如电影推荐中item是电影,社会化网络推荐中item是人,这些item属性都不好抽。其实,几乎在所有实际情况中我们抽取的item特征都仅能代表item的一些方面,不可能代表item的所有方面。这样带来的一个问题就是可能从两个item抽取出来的特征完全相同,这种情况下CB就完全无法区分这两个item了。比如如果只能从电影里抽取出演员、导演,那么两部有相同演员和导演的电影对于CB来说就完全不可区分了。

2.无法挖掘出用户的潜在兴趣(Over-specialization):既然CB的推荐只依赖于用户过去对某些item的喜好,它产生的推荐也都会和用户过去喜欢的item相似。如果一个人以前只看与推荐有关的文章,那CB只会给他推荐更多与推荐相关的文章,它不会知道用户可能还喜欢数码。

3.无法为新用户产生推荐(NewUserProblem):新用户没有喜好历史,自然无法获得他的profile,所以也就无法为他产生推荐了。当然,这个问题CF也有。

CB应该算是第一代的个性化应用中最流行的推荐算法了。但由于它本身具有某些很难解决的缺点(如上面介绍的第1点),再加上在大多数情况下其精度都不是最好的,目前大部分的推荐系统都是以其他算法为主(如CF),而辅以CB以解决主算法在某些情况下的不精确性(如解决新item问题)。但CB的作用是不可否认的,只要具体应用中有可用的属性,那么基本都能在系统里看到CB的影子。组合CB和其他推荐算法的方法很多(我很久以后会写一篇博文详细介绍之),最常用的可能是用CB来过滤其他算法的候选集,把一些不太合适的候选(比如不要给小孩推荐偏成人的书籍)去掉。

[References]           [1]GediminasAdomaviciusandAlexanderTuzhilin,TowardstheNextGenerationofRecommenderSystems:ASurveyoftheState-of-the-ArtandPossibleExtensions

[2]MichaelJ.PazzaniandDanielBillsus,Content-BasedRecommendationSystems,2007

[3]PasqualeLops,MarcodeGemmisandGiovanniSemeraro,Chapter3inRecommenderSystemsHandbook,2011

推荐算法简单介绍

1.基于内容推荐

基于内容推荐是信息过滤技术的延续与发展,它是建立在项目的内容信息上作出推断的,而不需要依据用户对项目的评价意见,更多的需要用机器学习的方法从关于内容的特征描述的事件中得到用户的兴趣资料。用户的资料模型取决于所用学习方法,常用的有决策树,神经网络和基于向量的表示方法等。基于内容的用户资料是需要有用户的历史数据,用户资料模型可能随着用户偏好的改变而改变。

基于内容推荐方法的优点:

(1)不需要其他用户的数据,没有冷开始问题和稀疏问题

(2)能为具有特殊兴趣爱好的用户进行推荐

(3)能推荐新的或者不是很流行的项目,没有新项目问题

(4)通过列出推荐项目的内容特征,可以解释为什么推荐那些项目

(5)已经有比较好的技术,如关于分类学习方面的技术已相当成熟

缺点是要求内容能容易抽取成有意义的特征,要求特征内容有良好的机构性,并且用户的口味必须能用内容特征形式来表达,不能显式的得到其他用户的判断情况。

2.协同过滤推荐

协同过滤推荐技术是推荐系统中应用最早和最为成功的技术之一,它一般采用最邻近技术,利用用户的历史爱好信息计算用户之间的距离。然后利用目标用户的最邻近用户对商品的评价的加权评价值来预测目标用户对特定商品的喜好程度,系统从而根据这一喜好程度来对目标用户进行推荐。

协同过滤最大的优点是对推荐对象没有特殊的要求,能处理非结构化的复杂对象,如音乐,电影。基于协同过滤的推荐系统可以说是从用户的角度来进行相应推荐的,而且是自动的,不需要用户努力的找到适合自己兴趣的推荐信息,如调查问卷等。

和基于内容的过滤方法对比,协同过滤具有如下的优点:

(1)能够过滤难以进行机器自动内容分析的信息,如艺术品,音乐等

(2)共享他人的经验,避免了内容分析的不完全和不精确

(3)有推荐新信息的能力,可以发现内容上完全不相似的信息,用户对推荐信息的内容事先是预料不到的,这也是协同过滤基于内容过滤一个较大的差别,可以发现用户潜在的但自己尚未发现的兴趣爱好。

(4)能够有效的使用其他相似用户的反馈信息,减少用户的反馈量,加快个性化学习的速度。

3.基于关联规则推荐

基于关联规则的推荐是以关联规则为基础,把已购商品作为规则头,规则体为推荐对象。关联规则挖掘可以发现不同商品在销售过程中的相关性,在零售业中已经得到了成功的应用。管理规则就是在一个交易数据库中统计购买了商品集X的交易中有多大比例的交易同时购买了商品集Y,其直观的意义就是用户在购买某些商品时有多大的倾向去购买另外一些商品。

算法的第一步关联规则的发现最为关键且耗时,是算法的瓶颈,但可以离线进行。

4.基于效用推荐

基于效用推荐是建立在对用户使用项目的效用情况上计算的,其核心问题是怎么样为每一个用户去建立一个效用函数。因此,用户资料模型很大程度上是由系统所采用的效用函数决定的。基于效用推荐的好处是它能把非产品的属性考虑进去,如供应商的可靠性和产品的可得性等考虑到效用计算中。

5.基于知识推荐

基于知识推荐在某种程度上可以看成一种推理技术,它不是建立在用户需要和偏好的基础上推荐的。基于知识的方法因它们所用的功能知识不同而有明显的区别。效用知识是一种关于一个项目如何满足某一特定用户的知识,因此能解释需要和推荐的关系。所以用户资料可以是任何支持推理的知识结构,它可以是用户已经规范化的查询,也可以是一个更详细的用户需要的表示。

6.组合推荐

由于各种推荐方法都有优缺点,所以在实际中,组合推荐经常被采用。研究应用最多的是内容推荐和协同过滤推荐的组合。最简单的做法就是分别用于基于内容的方法和协同过滤的推荐方法去产生一个预测结果,然后用某方法组合其结果。尽管从理论上有很多种推荐组合方法,但在某一具体问题中并不见得都有效,组合推荐的一个重要原则就是通过组合后要能避免或弥补各自推荐技术的弱点。

在组合上,有研究人员提出了七种组合思路

1)加权:加权多种推荐技术的结果

2)变换:根据问题背景和实际情况或要求决定变换采用不同的推荐技术

3)混合:同时采用多种推荐技术给出多种推荐结果为用户提供参考

4)特征组合:组合来自不同推荐数据源的特征被另一种推荐算法所采用

5)层叠:先用一种推荐技术产生一种粗糙的推荐结果,第二种推荐技术在这个结果上产生更精确的推荐结果

6)特征扩充:一种技术产生附加的特征信息嵌入到另一种推荐技术的特征输入中,感觉有点像特征组合

7)元级别:用一种推荐方法产生的模型作为另一种推荐方法的输入

FM算法(Factorization Machine)

因子分解机(Factorization Machine, FM)是由Steffen Rendle提出的一种基于矩阵分解的机器学习算法。目前,被广泛的应用于广告预估模型中,相比LR而言,效果强了不少。

一、FM背景

FM(Factorization Machine)主要目标是:解决数据稀疏的情况下,特征怎样组合的问题。以一个广告分类的问题为例,根据用户画像、广告位以及一些其他的特征,来预测用户是否会点击广告(二分类问题)。数据如下:

Clicked?是分类值,表明用户是否点击了此广告。1表示点击,0表示未点击。而Country,Day,Ad_type则是Categorical特征(类别特征),一般都是进行one-hot编码处理。

将上面的离散特征数据进行one-hot编码以后(假设Country,Day,Ad_type类别只有图中几种),如下图所示

显然可以看出,特征从最初的3个变成了现在的7个。而实际工程当中,由于有的Categorical特征维度会非常大(比如地区等),如果采用One-Hot编码,那么互联网公司的动辄上亿个特征的数据集就是这么来的了。

因式分解机是一种基于LR模型的高效的学习特征间相互关系,
对于因子分解机FM来说,最大的特点是对于稀疏的数据具有很好的学习能力。

二、FM优点

  • ① FMs allow parameter estimation under very sparse data where SVMs fails.(FM模型可以在非常稀疏的数据中进行合理的参数估计,而SVM做不到这点)
  • ② **FMs have linear complexity,**can be optimized in the primal and do not rely on support vectors like SVMs.
    在FM模型的复杂度是线性的,优化效果很好,而且不需要像SVM一样依赖于支持向量。)
  • ③ FMs are a general predictor that can work with any real valued feature vector. In contrast to this, other state-of-the-art factorization models work only on very restricted input data.
    FM是一个通用模型,它可以用于任何特征为实值的情况。而其他的因式分解模型只能用于一些输入数据比较固定的情况。)

三、FM模型

在一般的线性模型中,是各个特征独立考虑的,没有考虑到特征与特征之间的相互关系。但实际上,大量的特征之间是有关联的。最简单的以电商为例,一般女性用户看化妆品服装之类的广告比较多,而男性更青睐各种球类装备。那很明显,女性这个特征与化妆品类服装类商品有很大的关联性,男性这个特征与球类装备的关联性更为密切。如果我们能将这些有关联的特征找出来,显然是很有意义的。

一般的线性模型为(nn为特征维度):

y=ω0+i=1nωixiy=ω0+∑i=1nωixi

对于度为2的因子分解机(FM)的模型为:

y=ω0+i=1nωixi+i=1n1j=i+1n<vi,vj>xixjy=ω0+∑i=1nωixi+∑i=1n−1∑j=i+1n<vi,vj>xixj

其中,vRn,kv∈Rn,k<vi,vj><vi,vj>表示的是两个大小为kk的向量之间的点积

<vi,vj>=f=1kvi,fvj,f<vi,vj>=∑f=1kvi,f·vj,f

与线性模型相比,FM的模型就多了后面特征组合的部分。

四、FM求解

在基本线性回归模型的基础上引入交叉项,如下:

y=ω0+i=1nωixi+i=1n1j=i+1nωijxixjy=ω0+∑i=1nωixi+∑i=1n−1∑j=i+1nωijxixj

组合部分的特征相关参数共有n(n1)2n(n−1)2个。但是在数据很稀疏的情况下,满足xixi,xjxj都不为0的情况非常少,这样将导致ωijωij无法通过训练得出,无法对相应的参数进行估计。

这里,采用的方法是:对每一个特征分量xixi引入辅助向量vi=(vi1,vi2,...,vik)vi=(vi1,vi2,…,vik)。然后,利用vivTjvivjT对交叉项的系数ωijωij进行估计

ω^ij=vivTjω^ij=vivjT




这就对应了一种矩阵的分解。对kk值的限定,对FM的表达能力有一定的影响,下图为论文中说明的kk值选取原则。

这里写图片描述

下面,求<vi,vj><vi,vj>,这块的求解用到了
((a+b+c)2a2b2c2)/2((a+b+c)2−a2−b2−c2)/2求出交叉项。过程如下: