Matrixmultiplikation in großem Maßstab mit Pyspark (oder - wie zwei große Datensätze von Firmennamen abgeglichen werden)

Spark und Pyspark bieten eine hervorragende Unterstützung für die zuverlässige Verteilung und Parallelisierung von Programmen sowie für viele grundlegende algebraische Operationen und Algorithmen für maschinelles Lernen.

In diesem Beitrag beschreiben wir die Motivation und die Mittel zur Durchführung des namensweisen Abgleichs zweier großer Datensätze von Firmennamen mithilfe von Spark.

Motivation zuerst

Unser Ziel ist es, zwei große Gruppen von Firmennamen zuzuordnen. Wir sehen uns zwei lange Listen mit Firmennamen an: Liste A und Liste B. Ziel ist es, Unternehmen von A mit Unternehmen von B abzugleichen.

Normalerweise hätten wir so etwas:

Liste A | Liste B
---------------------
GOOGLE INC. | Google
MEDIUM.COM | Medium Inc
Amazon Labs | Amazonas
Google, inc |
Yahoo |
             | Microsoft

In diesem Beispiel besteht unser Ziel darin, sowohl GOOGLE INC. Als auch Google Inc. (von Liste A) mit Google (von Liste B) abzugleichen. und MEDIUM.COM auf Medium Inc abzustimmen; und Amazon Labs zu Amazon, etc…

Bei diesem einfachen Beispiel fallen einige Dinge auf:

  • Es ist möglich, dass mehr als eine Firma von A zu einer Firma von B passt. Es ist eine Eins-zu-Eins-Beziehung.
  • Firmennamen sind in den meisten Fällen für Menschen leicht zuzuordnen (z. B. Amazon Labs zu Amazon), für Computer jedoch nicht so einfach (woher weiß der Computer, dass "Labs" in diesem Fall unbedeutend sind und "Amazon" nur eine Abkürzung für „Amazon Labs“?)
  • Nicht alle Unternehmen aus A haben Übereinstimmungen mit B, und nicht alle Unternehmen aus B stimmen mit A überein. In unserem Beispiel stimmt Yahoo aus Liste A nicht mit keinem anderen Unternehmen auf B überein, und Microsoft aus B stimmt auch nicht mit keinem Unternehmen auf A überein .
  • Jedes Element aus Liste A sollte höchstens eine Übereinstimmung mit dem B aufweisen. Das Gegenteil ist nicht der Fall. Viele Unternehmen aus A könnten auf B zu einem einzigen Unternehmen zusammengefasst werden.

Erster Versuch - Trivial Match

OK, Zuerst dachten wir, wir würden versuchen, die einfachste und trivialste Lösung zu finden, um zu sehen, wie gut sie funktioniert, wenn nicht zumindest für irgendetwas anderes, um eine Grundlage für zukünftige Versuche zu schaffen. Am einfachsten ist es, nur die Groß- und Kleinschreibung zu berücksichtigen. Ordnen Sie einfach die Saiten von A den Saiten von B zu.

Präzision und Rückruf

Es gibt zwei relevante Maßnahmen: Präzision und Rückruf. Präzision ist "wie viele Fehler haben wir gemacht (nicht gemacht)", oder mit anderen Worten - bei allen Übereinstimmungen, wie viele von ihnen waren in der Tat richtige Übereinstimmungen - Präzise Übereinstimmungen. Bei Präzision geht es also um falsch positive Ergebnisse.

Auf der anderen Seite sei daran erinnert, „wie viele Übereinstimmungen hätten gefunden werden sollen, aber verpasst wurden“. Der Rückruf handelt also von den falschen Negativen.

Der erste unbedeutende Versuch war, wie erwartet, hochpräzise, ​​aber wenig rückrufbereit. Wenn wir uns eine kurze Liste von Beispielfirmen ansehen, würde diese mit null Elementen von A bis B übereinstimmen. Natürlich würde es im realen Szenario etwas mehr als null sein, aber es ist leicht zu erkennen, dass der Rückruf aufgrund vieler kleiner möglicher Abweichungen bei den Firmennamen gering bleiben würde.

Eine einfache Verbesserung wäre das Entfernen von Stoppwörtern.

Wörter stoppen

