SBBD 2006 Extração de dados e metadados em textos semi-estruturados usando HMMs Universidade...

SBBD 2006SBBD 2006

Extração de dados e metadadosem textos semi-estruturados

usando HMMs

Universidade Federal do AmazonasUniversidade Federal do AmazonasDepartamento de Ciência da ComputaçãoDepartamento de Ciência da Computação

Roberto Oliveira dos SantosFilipe de Sá Mesquita

Altigran Soares da SilvaEli Cortez

{ros, fsm, alti, eccv}@dcc.ufam.edu.br

SBBD 2006SBBD 2006 22

• Introdução

• Trabalhos relacionados

• Extração em textos semi-estruturados usando HMM

• Extração de dados e metadados

• Experimentos

• Conclusões e trabalhos futuros

Roteiro

SBBD 2006SBBD 2006 33

Introdução

• A Web pode ser considerada como sendo um grande repositório de dados

• Produzidos para consumo humano• Difícil de realizar tarefas como:

– Busca– Consulta– Mineração

• Texto semi-estruturado [Laender, SIGMOD/02]– Escondem uma estrutura implícita– Contém dados dispostos de forma contínua onde não há

delimitadores explícitos

SBBD 2006SBBD 2006 44

Introdução

Notícias

Por Exemplo:

SBBD 2006SBBD 2006 55

Introdução

Anúncios de Imóveis

Por Exemplo:

SBBD 2006SBBD 2006 66

Introdução

Por Exemplo:

Anúncios de Imóveis

SBBD 2006SBBD 2006 77

Introdução

Ano Bom. Av. Major José Bento, ótima casa, c/ varanda, gar., sl., 3 qtos. (ste.), banh. soc., copa, coz.

Ano Bom. Av. Major José Bento, ótima casa, c/ varanda, gar., sl., 3 qtos. (ste.), banh. soc., copa, coz.

SBBD 2006SBBD 2006 88

Introdução

Ano Bom. Av. Major José Bento, ótima casa, c/ varanda, gar., sl., 3 qtos. (ste.), banh. soc., copa, coz.

Ano Bom. Av. Major José Bento, ótima casa, c/ varanda, gar., sl., 3 qtos. (ste.), banh. soc., copa, coz.

BAIRRO ENDEREÇO

QUARTOS

SALA

SBBD 2006SBBD 2006 99

• [Embley, DKE/99]– Escrever ontologias para extração

• Identificar palavras-chaves para extrair o dado relacionado

• As ontologias são escritas manualmente

• [Viola, SIGIR/05]– Gramáticas livres de contexto– Extração em textos semi-estruturados– Treino exaustivo.

Trabalhos relacionados

SBBD 2006SBBD 2006 1010

• DATAMOLD [Borkar, SIGMOD/01]– HMM– Extração em textos semi-estruturados– Todos os termos são Dados;

• Nestes trabalhos, é desconsiderada a necessidade de extração dos metadadosmetadados.

• Muitos textos semi-estruturados disponíveis na Web são ricos em metadados, como é o caso de anúncios de classificados.

Trabalhos relacionados

SBBD 2006SBBD 2006 1111

Objetivo

• Principal ContribuiçãoPrincipal Contribuição

– Uma novanova formulação para o problema de extração em textos semi-estruturados, visando extrair dados e metadadosmetadados em cada atributo.

SBBD 2006SBBD 2006 1212

Importância do metadado

Vendo casa grande com 2 qtos., sl., banheiro, coz. e quintal, por apenas R$ 82.000,00.

Vendo casa grande com 2 qtos., sl., banheiro, coz. e quintal, por apenas R$ 82.000,00.

SBBD 2006SBBD 2006 1313

Importância do metadado

Vendo casa grande com 2 qtos., sl., banheiro, coz. e quintal, por apenas R$ 82.000,00.

Vendo casa grande com 2 qtos., sl., banheiro, coz. e quintal, por apenas R$ 82.000,00.

QUARTOS 2 qtos.

ATRIBUTO VALOR

SBBD 2006SBBD 2006 1414

Importância do metadado

Vendo casa grande com 2 qtos., sl., banheiro, coz. e quintal, por apenas R$ 82.000,00.

Vendo casa grande com 2 qtos., sl., banheiro, coz. e quintal, por apenas R$ 82.000,00.

