在时间序列异常检测中，通常有一个较为常见的场景就是“节假日效应”。所谓节假日效应，指的就是在节假日的时候，其时间序列的走势跟日常有着明显的差异性，但是又属于正常的情况。从国内 2020 年的节假日安排可以看出，一年中有好几个关键的假日：

1. 元旦：1 天；
2. 春节：7 天；
3. 清明节：3 天；
4. 五一劳动节：5 天；
5. 端午节：3 天；
6. 国庆节：8 天。

在这些节假日的时候，为了调休，自然也会带来工作日上的调整。例如：在 2020 年 1 月 19 日，2020 年 2 月 1 日是需要上班的（虽然今年受疫情影响最终也没上班）。因此，在这些节假日进行调整和变化的时候，各种各样的业务指标（时间序列）通常也会发生变化，变得跟以往的走势不太一致。因此，如何解决节假日效应的时间序列异常检测就是业务上所面临的问题之一。

清华大学的 Netman 实验室在 2019 年发表了一篇论文，专门用于解决时间序列异常检测中的节假日效应问题，论文的标题是《Automatic and Generic Periodic Adaptation for KPI Anomaly Detection》。在本文中，所用的时间序列是关于各种各样的业务指标的，包括搜索引擎，网上的应用商店，社交网络数据等等。作者们针对 KPI（Key Performance Indicator）做了时间序列异常检测，并且发明了一种方法来避免节假日效应的问题。论文针对时间序列的工作日（work days），休息日（off days），节假日（festival）做了必要的区分，然后将时间序列的不同时间段进行合理地拆分和组装，再进行时间序列异常检测，从而在一定的程度上解决节假日效应问题。

在实际的案例中，我们可以看到，同一条时间序列的走势在工作日（work day），休息日（off day），春节（Spring Festival）明显是不一样的。因此，根据工作日的时间序列走势来预测春节的走势明显是不太合理的；同理，根据春节的走势来预测休息日的走势也会带来一定的偏差的。那么如何解决节假日效应的问题就成为了本篇论文的关键之一。

在上图中，我们可以看到论文中使用的数据都具有某种周期性（Periodicity）。KPI A，B，C 都是具有明显具有工作日和周末特点的，在工作日和周末分别有着不同的形状；KPI D 则是关于网上应用商店周五促销的，因此在周五周六的时候，其实时间序列会出现一个尖峰（peak）；KPI E 的话则是每隔 7 天，会有两个尖刺，然后并且迅速恢复；KPI F 的话则是可以看出时间序列在十一的走势跟其余的时间点明显有区别。除此之外，对于一些做旅游，电商等行业的公司，其节假日效应会更加突出一点，而且不同的业务在节假日的表现其实也是不一样的。有的时间序列在节假日当天可能会上涨（电商销售额），有的时间序列在节假日当天反而会下降（订车票，飞机票的订单量）。因此，在对这些时间序列做异常检测的同时，如何避免其节假日效应就是一个关键的问题了。

而在实际处理的时候，通常也会遇到几个常见的问题；

1. 周期性的多样性：通过实际案例可以看出，对于不同的时间序列，其周期是完全不一样的，而且在不同的周期上也有着完全不同的表现；
2. KPI 数量巨大：这个通常来说都是智能运维领域中的常见问题；
3. 周期的漂移：一般来说，通过时间序列的走势我们只能够看出一个大致的变化，但是具体到细节的话，周期是存在一定的波动的。例如不一定恰好是 7 天，有可能是 7 天加减 5 分钟之类的周期。这个跟业务的具体场景有关系，也跟当时的实际情况有关。

于是，基于这些挑战，作者们希望提出一个健壮的机器学习算法来解决这个问题，本文的系统被作者们称之为 Period，正好也象征着解决节假日效应这个寓意。

从论文中可以看出 Period 的整体架构如上图所示，包括两个部分：

1. 离线周期性检测（offline periodicity detection）；
2. 在线适应性异常检测（online anomaly detection adaptation）。

在第一部分，每一条时间序列都会被按天切分成很多子序列（subsequence），然后将其聚集起来，把相似的时间序列放在一类，不相似的放在另外一类；在第二部分，新来的时间序列会根据其具体的日期，分入相应的聚类，然后用该类的时间序列异常检测方法来进行异常检测。

从上图可以看到 Period 的核心思路（core idea）。在本文使用的数据中，时间序列的长度较长，一般来说都是好几个月到半年不等，甚至更长的时间。对于一条时间序列（a given KPI），可以将它的历史数据（historical data）进行按天切分，获得多个子序列（sub KPIs）。对于这多个子序列，需要进行聚类以得到不同类别。或者按照日历直接把时间序列的工作日（work day），休息日（off day），春节（spring festival）序列进行切分，将工作日放在一起，休息日放在一起，春节放在一起。把这些子序列进行拼接就可以得到三条时间序列数据，分别是原时间序列的工作日序列（work day subsequence），休息日序列（off day subsequence），春节序列（spring festival subsequence）。然后分别对着三条时间序列训练一个异常检测的模型（例如 Holt-Winters 算法，简写为 HW）。对于新来的时间序列，可以根据当日具体的日期（工作日，休息日或者春节）放入相应的模型进行异常检测，从而进一步地得到最终的结果。

在离线周期性检测的技术方案里面，是需要对时间序列进行周期性检测（Periodicity Detection）。而周期性检测有多个方案可以选择。第一种就是周期图方法（Periodogram），另外一种就是自相关函数（Auto-correlation function）。但是在这个场景下，用这些方法就不太合适了。作者们提出了别的解决方案。

在本文中，作者们提出了一种 Shape-based distance（SBD）的方法，针对两条时间序列 和 ，提出了相似性的计算方法。

令

其中 的个数都是 进一步可以定义，当 时，

于是，选择令 归一化之后的最大值作为 的相似度，i.e.

而基于 SBD 的距离公式则可以定义为：

那么为什么需要考虑一个漂移量 呢，因为在一些实际的情况下，时间序列是会存在漂移的，例如上图所示。该时间序列在 10 月 30 日，31 日，11 月 1 日 都出现了一个凸起，但是如果考虑它的同比图，其实是可以清楚地看出该时间序列就存在了漂移，也就是说并不是在一个固定的时间戳就会出现同样的凸起，而是间隔了一段时间。这就是为什么需要考虑 的由来。

通过相似性和距离的衡量工具，我们可以将时间序列进行聚类，然后通过上述算法也可以对每一个聚类的结果进行命名。

在本文中，针对以上六条时间序列，作者们做了详细的分析，也对其余的 50 条时间序列进行了实验。其使用的方法包括 HW，TSD，Diff，MA，EWMA，Donut。在 HW 中，针对不同的日期使用了不同的方法，例如 HW-day，HW-week，HW-period；其余的方法也是针对不同的日期来做的。

从实验效果来看，Period 方法的话相对于其他方法有一定的优势。

结论：Period 方法包括两个部分，第一部分是离线周期性检测，第二部分是在线适应性异常检测。通过这样的方法，可以有效地减缓时间序列异常检测受节假日效应的影响。除此之外，想必未来也会有其余学者提出相应的问题和解决方案，敬请期待。

在运维领域，服务侧的异常会由多方面的原因造成，有的时候是因为网络的抖动，有的时候是因为机器的故障，有的时候甚至是因为人为的变更。本篇博客会介绍一种机器异常定位的方法，论文是来自于清华 Netman 实验室的《FluxRank：A Widely-Deployable Framework to Automatically Localizting Root Cause Machines for Software Service Failure Mitigation》。本篇论文主要介绍了如何从服务的故障定位到局部异常的机器，也就是说在发现服务故障的同时，进一步推断出是由哪些机器出现问题而导致的。

通常来说，在服务异常（例如服务的耗时长，失败数上涨）的时候，需要运维人员通过历史上的经验迅速定位到是哪个业务，哪个模块，甚至哪台服务器出现了故障。而人工定位的速度总是会出现瓶颈的，无论对模块的判断，还是机器的判断，都依赖于人工所积累的经验。而每个人的经验却各不相同，并且经验的传承也需要一定的时间成本。那么如何基于人工运维的经验来构建模型，进一步地提升异常定位的速度就是智能运维的关键之处之一。

对于一条业务指标（时间序列）而言，大多数情况下是处于正常的状态（normal）。但是如果出现了错误的变更，发布了错误的程序，或者服务器突然出现了故障，都会导致业务指标出现变化，就从正常（normal）变成异常（abnormal）。这个时候就会出现一个故障的开始时间，也就是 failure start time ，这个时间戳是运维领域非常重要的时间戳，它由异常检测（anomaly detection）产生，无论在告警收敛（alarm convergence）还是根因分析（root cause analysis）都非常依赖这个时间戳。而另外一个时间戳虽然没有故障开始时间那么重要，但是也有着其实用价值，那就是缓和开始时间（mitigation start time），它表示故障虽然还没有恢复，但是出于稍微平稳的走势，并没有持续恶化。在出现了故障之后，通常都会发送相应的告警给运维人员，那么在发送告警的时候，如果将异常定位的结果随之带出，则会大大减少运维人员排障的时间。在故障缓和的时间内，运维人员通常需要进行必要的操作来排查故障，例如切换流量（switch Traffic），回滚版本（Rollback Version），重启实例（Restart Instances），下线机器等操作。除此之外，为了定位问题（Root Cause Analysis），运维人员需要分析源码（Code Analysis），查看日志（Log Analysis）等一系列操作。如果能够将这一系列操作融入相应的机器学习模块中，将会节省运维人员大量的排障时间。

贝叶斯网络

通常来说，故障定位也称为根因分析或者根源分析（Root Cause Analysis），都是为了排查产生这次故障的原因。在机器学习领域，为了进行因果分析（Causal Analysis），则需要使用相应的模型来进行建模。其中较为经典的统计分析方法则是贝叶斯分析法，其中的贝叶斯网络（Bayesian Network）则是经典模型之一。下面来看一个简单的例子。

假设降雨（Rain）的概率是 0.2，不降雨的概率是 0.8；而洒水器（Sprinkler）是否开启会受到降雨的影响，其条件概率与下图所示。而降雨或者洒水器都会导致草湿润（Grass Wet），其概率分布如下图所示。那么可以问如下问题：

1. 如果草已经湿润，求降雨的概率是多少？
2. 如果草已经湿润，求没有降雨且洒水器开启的概率是多少？

而这一类的问题可以通过贝叶斯公式来进行解答。从表格来看：

从 Rain 的表格可得：。

从 Rain 和 Sprinkler 的表格可得：， 。

从 Grass Wet 和 Sprinkler，Rain 的表格可得：，，，

针对问题 1，需要计算条件概率 。从 Bayes 公式可以得到：。分别计算分子分母即可：

，

那么如果草已经湿润，求降雨的概率是

另外一个题目可以用类似的方法进行求解，在此不再赘述。

虽然贝叶斯算法能够计算出条件概率，例如本次故障是由哪些原因导致的，但是这个需要长期收集数据，需要对历史数据进行积累，才能通过人工或者统计的方法得到以上表格的条件概率。但是在实际的环境中是较难获取这些数据的，需要大数据平台的支持，因此需要探索其他的解决方案。

FluxRank

在本论文中，为了克服贝叶斯网络模型中的一些问题，针对子机异常定位的场景，设计了一套技术方案，作者们称之为 FluxRank。

FluxRank 这一模块的触发需要服务指标（Service KPI）的异常，因此需要对服务指标（Service KPI）进行异常检测。这里的服务指标通常指的是业务指标，包括某块 APP 的在线人数，某个接口的成功率，某个视频网站的卡顿数等指标。当服务指标出现了异常的时候，就启动 FluxRank 模块进行异常机器定位。

如果按照人工处理的流程来看，分成几个步骤：

1. 异常检测部分：通过设定阈值或者某个简单的规则来进行异常检测，包括服务的 KPI（Service KPI）和机器的 KPI（machine KPIs）；
2. 手工检查异常的时间段，并且查看在异常的时间段内发生了什么情况；
3. 运维人员根据自身的业务经验来对机器的故障程度做人工排序；
4. 运维人员根据自身的业务经验来对故障进行处理，并且人工给出处理方案。

那么 FluxRank 所面临的挑战就有以下几点：

1. 如何衡量海量 KPIs 的变化程度？在这里不仅有服务的 KPIs，还有机器的 KPIs。而机器的 KPIs 包括内存，硬盘，IO，CPU等诸多固定的指标，那么如何对这些海量的 KPI 曲线进行变化程度的衡量，为后续的指标排序做准备就成为了一个难点；
2. 如何对 KPIs 进行异常性或者重要性的聚类，让运维人员能够一眼看出每个聚簇的差异或者异常程度？
3. 如何对 KPIs 聚类的结果进行排序？

