PrefixSpan algorithm: derived from FreeSpan. The shrink speed is faster than FreeSpan.

University of Michigan - Ann Arbor

Sequential pattern mining is an important research field in data mining. It refers to finding frequent event sequences with a certain order from huge transaction records. At present, sequence pattern mining has been widely used in DNA sequence licensing, customer shopping behavior analysis, website access law analysis and network behavior law analysis.

For example, the transaction data of a large supermarket chain has a series of user transaction databases. Each record includes the user's ID, the time when the transaction occurred and the items involved in the transaction. If we can mine the patterns involving the association relationship between transactions, that is, the relationship between users' several purchase behaviors, we can take more targeted marketing measures.

Sequential Pattern Mining

Apriori algorithm: the original algorithm of association analysis, which is used to find frequent itemsets from candidate sets. Two steps: self connection and pruning. Disadvantages: no sequence.

AprioriAll algorithm: the execution process of AprioriAll algorithm is the same as that of Apriori algorithm. The difference lies in the generation of candidate set. It is necessary to distinguish the front and back of the last two elements.

AprioriSome algorithm: it can be regarded as an improvement of apriorall algorithm.

Apriori algorithm

GPS algorithm: it is used to find frequent itemsets with sequential order from the candidate item set. Two steps: self-connection and pruning. Disadvantages: Every time the support is calculated, all data sets need to be scanned; for the case of a very long sequence pattern, the algorithm is difficult to handle because the scale of the corresponding short sequence pattern is too large.

GPS algorithm

SPADE algorithm: Improved GPS algorithm to avoid the problem of scanning the data set D multiple times. It is roughly the same as the GSP algorithm, with an additional ID_LIST record, so that each ID_LIST is obtained according to the previous ID_LIST (thus obtaining support). The scale of ID_LIST is reduced as the pruning continues. Therefore, the problem of multiple scans of data set D by the GSP algorithm is solved.

SPADE algorithm

FreeSpan algorithm: the sequential pattern mining of frequent pattern projection. The core idea is the divide and conquer algorithm. The basic idea is: use frequent items to recursively project the sequence database to a smaller projection database set, and generate sub-sequence fragments in each projection database. This process divides the data and the frequent pattern set to be tested, and limits each test to a smaller projection database that matches it.
Advantages: reduce the overhead required to generate candidate sequences. Disadvantages: many projection databases may be generated, which is very expensive.

Learn Before

Related