利用Solr完成向量乘以矩阵功能:以协同过滤算法ItemCF为例

来源:转载


0. 背景

      很多应用的计算最终都转化为矩阵运算来完成,例如推荐算法中的协同过滤就可以套上去。协同过滤(collaborative filtering)是推荐系统中一类广泛使用的方法,协同过滤中两种比较出名的方法item-based CF、user-based CF。itemCF方法更简单,推荐理由也更温和,将是本文介绍的实践内容。

1. itemCF简介       

      itemCF算法用户u对物品i的喜欢程度Pui可以用如下公式计算:

                           Pui = ∑ s(i,j)·Puj  ;  j∈N(u)

    其中 s(i,j)是物品i与j的相似度,或者关联度;Puj是用户u对物品j的喜爱程度;N(u)代表用户u喜欢的东西列表;也就是一个用户会喜欢和他之前喜欢的东西类似的东西。s(i,j)有多种计算方式,例如余弦相似度,皮尔逊关系,并没有什么规定,Pui的偏好度如何定义也可以根据自己需要来定(而itemCF的特点是非常容易扩展成实时模型:Sij是物品关联关系,通常比较稳定,Pui则是用户模型,可以经常反应用户兴趣变换)。 推荐的时候,要对u的所有(除了已经看过的东西)物品进行累加计算,得到每个物品i的权重,通常排序选出最高的若干个物品进行推荐。

      本文不探讨itemCF合理性;s(i,j)的产生是itemCF关键,也是比较消耗时间的,通常都是离线计算。Puj可以根据不同情形离线或者在线获得。


2. 算法实现

       从计算的角度看,就是一个1*N的矩阵与一个N*N的矩阵相乘。用户u对自己已经看过的物品的偏好是1*N的矩阵,而s(i,j)就是个物品关联关系的矩阵。在现实中,一个网站或者有推荐需要的场景中,物品的数量往往成千上万甚至更多,关联关系通常都是稀疏的,如果保存成N*N的矩阵,将有大量的0元素占用大量空间。另外一点事用户喜好的物品也往往是其中的少数,为每个未接触的物品求喜好度计算量也不小。

       因而有必要转换一下思路降低计算消耗。我们只需要保留下非零或者强关联、强相似的物品关系,矩阵存成邻接表等形式。对用户u喜欢过的物品列表i, 逐个到邻接表中取出与i强关联的列表[j]...,然后把这些列表[j]求和合并即可。这样合并得到的权重列表[j]通常也远小于物品总数。    

       ItemCF算法的实现不复杂,但若要实现一套推荐系统则可能需要考虑现实问题,比如s(i,j)的矩阵如何存储,如何考虑架构使不同类型推荐也能套用,系统健壮性等问题。可以考虑使用redis, memcache, hazelcast等成熟的缓存系统来存储s(i,j)矩阵,服务端自己实现矩阵相乘的算法。本文将使用solr来完成向量乘以矩阵的任务,省去自己实现的麻烦与风险。


3. solr实现

       使用solr的查询来替换矩阵计算公式,那么首先就要了解一下solr的评分机制。Solr使用的是lucene的评分机制,从4.0开始lucene提供了不少用语信息检索的打分算法,当然solr默认也比较简单,是TF-IDF的变形。可以找到有关lucene评分细节的文章也比较多,比如这几篇比较好:第一篇,第二篇,第三篇 

       借用csdn的那篇文章内容,直接来看打分公式:

             score(q,d)   =   coord(q,d) ·  queryNorm(q) · ∑ ( tf(t in d) ·  idf(t)2 ·  t.getBoost() ·  norm(t,d) )

       简单说明(想详细深入可以仔细看那三篇文章):

coord(q,d) 指的是查询q命中了文档的程度,查询词命中越多,分数越高

queryNorm(q)  是对查询的一个归一化,但这函数只对q有效,因此所有文档影响都一样。

之后是针对q中每个词t进行累加

    tf(t in d) 是词t在文档密集程度,d含t越多分则越高

    idf(t) 是词t在整个文档集合的逆篇频,词t在整个文档集出现越多分数越低,比如too to这类词通常

    getBoost() 是d的加权

    norm(t,d) 压缩几个索引期间的加权和长度因子: 

1. doc boost ; 文档索引时的加权

2. field boost; 字段索引时的加权

3. lengthNorm(field) ;字段含词长度归一值,字段越短,评分越高。例如一个字段有很多词的时候,命中一个肯定不如命中一个很短的字段重要。 

         根据lucene打分公式,我们需要实现自己的similarity从而把矩阵相乘的算法套进去,还要设计文档的schema结构来存储s(i,j)矩阵。

       首先,使用lucene的query必然是要代表Puj的向量,那么让query检索文档集表达矩阵计算方式:就是获取那些匹配到query的[j]的文档[i]并打分,因此物品i关联的[j]集合不是按钱面计算那么直接,而是从另一面看:文档i表示物品i被那些[j]关联。例如前面例子讲的物品i与哪些[j]都很关联,在这里要表示成物品i被哪些[j]所关联。于是在这一篇doc的id是i, 而字段是被关联的[j]。如何存储[j],我起初想到solr支持的multivalue,但是这并不能为每个j指定权重,因此就想到用动态字段来存储,type使用基本类型即可,权重以boost方式存储,需要添加一个omitNorms=false。

 <dynamicField name="i_*" type="float" indexed="true" stored="true" omitNorms="false"/>

      其次,需要修改默认的similarity,如何实现可以参考  http://www.solr.cc/blog/?p=66 

