文档

SimRank++相似度计算算法

更新时间:

本文介绍了推荐系统中一个常用的协同过滤算法SimRank,包括它的算法原理,及其应用在个性化推荐场景时的改进。同时,本文还描述了如何在生产环境部署SimRank++算法。

算法简介

SimRank算法是一种用于衡量结构上下文中个体相似度的方法,其基本思想是:如果两个对象a和b分别与另外两个对象c和d关联,且已知c与d是相似的,则a与b也是相似的;并且任意节点与其自身拥有最大的相似度值为1。SimRank算法的主要出发点是利用已有个体的相似度来推算其他与之有关联个体的相似度。

SimRank算法基于一个简单和直观的图论模型,它把对象和对象之间的关系建模为一个有向图G = (V, E),其中V是有向图的节点集合,代表应用领域中的所有对象;E是有向图的边的集合,表示对象间的关系。对于图中的一个节点image.svg,与其所有入边关联的邻节点集合(in-neighbors)记为image.svg,同时,其出边对应的邻节点集合(out-neighbors)集合记为image.svg。用image.svg表示对象image.svg和对象image.svg之间的相似性,其计算公式为:

image.svg

从该计算公式可以看出,个体image.svg, image.svg的相似度取决于所有与image.svg, image.svg相连节点的相似度。式中image.svg是一个常量衰减因子。

上述公式可以用矩阵的形式表示出来。假设S表示有向图G的SimRank分数矩阵,其中image.svg表示对象image.svgimage.svg之间的相似性分数; P表示G的连接矩阵,其中image.svg表示从顶点image.svg到顶点image.svg的边数,则

image.svg

用矩阵的符号表示,即为:

image.svg

其中,矩阵image.svg表示按列归一化的image.svg矩阵, image.svgimage.svg的单位矩阵。image.svg 的作用是把矩阵 image.svg 的主对角线元素设为1。

SimRank++算法在SimRank算法的基础上引入一个新的函数image.svg表示二部图中节点间的转移概率:

image.svg

从而,新的算法迭代公式如下:

image.svg

image.svg

其中,image.svgimage.svg表示任意两个查询,image.svgimage.svg表示任意两个广告,因子image.svgimage.svg的定义如下:

image.svg

image.svg

对SimRank算法进行上述两个方面的扩展,即通过“权值”和“证据值”对原始计算结果进行校正,所得的新算法就是SimRank++算法。

SimRank++算法由Antonellis等人于2008年专门针对赞助商广告检索领域的查询重写应用提出的。

在推荐系统中的应用

原始的SimRank++算法是在计算广告领域做Query Rewrite的,一般会用最近一段时间的累计点击行为数据来计算Query-Query、Ad-Ad之间的相关性。

由于Query所表达的查询意图短期内能够保持稳定,所以用多天的行为数据来计算相似度是合理的。

在推荐系统中,没有意图明确的Query数据,一般用User-Item的点击或其他行为二部图作为SimRank++算法的输入。

在没有Query相关性的限制下,用户在推荐场景的行为意图相对来说不是很明确,同一用户在同一时期可能会有多个兴趣,并且用户的兴趣也会随时间发生演化。

另一方面,用户的量级通常比Query的量级大很多,从百万到数十亿不等,这给SimRank++算法的实现带来了不小的挑战。

基于以上原因,我们推荐使用Session-Based的行为二部图计算item-item的相似度。因为在同一个session内用户的兴趣点比较集中,一般不会分手到多个类目的item上。在没有明确session id埋点的场景,可以使用 concat(user_id, date) 作为session_id。

增量计算

由于session id的量级非常大,为了计算的可行性,不推荐合并多天的数据作为算法输入。

由此带来的覆盖率问题,我们提出了增量计算的方案。即SimRank++算法工具包会保留多天的item-item相似度数据,计算第T天的相似度时使用T-1天的物品相似度初始化item-item相似度矩阵。工具包不会保留session与session之间的相似度数据。

最终,累加多天的物品相似度分数作为最终的i2i相似度分 image.svg

image.svg