Was sind Stoppwörter? Stoppwörter sind Wörter, die vor der Verarbeitung verschiedener NLP-Algorithmen entfernt werden, da sie keine Informationen hinzufügen. In der Regel fügen sie nur Rauschen hinzu. In einfachem Englisch sind Stoppwörter normalerweise das "von", "für" "wenn" usw. der Sprache. Dies sind sehr häufige Wörter, die häufig verwendet werden, aber für viele NLP- und IR-Algorithmen werden dann keine Informationen hinzugefügt. Sie sorgen für korrekte syntaktische Sätze und beeinflussen in vielen Fällen die Semantik. Auf der Ebene vieler NLP-Prozessoren, die die tatsächliche Syntax nicht berücksichtigen, sind sie jedoch bedeutungslos.

In unserem Fall sind die Stoppwörter nicht das "Wenn", "Von" oder "Für", was typisch für Englisch ist, sondern das "Inc" und "Llc" aus der Firmenerweiterung. Daher besteht unsere einfache Verbesserung darin, einfach alle diese Firmenerweiterungen zu entfernen und die einfache Zeichenkettengleichung noch einmal zu versuchen.

Dies hat in der Tat geholfen, und wie Sie in unserem Beispiel sehen können, hat dies dazu beigetragen, "Google Inc." mit "Google" in Verbindung zu bringen. Durch einfaches Entfernen von Interpunktionszeichen und korrekte Token-Kennzeichnung können wir auch "Google Inc." mit "Google" in Verbindung bringen. Dies stimmt jedoch immer noch nicht mit „Amazon Labs“ und „Amazon B / C Labs“ überein. Dies ist kein Stoppwort in dem Sinne, dass es sich nicht um eine übliche Firmenerweiterung handelt. Wie sich herausstellt, sind "Amazon Labs" nicht nur ein zufälliges Beispiel. Viele Firmennamen haben diese Variationen in ihren Namen, die sich in einem Datensatz, aber nicht in anderen Datensätzen manifestieren. Fazit: Wir müssen einen Weg finden, „darüber hinaus zu schauen“, die „Labs“ in „Amazon Labs“ zu ignorieren.

Treffen wir uns mit der Wissenschaft.

Die Wissenschaft

Was wir hier sehen, ist das Problem, N Dokumente von Liste A zu M Dokumenten in Liste B in einer Beziehung von vielen zu eins zuzuordnen. Unser Matching-Algorithmus muss jedoch "intelligent" sein, in dem Sinne, dass er in der Lage sein muss, zwischen "wichtigen Wörtern" und "unwichtigen Wörtern" zu unterscheiden. Wir müssen einen Weg finden, um dem Computer mitzuteilen, dass "Labs" in "Amazon Labs" unbedeutend sind, "Amazon" jedoch tatsächlich von Bedeutung ist. Wir würden die Namen auch trivial in kleinere Token unterteilen, indem wir sie nach Leerzeichen, Interpunktion usw. aufteilen, sodass "medium.com" in "medium" und "com" aufgeteilt würde.

Wissenschaft zur Rettung!

TF-IDF

Zu diesem Zweck verwenden wir ein allgemeines Schema in der Information Retrieval-Theorie namens TF-IDF. TF-IDF steht für Term Frequency - Inverted Document Frequency. Begriff Häufigkeit bedeutet einfach "wie oft dieses Wort in diesem Dokument vorkommt" (unsere Dokumente sind nur Firmennamen, es handelt sich also um sehr kurze "Dokumente"). Im Fall von "amazon labs" haben wir also nur zwei Wörter im Dokument "amazon" und "labs" und ihre Häufigkeit ist einfach 1 und 1. (Wenn der Name des Unternehmens übrigens zufällig "amazon labs" ist amazon “, dann wären es 2 für„ amazon “und 1 für„ labs “.) Genau darum geht es bei TF, ganz einfach: Zählen Sie die Häufigkeit von Begriffen im Dokument.

Inverted Document Frequency ist das eigentliche Problem. Die invertierte Dokumenthäufigkeit überprüft alle "Dokumente" (auch Korpus genannt, alle Firmennamen) und testet, wie oft das Wort "Labs" in allen von ihnen vorkommt. Wenn das Wort „amazon“ nur in einem einzigen Dokument vorkommt, bedeutet dies, dass „amazon“ ein bedeutendes Wort ist, das Wort „labs“ jedoch in vielen anderen Dokumenten vorkommt (z. B. verwenden viele Unternehmen das Wort „labs“ als Teil ihres Dokuments) name) bedeutet dies, dass das wort „labs“ keine bedeutung hat. IDF ist genau das - wie viele Dokumente enthält das Wort?

TF-IDF ist die TF des Begriffs, geteilt durch die IDF des Begriffs. Es bietet ein gutes Maß dafür, wie wichtig oder wie wichtig Wörter im Kontext bestimmter Dokumente sind.

Es ist einfach, die TF-IDF-Matrix für eine Reihe von Dokumenten zu berechnen. Es gibt fertige Bibliotheken, die dies tun, und wir haben dafür die Implementierung von scikit-learn verwendet.

Die TF-IDF-Matrix ist eine zweidimensionale Matrix, in der die Zeilen Dokumente (in unserem Fall Firmennamen) und die Spalten eindeutige Token (oder Wörter) darstellen. Wenn wir die TF-IDF-Matrix unseres kleinen Korpus aus Liste A erstellen wollten, würde dies ungefähr so ​​aussehen (nach dem Entfernen von Stoppwörtern, Interpunktion und Herabsetzen von allem):

           | google | mittel | com | yahoo | amazon | Labore
-------------------------------------------------- ---------
GOOGLE INC. | 1 0 0 0 0 0
MEDIUM.COM | 0,77,63 0 0 0
Amazon Labs | 0 0 0 0 .7 .7
Google, inc | 1 0 0 0 0 0
Yahoo | 0 0 0 1 0 0
com | 0 0 1 0 0 0

Hier ist der Code:

aus sklearn.feature_extraction.text importieren Sie TfidfVectorizer
matrix = vectorizer.fit_transform (['GOOGLE', 'MEDIUM.COM', 'Amazon Labs', 'Google', 'Yahoo', 'com'])

Die erstellte Matrix lautet NxM, wobei N = Anzahl der Unternehmen und M = Anzahl der eindeutigen Token.

Sie werden feststellen, dass wir eine weitere (erfundene) Firma mit dem Namen "com" hinzugefügt haben. Wir haben das gemacht, um eine wichtige Eigenschaft von TF-IDF zu demonstrieren. Wir verwenden TF-IDF, um signifikante und nicht signifikante Token in den Dokumenten zu unterscheiden. Ein wichtiges Token in einem Dokument ist ein Token, das nicht nur häufig im Dokument vorkommt, sondern auch im gesamten Korpus relativ selten vorkommt. Wenn ein Begriff mehrmals im Korpus vorkommt, verliert er für dieses Dokument an Bedeutung. Wir haben die zusammengesetzte Firma „com“ hinzugefügt, damit „Medium“ innerhalb von „Medium.com“ an Bedeutung gewinnt. (Sie werden feststellen, dass das mittlere Gewicht 0,77 und das COM-Gewicht 0,63 beträgt. Dies ist darauf zurückzuführen, dass das COM in einem anderen Dokument angezeigt wird und der IDF daher niedriger ist.)

In der Praxis gibt es natürlich Dutzende oder Hunderte von Firmennamen mit dem Token "com" oder "labs", sodass der Name "Medium.com" einen wesentlichen Unterschied zwischen "com" und "Medium" aufweist.

Kosinus-Ähnlichkeit

Der nächste Schritt nach der Berechnung der TF-IDF-Matrix für beide Seiten (beide Listen A und B von Unternehmen) ist die Multiplikation der Matrizen.

Das Multiplizieren von Matrizen liefert ein interessantes Maß, das als Cosinus-Ähnlichkeit bezeichnet wird. Die Cosinus-Ähnlichkeit ist eine einfache Ähnlichkeitsmessung, die zwischen 0 und 1 liegt. Ein Wert von 1 zeigt identische Elemente an und ein Wert von 0 zeigt völlig unterschiedliche Elemente an (genau wie die Cosinus-Trigger-Funktion). Das Multiplizieren der Matrizen liefert die Kosinusähnlichkeit zwischen jedem Element in Liste A und jedem Element in Liste B. Tatsächlich multiplizieren wir A mit B.T (B.transponieren), so dass die Dimensionen passen. Das Interessante an der Cosinus-Ähnlichkeit zwischen TF-IDF-Matrizen ist, dass das Ergebnis eine Ähnlichkeitsmatrix zwischen jedem Element in A und jedem Element in B ist, wobei die Bedeutung von Tokens in den Namen berücksichtigt wird. Normalerweise bedeutet ein Ergebnis von> .8 eine gültige Übereinstimmung.

