Research On Change Point Detection Algorithm Based On Variance Of AUC And Its Parallelization

Change point detection is a hot research field in statistical analysis.It has important application in economics,biological genetics,geology and meteorology.The change point can be described as the time or position at which a structural mutation occurs in the time series.This mutation reflects that the time series before and after the change point follows two different distributions.In practical applications,accurately detecting the change points in the sequence can not only obtain the rich information contained in the sequence,but also timely avoid the risks caused by the abnormality.Therefore,it is extremely important to conduct in-depth research on the change point problem.In this paper,based on the analysis of the area under the curve(AUC)for the change point detection,considering the other statistical characteristics of AUC,a nonparametric change point detection algorithm based on AUC variance is proposed.The process of detecting a change point by the new algorithm consists of two phases,a data preprocessing phase and a detection phase.In the first stage,the time series data is preprocessed by the double sliding window method,and the AUC variance corresponding to the data in the window is extracted at each sliding position.In the second stage,the AUC variance after a certain multiple is amplified as a statistic.The statistical hypothesis test method is used to determine the existence of the change point.Under the premise of the change point,the position or time of the change point is estimated by searching for the local minimum value of the statistic.This non-parametric method makes full use of the superior statistical properties of AUC,and can effectively detect the change point when the time series distribution form is unknown.Through comparison experiments,the AUC variance is used to control the false alarm rate in the hypothesis test better than the AUC,and it shows stronger stability under the noise interference environment,and the online detection delay is shorter.At the same time,with the advent of the era of big data,more and more research areas need to face increasing data volume,as is the field of change detection.In the actual detection environment,the capacity of the data to be detected tends to be large,and only the CPU serial processing method is used to implement the change pointdetection,which requires a large amount of time.Aiming at this problem,and considering that the AUC variance-based change point detection algorithm works best when dealing with the single-point problem,this paper uses the Compute Unified Device Architecture(CUDA)technology to implement single-change detection for AUC variance.The process is parallelized to allow as many computational tasks as possible to be done in parallel on the GPU.Among them,two different memory optimization strategies are adopted to realize parallel processing in the data preprocessing stage,and the parallel processing in the detection stage is directly designed by means of the high-performance function library Thrust integrated in CUDA,and also based on the shared memory optimization strategy.A GPU General Purpose Computing(GPGPU)framework for single-point detection.Through comparison experiments,the detection efficiency of the variable point detection algorithm proposed in this paper is significantly higher than that of the CPU,and the data preprocessing stage is best achieved by shared memory optimization.