之前介绍了过一个Sketch了，现在再介绍一个吧。今天介绍的这个是Odd Sketch。它是用来快速估计集合相似度Jaccard similarity的。
- 实现
- 新建一个n bits的sketch S，置0。
- 选一个随机哈希函数
- 对集合每个元素
- Sh(x) = Sh(x) xor 1
- 返回S
- 性质
- Odd(S1) xor Odd(S2) = Odd(S1 diff S2)
- 估计
- 估计集合大小
- 让m和n分别代表集合S和Odd(S)的比特大小。因为哈希函数全随机，我们可以认为构造Odd(S)的过程是m球丢n桶实验。Odd(S)i最后为第i个桶的球数的奇偶性。这样想的话我们有两种方式来构造集合大小。
- 每一次丢球，对于任意一个桶来说都有1/n的几率转换球数奇偶性的状态，所以就当成简单的2-state Markov chain就好了。设pi为丢完i个球后任意一个给定的桶有奇数个球的概率。我们很容易知道：pi = （1 - (1 - 2/n)^i) / 2，这是标准的马式链的题目了。
- 不难推出m个球丢出去后所有奇数桶的数量的期望E[X] = n (1 - ((1 - 2 / n) ^ m) / 2)
- 现在假设有了z为奇数桶数，不难倒估m为ln(1 - 2z/ n) / ln(1 - 2/n)
- 当m球丢进了n桶，对于一个桶来说，可以认为其为一个均值u = m / n的泊松过程，
- 令p为有一个桶奇数个球的概率，则p = sum all i odd (e^(-u) * (u^i)) / i! = (1 - e^(-2u))/2。
- 令Y为整个过程结束后m个桶中奇数球数桶的期望,则有: E[Y] = np = n(1 - (e^(-2m / n)) / 2)
- 所以通过奇数桶数z可倒估m为-(n/2) * ln(1 - 2z/n)。
- 当n很大时，ln(1 - 2/n)约等于-2/n，这样和第一个等式就差不多了。
- 让m和n分别代表集合S和Odd(S)的比特大小。因为哈希函数全随机，我们可以认为构造Odd(S)的过程是m球丢n桶实验。Odd(S)i最后为第i个桶的球数的奇偶性。这样想的话我们有两种方式来构造集合大小。
- 估计Jaccard Similarity
- E[|S1 diff S2|] = 2k(1 - J),其中k是独立置换的数量。J是我们要估计的Jaccard Similarity。
- 我们上面的Odd Sketch的过程可以帮助我们找到|S1 diff S2|的一个估计为- (n / 2) * ln(1 - 2 |Odd(S1) diff Pdd(S2)|/n)，其中|Odd(S1) diff Odd(S2)|就是我们构造的的2个Odd Sketch不同的位数。现在根据E[|S1 diff S2|] = 2k(1 - J)，我们可以逆估
- J = 1 - |S1 Diff S2|/2k = 1 + (n/4k) * ln(1 - 2|Odd(S1) diff Odd(S2)| / n)
- 估计集合大小
- 后面的其他的估计我们就不讲了，说下结论，它在高Jaccard Similarity的情况下，比minhash的表现更好哦。
