Please use this identifier to cite or link to this item: https://repositorio.ufu.br/handle/123456789/12497
Document type: Dissertação
Access type: Acesso Aberto
Title: Mineração de padrões seqüênciais múltiplos
Author: Furtado, Daniel Antônio
First Advisor: Amo, Sandra Aparecida de
First member of the Committee: Silva, Ilmério Reis da
Second member of the Committee: Vieira, Marina Teresa Pires
Summary: 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.
Keywords: Mineração de dados
Banco de dados
Algoritmos de computador
Area (s) of CNPq: CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO
Language: por
Country: BR
Publisher: Universidade Federal de Uberlândia
Institution Acronym: UFU
Department: Ciências Exatas e da Terra
Program: Programa de Pós-graduação em Ciência da Computação
Quote: 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.
URI: https://repositorio.ufu.br/handle/123456789/12497
Date of defense: 13-Jun-2005
Appears in Collections:DISSERTAÇÃO - Ciência da Computação

Files in This Item:
File Description SizeFormat 
FurtadoDISSPRT.pdf1.36 MBAdobe PDFThumbnail
View/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.