C# Suche Algorithmus für Mustererkennung

[Varonimus]

Hallo ihr,

ich suche einen Algorithmus (nicht unbedingt die Implementierung) zur Mustererkennung.

Ganz vereinfacht soll der Algorithmus Stellen in einer Zahlenfolge markieren. Dazu soll er die wohl wahrscheinlichste Stelle markieren, die Reihenfolge ändert sich nicht.

Beispiel:
31517, 0, 247, 18471, 1642
wird manuell mit den Variablen belegt:
a, *, b, c, *

(nochmal zur Erklärung: a = 31517, b = 247 und c = 18471, die restlichen Werte sind egal)

In einem nächsten Zyklus sind die Zahlen so:
31517, 0, 8321, 245, 18472, 1642
nun soll(te) der Algorithmus liefern:

a, *, *, b, c, *

(also die 8321 ist hinzugekommen, die anderen Zahlen haben sich minimal geändert)

Die Variablen die nicht beachtet werden können dem Algorithmus zur Orientierung dienen.

Habt ihr irgendeine Idee? Genetischer Algo, Neuronales Netz, Bayessches, SOM vielleicht?

Vielen Dank!

 

[DarthSpot]

Dazu soll er die wohl wahrscheinlichste Stelle markieren, die Reihenfolge ändert sich nicht.

Die wahrscheinlichste Stelle bezogen worauf?

Was genau für ein Muster soll dein Algorithmus denn überhaupt erkennen? ^^ (Vielleicht bin ich auch nur zu blind um die Aufgabenstellung richtig zu deuten)

 

[kevchen01]

Wie soll was erkannt werden?

a = 31517 +-10
b = 247 +-10
c = 18471 +-10

Rest egal?

 

[DjNDB]

Du hast also Startwerte, und suchst in einer Zahlenfolge die Werte, die die geringste Differenz dazu haben?

Wenn ich das richtig verstehe, dann könntest du am Beispiel b z.B. jeweils 247 von jedem Wert der Folge abziehen, und die Differenz mit dem geringsten Betrag ist dann dein Treffer.

 

[M0sk1t0]

Es wäre sinnvoll zu wissen was du mit dieser Auswertung bezweckst, bzw. um was es geht.

So wie das jetzt für mich aussiehst möchtest du diverse Zahlenfolgen miteinander auf Gemeinsamkeiten vergleichen.

Dazu kannst du jede einzelne Zahl nehmen (dann einen Toleranzbereich einrichten, fest z.B. +/-100 oder dynamisch (90%-110%) des Wertes) und mit den Zahlen der anderen Reihen vergleichst und bei Treffern nen Counter erhöhen lässt. Am Ende lässt du dir dann die Zahlen mit den meißten Treffern oder so anzeigen.

Passt das?
Einen direkten Ansatz kann ich dir gerade nennen, weil sich mir der Sinn deiner Auswertung noch nicht erschlossen hat

 

[f1st]

Wenn du vorher weißt, in welchem Rahmen sich die Zahlen bewegen würde ich auch einfach Intervalle abschätzen, wie kevchen01 sagt.

Aber etwas mehr Hintergrundinformationen wären nett: Was suchst du da, warum suchst du es, was möchtest du am Ende haben.
Also gedanklich solltest du dich von den Ergebnissen, sprich den reinen Zahlen entfernen und dir überlegen wie das erzeugt wird, dann kannst du eher an Parameter oder allgemein Klassifizierungsarten denken.

 

[Turas]

Was ist denn die Eingabe? Ein computergeneriertes Bild? Ein Scan?

Ich habe eher den Eindruck, dass sich die eigentliche Problemstellung komplett ohne solche Algorithmen lösen lässt.

 

[Varonimus]

@DjNDB: Ah gut, das ist schonmal ein Ansatz!

@kevchen01: Also einen festen Wert +-10 soll das nicht sein. Als Mensch erkennt man auch leicht, selbst wenn die 247 nun eine 300 wäre, dass es immernoch eher dann diese Zahl ist, als bspw. die 8321

@DarthSpot: Der Algorithmus soll bei gleichbleibender Reihenfolge der zu findenden Positionen (also a, b und c) die Werte mit den geringsten Änderungen der neuen Zahlenfolge zuordnen.

Ergänzung (6. Februar 2012)

Vielen Dank für die vielen Antworten!!

@Turas, M0sk1t0: Die Problemlösung ist stark runtergebrochen. Es ist ein Memory-Dump eines Programms und ich möchte die beinhaltenden Werte zu Variablen zuordnen. Das hört sich aber leider nach Hack an und es ist eher eine Analyse ob sich eine Struktur geändert hat.
Das gleiche könnte man aber bspw. mit Excel / CSV Daten machen, bei denen man die Überschrift nicht mehr hat und diese aber automatisiert herausbekommen möchte.
Die Zahlen wären dann beispielsweise, Anzahl, Gewicht, Zuckeranteil bei Früchten und diese Variablen gilt es bei einer Veränderung der Struktur wieder zuzuordnen.

