第一章 简介

对基于时序数据的应用而言，数据质量至关重要。UDF-Library基于 IoTDB 的用户自定义函数 (UDF)，实现了一系列关于数据质量的函数，包括数据画像、数据质量评估与修复等，有效满足了工业领域对数据质量的需求。

第二章 数据画像

2.1 Distinct

本函数可以返回输入序列中出现的所有不同的值。

2.1.1 具体算法

2.1.1.1 UDF 设置

• 类型： UDTF
• 数据消费策略：本函数利用 RowByRowAccessStrategy 的策略消费原始数据。
• 输入序列：将索引为 0 的序列作为输入。
• 输出序列：一个与输入类型相同的序列。

2.1.1.2 非重复值计算

维护一个 HashSet，将所有数据都加入其中。之后，遍历这个集合，输出其中的所有元素。为了降低拆装箱的开销，利用第三方库 org.eclipse.collections 中的 IntHashSet 等来代替标准库中的HashSet。

2.1.2 复杂度分析

假设时间序列长度为 n，其中不同的值共有 m 个。那么，UDF 的时间复杂度为 O(n+m)，空间复杂度为 O(m)。

2.2 Histogram

本函数用于计算时间序列的时间加权平均值。

2.2.1 具体算法

2.2.1.1 UDF 设置

• 类型： UDTF
• 数据消费策略：本函数利用 RowByRowAccessStrategy 的策略消费原始数据。
• 输入序列：将索引为 0 的序列作为输入。
• 输出序列：一个 Int 类型的序列，表示直方图分桶的值。

2.2.1.2 直方图计算

根据输入的参数 start、end 和 count，我们进行线性分桶。对每一个输入数据 x，都可以利用下式计算它属于哪一个桶并将该桶的计数加一：

2.2.2 复杂度分析

假设时间序列长度为 n，直方图中桶的数目为 m。那么，UDF 的时间复杂度为 O(n+m)，空间复杂度为 O(m)。

2.3 Intergral

本函数用于计算时间序列的数值积分。

2.3.1 具体算法

2.3.1.1 UDF 设置

• 类型： UDAF
• 数据消费策略：本函数利用 RowByRowAccessStrategy 的策略消费原始数据。
• 输入序列：将索引为 0 的序列作为输入。
• 输出序列：一个 Double 类型的序列，仅包含一个数据点，时间戳为 0，值为数值积分。

2.3.1.2 数值积分计算

利用梯形法计算数值积分。数值积分 Si 可以按照下式递推计算：

其中，unit 是用户输入的时间轴单位包含的毫秒数（例如，当时间轴单位为 1s 时，unit =1000）。

2.3.2 复杂度分析

假设时间序列长度为 n。那么，UDF 的时间复杂度为 O(n)，空间复杂度为 O(1)。

2.4 IntegralAvg(TimeWeightedAverage)

本函数用于计算时间序列的时间加权平均值。

2.4.1 具体算法

2.4.1.1 UDF 设置

• 类型： UDAF
• 数据消费策略：本函数利用 RowByRowAccessStrategy 的策略消费原始数据。
• 输入序列：将索引为 0 的序列作为输入。
• 输出序列：一个 Double 类型的序列，仅包含一个数据点，时间戳为 0，值为时间加权平均值。

2.4.1.2 时间加权平均值计算

利用梯形法计算数值积分，再用整体的积分值除以序列的时间跨度。数值积分 Sn 可以按照2.3.1.2公式递推计算, 计算完成后利用以下公式求取时间加权平均值：

时间加权平均值结果与具体使用的时间轴单位无关，因此算法中固定取 unit = 1。

2.4.2 复杂度分析

本函数的时间复杂度与Integral相同，同为逐个遍历数据点与时间戳，故同为O(n)；空间复杂度相较Integral需额外记录首尾时间错，因此为O(1)

2.5 Mad

本函数用于计算时间序列的绝对中位差。

2.5.1 具体算法

2.5.1.1 UDF 设置

• 类型： UDAF
• 数据消费策略：本函数利用 RowByRowAccessStrategy 的策略消费原始数据。
• 输入序列：将索引为 0 的序列作为输入。
• 输出序列：一个 Double 类型的序列，仅包含一个数据点，时间戳为 0，值为绝对中位差。

2.5.1.2 精确算法

时间序列 x 的绝对中位差定义为下式：

MAD(x) = Median(|x − Median(x)|)

因此，我们需要先计算序列 x 的中位数，再计算 x 中的每一个值与它的距离，生成新的序列，再计算新的序列的中位数作为绝对中位差。

为了降低拆装箱的开销，我们利用第三方库 org.eclipse.collections 中的 IntArrayList等来保存时间序列。中位数的快速算法见章节2.6.1.2。

2.5.1.3 近似算法

2.5.2 复杂度分析

假设时间序列长度为 n。那么，对精确算法而言，时间复杂度为 O(n)，空间复杂度为 O(n)。

2.6 Median

本函数用于计算时间序列的中位数。

2.6.1 具体算法

2.6.1.1 UDF 设置

• 类型： UDAF
• 数据消费策略：本函数利用 RowByRowAccessStrategy 的策略消费原始数据。
• 输入序列：将索引为 0 的序列作为输入。
• 输出序列：一个 Double 类型的序列，仅包含一个数据点，时间戳为 0，值为中位数。

2.6.1.2 排序算法

由于枢轴交换法对极端情况，如存在大量重复数据或逆序排列数据，效率极低。因此本方法先采用Java内置的排序算法对数据排序，然后取出中位数。

2.6.1.3 精确算法

时间序列 x 的中位数定义为下式：

其中，n 是 x 的长度，x˜ 是 x 升序排序后的序列。我们使用章节2.6.1.2中的算法来具体计算中位数。为了降低拆装箱的开销，我们利用第三方库 org.eclipse.collections 中的 LongArrayList 等来保存时间序列。

2.6.1.4 近似算法

2.6.2 复杂度分析

假设时间序列长度为 n。那么，对精确算法而言，时间复杂度为 O(n)，空间复杂度为 O(n)。

2.7 Mode

本函数用于计算时间序列的众数，即出现次数最多的元素。

2.7.1 具体算法

2.7.1.1 UDF 设置

