Sequentielles Pattern Mining für eine einzelne Sequenz

8

Kann mir jemand einen Hinweis auf einen guten Ansatz geben, um häufige Muster in einer einzigen Sequenz zu finden?

Zum Beispiel gibt es die einzelne Sequenz

3 6 1 2 7 3 8 9 7 2 2 0 2 7 2 8 4 8 9 7 2 4 1 0 3 2 7 2 0 3 8 9 7 2 0

Ich suche nach einer Methode, die häufige Muster in dieser geordneten Reihenfolge erkennen kann:

3 6 1 [2 7] 3 [8 9 7 2] 2 0 [2 7] 2 8 4 [8 9 7 2] 4 1 0 3 [2 7] 2 0 3 [8 9 7 2] 0

Auch andere Informationen wären interessant wie:

  • Wie groß ist die Wahrscheinlichkeit, dass 7 nach 2 kommt?
  • Wenn jeder Nummer ein Zeitstempel zugewiesen ist, wie hoch ist das geschätzte Zeitintervall, in dem 7 nach 2 auftritt

Die von mir gefundenen sequentiellen Pattern-Mining-Methoden erfordern mehrere Sequenzen, aber ich habe eine große Sequenz, in der ich Regelmäßigkeiten erkennen möchte.

Vielen Dank für jede Hilfe!

MikeHuber
quelle

Antworten:

3

Berechnen Sie ein Histogramm von N-Gramm und Schwellenwert auf einem geeigneten Niveau. In Python:

from scipy.stats import itemfreq
s = '36127389722027284897241032720389720'
N = 2 # bi-grams
grams = [s[i:i+N] for i in xrange(len(s)-N)]
print itemfreq(grams)

Die N-Gramm-Berechnung (Zeilen drei und vier) ergibt sich aus dieser Antwort.

Die Beispielausgabe ist

[['02' '1']
 ['03' '2']
 ['10' '1']
 ['12' '1']
 ['20' '2']
 ['22' '1']
 ['24' '1']
 ['27' '3']
 ['28' '1']
 ['32' '1']
 ['36' '1']
 ['38' '2']
 ['41' '1']
 ['48' '1']
 ['61' '1']
 ['72' '5']
 ['73' '1']
 ['84' '1']
 ['89' '3']
 ['97' '3']]

72 ist also die häufigste zweistellige Teilsequenz in Ihrem Beispiel und tritt insgesamt fünfmal auf. Sie können den Code für alle ausführen, die Sie interessieren.N

mmh
quelle
Danke für den Hinweis, das ist ein guter Ausgangspunkt. Aber gibt es auch einen Ansatz, der auch die Vorhersage des nächsten Elements auf der Grundlage von Wahrscheinlichkeiten usw. ermöglicht?
MikeHuber
1
Das ist ein viel schwierigeres Problem (Sie sollten es vielleicht in einer separaten Frage stellen). Eine Idee, die in den Sinn kommt, ist, dass Sie, wenn Sie feststellen, dass eine lange Sequenz sehr häufig auftritt, diese für einige Vorhersagen verwenden können. Wenn Sie beispielsweise feststellen, dass 8972 sehr häufig vorkommt, wissen Sie, dass vor 72 89 steht.S
mmh
1
Außerdem wollte ich fragen, was Ihre Sequenzen darstellen.
mmh
Eine Anwendung, für die ich es verwenden möchte, ist die Analyse von Fehlern oder Alarmen, die ich in einer Protokolldatei finde. Eine interessante Sache ist es, häufige Fehlermuster zu finden, aber auch die Vorhersage eines zukünftigen Fehlers basierend auf der vergangenen Sequenz wäre interessant. Deshalb habe ich nach Hilfe gesucht, welcher Ansatz / welche Methode für diese Art von Problemen verwendet werden kann.
MikeHuber
1

Ich denke, Sie können den Apriori-Algorithmus verwenden . Zählen Sie die Anzahl der einzelnen Elemente in der Sequenz. Wenn die Anzahl größer als ein Schwellenwert ist, ist das Element häufig. Zählen Sie dann die Anzahl der Paare häufiger Elemente. Fahren Sie mit der Anzahl der häufigen Tupel usw. fort.ε4

fehlende Daten
quelle
1

Sie könnten so etwas wie das Folgende verwenden. Soweit ich weiß, verwendet SPADE auch etwas Ähnliches für mehrere Sequenzen.

36127389722027284897241032720389720

Zuerst müssen Sie die Positionen aller Elemente in Ihrer Sequenz erfassen.

Länge: 1

{
    0: [11,23,28,34], //4
    1: [2,22], //2
    2: [3,9,10,12,14,20,25,27,33], //9
    3: [0,5,24,29], //4
    4: [16,21], //2
    5: [], //0
    6: [1], //1
    7: [4,8,13,19,26,32], //6
    8: [6,15,17,30], //4
    9: [7,18,31] //3
}

