Seminário paty aula 9 04-05-2011

PGCIN/UFSC - PCI 3214 – Maio/2011 – Patricia Neubert

Universidade Federal de Santa CatarinaCentro de Ciências da Educação

Departamento de Ciência da InformaçãoPrograma de Pós-Graduação em Ciência da Informação

Mestrado em Ciência da Informação

Disciplina: PCI3214 – Recuperação Inteligente de Informação Professor: Dr. Angel Freddy Godoy Viera

Seminário – Aula 9

04 de maio de 2011

Patricia da Silva Neubert


Bibliografia recomendada:

CHEN, Hsinchun; CHAU, Michael. Web Mining: machine learning for Web applications. In: CRONIN, Blaise (ed.). Annual Review of Information Science and Technology. Medford: Information Today, Inc., 2004, v.38, cap. 6, p. 289-329.

Seminário – Aula 9

Temática:

Mineração de conteúdo web;

Spiders web inteligentes;

Mineração de estruturas da web;

Mineração de uso da web.

PGCIN/UFSC - PCI 3214 – Maio/2011 – Patricia NeubertPGCIN/UFSC - PCI 3214 – Maio/2011 – Patricia Neubert

INTRODUÇÃO A WEB MINING

Web

Nesse caso,

a extração de conhecimento útil é um problema.

(CHEN; CHAU, 2004)

Tamanho;

Conteúdo não-estruturado;

Conteúdo dinâmico;

Multilíngue;

Dados em vários formatos.

2



“O conhecimento não vem só do conteúdo das páginas

em si, mas também das características únicas da Web,tais como a sua estrutura de hyperlink e sua diversidade de

conteúdos e línguas. A análise destas características, muitas

vezes revela padrões interessantes e novos conhecimentos.

Tal conhecimento pode ser usado para melhorar a eficiência

dos usuários e eficácia na busca de informações na Web, e

também para aplicações não relacionadas com a Web, como

suporte à tomada de decisão ou gestão empresarial”

(CHEN; CHAU, 2004, p.289, tradução nossa, grifo nosso) 3



A solução para o problema vem das....

...técnicas de aprendizado de máquina.

A pesquisa sobre Data Mining se tornou um subcampo

significativo das pesquisas sobre aprendizagem de máquina.

“O termo Web Mining foi criado por Etzioni (1996) para denotar o

uso de técnicas de mineração de dados para descobrir

automaticamente documentos e serviços Web, extrair

informações a partir de recursos da Web, e descobrir padrões

gerais na web.”(CHEN; CHAU, 2004, p.289-290, tradução nossa) 4



Segundo colocam Chen e Chau (2004, p.289-290) a pesquisa

de Web Mining foi, com o passar do tempo, estendida para

abranger a utilização da mineração de dados e técnicas

similares para descobrir recursos, padrões e conhecimento a

partir da Web e dados relacionados à Web (por exemplo dados de uso

da Web ou servidor de web logs).

Os autores adotam a definição de Cooley, Mobasher e

Srivastava (1997, apud CHEN; CHAU, 2004, p.289-290, tradução nossa)

para Web Mining:

“é a descoberta e análise de informações úteis a partir da World

Wide Web.” 5



Web Mining coincide com outras áreas, incluindo mineração de

dados, mineração de texto, acesso e recuperação da

informação.

Fonte: Chen e Chau, 2004, p.291 6





informação.


A classificação é

baseada no objetivo e

na fonte dos dados.





informação.


A classificação é

baseada no objetivo e

na fonte dos dados.



A pesquisa de Web Mining está na intersecção de várias áreas:

Recuperação da informação

Recuperação na Web Aprendizado de máquina

Bases de dados Data Mining

Text Mining

Aprendizagem de máquina é a base para a maioria das

técnicas de mineração de dados e de mineração de textos;

As pesquisas de recuperação de informação tem grande

influencia nas pesquisas de aplicações de Web Mining.

(CHEN; CHAU, 2004)7



Aprendizagem de Máquina

(CHEN; CHAU, 2004)

Algoritmos de aprendizagem de máquina têm sido desenvolvidas

para atenuar os problemas de aquisição de conhecimentos por

computadores feitas manualmente – a partir de especialistas

humanos – visando a aquisição de conhecimentos

automaticamente a partir de exemplos ou dados de origem.

Mitchell (1997, p. 2) define a aprendizagem de máquina como o

