数据去重

七月 01, 2023

项目背景

建立深度学习模型，解决场景应用问题时，需要考量的重要指标之一便是模型的泛化性，要尽量避免模型在训练集上过拟合。在《Deduplicating Training Data Makes Language Model Better》这篇论文中提出，对训练数据进行重复数据消除会使语言模型变得更好，有助于减少训练集的过拟合。

同时，为了保证测试集能够真实反应模型的实际性能，还要杜绝测试集泄漏 ( 测试集部分样本原模原样地或者接近原模原样地出现在训练集中 ) 。

因此，训练集自身内部、训练集和测试集之间都要进行数据去重工作。

重复数据定义

训练集内部

字符串完全相等
仅是标点符号、空格等无意义字符不同
非核心语义替换的字词，如“的”等

训练集和测试集之间

字符串完全相等
仅是标点符号、空格等无意义字符不同
非核心语义替换的字词，如“的”等
具体问题场景 ( 工作中，负责 AWP 算术文字题 )，即题目场景及公式模版相同，替换了几处数字 ( 原则：是否能直接抄答案 )

调研去重算法

根据应用场景，主要是需要度量文本的相似性，常用的算法有 simHash、余弦相似度、IOU、编辑距离。

simHash

概述

simHash ，很早之前 google 用此算法进行重复网页去重，具体的原理：

最后的相似度比较就可以用最后的哈希对应位置上的值的相同个数做比较，即汉明距离。如果2个网页相同，则相似哈希值必定相同，如果存在极个别少量的权重低的词不同，它们的相似哈希值也可能会相同。

局部敏感哈希 (Locality-Sensitive Hashing)

两段文本，权衡精确度和复杂度，抽取特定维度的特征向量后，进行两两比较，复杂度依然很高。利用 hash 的方式生成指纹，比较指纹即可。但普通 hash 会把原始数值散列无序，导致 hash 后的指纹丧失了相似性的表征。而局部敏感哈希，如果原来的数据相似，hash 以后的数据也保持一定的相似性。而 SimHash 是 LSH 中的一种。

鸽笼原理

海明距离：hamming_distance(A, B) = count_1(A xor B) 。通过 simHash 得到每个样本的 hash 值，再通过度量海明距离计算相似度。然而海明距离并不能完全表征两者的相似程度，更多地用于缩小搜索空间。假如 hash 在 64 位，共将有 $2^{64}$ 个 hash 桶，计算某个样本的 top M 最相似，可以从最近的 hash 桶中搜索，最近的位本桶中的其他样本，其次为 1 位不同的其他 hash 桶，共 64 个，再其次为 2 位不同的桶，共 64 * 64 个……

按照作者论文中阐述，64 位 simhash ，海明距离在 3 以内的文本都可以认为是近重复文本。但是海量数据中，暴力两两计算海明距离也是成本高昂。根据抽屉原理，将 64 位的二进制串划分为 4 块，对于海明距离小等于 3 的两个样本之间，至少有一块区域是完全相同的。

由于事先并不知道完全相同的是哪一块，因此采用存储多份 table 的方式。比如存储 4 份，将每一段作为前 16 位。采用精确匹配的方式查找前 16 位。如果样本库中存有 $2^{34}$ ( 约 10 亿规模 ) 的哈希指纹，每个 table 会有 $2^{16}$ 个 cluster ，每个 cluster 中有 $2^{34} \div 2^{16}$ 个指纹，即 $2^{34-16} = 2^{18}=262144$ 个，(约 20 万规模) ，指定某个样本，分别根据 4 段对应的 16 位，到对应的 table 在对应的 cluster 进行寻找即可，极大的缩小搜索空间 ( 10 亿 ——-> 80万 )，大大减少了候选结果的规模，降低了计算海明距离的成本。

抽象出算法步骤

已知两篇文档 Simhash 值之间的海明距离越小，Jaccard 相似度越高，假设能够接受的最大海明距离为 K ，根据上面对 LSH 的描述，一种快速查找相似文档的方法：

对文档集中的每一篇文档：
- 计算一个 N 位的 SimHash 值
- 对值按位做 T 次随机排列，得到 T 个 N 位的值
- 对每个值取前 P 位生成 Key 存入词典，Value 为原 Simhash 值
查找时：
- 对查找文档生成一个 N 位的 Simhash 值
- 对值按位做 T 次随机排列，得到 T 个 N 位的值
- 对每个值取前 P 位生成 Key 查找词典，计算原 Simhash 值和 Value 间的海明距离
- 如果小于 K ，则加入到结果中

假设文档集中有一篇文档和查找文档的 Simhash 值间海明距离位 K ，则上述查找过程能够找到这个文档 (即 Key 命中) 的概率：

对某个排列，前 P 位相同的概率为：( 1 - K/N )^P
对某个排列，前 P 位不相同的概率为：1 - (1 - K/N)^P
对 T 次排列，前 P 位都不相同的概率为：(1 - (1 - K/N)^P)^T
对 T 次排列，前 P 位至少有一次相同的概率为：1 - (1 - (1 - K/N)^P)^T

因此，K 命中的概率为 1 - (1 - (1 - K/N)^P)^T ，N=64，P=16，K=3，T=8 时，概率为 0.9932

余弦相似度

余弦相似度，又称为余弦相似性，是通过计算两个向量的夹角余弦值来评估他们的相似度。

