Web Usage MiningWeb Usage Mining

Fábio Ávila Rêgo PessoaMariano Cravo Teixeira Neto

CIn-UFPE

Web: repositório de informaçãoWeb: repositório de informação

Sem padronização Enorme

• Documentos de todo tipo• Informação de links• Informação de uso e acesso

Amplamente distribuído Muito heterogêneo Não estruturado / semi-estruturado Inter-conectado Em evolução De hipertextos e hipermídia

WWW: FatosWWW: 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

Web: CaracterísticasWeb: Características

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

• Interface de consulta limitada, baseada em buscas por palavra-chave

• Customização limitada para usuários individuais

Web Mining: TaxonomiaWeb Mining: Taxonomia

Web Mining

Web Content Mining

Web Structure Mining

Web Usage Mining

Web Page Content Mining

Search Results Mining

General Access Pattern Mining

Customized Usage

Tracking

Tarefas de Mineração de ConteúdoTarefas de Mineração de Conteúdo

Heterogêneo Envolve técnicas e outras áreas de computação não

tradicionalemente incluídas em mineração de dados• Information Retrieval

Engenho de busca especializados em Engenho de busca especializados em tipos de páginas específicostipos de páginas específicos

Ahoy! (1996-2000) – "achador de homepages"• Motivação: Altavista muito impreciso. Directories pouco dinâmicos• Entrada: nome de uma pessoa e instituição• Analisa resultados de vários motores de busca• Resultados analisados sintaticamente usando heurísticas• "Adivinhar" a URL usando heurísticas• Massa de teste

Execução: 9s. 74% sucesso com top reference / 9% guess URL. Altavista: 58% sucesso (dos quais 23% top reference)

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.

Linguagem de consulta para Web Linguagem de consulta para Web RestructuringRestructuring

WebOQL (1998)• Linguagem de consulta declarativa• Funcional e select-from-where• Retorna informações dentro de documentos Web.• Estrutura básica: hyperlink

Árvores ordenadas com arcos nomeados Arco interno: objetos estruturados Arco externo: referências (links)

• Exemplo: select [y.Title, y'.Url] from x in csPapers , y in x' where y.Authors ~"Smith"

Minerar o que o Motor de Busca achaMinerar o que o Motor de Busca acha

Motores de Busca atuais: preprocessadores convenientes para mineração• Baseado em palavra-chave, retorna respostas demais,

respostas de baixa qualidade, ainda falta muito, não customizado, etc.

Data Mining irá ajudar:• Cobertura: "Aumente e depois encolha", usando

sinônimos e hierarquias conceituais• Filtragem colaborativa: preferências de usuário/dicas.• Análise de links: páginas confiáveis e clusters• Linguagens baseadas na web: XML+WebSQL_WebML

Refinando e Agrupando Resultados do Refinando e Agrupando Resultados do Motor de BuscaMotor de Busca

WebSQL (Mendelzon et.al., 1996): linguagem estilo SQL para extrair documentos pertinentes• Estrutura básica:

Documents Anchors

• Select-from-where Exemplo:

• SELECT d.url, e.url, a.label• FROM Document d SUCH THAT "www.mysite.start" ->* d,• Document e SUCH THAT d => e• Anchor a SUCH THAT a.base = d.url• WHERE a.href = e.url

Algoritmo cria hierarquia conceitual (caso usar clustering hierarquico)

Ontologia de Resultados de BuscaOntologia de Resultados de Busca

Ainda há resultados demais em respostas típicas de motores de busca

Reorganizar os resultados usando uma hierarquia semântica (Zaiane et.al., 2001)

Mapeia resultados em hierarquias conceituais pré-existentes (manualmente desenvolvidas, ex, WordNet, Mikrocosmos)

Web Web StructureStructure Mining Mining

Web Structure Mining é extrair conhecimento das interconexões dos documentos.

Enorme quantidade de anotações humanas escondidas• Podem ajudar a inferir noções de "autoridade" em um tópico.

Descoberta de páginas influentes e dominantes na WWW.

HyPursuit (Weiss et.al., 1996)• Agrupamento 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

Busca por Páginas InfluentesBusca por Páginas Influentes

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.• Kwok (1975): uso de títulos de citações leva a uma boa

separação de cluster

Hyperlink Induced Topic Search (HITS)Hyperlink Induced Topic Search (HITS)

Algoritmo de Jon Kleinberg, 1998, Cornell University Boa autoridade: página apontada por bons hubs Bom hub: página que aponta para boas autoridades Duas etapas principais:

• Amostra: constrói coleção de páginas candidatas• Propagação de pesos: determina estimativas numéricas de pesos

de hub e autoridades. Saída: Lista de páginas

• Com pesos mais altos de hub• Com os pesos de autoridade mais altos.

Etapas do algoritmo HITSEtapas do algoritmo HITS

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.

S

T

Etapas do algoritmo HITSEtapas do algoritmo HITS

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.

Conjunto T Conjunto S

Etapas do algoritmo HITSEtapas do algoritmo HITS

Mesma idéia do que o EM: dados atualizam pesos que atualizam dados etc...

HITS então iterativamente atualiza os pesos de hub e autoridade de cada página

Faça pq denotar "a página p tem um link para a página q". HITS atualiza os hubs e autoridades da seguinte forma:

pq

qp

qaph

qhpa

)()(

)()(

Melhorias para o HITSMelhorias para o HITS

Deficiências do HITS• Computação puramente baseada em links na primeira etapa

Depois, nenhuma relação aos termos da consulta.

• Links de uma página hub propagam o mesmo peso Não resolve bem hubs com múltiplos tópicos.

Sistema CLEVER (Chakrabarti, et.al.,1998-1999)• Extensão 1: mini-hub pagelets

Previne "topic drifting" Conjuntos contíguos de links ao invés de páginas inteiras

• Extensão 2: texto âncora Usar texto dos href's Aumento os pesos dos links que ocorrem perto de instâncias

de termos de consulta

Connectivity ServerConnectivity Server

Connectivity Server (Bharat et.al., 1998) também extrai informação de links

Conjunto Base do HITS e CLEVER• 200 páginas resultantes da busca do Altavista

Conjunto Base do Connectivity Server• Todas as páginas retornadas pelo AltaVista

Operação• Servidor aceita consulta que leva a um conjunto L de um ou mais

URL's• Servidor retorna lista de predecessores e sucessores das páginas

de L• Usando essa informação, Connectivity Server inclui informação

sobre todos os links que existem entre as páginas da vizinhança.

b1

b2

bk

...

s1

s2

sk

...

f1

f2

fk

...

Back Set Start Set Forward Set

Connectivity ServerConnectivity Server

O grafo da vizinhança é o conjunto de:• Páginas iniciais L• Predecedores de L• Sucessores de L• Arestas entre eles.

Método de Kleinberg (HITS) é usado para computar ranking.

Filtragem de outlier (Bharat & Henzinger 1998-1999)• Integra conteúdo textual• Nós no grafo da vizinhança são vetores de termo.• Durante a expansão do grafo, podam nós distantes do vetor de

termos da consulta.• Evita contaminação de links irrelevantes.

Ranking de páginas baseado na Ranking de páginas baseado na popularidadepopularidade

O método de rank de páginas (Brin e Page, 1998)• Fazer o rank da "importância" das páginas Web, baseada em um

modelo de um "browser aleatório"• Inicialmente usada pra selecionar páginas para revisitar pelo crawler• Fazer o ranking das páginas em resultados de busca do Google.

Em um web crawl simulado, seguindo um link randômico de cada página visitada pode levar à revisita de páginas populares (páginas frequentemente citadas).

Brin e Page vêm pesquisas na Web como caminhadas aleatórias para atribuir "rank" independente de tópico a cada página na WWW, que pode ser usada para reordenar a saída de um motor de busca.

O número de visitas a cada página é seu PageRank. PageRank estima a taxa de visitação => nota de popularidade.

Ranking de páginas baseado na popularidadeRanking de páginas baseado na popularidade

Cada página p tem um número de links saindo dele C(p) (C para citação), e número de páginas apontando para a página p1,p2,...pn.

PageRank de P é obtido por

n

kk

k

pC

pPRdpPR

1 )(

)()1()(

ComparaçãoComparação

Google atribui rankings iniciais e os guarda independentemente de quaisquer consultas. Isso torna ele mais rápido.

CLEVER e Connectivity Server monta conjuntos raiz diferentes para cada termo de procura e prioriza aquelas páginas no contexto da consulta particular.

Google trabalha na direção para frente de link em link. CLEVER e Connectivity Server olha tanto na direção para frente

quanto para trás. Tanto as metodologias de páginas de rank de páginas e

hub/autoridades têm mostrado prover qualitativamente bons resultados de procura para tópicos de consulta muito amplos na WWW.

Links de NepotismoLinks de Nepotismo

Links de nepotismo são links entre páginas que estão presentes por razões outras que mérito

Spamming é usado para enganar motores de busca para dar rank alto para alguns documentos

Alguns motores de busca usam links para dar o rank de documentos (ex. Google)• Necessário para identificar e descartar links nepotistas

Reconhecer links de nepotismo na Web (Davidson 2000)• Davidson usa o algoritmo de classificação C4.5 em um grande número

de atributos de página, treinados em páginas manualmente rotuladas

IntroduçãoIntrodução

Web Mining: Descoberta e análise de informações úteis a partir da WWW.• Web Content Mining (WCM)

Busca automática de fontes informaç₧o online.

• Web Usage Mining (WUM) Descoberta de padrões de acesso de usuários em Servidores

Web (e.g. Apache)

Logs de Servidores WebLogs de Servidores Web

Servidores Web registram todas as ações dos usuarios em um web site.

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

Necessidade de minerar Web logsNecessidade de minerar Web logs

Logs de acesso registram várias informações para cada acesso.

A quantidade de acessos registrados, dependendo do site, pode ser enorme.

É a descoberta automática de padrões de acessos de usuários através da análise de logs de Servidores Web.

Aplicações de Web Usage MiningAplicações de Web Usage Mining

Proporciona:• 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

Web LogWeb Log

Informações normalmente contidas em logs de Servidores Web:• IP• User Id• Timestamp• Método

GET, POST

• Path (URL)

• Status Códigos:

404,505,303...

• Tamanho• Referência

Página de origem do link

• Agente Browser + SO

• Cookie

Análise do WeblogAnálise do Weblog

Weblog pode:• Minerado e ser analisado multidimensionalmente • para marketing eletrônico• de forma análoga • a dados de um banco de vendas tradicional

Diferenças essenciais:• Dados semi-estruturados• Imprecisão

Informações faltando em WebLogInformações faltando em WebLog

Utiliza₤₧o de funções dos browsers (ex.: voltar a página anterior, scrolling up/down...)• Requisição de páginas que estavam em cache• Requisição de páginas que estavam em um servidor proxy

Problemas quanto a páginas dinâmicasProblemas quanto a páginas dinâmicas

• CGI: dispara executável que esconde a interação real do usuário com o site

• Diferentes ações de usuários levando ao mesmo CGI• Mesma ação do usuário, em horas diferentes, levando a CGIs

diferentes• Um usuário usando mais de um browser por vez.• Etc...

Ferramentas comerciais de análise de Ferramentas comerciais de análise de WebLogWebLog

Fornecem• Freqüência de erros• Agrupar ações em atividades

Ex.: Ler mensagens, etc...

• Obter freqüência de ações individuais por usuário, domínio e sessão.

• Quais componentes do site são mais/menos acessados?• Quais s₧o os eventos mais freqüentes?• Há diferença de perfis de usuários de domínios diferentes no

Website?

Análise Mais Aprofundada Do Que Análise Mais Aprofundada Do Que Ferramentas ComerciaisFerramentas Comerciais

Análise aprofundada:• Análise de padrões (entre

usuários, etc...).• Análise de tendências:

comportamento X tempo tráfego de rede X tempo etc...

Questões que podem ser respondidas pela análise em profundidade:• Em que contexto os

componentes do Website são utilizados?

• Seqüências de eventos mais comuns?

• Diferenças de uso do site entre os usuários?

• Diferenças de uso do site no decorrer do tempo?

• Mudanças de comportamento dos usuários no decorrer do tempo?

• Distribuição do tráfego de rede com o tempo?

Preparação de DadosPreparação de Dados

Pré-processamento dos dados Problemas:

• Identificar os tipos das páginas: páginas de conteúdo ou páginas de navegação.

• Identificar visitantes.• Identificar sessão, transação, seqüências, etc...• Inferir páginas de cache

ProblemasProblemas

Identificando visitantes:• Login, cookies, combinações de endereço IP, agente, caminho

percorrido... Identificação de sessão:

• 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).