@f1st: Ein Mensch hat auch kein Problem eine Zahl einer Gruppe zuzuordnen. Dabei ist es fast egal wie groß die Abweichung ist.
0, 135, 35735, 5
danach
0, 135, 92, 35500, 16
Stimmt's ? Kein Problem herauszufinden, welche Zahl hinzugekommen ist.

 

[WinKill]

Wie schon jemand geschrieben hat werden mehr Informationen benötigt.

Als Ansatzpunkt:

"Als Mensch erkennt man auch leicht....": Ja, dabei vergleicht der Mensch viele Punkte gleichzeitig (gibt es andere Zahlen in diesen Wertebereich in der vorherigen Kette? Gibt es andere Zahlen in der neuen Kette? Falls eine der Fragen mit ja, könnten diese auch Matchen oder stimmen dann die anderen, die näher drann sind, nicht mehr mit ihrer Position? etc).
Diese musst Du aufschlüsseln und in Funktionalität packen, wenn Du es "Wie ein Mensch" haben willst.

Wie viele können pro Durchgang neu hinzukommen? Immer genau 1? Beliebig viele? Um wie viel können sich die Zahlen pro Durchgang maximal unterscheiden? Ist dies für verschiedene Zahlen unterschiedlich?
Diese Fragen entscheiden mit, welcher Ansatz für Dich greifen kann und welcher nicht.

Wenn Du schon keine Zeit/Lust hast, es detaillierter zu beschreiben, dann wirds eh nichts

Viele Grüße
Winni

 

[kevchen01]

Die Randbedingungen die zu einer Erkennung führen sollen sind von dir nicht genau vorgegeben.
Schwierig wird es nur, wenn "augenscheinlich" die Differenzen gleich groß zu anderen Werten ist.
So bei 135 und 5...
Was passiert dann in nächsten Durchlauf mit einer 70... der Abstand ist zu beiden der gleiche.

 

[Turas]

Wenn es ein Memory Dump ist, brauchst du doch keine Mustererkennung?! Was du brauchst ist eher RegEx - das hat wenigstens 100 % Erkennungsrate...

Falls du keinen Zugriff auf den Text hast: Wenn es eine Art Screenshot ist, ist es ein computergeneriertes Bild und du kannst einfaches Templatematching nutzen.

Edit: Falls der Memory Dump wirklich nur als Bild vorhanden ist, dann ist das ganze laufzeitmäßig hoffnungslos. Wie groß ist denn das Bild vom Memory Dump? Selbst ein 4 MB Memory Dump würde wahrscheinlich hunderte A4 Seiten füllen. Damit fällt jeder etwas komplere Algorithmus weg.

 

[Varonimus]

@kevchen01: Okay. Das ist ein gutes Argument. Wenn die 70 kommen würde, und man nun nicht mehr weiss, welcher Position man das zuordnen müsste, dann könnte man warten auf den nächsten "Dump" oder man nimmt dann einfach diese 70. Allerdings ist das dann auch egal, weil so ein Wert zu unwahrscheinlich ist.

Noch mehr Infos. Hmm ok:
Stellt euch vor man hat ein Spiel, welches täglich gepatcht wird. In diesem Spiel hat man typische Werte wie Leben, Mana, Geld, Level usw.
Die Werte stehen im RAM und sollen nun ausgelesen werden, damit man auf einem Tastatur-Display diese Werte sehen kann.
Dadurch, dass es aber täglich gepatcht wird, kann man sich nicht mehr sicher sein, dass die Variablen genau an der gleichen Stelle wie am Vortag stehen. Deswegen muss man diese neu suchen. Die Reihenfolge wird sich nicht ändern, aber wahrscheinlich die Anzahl der Werte, die nun neu gemapt werden müssen.
Leben und Mana bewegen sich dabei im Bereich von 0 - 100, Geld von 0 - MAXINT und Level wahrscheinlich von 0 - 30. Hinzu kommen noch ein paar Werte Inventar usw. Die keine Rolle spielen, aber zur Strukturanalyse hilfreich sein könnten.

 

[Turas]

Dann musst du ja nur den Speicher direkt auslesen ohne Mustererkennung

Meiner Meinung nach lässt sich das selbst mit direkten Speicherzugriff nur schwer lösen, da im Speicherbereich oft Zahlen zwischen 0 und 100 vorkommen können. Es gibt zu viele Statusvariablen und Enum-Werte in diesen Wertebereich.

 

[Varonimus]

Teilweise gebe ich dir da recht Turas, allerdings kann man mehr ablesen als man glaubt, vor allen, wenn man auch noch die Vergangenen Werte hat. Beim Leben und Mana Zeugs habe ich zum Beispiel konkret diese Werte:
currentHP, maxHP, currentMana, maxMana
1150, 1150, 800, 800
Da würde man sich ja nicht mehr in den ähnlichen 0-100 Regionen bewegen. Und somit müsste man dann ja auch mitbekommen wenn etwas hinzugefügt wird, oder?