CN105373521B - 一种基于Minwise Hash动态多阈值过滤计算文本相似度的方法 - Google Patents

Abstract

本发明提供了一种基于Minwise Hash动态多阈值过滤计算文本相似度的方法，该方法将比对过程划分为多个比对点，并设置各比对点的动态阈值，过滤相似度低于下界阈值T_L(k)的文档，输出相似度高于上界阈值T_U(k)的文档。这种提前过滤的方法减少了后续的比对次数，降低了工作量。针对数据的各种情况，对于文档集合全部都是重复的极端情况，基于文本相似度上界阈值的过滤策略会非常有效；对于文档集合全部都是不重复的极端情况，基于文本相似度下界阈值的过滤策略则会非常有效。

Description

一种基于Minwise Hash动态多阈值过滤计算文本相似度的 方法

技术领域

本发明属于信息检索领域，特别涉及一种基于Minwise Hash动态多阈值过滤计算文本相似度的方法。

背景技术

WEB正经历着爆炸性增长，越来越多的文献资料开始在网上公布，这种趋势使得网络上文档资源成几何级数增长，为人类共享知识和创造财富提供了前所未有的便利，也对我国的现代化建设有着积极的推动作用。然而，这些数字化资源给人们提供帮助的同时，资源的易获性也使得文档的非法复制、抄袭、剽窃等行为越来越猖獗，使得在各种论文和项目申请书等中，可能存在比较严重的抄袭现象。同时，随着国家对教育科研的大量投入，提供了各种教育和科技项目的资助，如：国家自然科学基金项目、教育部的博士点项目，各省市的基金项目、各种科技计划等。由于这些项目属于不同的职能部门单位分管，这就使得项目申请书存在着多次申报和多头申报的现象。申请书的抄袭、多次申报和多头申报现象严重影响了项目审批的客观性和公平性，对国家科研经费的合理分配产生不良的影响，造成科学研究经费可能得不到高效利用。为防止抄袭剽窃，端正学术风气，进行文档相似性检测技术的研究非常有意义。由此，世界各地的搜索引擎、图书馆、基金会、论文库、知识产权部门等都投入巨大的人力、物力和财力，正努力地在文档相似性检测上摸索和探究，以期尽快突破相似性检测的关键科学问题，为论文、项目申请书、奖励申报书、专利的查重或搜索引擎的网页去重等提供了良好的解决方案。

相似性检测数据具有海量性的特点，以国家自然科学基金申请书为例，目前就2013年申请量来说，申请书数量达17万份以上，每年还将以较快的速度增长。又如，近几年中国每年高校毕业生人数约为700万，其中大部分的毕业论文都需要进行相似性检测，每年5月份论文检测量达到高峰，日均在几万份以上，相似性检测不但要和当年的数据进行查重，还需要和历史数据进行检测，而如此海量的文档，光靠常规检测方式是根本行不通的，因此迫切需要借助哈希估计技术，建立一套精度和效率俱优的检测机制，实现对海量文档的相似性比对技术。文本相似度度量这一概念及相关技术也应运而生。一个好的文本相似度度量方法在相似性检测、自动问答系统、智能检索、网页去重、自然语言处理等研究领域具有重要的意义。

文本相似度是指两个或者多个文本之间的匹配程度的一个度量参数，相似度越高，表示两个文本之间的相似程度越大，反之越低。传统的文本相似度度量方法是向量空间模型(VSM)通过计算待查文档与数据集中某一篇文档带有权重的频率向量内积，得到两篇文档的相似度。算法需要存储大量的特征词汇、比对速度慢、准确率低等缺点，无法应用于海量数据中相似度度量。基于Minwise相似性度量算法作为最主流、成熟的相似性检测方法，通过将相似度问题转换为一个事件的发生概率问题，将文本词汇集合映射到hash值集合中，将字符串比对问题转化为特征指纹比对问题，适用于海量数据相似度度量。

基于Minwise相似性度量算法及其变种算法具有较高的估计精度，被大多数的文本相似性度量技术借鉴，广泛应用于计算机的各个领域中，有了相当多的理论和实验方法的创新和发展。目前，在海量数据的环境下对于Minwise哈希估计算法的研究趋势，集中在以下四个方面：1)降低存储空间，2)三者相似性估计，3)提高估计精度，4)提高算法效率。

