MinHash聚类失败问题

这期广告外投针对抄底流量进行了一期优化，最终的技术方案使用MinHash聚类。Minhash计算得到的相似度逼近Jaccard相似度sim(A, B)=k/(m+n-k), m是A的特征个数，n是B的特征个数，k是A与B交叉的特征个数。一般使用时，会设置100个不同Hash函数进行计算，这100个Hash函数模拟100次独立重复实验，个数越多越逼近真实Jaccard相似度。
真实的Jaccard相似度大小对MinHash实际表现会是什么样的呢？下面用100个Hash函数以能否聚类成簇为标准分析：
分析1：假设A、B的Jaccard相似度为x，则聚类成功的概率为p=1-pow(1-x, 100)，也就是至少有一个Hash函数能聚到一起的概率：
                
                
                
                
当相似度大于0.1的时候，聚类成功的概率非常大，但当相似度小于某个阈值的时候，概率显著降低，尤其当x小于万分之五时成功的概率是小概率事件。
分析2：所有与A的Jaccard相似度不为0的集合里面，一个都不能和A聚成簇的概率p‘＝(1-p1)...(1-pn)：
                
                
sigma为k/n，n是A的相似网页特征数，k是相似网页与A交叉的特征数，A的特征数为2^31。其中p1...pn是从幂率分布中抽样得到的，以尽可能符合实际。这个曲线表明对于超高特征数的网页，只有相似网页支持度很高的时候，才能在幂率环境下聚类成功。
分析3：按分析2的方法可以分析聚簇成功的概率和网页Pv的关系，如下图所示：
                
                
从图中看出随着pv增大，聚类成功的概率越低。实际聚类的时候，门户网页之间确实没有聚类成功。
结论：用Minhash聚类时，要关注高频特征是否达到上限以至于不能成功聚类。
实现Minhash的时候，为加快聚类速度（减少计算量）对高频特征均匀采样，导致本来聚不成功的门户首页反而聚类成功，使聚类效果没有发挥出来。手动去掉这些门户后Ctr、Ecpm等纬度上的效果指标显著提升。由于幂率现象的存在，算法可以忽略低频特征，却不能不考虑高频特征。