Web MiningWeb Mining

Disciplina de Mineração de DadosCIn-UFPE

Web: repositório de informaçãoWeb: 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: 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

WWW e Web MiningWWW 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: 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

Mineração do Conteúdo da Web:Mineração do Conteúdo da Web: Abordagem Baseado em Agentes 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:Mineração do Conteúdo da Web: Abordagem Baseado em Agentes 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:Mineração do Conteúdo da Web: Abordagem Baseado em Banco de Abordagem Baseado em Banco de

DadosDados 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 WebOQLExemplo de Árvore em WebOQL

[Grupo: Linguagem de Programação][Grupo: Inteligência Artificial]

[Tag: html]

[Título: Paradimas de Programação,Autor: John Smith]

[Título: AIMA,Autor: Russel]

[Título: Machine Learning,Autor: Tom Mitchel]

[Label Full versionURL:http://www.cin.ufpe.br]

[Label:table of contentsURL:http://www.cmu.edu/ML]

[Label:bookURL:http://www.cmu.edu/ML/book.zip]

Mineração do Conteúdo da Web:Mineração do Conteúdo da Web: Abordagem Baseado em Banco de Abordagem Baseado em Banco de

DadosDados 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.titleFROM Document d SUCH THAT ”http://www.somewhere.com" -> d

Mineração do Conteúdo da WebMineração do Conteúdo da WebAtualização de Páginas em Engenhos de Atualização de Páginas em Engenhos de

BuscaBusca 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 Organização hierárquica automática de resultados de Buscaresultados 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 Web StructureStructure Mining 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 de páginas influentes e dominantes na WWW.

Web Web StructureStructure Mining 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)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 HITSEtapas 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.

S

T

Etapas do algoritmo HITSEtapas 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 pq denotar "a página p tem um link para a página q".

HITS atualiza os hubs e autoridades da seguinte forma:

qp

pq

qaph

qhpa

)()(

)()(

Melhorias para o HITSMelhorias 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

GHITSGHITS 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 RankPage 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 RankCá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

qCqPRpPR)()()(

q E B(p)

Cálculo do Page RankCálculo do Page Rank

53100

9

50

50

3

ComparaçãoComparação

Processanentoon-line

Denpendentede consulta

Tipo decomunidade

Consultasgenéricas

HI TS sim sim competitiva sim

GHI TS não não competitiva sim

Clever sim sim competitiva sim

Page Rank não não colaborativa sim

Links de NepotismoLinks 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 WebServidores Web

Registram uma entrada de log para cada acesso• Grande quantidade de informação

Informações normalmente contidas nos logs

129.128.4.21 - [15/Aug/1999:10:45:32 - 0800] “GET /index.html 200 512 /main.html Mozilla/3.04 (Win95)

IP ID do usuário

Timestamp

Método URL/caminho

Status Tamanho

Referência

Agente

Cookie

Servidores WebServidores 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 logsNecessidade 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 DadosPreparaçã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 DadosPreparaçã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 DadosPreparaçã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 dadosMineração dos dados Análise de caminhos

• Descobrir os caminhos mais acessados no site• Exemplo: 80% dos clientes acessaram o site a partir da

página /download Regras de Associação

• 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 dadosMineraçã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 MiningSistemas 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ã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.