其中tf、idf、coord返回值改成1,queryNorm不影响结果但也可以改成1。


4. 实验

     创建新索引schema中加入similarity的配置,solrconfig中指定对应jar包路径。提交数据:

{"add":{"doc":{"id":"1","i_1":{"boost":0.9,"value":1.0},"i_2":{"boost":0.3,"value":1.0},"i_3":{"boost":1.3,"value":1.0},"i_5":{"boost":0.5,"value":1.0}}}}

{"add":{"doc":{"id":"2","i_1":{"boost":1.5,"value":1.0},"i_2":{"boost":1.1,"value":1.0},"i_4":{"boost":0.5,"value":1.0},"i_5":{"boost":1.8,"value":1.0}}}}

{"add":{"doc":{"id":"3","i_1":{"boost":0.5,"value":1.0},"i_2":{"boost":2.1,"value":1.0},"i_3":{"boost":0.3,"value":1.0},"i_4":{"boost":0.8,"value":1.0}}}}

      三个物品,i_x 字段代表被某id商品关联,boost是相似度

      开启debug模式在查询中q指定:i_1:1^3 OR i_2:1^1.7 OR i_5:1^2  三篇doc的得分分别为 4.05, 9.7, 4.9。 拿出第一篇来看下计算过程:

 4.05 = (MATCH) sum of: 2.625 = (MATCH) weight(i_1:`/u000b|/u0000/u0000/u0000^3.0 in 0) [MySimilarity], result of: 2.625 = score(doc=0,freq=1.0 = termFreq=1.0 ), product of: 3.0 = queryWeight, product of: 3.0 = boost 1.0 = idf(docFreq=3, maxDocs=3) 1.0 = queryNorm 0.875 = fieldWeight in 0, product of: 1.0 = tf(freq=1.0), with freq of: 1.0 = termFreq=1.0 1.0 = idf(docFreq=3, maxDocs=3) 0.875 = fieldNorm(doc=0) 0.425 = (MATCH) weight(i_2:`/u000b|/u0000/u0000/u0000^1.7 in 0) [MySimilarity], result of: 0.425 = score(doc=0,freq=1.0 = termFreq=1.0 ), product of: 1.7 = queryWeight, product of: 1.7 = boost 1.0 = idf(docFreq=3, maxDocs=3) 1.0 = queryNorm 0.25 = fieldWeight in 0, product of: 1.0 = tf(freq=1.0), with freq of: 1.0 = termFreq=1.0 1.0 = idf(docFreq=3, maxDocs=3) 0.25 = fieldNorm(doc=0) 1.0 = (MATCH) weight(i_5:`/u000b|/u0000/u0000/u0000^2.0 in 0) [MySimilarity], result of: 1.0 = score(doc=0,freq=1.0 = termFreq=1.0 ), product of: 2.0 = queryWeight, product of: 2.0 = boost 1.0 = idf(docFreq=2, maxDocs=3) 1.0 = queryNorm 0.5 = fieldWeight in 0, product of: 1.0 = tf(freq=1.0), with freq of: 1.0 = termFreq=1.0 1.0 = idf(docFreq=2, maxDocs=3) 0.5 = fieldNorm(doc=0)

      4.05得分是q中三个小查询项之和,其中小查询项由公式中多个函数乘积而得,除去已经被我们归一的函数就只有boost和fieldNorm,而fieldNorm根据公式也只有fieldBoost一项。但是fieldNorm似乎并不等於提交的doc的fieldBoost,因为fieldNorm只有1字节,lucene将float压缩为byte精度区间只有0.125。从debug结果看,solr已经满足向量乘矩阵的算法了,但需要留意精度问题。

      如果是要对精度有很高要求,可以利用bf的方式:

       1). 权重boost要以字段b的形式存下来,

       2). 将similarity中idf改为0,让lucene的score变为0。

       3) 开启edismax模式,查询q写 i_1:1 OR i_2:1 OR i_5:1, bf写sum(product(i_1_b,3),product(i_2_b,1.7),product(i_3_b,2))。


5.总结

      到此为止,利用solr完成向量乘以矩阵就算介绍完了。对推荐业务来说是否要把coord,idf都改成1我觉得也不一定,idf表示稀有的物品更容易被推荐,也许使用默认方式更合理。本文利用solr本身提供了强大中的一小点,solr/lucene本身的功能如何应用好非常值得研究发掘,倒排索引的查询模式肯定还可以找到更多用处,就如同之前文章提到suggest和spell本身就能用倒排索引来完成。




分享给朋友:
您可能感兴趣的文章:
随机阅读: