Embed Size (px)
Citation preview
1
Aula 13: Recuperação da Informação e Busca na Web
Alexandre [email protected]
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