• 类型： UDAF
• 数据消费策略：本函数利用 RowByRowAccessStrategy 的策略消费原始数据。
• 输入序列：将索引为 0 的序列作为输入。
• 输出序列：一个与输入类型相同的序列，只包含一个时间戳为 0、值为众数的数据。

2.7.1.2 众数计算

维护一个 HashMap，遍历输入序列，统计每一个不同元素出现的次数。之后，遍历这个 Map，找到出现次数最多的元素并输出。为了降低拆装箱的开销，利用第三方库 org.eclipse.collections 中的 IntIntHashMap 等来代替标准库中的 HashMap。

2.7.2 复杂度分析

假设时间序列长度为 n，其中不同的值共有 m 个。那么，UDF 的时间复杂度为 O(n+m)，空间复杂度为 O(m)。

2.8 Percentile

本函数用于计算时间序列的分位数。

2.8.1 具体算法

2.8.1.1 UDF 设置

• 类型： UDAF
• 数据消费策略：本函数利用 RowByRowAccessStrategy 的策略消费原始数据。
• 输入序列：将索引为 0 的序列作为输入。
• 输出序列：一个 Double 类型的序列，仅包含一个数据点，时间戳为 0，值为分位数。

2.8.1.2 精确算法

长度为 n 的时间序列 x 的 r 分位数是 x 升序排序后的第 ⌈nr⌉ 个元素。该问题的算法见章节2.6.1.2。为了降低拆装箱的开销，我们利用第三方库 org.eclipse.collections中的 LongArrayList 等来保存时间序列。

2.8.1.3 近似算法

【本方法对相似数据压缩，实现细节有待补充】

2.8.2 复杂度分析

假设时间序列长度为 n。那么，对精确算法而言，时间复杂度为 O(n)，空间复杂度为 O(n)。

2.9 Resample

本函数对输入序列按照指定的频率进行重采样，包括上采样和下采样。目前，本函数 支持的上采样方法包括 NaN 填充法 (NaN)、前值填充法 (FFill)、后值填充法 (BFill) 以及 线性插值法 (Linear);本函数支持的下采样方法为分组聚合，聚合方法包括最大值 (Max)、 最小值 (Min)、首值 (First)、末值 (Last)、平均值 (Mean) 和中位数 (Median)。

2.9.1 具体算法

2.9.1.1 UDF 设置

• 类型： UDTF
• 数据消费策略：本函数利用 RowByRowAccessStrategy 的策略消费原始数据。
• 输入序列：将索引为 0 的序列作为输入。
• 输出序列：一个 Double 类型的序列。该序列按照重采样频率严格等间隔分布。

2.9.1.2 算法概览

算法维护三个结构：一是存放当前窗口内数据用于下采样的 window，基于可变数组；二是用于插值的数据源 source，基于循环队列；三是等待被插值的时间戳列表 waitlist，基于循环队列。

下采样：对数据流中的每一个数据点，都将其放入 window 中。如果当前数据点的时间戳已经超过了 window 的时间范围，应当对 window 进行聚合操作。数据预备：此时，如果 window 中的数据点个数大于等于 2，则将聚合结果（以 window的起始时刻为时间戳，聚合值为值，该数据点需要被输出）加入 source；如果数据点个数为 1，则将该原始点（不输出）加入 source, window 起始时刻加入 waitlist （如果两者时间戳相等，则不需要加入 waitlist，直接将原始点输出即可）；如果数据点个数为 0，则将window 起始时刻加入 waitlist。

上采样：根据 source 中的数据点，将 waitlist 中的时间戳进行插值填补并输出。此时，需要注意输出顺序。

2.9.2 复杂度分析

假设时间序列长度为 n，一个窗口内最多存在 w 个数据点（一般而言，w ≪ n）。那么，对精确算法而言，时间复杂度为 O(n)，空间复杂度为 O(w)。

2.10 Sample

本函数对输入序列进行采样，即从输入序列中选取指定数量的数据点并输出。

2.10.1 具体算法

2.10.1.1 UDF 设置

• 类型： UDTF
• 数据消费策略：在使用等距采样时，本函数利用 SlidingSizeWindowAccessStrategy的策略消费原始数据，并将窗口大小设置为MAX_VALUE 以操纵全部数据；在使用蓄水池采样时，本函数利用 RowByRowAccessStrategy 的策略消费原始数据。
• 输入序列：将索引为 0 的序列作为输入。
• 输出序列：一个与输入类型相同的序列，是输入的子序列。

2.10.1.2 等距采样

利用 SlidingSizeWindowAccessStrategy 的策略和无穷大的窗口，我们可以通过索引随机访问输入序列的任何一个数据点。假设输入序列长度为 n，采样数为 k。当 k ≥ n 时，我们将整个输入序列作为输出序列；当 k < n 时，我们采样索引为下列值的数据点：

⌊i × n / k⌋, i ∈ [0, k)

2.10.1.3 蓄水池采样

假设输入序列长度为 n，采样数为 k。蓄水池采样算法维护一个长度为 k 的蓄水池，遍历输入序列的全部数据点，当访问到第 i 个数据点时（i 从 0 开始），采用如下的算法：

1. 如果 i < k，则将该数据点放入蓄水池；
2. 否则，在 [0, i] 范围内取随机数 d，当 d ∈ [0, k − 1] 时，用第 i 个数据点替换蓄水池中的第 d 个数据。

最后，蓄水池中的数据就是采样得到的数据。由于其中的数据不一定有序，我们需要先对其排序再输出。

2.10.2 复杂度分析

假设输入序列长度为 n，采样数为 k。对等距采样而言，时间复杂度为 O(k)，空间复杂度为 O(1)；对蓄水池采样而言，时间复杂度为 O(n + k log2 k)，空间复杂度为 O(k)。

2.11 Skew

本函数用于计算时间序列的总体偏度，即三阶标准中心矩。

2.11.1 具体算法

2.11.1.1 UDF 设置

• 类型： UDAF
• 数据消费策略：本函数利用 RowByRowAccessStrategy 的策略消费原始数据。
• 输入序列：将索引为 0 的序列作为输入。
• 输出序列：一个 Double 类型的序列，只包含一个时间戳为 0、值为总体偏度的数据。

2.11.1.2 偏度计算