为了解决以上的问题，FluxRank 的框架有以下几个贡献点：

1. 基于 Kenel Density Estimation 用于衡量海量 KPIs 在某一个时间段的变化程度和异常程度；
2. 基于上一步生成的异常程度，对诸多机器所形成的特征使用距离公式或者相似度公式，然后使用 DBSCAN 聚类算法来对机器进行聚类；
3. 在排序部分，对上一步的机器聚类结果进行排序；

Change Quantification

首先，来看一下 Change Quantification 是怎么样做出来的。这里的 Change Quantification 使用与衡量机器 KPIs 的变化程度，称之为 change degree。Change degree 可以用于 CPU，内存，IO 等诸多机器指标。为了达到衡量变化程度，需要一个非常重要的信息，那就是变化的开始时间，change start time，也就是说在哪个时刻时间序列开始出现了变化。于是在 Change Quantification 部分，就分成两部分：（1）用 absolute derivative 或者 CUSUM 算法获得变化开始时间（change start time）；（2）用 Kernel Density Estimation（KDE）来计算变化程度（change degree）。

正如上图所示，针对服务 KPIs（ervice KPIs），存在两个关键的时间点，那就是失败开始时间（Failure Start Time） 和缓和开始时间（Mitigation Start Time）。在失败开始时间 之前，可能有的机器已经出现了故障，因此变化开始时间（Change Start Time） 小于或者等于 。通常情况下，一个或者多个机器故障会在半小时（30 mins）甚至更短的时间内引发服务故障，因此，只需要假设 即可。关键时间点的排序为 。

对于服务 KPIs 的异常检测，FluxRank 中提到了两种方法：分别是 absolute derivative 和 CUSUM 方法。

1. absolute derivative 方法：个人理解就是对时间序列进行一阶差分操作，然后对一阶差分来做时间序列异常检测，例如 3-sigma 等方法，一旦有明显的变化，就说明当前的时间点出现了突增或者突降；与该方法比较类似的一种方法是：MAD（Median Absolute Deviation）。对于一条时间序列 而言，MAD 定义为 ，而每个点的异常程度可以定义为： 当 较大或者较小的时候，表示上涨或者下降的异常程度。通过设置相应的阈值，同样可以获得时间序列的异常开始时间。
2. CUSUM 算法也是用于时间序列异常检测的。对于一条时间序列 ，可以预估它的目标值（target value），通常可以用均值来估计，也需要计算出这条时间序列的标准差 。通常设定 ，。而 Tabular CUSUM 指的是迭代公式 ，，初始值是 。当累计偏差 或者 大于 的时候，表示 出现了异常，也就是 out of control。通过这个值，可以获得时间序列开始异常的时间。

从论文的描述来看，作者是使用 absolute derivative 来做异常检测的，并且定位其异常开始时间的准确率较高。

Change Degree

其次，我们来看一下变化程度（Change Degree）是怎么计算出来的，通过之前的计算，我们已经可以获得一些关键的时间戳，例如 等时间戳。根据变化开始时间（change start time），同样需要设置一个窗口值 ，例如 60 分钟（1 小时）。可以从两个时间段获取数据，正常时间段 ，异常时间段 ，分别获取到数据 和 ，前者是在变化开始时间之前的数据点，后者是在变化开始之后的数据点。于是，作者们通过概率值来计算变化程度 ，意思就是计算一个条件概率，在观察到 之后，得到 的概率值。

为了计算以上概率值，需要简化模型，因此这里需要假设 是独立同分布（iid）的，于是 ，在这里 表示集合 的元素个数。 为了分别得到其上涨和下降到概率，则需要计算：

,

,

其中 表示上涨的程度， 表示下降的程度。如果不想处理连乘的话，则需要处理连加：

,

.

在这里，作者们使用了三种概率分布函数，分别是 Beta 分布（Beta distribution），泊松分布（Poisson distribution），高斯分布（Gaussian distribution）。

Beta 分布的概率密度函数（probabilisty density function）是 ，其中 。在机器 KPIs 中，CPU 等指标可以用 Beta 分布；

泊松分布的概率密度函数是 ，在机器 KPIs 中，SYS_OOM 用于衡量超出内存的频率，可以用泊松分布来做。

高斯分布的概率密度函数 。

根据论文中的陈述，机器 KPIs 分别适用于以下概率分布：

通过以上公式，可以计算出每一个机器的每一个指标的 和 两个值。

Digest Distillation

再来看一下 Digest Distillation 部分，在此部分需要对机器的 KPIs 进行聚类操作；那么就需要构造特征向量和距离函数，再加上聚类算法即可获得结果。

每一个机器的特征向量是由之前计算的 Change Degree 形成的，由于每台机器的 KPIs 都是一样的，因此可以对它们的 KPIs 的 change degree 进行排列。假设每台机器有 个 KPIs，那么这台机器所对应的向量就是 。

在描述向量的相似性方面，可以使用相关性的系数，包括 Pearson 系数，Kendall tau 系数，Spearman 系数。对于两条时间序列而言， 和 ，

Pearson 系数指的是： 其中 ，。

Kendall tau 系数指的是：如果 ( 且 ) 或者 ( 且 )，那么称之为 concordant；如果 ( 且 ) 或者 ( 且 )，称之为 discordant；如果 或者 ，则既不是 concordant，也不是 discordant。那么 Kendall tau 定义为

Spearman 系数指的是：通过原始序列变成秩次变量（rank）（从大到小降序排列即可）， 将会对应到 ，后者表示 在从大到小排序之后的序列 的位置，称之为秩次（rank），得到序列 。对原始序列 作同样的操作，得到 。一个相同的值在一列数据中必须有相同的秩次，那么在计算中采用的秩次就是数值在按从大到小排列时所在位置的平均值。如果没有相同的 rank，那么使用公式 进行计算，其中 ；如果存在相同的秩次，则对 和 来做 Pearson 系数即可，也就是 。

通过作者们的实验，说明 Pearson 系数在这个数据集上效果最佳。在聚类算法的场景下，作者们同样对比了 KMeans，Gaussian Mixture，Hierarchical Clustering，DBSCAN 算法的效果，最后使用了 DBSCAN 的聚类算法。每一个聚类的结果，作者称之为一个 digest，也就是下图的 M1，M2 等聚类结果。

Digest Ranking

最后，就是对聚类结果的排序工作。通过观察会发现：

1. 变化开始时间（change start time） 会在失败发生时间 之前；
2. 不同的故障机器 KPIs 的 change start time 是非常接近的；
3. 故障机器的一些 KPIs 的 change degree 是非常大的；
4. 故障机器的占比是与故障原因相关的，故障机器越多说明故障越大；

在同一个模块下，如果出现故障机器的占比较大，那么故障将集中于这个模块下，可以通过 ratio 这个指标进行排序工作。

实验数据

在 FluxRank 论文中，作者们收集了 70 个真实的案例，然后根据实验效果获得了结果。

在标记的时候，除了标记异常机器（Root Cause Machines，简称为 RCM）之外，也需要标记相关的指标（Relevant KPI，简称为 RK）。Root Cause Digest（简称为 RCD）把包括两个部分，不仅包括 RCM 的一个聚类结果，还包括聚类结果中的 top-five KPIs。

通过对 FluxRank 进行实验，可以得到如下实验数据：

其中 Recall@K 指的是： 或者

参考资料

1. FluxRank: A Widely-Deployable Framework to Automatically Localizing Root Cause Machines for Software Service Failure Mitigation，Ping Liu，Yu Chen，Xiaohui Nie，Jing Zhu，Shenglin Zhang，Kaixin Sui，Ming Zhang，Dan Pei，ISSRE 2019， Berlin, Germany, Oct 28-31, 2019。
2. Introduction to Statistical Quality Control，6th edition，Douglas C.Montgomery。
3. Bayesian Network：https://en.wikipedia.org/wiki/Bayesian_network

 

近期阅读了一篇论文《Rapid Deployment of Anomaly Detection Models for Large Number of Emerging KPI Streams》，这篇文章基于之前的 ROCKA 系统做了一些额外的工作。ROCKA 系统是用来做时间序列的实时聚类的，而这篇文章是在 ROCKA 系统的基础上增加了时间序列异常检测的功能。通常来说，时间序列异常检测可以使用有监督的方法来解决，参考 Opperentice 系统。而本篇文章使用了半监督学习的思路来解决异常检测的问题，下面来详细分析一下这篇文章的细节，本文的作者把这个系统称为 ADS（Anomaly Detection through Self-training）。

数据集的情况

在论文中，作者使用了两份数据集，分别是已经历史上的 70 条时间序列，另外还有新来的 81 条时间序列。在 ADS 系统中，历史上的 70 条时间序列被划分成 5 类，并且已经可以找出每个类的质心位置，并且每条历史上的时间序列通常来说会大于三个星期（3 weeks）。本篇论文的评价指标是 F-Score，也属于机器学习领域里面比较常用的衡量模型效果的指标。整体来看，这篇文章的数据集大约是 200 条时间序列，时间序列的时间间隔通常来说是五分钟（不过其余的运维场景会有一分钟的数据采集粒度），而一般来说都拥有大半年甚至一年的时间跨度。那么时间点的个数预估是 200 * (1440 / 5) * 365。假设异常的数据：正常的数据 = 1：10000（也就是说平均每条时间序列每周至少发生一次异常），于是这批时间序列数据的异常数据量大约是 200 * (1440 / 5) * 365 / 10000 = 2102，也就是说异常的样本大约是 2102 个左右，剩下的都是正常的样本。PS：当然如果异常的数据：正常的数据的比例大于 1：10000 的话，异常的样本还会更多一些。整体来看，时间序列异常检测是一个样本极其不均衡的场景。

ADS 的系统架构

按照作者之前论文的经验，时间序列异常检测通常都是先做聚类，然后再根据每一个类的特点来做一个异常检测模型，之前的技术架构就是 ROCKA + Opperentice。因为 ROCKA 可以根据时间序列的走势和趋势来进行时间序列的实时分类/聚类，然后 Opperentice 就是做时间序列异常检测的模型。在本文的场景下，作者把 70 条时间序列分成了5 类，因此只需要维护 5 个时间序列的异常检测模型就可以了。当然把时间序列切分成更多的类也是可以的，只是需要维护的时间序列异常检测就变多了，人工成本会加大。

如果看到上面两幅图，有心的读者一定会发现其实 ADS 就是基于 ROCKA 所做的工作。ADS 先对时间序列进行了分类，然后进行了特征提取的工作，再通过半监督学习模型，最后进行异常检测。也就是说，ADS 会走下面四个步骤：

1. ADS 先把历史上的时间序列进行聚类；
2. 通过算法获得每一个类的质心，并且标记出质心曲线的异常点和正常点；
3. 对新来的时间序列进行实时聚类，划分到合适的类别；
4. 基于新来的时间序列（没有标记）和历史上的时间序列（有标记）使用无监督算法来重新训练一个新的模型，进行该类别的时间序列异常检测。

ADS 的细节

对于时间序列的聚类框架 ROCKA，之前的一篇 BLOG 里面已经详细介绍过，这里将不会再赘述。而 ADS 的另一个模块就是半监督学习算法 Contrastive Pessimistic Likelihood Estimation（CPLE），详细的论文细节可以参考论文《Contrastive Pessimistic Likelihood Estimation for Semi-Supervised Classification》。CPLE 有几个好处：

1. CPLE 是半监督学习算法中比较健壮的，因为它并没有过多的假设条件，并且也符合这篇文章的业务场景，同时拥有质心曲线（有标记）和新来的曲线（无标记），使用半监督学习也是符合常理的。除了 CPLE，其实在实战过程中也可以多尝试其他的半监督模型，具体可以参考周志华的《机器学习》。
2. CPLE 的复杂度比较低，计算快。
3. CPLE 支持增量学习，因此，当越来越多新的时间序列进入 ADS，这个模型也会随之而调整并提高准确率。

整体来看，ADS = ROCKA + CPLE，而在论文中，它的对比模型就是 ROCKA + Opperentice。而且在 CPLE 中，也使用了与 Opperentice 系统类似的特征，如下图所示。

其实，从本质上来看，就是半监督学习与有监督学习在这份数据集合上面的比较。从这篇论文里面所展示的数据来看，CPLE 有一定的优势。

整体来看，本篇文章介绍了时间序列异常检测的一种方案，也就是把时间序列先进行聚类的操作，然后根据不同的类来进行异常检测。在异常检测的方法中，不仅可以使用 Random Forest，GBDT，XGBoost 等有监督学习方法，也可以使用 CPLE 等半监督算法。具体在业务中如何使用，其实只能够根据具体的数据来进行合理地选择了。

 