estudo de "qualquer algoritmo de computador que melhora seu

desempenho em algumas tarefas por meio da experiência.”

8




(CHEN; CHAU, 2004)

São classificados em:

Aprendizado supervisionado

Aprendizado não supervisionado

No aprendizado supervisionado, os exemplos de treinamento consiste nos

padrões para input/output. O objetivo do algoritmo de aprendizagem é prever

os valores de saída de novos exemplos, com base em seus valores de

entrada.

No aprendizado não supervisionado, os exemplos de treinamento contém

apenas os padrões de entrada, não especificado o padrão de saída associado

a entrada. O algoritmo de aprendizagem deve generalizar a partir dos padrões

de entrada para descobrir os valores de saída.9




(CHEN; CHAU, 2004)

Com base em Chen (1995), Langley e Simon (1995) os autores

identificaram cinco áreas de pesquisa em aprendizagem de

máquina:

I. Modelos probabilísticos;

II. Aprendizagem simbólica e indução de regras;

III. Redes neurais;

IV. Algoritmos baseados na evolução;

V. Aprendizagem analítica e lógica fuzzy.

10




I . Modelos probabilísticos

O uso de modelos probabilísticos, foi uma das primeiras

tentativas de realizar aprendizado de máquina, dos quais o

exemplo mais popular é o métodométodo BayesianoBayesiano.

(CHEN; CHAU, 2004)

Classifica os diferentes objetos em classes pré-definidas com base

em um conjunto de recursos, armazenando a probabilidade de cada

classe, de cada característica, e de cada recurso, com base nos

dados de treinamento. Quando uma nova instância for encontrado,

ele pode ser classificado de acordo com essas probabilidades (Langley,

Iba, & Thompson, 1992).(CHEN; CHAU, 2004)

11




II. Aprendizagem simbólica e indução de regras

São classificadas de acordo com a estratégia de aprendizagem:

a) aprendizagem mecânica; b) aprendizagem por ensino; c)

aprendizagem por analogia; d) aprendizagem a partir de

exemplos; e) e aprendizagem por descoberta (Carbonell, Michalski, &

Mitchell, 1983; Cohen & Feigenbaum, 1982).

A aprendizagem por exemplos parece ser a mais promissora.

Ela é implementado através da aplicação de um algoritmo que tenta

induzir a descrição do conceito geral, que melhor descreve as

diferentes classes de exemplos de treinamento. (CHEN; CHAU, 2004) 12




(CHEN; CHAU, 2004)

III. Redes neurais

Uma rede neural é um gráfico de muitos nós ativos (neurônios),

que são conectadas umas às outras por ligações ponderadas

(sinapses).

Com base em exemplos de treinamento, os algoritmos de

aprendizagem podem ser usados para ajustar os pesos de

conexão na rede para que ele possa prever ou classificar

exemplos desconhecidos corretamente.13




IV. Algoritmos baseados em evolução

Algoritmos baseados em evolução dependem de analogias com

os processos naturais e da noção Darwiniana da sobrevivência

dos mais aptos.

Fogel (1994, apud CHEN; CHAU, 2004) identifica três categorias de algoritmos

de evolução baseada em: algoritmos genéticos, estratégias

evolutivas e a programação evolutiva.Uma população sofre um conjunto de operações genéticas (crossover e mutação).

Seleção ‘natural’ de indivíduos mais aptos. Os indivíduos selecionados passam a

formar a próxima geração e o processo continua. Após uma série de gerações, o

programa converge e a solução ideal é representada pelo melhor indivíduo.14




(CHEN; CHAU, 2004)

V. Aprendizagem analítica e lógica fuzzy

Aprendizagem analítica representa o conhecimento como regras

de lógica, e executa este raciocínio sobre estas regras para

procurar provas. As provas podem ser compilados em regras

mais complexas para resolver problemas com um pequeno

número de pesquisas necessárias.

Os sistemas tradicionais de aprendizagem analítica dependem de

regras de computação rígido. Para resolver esse problema,

sistemas de lógica fuzzy têm sido propostas.15



Metodologias de Avaliação

(CHEN; CHAU, 2004)

Avaliação da precisão de um sistema de aprendizagem, e a

escolha de uma boa metodologia de avaliação.

Métodos de avaliação populares (Efron & Tibshirani, 1993; Stone, 1974):

amostragem de validação

