基于LSH技术的试题相似度检测方法

The Application of LSH Technology in Similar Question Detection

摘要: 试题内容重复率是评价试题库及试卷质量的重要指标之一，为了快速找出题库中的相似试题，本文主要研究了基于K-shingles的Jaccard相似度、MinHash和LSH技术应用于相似试题的检测方法。此方法首先将题干内容进行中文分词，进行适当处理后转换成K-shingle集，通过MinHash计算出签名，最后使用LSH技术快速地找出候选相似试题对并计算出相应的Jaccard相似度，若该相似度大于给定的阈值，则发现相似试题。该方法通过在题库系统中的使用，充分验证了该方法的可行性，达到了很好的效果。

Abstract: The repetition rate of test questions is one of the important indexes to evaluate the quality of test questions and test papers. In order to quickly find out similar questions in the test bank, this paper mainly studies the detection methods of similar questions based on K-shingles, Jaccard similarity, MinHash and LSH technology. First of all, the main content of the question is segmented into Chinese words, then converted into K-shingle set after proper processing, and the signature is calculated by MinHash. Finally, LSH technology is used to quickly find out the candidate pairs of similar questions and calculate the corresponding Jaccard similarity. If the similarity is greater than the given threshold, similar questions are found. Experiments prove to be practicable and effective.

1. 引言

试题内容重复是影响试题库及试卷质量的重要因素之一，所以对相似试题的检测和去重就尤为重要。目前相似试题的发现方法主要使用自然语言处理(NLP)中的文本相似性检测方法。这些方法大致可分为以下几类：

· 单词共现方法(Word co-occurrence)。

· 基于词汇数据库(lexical database)的相似度方法。

· 基于词向量(word vectors)的递归神经网络和深度神经网络方法。

单词共现方法通常用于识别文本数据中的重要部分 [1]。该方法具有明显的缺点，例如：

· 它忽略了句子的词序。

· 它不考虑单词在句子上下文中的含义。

但是它具有以下优点：

· 可匹配任何文本。

· 能成功地从中提取关键字。

词汇数据库方法，使用具有在树状结构中编译的词、含义和与其他词关系的预定义词层次来计算相似度 [2]。在比较两个词时，它考虑了词之间的路径距离以及包含者在层次中的深度。包含者指的是与被比较的两个词有关的相对根节点。它还使用单词语料库来计算单词的“信息内容”，这会影响最终的相似度。该方法具有以下局限性：

· 在计算相似度时不考虑单词的适当含义，而是选择最佳匹配对，即使单词在两个不同的句子中的含义完全不同。

· 来自一个语料库的词的信息内容与另一个语料库中的词的信息内容不同。

近年来，基于神经网络的模型在语义相似度有了很大的改进 [3] [4] [5] [6] [7]。其中乐雨泉等 [8] 提出了一个称为ACV-tree句子建模方法。这个方法可以看成一种通用的句子建模框架，此框架试图将句法知识(syntactic information)、语义信息(semantic information)、注意力权重机制(attention weight mechanism)合并到一个统一的结构中来吸收它们的优点。解决了自然语言处理中句子建模的问题。梁圣 [9] 提出了循环神经网络用于计算试题相似度的方法，对比了不同词向量维度以及LSTM隐含层神经单元个数对相似度计算结果的影响。田星等 [10] 提出了一种基于词向量的Jaccard句子相似度算法，该方法首先通过训练将每个词语映射为语义层面的高维向量，然后计算各个词向量之间的相似度，高于阈值α的作为共现部分，从而计算句子的相似度。陈勤等 [11] 提出了一种基于上下文对齐的RNN (CA-RNN)模型，该模型将对齐后的词的上下文信息整合到一个句子对中，用于内部hidden state的生成。虽然神经网络方法在语义的相似性上取得了很大的改善，但神经网络方法却需要成千上万个标记样本作为训练数据，而训练往往需要花费大量的时间。

总体而言，上述所有方法在试题相似性检测上往往不太适合。这些方法过于追求于语义上的精准相似，代价高昂。其忽略了在多个样本中，两两相似比较的时间复杂度。本文的研究方法，即不需要额外的语料数据库，也不需要大量的训练样本，更无需借助除了Office之外的其它功能即可快速地实现相似试题的检测。

该方法基于K-shingle，K-shingle是连续K个词的唯一序列，通过K-shingles将试题内容转换成一组位向量0和1来表示，其中，0表示该试题中不存在此shingle，1表示该试题存在此shingle。近似相同的两个试题应该有许多相同的shingle。两个试题内容是否相似可以通过使用Jaccard相似度来计算得到。Jaccard相似度在数据集较小时，相似对的比较和相似度计算都表现良好。然而，在数据集较大时，时间复杂度将几何上升，此时可以通过MinHash转换的签名矩阵和位置敏感散列(LSH)技术来解决这个问题，从而在更短的时间内快速逼近真正的Jaccard相似度。

2. 研究内容

2.1. Jaccard相似度

两个集合M和N的Jaccard相似度是 $\left|M\cap N\right|/\left|M\cup N\right|$，即两个集合交集的数目与两个集合并集数目的比例(Rajaraman and Ullman, 2011) [12]。

$JSim\left(M,N\right)=\frac{\left|M\cap N\right|}{\left|M\cup N\right|}$

Jaccard相似度具有如下性质：当且仅当两个集合相等时 $M=N$， $JSim\left(M,N\right)=1$ ；当且仅当 $M\ne N$， $JSim\left(M,N\right)=0$ ； $JSim$ 是对称的。基于Jaccard相似度的文档相似度在很多方面均有应用，如：文档抄袭、镜像页面、同源新闻稿等。如下面两个集合的相似度为 $JSim\left(M,N\right)=1$。

若有两个集合 $A=\left\{a,b,c,d,e\right\},B=\left\{c,d,e,f,g,h\right\}，则JSim\left(A,B\right)=3/8$。

2.2. 中文分词

在中文中，词语之间没有分隔，且边界模糊。因此进行中文自然语言处理通常是先将汉语文本中的字符串切分成合理的词语序列，然后再在此基础上进行其它分析处理。中文分词是中文信息处理的一个基础环节，已被广泛应用于中文文本处理、信息提取、文本挖掘等应用中。例如：T1 = {“关系数据库理论包括函数依赖和_____”}，经过分词之后为Ts1 = {“关系”，“数据库”，“理论”，“包括”，“函数”，“依赖”，“和”}。

2.3. 文档的K-shingles

为了识别字面上相似的文档，将文档表示成集合的最有效的方法是构建文档中的短字符串集合(即shingle)。如果文档采用这样的集合表示，那么有相同句子甚至短语的文档之间将会拥有很多公共的shingle。其中K表示子串的长度。为了通过K-shingle表示一个文档，需要提前对文档进行处理。如删除首尾空格、删除停用词等。然后再把文本拆分成分词。例如经过分词之后的T1 = {“关系”，“数据库”，“理论”，“包括”，“函数”，“依赖”}，如果K = 2，则通过K-shingle，Ts1 = {“关系数据库”，“数据库理论”，“理论包括”，“包括函数”，“函数依赖”}，如果还具有下列两个文本T2 = {“数据库的理论包括函数依赖和______”}、T3 = {“关系数据库理论包括______和规范化”}，则3个文本的shingle元素矩阵如表1所示。

Table 1. Shingle element matrix of text

表1. 文本的shingle元素矩阵

表1中的文本对相似度如下： $JSim\left(T1,T2\right)=4/5$， $JSim\left(T1,T3\right)=3/6$， $JSim\left(T2,T3\right)=2/6$。

2.4. Shingle的哈希

由于所有shingle集合的存储需要占用大量的空间。可以哈希shingle进行散列，使用散列之后的桶号来代替shingle串。我们使用以下形式的散列函数 [13]：

$h\left(x\right)=\left(ax+b\right)modp$

其中： $x$ 为原始矩阵中的shingle串，a和b是从(0, Shingle全集大小)之间的一个随机数，p是比Shingle全集稍大的数。

假定表1中的shingle串被哈希到0~5的桶中，见表2。

Table 2. Characteristic matrix M

表2. 特征矩阵M

表2中的矩阵也称为特征矩阵M，该矩阵的行对应shingle，列对应文本集合。由于特征往往非常稀疏，在处理大量文本对的相似度计算时非常不方便。

2.5. 最小哈希签名(MinHash)

通过最小哈希可以把特征矩阵转变为签名矩阵，该签名矩阵的行对应最小哈希函数，列对应文本集合。通常情况下签名矩阵所需的存储空间比特征矩阵M的存储空间要小很多。最小哈希签名的计算过程如算法1所示：

算法1：最小哈希签名

输入：特征矩阵M，哈希函数 $h_1,h_2,\cdots ,h_n$

输出：签名矩阵S

对于所有的每个哈希函数(i)，每一列(c)，签名矩阵中S的 $S\left(i,c\right)$ 表示第i个哈希函数及第c列对应的最小哈希值。

Step1循环对特征矩阵中的每一行进行处理，计算当前行r的哈希值， $h_1\left(r\right),h_2\left(r\right),\cdots ,h_n(r)$

