Scoring Konsistenz innerhalb des Datensatzes

Question

Angenommen, ich habe eine Reihe von strukturierten Daten gegeben. Die Daten sind bekanntermaßen problematisch, und ich muss sie irgendwie auf Konsistenz abstufen. Zum Beispiel habe ich die Daten wie folgt:

fieldA | fieldB | fieldC 
-------+--------+------- 
foo | bar | baz 
fooo | bar | baz 
foo | bar | lorem 
..  | ..  | .. 
lorem | ipsum | dolor 
lorem | upsum | dolor 
lorem | ipsum | baz 

annehmen So ist die erste Zeile des richtigen Eintrags in Betracht gezogen, weil es relativ mehr Daten in dieser Kombination im Vergleich zu den Aufzeichnungen in der zweiten und dritten Reihe ist. In der zweiten Zeile sollte der Wert für fieldAfoo sein (inkonsistent aufgrund von Rechtschreibfehlern). In der dritten Zeile sollte dann der Wert fieldCbaz sein, wie andere Einträge im Datensatz mit ähnlichen Werten für fieldA (foo) und fieldB (bar) vorschlagen.

Auch in anderen Teil des Datensatzes, gibt es eine andere Kombination, die relativ häufiger (lorem, ipsum, dolor). Das Problem in den folgenden Datensätzen ist das gleiche wie das zuvor erwähnte, nur dass die Wertekombination unterschiedlich ist.

Ich habe zunächst alles in eine SQL-Datenbank ausgegeben und verwende Anweisungen mit GROUP BY, um die Konsistenz der Feldwerte zu überprüfen. Also wird es eine Abfrage für jedes Feld geben, das ich auf Konsistenz und für jeden Datensatz prüfen möchte.

SELECT fieldA, count(fieldA) 
FROM  cache 
WHERE  fieldB = 'bar' and fieldC = 'baz' 
GROUP BY fieldA 

Dann könnte ich überprüfen, ob der Wert von fieldA einen Datensatz mit dem Rest durch Bezugnahme des Datensatz auf das Objekt unter (verarbeitetes Ergebnis der vorherigen SQL-Abfrage) konsistent ist.

{'foo': {'consistency': 0.99, 'count': 99, 'total': 100} 
'fooo': {'consistency': 0.01, 'count': 1, 'total': 100}} 

es war jedoch sehr langsam (-Datensatz hat über 2,2 Millionen Datensätze, und ich bin Überprüfung 4 Felder, so etwa 9mil Abfragen machen), und einen halben Tag zu vollenden würde. Dann habe ich den SQL-Speicher auf elasticsearch ersetzt und die Verarbeitungszeit auf ungefähr 5 Stunden verkürzt, kann es irgendwie schneller gemacht werden?

Auch nur aus Neugier, erfinde ich hier ein Rad neu? Gibt es dafür ein Tool? Momentan ist es in Python3 mit elasticsearch implementiert.

Answer 1

Ich lese gerade Ihre Frage und fand es ziemlich interessant. Ich habe etwas ähnliches mit ntlk (Python Natural Language Toolkit) getan. Wie auch immer, in diesem Fall denke ich, Sie brauchen nicht die anspruchsvolle string comparison algorithms.

Also versuchte ich einen Ansatz mit dem Python difflib. Der Titel klingt vielversprechend: difflib - Helfer zur Berechnung Delta ¶

Die difflib.SequenceMatcher Klasse sagt:

Dies ist eine flexible Klasse für Paare von Sequenzen jeglicher Art, solange dem Vergleich Sequenzelemente sind hashbar.

Übrigens glaube ich, dass man, wenn man Zeit sparen möchte, 2.000.000 3-Tupel von (relativ kurzen) Strings einfach im Memory halten und verarbeiten kann. (siehe Tests und Mem Usage unten)

Also schrieb ich eine demo App, die 2.000.000 produziert (Sie können das variieren) 3-Tupel von zufällig leicht gemischten Streichern. Die gemischten Strings basieren auf einem Standard-Pattern wie Ihres: ['foofoo', 'bar', 'lorem'].Es vergleicht sie dann mit difflib.SequenceMatcher. Alles im Speicher. Hier

ist der Code vergleichen:

def compare(intuple, pattern_list): 
    """ 
    compare two strings with difflib 
    intuple: in this case a n-tuple of strings 
    pattern_list: a given pattern list. 
    n-tuple and list must be of the same lenght. 

    return a dict (Ordered) with the tuple and the score 
    """ 
    d = collections.OrderedDict() 
    d["tuple"] = intuple 
    #d["pattern"] = pattern_list 
    scorelist = [] 
    for counter in range(0,len(pattern_list)): 
     score = difflib.SequenceMatcher(None,intuple[counter].lower(),pattern_list[counter].lower()).ratio() 
     scorelist.append(score) 
    d["score"] = scorelist 
    return d 

Hier sind die Laufzeit und Speicherverbrauch Ergebnisse:

2000 3-Tupel: - Vergleichen Zeit: 417 ms = 0,417 sec - Mem Verwendung: 594 KiB

200.000 3-Tupel: - Zeit vergleichen: 5360 ms = 5,3 sec - Mem Verbrauch: 58 MiB

2.000.000 3-Tupel: - Vergleichen Zeit: 462241 ms = 462 sec - Mem Verbrauch: 580 MiB

es linear in der Zeit und Speichernutzung So skaliert. Und es braucht (nur) 462 Sekunden für 2.000.000 3-Tupel-Streicher zum vergleichen.

Das Ergebnis sieht wie folgt aus: (Beispiel für 200.000 Zeilen)

[ TIMIMG ] 
build    function took 53304.028034 ms 
[ TIMIMG ] 
compare_all   function took 462241.254807 ms 
[ INFO ] 

num rows: 2000000 
pattern: ['foofoo', 'bar', 'lorem'] 
[ SHOWING 10 random results ] 
0: {"tuple": ["foofoo", "bar", "ewrem"], "score": [1.0, 1.0, 0.6]} 
1: {"tuple": ["hoofoo", "kar", "lorem"], "score": [0.8333333333333334, 0.6666666666666666, 1.0]} 
2: {"tuple": ["imofoo", "bar", "lorem"], "score": [0.6666666666666666, 1.0, 1.0]} 
3: {"tuple": ["foofoo", "bar", "lorem"], "score": [1.0, 1.0, 1.0]} 
.... 

Wie Sie können Sie eine Punktzahl sehen erhalten auf der Grundlage der Ähnlichkeit der Zeichenfolge im Vergleich zu dem Muster. 1.0 bedeutet gleich und alles darunter wird schlechter, je niedriger das Ergebnis ist.

difflib ist bekannt als nicht der schnellste Algorithmus dafür zu sein, aber ich denke, 7 Minuten sind eine Verbesserung für einen halben Tag oder 5 Stunden.

Ich hoffe, das hilft Ihnen (und ist nicht komplett Missverständnis), aber es war eine Menge Spaß, dies gestern zu programmieren. Und ich habe viel gelernt. ;) Zum Beispiel, um die Speichernutzung mit tracemalloc zu verfolgen. Hab ich noch nie gemacht.

Ich ließ den Code auf github (as a one file gist) fallen.