其中,image.svg 是一个折扣因子,即过去的相似度分累加到当前时刻时需要打一个折扣,时间越久折扣越大。

注意:我们不保证多天累加的相似度分数 image.svg,如有需要请自行归一化。

改进点1:热门打压

在推荐场景很容易发生"哈利波特"效应,即因为热门item会得到更多的曝光机会,因而算法在不加干预时很可能认为热门item与很多其他item之间都存在相似关系,这样会导致"富者越富"的马太效应。为了缓解这一问题,本SimRank算法工具包引入了一个热门打压机制。

具体来说,我们首先从输入的行为二部图中汇总item对应的边的权重(求和),以便发现热门的item。然后,对Item的热度(记为 image.svg )做一个z-score变换:

image.svg

接着,再把 image.svg 转换为值域在(0, 1) 区间内的一个单调递减函数:

image.svg

最后,用 image.svg 乘上原来的边的权重作为新的权重。这就相当于在随机游走时增加了往热门item游走的阻力。

改进点2:Reweight by prefer category

推荐场景下用户的点击行为可能有噪声,比如误点的情况;为了消除噪声的干扰,我们通过计算用户对item类目的偏好来调整行为二部图的权重。

给定一个用户,其对类目 image.svg 的偏好分如下:

image.svg

Ta 对物品 image.svg 的权重从原来的 image.svg 调整为 image.svg,其中物品 image.svg 属于类目 image.svg

输入输出格式

输入表(支持分区表)包含四列:

  • user_id: 用户ID、session_id、Query等 (类型不限)

  • item_id: 物品ID(类型不限)

  • weight: double类型的权重

  • category: [可选] item的类目,设置该字段可提高精度(类型不限)

  • 输入表中不可有重复的 <user_id, item_id> 二元组,请预先合并权重

  • 当使用category数据增强算法效果时,该field为空值的记录将会被删除;注意检查category列是否存在空值

  • 注意:需要控制同一Query对应的weight的方差在一定范围内,太大会导致权重转移矩阵的元素值为0,召回率严重下降

  • 建议为weight列提前做好归一化或者标准化,比如施加 "min-max", "z-score", "log", "sigmoid"等变换,

    • 也可以配置input_weight_normalizer参数。

  • 合理设置二部图边的权重,会显著提升算法效果

  • 用ctr作为权重时容易引入噪声数据,因为ctr高的record的曝光次数(pv)可能很低

    • 可以考虑用log(1+click)作为边的权重

  • 建议做好数据清洗,过滤掉一些噪声数据

  • 给定一个Query,可以过滤掉click/sum(click) < threshold的数据;例如,threshold=3e-5

输出表格式(支持分区列):

  • item1:物品ID

  • item2:相似物品ID

  • cumulative_score:多天数据计算出的累计相似度分数(使用该字段作为最后的结果)

  • score: 当天数据计算出的相似度分数,可能为空

备注:score、cumulative_score 没有做归一化

提交任务

  1. 下载 simrank_plus_plus-1.0.jar 算法包。

  2. 作为资源上传到MaxCompute项目空间。

    image.png

  3. 在DataWorks上新建 ODPS MR 节点(ODPS SQL类型的节点可能会报错),使用如下命令提交Job。

    --@resource_reference{"simrank_plus_plus-1.0.jar"}
    jar -resources simrank_plus_plus-1.0.jar
    -classpath simrank_plus_plus-1.0.jar
    com.aliyun.pai.simrank.SimRankDriver
    -project ${max_compute_project}
    -end_point http://service.cn-hangzhou.maxcompute.aliyun.com/api
    -access_id ${access_id}
    -access_key ${access_key}
    -input_table simrank_i2i_input
    -input_table_partition ds=${bizdate}
    -output_table simrank_i2i_output
    -output_table_partition ds=${bizdate}
    -init_partition ds=${yesterday}
    -session_column device_id
    -item_column item_id
    -category_column cate_lv3_id
    -num_matmul_reducer 2000
    ;

参数说明

参数

类型

说明

默认值

access_id

string