validação cruzada

leave-one-out

amostragem bootstrap

16







amostragem de validaçãoamostragem de validação

validação cruzada

leave-one-out


Os dados são divididos em um conjunto de

treinamento (2/3) e um conjunto de testes

(1/3 dos dados). Depois que o sistema é

formado pelos dados de treinamento, é

necessário prever o valor de saída de cada

exemplo no conjunto de teste. Estes valores

são então comparados com os valores de

saída real para determinar a precisão. 16




(CHEN; CHAU, 2004)





validação cruzadavalidação cruzada

leave-one-out


O conjunto de dados é divididos em

subconjuntos, geralmente subgrupos de 10. O

sistema é então treinado e testado para 10

interações e, em cada interação 9 subconjuntos

são usados como dados de treinamento e 1

como dados de teste. Na rotação, cada

subconjunto de dados serve como teste de jogo

em uma interação. A precisão do sistema é a

precisão média das 10 interações.

.

16








validação cruzada

leaveleave--oneone--outout


Leave-one-out é o caso extremo de validação

cruzada, onde os dados originais são

divididos em n subgrupos, onde n é o

número de observações nos dados originais.

O sistema é treinado e testado por n

interações, em cada um dos quais n-1

exemplos são usados para o treinamento e a

instância restante é usado para testes. 16




(CHEN; CHAU, 2004)





validação cruzada

leave-one-out

amostragem bootstrapamostragem bootstrap

n amostras aleatórias independentes são

retirados do conjunto de dados original de

tamanho n. Como as amostras são tomadas

com a substituição, o número de instâncias

exclusivas será inferior a n. Essas amostras

são então utilizadas como conjunto de

treinamento para o sistema de aprendizagem,

e os restantes dados que não foram incluídos

na amostra são usados para testar o sistema(Efron & Tibshirani, 1993).

16



Aprendizagem de Máquina para RI: Pré Web

(CHEN; CHAU, 2004)

Técnicas de aprendizagem de máquina foram aplicadas em

aplicações de recuperação de informação muito antes do

surgimento da web.

Algumas delas são o uso de aprendizado de máquina na:

Extração de informaçãoFeedback de relevânciaFiltragem de informações e recomendaçãoClassificação de texto e clustering.

17




(CHEN; CHAU, 2004)



surgimento da web.



Técnica destinada a identificar

automaticamente as informações

úteis a partir de documentos de

texto.

17




(CHEN; CHAU, 2004)



surgimento da web.



Método usado em sistemas de

IR para ajudar os usuários a

realizarem buscas de forma

interativa e reformular as

consultas de pesquisa com base

na avaliação de documentos

obtidos anteriormente. (Ide, 1971;

Rocchio, 1971). 17




(CHEN; CHAU, 2004)



surgimento da web.



Também ajudam os usuários a

reformular as consultas de

pesquisa, mas tenta aprender

sobre os interesses dos usuários,

por meio de suas avaliações e

ações e, em seguida, usa essas

informações para analisar novos

documentos. 17




(CHEN; CHAU, 2004)



surgimento da web.



Classificação de texto é a

classificação dos documentos em

grupos pré-definidas (aprendizado

supervisionado), e clustering é o

agrupamento dos documentos em

categorias definidas dinamicamente,

com base nas suas semelhanças

(aprendizado não supervisionado).17


WEB MINING

Web Mining pode ser dividido em três categorias (Kosala & Blockeel, 2000):

Mineração de conteúdo da Web;

Mineração de estruturas da Web;

Mineração de uso da Web.

refere-se à descoberta de informações úteis a partir do conteúdo da Web,

incluindo texto, imagens, áudio e vídeo.

Refere-se ao estudo de potenciais modelos subjacentes às estruturas de links da web. > Usada para a formação do ranking dos motores de busca.

Centra-se na análise de pesquisas/consultas para encontrar padrões interessantes. > Aplicação no desenvolvimento de perfis de usuário 18


WEB MINING

Desafios:

1. Documentos em HTML;

2. Diversidade dos documentos (tamanho, formato, estrutura);

3. Documentos dinâmicos.

“Outra característica da Web, talvez o mais importante, é a “Outra característica da Web, talvez o mais importante, é a

estrutura de hyperlink.”estrutura de hyperlink.”

19(CHEN; CHAU, 2004)


MINERAÇÃO DE CONTEÚDO WEB