1)降低存储空间方面：b位Minwise Hash[12]将b＝64缩小到b＝1，降低了存储空间和计算时间。分数位Minwise Hash算法[13]对各种精度和存储空间需求有着更加广泛的可选择性；2)三者相似性估计方面：文献[14]提出了基于b位Minwise哈希三者估计的估计子；3)在提高精度方面：文献[15]提出b位极大似然Minwise哈希，有效提高了在极端数据情况下的估计精度；4)在提高算法效率方面：One Permutation Hashing[16]只需一次置换，就能达到k次置换的效果(k次置换占Minwise哈希估计总消耗时间的80％)，提升了指纹生成效率。

综上所述，目前在降低海量指纹存储空间和提高精度等方面已经有较多成熟的算法，已有明显的改进。在海量文档数据的环境下，算法效率成为最制约海量文档相似性检测系统能否可用的因素。缩短算法的运算时间是相似度估计算法必须考虑的要素。因此，Minwise哈希估计理论急需解决问题是提高算法效率。

发明内容

针对文档集中的文档更多是低相似性文档这个特点，本发明提供了一种基于Minwise Hash动态多阈值过滤计算文本相似度的方法，克服Minwise Hash估算时间的瓶颈问题。

一种基于Minwise Hash动态多阈值过滤计算文本相似度的方法，包括以下步骤：

步骤一，提取待计算文本相似度的文档对的文本特征：minwise指纹集合S_d，集合S_d的大小为K；

[在现有的文本相似度计算方法中，需要minwise指纹集合中所有的指纹进行一一比对，即比对次数为指纹集合的大小；]

步骤二，设置多个比对点k，将总比对次数K划分为若干个阶段；

[为了减少比对次数，依据设置的比对点作为比对次数进行文本相似度计算，提前预估文本相似度；]

步骤三，分别计算所设置的比对点k对应的文本相似度上界阈值T_U(k)与文本相似度下界阈值T_L(k)：

T_U(k)＝m_l/k，T_U(k)＝m_u/k；

其中，m_l表示比对点的下界阈值，按照计算获得的m即为m_l；

m_u表示比对点的上界阈值，按照计算获得的m即为m_u；

X是文档对S₁,S₂的minwise特征指纹相等次数，m为比对次数阈值，0<m≤k；T₀为预设文本相似度阈值；i表示第i次比对；Pr(·)表示括号中的事件发生的概率，且事件发生概率为小概率；

步骤四，计算文档对第k次比对时的文本相似度估计值并依据以下准则判断是否过滤当前文本对：

若则过滤当前文档对；

若则当前文档对的相似度较高，以当前的文本相似度估计值作为当前文档对的文本相似度，保留当前文档对；

否则，增大比对点k，返回步骤三，重新计算文档对的文本相似度。

Pr(·)的取值小于或等于1E-10。

所述步骤一提取待计算文本相似度的文档对的文本特征minwise指纹集合S_d，具体过程如下：

首先，提取文档的文本特征，获得文本特征集合S_shgs；

其次，对文本特征集合进行数值映射，得到文档对应的数值集合S_d；

最后，文档对应的数值集合S_d采用minwise指纹表征：

有益效果

本发明提供了一种基于Minwise Hash动态多阈值过滤计算文本相似度的方法，该方法将比对过程划分为多个比对点，并设置各比对点的动态阈值，过滤相似度低于下界阈值T_L(k)的文档，输出相似度高于上界阈值T_U(k)的文档。这种提前过滤的方法减少了后续的比对次数，降低了工作量。针对数据的各种情况，对于文档集合全部都是重复的极端情况，基于文本相似度上界阈值的过滤策略会非常有效；对于文档集合全部都是不重复的极端情况，基于文本相似度下界阈值的过滤策略则会非常有效。而在实际的文档集中，相似的文档毕竟占少数，不相似性的文档是大多数。实验结果表明过滤算法在选取了适当的参数时，计算时间仅为Minwise Hash的31％，较大地提升了算法的时间效率。所发明的估算方法不仅能应用于Minwise Hash，也能用于它的变种算法(如b位Minwise Hash)，乃至所有符合二项分布的估计子。

在海量数据的相似度检测中，例如网页去重，常常有上亿的网页需要估计相似度。仅仅只需少量的比对次数(例如100次比对)，就可过滤大多数文档的比对，可减少大量比对时间，具有较强的实际应用价值。

附图说明

图1是原始Minwise Hash输出相似度大于预设阈值T₀的文档对的示意图；

图2是原始Minwise Hash在增设阈值T_k＝100后输出相似度大于T₀的文档对的示意图；

图3是原始Minwise Hash在增设上阈值和下阈值后输出相似度大于T₀的文档对的示意图；

