Agrupamento Automático de Páginas Web utilizando Técnicas dericardo/ficheiros/MasterThesis_RCampos... · 2013. 6. 15. · Agrupamento Automático de Páginas Web utilizando Técnicas

Agrupamento Automático de

Páginas Web utilizando Técnicas de

Web Content Mining

Ricardo Campos

Orientador: Professor Doutor Gaël Dias

Universidade da Beira Interior Departamento de Informática Mestrado em Eng.ª Informática

Agrupamento Automático de Páginas Web utilizando Técnicas de Web Content Mining - [wise . d i . u b i . p t ]

Sumário

• Introdução

• Trabalho Relacionado

• Contribuição

• Solução Proposta

• Resultados

• Objectivos

• Trabalhos Futuros

• Conclusão


Sumário

• Introdução


• Contribuição


• Resultados

• Objectivos


• Conclusão


Introdução

Os motores de busca confrontam-se com o problema de terem que

ajudar os utilizadores a lidar com mais informação do que aquela que

estes conseguem absorver;

Com a disponibilização massiva de novos conteúdos na Internet, a

pesquisa de informação (Information Retrieval) tornou-se cada vez

mais importante;

A localização e a organização de recursos com conteúdo relevante e

de qualidade é uma tarefa complicada;

A relevância dos documentos obtidos pode até ser virtual e não

satisfazer as necessidades do utilizador. Os utilizadores acabam por

ignorar dados preciosos;


Introdução

Estes problemas advêm do facto dos motores de busca:

Não interpretarem o conteúdo dos documentos no seu contexto geral

da língua (i.e., tendo em conta as ambiguidades da linguagem segundo

o contexto tratado). Não têm em atenção uma forte análise semântica;

(1)

Não apresentarem como consequência, a informação de forma

estruturada, i.e., classificada. (2)

Em resumo, os sistemas não estão, por um lado, capacitados para

entender o que os utilizadores procuram e por outro devolvem um

conjunto enorme de informação não estruturada.

Palavras utilizadas na

query do utilizador

Palavras utilizadas na

descrição da WebPage


Sumário

• Introdução


• Contribuição


• Resultados

• Objectivos


• Conclusão


Objectivos

Dar resposta a estes problemas. Como?

Desenvolver um meta motor de busca que encontre, analise,

entenda, desambigúe e organize a informação dispersa por entre

várias páginas de resultados;

Tornar o processo, anteriormente realizado pelos utilizadores, num

processo automático;

Agrupar os documentos em clusters, facilitando

a procura de informação em bases de dados

textuais, em particular a informação existente na

WWW;

Apresentar a informação, hierarquicamente

agrupada e desambiguada de conceitos;


Sumário

• Introdução


• Contribuição


• Resultados

• Objectivos


• Conclusão


Trabalho Relacionado

A comunidade de IR sugere na diferente literatura publicada,

diferentes soluções para o problema da pesquisa e organização de

resultados;

Mas todos os trabalhos estudados têm em

comum o facto de apenas considerarem o

título e o snippet de cada um dos resultados

devolvidos;

Jiang et al (2002) refere que os resultados são obviamente inferiores

quando comparados com o uso de todo o texto;

Ferragina et al (2005) tenta por isso enriquecer a utilização dos

snippets com o uso de duas bases de conhecimento, mas isto torna

a sua aplicação dependente das mesmas;

Snippets - pequeno resumo da

página disponibilizado ao

utilizador aquando da devolução

dos resultados.


A representação dos documentos, tendo por base apenas o título e

os snippets, é feita utilizando o conceito de:

Cada um dos diferentes trabalhos, utiliza também uma lista de

stop words1 e algoritmos de stemming2, com consequências ao nível

da dependência da língua;


utilizado por Martins et al 2003, Fung

et al 2003 e Ferragina et al 2005;

(1)

utilizado por Zamir et al 1998, Zhang

et al 2001, Jiang et al 2002 e Zeng et al

2004.

(2)

Vector Space Model – o conjunto de termos

relevantes da colecção é dado unicamente pela

medida TF.IDF.

Partilha de n-gramas – os termos que

caracterizam a colecção são todos aqueles termos

partilhados por mais do que um documento.

1 preposições, artigos e outras palavras que aparecem nos documentos demasiadas vezes,

razão pela qual acrescentam pouco significado ou relevância.

2 uma função que reduz uma palavra à sua forma básica (por exemplo dançando – dançar).


No que respeita ao clustering os algoritmos, distinguem-se pela

combinação dos 2 pontos seguintes:

Os que consideram como termos relevantes dos documentos palavras

simples, e os que consideram phrases; (1)

Os que implementam flat clustering e os que implementam hierarchical

clustering; (2)

Flat Clustering Hierarchical Clustering

Palavras

Simples

Hearst et al (1996)

Jiang et al (2002)

Fung et al (2003)

Phrases Zamir et al (1998)

Zeng et al (2004)

Zhang et al (2001)

Martins et al (2003)

Ferragina et al (2005)




A diferente literatura estudada, apresenta uma fraca análise

semântica dos documentos, razão pela qual pretendemos introduzir

técnicas de Web Content Mining para a representação dos

documentos;

Esta nova representação permitirá um maior grau de precisão na

definição dos clusters evitando assim a formação de grupos

potencialmente não relacionados;


Sumário

• Introdução


• Contribuição


• Resultados

• Objectivos


• Conclusão


Contribuição

Desenvolvemos um novo método de extracção de páginas

relevantes.

A nossa solução considera o documento todo ao invés de

considerar apenas o título e os snippets, tornando a solução mais

abrangente pelo número e essencialmente pela extensão dos

documentos no qual se baseia;

A nossa solução considera o documento todo

Desenvolvemos um novo método de extracção de páginas

relevantes.

Não utilizamos listas de stopwords nem algoritmos de stemming

para filtrar o conjunto dos resultados, mantendo a aplicação flexível,

e independente em relação à língua e ao domínio;

Não utilizamos listas de stopwords nem algoritmos de stemming


Zamir et al (1998) refere que a questão de

considerar phrases ainda não foi

praticamente aplicada na representação

de documentos. Adoptámos este

conceito, aumentando desta forma o

conhecimento sobre os documentos;

Contribuição

Phrases – Quando uma só palavra não é

suficiente para expressar um conceito recorre-se a

grupos de palavras (duas ou mais). Nuno Gomes,

Luis Filipe Vieira, são exemplos de phrases que

assumem um significado próprio quando

comparadas com a sua forma singular

Zamir et al (1998) refere que a questão de

considerar phrases ainda não foi

praticamente aplicada na representação

de documentos. Adoptámos este

conceito, aumentando desta forma o

conhecimento sobre os documentos;

Utilizámos técnicas de Web Content Mining

para extrair conhecimento do texto.

Web Content Mining –

processo que extrai conhecimento

da Web analisando o conteúdo

dos documentos. A ideia é usar

esse conhecimento de forma

inteligente criando aplicações de

procura automática e pesquisa de

informação, interpretando o

conteúdo dos milhares de

recursos disponíveis on-line.

Web Mining – Junção de

duas áreas: Data Mining e

Internet

Utilizámos técnicas de Web Content Mining


Utilizamos este conhecimento como base de formação dos

clusters, apresentando-os ao utilizador de forma hierarquicamente

organizada;

A este nível apresentamos de forma distinta, tópicos diferentes. Um

passo no sentido de resolver o problema da ambiguidade dos

termos;

A este nível apresentamos de forma distinta, tópicos diferentes.

Utilizamos este conhecimento como base de formação dos

clusters, apresentando-os ao utilizador de forma hierarquicamente

organizada;

Contribuição

A utilização de técnicas de Web Content Mining, permite uma

representação dos documentos, baseada em termos relevantes. A

análise semântica do conteúdo da WebPage permite aumentar o

número de palavras a comparar;

www.abola.pt

………………

………………

………..

{slb, glorioso, …}

A utilização de técnicas de Web Content Mining, permite uma

representação dos documentos, baseada em termos relevantes. A

análise semântica do conteúdo da WebPage permite aumentar o

número de palavras a comparar;


Sumário

• Introdução


• Contribuição


• Resultados

• Objectivos


• Conclusão


Solução Proposta

A arquitectura global do projecto WISE é composta por 4 passos:

Selecção de páginas relevantes, de entre o conjunto de documentos

devolvidos pelo Motor de Busca: (1) Selecção de páginas relevantes

(2) Integração do SENTA para extrair phrases dos documentos: Integração do SENTA para extrair phrases dos documentos:

A detecção de termos relevantes caracterizadores dos documentos,

através do WebSpy (ver Veiga et al 2004), implementando um conjunto

de técnicas de Web Content Mining;

(3) A detecção de termos relevantes caracterizadores dos documentos,

Apresentação dos documentos numa estrutura hierárquica, usando o

algoritmo de soft clustering Poboc (ver Cleuziou et al 2003); (4) Apresentação dos documentos numa estrutura hierárquica


