2

我有一堆（数百万）小实验的日志。

每个日志都包含一个条目列表（数十到数百个）。每个条目是一个时间戳和一个事件 ID（有数千个事件 ID，每个可能在日志中出现多次）：

1403973044 阿尔法
1403973045 测试版
1403973070 伽玛
1403973070 阿尔法
1403973098 三角洲

我知道一个事件可能会在以后触发其他事件。

我正在研究这个数据集。我正在寻找在实验中经常发生的“稳定”事件序列。

有没有办法在不编写太多代码且不使用专有软件的情况下做到这一点？该解决方案应该具有足够的可扩展性，并且可以处理大型数据集。

我认为这个任务类似于生物信息学所做的——在 DNA 中寻找序列等。只有我的任务在一个字母表中包含四个以上的字母......（更新，感谢@JayInNyc：蛋白质组学处理比我更大的字母表。）

（注意，顺便说一句，我事先不知道我想要我的序列有多稳定和相似，最小序列长度是多少等。我正在研究数据集，并且必须在旅途中弄清楚这一点。）

无论如何，对我可以使用的方法/工具/库有什么建议吗？

更新：评论中问题的一些答案：

稳定序列：在实验中经常发现。（多久才够？还不知道。看来我需要计算链的顶部，并丢弃最稀有的。）

相似序列：看起来相似的序列。“根据您，序列'ABCD E'和'ABCE D'（序列上的微小差异）是否相似？序列'ABCD E'和'ABC 1 D E'（所选事件的发生顺序相同）是否也相似给你？” ——对这两个问题都是。更剧烈的突变可能也可以。同样，我希望能够计算出一个顶部并丢弃最不同的......

计时：我现在可以丢弃计时信息（但不能丢弃订单）。但是将它放在相似性指数公式中会很酷。

更新 2：预期输出。

最后，我想对最受欢迎的最长稳定链进行评级。所有三个因素的组合都应该对评分的计算产生影响。

显然，这种评级中的链更像是足够相似的链的集群。

链簇的合成示例：

α
测试版
伽玛
[垃圾]
[垃圾]
三角洲

其他：

α
测试版
伽马|zeta|ε
三角洲

（或者我现在没有想到的任何变体。）

所以，最终输出会是这样的（在这个例子中数字是完全随机的）：

链簇ID | 发现时间 | 时间刺。因素 | 链刺。因素 | 长度 | 分数
一个 | 12345 | 123 | 3 | 5 | 100000
乙| 54321 | 12 | 30 | 3 | 700000
4

2 回答 2

0

在过去的一天左右，我一直在考虑这个设置——如何在 bash 等中以合理的可扩展方式进行设置。答案实际上是由你想要从数据中提取的关系信息和表观大小驱动的您当前拥有的数据集。最精简的解决方案是将您的数据集加载到关系数据库中（MariaDB 会根据我的建议）

由于您的数据已经以相当干净的格式存在，因此将数据导入数据库的选项是 2。 (1) 如果文件在可用的 rowxcol 设置中包含数据，那么您可以简单地使用LOAD DATA INFILE将数据导入数据库; 或者（2）在一个场景中用bash解析文件while read line; do，解析数据得到你想要的表格格式的数据，使用mysql批处理方式直接将信息一次性加载到mysql中。bash 命令的一般形式是mysql -uUser -hHost database -Bse "your insert command".

一旦进入关系数据库，您就可以使用适当的工具来以理智的方式对您的数据运行灵活的查询，而不是每次都不断地编写/重写 bash 片段来以不同的方式处理您的数据。这可能是您正在寻找的最佳可扩展解决方案。前期工作多一些，但未来的设置要好得多。

于 2014-06-30T09:53:33.200 回答
0

维基百科将算法定义为“精确步骤的精确列表”：“我正在寻找在实验中经常发生的“稳定”事件序列。没有定义的“稳定”和“经常足够”使为您提供算法的任务变得不可能。

所以我给你一个简单的计算长度为2的序列的频率。我将忽略时间戳。这是 awk 代码（pW 代表上一个 Word，pcs 代表对计数器）：

#!/usr/bin/awk -f

BEGIN { getline; pW=$2; }

{ pcs[pW, $2]++; pW=$2; }

END {
    for (i in pcs)
        print i, pcs[i];
}

我复制了你的样本来展示一些有意义的东西

1403973044 alpha
1403973045 beta
1403973070 gamma
1403973070 alpha
1403973098 delta
1403973044 alpha
1403973045 beta
1403973070 gamma
1403973070 beta
1403973098 delta
1403973044 alpha
1403973045 beta
1403973070 gamma
1403973070 beta
1403973098 delta
1403973044 alpha
1403973045 beta
1403973070 gamma
1403973070 beta
1403973098 delta

运行上面的代码给出：

gammaalpha 1
alphabeta 4
gammabeta 3
deltaalpha 3
betagamma 4
alphadelta 1
betadelta 3

可以解释为 alpha 后跟 beta 和 beta 后跟 gamma 是最常见的长度两个序列，每个序列在样本中出现 4 次。我想这就是你对经常发生的稳定序列的定义。

下一步是什么？

(1) 您可以轻松地将上面的代码应用于长度为 N 的序列，并找到经常出现的序列，您可以对第二列的输出进行排序 (-k2nr)。

(2) 要限制 N，您可以规定没有事件自行触发，这为您提供了一个截止点。或者您可以限制时间戳，即连续事件之间的差异。

(3) 到目前为止，这些序列实际上是字符串，我在它们之间使用了精确匹配（CLRS 术语）。没有什么可以阻止您使用您最喜欢的相似性度量来代替：

{ pcs[CLIFY(pW, $2)]++; pW=$2; }

CLIFY 将是一个函数，它接受 k 个连续事件并将它们放入一个 bin 中，即也许您希望 ABCDE 和 ABDCE 进入同一个 bin。CLIFY 当然可以将迄今为止的垃圾箱集作为附加参数。

选择 awk 是为了方便。它不会飞，但您可以轻松地并行运行它们。

目前还不清楚你想用这个做什么，但谷歌搜索马尔可夫链，Mark V Shaney 可能会有所帮助。

于 2014-06-30T10:09:13.473 回答