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 | Size | Format | |
---|---|---|---|---|
FurtadoDISSPRT.pdf | 1.36 MB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.