选择最小散列的哈希数？处理极其稀疏的数据，并希望有更多的冲突

Question

我试图使用min散列来生成集群和相似点，我主要是使用这些资源中的想法。

• http://www2007.org/papers/paper570.pdf
• https://chrisjmccormick.wordpress.com/2015/06/12/minhash-tutorial-with-python-code/

我正在处理的数据由用户和项之间的交互组成。有220万不同的用户和4.4亿不同的项目。在所有的数据中，只有9.05亿条记录，所以非常稀少。

在我的方法中，我通过重新排序条目(其中有440米)来计算每个用户的H最小哈希值。用户有广泛的项目交互。交互次数最多的用户为2.5M，最低的为1次，平均为403次，中位数仅为26次。

在Google的关于Google新闻的文档中，他们建议连接2-4键(LSH)，并这样做10-20次。我认为，当用户与较少的项目(如新闻文章)进行交互时，这种方法效果很好，但对于我所做的事情来说，它却低得可怜。当我为具有1,000+交互的用户测试此数目的密钥时，许多用户没有任何连接的min与另一个用户匹配。这是一个问题，因为我可以手动计算其中一些用户的余弦或jaccard相似度，并为我的需要看到一个可接受的相似度。我已经找到了更好的结果，不连接散列键和使用多达200。

对于我的大多数散列密钥组，224万用户大约有2M个不同的散列键。因此，碰撞的数量相当少。

你们有什么增加集群数量的建议吗？我正在考虑使用1,000个哈希键和配对用户，如果他们匹配多个。提前谢谢。

Answer 1

一种选择是将散列函数更改为更有可能发生冲突的函数。例如，皮尔逊散列是一个8位的散列，它比更常见的散列函数有更多的冲突。