时间序列的标签

本篇文章是为了介绍一种基于少量样本标记而获得更多样本的方法,论文的原文是《Label-Less: A Semi-Automatic Labeling Tool for KPI Anomalies》,是清华大学与多家公司(必示科技,中国建设银行等)的合作论文。

在时间序列异常检测中,因为标注的成本比较大,于是需要寻找一种较少而高效地标注时间序列异常点的方法。在该论文中,Alibaba,Tencent,Baidu,eBay,Sogou提供了上千条时间序列(每条时间序列大约是2-6个月的时间跨度),作者们进行了 30 条 KPIs 的标注工作。但是其标注成本依旧是很大的,于是作者们想到了一种异常相似搜索(anomaly similarity search)的算法,目标是对已经标注好的时间序列异常模式进行模版搜索。目的就是达到 label-less,也就是较少的标注而获得更多的标注数据。

在本篇论文中,在异常检测的过程中,作者们使用了时间序列的预测模型(time series prediction models)来获得时间序列的特征,使用了孤立森林(Isolation Forest) 来对时间序列的特征来做无监督的异常检测。并且其效果由于 one class svm 算法和 local outlier factor 算法。在搜索的部分,作者使用了加速版的 DTW 算法(accelerated dynamic time warping approach)来做相似度的搜索和模式的匹配。其中也尝试了各种技巧和方法,包括 constrained DTW,LB Keogh 方法,early stopping 算法等工具。

整个 Label-Less 的架构图如下表示:

Fig2.png

其中的 Operators 指的是业务运维人员,面对着无标记的多条时间序列曲线。系统首先会进行无监督的异常检测算法啊,包括时间序列的预处理(归一化等)操作,然后使用差分(Difference),移动平均算法(moving average),带权重的移动平均算法(weighted moving average),指数移动平均(ewma),holt winters,ARIMA 等算法来做特征的提取。此时,对于不同的时间序列预测工具,我们可以得到不同的预测值,然后把预测值减去实际值并且取绝对值,就得到时间序列的误差序列。i.e. |p_{i} - x_{i}| 就作为数据点 x_{i} 的特征。

在这种情况下,由于用了六个时间序列预测算法,因此原始的时间序列 X (n\times 1) 就可以变成特征矩阵 X' (n\times 1)。对于特征矩阵 X' 可以使用 isolation forest 来做无监督的异常检测并且做阈值的设定;如下图所示:

Fig3.png

而另外的一部分的异常相似搜索(anomaly similarity search)是在第一部分的基础上在做的,Unsupervised Anomaly Detection 会输出疑似异常或者候选异常,并且基于已知的异常模板(Anomaly Template)进行相似度的匹配,此时可以使用 accelerated DTW 算法,选择出最相似的 Top-K 异常,然后运维人员进行标注,得到更多的样本。

由于,对于两条长度分别是 mn 的时间序列,DTW 相似度算法的时间复杂度是 O(mn),因此在搜索的时候需要必要的加速工作。在这种地方,作者们使用了 LB-Kim,LB-Keogh,LB-Keogh-Reverse 算法来做搜索的加速工作。而这些的时间复杂度是 O(m+n)。整体的思路是,如果两条时间序列 qc 的 LB-Kim,LB-Keogh,LB-Keogh-Reverse 的下界大于某个阈值,则不计算它们之间的 DTW 距离。否则就开始计算 DTW。并且在计算 DTW 的时候,如果大于下界,则会提前终止(early stopping),不会继续计算下去。如果都没有大于阈值,则把这个候选曲线和 dist 距离放入列表,最后根据列表中的 dist 来做距离的逆序排列。

整体流程如下:

AnomalySimilaritySearch

其运行速度也比直接使用 DTW 快不少:

Table3.png

Label-Less 的交互页面如下所示:

图(a)表示使用无监督算法获得的疑似异常;

图(b)表示使用异常搜索算法获得的异常结果。

Fig10.png

下图则表示模板,m 表示模板的长度,c 表示相似的异常候选集个数;

Fig11

总结:

整体来看,本文提供了一种通过少量人工标注无监督算法相似度算法来获得更多样本的方法。在候选的时间序列条数足够多的时候,是可以进行时间序列的相似度匹配的。这给未来在运维领域提供海量的时间序列标注数据给予了一定的技术支持。

 