Glücklicherweise bietet das Python-Paket sklearn eine einfache cosine_similarity-Funktion, die zwei Matrizen akzeptiert und die Cosinus-Ähnlichkeit dieser beiden ergibt. Hier ist ein Demo-Code:

aus sklearn.feature_extraction.text importieren Sie TfidfVectorizer
importiere cosine_similarity aus sklearn.metrics.pairwise
a = vectorizer.fit_transform (['aa', 'bb', 'aa bb', 'aa aa bb'])
b = vectorizer.fit_transform (['aa', 'bb'])
cosimilarities = cosine_similarity (a, b)

Das Ergebnis ist eine Matrix von Ähnlichkeiten zwischen jedem Element in A und jedem Element in b.

           aa | bb
----------------------
aa | 1 | 0
bb | 0 | 1
aa bb | .7 | .7
aa aa bb | .89 | .44

Wie erwartet ist das Wort „aa“ von a dem Wort „aa“ von b sehr ähnlich (beachten Sie die 1). Sie können auch sehen, dass "aa bb" sowohl "aa" als auch "bb" ähnlich ist, und das macht auch Sinn. Und schließlich werden Sie feststellen, dass "aa aa bb" eine höhere Ähnlichkeit mit "aa" aufweist als mit "bb". Das alles macht Sinn.

Fassen wir die Wissenschaft hier zusammen. Zuerst nehmen wir zwei Dokumentenlisten und berechnen für jeden Satz die TF-IDF-Matrix *. Dann multiplizieren wir die beiden Matrizen, um ihre Kosinusähnlichkeit zu erhalten. Dabei handelt es sich um eine Matrix, die die Ähnlichkeit zwischen jedem Dokument in A und jedem Dokument in B beschreibt.

Zweiter Versuch - Zahlenmatrixmultiplikation

Nachdem wir die Wissenschaft gesehen haben, wollen wir dies in der Praxis versuchen. Der nächste Versuch ist, alle realen Firmen aus Liste A und alle realen Firmen aus Liste B zu laden und mit der Funktion cosine_similatiry zu multiplizieren.

Leichter gesagt als getan.

Im kleinen Maßstab funktioniert das einfach und es funktioniert sehr gut. Zum Beispiel mit ein paar tausend Firmen auf jeder Seite, die funktionieren würden. Bei unserem Datensatz, in dem sich in jeder Liste ein paar hunderttausend Namen befinden, bis zu einigen Millionen, wird dies jedoch zu einer Herausforderung.

Die einfache Berechnung der TF-IDF ist auch bei so großen Datenmengen auf einem einzelnen Host möglich (mein Laptop läuft so einfach in wenigen Sekunden). Das Multiplizieren der Matrizen ist jedoch die eigentliche Herausforderung.

Lokale Multiplikation skaliert nicht

Nehmen wir an, wir haben 1 Million (10⁶) Namen in jeder Liste. Jede Matrix wäre dann ungefähr in der Größenordnung von 10⁶ x 10⁶ (da die Anzahl der eindeutigen Token in Bezug auf die Anzahl der Unternehmen aufgrund der Eindeutigkeit der Namen ähnlich ist). Das Erzeugen einer 10⁶ x 10⁶ Matrix im Speicher bedeutet 10¹² Floats. Ein Python-Float benötigt 16 Bytes, sodass wir am Ende 16 * 10¹² Bytes haben, was ~ 4PT (vier Petabytes) RAM entspricht. Können wir eine 4PT-Matrix im Speicher behalten? Na klar nicht, jedenfalls nicht auf meinem schäbigen Laptop. Aber - es gibt einen Trick. Wir müssen nicht alles im Gedächtnis behalten. Beachten Sie, dass die Matrix zwar 1M auf 1M ist, in der Praxis jedoch meistens mit Nullen gefüllt ist. Warum sollten wir uns also die Mühe machen, all diese Nullen im Speicher zu behalten? Wir können stattdessen eine spärliche Darstellung der Matrix verwenden, in der wir anstatt die zweidimensionale Matrix mithilfe von Arrays von Arrays im Speicher zu halten, nur die Koordinaten der Nicht-Null-Elemente verfolgen und davon ausgehen, dass alle anderen gerecht sind Nullen. Dies ist ideal, um den Speicherbedarf gering zu halten und schnelle Matrixmultiplikationsoperationen auszuführen. Und genau das macht sklearn bereits. Wenn wir die Matrizen als spärliche Matrizen belassen, müssen wir nur etwa 1 Million Floats (Werte) plus 2 Millionen Integer (Indizes von Nicht-Null-Elementen) zuweisen, aber insgesamt sind es etwa 24 Millionen Byte, was ziemlich einfach ist.