这次整理的就是清华大学裴丹教授所著的两篇与时间序列相关的论文。一篇是关于时间序列聚类的，《Robust and Rapid Clustering of KPIs for Large-Scale Anomaly Detection》；另外一篇文章是关于时间序列异常检测的，重点检测时间序列上下平移的，《Robust and Rapid Adaption for Concept Drift in Software System Anomaly Detection》。本文将会整理一下这两篇文章的关键技术点。

Robust and Rapid Clustering of KPIs for Large-Scale Anomaly Detection

在互联网公司中，通常会拥有海量的的时间序列，而海量的时间序列就有着各种各样的形状和走势。因此，就有学者提出可以先对时间序列进行分类，然后根据不同的类使用不同的检测模型来进行异常检测。如果要做时间序列的分类，就先需要做聚类的操作，无论从 KMeans，DBSCAN，还是层次聚类来说，都会消耗一定的运算时间。所以，如何在较短的时间内进行聚类或者分类的操作则是这个系统的关键之处。于是，这篇文章提出了一个将时间序列快速聚类的方法。

时间序列 -> 时间序列分类

-> 根据每一类时间序列使用不同的异常检测模型

而在做时间序列聚类的时候，也有着不少的挑战。通常挑战来自于以下几点：

1. 形状：通常来说，时间序列随着业务的变化，节假日效应，变更的发布，将会随着时间的迁移而造成形状的变化。
2. 噪声：无论是从数据采集的角度，还是系统处理的角度，甚至服务器的角度，都有可能给时间序列带来一定的噪声数据，而噪声是需要处理掉的。
3. 平移：在定时任务中，有可能由于系统或者人为的原因，时间序列的走势可能会出现一定程度的左右偏移，有可能每天 5:00 起的定时任务由于前序任务的原因而推迟了。
4. 振幅：通常时间序列都存在一条基线，而不同的时间序列有着不同的振幅，振幅决定了这条时间序列的振荡程度，而振幅或者基线其实也是会随着时间的迁移而变化的。

从整篇论文来看，ROCKA 系统是为了做实时的时间序列分类判断的。要想做成实时的分类判断，就需要有离线和在线两个模块。其中离线是为了做模型训练或者聚类的，在线是为了使用离线处理好的模块来做曲线分类的。

从整个系统来看，离线模块需要做以下几件事情：首先需要收集一批时间序列数据，也就是所谓的 Raw Time Series Data（Raw），通过预处理模块，实施基线提取，再进行聚类的操作，获得相应的聚类结果和质心。在线模块同样也要做类似的事情：首先对于每一条新来的时间序列数据，也就是所谓的 New Time Series Data（Raw），通过预处理模块，实施基线提取，然后使用已经聚类好的离线模块来进行实时的分类。

下面，我们来逐一分析每个模块的作用。

预处理模块（Preprocessing）

通常预处理模块包含几个关键点：

1. 缺失值：缺失值指的是在该上报数据的时间戳上并没有相应的数据上报，数据处于缺失的状态。通常的办法就是把数据补齐，而数据补齐的方法有很多种，最简单的就是使用线性插值（Linear Interpolation）的方式来补齐。
2. 标准化：对于一个时间序列而言，有可能它的均值是10万，有可能只有10，但是它们的走势有可能都是一样的。所以在这个时候需要进行归一化的操作。最常见的有两种归一化方法：一种是标准化，另外一种是最大最小值归一化。如果 表示原始的时间序列的话，标准化指的是 ，其中 和 分别表示均值和标准差。最大最小值归一化指的是 ，其中 分别表示这段时间内的最大值与最小值。

基线提取模块（Baseline Extraction）

基线提取指的是把时间序列分成基线和剩余项两个部分，假设时间序列是 ，基线提取就是：

其中 分别指的是 的基线和剩余项。

在处理基线的时候，有几件事情需要注意：

1. 异常值的处理：通常需要移除一些明显异常的值，然后使用线性插值等方法来把这些移除的值补上。
2. 使用简单的移动平均算法加上一个窗口值 来提取基线。假设时间序列是 ，，。也就是说 。
3. 提取基线的方式其实还有很多，使用带权重的移动平均算法（Weighted Moving Average），指数移动平均算法（Exponentially Weighted Moving Average）都可以提取基线，甚至使用深度学习中的 Autoencoder 或者 VAE 算法都能够提取基线。

基于密度的聚类算法（Clustering）

使用预处理和基线提取技术之后，可以得到原始时间序列的基线值，然后根据这些基线值来进行时间序列的聚类操作。一般来说，时间序列的聚类有两种方法：

1. 通过特征工程的方法，从时间序列中提取出必要的时间序列特征，然后使用 KMeans 等算法来进行聚类。
2. 通过相似度计算工具，对比两条时间序列之间的相似度，相似的聚成一类，不相似的就分成两类。

对于第一种方法而言，最重要的就是特征工程；对于第二种方法而言，最重要的是相似度函数的选择。在这篇文章中，作者选择了第二种方法来进行时间序列的聚类。对于两条时间序列 和 而言，为了解决左右平移的问题，需要考虑一个偏移量 ，然后计算它们之间的内积。

通过这个偏移量 就可以计算出最大的相似度，然后计算出两条时间序列之间的距离。i.e.

其中 指的是 Normalized version of Cross-Correlation， 指的是 Shape-based distance。

而聚类的另一个重要指标就是质心的选择，在这里，每个类的质心可以设置为：

实时分类（Assignment）

对于一条新的时间序列（Raw Data），同样需要经过预处理，基线提取等步骤，然后计算它与之前每一个质心的距离。然后进行距离的从小到大排序，最小的那一类可能就是所需要的。当然，当最小距离大于某个 threshold ，就说明这条新的时间序列曲线很可能不属于之前的任何一类。通过人工查看之后，可以考虑新增一类，并且更新之前所做的聚类模型。

聚类与时间序列异常检测

如果要做海量的时间序列异常检测的话，通常有以下两种做法。

1. 先对时间序列进行聚类或者分类，针对不同的时间序列类型来使用不同的模型；
2. 在时间序列异常检测中加入分类特征。

对于第一种方法而言，需要针对不同形状的时间序列维护不同的模型，而且如果第一层的聚类/分类错误了，那么使用的模型也会出现错误。对于第二种方法而言，关键在于样本的积累和分类特征的构建。

Robust and Rapid Adaption for Concept Drift in Software System Anomaly Detection

这篇文章是关于时间序列异常检测的，而清华大学的 Netman 实验室做时间序列异常检测的相关工作比较多。从 2015 年开始的 Opperentice（Random Forest 模型），Funnel（SST 模型，变更相关），到后来的 Donut（VAE 模型），都是时间序列异常检测的相关文章。而这篇问题提到的 StepWise 系统针对的场景是关于指标的迁移的，所谓概念漂移（Concept Drift）指的就是时间序列会随着变更，发布，调度或者其他事件的发生而导致上下漂移或者左右漂移。一个比较典型的例子就是关于网络流量的漂移，通常来说在某个特点的时间点，时间序列会出现猛跌或者猛涨的情况，但是下跌或者上涨之后的走势和历史数据是及其相似的，只是绝对值上有所变化。

正如上图所示，在时间戳 08-02 附近，时间序列出现了一个下跌的情况。但是根据历史数据所计算出来的上界（Upper Bound）和下界（Lower Bound）却会把未来一段时间的序列都判断为异常。但是前后的曲线走势却是一样的，其实只有下跌的那一小段时间应该被判断为异常，其他时间都是正常的。基于以上的业务场景，这篇文章的作者就提出了概念漂移（Concept Drift）的一些方法。

在整个 StepWise 系统背后，有两个比较关键的地方。其中第一个关键之处就是如何判断异常点。在这个业务场景下，需要检测的是上图发生暴跌的点。而暴跌或者暴涨只是业务运维用来描述时间序列的一个词语。在统计学领域，这种点通常称为变点（Change Point）。所以概念漂移的检测可以转化为一个变点检测的问题，正是论文里面写的。

Insight 1：Concept drift detection can be converted into a spike detection problem in the change score stream.

如果是进行变点检测的话，其实可以参考 2016 年的论文 Funnel：Assessing Software Changes in Web-based Services。里面使用了 Singular Spectrum Transform 来进行检测，并且使用 Difference in Difference 来判断时间序列是否真正出现了异常。关于 SST（Singular Spectrum Transform）的具体细节可以参考 Yasser Mohammad, Toyoaki Nishida 所撰写的 Robust Singular Spectrum Transform。SST 算法是基于 SVD 算法的，有一定的时间复杂度。而基于 SST 又有学者提出了 Robust SST，具体可以详见论文。而 StepWise 的其中两步就是 Detection 和 Classification，其中的 Detection 使用了 Improved SST，Classification 使用了Difference in Difference。而 Funnel 系统的其中两步也是 Improved SST 和 Difference in Difference，这与 Funnel 有异曲同工之妙，Funnel 系统详情请见下图。

而突变前后的时间序列可以分别叫做 Old Concept 和 New Concept，由于前后的走势几乎一致，所以本文的第二个关键点就是相似度的判断。

Insight 2：The relationship between new concept and old concept can be almost perfectly fitted by linear regression.

从数学的角度来讲，Insight 2 的陈述是想判断两条时间序列是否相似。假设 和 ，那么以下陈述是等价的。

1. 存在一个线性关系 使得二维点集 能够被很好的拟合好，也就是说此刻的方差较小。
2. 与 的 Pearson 系数很高；
3. 与 标准化（z-score）之后的曲线几乎一致。
4. 分别存在两个值 使得 与 几乎一致。

所以，在 StepWise 中，作者通过线性回归的算法来判断 old concept 与 new concept 是否存在线性关系，也就是说这两者是否只是平移的关系。其实也可以尝试上面所说的其余方法。

整体来看，StepWise 大致分成两个关键步骤。首先使用类似 Funnel 系统的思想，先进行异常检测（SST），再使用判断一下是不是因为软件的变更引起的（DID），最后使用一层过滤逻辑（线性拟合）来判断是否出现了概念漂移的情况。在实际使用过程中，无论是异常检测还是过滤逻辑，都需要根据具体的业务来做，很难找到一个固定的模型来解决所有的难题。

 

随着深度学习的发展，word2vec 等技术的兴起，无论是 NLP 中的词语，句子还是段落，都有着各种各样的嵌入形式，也就是把词语，句子，段落等内容转换成一个欧氏空间中的向量。然后使用机器学习的方法来进行文本的聚类和相似度的提取，甚至进行情感分类等操作。那么在表示学习（Representation Learning）方向上，除了刚刚提到的自然语言之外，语音，图像，甚至图论中的Graph都可以进行嵌入的操作，于是就有了各种各样的表示算法。既然提到了表示学习，或者特征提取的方法，而且在标注较少的情况下，各种无监督的特征提取算法就有着自己的用武之地。除了 NLP 中的 word2vec 之外，自编码器（Auto Encoder）也是一种无监督的数据压缩算法，或者说特征提取算法。本文将会从自编码器的基础内容出发，在时间序列的业务场景下，逐步展开基于自编码器的时间序列表示方法，并且最终如何应用与时间序列异常检测上。

自编码器

提到自编码器（Auto Encoder），其实它就是一种数据压缩算法或者特征提取算法。自编码器包含两个部分，分别是编码层（encoder）和解码层（decoder），分别可以使用 和 来表示，也就是说：

其目标函数就是为了拟合一个恒等函数。对于最简单的情况，可以令 ，并且编码器和解码器都是前馈神经网络，也就是说：

损失函数就是 其中 和 分别是编码层和解码层的激活函数， 和 分别是编码层和解码层的矩阵和相应的向量。具体来说它们的矩阵大小分别是

对于自编码器而言，它的输入层的维度等于输出层的维度，隐藏层的维度是需要小于输入层的维度的。只有这样，自编码器才可以学习到数据分布的最显著特征。如果隐藏层的维度大于或者等于输入层的维度，其实是没有任何意义的，具体的解释可以参考下面这个Claim。

Claim. 对于自编码器而言，其中隐藏层的维度 一定是要小于输入层的维度 的。

Proof. 如果 ，那么令 就可以得到一个自编码器，而这个自编码器对于提取特征没有任何的意义。同理，当 时， 是一个 矩阵， 是一个 矩阵。从线性代数的角度来看，有无数个矩阵 满足 。这种情况下对于提取特征也是没有意义的。而当 时，其实无法找到矩阵 使得 如果存在 那么

这就导致了矛盾。因此，只有在 的情况下提取特征才是有意义的。