Advertisements

怀念 Jett

​之前笔者写过不少文章,其中不仅包括技术和数学文章,还有一些日常学习工作的心得,甚至还写过几篇关于旅游的流水账,但是却很少写关于人物的文章。最近我打算写一篇关于人物的文章,用于纪念在工作中一起战斗过的伙伴 Jett。

许多年前,我还在学校读书的时候,就有前辈告诉我,交朋友的时候基本上就只能够在学校,离开了学校之后在职场中想交到合适的朋友是比较困难的。当时作为一枚职场菜鸟的我,也只能够表示对这句话的认同。直到在工作后遇到了 Jett,我对这个观点就有了自己的看法。

屏幕快照 2019-08-10 下午10.02.49

我是2015年7月作为校招生进入公司,Jett 则是2015年10月通过社招进公司的。当年虽然两人身处同一个部门,但是由于不在一个中心,也不是同一条业务线,并且这两个中心平时也没啥日常工作的交集,因此我和 Jett 同处一个部门许久却互相不认识对方。就好比在学校里面,虽然身处同一个院系,甚至同一栋宿舍楼,由于种种原因而不认识对方。

随着工作时间的增加,到 2016 年的时候笔者就已经过了新手保护期。所谓新手保护期,就是每一个新人其实都有一段适应公司的过程,公司也会给人一定的保护时间,但是一旦过了这个时间就不算新人了。大约到了2016年5月份的时候,部门内部启动了一个用机器学习的方法来做安全对抗的项目。当年的安全中心并没有机器学习的从业者,因此需要从其他中心抽调人手去支持他们的项目。在一些机缘巧合之下,我作为数据团队的代表,就和安全团队的同事们同在安全大数据项目组。在公司里面,机器学习的人员通常都是和开发人员通力合作,各司其职,共建一个项目。在项目初期,其实 Jett 也不负责与我对接,后续随着项目的进一步发展和迭代,Jett 就成为了安全中心与我对接的人。

虽然 Jett 是和我对接的人,但是 Jett 主要也是负责平台开发,之前 Jett 在进入公司之前好像没有做过前端,但是在项目初期好像做了一些前端方面的工作,在邮件里面得到了领导的赞扬。这个应该是我对 Jett 的第一印象了,那就是一个靠谱的开发人员。当时虽然是成立了项目组,但是还是作为一个试点的工作来做,无论是算法的调研和平台的工作,都由我们两个来完成。这些项目在初期都是一大堆人在里面,但是随着项目的进展,人数都会越来越少,然后领奖的时候又出现了一大堆人。在项目的初期,我当时应该也只会 SQL,连 Python 都不算很熟悉,更没有开发过大型项目了。即使是作为一个试点的项目,其实个人也有着巨大的压力,毕竟这个方向在公司当年还处于一个相对不那么清晰的状态,也不知道该怎么做,甚至也不知道有什么资料可以查。不过作为一个 PHD,虽然写代码的能力不行,但是读论文和搜索资料的能力还是有点的。当时记得花了很多时间在网上找来找去,总算找到一两家号称做这个方向的创业公司,运气够好的是当时它们居然都发表了相关的论文。后来把它们的论文整理成资料和PPT,跟相关的同事沟通了一下,就打算复现这几篇论文。

屏幕快照 2019-08-10 下午10.01.49

当然,做项目总是有着各种各样的风险,况且当年本人的技术实力确实也不怎么样,写过不少的 SQL,做过很多数据分析的工作,查过一些数据方面的问题,至于其他方面也就那么回事。在项目的调研阶段和初期,大约是5月份-8月份,其实也没有什么特别大的产出,主要也是在积攒技术经验,把 Python 的各个工具库熟悉了一下。不过在公司里面总是有考核的,到了9月份的时候压力就比较大了,毕竟最终还是要对上线的效果负责的。在9月底的时候,我和 Jett 被拉去星巴克喝了一杯咖啡,然后被下达了任务和命令,也就是在十月份完成机器学习的效果指标。

屏幕快照 2019-08-10 下午9.59.46