Aber - die beiden Matrizen zu multiplizieren, selbst wenn sie dünn sind, würde mindestens 10¹² Operationen bedeuten (wenn wir mit den Nullen klug sind). Das ist etwas schwieriger. Und obwohl Numpy (der unter Sklearn liegt) sehr gut darin ist, so schnell zu rechnen, ist dieses Ding selbst für Numpy eine Herausforderung.

Wir haben das versucht - einfach diese beiden Matrizen multiplizieren. Es funktioniert gut für genügend kleine Matrizen, aber bei einigen Zahlen (die viel kleiner sind als das, was wir wollen) begann es zu scheitern und der Speicher geht zur Neige. Jetzt hätten wir das herausfinden können, indem wir eine der Matrizen in kleinere Teile aufgeteilt und eine Zahl oder Multiplikationen nacheinander ausgeführt und dann alle Dinge zusammengefasst hätten. Aber diese Art hat uns daran erinnert, dass wir diese Art von System bereits kennen, das heißt Spark.

Dritter Versuch - Funkenmatrixmultiplikation

Spark eignet sich hervorragend für stark parallelisierte speicherintensive Berechnungen. Es verfügt über einen BlockMatrix-Datentyp, der eine Multiplikationsoperation implementiert. Sieht genau so aus, wie wir gesucht haben! OK, also erstellen wir die TF-IDF-Matrizen und konvertieren sie in Spark's BlockMatrix und führen a.multiply (b.transpose ()) aus, was mehr oder weniger der cosine_similatiry entspricht.

# Pseudocode ...
a_mat = tfidf_vect.fit_transform ([..., ..., ...])
b_mat = tfidf_vect.fit_transform ([..., ..., ...])
a_block_mat = create_block_matrix (a)
b_block_mat_tr = create_block_matrix (b.transpose ())
cosimilarities = a_block_mat.multiply (b_block_mat_tr)

Das scheint einfach zu sein und ist es auch. Aber es gibt natürlich ein "aber" ... dieses Ding ist zwar einfach und funktioniert aus mathematischer Sicht korrekt - es skaliert jedoch nicht ... Wir können große Matrizen multiplizieren, aber nicht so groß, wie wir möchten . Wir haben leider versucht, mit den Blockgrößen usw. zu spielen. Bei Eingaben, die groß genug sind, schlägt dies entweder mit Fehlern aufgrund von unzureichendem Speicherplatz oder nur mit langen Läufen fehl, die niemals enden (Stunden und Stunden).

Was ist das Problem? Kann die Spark-Skala nicht funktionieren?

Natürlich kann sich der Funke absetzen. Aber Sie müssen es mit Bedacht anwenden, dumm ... Das Problem bei BlockMatrix ist, dass Spark zur Implementierung der Multiplikationsoperation die spärlichen Blöcke der Matrix in dichte (Sub-) Matrizen umwandelt. Und obwohl der größte Teil unserer Matrix aus Nullen besteht, würde spark dennoch alle diese Nullen in eine dichte Darstellung umwandeln, was entweder zu viel Speicher verbrauchen würde oder, wenn wir die Größe der Blöcke klein halten, zu viele Operationen, Neupartitionen usw. zur Folge haben und ausgeführt werden würden für immer.

Spark unterstützt Sparse-Matrizen, aber diese Matrizen implementieren die Multiplikationsoperation (auch Punktoperation genannt) nicht, und die einzige verteilte Matrix, die die Multiplikationsoperation zum Zeitpunkt des Schreibens implementiert, ist die BlockMatrix, in die, wie erwähnt, die Sparse-Repräsentation konvertiert wird dichte Darstellung, bevor sie multipliziert werden. Wir sollten beachten, dass es in der Spark-Community Diskussionen darüber gegeben hat, wie eine Multiplikation mit verteilter, spärlicher Matrix implementiert werden kann. Zum Zeitpunkt dieses Schreibens war dies jedoch noch nicht implementiert.