对于自编码器而言，其本质上也是一个神经网络，那么它的激活函数其实不仅可以选择 sigmoid, 还可以使用 tanh，ReLU，LeakyReLU 等其余激活函数，其本质上都是为了拟合一个恒等变换，中间层则作为一个特征提取的工具。在训练的时候，同样是使用反向传播算法，可以使用不同的优化函数，例如 SGD，Momentum，AdaGrad，RMSProp，Adam 等。

在图像领域，有学者尝试使用自编码器来进行图像的重构工作，图像的特征提取等内容，整体来看也能达到不错的效果，请看下图：

从上图来看，基于均方误差的自编码器是无法重构出乒乓球的。由于该自编码器的容量有限，目标函数是均方误差，因此自编码器并没有意识到乒乓球是图片中的一个重要物品。

 

时间序列异常检测：

时间序列异常检测一直是学术界和工业界都关注的问题，无论使用传统的 Holt-Winters，ARIMA，还是有监督算法进行异常检测，都是统计学和传统机器学习的范畴。那么随着深度学习的兴起，是否存在某种深度学习算法来进行异常检测呢？其实是存在的。请看上图，左边一幅图有一个白色的小乒乓球，但是随着自编码器进行重构了之后，白色的小乒乓球已经在重构的图像中消失了。那么根据异常检测的观点来看，小乒乓球其实就可以作为图片中的异常点。只要在图片的局部，重构出来的图片和之前的图片存在着巨大的误差，那么原始图片上的点就有理由认为是异常点。

在这个思想下，针对时间序列异常检测而言，异常对于正常来说其实是少数。如果我们使用自编码器重构出来的时间序列跟之前有所差异的话，其实我们就有理由认为当前的时间序列存在了异常。其实，简单来看，基于自编码器的时间序列异常检测算法就是这样的：

原始时间序列

-> Auto Encoder（Encoder 和 Decoder）

-> 重构后的时间序列

-> 通过重构后的时间序列与原始时间序列的整体误差和局部误差来判断异常点

简单来说，只要输出的时间序列在局部的信息跟原始的时间序列不太一致，就有理由认为原始的时间序列存在着异常。

那么，首先我们需要提取时间序列中的一些子序列，例如我们可以提取今天（today），昨天（yesterday），一周前（week）的数据，基于同样的时间戳把它们重叠在一起，也就是下图这个形式。其中，蓝线表示一周前的数据，黑线表示昨天的数据，红色表示今天的数据。

基于一条很长的时间序列，我们可以提取它的很多子序列，从而构造出很多的片段序列。这些片段序列就可以形成自编码器的输入数据，而自编码器是模拟一个恒等变换，因此它会把有异常的点尽量磨平，而正常的点则保持原样。所以，通过大量子片段来进行训练数据的输入，自编码器就能够得到一个较为合理的权重。得到了一个训练好的自编码器之后，对于任何一个子片段，都可以重构出一个新的片段。例如上面的子片段就可以重构成下图：对于今天的数据（today），那个凸起被直接抹平；对于昨天的数据（yesterday）而言，那个凹下去的部分也被磨平。基于时间序列重构前和重构后的数据差异，可以获得时间序列的异常点。

除此之外，还有很多时间序列的异常点可以被自编码器（AutoEncoder）发现，例如下面四幅图，无论是上涨，还是下跌，其实都可以被自编码器（AutoEncoder）发现异常。

总结

通常来说，在时间序列异常检测场景中，异常的比例相对于正常的比例而言都是非常稀少的。因此，除了有监督算法（分类，回归）之外，基于无监督算法的异常检测算法也是必不可少的。除了 HoltWinters，ARIMA 等算法之外，本文尝试了一种新的异常检测算法，基于深度学习模型，利用自编码器的重构误差和局部误差，针对时间序列的异常检测的场景，初步达到了一个还不错的效果。这种方法可以用来提供部分异常样本，加大异常检测召回率的作用。但是这种方法也有一定的弊端：

1. 从理论上说，它只能对一个时间序列单独训练一个模型，不同类型的时间序列需要使用不同的模型。这样的话，其实维护模型的成本比较高，不太适用于大规模的时间序列异常检测场景；
2. 对周期型的曲线效果比较好，如果是毛刺型的数据，有可能就不太适用；因为长期的毛刺型数据就可以看成正常的数据了。
3. 每次调参需要人为设置一定的阈值，不同的时间序列所需要的阈值是不一样的。

参考文献

1. Unsupervised Anomaly Detection via Variational Auto-Encoder for Seasonal KPIs in Web Applications, Haowen XU, etc., 2018
2. Deep Learning, Ian Goodfellow, etc., 2016
3. https://zr9558.com/2016/06/12/replicator-neural-networks/

 

黑盒函数的定义

在工程上和实际场景中，黑盒函数（black box function）指的是只知道输入和输出对应关系，而不知道它的内部结构，同时也不能写出具体表达式的一类函数。正如下图所示，每次给定一组输入，通过黑盒函数的计算，都能够得到一组输出的值，但是却无法写出 Black box 函数的精确表达式。

与之相反的是函数或者系统称之为白盒函数（open system），它不仅能够根据具体的输入获得相应的输出，还能够知道该函数的具体表达式和细节描述。例如 和 等都是白盒函数。

黑盒函数的研究对象

无论是白盒函数还是黑盒函数，都有很多的学术界人士和工业界人士去研究。通常来说，对于一个函数 而言，我们都可以研究该函数的以下性质：

1. 最大值与最小值，i.e. 和
2. 根，i.e.
3. 函数的单调性与凹凸性等。

对于具有明显表达式的函数，例如 等，我们能够使用的方法和技巧都很多，其方法包括但不限于导数，积分，Taylor 级数等等。但是对于黑盒函数，我们能够使用的方法和技巧就会一定的限制。本文将从如何研究一个函数的根，最大值和最小值等方向入手，逐步向大家展示黑盒函数研究中所遇到的数学与机器学习方法。

黑盒函数的根

对于多项式 而言，多项式的根指的是使得 的 的解。特别的，对于二次多项式而言，也就是 它的根可以表示为：

对于一般函数 而言，它的根指的是 这个集合。下面我们来介绍一下如何计算一个函数的根。

二分法

在数学分析中，介值定理（Intermediate value theorem）描述了连续函数在两点之间的连续性，具体描述是：

[介值定理] 如果连续函数 的定义域包含 而且通过 与 两点，它也必定通过区间 内的任意一点 其中

从介值定理可以得到，如果我们知道 和 那么必定存在 使得 。根据这个定理，我们可以提出二分法来计算函数的根。

如果要计算 的解，其一般步骤是：

1. 先找到一个区间 使得
2. 求这个区间的中点 并求出 的取值；
3. 如果 那么 就是函数的根；如果 就选择 为新的区间，否则选择 为新的区间；
4. 重复第 2 步和第 3 步直到达到最大迭代次数或者最理想的精度为止。

 

 

牛顿法（Newton’s Method）

牛顿法的大致思想是：选择一个接近 零点的初始点 计算这个点相应的函数取值 与导数值 然后写出通过点 的切线方程，并且计算出该切线与横轴的交点 i.e.

我们可以不停地重复以上过程，就得到一个递推公式：

在一定的条件下，牛顿法必定收敛。也就是说 随着 趋近于无穷，将会趋近于 的解。

割线法

根据导数的定义：

可以得到，当 靠近 的时候，可以用右侧的式子来估计导数值，i.e.

当我们不能够计算 的导数的时候，就可以用上式来代替。

于是，割线法与牛顿法的迭代公式非常相似，写出来就是：

在这里，割线法需要两个初始值 与 并且它们距离函数 的根越近越好。

备注

对于黑盒函数而言，我们是不知道它们的表达式的，因此以上的方法和技巧在黑盒函数的使用上就有限制。例如牛顿法是需要计算函数的导数值的，因此不适用在这个场景下。但是对于二分法与割线法，只需要计算函数在某个点的取值即可，因此可以用来寻找黑盒函数的根。

黑盒函数的最大值与最小值

对于能够写出表达式的函数而言，如果要寻找 的最大值与最小值，可以计算 的导数 然后令 就可以得到函数的临界点（critical point），再根据周围的点导数的性质即可判断这个点是否是局部最大值或者局部最小值。

Weierstrass 逼近定理

对于黑盒函数而言，通常来说我们只知道一组输入和相应的输出值。如果只考虑一维的情况而言，那就是 这 个样本。根据 Weierstrass 逼近定理可以知道：

1. 闭区间上的连续函数可以用多项式级数一致逼近；
2. 闭区间上的周期为 的连续函数可以用三角函数级数一致逼近。

用数学符号来描述就是：

[Weierstrass 逼近定理] 假设 是闭区间 连续的实函数。对于任意的 ，存在一个多项式 使得对于任意的 有

因此，如果要计算黑盒函数的最大值和最小值，可以使用一个多项式去拟合这 个点，于是计算这个多项式的最大值与最小值即可。

Lagrange 插值公式

按照之前的符号，如果我们拥有 个样本 那么我们可以找到一个多项式 使得 对每一个 都成立。根据计算，可以得到该多项式是：

于是，要计算黑盒函数的最大值与最小值，就可以转化成计算 的最大值与最小值。

除了数学方法之外，机器学习中有一种算法叫做启发式优化算法，也是用来计算黑盒函数的最大值和最小值的，例如粒子群算法与模拟退火算法等。

粒子群算法（Particle Swarm Optimization）

PSO 最初是为了模拟鸟群等动物的群体运动而形成的一种优化算法。PSO 算法是假设有一个粒子群，根据群体粒子和单个粒子的最优效果，来调整每一个粒子的下一步行动方向。假设粒子的个数是 ，每一个粒子 都是 维欧几里德空间里面的点，同时需要假设粒子的速度 。在每一轮迭代中，需要更新两个最值，分别是每一个粒子在历史上的最优值和所有粒子在历史上的最优值，分别记为 （）和 。在第 次迭代的时候，

在这里，，并且 是 中间的随机数。

模拟退火（Simulated Annealing）

模拟退火算法是为了模拟金属退火现象。其核心思想是构造了温度 这个维度，当温度 高的时候，分子运动速度快，能够探索更多的区域；温度 低的时候，分子运动速度慢，能够探索的区域有限。随着时间的迁移，温度 会从一个较大的值逐渐降低到 0。

模拟退火的大体思路是这样的：先设置一个较大的温度值 ，随机初始化 。假设目标函数是 需要寻找 ，然后执行以下的程序：

Repeat：

a. Repeat:

i. 进行一个随机扰动 ；

ii. 计算 ，

如果 ，也就是 ，选择 ；

否则，按照 的概率来接受 。

b. 令 。

直到 足够小。

总结

本文从数学和机器学习的角度，简要介绍了部分计算黑盒函数的最大值，最小值和根的方法，后续将会介绍更多的类似方法。

 

Fibonacci 序列

在开始讲解时间序列的自回归模型（AutoRegression Model）之前，我们需要先介绍一下线性代数的基础知识。为了介绍线性代数的基础知识，我们可以先看一个简单的例子。考虑整数序列 Fibonacci 序列，它的通项公式是一个递归函数，每项的取值是由前两项所生成的，其具体的公式就是

，

其初始值是 。按照其递归公式来计算，我们可以详细写出前面的几项，那就是：

0，1，1，2，3，5，8，13，21，34，55，89，144，…

但是，计算 Fibonacci 的通项公式则比计算等差数列和等比数列的通项公式复杂的多，因为这里需要使用线性代数的技巧才能解决这个问题。

求解 Fibonacci 序列的通项公式 －－－ 矩阵对角化

根据 Fibonacci 数列的递归公式，基于矩阵乘法的定义，Fibonacci 序列可以写成如下形式：

这就意味着我们需要计算出矩阵 A 的幂。在线性代数里面，为了计算矩阵的 n 次方，除了通过矩阵乘法的公式直接计算之外，还有一个经典的技巧，那就是将矩阵对角化。详细来说，如果 的矩阵 A 能够对角化，那就是存在可逆矩阵 P 使得

其中 表示一个 的对角矩阵，其对角的元素从左上角到右下角依次是 。如果把矩阵 P 写成列向量的形式，i.e. ，那么以上的矩阵方程就可以转换为 , 。进一步来说，如果要计算矩阵 A 的幂，就可以得到：

另外，如果想知道一个矩阵 A 的特征值和特征向量，则需要计算以下多项式的根，i.e. 计算关于 的多项式的解，

其中 I 是一个单位矩阵（identity matrix）。

按照以上的思路，如果令

,

可以计算出 A 的两个特征值分别是 和 ，它们所对应的特征向量分别是：

.

因此直接计算可以得到

.