既然被拉到星巴克去喝咖啡,也就是说明在9月份的时候,模型的效果都不算太好,估计再这样干下去也没有办法完成既定的目标。不过目标这种事情制定的时候都是根据当时的情况来制定的,很有可能会随着时间的变化而产生变化。虽然说目标总是在发生变化,但是整体的大思路是没有改变的。当时,作为开发人员的 Jett 问我要不要修改 XGBoost 的模型源码,我连忙说不用不用,其实就算让我改,我也没有本事修改别人的源码。既然不会修改模型的源码,那就只能够从数据和特征来入手了。在机器学习领域,只要把数据和特征处理好了,基本上就能够保证模型的效果和质量。于是 Jett 和我当时把成千上万条数据一起看了一遍,结果是发现正负样本有一部分混在了一起,于是模型的效果无论如何都做不好。

屏幕快照 2019-08-10 下午10.05.45
XGBoost 的 Github 主页

对于在校学生而言,通常来说都是 Python 跑完模型,然后得到一个模型文件,用它继续离线预测就可以得到最终的结果。但是在工业界,很多机器学习项目都需要进行上线的工作。这种时候只靠一个机器学习人员的战斗力是无法解决问题的,不可避免地需要有开发人力的介入。此时 Jett 发挥了作为一位开发人员的强大战斗力,一个人就能把线上的代码全部完成,没有让我撰写任何一行 C++ 的代码。在码农界有一种“结伴编程”的说法,也就是两个人共同搞一份代码,共同搞一个项目。我是负责数据处理和离线模块,Jett 是负责平台开发。有一次在核对数据的时候,把 Python 的预测结果和 C++ 的预测结果进行核对。也就是为了交流方便,那次我把 Mac Air 搬到了 Jett 的桌子上,两个人并排坐在一起,一起核对数据的准确性和可靠性。

不过核对数据只是机器学习项目的第一步,并且也是长期需要做的一步,因为数据总是会出现各种各样的问题。即使数据没有问题,也不代表最终的模型效果达标。到了2016年10月中旬的时候,我俩的压力也已经很大,每天晚上都在万利达五楼加班到十点以后。每天我都在训练模型和数据分析,Jett 每天也在做平台开发的工作,虽然我不懂他在做什么,但是总是感觉很忙的样子。而且项目经理每两天都会催一次进度,顺带着会有各种大大小小的会议。其实当时 Jett 是作为业务部门的人,压力更大的是压在他那一边。在思考了大半个月之后,在一个星期日的夜晚,我去华润万家买了一堆小本子,把整个项目的细节仔仔细细地思考了一遍,突然灵光一现,发现其实有一个优化点,于是就顺手写在了小本子上。到了周一的时候,我把小本子上面的想法去实现了一遍,结果效果瞬间提升,业务指标瞬间完成。当我把这个好消息告诉 Jett 的时候,Jett 还在 RTX 上说了一句:“等我去哭一会”。最终我俩猛加班两天,把模型往线上一扔,效果直线上升,而此刻的报表系统早已齐备,瞬间就看到了效果的提升,甩掉前面的模型五条大马路。

6EC4948295154B525FD67EAC9B309320.jpg
当年撰写思路的小本子

在2017年初的时候,模型的整体效果已经很好了,整体的路线其实已经基本走通。因此后续更多的是平台建设方面的工作,这一块做得更多一点的是 Jett,最终他还真是完成了无算法人员参与就能够自动接入各种业务的全自动流程。不过随着时间的流逝,我俩都各自都被抽调去做其它的项目,合作的时间和机会在项目成功之后就变得越来越少了。万幸的是,在2017年9月5日-2017年9月9日,我俩共同去了台湾进行了一次团建。参见《五日台湾行》。

640

640-2
2017年的台湾

后来,由于种种原因,我也不再继续从事安全方面的工作,与 Jett 的交集也越来越少。虽然后面也有吃饭聚餐等时候,但是却没有了在一个项目中一起为了一个目标奋斗的机会,心中不免有少许遗憾。随着去年的大调整,Jett 和我已经不在同一个部门。今年 Jett 由于家庭原因离开了公司,恐怕短期内已经再也没有通力协作,互帮互助的机会了。也许这个项目是我俩共同做的最后一个项目,但是当年在万利达五楼共同奋斗的时光,却是一段珍贵的回忆。