Multi-Window Change Point Detection Method Using Density Ratio Estimation

doi:10.3778/j.issn.1002-8331.2108-0068

Abstract

Abstract: Aiming at the problem that the density ratio estimation-based time series change point detection method is limited by the time window width and only few types of change points are recognized, a multi-window detection method mDRCPD（multiple window density-ratio change point detection） based on dynamic multiple filtering algorithm（MFA） is proposed. Firstly, the processed time series are divided into time windows, the change points are identified by comparing the distribution differences of adjacent time window data, and the relative Pearson divergence based on density ratio estimation is used to measure the difference of data in different time windows. Secondly, change point set is obtained under fixed window width, and the change point sets are integrated according to MFA. It is showed in simulation experiments and real data analysis that compared with the single-window change point detection method, the absolute error, recall rate, F1 score and other indicators in the detection of mean, variance, and frequency changes by mDRCPD method is significantly improved. Finally, it is also applied to the analysis of the transmission process of COVID-19, and the phased characteristics of the epidemic is described, the effect of national policies on reducing the spread of the epidemic is evaluated by piecewise modeling of the transmission rate.

Key words: time series, change point detection, density ratio estimation, COVID-19, multiple windows, multiple filtering algorithm

摘要： 针对基于密度比估计的时间序列变点检测方法受时间窗窗宽限制，识别变点类型单一的问题，利用和发展动态多重过滤算法MFA（multiple filtering algorithm），提出一种多窗口变点检测方法mDRCPD（multiple window density-ratio change point detection）。将处理后的时间序列按多个时间窗进行适当划分，通过比较相邻时间窗数据的分布差异来识别变点，采用基于密度比估计的相对皮尔逊散度来度量不同时间窗数据分布的差异性；固定窗宽下寻找变点集，并按照MFA方法集成各变点集。模拟实验和实证分析表明，与基于密度比的单窗口变点检测方法相比，mDRCPD方法在多变点时间序列变点检测中绝对误差、召回率、F1得分等指标均有改善。将mDRCPD方法应用到COVID-19的传播进程分析中，通过对传播率的分段建模来刻画疫情的阶段性特点，评估国家政策在降低疫情传播速度上的效果。

关键词: 时间序列, 变点检测, 密度比估计, COVID-19, 多窗口, 多重过滤算法

ZHANG Man, CUI Wenquan. Multi-Window Change Point Detection Method Using Density Ratio Estimation[J]. Computer Engineering and Applications, 2023, 59(3): 84-93.

张曼, 崔文泉. 采用密度比估计的多窗口变点检测方法[J]. 计算机工程与应用, 2023, 59(3): 84-93.

References