Mineração de conteúdo Web é baseado principalmente na

pesquisa em recuperação de informação e mineração de

texto, como extração de informações, classificação e agrupamento de texto e

visualização da informação.

A maioria dos documentos na Web são documentos de texto,

portanto, a mineração de texto para documentos na Web pode

ser considerado um sub-campo de mineração de conteúdos

da Web.




Mineração de conteúdo Web é baseado principalmente na

pesquisa em recuperação de informação e mineração de

texto, como extração de informações, classificação e agrupamento de texto e

visualização da informação.

A maioria dos documentos na Web são documentos de texto,

portanto, a mineração de texto para documentos na Web pode

ser considerado um sub-campo de mineração de conteúdos

da Web.extração de informação classificação de texto texto clustering

Aplicações de mineração de textos em documentos web: 20



As técnicas de extraçãoextração dede informaçõesinformações tem sido aplicado a

documentos de texto simples, nesse sentido, a extração de

informações de páginas da Web - em HTML - pode

apresentar problemas.

“Em vez de um documento composto de parágrafos, uma

página da Web pode ser um documento composto de uma

barra lateral com links de navegação, tabelas com dados

textuais e numéricos, frases capitalizados, e palavras

repetitivas. A gama de formatos e estruturas é muito

diversificada em toda a web.”

tags de marcaçãoPáginas não-estruturadas

(CHEN; CHAU, 2004, p.289, tradução nossa, grifo nosso)

21



A extração de informação analisa as páginas da Web

individualmente, a classificaçãoclassificação dede textotexto e textotexto clusteringclustering

analisam um conjunto de páginas web.

Em algumas aplicações, as tags de HTML são simplesmente

retirados dos documentos da Web e algoritmos tradicionais

são então aplicadas para realizar a classificação e

agrupamento de texto – ignorando, algumas características da

página web.

O texto de documentos vizinhos – links para os quais a página aponta - tem

sido utilizado na tentativa de melhorar o desempenho da classificação. 22(CHEN; CHAU, 2004)



Spiders são "programas de software que atravessam o espaço

de informação da World Wide Web, seguindo links de

hipertexto e recuperação de documentos na Web através do

protocolo HTTP padrão" (CHEONG, 1996, p. 82, apud CHEN; CHAU, 2004)

... são usados por motores de busca para construir suas bases

de dados.

A maior parte usa algoritmos simples para descoberta de

recursos web, mas há o uso de algoritmos avançados

(algoritmo genético, redes neurais, modelos híbridos...)

Spiders Web Inteligentes

23



Maior parte do conteúdo em inglês;

No entanto, número de páginas em outros idiomas vem

crecendo.

Problemas no processamento de texto de diferentes idiomas.

Alguns algoritmos são independentes de idioma (classificação

de texto, clustering); algoritmos como o de extração de

informações devem ser adaptados para os diferentes idiomas.

Web Mining Multilíngue




Muitas vezes é difícil extrair conteúdo útil a partir da Web,

neste caso, ferramentas de visualização têm sido utilizadas

para ajudar os usuários a manterem uma “visualização geral"

de um conjunto de resultados de recuperação de motores de

busca.

Nestes sistemas de visualização, técnicas de aprendizado de

máquina são muitas vezes utilizados para determinar como as

páginas Web devem ser apresentadas.

Web Visualização




Os documentos da Web não serão mais textos não

estruturados, eles serão identificados e entendidos por

computadores.

A aprendizagem de máquina pode desempenhar três papéis

importantes na Web Semântica. Sendo usada para...

1. criar automaticamente os metadados de marcação;

2. criar, fundir, atualizar e manter ontologias;

3. compreender e executar o raciocínio sobre os metadados

fornecidos pela Web Semântica, a fim de extrair

conhecimento a partir da Web de forma mais eficaz.

Web Semântica

26


MINERAÇÃO DE ESTRUTURAS DA WEB

A estrutura de links da Web tem sido amplamente

utilizada para inferir informações importantes sobre as

páginas web. A mineração de estruturas da Web tem sido

largamente influenciado pelas pesquisas de análise de

redes sociais e análise de citações (bibliometria).

Citações (ligações) entre as páginas da Web geralmente

são indicadores de grande relevância ou de boa

qualidade.27

(CHEN; CHAU, 2004)



Geralmente, quanto maior o número de links para uma

determinada página, mais útil a página é considerada. O

