精华内容
下载资源
问答
  • 时序图语言
    万次阅读
    2017-10-30 22:17:06
    • Prophet是比较简单易用的,对于非时序预测和机器学习领域专家的是非常容易上手的。其参数大多数都是非常直观的参数。(Prophet的python包大量使用了pandas库,所以使用python做开发的需要首先了解pandas的使用。)

    • Prophet也是一种约定优于配置的思想,写代码只需要按照约定的套路定义好pandas中的dataframe就可以轻松进行预测。

    • 下面我们来进行一个官方网站提供的Quick Start来进行学习了解。

    import pandas as pd
    import numpy as np
    from fbprophet import Prophet
    import matplotlib.pyplot as plt
    
    # 数据文件请从github上的Prophet项目下载,并放在代码的对应目录
    df = pd.read_csv('examples/example_wp_peyton_manning.csv')
    df['y'] = np.log(df['y'])
    print df.tail()
    
    # 定义模型
    m = Prophet()
    
    # 训练模型
    m.fit(df)
    
    # 构建预测集
    future = m.make_future_dataframe(periods=365)
    print future.tail()
    
    # 进行预测
    forecast = m.predict(future)
    
    print forecast.tail(10)
    forecast[['ds', 'yhat', 'yhat_lower', 'yhat_upper']].tail(10)
    m.plot(forecast)
    plt.show()

    结果
    上图为最终的作图结果,其中蓝色线为预测结果,黑色点为原数据点。除此之外,由于Prophet使用的是加性模型,也就是把模型分为趋势模型、周期模型、节假日以及随机噪声的叠加。因为我们可以方便对各个成分进行作图观察。我们可以利用m.plot_components(forecast),对各个成分进行作图观察,如下:这里写图片描述
    默认会画出趋势、年周期、星期周期成分(如果在定义模型时给出了holiday参数,还会做出holiday的成分图)

    • 下面干货,从我的学到的经验中设计如何利用Prophet构建有效的预测模型。
      1. 首先我们去除数据中的异常点(outlier),直接赋值为none就可以,因为Prophet的设计中可以通过插值处理缺失值,但是对异常值比较敏感。
      2. 选择趋势模型,默认使用分段线性的趋势,但是如果认为模型的趋势是按照log函数方式增长的,可设置growth='logistic'从而使用分段log的增长方式
      3. 设置趋势转折点(changepoint),如果我们知道时间序列的趋势会在某些位置发现转变,可以进行人工设置,比如某一天有新产品上线会影响我们的走势,我们可以将这个时刻设置为转折点。
      4. 设置周期性,模型默认是带有年和星期以及天的周期性,其他月、小时的周期性需要自己根据数据的特征进行设置,或者设置将年和星期等周期关闭。
      5. 设置节假日特征,如果我们的数据存在节假日的突增或者突降,我们可以设置holiday参数来进行调节,可以设置不同的holiday,例如五一一种,国庆一种,影响大小不一样,时间段也不一样。
      6. 此时可以简单的进行作图观察,然后可以根据经验继续调节上述模型参数,同时根据模型是否过拟合以及对什么成分过拟合,我们可以对应调节seasonality_prior_scale、holidays_prior_scale、changepoint_prior_scale参数。

    相关网站:

    更多相关内容
  • 分析方法的选择 在分析预测中主要提供了几种时间序列的分析方法包括指数平滑法ARIMA模型和季节调整方法 在分析预测中提供了时间序列分析的图形工具包括序列(Sequence)自相关函数和偏自相关函数等 另外也可利用...
  • Python中的时序分析工具包推荐(2)

    千次阅读 2022-01-04 01:23:36
    导读在前期推文Python中的时序分析工具包推荐(1)中介绍了时序分析的三个工具包,分别侧重于时序特征工程、基于sklearn的时序建模和更为高级的时序建模工具。今天,本篇再来介绍4个时序...

    导读

    在前期推文Python中的时序分析工具包推荐(1)中介绍了时序分析的三个工具包,分别侧重于时序特征工程、基于sklearn的时序建模和更为高级的时序建模工具。今天,本篇再来介绍4个时序分析好用的工具包:Prophet、Merlion、Darts和GluonTS。

    延续前篇推文的风格,本文主要对四个时序工具包进行简要介绍,包括工具包的功能定位、主要特色及优劣势等,并列出了相关的论文、文档和github地址可供详细查阅。

    01 Prophet

    dbd530115da0216d182ba10a848cdd02.png

    Prophet,英文原义有“预言家”或者“先知者”的含义,放在时间序列里,那么自然就是用于时序预测。这是一个由Facebook在2017年研究设计的时序分析工具,主要定位就是用于时序预测,如果按照时序预测的几种主流建模方式来加以区分的话,那么Prophet应当属于统计学模型流派。Prophet目前最新版本是1.0版本,其上一个版本是0.7,同时也刚好从1.0开始,该工具包更名为prophet,而之前的工具包则叫作为fbprophet,但主用的时序预测模型则都叫做Prophet。prophet工具包性能还是很强大的,最主要的是其自动化程度相当高,即使是全默认参数也能取得不错的效果,所以很多其他时序工具包都将其集成在内。

    6511784cef806baaf18151a8e0b9bb5d.png

    不过,prophet工具包的安装有些麻烦,主要是pystan依赖安装的问题。经过实践,利用conda源直接conda install prophet,可以顺利完成安装,体验较好。

    Prophet实现时序预测的基本思想是将时间序列按成分分解为趋势性(Trend)、季节性(Seasonality,这里的季节性既包括年、月、周等日期属性上的季节性,也包括更为一般的周期性)、误差项(Error),以及考虑节假日等特殊日期的影响(Holiday)。相较于其他经典的统计学时序预测模型,Prophet除了成分分解更为细化之外,还考虑趋势性的拐点因素(Trend Changepoints),同时对节假日的处理也支持双重假日的影响(例如中国的节日中,国庆和中秋重叠的情况),以期来进一步考虑节假日对时序带来的冲击。

    Prophet进行时序预测时,以dataframe作为输入数据类型,且该dataframe中要求含有ds和y两个字段,其中ds表示时间列,y表示时序变量,而后直接调用fit和predict接口就可以愉快的玩耍了。同时,Prophet还可以对预测结果进行快速可视化对比,下图中黑色散点为真实值,而蓝色区域则为预测的置信度范围。

    51760e480ae6a27ed4ba740fa918e87c.png

    关于Prophet的相关参考信息如下:

    论文:https://peerj.com/preprints/3190.pdf
    文档:https://facebook.github.io/prophet/docs
    GitHub:https://github.com/facebook/prophet (13.9K star)

    02 Merlion

    b7c007ca419a18f316c41da5686c4181.png

    Merlion是由美国salesforce公司新推出的一个时序分析工具,主要定位是时序预测(Forecasting)和异常检测(Anomaly Detection)。

    于我个人而言,对salesforce的了解源于在使用AutoML工具transmogify,这也是由salesforce推出的一款基于Spark.ml的自动化机器学习框架。

    Merlion因为在本次对比的几个时序分析工具中推出时间相对较晚,所以一定程度上占有后发优势。就时序预测和异常检测两类时序分析任务而言,Merlion既支持单变量也支持多变量的时序分析,而且还支持了模型融合(Ensemble)以及AutoML能力(可以理解为带有模型选择和自动调参功能的时序建模)。下图是Merlion的github中给出的和其他几个时序分析工具的功能覆盖对比图:

    91958d8457b35a33c5592f556b720f33.png

    具体到时序预测任务,Merlion大体上支持统计学模型和机器学习模型,其中统计学模型包括ARIMA、ETS等常用模型外,也将Prophet集成进来;而机器学习模型则主要是基于决策树的集成模型,例如RF和GB等。同时,如前文所述,Merlion内置了AutoML能力,可以实现模型的选择和调参,同时也可方便的对多个模型的预测结果进行融合,毕竟在时序预测中不存在单一模型通吃所有数据集的情况。与Prophet类似,Merlion也支持自动绘制真实值和预测结果及置信区间的对比曲线,某种程度上比Prophet更加直观,如下图所示。

    b23305fcb704ecc793e43052496fa2f3.png

    Merlion是我个人前期使用较多的一个工具,安装的话推荐使用离线安装(首先从github下载源码,然后pip install 文件夹)。与Prophet不同,由于Merlion既支持单变量也支持多变量,所以其内置了定制的输入数据格式TimeSeries类型,但也可以非常方便的从dataframe加载转换。

    关于Merlion的相关参考信息如下:

    论文:https://arxiv.org/abs/2109.09265
    文档:https://opensource.salesforce.com/Merlion/v1.1.0/index.html
    GitHub:https://github.com/salesforce/Merlion (2.3k star)

    03 Darts

    aa7c424105b6bc518f2a3adac44922e2.png

    Darts工具包也是一个强大的时序分析工具,也支持了众多模型和任务场景,并提供了高度集成化的调用方式,包括Prophet也是其内置集成的模型之一。下图是Darts的Github中给出的模块功能阵列,从中可以看出支持的模型及所使用时序预测场景:

    6729cf23e1c365829d78d9af552864e1.png

    Darts给我的第一印象是其与Merlion十分接近,包括二者都是定制了一个TimeSeries数据类型作为模型的标准输入。但二者的主要区别也很明显,主要可概括如下:

    • Merlion支持的时序分析任务包括时序预测和异常检测;而Darts仅聚焦于时序预测问题;

    • Merlion支持的模型主要是统计学模型和传统机器学习模型,而Darts支持的模型更为丰富,最大的特色是深度学习模型,其中不乏Transformer、TCN等这些新的时序建模方法。

    此外,Darts工具包也支持了包括Pipeline、自动调参等特性,也算是工程化支持较为完备的工具包。不过,个人在尝试使用时体验并不是很优秀7271a33e811cf912d4b1118324f64e15.png

    关于Darts的相关参考信息如下:

    论文:https://arxiv.org/abs/2110.03224
    文档:https://unit8co.github.io/darts
    GitHub:https://github.com/unit8co/darts (3.3k star)

    04 GluonTS

    18897495ec011b649143dbc7e3490d2b.png

    如果了解AutoML技术的读者肯定知道亚马逊出过一个AutoML框架,叫做AutoGluon,也正是从那时起我对gluon才有所了解,知晓这是亚马逊推出的一个深度学习框架(不过,至今也未曾深入调研和探索使用过。。),而GluonTS则是Gluon生态中用于实现时序建模的一个工具包,更确切的说是一个基于深度学习的概率时序模型工具,至于时序分析任务也是都支持时序预测和异常检测任务。

    坦白地讲,GluonTS于我个人而言仅停留于阅读其官方Paper的层面,实际的工具尚未探索使用,所以对于其性能的描述也仅停留于眼见耳听,而缺乏动手实践,所以这里不做更多介绍。

    关于GluonTS的相关参考信息如下:

    论文:https://arxiv.org/abs/1906.05264v1
    文档:https://ts.gluon.ai/
    GitHub:https://github.com/awslabs/gluon-ts/(2.4k star)

    05 小结

    总体而言,四个时序工具包各有特色,功能覆盖各有千秋:

    • Prophet功能相对单一,仅适用于单变量的时序预测模型,而且也仅支持这一个模型。但与此同时,该模型也做到了高度专业和成熟,GitHub上的star数量高达13k之多,更是成了很多其他时序分析工具包的必备集成模型之一

    • Merlion定位于时序预测和异常检测场景,既支持单变量也支持多变量时序,模型以统计学模型和机器学习模型为主,一大亮点是支持时序建模的Auto能力和多模型的Ensemble能力

    • Darts也是时序分析工具的一个集大成者,主要面向的场景是时序预测任务,但在模型的丰富程度上更为出色,亮点是支持很多深度学习模型,包括Transformer、TCN等序列模型新星

    • GluonTS作为亚马逊Gluon生态中的时序建模工具,是一款主打深度学习模型的时序分析工具,适用任务包括时序预测和异常检测,但在模型使用灵活度方面个人感觉则要略逊于Merlion和Darts

    考虑前期推文中介绍的tsfresh、tslearn、sktime三个工具,加之本文介绍的Prophet、Merlion、Darts和GluonTS四个工具,其实在应对主流的时序数据分析任务时基本是足够的。同时,以此为基础,更重要的是提升相关的理论基础,方能更好的使用和驾驭这些工具,也才不枉成为一名真正的算法工程师调包侠。

    947de0029f8996a7dbedd0254ce82b6f.png

    相关阅读:

    展开全文
  • 转载自:http://blog.csdn.net/kanghua/article/details/44650831Hummer TimeSeries DB (蜂鸟时序数据库)技术...这些时序数据不但数量越积越多、而且频率也越来越快,但传统数据库对于这种数目庞大、更新频繁的时序

    转载自:http://blog.csdn.net/kanghua/article/details/44650831


    Hummer TimeSeries DB (蜂鸟时序数据库)技术介绍

    1. 背景介绍

        不知不觉中我们已经跨入“大数据”时代,而大数据的主要来源是来自于各种“传感器”所产生的时序数据记录。这些时序数据不但数量越积越多、而且频率也越来越快,但传统数据库对于这种数目庞大、更新频繁的时序数据,无论存储或检索都难以应对(“存不下”、“查不出”)。因此工业界当前迫切需要一种面向时序数据特征而专门设计的新型时序数据库 —— 蜂鸟时序数据库正是在此背景下,为存储和检索时序数据而研发的分布式数据库。

    注 : 取名蜂鸟源自于蜂鸟令人惊叹的挥翅速度。蜂鸟每秒翅膀能挥动15-80次不等。想象一下,蜂鸟本身就犹如一个“传感器”,而翅膀挥动就好比不断产生时序数据。

    2. 时序数据带来的新挑战

    2.1. 数据量急剧膨胀

        机器(传感器)产生的时序数据量与人手工录入的传统档案类数据量相比,完全不是一个数量级—— 前者百万、千万记录量已触顶,而后者动暨数十亿、数百亿的记录规模。面对如此大量的时序数据,传统数据库既“存不下”,也“查不出”(原因见 2.2/2.3/2.4)。因此当前业界普遍采用的妥协方案是:或者只存近期数据(无奈的丢弃老数据),或者只存储一些抽样记录(如: 降频down-sampling到只记录整点数据)。显然这些方案都无法避免丢弃宝贵数据。在数据为王的时代,谁拥有的数据更多,谁就拥有更强的竞争力,被迫放弃数据实为可惜!

    2.2. 数据需高速实时导入,且可实时数据获取(ingestin real time)

        大量的传感器数据从四面八方、实时涌来(每分钟成千上万,甚至每秒钟成千上万条记录),若想从中找到瞬息万变的“机会”,就需要数据能高速入库,同时还能允许及时查询刚入库的新鲜数据。但传统数据库在大量随机数据实时写入时,性能欠佳 (入库速度明显不够),更糟的是在入库同时当有并发读操作时,读写性能都将变的更差。因此当前业界普遍采用的妥协办法是: 延迟入库(如,到晚上无查询业务时再入库新数据),或批量入库(如,每天积攒一批数据再批量入库) —— 这些方法实际上都是为了避免或减少读写混合发生。显然上述方案肯定会牺牲数据处理的实时性,因此也必然降低了数据的内在“价值”。

     

    2.3. 按时间断面(区间)高速检索数据

       时序数据最普遍的查询需求是:“在时间断面上,(精确、条件、模糊)检索数据”。其检索特征更偏向于数据扫描(Scan) —— 而不是传统数据库最擅长的数据定位(seek)。对于数据量有限的档案数据,传统数据库只需在时间列上和键(key)上建立索引,就得能应这类检索。但不幸的是当时序数据上量后,索引无法继续驻留在内存;更糟的是不断的更新操作(如无序插入)又带来了索引分片(indexfragment)的麻烦。这两点都使得传统数据库在按时段查询时无法顺序扫描目标数据区(磁头需要跳跃寻址),因此传统数据库的查询性能会随时序数据增加和持续更新变的越来越差,而且是指数性下降。

       除了时序数规模增长和持续更新对传统数据库索引机制造成冲击外,数据乱序入库对传统索引机制更是灾难 —— 乱序入库是指 : 记录入库顺序并非严格按时间有序(试想多地传感器数据从远程输送来,然后再集中入库。经这个“漫长”过程后,几乎可以肯定数据入库顺序已然不等于数据的发生时间顺序了)。传统数据库在时序数据无序写入的情形下,会造成数据在物理存储上也无序分布。所以即便在时间列上建有索引,按时间断面查询还是无法顺序扫描磁盘,而需要不断seek才能定位数据 —— 我们知道在磁盘上只有顺序读写性能才是最佳,随机读写性能要相差百倍以上。

    2.4. 数据分析重要性越发突出

      时序数据存储的目的有两类:第一是“事故反演、场景回放”;第二是“分析统计和预测”。而分析类需求从简单到复杂可再分为三小类:

    n   朴素的统计分析(如多维分析等)


    n   基于移动平均值或者差值的预测分析

    n   基于机器学习等的预测和挖掘分析

        统计分析离不开SQL和各种聚合函数和窗口函数;而对于预测、挖掘则往往需要借助于Hadoop体系的M/R、BSP等计算框架。传统数据库对于统计需求,在数据量不大时还算比较擅长,但若要与Hadoop等NOSQL系统配合,则多有不便 —— 或者接口支持不好、或不能最大发挥硬件能力。

    2.5. 可控的实施成本

        时序数据相关业务才刚刚起步,而且多属于运营支撑性业务。相对于一线盈利业务而言其业务价值和技术本身都存在一定风险;另外业务的数据规模也不一定能一步到位,数据往往是由少到多逐步积累,一开始或相当时间内数据量都很有限。鉴于上述实时,我们建议在项目实施开始阶段应尽量控制成本,降低实施风险。

    成本控制从技术角度讲最好的选择是:

    ü 使用普通PC机器,也可用私有云提供的标准虚拟机。

    ü 先部署有限规模的机器集群(如先满足未来半年数据存储需求)。当业务价值得已证实、数据规模逐步上量后,再对集群进行扩容也不迟(避免初期实施就一步到位,而闲置大量资源)。

    上述需求换而言之就是要求:

    1.  系统在软件层面要做好、做足容错工作(因为普通pc机缺少小型机所具备的硬件容错设备)。传统数据库往往把容错都交给硬件做,不但成本高,而且实际上也不如软件层面更可靠和可控。

    2.  系统必须有良好的横向扩展能力,即补充同类机器机即可实现自动扩容。而传统数据库初期就要购置昂贵的小机,而且扩容时多是采用纵向扩展方式,即需要用户再购买更高配置的小机代替原先的小型机。

     

         综上所述(2.1-2.5),传统数据库由于设计初衷是应对“档案”数据,而非时序数据,所以面对当前大规模时序数据时,传统数据库就显得捉襟见肘,难以应对了。正是如此,原先并不被业界所重视的“时序数据库”得以快速走向前台,并日渐受到重视和推崇。

    3. 时序数据库适用场景

        毫无疑问,存储和检索时序数据肯定是时序数据库的最佳使用场景,但到底有那些场景会产生时序数据呢?我们身边是否有时序数据呢?

        我们首先要认识到最可能产生时序数据的不是人,而是机器,更确切的讲是“传感器”。不过这里所谓的“传感器”更具抽象意义 —— 凡是具备数据采集和上报功能的设备都属于“传感器”。比如刷卡POS机、ATM款机、交通摄像头、手机、PM2.5探头等等都属于传感器。可见我们身边充斥着各种“传感器”,生活中的万千变化都被“传感器”时刻记录着。我们不妨大胆预言——不久的将来,随着数据越来越丰富和准确,基于数据权威的社会发展模式必然会让社会变得更高效、更公平、更廉洁。

      我们不妨归纳一下依赖时序数据的典型行业和其用到的“传感器”数据:

    n  能源行业:智能电表用电量数据。

    n  通讯行业:短信、话单、邮件。

    n  交通行业:监控摄像头(卡口设备)过车记录;监控油轮航运轨迹、耗油等。

    n  金融行业:银行POS机刷卡数据、ATM机取款数据。

    n  环保行业:气象监控数据(温度、风速、降雨等)、环境监控数据(pm2.5等)。

    n  互联网行业:用户访问日志、广告点击日志。

    n  移动互联:近场通讯数据、App应用统计数据。

    n  广电行业:机顶盒操作数据。

    n  物流行业:配送记录数据。

    n  地理信息系统:GPS数据存储和分析。

    n  云计算:服务器性能计数数据。

    n  制造业:监控机器运行指标,优化制造流程。

    n  医疗行业:纪录和监控药品使用情况、纪录和监控病人病理指标。

        另外,公安刑侦、情报分析、物联网、智慧城市等也都是时序数据的消费行业。不夸张的讲:凡是具有公共服务特征的行业就离不开时序数据—— 或产生时序数据、或消费时序数据、或兼而有之(时序数据库的具体实践请见“最佳实践”一章)。

    4. 系统运行环境要求

        蜂鸟不需要高端存储设备和高性能小型机,而是使用配置SATA磁盘的普通PC服务器(组成计算存储一体化集群)。这种通用机型的配置要求其实正是大数据、云计算运行环境发展的主流趋势和必然结果。因为通用机型除了价格低廉和保护企业现有投资的原因外,更重要的原因是:可以使用私有云和公有云所提供的虚拟机部署系统。由此可见,蜂鸟系统可部署在提供虚拟机的“私有云”中,甚至还可被部署在EC2这种“公有云”上。

        当然对于预算宽裕,或想要求最佳性能表现的客户,完全可以给出较高的环境配置 —— 更高的配置必然能带来更高的性能。

        下面简要给出一个大众化的配置要求(可满足大多数要求),供大家参考:

    n  CPU — 4-12 core(主频>2G)  # 如果计算任务颇多,可尝试提升CPU主频档次, 另外核/core数最好比机器磁盘数多才好(如8盘,则12核最佳)

    n  内存 — 16G-512G # 32G属于标配,内存越大缓存越多,处理数据也自然更快,所以有实力的可将内存容量扩充到32G、64G、128G、256G、甚至更高。

    n  磁盘 — 2 - 12个STAT/SAS磁盘 # 一般大容量的SATA磁盘速度就足够了,但数量应尽可能多,因为越多的磁盘数量不仅仅是容量增加,更重要是写入和查询性能的提升(近线性提升),所以多盘是高性能性能的保证之一。

    n  网络 — 千兆网络环境 # 千兆网络已能应对大多数场景了,如在万兆网环境下,则写入和查询性能(尤其是大表Join操作)都将显著提升。

    n  OS — Centos6.5(64bit) # 我们推荐比较稳定的Centos系统,不过实际上Linux各种操作系统都予以支持

    如果要求更高的处理性能和存储能力,则简单补充机器即可达到目的(性能的具体计算公式见章节10.2)

    注:如果需要高可用性,则最少配置三台机器,以保证数据安全;

    5. 体系架构

       蜂鸟系统最重要的架构特点是分层结构 —— 每层各司其职,相互解耦,独立演化。最重要的两层分别是NOSQL数据层和SQL查询层。 而在NOSQL层于SQL层上分别选择了Shared Nothing和MPP两种分布式经典架构。

    层次说明(见图1):


    n  NOSQL数据层 : NOSQL层处于基础层,内部自下而上又分为 “数据存储层” 、“数据同步层”、 “对象检索层”。分别负责数据持久化、多副本数据传播、对象读写控制功能。该层采用NOSQL经典的Shared Nothing架构,具备高扩展性、高并发性、高可用性等优良特性。

    n  SQL查询层 : SQL层依赖于 NOSQL层,内部自下而上又分为“并行SQL执行层” 和“JDBC/ODBC接口层”。该层采用SQL查询领域最成功的MPP架构,具备大吞吐、高并发等优良特性。

    n  离线计算层 : 该层和SQL层一样都是依赖于NOSQL层,但同时也依赖于HADOOP 体系中得M/R组件。简单讲,离线计算原理是利用M/R框架就近(到数据所在机 执行计算任务)操作NOSQL数据层所管理的数据。 从编程接口一节可看到,蜂鸟支持M/R 程序,也支持PIG、Hive等工具,都些无不得益于离线计算层。显然该层继承了HADOOP离线计算框架具有的大吞吐、高容错等优良特性。

     

     图 1

    6. 时序数据存储格式

        近年来,经过在大数据项目中不断探索与实践,使得我们更“懂”时序数据。蜂鸟大胆抛弃了传统数据库的掣肘,针对时序数据设计了专有数据格式和执行计划,以求最佳性能。在展开时序数据存储格式前,重申时序数据处理的主要特征 : 时间断面(区间)上进行精确、模糊、条件检索 —— 例如 : 查找国庆期间查询给定嫌疑人通讯踪迹(精确查询) ; 查春节期间具有“陕A”车牌号字样的进京车辆/总数(模糊前缀查询) ; 查询大年初一北京望京地区用电量最高的电表(地域条件查询);除时间区间上基本检索外,很多场景更需要在时间段面(区间)上进行各种统计分析计算 —— 例如 : 如,总量统计、同比、环比计算等。

        我们针对上述时序数据处理的两大场景 : “区间内个体回放”和“区间内统计分析”(前者是在时间区间上进行给定key的检索;后者是在时间区间上进行分析计算),分别设计了KT和TK两种针对性存储格式。如果应用场景同时有统计分析和个体回放两类需求,则可使用蜂鸟专有的PKT格式兼顾这两类需求 —— PKT格式属于TK格式和KT格式之间的一种“折中”选择。若场景确定时,优先考虑使用KT或TK场格式 —— 比如,侦查员追查嫌疑车辆轨迹,或疑犯的通话记录等场景,属标准的个体回放需求,应优先考虑KT格式;路况车流等指标计算则属于区间内统计分析运算需求,应优先考虑TK格式;但当你既想查看给定车轨迹,又想统计路况信息时,则最好选择PKT格式了。

     

    我们以示例数据做样本,分别按照三种不同存储格式组织时序数据,通过对比展示几种格式之间的区别。

    示例数据:

    时间从2012-06-19 20:30:00到2012-06-21 02:30:00三个小时区间为例,共到来9个时序数据,内容分别如下:

    2012-06-19 20:30:00(1340109000000)  K1,V1(内部包含colume1,colume2,colume3,....)

    2012-06-19 20:40:00(1340109600000)  K3,V2

    2012-06-19 21:10:00(1340111400000)  K2,V3

    2012-06-19 21:35:00(1340112900000)  K1,V4

    2012-06-19 21:45:00(1340113500000)  K3,V5

    2012-06-19 22:15:00(1340115300000)  K1,V6

    2012-06-19 22:45:00(1340117100000)  K3,V7

    2012-06-19 22:55:00(1340117700000)  K2,V8

    2012-06-19 22:58:00(1340117880000)  K1,V9

     

    n   TK 格式(即 TIMESTAMP-KEY 格式) —— 该格式首先按照事件发生时间排序,当时间相同时,则再按照事件ID(key)排序。具体 Layout 见表 6.1:

    Timestamp

    Key

    Colume1

    Colume2

    Colume3

    ....

    1340109000000

    K1

     

     

     

     

    1340109600000

    K3

     

     

     

     

    1340111400000

    K2

     

     

     

     

    1340112900000

    k1

     

     

     

     

    1340113500000

    K3

     

     

     

     

    1340115300000

    K1

     

     

     

     

    1340117100000

    K3

     

     

     

     

    1340117700000

    K2

     

     

     

     

    1340117880000

    K1

     

     

     

     

    ...

    ...

     

     

     

     

     

     表6.1














    n  KT 格式(即 KEY-TIMESTAMP 格式) —— 该格式首先按照key排序。当在key相同时,则再按照事件发生时间再排序。具体 Layout 见表 6.2:

    Key

    Timestamp

    Colume1

    Colume2

    Colume3

    .....

    K1

    1340109000000

     

     

     

     

    K1

    1340112900000

     

     

     

     

    K1

    1340115300000

     

     

     

     

    K1

    1340117880000

     

     

     

     

    K2

    1340111400000

     

     

     

     

    K2

    1340117700000

     

     

     

     

    K3

    1340109600000

     

     

     

     

    K3

    1340113500000

     

     

     

     

    K3

    1340117100000

     

     

     

     

    ...

    ...

     

     

     

     

     表6.2

     














    n   PKT 格式(即 PARTITION-KEY-TIMESTAMP 格式) —— 该格式首先按照时间分区分组排序(其中partition可选择小时、天、月、年等时间单位,其类似传统数据库中的分区概念),在组内首先按照KEY排序,相同KEY再按照事件时间排序。具体 Layout 见表 6.3

    Parttion

    Key

    Timestamp

    Colume1

    Colume2

    Colume3

    Colume4

    13401072

    K1

    1340109000000

     

     

     

     

    13401072

    K3

    1340109600000

     

     

     

     

    13401108

    K1

    1340112900000

     

     

     

     

    13401108

    K2

    1340111400000

     

     

     

     

    13401108

    K3

    1340113500000

     

     

     

     

    13401144

    K1

    1340115300000

     

     

     

     

    13401144

    K1

    1340117880000

     

     

     

     

    13401144

    K2

    1340117700000

     

     

     

     

    13401144

    K3

    1340117100000

     

     

     

     

    ...

    ...

     

     

     

     

     

      分区单位-小时

      表6.3

     













       上述的数据存储格式核心目的都是为了让时序数据在磁盘上“有序存储”,从而按区间扫描时磁头可保证高速顺序移动,并且遍历的数据尽可能少。如果理解了这个准则,那么自然可知上述时序数据格式各自的优缺点了:

    n  TK格式对于区间内无key检索性能最优,而对于给定key查询则有所浪费 —— 因为TK

    格式中未按KEY聚集数据,所以检索给定KEY需要扫描给定时段内全部数据。

    n  KT格式对于给定key检索性能最优,如果区间内无key查询则是麻烦 —— 因为KT格式下要统计给定时段则必须扫描全部数据。

    n  PKT格式对于区间内无key查询效率比TK格式稍差 —— 因为需要扫描完时段所跨分区的全部数据;PKT格式对于给定key检索效率比KT稍差 —— 因为需要在时段所跨越的每个分区内,依次扫描该给定key的对应数据。但PKT格式能兼顾两类查询,且性能损失不大。

       为了能在多种场景下都能提供最佳处理性能,我们对同一数据的不同副本可选择不同数据格式存储,在查询时根据查询条件“智能”选择最佳数据格式所在的分片实施查询,从而确保蜂鸟在各时序场景下都能提供最佳性能(见图2)。


     图2

     

    7. 重要特性和优势

    蜂鸟系统的数据存储格式和体系架构决定了蜂鸟系统的最重要的几个特性:

    n   面向时序检索和分析优化 


    n   分布式存储和计算

    n   高可用性

    n   支持SQL,并扩充时序分析SQL

    上述特性将为用户处理大规模时序数据带来显著好处,具体如下。

    7.1. 读写性能突出

    n  数据导入速度高 :蜂鸟集群中单机单盘能提供40M/s的写入速度,因此不存在数据无法及时入库的烦恼。

    n  数据更新速度高 :蜂鸟实现了列(列族)存储结构,因此很合适需要大规模按列(列族)更新的场景。

    n  数据扫描速度高 :配备8SATA磁盘的PC服务器,能提供约2-4G/s的数据扫描速度,确保时间断面上统计(或者说上钻)性能。

    n  按列计算速度高 :蜂鸟具备列存结构,因此能保证快速在给定列上进行分析计算(无需读取全行)。

    n  时间排序查询速度高 :由于我们时序数据存储遵循时间排序(还有key排序),因此对于按时间排序的检索操作非常高效 —— 比如逆序/正序检索:如,order by timestamp desc/asc limit 100 ;或时间滑动窗口上的计算:如,计算股票MACD等指标。

    7.2. 恒时检索(Constant Query Time)

    恒时体现数据检索速度不随数据总量而变,只与“命中(touched data)”的数据量相关。具体表现在两个方面:

    ü 当给定key检索时,性能只和该key对应的数据多少相关,而与共有多少个key无关(比如,城市车里从100万辆涨到1000万辆后,检索给定车辆的速度不会改变)。

    ü 当无key检索时,性能只和时间段数据量相关,而与总数据量无关(比如,只积累一年数据和积累十年数据情况下,统计某个月数据则响应时间不变)

     

    7.3. 实时数据获取(ingest data in real time)

         蜂鸟支持数据实时流式灌入,无须等待,及刻便能被查询到。这种实时性是在线时序数据处理系统的关键需求。(而使用impala,shark等基于HDFS存储的系统都无法做到数据实时获取)。

    7.4. 支持面向时序的SQL查询

       蜂鸟针对时序数据在插值、时间聚合、Join、递增指标计算等方面对标准SQL进行了扩充,目的是使用户能更直观、方便的对时序数据进行分析处理。

     

    时序SQL扩充项

    语法

    作用

    举例

    时间聚合

    Group by time(number,‘s|m|h|d’

    按照给定时间进行rollup 聚合计算

    监控工厂设备运行状态,需要计算是每5分钟内的某项指标的偏差:

    select deviation(x) from table group by (5,‘m’);

    插值

    Nullpolcation()/prepolcation()

    对于空白时段按照空值或前值进行填充

    为了绘制每5分钟的时间内的数据偏离值,对于采集盲区,需给进行“前值”插值补充:

    select prepolcation(x) from table group by (5,‘m’);

    Join

    time join

    对于多个时序数据进行合并,用于产生新时序(用于分析因果,或计算等)

    观察用电量消耗时序表和天气温度变化时序表之间的因果关系:

    select * from energy time join temperature

     

     

     

    递增指标求增量变化

    Delta()

    对于递增计数指标

    计算用电量费用变化趋势—— 用电量属于单调递增指标。假设电量时序表为table1,电价时序表为table2,两个表的值都按时间变换。

    select table1.timestamp, delta(table1.mount)*table2.price group by table1 time join table2

     

         比如group by语义在蜂鸟中不仅仅作用于给定字段上,而且也可按照任意时间粒度进行聚合 —— select count(type) from events group by time(10m) —— 该功能特别适合于趋势统计(为了方便可视化,蜂鸟还支持对于未有结果的聚集区间进行差值(如填写0/前值等)。 另外蜂鸟也还支持group by count(100)等特有聚合语法。

     

    7.5. 节约空间

        蜂鸟系统存储时序数据相比传统数据库更节约空间。其主要原因如下:

    n  数据压缩存储 :蜂鸟支持面向行和列的压缩,数据压缩比可达到3 – 20 (具体压缩比和数据内容密切相关)

    n  无需额外索引 :蜂鸟避免了像传统数据库那样,在时间列和事件id上建立b树索引,而是将“时间”和“事件ID/Key”撮合为组合KEY,借助LSM树维护有序记录(见数据存储格式一章)。这种“前缀”索引结构以来不但便于时序处理,而且无需额外索引文件,节约了大量存储空间。

        相对于多数传统数据库,蜂鸟至少能节约3-4倍以上的存储空间。比如我们在基准测试一章中提到的120亿、大约600G的气象原始文本数据。如果在关系数据库(如MySQL)中存储,数据本身,再加上索引(需要在key、timestamp、key+timestamp上分别建立索引)大约需要近2*600 = 1.2T存储空间,而在蜂鸟系统中无须额外建索引,且有至少3-4倍的压缩比,所以实际存储空间只需要600/3 = 0.2 T存储空间。

    7.6. 在线离线处理一体化(混合负载支持)

        在传统的大数据处理流程中,在线系统(如OLTP、AD HOC)与离线系统(如报表、OLAP 、数据挖掘)往往被部署成相互独立的的两个集群 —— 在线集群负责数据检索,离线集群负责数据分析。之所以将数据划分到不同集群,是为了避免离线分析对在线数据查询带来负载干扰,妨碍在线系统使用。但如此划分,无疑需要额外的数据搬迁和数据抽取,即ETL过程 —— 数据需要“定期”从在线系统中导入到离线系统。 在工程中运维人员一般会在每天夜间进行ETL操作。但这种传统做法有几个弊端:

    1. 因为离线集群中的数据总要落后于在线集群,所以“新鲜”数据不能及时被分析,从而数据的时效性较差,分析价值也大打折扣。

    2. ETL操作和维护两个集群都需要额外的软件和操作人员,无形增加了软件和人员成本。

    那么理想情况应该将离线集群与在线集群合并,避免不必要的ETL工作,也无需再维护两个集群。为了达到”在线\离线一体化”目的着重需要解决的技术问题是如何避免在线任务和离线任务的负载隔离。具体技术是:

    ü   数据多副本异构同步存储 —— 同一份数据需要存储为多个不同副本,副本之间要求数据同步,副本各自可拥有自己的格式。不同副本将应对不同类型的任务,如列存格式的副本应对分析类任务,排序行存格式应对检索任务。

    ü   任务智能调度,根据任务的不同类型、和集群负载情况,动态选择合适的机器和数据副本执行任务。要求达到最大的资源利用率和性能。

     

       图3

    7.7. 灵活的数据一致性

    根据不同业务需求,用户可选择不同的数据一致性约束。蜂鸟支持如下一致性:

    n  数据“强一致性”:在线检索多使用强一致性

    n  数据“弱一致性”(最终一致性):离线分析时常使用最终一致性。

    n   Session一致性 :

    7.8. 高可用性和高数据安全性

       首先蜂鸟实现了磁盘粒度的故障处理,即当某个磁盘故障时,所在机器其余磁盘负责的数据服务不受影响;另外根据实践统计,存储型机器硬盘年故障率约为3%(网络故障率和机器其他硬件故障率相比磁盘故障要低1-2个数量级别,故下面计算可忽略不计),系统故障切换(Failover)的时间为20秒,系统恢复一块故障硬盘上所存数据最多需要1小时。根据上述条件,我们可计算出“系统可用性”和”数据安全性”这两个衡量系统健壮性的典型指标。

    n  可用性量化计算

        假设一个table只要有一个分片(fragment)不可用,则认为该table不可用。我们只考虑因disk故障(最主要因素)引起的不可用。按含有10台机器的典型集群计算,每台机器8块数据盘,每块数据盘10个副本,分片冗余数为3 —— 即每个分片3 个副本(replica)。一个table在一年内有分片不可用的累计时间是:10*8*3% /20≈0.2小时,有分片有两个副本同时因disk故障丢失的时间为: 10*8*10*2/3*3%*3%/365/24≈0.001826时,因此可得可用性为 1- (0.2 + 0.001826)/365/24≈99.999%。

    n  可靠性量化计算

        一个key-value对成功写入系统后,在一年内丢失的概率为:3%*3%/365/24*3%/365/24≈3.5*10-13,即可靠性为99.99999999996%。 

    7.9. 可扩展性优势

        当数据过多造成容量不足时,或检索分析过程发现性能不足时,蜂鸟只需简单增加硬件即可让系统容量,同时性能也会线性提升—— 增加硬件应优先考虑增加机器中的磁盘,然后才是增加机器。

    7.10. 高并发优势

         蜂鸟设计上重点考虑了多用户并发读写需求,因此相比传统数据库而言,蜂鸟系统在并发性上可以说优势显著 ——SQL接口可支持到数百级别并发读写 ;NOSQL接口单机可支持到数万级别并发读写。

         高并发度的根本原因在于数据负载和查询负载能保持均衡(无数据倾斜和计算倾斜)。因为蜂鸟在时序数据存储时,会将记录按KEY均衡分布到集群中各机器上,在机器内部还会被均分到各磁盘上;而对于分析计算任务,按照数据就近原则,子查询任务将被派发到各段数据所在机器的所在磁盘上并行执行。这种数据分布和计算分布策略对于时序数据处理场景能做做到最大均衡,不存在数据或计算“热点”问题。(Hbase虽然也常用于时序存储,但只能做到数据均衡而无法做到计算均衡)

    7.11. 互联互通性

       除了接口上符合 SQL92 和 M/R 标准外 (见章节8),在互联互通性方面蜂鸟进一步做了两个努力: 


    n 兼容 Mysql协议 :其目的是为了让蜂鸟继承Mysql 客户端的最大优势 ——支持多平台(Linux,Windows,Mac OS)工具访问。但更重要的好处则是:蜂鸟可以借助Mysql协议支持第三方BI软件(因为多数BI软件都支持Mysql)。 


    n 蜂鸟提供了自身与传统关系数据库之间的数据高速迁移工具:可以高效的从传统关系数据库(如 Oracle、Mysql)将数据迁移到蜂鸟时序数据库中,反之亦然。

    7.12.丰富的分析函数

    方便和强大的分析函数是分析型数据库不可或缺的功能—— 既能简化繁琐的SQL表达式,又能提高分析效率。因此蜂鸟系统也努力提供了如下分析函数:

    n  一些列内置的分析函数(兼容Oralce分析函数,如lag,lead,over等窗口函数)

    n  允许用户自定义分析函数

    n  提供特定行业(如交通、电力)的业务分析函数

    7.13. 简单易用的管理界面

        蜂鸟管理中断简单易用,功能完善。支持:一键安装、SQL编辑、结果可视化、故障恢复扩容、缩容等操作。

    7.14. 其它优势                            

    n  支持跨数据中心部署:蜂鸟可应对数据高安全性要求,支持跨机房(地域)部署。

    n  支持数据超期淘汰(OldOut) :蜂鸟支持过期数据自动淘汰,以腾出存储空间用于存储近期数据(如,只存储最近半年的数据)。

    n  支持在线备份:无需停机可在线备份数据(如磁带机)。

    n  支持非时序表:除了时序表外,码表和结果表都是典型非时序表。因此蜂鸟除了重点支持时序表外,同时也支持非时序表的支持。从而予用户使用上的最大方便—— 如,用户可以将时序表和码表进行join,还可以将join结果写入到结果表中。

    n  支持按需动态健表、删表:用户可针对不同场景,在建表语句中指定表类型(时序、非时序)和分布属性(副本数、分布广度等);建表语句可由管理员手动执行,也可在程序中通过API调用;蜂鸟系统可管理数是十到数万张不同类型、不同分布的数据表,完全可以作为数据资源池使用。

    n  支持在线扩容、缩容:蜂鸟支持在不中断在线服务的情况下,进行系统扩容、缩容等运维操作;而且扩容、缩容操作支持以表粒度进行。

    n  支持在线Bug Fix:蜂鸟支持在不中断在线服务的情况下,修复软件Bug。

    n  高速数据恢复:即磁盘或机器永久故障后,系统可将数据损失的副本数据高速(集群环境下 20 - 60分钟)恢复,尽快让副本数重新达到期望值。

    8. 编程和使用接口

          具备方便、易用的用户接口是时序数据库系统能被接受的首要条件,那什么样的接口是最方便、易用呢?从我们多年工程实践经验来看,时序数据库目前最成熟、最受欢迎的用户接口还是SQL(JDBC/ODBC) —— 蜂鸟实现了SQL92标准! 

    n  一是因为SQL接口表现力很强,常见的时序查询和统计需求几乎都可用SQL表达。

    n  二是因为SQL接口容易和第三方或遗留系统对接。JDBC,ODBC是第三方系统访问数据库的业界标准接口,遵循其标准才能与第三方软件实现互联互通。

    鉴于此,我们首推SQL接口;其次我们还提供了其它访问方式:

    ü   NativeJava Api (直接操作NOSQL层)

    ü   ThriftApi(直接操作NOSQL层) —— 可适配各种编程语言(Python、c++、ruby、Java、erlang等)

       除了上述访问接口外,蜂鸟系统同时也兼容Hadoop体系,因此可以直接使用Hive,Pig和M/R程序访问蜂鸟中存放的时序数据。

    9. 竞品分析

          时序数据处理的产品大致分为两类:一类是NOSQL架构的时序数据存储产品(还不能说是数据库);一类是在传统关系数据库内实现时序功能的商业数据库产品。

    前者具有良好的扩展性、可用性和并发性能,但接口一般不支持标准SQL(即便有些产品能模仿SQL接口,但也不能支持聚合运算、嵌套查询、或多表关联等操作);后者能支持标准SQL(甚至支持事务操作),但扩展性和并发性能相比前者要逊色许多。

    蜂鸟系统架构融合了NOSQL和SQL架构的精髓(见体系架构一章)。既具备了NOSQL系统的高扩展性、可用性和高并发特征,同时也具备了SQL系统方便的查询接口和强大的分析功能。

    9.1主要竞品分析

    n   Oralce/Mysql/MS-SQL

    Oracle/Mysql/MS-SQL等传统关系数据库的设计目标是针对“随机访问、随时更新”类档数据,而对于“流式追加、区间检索”类时序数据并未做任何优化处理。事实上传统关系数据库无法应对大规模时序数据处理需求(具体原因见章节2)。

    n   Hbase

    Hbase具备良好的可扩展性,而且也经常被用于存储时序数据。对于时序数据存储又可分为横表存储和纵表存储。横表是指用RowKey存储ID(KEY),而用动态列存储时序事件;纵表则是用RowKey存储ID和事件时间戳的组合键(组合方式多种,如蜂鸟格式中的 PKT,KT,TK等)。但Hbase/Cassandra存在如下问题是:

    1. 未能支持SQL92标准,因此对于聚合运算、嵌套查询、多表join等常用操作都无法简单实现。

    2. 由于存储引擎使用java语言实现,相比C/C++实现的存储引擎,检索性能相对较慢。

    3. Hbase存储按rowKey有序,因此若采用横表方式存储时序数据,则会遇到“热点”问题(具体见7.1章节)。

    n   Cassandra

         Cassandra 相比Hbase而言,对时序数据更友好—— 其避免了hbase的热点问题。但其最终一致性模型对于下推扫描和计算并非最佳选择。

    n   Druid、Geras、InfluxDB、KairosDB、KDB+、OpenTSDB、SiteWhere、TempoDB、TreasureData

    维基百科给出了上述当前比较流行的NOSQL类时序数据库。这些NOSQL架构的时序数据库,其主要服务形态是提供云服务,对外一般提供rest风格的web 接口。它们和Hbase、Cassandra的主要缺陷一样(实际上不少后台的存储就是Hbase或Mysql)—— 不支持SQL92,不支持聚合运算、嵌套查询、多表join等常用查询。

    n   Hive/Impala

    Hive/Impala 实现了SQL92的相关标准,适合数据离线分析(一般使用时间分区的方式将数据存储于HDFS之上)。但对于时序数据处理要求的“实时数据获取”需求无法满足(见7.3),因此不便运用于实时在线系统。

    n   Informix Timeseries

    InformixTimeseries 是当前时序数据库领域里的商业数据库的代表。其有专门“时序数据”类型、也支持SQL92、甚至还支持事务操作。但它扩展性上和并发性比不上NOSQL架构的时序存储系统,也是因为这个原因使得其计算能力受到限制,因此面对计算密集性业务,Informix TimeSeries 比不上蜂鸟。除此以外,InformixTimeSeries 还有两个重要“缺点” —— 成本高、非国产。

    n   Oracle xadata

    Oracle Exadata 数据库是ORACLE应对大规模数据分析的旗舰产品,其已以高性能著称。但Exadata必须使用专有硬件,而且也并非为时序数据优化。另外,和Informix 一样,Exadata扩展性和并发性的局限也使得其计算能力受限(简单计算即可得知:装备20台PC服务器的蜂鸟集群可有大约12*20个CPU CORE 投入计算任务,而Exdata全机架配置也不过128个CPU),而且相比informix其成本更高。

    10. 基准测试

    10.1对比Mysql

       我们使用一组来自NCDC(National Climatic Data Center)的全球气象监控(来自全球分布的气象站)数据作为测试数据,比较蜂鸟和MYSQL对海量气象时序数据处理能力差异。

       测试环境说明:

    ü     物理机器一台: 16G内存、1个容量1T的STATA硬盘、E5-2640(8 core)CPU

    ü     时序数据: 1992-2014年,共约1200个气象监测站,数据记录50字节左右,每分钟产生1条记录。因此原始数据大约120亿条,大小600G左右。

    ü     数据原始格式:93721KBWI(气象站ID) BWI2003090100080508(时间戳) 0.148 N 0.138 N 153(2min均向) 5(2min均速) 151(最高5sec均向) 6(最高5sec均速) 10 60(能见度)

    ü     查询语句: 查询某天平均“能见度” ——  SELECT avg 能见度列 FROM data WHERE id(气象站ID) = ‘93721KBWI’AND timestamp BETWEEN ‘2013-01-01’ AND ‘2014-01-02’—— 大约需要扫描170万(1200*24*60)条记录


     

        图4

       如图(4)可见蜂鸟和MYSQL除了统计速度上存在明显差距外,Mysql 在大约写入4亿条数据之后(这时系统内存不够存放索引),读取性能显著下降,而蜂鸟系统则表现出“恒时查询”特性。

       注:为了便于比较,我们仅是单机单盘条件下对比蜂鸟和Mysql系统。

     

    10.2.性能预测

    由于蜂鸟系统按KEY和时间有序存储数据(类似传统数据库的聚集索引),而且具备线性扩展能力,因此完全可以在给定的硬件环境下,较为准确的预测出检索速度。

    具体的推测方式可按下面的公式简单计算:

    l  机器数量 = M

    l  单机磁盘数量 = N

    l  记录大小 = X

    l  记录数量 = C

    l  实体(KEY)数量 = K

    l  记录时间跨度 = S

    l  压缩比 = Z

    l  磁盘顺序读速度约为60M/s

     

    n  给定时间段D内检索单key耗时T(即在单盘上扫描出该key在该时段的所有记录耗时)

    =  (D/S * C/K  * X ) / Z / (60*1024*1024) 

    n  给定时间段D内统计耗时T(即多盘并发扫描出该时段所有数据耗时)

    =  (D/S * C *X)/ Z / (60*1024*1024) / (M*N)

     

       举例说明:集群机器数量为10,每个机器8个磁盘;记录大小100字节,记录数量100亿,key数量1万,时间跨度1年,压缩比是3,那么可推断出如下结果:

    ü  检索一天内的给定key时间约为 = (1/365 * 10,000,000,000/10,000 * 100) / 3 / (60 * 1024*1024) =0.002秒

    ü  统计一天内的数据时间约为=   1/365 * 10,000,000,000 * 100 / 3 / (60 * 1024*1024) /(10*8) = 0.4秒

     注意,上述查询耗时是扫描数据理论速度,实际在集群环境下执行查询的总耗时必然要高于其。因为除了扫描磁盘外,执行过程还要包含“语法解析”、“任务调度”、“结果返回”、“结果解析”等环节,但是即便如此,以上操作的也能达到亚秒返回(所谓的“秒出”)。

     

    10.3性能优化

     相比传统关系数据库,蜂鸟系统的优化相对简单。从性能预测给出的公式就能看出,优化方向是:

    1. 缩减记录大小;

    2. 提高处理并发度;

    3. 增加磁盘顺序读写速。

        缩减记录大小的最简单办法是将记录中离散度不高的字段进行码表化,进而减少记录大小。比如卡口送出的原始过车记录中含有车品牌、方向等信息(如“大众”、“西向东”)就属于离散度低的字段,完全可以以数字代替,而使用码表来维护数字和实际品牌或方向间的对应关系,查询时将过车时序表和码表做Join即可。提高并发度最简单、经济的办法是增加单机所带磁盘数目,然后是增加机器。增加磁盘顺序读写速度常用办法有:使用前先格式化一次磁盘;采用“轻量”磁盘挂载方法(如ext4格式磁盘采用noatime,data=writeback,barrier=0,nobh,errors=remount-ro方式挂载);使用更对读友好的调度器DeadLine;其它内核参数微调,如增加磁盘队列长度的内核参数(sudo sh -c'echo 1024 > /sys/block/sdx/queue/nr_requests)。

    11. 最佳实践(实例介绍)

    11.1 电力-智能电表相关业务:

    n   用户用电量查询:给定用户单日查询或多日查询等。

    n   低电压异常判断:电压位于 198-205V,则认为该电表低电压异常。

    n   电能量异常判断:当前时间点的电能量值小于前一个时间点电能量值,但中间电表并没有过零的情况发生,则认为该电表电能量异常。

    n   电量/电费计算:计算一段时间内电量的消耗和电费(分时计算)。

    n   线损计算:根据各供电点 ( 电量流入 ) 和受电点 ( 电量流出 ) 的电能量数据的差值为线损。

    n   三相不平衡分析:计算电表24(整点)电流不平很曲线。计算方法三相电中最大电流减去最小电流,再除以最大电流。

    n   分析整箱有功电量曲线中相邻两个整点的跳数。相邻两点之差大鱼该亮点中最大值的%80则为跳跃。

    n   环比增长率计算:本月比上月增长情况。一般环比增长率可使用如下公式计算:(本月电量消耗值– 上月电量消耗值)/ 上月电量消耗值。

    11.2 交通-卡口监控相关业务:

    n   车辆轨迹抽取:按照给定时段检索给定车辆的行车轨迹(经过卡口的记录)。

    n   嫌疑套牌车分析:在选定的行政区划、卡口范围内利用卡口位置信息、路段时段的平均车速信息、以及车辆经过相邻卡口的耗时。当发现耗时明显过小,则可推断出现了相同号牌号码和号牌种类的车辆,即套牌车。

    n   伴随车分析:根据用户输入参数查询出指定车辆(主车)的轨迹,并根据查询出的轨迹结果分析出车辆经过相应卡口时(要求同方向)在伴随时间偏差范围出现的车辆,如果这些车辆的累计出现次数达到用户输入的伴随车轨迹次数,该车列为伴随车。

    n   碰撞车分析:在明确时间和地点,不明确车辆信息的情况下,分析在多个不相关的地点同时出现的车辆信息。

    11.3 刑侦:通讯记录检索相关业务

    n   查询给定时间范围嫌疑号码的呼入呼出记录。

    n   查询给定时间范围嫌疑邮箱的发件和收件记录。

    n   根据嫌疑人的电话、短信、邮件记录,分析嫌疑人的社会关系网。

     

    Hummer TimeSeries DB Dock DEMO 介绍文章和下载见 http://blog.csdn.net/kanghua/article/details/44653149


    展开全文
  • 信息化工程造价.doc

    2022-07-19 07:31:19
    信息化工程造价.doc
  • 信息化工程造价.docx

    2022-07-19 07:31:18
    信息化工程造价.docx
  • 医疗大数据分析应用平台.doc
  • 《基于ARM的LED显示屏的控制系统的设计与实现》.doc
  • 医疗大数据分析应用平台(DOC84页).doc
  • 基于FPGA的模拟信号检测处理系统设计与仿真2.doc
  • 嵌入式系统发展历史嵌入式系统发展历史
  • 时序分析:隐马尔可夫模型

    千次阅读 2016-06-06 11:29:18
    接下来我们试图去预言我们所不能观察到的"隐形"的系统状态,在上面的例子中,能被观察到的序列就是海藻的状态吗,隐形的系统就是天气情况 然后我们看一下关于我们这个模型的一些问题,在上面那个例子中,也许我们想...

         在AI综合领域,HMM模型是离散贝叶斯网络,最主要用于非确定性(概率)推理。

           上次的文章被标记为链接,真是有意思。

        

    一:隐马尔科夫模型   


           本人对这篇转载做了修改!

           英文链接http://www.comp.leeds.ac.uk/roger/HiddenMarkovModels/html_dev/main.html

           文章链接:http://blog.csdn.net/likelet/article/details/7056068      此文的公式和说明更清晰一些,没有分段总结。

           文章原始链接:http://www.52nlp.cn/hmm-learn-best-practices-one-introduction

           算法杂货铺——分类之贝叶斯网络及应用:http://www.cnblogs.com/leoo2sk/archive/2010/09/18/bayes-network.html


    (一):定义及简介介绍(introduction)


    通常我们总是对寻找某一段时间上的模式感兴趣,这些模式可能出现在很多领域:一个人在使用电脑的时候使用的命令的序列模式;一句话中的单词的序列;口语中的音素序列。总之能产生一系列事件的地方都能产生有用的模式。

    考虑一个最简单的情况:有人(柯南?)试图从一块海藻来推断天气的情况。一些民间的传说认为“soggy”的海藻意味着潮湿(wet)的天气,“dry”的海藻预示着晴朗(sun)。如果海藻处于中间状态“damp”,那就无法确定了。但是,天气的情况不可能严格的按照海藻的状态来变化,所以我们可以说在一定程度上可能是雨天或是晴天。另一个有价值的信息是之前某些天的天气情况,结合昨天的天气和可以观察到的海藻的状态,我们就可以为今天的天气做一个较好的预报。

    这是在我们这个系列的介绍中一个非常典型的系统。

     

    • 首先我们介绍一个可以随时间产生概率性模型的系统,例如天气在晴天或者雨天之间变动。
    • 接下来我们试图去预言我们所不能观察到的"隐形"的系统状态,在上面的例子中,能被观察到的序列就是海藻的状态吗,隐形的系统就是天气情况
    • 然后我们看一下关于我们这个模型的一些问题,在上面那个例子中,也许我们想知道

     

    1. 如果我们观察一个星期每一天的海藻的状态,我们是否能知相应的其天气情况
    2. 如果给出一个海藻状态的序列,我们是否能判断是冬天还是夏天?我们假设,如果海藻干(dry)了一段时间,那就意味着是夏天如果海藻潮湿(soggy)了一段时间,那可能就是冬天。

     


     

    (二):生成模式(Generating Patterns)

     


    • 确定的模式(Deterministic Patterns)

    考虑交通灯的例子,一个序列可能是红-红/橙-绿-橙-红。这个序列可以画成一个状态机,不同的状态按照这个状态机互相交替

    确定的模式

    我们可以注意到,每一个状态都只依赖于此前的状态,如果当前的是绿灯,那么接下来就是橙灯,这就是一个确定型的系统。确定型的系统更容易理解和分析,只要这些状态转移都是已知的。

     

     

    • 不确定的模式(Non-Deterministic Patterns)

    为了让之前那个天气的例子更贴近现实,我们可以添加一个状态-多云。和交通灯的例子不同,我们不能得到一个确定的状态转移系统,但是我们还是希望能得到一个天气的模式。

    一种办法就是假设这个模型的每个状态都只依赖于之前的状态,这个假设被称为马尔科夫假设,这个假设可以大大的简化这个问题。显然,这个假设可能是一个非常糟糕的假设,导致很多重要的信息都丢失了。

    当涉及到天气的时候,马尔科夫假设假设如果我们知道之间一些天的天气的信息,不考虑风力、气压等因素,那么我们就能预言今天的天气。当然,和其他许多例子一样,这个列子也是不合实际的。但是,这样一个简化的系统可以有利于我们的分析,所以我们通常接受这样的假设,因为我们知道这样的系统能让我们获得一些有用的信息,尽管不是十分准确的。

    晴天雨天阴天

    一个马尔科夫过程就是指过程中的每个状态的转移只依赖于之前的n个状态,这个过程被称为1个n阶的模型,其中n是影响转移的状态的数目。最简单的马尔科夫过程就是一阶过程,每一个状态的转移只依赖于其之间的那一个状态。注意这和确定型的系统不一样,因为这种装因是有概率的,而不是确定的。下面这个图展示了天气这个例子中所有可能的一阶转移:

    一阶状态转移

    注意一个含有M个状态的一阶过程有M的平方个状态转移。每一个转移的概率叫做状态转移概率(state transition probability),就是从一个状态转移到另一个状态的概率。这所有的M的平方个概率可以用一个状态转移矩阵来表示。注意这里有一个假设,概率不随时间的变化而变化,这又是一个不现实但很重要的假设。下面就是一个状态转移矩阵的列子:

    状态转移矩阵

    这个矩阵的意思是,如果昨天是晴天,那么今天又50%的可能是晴天,37.5%的概率是阴天,12.5%的概率会下雨,很明显,每一行的和都是1。

    为了初始化这样一个系统,我们需要一个初始的概率向量:

    初始概率向量

    这个向量表示第一天是晴天。

    到这里,我们就为一阶马尔科夫过程定义了以下三个部分:

    • 状态:晴天、阴天和下雨
    • 初始向量:定义系统在时间为0的时候的状态的概率
    • 状态转移矩阵:每种天气转换的概率

    所有的能被这样描述的系统都是一个马尔科夫过程。

     

    • 总结(Summary)

    我们为了找到随时间变化的模式,就试图去建立一个可以产生模式的过程模型。我们使用了具体的时间步骤、状态、并且做了马尔科夫假设。有了这些假设,这个能产生模式系统就是一个马尔科夫过程。一个马尔科夫过程包括一个初始向量和一个状态转移矩阵。关于这个假设需要注意的一点是状态转移概率不随时间变化。


    (三):隐含模式(Hidden Patterns)


           当马尔科夫过程不够强大的时候,我们又该怎么办呢?

     

          在某些情况下马尔科夫过程不足以描述我们希望发现的模式。回到之前那个天气的例子,一个隐居的人可能不能直观的观察到天气的情况,但是有一些海藻。民间的传说告诉我们海藻的状态在某种概率上是和天气的情况相关的。在这种情况下我们有两个状态集合,一个可以观察到的状态集合(海藻的状态)和一个隐藏的状态(天气的状况)。我们希望能找到一个算法可以根据海藻的状况和马尔科夫假设来预测天气的状况。

         一个更现实的例子是语音识别,我们听到的声音是声带、喉咙和一起其他的发音器官共同作用的结果。这些因素相互作用,共同决定了每一个单词的声音,而一个语音识别系统检测的声音(可以观察的状态)是人体内部各种物理变化(隐藏的状态、引申一个人真正想表达的意思)产生的。

            某些语音识别设备把内部的发音机制作为一个隐藏的状态序列,把最后的声音看成是一个和隐藏的状态序列十分相似的可以观察到的状态的序列。在这两个例子中,一个非常重要的地方是隐藏状态的数目和可以观察到的状态的数目可能是不一样的。在一个有三种状态的天气系统(sunny、cloudy、rainy)中,也许可以观察到四种潮湿程度的海藻(dry、dryish、damp、soggy)。在语音识别中,一个简单的发言也许只需要80个语素来描述,但是一个内部的发音机制可以产生不到80或者超过80种不同的声音。

           在上面的这些情况下,可以观察到的状态序列和隐藏的状态序列是概率相关的。于是我们可以将这种类型的过程建模为又一个隐藏的马尔科夫过程和一个和这个马尔科夫过程概率相关的并且可以观察到的状态集合。

          下图显示了天气的例子中隐藏的状态和可以观察到的状态之间的关系。我们假设隐藏的状态是一个简单的一阶马尔科夫过程,并且他们两两之间都可以相互转换。

    隐马尔科夫


            下图则明确的表示出模型的演化,其中绿色的圆圈表示隐藏状态,紫色圆圈表示可观察到状态,箭头表示状态之间的依存概率。一个 HMM 可用一个5元组 { N, M, π,A,B }表示,其中 N 表示隐藏状态的数量,我们要么知道确切的值,要么猜测该值,M 表示可观测状态的数量,可以通过训练集获得, π=i}为初始状态概率,A={aij}为隐藏状态的转移矩阵 Pr(xt(i) | xt-1(j)),B={bik} 表示某个时刻因隐藏状态而可观察的状态的概率,即混淆矩阵,Pr(ot(i) | xt(j))。在状态转移矩阵和混淆矩阵中的每个概率都是时间无关的,即当系统演化时,这些矩阵并不随时间改变。对于一个 N 和 M 固的 HMM 来说,用 λ={ π, A, B } 表示 HMM 参数。



            隐藏的状态和可以观察到的状态之间有一种概率上的关系,也就是说某种隐藏状态H被认为是某个可以观察的状态O1是有概率的,假设为P(O1|H)。如果可以可以观察的状态有三种,那么很显然P(O1|H)+ P(O2|H)+ P(O3|H) = 1。这里我和原文的意思不太相同,原文说的意思是P(O1|H1)+ P(O1|H2)+P(O1|H3)= 1,但是这和下面的例子又不同。

           这样,我们也可以得到一个另一个矩阵,称为混淆矩阵。这个矩阵的内容是某个隐藏的状态被分别观察成集中不同的可以观察的状态的概率,在天气的例子中,这个矩阵如下图:

    混淆矩阵

    注意到图中每一行的和为1,但是每一列的和不为1,这里我觉得可能是原文出错了,或者隐藏状态还有其他。

     

    总结

    我们已经看到有一些过程是和一个隐藏的马尔科夫过程概率相关的。在这种情况下,可以观察到的状态和隐藏的状态的数目可能是不一样的。我们可以把这种过程建模为隐马尔科夫模型(HMM)。这个模型包含两个状态集合和三个概率集合。

    • 隐藏的状态:一个隐藏的马尔科夫过程
    • 可以观察到的状态:如名
    • 初始向量:初始状态的隐藏状态的概率
    • 状态转移矩阵:隐藏状态的状态转移概率
    • 混淆矩阵:隐藏状态被观察成各个可以观察到的状态的概率

    我们可以认为隐马尔科夫模型是在一个不可观察的马尔科夫过程上添加了一个可以观察到的状态集合,加上这个过程到这个集合的一些概率关系得到的。


    (四):隐马尔科夫模型(Hidden Markov Models)


    定义隐马尔科夫模型可以用一个三元组(π,A,B)来定义:

    1. π 表示初始状态概率的向量
    2. A =(aij)(隐藏状态的)转移矩阵 P(Xit|Xj(t-1)) t-1时刻是j而t时刻是i的概率
    3. B =(bij)混淆矩阵  P(Yi|Xj)在某个时刻因隐藏状态为Xj而观察状态为Yi的概率

    值得注意的是,在状态转移矩阵中的每个概率都是时间无关的,也就是说我们假设这个概率是固定的,不随时间变化。当然,这是马尔科夫模型最不切合实际的一个假设。

     

    隐马尔科夫模型的使用

    如果一个模型可以被描述成一个隐马尔科夫模型,有三个问题可以得到解决。

    前两个是模式识别的问题:

           1)根据隐马尔科夫模型得到一个可观察状态序列的概率(评价);

            2)找到一个隐藏状态的序列使得这个序列产生一个可观察状态序列的概率最大(解码)。

    第三个问题就是根据一个可以观察到的状态序列产生一个隐马尔科夫模型(学习)。

     

    1. 评价

    假设我们有很多隐马尔科夫模型(也就是说一个三元组的集合)描述不同的系统和一个可观察状态序列集。我们也许想知道哪一个隐马尔科夫模型最可能产生某个可观察状态序列。比如说,我们也许有一个海藻的“Summer”模型和一个“Winter”模型,因为海藻在夏天和冬天的状态应该是不同的,我们希望根据一个可观察状态(海藻的潮湿与否)序列来判断现在是夏天还是冬天。

    我们可以使用前向算法来计算在某个特定的HMM下一个可观察序列的概率,然后据此找到最可能的模型。

    这种类型的应用通常出现在语音设别中,通常我们会使用很多HMM,每一个针对一个特别的单词。一个可观察状态的序列是从一个可以听到的单词向前得到的,然后这个单词就可以通过找到满足这个可观察状态序列的最大概率的HMM来识别。

     

    2. 解码

    根绝可观察状态的序列找到一个最可能的隐藏状态序列。

    和上面一个问题相似的并且更有趣的是根据可观察序列找到隐藏序列。在很多情况下,我们队隐藏状态更有兴趣,因为其包含了一些不能被直接观察到的有价值的信息。比如说在海藻和天气的例子中,一个隐居的人只能看到海藻的状态,但是他想知道天气的状态。这时候我们就可以使用Viterbi算法来根据可观察序列得到最优可能的隐藏状态的序列,当然前提是已经有一个HMM。

    另一个广泛使用Viterbi算法的领域是自然语言处中标引词性。句子中的单词是可以观察到的,词性是隐藏的状态。通过根据语句的上下文找到一句话中的单词序列的最有可能的隐藏状态序列,我们就可以得到一个单词的词性(可能性最大)。这样我们就可以用这种信息来完成其他一些工作。

     

    3.学习

    从一个观察集中得到一个隐马尔科夫模型。

    第三个问题也是最困难的问题,根绝观察到的序列集来找到一个最有可能的HMM,也就是说确定一个最有可能的三元组(π,A,B)。当A,B矩阵都不是直观可测量(通过经验得到)的的时候,可以使用前向后向算法来解决这个问题。

     

    总结:

    尽管做出了一些不太符合实际的假设,但是用三元组描述的HMMs在描述真实系统并进行分析的时候具有很大的价值,并且可以解决下面这些问题:

    1. 用前向算法找到最有可能的隐马尔科夫模型
    2. 用Viterbi算法根据观察序列找到最有可能的隐藏序列
    3. 用前向后向算法决定最有可能产生某个观察集的隐马尔科夫模型的参数


    (五):前向算法(Forward Algorithm)

     

    1如果计算一个可观察序列的概率?  

     

    1.穷举搜索

     加入给定一个HMM,也就是说(P,A,B)这个三元组已知,我们想计算出某个可观察序列的概率。考虑天气的例子,我们知道一个描述天气和海藻状态的HMM,而且我们还有一个海藻状态的序列。假设这个状态中的某三天是(dry,damp,soggy),在这三天中的每一天,天气都可能是晴朗,多云或者下雨,我们可以用下图来描述观察序列和隐藏序列:

    ob

    在这个图中的每一列表示天气的状态可能,并且每个状态都指向相邻的列的每个状态,每个状态装换在状态转移矩阵中都有一个概率。每一列的下面是当天的可观察的海藻的状态,在每种状态下出现这种可观察状态的概率是由混淆矩阵给出的。

    一个可能的计算可观察概率的方法是找到每一个可能的隐藏状态的序列,这里有3^3 = 27种,这个时候的可观察序列的概率就是 Pr(dry,damp,soggy | HMM) = Pr(dry,damp,soggy | sunny,sunny,sunny) + Pr(dry,damp,soggy | sunny,sunny ,cloudy) + Pr(dry,damp,soggy | sunny,sunny ,rainy) + . . . . Pr(dry,damp,soggy | rainy,rainy ,rainy)。

    很显然,这种计算的效率非常低,尤其是当模型中的状态非常多或者序列很长的时候。事实上,我们可以利用概率不随时间变化这个假设来降低时间的开销。

     

    2.使用递归来降低复杂度

    我们可以考虑给定HMM的情况下,递归的计算一个可观察序列的概率。我们可以首先定义一个部分概率,表示达到某个中间状态的概率。接下来我们将看到这些部分概率是如何在time=1和time = n(n > 1)的时候计算的。

    假设一个T时间段的可观察序列是:

    seq

    2a.部分概率

    下面这张图表示了一个观察序列(dry,damp,soggy)的一阶转移

    tr

    我们可以通过计算到达某个状态的所有路径的概率和来计算到达某个中间状态的概率。比如说,t = 2时刻clody的概率用三条路径的概率之和来表示:

    paths

    我们用at(j)来表示在t时刻是状态j的概率,at ( j )= Pr( observation | hidden state is j ) x Pr(all paths to state j at time t)。

    最后一个观察状态的部分概率就表示了整个序列最后达到某个状态的所有可能的路径的概率和,比如说在这个例子中,最后一列的部分状态

    是通过下列路径计算得到的:

    final

    因为最后一列的部分概率是所有可能的路径的概率和,所以就是这个观察序列在给定HMM下的概率了。

     

    2b.计算 t = 1时候的部分概率

    计算部分概率的公式是:a t ( j )= Pr( observation | hidden state is j ) x Pr(all paths to state j at time t)

    当t = 1的时候,没有路径到某个状态,所以这里是初始概率, Pr( state | t = 1) = P(state),这样我们就可以计算t=1时候的部分概率为:

    ini

    因为在初始的时候,是状态j的概率不仅和这个状态本身相关,还和观察状态有关,所以这里用到了混淆矩阵的值,k1表示第一个观察状态,bjk1表示隐藏状态是j,但是观察成k1的概率。

     

    2c.计算 t > 1时候的部分概率

    还是看计算部分概率的公式:a t ( j )= Pr( observation | hidden state is j ) x Pr(all paths to state j at time t)

    这个公式的左边是从混淆矩阵中已知的,我只需要计算右边部分,很显然右边是所有路径的和:

    cal

    需要计算的路径数是和观察序列的长度的平方相关的,但是t时刻的部分概率已经计算过了之前的所有路径,所以在t+1时刻只需要根据t时刻的概率来计算就可以了:

    t时刻

    这里简单解释下,bjkt+1 就是在t+1时刻的第j个隐藏状态被认为是当前的观察状态的概率,后面一部分是所有t时刻的隐藏状态到t+1时候的隐藏状态j的转移的概率的和。这样我们每一步的计算都可以利用上一步的结果,节省了很多时间。

     

    2d.降低计算复杂度

    我们可以比较穷举和递归算法的复杂度。假设有一个HMM l  =(P,A,B),其中有n个隐藏状态,我们有一个长度为T的观察序列。

    穷举算法的需要计算所有可能的隐藏序列:

    穷举

    需要计算:

    穷举

    很显然穷举算法的时间开销是和T指数相关的,而如果采用递归算法,由于我们每一步都可以利用上一步的结果,所以是和T线性相关的。(这里认为n是一个常数)

     

    3.总结

    这里我们的目的是在某个给定的HMM下,计算出某个可观察序列的概率。我们通过先计算部分概率的方式递归的计算整个序列的所有路径的概率,大大节省了时间。在t=1的时候,使用了初始概率和混淆矩阵的概率,而在t时刻的概率则可以利用t - 1时刻的结果。

     

    2、前向算法的定义

    我们使用前向算法去计算T长度序列的概率:

    seq

    每一个y就是观察状态。在t=1时刻的中间节点的部分状态可以用下面的公式计算:

    def

    对于t>1的情况,部分概率的计算可以用下面的公式:

    中间

    这里,我觉得是原作者的笔误,后面的应该是bjkt+1

    这样我们就可以用递归的方式来计算所有可能的路径的概率和,最后,所有的部分概率的计算公式为

    all

    使用天气的例子,计算t = 2时刻的cloud状态的概率方法如图:

    例子

    3、总结

    我们使用前向算法在给定的一个HMM下计算某个可观察序列的概率。前向算法主要采用的是递归的思想,利用之前的计算结果。有了这个算法,我们就可以在一堆HMM中,找到一个最满足当前的可观察序列的模型(前向算法计算出来的概率最大)。


    (六):维特比算法(Viterbi Algorithm)

     

    找到可能性最大的隐藏序列

    通常我们都有一个特定的HMM,然后根据一个可观察序列去找到最可能生成这个可观察序列的隐藏序列。

     

    1.穷举搜索

    我们可以在下图中看到每个状态和观察的关系。

    re

    通过计算所有可能的隐藏序列的概率,我们可以找到一个可能性最大的隐藏序列,这个可能性最大的隐藏序列最大化了Pr(observed sequence | hidden state combination)。比如说,对于上图中的可观察序列(dry damp soggy),最可能的隐藏序列就是下面这些概率中最大的:

    Pr(dry,damp,soggy | sunny,sunny,sunny),

    Pr(dry,damp,soggy | sunny,sunny,cloudy),

    Pr(dry,damp,soggy | sunny,sunny,rainy),

    . . . .

    Pr(dry,damp,soggy | rainy,rainy,rainy)

    这个方法是可行的,但是这种计算的代价是昂贵。和前向算法一样,我们可以利用转移概率在时间上的不变性来降低计算的复杂度。

     

    2.使用递归降低复杂度

    在给定了一个可观察序列和HMM的情况下,我们可以考虑递归的来寻找最可能的隐藏序列。我们可以先定义一个部分概率d,既是到达某个中间状态的概率。接下来我们将讨论如果计算t = 1和t = n( n > 1)的部分概率。

    注意这里的部分概率和前向算法中的部分概率是不一样的,这里的部分概率表示的是在t时刻最可能到达某个状态的一条路径的概率,而不是所有概率之和。

     

    2a.部分概率和部分最优路径

    考虑下面这个图以及可观察序列(dry,damp,soggy)的一阶转移

    部分概率

    对于每一个中间状态和终止状态(t = 3)都有一个最可能的路径。比如说,在t=3时刻的三个状态都有一个如下的最可能的路径:

    path

    我们可以称这些路径为部分最优路径。这些部分最优路径都有一个概率,也就是部分概率d。和前向算法中的部分概率不一样,这里的概率只是一个最可能路径的概率,而不是所有路径的概率和。

     我们可以用d (i,t)来表示在t时刻,到状态i的所有可能的序列(路径)中概率最大的序列的概率,部分最优路径就是达到这个最大概率的路径,对于每一个时刻的没一个状态都有这样一个概率和部分最优路径。

    最后,我们通过计算t = T时刻的每一个状态的最大概率和部分最优路径,选择其中概率最大的状态和它的部分最优路径来得到全局的最优路径。

     

    2b.计算t = 1时刻的部分概率

    当t=1时刻的时候,到达某个状态最大可能的路径还不存在,但是我们可以直接使用在t=1时刻某个状态的概率和这个状态到可观察序列k1的转移概率:

    t = 1

    2c.计算t >1 时刻的部分概率

    接下来我们可以根据t - 1时刻的部分概率来求t 时刻的部分概率

    t

    我们可以计算所有到状态X的路径的概率,找到其中最可能的路径,也就是局部最优路径。注意到这里,到达X的路径必然会经过t - 1时刻的A、B和C,所以我们可以利用之前的结果。达到X的最可能的路径就是下面三个之一:

    (sequence of states), . . ., A, X(sequence of states), . . ., B, Xor (sequence of states), . . ., C, X

    我们需要做的就是找到以AX、BX和CX结尾的路径中概率最大的那个。

    根据一阶马尔科夫的假设,一个状态的发生之和之前的一个状态有关系,所以X在某个序列的最后发生的概率只依赖于其之前的一个状态:

    Pr (most probable path to A) . Pr (X | A) . Pr (observation | X)

    有个了这个公式,我们就可以利用t - 1时刻的结果和状态转移矩阵和混淆矩阵的数据:

    alg

    将上面这个表达式推广一下,就可以得到t时刻可观察状态为kt的第i个状态的最大部分概率的计算公式:

    gener

    其中aji表示从状态j转移到状态i的概率,bikt表示状态i被观察成kt的概率。

     

    2d.后向指针

    考虑下图

    back

    在每一个中间状态和结束状态都有一个部分最优概率d (i,t)。但是我们的目的是找到最可能的隐藏状态序列,所以我们需要一个方法去记住部分最优路径的每一个节点。

    考虑到要计算t时刻的部分概率,我们只需要知道t-1时刻的部分概率,所以我们只需要记录那个导致了t时刻最大部分概率的的状态,也就是说,在任意的时刻,系统都必须处在一个能在下一时刻产生最大部分概率的状态。我们可以利用一个后向指针f来记录导致某个状态最大部分概率的上一个状态,形式化的描述为:

    pointer

    这里argmax表示能最大化后面公式的j值,同样可以发现这个公式之和t-1时刻的部分概率和转移概率有关,因为后向指针只是为了找到“我从哪里来”,这个问题和可观察没有关系,所以这里不需要再乘上混淆因子。

     

    2e.优点

    使用viterbi算法对一个可观察状态进行解码有两个重要的优点:

    1. 通过使用递归来减少复杂度,这点和之前的前想算法是一样的
    2. 可以根据可观察序列找到最优的隐藏序列,这个的计算公式是:

    exe

    where

    exet

    这里就是一个从左往右翻译的过程,通过前面的翻译结果得到后面的结果,起始点是初始向量p

     

    2.补充

    但在序列某个地方有噪声干扰的时候,某些方法可能会和正确答案相差的较远。

    但是Viterbi算法会查看整个序列来决定最可能的终止状态,然后通过后向指针来找到之前的状态,这对忽略孤立的噪声非常有用。

     

    3.总结

    Viterbi算法提供了一个根据可观察序列计算隐藏序列的很高效的方法,它利用递归来降低计算复杂度,并且使用之前全部的序列来做判断,可以很好的容忍噪声。

    在计算的过程中,这个算法计算每一个时刻每一个状态的部分概率,并且使用一个后向指针来记录达到当前状态的最大可能的上一个状态。最后,最可能的终止状态就是隐藏序列的最后一个状态,然后通过后向指针来查找整个序列的全部状态。

     

    (七):前向后向算法(Forward-Backward Algorithm

     

          和隐马尔科夫模型相关的有趣的问题就是判断一个模型的实用性(前向算法)和找到一个隐藏在可观察序列背后的隐藏序列(Viterbi算法)。当然,这两个过程都需要知道HMM的一些信息,比如转移矩阵,混淆矩阵以及初始的π向量。

         但是在很多实际的情况下,HMM不能被直接的判断,这就变成了一个学习问题,前向后向算法可以根据一系列可观察序列来对HMM进行评测。一个可能的例子就是一个很大的语音处理数据库,语音序列可能被建模为一个马尔科夫链,可观察的序列可以被建模为可识别的状态,但是不能直接获得一些其他的相关信息。

          前向后向算法理解起来并不困难,但是却要比前向算法和Viterbi算法要复杂,所以这里我们不再详细的介绍。总的来说,这个算法先对一些参数进行猜测,然后再通过评估这些参数的价值来修改这些参数,使得和给定的训练数据的误差变小,这其实是机器学习中的梯度下降的思想。

          前向后向算法的名称来源于对于每一个状态,这个算法既要计算到达这一状态的前一个状态的概率,也要计算产生终止状态的后向状态的概率,这两个概率都可以通过递归的方法来实现。对HMM参数的调整可以提高中间概率的准确性,并且这些调整是算法迭代的基础。


    详细介绍:

    根据观察到的序列集来找到一个最有可能的 HMM。 

      在很多实际的情况下,HMM 不能被直接的判断,这就变成了一个学习问题,因为对于给定的可观察状态序列 O 来说,没有任何一种方法可以精确地找到一组最优的HMM 参数λ 使 P(O | λ) 最大,于是人们寻求使其局部最优的解决办法,而前向后向算法(也称为Baum-Welch算法)就成了HMM学习问题的一个近似的解决方法。

      前向后向算法首先对于HMM 的参数进行一个初始的估计,但这个很可能是一个错误的猜测,然后通过对于给定的数据评估这些参数的的有效性并减少它们所引起的错误来更新HMM 参数,使得和给定的训练数据的误差变小,这其实是机器学习中的梯度下降的思想。

      对于网格中的每一个状态,前向后向算法既计算到达此状态的“前向”概率,又计算生成此模型最终状态的“后向”概率,这些概率都可以通过前面的介绍利用递归进行高效计算。可以通过利用近似的 HMM 模型参数来提高这些中间概率从而进行调整,而这些调整又形成了前向后向算法迭代的基础。

      另外,前向后向算法是 EM 算法的一个特例,它避免了 EM 算法的暴力计算,而采用动态规划思想来解决问题,Jelinek 在其书《Statistical Methods for Speech Recognition》中对前向后向算法与 EM 算法的关系进行了详细描述,有兴趣的读者可以参考这本书。

      类似于上面讲到的前向算法,我们也可以定义后向变量 βt(i) 来计算给定当前隐藏状态 i 时,部分观察序列 ot+1,ot+2,…,oT的概率,即:

      与前向算法类似,我们也可以通过迭代算法有效计算 βt(i),计算公式如下:

      其中

      进一步我们可以发现

      因此

      下面开始介绍前向后向算法

      首先我们需要定义两个辅助变量,这两个变量可以用前文介绍过的前向变量和后向变量进行定义。

      第一个变量定义为 t 时状态 i 和 t+1 时状态 j 的概率,即

      该变量在网格中所代表的关系如下图所示:

      

      该等式等价于

      利用前向变量和后向变量,上式可以表示为

      第二个变量定义为后验概率,也就是在给定观察状态序列和HMM的情况下,t 时状态 i 的概率,即

      利用前向变量和后向变量,上式可以表示为

      因此,下式为在任意时刻状态 i 的期望,也就是从状态 i 转移到观察状态 o 的期望

      同样,下式也就是从状态 i 转移到状态 j 的期望

      我们可以发现定义的这两个变量之间的关系为

      下面介绍前向后向算法的参数学习过程,在学习的过程中,不断更新 HMM 的参数,从而使得 P(O | λ) 最大。我们假设初始的HMM 参数为  λ={ π, A, B },首先计算前向变量 α 和后向变量 β,再根据刚刚介绍的公式计算期望 ξ 和 ζ,最后,根据下面的3个重估计公式更新 HMM 参数

      如果我们定义当前的HMM 模型为 λ={ π,A,B },那么可以利用该模型计算上面三个式子的右端;我们再定义重新估计的HMM 模型为那么上面三个式子的左端就是重估的HMM 模型参数。Baum 及他的同事在70年代证明了因此如果我们迭代地计算上面三个式子,由此不断地重新估计HMM 的参数,那么在多次迭代后可以得到HMM 模型的一个最大似然估计。不过需要注意的是,前向后向算法所得的这个最大似然估计是一个局部最优解。

     


     

    总结(summary)

     

    通常一个特别的模式不是单独的出现,而是作为某一个时间段下的序列出现。对于以时间为单位的过程有一个假设,一个状态的出现之和其前N个时间单位的状态有关系,这样就是一个N阶马尔科夫链,最简单的情况就是一阶马尔科夫链。

    很多情况下,真实的状态序列是不能被直接观察到的,但是可以在一定概率下被间接观察到,这个观察的结果就是另一个可观察的序列,这样我们就可以定义一个隐马尔科夫模型,这个模型在现在的某些领域体现了很大的价值,尤其是语音识别。

    这种关于真实序列的模型有三个相关的问题:

    1. 评价:一个给定的模型在多大的概率下能产生某个可观察的序列,这个问题可以用前向算法来解决。
    2. 解码:给定一个模型和某个可观察序列,最可能的隐藏序列是什么,这个问题可以用Viterbi算法来解决。
    3. 学习:给定某个可观察序列,怎么知道这个模型的一些参数,这个问题可以用前向后向算法来解决。

    隐马尔科夫模型在分析真实系统的时候表现出了巨大的价值,但是它也有一些缺点,一个最大的缺点就是由于之前的假设导致的过于简化——一个状态只依赖其之间的状态,而且这种依赖是时间无关的。

     

    一个更详细的关于HMMs的介绍可以参见

    L R Rabiner and B H Juang, `An introduction to HMMs', iEEE ASSP Magazine, 3, 4-16.


      参考资料:

      1.http://blog.csdn.net/eaglex/article/details/6376826

      2. http://en.wikipedia.org/wiki/Markov_chain

      3. http://en.wikipedia.org/wiki/Hidden_Markov_model

      4. Lawrence R. Rabiner, A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition.Proceedings of the IEEE, 77 (2), p. 257–286, February 1989.

      5. L. R. Rabiner and B. H. Juang, “An introduction to HMMs,”IEEE ASSP Mag., vol. 3, no. 1, pp. 4-16, 1986.

      6. http://jedlik.phy.bme.hu/~gerjanos/HMM/node2.html

      7. http://www.cs.brown.edu/research/ai/dynamics/tutorial/Documents/HiddenMarkovModels.html

      8. 隐马尔可夫模型简介,刘群

           9.这个................................................................................................



    展开全文
  • 再后来的嵌入式开发使用DSP处理器和RTOS实时操作系统,硬件部分也变得集成度更高更复杂,嵌入式工程师对硬件方面的掌控和要求也越来越低,仅限于看原理,配置一些I/O引脚和寄存器,原理设计基本都交给专门的硬件...
  • 麦克斯韦预言了电磁波的存在,总结出电场和磁场的强度仅用电流和电压就可以简单的关联起来。著名的麦克斯韦方程最初是由近20个方程来表示电路的几个可测性质之间的关系,海维塞修订了麦克斯韦理论形成了4个方程,...
  • (b)基于返回扰动函数值或梯度信息的随机预言的算法 ©用于确定性有限和最小化的算法,例如,经验风险最小化,其中随机机制仅产生于对目标函数中的组件的子集(小批量)的随机访问。 由于我们的主要兴趣是解决具有确定...
  • 在实时系统中,操作的正确性不仅依赖于逻辑设计的正确程度,而且与这些操作进行的时间有关,也就是说,实时系统对逻辑和时序的要求非常严格,如果逻辑和时序控制出现偏差将会产生严重后果。 实时系统 主要通过三个...
  • Javascript的时序和同步机制

    千次阅读 2011-09-28 20:21:22
    http://dev.opera.com/articles/view/timing-and-synchronization-in-javascript/> 时序问题是Javascript应用程序中最难解错误的来源之一。在开发中从来不出现的问题可能在终端用户的慢速网络和机器上冒出
  • 【杂文】宇宙思辨

    2016-12-16 23:20:16
    在管理的角度来说,如何让多人形成一个团队协同工作,就是要把人的大脑链接在一起,有时序地进行工作,这个非常类似大型计算系统,将多个计算节点链接在一起进行计算,组成一个整体服务,目前已经有科学家探索如何...
  • David Ha 不会想到,这句预言被一个月后出现的 Transformer 打破,而这仅用了 4 年时间。 著名机器学习资源网站 Papers with Code 在 1 月 20 日发布的 Newsletter 中列举了近期应用 Transformer 的十大新任务: ...
  • 1 T5 思维导图 为了解决Text-to-Text问题,目前主要有Encoder-Decoder、Language model和Prefix LM三类结构。Language model和Prefix LM比较适用于NLU类问题,但对于NLG,实验结果表明Encoder-Decoder效果更好。...
  • 细说嵌入式驱动程序设计

    千次阅读 2020-11-29 19:16:59
    触发中断的时间点 GPIO通过不同的状态和时序组合以达到控制外部IC的目的,以下是某NAND Flash 读操作的时序图: image-20201128130254639 编写驱动时,就要按照NAND Flash datasheet里的时序图,先依序改变各个PIN...
  • • 控制总线(CB):用来传送控制信号、时序信号和状态信息等。CB中的每一条线的信息传送方向是单方向且确定的,但CB作为一个整体则是双向的 考点6:输入输出的程序控制方式 第四种DMA方式是指数据在主存和外设直接...
  • 区块链的认识与总结

    2022-05-30 11:37:42
    1.4 区块链的数据结构 区块链是一个链式的数据结构,它是由 经过共识 的 区块 按照 时序的顺序 进行链接而成的一条链式结构,通过区块 头中的父区块 hash 进行链接。 1.5 区块链的数据存储 不管是公链系统,还是...
  • 嵌入式驱动开发总结

    千次阅读 2020-08-12 19:51:10
    对寄存器的配置和修改,完成芯片对于接口的功能设置需求,如模块时钟的开关,gpio的使能,复用功能的配置,中断的使能关断等初始化操作, 然后在通过封装的读写接口,将时序和电平反映外部的引脚上。 2.对外部设备或...
  • (6)灵活的版本处理技术,因为Java预言本身内置了版本控制功能,使开发人员能够更加容易挤开发和维护。 (7)完善的错误,异常处理机制,Java提供了完善的错误和异常处理机制,使程序在交付应用时能够更加健壮。 ...
  • 这就是我建议的自动化测试和手工测试有机结合的策略:新功能采用探索式测试,回归测试尽量全部自动化,针对上一次迭代实现的功能进行脚本开发,如 2 所示。 探索未知的,自动化已知的 这几年我一直倡导要重新认识...
  • 《Spring 揭秘》是一本09年出版的书,当时还在流行,作者大胆预言有着更广阔的发展前途,并且建议新的项目采用进行开发。现在回过头来看,当年的之于就如现今的 之于 。当年作者熟练掌握了才悟得的好,那么如今在...
  • 947: Estimating Early Fundraising Performance of Innovations via Graph-based Market Environment Model947:通过基于的市场环境模型估计创新的早期筹款绩效 951: Multi-Label Classification with Label ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 384
精华内容 153
关键字:

时序图语言