详解min-hash算法系列[一]

LSH算法简介

在介绍min-hash算法之前，我们必须先简单介绍一下LSH（局部敏感哈希 Locality Sensitive Hashing）的概念。

LSH（局部敏感哈希 Locality Sensitive Hashing）算法是近似最近邻搜索算法中最流行的一种，而近似最近邻搜索最通俗的解释就是寻找与指定对象相似的目标对象。其主要应用于从海量的数据中挖掘出相似的数据，可以具体应用到文本相似度检测、网页搜索等领域。

LSH算法大致分为三个步骤：

1. Shingling:将文本文档转换为集合表示 (通常是转换为布尔型向量）
2. Min-Hashing: 将高维度的向量转换为低维的数字签名，此时再计算数字签名的相似性
3. Locality-Sensitive Hashing: 重点关注来自相似文档的一对候选数字签名

（上述的三个步骤中，第一步Shingling属于文本的向量化，这是一个非常大的方面，之后会单独开系列讲解。）

现在我们可以知道，min-hash 算法是LSH算法中的一个步骤，其主要工作是对输入的高维向量（可能是几百万维甚至更高）转换为低维的向量（降维后的向量被称作数字签名），然后再对低维向量计算其相似，以达到降低计算成本，提高运行效率的目的。

知道了min-hash的目的，我们接下来需要关注的就是min-hash是如何实现上述需求的了。

Jaccard距离

先别慌，在正式进入min-hash算法的讲解之前，我们必须再学习一个非常重要的概念，即Jaccard距离。

我们知道，计算两个集合的相似性有很多种度量方法，例如欧式距离、余弦相似度等，Jaccrad距离也是度量集合相似度的方法之一，其基本公式如下：

Jaccard(Ci,Cj)=∣Ci⋂Cj∣∣Ci⋃Cj∣Jaccard(C_i ,C_j)=\frac{|C_i \bigcap C_j|}{|C_i \bigcup C_j|}Jaccard(Ci​,Cj​)=∣Ci​⋃Cj​∣∣Ci​⋂Cj​∣​

这里我们声明一个概念，前文中一直所提及的“集合”（也即公式中的Ci、Cj），你可以将其视为一个矩阵中的列，而行则代表集合中的元素（你可以用它表征自然界中任何东西，反正是要被转化为布尔型向量的）。

例如：

Jaccard(C1,C2)=2/5=0.4Jaccard(C_1 ,C_2)=2/5=0.4Jaccard(C1​,C2​)=2/5=0.4

Jaccard距离的概念就如上文所述，是一个并不复杂的概念。

尽管Jaccard距离本身是一个不复杂的概念，然而，随着集合的维度的增加，计算集合之间的Jaccard距离的计算成本也呈指数级增长，因此我们不得不思考一个问题：如何降低运算的复杂度？

还记得上一节最后一段中所说的min-hash算法的目的吗，没错，min-hash算法就是一个在Jaccard距离基础之上进行改进，带有降维功能的进阶版Jaccard距离。

好了，有了对上述概念的理解，我们现在可以正式开始进行min-hash算法的学习了。