算法思路

1. 均值 & 标准差

   • 用前缀和与前缀平方和可快速计算：

     • sum = prefix[i+w] - prefix[i]
     • mean = sum / w
     • var = (Σy² - w*mean²) / (w-1)
     • std = sqrt(max(var,0))

题目内容

题目背景:

数据治理阶段经常会碰到特征转换，当前有一个时间序列数据(用 $1$ 维整数数组表示)，和一个窗口序列( $1$ 维整数数组)，窗口序列中每个元素表示 $1$ 个窗口 $w$ 。

转换要求:

实现一个多尺寸滑动窗口特征转换函数，每个窗口提取 $5$ 个特征，计算出来如果是整数不带小数点，则小数点后最多保留 $3$ 位(四舍五入)

小数点举例说明:

$1.0->1$ 整数不带小数点

$1.10->1.1$ 结尾不带 $0$

$1.1116->1.112$ 最多保留 $3$ 位小数，最后一位四舍五入

特征包含:

均值($mean$)

标准差(样本标准差，$ddof=1$ ;分母为 $0$ 时，返回 $0$ )

最小值($min$)

最大值($max$)

线性趋势斜率(使用线性回归拟合)

线性趋势斜率算法:

时间索引: $x = [0, 1, 2,...,w-1]$

对应的值: $y = [y_0,y_1, y_2,...,y_{w-1}]$

拟合一条直线:$y=βx+α$

$β$ 是斜率(我们需要的趋势斜率)

$α$ 是截距

使用最小二乘法，斜率的计算公式为:

$β = [n* ∑(xy) - ∑x*∑y] / [n*∑(x^2) - (∑x)^2]$

$n$ 是窗口大小

标准差计算公式:

$s=\sqrt{\frac{1}{n-1} \sum_{i=1}^{n}\left(x_{i}-\bar{x}\right)^{2}}$

转换规则:

对于每个窗口大小 $w(window\_array$ 中的一个元素)，从索引(索引从 $0$ 开始)$i=max(window\_arravy)-w$ ，开始滑动窗口

所有窗口的特征按 $window\_arrav$ 中的元素顺序排列

如果数组长度小于任意一个窗口大小,则结果数组为空

输入描述

$input$_$array$ :一维数组,表示时间序列数据

$window$_$array$:一维数组,多个窗口，每个元素为窗口 $w$

输出描述

二维数组，形状为 $(n,m)$ ，其中:

$n = len(input\_array) - max(window\_array) +1$

$m = len(window\_array) * 5$

每一行说明:

$[mean1, std1, min1, max1, slope1, mean2, std2, min2, max2, slope2,...]$

样例1

输入

[10, 20], [3, 4]

输出

[]

说明

输入长度小于窗口最小大小，输出空数组

样例2

输入

[1, 2, 3, 4, 5], [2, 3]

输出

[2.5, 0.707, 2, 3, 1, 2, 1, 1, 3, 1]
[3.5, 0.707, 3, 4, 1, 3, 1, 2, 4, 1]
[4.5, 0.707, 4, 5, 1, 4, 1, 3, 5, 1]

说明

1、窗口大小 $2$ 的特征:

[2,3]: mean=2.5,std=0.707, min=2, max=3, slope=1

[3,4]: mean=3.5, std=0.707, min=3, max=4, slope=1

[4,5]: mean=4.5, std=0.707, min=4, max=5, slope=1

2、窗口大小 $3$ 的特征:

[1,2,3]: mean=2, std=1, min=1, max=3, slope=1

[2,3,4]: mean=3, std=1, min=2, max=4, slope=1

[3,4,5]: mean=4, std=1, min=3, max=5, slope=1