遍历输入序列，维护 以及样本总数。最后，使用下面的偏度公式得到总体偏度。

2.11.2 复杂度分析

假设时间序列长度为 n，那么，UDF 的时间复杂度为 O(n)，空间复杂度为 O(1)。

2.12 Spread

本函数用于计算时间序列的极差，即最大值减去最小值的结果。

2.12.1 具体算法

2.12.1.1 UDF 设置

• 类型： UDAF
• 数据消费策略：本函数利用 RowByRowAccessStrategy 的策略消费原始数据。
• 输入序列：将索引为 0 的序列作为输入。
• 输出序列：一个与输入类型相同的序列，只包含一个时间戳为 0、值为极差的数据。

2.12.1.2 极差计算

遍历输入序列，维护当前的最大最小值。最后，输出最大值与最小值的差。

2.12.2 复杂度分析

假设时间序列长度为 n，那么，UDF 的时间复杂度为 O(n)，空间复杂度为 O(1)。

2.13 Stddev

本函数用于计算时间序列的总体标准差，即下式:

2.13.1 具体算法

2.13.1.1 UDF 设置

• 类型： UDAF
• 数据消费策略：本函数利用 RowByRowAccessStrategy 的策略消费原始数据。
• 输入序列：将索引为 0 的序列作为输入。
• 输出序列：一个 Double 类型的序列，只包含一个时间戳为 0、值为总体标准差的数据。

2.13.1.2 标准差计算

遍历输入序列 x，按照下面的公式递推计算均值 µi 和总体方差：

最后，对总体方差开平方，即可得到总体标准差。

2.13.2 复杂度分析

假设时间序列长度为 n，那么，UDF 的时间复杂度为 O(n)，空间复杂度为 O(1)。

2.14 MvAvg

本函数用于计算指定长度的滑动窗口内均值。

2.14.1 具体算法

2.14.1.1 UDF 设置

• 类型： UDTF
• 数据消费策略：本函数利用 RowByRowAccessStrategy 的策略消费原始数据。
• 输入序列：将索引为 0 的序列作为输入。
• 输出序列：一个 Double 类型的序列，每个输出点的时间戳为窗口中最后一个值的队列。

2.14.1.2 滑动平均计算

维护一个指定长度的循环队列，该队列长度为窗口长度 +1. 在队列进行插入或删除操作时自动维护队列和与队列长度，从而求得窗口内的滑动平均。

2.14.2 复杂度分析

函数的时间复杂度是O(n)，空间复杂度是O(window)

2.15 QLB

本函数用于计算序列的 Ljung-Box Q 统计量。

2.15.1 具体算法

2.15.1.1 UDF 设置

• 类型： UDTF
• 数据消费策略：本函数利用 RowByRowAccessStrategy 的策略消费原始数据。读取完整序列。
• 输入序列：将索引为 0 的序列作为输入。
• 输出序列：一个 Double 类型的序列，输出结果为统计量对应的 p 值。每个输出点的时间戳与 QLB 统计量的滞后阶数对应。默认计算 1 至 n − 2 阶的值。

2.15.1.2 QLB 统计量计算

式中的表示 l 阶自相关系数。N 表示序列长度。求得统计量后换算为对应卡方分布的p 值。

2.15.2 复杂度分析

本方法的复杂度与ACF相同。

2.16 PACF

本函数用于计算序列的偏自相关系数。

2.16.1 具体算法

2.16.1.1 UDF 设置

• 类型： UDTF
• 数据消费策略：本函数利用 RowByRowAccessStrategy 的策略消费原始数据。读取完整序列。
• 输入序列：将索引为 0 的序列作为输入。默认输入序列为等时间间隔。
• 输出序列：一个 Double 类型的序列，每个输出点的时间戳与偏自相关系数的滞后阶数对应。

2.16.1.2 PACF 计算

算法采用逐阶求解 Yule-Walker 方程的方法得到偏自相关系数。该方法与最小二乘法得到的结果相同。关于 Yule-Walker 方程的描述，可参见这里，或其它有关时间序列分析的教材。

2.16.2 复杂度分析

由于Yule-Walker方程是线性方程组，因此求解复杂度与求解器解方程的复杂度一致，可以认为复杂度是O(n^3)，n是方程组未知数的个数，在这里等同于迟滞阶数。

2.17 MinMax

本函数使用 Min-Max 方法将数据归一至 [0, 1] 区间。

2.17.1 具体算法

2.17.1.1 UDF 设置

• 类型： UDTF
• 数据消费策略：本函数利用 RowByRowAccessStrategy 的策略消费原始数据。若未提供最大最小值，则读取完整序列。
• 输入序列：将索引为 0 的序列作为输入。
• 输出序列：一个 Double 类型的序列。

2.17.2 复杂度分析

当提供最大最小值时，本函数逐个处理每个数据点，因此时间复杂度是O(n)，空间复杂度是O(1)

当未提供最大最小值时，函数额外寻找最大最小值，时间复杂度仍为O(n)，空间复杂度增加至O(n)

2.18 ZScore

本函数使用 z-score 方法将数据标准化。

2.18.1 具体算法

2.18.1.1 UDF 设置

• 类型： UDTF
• 数据消费策略：本函数利用 RowByRowAccessStrategy 的策略消费原始数据。若未提供均值和标准差，则读取完整序列。
• 输入序列：将索引为 0 的序列作为输入。
• 输出序列：一个 Double 类型的序列。

2.18.2 均值和方差的计算

计算方法与使用的流式方法相同。

2.18.3 复杂度分析

当提供均值与标准差时，本函数逐个处理每个数据点，因此时间复杂度是O(n)，空间复杂度是O(1)

当未提供均值与标准差时，函数额外计算均值标准差，时间复杂度仍为O(n)，空间复杂度增加至O(n)

2.19 Segment

本函数将原始数据按线性变化趋势分割为数个片段。

2.19.1 具体算法

2.19.1.1 UDF 设置

• 类型： UDTF
• 数据消费策略：本函数利用 RowByRowAccessStrategy 的策略消费原始数据。读取完整序列。
• 输入序列：将索引为 0 的序列作为输入。默认时间戳间隔相等。
• 输出序列：一个 Double 类型的序列。

2.19.1.2 片段切割

本函数采用自底向上的分割方法，即首先将相邻的 2 个数据点视为同一片段，然后逐个比较每两个相邻片段合并为一个片段的代价（均方误差），选择代价最小的相邻片段合并；重复执行直至代价超过设定阈值或不可继续合并。常见的切割方法还有自顶向下法等。

2.19.2 复杂度分析

每次合并后，需计算合并片段与相邻片段再次合并的代价。假设起始共有n个数据点，那么总计计算了n/2次代价；至多发生n/2-1次合并，需计算约n次合并代价。合并代价的复杂度与Pearson函数相同，与区间片段长度有关。每次计算额外合并代价的总片段长度不超过2n，因此时间复杂度保证在O(n^3)。

2.20 Spline

本函数将原始数据进行三次样条曲线拟合，并等间隔输出插值结果。

2.20.1 具体算法

2.20.1.1 UDF 设置

• 类型： UDTF
• 数据消费策略：本函数利用 RowByRowAccessStrategy 的策略消费原始数据。读取完整序列。
• 输入序列：将索引为 0 的序列作为输入。
• 输出序列：一个 Double 类型的序列。

2.20.1.2 插值算法

本函数调用org.apache.commons.math3.analysis.interpolation.AkimaSplineInterpolator，polynomials.PolynomialSplineFunction完成拟合与插值。

2.20.2 复杂度分析

假设共提供n个样本点，三次样条插值需要求解n元线性方程组，对应的时间复杂度是O(n^3)。

2.21 Period

本函数计算给定序列的周期。

2.21.1 具体算法

2.21.1.1 UDF 设置

• 类型： UDTF
• 数据消费策略：本函数利用SlidingSizeWindowAccessStrategy 的策略，取最大可能的窗口长度消费原始数据。
• 输入序列：将索引为 0 的序列作为输入。
• 输出序列：一个 INT32 类型的点。

2.21.1.2 具体算法

本函数首先求序列的自相关系数，得到一个新的序列；再从这个新的序列中寻找峰值的位置，计算相邻峰位置之间的间隔；这些间隔取中位数作为最终得到的周期。

对于良好周期性的序列，算法可以准确地得到周期；对于周期为非整数的序列，使用中位数计算近似的周期；对于周期性不佳的序列，输出结果没有意义。

2.21.2 复杂度分析

算法的主要时间复杂度在于计算序列的自相关系数。假设序列共有n个数据点，那么共计算n阶的自相关系数；如果每次重叠部分共m个数据点，那么每次计算的时间复杂度是O(m)；因此总时间复杂度保持在O(n^2)。

算法读取所有数据，空间复杂度为O(n)。

2.22 ACF

本函数计算给定序列的自相关系数。

2.22.1 具体算法

2.22.1.1 UDF 设置

• 类型： UDTF
• 数据消费策略：本函数利用 RowByRowAccessStrategy 的策略，取最大可能的窗口长度消费原始数据。
• 输入序列：将索引为 0 的序列作为输入。
• 输出序列：一个 DOUBLE 类型的序列。

2.22.1.2 具体算法

n阶自相关系数就是序列S(t)与序列S(t-n)之间的相关系数。相关系数的计算可以参见Pearson函数。

2.22.2 复杂度分析

由相关系数的时间复杂度乘以相关系数的计算次数，可知总时间复杂度保证在O(n^2)。

算法读取所有数据，空间复杂度为O(n)。

第三章 数据质量

3.1 Completeness

本函数用于计算时间序列的完整性。将输入序列划分为若干个连续且不重叠的窗口，分别计算每一个窗口的完整性，并输出窗口第一个数据点的时间戳和窗口的完整性。

3.1.1 主要思想

完整性包含数据丢失异常、空值异常和特殊值异常，采用如下的公式计算：

Completeness = 1 − (Nnull + Nspecial + Nmiss)/(N + Nmiss)

其中，N 是时间序列总的数据点数目，Nnull 是时间序列中值为空的数据点数目，Nspecial是时间序列中值为特殊值的数据点数目，Nmiss 是时间序列中丢失的数据点数目。

3.1.2 具体算法

3.1.2.1 UDF 设置

• 类型： UDTF
• 数据消费策略：本函数利用 SlidingSizeWindowAccessStrategy 的策略基于滚动窗口消费原始数据。窗口的大小由用户作为参数输入。在用户没有输入参数时，所有的数据都被作为一个窗口处理，因此窗口大小设为MAX_VALUE。
• 输入序列：将索引为 0 的序列作为输入。当该序列不是数值类型时，抛出 NoNumberException。
• 输出序列：一个 DOUBLE 类型的序列，每一个滚动窗口对应于一个数据点。

3.1.2.2 数据预处理

如果输入数据点的值是 null，那么就是一个空值异常；如果输入数据点的值是 NaN、INF 等非有限值，那么就是一个特殊值异常。在数据预处理时，遍历所有的输入数据点，就可以统计空值和特殊值异常出现的次数。对所有的空值和特殊值，都采用线性插值的方式进行修正。

3.1.2.3 时间戳异常检测

时间戳异常包括数据丢失异常（完整性）、数据过密异常（一致性）和数据延迟异常（有效性），关注于相邻数据点的时间间隔。在异常检测时，我们以经过预处理的数据为基础，将时间间隔的中位数作为基准，并维护一个滑动窗口（窗口大小为 10），统计各种异常出现的次数。

当窗口内前两个数据点的时间间隔为基准的 0.5 倍以内时，出现了过密点，我们认为出现了数据过密异常，应当删除第二个数据点。当时间间隔为基准的 2-9 倍时（9 倍以上认为是停机），出现了缺失点，可能发生了数据丢失异常或者数据延迟异常（数据点向后移动了一小段距离，作为过密点存在）。因此，我们在窗口内向后继续寻找过密点：每发现一个过密点，我们将其移回到缺失点处，认为出现了一个数据延迟异常。只有当过密点的数量足够填补前面的缺失点，或者发现新的缺失点，或者已经遍历了整个窗口，寻找过密点的工作才会结束。此时，尚未被填补的缺失点会被认为是数据丢失异常。

3.1.2.4 完整性计算

