序列学习是近年来深度学习的热点之一. 从推荐系统到语音识别再到自然语言处理, 它的潜力似乎无穷无尽, 推动着业界不断创新, 涌现出前所未有的解决方案.
序列学习的实现形式多种多样, 如机器学习域的马尔可夫模型, 有向图等, 深度学习域的 RNNs/LSTMs 等等.
在本文中, 我们将使用一种尚不太为人所知的叫做紧致预测树 (CompactPredictionTree,CPT) 的算法来进行序列学习. 这种方法简单得让人吃惊, 并且比一些著名算法如马尔可夫, 有向图等更为强大.
在深入阅读本文之前, 我推荐你先读一读 "你必读的序列模型(附用例)" 一文, 作者 Tavish 在这篇文章中介绍了序列模型及其典型用例和应用场景.
本文目录:
序列学习入门
紧致预测树算法(CPT)
理解 CPT 中的数据结构
用 CPT 进行训练和预测
训练阶段
预测阶段
建模与预测
序列学习入门
当我们需要预测一个事件之后可能会发生的某个特定事件时, 就需要进行序列学习. 序列学习广泛应用于各个行业, 例如:
网页预取: 给定用户访问的网页序列, 浏览器预测用户接下来最有可能访问的页面并预加载它, 以节省时间和改善用户体验.
产品推荐: 根据用户将商品添加到购物车中的顺序来推荐用户可能感兴趣的商品.
临床事件预测: 根据患者病史对疾病进行鉴别诊断(译者注: 鉴别诊断指根据患者主诉, 与其他疾病鉴别, 并排除其他疾病可能性的诊断方法).
天气预报: 根据过去的天气情况预测下一时段的天气.
序列学习还可能应用到许多其他的领域.
解决方案现状
为了在这一领域发掘更多解决方案, 我们推出了 "序列学习黑客马拉松". 参与者各有路数, 其中最受欢迎的是 LSTMs/RNNs, 使用率在私人排行榜前 10 名.
LSTMs/RNNs 已经成为序列建模的热门选择, 无论是文本, 音频等. 然而它们有两个基本问题:
训练时间太长, 通常需要几十个小时.
当序列中包含在以前的训练迭代中没有出现过的项时, 就需要重新训练. 这个过程代价特别高, 在经常遇到新项的情况下是不可行的.
初探 CPT(紧致预测树)
紧致预测树 (CPT) 是一种比传统的机器学习模型 (如马尔可夫模型) 和深度学习模型 (如自动编码器) 更精准的算法.
CPT 算法的独特之处是其快速的训练和预测时间. 我能够在 4 分钟内对上面黑客马拉松的序列数据集完成训练并进行预测.
不幸的是, 这个算法目前只能用 Java 实现, 因此它还没在数据科学家之间流行起来(尤其是那些使用 Python 的数据科学家).
为此, 我根据算法初创者的文档, 创建了一个 Python 版本的库. Java 代码当然有助于理解本文的某些部分.
这个公开的 Python 库可以在这里 (https://github.com/analyticsvidhya/CPT) 获得, 欢迎您对它作出贡献. 从某种意义上说, 这个库仍然是不完整的, 它还没有得到算法初创者的推荐, 但它已经足够好, 在黑客马拉松排行榜上获得了 0.185 分, 并且一切都在几分钟内完成. 我相信这个库完整之后, 性能应该能够和 RNNs/LSTMs 相匹敌.
在下一节中, 我们将介绍 CPT 算法的内部工作原理, 以及它如何比马尔可夫链, DG 等传统机器学习模型的性能更优.
理解 CPT 中的数据结构
作为先决条件, 首先需要理解 PythonCPT 接受的数据格式. CPT 接受两个. csv 文件 -- 训练和测试. 训练文件里是训练序列, 而测试文件包含每个序列需要预测的接下来的 3 项. 为了清晰起见, 训练和测试文件中的序列定义如下:
- 1,2,3,4,5,6,7
- 5,6,3,6,3,4,5
- .
- .
请注意, 序列的长度可以不相同. 此外, 热编码序列也不适用.
CPT 算法使用了三种基本的数据结构, 我们将在下面做简要介绍.
1. 预测树
预测树带有多个节点, 每个节点有三个元素:
数据项 - 存储在节点中的实际数据项.
子节点 - 该节点的所有子节点的列表.
父节点 - 指向此节点的父节点的链接或引用.
预测树基本上是一种 TRIE 数据结构, 它将整个训练数据压缩成一棵树的形式. 如果您不知道 TRIE 结构是如何工作的, 下面两个序列的 TRIE 结构图将说明问题.
Sequence 1:A, B, C
Sequence 2:A, B, D
TRIE 数据结构从序列 A,B,C 的第一个元素 A 开始, 并将其添加到根节点. 然后 B 被添加到 A 后, C 被添加到 B 后. 对于每个新的序列, TRIE 会再次从根节点开始, 如果一个元素已经被添加到结构中则跳过.
产生的结构如上所示. 这就是预测树如何有效地对训练数据进行压缩.
2. 倒排索引(II)
倒排索引是一种字典, 其中的键是训练集中的数据项, 值是该项出现的序列的集合. 例如:
- 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'}
- }
3. 查找表(LT)
查找表是一个字典, 带有序列 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 是训练集中的数据项.
1. 训练阶段
训练阶段会同时建立预测树, 倒排指数 (II) 和查找表(LT). 整个训练过程如下.
第一步: 插入 A,B,C
查找表
先得到一个根节点和一个初始设置为根节点的当前节点.
我们从 A 开始, 检查作为根节点的子节点 A 是否存在. 如果没有, 我们将 A 添加到根节点的子列表中, 在带有值为 seq 1 的倒排索引中添加一个 A 的条目, 然后将当前节点移到 A.
查看下一项, 即 B, 看看 B 是否作为当前节点 A 的子节点存在. 如果不存在, 我们将 B 添加到 A 的子列表中, 在带有 seq1 值的倒排索引中添加 B 的条目, 然后将当前节点移动到 B.
重复上面的过程, 直到我们完成添加 seq 1 的最后一个元素为止. 最后, 我们将使用 key="seq 1" 和 value=node(C)将 seq 1 的最后一个节点 C 添加到查找表中.
第二步: 插入 A,B
第三步: 插入 A,B,D,C
第四步: 插入 B,C
重复这个过程, 直到穷尽训练数据集中的每一行(记住, 一行表示单个序列). 现在, 我们已经准备好了所有必需的数据结构, 可以开始对测试数据集进行预测了.
2. 预测阶段
预测阶段以迭代的方式对测试集中的每个数据序列进行预测. 对于单个行, 我们使用倒排索引 (II) 找到与该行相似的序列. 然后, 找出相似序列的结果, 将其添加到计数字典的数据项中, 并给出它们的分值. 最后, 使用 "计数" 返回得分最高的项作为最终预测. 下面详细阐述每一步的做法.
目标序列: A,B
第一步: 查找与目标序列相似的序列.
利用倒排索引找出与目标序列相似的序列. 通过以下几步来查找:
找到目标序列中唯一的数据项,
查找存在特定唯一数据项的序列 ID 集,
然后, 取所有唯一数据项集合的交集.
比如:
存在 A 项的序列集 = {'Seq1','Seq2','Seq3'}
存在 B 项的序列集 = {'Seq1','Seq2','Seq3','Seq4'}
与目标序列相似的序列 = 二者之交集 = {'Seq1','Seq2','Seq3'}
第二步: 查找与目标序列相似的后续序列
对于每个相似序列, 后续序列定义为在相似序列中目标序列最后一项发生后, 减去目标序列中存在的项之后的最长子序列.
注意: 这与开发人员在他们论文中的做法有所不同, 但我的这种实现方式似乎比他们的更适合.
通过下面的例子来理解这一点:
目标序列 = ['A','B','C'] 相似序列 = ['X','A','Y','B','C','E','A','F']
目标序列的最后一项 = 'C'
相似序列中'C'发生后的最长子序列 = ['E','A','F']
后续序列 = ['E','F']
第三步: 将相应的项添加到 "计数字典" 中, 同时添加它们的分值.
将每个相似序列的后续项与得分一起添加到字典中. 例如, 继续上面的示例, 随后的 ['E','F'] 项的得分计算如下:
计数字典的初始状态 = {}, 是一个空字典.
如果字典中没有该项, 那么:
得分 = 1 + (1 / 相似序列的数量) +(1 / 当前计数字典中项的数量 + 1)*0.001, 否则, 得分 = (1 + (1 / 相似序列的数量) +(1/n 当前计数字典中项的数量 + 1)*0.001) * 旧分值
因此, 对于元素 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
经过上面的计算, 计数字典为,
计数字典 = {'E' : 2.001, 'F': 2.0005}
第四步: 利用计数字典的值进行预测
最后, 将计数字典中值最大的键作为预测值返回. 在上述示例中, E 作为预测值返回.
建模与预测
步骤 1: 复制 GitHub 存储库.
git clone https://github.com/NeerajSarwan/CPT.git
步骤 2: 使用下面的代码读取. csv 文件, 训练模型并做出预测.
- #Importing everything from the CPT file
- from CPT import *
- #Importing everything from the CPT file
- from CPT import *
- #Creating an object of the CPT Class
- model = CPT()
- #Reading train and test file and converting them to data and target.
- data, target = model.load_files("./data/train.csv","./data/test.csv")
- #Training the model
- model.train(data)
- #Making predictions on the test dataset
- predictions = model.predict(data,target,5,1)
尾注
在本文中, 我们介绍了一种高效, 准确的序列学习算法 -- 紧致预测树. 我鼓励你用序列学习黑客马拉松数据集 (Hackathon dataset) 尝试一下, 祝你在私人排行榜上爬得更高!
如果您想要为 CPT 库贡献, 可以自由地提出问题. 如果您知道执行序列学习的任何其他方法, 请在下面的注释部分中写入它们. 别忘了给 CPT 库标注星号.
来源: https://yq.aliyun.com/articles/592093