[1] JIANG F，ZHAO Z，SHAO X.Time series analysis of COVID-19 infection curve：a change-point perspective[J].arXiv：2007.04553，2020.
[2] AMINIKHANGHAHI S，COOK D J.A survey of methods for time series change point detection[J].Knowledge and Information Systems，2017，51（2）：339-367.
[3] MONTANEZ G，AMIZADEH S，LAPTEV N.Inertial hidden Markov models：modeling change in multivariate time series[C]//Proceedings of the AAAI Conference on Artificial Intelligence，2015.
[4] WANG Y，HUANG G，YANG J，et al.Change point detection with mean shift based on AUC from symmetric sliding windows[J].Symmetry，2020，12（4）：599.
[5] 王阳阳.时间序列中多个变点的检测问题[J].现代商贸工业，2019（35）.
WANG Y Y.Detection of multiple change points in time series[J].Modern Business and Trade Industry，2019（35）.
[6] FOX A J.Outliers in time series[J].Journal of the Royal Statistical Society：Series B（Methodological），1972，34（3）：350-363.
[7] 高桢.时间序列变化点检测算法研究及应用[D].济南：山东大学，2018.
GAO Z.Research and application of time series change point detection algorithm[D].Jinan：Shandong University，2018.
[8] BONDU A，BOULLé M.A supervised approach for change detection in data streams[C]//The 2011 International Joint Conference on Neural Networks，2011：519-526.
[9] DESOBRY F，DAVY M，DONCARLI C.An online kernel change detection algorithm[J].IEEE Transactions on Signal Processing，2005，53（8）：2961-2974.
[10] AURET L，ALDRICH C.Change point detection in time series data with random forests[J].Control Engineering Practice，2010，18（8）：990-1002.
[11] WANG K，ZHAO Y，XIONG Q，et al.Research on healthy anomaly detection model based on deep learning from multiple time-series physiological signals[J].Scientific Programming，2016.
[12] CHEON S，KIM J.Multiple change-point detection of multivariate mean vectors with the Bayesian approach[J].Computational Statistics & Data Analysis，2010，54（2）：406-415.
[13] KAWAHARA Y，SUGIYAMA M.Sequential change-point detection based on direct density-ratio estimation[J].Statistical Analysis and Data Mining：The ASA Data Science Journal，2012，5（2）：114-127.
[14] BASSEVILLE M，NIKIFOROV I V.Detection of abrupt changes：theory and application[M].Englewood Cliffs：Prentice Hall，1993.
[15] BRODSKY E，DARKHOVSKY B S.Nonparametric methods in change point problems[M].[S.l.]：Springer Science & Business Media，2013.
[16] SUGIYAMA M，SUZUKI T，KANAMORI T.Density ratio estimation in machine learning[M].[S.l.]：Cambridge University Press，2012.
[17] GRETTON A，SMOLA A，HUANG J，et al.Covariate shift by kernel mean matching[J].Dataset Shift in Machine Learning，2009，3（4）：5.
[18] BICKEL S，BRüCKNER M，SCHEFFER T.Discriminative learning for differing training and test distributions[C]//Proceedings of the 24th International Conference on Machine Learning，2007：81-88.
[19] SUGIYAMA M，SUZUKI T，NAKAJIMA S，et al.Direct importance estimation for covariate shift adaptation[J].Annals of the Institute of Statistical Mathematics，2008，60（4）：699-746.
[20] KANAMORI T，HIDO S，SUGIYAMA M.A least-squares approach to direct importance estimation[J].The Journal of Machine Learning Research，2009，10：1391-1445.
[21] YAMADA M，SUZUKI T，KANAMORI T，et al.Relative density-ratio estimation for robust distribution comparison[J].Neural Computation，2013，25（5）：1324-1370.
[22] LIU S，YAMADA M，COLLIER N，et al.Change-point detection in time-series data by relative density-ratio estimation[J].Neural Networks，2013，43：72-83.
[23] MESSER M，KIRCHNER M，SCHIEMANN J，et al.A multiple filter test for the detection of rate changes in renewal processes with varying variance[J].The Annals of Applied Statistics，2014，8（4）：2027-2067.
[24] WANG Q，XIE S，WANG Y，et al.Survival-convolution models for predicting COVID-19 cases and assessing effects of mitigation strategies[J].Frontiers in Public Health，2020，8：325.
[25] BOUCHIKHI I，FERRARI A，RICHARD C，et al.Non-parametric online change-point detection with kernel LMS by relative density ratio estimation[C]//2018 IEEE Statistical Signal Processing Workshop（SSP），2018：538-542.
[26] HUSHCHYN M，USTYUZHANIN A.Generalization of change-point detection in time series data based on direct density ratio estimation[J].Journal of Computational Science，2021：101385.
[27] SUGIYAMA M，SUZUKI T，ITOH Y，et al.Least-squares two-sample test[J].Neural Networks，2011，24（7）：735-751.
[28] TAKEUCHI J，YAMANISHI K.A unifying framework for detecting outliers and change points from time series[J].IEEE Transactions on Knowledge and Data Engineering，2006，18（4）：482-492.
[29] SUNDARARAJAN R R，POURAHMADI M.Nonparametric change point detection in multivariate piecewise stationary time series[J].Journal of Nonparametric Statistics，2018，30（4）：926-956.
[30] TRUONG C，OUDRE L，VAYATIS N.Selective review of offline change point detection methods[J].Signal Processing，2020，167：107299.