Identificando ações de usuários:• Análise de caminhos e parâmetros.

Uso do Conteúdo e da Estrutura Uso do Conteúdo e da Estrutura durante limpeza de Dadosdurante limpeza de Dados

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éias de

como realizar a limpeza e seleção dos dados. Ex: Agrupar páginas de transação por conteúdo

• O conteúdo de páginas dá pistas sobre o tipo da página:

Ex.: Página de navegação ou de conteúdo.

ClusteringClustering

Agrupando objetos que possuem características similares:• Agrupamento de transações:

Agrupar comportamentos sem se importar com conteúdo da transação ou com a identidade do usuário.

• Agrupamento de páginas e caminhos Agrupar páginas visitadas baseadas no conteúdo e usuários

• Agrupar visitantes Agrupar usuários de mesmo comportamento.

Classificação e associaçãoClassificação e associação

Regras de classificação de visitantes• Categorizar visitantes através da seleção de características

do site que melhor descrevem seus comportamentos.• Ex.: 40% dos visitantes que compram livros técnicos em

Recife têm entre 19 e 25 anos, e compram depois das 19:00. Regras de associação

• entre sessões e dentro das sessões

Sistemas de Web Usage MiningSistemas de Web Usage Mining

Gerais:• WebLogMiner (Zaïane et al, 1998)• WUM (Spiliopoulou et al, 1998)• WebSIFT (Cooley et al, 1999)

