V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
iblislsy
V2EX  ›  程序员

求一个可行方案:计算新用户和老用户通讯录的最高匹配度

  •  
  •   iblislsy · 2018-10-29 12:13:42 +08:00 · 4978 次点击
    这是一个创建于 2196 天前的主题,其中的信息可能已经有所发展或是发生改变。

    需求: 对于每一个新用户,希望能计算出和老用户的通讯录最高匹配度,找到类似伪造通讯录的情况。

    例子: 每一个用户的通讯录表结构如下

    user_id phone

    123 18721212111

    123 18721212112

    123 18721212113

    124 18721212111

    124 18721212112

    124 18721212115

    124 18721212116

    假设 user_id:123 是一个新用户,可以发现用户 123 和用户 124 存有相同的联系人

    用户 123 和 124 的匹配度为: 相同号码数量 /新用户的号码数量 = 2/3 = 0.67

    需要遍历找到匹配度最高的用户,或者是大于某一阈值的用户群体。

    各位大佬,这个复杂度似乎有点高,有没有可行的方案。

    51 条回复    2018-11-06 12:10:37 +08:00
    swulling
        1
    swulling  
       2018-10-29 12:17:39 +08:00
    网贷风控?
    luozic
        2
    luozic  
       2018-10-29 12:20:32 +08:00 via iPhone
    向量?
    lance6716
        3
    lance6716  
       2018-10-29 12:22:12 +08:00 via Android
    遍历找到匹配度最高的用户对?还是啥,请使用量词定义
    proudofmyself911
        4
    proudofmyself911  
       2018-10-29 12:34:11 +08:00 via Android
    老用户是伪造的怎么办。。。
    luckychenhaha
        5
    luckychenhaha  
       2018-10-29 12:35:24 +08:00
    局部敏感哈希
    Humorce
        6
    Humorce  
       2018-10-29 12:37:41 +08:00 via iPhone
    @proudofmyself911
    抓网上营业厅详单,虽然这个做法很恶心,但是你要知道这个操作是要用户“授权”的
    iblislsy
        7
    iblislsy  
    OP
       2018-10-29 12:38:04 +08:00
    @lance6716 找到这个匹配度 0.67 就可以了,能找到超过给定阈值θ(比如 0.5)的用户集群更好
    iblislsy
        8
    iblislsy  
    OP
       2018-10-29 12:38:33 +08:00
    @lance6716 这个 0.67 是用户 123 和其他所有用户匹配的最大值
    iblislsy
        9
    iblislsy  
    OP
       2018-10-29 12:39:18 +08:00
    @luckychenhaha 我补习一下
    codingadog
        10
    codingadog  
       2018-10-29 12:39:55 +08:00 via Android   ❤️ 6
    麻烦说明下是什么 app,我先去卸载了
    iblislsy
        11
    iblislsy  
    OP
       2018-10-29 12:41:04 +08:00
    @codingadog 传说中的钢筋?
    iblislsy
        12
    iblislsy  
    OP
       2018-10-29 12:42:53 +08:00
    @iblislsy 通讯录授权请问是第一天出现吗? 我把通讯录换成别的变量,你是不是就杠不了? 又多了一个 block 谢谢了,纯讨论技术
    semut
        13
    semut  
       2018-10-29 12:43:31 +08:00 via iPhone   ❤️ 1
    关键词 simhash
    iblislsy
        14
    iblislsy  
    OP
       2018-10-29 12:45:08 +08:00   ❤️ 1
    @semut 谢谢,我补课
    wizardoz
        15
    wizardoz  
       2018-10-29 12:45:31 +08:00
    如果结合对联系人的称谓,会不会更好玩一些?
    iblislsy
        16
    iblislsy  
    OP
       2018-10-29 12:47:04 +08:00
    @wizardoz 加上称谓,问题 又复杂了,先看看能不能找一个容易出结果的方案
    jmc891205
        17
    jmc891205  
       2018-10-29 12:58:46 +08:00
    老用户数据量有多少?能一口气读到内存里再处理吗?
    Zzdex
        18
    Zzdex  
       2018-10-29 13:02:57 +08:00
    最近在做一个类似的,也是占比来算出来匹配度。但我的数据量很小,硬算的,如果你找到好的方法希望分享以下 :)
    iblislsy
        19
    iblislsy  
    OP
       2018-10-29 13:11:31 +08:00
    @jmc891205 老用户数量(号码数量)粗略 1 千 w 吧,还会增长
    codingadog
        20
    codingadog  
       2018-10-29 13:24:06 +08:00 via Android
    @iblislsy 不好意思,我不给,blocked
    iblislsy
        21
    iblislsy  
    OP
       2018-10-29 13:26:09 +08:00
    @semut 看了一下 simhash ,LSH ,好像都是针对文本类的(可以分词)的数据? 像手机号码这样的 应该怎么办
    iblislsy
        22
    iblislsy  
    OP
       2018-10-29 13:26:28 +08:00
    看了一下 simhash ,LSH ,好像都是针对文本类的(可以分词)的数据? 像手机号码这样的 应该怎么办
    @luckychenhaha
    owenliang
        23
    owenliang  
       2018-10-29 13:37:59 +08:00
    我有一个方案,楼主看一下是否可行。(用 Elasticsearch,没什么神奇的东西)

    核心思路:new user 有 100 个号码,找一个 old user 与 new user 的 phone 交集最大。

    过程:
    1,把 user phone 的关系一条一条的存到 ES 里。
    2,给定一个 new user,它的 phone list 有 100 条,那么去 ES 里做 terms query 召回关联任意 phone 的记录。
    3,召回的 user phone 记录的 phone 一定在 100 条内,所以接着做 agg 聚合统计每个 user 的出现次数,保留 size=10 就是相同号码最多的 10 个用户了。
    guyskk0x0
        24
    guyskk0x0  
       2018-10-29 14:05:27 +08:00 via Android
    @owenliang 你提醒了我,也可以用 redis 实现:
    以 phone 为键,user_id 集合为值,数据全部存入 redis。查询时用 new user 的 phone list 把相关 user_id 取出,再统计 user_id 出现次数。
    owenliang
        25
    owenliang  
       2018-10-29 14:09:08 +08:00
    @guyskk0x0 redis 扩展性不好嘛,用 ES 就能应付,1000 万级别实时聚合没啥问题。
    iblislsy
        26
    iblislsy  
    OP
       2018-10-29 14:10:49 +08:00
    @owenliang
    @guyskk0x0 我现在准备用 ES 试一下,之前没用过,我现在开天辟地
    gamexg
        27
    gamexg  
       2018-10-29 14:13:20 +08:00
    能提升些效率,

    Bloom Filter
    每个用户有一个自己的 Bloom Filter,新用户添加时,遍历所有现存用户的 Bloom Filter,如果命中率较低,可以跳过,否则进行详细查询。
    jadec0der
        28
    jadec0der  
       2018-10-29 14:14:06 +08:00   ❤️ 1
    对,楼上两层倒排索引的思路是可行的
    iblislsy
        29
    iblislsy  
    OP
       2018-10-29 14:21:13 +08:00
    @gamexg bloom 感觉弄大动作了,我先学一下 ES
    SeaRecluse
        30
    SeaRecluse  
       2018-10-29 16:02:19 +08:00   ❤️ 1
    啧,你可以按号码段分开然后存成向量,然后根据号码数生成矩阵,矩阵运算很容易得到匹配的号码数。
    e.g.: ((1,3,9),(1,8,7),(1,6,1),(1,2,3)...) * (... ; ...)T = (a,b,c;.......)
    if a == 1^2 + 3 ^2 + 9^2
    balabalbala..........
    liwl
        31
    liwl  
       2018-10-29 16:02:38 +08:00   ❤️ 1
    麻烦说明下是什么 app,我先去卸载了
    WhyLiam
        32
    WhyLiam  
       2018-10-29 16:20:48 +08:00   ❤️ 1
    别整体卸载卸载的,单纯看看技术讨论也是值得学习的
    iblislsy
        33
    iblislsy  
    OP
       2018-10-29 16:23:52 +08:00
    @WhyLiam 钢筋太多,应该是下午茶时间到了
    amao12580
        34
    amao12580  
       2018-10-29 17:02:39 +08:00
    哪来这么多钢筋
    lance6716
        35
    lance6716  
       2018-10-29 17:10:12 +08:00
    感觉还是先试一下允许的复杂度,一般能应用的算法不超过线性代数级别。但是要是能控制数量级的话就好说。线性对数以内没想到好的方法
    imn1
        36
    imn1  
       2018-10-29 17:14:11 +08:00
    昨晚才给手机通讯录添加了 800+人
    八百标兵奔北坡
    ooooo
        37
    ooooo  
       2018-10-29 17:17:30 +08:00 via Android   ❤️ 1
    这是在讨论交流做恶技术,楼主在哪个 996 的金融创业公司?约莫是山西人?
    smilenceX
        38
    smilenceX  
       2018-10-29 17:24:12 +08:00   ❤️ 1
    麻烦说明下是什么 app,我先去卸载了
    欢迎 block,直接 B 就行,不用艾特通知我。
    xiaoxinshiwo
        39
    xiaoxinshiwo  
       2018-10-29 17:44:43 +08:00
    @ooooo #37 如果改成文档的相似度是不是就不作恶了?
    iblislsy
        40
    iblislsy  
    OP
       2018-10-29 17:53:05 +08:00
    @xiaoxinshiwo 不用搭理钢筋
    owenliang
        41
    owenliang  
       2018-10-29 18:12:56 +08:00 via Android
    什么叫钢筋
    iblislsy
        42
    iblislsy  
    OP
       2018-10-29 18:16:03 +08:00
    @owenliang 下午试了一下 ES,包括数据导入和查询,效率上挺快的,分布式还没有研究。 钢筋就是,任何时候都能抬杠,找存在感。
    owenliang
        43
    owenliang  
       2018-10-29 19:32:46 +08:00 via Android   ❤️ 1
    @iblislsy es 很成熟的,你这个需求取决于召回阶段拥有相同号码的记录数量,肯定不会很大,所以参与聚合计算量也不大,选型 es 问题不大。
    sky101001
        44
    sky101001  
       2018-10-29 20:24:24 +08:00 via iPad   ❤️ 2
    个人觉得数据量较大时,利用 Bloom Filter 是最佳解决方案:
    1. 首先设计几个不同的 hash 函数,这些 hash 函数可以把手机号映射到 256bit 的空间里,并具有“稀疏”的特点(就是说 1 的数量很少,几乎全是 0 )比如手机号 A 可以在 hash 后得到 00100010,手机号 B 得到 00100001。
    2. 然后对用户通讯录里的每个手机号进行 hash 操作,并将所得的结果按位相加,得到一个签名。比如手机号 AB 相加,得到 00100011。不同的 hash 算法可以得到不同的签名。记录这些签名。
    3. 每当有新用户注册,对其通讯录进行以上处理,得到其签名(如 00100001 )。将新用户的签名和老用户的签名进行与操作,记录 1 的个数,1 的个数最多的,就可能是最相似的。
    这样初筛时间复杂度是 O(N),之后再进行处理就快多了。
    Xs0ul
        45
    Xs0ul  
       2018-10-30 04:53:33 +08:00   ❤️ 1
    你这个 Bloom Filter 有点问题,即使每个手机号 hash 之后稀疏,一堆手机号取或以后,1 还是很多的,就不洗漱了。Bloom Filter 概念上是检查一个元素在不在一个集合里的,而不是比较两个文档的相似度。估计文档相似度的算法是楼上说的 minHash 和 LSH。

    @iblislsy #21 你这个例子不用分词,每个手机号就是一个单词,一个人的通讯录组成一篇“文档”。当然你可以用取前 N 位或 hash 之类的办法来降低“词汇量”。
    sky101001
        46
    sky101001  
       2018-10-30 09:13:01 +08:00 via iPad   ❤️ 1
    @Xs0ul 是的,这个不是 bloomfilter 的标准用法,在取或操作后摘要不再稀疏。 个人是觉得在文本长度不定的情况下,用局部敏感哈希按照(相同号码数量 /新用户的号码数量)计算相似度会比较麻烦,所以提了这个方法。本质上是就给号码归类以降低计算量。

    最终要的就是这个不稀疏的结果,假设有三个签名,分别为 11000110,11000100,01100111,可以很容易地看出前两个数据集重合的可能性更大,这样就可以筛除海量数据中不相似的那部分。

    当然,这是有误判的概率的,这个概率是和 hash 函数以及签名的长度有关的。这种 hash 函数,很好取,提一个不太好的函数--比如我希望 hash 函数要在 256bit 的空间里至多有 2 个 1,我可以把 md5 的最后 16 位分成两段 8 位的摘出来,决定这两个 1 的位置。
    xiaoxinshiwo
        47
    xiaoxinshiwo  
       2018-11-05 16:14:51 +08:00
    楼主,redis 的 set 数据类型可以支持完成你的需求,求并集即可;
    Redis Set 是 String 的无序排列。SADD 指令把新的元素添加到 set 中。对 set 也可做一些其他的操作,比如测试一个给定的元素是否存在,对不同 set 取交集,并集或差,等等。
    xiaoxinshiwo
        48
    xiaoxinshiwo  
       2018-11-05 16:31:07 +08:00   ❤️ 1
    另外推荐看看:MapReduce 练习----求共同好友
    https://blog.csdn.net/zyz_home/article/details/79659694
    xiaoxinshiwo
        49
    xiaoxinshiwo  
       2018-11-05 16:37:38 +08:00
    @guyskk0x0 #24 用 redis 何不使用 set ?可以直接取交集
    guyskk0x0
        50
    guyskk0x0  
       2018-11-06 12:09:08 +08:00 via Android
    @xiaoxinshiwo 这里需求是在 N 个集合里找与目标交集最大的一个,不是简单的求交集
    xiaoxinshiwo
        51
    xiaoxinshiwo  
       2018-11-06 12:10:37 +08:00
    @guyskk0x0 #50 知道啊,无非使用定时任务跑 N 次嘛
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   2790 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 33ms · UTC 06:16 · PVG 14:16 · LAX 23:16 · JFK 02:16
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.