Recuperação da Informação e Busca na Web

1

Aula 13: Recuperação da Informação e Busca na Web

Alexandre Duartealexandre@di.ufpb.br

111

Ordenação e Recuperação de Dados

Breve contextualização histórica

Motores de busca baseados em palavras-chave 1995-1997 Altavista, Excite, Infoseek, Inktomi, Lycos

Classificação paga : Goto (transformou-se em Overture.com → Yahoo!) A sua classificação nos resultados de busca

dependia de quanto você pagava Leilão de palavras-chave: casino era muito cara!

2

Breve contextualização histórica 1998+: Classificação baseada em links é criada pela Google

Destruiu todos os outros motores de busca com exceção do Inktomi Aumento da satisfação do usuário Enquanto isso, o faturamento anual da Goto/Overture está perto de

U$1 bilhão

Resultado : Google adiciona anúncios pagos, de forma independente dos resultados das buscas Yahoo segue, comprando a Overture (para anúncios pagos) e Inktomi

(para busca)

2005+: Google aumenta sua parcela no mercado de busca, dominando a Europa e ganhando força na América do Norte 2009: Yahoo! e Microsoft propõem um modelo combinado de busca

paga3

4

Anúncios

Resultados

Básico de busca na web

Web

Índice de propagandas

Web Results 1 - 10 of about 7,310,000 for miele. (0.12 seconds)

Miele, Inc -- Anything else is a compromise At the heart of your home, Appliances by Miele. ... USA. to miele.com. Residential Appliances. Vacuum Cleaners. Dishwashers. Cooking Appliances. Steam Oven. Coffee System ... www.miele.com/ - 20k - Cached - Similar pages

Miele Welcome to Miele, the home of the very best appliances and kitchens in the world. www.miele.co.uk/ - 3k - Cached - Similar pages

Miele - Deutscher Hersteller von Einbaugeräten, Hausgeräten ... - [ Translate this page ] Das Portal zum Thema Essen & Geniessen online unter www.zu-tisch.de. Miele weltweit ...ein Leben lang. ... Wählen Sie die Miele Vertretung Ihres Landes. www.miele.de/ - 10k - Cached - Similar pages

Herzlich willkommen bei Miele Österreich - [ Translate this page ] Herzlich willkommen bei Miele Österreich Wenn Sie nicht automatisch weitergeleitet werden, klicken Sie bitte hier! HAUSHALTSGERÄTE ... www.miele.at/ - 3k - Cached - Similar pages

Sponsored Links

CG Appliance Express Discount Appliances (650) 756-3931 Same Day Certified Installation www.cgappliance.com San Francisco-Oakland-San Jose, CA Miele Vacuum Cleaners Miele Vacuums- Complete Selection Free Shipping! www.vacuums.com Miele Vacuum Cleaners Miele-Free Air shipping! All models. Helpful advice. www.best-vacuum.com

Web spider

Indexador

Índices

Buscar

Usuário

5

Necessidades do usuário Necessidade

Informacional – deseja aprender algo (~40% / 65%)

Navigacional – deseja ir a uma página (~25% / 15%)

Transacional – desejar fazer algo (através da web) (~35% / 20%)

Acessar um serviço

Downloads

Compras

Baixa hemoglobina

United Airlines

Tempo na Serra GaúchaImagens da Lua

Canon S410

6

Quantos resultados são analisados pelos usuários?

(Source: iprospect.com WhitePaper_2006_SearchEngineUserBehavior.pdf)7

Avaliação empírica dos resultados (usuários) Qualidade das páginas varia bastante

Relevância não é suficiente Outras qualidades desejadas (não RI!!)

Conteúdo: Confiabilidade, diversidade, não-duplicidade Legibilidade: Mostrar os documentos de forma rápida e correta Sem aborrecimentos: pop-ups, etc.

Precisão vs. recall Na Web, recall geralmente não importa

O que importa Precisão na posição 1? Precisão antes da quebra de página? Extensão – precisa ser capaz de lidar com pesquisas obscuras

Recall importa quando o número de resultados é muito pequeno

A percepção dos usuários pode não ser científica mas é bastante significativa

8

Avaliação empírica dos motores de busca (usuários) Relevância e validade dos resultados UI – simples, sem desordem, tolerante a erros Confiança – Resultados são objetivos Oferta de ferramentas de Pré/Pós processamento

Mitigar erros do usuário (correção ortográfica, assistente de busca,…) Explícito: Busca dentro dos resultados, mais como esses, refinar ... Antecipativo: consultas relacionadas

Lida com idiossincrasias Vocabulário específico da web Endereços web digitados na caixa de busca

9

10

A coleção de documentos da Web Sem projeto/coordenação Criação distribuída de conteúdo, ligações,

democratização da publicação Conteúdo inclui verdades, mentiras,

informação obsoleta, contradições … Documentos não-estruturados (text, html,

…), semiestruturados (XML, fotos anotadas), estruturado (bases de dados)…

Escala muito maior que qualquer outra coleção de texto

Crescimento – desacelerou em relação ao boom inicial de “duplicar o volume a cada poucos meses” mas continua se expandido

Conteúdo pode ser gerado dinamicamenteWeb

11

SPAM(Otimização de Motores de Busca)

12

O problema com os anúncios pagos …

Custam dinheiro! Qual seria a alternativa? Otimização de Motores de Busca:

“Refinar” suas páginas para que elas sejam melhor classificadas nos resultados de buscas para determinadas palavras-chave

