Mineração de padrões seqüênciais múltiplos

Abstract

Discovering sequential patterns is an important problem in data mining with a lot of application domains including financial market, medicine, retailing, telecommunications, e-commerce, etc. Previous studies on mining sequential patterns have focused on temporal patterns specified by some form of propositional temporal logic. However, there are some interesting sequential patterns whose specification needs a more expressive formalism, the first-order temporal logic. In this dissertation, we propose a new temporal pattern, called multi-sequential pattern, which is a first-order temporal pattern (not expressible in propositional temporal logic) and aims at representing the behaviour of individuals/objects related to each other by some criteria, throughout time. Our pattern appears in many application domains, like financial market and retailing. We propose two Apriori-based algorithms to find all frequent patterns in a given dataset: the PM algorithm (Projection Miner), that performs the mining task by projecting the first-order pattern in two propositional components and adapts the key idea of the classical GSP algorithm (for propositional sequential pattern mining); and the SM (Simultaneous Miner) algorithm, that finds out the first-order pattern without decomposing it. Our extensive experiments shows that SM scales up far better than PM. Beyond that, we extend a well-known user-controlled tool, based on regular expressions constraints, to the multi-sequential pattern context. This specification tool enables the incorporation of user focus into the multi-sequential patterns mining process. We also present MSP-Miner, an Apriori-based algorithm to discover all frequent multi-sequential patterns satisfying a user-specified regular expression constraint. We perform detailed experiments on synthetic data to study the performance and scalability of MSP-Miner.