“中兴捧月”杯算法精英挑战赛-Dijkstra赛道解决方案分享

  • A+
所属分类:CTF专场

本篇文章由ChaMd5安全团AI小组投稿“中兴捧月”杯算法精英挑战赛-Dijkstra赛道解决方案分享

赛题分析

  • 竞赛题目

在全民抗击新冠疫情中,发现流动人口统计监控具有重要意义。根据过去人口的流动性,通过技术手段预测未来人口趋势,将为组织决策带来空前的优势。在A市的代表性社区、关键街道、核心路口部署传感器,统计每天人口流入的数据。因为隐私保护的原因,不能直接公布人口流动的真实数据,而是公布经过脱敏处理的人口流动率。请你根据历史数据预测未来一段时间的人口流动,帮助A市进行决策。

  • 竞赛数据

1、数据经过脱敏处理,人口流动率范围在 0-100之间;

2、数据包含两个文件:

train_step1.csv:  包含三列,分别为 id、日期、人口流动率。样例:

id date value
"-92224985456548" 2017-01-22 2.5546
"-92224985456548" 2017-01-23 2.5532
"-92224946545651" 2017-01-23 5.7432

test_step1.csv: 包含两列,分别为 id,日期。样例:

id date value
"-92224985456548" 2018-05-22

"-92224985456548" 2018-05-23

"-92224946545651" 2018-05-23


3、测试文件test_step1.csv里面,含有部分不用于判决的噪声数据。

4、test_step1.csv里面传感器 id 全部在train_step1.csv里面出现过。

  • 评价指标

1、单个预测值误差20%以内得100分,预测值误差超过20%得0分。误差计算规则如下:

误差 =  abs(预测值 - 真实值) / 真实值 * 100%

2、所有得分的平均值为题目得分。

3、按照统一的baseline的百分比进行展示得分,即[题目得分]/baseline*100%,上限为100。

  • 赛题转化

针对过去的一段时间的人口流动率进行人口流动率预测是一种经典的时间序列预测问题。针对时序预测问题,首先需要对数据做探索性数据分析(Exploratory Data Analysis,EDA),对数据的分布,趋势,异常值,均值,极差等及进行分析。之后根据所分析的数据特性建立相应的模型进行最终的预测。

解题思路

在全民抗击新冠疫情中,发现流动人口统计监控具有重要意义。这个问题实际上是一个时间序列的预测问题,尽管时间序列的预测问题已经在学术界和工业界被大量研究,但当前时间序列预测的研究多针对小规模长序列时序数据进行,而此次比赛的数据属于大规模短序列时序数据,所以在预测上依旧有相当的难度。

“中兴捧月”杯算法精英挑战赛-Dijkstra赛道解决方案分享

此处我们使用部分数据对当前比较前沿/常用的模型进行了测试,但是这些模型均针对长时间序列预测问题设计,在序列较短时容易欠拟合导致效果不是很理想。

“中兴捧月”杯算法精英挑战赛-Dijkstra赛道解决方案分享

此外我们还尝试了比较传统的模型:以 ARIMA为代表的传统统计学模型和以 Prophet为代表的广义加性模型,但是效果也不是很好,而且由于数据条数多的原因,计算速度过慢。

“中兴捧月”杯算法精英挑战赛-Dijkstra赛道解决方案分享

实际上,此题与Kaggle经典赛题:Kaggle Web Traffic很相似,均属于大规模短序列数据的预测问题。而 Kaggle Web Traffic的 Top-1方案为 Seq2Seq类模型,在前期的实验中,本文亦使用过 Seq2Seq类模型,但是发现效果并不是很理想。究其原因可能是因为 Kaggle Web Traffic有 “Page ID”,即除了时序信息外其还可以提取语义特征。而 Kaggle Web Traffic的 Top-2方案为 XGB+LGB+DNN的Ensemble,此处我们认为 XGB+LGB的使 用在这里可能不尽合理,因为XGB+LGB均属于 GBDT模型, GBDT模型使用的场景是时间序列相对平稳的情况,其核心原因是 tree没有办法做 “外推 ”。趋势性非常强的数据,GBDT是没有办法拟合的,以单 tree为例, tree的叶子节点的值是已知标签的值的平均,而对于 GBDT的集成模型而言,某个样本是其落在的所有子树的叶子上的值的加权平均(权重是学习率),这导致的问题就是预测结果一定是介于序列数据的最大和最小值之间的。也有专家学者表示,如果要将其用于外推预测,可以创建隐含外推的特征实现,本文尝试使用 tsfresh提取了部分 创建隐含外推的特征 ,构建了一个基于 XGBoost的预测算法,预测结果如图所示。但在特征工程的过程中 本文 发现序列的特征不尽一致,找到比较好的特征可能比较困难,而且 费时费力。综合以上的前期调研, 我们最终选择使用 DNN模型进行序列的预测。


“中兴捧月”杯算法精英挑战赛-Dijkstra赛道解决方案分享

  • 探索性数据分析

此处我们对日期长度分布、特征指标进行基本统计。同时考虑到指标间的相关性,对不同指标间进行了初步的相关分析。

“中兴捧月”杯算法精英挑战赛-Dijkstra赛道解决方案分享

在整个构建模型以及EDA分析的过程中,我们发现利用好以下 Trick可以使得模型线上分数大幅度增加,因此首先陈列出它们:

  1. 周期性:此处数据的周期性其实是非常强的, 可以 以 一周 为数据周期进行后续模型的构建;而且考虑到数据的年周期性和波动因素,此处构建训练集的时候选择整个时间序列进行预测其实效果并不好,这里其实做了一个 bet,选择了270天来构建训练集;

  2. 损失函数:考虑到赛题的评价指标为:误差 = abs(预测值 - 真实值 ) / 真实值 * 100%,因此此处的训练不应该采用 RMSE来作为损失函数,而应该使用MAPE来作为损失函数,这样训练的模型更符合比赛要求;

  3. 异常值处理:此处对数据做 log1p光滑,可以较为有效地解决异常值问题;同时 本文 使用 DNN逐个 'id'计算 预测值的 MAPE,丢弃 MAPE大于 1.25的 ‘使用平均数来预测这些 ‘

  4. 缺失值处理:此处缺失值 本文 全部填一个较大的常数,之后再用 ‘nan’来做替换;

  5. 网络输入:此处 本文 使用中值作为网络输入,而不是原始值,这是受到kaggle web traffic的启发。输入主要是过去 8到 12周的周中位数。后来又增加了滞后一周的中位数、与中位数的差异、一周的最大值等。

整体方案介绍

传统时间序列预测模型多基于长时间序列进行模型设计,针对此次比赛的数据属于大规模短序列时序数据,本方法采用了基于DNN和平均数做Ensemble的基本思路,并提出了一种基于规则的加权投票机制,其具有轻量级、可迁移的特点。

“中兴捧月”杯算法精英挑战赛-Dijkstra赛道解决方案分享

  • 研究难点

1.训练数据存在噪声(抗干扰)

2.AB数据集指标不一致(适应性)

3.模型预测准确有效(准确性)

  • DNN结构

为了充分利用到周期性,本文并没有直接将270个数据输入网络。而是用它们除以 7取余数来定义索引:这样无论是在哪一年,第三个星期二的输出都在同一个位置。这是构建网络的关键,因为它能预测每周的模式。、此处采用的中位数是是log1p转换后的数据,且没有对数据进行归一化处理,因为平均值已经接近于转换后的数据,且没有对数据进行归一化处理,因为平均值已经接近于0,方差接近于1。考虑到此处序列较短,容易过拟合。因此,此处的DNN为为 一个简单的前馈网络,每层有200、200、100、200个单元。输入与第一层的输出再次串联。除了最后一层是线性的外,其他的激活都是重复的。

“中兴捧月”杯算法精英挑战赛-Dijkstra赛道解决方案分享

  • How to train?

本文对几乎所有的层都使用了0.5的的dropout(0.5是由是由GridSearchCV选择的),且对中间层使用了批量归一化。模型是用ADAM优化器和优化器和MAPE损失函损失函数编译的。本文对DNN使用了五折交叉验证,batch-size为为4096,因为增加批处理量既能减少训练时间,又能提高准确率。训练了200个epoch,每10个epoch计算所有计算所有fold的实际训练的MAPE,并使用所有最佳epoch的预测的中位的预测的中位数来提交。对于每个fold,本文训练了一个模型,并取其预测的中值。训练总时间在时间在GTX 1060上约为10分钟。

同时在决赛中由于有多个数据集,又因为EDA分析中本方法对不同指标进行了Person相关分析,发现数据间的相关性很强,因此本方法将不同指标归一化后输入网络进行多次训练。

  • How to inference?

由于最终B榜数据推理时间有限,此处不对模型进行再次训练,而是使用之前的模型直接进行推理。

  • 网络输入输出

特别的,针对数据进行标准化处理和增加趋势性的度量特征,本文定义了一个add_median 函数,其中本文通过计算不同周期的中位数实现了趋势特征的衍生,以(0,1)为例,这里计算的是最近的 112 天中,最早的 0 到 7 天的访问量的中位数,以(1,2)为例,就是计算最近 112 天中,最早的 7 到 14 天的访问量的中位数 ,之后本文把计算出来的每一个‘id’对应时间段下的中位数合并进来,列名为c,使用 c 减去所有 112 天的中位数,缺失值补 0。比如说 104 天的访问量的中位数为500,某一周的访问量为 5000,则显然 5000-500=4500 是一个明显的上升趋势,如果某一周访问量为 0,则 0-500=-500 是一个明显的下降趋势,并且不同大小的结果可以较好的表示出趋势的强弱。而此处的标准化方法是,每一个‘id’数据中的每一天,都针对于过去某个时间段的中位数进行了减法处理:

“中兴捧月”杯算法精英挑战赛-Dijkstra赛道解决方案分享

如图 所示,数据中 91 天的部分,每一天的数据都减去了过去 104 天的访问量的中位数,从而完成趋势的消除。相对于简单的 log1p 变换多了一个减去近期一段时间的中位数的操作。综上所述,本文构建了一个中位数、中位数趋势预测+DNN 模型,预测的时候,两个模型进行求和集成。

  • 加权投票机制

选用以周为单位进行加权后的平均数作为投票前填充的 baseline,将其与 DNN 相融合,而其他的平均数则和DNN 预测的模型一起作为参考,作为是否填充'nan',以及是否与 DNN 融合的条件。

“中兴捧月”杯算法精英挑战赛-Dijkstra赛道解决方案分享

  • NaN值投票填充机制

由于AE数据集NaN值包含过多,而新的评价指标中NaN值得分降低,因此我们对数据中的NaN值进行补偿填充。

“中兴捧月”杯算法精英挑战赛-Dijkstra赛道解决方案分享

方案展望

“中兴捧月”杯算法精英挑战赛-Dijkstra赛道解决方案分享

“中兴捧月”杯算法精英挑战赛-Dijkstra赛道解决方案分享


工作总结

Ø设计了一种针对大规模短序列时序数据的DNN预测模型,并依据数据间的相关性来进行模型的多步训练,改善了模型的泛化能力;

Ø提出了一种基于加权投票机制和NaN值投票填充机制的融合方法,提升了预测结果的精度;

Ø搭建了基于图卷积神经网络的预测模型,对数据拼接、增强、分群打标和邻接矩阵初始化方法进行了研究;

参考资料

[1] Taylor SJ, Letham B. 2017. Forecasting at scale. PeerJ Preprints 5:e3190v2 https://doi.org/10.7287/peerj.preprints.3190v2

[2] gbdt不适用于什么样的时间序列问题: https://zhuanlan.zhihu.com/p/311883742

[3] Web Traffic Time Series Forecasting: https://www.kaggle.com/c/web-traffic-time-series-forecasting

[4] ARIMA Model – Complete Guide to Time Series Forecasting in Python: https://www.machinelearningplus.com/time-series/arima-model-time-series-forecasting-python/

[5] Guolin Ke, Qi Meng, Thomas Finley, Taifeng Wang, Wei Chen, Weidong Ma, Qiwei Ye, Tie-Yan Liu. "LightGBM: A Highly Efficient Gradient Boosting Decision Tree". Advances in Neural Information Processing Systems 30 (NIPS 2017), pp. 3149-3157.

[6] Qi Meng, Guolin Ke, Taifeng Wang, Wei Chen, Qiwei Ye, Zhi-Ming Ma, Tie-Yan Liu. "A Communication-Efficient Parallel Algorithm for Decision Tree". Advances in Neural Information Processing Systems 29 (NIPS 2016), pp. 1279-1287.

[7] Huan Zhang, Si Si and Cho-Jui Hsieh. "GPU Acceleration for Large-scale Tree Boosting". SysML Conference, 2018.

[8] LightGBM:https://lightgbm.readthedocs.io/en/latest/

[9] Tianqi Chen and Carlos Guestrin. XGBoost: A Scalable Tree Boosting System. In 22nd SIGKDD Conference on Knowledge Discovery and Data Mining, 2016

[10] Colin Lea, Rene Vidal, Austin Reiter, Gregory D. Hager, Temporal Convolutional Networks: A Unified Approach to Action Segmentation, 2016.

[11] Shaojie Bai1J. Zico Kolter2Vladlen Koltun, An Empirical Evaluation of Generic Convolutional and Recurrent Networksfor Sequence Modeling, 2018.

[12] Transformer: https://en.wikipedia.org/wiki/Transformer

[13] Thomas N. Kipf, Max Welling, Semi-supervised Classification with Graph Convolutional Networks,2017.

[14] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, Yoshua Bengio, Graph Attention Networks, 2017.

[15] William L. Hamilton, Rex Ying, Jure Leskovec, Inductive Representation Learning on Large Graphs, 2018.


end


招新小广告

ChaMd5 Venom 招收大佬入圈

新成立组IOT+工控+样本分析+AI 长期招新

欢迎联系[email protected]



“中兴捧月”杯算法精英挑战赛-Dijkstra赛道解决方案分享

本文始发于微信公众号(ChaMd5安全团队):“中兴捧月”杯算法精英挑战赛-Dijkstra赛道解决方案分享

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: