P4572.第3题-动态区间的多项式岭回归

1000ms

Difficulty: 9

所属公司 : 华为

算法与标签>数学

题目内容

某大型互联网公司的数据中心，记录了其核心服务在连续 $N=200$ 天内的出口总流量(单位 $GB$ ，取值范围通常在 $100.00$ 到 $500.00$ 之间)已按时间顺序给出。由于监控系统维护，数据中有 $M$ 个( $M$ 的范围为 $20$ 到 $30$ )缺失值，按顺序标记为 $Missing\_1,Missing\_2,...,Missing\_M$ 。

已知这些缺失值保证不会出现在第 $1$ 天和最后 $1$ 天（即首尾两条记录一定存在）

任务描述

你需要为每一个缺失值，通过其邻近的、动态变化的真实数据区间，建立一个 二阶多项式岭回归( $2nd$ $Ridge$ $Regression$ )模型进行预测。

区间定义

对位于全局序号 $pos$ 的缺失值：

前向区间 $[left\_start,pos-1]$ ：从 $pos-1$ 开始向前(向着第 $1$ 天)寻找，遇到的第一个原始缺失值 $(Missing\_1...Missing\_M$ 中的任意一个)的后一天。如果到第 $1$ 天仍未碰到任何原始缺失值，则前向区间的起始点 $left\_start$ 为第 $1$ 天。

后向区间 $[pos+1,right\_end]$ ：从 $pos+1$ 开始向后(向着第 $N$ 天)寻找，遇到的第一个原始缺失值的前一天。如果到第 $N$ 天仍未碰到任何原始缺失值则后向区间的结束点 $right\_end$ 为第 $N$ 天。

算法与公式

取上述两个区间内的所有真实记录作为训练集 ( $x,y$ )，其中：

$x$ 为日期序号 ( $1,2,...,N$ )

$y$ 为对应的流量值

你需要使用岭回归求解二阶多项式模型求岭回归模型

Latex: $\hat{y} = \beta_2 x^2 + \beta_1 x + \beta_0$

岭回归的解可以通过以下矩阵公式计算：

$\beta=\left(X^{T} X+\lambda \right)^{-1} X^{T} y$ ，

其中:

$β$ 是一个 $3×1$ 的列向量，包含需要求解的系数 [β_2 β_1 β_0]。
$X$ 是一个 $n×3$ 的设计矩阵，其中 $n$ 是训练集的数据点数量。对于训练集中的每一个日期序号，矩阵 $X$ 中对应的一行为 $[x_i^{2}，x_i,1]$ 。
$y$ 是一个 $n×1$ 的列向量，包含训练集中 $n$ 个观测点的流量值。
$X$ ^ $T$ 是 $X$ 的转置矩阵。
$\lambda$ 是正则化参数，在本题中统一设为 $\lambda=0.1$ 。
$1$ 是一个 $3×3$ 的单位矩阵。
(.)^{-1} 表示矩阵求逆。

输入描述

第 $1$ 行：两个整数 $M$ 和 $N$ ，由空格分隔。第一个参数 $M$ 指的是缺失值的总数(范围为 $20$ 到 $30$ )；第二个参数 $N$ 是指后续的数据行数(固定为 $200$ )
第 $2$ 行到第 $N+1$ 行：每行包含一个值，该值可以是
- 一个浮点数，代表当日的真实流量值。
- 一个字符串，格式为 $Missing\_i$ (其中 $i$ 从 $1$ 到 $M$ )，代表当日的流量数据缺失。

输出描述

共 $M$ 行，严格按照 $Missing\_1, Missing\_2,...,Missing\_M$ 的顺序输出。

每行格式为 $Missing\_i$ ：xxx.xx，即标签、冒号、空格、预测值。预测值要求保留两位小数。

样例1

输入

20 200
140.36
146.38
167.91
162.64
181.99
166.79
Missing_1
156.46
175.24
165.52
157.71
Missing_2
158.26
169.09
142.55
151.18
148.18
Missing_3
140.23
146.42
135.47
Missing_4
130.90
138.79
133.65
129.18
151.72
142.50
133.01
157.68
Missing_5
157.02
169.40
168.70
178.77
160.13
174.77
174.48
162.20
167.09
181.81
160.76
172.85
167.83
167.38
164.35
140.30
160.63
143.56
142.56
133.02
133.61
Missing_6
130.73
143.76
146.32
136.02
Missing_7
151.45
143.21
147.88
164.99
176.53
177.58
163.27
Missing_8
163.40
167.27
182.03
189.90
175.84
181.42
171.06
160.66
161.04
159.17
156.67
Missing_9
140.52
153.13
135.72
153.66
136.88
143.00
Missing_10
147.52
136.38
152.19
Missing_11
140.37
151.19
155.24
Missing_12
176.08
166.01
174.35
186.10
189.84
Missing_13
167.38
180.46
184.17
167.70
158.32
170.87
159.46
152.25
164.62
159.22
160.63
155.92
132.63
146.97
128.47
133.05
134.12
145.20
161.01
153.34
152.31
160.25
157.89
162.57
159.33
188.02
188.42
Missing_14
190.36
172.49
179.07
186.54
174.78
189.76
179.46
169.32
Missing_15
166.40
174.29
147.45
140.39
166.35
150.74
133.56
158.77
140.73
153.93
136.37
143.02
168.03
162.22
173.28
176.61
159.22
173.93
179.96
169.60
178.89
190.53
202.52
200.04
187.90
Missing_16
184.13
193.93
170.60
183.11
178.36
170.28
174.84
160.06
169.08
159.11
Missing_17
140.99
148.42
156.97
144.91
144.61
169.12
152.68
176.46
Missing_18
165.14
170.70
171.10
182.38
181.63
196.53
Missing_19
180.73
182.49
192.30
184.48
178.30
192.26
193.45
188.63
Missing_20
176.12
173.62

输出

Missing_1: 175.81
Missing_2: 168.12
Missing_3: 150.08
Missing_4: 138.62
Missing_5: 158.61
Missing_6: 141.85
Missing_7: 146.87
Missing_8: 166.18
Missing_9: 155.56
Missing_10: 144.75
Missing_11: 147.16
Missing_12: 160.65
Missing_13: 166.72
Missing_14: 169.88
Missing_15: 166.19
Missing_16: 174.53
Missing_17: 164.11
Missing_18: 167.63
Missing_19: 181.34
Missing_20: 182.15

说明

Missing_1:175.81

Missing_2:168.12

Missing_3:150.08

Missing_4:138.62

Missing_5:158.61

Missing_6:141.85

Missing_7:146.87

Missing_8:166.18

Missing_9:155.56

Missing_10:144.75

Missing_11:147.16

Missing_12:160.65

Missing_13:166.72

Missing_14:169.88

Missing_15:166.19

Missing_16:174.53

Missing_17:164.11

Missing_18:167.63

Missing_19:181.34

Missing_20:182.15

输入

预期输出（选填）

解题思路

P4572.第3题-动态区间的多项式岭回归

题目内容

输入描述

输出描述

样例1

Status

Development

Support

About