章节3.1.2.2和章节3.1.2.3讲述了如何统计数据丢失异常、空值异常和特殊值异常的出现次数。根据完整性计算公式 (3.1)，我们可以具体计算时间序列的完整性。

3.1.3 复杂度分析

假设输入序列划分成的窗口大小为 w，输入数据点数目为 n。那么，对每一个窗口，计算完整性的时间复杂度为 O(w)，空间复杂度为 O(w)；对所有数据而言，计算完整性的时间复杂度为O(n)，空间复杂度为 O(w)。

3.2 Consistency

本函数用于计算时间序列的一致性。将输入序列划分为若干个连续且不重叠的窗口，分别计算每一个窗口的一致性，并输出窗口第一个数据点的时间戳和窗口的一致性。

3.2.1 主要思想

一致性包含数据过密异常，采用如下的公式计算：

Consistency = 1 − Nredundancy/N

其中，N 是时间序列总的数据点数目，Nredundancy 是时间序列中过密的数据点数目。

3.2.2 具体算法

3.2.2.1 UDF 设置

• 类型： UDTF
• 数据消费策略：本函数利用 SlidingSizeWindowAccessStrategy 的策略基于滚动窗口消费原始数据。窗口的大小由用户作为参数输入。在用户没有输入参数时，所有的数据都被作为一个窗口处理，因此窗口大小设为MAX_VALUE。
• 输入序列：将索引为 0 的序列作为输入。当该序列不是数值类型时，抛出 NoNumberException。
• 输出序列：一个 DOUBLE 类型的序列，每一个滚动窗口对应于一个数据点。

3.2.2.2 一致性计算

章节3.1.2.2讲述了如何对数据进行预处理，章节3.1.2.3讲述了如何统计数据过密异常的出现次数。根据一致性计算公式 (3.2)，我们可以具体计算时间序列的一致性。

3.2.3 复杂度分析

假设输入序列划分成的窗口大小为 w，输入数据点数目为 n。那么，对每一个窗口，计算一致性的时间复杂度为 O(w)，空间复杂度为 O(w)；对所有数据而言，计算一致性的时间复杂度为O(n)，空间复杂度为 O(w)。

3.3 Timeliness

本函数用于计算时间序列的时效性。将输入序列划分为若干个连续且不重叠的窗口，分别计算每一个窗口的时效性，并输出窗口第一个数据点的时间戳和窗口的时效性。

3.3.1 主要思想

时效性包含数据延迟异常，采用如下的公式计算：

Timeliness = 1 − Nlate/N

其中，N 是时间序列总的数据点数目，Nlate 是时间序列中延迟的数据点数目。

3.3.2 具体算法

3.3.2.1 UDF 设置

• 类型： UDTF
• 数据消费策略：本函数利用 SlidingSizeWindowAccessStrategy 的策略基于滚动窗口消费原始数据。窗口的大小由用户作为参数输入。在用户没有输入参数时，所有的数据都被作为一个窗口处理，因此窗口大小设为MAX_VALUE。
• 输入序列：将索引为 0 的序列作为输入。当该序列不是数值类型时，抛出 NoNumberException。
• 输出序列：一个 DOUBLE 类型的序列，每一个滚动窗口对应于一个数据点。

3.3.2.2 时效性计算

章节3.1.2.2讲述了如何对数据进行预处理，章节3.1.2.3讲述了如何统计数据延迟异常的出现次数。根据时效性计算公式 (3.3)，我们可以具体计算时间序列的时效性。

3.3.3 复杂度分析

假设输入序列划分成的窗口大小为 w，输入数据点数目为 n。那么，对每一个窗口，计算时效性的时间复杂度为 O(w)，空间复杂度为 O(w)；对所有数据而言，计算时效性的时间复杂度为O(n)，空间复杂度为 O(w)。

3.4 Validity

本函数用于计算时间序列的有效性。将输入序列划分为若干个连续且不重叠的窗口，分别计算每一个窗口的有效性，并输出窗口第一个数据点的时间戳和窗口的有效性。

3.4.1 主要思想

有效性包含取值范围异常、取值变化范围异常、速度范围异常和速度变化范围异常，采用如下的公式计算：

Validity = 1 − (Nvalue + Nvariation + Nspeed + Nspeedchange)/(4 ∗ N)

其中，N 是时间序列总的数据点数目，Nvalue 是违反取值范围约束的数据点数目，Nvariation是违反取值变化约束的数据点数目，Nspeed 是违反速度约束的数据点数目，Nspeedchange是违反速度变化约束的数据点数目（同一个数据点可能违反多项约束）。

3.4.2 具体算法

3.4.2.1 UDF 设置

• 类型： UDTF
• 数据消费策略：本函数利用 SlidingSizeWindowAccessStrategy 的策略基于滚动窗口消费原始数据。窗口的大小由用户作为参数输入。在用户没有输入参数时，所有的数据都被作为一个窗口处理，因此窗口大小设为MAX_VALUE。
• 输入序列：将索引为 0 的序列作为输入。当该序列不是数值类型时，抛出 NoNumberException。
• 输出序列：一个 DOUBLE 类型的序列，每一个滚动窗口对应于一个数据点。

3.4.2.2 有效性计算

章节3.1.2.2讲述了如何对数据进行预处理。基于预处理后的原始数据 value 和它的时间戳 time，可以计算它的变化 variation、速度 speed 以及速度变化 speedchange：

variationi = valuei+1 − valuei
speedi = (valuei+1 − valuei)/(timei+1 − timei)
speedchangei = speedi+1 − speedi

对序列 x，当 xi 与其中位数的偏差超过了三倍绝对中位差（为了达到渐进正态性，乘上比例因子 1.4826）时，称作违背约束，即

|xi − mid(x)| > 3 ∗ mad(x)

遍历上述的原始数据 value、变化 variation、速度 speed 以及速度变化 speedchange四个序列，可以统计每个序列中违背约束的数据点个数。根据有效性计算公式 (3.4)，我们可以具体计算时间序列的有效性。

3.4.3 复杂度分析

假设输入序列划分成的窗口大小为 w，输入数据点数目为 n。那么，对每一个窗口，计算有效性的时间复杂度为 O(w)，空间复杂度为 O(w)；对所有数据而言，计算有效性的时间复杂度为O(n)，空间复杂度为 O(w)。

