Extração de Informações
Carlos Alberi dos Santos Melo
Ivan Gesteira Costa Filho
1
WEB
Crescente números de textos
digitalizados: intranets, bibliotecas
digitais, CD-Rom, ...
2
Extração de Informações
• Trata o problema de extração de dados
a partir de uma coleção de documentos.
• Apenas informações relevantes
3
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”
4
Contexto
Documentos
Classificação
Extração de
Informação
Dados
5
Histórico
•
•
•
•
Linguistic String Project (60)
FRUMP - newswire (79)
DARPA - Grupos de Pesquisa (80)
MUC - Message Understanding
Conference (80)
6
Tipos de Texto
• Estruturados
– Ex. tabelas, listas, XML, ...
• Não estruturados
– Ex. Fichas médicas, artigos, reportagens, ...
• Semi-estruturados
– Ex. Referencias bibliográficas, anuncios, ...
7
Texto Estruturados
<html><title> Some Country Codes </title>
<body><b>Some Country Codes</b><p>
<b>Congo</b><i>242</i><BR>
<b>Egypt</b><i>20</i><BR>
<b>Brazil</b><i>55</i><BR>
</body></html>
Some Country Codes
Congo 242
Egypt 20
Brazil 55
8
Texto Não Estruturados
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.
• Evento
– Pessoa Entrando: C. Vicent Protho
– Pessoa Saindo: John W. Smith
– Cargo: Presidente
9
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
10
XML
• Tags SGML
• Semântica no texto.
• Arquivo DTD
Será XML amplamente
usado na WEB?
11
XML
Documento
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>
Documento <!element CodigoTelefonico (Pais, Codigo)>
<!element Pais (#PCDATA)>
DTT
<!element Codigo (#PCDATA)>
12
Técnicas de IE
PLN
•Textos não-estruturados
•Técnicas simplificadas
de PLN
Wrappers
•Textos estruturados
•Aplicações Web
•Ex. html, wml, xml, ..
13
PLN
Tokenização
Análise Léxica
/Morfológica
Análise Sintática
/Semântica
Construção de
Regras de Extração
Análise de
Discurso
Preenchimento
de Templates
14
PLN - Tokenização
Tokenização
Análise Léxica
/Morfológica
Análise Sintática
/Semântica
•Segmentação das Palavras
•Divisão em segmentos (estruturas)
•Pre-processamento
Construção de
Análise de
– ignorarRegras
partesdedo
texto
Extração
Discurso
Preenchimento
de Templates
15
PLN - Análise Léxica
Tokenização
Análise Léxica
/Morfológica
Análise Sintática
/Semântica
Construção
de
Análise de
•Classificação Morfológica
(artigo,
verbo,
Regras de Extração
Discurso
substantivo).
•Reconhecimento de nomes próprios, empresas,
datas, ...
Preenchimento
•Etiquetagem automática
de Templates
16
PLN - Análise Sintática
Tokenização
Análise Léxica
/Morfológica
Análise Sintática
/Semântica
Construção
•Construção
arvore de
sintática Análise de
Regras
de Extração
Discurso
•Grupos
Nominais
•Grupos Verbais
•Análise sintática parcial
Preenchimento
de Templates
17
PLN - Construção de Padrões
•Dicionário de padrões de Extração
•Específico ao Domínio
Tokenização
•Automática X Manual
•eficiência, portabilidade, treinamento,
alterações
Análise
Léxica ad hoc
Análise Sintática
/Morfológica
/Semântica
Construção de
Regras de Extração
Análise de
Discurso
Preenchimento
de Templates
18
PLN - Construção de Padrões
Exemplo:
Regras:
•O parlamento foi bombardeado pela Guerrilha.
•A guerrilha bombardeou o parlamento
ALVO - foi bombardeado pela - GRUPO
grupo-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))
19
PLN - Análise de Discurso
Tokenização
•Relações entre sentenças do texto.
•Correferência
•Ligações entre palavras.
Análise Léxica
/Morfológica
Análise Sintática
/Semântica
Construção de
Regras de Extração
Análise de
Discurso
Preenchimento
de Templates
20
PLN - Preenchimento dos
Templates
Tokenização
Análise Léxica
/Morfológica
Análise Sintática
/Semântica
•Preenches os dados em templates especificados
pela aplicação.
Construção de
Análise de
•Objetos ou tabelas
Regras de Extração
Discurso
Preenchimento
de Templates
21
Avaliação do Sistema
• Corpus Etiquetado
• Cobertura X Precisão
• F-Measure
FMeasure = (2 * Cobertura * Precisão)
(Cobertura + Precisão)
• Taxa Mínima de 90%
22
Problemas - PLN
• Adequação de Teorias
• Custo de Etiquetagem
– Técnicas automáticas
• Custo de Produção
– Seis especialistas mês
23
PLN X Homem
• Tipster
– 38 paginas de regras
– Artigos de 10 paginas
Homem
X
Máquina
60% a 80%
50%
20 horas
30 minutos
24
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
25
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
26
Construção Manual
• Regras escritas manualmente em uma
linguagem de programação
27
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
28
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
29
Arquitetura
consulta
Resultados
Interpretador
Projetista/Otimizador
Executor
Casamento de padrões
Interpretador
Acesso à rede
Especificações
Documentos
Web
30
ProdExt
• Extração de dados sobre produção
técnica.
– Ex. Autor, Título, Local, Data, ...
• Textos semi-estruturados
• Arquitetura Híbrida
31
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
32
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)
33
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
34
Construção semi-automática
• 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
35
Construção semi-automática
• 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
36
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
37
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.
38
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
39
Construção Automática
• 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
40
Construção Automática
• 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
41
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
42
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>, <P>, <BR>, <LI>
• Gera uma assinatura para cada registro
através da remoção de tags HTML.
43
Análise
• Página de entrada:
<html>
<title>CD’s</title>
<body>
<B>Preços</B><P>
<B>Pixies</B> <I>23,00</I><br>
<B>The Cure</B> <I>22,00</I><br>
<B>Suede</B> <I>22,00</I><br>
</body>
< /html>
44
Análise
• Assinatura:
<html> <title>texto</title> <body> <B>texto</B><P>
<B>texto</B> <I>texto</I><br>
<B>texto</B> <I>texto</I><br>
<B>texto</B> <I>texto</I><br>
</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
45
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.
46
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
47