Research On Multiple Change-points Detection Method Based On Shape Recognition

The change-point detection is an important topic in statistics,which is originally used in the context of quality control.In recent decades,due to the wide applications in natural and social sciences such as economics,environtol-ogy,finance and biomedical,the change-point detection has gained a valuable attention in Statistics.In this paper,we mainly research on the method of multiple change-points detection for mean change of independent observation time series under normal assumptionBS(Binary Segmentation)algorithm is one of the most classical algorithm-s in multiple change-points detection of time series data,but the recognition process based on global CUSUM statistics may lead to too many misjudge-ments and a high time complexity.On the one hand.BS algorithm is an off-line sequential method,so it does not make full use of the sequential infor-mation of data.On the other hand,the principle of BS algorithm to identify change-points is to find maximizer of CUSUM statistics without considering the morphological characteristics of the sequence of statistics.In view of this.two improved BS algorithms are proposed in this paper.One is Double-K B-SW algorithm,which is based on weighted statistic-exponential decay weight-ed statistic,with a low time complexity of o(n/k log n/k).Another proposed Shape-based BS algorithm is based on local morphological recognition statis-tics,which is fully mining the curve morphological information of local test statistics.The algorithm not only greatly reduces the computational complex-ity,but also reduces the misjudgment rate caused by the interference between the change-points,and adds a single peak change point recognition criterion.which improves the robustness of the change-point recognition.Finally,we apply these two algorithms to practical examples to verify their effectiveness.In addition,the change-points are relatively sparse to the sample size in general,so in order to reduce the unnecessary calculation in the execution pro-cess of the algorithm,the data can be filtered firstly.By excluding most areas without change-points,the change-points are locked in small areas.And then the fast multiple change-points detection algorithms,based on cutting shape recognition,are proposed.According to the different cutting technologies,this paper proposes two types of fast shape recognition algorithms:one is based on transverse projection cutting,including SCC and SMSA;another is based on longitudinal cutting,including FSSR.The methods based on the transverse cutting methods,are three key tools used to mine the curve morphological f'eatures of test statistics,which are local CUSUM statistics,sharp drop point and local peak recognition.And There are three key steps in this method:data-driven threshold,adaptive window width and single peak recognition.According to the different cutting thresholds,SCC(Shape-based Cutting and Clustering)algorithm and SMSA(Shape-based Multiple Segmentation Algo-rithms)method are proposed.The cutting threshold of SCC is the biggest sudden drop point,which can filter out the non-change point to the greatest extent.It greatly improves the detection speed,and the operation effect is insensitive to the size of data.However,due to the randomness of the data,some change-points may be omitted when bounded by the maximum sudden drop point.Therefore,the SMSA algorithm chooses the rightmost sudden drop point as the screening boundary,which ensures that the filtered data contains all the real change-points.And adding multi-segmentation steps,the detec-tion speed is improved to a certain extent.The larger the amount of data,the better the effect of SMSA is.In this paper,the theoretical properties of SCC algorithm and SMSA method are given.The method based on vertical cutting and grouping is FSSR(Fast Screen and Shape Recognition)algorith-m.The key steps of FSSR include grouping locking the segment containing the change-point and verifying the change-point based on shape recognition in the quasi-change points segments.FSSR algorithm has obvious advantages in recognition speed and stability,and can reduce the time complexity to O((?)).Especially,the more sparse the distribution of change-points,the more obvi-ous the advantages of FSSR algorithm.And the above calculations are applied to practical examples to verify their effectiveness.Finally,the corresponding theoretical properties are given.In summary,this paper proposes improved BS algorithms based on new test statistics,and fast algorithms of shape recognition based on cutting.The corresponding theoretical properties are given.The simulation shows the su-periority of the proposed algorithms.The application of examples shows the effectiveness of the proposed algorithms.