1 Extração de Informações Carlos Alberi dos Santos Melo Ivan Gesteira Costa Filho

1

Extração de Informações

Carlos Alberi dos Santos MeloIvan Gesteira Costa Filho

2

Crescente números de Crescente números de textostextos digitalizados: intranets, bibliotecas digitalizados: intranets, bibliotecas

digitais, CD-Rom, ...digitais, CD-Rom, ...

WEB

3

• Trata o problema de extração de dados Trata o problema de extração de dados a partir de uma coleção de documentos.a partir de uma coleção de documentos.

• Apenas informações relevantesApenas informações relevantes

Extração de Informações

4

IR x IE

• IR (Information Retrieval)– recuperação de páginas (documentos)– ex. nosso projeto

• IE (Information Extraction)– recuperar dados dentro de documentos– deadlines, locais e assuntos em páginas de

“call for papers”

5

Contexto

Documentos

Dados

Classificação

Extração deInformação

6

Histórico

• Linguistic String Project (60)• FRUMP - newswire (79)• DARPA - Grupos de Pesquisa (80)• MUC - Message Understanding

Conference (80)

7

Tipos de Texto

• Estruturados– Ex. tabelas, listas, XML, ...

• Não estruturados– Ex. Fichas médicas, artigos, reportagens, ...

• Semi-estruturados– Ex. Referencias bibliográficas, anuncios, ...

8

Texto Estruturados

<html><title> Some Country Codes </title><body>Some Country CodesCongo242 Egypt20 Brazil55 </body></html>

Some Country CodesCongo 242Egypt 20Brazil 55

9

Texto Não Estruturados

• Evento– Pessoa Entrando: C. Vicent Protho– Pessoa Saindo: John W. Smith– Cargo: Presidente

C. Vicent Protho, diretor executivo do deste fabricante de chips, foi nomeado ao posto adicional de presidente , sucedendo John W. Smith, que renunciou o cargo em vista de outros interesses.

10

Texto Semi-estruturados

VDO/TRC/ALG - Casa Pau Amarelo c/ 3 qts, 2sls, copa, coz, 3wcs, muro alto. Terreno medindo 936m2, area construída 248.69m2. R$50 mil.Fones: 436.1648

11

XML

• Tags SGML• Semântica no texto.• Arquivo DTD

Será XML amplamente usado na WEB?

12

XML

<!doctype CodigoTelefonico SYSTEM ”http:/www.di.ufpe.br/ias/codtel.dtt><pais>Congo</pais><codigo>242</codigo><pais>Egypt</pais><codigo>20</codigo><pais>Brazil</pais><codigo>55</codigo>