Step2对每列c进行如下操作

(a) 若特征矩阵中 $M\left(i,c\right)=0$，则什么都不做；

(b) 若 $M\left(i,c\right)=1$，那么对于每个 $i=1,2,\cdots ,n$，将 $S\left(i,c\right)$ 设为原来 $S\left(i,c\right)$ 和 $h_i\left(r\right)$ 之中的最小值。

若 $h_1=\left(x+1\right)\mathrm{mod}7,h_2=\left(3x+1\right)\mathrm{mod}7$，则经过两个哈希函数变换之后的特征矩阵M见表3，签名矩阵计算结果见表4，最后通过签名矩阵计算得到的Jaccard相似度见表5。

Table 3. Characteristic matrix M after two hash function transformations

表3. 经过两个哈希函数变换之后的特征矩阵M

Table 4. Signature Matrix S

表4. 签名矩阵S

Table 5. Jaccard similarity of text pairs

表5. 文本对的Jaccard相似度

2.6. LSH

若有 $N$ 个文本，进行两两相似度将需要比较 $N^2/2$ 次。这将极大增加计算量。LSH仅仅关注散列到同一个桶中的候选对，只检查这些候选对之间的相似度，它的基本思想就是将签名矩阵划分成b个行条，每个行条由r行组成。其中n = br，n为哈希函数的个数，即签名矩阵的行数。行条化策略能够使得相似列比不相似列更有可能成为候选对，从而大大减少文本对之间的比较次数。

2.7. 基于LSH技术的试题相似度检测算法

本文具体处理的过程见算法2。

算法2：基于LSH技术的试题相似度检测算法

输入：试题文本集合 $T_1,T_2,\cdots ,T_N$，Jaccard相似度阈值T^*

输出：相似试题文本对及相应的Jaccard估计相似度

Step1对所有试题文本进行中文分词，同时去除停用词，删除首尾空格

Step2把上一步中的结果转换成K-shingle集，得到特征矩阵M

Step3随机生成n_hashes个哈希函数 $h_1,h_2,\cdots ,h_{n\_hashes}$，根据算法1计算出签名矩阵S

Step4通过LSH得到所有的候选相似对，具体是将签名矩阵划分成n_bands个行条，每个行条由 $r=N/n\_bands$ 行组成，每个行条采用一个哈希函数对r个整数构成的列向量进行散列。若两向量相同，则会散列到同一个桶中，从而得到候选相似对。

Step5计算所有候选相似对的Jaccard相似度，若大于相似度阈值T^*，则两试题文本相似。

3. 实验结果及分析

本文采用的数据为《数据库课程》试题库，其中，判断题100道，填空题100道，选择题100道，解答题50道，综合题20道。考虑到组卷系统的大众化使用，更方便的在任何地方组卷，不借助除了Office之外的其它任何组件，所有功能全部在VBA中实现。程序采用了Word自带的中文分词功能，对试题内容去除停用词、删除空格。然后转换为K-shingle集，从而把所有的试题内容转换成了特征矩阵M，通过最小哈希(Minhash)计算出试题签名，最后通过LSH快速的找出候选相似对，同时计算出相应的Jaccard相似度。若该相似度大于给定的阈值，则输出。同时在组卷的过程中避免了相似试题，从而由此提高组卷的质量。

在实验中，设置题3与题5相似，题7与题9相似，题269与题271相似。哈希函数个数n_hashes为20个，LSH中的行条数n_bands为4个。运行结果如表6所示，其中的真实相似度是在不同Shingle长度下，对两Shingle集计算的Jaccard相似度。估计相似度是对两试题的最小哈希签名计算的Jaccard相似度。

Table 6. Results of different shingle lengths

表6. 不同shingle长度的程序运行情况

表6表明：由于试题文本一般不会太长，所以shingle长度不宜过大，设置为2比较合适。

当改变哈希函数n_hashes的数目时，运行情况表7所示。

表7表明：当哈希函数数目和行条数目较少时，真实度与近似相似有较大差距，且会漏检；随着哈希数目和行条数目的增多，差距越来越小。漏检率越来越低，精度越来越高。

组卷情况统计如图1所示。

Table 7. Shingle length is 2, the result of different hash functions and bands

表7. Shingle长度为2，不同哈希函数和行条数目的运行情况

Figure 1. The result of generating test paper

图1. 组卷情况

4. 结语

本文提出的基于LSH技术的试题相似度检测方法，实验结果表明，通过该方法检测能有效减少相似试题的重复率，并极大地减少相似对的比较次数，降低时间复杂度。

基金项目

楚雄师范学院校级教改项目，项目编号：1807。