ReservoirSampling蓄水池抽样

如果说动态规划在日常使用中出现的次数可能不是特别多,可能更加是一个面试需要加的技能点的话,我今天整理的ReservoirSampling却是真真切切的业务需求中必备的技能,之前已经拥有了一定的实践尝试,这边和大家分享一下。

场景

我司是一个车货匹配的信息平台,可以理解为货车版本的滴滴出行,货物天生比客运出行要有更加丰富的定制化场景,比如我从南京运一车梨子到上海,可能这个梨子是需要雨布去遮盖、可能需要棉被防摔等等,司机货主会在平台上利用文本进行定制化需求的描述,问题来了,有些不法分子可能会通过这个信息匹配平台进行不正当言论的交流、包括黄色反动暴力等内容。

我们team在后台设计了套召回率在95%以上的文本正常程度鉴别系统,能够保证至少95%的有问题的文本会被直接拦截,5%的文本会在拦截阈值x-0.3的以内,但是由于每日撮合信息量高达千万级别,在x-0.3以内的文本条数日高达十万级别的文本条数,问,如何保证尽可能多实时的在阈值x-0.3以内寻找到尽可能多的有问题的文本信息。

问题剖析

尽可能多

很明显,不可能全量复审,那我们我们只能通过随机采样,而稍加分析数据或者有一定的风控经验的同学都知道,这些黑名单用户的活动都是批量进行的。
其实,我们更多的均衡采点的效果不如分层采点:
均衡采点:比如把数据流看成1,以等时长、等数据流的方式进行采样,去筛选有问题的文本。
分层采点:比如把数据流看成N段1/N单独对象,1/N单独对象内以等概率的方式去采样,如果采样存在问题,则1/N单独对象内进行全覆盖复查。

实时

很明显,就日聚合度的分布可以看出,分层采样捕获的问题样本会更多,但是会有一个问题。
实际情况下,如果我们需要实时去捕获问题文本信息,如果我们是拿不到1/N中的N的,换句话说,我们不知道下一秒会有多少信息文本会被发出来,我们就做不到该段时间内的等概率抽样。

ReservoirSampling

说了这么久,终于出现了我们的主角ReservoirSampling,蓄水池抽样。
最初,我们的审核同学的人力是已知的,比如一共20个同学,每小时内可以人均审核300条,则一小时的池水量为6000条。
我们实际做的时候,把一小时切分成6段,每段10分钟,在10分钟的分段内首先先保留阈值在x-0.3以内前600条,然后后面来的每一条以N/i的概率保留,并在原来600条中随机剔除一条。其中i为数据序号,此处N为600。
当i<=N的时候,每条数据进入池子的概率都是1。
当i>N的时候,当出行第N+1个满足条件的元素时,被保留的概率是N/(1+N);被保留后,就需要计算剔除概率为N/(1+N)/N,1-N/(1+N)/N=N/(1+N)即为被保留的概率,所以池子内外被保留的概率相等。
在这种方法下,我们只需要知道,我们在单位时间内需要保留多少个目标信息本文条数即可,无需在意单位时间内可能会出现多少条总量信息样本。
然后复审同学只需要在t2时间,去审核t1时间内的产出的文本信息即可,不需要等待落表,存库,读库,采样等各种额外操作。一旦审核到任意一条文本有问题,则转交稽核同学全量审核。

LeetCode

在leetcode中也是有相关的题目的:

  • 398题随机数索引
    题目中的核心在于把N缩小成1,做了一个not randint(0,n)被采纳执行的逻辑,对于任意一次中间次数k+1,被保留的概率为1/(k+1),未被保留,依旧保留上次的结果的概率为1/k*(k/(k+1)),为1/(k+1),所以为等概率的。

  • 382题链表随机节点
    题目中的跟上面一摸一样,先保存第一个也就是not randint(0,0)必为True,对于生下来的每次以not randint(0,n)进行保留,最后进行节点输出即可。我在GitHub中实际去实现的时候采用了普通方式,建议以我398题的方式去完善即可

总结

蓄水池抽样的方式确确实实能够解决大家工作中的实际问题,实际使用中在原始的95%的召回的情况下,给力的提升了2.3pp的召回率。

ReservoirSampling蓄水池抽样就给大家整理到这,如果大家想看更多的数据结构问题,可以关注一下我的Github,希望有所帮助。

欢迎大家关注我的个人bolg知乎,更多代码内容欢迎follow我的个人Github,如果有任何算法、代码、转行疑问都欢迎通过邮箱发消息给我。

打赏的大佬可以联系我,赠送超赞的算法资料