連續序列數據中的模式

假設我有一個事件列表。例如A, D, T, H, U, A, B, F, H, ...。連續序列數據中的模式

我需要的是找到完整序列中出現的頻繁模式。在這個問題中，我們不能使用先驗或fp增長等傳統算法，因爲它們需要單獨的項目集。而且，我不能把這個流分成更小的集合。

任何想法哪種算法適合我？

EDIT

例如，對於序列A, D, T, H, U, A, D, T, H, T, H, U, A, H, T, H，並用min_support = 2。

頻繁模式將是

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

來源

2015-10-18 Haris

我認爲這個問題太廣泛了，但作爲第一個猜測，你可能想看看[iSAX]（http://www.cs.ucr.edu/~eamonn/iSAX/iSAX.html ） – Marco13

我只想在那個大流中找到所有長度的頻繁模式。搜索了很多東西之後，我在互聯網上找不到任何東西。 – Haris

[「字符串」壓縮]（https://en.wikipedia.org/wiki/Lossless_compression#General_purpose）算法嘗試利用（至少是本地的）可預測的序列概率非均勻性。 – greybeard

您可以嘗試aho-corasick算法，使用通配符和/或僅包含所有子字符串。 Aho-corasick基本上是一個有限狀態機，它需要一個字典，但隨後它會在搜索字符串中非常快地找到多個模式。您可以構建一個帶有樹狀結構和廣度優先搜索的有限狀態機。這裏是動畫的一個很好的例子：http://blog.ivank.net/aho-corasick-algorithm-in-as3.html。所以你需要基本上2個步驟：構建有限狀態機並搜索字符串。

來源

2015-11-12 19:48:48 Bytemain

它非常接近爲所有可能的子字符串構建*後綴樹，然後使用它來檢查模式。其實，這正是我正在考慮的。 – Haris

您可以生成所有可能的子串，如：

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

現在的問題是，不元素較小的子關係的順序。

如果不是，您可以嘗試運行標準關聯挖掘算法。

如果是，那麼該順序在整個序列及其子序列中很重要，這使得這成爲信號處理或時間序列問題。但即使順序很重要，我們仍然可以繼續以這種方式分析所有子字符串。我們可以嘗試匹配它們，完全匹配或模糊匹配以及類似的東西。

來源

2015-10-18 11:48:59 dimm

對於一個非常大的序列，這不需要很多時間。要生成所有可能的子字符串將需要指數時間。 – Haris

有n^2個子字符串。我認爲這是可行的。 – dimm

這似乎是可行的，但我需要存儲每個序列與其發生頻率來選擇最佳的一個。 – Haris

這是頻繁項目集挖掘的一個特定變體，被稱爲序列模式挖掘。

如果你看這個話題，你會發現幾十個算法。

有GSP，SPADE，PrefixSpan等等。

來源

2015-10-18 14:58:31

一個不能使用GSP。或SPADE，因爲它們在已經出現的彼此分離的序列上工作。不是一個大的連續序列。 – Haris

例如，你可以在那個序列的ngrams上運行它。 –

我沒有得到你，你能否通過編輯你的答案來闡述一點。 – Haris

下面是一個簡單的算法（在JavaScript中），它將生成所有子字符串的計數。

保留字典中子字符串出現次數。遍歷流中的每一個可能的子串，如果它已經在字典中，增加它，否則用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; 
    } 
}

值添加它然後使用一個排序算法通過其價值觀訂購字典。

來源

2015-11-09 16:21:16

是的，這已被建議。但我想要一些更有效的方式，然後暴力。 – Haris

你看過http://stackoverflow.com/q/2560262/5111146嗎？ –

這看起來像一個很好的來源。謝謝，我會通過它。 – Haris

連續序列數據中的模式

回答

相關問題