背景：
我遇到一个问题，要计算140万商品的杰卡德相似度。如果直接要直接两两计算的话，这计算量根本算不了，而且也没必要。
分析：
在这些商品中很多商品的相似度并不高，也就是说其中达到相似度阈值的商品只占这些商品组合的一小部分。针对这种情况，首先想到的是按照类别，或者商品品牌进行计算，只计算同类别或者同品牌下的相似品。
但是实际执行效果并不理想，分析原因可能有以下两点。
一、不同类别下的商品数目极不均衡，一些类别比较少的只有十几个，而一些类别下的商品数量极大，可能有十万以上。
二、如果按品牌划分则推荐效果不理想，只能推荐该品牌下的商品，而且同样存在问题一中的情况，即不同品牌的商品数量差别很大。
解决方案：
找到的一种解决方案是使用minhash加一些近似估计的处理。最后达到的效果是在满足一定的准确率的情况下，获得杰卡德距离大于一定阈值的所有商品组合，然后在对这些商品对计算真正的距离。比如我们要求获取杰卡德距离大于0.2的所有商品对，而且准确率不低于99%
先介绍minHash
minhash是局部敏感hash的一种。局部敏感哈希是将原始数据去一个摘要，该摘要还能够表示原始数据之间的相似性，例如相似性大于一定阈值的话，Hash值相等。
minHash要实现这么一种Hash，对于原始集合Set1和Set2的hash，hmin(Set1)=hmin(Set2)的概率p 等于Set1与Set2的杰卡德相似度。
下图是维基百科上的介绍。
接下来介绍算法的两种实现：
一种是使用多个hash函数，这种比较简单。具体过程为，使用K个Hash函数，然后每个Hash函数分别对集合A和集合B计算hmin(SetA) ,hmin(SetB)。然后计算SetA的K个Hash min 和SetB的K个Hash值的交集，假设交集有Y个。则杰卡德相似度的值为Y/K。
第二种是使用一个Hash函数：
使用多个hash函数的计算代价太大（每个都求一次最小值确实费劲）。我们使用一个Hash函数分别求出SetA和SetB的前K小的元素。SetA的前K小的作为A的签名，SetB的前K小的作为B的签名。然后计算集合X:
X = h(k)(h(k)(A) ∪ h(k)(B)) = h(k)(A ∪ B)
根据之前说过的该Hash函数要求的性质X等价于求得A和B的并集的前K小元素的集合。
然后在求一个子集Y，令Y等于：
Y = X ∩ h(k)(A) ∩ h(k)(B)
集合A和集合B的杰卡德距离的估计值是：|Y|/X
应用：
1、MinHash的应用应该是对要计算杰卡德距离的两个集合进行降维，然后通过集合的摘要计算杰卡德相似度。
2、还有一种是通过minhash相等的概率等于杰卡德相似度，来优化大量集合之间的杰卡德相似度的计算。
参考资料：
http://www.cnblogs.com/bourneli/archive/2013/04/04/2999767.html
https://en.wikipedia.org/wiki/MinHash