BlockMatrix.multiply () ist fehlgeschlagen. Was kommt als nächstes?

Vierter Versuch - und der Gewinner ist ...

Unser vierter und letzter Versuch war erfolgreich. Die Idee ist, Spark mit Numpy zu kombinieren. Unsere Tests zeigen, dass numpy in der Lage ist, eine kleinere Matrix mit einer größeren Matrix zu multiplizieren. Wenn wir also nur einen kleinen Teil der Matrix A nehmen und diesen mit der Matrix B multiplizieren, würde dies funktionieren und numpy würde nicht explodieren. Und wenn Sie sich an Ihre Algebra-Lektionen erinnern, können Sie die Matrizen Vektor für Vektor so algebraisch multiplizieren, dass dies immer noch richtig wäre. Die Idee besteht darin, nur eine der Matrizen in kleinere Teile aufzuteilen und dann jeden Spark-Worker die Multiplikation auf seinem Block ausführen zu lassen und dann nur die Schlussfolgerung zurückzugeben, z. die Schlussfolgerung könnte sein, dass der Name bei A [13] mit dem Namen bei B [21] übereinstimmt usw.

Broadcast und Parallelisierung zur Rettung

Spark bietet zwei nützliche Funktionen: Senden und Parallelisieren. Broadcast sendet einfach die exakt gleichen Daten an alle Mitarbeiter. Wir verwenden Broadcast, um Matrix B an alle Worker zu senden, sodass alle Worker die vollständige B-Matrix haben. Parallelisieren teilt die Daten in Partitionen auf und sendet jede Partition an einen anderen Worker. Wir verwenden Parallelisieren, um Blöcke von A an die Arbeiter zu senden, so dass jeder Arbeiter nur einen kleinen Block von A hat.

Hier ist der allgemeine Überblick:

  1. Berechnen Sie die TF-IDF-Matrizen auf dem Treiber.
  2. Matrix A parallelisieren; Broadcast-Matrix B
  3. Jeder Worker ordnet seinen Arbeitsblock jetzt flach zu, indem er seinen Matrixblock A mit der gesamten Matrix B multipliziert. Wenn also ein Worker A [0:99] bearbeitet, multipliziert er diese hundert Zeilen und gibt das Ergebnis von beispielsweise A [13 zurück ] entspricht einem in B [21] gefundenen Namen. Die Multiplikation erfolgt mit numpy.
  4. Der Fahrer sammelte alle Ergebnisse der verschiedenen Mitarbeiter und passte die Indizes (A [13] und B [21]) an die tatsächlichen Namen im Originaldatensatz an - und fertig!

Diese Methode funktioniert sehr gut und als sie zum ersten Mal ausgeführt wurde, war es eine so schöne Überraschung, dass wir dachten, es hat einfach nicht funktioniert (aber es hat…). Im Vergleich zu den vorherigen Methoden, die entweder stundenlang ausgeführt wurden (und nicht beendet wurden) oder nur noch wenig oder nur noch wenig Arbeitsspeicher hatten, konnte diese Methode ihre Berechnung in wenigen Minuten abschließen. Natürlich hängt es von der Größe der Daten und der Größe des Spark-Clusters ab, aber alles in allem lief es sehr gut.

Momentan ist der einzige Engpass der Treiber, der TF-IDF-Matrizen berechnet, und an dieser Front haben wir immer noch jede Menge Spielraum, da diese Berechnung für Sklearn noch recht einfach ist. (Randnotiz: Spark implementiert auch die verteilte TF-IDF-Berechnung, musste jedoch nicht verwendet werden.)

Hier ist der Pseudocode zur Veranschaulichung unserer Lösung:

aus sklearn.feature_extraction.text importieren Sie TfidfVectorizer
aus sklearn.feature_extraction.text CountVectorizer importieren
importiere cosine_similarity aus sklearn.metrics.pairwise
# Diese werden realistisch aus Dateien oder Datenrahmen gelesen.
a = ['google inc', 'medium.com', ...]
b = ['google', 'microsoft', ...]
stopwords = ['ltd', ...]
vect = CountVectorizer (stop_words = stopwords)
# Dies kann mit weniger Speicheraufwand durch Verwendung eines Generators erreicht werden
Wortschatz = vect.fit (a + b) .vocabulary_
tfidf_vect = TfidfVectorizer (stop_words = stopwords,
                             Wortschatz = Wortschatz)
a_mat = tfidf_vect.fit_transform (a)
b_mat = tfidf_vect.fit_transform (b)
a_mat_para = parallelize_matrix (a_mat, rows_per_chunk = 100)
b_mat_dist = broadcast_matrix (a_mat)
a_mat_para.flatMap (
        Lambda-Submatrix:
        find_matches_in_submatrix (csr_matrix (submatrix [1],
                                             Form = Untermatrix [2]),
                                   b_mat_dist,
                                   Untermatrix [0]))
def find_matches_in_submatrix (Quellen, Ziele, input_start_index,
                              Schwelle = .8):
    cosimilarities = cosine_similarity (Quellen, Ziele)
    für i, Cosimilarity in enumerate (Cosimilarities):
        cosimilarity = cosimilarity.flatten ()
        # Finde die beste Übereinstimmung mit argsort () [- 1]
        target_index = cosimilarity.argsort () [- 1]
        source_index = input_start_index + i
        Ähnlichkeit = Cosimilarität [target_index]
        if cosimilarity [target_index]> = threshold:
            Ausbeute (source_index, target_index, Ähnlichkeit)
def broadcast_matrix (mat):
    bcast = sc.broadcast ((mat.data, mat.indices, mat.indptr))
    (Daten, Indizes, indptr) = bcast.value
    bcast_mat = csr_matrix ((Daten, Indizes, indptr), shape = mat.shape)
    return bcast_mat
def parallelize_matrix (scipy_mat, rows_per_chunk = 100):
    [rows, cols] = scipy_mat.shape
    i = 0
    Submatrizen = []
    während ich 

Sie werden feststellen, dass wir die Matrix nach der Übertragung und Parallelisierung wieder zu scipy csr_matrix zusammensetzen, von der sie stammt. Also, was wir im Grunde tun, ist - wir serialisieren die Matrizen über den Draht und setzen sie dann auf der anderen Seite wieder zusammen, auf den Arbeitern. Die Serialisierung ist effizient, da wir nur die Nicht-Null-Elemente der Sparse-Matrix senden müssen. Für eine Matrix von 1 Mio. Elementen senden wir also nur ca. 1 Mio. Floats zusammen mit 2 Mio. Ints, was definitiv in der Komfortzone von Spark liegt.

Fazit

Wir beschreiben eine Methode zum Ermitteln der Ähnlichkeit zwischen zwei Listen von Zeichenfolgen A und B, die Firmennamen beschreiben. Wir haben TF-IDF und Cosinus-Ähnlichkeit als Ähnlichkeitsfaktor verwendet.

Als nächstes zeigen wir verschiedene Versuche zur skalierbaren Implementierung der Matrixmultiplikation unter Verwendung von Spark und die Gewinnmethode, die die Numpy-Matrixmultiplikation mit den Broadcast- und Parallelisierungsfunktionen von Spark kombiniert.

* Ein wichtiger Punkt: Das Vokabular beider Matrizen muss identisch sein. Mit anderen Worten, die Anzahl der Zeilen in beiden Matrizen muss gleich sein und sie müssen exakt die gleiche Reihenfolge haben, z. Jede Zeile stellt einen Term dar, und die Reihenfolge der Zeilen muss zwischen Matrix A und Matrix B genau gleich sein. Dies geschieht auf einfache Weise, indem zunächst das Vokabular und dann die TF-IDF wie im folgenden Beispiel berechnet werden:

aus sklearn.feature_extraction.text importieren Sie TfidfVectorizer
aus sklearn.feature_extraction.text CountVectorizer importieren
importiere cosine_similarity aus sklearn.metrics.pairwise
a = ['google inc', 'medium.com']
b = ['google', 'microsoft']
company_name_stopwords = frozenset (['ltd', 'llc', 'inc'])
vect = CountVectorizer (stop_words = company_name_stopwords)
Wortschatz = vect.fit (a + b) .vocabulary_
tfidf_vect = TfidfVectorizer (stop_words = company_name_stopwords,
                             Wortschatz = Wortschatz)
a_mat = tfidf_vect.fit_transform (a)
b_mat = tfidf_vect.fit_transform (b)
cosimilarities = cosine_similarity (a_mat, b_mat)