第四章 数据修复

4.1 ValueFill

本函数用于填补序列中的NaN值。

4.1.1 主要思想

在时间序列中，由于传感器出错等各种原因，部分值在序列中表现为NaN。目前，本函数支持以下填补方法：

1. AR 自回归模型；
2. MA 移动平均模型；
3. linear 线性回归模型；
4. mean 均值填补；
5. previous 前值填补；
6. likelihood 基于速度正态分布的极大似然填补；
7. screen 速度约束填补；

4.1.2 具体算法

4.1.2.1 UDF 设置

• 类型： UDTF
• 数据消费策略：本函数利用SlidingSizeWindowAccessStrategy 的策略消费原始数据，并将窗口大小设置为MAX_VALUE 以操纵全部数据。
• 输入序列：将索引为 0 的序列作为输入。
• 输出序列：一个与输入类型相同的序列，是输入修复后的结果。

4.1.2.2 AR与MA

ARMA模型可以参考任意时间序列分析教材。其中MA算法可以参考MvAvg函数。对于AR模型，函数拟合整条序列的值，并按照模型预测值填补。

4.1.2.3 likelihood

本方法假设数据的速度分布满足正态分布，使填补后在填补值前后的速度满足分布上的极大似然。

4.1.2.4 screen

本方法可参考ValueRepair函数中的Screen方法。

4.2 TimestampRepair

本函数用于对时间序列的时间戳进行修复。

4.2.1 主要思想

在时间序列中，由于传感器出错等各种原因，可能存在不正常的时间戳。通常认为正确的时间戳是等间隔排列的。本函数试图以最小调整时间戳的代价修复时间戳。目前，本函数支持以下寻找等间隔序列的方法：

1. median 以中位数作为准确间隔；
2. mode 以众数作为准确间隔；
3. cluster 以聚类中心推断准确间隔。

4.2.2 具体算法

4.2.2.1 UDF 设置

• 类型： UDTF
• 数据消费策略：本函数利用 RowByRowAccessStrategy 的策略消费原始数据，并一次读取全部数据。
• 输入序列：将索引为 0 的序列作为输入。
• 输出序列：一个与输入类型相同的序列，是输入修复后的结果。

4.2.2.2 median与mode

普通的计算中位数或众数的算法。可以参考median和mode函数。

4.2.2.3 cluster

当传感器极不稳定，单个点在正确时间附近有偏差，且经常漏过时间戳导致一些时间间隔是正确间隔的倍数左右时，使用本方法可以确定正确时间间隔。当前函数固定聚类中心共3个，起始聚类中心位置分别在最大值、最小值、中位数。随后逐个依数据点更新聚类中心。

4.2.2.4 时间戳修复

依据确定的时间戳间隔，函数采用线性拟合的办法，确定最近的正确数据点。

4.2.3 复杂度分析

假设输入序列长度为 n。函数的主要时间开销是线性回归过程，复杂度为O(n^3)。

4.3 ValueRepair

本函数用于对时间序列的数值进行修复。

4.3.1 主要思想

在时间序列中，由于传感器出错等各种原因，可能存在错误的数值。因此，我们需要对时间序列进行数值修复。目前，本函数支持下面的修复方法：

1. Screen 是一种基于速度阈值的方法，在最小改动的前提下使得所有的速度符合阈值要求；
2. LsGreedy 是一种基于速度变化似然的方法，将速度变化建模为高斯分布，并采用贪心算法极大化似然函数。

4.3.2 具体算法

4.3.2.1 UDF 设置

• 类型： UDTF
• 数据消费策略：本函数利用 SlidingSizeWindowAccessStrategy 的策略消费原始数据，并将窗口大小设置为MAX_VALUE 以操纵全部数据。
• 输入序列：将索引为 0 的序列作为输入。
• 输出序列：一个与输入类型相同的序列，是输入修复后的结果。

4.3.2.2 Screen

Screen 方法 [2] 是一种基于速度阈值的修复方法。它的核心思想是，在修改尽可能少的数据点的前提下，使整个时间序列的速度都不超过阈值。由于考虑全局约束的算法复杂度过大，这里将约束放松到一个滑动窗口（窗口大小 w 固定为 5 倍的时间间隔中位数）内，结合候选范围与中位原则确定合适的修复方案。

本算法的伪代码：

4.3.2.3 LsGreedy

LsGreedy 方法 [3] 是一种基于速度变化似然的修复方法。它的核心思想是，对速度变化分布进行建模，并找到使似然函数最大化的修复方案。一般地，模型可以被视作高斯模型。为了降低运算复杂度，这里采用贪心算法寻找较优的修复方案。减小速度变化与中心的偏移可以增大似然函数。利用大根堆维护序列的速度变化，找到与高斯分布中心偏移最大的，并对其进行调整，使其更加接近中心。当所有的速度变化与中心的偏移都小于 3 倍标准差时，贪心算法终止。

本算法的伪代码：

4.3.3 复杂度分析

假设输入序列长度为 n。那么，Screen 方法的时间复杂度为 O(n)，空间复杂度为O(n)；LsGreedy 方法的时间复杂度为 O(n log2 n)，空间复杂度为 O(n)。

第五章 数据匹配

5.1 Cov

本函数用于计算两个时间序列之间的总体协方差，即下式：

5.1.1 具体算法

5.1.1.1 UDF 设置

• 类型： UDTF
• 数据消费策略：本函数利用 RowByRowAccessStrategy 的策略消费原始数据。
• 输入序列：将索引为 0 和 1 的序列作为输入。
• 输出序列：一个 Double 类型的序列，只包含一个时间戳为 0、值为总体协方差的数据。

5.1.1.2 协方差计算

遍历输入序列 x，递推计算。最后，按照下式计算协方差：

5.1.2 复杂度分析

假设时间序列长度为 n，那么，UDF 的时间复杂度为 O(n)，空间复杂度为 O(1)。

5.2 DTW

本函数计算两个时间序列的DTW距离

5.1.1 具体算法

5.1.1.1 UDF 设置

• 类型： UDTF
• 数据消费策略：本函数利用 RowByRowAccessStrategy 的策略消费原始数据。
• 输入序列：将索引为 0 和 1 的序列作为输入。
• 输出序列：一个 Double 类型的序列，只包含一个时间戳为 0、值为总体协方差的数据。

