对simhash的简单理解

-1为什么这么长

我整理这个文档的最初目的是将simhash的基本原理搞清楚,这个初心在学习的过程中逐渐改变了。

在整理和学习simhash相关资料的过程中,我不理解simhash得到的文本特征有效性的来源,于是开始了解simhash所属的局部敏感哈希,尝试找到解释。从论文和大家的博客来看,随机投影hash和随机超平面hash局部敏感哈希的经典形式。于是,我盯着这两个“随机”朋友看了很久。当了解到随机投影是一种数据降维方法的时候,我终于相信这两个hash算法区别不是特别大。

为了记录simhash相关知识内容,也为了记录自己在知识地图中搜索的过程,我搞了一个新花样——大杂烩。新花样总的来说会让人的大脑分泌一些带来快乐的东西,然后露出如图-1-1的表情。这也是强化自己的学习动力的一种方式。


图-1 -1当手下又有鬼点子时

本文的目录如图-1-2。


图-1-2 目录

0引言

21世纪不是生物的世纪,而是数据的世纪。数据已经成为我们这个文明必不可少的一部分,不管走到哪里,我们都沐浴在数据形成的空气中。现在,这种空气有点太多,大家快要氧中毒了——互联网、工业生产等领域产生的数据太多,我们在管理和使用这些数据时遇到了几种困难:高维度、极大的数量、重复问题。我们需要使用包括simhash在内的算法来解决这些问题。

0.1我要降维

随着采集能力和存储能力的强大,我们得了贪食症,不管一个字段是否有用,先存起来再说。总的来说,字段越多,我们可以构造的特征就越多、可以输入模型的信息就越多。不过呢,特征多是有代价的,它会降低模型的训练和计算速度。但是,我比较贪心,就是要马儿不吃草、还跑得快:在特征数量较小的情况下,尽量多地向模型提供信息。

那只能降维了。

0.2我要搜索

采集和存储能力的强大,也让我们的数据积累了海量的文档、“啥都有”。但是,如果没有较强的检索能力,“海量数据”就是“啥都找不到”“啥都没有”的代名词。

我们需要强有力的搜索技术。

0.3我需要去重

很多情况下,我们需要对文本数据进行去重:当文本分类语料有重复的样本;有些网站会将同一片文章重复发若干次,导致我们采集到大量重复的内容,进而影响后续热点检测等任务的效果;等等。

假如有10篇文档需要去重,我可以亲自上、手工排重。这个任务几十秒钟就完成了。

假如有10000篇文档需要去重,可以使用适当的相似度算法判断是否重复,然后用single-pass的框架对文档进行聚类 ,最后保留所有簇的中心文档即可。这种算法最多需要计算大约(1+9999)*10000/2次相似度,耗时会很久。当然了,我们可以用一个倒排索引来加速。

假如我们有100000000篇文档需要去重,按我以前的套路,就是用Spark这样的工具咔咔算,算到天荒地老。不过呢,如果我们使用合适的文本相似度算法和倒排索引的构建方法,用一台内存足够的机器,可以在有生之年完成这个任务。

我需要一个高效的文本去重算法。

0.4我要局部敏感哈希

前面所说的几个需求,我们可以用很多方法来满足。可选的方案中,有一朵奇葩,那就是局部敏感哈希(Local Sensitive Hash)。LSH的思想是,在保留数据相对位置的条件下,将原始数据映射到一个碰撞率较高的低维的新空间里,从而降低下游任务的计算量。利用局部敏感哈希编码的高碰撞率,我们可以设计出更加稀疏的倒查索引键值,从而得到非常高效的文本去重方案,即基于simhash的文本去重方法。

如图0-1,是我在整理simhash相关的内容时,探索出来的知识地图,算是本文的另一种目录。


图0-1 已探明的知识地图

1从基于随机投影的数据降维说起

1.1向量点积的含义

随机投影的基础方法,是向量点积运算。而理解随机投影的基础,是理解向量点积运算的含义。如图1-1,二维平面中有两个向量

。二者的点积为:

一般来说,我们会把向量点积理解为,计算向量夹角时的中间结果。

这里,为了帮助理解随机投影,需要重新解释一下。向量点积表示的是,向量

在向量

法平面上投影长度的加权值,其中权重为

的长度(当然由于乘法可交换,这里两个向量可以互换)。得到的投影向量为:

如果我们将

看做一个新空间的坐标轴,那么,在新的空间中,点A的坐标就是

这样,我们就用向量

完成了对点A的映射。

举个例子,假设两个向量:

那么a.b=7*1+3*(-1)=4。点A以

向量所在直线为坐标轴的空间中,坐标是4。

注意,经过这通操作,点A(在新空间中)的坐标由2维降到了1维。


图1-1 向量点积的含义

1.2基于随机投影的降维——2维到1维

Johnson–Lindenstrauss引理指出,在欧式空间中的若干点,经过相同的映射后进入新的空间,它们仍然会保持原来的相对位置。简单来说,“相对位置”指的是一些点相距较近,一些点相距较远。这里只从直觉上展示随机投影“保留数据相对位置”的性质。具体的证明暂时就免了。

假设二维平面中,有若干点A=(7,3), C=(-0.5,-1.5),D=(9,2),E=(-0.5,2.5)。目测,A和D离得比较近;C和E里的比较近。

我们使用向量

,将这4个点映射到新的空间,坐标分别是A1=4,C1=1,D1=7,E1=-3。A1和D1里的比较近;C1和E1离得比较近;当然了,C1和D1也挺近的。这样,二维坐标系里的4个点,被映射到了一个1维空间中,还在一定程度上保留了原来的相对位置。

那么,

是怎么来的呢?随机生成。我们可以基于高斯分布,生成B点的横坐标和纵坐标。为啥是高斯分布呢?有一定的原因,这里暂时无力讲述

这可省事了,我们在原始数据所属的空间中,随机生成一个向量,就可以基于这个向量,将原始数据映射到一个1维空间中。不过呢,在新空间中,数据点之间的相对距离存在一定程度的失真,怎么办呢?


图1-2 二维平面里的几个点

1.3随机投影的降维——N维到K维

假设有M条数据,维度非常高,为N。随机投影法将帮我们把这种数据压缩为K维(K远小于N)。


图1-1 二维平面上的原始数据向量和随机向量

将原始数据看做高维空间中的一个点。那么对应第m条数据,有一个向量

,从原点出发到这个数据点。

我们随机生成K(K远小于N)个长度为N的一维向量

,将原始数据映射到以这些随机向量所在直线为坐标轴的新空间中,得到点

。这种降维方法叫做“随机投影法”。总的来说,K越大,降维后的数据,保留的信息越多,数据之间的相对位置越“保真”——可以证明,但是这里无力搞了。

1.4随机投影法降维的python实现

github地址:

https://github.com/lipengyuer/DataScience/blob/master/src/algoritm/RandomProjectionDimReduction.py​github.com

2随机投影与局部敏感哈希

2.1随机投影降维的简化——基于随机投影的局部敏感哈希

在1.3中提到,随机投影法可以把高维数据映射到新的空间中。由于特征维度大大降低了,聚类、分类、搜索等任务的计算量也大大降低了。不过呢,人心不足蛇吞象,我还想进一步降低计算量。

新的空间里,坐标轴还是实数轴,降维后的特征是连续特征。有人认为,这样的话还得用float这种类型存储数据、还得进行float*float的操作,浪费。有些高手本着如图2-1的原则,对随机投影降维进行了改进。


图2-1 工程师的追求

在将数据映射到新空间后,我们将落在坐标轴负轴的维度(该维度取值为负数),统一赋值为0,表示数据与对应随机向量夹角大于90度。或者说,数据点与随机向量,在以后者为法向量、过原点的超平面的同侧。类似的,我们将落在坐标轴非负轴的维度,统一赋值为1。这样原始数据就被映射到了一个离散的新空间里。

这里所述的数据映射方法,就是我们常说的基于随机投影的局部敏感哈希。局部敏感哈希,与常见的hash有啥关系呢?局部敏感哈希是hash算法的一种,是数据映射方法,通常被用来对数据进行降维。

2.2黑白分明的hash

