Publicação: Mineração de padrões seqüênciais múltiplos
Carregando...
Arquivos
Tipo do documento
Data
Direito de acesso
Área do conhecimento
CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO
Título da Revista
ISSN da Revista
Título de Volume
Autores
Orientador
Coorientador
Resumo
A descoberta de padrões seqüenciais constitui um importante problema em mineração de dados e possui aplicações nas mais diversas áreas tais como mercado financeiro, medicina,
análise de mercado, telecomunicações, comércio eletrônico, etc. A maioria das pesquisas já realizadas sobre a mineração de padrões seqüenciais concentra-se na descoberta de padrões temporais que podem ser especificados, de alguma maneira, na Lógica Temporal Proposicional. Entretanto, existem alguns padrões seqüenciais interessantes que necessitam de um formalismo mais expressivo, o da Lógica Temporal de Primeira Ordem.
Nesta dissertação estamos propondo um novo padrão temporal, que denominamos de padrão seqüencial múltiplo, que é um padrão temporal de primeira ordem e tem como ob-
jetivo representar o perfil de indivíduos/objetos relacionados entre si, ao longo do tempo. Nosso padrão possui aplicações em várias áreas, como no mercado financeiro e no varejo.
Propomos dois algoritmos para efetuar a mineração de todos esses padrões freqüentes em um banco de dados: o algoritmo PM (Projection Miner), que realiza a mineração decompondo o padrão de primeira ordem em componentes proposicionais e adapta idéias do algoritmo GSP (que minera padrões seqüenciais proposicionais); e o algoritmo SM (Simul-
taneous Miner), que efetua a mineração do padrão de primeira ordem sem decompô-lo.
Nossos resultados experimentais mostram que a performance de SM é superior a de PM. Também exploramos um mecanismo que permite o controle por parte do usuário com
relação aos padrões múltiplos que são minerados. Propomos o algoritmo MSP-Miner, que incorpora no processo de mineração uma restrição especificada pelo usuário através de
expressões regulares. MSP-Miner encontra somente os padrões múltiplos satisfazendo a restrição informada. A performance e a escalabilidade desse algoritmo foi avaliada através de um conjunto de testes realizados em bancos de dados sintéticos.
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.
Palavras-chave
Mineração de dados, Banco de dados, Algoritmos de computador
Citação
FURTADO, Daniel Antônio. Mineração de padrões seqüênciais múltiplos. 2005. 115 f. Dissertação (Mestrado em Ciências Exatas e da Terra) - Universidade Federal de Uberlândia, Uberlândia, 2005.