Python处理百万行数据集移除近重复行 现有代码结果不符求解

我有一个包含数百万行的数据集，需要删除行之间差异低于阈值x的近似重复行。
以下是数据集示例：

1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 3
1 1 1 1 1 1 1 1 1 1 1 1 2
1 1 1 1 1 1 1 1 1 1 1 3 1
1 1 1 1 1 1 1 1 1 1 1 3 3
1 1 1 1 1 1 1 1 1 1 1 3 2

上述样本中1-3行、4-6行仅最后一列存在差异，阈值设为1时期望输出2行（分别从两组中任选一行即可）；阈值设为2时所有行仅最后两列不同，期望仅输出1行，保留首行、末行或随机行均可。

我尝试了公开的近似去重代码，运行后仅返回1行，不符合预期，代码如下：

from sklearn.preprocessing import OrdinalEncoder
import pandas as pd
import numpy as np

# 加载数据
data = pd.read_csv(r'testfile.csv')
df = pd.DataFrame(data, columns=['File_1', 'File_2', 'File_3', 'File_4', 'File_5', 'File_6', 'File_7', 'File_8', 'File_9', 'File_10', 'File_11', 'File_12', 'File_13'])

def dedupe_partially_vectorized(df, threshold=1):
    """
    - 从最后一行开始遍历，检查所有之前的行是否为近似重复
    - 如果是，将索引加入重复索引列表
    """
    # 将字段数据转换为整数编码
    enc = OrdinalEncoder()
    X = enc.fit_transform(df.to_numpy())

    """
    - 从最后一行开始逐行遍历
    - 对当前行，计算和所有之前行的汉明距离
    - 如果存在任意距离小于等于阈值，标记当前行为重复行
    - 遍历到第二行停止，第一行默认不是重复项
    """
    dupe_idx = []
    for j in range(len(X) - 1):
        idx = len(X) - j - 1
        row = X[idx]
        prev_rows = X[0:idx]
        dists = np.sum(row != prev_rows, axis=1)
        if min(dists) <= threshold:
            dupe_idx.append(idx)
        dupe_idx = sorted(dupe_idx)
    df_dupes = df.iloc[dupe_idx]
    df_deduped = df.drop(dupe_idx)
    return (df_deduped, df_dupes)

# 输出结果到csv
(df_deduped, df_dupes) = dedupe_partially_vectorized(df)

print(df_deduped)

在上述示例数据集上运行代码后返回结果如下：

File_1  File_2  File_3  File_4  ...  File_10  File_11  File_12  File_13
0       1       1       1       1  ...        1        1        1        1

[1 rows x 13 columns]

Process finished with exit code 0

该结果不符合阈值为1时输出2行的预期。

测试其他实现后仍未完全移除近似重复项，以下数据集共7行，阈值为1时本应仅保留1行，实际保留了5行：

1 1 3 3 3 2 1 2 1 1 2 2 1 
1 3 3 3 3 2 1 2 1 1 2 2 1  
1 1 3 3 3 2 1 2 1 1 2 2 2  
1 1 3 3 3 2 3 2 1 1 2 2 1  
1 1 3 3 3 2 1 2 1 1 2 1 1  
1 1 3 3 3 2 1 2 1 1 2 3 1  
1 1 3 3 3 2 1 2 2 1 2 2 1

原有代码的逻辑缺陷在于，只要某行和任意之前的行汉明距离≤阈值，就直接判定为重复，这会导致所有和第一行差异≤阈值的行都会被删除，完全不符合「按相似簇分组，每簇留一个」的需求。你需要的本质是基于汉明距离的密度聚类，每个聚类簇保留一个样本即可。

可直接运行的实现 #

import pandas as pd
import numpy as np
from sklearn.preprocessing import OrdinalEncoder

def dedupe_by_similarity_cluster(df, threshold=1):
    # 编码非数值字段
    enc = OrdinalEncoder()
    X = enc.fit_transform(df.to_numpy())
    n_samples = X.shape[0]
    # 存储保留的簇代表行索引
    keep_idx = []
    for i in range(n_samples):
        # 第一行直接作为第一个簇的代表
        if not keep_idx:
            keep_idx.append(i)
            continue
        # 计算当前行和所有已保留簇代表的最小汉明距离
        min_dist = np.min(np.sum(X[i] != X[keep_idx], axis=1))
        # 最小距离大于阈值，说明属于新簇，加入保留列表
        if min_dist > threshold:
            keep_idx.append(i)
    return df.iloc[keep_idx]

# 测试示例1
data1 = [
    [1]*12 + [1],
    [1]*12 + [3],
    [1]*12 + [2],
    [1]*11 + [3,1],
    [1]*11 + [3,3],
    [1]*11 + [3,2]
]
df1 = pd.DataFrame(data1, columns=[f'File_{i}' for i in range(1,14)])
print("测试集1阈值=1结果：")
print(dedupe_by_similarity_cluster(df1, threshold=1)) # 输出2行，符合预期
print("测试集1阈值=2结果：")
print(dedupe_by_similarity_cluster(df1, threshold=2)) # 输出1行，符合预期

# 测试示例2
data2 = [
    [1,1,3,3,3,2,1,2,1,1,2,2,1],
    [1,3,3,3,3,2,1,2,1,1,2,2,1],
    [1,1,3,3,3,2,1,2,1,1,2,2,2],
    [1,1,3,3,3,2,3,2,1,1,2,2,1],
    [1,1,3,3,3,2,1,2,1,1,2,1,1],
    [1,1,3,3,3,2,1,2,1,1,2,3,1],
    [1,1,3,3,3,2,1,2,2,1,2,2,1]
]
df2 = pd.DataFrame(data2, columns=[f'File_{i}' for i in range(1,14)])
print("测试集2阈值=1结果：")
print(dedupe_by_similarity_cluster(df2, threshold=1)) # 输出1行，符合预期

大规模数据优化方案 #

如果需要处理数百万行的数据集，上述逐行对比的方式时间复杂度为O(nk)（k为保留的簇数量），可采用以下方案降低耗时：

• 使用局部敏感哈希（LSH）快速过滤距离肯定大于阈值的样本，仅对候选相似样本做精确距离计算
• 提前聚合完全重复的行，减少参与距离计算的样本量
• 采用多进程并行计算当前行与已保留行的距离

内容的提问来源于stack exchange，提问作者OldSport