Überprüfen Sie dann die Unterstützung dieser Elemente anhand der Mindestunterstützung, die Sie für häufige Sequenzen auswählen.

min_sup: 3

{
    0: [11,23,28,34], //4
    2: [3,9,10,12,14,20,25,27,33], //9
    3: [0,5,24,29], //4
    7: [4,8,13,19,26,32], //6
    8: [6,15,17,30], //4
    9: [7,18,31] //3
}

In Ihrem Fall müssen Sie die Elemente mit aufeinanderfolgenden Positionen finden. Sie können auch Platzhalter verwenden, aber in diesem Fall beträgt der Positionsunterschied mehr als 1 und Sie finden viel mehr Kandidaten.

Länge: 2

{
    00: [], //0
    02: [[11,12]], //1
    03: [[23,24],[28,29]], //2
    07: [], //0
    08: [], //0
    09: [], //0
    20: [[33,34]], //1
    22: [[9,10]], //1
    23: [], //0
    27: [[3,4],[12,13],[25,26]], //3
    28: [], //0
    29: [], //0
    30: [], //0
    32: [[24,25]], //1
    33: [], //0
    37: [], //0
    38: [[5,6],[29,30]], //2
    39: [], //0
    70: [], //0
    72: [[8,9],[13,14],[19,20],[26,27],[32,33]], //5
    73: [[4,5]], //1
    77: [], //0
    78: [], //0
    79: [], //0
    80: [], //0
    82: [], //0
    83: [], //0
    87: [], //0
    88: [], //0
    89: [[6,7],[17,18],[30,31]], //3
    90: [], //0
    92: [], //0
    93: [], //0
    97: [[7,8],[18,19],[31,32]], //3
    98: [], //0
    99: [] //0
}

min_sup: 3

{
    27: [[3,4],[12,13],[25,26]], //3
    72: [[8,9],[13,14],[19,20],[26,27],[32,33]], //5
    89: [[6,7],[17,18],[30,31]], //3
    97: [[7,8],[18,19],[31,32]], //3
}

Sie können versuchen, die oberen Sequenzen basierend auf dem Ende zu kombinieren, oder Sie können einfach die Positionen überprüfen.

Länge: 3

{
    272: [[12,13,14],[25,26,27]], //2
    727: [], //0
    897: [[6,7,8],[17,18,19],[30,31,32]], //3
    972: [[7,8,9],[18,19,20],[31,32,33]] //3
}

min_sup: 3

{
    897: [[6,7,8],[17,18,19],[30,31,32]], //3
    972: [[7,8,9],[18,19,20],[31,32,33]] //3
}

Länge: 4

{
    8972: [[6,7,8,9],[17,18,19,20],[30,31,32,33]] //3
}

min_sup: 3

{
    8972: [[6,7,8,9],[17,18,19,20],[30,31,32,33]] //3
}

Es gibt nur ein Muster und Sie können es nicht mit sich selbst kombinieren, sodass der Abbau abgeschlossen ist.

{
    27: [[3,4],[12,13],[25,26]], //3
    72: [[8,9],[13,14],[19,20],[26,27],[32,33]], //5
    89: [[6,7],[17,18],[30,31]], //3
    97: [[7,8],[18,19],[31,32]], //3
    897: [[6,7,8],[17,18,19],[30,31,32]], //3
    972: [[7,8,9],[18,19,20],[31,32,33]] //3
    8972: [[6,7,8,9],[17,18,19,20],[30,31,32,33]] //3
}

Wenn wir die Untermuster von 8972 ausschließen.

{
    27: [[3,4],[12,13],[25,26]], //3
    72: [[13,14],[26,27]], //2
    8972: [[6,7,8,9],[17,18,19,20],[30,31,32,33]] //3
}

min_sup: 3

{
    27: [[3,4],[12,13],[25,26]], //3
    8972: [[6,7,8,9],[17,18,19,20],[30,31,32,33]] //3
}

Ich denke, es ist das gleiche wie die Muster, die Sie gefunden haben.

361[27]3[8972]20[27]284[8972]4103[27]203[8972]0

Eine weitere Option, um die 72 ebenfalls beizubehalten, da sie dreimal als Teilsequenz von 8972 und zweimal unabhängig von 8972 auftritt. Ich denke, dies sollte davon abhängen, ob Sie Überlappungen zulassen.

361[27]3[89(72)]202(72)84[89(72)]4103[2(7]2)03[89(72)]0

Hinweis: Ich denke nicht, dass sequentielles Pattern Mining als maschinelles Lernen betrachtet wird.

inf3rno
quelle