Sites Adaptativos (Perkowitz et al, 1998) Personalização e recomendação:

• WebWatcher (Joachims et al, 1998)

Exemplo de processo de mineração de Exemplo de processo de mineração de web log web log

O Web log deve ser filtrado para gerar 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)

Limpeza dos Dados e TransformaçãoLimpeza dos Dados e Transformação

IP, Usuário, Timestamp, M₫todo, Arquivo+parâmentros, Status, Tamanho

Máquina, Domínio da Internet, Usuário, dia, mês, ano, hora, minuto, segundo, método, arquivo, parâmetro, status, tamanho

Transformação e limpesa dos dados

Máquina, Domínio da Internet, Usuário, Field Site, dia, mês, ano, hora, minuto, segundo, Resource, Módulo/Ação, status, tamanho, Duração

Banco de Dados

Estrutura do Site

ConclusãoConclusã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.

Web Content MiningWeb Content Mining

Web Page Content Mining• Web Page Summarization• WebLog (Lakshmanan et.al., 1996)• WebOQL (Mendelzon et.al., 1998)

Pode identificar informações dentro de determinadas páginas• Ahoy! (Etzion et.al., 1997)

Usa heurísticas para distinguir páginas pessoais de outras páginas da web

• ShopBot (Etzion et.al., 1997) Procura por preços de produtos dentro de páginas da web.

Search Result Mining• Resumo de resultados de motores de busca• "Clustering Search Result (Leouski and Croft, 1996, Zamir e

Etzioni, 1997) Categoriza documentos usando frases em títulos e fragmentos

Web Structure MiningWeb Structure Mining

Usando Links• Hypursuit (Weist et.al., 1996)• PageRank (Brin et.al., 1998)• CLEVER (Chakrabarti et.al., 1998)

Usa interconexões entre páginas web para dar peso às páginas Usando Generalização

• MLDB (1994), VWV (1998) Usa uma representação multi-nível em banco de dados da web.

Contadores (popularidade) e listas de link são usados para capturar a estrutura.

Web Usage MiningWeb Usage Mining

General Access Pattern Tracking• Conhecimento a partir da navegação da página web (Shahabi

et.al., 1997)• WebLogMining (Zaiane, Xian e Han, 1998)• SpeedTracer (Wu, Yu, Ballman, 1998)• Wum (Spiliopiolou, Faulstich, 1998)• WebSIFT (Cooley, Tan, Srivastave, 1999)

Usa técnicas de KDD para entender padrões gerais de acesso e tendências. Pode dar luz a melhores estruturas e agrupamento de provedores de recursos assim como melhorias de rede e cacheamento.

Customized Usage Tracking• Sites Adaptativos (Perkowitz & Etzioni, 1997)

Analisa padrões de acesso de um usuário por vez. O site da web se re-estrutura automaticamente aprendendo de padrões de acesso do usuário.

• Personalização (SiteHelper: Ngu & Wu, 1997. WebWatcher: Joachims et.al., 1997, Mobasher et.al., 1999)

Provê recomendações aos usuários web