5.1.1.2 DTW计算

DTW计算使用动态规划方法。

5.1.2 复杂度分析

假设时间序列长度为 n，那么，UDF 的时间复杂度为 O(n^2)，空间复杂度为 O(n)。

5.3 Pearson

本函数用于计算时间序列的皮尔森相关系数，即下式：

5.3.1 具体算法

5.3.1.1 UDF 设置

• 类型： UDTF
• 数据消费策略：本函数利用 RowByRowAccessStrategy 的策略消费原始数据。
• 输入序列：将索引为 0 和 1 的序列作为输入。
• 输出序列：一个 Double 类型的序列，只包含一个时间戳为 0、值为皮尔森相关系数的数据。

5.3.1.2 皮尔森相关系数计算

遍历输入序列 x，递推计算。最后，按照下式计算协方差：

5.3.2 复杂度分析

假设时间序列长度为 n，那么，UDF 的时间复杂度为 O(n)，空间复杂度为 O(1)。

第六章 异常检测

6.1 KSigma

本函数可以返回输入序列中出现的偏离均值大于指定倍数标准差的异常。

6.1.1 具体算法

函数维护窗口内的均值和方差，在滑动窗口时更新，并判断新的数据点是否为异常。

6.1.1.1 UDF 设置

• 类型： UDTF
• 数据消费策略：本函数利用 RowByRowAccessStrategy 的策略基于滚动窗口消费原始数据。
• 输入序列：将索引为 0 的序列作为输入。
• 输出序列：与输入序列相同。

6.1.1.2 滚动窗口设计

窗口大小设置为 10000，每次滚动为 1，null 值与 NaN 值不进入窗口。当窗口被填满时，从下标 0 开始检查是否为异常。当窗口滚动时，检查新的数据点是否为异常。若数据点数量小于窗口大小，只进行一遍计算。

6.1.2 复杂度分析

假设时间序列长度为 n，窗口大小为 m。那么，UDF 的时间复杂度为 O(n)，空间复杂度为 O(m)。

6.2 Range

6.2.1 具体算法

逐个判断每个值是否超过了用户提供的阈值。

6.2.1.1 UDF 设置

• 类型： UDTF
• 数据消费策略：本函数利用 RowByRowAccessStrategy 的策略基于滚动窗口消费原始数据。
• 输入序列：将索引为 0 的序列作为输入。
• 输出序列：与输入序列相同。

6.2.2 复杂度分析

假设时间序列长度为 n，UDF 的时间复杂度为 O(n)。

6.3 LOF

本函数计算输入序列完整点的 LOF 值。

6.3.1 具体算法

函数在窗口内轮流寻找第 k 近邻点，并依公式计算 LOF 值。

6.3.1.1 UDF 设置

• 类型： UDTF
• 数据消费策略：本函数利用 SlidingSizeWindowAccessStrategy 的策略基于滚动窗口消费原始数据。
• 输入序列：将多个序列作为输入。
• 输出序列：一列 DOUBLE。

6.3.1.2 滚动窗口设计

窗口大小设置为 10000，依次计算窗口中所有完整点的 LOF 值。

6.3.2 复杂度分析

假设时间序列总长为 n，窗口内时间序列长度为 m，UDF 的时间复杂度是 O(mn)。

6.4 IQR

本函数可以返回输入序列中出现的偏离四分位数 1.5 倍以上 IQR 的异常。

6.4.1 具体算法

若用户提供 Q1, Q3, IQR，则进行流式计算；否则读取全部数据得到以上结果后再查找异常。

IQR = Q3 − Q1

6.4.1.1 计算分位数

本函数调用 com.google.common.math.Quantiles 计算数组内的分位数。

6.4.1.2 UDF 设置

• 类型： UDTF
• 数据消费策略：本函数利用 RowByRowAccessStrategy 的策略基于滚动窗口消费原始数据。
• 输入序列：将索引为 0 的序列作为输入。
• 输出序列：与输入序列相同。

6.4.2 复杂度分析

假设时间序列总长为 n，流式计算的时间复杂度为O(n)，空间复杂度为O(1)；否则时间复杂度为O(n lgn)，空间复杂度为O(n)。

第七章 频域相关

7.1 Conv

本函数对两个输入序列求多项式卷积。

7.1.1 具体算法

7.1.1.1 UDF设置

• 类型：UDTF
• 数据消费策略：本函数利用 RowByRowAccessStrategy 的策略消费原始数据。
• 输入序列：将索引为 0 和 1 的序列作为输入。
• 输出序列：一个 Double 类型的序列，长度为两个输入序列长度之和减一。

7.1.1.2 卷积

遍历输入序列，按照公式依次计算每一项的值。

7.1.2 复杂度分析

假设两个时间序列长度分别为 m和n，那么函数的时间复杂度为 O(m*n)。

7.2 Deconv

本函数使用长除法将向量v从向量u中解卷积，并返回商q和余数r。u = conv(q, v) + r

7.2.1 具体算法

7.2.1.1 UDF设置

• 类型：UDTF
• 数据消费策略：本函数利用 RowByRowAccessStrategy 的策略消费原始数据。
• 输入序列：将索引为 0 和 1 的序列作为输入。
• 输出序列：一个 Double 类型的序列。

7.2.1.2 反卷积

 遍历输入序列，然后对输入序列做长除法。求得商与余数。

7.2.2 复杂度分析

假设两个时间序列长度分别为 m和n，那么函数的时间复杂度为 O(m*n)。

7.3 FFT

本函数对输入序列进行快速傅里叶变换。即下式：

7.3.1 具体算法

7.3.1.1 UDF 设置

• 类型： UDTF
• 数据消费策略：本函数利用 RowByRowAccessStrategy 的策略消费原始数据。
• 输入序列：将索引为 0 的序列作为输入。
• 输出序列：一个 Double 类型的序列，长度与输入相同。

7.3.1.2 快速傅里叶变换

调用 jtransform 库实现。

7.3.2 复杂度分析

假设时间序列长度为 n，那么，UDF 的时间复杂度为 O(n log n)，空间复杂度为 O(n)。

7.4 IFFT

7.4.1 具体算法

7.4.1.1 UDF 设置

• 类型： UDTF
• 数据消费策略：本函数利用 RowByRowAccessStrategy 的策略消费原始数据。
• 输入序列：将索引为 0 的序列作为输入。
• 输出序列：一个 Double 类型的序列，长度与输入相同。

7.4.1.2 快速傅里叶逆变换

调用 jtransform 库实现。

7.4.2 复杂度分析

假设时间序列长度为 n，那么，UDF 的时间复杂度为 O(n log n)，空间复杂度为 O(n)。

7.5 HighPass

7.5.1 具体算法

7.5.1.1 UDF 设置

• 类型： UDTF
• 数据消费策略：本函数利用 RowByRowAccessStrategy 的策略消费原始数据。
• 输入序列：将索引为 0 的序列作为输入，以及一个大小处于0和1之间的数值wpass。
• 输出序列：一个 Double 类型的序列，长度与输入相同。

7.5.1.2 高通滤波

将序列中频率低于wpass的低频信息置为0，仅保留高频信息。

7.5.2 复杂度分析

假设时间序列长度为 n，那么UDF 的时间复杂度为 O(n)，空间复杂度为 O(n)。

7.6 LowPass

7.6.1 具体算法

7.6.1.1 UDF 设置

• 类型： UDTF
• 数据消费策略：本函数利用 RowByRowAccessStrategy 的策略消费原始数据。
• 输入序列：将索引为 0 的序列作为输入，以及一个大小处于0和1之间的数值wpass。
• 输出序列：一个 Double 类型的序列，长度与输入相同。

7.6.1.2 低通滤波

将序列中频率高于wpass的高频信息置为0，仅保留低频信息。

7.6.2 复杂度分析

假设时间序列长度为 n，那么UDF 的时间复杂度为 O(n)，空间复杂度为 O(n)。

7.7 DWT

本函数对输入序列进行一维离散小波变换。即下式：

其中

函数将根据用户指定展开层数，依次将序列分解为高频部分与低频部分；高频部分继续分解，低频部分保留。

小波可以认为是一个带通滤波器，只允许频率和小波中心频率（经过尺度伸缩后）相近的信号通过。

7.7.1 具体算法

7.7.1.1 UDF 设置

• 类型： UDTF
• 数据消费策略：本函数利用 RowByRowAccessStrategy 的策略消费原始数据。
• 输入序列：将索引为 0 的序列作为输入。
• 输出序列：一个 Double 类型的序列，长度与输入相同。

7.7.1.2 离散小波变换

7.8 IDWT

本函数是DWT函数的逆运算，将分解后的小波还原为原始数据。

7.7.1 具体算法

7.7.1.1 UDF 设置

• 类型： UDTF
• 数据消费策略：本函数利用 RowByRowAccessStrategy 的策略消费原始数据。
• 输入序列：将索引为 0 的序列作为输入。
• 输出序列：一个 Double 类型的序列，长度与输入相同。

7.7.1.2 离散小波逆变换

根据给定的离散小波，逐次合并高通序列与低通序列，直至还原原始序列。

第八章 序列发现

8.1 ConsecutiveSequences

本函数用于在多维严格等间隔数据中发现局部最长连续子序列。

严格等间隔数据是指数据的时间间隔是严格相等的，允许存在数据缺失（包括行缺失和值缺失），但不允许存在数据冗余和时间戳偏移。

连续子序列是指严格按照标准时间间隔等距排布，不存在任何数据缺失的子序列。如果某个连续子序列不是任何连续子序列的真子序列，那么它是局部最长的。

8.1.1 具体算法

8.1.1.1 UDF 设置

• 类型： UDTF
• 数据消费策略：本函数利用 RowByRowAccessStrategy 的策略消费原始数据。
• 输入序列：将所有序列作为输入。
• 输出序列：一个 INT32 类型的序列。输出序列中的每一个数据点对应一个局部最长连续子序列，时间戳为子序列的起始时刻，值为子序列包含的数据点个数。

8.1.1.2 标准时间间隔估计

选择前 128 个数据点（如果数据总数不足 128，则选择全部数据），先计算它们中的相邻数据点的时间间隔，再求时间间隔的众数，将其作为标准时间间隔。

8.1.1.3 局部最长连续子序列发现

流式处理数据，维护一个计数器记录当前的局部最长连续子序列的长度，并记录这一个子序列的开始时间戳。如果当前行与上一行的距离是标准时间间隔，且当前行没有缺失数据，那么就将计数器加一；如果当前行与上一行的距离不是标准时间间隔，或者当前行缺失数据，说明发生了行缺失或值缺失，连续子序列的长度不能继续增加，需要输出当前的局部最长连续子序列，并将计数器归零。需要注意的是，如果当前行没有缺失数据，那么它可以作为一个新的局部最长连续子序列的起点。

8.1.2 复杂度分析

假设输入序列长度为 n。那么，UDF 的时间复杂度为 O(n)，空间复杂度为 O(1)。

8.2 ConsecutiveWindows

本函数用于在多维严格等间隔数据中发现指定长度的连续窗口。

严格等间隔数据是指数据的时间间隔是严格相等的，允许存在数据缺失（包括行缺失和值缺失），但不允许存在数据冗余和时间戳偏移。

连续窗口是指严格按照标准时间间隔等距排布，不存在任何数据缺失的子序列。

8.2.1 具体算法

8.2.1.1 UDF 设置

• 类型： UDTF
• 数据消费策略：本函数利用 RowByRowAccessStrategy 的策略消费原始数据。
• 输入序列：将所有序列作为输入。
• 输出序列：一个 INT32 类型的序列。输出序列中的每一个数据点对应一个连续窗口，时间戳为窗口的起始时刻，值为窗口包含的数据点个数。

8.2.1.2 指定长度连续窗口发现

指定长度连续窗口发现建立在章节8.1的算法基础之上，主要的不同在于输出。对每一个无法继续增长的局部最长连续子序列，局部最长连续子序列直接将其输出，而指定长度连续窗口发现则在序列上滑动，逐个输出指定长度的窗口。

8.2.2 复杂度分析

假设输入序列长度为 n。那么，UDF 的时间复杂度为 O(n)，空间复杂度为 O(1)。