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). / 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). / Mestre em Ciência da Computação
| Identifer | oai:union.ndltd.org:IBICT/urn:repox.ist.utl.pt:RI_UFU:oai:repositorio.ufu.br:123456789/12459 |
| Date | 25 March 2008 |
| Creators | Felício, Crícia Zilda |
| Contributors | Amo, Sandra Aparecida de, Julia, Rita Maria da Silva, Biajiz, Mauro |
| Publisher | Universidade Federal de Uberlândia, Programa de Pós-graduação em Ciência da Computação, UFU, BR, Ciências Exatas e da Terra |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | Portuguese |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis |
| Format | application/pdf |
| Source | reponame:Repositório Institucional da UFU, instname:Universidade Federal de Uberlândia, instacron:UFU |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.011 seconds