连续序列数据中的模式

Question

假设我有一个事件列表。例如 A, D, T, H, U, A, B, F, H, ....

我需要的是找到在完整序列中出现的频繁模式。在这个问题中，我们不能使用像先验或 fp 增长这样的传统算法，因为它们需要单独的项目集。而且，我无法将此流分成更小的集合。

知道哪种算法适合我吗？

编辑

例如，对于序列 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

Answer 1

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

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

现在的问题是，较小子串的元素顺序是否重要。

如果没有，您可以尝试运行标准关联挖掘算法。

如果是，那么顺序在整个序列及其子序列中都很重要，这使得这是一个信号处理或时间序列问题。但即使顺序很重要，我们也可以继续以这种方式分析所有子串。我们可以尝试匹配它们，精确匹配或模糊匹配之类的。

Answer 2

这是频繁项集挖掘的一个特殊变体，称为顺序模式挖掘。

如果您查找此主题，您会发现几十种算法。

有 GSP、SPADE、PrefixSpan 等等。

Answer 3

这是一个简单的算法（在 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;
    }
}

然后使用排序算法按字典的值对字典进行排序。

Answer 4

您可以尝试使用通配符 and/or 的 aho-corasick 算法，仅对所有子字符串进行处理。 Aho-corasick 基本上是一个有限状态机，它需要一个字典，然后它可以非常快速地在搜索字符串中找到多个模式。您可以使用 trie 和广度优先搜索构建有限状态机。这是一个很好的动画示例：http://blog.ivank.net/aho-corasick-algorithm-in-as3.html。所以您基本上需要 2 个步骤：构建有限状态机并搜索字符串。

连续序列数据中的模式

Pattern in continuous sequence data

algorithm

frequency

data-mining

sequence-analysis