IOU

IOU，Intersection over Union ，交并比，此概念来自视觉图像领域，目标检测中度量两个 box 。在文本领域，更为简单。两个样本在字、或者词粒度上构建集合，交集的元素数目比上并集的元素数目，此值在 0～1 之间，值越大，此两条样本越相似。时间复杂度低，针对短文本场景，鲁棒性较高，比较适合海量数据上的去重。

资源：

视觉上的各种 iou 损失

编辑距离

典型的动态规划思路，最长公共子序列和最长公共子串的区别：

最长公共子序列：不要求子序列连续。
最长公共子串：要求子串一定连续。

资源：

去重过程

对训练集-训练集，训练集-测试集进行去重，效果最好的算法，应是编辑距离(最长公共子序列)，但数据量太过于庞大，直接两两构建 pair 对进行计算，时间上无法接受。故需要阶段性的去重，先用时间复杂度较低的算法尽可能将大概率重复的数据筛选出来，再用去重效果较好的算法进行验证，既降低复杂度，又能保证去重效果。调研的几种算法，在时间上，Iou > Simhash > Cos >> 编辑距离 ( 越大越快)。

构建验证去重效果的评测数据集

训练集-训练集评测数据集：从训练集中抽取 50 条样本，对于每条样本，在训练集中(剔除其本身)，利用编辑距离筛选最小的 top 10 的样本，构建 500 个 pair 对，进行是否重复的人工标注。
训练集-测试集评测数据集：从测试集中抽取 50 条样本，对于每条样本，在训练集中，利用编辑距离筛选最小的 top 10 的样本，构建 500 个 pair 对，进行是否重复的人工标注。

代码参考

整套工具包：code/de_dup_util.py
SimHash：simhash python 开源包，开源代码逻辑，后续深扒
余弦相似度：sklearn 中 TfidfTransformer、CountVectorizer、cosine_similarity、precision_recall_curve，开源代码逻辑，后续深扒

Iou

1	len(list(set(list1) & set(list2))) / len(list(set(list1) + set(list2)))

最长公共子序列

# 最长公共子序列
def longest_common_subsequence(str1, str2):
    matrix = [["" for x in range(len(str2))] for x in range(len(str1))]
    for i in range(len(str1)):
        for j in range(len(str2)):
            if str1[i] == str2[j]:
                if i == 0 or j == 0:
                    matrix[i][j] = str1[i]
                else:
                    matrix[i][j] = matrix[i-1][j-1] + str1[i]
            else:
                matrix[i][j] = max(matrix[i-1][j], matrix[i][j-1], key=len)

    cs = matrix[-1][-1]
    return cs

编辑距离

# 得到编辑距离
def levenshtein_distance(str1, str2):
    matrix = [[ i + j for j in range(len(str2) + 1)] for i in range(len(str1) + 1)]
    for i in range(1, len(str1)+1):
        for j in range(1, len(str2)+1):
            if(str1[i-1] == str2[j-1]):
                d = 0
            else:
                d = 1
            matrix[i][j] = min(matrix[i-1][j]+1, matrix[i][j-1]+1, matrix[i-1][j-1]+d)

    return matrix[len(str1)][len(str2)]

去重实验

去重算法的计算粒度，可以基于字 (N-gram)、也可以基于词 (结巴分词)

实验设置：

基于字 (N-gram) / 词 (N-gram) 的 Simhash
基于字 (N-gram) / 词 (N-gram) 的余弦相似度
基于字 (N-gram) 的 Iou

实验	粒度	召回率	保召回阈值(最小最大归一化)	准确率
Simhash	单元格	92.31%	0.19048	-
	词	84.62%	0.33333	-
余弦相似度	字	92.31%	0.47717	-
	词	7.69%	-	-
Iou	字	92.31%	0.63636	-
	词	-	-	-

通过对比，第一阶段利用时间复杂度较低的算法尽可能将大概率重复的数据筛选出来，基于字的粒度更好，因为场景是短文本，短文本经分词，特征更少，因此误差较大；此外，在保召回上，阈值较高的，被误召回的其实不重复的样本对较少，且 Iou 时间效率更好，所以最终第一阶段选择 Iou 。

第二阶段，利用第一阶段产生的超过阈值的候选重复样本集，经过编辑距离核实，去掉真正重复的样本。

考虑业务场景，对 AWP 算术文字题的解题模版作为特征，进行 groupby，之后再每组进行第一阶段、第二阶段的去重。之后，整体再进行第一阶段、第二阶段的去重。

去重效果

最终，训练集-训练集，认定重复的样本 pair 对，随机抽样 100 条，96% 的准确率；训练集-测试集，认定重复的样本 pair 对，随机抽样 100 条，98% 的准确率。

去除重复剩余的训练集中，随机抽样 10 条，每条利用编辑距离，取 top 10 最小的，共有 100 pair 对，仍然是重复的有 3 对，约 3%，主要是表述相差较大，比如场景不一样，但整体解法、思路是一样的。这应属于场景问题，整体去重工作还是得到预期收益的。如：“一条公路，已修的路程是未修的(2/5)，如果再修300米，就修好这条公路的一半，求这条公路的全长有多少米？”和“修一条路，已经修的是未修的(2/5)，再修300米，就正好修了这条路的一半，这条路有多少米？”，二者编辑距离为 16 ，但应该为重复样本。

查看评论