Web Usage Mining

  • View
    18

  • Download
    0

Embed Size (px)

DESCRIPTION

Web Usage Mining. Fábio Ávila Rêgo Pessoa Mariano Cravo Teixeira Neto CIn-UFPE. Web: 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 - PowerPoint PPT Presentation

Text of Web Usage Mining

  • Web Usage MiningFbio vila Rgo PessoaMariano Cravo Teixeira NetoCIn-UFPE

  • Web: repositrio de informaoSem padronizaoEnormeDocumentos de todo tipoInformao de linksInformao de uso e acessoAmplamente distribudoMuito heterogneoNo estruturado / semi-estruturadoInter-conectadoEm evoluoDe hipertextos e hipermdia

  • WWW: FatosCrescendo e mudando muito rapidamenteUm servidor WWW a cada 2 horas5 milhes de documentos em 1995320 milhes de documentos em 1998Mais de 1 bilho em 2000ndices se tornam inadequados muito rapidamenteNecessidade para uma melhor descoberta de recursos e extrao de conhecimento

  • Web: CaractersticasProblemas:O problema da "abundncia"99% da informao no do interesse de 99% das pessoasCobertura limitada da webRecursos da web escondidosMaioria dos dados em SGBD'sInterface de consulta limitada, baseada em buscas por palavra-chaveCustomizao limitada para usurios individuais

  • Web Mining: TaxonomiaWeb MiningWeb Content MiningWeb Structure MiningWeb Usage MiningWeb Page Content MiningSearch Results MiningGeneral Access Pattern MiningCustomized Usage Tracking

  • Tarefas de Minerao de ContedoHeterogneoEnvolve tcnicas e outras reas de computao no tradicionalemente includas em minerao de dadosInformation Retrieval

  • Engenho de busca especializados em tipos de pginas especficosAhoy! (1996-2000) "achador de homepages"Motivao: Altavista muito impreciso. Directories pouco dinmicosEntrada: nome de uma pessoa e instituioAnalisa resultados de vrios motores de buscaResultados analisados sintaticamente usando heursticas"Adivinhar" a URL usando heursticasMassa de testeExecuo: 9s.74% sucesso com top reference / 9% guess URL.Altavista: 58% sucesso (dos quais 23% top reference)ShopbotAgente de comprasIdentifica listas de preo e ofertas especiais.Aprende a reconhecer estruturas de documentos de catlogos on-line e sites e e-commerce.Tem que se ajustar s mudanas de contedo das pginas.

  • Linguagem de consulta para Web RestructuringWebOQL (1998)Linguagem de consulta declarativaFuncional e select-from-whereRetorna informaes dentro de documentos Web.Estrutura bsica: hyperlinkrvores ordenadas com arcos nomeadosArco interno: objetos estruturadosArco externo: referncias (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 achaMotores de Busca atuais: preprocessadores convenientes para mineraoBaseado em palavra-chave, retorna respostas demais, respostas de baixa qualidade, ainda falta muito, no customizado, etc.Data Mining ir ajudar:Cobertura: "Aumente e depois encolha", usando sinnimos e hierarquias conceituaisFiltragem colaborativa: preferncias de usurio/dicas.Anlise de links: pginas confiveis e clustersLinguagens baseadas na web: XML+WebSQL_WebML

  • Refinando e Agrupando Resultados do Motor de BuscaWebSQL (Mendelzon et.al., 1996): linguagem estilo SQL para extrair documentos pertinentesEstrutura bsica: Documents AnchorsSelect-from-whereExemplo:SELECT d.url, e.url, a.labelFROM Document d SUCH THAT "www.mysite.start" ->* d, Document e SUCH THAT d => e Anchor a SUCH THAT a.base = d.urlWHERE a.href = e.urlAlgoritmo cria hierarquia conceitual (caso usar clustering hierarquico)

  • Ontologia de Resultados de BuscaAinda h resultados demais em respostas tpicas de motores de buscaReorganizar os resultados usando uma hierarquia semntica (Zaiane et.al., 2001)Mapeia resultados em hierarquias conceituais pr-existentes (manualmente desenvolvidas, ex, WordNet, Mikrocosmos)

  • Web Structure MiningWeb Structure Mining extrair conhecimento das interconexes dos documentos.Enorme quantidade de anotaes humanas escondidasPodem ajudar a inferir noes de "autoridade" em um tpico.Descoberta de pginas influentes e dominantes na WWW.HyPursuit (Weiss et.al., 1996)Agrupamento hierrquicoUsa relaes baseadas no contedo e nos linksGrau de similaridade proporcional ao:Nmero de termos, ancestrais e descendentes em comumNmero de links entre documentos

  • Busca por Pginas InfluentesMtodo em procedncia de jornalismo / biblioteconomia:O fator de impacto de Garfield (1972): prov uma avaliao numrica na citao de jornais.Kwok (1975): uso de ttulos de citaes leva a uma boa separao de cluster

  • Hyperlink Induced Topic Search (HITS)Algoritmo de Jon Kleinberg, 1998, Cornell UniversityBoa autoridade: pgina apontada por bons hubsBom hub: pgina que aponta para boas autoridadesDuas etapas principais:Amostra: constri coleo de pginas candidatasPropagao de pesos: determina estimativas numricas de pesos de hub e autoridades.Sada: Lista de pginasCom pesos mais altos de hubCom os pesos de autoridade mais altos.

  • Etapas do algoritmo HITSComeando de uma consulta convencional, HITS monta um conjunto inicial S de pginasO conjunto S o conjunto raiz.As pginas so expandidas para um conjunto raiz T adicionando pginas que esto ligadas de ou para qualquer pgina no conjunto inicial S.ST

  • Etapas do algoritmo HITSHITS ento associa com cada pgina p um peso de hub h(p) e um peso de autoridade a(p), tudo inicializado para um.Conjunto TConjunto S

  • Etapas do algoritmo HITSMesma idia do que o EM: dados atualizam pesos que atualizam dados etc...HITS ento iterativamente atualiza os pesos de hub e autoridade de cada pginaFaa pq denotar "a pgina p tem um link para a pgina q". HITS atualiza os hubs e autoridades da seguinte forma:

  • Melhorias para o HITSDeficincias do HITSComputao puramente baseada em links na primeira etapaDepois, nenhuma relao aos termos da consulta.Links de uma pgina hub propagam o mesmo pesoNo resolve bem hubs com mltiplos tpicos.Sistema CLEVER (Chakrabarti, et.al.,1998-1999)Extenso 1: mini-hub pageletsPrevine "topic drifting"Conjuntos contguos de links ao invs de pginas inteirasExtenso 2: texto ncoraUsar texto dos href'sAumento os pesos dos links que ocorrem perto de instncias de termos de consulta

  • Connectivity ServerConnectivity Server (Bharat et.al., 1998) tambm extrai informao de linksConjunto Base do HITS e CLEVER200 pginas resultantes da busca do AltavistaConjunto Base do Connectivity ServerTodas as pginas retornadas pelo AltaVistaOperaoServidor aceita consulta que leva a um conjunto L de um ou mais URL'sServidor retorna lista de predecessores e sucessores das pginas de LUsando essa informao, Connectivity Server inclui informao sobre todos os links que existem entre as pginas da vizinhana.

  • b1b2bk

    ...

    s1s2sk

    ...

    f1f2fk

    ...

    Back SetStart SetForward Set

  • Connectivity ServerO grafo da vizinhana o conjunto de:Pginas iniciais LPredecedores de LSucessores de LArestas entre eles.Mtodo de Kleinberg (HITS) usado para computar ranking.Filtragem de outlier (Bharat & Henzinger 1998-1999)Integra contedo textualNs no grafo da vizinhana so vetores de termo.Durante a expanso do grafo, podam ns distantes do vetor de termos da consulta.Evita contaminao de links irrelevantes.

  • Ranking de pginas baseado na popularidadeO mtodo de rank de pginas (Brin e Page, 1998)Fazer o rank da "importncia" das pginas Web, baseada em um modelo de um "browser aleatrio"Inicialmente usada pra selecionar pginas para revisitar pelo crawlerFazer o ranking das pginas em resultados de busca do Google.Em um web crawl simulado, seguindo um link randmico de cada pgina visitada pode levar revisita de pginas populares (pginas frequentemente citadas).Brin e Page vm pesquisas na Web como caminhadas aleatrias para atribuir "rank" independente de tpico a cada pgina na WWW, que pode ser usada para reordenar a sada de um motor de busca.O nmero de visitas a cada pgina seu PageRank. PageRank estima a taxa de visitao => nota de popularidade.

  • Ranking de pginas baseado na popularidadeCada pgina p tem um nmero de links saindo dele C(p) (C para citao), e nmero de pginas apontando para a pgina p1,p2,...pn.PageRank de P obtido por

  • ComparaoGoogle atribui rankings iniciais e os guarda independentemente de quaisquer consultas. Isso torna ele mais rpido.CLEVER e Connectivity Server monta conjuntos raiz diferentes para cada termo de procura e prioriza aquelas pginas no contexto da consulta particular.Google trabalha na direo para frente de link em link.CLEVER e Connectivity Server olha tanto na direo para frente quanto para trs.Tanto as metodologias de pginas de rank de pginas e hub/autoridades tm mostrado prover qualitativamente bons resultados de procura para tpicos de consulta muito amplos na WWW.

  • Links de NepotismoLinks de nepotismo so links entre pginas que esto presentes por razes outras que mritoSpamming usado para enganar motores de busca para dar rank alto para alguns documentosAlguns motores de busca usam links para dar o rank de documentos (ex. Google)Necessrio para identificar e descartar links nepotistasReconhecer links de nepotismo na Web (Davidson 2000)Davidson usa o algoritmo de classificao C4.5 em um grande nmero de atributos de pgina, treinados em pginas manualmente rotuladas

  • IntroduoWeb Mining: Descoberta e anlise de informaes teis a partir da WWW.Web Content Mining (WCM)Busca automtica de fontes informao online.Web Usage Mining (WUM)Descoberta de padres de acesso de usurios em Servidores Web (e.g. Apache)

  • Logs de Servidores WebServidores Web registram todas as aes dos usuarios em um web site.Ferramentas comerciais fornecem:Relatrio de hits e bytes transferidosURLs mais acessadasLista de browsers mais usados pelos usuriosHits por hora/dia/semana/ms.Lista de erros.rvore de diretrios acessados

  • Necessidade de minerar Web logsLogs de acesso registram vrias informaes para cada acesso.A quantidade de acessos registrados, dependendo do site, pode ser enorme. a descoberta automtica de padres de acessos de usurios atravs da anlise de logs