Graph Clustering und Community-Suche. Teil 1: Einführung, Überblick über Werkzeuge und Haarbälle

    Hallo habr In unserer Arbeit besteht häufig die Notwendigkeit, Communities (Cluster) verschiedener Objekte hervorzuheben: Benutzer, Websites, Produktseiten von Online-Shops. Die Vorteile solcher Informationen sind sehr vielfältig - hier nur einige praktische Anwendungsbereiche für hochwertige Cluster:

    1. Zuordnung von Nutzersegmenten für gezielte Werbekampagnen.
    2. Verwenden von Clustern als Prädiktoren („Features“) in persönlichen Empfehlungen (in inhaltsbasierten Methoden oder als zusätzliche Informationen in der kollaborativen Filterung).
    3. Dimensionsreduzierung bei jeder maschinellen Lernaufgabe, bei der vom Benutzer besuchte Seiten oder Domänen als Funktionen fungieren.
    4. Vergleich von Produkt-URLs zwischen verschiedenen Online-Shops, um Gruppen zu identifizieren, die demselben Produkt entsprechen.
    5. Kompakte Visualisierung - es wird für eine Person einfacher, die Datenstruktur zu erkennen.

    Aus Sicht des maschinellen Lernens sieht das Abrufen dieser verwandten Gruppen wie eine typische Clustering-Aufgabe aus. Beobachtungsmerkmale stehen uns jedoch nicht immer ohne weiteres zur Verfügung, in deren Raum nach Clustern gesucht werden könnte. Die Beschaffung von Inhalten oder semantischen Merkmalen sowie die Integration verschiedener Datenquellen, aus denen diese Merkmale beschafft werden könnten, ist recht mühsam. Wir haben jedoch einen DMP mit dem Namen Facetz.DCA , bei dem es oberflächlich gesehen Fakten zum Besuch von Seiten durch Benutzer gibt. Aus ihnen ist es einfach, die Anzahl der Besuche einzelner Standorte und die Anzahl der gemeinsamen Besuche für jedes Standortpaar zu ermitteln. Diese Informationen sind bereits für die grafische Darstellung von Webdomains oder Produktseiten ausreichend. Nun kann das Clustering-Problem als die Aufgabe formuliert werden, Communities in den erhaltenen Graphen zu isolieren.

    Mit Blick auf die Zukunft kann ich sagen, dass wir es bereits geschafft haben, die Webdomain-Communitys mit großem Nutzen für RTB-Werbekampagnen zu nutzen. Das klassische Problem, mit dem Händler konfrontiert sind, ist die Notwendigkeit, zwischen Zielgenauigkeit und Segmentvolumen zu manövrieren. Einerseits ist das grobe Targeting nach soziodemografischen Merkmalen zu umfassend und ineffektiv. Auf der anderen Seite sind raffinierte thematische Segmente oft zu eng und Änderungen der Wahrscheinlichkeitsschwellen in den Klassifizierern können das Segment nicht auf das erforderliche Volumen erweitern (z. B. bis zu mehreren zehn Millionen Cookies). Gleichzeitig bilden Personen, die häufig Domains desselben Clusters besuchen, gute Segmente für derart weitreichende Kampagnen.

    In dieser Reihe von Beiträgen werde ich versuchen, mich mehr auf die algorithmische Seite des Problems als auf die geschäftliche Seite zu konzentrieren. Beschreiben Sie zunächst unsere Versuche und zeigen Sie die erhaltenen Bilder. Zweitens, um auf die Methoden im Detail einzugehen: Was wir angewendet haben / anwenden wollten, aber unsere Meinung geändert haben / noch anwenden wollen.

    Viele von Ihnen mussten wahrscheinlich die Daten gruppieren, aber wahrscheinlich haben die meisten, wie wir, das Diagramm nie gruppiert. Das Hauptmerkmal von Graph Clustering ist das Fehlen von Beobachtungsmerkmalen. Wir haben keinen Abstand zwischen zwei willkürlichen Punkten im Raum, weil es keinen Raum selbst gibt, es keine Norm gibt und es unmöglich ist, den Abstand zu bestimmen. Stattdessen haben wir Kantenmetadaten (idealerweise für jedes Eckpunktpaar). Wenn es ein "Gewicht" einer Kante gibt, kann es als Abstand (oder im Gegenteil als Ähnlichkeit) interpretiert werden, und dann haben wir die Abstände für jedes Knotenpaar bestimmt.

    Viele der Clustering-Algorithmen im euklidischen Raum eignen sich auch für Graphen, da für diese Algorithmen nur der Abstand zwischen Beobachtungen und nicht zwischen willkürlichen "Punkten im Raum" bekannt sein muss. Einige benötigen einen Feature-Space und eignen sich nicht für Diagramme (z. B. k-means). Auf der anderen Seite weisen Diagramme viele ihrer einzigartigen Eigenschaften auf, die ebenfalls verwendet werden können: Konnektivitätskomponenten, lokale Cluster von Kanten, Orte, an denen Informationsflüsse durchlaufen werden usw.

    Tools-Übersicht


    Bis heute haben die Menschen eine Vielzahl von Methoden zum Clustering von Graphen erfunden - jede mit ihren eigenen Vorteilen und Pfosten. In einem der folgenden Beiträge werden wir einige Algorithmen und ihre Eigenschaften genauer untersuchen. In der Zwischenzeit halten wir es für nützlich, Links zu offenen Tools für die Analyse von Diagrammen freizugeben, in denen bereits etwas für das Clustering und die Suche nach Communities implementiert wurde.

    1. Sehr modisch und entwickelt sich jetzt GraphX . Es musste als erstes Element in die Liste geschrieben werden, aber als solches gibt es dort keine vorgefertigten Clustering-Algorithmen (Version 1.4.1). Es gibt eine Anzahl von Dreiecken und verbundenen Komponenten, mit denen zusammen mit Standardoperationen in Spark RDD Ihre eigenen Algorithmen geschrieben werden können. Bisher hat GraphX ​​API nur für Scala, was auch die Verwendung erschweren kann.

    2. Eine Bibliothek für Apache Giraph namens Okapi verwendet mehrere Algorithmen, einschließlich eines ziemlich neuen proprietären Algorithmus namens Spinner , der auf der Etikettenausbreitung basiert. Giraph ist ein Add-On für Hadoop, das für den Umgang mit Grafiken entwickelt wurde. Es gibt fast kein maschinelles Lernen, und um dies auszugleichen, hat Telefonica Okapi entwickelt. Wahrscheinlich sieht Giraph vor dem Hintergrund von GraphX ​​jetzt nicht so vielversprechend aus, aber der Spinner-Algorithmus selbst passt gut zum Spark-Paradigma. Sie können über Spinner hier lesen .

    3. Die Graph-Tool- Bibliothek für Python enthält einige der neuesten Clustering-Algorithmen und ist sehr schnell. Wir haben damit URLs verglichen, die demselben Produkt entsprechen. Alles, was möglich ist, wird über die Prozessorkerne parallelisiert, und für lokales Computing (Grafiken mit bis zu ein paar hunderttausend Knoten) ist dies die schnellste Option.

    4. Gephi ist ein bekanntes Werkzeug, das wir vielleicht zu Unrecht ignoriert haben. Gephi hat sich lange Zeit praktisch nicht weiterentwickelt, aber es hat gute Plugins bekommen, auch zum Hervorheben von Communities . Vor kurzem wurde das Projekt wieder ins Leben gerufen und Version 0.9 wird erwartet

    5. GraphLab Create . Dies ist ein Python-Wrapper über C ++, mit dem Sie maschinelles Lernen sowohl lokal als auch verteilt (in Yarn) ausführen können. Clustering-Graphen gibt es immer noch nicht, nur die Suche nach Kerneln .

    6. Das gelobte networkX weiß trotz der Fülle an Algorithmen nicht, wie man Graphen gruppiert, sondern nur verbundene Komponenten und Klicks analysiert. Außerdem ist es viel langsamer als das Graph-Tool und in Bezug auf die Visualisierung schlechter als dasselbe Graph-Tool und Gephi.

    7. Implementierung des Markov-Clustering-Algorithmus (MCL) von seinem Erfinder. Der Autor reduzierte die Komplexität der üblichen MCL im schlimmsten Fall von inline_formulaauf inline_formula, wo inline_formuladie Anzahl der Knoten und inline_formulader maximale Grad des Knotens ist, und ist beleidigt, wenn der MCL-Algorithmus als nicht skalierbar bezeichnet wird. Er fügte auch Chips hinzu, um die Anzahl der Cluster anzupassen. Die MCL hatte jedoch mehrere andere schwerwiegende Probleme, und es ist unklar, ob sie gelöst wurden. Zum Beispiel das Problem der Clustergrößeninstabilität (unser kleines Experiment ergab eine riesige zusammenhängende Komponente und viele kleine Cluster mit jeweils 2-3 Knoten, aber vielleicht fanden wir nicht den richtigen Handle). Die neuesten Nachrichten auf der Website stammen aus dem Jahr 2012, was nicht sehr gut ist.

    8. Verschiedene Implementierungen eines der beliebtesten Louvain-Algorithmen: für C , für Python und sogar für Python . Ein klassischer Artikel zu diesem Algorithmus: link .

    9. Die dem Infomap-Algorithmus und seinen Modifikationen gewidmete Site, von den Autoren der Methode. Wie überall gibt es Open Source. Neben einer guten Support und Dokumentation gibt es erstaunliche Demos den Algorithmus darstellt: hier und hier . Wie der Algorithmus funktioniert, erfahren Sie hier .

    10. Ein Paket für R namens igraph . Es implementiert eine ganze Reihe von Clustering-Algorithmen, zu denen wir jedoch keine genauen Angaben machen können, da wir das Paket nicht untersucht haben.

    Wenn das Ziel darin besteht, ein reproduzierbares Experiment mit kleinen Daten durchzuführen, anstatt das fertige Produkt in die Produktion einzuführen, dann sind nach unserer Meinung unter allen oben genannten Optionen Graph-Tool (Punkt 3), Gephi (Punkt 4) oder Infomap (Punkt 9) die besten.

    Unsere Experimente


    Und jetzt werden wir erzählen, wie wir die Graphen der Runet-Domänen und der Umgebung gebildet haben, und die Bilder mit den Ergebnissen ihrer Gruppierung zeigen. Im nächsten Teil unserer Artikelserie beschreiben wir den Algorithmus, mit dem die folgenden Bilder erhalten wurden. Hierbei handelt es sich um modifizierte k-Medoide, die wir in den besten Traditionen des Radfahrens auf die Wurzelpython geschrieben haben und mit deren Hilfe wir einige Probleme überraschend gut gelöst haben. Ein Teil der Informationen aus diesem und dem nächsten Beitrag sowie eine Beschreibung einiger anderer Algorithmen sind in der Präsentation enthalten, über die ich in diesem Frühjahr auf newprolab im digitalen Oktober gesprochen habe:


    Daten


    Die erste Aufgabe ist das Clustering von Webdomänen. Aus DMP nehmen wir Daten von Benutzern auf, die verschiedene Domänen besuchen, und erstellen anhand dieser Daten ein Diagramm, in dem die Knoten die Domänen und die Kanten die Affinität zwischen den Domänen darstellen. Affinity (aka Lift) zwischen den Domänen inline_formulaund inline_formula- eine Probe Schätzung, wie Ereignissen „Gesehen durch die Benutzer - inline_formulaDomäne inline_formula“ und „Gesehen durch die Benutzer - inline_formulaDomäne inline_formula“ in der Nähe Unabhängigkeit. Wenn inline_formula- die Gesamtzahl der fraglichen Benutzer und inline_formula- die Anzahl der besuchten Benutzer inline_formula, dann:


    Um das Rauschen zu beseitigen, müssen Sie Domänen mit zu wenigen Besuchen sowie Kanten mit geringer Affinität herausfiltern. Die Praxis zeigt, dass eine Schwelle von 15-20 für Besuche und 20-25 für Affinität ausreicht. Bei einer höheren Affinitätsschwelle erscheinen als Ergebnis zu viele isolierte Scheitelpunkte.

    Mit einer solchen Diagrammkonstruktionsmethode können Sie in den Daten eine ziemlich klare Struktur der „Communitys“ von Domänen sehen. Eines seiner interessanten Merkmale ist, dass die größten Domänen (Suchmaschinen, soziale Netzwerke, einige große Geschäfte und Nachrichtenseiten) in der Regel keine sehr "dicken" Kanten ohne andere Eckpunkte aufweisen. Dies führt dazu, dass diese Domänen an den Rand gedrängt werden und häufig isolierte Eckpunkte bleiben, ohne in einen der Cluster zu fallen. Wir halten dies für ein Plus, da ein gemeinsamer Besuch von vk.com und einer hochspezialisierten Website wenig über ihre Beziehung zueinander aussagt.

    Ich muss sagen, dass das Abrufen und Filtern von Daten, das Erstellen eines Diagramms und das Berechnen verschiedener Matrizen eine viel anspruchsvollere Aufgabe ist, als das Abrufen der Cluster selbst. Einige Stufen (insbesondere die Berechnung der paarweisen Ähnlichkeit) konnten mit dem Pathos-Paket ( pathos.multiprocessing ) parallelisiert werden . Im Gegensatz zum standardmäßigen Python-Multiprozessor-Paket treten keine Serialisierungsprobleme auf, da Dill anstelle von Pickle verwendet wird. Die Syntax ist absolut identisch mit der Standard-Mehrfachverarbeitung. Hier können Sie über Dill lesen.

    Visualisierung


    Es ist Zeit, einige Bilder mit Grafiken zu zeigen (wie sich herausstellte, werden wir im nächsten Teil erzählen). Es ist bekannt, dass networkX nicht für die Visualisierung von Graphen vorgesehen ist. Zu diesem Zweck ist es besser, auf d3.js, gephi oder graph-tool zu verweisen. Wir haben das zu spät herausgefunden und haben entgegen dem gesunden Menschenverstand weiterhin mutig Bilder in networkX gezeichnet. Es stellte sich heraus, dass es nicht so reiner Honig war (insbesondere war es nicht möglich, die gegenseitige Abstoßung von Knoten und nicht überlappenden Etiketten zu konfigurieren), aber wir haben versucht, die Möglichkeiten von networkX so weit wie möglich auszuschalten. In allen Bildern entspricht der Durchmesser des Kreises (Domäne) seiner Anwesenheit, die Dicke der Rippe entspricht der Affinität, die Farbe des Kreises zeigt an, dass die Domäne zum Cluster gehört. Die Farbe der Kante bedeutet, dass beide Eckpunkte zu diesem Cluster gehören, die graue Farbe entspricht den Kanten.

    Kommentare zu Clustern als Beispiel für eine der Grafiken


    Ein nicht ganz so großes Diagramm mit 1285 Domänen:

    Die spärliche Version ist auf dem Bild dargestellt: Die meisten Kanten werden mit der lokalen Sparsifikationsmethode entfernt (dies wird im nächsten Teil beschrieben), wodurch die Gruppierung in Communities deutlicher wird und die Wirkung des Big Hair Balls gemildert wird ". Cluster nur 18 in voller Größe Bilder (PNG).

    Auf jedem Vertex steht der Name der Domain und die Nummer des Clusters, zu dem er gehört. Achten Sie auf isolierte Scheitelpunkte entlang des äußeren Kreises - dies sind normalerweise große Domänen ohne starke Verbindungen zu irgendjemandem. Der untere Teil des Diagramms kann als „weiblicher“ (oder besser als „Familie“) beschrieben werden. Es ist ziemlich chaotisch, wahrscheinlich, weil mehrere Familienmitglieder die Seite mit demselben Browser (mit einem Cookie) zu unterschiedlichen Zeiten angesehen haben. Der Algorithmus kam mit der Zuweisung von Communities in diesem Teil der Grafik nicht sehr gut klar.

    Ein riesiger Cluster auf Platz 17 (pink) hat eine Menge zu bieten - von Schwangerschaftsorten unterhalb und medizinischen Standorten im Zentrum bis hin zu einer Mischung aus Wettervorhersagen, Frauenforen und Magazinen an der Spitze des Clusters. Im "Südwesten" davon befindet sich der kulinarische Cluster (Nummer 4):



    Im "Südosten" des Familienclusters befindet sich die Immobilien- und Stellensuche (zusammengefasst in einem Cluster Nummer 2):



    Im "Süden" des Clusters 17 befindet sich ein sehr schlecht markiertes Gebiet. Daher konnte der Algorithmus die Community der Tourismusdomains nicht isolieren (sie sind auf verschiedene Communities verteilt), und die Site über die Waffe wurde in den kulinarischen Cluster aufgenommen.

    Der kleine Cluster 15 (rot) enthielt hauptsächlich legale Sites:



    Im "Nordwesten" des "Familienteils" befinden sich die ausgeprägtesten Cluster. Anscheinend verwendet niemand sonst die Browser der Besucher dieser Websites (und dies ist logisch, basierend auf den Themen der Cluster). Erstens fallen zwei dichte Gruppen auf: russische (Nummer 16, Ziegel) und ukrainische (Nummer 12, blau) Nachrichtenseiten, wobei letztere viel dichter sind, wenn auch kleiner. Sie können auch feststellen, dass sich die Ausrichtung der Standorte entlang des russischen Clusters ändert:



    Filme, Fernsehsendungen und Online-Kinos (graue und gelbe Cluster mit den Nummern 3 und 8) befinden sich auf den Nachrichtenseiten im Nordosten. Zwischen den Filmclustern und dem ukrainischen Nachrichtencluster als Übergangszone befindet sich eine Gruppe von Pornografie.



    Näher im Osten befindet sich Cluster Nummer 1 - das gesamte kasachische Internet. Daneben befinden sich Automobilstandorte (Cluster 6, violett) und russische Sportstandorte (sie haben sich anderen Nachrichten in Cluster 16 angeschlossen).



    Weiter südlich gibt es eine Ansammlung von Cartoons und Kinderspielen (Nummer 10, Sumpf) sowie eng verwandte Schulansammlungen von Wörterbüchern, Online-Resolvern und Aufsätzen: ein großer Russe (Nummer 5, Pfirsich) und ein sehr kleiner Ukrainer (Nummer 0, Grün). . Cluster Nummer 0 umfasste auch ukrainische Websites aller Themen, mit Ausnahme von Nachrichten (es gab nur sehr wenige). Schulgruppen im "Süden" rücken nahtlos in die weibliche Hauptgruppe Nr. 17 vor.



    Als letztes ist hier die Büchergruppe am Stadtrand im "östlichen" Teil des Bildes zu beachten:



    Jährliche Änderungen


    So sieht derselbe Graph aus, nur ohne Ausdünnung gezeichnet:


    Volle Größe.

    Und hier ist ein ungefähr ähnliches Diagramm, das fast ein Jahr vor dem vorherigen erstellt wurde. Es hat 12 Cluster:

    Volle Größe.

    Wie Sie sehen, blieb die Struktur in dieser Zeit insgesamt unverändert (Nachrichtenseiten, ein großer weiblicher Haufen, ein großer, spärlicher Bereich von Unterhaltungsseiten unterschiedlicher Richtungen). Von den Unterschieden ist das endgültige Verschwinden des Clusters mit Musik während dieser Zeit zu bemerken. Wahrscheinlich haben die Leute in dieser Zeit fast aufgehört, spezielle Websites zu nutzen, um nach Musik zu suchen, und sich häufig sozialen Netzwerken zugewandt, um Impulsservices wie Spotify zu erhalten. Die Aufteilbarkeit des gesamten Diagramms in Communities insgesamt hat zugenommen, und die Anzahl der aussagekräftigen Cluster wurde von 12 auf 18 erhöht. Die Gründe dafür liegen höchstwahrscheinlich nicht in einem veränderten Benutzerverhalten, sondern lediglich in einer Änderung unserer Datenquellen und des Datenerfassungsmechanismus.

    Wenn wir die Stichprobe der Benutzer erhöhen und die Filter auf die Mindestanzahl der Besuche in der Domäne und in zwei Domänen sowie auf die Mindestaffinität für die Bildung einer Kante beschränken, erhalten wir ein größeres Diagramm. Unten ist ein Graph von 10121 Peaks und 30 Clustern dargestellt. Wie Sie sehen, funktioniert der Power-Drawing-Algorithmus von networkx bereits nicht sehr gut und liefert ein ziemlich verwirrendes Bild. Dennoch können einige Muster in dieser Form verfolgt werden. Die Anzahl der Kanten wurde unter Verwendung derselben lokalen Sparsifizierungsmethode von anderthalb Millionen auf 40.000 verringert. Die PNG-Datei belegt 80 MB. Die vollständige Größe finden Sie hier.



    Bei der Visualisierung war es nicht möglich, die Struktur von Communities (ein Hash im Zentrum) richtig zu unterscheiden, aber in Wirklichkeit erwiesen sich die Cluster als nicht weniger aussagekräftig als im Fall von 1285 Domänen.

    Mit zunehmender Datenmenge werden interessante Muster beobachtet. Einerseits zeichnen sich kleine periphere Cluster ab, die bei kleinen Daten nicht zu unterscheiden waren. Auf der anderen Seite ist das, was bei kleinen Daten schlecht geclustert ist, bei großen Daten schlecht geclustert (z. B. mischen sich Immobilien- und Jobsucheseiten, Esoterik und Astrologie schließen sich häufig an).

    Hier sind einige Beispiele für neue Communities. Am Stadtrand stach die spanische Gruppe hervor, als wir etwas von dort sehen:



    Nicht weit davon entfernt, näher an der Hauptpunktgruppe, befinden sich die aserbaidschanischen Cluster (Nummer 2) und die georgischen Cluster (Nummer 4):



    Neben den „russischen Nachrichten“ und (Nummer 16) sind im Hauptteil der Domänen ein usbekisch-tadschikischer Cluster sowie ein belarussischer Cluster aufgetreten "Ukrainian non-news" -Communitys:



    Der nächste Beitrag beschreibt den Algorithmus:

    - wie die Cluster selbst erhalten wurden, damit die Grafik so gefärbt werden kann;
    - wie überschüssige Rippen entfernt wurden.

    Bereit, Ihre Fragen in den Kommentaren zu beantworten. Bleib dran!

    Jetzt auch beliebt: