Die Vorteile der Big Data-Technologie im Alltag



    Viele Forscher und Entwickler sind der Meinung, dass die Tools für die Verarbeitung von Big Data im Bereich des maschinellen Lernens häufig überflüssig sind. Sie können jederzeit ein Sample erstellen, es in den Speicher verschieben und Ihr bevorzugtes R, Python und Matlab verwenden. In der Praxis gibt es jedoch Probleme, wenn es schwierig ist, selbst eine relativ kleine Datenmenge mit einer Größe von einigen Gigabyte in diesem Stil zu verarbeiten - und genau hier können die „Big Data“ -Technologien Abhilfe schaffen.

    Ein gutes anschauliches Beispiel für eine solche Aufgabe ist die Aufgabe unseres SNA Hakathon 2016- Wettbewerbs : ein soziales Diagramm mit einer Million Nutzern und deren demografischen Merkmalen . Die Aufgabe besteht darin, versteckte Verbindungen in dieser Spalte zu finden.. Die Größe des bereitgestellten Graphen beträgt in GZip nur zwei Gigabyte, und der Einsatz von Big-Data-Technologien ist anscheinend hier nicht gerechtfertigt, aber dies ist nur auf den ersten Blick.

    Eines der wichtigsten „Merkmale“ bei der Suche nach versteckten Verbindungen in einem sozialen Diagramm ist die Anzahl der gemeinsamen Freunde. Und in Bezug auf die Berechnung ist dies ein sehr schwieriges „Merkmal“ - die Anzahl der Knoten, zwischen denen Pfade der Länge 2 liegen, ist mehrere Größenordnungen größer als die Anzahl der direkten Verbindungen im Diagramm. Infolgedessen „explodiert“ der Graph während der Berechnung und verwandelt sich von einer dünnen Matrix in zwei Gigabyte in eine dichte Terabyte-Matrix .

    Um dieses Problem zu lösen, ist es anscheinend richtig, einen kleinen Cluster aufzubauen, aber Sie sollten sich nicht beeilen: Nachdem Sie die Prinzipien der Verarbeitung von Big Data und die entsprechenden Technologien übernommen haben, kann das Problem auf einem normalen Laptop gelöst werden. Aus den Grundsätzen nehmen wir "teilen und erobern" und "Schwanz sofort hacken" und als Werkzeug - Apache Spark .

    Was ist das Problem?


    Das zur Analyse geöffnete Diagramm wird in Form einer Adjazenzliste (für jeden Scheitelpunkt wird eine Liste der Nachbarn angegeben) und asymmetrisch (nicht alle ausgehenden Scheitelpunkte kennen ausgehende Bögen) dargestellt. Die offensichtliche Methode zum Berechnen der Anzahl gemeinsamer Freunde zwischen den Eckpunkten in diesem Diagramm lautet wie folgt:



    1. Wir übersetzen den Graphen in eine Liste von Paaren;
    2. Schließen Sie sich ihnen an, um sich eine Liste von Paaren von einem „gemeinsamen Freund“ zusammenzustellen.
    3. Fasse die Anzahl der Vorkommen jedes Paares zusammen.

    Zu den Vorteilen dieses Ansatzes gehört natürlich die Einfachheit - bei Spark wird diese Lösung 5 Zeilen umfassen. Aber er hat viel mehr Minuspunkte. Bereits im zweiten Schritt, bei der Implementierung von join-a, kommt es zu einem Shuffle (Datenübertragung zwischen verschiedenen Verarbeitungsschritten), wodurch die lokalen Speicherressourcen sehr schnell erschöpft werden. Und wenn auf Ihrem Laptop plötzlich noch genügend Speicherplatz vorhanden ist, reicht dies auf keinen Fall für das Mischen in der dritten Stufe aus.

    Um die Aufgabe zu bewältigen, müssen Sie sie in Teile teilen ("Teilen und Erobern") und die Ergebnisse mit einer kleinen Anzahl gemeinsamer Freunde filtern ("Schwanz sofort hacken"). Die Erfüllung beider Bedingungen ist jedoch sofort problematisch. Wenn wir die Anzahl der gemeinsamen Freunde nur für einen Teil des Diagramms berechnen, erhalten wir ein unvollständiges Bild und können den Filter nicht ausreichend anwenden.

    Wo ist die Lösung?


    Lassen Sie uns versuchen, das Problem von der anderen Seite zu betrachten. Die meisten Probleme treten in der zweiten Stufe beim Zusammenfügen einer Liste von Paaren auf: Das Format der Liste von Paaren selbst ist in Bezug auf die Größe ineffizient. Außerdem kann eine der Seiten von Join-a nicht gefiltert werden, ohne das Ergebnis zu verfälschen. Ist es möglich, ohne Konvertierung in eine Liste von Paaren und Join-A zu tun? Ja, wenn Sie das Prinzip "Ich bin ein gemeinsamer Freund meiner beiden Freunde" verwenden. In diesem Fall durchlaufen wir die Adjazenzliste für jede der Freundeslisten und generieren alle Paare. Anschließend zählen wir, wie oft jedes Paar im gesamten System aufgetreten ist. Infolgedessen wird das Problem mit einem Shuffle gelöst. :)

    Bei der Entwicklung dieser Idee ist es nicht schwierig, den nächsten Schritt zu machen: Statt alle möglichen Paare zu generieren, müssen Sie nur Paare für eine bestimmte Teilmenge von Benutzern auf der linken Seite generieren (z. B. mit geraden Bezeichnern). Außerdem kann dieser Vorgang mehrmals wiederholt werden, um eine vollständige Abdeckung zu erhalten. Gleichzeitig können Sie bei jeder Iteration sicher einen Filter anwenden, um den "langen Schwanz" abzuschneiden - für Benutzer in dieser Untergruppe werden die Zahlen genau erhalten.

    Dieser Ansatz eignet sich gut für ein symmetrisches Diagramm, das beim SNA Hakathon 2016 vorgestellte Diagramm ist jedoch asymmetrisch - für einige Benutzer sind nur eingehende Bögen bekannt. Um diesen Trick anwenden zu können, muss das Diagramm zunächst erweitert werden:



    Das Konvertierungsergebnis kann bereits gespeichert und als Eingabe für einen iterativen Algorithmus verwendet werden:



    Ist das Spiel die Kerze wert?


    In diesem Diagramm dauerte die Zählung der Anzahl der gemeinsamen Freunde auf einem Cluster von 100 Servern 1 Stunde. Die optimierte iterative Option arbeitete viereinhalb Stunden auf einem Dual-Core-Laptop. Diese Zahlen lassen den Schluss zu, dass die Option „Stirn“ nur für ausreichend große Unternehmen und / oder Forschungsteams akzeptabel ist, während eine optimierte Option von nahezu jedem gestartet werden kann. Außerdem sind alle erforderlichen Codes und Anweisungen auf GitHub öffentlich verfügbar .

    Sind diese „Big-Data-Technologien“ in diesem Schema wirklich notwendig? Kann dasselbe in R oder Python wiederholt werden? Theoretisch ist nichts unmöglich. In der Praxis muss die Implementierung jedoch eine Vielzahl von Problemen lösen und sich mit vielen sehr spezifischen Paketen und Funktionen vertraut machen. Der resultierende Code wird größer und deutlich teurer in der Entwicklung und Wartung.

    Selbst wenn wir dieses Beispiel ignorieren, ist die Verwendung von Apache Spark in vielen Fällen R und Python vorzuziehen: Die parallele Verarbeitung von Daten ist für Spark eine Selbstverständlichkeit, da sie eine höhere Geschwindigkeit bietet. Der Code kann in Google Cloud praktisch unverändert an den Cluster übertragen werden ( Fallstudie) und auf eine wesentlich größere Datenmenge angewendet. Nun, die Sammlung der unterstützten Algorithmen für maschinelles Lernen ist bereits beeindruckend und wird ständig aktualisiert ( MLLib ) , obwohl sie den "Großeltern" noch unterlegen ist .

    Zeit um Scala zu lernen :)

    Jetzt auch beliebt: