4.3.2 相关研究及存在的问题
重复数据检测，亦称抄袭检测、复制检测、查重等，可通过文档相似度计算或者文档聚类来完成，而聚类往往需要直接或者间接的计算。用于相似度计算的元素可以是字符、单词及词序和语义（王腾等，2013；Song W et al，2014）、n-Grams（Choi DJ et al，2014）、频繁项集（Zhang W et al，2010）、句子（Lin YS et al，2013；李茹等，2013）、段落甚至是文档，对Web网页而言，还可以应用链接信息（Majid Y et al，2013）、特殊标签信息（Özel SA et al，2011）等。经典的文本聚类方法可以分为分割聚类[典型的如k-Means聚类算法（Yao MY et al，2012）]、分层聚类（典型的如BIRCH算法）等，也有不少研究者针对这些方法进行改进或者扩展，此外也有将多种聚类方法分阶段使用从而实现多方法融合的聚类方法。鉴于传统方法在大规模高维文档下的不足，一些新方法（Wang XM et al，2013；Liu YC et al，2011）也逐渐被提出来；鉴于传统方法无法有效的应用短文本（如句子）的缺陷，也有研究者提出了相应的新方法（Yang LB et al，2014）。在诸多的聚类方法中，出现了各种各样的相似度或者距离计算函数，其中最为经典的即欧几里得距离：设在n维空间中的两个点分别为：
，则其欧几里得距离可表示为：
显然，d（p，q）越小，意味着两个点之间的距离越近，反之则越远。可以将其推广到更为一般的闵可夫斯基距离，即：
当k=1时，即可得到曼哈顿距离，而当k=2时，即为上述欧几里得距离。此外，欧几里得距离的平方表达也是一种常用的距离度量方式。
在处理文本文档时，我们往往采用相似度计算，而不是距离计算的方法。计算相似度最常用的计算方式即余弦相似度公式。设在n维向量空间中的两个向量分别为：
，则两个向量Dp，Dq的相似度计算表达式如下：
两个向量的夹角越小，上述相似度值越接近1，则表明两个向量的相似度越高；当相似度值为1时，表示两个向量完全相同，亦即两个向量对应的文档完全一样。
在将上述计算方法应用于文本文档时，一个不可或缺的环节即将文本文档向量化。一种常见的向量化方式是采用分词手段，在去除停用词后，获取高频词。当然也有一些其他的关键词或特征获取方式，如在文献（Carretero-Campos C et al，2013；Gong LH et al，2011）中，通过给不同的词或特征赋予不同的权重，进而使用这些词或特征作为向量空间的基底并完成文本的向量化，例如文献（Lin YS et al，2013）；此外也有一些其他的向量化方式。但是这些方式几乎都面临着两个较为普遍性的问题：其一是特征项难以确定，其二是特征项的维数往往很大，需要降维以降低计算复杂度，改善计算效果，且在降维的同时不能丢失文档的某些本质信息，这些环节在很多情形下都会造成较大障碍，且无法脱离人工的参与，工作量较为繁重。鉴于此，文献（Bharti KK et al，2014）提出了一种针对文本聚类的无监督降维方法，以减少在聚类过程中的人工工作量。
基于上述这些问题，我们提出了一种基于随机n-Grams的文本相似度计算方法（王贤明等，2013），简称R-Grams文本相似度算法。这是一种可应用于长文本相似度计算的新型算法，通过随机策略，充分利用了短n-Grams的细粒度检测特性和长n-Grams的高效检测特性，具有语言无关性、精度和速度易调节等特点。针对该算法中n-Grams的随机抽取这一核心部分，笔者提出了一种位置约束随机策略。通过实验探究了在位置约束下的随机策略对相似度算法的影响，并对结果做了深入分析。实验结果表明：R-Grams文本相似度算法在各种约束随机策略下，基本表现出与无约束随机策略下相似的结果精度，可见该算法具有很强的抗干扰能力。不过在该文直接采用的是无任何约束的随机策略，并未就n-Grams的随机选取策略做深入细致地探讨，本节将针对这一关键问题展开研究。