CPT: 用紧致预测树进行序列预测

#TSer#

时间序列学术前沿系列持续更新中 ⛳️

后台回复"讨论"，加入讨论组一起交流学习吧 🏃

序列预测是近年来深度学习的热点应用之一。从推荐系统、自然语言处理还是时间序列分析，它的潜力似乎是无穷无尽的。这使得业界涌现出前所未有的解决方案，并推动着不断创新。

实现序列预测的方法多种多样，如机器学习域的马尔可夫模型、有向图等、深度学习域的RNNS/LSTM等等。

本文将介绍一种相对未知的名为算法：紧致预测树Compact Prediction Tree (CPT)，来执行序列预测。您将看到这是一个令人惊讶的简单技术，它比一些非常著名的方法比如：Markov方法、有向图等等更为强大。

项目地址：https://github.com/NeerajSarwan/CPT

概述

当我们可以预测某个特定事件可能会在另一个事件之后发生时，就需要进行序列预测，而且我们需要预测整个事件。

序列预测是一类广泛应用于各个行业的重要问题，例如：

• 网页预取-给定用户访问的网页序列，浏览器可以预测用户访问的最有可能的页面并预加载它。这会节省时间和改善用户体验。
• 产品推荐-根据用户将产品添加到其购物列表中的顺序来推荐用户可能感兴趣的产品。
• 临床事件的序列预测--鉴于病人的病史，可以利用序列预测对未来的疾病进行鉴别诊断。
• 天气预报-根据先前的天气情况，预测下一时间的天气。

解决这类问题，LSTMS/RNN已经成为顺序数据建模的热门选择，无论是文本、音频等。然而，他们有两个基本问题：

• 训练时间太长，通常需要几十个小时。
• 当序列中包含在以前的训练迭代中没有看到的项目时，需要重新训练。这个过程代价特别高，在经常遇到新项目的情况下是不可行的。

CPT

CPT算法使用了三种基本的数据结构，我们将在下面做简要介绍。

01

预测树

预测树带有多个节点，每个节点有三个数据元素：

• 数据项存储在节点中的实际数据项。
• 子节点-该节点是所有子节点的列表。
• 父节点-指向此节点的父节点的链接或引用。

预测树基本上是一种TRIE数据结构，它将整个训练数据压缩成一棵树的形式。对于那些不知道TRIE结构是如何工作的读者，下面两个序列的TRIE结构图将说明问题。

Sequence 1: A, B, C Sequence 2: A, B, D

TRIE数据结构从序列A、B、C的第一个元素A开始，并将其添加到根节点。然后B被添加到A， C被添加到B中。对于每个新的序列，如果一个元素已经被添加到结构中，TRIE再次从根节点开始，再次添加它。

产生的结构如上所示。这就是预测树如何有效地对训练数据进行压缩。

02

倒排索引

倒排索引是一种字典，其中的关键字是训练集中的数据项，值是该项出现的序列的集合。例如，

Sequence 1: A,B,C,D Sequence 2: B,C Sequence 3: A,B

上述序列的倒排索引如下所示：

II = {
‘A’:{‘Seq1’,’Seq3’},
’B’:{‘Seq1’,’Seq2’,’Seq3’},
’C’:{‘Seq1’,’Seq2’},
’D’:{‘Seq1’}
}

03

查找表

查找表是一个字典，带有序列ID和预测树中的序列的终端节点的关键字。例如：

Sequence 1: A, B, C Sequence 2: A, B, D

LT = {
'Seq1' : node(C),
'Seq2' : node(D)
}

如何在CPT中进行训练和预测呢？我们将通过一个例子来巩固我们对CPT算法中训练和预测过程的理解。下面是此示例的训练集：

正如你所看到的，上面的训练集有3个序列。让我们用ID表示序列：seq 1、seq 2和seq 3。A、B、C和D是训练数据集中的数据项。

CPT 的训练

‍‍‍‍

训练阶段包括同时建立预测树、倒排指数(II)和查找表(LT)。现在我们将看一看训练阶段的整个过程。

第一步：插入A,B,C

查找表

1. 我们已经有一个根节点和一个初始设置为根节点的当前节点。我们从A开始，检查作为根节点的子节点A是否存在。如果没有，我们将A添加到根节点的子列表中，在带有值为seq 1的倒排索引中添加一个A的条目，然后将当前节点移到A。
2. 查看下一项，即B，看看B是否作为当前节点的子节点存在，即A。如果不存在，我们将将B添加到A的子列表中，在带有SEQ 1值的倒排索引中添加B的条目，然后将当前节点移动到B。
3. 重复上面的过程，直到我们完成添加seq 1的最后一个元素为止。最后，我们将使用key=“seq 1”和value=node(C)将seq 1的最后一个节点C添加到查找表中。

第二步：插入A,B

第三步：插入A,B,D,C

第四步：插入B,C

一直这样做下去，直到穷尽训练数据集中的每一行(记住，一行表示单个序列)。现在，我们已经准备好了所有必需的数据结构，可以开始对测试数据集进行预测。现在让我们来看看预测阶段。

CPT 的预测

预测阶段包括以迭代的方式对测试集中的每个数据序列进行预测。对于单个行，我们使用倒排索引(II)找到与该行相似的序列。然后，找出类似序列的结果，并将其添加到可计数字典中的数据项中，并给出它们的分值。最后，使用“计数”返回得分最高的项作为最终预测。我们将详细地看到这些步骤中的每一步，以获得深入的理解。

目标序列：A,B

第一步：查找与目标序列相似的序列

利用倒排索引找到与目标序列相似的序列。通过以下来识别：

• 找到目标序列中唯一的数据项，
• 查找存在特定唯一数据项的序列ID集，
• 然后，取所有唯一数据项集合的交集。

第二步：查找与目标序列相似的后续序列

对于每个相似的序列，后续序列定义为在类似序列中目标序列最后一项发生后，减去目标序列中存在的项之后的最长子序列。注意，这与开发人员在他们的研究论文中提到的不尽相同，但我的这种实现方式似乎比他们的实现方式更适合。

通过下面的例子来理解这一点：

Target Sequence = [‘A’,’B’,’C’] 
Similar Sequence = [‘X’,’A’,’Y’,’B’,’C’,’E’,’A’,’F’]
Last item in Target Sequence = ‘C’
Longest Sub-Sequence after last occurrence of ‘C’ in Similar Sub-Sequence = [‘E’,’A’,’F’]
Consequent = [‘E’,’F’]

第三步：将相应的元素添加到“计数词典”中，同时添加它们的分值

将每个相似序列的后继元素与分数一起添加到字典中。例如，继续上面的示例。随后的[‘E’，‘F’]项的得分计算如下：

current state of counttable = {}, an empty dictionary

如果字典中没有该项，那么，

score = 1 + (1/number of similar sequences) +(1/number of items currently in the countable dictionary+1)*0.001

否则,

score = (1 + (1/number of similar sequences) +(1/number of items currently in the countable dictionary+1)*0.001) * oldscore

因此，对于元素E，即后续的第一项，得分将是

score[E] = 1 + (1/1) + 1/(0+1)*0.001 = 2.001
score[F] 1 + (1/1) + 1/(1+1)*0.001 = 2.0005

经过上面的计算，counttable为，

counttable = {'E' : 2.001, 'F': 2.0005}

第四步：利用Counttable的值进行预测

最后，返回作为预测值的Counttable数值最大的关键字。在上述示例中，E作为预测返回。

总结

在本文中，我们介绍了一种高效、准确的序列预测算法--紧致预测树。我鼓励你在序列预测哈克马拉松数据集（Hackathon dataset）上尝试一下，祝你在私人排行榜榜单上爬得更高！

如果您想要为CPT库贡献，可以自由地提出问题。如果您知道执行序列预测的任何其他方法，请在下面的注释部分中写入它们。别忘了给CPT库标注星号。