<!element CodigoTelefonico (Pais, Codigo)><!element Pais (#PCDATA)><!element Codigo (#PCDATA)>

Documento XML

DocumentoDTT

13

Técnicas de IE

WrappersPLN

•Textos não-estruturados•Técnicas simplificadas de PLN

•Textos estruturados•Aplicações Web

•Ex. html, wml, xml, ..

14

PLN

Análise Léxica /Morfológica

Análise Sintática/Semântica

Construção de Regras de Extração

Preenchimentode Templates

Análise deDiscurso

Tokenização

15

PLN - Tokenização

Tokenização




Análise deDiscurso


•Segmentação das Palavras•Divisão em segmentos (estruturas)•Pre-processamento

– ignorar partes do texto

16

PLN - Análise Léxica

Tokenização




Análise deDiscurso


•Classificação Morfológica (artigo, verbo, substantivo).•Reconhecimento de nomes próprios, empresas, datas, ...•Etiquetagem automática

17

PLN - Análise Sintática

Tokenização




Análise deDiscurso


•Construção arvore sintática•Grupos Nominais•Grupos Verbais

•Análise sintática parcial

18

PLN - Construção de Padrões

Tokenização




Análise deDiscurso


•Dicionário de padrões de Extração•Específico ao Domínio•Automática X Manual

•eficiência, portabilidade, treinamento, alterações ad hoc

19

PLN - Construção de Padrões

•O parlamento foi bombardeado pela Guerrilha.•A guerrilha bombardeou o parlamento

ALVO - foi bombardeado pela - GRUPOgrupo-nominal(ALV,cabeca(alvo-fisico))grupo-nominal(GRP,cabeca(GRP))grupo- verbal(VG,tipo(passivo),cabeca(bombardeado)

sujeito(ALV,VG)objeto(GRP,VG)

-> EventoBonbardeamento(alvo(AVL),agente(GRUPO))

Exemplo:

Regras:

20

PLN - Análise de Discurso

Tokenização




Análise deDiscurso


•Relações entre sentenças do texto.•Correferência•Ligações entre palavras.

21

PLN - Preenchimento dos Templates

Tokenização




Análise deDiscurso


•Preenches os dados em templates especificados pela aplicação.•Objetos ou tabelas

22

Avaliação do Sistema

• Corpus Etiquetado• Cobertura X Precisão• F-Measure

• Taxa Mínima de 90%

FMeasure = (2 * Cobertura * Precisão) (Cobertura + Precisão)

23

Problemas - PLN

• Adequação de Teorias• Custo de Etiquetagem

– Técnicas automáticas

• Custo de Produção– Seis especialistas mês

24

PLN X Homem

• Tipster– 38 paginas de regras– Artigos de 10 paginas

Homem MáquinaX

60% a 80% 50%

30 minutos20 horas

25

Wrappers

• Ferramenta usada para extrair dados de textos estruturados ou com algum tipo de estrutura

• Usada para permitir acesso integrado a base de dados heterogêneas

• Não usa conhecimento lingüístico• Identifica padrões no documento

26

Tarefas & Construção

• 3 Tarefas– Recuperar/ler documento– Extrair informações– Estruturar os dados (ex. BD)

• Construção– Depende do problema a ser resolvido

• Abordagem– Manual– Semi-automática– automática

27

Construção Manual

• Regras escritas manualmente em uma linguagem de programação

28

Construção Manual

• Prós– Maior precisão – Técnica simples

• Contra– Tempo e esforço de desenvolvimento– Habilidade para definição das regras– Mudança no código caso a estrutura dos

documentos seja alterada

29

COIN (Context Interchange)

• Utiliza wrappers para permitir acesso integrado a fontes de dados heterogêneas

• A intenção é construir wrappers com interfaces genéricas

• Proporcionar facilidade de reuso de código

30

Arquitetura

Interpretador

Projetista/Otimizador

Interpretador

Executor

Casamento de padrões

Acesso à rede

Especificações

Documentos Web

consultaResultados

31

ProdExt

• Extração de dados sobre produção técnica.– Ex. Autor, Título, Local, Data, ...

• Textos semi-estruturados• Arquitetura Híbrida

32

ProdExt - PLN

• Análise Léxica– Identificação de nomes de lugares, datas,

veículos, nomes próprios (desejável)

• Dicionários– Veiculo de publicação, editora

33

ProdExt - Wrappers

• Regras com peso– Autor, Título, Veiculo de Produção, ...

• Ex. Regra para Título

Se cadeia tem sinal de hifem ou dois pontos:ENTÃO incrementa a chance de ser Título( 0.25)e incrementa a chance de ser Veículo( 0.2)e incrementa a chance de ser Local( 0.1)e incrementa a chance de ser Editora( 0.015)

34

Construção semi-automática

• Uso de uma ferramenta no desenvolvimento

• Especificado de maneira interativa e com uso de exemplos

• O usuário delimita trechos que interessam

35


• Com base nos trechos selecionados, a ferramenta define um padrão sintático

• O resultado é um conjunto de dados estruturados de acordo com o modelo criado pela ferramenta

36


• Prós:– Torna mais rápido e fácil o desenvolvimento

• Contras:– Caso a estrutura do documento seja

modificado o wrapper tem que ser refeito

37

NoDoSe

• Ferramenta para estruturar e extrair dados de forma semi-automática

• Tanto o processo de estruturação quanto o de extração ocorre interativamente

38

O processo

• Especificar como os dados devem ser modelados:– A estrutura é constituída de um conjunto de nós– Cada nó é descrito por uma lista de atributos

onde cada atributo tem a forma: <nome, valor>

• Decompor o documento em regiões:– As regiões são mapeadas em nós

• Definir o formato de saída:– Relatórios, BD etc.

39

Construção Automática

• Utiliza indução para encontrar padrões a partir de um conjunto de exemplos

• O processo de aprendizagem pode gerar várias hipóteses para um mesmo dado

• A solução é ajustar o algoritmo de aprendizagem para obedecer alguns critérios

40


• Três aspectos a considerar em relação ao processo de aprendizagem:– Aprendizagem o corre de maneira

incremental ou o corpus é definido antecipadamente

– Em que linguagem(ou formalismo) será descrito o corpus e as hipóteses

– O algoritmo terá abordagem top-down ou bottom-up

41


• Prós:– Não requer nenhum esforço humano

• Contras:– As regras dependem do dos exemplos de

treinamento– Caso a estrutura dos documentos seja

alterada torna-se necessário selecionar um novo corpus e repetir o processo de aprendizagem

42

ShopBot

• Agente de compras para comércio eletrônico

• Realiza consultas em lojas on-line e extrai e resume informações de interesse

• Duas fases de atuação:– Aprendizado

• Analisa páginas utilizando técnicas de aprendizagem– Comparação

• Encontra o melhor preço de um produto específico

43

Análise

• Procura-se padrões no código do documento HTML

• Cria uma seqüência de registros separadas por tags visualmente perceptíveis como:– <HR>, , , <LI>

• Gera uma assinatura para cada registro através da remoção de tags HTML.

44

Análise

• Página de entrada:

<html> <title>CD’s</title> <body> Preços Pixies 23,00 The Cure 22,00 Suede 22,00 </body> < /html>

45

Análise

• Assinatura:<html> <title>texto</title> <body> textotexto texto texto texto texto texto </body> </html>

• A primeira e a última linha representam, cada uma, apenas 1/5 das assinaturas, enquanto as outras, idênticas, representam 3/5

• O shopBot descarta então, a primeira e a última linha

46

Avaliação de Wrappers

• O modo de avaliação não é padrão• Podem ser usados:

– Tempo de processamento em relação ao volumes de dados;

– Taxa de erros;– Custo e eficácia no processo de

aprendizagem;– F-measure, etc.

47

Bibliográfia

• Rodrigues Nunes C.C. ProdExt: Um Wrapper para Extração de Produção Técnica e Científica de Páginas Eletrônicas. Dissertação de Mestrado, UFPE, 2000.

• Cowie J., Lehnert W.. Information extraction. Comunications of the ACM, 39(1):80-91, January 1996.

• Maruyama H., Tamura K., Uramoto N. XML and Java.Addison-Wesle, 1998

Documents

1 Extração de Informações Carlos Alberi dos Santos Melo Ivan Gesteira Costa Filho