Ceci peut être formulé comme un calcul de distance de Hamming par paire entre tous les enregistrements, en séparant les paires suivantes en dessous d'un certain seuil. Heureusement, numpy/scipy/sklearn a déjà fait le gros du travail. J'ai inclus deux fonctions qui produisent une sortie identique - l'une qui est entièrement vectorisée (mais consomme de la mémoire O(N^2) et une autre qui consomme de la mémoire O(N) mais qui est uniquement vectorisée le long d'une seule dimension. À votre échelle, vous ne voulez presque certainement pas la version entièrement vectorisée - elle donnera probablement une erreur OOM. Dans les deux cas, l'algorithme de base est le suivant :
- encoder chaque valeur de caractéristique comme une valeur entière (merci sklearn!)
- pour toutes les paires de lignes, calculer la distance de Hamming (somme des valeurs différentes)
- si deux lignes sont trouvées à une distance de Hamming inférieure ou égale à
seuil, écarter la dernière jusqu'à ce qu'il ne reste plus de lignes en dessous de ce seuil
code :
from sklearn.preprocessing import OrdinalEncoder
import pandas as pd
from scipy.spatial.distance import pdist, squareform
import numpy as np
def dedupe_fully_vectorized(df, seuil=1):
"""
version de consommation de mémoire entièrement vectorisée - il vaut mieux ne pas l'utiliser pour n > 10k
"""
# convertir les données du champ en entiers
enc = OrdinalEncoder()
X = enc.fit_transform(df.to_numpy())
# calculez la distance de Hamming (non normalisée) pour toutes les paires de lignes
d = pdist(X, metric="hamming") * df.shape[1]
s = squareform(d)
# s contient toutes les paires (j, k) et (k, j); exclure toutes les paires j < k comme "doublons"
s[np.triu_indices_from(s)] = -1
matrice_de_paires_de_doublons = (0 <= s) * (s <= seuil)
df_dupes = df[np.any(matrice_de_paires_de_doublons, axis=1)]
df_deduped = df.drop(df_dupes.index).sort_index()
return (df_deduped, df_dupes)
def dedupe_partially_vectorized(df, seuil=1):
"""
- Parcourir chaque ligne en commençant par la dernière ; examiner toutes les lignes précédentes pour les doublons.
- Si trouvé, il est ajouté à une liste d'indices de doublons.
"""
# convertir les données du champ en entiers
enc = OrdinalEncoder()
X = enc.fit_transform(df.to_numpy())
"""
- parcourir chaque ligne, en commençant par la dernière
- pour chaque `ligne`, calculer la distance de Hamming à toutes les lignes précédentes
- si une telle distance est inférieure ou égale à `seuil`, marquer `idx` comme un doublon
- la boucle se termine à la 2ème ligne (la 1ère n'est pas un doublon par définition)
"""
dupe_idx = []
for j in range(len(X) - 1):
idx = len(X) - j - 1
ligne = X[idx]
lignes_precedentes = X[0:idx]
dists = np.sum(ligne != lignes_precedentes, axis=1)
if min(dists) <= seuil:
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)
Testons maintenant les choses. D'abord, vérifions la cohérence :
df = pd.DataFrame(
[
["john", "doe", "m", 23],
["john", "dupe", "m", 23],
["jane", "doe", "f", 29],
["jane", "dole", "f", 28],
["jon", "dupe", "m", 23],
["tom", "donald", "m", 12],
["john", "dupe", "m", 65],
],
columns=["first", "last", "s", "age"],
)
(df_deduped_fv, df_dupes_fv) = dedupe_fully_vectorized(df)
(df_deduped, df_dupes) = dedupe_partially_vectorized(df)
df_deduped_fv == df_deduped # True
# df_deduped
# first last s age
# 0 john doe m 23
# 2 jane doe f 29
# 3 jane dole f 28
# 5 tom donald m 12
# df_dupes
# first last s age
# 1 john dupe m 23
# 4 jon dupe m 23
# 6 john dupe m 65
J'ai testé cela sur des dataframes jusqu'à ~40k lignes (comme ci-dessous) et cela semble fonctionner (les deux méthodes donnent des résultats identiques), mais cela peut prendre plusieurs secondes. Je ne l'ai pas essayé à votre échelle, mais cela peut être lent :
arr = np.array("abcdefgh")
df = pd.DataFrame(np.random.choice(arr, (40000, 15))
# (df_deduped, df_dupes) = dedupe_partially_vectorized(df)
Si vous pouvez éviter de faire toutes les comparaisons par paire, comme regrouper par nom, cela améliorera considérablement les performances.
amusement/problèmes avec l'approche
Vous pouvez remarquer que vous pouvez obtenir des "chaînes de Hamming" intéressantes (je ne sais pas si c'est un terme) où des enregistrements très différents sont connectés par une chaîne d'enregistrements ayant une seule différence de modification :
df_bad_news = pd.DataFrame(
[
["john", "doe", "m", 88],
["jon", "doe", "m", 88],
["jan", "doe", "m", 88],
["jane", "doe", "m", 88],
["jane", "doe", "m", 12],
],
columns=["first", "last", "s", "age"],
)
(df_deduped, df_dupes) = dedupe(df)
# df_deduped
# first last s age
# 0 john doe m 88
# df_dupes
# first last s age
# 1 jon doe m 88
# 2 jan doe m 88
# 3 jane doe m 88
# 4 jane doe m 12
Les performances seront grandement améliorées s'il y a un champ sur lequel vous pouvez regrouper (il a été mentionné dans les commentaires que name devrait être identique). Ici, le calcul par paire est n^2 en mémoire. Il est possible d'échanger quelque efficacité en temps contre de l'efficacité en mémoire au besoin.
