| With the continuous development of the big data,the speed of data generation is accelerating and changes with time in real time.Compared with traditional static data,this kind of data takes the form of a stream,which is called a Data Stream.Because the data stream is continuous,orderly,rapid,massive and changing,traditional negative sequential patterns mining algorithms cannot directly process the data stream.Meanwhile,because the generation of negative sequential candidates is based on positive sequential patterns,the request response time of traditional piecewise negative sequential patterns mining method in data stream is longer,which affects the real-time performance of the algorithm.To solve the above problems,this thesis takes data stream in big data as the research object,and studies the mining method of negative sequential patterns based on sliding window mechanism and the parallel mining method of positive and negative sequential patterns based on bitmap.The main innovations in this thesis are as follows:(1)The Mining Negative Sequential Patterns Based Sliding Window(sw-NSP)algorithm is proposed to solve the problem that the traditional negative sequential patterns mining algorithm can only handle the static data set and cannot meet the demand of data stream.Firstly,the sliding window mechanism is introduced to divide the data stream into smaller windows for processing,so as to solve the problem that data streams cannot be stored at one time due to limited memory.Secondly,a prefix tree structure is designed so that the algorithm can obtain the positive sequential patterns in the current window by processing only the latest data without completely discarding the mining results of the previous window,and avoid repeated scanning of historical data.Finally,sw-NSP algorithm is proposed based on sc-NSP algorithm.In the whole mining process,sw-NSP algorithm only carries out negative sequential candidate generation operation one time,which avoids a lot of time waste caused by repeated negative sequential candidate generation.Experimental results show that sw-NSP algorithm can effectively implement negative sequential patterns mining in data streams.(2)The Mining Negative Sequential Patterns from Data Streams(nsp-DS)algorithm was proposed to solve the problem that piecewise negative sequential patterns mining algorithm could not parallelize positive and negative sequential patterns mining.Firstly,the sliding window mechanism is introduced,and the data is converted into bitmap matrix for storage.Secondly,a prefix tree structure that can store both positive and negative sequential patterns is designed to maintain the positive and negative sequential patterns in the sliding window.Finally,the nsp-DS algorithm is proposed to mine positive and negative sequential patterns parallelly in the data stream.In this algorithm,the mining results in each window are output in real time by traversing the prefix tree.Experimental results show that the nsp-DS algorithm can mine the positive and negative sequential patterns parallelly in the data stream. |