raciocínio é que uma página referenciada por muitas

pessoas, é provável que seja mais importante do que

uma página que raramente é mencionada.

“Além disso, é razoável dar uma ligação de uma fonte

autorizada (como Yahoo) um peso maior do que um link

de uma página Web da importância pessoal.”

28(CHEN; CHAU, 2004, p.311)



As técnicas de mineração de estruturas da Web são

frequentemente utilizados para melhorar o desempenho de

aplicações web.

Por exemplo o PageRank:

É eficaz no ranking dos resultados do motor de busca Google

(http://www.google.com) (Brin e Page, 1998).

É utilizado como uma medida para orientar as aranhas do

Search Engine, onde URLs com PageRank mais elevado são

visitadas primeiro (Cho et al., 1998).



MINERAÇÃO DE USO DA WEB

Servidores Web, proxies, e aplicações cliente podem

facilmente capturar dados sobre o uso da Web.

Logs do servidor Web contêm informações sobre todas as

visitas às páginas hospedadas em um servidor.

Ficheiros solicitados

endereço de IP

código de erro número de bytes enviados

navegador usado

Ao realizar a análise dos dados de uso da Web, os sistemas de

mineração da Web podem descobrir conhecimentos úteis sobre

as características de um sistema, do uso e os interesses dos

usuários.30

(CHEN; CHAU, 2004)



Um dos principais objetivos da mineração de utilização da

Web é o interesse em revelar tendências e padrões. Esses

padrões podem frequentemente fornecer conhecimentos

importantes sobre os clientes de uma empresa ou dos

usuários do sistema.

Srivastava, Cooley, Despande e Tan (2000) fornecem uma

estrutura para a mineração de uso da Web, que consiste em

três etapas principais:

Análise de padrões e tendências

I. pré-processamento;

II. descoberta de padrões;

III. análise de padrões.31

(CHEN; CHAU, 2004)



Personalização e colaboração

Muitos dos objetivo de uso das técnicas de Web Mining são

fornecer informações e serviços personalizados para os usuários.

OsOs dadosdados dede usouso dada WebWeb fornecemfornecem umauma excelenteexcelente maneiramaneira dede

aprenderaprender sobresobre oo interesseinteresse dosdos usuáriosusuários (Srivastava(Srivastava etet alal..,, 20002000))..

Mineração de uso da Web pode ajudar a identificar usuários que

acessaram páginas Web semelhante. Os padrões que emergem

podem ser aplicados em pesquisas sobre a Web colaborativa e

filtragem colaborativa.32

(CHEN; CHAU, 2004)


CONSIDERAÇÕES FINAIS

A Web tornou-se o maior repositório de conhecimento do mundo.

A extração de conhecimento da Web de forma eficiente e

eficaz está se tornando cada vez mais importante.

Limitações das pesquisas em Web Mining:

dificuldade de criação de coleções de ensaio adequadas;

dificuldade de coletar dados de uso da Web em sites

diferentes (maioria dos dados de log do servidor e os dados

recolhidos por empresas são proprietários).

(CHEN; CHAU, 2004, p.316, tradução nossa) 33



As atividades de Web Mining ainda estão em estágios iniciais

e devem continuar a desenvolver-se como a evolução da web.

No futuro...

mineraçãomineração dede dadosdados multimídiamultimídia..

“Além dos documentos textuais, como HTML, MS Word Document, PDF e

arquivos de texto, um grande número de documentos multimídia estão

contidas na Web, tais como imagens, áudios e vídeos. Apesar de os

documentos textuais serem relativamente fáceis de recuperar e analisar, as

operações em arquivos de multimídia são muito mais difíceis de executar, e

como o conteúdo multimídia na web cresce rapidamente, Web Mining

tornou-se um problema desafiador.”(CHEN; CHAU, 2004, p.316-317, tradução nossa)

34



Web Mining no futuro...

conteúdo multilíngüe;

Internet sem fio;

Web invisível.

“A Web tornou-se a maior base de conhecimento que jamais

existiu. No entanto, sem a representação do conhecimento

adequado e algoritmos de descoberta de conhecimento, é

apenas como um ser humano com a memória extraordinária,

mas sem capacidade de pensar e raciocinar.”(CHEN; CHAU, 2004, p.319, tradução nossa)

35


OBRIGADA!

Education

Seminário paty aula 9 04-05-2011