图4是原始Minwise Hash在增设多个上阈值和下阈值后输出相似度大于T₀的文档对的示意图；

图5是选取的不同小概率和Minwise Hash动态多阈值过滤算法过滤率的关系图，其中，(a)是预设相似度阈值T₀为0.3的情况，(b)是预设相似度阈值T₀为0.5的情况，

(c)是预设相似度阈值T₀为0.8的情况；

图6是不同小概率和下阈值T_L(k)的关系图，(a)是预设相似度阈值T₀为0.3的情况，(b)是预设相似度阈值T₀为0.5的情况，(c)是预设相似度阈值T₀为0.8的情况；

图7是原始Minwise Hash方法和Minwise Hash动态多阈值过滤算法时间性能在选取多种小概率的情况下的比较图，其中，(a)为R_M和R_k(Pr＝1E-10,1E-5,1E-3)计算时间；(b)为Rb和Eb_k(Pr＝1E-10,1E-5,1E-3)计算时间。

具体实施方式

下面将结合附图和实施例对本发明做进一步的说明。

本发明提出的查找相似文本的方法，具体包括如下步骤：

步骤一，文本特征提取步骤：该步骤用于提取文本特征集合S_d；

首先，对文本信息进行扫描分析，利用中文分词算法对文档进行分词，利用停用词表过滤掉文本噪音数据后的分词集合即为文档的词集S_shgs。噪音即为文本中无意义的词语，一般是高频低义的助词、虚词等；

对词集S_shgs采用Rabin函数，映射32位的整数，映射后集合命名为S_d。假定全集Ω＝{0,1,...,D-1}，a₀a₁,…a_D-1恒指Ω上的一个排列，向量(a_0,a₁,…,a_D-1)代表Ω的一个置换：

如果对于数据集X∈Ω且x∈X，存在一个排列π，使得

步骤二，在原始Minwise Hash过滤算法中设定若干个对比点；

给定2个文档S₁和S₂，两者的相似度定义为：其中，f₁＝|S_d1|,f₂＝|S_d1|,a＝|S_d1∩S_d1|

在Minwise相似性估计算法中，两个文档的Minwise相似性估计子为：

式中，K表示两篇文档进行比对的minwise特征指纹的数量。一般而言，K必须要是一个比较大的值,如1000，即两个文档必须要比对足够多的minwise特征指纹才能得到相对精确的相似度。

选择若干个比对点将比对过程划分为数个阶段。若总比对次数K＝1000，可设比对点为100,200,…等。

步骤三，计算比对点k处的上阈值T_U和下阈值T_L；

在比对点k处，假设文档对{S₁,S₂}的相似度根据二项分布概率公式可知，对于参数m(0<m≤k),事件{X≤m}的概率：

事件{X>m}的概率：

可得定理1：

定理2：

其中，T_L(k)为下界阈值,T_U(k)为上界阈值。

下界阈值的计算方法为：

预设阈值T₀＝0.5，在比对点k上，选择小概率值Pr，代入公式(3)可以计算出m_l。代入定理1中即可计算得出下界阈值T_U(k)＝m_l/k。

如选择小概率为Pr＝1E-10，k为100，T₀为0.5的时候，代入公式(3)中可得方程：

解之得m_l为21，可知给定条件下，k＝100处的下界阈值为0.21。

上界阈值的计算方法为：

预设阈值T₀，在比对点k上，选择小概率值Pr，代入公式(4)可以计算出m_u。代入定理2中即可计算得出下界阈值T_U(k)＝m_u/k。

如选择小概率为Pr＝1E-10，k为100，T₀为0.5的时候，代入公式(4)中可得方程：

解之得m_l为81，可知给定条件下，k＝100处的下界阈值为0.81。

步骤四，每一个文档对在进行第k_i次比对的时候，若相似度大于T_U，则提前输出；若相似度小于T_L，则提前过滤；

否则，增大比对点k，返回步骤三，重新计算文档对的文本相似度。

当预设阈值T₀为0.5，在比对点k＝100上，若文档对{S₁,S₂}的相似度则在全部K次比对后，相似度不可能大于T₀(大于T₀的概率为1E-10，可看做不可能发生事件)，可以提前过滤该文档对。若文档对的相似度则在全部K次比对后，相似度不可能小于T₀(小于T₀的概率为1E-10，可看做不可能发生事件)，可以提前输出该文档对。

在选定的所有比对点k上分别计算上界阈值和下界阈值。文档对在进行第k_i次比对时，若相似度小于下界阈值，则提前过滤；若相似度大于上界阈值，则提前输出。最终输出所有相似度大于T₀的文档对。