Alternativa a pagar por classificação Portanto, é intrinsicamente uma atividade de marketing

Realizado por empresas, webmasters e consultores (“Search engine optimizers”) para seus clientes

Alguns perfeitamente legítimos, outros um tanto nebulosos

13

Otimização de motores de busca (SPAM)

Razões Comercial, política, religiosa, lobby

Operadores Prestadores de serviço (Search Engine Optimizers) Webmasters Serviços de hospedagem

Fóruns Web master world ( www.webmasterworld.com )

SEO News (http://www.seonews.com/)

14

Search (Google) Bombing

15

Search (Google) Bombing

16

Search (Google) Bombing

17

Search (Google) Bombing

18

Search (Google) Bombing

19

Search Bombing

As primeiras gerações de motores de busca dependiam fortemente do tf/idf As páginas mais bem classificadas para a consulta resort porto de

galinhas eram as que continham a maior quantidade de ocorrências de cada palavra

SEOs contra-atacaram com densas repetições de termos e.g., porto de galinhas resort porto de galinhas resort porto de galinhas resort

Muitas vezes as repetições apareciam na mesma cor que o background da página

Termos repetidos influenciavam a indexação Mas são invisíveis para os usuários

Densidade de palavras não pode ser confiável em

sistemas de busca na web 20

Variações da repetição de palavras-chave Meta-dados enganosos, repetitivos e excessivos Texto escondido com cores, folhas de estilo, etc

Meta-dados = “… London hotels, hotel, holiday inn, hilton, discount, booking, reservation, sex, mp3, britney spears, viagra, …”

21

Cloaking O servidor forja o conteúdo da página para um

motor de busca

Is this a SearchEngine spider?

Y

N

SPAM

RealDocCloaking

22

Mais técnicas de SPAM

Páginas de entrada Páginas otimizadas para uma única palavra-chave que

redirecionam para a página real Link spamming

Sociedades de admiração mútua, links escondidos Domain flooding: numerosos domínios apontando para

uma única página

23

A guerra contra o SPAM Sinais de qualidade – dar

preferência a páginas baseado nos: Votos de autores (links) Votos de usuários (sinais de uso)

Policiamento da submissão de URL Teste anti-robô

Limite de palavras chave em meta-dados

Análise robusta de links Ignorar encadeamentos

estatísticamente não-plausíveis Usar análise de links para

detectar spammers (culpa por associação)

Reconhecimento de SPAM com aprendizagem de máquina Conjunto de treinamento

baseado em spam conhecido

24

TAMANHO DA WEB

25

Qual o tamanho da Web? Problemas

A web é realmente infinita Conteúdo dinâmico, ex., calendários Soft 404: www.yahoo.com/<anything> é uma página válida

Web estática possui duplicação sintática, principalmente por conta do espelhamento (~30%)

Alguns servidores estão raramente disponíveis Quem se importa?

Projetista do motor de busca Política de spidering. Impacto no recall.

26

O que podemos tentar medir?

Os tamanhos relativos dos motores de busca A noção de uma página sendo indexada ainda é

razoavelmente bem definida. Mas tem alguns problemas

Extensão do documento: ex., motores indexam páginas ainda não recuperadas indexando o texto descritivo dos links para as páginas (texto âncora).

Restrições nos Documentos: Todos os motores restringem o que pode ser indexado (primeiras n palavras, apenas palavras relevantes, etc.)

27

Nova definição? A web estaticamente indexável é o que os

motores de busca conseguem indexar. QI é o que os testes de QI conseguem medir.

Motores diferentes têm preferências diferentes Motores diferentes indexam coisas diferentes sob a

mesma URL: frames, meta-keywords, restrições de documentos, extensões de

documentos, ...

28

A ∩ B = (1/2) * Tamanho A

A ∩ B = (1/6) * Tamanho B

(1/2)*Tamanho A = (1/6)*Tamanho B

∴ Tamanho A / Tamanho B = (1/6)/(1/2) = 1/3

URLs escolhidas aleatoriamente de A

Checar se estão em B e vice versa

A ∩ B

Tamanho relativo pela interseçãoDados dois motores de busca A e B

29

DETECÇÃO DE DUPLICATAS

30

Documentos duplicados A web está cheia de conteúdo duplicado Detecção estrita de duplicadas = casamento

perfeito Não tão comum

Mas há muitos, muitos casos de quase-duplicatas Ex., a última data de modificação é a única

diferença entre duas copias de uma página

31

Detecção de Duplicatas/Quase-duplicatas Duplicação: Pode ser detectada com assinaturas Quase-duplicação: Casamento aproximado

Visão geral Computar a similaridade sintática utilizando alguma

medida de distância de edição Usar um limiar de similaridade para detectar quase-

duplicatas Ex., Similaridade > 80% => Documentos são quase-duplicatas

32

Similaridade dos conjuntos Ci , Cj

Ver conjuntos como colunas em uma matriz A; uma linha para cada elemento no universo. aij = 1 indica a presença do item i no conjunto j

Exemplo

ji

ji

jiCC

CC)C,Jaccard(C

=

C1 C2

0 1 1 0 1 1 Jaccard(C1,C2) = 2/5 = 0.4 0 0 1 1 0 1

33

Observação Chave Das colunas de Ci, Cj, podemos quatro tipos de linha

Ci Cj

A 1 1

B 1 0

C 0 1

D 0 0

Sobrecarga de Notação : A = # de linhas do tipo A Portanto

CBA

A)C,Jaccard(C ji ++

=

34