Ich habe Daten über Direktoren in vielen Firmen, aber manchmal sind "John Smith, Direktor von XYZ" und "John Smith, Direktor von ABC" die gleiche Person, manchmal auch nicht. Auch "John J. Smith, Direktor von XYZ" und "John Smith, Direktor von ABC" könnten dieselbe Person sein oder auch nicht. Oft ermöglicht die Untersuchung zusätzlicher Informationen (z. B. Vergleich von biographischen Daten zu "John Smith, Direktor von XYZ" und "John Smith, Direktor von ABC") zu klären, ob zwei Beobachtungen die gleiche Person sind oder nicht.
In diesem Sinne sammle ich Daten, die übereinstimmende Paare identifizieren. Angenommen, ich habe die folgenden übereinstimmenden Paare: {(a, b), (b, c), (c, d), (d, e), (f, g)} . Ich möchte die Transitivitätseigenschaft der Beziehung "ist dieselbe Person wie" verwenden, um "verbundene Komponenten" von {{a, b, c, d, e}, {f, g}} zu generieren. Das ist {a, b, c, d, e} ist eine Person und {f, g} ist eine andere Person. (Eine frühere Version der Frage bezog sich auf "Cliquen", die anscheinend etwas anderes sind; dies würde erklären, warum find_cliques in networkx die "falschen" Ergebnisse (für meine Zwecke) ergab.
Der folgende Python-Code erledigt den Job. Aber ich frage mich: Gibt es einen besseren (weniger rechenintensiven) Ansatz (z. B. mit Standard-oder verfügbaren Bibliotheken)?
Es gibt Beispiele hier und dort, die verwandt erscheinen (zB Cliquen in Python ), aber diese sind unvollständig, daher bin ich mir nicht sicher, auf welche Bibliotheken sie sich beziehen oder wie ich meine Daten für deren Verwendung einrichten soll.
Dies erzeugt die gewünschte Ausgabe: [Set(['a', 'c', 'b', 'e', 'd']), Set(['g', 'f'])] .
Dies erzeugt [set(['a', 'c', 'b', 'e', 'd']), set(['g', 'f'])] ):
Mit networkX:
%Vor%geben:
%Vor%Sie müssen jetzt den schnellsten Algorithmus überprüfen ...
OP:
Das funktioniert großartig! Ich habe das jetzt in meiner PostgreSQL-Datenbank. Ordnen Sie Paare einfach in eine zweispaltige Tabelle ein und verwenden Sie dann array_agg() , um an die PL / Python-Funktion get_connected() zu übergeben. Danke.
(Hinweis: Ich habe die Antwort bearbeitet, da ich dachte, dass dieser Schritt hilfreich wäre, aber zu lang für einen Kommentar.)
Ich glaube nicht (korrigiere mich, wenn ich falsch liege), dass dies direkt mit dem größten Cliquenproblem zusammenhängt. Die Definition von Cliquen (wikipedia) besagt, dass eine Clique "in einem ungerichteten Graph eine Teilmenge ihrer Ecken ist, so dass alle zwei Knoten in der Teilmenge durch eine Kante verbunden sind". In diesem Fall wollen wir herausfinden, welche Knoten sich (auch indirekt) erreichen können.
Ich habe eine kleine Probe gemacht. Es erstellt ein Diagramm und durchquert es auf der Suche nach Nachbarn. Dies sollte ziemlich effizient sein, da jeder Knoten nur einmal durchlaufen wird, wenn Gruppen gebildet werden.
%Vor%Wenn Ihr Datensatz am besten wie ein Diagramm modelliert und wirklich groß ist, ist vielleicht eine Diagrammdatenbank wie Neo4j geeignet?
Der Kommentar von DSM ließ mich nach Set-Konsolidierungsalgorithmen in Python suchen. Rosetta Code enthält zwei Versionen desselben Algorithmus. Beispiel Verwendung (die nicht-rekursive Version):
%Vor%Ich habe versucht, eine alternative Implementierung mit Wörterbüchern als Nachschlagevorgänge und möglicherweise eine kleine Reduzierung der Rechenlatenz.
%Vor% Und um mich selbst davon zu überzeugen, dass es das richtige Ergebnis liefert ( get_cliques1 hier ist Ihre ursprüngliche Python 2 Lösung):
Timing-Info in Sekunden (mit 10 Millionen Wiederholungen):
%Vor% Der Vollständigkeit und Referenz halber ist dies die vollständige Auflistung von cliques.py und get_times.py timing script:
Also zumindest in diesem erfundenen Szenario gibt es eine messbare Beschleunigung. Es ist zugegebenermaßen nicht bahnbrechend, und ich bin mir sicher, dass ich einige Performance-Bits in meiner Implementierung auf dem Tisch gelassen habe, aber vielleicht wird es dir helfen, über andere Alternativen nachzudenken?
Tags und Links python postgresql connected-components plpython clique