通过上面的计算方法，为了计算 Fibonacci 数列的通项公式，我们可以先把它转换成一个矩阵求幂的问题，于是我们就能矩阵对角化的方法把 Fibonacci 数列的通项公式求出来。

时间序列的弱平稳性

要讲解自回归模型，就必须提到时间序列的弱平稳性。一个时间序列 具有弱平稳性（Weak Stationary）指的是：

1. 对于所有的 都是恒定的；
2. 对于所有的 都是恒定的；
3. 与 的协方差对于所有的 都是恒定的。

另外，时间序列的自相关方程（AutoCorrelation Function）指的是对于 ，可以定义 ACF 为

.

如果时间序列 在弱平稳性的假定下，ACF 将会简化为

.

时间序列的自回归模型（AutoRegression Model）

AR(1) 模型

AR(1) 模型指的是时间序列 在时间戳 时刻的取值 与时间戳 时刻的取值 相关，其公式就是：

，

这个时间序列 满足如下条件：

1. ，并且 满足 iid 条件。其中 表示 Gauss 正态分布，它的均值是0，方差是 。
2. 与 是相互独立的（independent）。
3. 是弱平稳的，i.e. 必须满足 。

如果选择初始条件 ，则可以得到一些 AR(1) 模型的例子如下图所示：

从 AR(1) 以上的定义出发，我们可以得到：

1. .
2. .
3. .

Proof of 1. 从 AR(1) 的模型出发，可以得到

,

从而，.

Proof of 2. 从 AR(1) 的模型出发，可以得到

,

从而，.

Proof of 3. 令 . 从 的定义出发，可以得到：

从而，

.

AR(1) 模型与一维动力系统

特别的，如果假设 恒等于零，就可以得到 对于所有的 都成立。也就是可以写成一个一维函数的迭代公式：

下面我们要计算 的收敛性，这里的 表示函数 的 次迭代。

Method 1. 

通过 的定义直接计算可以得到：

,

令 ，可以得到 。这与 其实是保持一致的。

另外，如果 ，可以从公式上得到 当 。

Method 2.

将原函数转换成 Lipschitz 函数的形式，i.e. 如果 ，那么

.

因为 ，我们可以得到 . i.e. 趋近于 .

反之，如果 ，很容易得到

.

因此，在 这种条件下， as . 特别地，对于一阶差分方程  而言，如果 ，那么 的取值会越来越大，这与现实的状况不相符，所以在时间序列的研究中，一般都会假设 。

AR(p) 模型

按照之前类似的定义，可以把 AR(1) 模型扩充到 AR(p) 模型，也就是说：

1. AR(1) 模型形如：

2. AR(2) 模型形如：

3. AR(p) 模型形如：

AR(p) 模型的稳定性 －－－ 基于线性代数

对于 AR(2) 模型，可以假定 并且忽略误差项，因此可以得到简化版的模型形如：

.

写成矩阵的形式形如：

求解其特征多项式则是基于 ，求解可以得到 ，i.e. 。当 都在单位圆内部的时候，也就是该模型 满足稳定性的条件。

对于更加一般的 AR(p) 模型，也就是考虑 p 阶差分方程

可以用同样的方法将其转换成矩阵的形式，那就是：

计算 ，可以得到其特征多项式为：

当每个特征值都在单位圆盘内部的时候，i.e. ，该 p 阶差分方程

存在稳定性的解。

 

在之前的时间序列相似度算法中，时间戳都是一一对应的，但是在实际的场景中，时间戳有可能出现一定的偏移，但是两条时间序列却又是十分相似的。例如正弦函数 和余弦函数 ，只是平移了 个长度而已。本文将会介绍一些基于形状的时间序列的距离算法，并且介绍如何在给定时间序列的情况下，在时间序列数据库中寻找相似的时间序列。

 

基于动态规划的相似度计算方法

DTW 的经典算法

基于动态规划的相似度计算的典型代表就是 DTW（Dynamical Time Warping ）和 Frechet 距离。在这里将会主要介绍 DTW 算法。详细来说，DTW 算法是为了计算语音信号处理中，由于两个人说话的时长不一样，但是却是类似的一段话，欧几里德算法不完全能够解决这类问题。在这种情况下，DTW 算法就被发展出来。DTW 算法是为了计算两条时间序列的最佳匹配点，假设我们有两条时间序列 Q 和 C，长度都是 n，并且 和 。首先我们可以建立一个 的矩阵， 位置的元素是 ，这里的 dist 可以使用 范数。其次，我们想找到一条路径，使得这个矩阵的累积距离最小，而这条路则是两条时间序列之间的最佳匹配。在这里，我们可以假设这条路径是 ，其中 的每个元素表示时间序列 Q 中的第 i 个元素和时间序列 C 中的第 j 个元素之间的距离. i.e. 。

现在我们需要找到一条路径使得

.

这条路径就是动态规划的解，它满足一个动态规划方程：对于 ，有

其初始状态是 最终的取值 就是我们需要的解，也就是两条时间序列的 DTW 距离。按照上面的算法，DTW 算法的时间复杂度是 。特别地，

1. 如果 时，则 表示最后的距离；
2. 如果 时，则 表示最后的距离。
3. 如果 时，则 表示最后的距离。

Remark. 

DTW 算法不满足三角不等式。例如：，则

DTW 的加速算法

某些时候，我们可以添加一个窗口长度的限制，换言之，如果要比较 与 的话，i 与 j 需要满足 ，这里的 w 表示窗口长度。因此算法的描述如下：

初始条件和之前一样。

这里的 取值范围是：对每一个 ，需要 满足。

 

相似时间序列的搜索

相似的时间序列的搜索问题一般是这样的：

Question 1. 给定一条时间序列 和一个时间序列的数据库 。通过某种相似度或者距离计算方法，计算出给定的时间序列 与时间序列数据库中 中最相似的时间序列。

Question 2. 给定一条时间序列 和一个时间序列的数据库 ，以及正整数 。从数据库 中寻找与给定的时间序列 最相似的 条时间序列。

DTW 算法的下界 LB_Kim

对于两条时间序列 Q 和 C 而言，可以分别提取它们的四个特征，那就是最大值，最小值，第一个元素的值，最后一个元素的值。这样可以计算出 LB_Kim

可以证明 .

DTW 算法的下界 LB_Yi

有学者在 LB_Kim 的基础上提出了一种下界的计算方法，那就是 LB_Yi，有兴趣的读者可以参见：efficient retrieval of similar time sequences under time warping， 1998.

DTW 算法的下界 LB_Keogh

但是，如果是基于 DTW 的距离计算方法，每次都要计算两条时间序列的 DTW 距离，时间复杂度是 。于是就有学者研究是否存在 DTW 距离的下界表示，也就是说找到一个合适的下界，Lower Bound of DTW。每次判断 Lower Bound of DTW 是否小于当前的最小距离，如果下界高于最小距离，就不需要进行 DTW 的计算；否则开始计算 DTW 的值。如果下界的计算速度足够快，并且下界足够精准的话，可以大量的压缩搜索的时间。于是，Keogh 提出了下界的计算方法。

（1）首先定义时间序列 Q 的上下界。i.e. ，给定一个窗口的取值 r，得到 ，。

（2）定义公式：

其中，LBKeogh 满足性质：

对于任意两条长度为 n 的时间序列 Q 和 C，对于任意的窗口 ，有不等式 成立。

所以，可以把搜索的算法进行加速：

Lower Bounding Sequential Scan(Q)
    best_so_far = infinity 
    for all sequences in database
        LB_dist = lower_bound_distance(C_{i},Q)
        if LB_dist < best_so_far
            true_dist = DTW(C_{i},Q)
            if true_dist < best_so_far
                best_so_far = true_dist
                index_of_best_match = i
            endif
        endif
    endfor

在论文 Exact Indexing of Dynamic Time Warping 里面，作者还尝试将 Piecewise Constant Approximation 与 LB_Keogh 结合起来，提出了 LB_PAA 的下界。它满足条件 .

 

总结

本文初步介绍了 DTW 算法以及它的下界算法，包括 LB_Kim, LB_Keogh 等，以及时间序列数据库的搜索算法。

 

Riemann 积分和 Lebesgue 积分是数学中两个非常重要的概念。本文将会从 Riemann 积分和 Lebesgue 积分的定义出发，介绍它们各自的性质和联系。

积分

Riemann 积分

Riemann 积分虽然被称为 Riemann 积分，但是在 Riemann 之前就有学者对这类积分进行了详细的研究。早在阿基米德时代，阿基米德为了计算曲线 在 [0,1] 区间上与 X 坐标轴所夹的图形面积，就使用了 Riemann 积分的思想。 他把 [0,1] 区间等长地切割成 n 段，每一段使用一个长方形去逼近 这条曲线的分段面积，再把 n 取得很大，所以得到当 n 趋近于无穷的时候，就知道该面积其实是 1/3。

下面来看一下 Riemann 积分的详细定义。

考虑定义在闭区间 [a,b] 上的函数 ，

取一个有限的点列 ， 表示这些区间长度的最大值，在这里 。在每一个子区间上 上取出一个点 。而函数 关于以上取样分割的 Riemann 和就是以下公式：

当我们说该函数 在闭区间 上的取值是 的意思是：

对于任意 ，存在 使得对于任意取样分割，当 时，就有

通常来说，用符号来表示就是：.

用几幅图来描述 Riemann 积分的思想就是：

 

Lebesgue 积分

Riemann 积分是为了计算曲线与 X 轴所围成的面积，而 Lebesgue 积分也是做同样的事情，但是计算面积的方法略有不同。要想直观的解释两种积分的原理，可以参见下图：

Riemann 积分是把一条曲线的底部分成等长的区间，测量每一个区间上的曲线高度，所以总面积就是这些区间与高度所围成的面积和。

Lebesgue 积分是把曲线化成等高线图，每两根相邻等高线的差值是一样的。每根等高线之内含有它所圈着的长度，因此总面积就是这些等高线内的面积之和。

用再形象一点的语言来描述就是：吃一块汉堡有多种方式

1. Riemann 积分：从一个角落开始一口一口吃，每口都包含所有的配料；
2. Lebesgue 积分：从最上层开始吃，按照“面包-配菜-肉-蛋-面包”的节奏，一层一层来吃。

再看一幅图的表示就是：Riemann 积分是按照蓝色的数字顺序相加的，Lebesgue 积分是按照红色的数字来顺序相加的。

 

基于这些基本的思想，就可以给出 Lebesgue 积分的定义：

简单函数指的是对指示函数的有限线性组合，i.e. ，这里的 是系数， 是可测集合， 表示指示函数。当 非负时，令

如果 是一个非负可测函数时，可以定义函数 在可测集合 上的 Lebesgue 积分是：

,

这里的 指的是非负简单函数， 表示零函数，这里的大小关系表示对定义域内的每个点都要成立。

而对于可测函数时，可以把可测函数 转换成 ，而这里的 和 都是非负可测函数。所以可以定义任意可测函数的 Lebesgue 积分如下：

.

Riemann 积分与Lebesgue 积分的关系

定义了两种积分之后，也许有人会问它们之间是否存在矛盾？其实，它们之间是不矛盾的，因为有学者证明了这样的定理：

如果有界函数 在闭区间 是 Riemann 可积的，则它也是 Lebesgue 可积的，并且它们的积分值相等：

.

左侧是表示 Riemann 积分，右侧表示 Lebesgue 积分。

用形象化一点的语言描述就是：无论从角落一口一口地吃汉堡，还是从顶至下一层一层吃，所吃的汉堡都是同一个。

但是 Lebesgue 积分比 Riemann 积分有着更大的优势，例如 Dirichlet 函数，

1. 当 是有理数时，；
2. 当 是无理数时，.

Dirichlet 函数是定义在实数轴的函数，并且值域是 ，无法画出函数图像，它不是 Riemann 可积的，但是它 Lebesgue 可积。

 

时间序列

提到时间序列，也就是把以上所讨论的连续函数换成离散函数而已，把定义域从一个闭区间 换成 这样的定义域而已。所以，之前所讨论的很多连续函数的想法都可以应用在时间序列上。

时间序列的表示 — 基于 Riemann 积分

现在我们可以按照 Riemann 积分的计算方法来表示一个时间序列的特征，于是就有学者把时间序列按照横轴切分成很多段，每一段使用某个简单函数（线性函数等）来表示，于是就有了以下的方法：

1. 分段线性逼近（Piecewise Linear Approximation）
2. 分段聚合逼近（Piecewise Aggregate Approximation）
3. 分段常数逼近（Piecewise Constant Approximation）

说到这几种算法，其实最本质的思想就是进行数据降维的工作，用少数的数据来进行原始时间序列的表示（Representation）。用数学化的语言来描述时间序列的数据降维（Data Reduction）就是：把原始的时间序列 用 来表示，其中 。那么后者就是原始序列的一种表示（representation）。

