Graph Clustering und Community-Suche. Teil 2: k-Medoide und Modifikationen

    BildHallo habr In diesem Teil werden wir Ihnen den Algorithmus beschreiben, mit dem die Farben der Grafiken aus dem ersten Teil erhalten wurden . Der Algorithmus basiert auf k-Medoiden - eine relativ einfache und transparente Methode. Es ist eine Variante des beliebten k-means , von dem die meisten von Ihnen wahrscheinlich schon eine Idee haben.

    Im Gegensatz zu k-means kann in k-medoids kein Punkt als Zentroide fungieren, sondern nur ein Teil der verfügbaren Beobachtungen. Da im Graphen zwischen den Eckpunkten der Abstand bestimmt werden kann, eignen sich k-Medoide zum Clustering des Graphen. Das Hauptproblem dieser Methode ist die Notwendigkeit, die Anzahl der Cluster explizit anzugeben, dh es handelt sich nicht um eine Community-Identifikation, sondern um eine optimale Aufteilung in eine bestimmte Anzahl von Teilen (Graphpartitionierung).

    Es gibt zwei Möglichkeiten, damit umzugehen:

    • oder indem Sie eine bestimmte Metrik für die „Qualität“ der Partition festlegen und den Prozess der Auswahl der optimalen Anzahl von Clustern automatisieren;
    • oder indem Sie ein farbiges Diagramm zeichnen und versuchen, die logischste Unterteilung „nach Augenmaß“ zu bestimmen.

    Die zweite Option eignet sich nur für kleine Daten und nicht mehr als ein paar Dutzend Cluster (oder Sie müssen einen Algorithmus mit mehrstufigem Clustering verwenden). Je größer die Grafik, desto gröber müssen die Details sein, um die Qualität „mit dem Auge“ beurteilen zu können. Gleichzeitig muss der Vorgang für jeden einzelnen Graphen erneut wiederholt werden.

    PAM


    Die häufigste Implementierung von k-Medoiden heißt PAM (Partitioning Around Medoids). Es ist ein gieriger Algorithmus mit sehr ineffizienten Heuristiken. So sieht es als Anhang zu einem Diagramm aus:

    Eingabe: Graph G, eine gegebene Anzahl von Clustern k
    Ausgabe: Optimale Aufteilung in k Cluster + jeweils ein „zentraler“ Eckpunkt
    Initialisieren: Wählen Sie k zufällige Knoten als Medoide aus.
    Für jeden Punkt finden wir das nächstgelegene Medoid, das die anfängliche Clusterbildung bildet.
    minCost = Verlustfunktion ab Erstkonfiguration
    Bis sich die Medoide stabilisieren:
        Für jedes Medoid m:
            Für jeden Scheitelpunkt v! = M innerhalb des Clusters, der um m zentriert ist:
                Wir bewegen den Honeyoid in v
                Wir verteilen alle Eckpunkte zwischen den neuen Medoiden neu
                Cost = Loss-Funktion über den gesamten Graphen
                Wenn Kosten <minCost:
                    Medoids auswendig lernen
                    minCost = Kosten
                Setzen Sie das Medoid ein (in m)
        Wir machen den besten Ersatz für alle gefundenen (d. H. Innerhalb eines Clusters wechseln wir ein Medoid) - dies ist eine Iteration.

    Bei jeder Iteration iteriert der Algorithmus über die inline_formulaPunkte des Graphen (wobei inline_formuladie Gesamtzahl der Knoten ist) und bewegt das entsprechende Medoid dorthin. Für jeden solchen Ersatz muss er die Abstände aller Punkte zu den Medoiden neu berechnen. Wenn alle paarweisen Abstände zwischen Punkten in den Speicher passen, wird dieser Schritt ausgeführt inline_formula. Außerdem ergreift der optimale Ersatz eine andere inline_formulaMaßnahme. Gesamtkomplexität einer Iteration im schlimmsten Fall inline_formula, was absolut inakzeptabel ist. Die Anzahl der Iterationen für ein Diagramm mit mehreren tausend Knoten beträgt ungefähr 30-50.

    Die gierigste Heuristik


    Nachdem wir ein wenig mit diesem Algorithmus gearbeitet hatten, begannen wir zu überlegen, wie der Prozess beschleunigt werden kann, da das Clustering eines Diagramms mit nur 1.200 Knoten auf einer Maschine mehrere Minuten (für 10.000 Knoten bereits mehrere Stunden) in Anspruch nahm. Eine mögliche Verbesserung besteht darin, den Algorithmus noch gieriger zu gestalten, indem nach dem besten Ersatz für nur einen Cluster oder noch besser für einen kleinen Bruchteil der Punkte innerhalb desselben Clusters gesucht wird. Die letzte heuristische Variante gibt dem Algorithmus folgende Form:

    Eingabe: Graph G, eine gegebene Anzahl von Clustern k
    Ausgabe: Optimale Aufteilung in k Cluster + jeweils ein „zentraler“ Eckpunkt
    Für jeden Punkt finden wir das nächstgelegene Medoid, das die anfängliche Clusterbildung bildet.
    Wie viele Iterationen hintereinander gab es keine Verbesserung: StableSequence = 0  
    Während wahr:
        Für jedes Medoid m:
            Wählen Sie zufällig s Punkte innerhalb eines Clusters um m zentriert
            Für jeden Eckpunkt v von s:
                Wir bewegen den Honeyoid in v
                Wir verteilen alle Eckpunkte zwischen den neuen Medoiden neu
                Cost = Loss-Funktion über den gesamten Graphen
                Wenn Kosten <minCost:
                    Medoids auswendig lernen
                    minCost = Kosten
                Setzen Sie das Medoid ein (in m)
            Wenn der beste Ersatz für s die Verlustfunktion verbessert:
                Wir machen diesen Ersatz
                StableSequence = 0
            Ansonsten:
                StableSequence + = 1
                If StableSequence> Threshold:
                    Wir geben die aktuelle Konfiguration zurück

    In einfachen Worten, jetzt suchen wir nach einem optimalen Ersatz nicht für alle Scheitelpunkte des Graphen, sondern für einen Cluster, und wir werden nicht alle Scheitelpunkte innerhalb dieses Clusters sortieren, sondern nur inline_formulavon diesen. In diesem Fall ist die Komplexität einer Iteration inline_formulain der Anzahl der Knoten linear. Gleichzeitig inline_formula, was die Komplexität der Berechnungen drastisch reduziert, aber wird die Qualität der Cluster mit einer derart drastischen Vereinfachung nicht abnehmen? Es gibt einen Artikel, in dem ein Beispiel für einen Algorithmus angegeben ist, in dem es einen Parameter mit einer ähnlichen inline_formulaBedeutung gibt.

    Es stellt sich heraus, dass die Abnahme auf 2 und sogar auf 1 verschiedene Clusterqualitätsmetriken (z. B. Modularität ) praktisch nicht verschlechtert . Aus diesem Grund haben wir beschlossen inline_formula, einen von zwei Punkten innerhalb desselben Clusters zu nehmen und den Prozess zu stoppen, wenninline_formulaIterationen hintereinander (StableSequence) ändern das aktuelle Optimum nicht. Bei normaler PAM wird der Prozess nach einer solchen Iteration beendet. In der Praxis führt dies dazu, dass sich die Anzahl der Iterationen mit einer neuen Heuristik um das 10 bis 20-fache erhöht, die Beschleunigung jeder Iteration jedoch nicht kompensiert. Infolgedessen konnte durch diese Änderung die Clustering-Zeit des Diagramms von 1209 Knoten auf 5,5 Sekunden und von 10.000 Knoten auf 2-3 Minuten reduziert werden, was bereits akzeptabel, aber immer noch recht lang ist. Dies ist jedoch die wichtigste Verbesserung des Algorithmus, nach der der schwierigste Schritt nicht das Clustering selbst ist, sondern die Vorverarbeitung der Daten, insbesondere die Berechnung paarweiser Ähnlichkeiten / Abstände zwischen Scheitelpunkten.

    Clara


    Der nächste Schritt zur Verbesserung der Skalierbarkeit von k-Medoiden ist eine bekannte PAM-Modifikation namens Clara. Eine Untergruppe von Scheitelpunkten wird zufällig aus dem Originaldiagramm ausgewählt, und der von diesen Scheitelpunkten gebildete Untergraph wird gruppiert. Dann (vorausgesetzt, der Graph ist verbunden) werden die verbleibenden Eckpunkte einfach über das nächste Medoid vom Subgraphen verteilt. Alle clara salt besteht darin, den Algorithmus nacheinander auf verschiedenen Untergruppen von Vertices auszuführen und das bestmögliche Ergebnis auszuwählen. Aus diesem Grund soll es den Schaden aus dem Ausschluss eines Teils der Informationen für jeden einzelnen Lauf kompensieren sowie vermeiden, in einem lokalen Minimum hängen zu bleiben. Als Maß für die Optimalität bei der Auswahl des Ergebnisses haben wir die Modularität verwendet. Es gibt viele knifflige Möglichkeiten, einen Subgraphen in der ersten Phase zu isolieren, aber wir haben ein paar einfache verwendet:

    1. Zufällige Auswahl von Eckpunkten mit gleicher Wahrscheinlichkeit;
    2. Mit einer Wahrscheinlichkeit proportional zum Grad des Scheitelpunkts im Originaldiagramm;
    3. Wählen Sie immer eine feste Anzahl von Scheitelpunkten mit dem größten Grad und fehlende Scheitelpunkte zufällig mit gleicher Wahrscheinlichkeit.
    4. Wählen Sie Scheitelpunktpaare aus, zwischen denen das Jacquard-Maß über dem Schwellenwert und das fehlende mit gleicher Wahrscheinlichkeit liegt (oder kriechen Sie in die Nachbarn).

    Alle Methoden zeigten ungefähr die gleiche Qualität von Clustern gemäß der beliebten WTF-Metrik, die der Anzahl der Ausrufe „What the fuck?“ (Was zum Teufel?) Entspricht, wenn die Cluster-Zusammensetzung visuell betrachtet wurde (zum Beispiel, wenn Sie sich im selben Cluster des Airborne Forces-Forums und auf der cosmo.ru-Website befinden).

    Die Auswahl eines Subsampling-Volumens für clara ist auch ein Kompromiss zwischen Qualität und Geschwindigkeit. Je mehr Cluster in den Daten vorhanden sind, desto geringer sind unsere Stichprobenfunktionen: Einige Cluster fallen möglicherweise einfach nicht in die Stichprobe. Wenn der Unterschied in der Clustergröße groß ist, ist dieser Ansatz im Allgemeinen kontraindiziert. Wenn die Struktur mehr oder weniger gleichmäßig ist, empfehlen wir, die inline_formulaKnoten - die Hälfte des Graphen - abzutasten. Wir sind zu diesem Verhältnis gekommen, das sich an der WTF-Metrik orientiert. Wenn Sie ohne Lehrer lernen, ist diese Metrik häufig die nützlichste.

    Anscheinend sollte clara ursprünglich die Ausführungszeit von Clustering-Algorithmen verkürzen, deren Rechenaufwand schneller ansteigt als die Anzahl der Scheitelpunkte (wenn ein Teilgraph mehrmals ausgeführt wird, ist dies schneller als ein vollständiger Graph). Daher sinkt der Nutzen von Clara bei Verwendung verbesserter Heuristiken (lineare Komplexität) stark. Wir haben jedoch eine andere Verwendung für Clara gefunden: einen Ensemble-Ansatz, auf den später noch eingegangen wird.

    Lokale Ausdünnung (L-Spar)


    Der nächste Schritt heißt L-Spar (aus lokaler Sparsifikation) und wird hier ausführlich beschrieben . Dies ist eine Methode zur Vorverarbeitung von Diagrammen vor dem Clustering. Es "verdünnt" den Graphen durch Entfernen eines Teils der Kanten (aber nicht der Knoten!), Ohne in der Regel seine Konnektivität zu zerstören.

    Um diesen Schritt zu implementieren, müssen Sie den Grad der "Ähnlichkeit" zwischen zwei beliebigen Knoten kennen. Da wir bei jeder Iteration von k-Medoiden Ähnlichkeit benötigen, haben wir uns entschlossen, die Ähnlichkeitsmatrix vorab zu lesen und auf der Festplatte zu speichern. Als Maß für die Ähnlichkeit wurde das Jacquard-Maß verwendet, mit dem Sie sich höchstwahrscheinlich bereits getroffen haben:


    wo inline_formulaist die Menge der Nachbarn des Knotens inline_formula.

    Der L-Spar-Algorithmus ist sehr einfach. Zunächst werden für jeden Knoten inline_formulaalle Kanten inline_formulain absteigender Reihenfolge sortiert inline_formula, wonach der Ende der Liste zum Filtern in die Gruppe aufgenommen wird. Für jeden nächsten Scheitelpunkt gibt es einen eigenen Satz Kanten zum Filtern, der mit dem vorhandenen kombiniert wird. Wenn jeder Eckpunkt verarbeitet wird, werden alle Kanten aus der Ergebnismenge aus dem Diagramm entfernt. Die Autoren der Methode schlagen vor, in die Liste der "überlebenden" inline_formulaKanten aufzunehmen, wo inline_formulader Grad des Knotens ist inline_formula, undinline_formula- Grad von 0 bis 1. Wenn eine Kante für mindestens einen ihrer Knoten auf der Liste der „Überlebenden“ steht, „überlebt“ sie. Somit werden keine neuen isolierten Knoten gebildet, und wenn der ursprüngliche Graph verbunden wurde, bleibt die geringe Wahrscheinlichkeit wahrscheinlich verbunden.

    Es ist bewiesen, dass gleichzeitig das Potenzgesetz der Gradverteilung im Graphen erhalten bleibt, was zum Phänomen einer "engen Welt" oder "kleinen Welt" führt, wenn der kürzeste Weg zwischen zwei Knoten im Durchschnitt eine sehr kurze Länge hat. Diese Eigenschaft ist den meisten vom Menschen erzeugten Netzwerken inhärent, und L-Spar zerstört sie nicht.

    L-Spar hat einen wichtigen Vorteil gegenüber beispielsweise dem Abschneiden aller Rippen mitinline_formulaunterhalb einer bestimmten Schwelle, gleich im gesamten Graphen. Mit der letzteren Methode werden nämlich in dünneren Clustern fast alle Kanten entfernt, während die dichtesten Gemeinschaften fast unberührt bleiben. Gleichzeitig hängt der Grad der Ausdünnung in L-Spar von der Dichte des Graphen in unmittelbarer Nähe des Knotens ab und bewahrt die Struktur sowohl dichter als auch spärlicher Gemeinschaften.

    Diese Methode der Graph-Vorverarbeitung kann natürlich mit jeder Clustering-Methode verwendet werden. Der größte Effekt kann für Algorithmen erzielt werden, deren Komplexität nur von der Anzahl der Kanten abhängt, nicht jedoch von Knoten, da nur die Anzahl der Kanten reduziert wird. In dieser Hinsicht hatten k-Medoide Pech: Ihre Komplexität hängt nur von der Anzahl der Knoten ab. Bei einer ausgeprägteren Community-Struktur kann sich jedoch die Anzahl der für die Konvergenz erforderlichen Iterationen verringern. Wenn durch die Sparsifikation „verrauschte“ Kanten entfernt werden, ist eine deutlichere Struktur der Communitys und damit eine geringere Anzahl von Iterationen zu erwarten. Diese Hypothese wurde durch die Experimente der Autoren dieser Methode bestätigt, aber unsere Experimente bestätigten es nicht.

    In unseren Grafikdomänen gibt es keine „verrauschten“ Kanten, da schwache Affinitäten zwischen den Scheitelpunkten vorgefiltert wurden. Wenn Cluster visuell schlecht zugeordnet sind, sind sie in den Daten schlecht zugeordnet. Daher hängt die Anzahl der Iterationen von k-Medoiden in unseren Diagrammen nicht vom Grad der Ausdünnung ab. Wenn inline_formulasich dies nicht auf die Laufzeit auswirkt, weder bei 1200 noch bei 10.000 Domänen. Darüber hinaus tritt bei der Verwendung von k-Medoiden ein negativer Nebeneffekt auf: Je niedriger die Graphendichte ist, desto höher ist die Wahrscheinlichkeit, dass ein bestimmter Knoten mit allen Medoiden keine Ähnlichkeit mit Jacquard aufweist. Dies wird durch die relativ geringe Anzahl von Medoiden selbst, d. H. Clustern, verstärkt. Aus diesem Grund wurde entschieden, L-Spar vor dem Ausführen von k-medoids nicht zu verwenden (dies kann jedoch für andere Algorithmen äußerst nützlich sein).

    Es ist erwähnenswert, eine weitere Eigenschaft von L-Spar zu erwähnen, die wir mit aller Kraft und größter Sorgfalt verwendeten: die Verbesserung der Lesbarkeit des Bildes. Aufgrund der drastischen Verringerung der Anzahl der Rippen ist es nun möglich, die Haarbälle von sozialen Netzwerken besser zu visualisieren und Communitys darauf anzuzeigen. Ein Beispiel für eine solche Visualisierung wurde im vorherigen Teil dieses Beitrags gegeben, in dem nach dem Anwenden von L-Spar und davor ein Diagramm mit 1285 Webdomänen angezeigt wurde.

    Auswahl der Anzahl der Cluster inline_formula


    Eines der Probleme von k-Medoiden ist die feste Anzahl von Clustern. Um die optimale Anzahl von Clustern zu finden, haben wir verschiedene Optionen ausprobiert. Das Problem mit Modularität, Leitfähigkeit, normalisiertem Schnitt und anderen Messwerten ist, dass sie unter einer Auflösungsgrenze leiden und ihr Maximum zu niedrig erreicht wird inline_formula(im Vergleich zu dem, was uns unsere Augen sagen). Hier ist zum Beispiel die Grafik der Modularität, die wir in Abhängigkeit von der inline_formulaGrafik der Webdomänen von 1029 Knoten vor über einem Jahr erhalten haben:

    Blau zeigt die durchschnittliche Modularität und ihre 1,95 Standardabweichungen pro 100 Wiederholungen von k-Medoiden, Grün zeigt die maximale Modularität pro 100 Wiederholungen . Die rote Farbe gibt den Punkt an, der der maximalen Anzahl von Clustern entsprichtinline_formulabei dem die durchschnittliche Modularität nicht niedriger ist als die obere Grenze des Konfidenzintervalls für inline_formula. Der Punkt befindet sich inline_formulabereits in der Zone des Verfalls der Modularität, während ungefähr so ​​viele Communities in den Daten vorhanden sind, wie es visuell erscheint (WTF). Es wurde inline_formulaletztendlich gewählt.

    Stabiler Kern


    Die obigen Modifikationen mögen in Bezug auf die Skalierbarkeit gut sein, aber sie führen zu zwei interessanten Problemen. Erstens kann die Qualität von Clustern abnehmen: Es ist nicht offensichtlich, wie stark die Partitionslogik abnimmt, wenn die Heuristik vereinfacht wird (insbesondere wenn ein Teilgraph ausgewählt oder die meisten Kanten gelöscht werden). Zweitens steht die Stabilität des Ergebnisses auf dem Spiel: Die Aufteilung in Cluster im zweiten Durchlauf unterscheidet sich erheblich von der Aufteilung im ersten Durchlauf, auch bei gleichen Anfangsdaten. Alle unsere Modifikationen haben den Algorithmus noch mehr randomisiert. Was aber, wenn sich ein Graph auch im Laufe der Zeit entwickelt? Wie identifiziere ich Cluster aus verschiedenen Läufen miteinander?

    Wir führten ein kleines Experiment mit einem Domänengraphen von 1209 Knoten durch, um die Stabilität von k-Medoiden zu testen. Für zwei verschiedene Läufe des Algorithmus mit allen Modifikationen haben wir die "zentralsten" Knoten (gemäß der Harmonischen-Zentralitäts-Metrik) in jedem Cluster gefunden - ein Viertel der Gesamtzahl der Knoten im Cluster, jedoch nicht weniger als acht. Dann haben wir für jeden Cluster der ersten Partition einen Cluster der zweiten Partition gefunden, der die größte Anzahl seiner „zentralen“ Knoten enthält. Wenninline_formulaDann ist es für die meisten Partitionspaare nur für 9-10 Cluster aus dem ersten Durchlauf möglich, ein Analogon aus dem zweiten zu finden, bei dem mindestens die Hälfte der „zentralen Knoten“ zusammenfallen. Dies reicht natürlich nicht aus, um beispielsweise Segmente für Werbekampagnen aufzubauen. Gleichzeitig ist nicht bekannt, welches Ergebnis in der Dynamik eingetreten wäre, da sich mit der Zeit sowohl die Popularität von Domänen als auch deren Beziehungen ändern.

    Die folgenden Artikel befassen sich mit diesem Problem: eins , zwei , drei. Sie sagen, dass das Hinzufügen oder Entfernen nur eines Scheitelpunkts die gesamte Partition radikal verändern kann und nicht nur die nächsten Nachbarn, sondern auch die entfernten Teile des Diagramms betrifft. Eine Lösung für dieses Problem ist die Mittelwertbildung von Clustern. Dies ist ein Versuch, den Ensemble-Ansatz, der sich im Unterricht mit einem Lehrer bewährt hat, für Clustering-Aufgaben anzupassen. Wenn Sie nicht nur einen, sondern beispielsweise 100 Läufe des Algorithmus ausführen und dann Gruppen von Eckpunkten (Kernel) finden, die immer in demselben Cluster zusammengefasst sind, sind diese Gruppen zeitlich viel stabiler als die Ergebnisse einzelner Läufe. Der einzige Nachteil dieser Methode ist ihre Geschwindigkeit: Dutzende Wiederholungen können Erfolge bei der Beschleunigung des Algorithmus zunichte machen. Wenn Sie jedoch die Kerne finden, können Sie den Graphen mit geringeren Verlusten abtasten, d. H. benutze clara.

    Wir haben eine etwas andere Option für die Beschaffung von Kernen implementiert. Für jedes Knotenpaar betrachten wir, in welchem ​​Anteil der Läufe sie in den gleichen Cluster fielen. Die erhaltenen Daten können als Gewicht der Rippen (Grad der Nähe) in einem neuen, vollständigen Diagramm interpretiert werden. Weiter wird auf dieser Grafik hierarchisches Clustering aufgebaut. Wir haben die agglomerative Methode scipy.linkage und die Ward-Methode als Funktion der Entfernung beim Clustering verwendet.

    Hier sehen Sie die Vollversion des Dendrogramms.

    Die Abschaltschwelle kann auf eine beliebige Höhe eingestellt werden, während eine andere Anzahl von Clustern empfangen wird. Es mag am logischsten erscheinen, einen solchen Schwellenwert so festzulegen, dass die Anzahl der Cluster gleich der Anzahl der Cluster in jedem k-medoids-Lauf ist, wenn das Dendrogramm selbst empfangen wird. Seltsamerweise können in der Praxis jedoch inline_formulalogische „Untergemeinschaften“ mit viel geringerer Größe unterschieden werden , wenn Sie die richtige für k-Medoide auswählen . Zum Beispiel wurde in dem Teil des Baums darunter ein türkisfarbener Cluster bei einer Schwelle von 12 Kernen erhalten, während die Schwelle gesenkt wurde. Dieser Cluster könnte in zwei sinnvolle Subcluster aufgeteilt werden: Autos von oben und Psychologie von unten. Hier ist ein Screenshot:


    Ein Cluster von Büchern und Stücken von Spielen und Serien fiel ebenfalls in den Rahmen

    Mit dieser Methode erhaltene Domain-Kernel fungieren erfolgreich als Benutzersegmente in unserem Exebid.DCA- RTB-System .

    Es gibt bereits mehrere hervorragende Community-Zuweisungsalgorithmen, die schneller und effizienter sind als unsere Best Practices. Louvain, MLR-MCL, SCD, Infomap, Spinner, Stochastic Blockmodeling sind einige davon. In Zukunft planen wir, über unsere Experimente mit diesen Methoden zu schreiben. Aber wir wollten selbst etwas schreiben. Hier sind einige Bereiche für Verbesserungen:

    • Die Berechnung des Jacquard-Maßes ist die ressourcenintensivste Phase, die inline_formulaOperationen erfordert . Bekannt für eine schnelle ungefähre Methode zur Ermittlung von Ähnlichkeiten, die als MinHash bezeichnet wird. Lesen Sie mehr über sie, können Sie zum Beispiel hier . Es gibt ausgefeiltere Methoden wie BayesLSH.

    • Die Komplexität der Berechnungen ist abhängig von der Anzahl der Cluster. Aufgrund dieser Eigenschaft von k-medoids ist sie für eine Vielzahl von Aufgaben nicht anwendbar. Sie können damit folgendermaßen umgehen: Suchen und speichern Sie für jedes Medoid bei jeder Iteration eine Liste der „benachbarten“ Medoide, und zählen Sie sie nur bei jeder Iteration nach.

    • Die Beliebigkeit bei der Wahl der Anzahl der Cluster inline_formulaist eine weitere Schwierigkeit bei k-Medoiden. Ein Ausweg besteht darin, eine sinnvolle Metrik zu finden, anhand derer die Ergebnisse für verschiedene Metriken verglichen werden können inline_formula. Diese Rolle wird vom ÖRK (Weighted Community Clustering Coefficient) beansprucht, der auf der Analyse von geschlossenen Dreiecken innerhalb und außerhalb der Cluster basiert. Vielleicht sollte die Wahl des optimalen Ersatzes bei jeder Iteration auch in diese Metrik übersetzt werden.

    Vielen Dank für Ihre Aufmerksamkeit!

    Nur registrierte Benutzer können an der Umfrage teilnehmen. Bitte komm rein .

    Wem sollten die folgenden Artikel des Zyklus gewidmet sein?

    • 77,2% Detaillierte Analyse der neuesten Clustering-Algorithmen 51
    • 51,5% Experimente mit anderen Algorithmen, mit Beispielen und Code 34
    • 12,1% Neue Verbesserungen bei k-medoids 8
    • Tutorial zur 18,1% -Visualisierung in networkx 12
    • 24,2% Visualisierungs-Tutorial in Graph-Tool oder Gephi 16
    • 3% Nichts. Rybachuk ist traurig. 2

    Jetzt auch beliebt: