专栏首页数据派THU手把手教你深度学习强大算法进行序列学习(附Python代码)

手把手教你深度学习强大算法进行序列学习(附Python代码)

作者:NSS

翻译:陈之炎

校对:丁楠雅

本文共3200字,建议阅读10分钟。 本文将教你使用做紧致预测树的算法来进行序列学习。

概述

序列学习是近年来深度学习的热点之一。从推荐系统到语音识别再到自然语言处理,它的潜力似乎无穷无尽,推动着业界不断创新,涌现出前所未有的解决方案。

序列学习的实现形式多种多样,如机器学习域的马尔可夫模型、有向图等,深度学习域的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库标注星号。

作者 NSS

我是一个终身热衷于探索数据分析和科学领域的快手,对于我们所处的时代以及生成数据并将其转化为资产的速度深感兴奋。我对一些数据处理工具非常熟悉,也正处于学习其他数据处理工具和知识的过程中。

原文链接:https://www.analyticsvidhya.com/blog/2018/04/guide-sequence-prediction-using-compact-prediction-tree-python/

译者简介

陈之炎,北京交通大学通信与控制工程专业毕业,获得工学硕士学位,历任长城计算机软件与系统公司工程师,大唐微电子公司工程师,现任北京吾译超群科技有限公司技术支持。目前从事智能化翻译教学系统的运营和维护,在人工智能深度学习和自然语言处理(NLP)方面积累有一定的经验。业余时间喜爱翻译创作,翻译作品主要有:IEC-ISO 7816、伊拉克石油工程项目、新财税主义宣言等等,其中中译英作品“新财税主义宣言”在GLOBAL TIMES正式发表。能够利用业余时间加入到THU 数据派平台的翻译志愿者小组,希望能和大家一起交流分享,共同进步

本文分享自微信公众号 - 数据派THU(DatapiTHU),作者:NSS

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2018-05-11

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 吴恩达deeplearning.ai五项课程完整笔记了解一下?

    来源:机器之心 通过本文为大家解读如何构建自然语言、音频和其他序列数据的模型。 自吴恩达发布 deeplearning.ai 课程以来,很多学习者陆续完成了所...

    数据派THU
  • 手把手教你用Python处理非平稳时间序列(附代码)

    预测一个家庭未来三个月的用电量,估计特定时期道路上的交通流量,预测一只股票在纽约证券交易所交易的价格……这些问题都有什么共同点?

    数据派THU
  • 数据变金矿:一文读懂序列模型(附用例)

    众所周知,人工神经网络(ANN)的设计思路是模仿人脑结构。但是直到10年前,ANN和人类大脑之间唯一的共同点是对实体的命名方式(例如神经元)。由于预测能力较弱并...

    数据派THU
  • 生物信息学初识篇——第二章:序列比对(4)

    多序列比对的定义很简单,两条以上的生物序列进行的全局比对就是多序列比对。为了看清楚每一列的保守情况和理化性质,通常会给多序列比对根据不同的原则赋予丰富的色彩。目...

    DoubleHelix
  • 生物信息学初识篇——第二章:序列比对(5)

    在 EMBL Clustal Omega 比对结果的 Result Summary 标签下有Jalview按钮。这个按钮可以快速启动 Jalview,但这里启动...

    DoubleHelix
  • BBQ(生信基础问题13):序列比对专题

    测序的数据下机之后,我们一般是需要进行回贴到参考基因组上进行后续分析的(序列比对这一步一般都比较耗时间。很多开发软件的生信程序员都想办法在各种优化mapping...

    liu_ll
  • 2️⃣ 双序列比对(1):算法及数据库

    注意:动态规划和BLAST适用于不同比对情况。前者适合较少量序列间比对,BLAST适合从一组大量序列中搜索与查询相似的序列

    Y大宽
  • 如何把时间序列问题转化为监督学习问题?通俗易懂的 Python 教程

    AI 研习社按:本文作者 Jason Brownlee 为澳大利亚知名机器学习专家,对时间序列预测尤有心得。原文发布于其博客。AI 研习社编译。 ? Jaso...

    AI研习社
  • 开发 | 如何把时间序列问题转化为监督学习问题?通俗易懂的 Python 教程

    AI科技评论按:本文作者 Jason Brownlee 为澳大利亚知名机器学习专家,对时间序列预测尤有心得。原文发布于其博客。 Jason Brownlee ...

    AI科技评论
  • 序列预测问题的简单介绍

    序列预测与其他类型的监督学习问题不同。这个序列在观察结果上被强加了一个命令:当训练模型和做预测时序列必须保存。通常,包含序列数据的预测问题被称为序列预测问题,尽...

    AiTechYun

扫码关注云+社区

领取腾讯云代金券