如何从序列集中挖掘带变量推断的通用序列模式？

问题说明 #

需要从一组序列中提取能覆盖所有序列公共特征的模式序列。这类序列是事件的有序列表，每个事件为特征多重集（bag）——事件内元素可重复、顺序无关，但序列中事件的顺序固定。

单个序列示例 #

[{'a', 'y'}, {'H', 'b'}, {'C', 'F', 'c'}]

输入输出示例 #

输入序列集 #

[
[{'a', 'y'}, {'H', 'b'}, {'x'}, {'C', 'F', 'c'}],
[{'a', 'd'}, {'b', 's'}, {'l'}, {'F', 'c', 'k'}],
[{'J', 'a'}, {'H', 'b'}, {'b'}, {'c', 'c', 'm'}],
[{'W', 'a'}, {'H', 'b'}, {'m'}, {'K', 'c', 'z'}],
[{'a', 'h', 'm'}, {'L', 'b', 'y'}, {'b', 'x'}, {'H', 'c', 'g'}]
]

期望输出 #

[{'a', '*'}, {'b', '*'}, {'*'}, {'c', '*', '*'}]

输出含义 #

• 所有序列的第一个事件必含固定元素'a'，且至少带一个可变元素（用*表示）；
• 第二个事件必含固定元素'b'，且至少带一个可变元素；
• 第二个事件与最后一个事件之间，存在至少一个包含任意元素的事件（用单独*表示）；
• 最后一个事件必含固定元素'c'，且至少带两个可变元素。

传统算法的局限性 #

传统序列模式挖掘算法（如BIDE、PrefixSpan、Apriori等）仅能处理元素固定的事件序列，无法识别这类包含可变元素的事件模式。

以下是用Python prefixspan包测试PrefixSpan算法的结果，完全无法得到预期模式：

测试代码 #

from prefixspan import PrefixSpan

# 函数要求事件为可哈希类型，因此将每个事件转为元组
db = [[('y', 'a'), ('H', 'b'), ('x',), ('F', 'C', 'c')],
     [('a', 'd'), ('b', 's'), ('l',), ('F', 'k', 'c')],
     [('J', 'a'), ('H', 'b'), ('b',), ('m', 'c')],
     [('a', 'W'), ('H', 'b'), ('m',), ('z', 'K', 'c')],
     [('h', 'm', 'a'), ('b', 'y', 'L'), ('x', 'b'), ('g', 'H', 'c')]]

# 初始化PrefixSpan对象
ps = PrefixSpan(db)

# 获取支持度为5（覆盖所有序列）的闭序列模式
print(ps.frequent(5, closed=True))

>>[]

将支持度降至2时，结果仅为：

print(ps.frequent(2, closed=True))
>>[(3, [('H', 'b')])]

内容的提问来源于stack exchange，提问作者Leen