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

[iblislsy]

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

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

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

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

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

[swulling]

网贷风控？

[luozic]

向量？

[lance6716]

遍历找到匹配度最高的用户对？还是啥，请使用量词定义

[proudofmyself911]

老用户是伪造的怎么办。。。

[luckychenhaha]

局部敏感哈希

[Humorce]

@proudofmyself911
抓网上营业厅详单，虽然这个做法很恶心，但是你要知道这个操作是要用户“授权”的

[iblislsy]

@lance6716 找到这个匹配度 0.67 就可以了，能找到超过给定阈值θ(比如 0.5)的用户集群更好

[iblislsy]

@lance6716 这个 0.67 是用户 123 和其他所有用户匹配的最大值

[iblislsy]

@luckychenhaha 我补习一下

[codingadog]

麻烦说明下是什么 app，我先去卸载了

[iblislsy]

@codingadog 传说中的钢筋？

[iblislsy]

@iblislsy 通讯录授权请问是第一天出现吗？ 我把通讯录换成别的变量，你是不是就杠不了？ 又多了一个 block 谢谢了，纯讨论技术

[semut]

关键词 simhash

[iblislsy]

@semut 谢谢，我补课

[wizardoz]

如果结合对联系人的称谓，会不会更好玩一些？

[iblislsy]

@wizardoz 加上称谓，问题 又复杂了，先看看能不能找一个容易出结果的方案

[jmc891205]

老用户数据量有多少？能一口气读到内存里再处理吗？

[Zzdex]

最近在做一个类似的，也是占比来算出来匹配度。但我的数据量很小，硬算的，如果你找到好的方法希望分享以下 ：）

[iblislsy]

@jmc891205 老用户数量（号码数量）粗略 1 千 w 吧，还会增长

[codingadog]

@iblislsy 不好意思，我不给，blocked

[iblislsy]

@semut 看了一下 simhash ,LSH ,好像都是针对文本类的（可以分词）的数据？ 像手机号码这样的 应该怎么办

[iblislsy]

看了一下 simhash ,LSH ,好像都是针对文本类的（可以分词）的数据？ 像手机号码这样的 应该怎么办
@luckychenhaha

[owenliang]

我有一个方案，楼主看一下是否可行。（用 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]

@owenliang 你提醒了我，也可以用 redis 实现：
以 phone 为键，user_id 集合为值，数据全部存入 redis。查询时用 new user 的 phone list 把相关 user_id 取出，再统计 user_id 出现次数。

[owenliang]

@guyskk0x0 redis 扩展性不好嘛，用 ES 就能应付，1000 万级别实时聚合没啥问题。

[iblislsy]

@owenliang
@guyskk0x0 我现在准备用 ES 试一下，之前没用过，我现在开天辟地

[gamexg]

能提升些效率，

Bloom Filter
每个用户有一个自己的 Bloom Filter，新用户添加时，遍历所有现存用户的 Bloom Filter，如果命中率较低，可以跳过，否则进行详细查询。

[jadec0der]

对，楼上两层倒排索引的思路是可行的

[iblislsy]

@gamexg bloom 感觉弄大动作了，我先学一下 ES

[SeaRecluse]

啧，你可以按号码段分开然后存成向量，然后根据号码数生成矩阵，矩阵运算很容易得到匹配的号码数。
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]

麻烦说明下是什么 app，我先去卸载了

[WhyLiam]

别整体卸载卸载的，单纯看看技术讨论也是值得学习的

[iblislsy]

@WhyLiam 钢筋太多，应该是下午茶时间到了

[amao12580]

哪来这么多钢筋

[lance6716]

感觉还是先试一下允许的复杂度，一般能应用的算法不超过线性代数级别。但是要是能控制数量级的话就好说。线性对数以内没想到好的方法

[imn1]

昨晚才给手机通讯录添加了 800+人
八百标兵奔北坡

[ooooo]

这是在讨论交流做恶技术，楼主在哪个 996 的金融创业公司？约莫是山西人？

[smilenceX]

麻烦说明下是什么 app，我先去卸载了
欢迎 block，直接 B 就行，不用艾特通知我。

[xiaoxinshiwo]

@ooooo #37 如果改成文档的相似度是不是就不作恶了？

[iblislsy]

@xiaoxinshiwo 不用搭理钢筋

[owenliang]

什么叫钢筋

[iblislsy]

@owenliang 下午试了一下 ES，包括数据导入和查询，效率上挺快的，分布式还没有研究。 钢筋就是，任何时候都能抬杠，找存在感。

[owenliang]

@iblislsy es 很成熟的，你这个需求取决于召回阶段拥有相同号码的记录数量，肯定不会很大，所以参与聚合计算量也不大，选型 es 问题不大。

[sky101001]

个人觉得数据量较大时，利用 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]

你这个 Bloom Filter 有点问题，即使每个手机号 hash 之后稀疏，一堆手机号取或以后，1 还是很多的，就不洗漱了。Bloom Filter 概念上是检查一个元素在不在一个集合里的，而不是比较两个文档的相似度。估计文档相似度的算法是楼上说的 minHash 和 LSH。

@iblislsy #21 你这个例子不用分词，每个手机号就是一个单词，一个人的通讯录组成一篇“文档”。当然你可以用取前 N 位或 hash 之类的办法来降低“词汇量”。

[sky101001]

@Xs0ul 是的，这个不是 bloomfilter 的标准用法，在取或操作后摘要不再稀疏。 个人是觉得在文本长度不定的情况下，用局部敏感哈希按照（相同号码数量 /新用户的号码数量）计算相似度会比较麻烦，所以提了这个方法。本质上是就给号码归类以降低计算量。

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

当然，这是有误判的概率的，这个概率是和 hash 函数以及签名的长度有关的。这种 hash 函数，很好取，提一个不太好的函数--比如我希望 hash 函数要在 256bit 的空间里至多有 2 个 1，我可以把 md5 的最后 16 位分成两段 8 位的摘出来，决定这两个 1 的位置。

[xiaoxinshiwo]

楼主，redis 的 set 数据类型可以支持完成你的需求，求并集即可；
Redis Set 是 String 的无序排列。SADD 指令把新的元素添加到 set 中。对 set 也可做一些其他的操作，比如测试一个给定的元素是否存在，对不同 set 取交集，并集或差，等等。

[xiaoxinshiwo]

另外推荐看看：MapReduce 练习----求共同好友
https://blog.csdn.net/zyz_home/article/details/79659694

[xiaoxinshiwo]

@guyskk0x0 #24 用 redis 何不使用 set ？可以直接取交集

[guyskk0x0]

@xiaoxinshiwo 这里需求是在 N 个集合里找与目标交集最大的一个，不是简单的求交集

[xiaoxinshiwo]

@guyskk0x0 #50 知道啊，无非使用定时任务跑 N 次嘛