QUARTOS 2 qtos.

SALA Sim sl.

ATRIBUTO VALOR

SBBD 2006SBBD 2006 1515

Importância do metadado

Vendo casa grande com 2 qtos., sl., banheiro, coz. e quintal, por apenas R$ 82.000,00.

Vendo casa grande com 2 qtos., sl., banheiro, coz. e quintal, por apenas R$ 82.000,00.

QUARTOS 2 qtos.

SALA Sim sl.

... ... ... ...

PREÇO 82.000,00 R$

ATRIBUTO VALOR

SBBD 2006SBBD 2006 1616

Importância do metadado

Vendo casa grande com 2 qtos., sl., banheiro, coz. e quintal, por apenas R$ 82.000,00.

Vendo casa grande com 2 qtos., sl., banheiro, coz. e quintal, por apenas R$ 82.000,00.

QUARTOS 2 qtos.

SALA Sim sl.

... ... ... ...

PREÇO 82.000,00 R$

METADADOATRIBUTO VALOR

SBBD 2006SBBD 2006 1717

Importância do metadado

Vendo casa grande com 2 qtos., sl., banheiro, coz. e quintal, por apenas R$ 82.000,00.

Vendo casa grande com 2 qtos., sl., banheiro, coz. e quintal, por apenas R$ 82.000,00.

QUARTOS 2 qtos.

SALA Sim sl.

... ... ... ...

PREÇO 82.000,00 R$

TIPO casa -

METADADOATRIBUTO VALOR

SBBD 2006SBBD 2006 1818

Conceitos

• Caracterizamos textos semi-estruturados (TS) como um conjunto de Atributos, onde:– TS = {A1, A2,...,An};– Ai = {D, M}– D = {d1, d2,..., dk};– M = {m1, m2, ..., ml}– D ou M podem ser vazios

• D = , assume-se que ele é verdadeiro.

– Aextra: São extraídos mas não fazem parte de nenhum outro atributo (ruídos).

SBBD 2006SBBD 2006 1919

Conceitos

Ano Bom. Av. Major, josé bento, casa grande c/ varanda, gar., sl.,

3 qtos. (ste.), banh. soc., copa, coz.

Ano Bom. Av. Major, josé bento, casa grande c/ varanda, gar., sl.,

3 qtos. (ste.), banh. soc., copa, coz.

SALASALA

Metadado: “sl.”

Dado: vazio

QUARTOSQUARTOS

Metadado: “qtos.”

Dado: “3”

EXTRAEXTRA

Dado: grande c/

SBBD 2006SBBD 2006 2020

Problemas

SBBD 2006SBBD 2006 2121

• Determinar os metadadosmetadados

Ano Bom. Av. Major José bento, ótima casa, c/ varanda, gar., sl., 3 qtos. (ste.), banh. soc., copa, coz.

Ano Bom. Av. Major José bento, ótima casa, c/ varanda, gar., sl., 3 qtos. (ste.), banh. soc., copa, coz.

Problemas

SBBD 2006SBBD 2006 2222

• Determinar os metadadosmetadados

• Associar o(s) dado(s) ao seu metadadometadado relacionado;

Ano Bom. Av. Major José bento, ótima casa, c/ varanda, gar., sl., 3 qtos. (ste.), banh. soc., copa, coz.

Ano Bom. Av. Major José bento, ótima casa, c/ varanda, gar., sl., 3 qtos. (ste.), banh. soc., copa, coz.

Problemas

Ano Bom. Av. Major José bento, ótima casa, c/ varanda, gar., sl., 3 qtos. (ste.), banh. soc., copa, coz.

Ano Bom. Av. Major José bento, ótima casa, c/ varanda, gar., sl., 3 qtos. (ste.), banh. soc., copa, coz.

SBBD 2006SBBD 2006 2323

Problemas

• Determinar os metadadosmetadados

• Associar o(s) dado(s) ao seu metadadometadado relacionado;

• Delimitar quais os termos fazem parte de um atributo;

Ano Bom. Av. Major José bento, ótima casa, c/ varanda, gar., sl., 3 qtos. (ste.), banh. soc., copa, coz.

Ano Bom. Av. Major José bento, ótima casa, c/ varanda, gar., sl., 3 qtos. (ste.), banh. soc., copa, coz.