分段聚合逼近（Piecewise Aggregate Approximation）— 类似 Riemann 积分

在这种算法中，分段聚合逼近（Piecewise Aggregate Approximation）是一种非常经典的算法。假设原始的时间序列是 ，定义 PAA 的序列是：，

其中

.

在这里 。用图像来表示那就是：

至于分段线性逼近（Piecewise Linear Approximation）和分段常数逼近（Piecewise Constant Approximation），只需要在 的定义上稍作修改即可。

符号特征（Symbolic Approximation）— 类似用简单函数来计算 Lebesgue 积分

在推荐系统的特征工程里面，特征通常来说可以做归一化，二值化，离散化等操作。例如，用户的年龄特征，一般不会直接使用具体的年月日，而是划分为某个区间段，例如 0~6（婴幼儿时期），7~12（小学），13~17（中学），18~22（大学）等阶段。

其实在得到分段特征之后，分段特征在某种程度上来说依旧是某些连续值，能否把连续值划分为一些离散的值呢？于是就有学者使用一些符号来表示时间序列的关键特征，也就是所谓的符号表示法（Symbolic Representation）。下面来介绍经典的 SAX Representation。

如果我们希望使用 个符号来表示时间序列，那么我们其实可以考虑正态分布 ，用 来表示 Gauss 曲线下方的一些点，而这些点把 Gauss 曲线下方的面积等分成了 段。用 表示 个字母。

SAX 方法的流程如下：

1. 正规化（normalization）：把原始的时间序列映射到一个新的时间序列，新的时间序列满足均值为零，方差为一的条件。
2. 分段表示（PAA）：。
3. 符号表示（SAX）：如果 ，那么 ；如果 ，那么 ，在这里 ；如果 ，那么 。

于是，我们就可以用  这 个字母来表示原始的时间序列了。

时间序列的表示 — 基于 Lebesgue 积分

要想考虑一个时间序列的值分布情况，其实就类似于 Lebesgue 积分的计算方法，考虑它们的分布情况，然后使用某些函数去逼近时间序列。要考虑时间序列的值分布情况，可以考虑熵的概念。

熵（Entropy）

通常来说，要想描述一种确定性与不确定性，熵（entropy）是一种不错的指标。对于离散空间而言，一个系统的熵（entropy）可以这样来表示：

.

如果一个系统的熵（entropy）越大，说明这个系统就越混乱；如果一个系统的熵越小，那么说明这个系统就更加确定。

提到时间序列的熵特征，一般来说有几个经典的熵指标，其中有一个就是 binned entropy。

分桶熵（Binned Entropy）

从熵的定义出发，可以考虑把时间序列的值进行分桶的操作，例如，可以把 [min, max] 这个区间等分为十个小区间，那么时间序列的取值就会分散在这十个桶中。根据这个等距分桶的情况，就可以计算出这个概率分布的熵（entropy）。i.e. Binned Entropy 就可以定义为：

其中 表示时间序列 X 的取值落在第 k 个桶的比例（概率），maxbin 表示桶的个数，len(X) 表示时间序列 X 的长度。

如果一个时间序列的 Binned Entropy 较大，说明这一段时间序列的取值是较为均匀的分布在 [min, max] 之间的；如果一个时间序列的 Binned Entropy 较小，说明这一段时间序列的取值是集中在某一段上的。

总结

在本篇文章中，笔者从 Riemann 积分和 Lebesgue 积分出发，介绍了它们的基本概念，性质和联系。然后从两种积分出发，探讨了时间序列的分段特征，时间序列的熵特征。在未来的 Blog 中，笔者将会介绍时间序列的更多相关内容。

 

在文本挖掘中，可以通过 Word2Vec 生成的向量以及向量的内积，或者根据语义和词性来判断两个词语是否是近义词。在时间序列的挖掘中，同样可以找到一些方法来描述两条时间序列是否相似。

在介绍时间序列的距离之前，笔者感觉需要回顾一下数学中度量空间和内积空间的定义。

度量空间

在数学里面，集合 上的距离函数定义为 ，其中 表示实数集合，并且函数 满足以下几个条件：

1. ，并且 当且仅当 ;
2. ，也就是满足对称性；
3. ，也就是三角不等式。

满足这三个条件的距离函数称为度量，具有某种度量的集合则叫做度量空间。

Remark.

在本文下面的时间序列距离的各种定义中，这些距离不一定满足三角不等式。例如动态时间算法（DTW）就不满足三角不等式。

内积空间

一个内积空间是域 （其中 或者 ）上的向量空间 与一个内积（映射）所构成， 上的一个内积定义为正定，非退化的共轭双线性形式，记成 ，它满足以下设定：

1. 对于任意的 ，有

2. 共轭双线性形式指的是：

3. 非负性：

4. 非退化：从 到对偶空间 的映射： 是同构映射。

 

基于欧几里德距离的相似度计算

假设两条时间序列曲线为 和 ，于是可以使用欧几里德空间里面的 范数来表示两个时间序列之间的距离。用公式来描述就是：

 

基于相关性的相似度计算方法

Pearson 系数（Pearson Coefficient）

其中，

, 。

Pearson 系数的性质如下：

1. 如果两条时间序列 ，则 表是它们是完全一致的，如果两条时间序列 ，则 表示它们之间是负相关的。
2. .

可以基于 Pearson 系数来制定两条时间序列之间的距离：

其中.

The First Order Temporal Correlation Coefficient

这个相关性系数与 Pearson 系数类似，但是略有不同，其定义为：

的性质：

1. 
2. 表示两条时间序列持有类似的趋势， 它们会同时上涨或者下跌，并且涨幅或者跌幅也是类似的。
3. 表示两条时间序列的上涨和下跌趋势恰好相反。
4. 表示两条时间序列在单调性方面没有相关性。

基于 CORT，同样可以定义时间序列的距离，用公式描述如下：

其中， 可以用 来计算，而

是一个递减函数。

基于自相关系数的距离（Autocorrelation-based distance)

假设时间序列是 ，对于任意的 ，可以定义自相关系数为：

,

其中 分别表示该时间序列的均值和方差。该公式相当于是比较整个时间序列 的两个子序列的相似度（Pearson 系数），这两个子序列分别是 和 。

于是，通过给定一个正整数 ，可以对每一个时间序列得到一组自相关系数的向量，用公式描述如下：

对于 的情况，可以假定 和 。于是，可以定义时间序列之间的距离如下：

.

其中的 表示一个 的矩阵。它有着很多种选择，例如：

（1） 表示单位矩阵。用公式表示就是

.

（2） 表示一个 的对角矩阵，其中 。此时相当于一个带权重的求和公式。

.

除了自相关系数（Autocorrelation Coefficients）之外，也可以考虑偏自相关系数（Partial Autocorrelation Coefficients），使用 PACFs 来取代 ACFs。这样，使用同样的定义方式就可以得到 和 两个距离公式。

 

基于周期性的相似度计算方法

这里会介绍基于周期图表（Periodogram-based）的距离计算方法。其大体思想就是通过 Fourier 变换得到一组参数，然后通过这组参数来反映原始的两个时间序列时间的距离。用数学公式来描述就是：

,

.

其中 ，，。这里的 表示 Gauss 取整函数。

（1）用原始的特征来表示距离：

.

（2）用正则化之后的特征来描述就是：

,

其中 ，， 和 表示 的标准差（sample variance）。

（3）用取对数之后的特征表示：

.

 

 

基于模型的相似度计算

Piccolo 距离

基于模型的相似度判断本质上是用一个模型和相应的一组参数去拟合某条时间序列，然后得到最优的一组参数，计算两个时间序列所得到的最优参数的欧几里德距离即可。

模型有自己的 AR 表示，因此可以得到相应的一组参数 ，所以，对于每一条时间序列，都可以用一组最优的参数去逼近。如果

分别表示 和 对于时间序列 和 的参数估计，则 Piccolo 距离如下：

,

其中 ， 当 ，并且 当 。 当 ，并且 当 。

Maharaj 距离

按照之前的描述，可以增加一个矩阵来修改 Piccolo 距离：

其中 和 表示 模型对于 和 的参数估计，和 Piccolo 距离一样。， 和 表示时间序列的方差， 和 表示时间序列的 sample covariance 矩阵。

基于 Cepstral 的距离

考虑时间序列 满足 的结构，i.e. ，这里的 表示 AR 模型的参数， 表示白噪声（均值为 0，方差为 1 的 Gauss 正态分布）。于是可以从这些参数定义 LPC 系数如下：

，

当 ，

当 。

所以，LPC 的距离定义是：

.

 

总结

在本文中，介绍了时间序列之间距离的计算方法，包括基于 范数的距离，基于相关性的距离，基于周期图表的计算方法，基于模型的计算方法。

 

 

提到时间序列，大家能够想到的就是一串按时间排序的数据，但是在这串数字背后有着它特殊的含义，那么如何进行时间序列的表示（Representation），如何进行时间序列的信息提取（Information Extraction）就成为了时间序列研究的关键问题。

就笔者的个人经验而言，其实时间序列的一些想法和文本挖掘是非常类似的。通常来说句子都是由各种各样的词语组成的，并且一般情况下都是“主谓宾”的句子结构。于是就有人希望把词语用一个数学上的向量描述出来，那么最经典的做法就是使用 one – hot 的编码格式。i.e. 也就是对字典里面的每一个词语进行编码，一个词语对应着一个唯一的数字，例如 0，1，2 这种形式。one hot 的编码格式是这行向量的长度是词典中词语的个数，只有一个值是1，其余的取值是0，也就是 (0,…,0,1,0,…,0) 这种样子。但是在一般情况下，词语的个数都是非常多的，如何使用一个维度较小的向量来表示一个词语就成为了一个关键的问题。几年前，GOOGLE 公司开源了 Word2vec 开源框架，把每一个词语用一串向量来进行描述，向量的长度可以自行调整，大约是100~1000 不等，就把原始的 one-hot 编码转换为了一个低维空间的向量。在这种情况下，机器学习的很多经典算法，包括分类，回归，聚类等都可以在文本上得到巨大的使用。Word2vec 是采用神经网络的思想来提取每个词语与周边词语的关系，从而把每个词语用一个低维向量来表示。在这里，时间序列的特征提取方法与 word2vec 略有不同，后面会一一展示这些技巧。

 

时间序列的统计特征

提到时间序列的统计特征，一般都能够想到最大值（max），最小值（min），均值（mean），中位数（median），方差（variance），标准差（standard variance）等指标，不过一般的统计书上还会介绍两个指标，那就是偏度（skewness）和峰度（kuriosis）。如果使用时间序列 来表示长度为 的时间序列，那么这些统计特征用数学公式来表示就是：

其中 和 分别表示时间序列 的均值和方差。

 

时间序列的熵特征

为什么要研究时间序列的熵呢？请看下面两个时间序列：

时间序列（1）：(1,2,1,2,1,2,1,2,1,2,…)

时间序列（2）：(1,1,2,1,2,2,2,2,1,1,…)

在时间序列（1）中，1 和 2 是交替出现的，而在时间序列（2）中，1 和 2 是随机出现的。在这种情况下，时间序列（1）则更加确定，时间序列（2）则更加随机。并且在这种情况下，两个时间序列的统计特征，例如均值，方差，中位数等等则是几乎一致的，说明用之前的统计特征并不足以精准的区分这两种时间序列。

通常来说，要想描述一种确定性与不确定性，熵（entropy）是一种不错的指标。对于离散空间而言，一个系统的熵（entropy）可以这样来表示：

如果一个系统的熵（entropy）越大，说明这个系统就越混乱；如果一个系统的熵越小，那么说明这个系统就更加确定。

提到时间序列的熵特征，一般来说有几个经典的例子，那就是 binned entropy，approximate entropy，sample entropy。下面来一一介绍时间序列中这几个经典的熵。

Binned Entropy

从熵的定义出发，可以考虑把时间序列 的取值进行分桶的操作。例如，可以把 这个区间等分为十个小区间，那么时间序列的取值就会分散在这十个桶中。根据这个等距分桶的情况，就可以计算出这个概率分布的熵（entropy）。i.e. Binned Entropy 就可以定义为：

其中 表示时间序列 的取值落在第 个桶的比例（概率）， 表示桶的个数， 表示时间序列 的长度。

如果一个时间序列的 Binned Entropy 较大，说明这一段时间序列的取值是较为均匀的分布在 之间的；如果一个时间序列的 Binned Entropy 较小，说明这一段时间序列的取值是集中在某一段上的。

Approximate Entropy