一般来说,我们遇到的数据长度n是可变的。我们可以用hash函数,将数据映射为一个长度固定为K(K远小于n)的编码。Hash函数的输出,是对原始数据的一种压缩表示,也叫做数字签名、数字指纹、消息摘要或者散列值。常见的hash算法非常严格,要求碰撞率尽量低,即每条数据拥有一个唯一的id。

从hash的原理来看,内容相同的文档,具有相同的哈希码;内容略有不同的文档,对应的哈希码会有很大的不同。如表2-1,是一些句子的hash值。其中句子1和3的哈希码相等;句子1和句子4只差了一个字,哈希码具有肉眼可见的巨大差异。

Hash码可以用来判断两个字符串是否相等。这样做有什么意义呢?我们把文档的哈希码存储起来,当需要判断两篇文档是否相等时,直接判断二者的哈希码即可。如果文档比较长(几百字),而哈希码比较短(几十位),那么后者的相等判断是比较快的。如果说,我们用位运算来进行哈希码的相等判断,那就更快了。因此,基于哈希码来判断文档内容是否相同,在一些场景里是非常高效的方案。

表2-1 句子们和它们的hash编码

在信息检索任务中,我们可以为每一条记录生成一个hash码、作为id,这样就可以为一篇文档快速地找到相关的字段了。然而,假如需要检索的是相似的文档,普通的hash算法就没办法了。这时候,我们需要不太严格的hash编码方法。

2.3随机投影hash的用途

局部敏感哈希是非常适合文本数据检索场景的编码方法。 局部敏感哈希在随机投影降维方法的基础上,增加了离散化环节。这个“离散”有啥用呢?

直观地看,原来空间中的-0.66和-100,在新空间都成为1或者0,也就是说,二者在新的空间中是相等的。这样的结果是,在原来空间中比较接近的数据点,在新的空间中,在一些维度上可能是相等的。

基于取值相同的维度,我们可以把数据分组(俗称分到桶里)。在搜索文档的时候,我们对查询语句进行hash,然后把各个维度上、桶的编号相同的文档召回,最后进行精排,可以实现快速而高质量的搜索。一个基于分桶构建的倒查索引可以帮助我们实现这样的操作。

一些在原来空间接近的数据点,经过这样的映射后,仍然相似甚至相等(各个维度坐标都相等)。对二进制编码进行相似度计算是非常快速的,在这个基础上我们可以进行非常快速的聚类。

另外,我们可以把映射后相等的数据看做是相同的数据,进而进行排重。

2.4随机超平面hash

随机超平面hash是在随机投影hash的基础上发展而来的。二者的名称含义相近,就像算法内容一样。与随机投影hash的主要区别是,随机超平面hash的编码结果是-1和1组成的串——与随机向量点积为负数,新空间中该维度取值-1;与随机向量点积为非负数,新空间中该维度取值为1。

由于使用了新空间中所有象限,随机超平面hash的性能更好一些,在文本分类、聚类任务中表现更好。

2.5两种局部敏感哈希的python实现

GitHub地址:

https://github.com/lipengyuer/DataScience/blob/master/src/nlp/LSH/RandomProjectionLSH.py​github.com

https://github.com/lipengyuer/DataScience/blob/master/src/nlp/LSH/RandomHyperplaneLSH.py​github.com

3局部敏感哈希的杰出代表:simhash

“hash”是我们经常使用的一种对数据的映射操作,它会把特定类型的数据(如字符串)映射为另一种数据(比如内存地址)。“simhash”是一种将文本数据映射为固定长度的二进制编码的算法。当然了,由于基于simhash的文本相似度计算方法、文本去重方法名气比较大,大家经常以“simhash”代指“基于simhash编码的文本相似度计算方法”或者“基于simhash编码表示的文本去重方法”。这样混乱的称呼,特别容易引起混淆,因此这里约定几个提法:(1)simhash是一种将文本数据映射为定长二进制编码的hash算法,用NLP的说法就是一种文本表示模型 ;(2)基于simhash的文本相似度计算,就是用文本的simhash值作为特征向量,来计算文档之间的相似度或者距离;(3)基于simhash的文本去重,就是使用基于simhash表示来计算文本相似度,进而发现重复文档并删除。

3.1历史选择了simhash

