SimRank++相似度计算算法

算法简介

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

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

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

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

用矩阵的符号表示，即为：

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

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

从而，新的算法迭代公式如下：

其中，和表示任意两个查询，和表示任意两个广告，因子和的定义如下：

对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相似度分 。

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

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

改进点1：热门打压

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

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

接着，再把 转换为值域在（0, 1） 区间内的一个单调递减函数：

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

改进点2：Reweight by prefer category

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

给定一个用户，其对类目 的偏好分如下：

Ta 对物品 的权重从原来的 调整为 ，其中物品 属于类目 。

输入输出格式

输入表（支持分区表）包含四列：

• 输入表中不可有重复的 <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

Item相似度（i2i）输出表格式（支持分区列）：

备注：$$score\in (0,1)$$、cumulative_score 没有做归一化

Query相似度（q2q）输出表格式（支持分区列）：

提交任务

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

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

   

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
   ;

参数说明

搜索场景，如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

参考资料

• 一文说尽协同过滤算法中的相似度计算

• SimRank++算法原理解析