阿里云账号access_id

access_key

string

阿里云账号access_key

end_point

string

MaxCompute的服务地址. 公有云Endpoint

project

string

default odps project

input_table

string

输入table name

input_table_partition

string

输入table的partition

init_partition

string

item相似度输出table的用于初始化的partition

无,一般使用前一天的

output_table

string

item相似度输出table

output_table_partition

string

输出table的partition

session_output_table

string

query相似度输出table

session_output_table_partition

string

query相似度输出table的partition

session_column

string

输入table表示query的列名

user_id

item_column

string

输入table表示item的列名

item_id

category_column

string

输入table表示item的类目的列名

job_name

string

任务名,中间表的前缀,设置该参数可以续跑中断的任务; 必须要保证和别人的任务不同名

自动生成一串uuid

debug

bool

是否开启调试模式

false

iter_times

int

SimRank算法的迭代次数

3

decay_factor

float

SimRank算法的衰减因子参数C, 范围:(0, 1)

0.8

discount_factor

float

相似度分数随时间衰减因子, 范围:(0, 1];仅用于增量计算

0.95

sim_threshold

float

SimRank算法迭代过程中使用的相似度过滤阈值

0.000001

weight_threshold

float

行为二部图边的权重的过滤阈值

1e-6

input_weight_normalizer

string

输入权重的归一化函数,例如LOG10(1+weight)

zero_spread_weight_cnt

int

权重转移矩阵score的零值报错阈值(零值表示input的weight方差过大)

100

default_evidence

float

SimRank++算法使用的默认证据权重,范围:(0, 0.5)

0.25

evidence_amplifier

float

证件权重的放大因子,放大后的evidence范围:[default_evidence, evidence_amplifier]

1/decay_factor

anti_popular

bool

是否开启热门物品打压,解决"哈利波特效应"

true

item_block_size

int

Item矩阵分块大小,性能相关,不建议修改(输入数据较小是不会触发矩阵分块)

50000

session_block_size

int

Query矩阵分块大小,性能相关,不建议修改(输入数据较小是不会触发矩阵分块)

50000

matmul_strategy

int

矩阵分块乘法策略,可选值:2、3、4(输入数据较小时不会触发矩阵分块)

4

matmul_reducer_memory

int

矩阵乘法Job1的Reducer内存,单位为M

触发分块:12288;不触发分块:3072

matmul_split_size

int

矩阵乘法Mapper的切片大小,单位为M

触发分块:16;不触发分块:256

num_matmul_reducer

int

矩阵乘法Job1的Reducer数量

触发分块:自动计算;不触发分块:无

num_matmul_reducer2

int

矩阵乘法Job2的Reducer数量(不触发分块时不需要Reducer2)

evidence_split_size

int

计算证据矩阵Mapper的切片大小,单位为M

16

num_evidence_reducer1

int

计算证据矩阵Job1的Reducer数量

num_evidence_reducer2

int

计算证据矩阵Job2的Reducer数量

priority

int

Job优先级

1

搜索场景,如Query Rewrite,可以把anti_popular置为false;推荐场景则置为true。

案例分析

某搜索场景,输入数据约1700万,query量级为120万,item量级为150万,使用如下参数跑通整个流程耗时约87分钟。

--@resource_reference{"simrank_plus_plus-1.0.jar"}
jar -resources simrank_plus_plus-1.0.jar
-classpath simrank_plus_plus-1.0.jar
com.aliyun.pai.simrank.SimRankDriver
-project ${project}
-end_point http://service.cn-shanghai.maxcompute.aliyun.com/api
-access_id ${access_id}
-access_key ${access_key}
-input_table ${input_table}
-input_table_partition dt=20240512
-output_table simrank_i2i_score
-output_table_partition dt=20240512
-session_output_table simrank_q2q_score
-session_output_table_partition dt=20240512
-output_table_lifecycle 7
-session_column query_word
-item_column item_id
-category_column category
-anti_popular false
-num_matmul_reducer 2000
-num_evidence_reducer1 1000
-num_evidence_reducer2 200

参考资料