这是一个创建于 2253 天前的主题，其中的信息可能已经有所发展或是发生改变。
需求： 对于每一个新用户，希望能计算出和老用户的通讯录最高匹配度，找到类似伪造通讯录的情况。
例子： 每一个用户的通讯录表结构如下
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 次嘛
|
Select Language