回到本节的问题，如何判断一个时间序列是否具备某种趋势还是随机出现呢？这就需要介绍 Approximate Entropy 的概念了，Approximate Entropy 的思想就是把一维空间的时间序列提升到高维空间中，通过高维空间的向量之间的距离或者相似度的判断，来推导出一维空间的时间序列是否存在某种趋势或者确定性。那么，我们现在可以假设时间序列 的长度是 ，同时 Approximate Entropy 函数拥有两个参数， 与 ，下面来详细介绍 Approximate Entropy 的算法细节。

Step 1. 固定两个参数，正整数 和正数 ，正整数 是为了把时间序列进行一个片段的提取，正数 是表示时间序列距离的某个参数。i.e. 需要构造新的 维向量如下：

Step 2. 通过新的向量 ，可以计算出哪些向量与 较为相似。i.e.

在这里，距离 可以选择 范数。在这个场景下，距离 通常选择为 范数。

Step 3. 考虑函数

Step 4. Approximate Entropy 可以定义为：

Remark.

1. 正整数 一般可以取值为 2 或者 3， 会基于具体的时间序列具体调整；
2. 如果某条时间序列具有很多重复的片段（repetitive pattern）或者自相似性（self-similarity pattern），那么它的 Approximate Entropy 就会相对小；反之，如果某条时间序列几乎是随机出现的，那么它的 Approximate Entropy 就会相对较大。

Sample Entropy

除了 Approximate Entropy，还有另外一个熵的指标可以衡量时间序列，那就是 Sample Entropy，通过自然对数的计算来表示时间序列是否具备某种自相似性。

按照以上 Approximate Entropy 的定义，可以基于 与 定义两个指标 和 ，分别是

其中， 表示集合的元素个数。根据度量 （无论是 ）的定义可以知道，因此 Sample Entropy 总是非负数，i.e.

Remark.

1. Sample Entropy 总是非负数；
2. Sample Entropy 越小表示该时间序列具有越强的自相似性（self similarity）。
3. 通常来说，在 Sample Entropy 的参数选择中，可以选择 .

 

时间序列的分段特征

即使时间序列有一定的自相似性（self-similarity），能否说明这两条时间序列就完全相似呢？其实答案是否定的，例如：两个长度都是 1000 的时间序列，

时间序列（1）： [1,2] * 500

时间序列（2）： [1,2,3,4,5,6,7,8,9,10] * 100

其中，时间序列（1）是 1 和 2 循环的，时间序列（2）是 1~10 这样循环的，它们从图像上看完全是不一样的曲线，并且它们的 Approximate Entropy  和 Sample Entropy 都是非常小的。那么问题来了，有没有办法提炼出信息，从而表示它们的不同点呢？答案是肯定的。

首先，我们可以回顾一下 Riemann 积分和 Lebesgue 积分的定义和不同之处。按照下面两幅图所示，Riemann 积分是为了算曲线下面所围成的面积，因此把横轴划分成一个又一个的小区间，按照长方形累加的算法来计算面积。而 Lebesgue 积分的算法恰好相反，它是把纵轴切分成一个又一个的小区间，然后也是按照长方形累加的算法来计算面积。

之前的 Binned Entropy 方案是根据值域来进行切分的，好比 Lebesgue 积分的计算方法。现在我们可以按照 Riemann 积分的计算方法来表示一个时间序列的特征，于是就有学者把时间序列按照横轴切分成很多段，每一段使用某个简单函数（线性函数等）来表示，于是就有了以下的方法：

1. 分段线性逼近（Piecewise Linear Approximation）
2. 分段聚合逼近（Piecewise Aggregate Approximation）
3. 分段常数逼近（Piecewise Constant Approximation）

说到这几种算法，其实最本质的思想就是进行数据降维的工作，用少数的数据来进行原始时间序列的表示（Representation）。用数学化的语言来描述时间序列的数据降维（Data Reduction）就是：把原始的时间序列 用 来表示，其中 。那么后者就是原始序列的一种表示（representation）。

分段聚合逼近（Piecewise Aggregate Approximation）— 类似 Riemann 积分

在这种算法中，分段聚合逼近（Piecewise Aggregate Approximation）是一种非常经典的算法。假设原始的时间序列是 ，定义 PAA 的序列是：，

其中

.

在这里 。用图像来表示那就是：

至于分段线性逼近（Piecewise Linear Approximation）和分段常数逼近（Piecewise Constant Approximation），只需要在 的定义上稍作修改即可。

符号逼近（Symbolic Approximation）— 类似 Riemann 积分

在推荐系统的特征工程里面，特征通常来说可以做归一化，二值化，离散化等操作。例如，用户的年龄特征，一般不会直接使用具体的年月日，而是划分为某个区间段，例如 0~6（婴幼儿时期），7~12（小学），13~17（中学），18~22（大学）等阶段。

其实在得到分段特征之后，分段特征在某种程度上来说依旧是某些连续值，能否把连续值划分为一些离散的值呢？于是就有学者使用一些符号来表示时间序列的关键特征，也就是所谓的符号表示法（Symbolic Representation）。下面来介绍经典的 SAX Representation。

如果我们希望使用 个符号，例如 来表示时间序列。同时考虑正态分布 ，用 来表示 Gauss 曲线下方的一些点，而这些点把 Gauss 曲线下方的面积等分成了 段。

SAX 方法的流程如下：

Step 1. 正规化（normalization）：也就是该时间序列被映射到均值为零，方差为一的区间内。

Step 2. 分段表示（PAA）：。

Step 3. 符号表示（SAX）：如果 ，那么 ；如果 ，那么 ；如果 ，那么 。

于是，我们就可以用  这 个字母来表示原始的时间序列了。

、

 

总结

在本篇文章中，我们介绍了时间序列的一些表示方法（Representation），其中包括时间序列统计特征，时间序列的熵特征，时间序列的分段特征。在下一篇文章中，我们将会介绍时间序列的相似度计算方法。

 

文章是：”Correlating Events with Time Series for Incident Diagnosis” 是微软在2014年的工作，并且发表在KDD上。

本文提出了一种无监督和统计判别的算法，可以检测出事件（E）与时间序列（S）的关联关系，并且可以检测出时间序列（S）的单调性（上升或者下降）。在这篇文章中，选择的事件有CPU（Memory, Disk）Intensive Program，Query Alert；选择的时间序列有 CPU（Memory）Usage，Disk Transfer Rate。时间序列的特点是它们的值域范围都是[0,1]。

案例是：时间序列是CPU的Usage，事件是Disk Intensive task和CPU intensive task。

关联关系的挖掘分成三个部分：

（1）是否存在关联性（Existence of Dependency）：在事件（E）与时间序列（S）之间是否存在关联关系。

（2）关联关系的因果关系（Temporal Order of Dependency）：是事件（E）导致了时间序列（S）的变化还是时间序列（S）导致了事件（E）的发生。

（3）关联关系的单调性影响（Monotonic Effect of Dependency）：用于判断时间序列（S）是发生了突增或者是突降。

基本概念：

给定一个事件序列（E），事件发生的时间戳是，这里n表示有n个事件发生。时间序列（S）表示为，这里的m表示时间序列的长度。时间序列的时间戳可以选择一个等差序列，等差用来表示，并且，and +。

用来表示某个事件，表示序列S在事件之后的长度为k的子序列，表示序列S在事件之前的长度为k的子序列。如果事件E与时间序列S之间存在关联关系，那么

和

应该是不一样的。

定义一：如果事件序列E和时间序列S是相关的，并且，当且仅当和随机选择的子序列分布不一致。

定义二：如果事件序列E和时间序列S是相关的，并且，当且仅当和随机选择的子序列分布不一致，并且和随机选择的子序列分布一致。

定义三：如果事件序列E和时间序列S是相关的，那么或者。

定义四：如果 (or )，并且时间序列相比E之前是增加了，那么记为 (or )。如果 (or )，并且时间序列相比E之前是减少了，那么记为 (or )。

方法论：

第一步：最邻近算法（类似kNN）（Nearest Neighbor Method）

在计算时间序列之间距离的时候，使用DTW算法或者DTW-D算法会优于L1或者L2算法。

用来做例子， ， 是随机选择的，，可以标记为，其中+。 when ， when +。可以使用记号，其中，是随机选择的。

对于集合 ， 而言， 表示中距离x最近的第r个元素，对于两个不相交的集合 和 ，可以定义方程：

when ,

when otherwise.

该方程表示x与x的第r个最近的邻居是否在同一个子集内。

定义

,

在这里+表示样本的总个数，表示集合A的第i个元素。从直觉上讲，如果小，则说明两类samples 混合得非常好，表示无异常情况；如果大，则说明两类samples 有区分度，很多元素与它的邻居集中在某个子集里面，说明 这个集合与 有区分度。

根据文献里面的观点，当p足够大的时候，遵循标准Gauss分布，其参数是+, +,

+, +。

根据传统的Gauss分布Test方法，和有显著的不同，当，在这里，参数可以按照以下标准设置：

for ，

for 。

如果和存在显著性偏差，那么说明应该返回异常的标识。类似的，如果使用并且它与存在显著性偏差，那么说明应该返回异常的标识。

 

第二步：关联顺序的挖掘（Mining Existence and Temporal Order）

如果前面的子序列与随机选择的子序列有显著偏差，那么说明时序的变化导致了事件的发生，。

如果后面的子序列与随机选择的子序列有显著偏差，那么说明事件导致了时序的变化，。

在Figure 3中，CPU Intensive Program 导致了 CPU Usage，并且 CPU Usage 导致了 SQL Query Alert。

 

第三步：单调性的影响类型（Mining Effect Type）

现在需要判断时间序列是突增还是突降了，需要引入的概念。

对于和而言，其中n是E中的事件个数。就可以定义为：

.

那么，如果，可以得到 或者 ；如果，可以得到 或者 。

其中参数可以设置为：

for ，

for 。

 

算法综述：

其中，5，6行是为了计算相关性， 是 True 表示 有异常，否则表示正常； 是 True 表示 有异常，否则表示正常。

7-13行是 的情形，因为 异常，同时 正常，说明事件导致了时间序列的变化。7-13行是为了计算 的范围，判断是显著的提升还是下降。

14-20行是 的情形，因为 异常，就导致了事件的发生。14-20行是为了计算  的范围，判断是显著的提升还是下降。

参数：

时间序列的长度 可以设置为第一次达到顶峰的长度，

最邻近的元素个数 ，其中p是样本的总个数。

其他算法：

（1）Pearson Correlation

（2）J-Measure Correlation

 

 

本篇文章是智能运维系统的调研文章，作者是清华大学的裴丹教授，论文标题是《Funnel: Assessing Software Changes in Web-based Services》，大概的内容是介绍软件更新给KPI（key performance indicator）指标的影响。下面将会详细介绍这篇文章的大概思想和技术框架。

 

本文是运维系统智能化的一次探索工作，论文的作者是清华大学的裴丹教授，论文的题目是《Opprentice: Towards Practical and Automatic Anomaly Detection Through Machine Learning》。目的是基于机器学习的 KPI（Key Performance Indicator）的自动化异常检测。

标题 Opprentice 来源于（Operator’s Apprentice），意思就是运维人员的学徒。本文通过运维人员的业务经验来进行异常数据的标注工作，使用时间序列的各种算法来提取特征，并且使用有监督学习模型（例如 Random Forest，GBDT，XgBoost 等）模型来实现离线训练和上线预测的功能。本文提到系统 Opprentice 使用了一个多月的历史数据进行分析和预测，已经可以做到准确率>=0.66，覆盖率>=0.66 的效果。

1. Opprentice的介绍

系统遇到的挑战：

Definition Challenges: it is difficult to precisely define anomalies in reality.（在现实环境下很难精确的给出异常的定义）

Detector Challenges: In order to provide a reasonable detection accuracy, selecting the most suitable detector requires both the algorithm expertise and the domain knowledge about the given service KPI (Key Performance Indicators). To address the definition challenge and the detector challenge, we advocate for using supervised machine learning techniques. （使用有监督学习的方法来解决这个问题）

该系统的优势：

(i) Opprentice is the first detection framework to apply machine learning to acquiring realistic anomaly definitions and automatically combining and tuning diverse detectors to satisfy operators’ accuracy preference.

(ii) Opprentice addresses a few challenges in applying machine learning to such a problem: labeling overhead, infrequent anomalies, class imbalance, and irrelevant and redundant features.

(iii) Opprentice can automatically satisfy or approximate a reasonable accuracy preference (recall>=0.66 & precision>=0.66). （准确率和覆盖率的效果）

2. 背景描述：

KPIs and KPI Anomalies:

