An Effective Method for Mining Negative Sequential Patterns From Data Streams

Abstract

Traditional negative sequential patterns(NSPs) mining algorithms are used to mine static dataset which are stored in equipment and can be scanned many times. Nowadays, with the development of technology, many applications produce a large amount of data at a very high speed, which is called as data stream. Unlike static data, data stream is transient and can usually be read only once. So, traditional NSP mining algorithm cannot be directly applied to data stream. Briefly, the key reasons are: (1) inefficient negative sequential candidates generation method, (2) one-time mining, (3) lack of real-time processing. To solve this problem, this paper proposed a new algorithm mining NSP from data stream, called nsp-DS. First, we present a method to generate positive and negative sequential candidates simultaneously, and a new negative containment definition. Second, we use a sliding window to store sample data in current time. The continuous mining of entire data stream is realized through the continuous replacement of old and new data. Finally, a prefix tree structure is introduced to store sequential patterns. Whenever the user requests, it traverses the prefix tree to output sequential patterns. The experimental results show that nsp-DS may discover NSPs from data streams.

Keywords

• Data stream
• transient
• sliding window
• negative sequential patterns (NSPs)