5.6.1　基于MinHash聚类

对于用户u，他的点击历史记为C_u。那么两个用户u_i、u_j的相似度可以用Jaccard系数来表示：

有了两个用户之间的相似度，我们可以非常形式化地将相似用户点击过的新闻通过上面的相似度加权推荐给用户u。但是用户数和新闻数都是天文数字，无法在极短时间内为大量用户完成计算。这时，我们可以采用LSH（Locality Sensitive Hashing）的思路来计算，大大降低计算复杂度。LSH的核心思想是，对于一组数据（对于我们这个场景来说，这一组数据就是用户的历史点击记录C_u），可以用一组哈希函数来获得哈希值，如果两组数据非常相似，那么哈希值冲突的概率就越大，而冲突率是等于这两组数据的相似度的。当我们用Jaccard系数来计算用户点击历史的相似度时，LSH就叫作MinHash。

下面先来说明怎样为一个用户u计算哈希值，所有新闻集为C，我们对集合C进行一次随机置换，置换后的有序集合记为P={i₀,i₁,…,i_k,…,i_m}（||C||=m+1，即一共有m+1条新闻），计算用户u的哈希值为

上式表示按顺序从左到右数，P中第一个包含在C_u中的元素的下标就是u的哈希值。

可以证明（有兴趣的读者可以自行证明，或者参考相关参考文献），两个用户u₁、u₂的哈希值冲突（值一样）的概率就是u₁、u₂用Jaccard系数计算的相似度。所以我们可以将MinHash认为是一种概率聚类方法，对应的哈希值就是一个类D_a={u|h(u)=a}，所有哈希值为a的用户聚为一类D_a。

我们可以取p个置换（即p个哈希函数），将这p个哈希函数得到的哈希值拼接起来，那么对于两个用户u₁、u₂，这p个拼接起来的哈希值完全一样的概率就等于S(u₁,u₂)^p。很显然，通过将p个哈希值拼接起来得到的聚类更精细（p个哈希值都相等的用户肯定更少，所以类D_a更小，更精细），并且相似度也会更高。从找用户最近的领域（最相似的用户）的角度来看，将p个哈希值拼接起来的方法的精准度更高，但是召回率更低（聚类更小了，因此召回的新闻更少了，所以一般召回率就降低了），为了提升召回率，获得更多的相似用户，我们可以将这个过程并行进行q次，最终每个用户获得q个聚类，相当于进行了q次召回，在论文中作者建议p取2～4，q取10～20。

在实际的工程实践上，由于新闻数量太大，因此进行置换操作的耗时也很大，可以采用简化的思路（精度会打折扣），对于上面提到的p×q个哈希函数（置换），我们事先取p×q个独立的随机种子值与之一一对应，每个随机种子就是哈希函数的替代。对于每个新闻及每个种子值，我们利用该种子值和该新闻的id（整数值），再利用一个特定的哈希函数H来计算哈希值，该哈希值是利用前面讲的置换后该新闻的下标的最小值，那么采用这种方法后用户u的哈希计算公式如下：

该方法不需要对新闻集进行置换，会大大减少计算量，并且只要这个特定哈希函数H的取值范围在0到2⁶⁴-1之间，那么冲突概率就会比较小，这种近似的MinHash函数与真正的通过置换产生的MinHash函数的性质是近似的。

上面讲解了MinHash聚类的算法实现细节，具体工程实现中可以用Hadoop或者Spark等分布式计算平台来并行计算，这里不细说。我们可以将每个用户的聚类及每个聚类包含的用户用倒排索引表的格式存储起来，方便后面做推荐时查阅。