Please use this identifier to cite or link to this item: https://repositorio.ufu.br/handle/123456789/12603
metadata.dc.type: Dissertação
metadata.dc.rights: Acesso Aberto
Title: CobMiner - Mineração de Padrões Arborescentes com Restrições
metadata.dc.creator: Silva, Nyara de Araújo
metadata.dc.contributor.advisor1: Amo, Sandra Aparecida de
metadata.dc.contributor.referee1: Meira Junior, Wagner
metadata.dc.contributor.referee2: Silva, Ilmério Reis da
metadata.dc.description.resumo: Há muito trabalho em mineração de padrões com foco em estruturas de dados simples como itemsets ou seqüência de itemsets. Entretanto, recentes aplicações utilizam dados mais complexos como componentes químicos, estruturas proteicas, rede social, XML e logs da Web, exigindo estruturas de dados mais sofisticadas (árvores ou grafos) para serem especificadas. Aqui, padrões de interesse não envolvem apenas valores de objetos frequentes labels que aparecem em árvores (ou grafos), mas também topologias específicas frequentes encontradas nessas estruturas. A mineração de padrões de árvores frequentes tem sido bastante estudada, com a motivação do crescente interesse e aplicabilidade em diferentes áreas (Web Mining, Bioinformática, etc.). Porém, os sistemas convencionais de mineração de árvores permitiam ao usuário apenas definir o suporte mínimo como mecanismo de filtro dos padrões a serem minerados. Após o processo de mineração, um árduo trabalho é necessário para filtrar os padrões de interesse dos usuários. Nessa dissertação, propomos o algoritmo CobMiner, Constrained-based Miner, um algoritmo de mineração de padrões arborescentes, incorporando ao processo de mineração os Autômatos de Árvores, como mecanismo para restringir o escopo da mineração e produzir padrões frequentes mais próximos do real interesse dos usuários. Comparamos dois métodos de inclusão das restrições do usuário dentro do processo de descoberta: o primeiro é o CobMiner que incorpora o autômato de árvore dentro do mecanismo de mineração, o segundo é o TreeMinerPP que consiste do conhecido algoritmo de mineração de árvores, TreeMiner, seguido de uma fase de pós-processamento, onde os padrões são filtrados pelo autômato de árvore. Um grande conjunto de testes foi executado em dados sintéticos e reais (documentos XML), o que nos permite concluir que utilizar as restrições durante a mineração é muito mais eficiente do que filtrar os padrões frequentes após o processo de mineração.
Abstract: Most work on pattern mining focus on simple data structures like itemsets or sequences of itemsets. However, a lot of recent applications dealing with complex data like chemical compounds, protein structure, social network, XML and Web Log databases, require much more sophisticated data structures (trees or graphs) for their specification. Here, interesting patterns involve not only frequent object values (labels) appearing in the trees (or graphs) but also frequent specific topologies found in these structures. Mining frequent tree patterns have been extensively studied, motivated by the increasing interest and applicability in different areas (Web Mining, Bioinformatics, etc). However, conventional tree mining systems normally consider only minimum support criterium as a mechanism for filtering patterns to be mined. After mining process, hard work is requiring to filter patterns concerned with user interests. In this dissertation, we propose CobMiner, Constrained-based Miner, a tree pattern mining algorithm which incorporates tree automata into the mining process in order to restrict the mining scope and to generate frequent patterns more closely related to user interests. We compare two methods for introducing user constraints into the discovery process: the first one is CobMiner which incorporates tree automata constraints as an intra-mining mechanism, the second one is TreeMinerPP which consists of a well-known tree pattern mining algorithm, TreeMiner, followed by a post-processing phase, where patterns are filtered using a tree automatum. An extensive set of experiments executed over synthetic and real data (XML documents) allow us to conclude that incorporating constraints during the mining process is far better effective than filtering the frequent and interesting patterns after the mining process.
Keywords: Descoberta de Padrões Freqüentes
Mineração de Padrões Arborescentes
Autômato de Árvore
Mineração de Dados com Restrições
Mineração de Documentos XML
Mineração na Web
Frequent Pattern Descovery
Tree Pattern Mining
Tree Automata
Constraint-based Data Mining
XML Mining
Web Mining
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: SILVA, Nyara de Araújo. CobMiner - Mineração de Padrões Arborescentes com Restrições. 2007. 88 f. Dissertação (Mestrado em Ciências Exatas e da Terra) - Universidade Federal de Uberlândia, Uberlândia, 2007.
URI: https://repositorio.ufu.br/handle/123456789/12603
Issue Date: 22-Oct-2007
Appears in Collections:PPGCC - Mestrado em Ciência da Computação

Files in This Item:
File Description SizeFormat 
Nyara.pdf882.88 kBAdobe PDFView/Open


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