在文本分类、聚类、相似度计算等等任务中,我们希望用一个定长的数值向量表示文本。这样我们才能用欧氏距离等方法计算文本的相似度。常见的文本表示模型有TF(Term Frequency)、TF-IDF(Term Frequency-Inverse Document Frequency)、句向量等等。

在海量文本去重场景下,上述几种模型都有一些不足:

(1)TF精度较差,即对“非常相似”到“相同”这个相似度范围的判断不是很敏感;受文本长度等因素影响较大,相似度阈值定起来比较麻烦。

(2)精度也比较差; TF-IDF要求首先遍历一遍所有文本来的得到IDF,计算量比较大;

(3)句向量主要关注的是语义,对字面的相似不太擅长;计算量比较大。

而simhash克服了以上几种算法的不足。

3.2从文本的词向量空间模型到simhash

在词向量空间模型中,我们把词语映射为一个独热编码(one-hot encoding)。假设词汇表为(我,是,中国人,农民,儿子),大小为5,那么这几个词语的独热编码如表3-1。将文本分词后,把词语的独热编码按位累加,就得到了TF向量。比如“我是一个码农,是农民的儿子”,分词后得到“我/是/一个/码农/,/是/农民/的/儿子”,基于词语编码表,得到的TF向量就是(1,2,0,1,1)。

表3-1 词语的独热编码

高维度是TF的主要缺点。一般来说,我们的词汇是数以万计的,TF向量会比较长,导致下游任务计算量比较大。比如计算两篇文本的欧氏距离,我们需要执行数万次的减法、平方、加法等。

为此,Simhash从词语编码的降维入手,实现了对TF的降维。

3.3simhash的计算过程

Simhash是如何将文本映射为数值向量的呢?

首先,它基于hash算法将词语映射为较短的编码,然后使用随机超平面hash的做法得到最终的词语编码。然后,就像TF的计算一样,将每个词语的编码加起来。最后,采用随机超平面的离散化方法,得到文本的最终表示。

假设我们需要把S=“我爱北京天安门”这句话转换成长度为5的二进制编码。

3.3.1分词

按照一定的粒度切分文本,比如分词。S可以切分为”我/爱/北京/天安门”.

3.3.2将词语映射为定长二进制编码

将文本的每一个碎片,用一种hash算法映射为一定长度的二进制编码。如表3-2,是我假想的几个词语的编码值。

表3-2 S的词语的hash值

3.3.3将词语的二进制编码再转换一下

我们需要把词语二进制编码中的“0”一律转换为“-1”,得到词语的最终编码,如表3-3。将0转换为-1的目的,是将映射后的词语放置在整个空间中,而不是某一个象限,这样可以让数据点分布得更均匀一点。

注意,TF里,每个词语的权重比较粗暴,如果想升级一下,可以考虑TF-IDF。

与随机超平面hash相比,这里使用了一个“不随机”的超平面,将空间进行了分割。

表3-3 S的词语的新编码

3.3.4计算文档的初级编码

我们将句子中所有词语的编码加起来,就得到了句子的编码(0,0,0,2,2)。

3.3.5计算文档的最终编码

将句子编码的非正数元素转换为0,正数元素转换为1,就得到了句子的最终编码(0,0,0,1,1)——这就是句子的simhash编码。

3.4基于simhash编码计算文本距离

Simhash完成了文本的低纬度表示 ,接下来我们就可以进行文本相似度、文本分类等任务了。这里以文本相似度计算为例,展示simhash码的使用方式。

3.4.1海明距离

海明距离是simhash的经典搭档,用来在simhash码的基础上度量文本之间的距离或相似度。假设有两个等长(长度为K)的数据串:

二者的海明距离等于:

其中

假设文档A和文档B的simhash码分别为(1,1,0,1)和(1,0,0,1),那么二者的海明距离就是0+1+0+0=1(感谢

victor diao​www.zhihu.com图标

的提醒,之前这里是”0+1+1+0=2″,是一个错误)。

海明距离的特点是,在实际应用中,只需要进行基本数据类型的相等判断和加法,计算速度非常快。

3.4.2用位运算对simhash升级

Simhash码是二进制编码,可以使用位运算来实现一些快速的操作。这是simhash高性能的一个重要来源。

