Der wahrscheinlichste Pfad zum Erreichen eines bestimmten Knotens in Grafik

Question

Wir haben ein System, in dem der Kunde kommt und interagiert, Jobs auslöst und viele Aktionen ausführt. Wir haben 1000 solcher Benutzer. Jeder Job hat einen Namen und unsere Backend-Datenbank enthält alle Daten über die Kundeninteraktionen.

Diese Jobs schlagen häufig fehl. Wir wissen, warum ein bestimmter Job aufgrund seiner Eingaben fehlgeschlagen ist, aber jetzt möchten wir herausfinden, welchen Weg der Benutzer genommen hat (Reise), bevor er den Fehlerjob erreicht hat. Wir wollen sehen, ob wir die Erfahrung viel früher verbessern können, so dass der Fehler vermieden wird.

Beispiel (hypothetisch), Login-> Datei erstellen-> Datei speichern -> Datei herunterladen. Download-Datei schlägt mit einem Fehler fehl. Angenommen, das passiert normalerweise, wenn gerade ein Speichervorgang abgeschlossen wurde. Wenn Sie eine Operation zwischen Datei speichern und herunterladen durchgeführt haben, schlägt das Herunterladen fehl. Das ist möglicherweise ein versteckter Fehler.

Die Frage ist - eine Geschichte von 3000 Benutzern Graph Traversal Given (nehmen Pfade der Größe 5 [als ein mir bewegendes Fenster]) baut ein System, dass, wenn Sie gefragt **

„Was sind die wahrscheinlichsten Pfade Knoten X“

gibt die Top-5 höchstwahrscheinlichen Pfade zu erreichen X.

ich die Knoten erstellt haben zu erreichen, wie [jobname] [State], beispielsweise loginSuccess-> createFileSuccess-> SaveFi leSuccess-> DownloadFailed. X wird typischerweise ein [Jobname] fehlgeschlagener Knoten sein, den wir abfragen werden. Wir haben etwa 50 Jobs und 3 Staaten, Erfolg, fehlgeschlagen abgebrochen.

Irgendeine Idee, wie man dieses Modell baut, welchen Algorithmus zu verwenden, und wie man die Wahrscheinlichkeiten umkehrt, wenn ein Knoten gefragt wird?

etwas mehr Klarheit Hinzufügen -

ein Zielknoten gegeben, kann ich Liste, was die wahrscheinlichsten Wege zu waren erreichen es mit der Länge 5. Ich habe nicht die Ausgangspunkte kennen die Dijkstra zu starten. Auch ein direkter Pfad von geringer Wahrscheinlichkeit könnte aus einem verläßt gegebenen Knoten beginnend direkt an den Zielknoten, aber ich brauche Wege der Länge 5.

Answer 1

Der erste Schritt, den ich finden würde wäre ein konstruieren Liste von Datensätzen der Länge 5, wobei jeder solche Datensatz die 5 Schritte enthält, die von einem bestimmten Kunden bis zu Knoten X ausgeführt wurden. Dann können Sie diese Liste einfach sortieren und die Anzahl der Male zählen, die jeder mögliche Datensatz darin vorkommt, um den beliebtesten Datensätze. Ein anderer Ansatz wäre, jeder Kante, die einen Knoten verlässt, eine Punktzahl zuzuordnen, die der Bruchteil der Pfade war, die diesen Knoten verlassen haben, um ihn über diese Kante zu verlassen. Berechnen Sie dann die Gesamtpunktzahl für einen Pfad, indem Sie die Punktzahlen für seine Kanten miteinander multiplizieren, und nehmen Sie erneut die beobachteten Pfade mit den höchsten Punktzahlen.

Answer 2

Von dem, was ich verstanden habe, müssen Sie Pfad am häufigsten von Benutzern gefolgt finden, und Sie können Knoten für jeden Prozess und zwei Prozesse miteinander verbunden werden, wenn ein Kunde von einem Prozess zu anderen geht.

STEP 1. Construct a graph for all 3000 users which will be a weighted graph 
     (as such weight of an edge will be number of times a user goes from 
     one process to another, so each time you find an already built edge 
     increment its weight by 1 or else make a new edge with weight =1) 

Nun finden wahrscheinlichste Weg vom Quellknoten zu einem anderen

STEP 2. Apply Dijkstra's algorithm but with small change. 
     Dijkstra's algo find smallest path from one node to every other 
     node,so you need to find maximum path from one node to another. 

Ich denke, es sollte funktionieren wie alle Kanten positives Gewicht haben und es wird Ihnen den wahrscheinlichste Weg aus genommen geben ein Knoten zu einem anderen von allen Benutzern und Sie könnten leicht Daten aller Knoten von Quelle zu Zielknoten sehr leicht erhalten.

Aber es wird Ihnen nur den wahrscheinlichsten Weg und nicht Top 5 von ihnen geben.