Ano Bom. Av. Major José bento, ótima casa, c/ varanda, gar., sl., 3 qtos. (ste.), banh. soc., copa, coz.

Ano Bom. Av. Major José bento, ótima casa, c/ varanda, gar., sl., 3 qtos. (ste.), banh. soc., copa, coz.

Ano Bom. Av. Major José bento, ótima casa, c/ varanda, gar., sl., 3 qtos. (ste.), banh. soc., copa, coz.

Ano Bom. Av. Major José bento, ótima casa, c/ varanda, gar., sl., 3 qtos. (ste.), banh. soc., copa, coz.

SBBD 2006SBBD 2006 2424

Extração em textos semi-estruturados usando HMM

• Proposto por Rabiner [Rabiner, IEEE/89]

• Procura determinar eventos não-observáveis/ocultos (ATRIBUTOS) a partir de estados observáveis (SÍMBOLOS)

• Cada estado emite um símbolo

• Sabemos: os símbolos

• Queremos descobrir: a sequência de estados que emitiram os símbolos

SBBD 2006SBBD 2006 2525

• Um HMM é um autômato finito determinístico– Vértices: ESTADOS (Ex: SALA, QUARTO, VALOR,

etc.)– Arestas: PROBABILIDADE DE TRANSIÇÃO– Um símbolo é consumido/emitido em cada estado

• Símbolos– Termos como: “qto.”, “sl.”, “coz.”, “2”, “R$”, etc.

Extração em textos semi-estruturados usando HMM

SBBD 2006SBBD 2006 2626

• Probabilidades de emissão:– Probabilidade do estado E emitir símbolos S: E (S)

• Probabilidade de transição– Probabilidade de um estado ocorrer após outro– QUARTO COZINHA = 43%

Extração em textos semi-estruturados usando HMM

SBBD 2006SBBD 2006 2727

• Alg. ViterbiAlg. Viterbi

• O algoritmo de Viterbi:– Baseado em programação dinâmica– Encontra a sequência mais provável a um

custo O(xN2)• x é a quantidade de SÍMBOLOS de entrada• N é o número de ESTADOS conhecidos

Extração em textos semi-estruturados usando HMM

SBBD 2006SBBD 2006 2828

HMM em dois níveis para extração de dados e metadados

SBBD 2006SBBD 2006 2929

HMM em dois níveis para extração de dados e metadados

HMM ExternoHMM ExternoHMM ExternoHMM ExternoESTADOS → Atributos

SBBD 2006SBBD 2006 3030

HMM em dois níveis para extração de dados e metadados

N

HMM ExternoHMM ExternoHMM ExternoHMM Externo

HMM InternoHMM InternoHMM InternoHMM Interno

ESTADOS → Atributos

ESTADOS → Dados e Metadados

SBBD 2006SBBD 2006 3131

HMM em dois níveis para extração de dados e metadados

• Alterações no HMM clássico– Suavização: Função para gerar a probabilidade de

emissão de símbolos no 2º nível (HMM interno)– Viterbi Externo

• Detectar a seq. de atributos mais prováveis

– Viterbi Interno• Detectar os dados e metadados mais prováveis para um

conjunto de termos observáveis

– Queremos descobrir: a seqüência de estados que emitiram os símbolos(termos) e qual a característica de cada termo.

• Dados e Metadados dos atributos

SBBD 2006SBBD 2006 3232

Vendo casa grande c/ 2 qtos., sl., banh., coz., por apenas R$ 82.000,00.Vendo casa grande c/ 2 qtos., sl., banh., coz., por apenas R$ 82.000,00.

HMM em dois níveis para extração de dados e metadados

• TreinamentoTreinamento

SBBD 2006SBBD 2006 3333

• TreinamentoTreinamento

Vendo casa grande c/ 2 qtos., sl., banh., coz., por apenas R$ 82.000,00.Vendo casa grande c/ 2 qtos., sl., banh., coz., por apenas R$ 82.000,00.

[ATRIBUTO (HMM Externo) = <(D,M): ... , (M,D): ...> (HMM Interno)];

HMM em dois níveis para extração de dados e metadados

SBBD 2006SBBD 2006 3434

• TreinamentoTreinamento

Vendo casa grande c/ 2 qtos., sl., banh., coz., por apenas R$ 82.000,00.Vendo casa grande c/ 2 qtos., sl., banh., coz., por apenas R$ 82.000,00.