图1表明了原始Minwise Hash输出相似度大于T₀的文档。图2表明在k＝100时，可增设下界阈值T_L(100)，若则不用后续900次比对，即可得出若则还需进行剩下的900次比对，计算出

下面给出了Minwise Hash的动态双重阈值过滤器的完整实现过程。

设小概率为1E-10，由定理1、2经计算可得Minwise Hash的若干个动态相似度下界阈值T_L(k)和上界阈值T_U(k)，如表1、2所示。

表1动态下界阈值T_L(k)

表2动态上界阈值T_U(k)

Minwise Hash的动态双重阈值过滤器具体过程如下：

以下从时间性能和参数优化选择论证该优势：

以某基金的申报项目为数据来源，对30万文档对，设定的小概率值Pr＝1E-10、1E-5、1E-3进行下界阈值T_L(k)的检测实验

比对点k时的过滤率为：

其中，Num为文档对的总数(30万)。

显然，过滤率和输入的文档数据有很大的关系。低相似性的数据越多，则过滤率越高。而本实验主要测试小概率和过滤率的关系，通过式(12)，测得在不同小概率Pr(1E-10,1E-5,1E-3)下的过滤率，如图5所示。图5表明，选取的小概率Pr越大，则过滤率越高，例如当k＝100，R₀＝0.3时，E(0.3,100,1E-10)＝10％，E(0.3,100,1E-5)＝60％，E(0.3,100,1E-3)＝72％。其中，E(0.3,100,1E-10)＝10％表明有10％文档节省了后面的900次比对。

测量R_Minwise(原始Minwise Hash)，在不同的小概率Pr(Pr＝1E-10、1E-5、1E-3)下的R_k(Minwise Hash的下界阈值过滤)的计算时间，如图7(a)所示。测量Rb_minwise(b位MinwiseHash)，在不同的小概率Pr(Pr＝1E-10、1E-5、1E-3)下Eb_k(b位Minwise Hash的下界阈值过滤)的计算时间，如图7(b)所示。

图7表明在不同的小概率值(Pr＝1E-10、1E-5、1E-3)下，比对10000个文档对，R_Minwise的计算时间为7020s，R_k(Pr＝1E-3)的计算时间最少，只需要2175s，计算时间仅为Minwise Hash的31％；Rb_minwise的计算时间为6000s；Eb_k(Pr＝1E-3)的计算时间为2200s，仅为b位Minwise Hash的36％。

这表明：1)过滤算法能提升时间性能。2)若设置越大的小概率(Pr)，则下界阈值也会越大，过滤率越大，则比对时间越少。

Claims (3)

1.一种基于Minwise Hash动态多阈值过滤计算文本相似度的方法，其特征在于，包括以下步骤：

步骤一，提取待计算文本相似度的文档对的文本特征：minwise指纹集合S_d，集合S_d的大小为K；

步骤二，设置多个比对点k，将总比对次数K划分为若干个阶段；

步骤三，分别计算所设置的比对点k对应的文本相似度上界阈值T_U(k)与文本相似度下界阈值T_L(k)：

T_U(k)＝m_l/k，T_U(k)＝m_u/k；

其中，m_l表示比对点的下界阈值，按照计算获得的m即为m_l；

m_u表示比对点的上界阈值，按照计算获得的m即为m_u；

X是文档对S₁,S₂的minwise特征指纹相等次数，m为比对次数阈值，0<m≤k；T₀为预设文本相似度阈值；i表示第i次比对；Pr(·)表示括号中的事件发生的概率，且事件发生概率为小概率；

步骤四，计算文档对第k次比对时的文本相似度估计值并依据以下准则判断是否过滤当前文本对：

若则过滤当前文档对；

若则当前文档对的相似度较高，以当前的文本相似度估计值作为当前文档对的文本相似度，保留当前文档对；

否则，增大比对点k，返回步骤三，重新计算文档对的文本相似度。

2.根据权利要求1所述的方法，其特征在于，Pr(·)的取值小于或等于1E-10。

3.根据权利要求1或2所述的方法，其特征在于，所述步骤一提取待计算文本相似度的文档对的文本特征minwise指纹集合S_d，具体过程如下：

首先，提取文档的文本特征，获得文本特征集合S_shgs；

其次，对文本特征集合进行数值映射，得到文档对应的数值集合S_d；

最后，文档对应的数值集合S_d采用minwise指纹表征：