An Online Change Point Detection Method Based On Adaptive Sliding Window

With the increasing concern on data in various industries,a large amount of data has been collected in the fields of production,transaction and medical for research on product upgrades or service transformation in the past 20 years.The attention of data from all walks of life has accelerated the development of data analysis technology,and put forward higher requirements for existing data analysis methods.The traditional off-line data analysis methods can no longer meet the real-time requirements of data stream analysis,because the data stream shows the characteristics of high immediacy and high velocity.Therefore,the online analysis method of data stream is gradually favored by academia and industry,and has become an important direction of data stream research.At present,sliding window model is one of the key technologies for online detection of change points in data stream.The sliding window technology is used to divide the data stream into several windows for analysis,which greatly improves the speed of change point detection and meets the real-time requirements of online detection.However,in the sliding window model,selecting a window of improper size will decrease the detection accuracy of the change point.If the window is too large,the fluctuation of data in the window will be covered,which will lead to poor detection accuracy of the change point.If the window is too small,the amount of data and its carrying information will be small,which will also reduce the detection accuracy of the change point.Therefore,the size of the window in the sliding window model is an important factor affecting the detection accuracy of data stream change point.In this paper,the relationship between the window size and the detection accuracy of change point in sliding window model is taken as the research object.An adaptive window model that can dynamically adjust the window size with the detection process is proposed.This model is applied to detect change points in simulated data and real brain waves,which has achieved remarkable results.First of all,this paper introduces a fast TSTKS change point detection algorithm,and combines the sliding window theory to construct an online detection model of data stream change point.The TSTKS algorithm is improved from HWKS algorithm.By adding intermediate branches to the binary tree,the problem that the HWKS algorithm is insensitive to change points appearing in the middle part is solved.The experimental results show that compared with other algorithms,the sliding window model with TSTKS algorithm performs better in change point detection.Secondly,according to the local information obtained during the detection of change point in the data stream,three adaptive window adjustment strategies are proposed.Strategy 1 is formulated based on the detection results of change point in each window during the detection process,which is suitable for data stream with slight oscillation.Strategy 2 is formulated based on the changes in the interval of each change point during the detection process,which is applicable to data stream with severe oscillation.Strategy 3 is formulated based on the difference of data distribution in adjacent windows during the detection process,which is suitable for data stream with smooth distribution.Three adaptive window strategies are introduced into the sliding window model for simulation and compared with the fixed window model.The experimental results show that all the three adaptive strategies can optimize the detection performance of the sliding window model within a certain range.Furthermore,according to the performance characteristics of the three adaptive window strategies,a method of automatically selecting adaptive window strategy is presented.This method combines the advantages of three adaptive window strategies,and can flexibly select the corresponding adaptive window strategy based on the distribution of local data.The experimental results indicate that the performance of the model with this method is better than that of any single adaptive strategy model.Finally,combined with three kinds of adaptive window strategies and intelligent strategy selection methods,an online change point detection model of adaptive window is constructed and the change points of real epilepsy EEG data is detected by the model.Comparison experiments show that the performance of the proposed adaptive window model is significantly promoted compared with the traditional fixed window model.