KPIs: The KPI data are the time series data with the format of (time stamp, value). In this paper, Opprentice pays attention to three kinds of KPIs: the search page view (PV), which is the number of successfully served queries; The number of slow responses of search data centers (#SR); The 80th percentile of search response time (SRT).

Anomalies: KPI time series data can also present several unexpected patterns (e.g. jitters, slow ramp ups, sudden spikes and dips) in different severity levels, such as a sudden drop by 20% or 50%.

问题和目标：

覆盖率（recall）：# of true anomalous points detected / # of the anomalous points

准确率（precision）：# of true anomalous points detected / # of anomalous points detected

1-FDR（false discovery rate）：# of false anomalous points detected / # of anomalous points detected = 1 – precision

The quantitative goal of opprentice is precision>=0.66 and recall>=0.66.

The qualitative goal of opprentice is automatic enough so that the operators would not be involved in selecting and combining suitable detectors, or tuning them.

3. Opprentice Overview: （Opprentice系统的概况）

(i) Opprentice approaches the above problem through supervised machine learning.

(ii) Features of the data are the results of the detectors.（Basic Detectors 来计算出特征）

(iii) The labels of the data are from operators’ experience.（人工打标签）

(iv) Addressing Challenges in Machine Learning: （机器学习遇到的挑战）

(1) Label Overhead: Opprentice has a dedicated labeling tool with a simple and convenient interaction interface. （标签的获取）

(2) Incomplete Anomaly Cases:（异常情况的不完全信息）

(3) Class Imbalance Problem: （正负样本比例不均衡）

(4) Irrelevant and Redundant Features:（无关和多余的特征）

4. Opprentice’s Design:

Architecture: Operators label the data and numerous detectors functions are feature extractors for the data.

Label Tool:

人工使用鼠标和软件进行标注工作

Detectors:

(i) Detectors As Feature Extractors: （Detector用来提取特征）

Here for each parameter detector, we sample their parameters so that we can obtain several fixed detectors, and a detector with specific sampled parameters a (detector) configuration. Thus a configuration acts as a feature extractor:

data point + configuration (detector + sample parameters) -> feature,

(ii) Choosing Detectors: (Detector的选择，目前有14种较为常见的）

Opprentice can find suitable ones from broadly selected detectors, and achieve a relatively high accuracy. Here, we implement 14 widely-used detectors in Opprentice.

Opprentice has 14 widely-used detectors:

“Diff“: it simply measures anomaly severity using the differences between the current point and the point of last slot, the point of last day, and the point of last week.

“MA of diff“: it measures severity using the moving average of the difference between current point and the point of last slot.

The other 12 detectors come from previous literature. Among these detectors, there are two variants of detectors using MAD (Median Absolute Deviation) around the median, instead of the standard deviation around the mean, to measure anomaly severity.

(iii) Sampling Parameters: （Detector的参数选择方法，一种是扫描参数空间，另外一种是选择最佳的参数）

Two methods to sample the parameters of detectors.

(1) The first one is to sweep the parameter space. For example, in EWMA, we can choose to obtain 5 typical features from EWMA; Holt-Winters has three [0,1] valued parameters . To choose , we have features; In ARIMA, we can estimate their “best” parameters from the data, and generate only one set of parameters, or one configuration for each detector.

Supervised Machine Learning Models:

Decision Trees, logistic regression, linear support vector machines (SVMs), and naive Bayes. 下面是决策树（Decision Tree）的一个简单例子。

Random Forest is an ensemble classifier using many decision trees. It main principle is that a group of weak learners (e.g. individual decision trees) can together form a strong learner. To grow different trees, a random forest adds some elements or randomness. First, each tree is trained on subsets sampled from the original training set. Second, instead of evaluating all the features at each level, the trees only consider a random subset of the features each time. The random forest combines those trees by majority vote. The above properties of randomness and ensemble make random forest more robust to noises and perform better when faced with irrelevant and redundant features than decisions trees.

Configuring cThlds: （阈值的计算和预估）

(i) methods to select proper cThlds: offline part

We need to figure cThlds rather than using the default one (e.g. 0.5) for two reasons.

(1) First, when faced with imbalanced data (anomalous data points are much less frequent than normal ones in data sets), machine learning algorithems typically fail to identify the anomalies (low recall) if using the default cThlds (e.g. 0.5).

(2) Second, operators have their own preference regarding the precision and recall of anomaly detection.

The metric to evaluate the precision and recall are:

(1) F-Score: F-Score = 2*precision*recall/(precision+recall).

(2) SD(1,1): it selects the point with the shortest Euclidean distance to the upper right corner where the precision and the recall are both perfect.

(3) PC-Score: （本文中采用这种评估指标来选择合适的阈值）

If r>=R and p>=P, then PC-Score(r,p)=2*r*p/(r+p) + 1; else PC-Score(r,p)=2*r*p/(r+p). Here, R and P are from the operators’ preference “recall>=R and precision>=P”. Since the F-Score is no more than 1, then we can choose the cThld corresponding to the point with the largest PC-Score.

(ii) EWMA Based cThld Prediction: （基于EWMA方法的阈值预估算法）

In online detection, we need to predict cThlds for detecting future data.

Use EWMA to predict the cThld of the i-th week ( or the i-th test set) based on the historical best cThlds. Specially, EWMA works as follows:

If , then 5-fold prediction

Else , then +, where is the best cThld of the (i-1)-th week. is the predicted cThld of the i-th week, and also the one used for detecting the i-th week data. is the smoothing constant.

For the first week, we use 5-fold cross-validation to initialize . As increases, EWMA gives the recent best cThlds more influences in the prediction. We use in this paper.

5. Evaluation（系统评估）

在 Opprentice 系统中，红色表示 Opprentice 系统的方法，黑色表示其他额外的方法。

Opprentice has 14 detectors with about 9500 lines of Python, R and C++ code. The machine learning block is based on the scikit-learn library.

Random Forest is better than decision trees, logistic regression, linear support vector machines (SVMs), and naive Bayes.

 

本文作为智能运维系统的探索，这篇论文的标题是《Focus: Shedding Light on the High Search Response Time in the Wild》，来自于清华大学裴丹教授。目标是解决在运维过程中，发现高搜索响应时间之后，使用机器学习算法发现异常的原因和规则。该系统（Focus）使用过2.5个月的数据，并且分析过数十亿的日志。下面将会详细介绍这篇文章的主要内容。

问题描述：

To help search operators dubug HSRT (high search response time)，Focus is a search log analysis framework to answer the three questions:

(1) What is the HSRT condition?

(2) Which HSRT condition types are prevalent across days?

(3) How does each attribute affect SRT in those prevalent HSRT condition types?

解决方案：

Focus has one component for each of the above questions:

(1) A decision tree based classifier to identify HSRT conditions in search logs of each day;

(2) A clustering based condition type miner to combine similar HSRT conditions into one type, and find the prevalent condition types across days; following Occam’s razor principle.

(3) An attribute effect estimator to analyze the effect of each individual attribute of SRT within a prevalent condition type.

基础知识准备：

(A) Search Logs:

For each measured query, its search log records two types of data: SRT and SRT components, Query Attributes.

(1) SRT and SRT components:（特征层）

is when a query is submitted; is when the result HTML file has been downloaded; is when a brower finishes parsing the HTML; is when the page is completely rendered. SRT is measured by , the user-received search response time.

is the server response time of the HTML file, which is recorded by servers; is the network transmission time of the HTML file; is the browser parsing time of the HTML; is the remaining time spent before the page is rendered, e.g. download time of images from image servers.

(2) Query Attributes:（特征层）

The search logs record the following attributes for each measured query:

(i) Browser Engine: Webkit(e.g. Chrome, Safari and 360 Secure Browser), Gecko, Trident LEGC, Trident 4.0, Trident 5.0, and others.

(ii) ISP: China Telecom, China Unicom, China Mobile, China Netcom, CHina Tietong, others.

(iii) Localtion: Based on the client IP, convert IP to its geographic location. In total, there are 32 provinces.

(iv) #Image: the number of embedded images in the result page.

(v) Ads: A result page contains paid advertise links or not.

(vi) Loading Mode: The loading mode of a result page can be either synchronous or asynchronous.

(vii) Background page views: On the service side, the search engine S also post-analyzes the logs and generates the background page views. The background PVs (page views) for a query q is measured by the number of queries served within 30 seconds before and after q is served.It reflects the average search request load where q is served. Due to confidentiality constraints, we normalize specific background PVs (page Views) by the maximum value.（事后分析，统计出一些必要的特征，输入 Focus 系统的机器学习模型中）

(B) HSRT and HSRT Conditions:（样本层）

Usually, we can use cumulative distribution fraction (CDF) of SRT in the search logs to determine the high search response time condition (HSRT condition). In this paper,  we define HSRT as the SRT longer than 1s.

Challenges of Identifying HSRT Conditions: In order to identify HSRT conditions in multi-dimensional search logs.（以下是这个系统的一些难点和挑战点）

(a) Naive Single Dimensional Based Methods: including pair-wise correlation analysis and so on, but is inefficient.

(b) Attributes can be potentially interdependent on each other: that means Naive Bayes Method may not applicable in this situation.

(c) Need to avoid output overlapping conditions: like {#image>30}, {ads=yes}, and {#image>20, ads=yes}.  （随着时间的推移，每天使用模型可能会推出类似或者重复的规则）。

关键思想和系统概况

Condition is a combination of attributes and specific values in search logs.

HSRT Condition is a condition that covers at least 1%$ of total queries, and has the fraction of HSRT large than the global level:

(# of HSRT queries in a HSRT condition / #of queries in a HSRT condition) > (# of HSRT queries / # of queries). This is in order to assign to labels and we can change this definition in practice. （这只是用来打标签的定义，用于判断什么是HSRT，在实际的应用中，我们可以根据具体的场景采用不同的定义，例如返回码等指标）。

‘Focus’ System Overview:

Input: search logs（日志）

(i) Use a decision tree based classifier to identify HSRT conditions  in search logs every day; （每天可以使用决策树模型从日志中提取HSRT条件）。

(ii) Use a clustering based condition type miner to identify condition types of similar HSRT conditions, and fine prevalent condition types across days; （用于把类似的条件融合在一起）。

(iii) Use an attribute effect estimator to analyze how an attribute affects SRT and SRT components in each prevalent condition type. （用于判断哪些属性或者特征对这个标签影响更加深远）。

Output: prevalent condition types and their attributes effects on SRT.（第二步输出的条件以及第三步属性的重要性）。

Part (i): Decision Tree Based Classifier including ID3, C4.5, CART. It contains five important parts: (1) expressing attribute splits; (2) evaluate splits; (3) stopping tree growing; (4) assigning Labels: assign HSRT labels to the left nodes whose fraction of HSRT is larger than the global fraction of HSRT; (5) identify HSRT Branching Attribute Conditions. （这里是 Focus 系统所采用的机器学习算法）。

Part (ii): Condition Type Miner: group HSRT conditions according to (1) the same combination of attributes, (2) the same value from each category attribute, and (3) similar interval for each numeric attribute, using Jaccard Index to measure the similarity between intervals. （条件的融合）。

Part (iii): Attribute Effect Estimator: With each condition type

,

we design a method to understand how each attribute condition affects SRT.

For example, what is the HSRT fraction caused by in ? What SRT components (e.g. and ) are affected by ?

Main Idea: flip condition to the opposite to get a variant condition type . In the past days, we have the number of HSRT events in total, the number of HSRT events in condition and the number of HSRT events in condition . As a result, we believe the historical data based comparison can provide a reasonable estimate of the attribute effects. The comparison between and in these days is based on the specific HSRT conditions of these days. （用于判断哪些属性更能够引起 HSRT）。

In Table IV, the results are sorted by the variation of the fraction of HSRT in condition types (HSRT% column) caused by flipping an attribute condition.

(i) We highlight the variations greater than zero (getting worse after flipping an attribute condition).

(ii) We focus on that flipping the HSRT branching attribute conditions can yield improvements on HSRT%. For example, the condition #image>x are all ranked at the top. It means we need to reduce the impact of images on SRT and we can get the highest potential improvement of HSRT.

(iii) Table III and Table IV are the output of Focus to the operators for these months.

Observations by Further Inverstigation

Table IV raises some interesting questions:（通过 Focus 输出的表格 Table IV 可以提出很多其余的问题，也许是人工经验不容易发现的问题）

(1) Why does reducing #images increase , the time that servers prepare the result HTML (row 1, 2, 3, 4 of Table IV)?

(2) How do ads inflate SRT? Why do the pages with ads need more and (row 7)?

(3) Why does Webkit engine perform better, especially greatly decreasing (row 5, 10, 11, 12)?

(4) It is nature that switching ISPs can affect network transmission time , but why does switching to China Telecom reduce by over 20% (row 6, 8, 9)?