3.5基于simhash计算文本距离的python实现

github地址是:

https://github.com/lipengyuer/DataScience/blob/master/src/nlp/LSH/simhash_v1.py​github.com

https://github.com/lipengyuer/DataScience/blob/master/src/nlp/LSH/simhash_v2.py​github.com

4基于simhash的文本去重框架

基于simhash的海量文本去重框架里同时涉及了搜索和聚类的关键技术,可以快速地修改为搜索和聚类工具。因此,这里用一个基于simhash 的文本去重框架展示simhash的应用方式。

假设我们需要对M篇文档进行去重。

4.1比较暴力的去重框架

最简单的方式,是计算每两篇文档之间的距离,然后对距离不超过3的文档对进行去重处理。这样的话,我们需要计算(M-1+0)*M/2词相似度,计算量非常大。

4.2使用倒查索引优化去重框架

我们可以使用倒查索引来降低计算量。以64位simhash编码表示的数据集为例,我们可以构建64个倒查索引,对应simhash码的64个维度;每个倒查索引只有两个key,即0和1,表示文本编码在这个维度上的取值;这样,我们就可以把所有的文档,按照simhash编码在各维度上的取值,放到各个倒查索引中。

在实际去重的时候,每遍历到一个不重复的文档,就把它添加到64个倒查索引中。

在考察一篇文档是否重复的时候,我们首先把64个倒查索引中,与当前文档编码匹配的部分召回,然后比对当前文档与召回文档的相似度,进而判断是否重复。这种查询方式比4.1所述的方式,需要比对的次数要少很多。

当然,这种倒查索引的key还是比较稠密,每次查询会召回比较多的文档。

4.3基于抽屉原理升级倒查索引

我们可以设计更稀疏的key,来获得更高的查询精度,进而进一步减少召回的文档数量。

4.3.1抽屉原理

我们可以用抽屉原理来对去重框架进行升级。

如图4-1,有3个抽屉、4个苹果。将4个苹果放到抽屉里,那么至少一个抽屉里,有2个苹果。当我们有X个抽屉、X+1个苹果,可以得到同样的结论,至少有一个抽屉里有2个苹果。这就是抽屉原理。


图 4-1个苹果与3个抽屉

一般来说文本重复与否海明距离阈值是3,当两篇文档被判定相似,那么二者的simhash码最多有3个位置是不相等的(感谢

AndrewFu​www.zhihu.com图标

的提醒,原来是“相等”,现已改正)。换句话说,如果两篇文档的simhash 编码的海明距离小于等于3,我们认为二者是相似的。假设我们的simhash编码是64位,可以分为4组连续的数字。那么两篇相似文档的simhash编码中,至少有一个子串是完全相等的。换句话说,只有包含了文档A的4个子串中的一个的文档,才有可能与A相似。

4.3.2更稀疏的key

我们可以把simhash码切分为4个(数字可以变化)连续的子串,然后以子串为key取构建倒排索引。这时候,倒查索引的数量降到了4个。每个字串是一个16位的二进制编码,命中的文档数量相比4.2所述key更少。结果就是,查询的时候,召回的文档数量更少了。

4.4完整的去重框架

如图4-2和图4-3,分别是向倒查索引添加文档,和召回文本并排重的框架。


图4-2 构建倒排

图4-3 查询的过程

4.5文本去重框架的python实现

github地址是:

https://github.com/lipengyuer/DataScience/blob/master/src/nlp/LSH/NearRedupRemove.py​github.com

5结语

Simhash的背后是局部敏感哈希;基于simhash的文本去重技术背后,是基于局部敏感哈希的海量数据检索技术。

simhash也可以看做是一种文本你的分布式表示方法。难得的是,这种方法是无监督的。当然了,simhash挖掘文本信息的能力没有word2vec这种模型强,simhash编码会限制分类、聚类模型的效果上限。一般来说,在低精度、高速度的场景下,可以试一下simhash。

这里对局部敏感哈希的理解方式,具有较强的个人风格,不一定适合所有的人。如果看不懂,那是我的表达方式导致的。可以参考这里的知识地图搜索套路,整理出属于自己的表达。