Muster in kontinuierlichen Sequenzdaten

Question

Angenommen, ich habe eine Liste von Ereignissen. Zum Beispiel A, D, T, H, U, A, B, F, H, ....

Was ich brauche ist, häufige Muster zu finden, die in der vollständigen Sequenz auftreten. In diesem Problem können wir keine traditionellen Algorithmen wie a priori oder fp growth verwenden, da sie separate Elementmengen benötigen. Und ich kann diesen Stream nicht in kleinere Sets aufteilen.

Jede Idee, welcher Algorithmus würde für mich arbeiten?

---

EDIT

Zum Beispiel für die Sequenz A, D, T, H, U, A, D, T, H, T, H, U, A, H, T, H und mit min_support = 2.

Die häufigen Muster wird

Of length 1 --> [A, D, T, H, U] 
Of length 2 --> [AD, DT, TH, HU, UA, HT] 
Of length 3 --> [ADT, DTH, THU, HUA] 
Of length 4 --> [ADTH, THUA] 
No sequences of length 5 and further 

Answer 1

Sie können Aho-Corasick-Algorithmus mit einem Platzhalter und/oder nur mit allen Teilstrings versuchen. Aho-corasick ist im Grunde eine endliche Zustandsmaschine, es benötigt ein Wörterbuch, aber dann findet es mehrere Muster in der Suchkette sehr schnell. Sie können einen endlichen Automaten mit einem Trie und einer Breitensuche erstellen. Hier ist ein schönes Beispiel mit Animation: http://blog.ivank.net/aho-corasick-algorithm-in-as3.html. Sie benötigen also grundsätzlich 2 Schritte: Erstellen Sie den endlichen Automaten und suchen Sie den String.

Answer 2

Sie alle möglichen Teil erzeugen können, zB .:

A 
AD 
ADT 
ADTH 
... 
D 
DT 
DTH 
... 

Nun ist die Frage, wird die Reihenfolge der Elemente die kleineren Teil Materie.

Wenn nicht, können Sie versuchen, Standard-Association Mining-Algorithmen auszuführen.

Wenn ja, dann ist die Reihenfolge in der gesamten Sequenz und ihren Untersequenzen von Bedeutung, was dies zu einem Signalverarbeitungs- oder Zeitreihenproblem macht. Aber selbst wenn die Reihenfolge wichtig ist, können wir diesen Weg mit allen Teilsträngen fortsetzen. Wir können versuchen, sie zu vergleichen, genaue Übereinstimmung oder Fuzzy-Match und solche Sachen.

Answer 3

Dies ist eine besondere Variante von häufige Itemset Mining, bekannt als sequenzielle Musterbergbau.

Wenn Sie nach diesem Thema suchen, finden Sie buchstäblich Dutzende von Algorithmen.

Es gibt GSP, SPADE, PrefixSpan und viele mehr.

Answer 4

Hier ist ein einfacher Algorithmus (in JavaScript), der eine Zählung aller Teilstrings generiert.

Behalten Sie eine Anzahl von Substring-Vorkommen in einem Wörterbuch. Iterieren jede mögliche Teilkette in den Strom über, und wenn es schon im Wörterbuch enthalten ist, erhöht es, sonst fügen Sie es mit einem Wert von 1.

var stream = 'FOOBARFOO'; 
var substrings = {}; 
var minimumSubstringLength = 2; 

for (var i = 1; i <= stream.length; i++) { 
    for (var j = 0; j <= i - minimumSubstringLength; j++) { 
     var substring = stream.substring(j, i); 
     substrings[substring] ? substrings[substring]++ : substrings[substring] = 1; 
    } 
} 

dann einen Sortieralgorithmus verwenden das Wörterbuch durch seine Werte zu bestellen.