Markov-Clustering-Algorithmus

Question

Markov-Clustering-Algorithmus

8

Ich habe das folgende Beispiel für die Details des Markov-Clustering-Algorithmus durchgearbeitet:

Ich habe den Eindruck, dass ich den Algorithmus korrekt dargestellt habe, aber ich bekomme nicht die gleichen Ergebnisse, die zumindest dieser Leitfaden für diesen Input erhalten hätte.

Der aktuelle Code lautet: Ссылка

Ich bin mir nicht sicher, ob ich vielleicht gerade eine kleine Tatsache verpasst habe oder nur eine kleine Verbesserung brauche, aber ich habe ein paar Variationen ausprobiert, einschließlich:

Austauschen der Inflation / Expansion
Überprüfung auf Gleichheit basierend auf einer Genauigkeit
Entfernen der Normalisierung (da das ursprüngliche Handbuch dies nicht erfordert hat, obwohl die offizielle MCL-Dokumentation angibt, die Matrix bei jedem Durchgang zu normalisieren)

Alle haben das gleiche Ergebnis zurückgegeben - der Knoten beeinflusst nur sich selbst.

Ich habe sogar eine ähnliche Algorithmusimplementierung in VB gefunden: Ссылка

Und mein Code scheint mit Ausnahme ihrer Nummerierung übereinzustimmen (600 - Abstand zum Beispiel).

Dies ist die Erweiterungsfunktion

%Vor%

Und das ist die Inflationsfunktion

%Vor%

Und schließlich die Hauptdurchgangsfunktion

%Vor%

javascript cluster-analysis markov

methodin 06.01.2012, 20:50

quelle

2 Antworten

0

Die Verwendung von currentMatrix.slice zum Klonen einer Matrix wirkt verdächtig. Es ist ein seichter Klon, und da du mutierst, kann das Ärger machen.

Die Verwendung von Runde sieht auch ein wenig seltsam aus, da Rundung nicht als Teil des Normalisierungsschritts in dieser PowerPoint-Präsentation erwähnt wird.

dyoo 06.01.2012 23:43

quelle

Tags und Links javascript cluster-analysis markov

Django: Verwenden von Annotate, Count und Distinct in einem Queryset Strict pointer aliasing: Gibt es eine Lösung für ein bestimmtes Problem?

score 2 · Accepted Answer

Ihre Implementierung ist korrekt. Das Beispiel ist einfach falsch.

Die drei Ergebnismatrizen auf der Folie "Schritte 5 und 6 wiederholen, bis ein stetiger Zustand erreicht ist (Konvergenz)" sind die Ergebnisse, wenn NUR die Inflation durchgeführt wird.

Um einige Punkte über den Algorithmus zu klären.

Expantion dann Inflation.
Präzision ist ein wichtiger Faktor. Die Gleichungen können niemals mathematisch zur Konvergenz führen. Es ist die begrenzte Genauigkeit von Gleitkommaoperationen auf CPUs, die dazu führen, dass einige Elemente in der Matrix zu Null statt zu unendlich kleinen Zahlen werden. Tatsächlich verwendet die offizielle Implementierung einen Grenzwert, um eine bestimmte Anzahl von Elementen pro Spalte zu eliminieren, um die Konvergenz zu beschleunigen und die Zeitkomplexität des Algorithmus zu verbessern. In der ursprünglichen Arbeit analysierte der Autor den Effekt und kam zu dem Schluss, dass der Cutoff in der Praxis das gleiche Ergebnis liefert wie ein leichter Anstieg des Inflationsparameters.
Normalisierung ist ein integraler Bestandteil des Inflationsschritts, lesen Sie die Gleichung in diesem Leitfaden erneut.

Was Ihren Code betrifft.

array.slice erstellt eine flache Kopie, aber das ist in Ihrem Fall nicht wichtig, da Sie in matrixExpand ein neues Array erstellen.
Ihre Implementierung von matrixExpand ignoriert die pow-Variable und macht immer eine Potenz von 2.

Das Ergebnis, bei dem alle Einsen in der ersten Zeile stehen, wird erwartet, was interpretiert wird, da sich alle Elemente im selben Cluster befinden.