Web Mining
Disciplina de Mineração de Dados
CIn-UFPE
Franklin Ramalho
Rodrigo Cunha
Roteiro


Motivação e Contexto
Taxonomia





Web Content Mining
Web Structure Mining
Web Usage Mining
Softwares no Mercado
Considerações Finais
Motivação - Web







Conteúdo + Hyper-links
Sem padronização
Heterogênea
Não estruturado / semi-estruturado
Enorme
Amplamente distribuído
Em evolução
Motivação - Web

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
Web

Problemas:

O problema da "abundância"


Cobertura limitada da web




99% da informação não é do interesse de 99% das
pessoas
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 e navegação em
links
WWW e Web Mining

Web é uma grande coleção de informação:




Documentos
Hiper-links
Acesso e uso da informação
A parte relevante desta informação, o
conhecimento, está escondida e precisa ser
descoberta
Exemplo de aplicação prática

Recuperação da Informação

Engenhos de Busca (Google, AltaVista, etc)
Usuário
Resultado
Consulta
Web
Baixa Precisão
e Baixa
Cobertura
Interface
Documentos
+
URLs
Casamento de
Termos
BI
RobôsÍndices + URLs
BI
Exemplo de aplicação prática




Engenhos de Busca
Ineficientes: Baixa precisão e cobertura
Precisam descobrir documentos relevantes escondidos
Data Mining vai ajudar em vários aspectos:








Análise de links
Criação de linguagens baseadas na Web
Personalização
Classificação
Clustering
Encontrar melhores primitivas de busca
Melhorar a eficiência (precisão e cobertura)
Outros exemplos: Sites de e-commerce, chats, sites de
entretenimento, portais genéricos, etc.
Exemplo de aplicação prática
Web Mining: Taxonomia
Web Mining
Web Content
Mining
Web Structure
Mining
Web Usage
Mining
Web Content Mining


Sumarização de páginas
Classificadores



Wrappers


Ahoy
Atualização de páginas na Web
ShopBot
Linguagens de Consultas


WebLog
WebOQL
Web Content Mining

Ahoy! (1996-2000) – "achador de homepages"






Motivação: Altavista muito impreciso. Diretórios 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
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
Web Content Mining

WebOQL (1998)




Linguagem de consulta declarativa
Baseada em select-from-where
Retorna informações dentro de documentos Web.
Exemplo:







select [x.Titulo]
from x in "books.html"
where x.Autor = ”John Smith“
Select [x.Text]
from x in “papers.html”
where x.Tag=“H2”
WebSQL - Exemplo:
Recuperar o título e a URL de todos os documentos que são apontados
pelo documento cuja URL é http://www.somewhere.com
SELECT d.url, d.title
FROM Document d SUCH THAT ”http://www.somewhere.com" -> d
 API para Java

Web Structure Mining

Como achar os principais engenhos de busca?


Extrair conhecimento das interconexões dos documentos.




Consulta “search engines”
Navegação
Recomendação
Citação
Descoberta de páginas influentes e importantes na WWW.
Web Structure Mining

Hyperlink Induced Topic Search (HITS)

Algoritmo de Jon Kleinberg, 1998, Cornell University
Problema






Hubs e autoridades



Qualidade das respostas para consultas genéricas em engenhos de busca
Os engenhos de busca consideram apenas palavras-chave do texto
Consulta: “search engine”
Como ficam as páginas como Google e Altavista, por exemplo?
Boa autoridade: página apontada por bons hubs
Bom hub: página que aponta para boas autoridades
Algoritmo aplicado em dois passos: construção do conjunto de
páginas candidatas e propagação de pesos
Etapas do algoritmo HITS

Primeiro passo: construção das páginas candidatas


Começando de uma consulta convencional, HITS monta um conjunto
inicial S de páginas, o conjunto raiz.
As páginas são expandidas para um conjunto 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 passo: 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 com o valor um.
HITS então iterativamente atualiza os pesos de hub e autoridade de
cada página
Ë aplicada, então, uma normalização para todos os pesos
Considerando que pq denota que 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


O HITS devolve um conjunto de páginas com altos hubs e/ou altos
valores de autoridade
Deficiências do HITS



Cálculo é feito on-line
O conteúdo dos links é ignorado
Sistema CLEVER (Chakrabarti, et.al.,1998-1999)


Estende o HITS
Combina a informação existente tanto no conteúdo como na informação do link


Considera o texto da âncora da página, aumentando os pesos para
aquelas cujo texto casa com termos da consulta
Divide conjunto de links de uma página em sub-conjuntos de mini-hubs
a( p) =
w
q
q p
h( p) =
w
pq
q
 h(q)
 a(q)
Web Structure Mining

HyPursuit (Weiss et.al., 1996)

Engenho de busca que utiliza clustering de hipertexto
baseado no conteúdo e nos links das páginas web
A função de similaridade do algoritmo de clustering é
proporcional ao:



Grau de similaridade dos termos.
Grau de similiaridade da estrutura de hiperlinks – ancestrais e
descendentes em comum, além do caminho de links entre os
documentos (grau de conectividade)
S
hibrido
ij
= f (S
termos
ij
,S
link
ij
)
S ijtermos = Wik  W jk
k
S
links
ij
= Wd  S
dsc
ij
 Wa  S
