需求: 对于每一个新用户,希望能计算出和老用户的通讯录最高匹配度,找到类似伪造通讯录的情况。
例子: 每一个用户的通讯录表结构如下
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
需要遍历找到匹配度最高的用户,或者是大于某一阈值的用户群体。
各位大佬,这个复杂度似乎有点高,有没有可行的方案。
1
swulling 2018-10-29 12:17:39 +08:00
网贷风控?
|
2
luozic 2018-10-29 12:20:32 +08:00 via iPhone
向量?
|
3
lance6716 2018-10-29 12:22:12 +08:00 via Android
遍历找到匹配度最高的用户对?还是啥,请使用量词定义
|
4
proudofmyself911 2018-10-29 12:34:11 +08:00 via Android
老用户是伪造的怎么办。。。
|
5
luckychenhaha 2018-10-29 12:35:24 +08:00
局部敏感哈希
|
6
Humorce 2018-10-29 12:37:41 +08:00 via iPhone
@proudofmyself911
抓网上营业厅详单,虽然这个做法很恶心,但是你要知道这个操作是要用户“授权”的 |
9
iblislsy OP @luckychenhaha 我补习一下
|
10
codingadog 2018-10-29 12:39:55 +08:00 via Android 6
麻烦说明下是什么 app,我先去卸载了
|
11
iblislsy OP @codingadog 传说中的钢筋?
|
12
iblislsy OP @iblislsy 通讯录授权请问是第一天出现吗? 我把通讯录换成别的变量,你是不是就杠不了? 又多了一个 block 谢谢了,纯讨论技术
|
13
semut 2018-10-29 12:43:31 +08:00 via iPhone 1
关键词 simhash
|
15
wizardoz 2018-10-29 12:45:31 +08:00
如果结合对联系人的称谓,会不会更好玩一些?
|
17
jmc891205 2018-10-29 12:58:46 +08:00
老用户数据量有多少?能一口气读到内存里再处理吗?
|
18
Zzdex 2018-10-29 13:02:57 +08:00
最近在做一个类似的,也是占比来算出来匹配度。但我的数据量很小,硬算的,如果你找到好的方法希望分享以下 :)
|
20
codingadog 2018-10-29 13:24:06 +08:00 via Android
@iblislsy 不好意思,我不给,blocked
|
21
iblislsy OP @semut 看了一下 simhash ,LSH ,好像都是针对文本类的(可以分词)的数据? 像手机号码这样的 应该怎么办
|
22
iblislsy OP 看了一下 simhash ,LSH ,好像都是针对文本类的(可以分词)的数据? 像手机号码这样的 应该怎么办
@luckychenhaha |
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 个用户了。 |
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 出现次数。 |
27
gamexg 2018-10-29 14:13:20 +08:00
能提升些效率,
Bloom Filter 每个用户有一个自己的 Bloom Filter,新用户添加时,遍历所有现存用户的 Bloom Filter,如果命中率较低,可以跳过,否则进行详细查询。 |
28
jadec0der 2018-10-29 14:14:06 +08:00 1
对,楼上两层倒排索引的思路是可行的
|
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.......... |
31
liwl 2018-10-29 16:02:38 +08:00 1
麻烦说明下是什么 app,我先去卸载了
|
32
WhyLiam 2018-10-29 16:20:48 +08:00 1
别整体卸载卸载的,单纯看看技术讨论也是值得学习的
|
34
amao12580 2018-10-29 17:02:39 +08:00
哪来这么多钢筋
|
35
lance6716 2018-10-29 17:10:12 +08:00
感觉还是先试一下允许的复杂度,一般能应用的算法不超过线性代数级别。但是要是能控制数量级的话就好说。线性对数以内没想到好的方法
|
36
imn1 2018-10-29 17:14:11 +08:00
昨晚才给手机通讯录添加了 800+人
八百标兵奔北坡 |
37
ooooo 2018-10-29 17:17:30 +08:00 via Android 1
这是在讨论交流做恶技术,楼主在哪个 996 的金融创业公司?约莫是山西人?
|
38
smilenceX 2018-10-29 17:24:12 +08:00 1
麻烦说明下是什么 app,我先去卸载了
欢迎 block,直接 B 就行,不用艾特通知我。 |
39
xiaoxinshiwo 2018-10-29 17:44:43 +08:00
@ooooo #37 如果改成文档的相似度是不是就不作恶了?
|
40
iblislsy OP @xiaoxinshiwo 不用搭理钢筋
|
41
owenliang 2018-10-29 18:12:56 +08:00 via Android
什么叫钢筋
|
42
iblislsy OP @owenliang 下午试了一下 ES,包括数据导入和查询,效率上挺快的,分布式还没有研究。 钢筋就是,任何时候都能抬杠,找存在感。
|
43
owenliang 2018-10-29 19:32:46 +08:00 via Android 1
@iblislsy es 很成熟的,你这个需求取决于召回阶段拥有相同号码的记录数量,肯定不会很大,所以参与聚合计算量也不大,选型 es 问题不大。
|
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),之后再进行处理就快多了。 |
45
Xs0ul 2018-10-30 04:53:33 +08:00 1
你这个 Bloom Filter 有点问题,即使每个手机号 hash 之后稀疏,一堆手机号取或以后,1 还是很多的,就不洗漱了。Bloom Filter 概念上是检查一个元素在不在一个集合里的,而不是比较两个文档的相似度。估计文档相似度的算法是楼上说的 minHash 和 LSH。
@iblislsy #21 你这个例子不用分词,每个手机号就是一个单词,一个人的通讯录组成一篇“文档”。当然你可以用取前 N 位或 hash 之类的办法来降低“词汇量”。 |
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 的位置。 |
47
xiaoxinshiwo 2018-11-05 16:14:51 +08:00
楼主,redis 的 set 数据类型可以支持完成你的需求,求并集即可;
Redis Set 是 String 的无序排列。SADD 指令把新的元素添加到 set 中。对 set 也可做一些其他的操作,比如测试一个给定的元素是否存在,对不同 set 取交集,并集或差,等等。 |
48
xiaoxinshiwo 2018-11-05 16:31:07 +08:00 1
另外推荐看看:MapReduce 练习----求共同好友
https://blog.csdn.net/zyz_home/article/details/79659694 |
49
xiaoxinshiwo 2018-11-05 16:37:38 +08:00
@guyskk0x0 #24 用 redis 何不使用 set ?可以直接取交集
|
50
guyskk0x0 2018-11-06 12:09:08 +08:00 via Android
@xiaoxinshiwo 这里需求是在 N 个集合里找与目标交集最大的一个,不是简单的求交集
|
51
xiaoxinshiwo 2018-11-06 12:10:37 +08:00
@guyskk0x0 #50 知道啊,无非使用定时任务跑 N 次嘛
|