推荐系统中的相似度度量

Cosine

最常使用的相似度计算方法,而且总体效果较好,可以说是简单实用。数学描述如下:

cosine_define

其中 是X的模。

例如,在推荐引擎中,使用 r_ui表示User u对Item i的打分,则可以使用u对各Item打的分数的向量作为User u的兴趣爱好,则User u和User v之间的cosine相似度计算方式为:

cosine_define1

其中 I_ui 表示User u,v均投票了的item。

Cosine的几何意义为向量空间中,将待计算相似度的向量均归一化为长度为1的向量, 所有被归一化后的向量  ov的v点坐标均落在以向量0为球心,半径为1的球面上,使用二向量的夹角度量二者相似度,夹角越小,相似程度越高。

在文本处理过程中,cosine度量方式表现效果都会比较好。

Mahout中参见CosineDistanceMeasure.java

Pearson Correlation

用于度量线性关系最常用的方法, 定义 为协方差,σ为标准差, 则Pearson相关系数为:

Pearson_num

例如,使用 表示User u对Item的打分,则User u,v之间的相似度计算方式为:

Pearson_num_2

其中 表示User u,v均投票了的item,与COS的区别是考虑了投票的均值, 且分母考虑的是User u,v共同投票的Item。

很多时候,针对User的PC要比针对Item的PC效果较好,因为针对User的PC相当于对各个用户的投票Scales做了一个中心化,避免各用户对相同Item投票时,因为投票习惯不一样而导致的差异。例如:投票分值分[1,5]档,有些人投4表示非常喜欢, 而有些人会投5表述相同的喜好程度。

PC的缺点如下:

  1. 如任意User仅投票了一个元素, 则无法使用该公式计算。
  2. 如任意User的每个投票分值均一样, 则无法使用该公式计算。
  3. 计算时没有考虑投票的总数量, 例如User u投票了200 Items,而v仅投票了2Items,则最后有可能还是v与待比较User近似。

另外PC也经常用作序列趋势的相近程度度量。在检索,推荐系统中经常需要考虑检索结果及推荐商品的季节因素,例如根据往年某一商品的季节特征,预测类似产品的接下来的流行程度。 下图分别为检索词‘吴莫愁’,‘梁博’,‘滑雪’在过去3个月的搜索PV,使用PC度量,很容易得到检索词‘吴莫愁’与‘梁博’的相似度远远大于‘梁博’与‘滑雪’的相似度。

tread_liangbo_wumochou

Mahout中参见PearsonCorrleationSimilarity.java

Spearman Rank Correlation(SRC)

Spearman Rank Correlation和Pearson Correlation非常类似, 只是SRC没有考虑对User对某具体Item的投票,而是考虑Item 在User所有投票中的相对Ranking。其数学表示为:

SRC

其中 k_ui表示User u对Item的投票值在User u所有投票中的Ranking。

SRC的优点是能够避免每个用户因投票习惯不一致带来的误差, 缺点是计算开销较大(每次计算都需要进行排序)

Mahout中参见SpearmanCorreleationSimilarity.java。计算复杂度较高。

Simple Matching Coefficient

imple Matching Coefficient

仅考虑数据为二值的情况(0,1)。 如果数据非二值, 则将数据转化为为二值。定义M01为u中属性为0,但v中属性为1的数量,M00表示u,v中属性均为0的数量,M10,M11同理。则SMC定义如下:

SMC

例如u=[1,1,0,0],v=[0,1,1,0],则SMC=2/4=0.5

Jaccard Coefficient

与SMC计算方式类似,但具体运算公式如下:

JC

即仅考虑两个向量中,同一维度上值均为1的数量。该相似度度量公式在文本匹配中也较为常用, 比如在计算两个短字串的相似度时,首先将字符串切词,找到更细粒度的切词结果term,之后以不同的term作为不同维度的属性,使用JC计算相似度。

Extented Jaccard(Tanimoto)

extend_JC

 

距离度量方式

该度量方式是最直观的度量方式,一般使用曼哈顿,欧几里得距离度量,而更为广义的是闵科夫斯基度量方式。以Euclidean Distance为例:

欧几里得距离计算公式

可简单转化为相似度则表示为:

欧氏距离转相似度

在Mahout中参见以下实现:

EuclideanDistanceMeasure.java

ManhattanDistanceMeasure.java

ManhalanobisDistanceMeasure.java

其他内容

为了提高运算速度, Mahout中实现了CachingUserSimilarity.java来缓存两User/Item的相似度计算结果。

也可关注我的微博:  weibo.com/dustinsea

或直接访问 semocean.com

关键词推荐系统架构

在百度做关键词推荐系统3年多, 以前更多是从工程, 以及解决用户需求的角度去考虑系统的实现。 大概一年前开始系统地学习业界推荐系统相关的内容并对照自己手头的工作。 当时就画了以下系统结构图, 算是对百度关键词系统(KR: Keyword Recommendation)中主动推荐(主动push结果给客户)的一个总结。
系统逻辑图如下:
当中包含以下几个重要步骤:
  1. 离线的数据挖掘: 根据广告库,客户landingpage内容, 网名检索query等数据,建立关键词之间的关系。 这块能做的工作非常多,包括建立关键词之间的商业价值关系,等同相关性等。很多任务都是offline的, 在hadoop/spark上进行挖掘。
  2. 关键词候选集索引建立:当这些关系建立后,就将这些关系数据建立索引加入线上系统,而且经常会提前做结构化的预处理以提升线上处理效率。
  3. user profile建立:根据用户提词反馈, 包括显式的反馈,包括对关键词的正/负向评估以及隐式反馈(通过KR,或者通过其他途径提交了关键词),以及用户的注册信息,Landingpage等构建用户user profile
  4. 结果触发:当用户访问KR时,首先根据离线挖掘的各种关系数据进行触发, 得到关系数据的大量候选。之后结合user profile进行过滤
  5. ranking: 该处的ranking较为负责, 可以分别对采用率, 的pair的效用,使用模型进行预估, 之后综合加权。 此处的效用, 可以根据具体场景的不同而做定制。
  6. 业务逻辑的ranking(Marketing Rule):相较于上边提到的纯算法策略的ranking,有时也需要根据具体产品的出口, 场景等因素, 使用规则对结果进行reranking, 以满足业务需求(此处未在上图中体现)
当然真实系统并不是上述内容就能说清的, 例如线下数据挖掘,就会用到二步图, 全关系PageRank, 关联规则等多种方式进行挖掘。 触发时也需要考虑各种同意,核心等的变换, ranking时使用机器学习方法结合业务规则综合排序。 更多细节可以参考后续推荐系统相关文章。
更多内容可关注微博:weibo.com
或是直接访问: http://semocean.com