Please use this identifier to cite or link to this item: https://repositorio.ufu.br/handle/123456789/12459
metadata.dc.type: Dissertação
metadata.dc.rights: Acesso Aberto
Title: VISTREE: uma linguagem visual para análise de padrões arborescentes e para especificação de restrições em um ambiente de mineração de árvores
metadata.dc.creator: Felício, Crícia Zilda
metadata.dc.contributor.advisor1: Amo, Sandra Aparecida de
metadata.dc.contributor.referee1: Julia, Rita Maria da Silva
metadata.dc.contributor.referee2: Biajiz, Mauro
metadata.dc.description.resumo: A mineração de padrões freqüentes em dados representados por estruturas mais complexas como árvores e grafos vêm crescendo muito nos últimos tempos. Entre as razões para esse crescimento está o fato do padrão arborescente ou em forma de grafo possuir mais informações do que os padrões seqüenciais, e na possibilidade de aplicação desse tipo de mineração em várias áreas como XML Mining, Web Mining e Bioinformática. Um problema que ocorre na mineração de padrões em geral é a grande quantidade de padrões gerados; sendo que muitos deles nem são do interesse do usuário. A diminuição da quantidade de padrões gerados pode ser feita restringido o tipo de padrão produzido através de especificações do usuário. Mesmo incorporando restrições no processo de mineração, a quantidade de padrões arborescentes minerados é grande, o que torna necessário uma ferramenta de análise dos padrões, possibilitando ao usuário especificar consultas para extrair da massa de padrões minerados aqueles que satisfazem os critérios de seleção da consulta. A mineração de padrões com restrição, visa obter como resultado de um processo de mineração apenas os padrões de real interesse do usuário. Uma restrição sobre padrões será representada de acordo com a estrutura dos mesmos. Para a mineração de padrões seqüencias uma forma de representá-la seria através de expressões regulares, para a mineração de padrões arborescentes, os autômatos de árvore. O uso de restrições resolve o problema da geração de uma grande quantidade de padrões, mas o mecanismo usado para representar a restrição ainda se constitui em um outro problema que seria a dificuldade de um usuário em fazer a entrada da restrição utilizando esse mecanismo. As consultas sobre padrões freqüentes são feitas de acordo com as características dos dados. Uma forma de extrair padrões específicos em dados estruturados como árvores é armazenar os padrões freqüentes em um documento XML e efetuar uma consulta usando uma das linguagens de consulta a documentos XML. Dentre as linguagens de consulta XML, a linguagem XQuery é muito utilizada, principalmente pelo fato de ser similar semanticamente a SQL (linguaguem de consulta a banco de dados). A consulta aos padrões freqüentes poderia então ser feita utilizando essa linguagem, mas para isso o usuário teria que conhecer e ser capaz de expressar sua consulta através dela. Nesse trabalho é apresentada a linguagem visual VisTree, que consiste em uma ferramenta visual a ser utilizada tanto numa fase de Pré-processamento para a especificação das preferências do usuário no que se refere ao formato dos padrões arborescentes que lhe interessa, quanto numa fase de pós-processamento para a análise dos padrões minerados. A sintaxe da VisTree se baseia na sintaxe de um fragmento simples da linguagem Tree Pattern [Miklau and Suciu 2004, Chen et al. 2003], na qual a linguagem XPath 1.0 [Clark and Derose 1999, Olteanu et al. 2002] também se baseou. Entretanto, a semântica de VisTree difere da semântica destas linguagens no sentido de que consultas de VisTree retornam conjuntos de padrões arborescentes. A VisTree utiliza a linguagem XQuery [Chamberlin 2003, Katz et al. 2003] como mecanismo de processamento de consultas: as consultas visuais especificadas em VisTree são mapeadas em consultas da XQuery e suas respostas adaptadas para se adequarem ao formato retornado por VisTree. Um sistema completo de mineração de padrões arborescentes foi desenvolvido para testar e validar o uso da linguagem VisTree em contextos específicos de aplicações. O sistema foi construído de forma modular para que novas aplicações possam ser incorporadas de maneira simples. A aplicação de mineração de árvores com restrição nas áreas de XML Mining e Web Mining foi feita através de um estudo de caso. Nas duas aplicações, o sistema utiliza a linguagem VisTree nos módulos que fazem a tarefa de Pré-Processamento (entrada da restrição) e de Análise de Padrões (entrada da consulta).
Abstract: The frequent pattern mining in data represented by more complex structures like trees and graphs are growing lately. Among the reasons for this improvement is the fact that the tree and graph patterns has more information than sequential patterns, besides there is the possibility of usage of this type of mining in several areas like XML Mining,Web Mining and Bioinformatic. A problem that occurs in mining patterns in general is the great amount of patterns generated. Being some of them not interesting for users. The decrease in the quantity of patterns generated can be done restricting the patterns types produced through the user constraint. Even incorporating constraints in the mining process, the quantity of tree pattern mined is large, what make necessary one tool for pattern analysis, possibiliting the user specify queries to extract in the mass of mined patterns that satisfy the criteria of the selection in the query. The pattern mining with constraint, aim to obtain as a result of the process of mining only the patterns with the real interest for the user. The constraint about patterns will be represented related to the structure of them. One form to represent the sequential pattern mining would be through regular expressions, for the tree pattern mining, the tree automata. The use of constraints solve the problem to generate a large amout of patterns, but the mechanism used to represent the constraint is still constituted in another problem that would be the difficult for a user do the input of constraint using this mechanism. The queries about frequent patterns are made according to the characteristics of the data. One way to extract specific patterns in data structured like trees is to store the specific patterns in a XML file and make queries using one of the query languages for XML files. Among the XML query languages, the XQuery language is very used, mainly by the fact that it s similar in semantic to SQL, the query language for databases. The frequently patterns queries could be made using this language, but, for this the user would have to know and be capable to express queries through it. In this research it will be presented the visual language VisTree that consists of visual tool to be used in a phase of preprocess for specification the user preferences that involves the format of the tree pattern that are interested to him, as in a phase of postprocess to analyze the mined patterns. The VisTree sintaxe is based on in a fragment of the Tree Pattern language[Chen et al. 2003, Che and Liu 2005], the core of XPath 1.0 [Clark and Derose 1999, Olteanu et al. 2002]. However, the semantic of VisTree differs from the semantic of these languages in the sense that VisTree queries return the sets of tree patterns. VisTree uses a XQuery language [Chamberlin 2003, Katz et al. 2003] like query process mechanism: the visual queries specified in VisTree are mapped in XQuery queries and theirs responses are adapted to fit the format returned by VisTree. VisTree works like a XQuery front-end. A complete system of mining tree pattern was developed to test and validate the use of VisTree language in specific contexts of applications. The system was made in a modular form, in a way to allow that new applications could be incorporated in a simple way. This research show the application of tree mining with constraint in the areas of XML Mining andWeb Mining through study case. In both applications, the system use the VisTree language in the preprocess modules (constraint input) and analysis of patterns (query input).
Keywords: Datamining
Mineração de árvores
Mineração de árvores com restrição
Tree mining
Constraint-based tree mining
Web mining
XML mining
Banco de dados
Mineração de dados (Computação)
metadata.dc.subject.cnpq: CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO
metadata.dc.language: por
metadata.dc.publisher.country: BR
Publisher: Universidade Federal de Uberlândia
metadata.dc.publisher.initials: UFU
metadata.dc.publisher.department: Ciências Exatas e da Terra
metadata.dc.publisher.program: Programa de Pós-graduação em Ciência da Computação
Citation: FELÍCIO, Crícia Zilda. VISTREE: uma linguagem visual para análise de padrões arborescentes e para especificação de restrições em um ambiente de mineração de árvores. 2008. 112 f. Dissertação (Mestrado em Ciências Exatas e da Terra) - Universidade Federal de Uberlândia, Uberlândia, 2008.
URI: https://repositorio.ufu.br/handle/123456789/12459
Issue Date: 25-Mar-2008
Appears in Collections:PPGCC - Mestrado em Ciência da Computação

Files in This Item:
File Description SizeFormat 
Cricia Zilda.pdf1.01 MBAdobe PDFView/Open


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