Web Mining
Disciplina de Mineração de Dados
CIn-UFPE
Web: repositório de informação
 Sem padronização
• Documentos de todo tipo
 Enorme
• Informação de links
• Informação de uso e acesso
 Amplamente
distribuído
 Não estruturado / semi-estruturado
 Inter-conectado
 Em evolução
WWW: Fatos
 Crescendo
•
•
•
•
e mudando muito rapidamente
Um servidor WWW a cada 2 horas
5 milhões de documentos em 1995
320 milhões de documentos em 1998
Mais de 1 bilhão em 2000
 Índices
se tornam inadequados muito rapidamente
• Necessidade para uma melhor descoberta de recursos e
extração de conhecimento
WWW e Web Mining
 Problemas:
• O problema da "abundância"

99% da informação não é do interesse de 99% das pessoas
• Cobertura limitada da web



Recursos da web escondidos
Maioria dos dados em SGBD's
400 a 500 vezes maior que a Web estática
• Interface de consulta limitada, baseada em buscas por
palavra-chave
 Envolve
outras áreas de computação
• Recuperação de Informação
Web Mining: Taxonomia
Web Mining
Web Content
Mining
Web Page
Content
Mining
Web Structure
Mining
Search Results
Mining
Web Usage
Mining
General
Access Pattern
Mining
Customized
Usage
Tracking
Mineração do Conteúdo da Web:
Abordagem Baseado em Agentes
 Ahoy!
(1996-2000) – "achador de homepages"
• Motivação: Altavista muito impreciso. Directories
pouco dinâmicos
• Entrada: nome de uma pessoa, país e instituição
• Analisa resultados de vários motores de busca
• Resultados analisados sintaticamente usando
heurísticas
 Páginas que contêm frases como "home page”
• http://www.help4web.net/search/eMail/Ahoy.html
Mineração do Conteúdo da Web:
Abordagem Baseado em Agentes
 Shopbot
• Agente de compras
• Identifica listas de preço e ofertas especiais.
• Aprende a reconhecer estruturas de documentos
de catálogos on-line e sites e e-commerce.
• Tem que se ajustar às mudanças de conteúdo das
páginas.
• http://www.edgegain.com
Mineração do Conteúdo da Web:
Abordagem Baseado em Banco de Dados
 WebOQL
•
•
•
•
(1998)
Linguagem de consulta declarativa
Funcional e select-from-where
Retorna informações dentro de documentos Web.
Estrutura básica:



Árvores ordenadas com arcos nomeados
Arco interno: objetos estruturados
Arco externo: referências (links)
• Exemplo:



select [x.Titulo]
from x in "books.html"
where x.Autor = ”John Smith"
Exemplo de Árvore em WebOQL
[Tag: html]
[Grupo: Inteligência Artificial]
[Grupo: Linguagem de Programação]
[Título: AIMA,
Autor: Russel]
[Título: Paradimas de Programação,
Autor: John Smith]
[Título: Machine Learning,
Autor: Tom Mitchel]
[Label Full version
URL:http://www.cin.ufpe.br]
[Label:table of contents
URL:http://www.cmu.edu/ML]
[Label:book
URL:http://www.cmu.edu/ML/book.zip]
Mineração do Conteúdo da Web:
Abordagem Baseado em Banco de Dados
 WebSQL
• linguagem estilo SQL para extrair documentos pertinentes
 Estrutura
básica
• Document: url, title, text, length, type,date
• Anchor: base, label, href
 Exemplo:
• Recuperar o título e a URL de todos os documentos que são
apontados pelo documento cuja URL é
http://www.somewhere.com no mesmo servidor
• SELECT d.url, d.title
FROM Document d SUCH THAT ”http://www.somewhere.com" -> d
Mineração do Conteúdo da Web
Atualização de Páginas em Engenhos de
Busca
 Abordagens
• Atualizar as páginas na mesma freqüência
• Atualizar em freqüências diferentes


Aprender como as páginas se comportam à medida que se
atualiza
Utilizar um classificador para prevê em que classe a
página se encontra
¤ Uso de clustering para criar as classes
¤ Uso de técnicas classificação para gerar classificador
Organização hierárquica automática de
resultados de Busca


Motores de Busca atuais
• Baseado em palavra-chave
• Retorna respostas demais
• Respostas de baixa qualidade
Hierarquia de Resultados de Busca
• Reorganizar os resultados usando uma hierarquia semântica (Zaiane
et.al., 2001)





Realiza metabusca
Mapeia consulta em hierarquias conceituais pré-existentes WordNet
Mapeamento das páginas na hierarquia
J-Walker
Clusterização
• http://www.wisenut.com
Web Structure Mining
 Extrair
conhecimento das interconexões dos
documentos.
 Método em procedência de jornalismo /
biblioteconomia:
• O fator de impacto de Garfield (1972): provê uma avaliação
numérica na citação de jornais.
 Enorme
quantidade de anotações humanas escondidas
• Podem ajudar a inferir noções de "autoridade" em um tópico.
 Descoberta
WWW.
de páginas influentes e dominantes na
Web Structure Mining
 HyPursuit
(Weiss et.al., 1996)
• Engenho de busca hierárquico
• Usa relações baseadas no conteúdo e nos links
• Grau de similaridade proporcional ao:


Número de termos, ancestrais e descendentes em comum
Número de links entre documentos (grau de
conectividade)
Hyperlink Induced Topic Search (HITS)
 Algoritmo
de Jon Kleinberg, 1998, Cornell University
 Problema
• Qualidade das respostas para consultas genéricas em engenhos
de busca
 Hubs e autoridades
• Boa autoridade: página apontada por bons hubs
• Bom hub: página que aponta para boas autoridades
 Comunidades competitivas
• Ex: consulta “engenho de busca”
Etapas do algoritmo HITS

Primeira etapa: construção das páginas candidatas
• Começando de uma consulta convencional, HITS monta um conjunto
inicial S de páginas
• O conjunto S é o conjunto raiz.
• As páginas são expandidas para um conjunto raiz T adicionando páginas
que estão ligadas de ou para qualquer página no conjunto inicial S.
T
S
Etapas do algoritmo HITS
 Segunda
Etapa: propagação de pesos
• Cria um vetor de hubs e um vetor de autoridades
• HITS então associa com cada página p um peso de hub h(p) e um
peso de autoridade a(p), tudo inicializado para um.
• HITS então iterativamente atualiza os pesos de hub e autoridade de
cada página
• Faça pq denotar "a página p tem um link para a página q". HITS
atualiza os hubs e autoridades da seguinte forma:
a( p) =
 h( q )
q p
h( p ) =
 a(q )
p q
Melhorias para o HITS
 Deficiências
do HITS
• O termo não está amarrado à consulta

Piora a precisão
• Cálculo é feito on-line

Problemas de desempenho
 Sistema
CLEVER (Chakrabarti, et.al.,1998-1999)
• Baseado tanto no conteúdo como na informação do link
• Observa uma janela próxima ao href
• As arestas possuem pesos

W = 1 + ocorrências + (janela - distância) + raiz_do_grafo
GHITS
 Desenvolvido
no Cin
 Encontrar autoridades na Web independentemente de
consulta
 Processo realizado em batch
 Peso menor no ranqueamento
• R = text * 0.75 + GHHITS(autoridade)*0.25
 Melhoria
de 10% na qualidade da resposta
Page Rank
Tenta capturar a noção de importância de uma página
 Uma boa autoridade aponta para uma boa autoridade
 Ranqueamento baseado em um modelo de um "browser
aleatório“
 O número de visitas para cada página é seu Page Rank
 Usado para selecionar páginas para o crawler
 Fazer o ranking das páginas em resultados de busca do
Google.
 Independente do tópico
 Comunidades colaborativas

Cálculo do Page Rank
Cada página p tem um número de links saindo dele C(p)
 B(p): páginas que apontam para p
 PageRank de p é obtido por

PR( q )
PR( p) = 
q E B(p) C ( q )
Cálculo do Page Rank
100
53
50
3
50
9
Comparação
Processanento
on-line
Denpendente
de consulta
Tipo de
comunidade
Consultas
genéricas
HITS
sim
sim
competitiva
sim
GHITS
não
não
competitiva
sim
Clever
sim
sim
competitiva
sim
Page Rank
não
não
colaborativa
sim
Links de Nepotismo
 Links
entre páginas que estão presentes por razões
outras que mérito
 Spamming
• Enganar motores de busca para dar rank alto para alguns
documentos
 Abordagens
para combater o problema
• Não considerar páginas de mesmo host, mesmo ip
• Manter uma lista de páginas que abusam de links
• Manter um limiar para o número de backlinks
Servidores Web
 Registram
uma entrada de log para cada acesso
• Grande quantidade de informação
 Informações
IP
ID do usuário
normalmente contidas nos logs
Timestamp
Método
URL/caminho
Status
Tamanho
Referência
Agente
Cookie
129.128.4.21 - [15/Aug/1999:10:45:32 - 0800] “GET /index.html 200 512 /main.html Mozilla/3.04 (Win95)
Servidores Web
 Ferramentas
•
•
•
•
•
•
•
•
comerciais fornecem:
Relatório de hits e bytes transferidos
URLs mais acessadas
Lista de browsers mais usados pelos usuários
Hits por hora/dia/semana/mês.
Lista de erros.
Árvore de diretórios acessados
Exemplo: http://www.sane.com/demo/NetTracker/
Problema

Desempenho e profundidade de análise limitado
Necessidade de minerar Web logs
 Ganho
de performance do servidor
 Melhora a navegação dentro do site
 Melhora o design da aplicação web
 Direcionam os clientes no comércio eletrônico
 Identificam locais privilegiados para propaganda
Preparação de Dados
 Identificando
ações de usuários:
• Análise de caminhos
 Problemas:
• Grande quantidade de dados
• Identificar os tipos das páginas: páginas de conteúdo ou
páginas de navegação (retirar .gifs).
• Tentar prever acessos que não foram identificados no log



Proxy server e chache de browser
Utilização de funções dos browsers (ex.: voltar a página anterior,
scrolling up/down...)
Solução: utilizar cookies ou realização de login
Preparação de Dados
 Problemas
• Identificação de usuários que estão sobre o mesmo ip
• Não se sabe quando um usuário sai do site. Usa-se o tempo de
inatividade como heurística (20 ou 30 minutos sem uso).
• Páginas dinâmicas


Diferentes ações de usuários levando ao mesmo CGI
Mesma ação do usuário, em horas diferentes, levando a CGIs
diferentes
Preparação de Dados
 Uso
da estrutura e conteúdo do site
• Estrutura:

É necessário conhecer estrutura do web site a minerar para analisar
a sessão e as transações do usuário.
¤ Ex.: Grafo de links entre as páginas.
• Conteúdo:

O conteúdo das páginas visitadas pode dar idéia de como realizar a
limpeza e seleção dos dados.
¤ Ex.: Página de navegação ou de conteúdo.
Mineração dos dados
 Análise
de caminhos
 Regras
de Associação
• Descobrir os caminhos mais acessados no site
• Exemplo: 80% dos clientes acessaram o site a partir da
página /download
• Correlação entre acessos a arquivos no Web Server
• Ajuda em estratégias de marketing
• Exemplo: 40% dos usuários que acessaram a URL /download
também acessou a URL /products
 Seqüência
de padrões temporais
• Determinar relacionamentos temporais
• Exemplo: 60% dos clientes que pediram um produto na URL
/company/product também visitaram a URL /download dentro
de 15 dias
Mineração dos dados
 Regras
de classificação
• Categorizar visitantes através da seleção de características
do site que melhor descrevem seus comportamentos.
• Exemplo: clientes vindos de sites do governo tendem a
interessar-se por páginas de produtos
 Clustering
• Agrupamento de transações
• Agrupamento de páginas baseado no conteúdo
• Agrupar usuários de mesmo comportamento.
Sistemas de Web Usage Mining
 Gerais:
• WebLogMiner (Zaïane et al, 1998)




filtrar dados para um banco de dados convencional (relacional, OR,
OO)
Gerar um datacube a partir do banco de dados
Usar ferramentas OLAP para realizar ações de drill-down e roll-up no
cubo
Extração de conhecimento (OLAM)
• WUM

http://wum.wiwi.hu-berlin.de/demo/
 WebSIFT
(Cooley et al, 1999)
 Personalização e recomendação:
• WebWatcher (Joachims et al, 1998)
Conclusão
 Usar
o log gerado pelo servidor Web pode ajudar a
entender o comportamento do usuário e assim melhorar
o funcionamento do site (design, aplicação, etc)
 Nem sempre o log tem informações suficientes
 OLAP proporciona a visualização em diferentes
perspectivas e em diferentes níveis.
 Web Usage Mining oferece relatórios mais detalhados
sobre o uso do site.