当前位置：首页 > news >正文

[搜广推]王树森推荐系统笔记——曝光过滤 Bloom Filter

news 来源：原创 2025/5/21 0:37:46

曝光过滤 & Bloom Filter

曝光过滤主要在召回阶段做，主要方法是Bloom Filter

曝光过滤问题

-如果用户看过某个物品，则不再把该物品曝光给该用户。
- 原因是重复曝光同一个物品会损害用户体验
- 但长视频通常没有曝光过滤（youtube）

要想做曝光过滤，需要对每个用户记录已经曝光过的物品。
- 小红书只召回1个月以内的笔记，因此只需要记录每个用户最近1个月的曝光历史。
召回之后，对于每个召回的物品做曝光过滤，判断它是否已经给该用户曝光过，排除掉曾经曝光过的物品。
- 一位用户看过n个物品，本次召回r个物品，如果暴力对比，需要O(nr)的时间。
- n 和 r 的量级大约是几千，暴力对比需要的计算量太大，无法使用，因此引入Bloom Filter

Bloom Filter

Bloom Filter是一种空间效率很高的概率型数据结构，把物品集合表征为一个m维二进制向量，用于判断一个元素是否在一个集合中。
它允许一些误报（false positives），但不允许误漏（false negatives）。也就是说，如果Bloom Filter说一个元素不在集合中，那么这个元素一定不在；但如果它说一个元素在集合中，那么这个元素可能在，也可能不在。
- 如果判断为no，那么该物品一定不在集合中。
- 如果判断为yes，那么该物品很可能在集合中。（可能误伤，错误判断未曝光物品为已曝光，将其过滤掉。）

原理

初始化
- 每个用户有一个曝光物品的集合，表征为一个向量，需要m bit的存储。
- Bloom filter有k个哈希函数，每个哈希函数把物品ID映射成介于0和m−1之间的整数。
  - k和m是需要设置的参数
插入：向集合中添加元素时，使用k个哈希函数计算该元素的哈希值，并将这些哈希值对应的二进制向量位置设为1。
查询：检查元素是否在集合中时，同样使用k个哈希函数计算哈希值，并查看这些位置上的二进制向量是否都为1。
- 如果都为1，则元素很可能在集合中
- 如果任何一个位置为0，则元素一定不在集合中。

示例

以k=1和k=3为例，展示如何通过哈希函数将物品ID映射到二进制向量中，并标记为1。
在这里插入图片描述

误伤概率

曝光物品集合大小为n，二进制向量维度为m，使用k个哈希函数。

Bloom filter误伤的概率为 $exp(−\frac{kn}{m})^k$ 。
- n越大，向量中的1越多，误伤概率越大。（未曝光物品的k个位置恰好都是1的概率大。）
- m越大，向量越长，越不容易发生哈希碰撞。但是m越大，需要的存储就越多
- k太大、太小都不好，k有最优取值。

认为设定可容忍的误伤概率为δ，那么最优参数为：

$ln(\frac1δ)$
$ln(\frac1δ)$

曝光过滤的链路

召回 -> 排序 -> 实时流处理（Kafka+Flink）-> 曝光过滤服务（Bloom Filter）-> 写二进制向量
在这里插入图片描述

app记录所有曝光的物品
用实时流处理，防止用户刷新得到重复数据
- 把数据写入Kafka消息队列
- 用实时流Flink计算曝光物品的哈希值
- 结果写入bloom filter的二进制向量中
曝光过滤用在召回完成之后
- 召回服务器请求曝光过滤服务
- 曝光过滤服务把用户的二进制向量发送给召回服务器
- 召回服务器上用bloom filter计算召回物品的哈希值，再和二进制向量对比
- 过滤已经曝光的物品
曝光过滤之后，剩余的物品发给排序服务器

Bloom Filter的缺点

Bloom filter只支持添加物品，不支持删除物品。如果从集合中移除一个物品，无法消除它对向量的影响
- 不能简单的把这个物品对应的k个哈希函数从1改成0，因为可能有其他物品也对应这个哈希函数）
每天都需要从物品集合中移除年龄大于1个月的物品。但想要删除物品，要重新计算整个集合的二进制向量
- 超龄物品不可能被召回，没必要把它们记录在Bloom filter，降低n可以降低误伤率。

视频合集链接