[EXTRA=<D: Vendo >];[TIPO=<D: casa >];[EXTRA=<D: c/ >];[QUARTOS=<D: 2, M: qtos. >];[SALA=<M: sl. >];[BANHEIRO=<M: banheiro >];[COZINHA=<M: coz. >];[EXTRA=<D: por apenas >];[PREÇO=<M: R$, D: 82.000,00. >];

HMM em dois níveis para extração de dados e metadados

[ATRIBUTO (HMM Externo) = <(D,M): ... , (M,D): ...> (HMM Interno)];

SBBD 2006SBBD 2006 3535

ExperimentosExperimentos

SBBD 2006SBBD 2006 3636

• Sites de anúncios para testes

• 120 exemplos de cada Web site– 20 para treinamento; (Rotulados manualmente)– 100 para testes (cada site);

Experimentos

SBBD 2006SBBD 2006 3737

• Objetivo– Verificar a eficácia do processo de extração em

três granularidades de problemas:• 1. Dados e Metadados• 2. Atributos• 3. Anúncios extraídos corretamente como um todo

Experimentos

SBBD 2006SBBD 2006 3838

Experimentos 1

Percentual de precisão nos acertos na extração dos dados, metadados e termos o atributo extra.

Vendo Casa, sl., 2 qtos. e cozinha.Vendo Casa, sl., 2 qtos. e cozinha.

SBBD 2006SBBD 2006 3939

Vendo Casa, sl., 2 qtos. e cozinha.Vendo Casa, sl., 2 qtos. e cozinha.MMM

Experimentos 1

Percentual de precisão nos acertos na extração dos dados, metadados e termos o atributo extra.

SBBD 2006SBBD 2006 4040

Vendo Casa, sl., 2 qtos. e cozinha.Vendo Casa, sl., 2 qtos. e cozinha.MMM DD

Experimentos 1

Percentual de precisão nos acertos na extração dos dados, metadados e termos o atributo extra.

SBBD 2006SBBD 2006 4141

Vendo Casa, sl., 2 qtos. e cozinha.Vendo Casa, sl., 2 qtos. e cozinha.X MMM DDX

Experimentos 1

Percentual de precisão nos acertos na extração dos dados, metadados e termos o atributo extra.

SBBD 2006SBBD 2006 4242

Tipo

Vendo Casa, sl., 2 qtos. e cozinha.Vendo Casa, sl., 2 qtos. e cozinha.X MMM DDX

Experimentos 1

Percentual de precisão nos acertos na extração dos dados, metadados e termos o atributo extra.

SBBD 2006SBBD 2006 4343

Tipo

Vendo Casa, sl., 2 qtos. e cozinha.Vendo Casa, sl., 2 qtos. e cozinha.X MMM DDX

Experimentos 1

Percentual de precisão nos acertos na extração dos dados, metadados e termos o atributo extra.

SBBD 2006SBBD 2006 4444

Vendo Casa, sl., 2 qtos. e coz.Vendo Casa, sl., 2 qtos. e coz.

Experimentos 2

Médias por site da medida-F para delimitaçãodelimitação dos atributos.

SBBD 2006SBBD 2006 4545

[EXTRA: Vendo]

[TIPO: Casa]

[SALA: sl.]

[QUARTO: 2 qtos.]

[EXTRA: e]

[COZINHA: coz.]

Vendo Casa, sl., 2 qtos. e coz.Vendo Casa, sl., 2 qtos. e coz.

Experimentos 2

Médias por site da medida-F para delimitaçãodelimitação dos atributos.

SBBD 2006SBBD 2006 4646

Vendo Casa, sl., 2 qtos. e coz.Vendo Casa, sl., 2 qtos. e coz.

AtributosAtributos

Experimentos 2

[EXTRA: Vendo]

[TIPO: Casa]

[SALA: sl.]

[QUARTO: 2 qtos.]

[EXTRA: e]

[COZINHA: coz.]

Médias por site da medida-F para delimitaçãodelimitação dos atributos.

SBBD 2006SBBD 2006 4747

Vendo Casa, sl., 2 qtos. e coz.Vendo Casa, sl., 2 qtos. e coz.

AtributosAtributos

Experimentos 2

[EXTRA: Vendo]

[TIPO: Casa]

[SALA: sl.]

[QUARTO: 2 qtos.]

[EXTRA: e]

[COZINHA: coz.]

Médias por site da medida-F para delimitaçãodelimitação dos atributos.

SBBD 2006SBBD 2006 4848

Experimentos 3

Corretude na extração dos anúncios

SBBD 2006SBBD 2006 4949

Experimentos 3

Corretude na extração dos anúncios

Anúncios que foram extraídos corretamente

SBBD 2006SBBD 2006 5050

Corretude na extração dos anúncios

Experimentos 3

Atributos que existiam no anúncio e foram extraídos corretamente pelo método

SBBD 2006SBBD 2006 5151

• Neste artigo apresentamos:– Nova formulação para extração em texto semi-

estruturado, a qual considera a importância dos metadados.

– Nova abordagem que utiliza uma estrutura aninhada de HMM:

• Um HMM externo identifica os atributos implícitos ocorrendo no texto

• Vários HMMs internos identificam os dados e metadados de cada atributo individualmente.

Conclusões

SBBD 2006SBBD 2006 5252

• Experimentos sobre 7 conjuntos de anúncios de classificados de imóveis coletados da Web mostram:– Precisão média 97% na identificação de dados e

metadados.– A qualidade da extração de atributos superior a 0,97

(medida-F).– Eficácia da extração de anúncios 0,98 (medida-F).

• Resultados foram obtidos usando 20% dos anúncios no treinamento.– Este percentual é consideravelmente menor do que os

utilizados na literatura.– Isso pode ser explicado em parte pela ênfase que é

dada à identificação de metadados.

Conclusões

SBBD 2006SBBD 2006 5353

• Testar o método em outros domínios

• Aumentar a precisão na detecção dos metadados

• Propor uma maneira de reduzir, ainda mais, o esforço do usuário no momento do treinamento

• Construir aplicações reais utilizando o método proposto.

Trabalhos futuros

SBBD 2006SBBD 2006

• Projetos:– Tamanduá (MCT/FINEP/CT-INFO-Grade-01/2004)– Gerindo (MCT/CNPq/CT-INFO 552.087/02-5)– SIRIAA (CNPq/ CT-Amazônia 55.3126/2005-9).

• CAPES

Agradecimentos

UOL (www.uol.com.br), através do Programa UOL Bolsa Pesquisa.UOL Bolsa Pesquisa.

SBBD 2006SBBD 2006 5555

Referências

• [Embley, DKE/99] David W. Embley et. Al. Conceptual-model-based data extraction from multiplerecord web pages. Data & Knowledge Engineering, 31(3):227–251.

• [Borkar, SIGMOD/01] Vinayak R. Borkar, Kaustubh Deshmukh and Sunita Sarawagi. Automatic Segmentation of Text into Structured Records. SIGMOD Conference, 2001.

• [Laender, SIGMOD/02] Laender, A. H. F. et al. (2002). A brief survey of web data extraction tools. SIGMOD Record, 31(2):84–93.

• [RAPIER, CIAAI/99] Califf, M. E., and Mooney, R.J. Relational Learning of Pattern-Match Rules for Information Extraction. In Proceedings of the Sixteenth National Conference on Artificial Inteligence and Eleventh Conference on Innovative Application of Artificial Inteligence (Orlando, Florida, 1999), pp. 328-334.

• [Rabiner, IEEE/89] Rabiner, L. R. (1989). A tutorial on hidden markov models and selected applications in speech recongnition. Proceedings of the IEEE, 77(2):257–286.

SBBD 2006SBBD 2006 5656

Medida-F

Fi = 2(Ri Pi) / (Ri + Pi)

Ri = (Si Ti) / Si

Pi = (Si Ti) / Ti

Si = Termos que pertencem ao atributo

Ti = Termos identificados corretamente como dados ou metadados

SBBD 2006SBBD 2006 5757

• EMBLEY– Foi um journal, com resultados de vários outros trabalhos

• Outros exemplos de metadados (MCT)• Diferenca em relacao ao VIOLA

– Ele não usa HMM– Treino é muito exaustivo

• Diferenca em relacao ao BORKAR– Não considera metadados– Ele é aplicado em bases onde todos os termos são importantes e

devem ser extraídos(ref. Bib e enderecos)

• Os textos de anúncios são extraídos através de um processo existente como alguns apresentados na literatura.