Solução Proposta

Selecção de Páginas Relevantes

Cada um dos documentos devolvidos por parte do Motor de Busca

tem diferente relevância para com a query, diminuindo à medida que

mais resultados vão sendo devolvidos;

Produzir clusters com base em documentos de pouca relevância

pode reduzir a qualidade dos resultados e por essa razão excluímos

alguns, beneficiando a precisão em detrimento do recall;

Motivação:


Solução Proposta

diferentes absolutos URLs#

devolvidos URLs#_ relevânciamédia

Em vez de extrair termos relacionados de todos os documentos ou

dos mais pontuados, propomos definir como páginas relevantes,

todos os endereços absolutos e todos, cujo número de ocorrências1

for maior que um dado threshold, calculado com base na equação

seguinte:

Solução:

1 é a soma de todos os URLs que partilhem o mesmo URL absoluto

Observe-se a seguinte figura:

33,13

4

Em vez de extrair termos relacionados de todos os documentos ou

dos mais pontuados, propomos definir como páginas relevantes,

todos os endereços absolutos e todos, cujo número de ocorrências1

for maior que um dado threshold, calculado com base na equação

seguinte:


Adicionamos por outro lado, o número de páginas relevantes

devolvidas pelo motor de busca, não apanhadas pelo sistema, mas

relacionados com a query.

Assim, para os URLs absolutos, executamos a mesma query,

utilizando uma funcionalidade dos Motores de Busca que

devolvem para cada endereço as N melhores páginas;

Solução Proposta

Adicionamos por outro lado, o número de páginas relevantes

devolvidas pelo motor de busca, não apanhadas pelo sistema, mas

relacionados com a query.


Solução Proposta

Extracção de Phrases dos documentos

Identificar phrases nos documentos, por forma a aumentar o

conhecimento sobre cada um desses mesmos documentos;

Motivação:

Aplicamos o software SENTA ao conjunto de todos os textos

provenientes do passo anterior (selecção de páginas relevantes),

substituindo as palavras simples pelas respectivas phrases:

Solução:


Solução Proposta

O SENTA (ver Dias, 2002) é um software independente em relação à

língua, que faz a utilização de métodos puramente estatísticos,

baseado no número de vezes que cada n-grama, ocorre no corpus.

Utiliza o algoritmo GenLocalMax (ver Silva et al 1999) e a medida de

associação Expectativa Mútua (ver Dias et al 1999) baseando-se na

procura do máximo local da função de associação, que mede a força

de associação entre os vários tokens de um n-grama.

Sequências de tokens, fortemente ligadas entre si, corresponderão a

valores de EM elevados e serão escolhidos pelo algoritmo

GenLocalMax como phrases.


Solução Proposta

Extracção de termos relevantes

Análise semântica dos documentos Web, para entender factos que

de outra forma não seriam compreendidos, utilizando o WebSpy (ver

Veiga et al 2004).

Motivação:

Utilização de técnicas de Web Content

Mining para determinar o conjunto de

termos relevantes caracterizadores do

documento;

Solução:

A relevância de um termo é assim

definida por mais características que

apenas o TF.IDF.

Vector Space Model – o conjunto de termos

relevantes da colecção é dado unicamente pela

medida TF.IDF

Partilha de n-gramas – os termos que

caracterizam a colecção são todos aqueles termos

partilhados por mais do que um documento


Solução Proposta

Para inferir esse termos e o respectivo nível de relacionamento, a

aplicação utiliza um conjunto de árvores de decisão, onde o

conteúdo semântico de cada palavra do documento web é definido

por um conjunto de 12 atributos:

Importância dos termos nos documentos

Relações entre as palavras

Conhecimento do Contexto

www.abola.pt

A bola é …….

A

cujo cálculo é baseado no seguinte:

A, bola, é

A, é bola

bola

é

Se… Se…


Solução Proposta

O WebSpy procura devolver para cada conjunto de documentos

(identificados pelo respectivo URL), um conjunto de palavras

relacionados com o assunto especificado.

O WebSpy procura devolver para cada conjunto de documentos

(identificados pelo respectivo URL), um conjunto de palavras

relacionados com o assunto especificado.


O WISE faz uma procura à escala global, não se restringindo a um

único site;

Solução Proposta

Considera phrases, não

apenas palavras simples;

O WISE faz uma procura à escala global, não se restringindo a um

único site;

Considera phrases, não

apenas palavras simples;


Solução Proposta

Apresentação dos Documentos numa

Estrutura Hierárquica

No passo anterior atingiu-se o flat clustering:

O utilizador fica perdido no meio de informação díspar; (1)

O conjunto de resultados partilha conceitos diferentes, mas

dispostos de forma não distinta (problema de ambiguidade, por

resolver);

(2)

Para atingir o Hierarchical clustering:

O WISE utiliza de forma recursiva o WebSpy, determinando que termos

estão relacionados com cada um dos termos previamente devolvidos

do flat clustering;

(1)


Solução Proposta

O próximo passo é avaliar a similaridade existente entre cada um dos

flat clusters:

O agrupamento dos documentos é feito com base na similaridade do

seu conteúdo, i.e., das suas palavras mais relevantes;

O próximo passo é avaliar a similaridade existente entre cada um dos

flat clusters:


Solução Proposta

Essa similaridade é registada numa matriz simétrica, com dimensão

igual ao número de flat clusters:

O valor de cada uma das similaridades é construído com recurso à

medida de Cosine, que mede a distância entre 2 vectores de dimensão

N;

Essa similaridade é registada numa matriz simétrica, com dimensão

igual ao número de flat clusters:

O valor de cada uma das similaridades é construído com recurso à

medida de Cosine, que mede a distância entre 2 vectores de dimensão

N;


Solução Proposta

Os vectores são constituídos pelos termos relacionados e respectivas

probabilidades de relevância, obtidas da execução recursiva do

WebSpy para cada um dos flat clusters:

Assim, quando 2 vectores partilham

termos iguais, deve proceder-se ao

cálculo da similaridade aplicando a

medida de cosine, caso contrário se

os vectores não partilharem

qualquer termo entre eles, o valor da

similaridade será zero

Os vectores são constituídos pelos termos relacionados e respectivas

probabilidades de relevância, obtidas da execução recursiva do

WebSpy para cada um dos flat clusters:


O algoritmo de soft clustering Poboc (ver Cleuziou et al 2003),

determina, a partir da matriz de similaridade, clusters de termos

relacionados:

O número de clusters é desconhecido à priori; (1)

Um objecto pode pertencer a mais do que um cluster (overlap); (2)

Solução Proposta

As 3 principais tarefas do Poboc são:

Construção de uma representação em grafos de similaridade; (1)

Construção dos pólos; (2)

Atribuição dos objectos a um ou mais pólos; (3)


O processo de clustering não

termina com o agrupamento e a

criação de clusters coerentes;

A actual procura pela lista de

resultados não deve ser substituída

por uma procura por entre os

clusters;

Devem por isso ser escolhidos labels descritivos dos clusters:

Solução Proposta

O nome do label de um dado cluster, é aquele que mais vezes aparece

partilhado, pelo conjunto de vectores pertence ao grupo; (1)

nos casos em que existe mais do que um termo com o mesmo

número de ocorrência máxima, o sistema escolhe aquele que obtém

a maior soma de pesos (nos vectores em que ocorre).

(2)


Solução Proposta

Observe-se em termos

conceptuais a diferença entre o

WebSpy e o WISE;


Sumário

• Introdução


• Contribuição


• Resultados

• Objectivos


• Conclusão


Resultados

Conjunto de resultados obtidos no dia 31/05/2005, para a query

Benfica, tendo por base o Motor de Busca Google e uma lista inicial

de 100 resultados;

Os labels são semanticamente descritivos a nível dos conteúdos,

devido à identificação de phrases relevantes; (1)

Capacidade do sistema em lidar com erros ortográficos (Giovanni e

não Geovanni), o que se deve ao facto de não ser feita nenhuma

restrição relativa à frequência de termos;

(2)

Capacidade do sistema em agrupar diferentes URLs para um mesmo

conceito; (3)

Os labels são semanticamente descritivos a nível dos conteúdos,

devido à identificação de phrases relevantes;

Capacidade do sistema em lidar com erros ortográficos

Capacidade do sistema em agrupar diferentes URLs para um mesmo

conceito;


Resultados

(4) Possibilidade de um documento falar de dois ou mais tópicos (overlap).

Note-se que www.slbenfica.pt é referenciado por 2 clusters.

(5) A nossa cobertura de resultados é muito maior, por considerarmos um

conjunto alargado de URLs, para lá dos devolvidos pelo Motor de Busca.

Possibilidade de um documento falar de dois ou mais tópicos (overlap).

A nossa cobertura de resultados é muito maior


Resultados

(6) Independência em relação à língua permite ter num mesmo cluster

referências a URLs em diferentes idiomas.

Independência em relação à língua


Resultados

(7) Capacidade do sistema em lidar com a desambiguação de termos

Cluster José-António-Camacho Benfica Clube

Cluster PS Benfica Bairro

Cluster Universitários Transportes/Aluguer de Casas em Benfica

Capacidade do sistema em lidar com a desambiguação de termos


Sumário

• Introdução


• Contribuição


• Resultados

• Objectivos


• Conclusão


Trabalhos Futuros

Apesar dos seus imensos recursos, pouca gente considerou usar

técnicas de Web Content Mining como input para uma Data

Warehouse;

Web Farming – conceito

descrito por Hacktorn (1998) como

uma poderosa combinação entre a

Web e o conceito de Data

Warehouse, que consiste numa

procura sistemática de conteúdos

relevantes na Web que alimentem a

Data Warehouse, complementando-

os com os dados provenientes dos

Sistemas Operacionais.

A pesquisa de informação e a área de bases de dados, disponibilizam

pontos comuns e são uma direcção interessante na área de Web

Content Mining;

A pesquisa de informação e a área de bases de dados, disponibilizam

pontos comuns


Propomos a implementação de uma Web Warehouse que guarde o

conjunto de termos relacionados com uma dada query. Esta

implementação permitirá a construção automática e gradual de um

thesaurus;

Propomos a implementação de uma nova medida de similaridade

(InfoSimba, ver Dias & Alves 2005), que substitua a utilização de

cosine, na exacta medida em que esta, desconsidera potenciais

vectores similares, caso estes não partilhem nenhum palavra em

comum;

Noutra direcção, uma medida que poderá resultar, também, numa

valorização dos clusters, é um possível reagrupamento dos mesmos;

Propomos a implementação de uma Web Warehouse

Propomos a implementação de uma nova medida de similaridade

Noutra direcção, uma medida que poderá resultar, também, numa

valorização dos clusters, é um possível reagrupamento dos mesmos;

Trabalhos Futuros


Garantir a rapidez da aplicação, não foi o focus desta dissertação. Tal

não invalida que esse facto não seja tido em conta. Assim, propomos

uma optimização da aplicação, paralelizando o seu código, ou

utilizando técnicas de computação distribuída (Grid Computing ou

Cluster Computing);

Gostaríamos de validar no futuro, até que ponto, os actuais motores

de busca adoptarão estes conceitos e se, por outro lado, novos

motores de busca, surgirão por via deste tipo de estudos.

Garantir a rapidez da aplicação, não foi o focus desta dissertação. Tal

não invalida que esse facto não seja tido em conta. Assim, propomos

uma optimização da aplicação, paralelizando o seu código, ou

utilizando técnicas de computação distribuída (Grid Computing ou

Cluster Computing);

Trabalhos Futuros

Aplicação de técnicas mais elaboradas para determinar os labels dos

clusters: word sense disambiguation;


Sumário

• Introdução


• Contribuição


• Resultados

• Objectivos


• Conclusão


Conclusão

A solução aqui descrita permite mostrar ao utilizador:

A informação mais importante de acordo com uma dada query; (1)

Organizada de forma hierárquica. (2)

Para atingir esses objectivos usamos:

Um algoritmo que ignore documentos pouco relevantes, um outro que

acrescente;

Um conjunto de técnicas de Web Content Mining, que permitem extrair os

termos semanticamente relacionados com o documento e a query,

entendendo factos, que até ao momento nenhum outro motor de busca

procura compreender;

Um algoritmo de clustering de documentos, que permite apresentar a

informação de forma estruturada e organizada hierarquicamente.

Phrases, para definir conceitos, com consequências, também, a nível do

entendimento dos documentos;

(1)

(2)

(3)

(4)


Conclusão

A arquitectura e os algoritmos propostos são a solução para um dos

maiores problemas com que os motores de busca lidam actualmente:

A devolução de resultados de qualidade, através de uma estrutura

flexível (independente em relação à língua e ao domínio), automática,

organizada e desambiguada de conceitos.

Este trabalho foi apresentado no Workshop ELECTRA em associação

com a conferência ACM SIGIR, que é presentemente a conferência

mais conceituada em Pesquisa de Informação em Bases de Dados.


FIM

Obrigado pela vossa atenção!

O sistema estará brevemente disponível no seguinte url:

http://wise.di.ubi.pt

Documents

Agrupamento Automático de Páginas Web utilizando Técnicas dericardo/ficheiros/MasterThesis_RCampos... · 2013. 6. 15. · Agrupamento Automático de Páginas Web utilizando Técnicas