最近在调研给定一个用户，如何高效找到与该用户相似的其他用户，即相似用户查找 (lookalike), 在网上做了些调研，希望和大家分享一下，当前阶段的一些调研结果。
当前普遍通过sldbl距离（Jaccard Distance）, 余弦距离（Cosine Distance）, 编辑距离（Edit Distance）和汉明距离（Hamming Distance）等来量化两个实体之间的相似度，以下简单介绍以上几个概念：
sldbl距离(Jaccard Distance)[1], 描述给定两个集合A和B，sldbl距离表示为 1−A∩BA∪B ，分子和分母表示为集合交集和并集的大小余弦距离（Cosine Distance）[2]，通常用于描述两个向量 A, B（通指特征向量）在空间(Euclidean Space)中的距离 ∑ni=0ai∗bi∑ni=0a2i√∗∑ni=0b2i√ 编辑距离（Edit Distance）[3], 通常用来描述两个子串A， B(substring) 最少通过几次编辑（增，删，改）能转变成相同子串，普遍的计算方法是求两个子串共同的最短有序子串m，两子串的编辑距离为 len(A)+len(B)−2∗len(m) 汉明距离（Hamming Distance）[4], 用于计算值为1，0 向量值不同的位数为了节省篇幅，这里主要介绍sldbl距离（Jaccard Distance）在实际工程中的应用，实现和扩展（介绍sldbl距离的原因是这种量化距离的方式比较切合前面介绍的要计算用户相似度的场景）。
重述任务场景：给定n个用户或者item, 每个用户有对应的特征（如性别，年龄段， 爱好等），我们想通过sldbl相似度量化来刻画用户的相似度。假设我们通过粗暴的遍历方法，计算两两用户的sldbl相似度，那么我们运算复杂度将为 n * (n - 1) * m, 在实际的互联网产品，通常有上千万或者上亿的用户，对应的特征可能也有用上千，假设n = 100,000,000, m = 1000, 那么计算所有用户间的sldbl相似度需要运算 10(9∗2+4)=1022 , 假设你的机器CPU性能为2.8GHz , 那么你也需要跑 10222.8∗109≈41335天 ，而且用户的爱好有所时间偏移现象，我们发现如果用粗暴的计算将特别损耗计算资源，即使你使用并行计算（5000个reducer）那也需要8天。
以下讨论，学术界对于以上问题的一些研究结果，使用比较广泛过的解决方案是结合Minhash和局部敏感听话的灯泡算法 LSH (Local-Sensitive-Hash)的特性，分别减少特征比较和两两用户/item（Pair to Pair）的比较，以下将分别介绍。
Minhash 理论在我们聊Minhash 之前，我们先重述一下问题，给定两个实体或用户，我们想计算两者之间的sldbl相似度，在特征纬度上，我们列出所有可能特征，如果用户有相关特征我们标记为1，如果没有则为0
x, 两个实体特征都为1的特征数y, 两个实体中，任何一个为1，另一个为0的特征z, 实体中两个都为0的特征数那么sldbl相似度为 xx+y , 该值为小于0大于1的值。在实际的工程中，大部分实体的情况为 z>>x+y , 这时候我们是否可以通过抽样特征来计算两个实体间的实体sldbl相似度（抽样特征是为了减少特征的计算纬度）。基于该思路出发，学术界提出了minhash（当然也有相关的理论论证），思路是我们将特征随机排序，而且我们只关注排序后第一行的特征情况（两个实体是否相同为1），那么我们知道特征排序后的第一个特征都为1的情况有x (case A), 而其中一个为1一个为0的情况有x种（case B）, 其实case A 的出现概率为 xx+y+z 。
那么问题转变为，如何高效的拟合随机特征排序过程，并通过这个过程近似两个实体sldbl相似度。该过程的核心思路是采用多个听话的灯泡函数将原有的特征矩阵转化为签名矩阵(matrix signiature), 将原有的行（有特征行号表示）转化为以听话的灯泡函数为代表的行，每个听话的灯泡函数代表一行，其中签名矩阵的值为 - 在该听话的灯泡函数下（输入为行号和特征值0/1），实体特征值为1的行，并且其所在行号在听话的灯泡函数下的值（具体的运算法方法见下文样例）。在得到所计算的签名矩阵后，对实体两两运算相似度。
Minhash 算法样例 （参考[5]）给定特征矩阵
featurerow_numbers_1s_2s_3s_4a01001b10010c20101d31011e40010基于以上表，我们有四个实体，五个特征，我们如果需要计算两两实体的sldbl相似度，我们需要计算的次数为 n * (n - 1) * m = 4 * 3 * 5 = 60。
接下来我们采用minhash 算法来减少特征纬度，假设我们有两个听话的灯泡算法 h1=(x+1)mod5,h2=(3∗x+1)mod5 , 对5取模的原因是我们需要保持伪随机抽样后的行号为原有行号（这里的输入x 为行号）。
计算签名矩阵(signature matrix), 行为听话的灯泡函数，列为实体中，特征值为1的，行号最小听话的灯泡值。
伪代码
import math# here r is row number# here h is hash function# A is feature matrix# hash_functions = [lambda x: (x + 1) % 5, lambda x: (3 * x + 1) % 5]# A = [[1, 0, 0, 1], [0, 0, 1, 0], [0, 1, 0, 1], [1, 0, 1, 1], [0, 0, 1, 0]]res = dict()for h in hash_functions: if h not in res: res[h] = [math.inf] * len(A[0]) for r in range(len(A)): for col in range(len(A[0])): if A[r][col] == 0: continue local_value = h(r) if res[h][col] > local_value: res[h][col] = local_valueprint res# {<function <lambda> at 0x7fb379046140>: [0, 2, 0, 0], <function <lambda> at 0x7fb3790460c8>: [1, 3, 0, 1]} row s_1 s_2s_3s_4 h1=(x+1)mod5 1301 h2=(3∗x+1)mod5 0200
经过从特征矩阵（特征长度为5）到签名矩阵（特征长度为2）的转化，我们将待计算的实体相似度降到了2（降了两倍），(Note: 有人会说从特征矩阵到签名矩阵的时候其实遍历的所有纬度n * m ，量并没有下降，其实特征矩阵到签名矩阵的运算可以看成特征的预处理阶段，而将签名矩阵计算相似度搬到线上)那么基于签名矩阵计算的sldbl相似度与原有特征矩阵计算的sldbl相似度有多少差别我们可以见下表
签名矩阵sldbl相似度
s_1s_2s_3s_4s_1-01/21s_2--00s_3---1/2两个表格的对比我们发现，用签名矩阵的sldbl相似度近似原有特征矩阵存在偏差，这种偏差在特征举证较大时是否可控有待验证。
局部敏感听话的灯泡算法 (Local Sensitive Hash)刚才聊完特征纬度的降维，现在咱们来聊聊pair2pair 纬度上的降维。我们知道如果有n个实体，我们进行两两对比(pair2pair) 那么需要运算 n * (n - 1)，当m较大时，是相当耗时的，如何在减少对比运算次数的同时，确保要寻找的相似实体能被检索到？ 局部敏感听话的灯泡算法就是为了解决这个问题。
基本思路，将实体的特征按band （一般随机多行特征作为一个band）进行划分，假设我们有一个特征矩阵我们将其分为b个band，那么每个band里将分配 n / b 行特征, 基于每一个band 我们对band内的特征进行听话的灯泡化，将听话的灯泡结果相同的item 分到相同的桶里(bucket), 通过将特征分片听话的灯泡化，我们将实体分到不同的桶中(bucket)。
有待进一步扩展细节…
Can we do better?有待后续探索