anc
ij
 Wc  S
ca min ho
ij
Links de Nepotismo



Spamming – poluição de páginas web com termos que não são
texto
Com o uso de algoritmos como HITS, Clever, Page Rank, dentre
outros, muitos links “tendenciosos” surgiram
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
Web Usage Mining (WebLog)

Descoberta do comportamento de acesso de usuários a
sites na Web usando técnicas de mineração de dados.

Geralmente usa-se o LOG do Servidor Web como dados
de entrada.

CRM (Customer Relationship Management) analítico na
Web.

Exemplos:
Amazon.com
Siciliano
Motivação do WebLog
Por que Amazon.com e Siciliano fazem WebLOG?

Conhecer melhor o consumidor.

Melhorar o relacionamento com o cliente.

Fidelizar o Cliente

Satisfação do cliente

Maior Retorno Financeiro
KDD x Web KDD
 Difere basicamente pela natureza dos dados.
Natureza dos Dados

Parte crítica do Web Usage Mining.

Perda de informação quando os dados são coletados no
servidor (caching).

Privacidade do usuário.

Identificação do acesso de usuários (natureza sem estado).

Não se sabe o momento da saída do usuário.
Preparação dos Dados
Informações poderiam ser mais ricas:

Movimento do mouse durante o acesso.

Movimento da barra de rolagem.

Momento da mudança do site.

Integração dos dados de Conteúdo e Estrutura.
Tipo de Dados

Dados de uso da Web

Dados de Conteúdo

Dados de estrutura

Dados de Perfil do usuário
 Ideal: Combinação de todos os tipos de dados
Onde obter os dados?
Servidor: Múltiplos usuário em um site.
Cliente: Um cliente em vários sites.
Proxy: Vários usuários em vários sites.
Exemplo de dados Web
IP
ID
Data
Pedido Status Bytes
150.165.1.76
...
28/02/1999
05:01:20
POST
200
200.131.198.2 ...
27/01/2001
06:31:14
GET
200
200.246.210.4 ...
11/11/2002
15:15:17
POST
200
URL de Origem
Agente
2045
www.radix.com.br
Mozila4.0
(win95)
1287
www.cin.ufpe.br
IE6.0
(Win98)
www.cesar.org.br
Mozila 4.7
(WinNT)
2045
Aplicações
Aplicações Gerais:
Entendimento geral do
padrão de acesso dos
usuários de determinado
site.
Aplicação Específica:
Personalização do site
para clientes, premiação
de clientes por tempo ou
quantidade de acessos,
modificações na estrutura
do site.
Perfil Geral da Carteira
de Clientes
Satisfação e Fidelização
dos Clientes
Aplicações
Exemplos:
Consultas OLAP:
Qual a área do site mais acessada por usuários por turno:
manhã, tarde e noite?
Regras de Associação:
40% dos clientes que acessam o link download também
acessam o link de preços de produtos.
Classificação:
Ao entrar no site o cliente é classificado em um dos
possíveis padrões de página, baseado no seu perfil de
acesso.
Softwares no Mercado
Web Usage Mining:
Analog (http://www.analog.cx)
WUN 6.0 (http://ebusiness.hhl.de/research/wum)
Clementine (http://www.spss.com/SPSSBI/Clementine)
Web Content Mining:
Sav Z Server (http://savtechno.com)
mnoGoSearch (http://mnogosearch.org)
Web Structure Mining:
Clementine (http://www.spss.com/SPSSBI/Clementine)
Softwares no Mercado
- Clementine
Exemplo Prático
Exemplo: Encontrar associações entre links do site da UOL.
Exemplo Prático
Exemplo: Encontrar associações entre links do site da UOL.
ID
Amigos
Bate - Papo Biblioteca Carros ... Esportes
Virtuais
...
1
1
0
1
...
1
...
0
0
0
1
...
1
...
0
0
0
0
...
0
...
0
1
0
0
...
0
...
1
1
0
0
...
1
Exemplo Prático
Exemplo: Encontrar associações entre links do site da UOL.
Possíveis resultados:
55% dos clientes que acessam o link “Amigos Virtuais” não passam
mais que 5 minutos no site.
•
70% dos clientes que clicam no item de compras são clientes do
UOL.
•
50% dos clientes que acessam o link “Esportes” também acessam
o link “Carros”.
•
Exemplo Prático
Baseado no conhecimento adquirido: 50% dos clientes que
acessam o link “Esportes” também acessam o link “Carros”.
Por que não colocar uma chamada na página do UOLcarros das
principais notícias do esporte no dia?
Considerações Finais
Web: Enorme quantidade de dados, mas pouco conhecimento
 Web Mining: Descobrir este conhecimento para melhorar
eficiência de diversas aplicações da Web
 Web Mining não é só texto HTML
 Web Mining = Web Content + Web Structure + Web Usage
 Aplicação isolada de uma sub-área deixa lacunas
 Web Content e Web Structure tratam dados genéricos
 Web Usage se concentra em dados privativos
 Web Usage é usado principalmente em marketing na melhoria do
relacionamento com o cliente.
 Poucas empresas tem um processo de WebLog
 Muita informação não capturada como: movimento do mouse,
barra de rolagem e momento da mudança do site
