Research And Implementation Of A Fast Detection Algorithm For Abrupt-point Change Of Data Stream

Data has been becoming significant,like natural resources and human resources,for the potential values behind it.The big data has the characteristics of large volume,various modes,rapid generation and great value.Time series analysis in data flow is one of important branches of big data research.Data flow analysis technology is the rapid acquisition of valuable information from various types of data.The rapid development of data flow and its application not only promote the development of basic science,but also are important opportunity and challenge for technological progress,national innovation and industrial development in many industries.The abrupt change of the data flow means that the value of the data flow at the current time is larger or smaller than the previous one or the average value.Most of the analysis methods of mutation point detection in current data flow are very timeconsuming,and the detection of abrupt points at both ends is inaccurate.In this thesis,the HWKS algorithm was introduced,which can quickly detect the mutation points in the data and make a comparative verification.Based on this algorithm,the sliding window was employed to realize the on-line detection of data,and the effectiveness of this method was verified by the simulated data from the actual fire.The HWKS algorithm is based on Haar wavelet transform theory and a modified KS statistical test theory.The HWKS algorithm is mainly aimed at the time series model data in the data stream.The main steps of this algorithm include the application of the multi-level Haar wavelet transform to decompose the detected data stream and building mean binary tree and difference binary tree at the same time.Then,based on the modified KS statistic,two search rules for mutation point detection were built.The first rule is based on difference binary search tree and the second is based on average binary search tree.When the first rule cannot search mutation point,the second would work,so these two rules are complementary.Abrupt point detection was carried out according to the rules.The algorithm uses a top-down search strategy with the idea of binary search algorithm,greatly improving the detection efficiency.In this thesis,we compared the HWKS algorithm with KS test,Haar wavelet and t-test,respectively,in terms of time-consuming,hit rate,error and accuracy,which has verified HWKS algorithm's advantages including efficiency,accuracy and sensitivity.To deal with the real-time characteristic of data stream,this thesis introduced sliding window model based on HWKS algorithm.Through the simulation analysis,the influence of the size of the sliding window on the detection of abrupt changes is discussed in the data stream by keeping the size of the data stream.The experimental results showed that the more accurate position of the detected abrupt point can be got by increasing the size of sliding window in detection process.But it does not mean that bigger sliding window would be better for the data flow velocity should be considered.In addition,the situation of multi abrupt points in data stream also should be taken into consideration.To verify the sensitivity of HWKS algorithm to the abrupt change point in the data stream,this simulation set the abrupt change points at the beginning and the end of the data stream,respectively.The results demonstrated that the HWKS algorithm can not only detect the abrupt changes of the data edge but also detect all the abrupt changes in the data stream exactly by introducing sliding window model.Finally,the HWKS algorithm with sliding window was compared with the one without sliding window by the simulated data from the actual fire including temperature,smoke concentration,CO concentration and CO2 concentration.These results explained that the HWKS algorithm with sliding window not only can detect the characteristic change at the time of the fire,but also can detect that after the fire.In addition,the HWKS algorithm with sliding window was more accurate than the HWKS algorithm without sliding window,so the former algorithm showed a good prospect for fire detection in practice.