Use este identificador para citar o ir al link de este elemento: http://hdl.handle.net/1843/RVMR-6EAG8V
Tipo: Dissertação de Mestrado
Título: Distância de edição de árvores aplicada à extração de dados da web
Autor(es): Davi de Castro Reis
primer Tutor: Alberto Henrique Frade Laender
primer Co-tutor: Altigran Soares da Silva
primer miembro del tribunal : Caetano Traina Júnior
Segundo miembro del tribunal: Marcos André Gonçalves
Resumen: A World Wide Web é hoje um dos maiores repositório de informação existentes e bilhões de páginas web, tratando dos mais variados tópicos, estão ao alcance de pessoas das mais diferentes nacionalidades. Esse conteúdo, porém, é formatado para o consumo humano, e agentes computacionais têm grande dificuldade em acessar e manipular os dados contidos nas páginas da Web. Uma das opções para se contornar esse problema é escrever manualmente extratores para todas as páginas web das quais se deseja extrair dados e,portanto, torná-las adequadas para o consumo por agentes computacionais. Porém, mesmo com o advento de novas ferramentas para geração semi-automática desses extratores, ainda assim não é possível fazer a extração de dados de um grande volume de páginas web, pois, dada a necessidade da intervenção humana, essas ferramentas têm escalabilidade limitada. Esta dissertação apresenta uma nova estratégia para construção de sistemas de extração da dados da Web. Os sistemas criados a partir da estratégia proposta são completamente automáticos e podem ser usados para extração de grandes quantidades de páginas. Em nossos experimentos, realizamos a extração, de forma completamente automática, das notícias de 35 dos principais veículos de comunicação brasileiros, totalizando 4088 páginas, e atingimos um grau de precisão de 87,71%.A chave para obtenção desse resultado é o uso da técnica de distância de edição árvores. Uma vez que páginas Web são árvores serializadas, pode-se usar essa técnica para obter as variações entre as páginas e, então, extrair os dados contidos nestas páginas. Além de uma revisão extensiva do problema de distância de edição em árvores, esta dissertação apresenta um novo algoritmo para o problema. O algoritmo, denominado Restricted Top-Down Mapping, ou simplesmente RTDM, é descrito em detalhes, incluindo pseudo-código, estudo dos limites assintóticos e análise empírica, o que nos levou a conclusão que oalgoritmo supera todos os outros algoritmos, com aplicações a extração de dados da Web, existentes na literatura.
Abstract: The World Wide Web is the largest information repository nowadays, with billions of pages, dealing with several topics, available to people of different nationalities. The content of these pages, however, is formatted for human consumption, and computer agents have a lot of difficulties to access and manipulate the data in these web pages. One of the options to circumnvent this problem is to write, manually, extractors for all web pages one is interested in, and, therefore, make them suitable for computer agents. Recently, new semi-automatic extractor generation tools have been developed, but, even with these tools, it is still not possible to extract data from a large collection of web pages, due to the need of human intervention.This dissertation presents a new strategy for the construction of web data extraction systems. The systems created using the proposed strategy are completely automatic and can be used for large extractions tasks. In our experiments, we extracted in a completely automatic fashion, the news found in the pages of 35 of the main Brazilian media vehicles present on the Web, summing up a total of 4088 pages, with correctness precision of 87.71%. The key to achieve this result is the use of the tree edit distance technique. Given that web pages are serialized trees, we can use this technique to find the differences between the trees and, then, extract the data from the pages. Besides an extensive revision of the tree edit distance problem, this dissertation presents a new algorithm for the problem. The algorithm, named Restricted Top-Down Mapping, or simply RTDM, is described in details, including pseudo-code, assyntotical limits and empirical analysis, which led to the conclusion that this algorithm surpasses all other algorithms, with applications to web data extraction, available in the literature.
Asunto: World Wide Web (Sistema de recuperação da informação)
Computação
Sistemas de recuperação da informação
Mineração de dados (Computação)
Idioma: Português
Editor: Universidade Federal de Minas Gerais
Sigla da Institución: UFMG
Tipo de acceso: Acesso Aberto
URI: http://hdl.handle.net/1843/RVMR-6EAG8V
Fecha del documento: 29-abr-2005
Aparece en las colecciones:Dissertações de Mestrado

archivos asociados a este elemento:
archivo Descripción TamañoFormato 
tese.pdf1.45 MBAdobe PDFVisualizar/Abrir


Los elementos en el repositorio están protegidos por copyright, con todos los derechos reservados, salvo cuando es indicado lo contrario.