Embed Size (px)
Citation preview
Ilma da Consolação Barbosa
PROSPECÇÃO DE DADOS NO APOIO
À GESTÃO DE CONHECIMENTO
EM UM PORTAL WEB
Dissertação apresentada ao Curso de Pós Graduação em Ciência da Computação do Instituto de Ciências Exatas da Universidade Federal de Minas Gerais, como requisito parcial para a obtenção do grau de Mestre em Ciência da Computação.
Belo Horizonte
Janeiro de 2004
Agradecimentos
A Deus pelo dom sagrado da vida e por ter me presenteado com o convívio entre
pessoas que valorizam o conhecimento como o único tesouro que jamais poderá nos ser
furtado, preceito este que sempre me impulsionou na dedicação aos estudos acadêmicos.
Ao meu orientador e amigo, Prof. José Luis Braga, pela grande dedicação e
incentivo, demonstrando a cada momento a sua verdadeira vocação para o exercício desta
árdua profissão. Principalmente, o agradeço pelo incomensurável apoio, confiança e
generosidade no momento de maior dificuldade pessoal pelo qual passei durante esta
jornada. É fácil ser amigo de mil pessoas nos seus momentos felizes, o difícil e grandioso
é permanecer amigo de uma única pessoa nos seus momentos de angústia e tristeza.
Ao meu único e amado filho, Pedro Henrique, meu “herói da resistência”, que
apesar de, neste último ano, ter enfrentado uma grande enfermidade, lutou com bravura e
conseguiu superá-la, demonstrando a existência da verdadeira bondade Divina. Muito lhe
agradeço pelo seu “coração de melão”, pelo carinho e amor e por aceitar os meus
momentos de ausência, principalmente quando estávamos fisicamente próximos.
Ao meu marido Wender, amigo e companheiro de todas as horas, por ter me
incentivado a iniciar esta jornada, pelo carinho, pela compreensão, pela grande
colaboração e pela paciência, principalmente nos momentos de grande ansiedade.
Aos meus pais e todos os familiares pelos exemplos de fé, união e superação
diante dos problemas da vida. Agradeço, carinhosamente, a todos vocês que me
ajudaram, me apoiaram, sempre acreditaram e torceram por mim. Espero que este
trabalho concretize o sonho daqueles que não tiveram a mesma oportunidade.
A Dedeca, por toda a ajuda, pelo carinho e dedicação com que cuida de todos nós.
A Marisa Mendes de Freitas, do DPI-UFV, e a Renata Viana Moraes Rocha, do
DCC-UFMG, pela compreensão e colaboração em todos os momentos de necessidade.
Aos colegas do mestrado pelos bons momentos de convivência e de estudo em
grupo, comprovando que somente unidos conseguimos superar as dificuldades.
Aos professores do mestrado pelos ensinamentos e incentivo.
A UFV e UFMG pela oportunidade.
A Escola Agrotécnica Federal de Barbacena, principalmente ao Prof. César
Romano Quintão e a Profª. Marisa Attademo Raso Marques, que não mediram esforços
para que este sonho pudesse ter um início de realização.
ii
Abstract
Web Data Mining is an application of datamining techniques to web data recovery
and information generation. It can be considered a promising support technique in
enterprise knowledge management. In that environment, users with common interests and
goals use the internet or even intranets to make knowledge available as collective
knowledge or even collective intelligence.
Aiming at providing support to knowledge management in a web or internet
environment, this work is dedicated to investigating the special area of Web Usage
Mining. Among our established goals is the development of a tool to extract web access
patterns from knowledge portals usage logs.
Knowledge portals can benefit from those patterns by using them for
personalization and cooperativity purposes. This means supporting the ability of
offering the user more information than he actually have asked for, in an intelligent
information extraction dialogue between the system and the user. Usage patterns can also
be used to enhance and refine knowledge contained in behind the scenes ontologies or
thesaurus, used to provide semantic support to the whole process.
A consequence of the results presented in this work is the enhancement of
knowledge management environments, leading to improvements in knowledge
generation, creation, integration and broadcasting.
iii
Resumo
Dentre as possibilidades de aplicação da prospecção de dados, a Prospecção de
Dados da Web pode ser utilizada com o objetivo de gerar informações úteis ao processo
de Gestão de Conhecimento neste ambiente, visto que este processo pode ser aplicado
além do âmbito das organizações, onde uma comunidade de usuários com interesses em
comum usam a Internet como infraestrutura para disponibilizar seu conhecimento,
tornando-o coletivo.
Com a finalidade de proporcionar apoio à Gestão de Conhecimento no ambiente
Web, este trabalho é dedicado ao estudo da Prospecção de Uso da Web e ao
desenvolvimento de uma ferramenta tecnológica destinada à tarefa de geração de padrões
de acesso relativos às consultas realizadas em um portal Web.
Tais padrões são disponibilizados para uso pelo mecanismo de busca do portal
Web, visando-se os benefícios futuros de personalização, como a habilidade de melhor
servir às necessidades dos usuários, apresentando-lhe as informações mais apropriadas a
qualquer momento, a partir da utilização de uma política de ranqueamento que se
beneficie da filtragem colaborativa. Por outro lado, tais padrões são utilizados para a
geração de conhecimento visando a manutenção da ontologia incorporada ao portal.
Assim, ambas as utilizações da ferramenta proposta se destinam a apoiar o processo de
Gestão de Conhecimento no domínio Web através de aprimoramento das tarefas de
criação, integração e disseminação do conhecimento, possibilitando melhorias na
personalização das relações entre o usuário e o portal com o objetivo de proporcionar ao
usuário informações relevantes a partir da investigação de suas estratégias de buscas e de
suas preferências frente aos documentos recuperados pelo mecanismo de busca do portal.
Assim, foram consideradas todas as etapas do processo de Prospecção de Uso da
Web, desde a obtenção e pré-processamento dos dados, passando-se pela fase de
prospecção de dados propriamente dita, até a análise e utilização dos padrões obtidos a
partir dos dados de uso do mecanismo de busca disponível no portal.
iv
Sumário
AGRADECIMENTOS .........................................................................................II
ABSTRACT......................................................................................................... III
RESUMO............................................................................................................. IV
SUMÁRIO ............................................................................................................. V
LISTA DE FIGURAS........................................................................................VII
LISTA DE TABELAS ........................................................................................ IX
1 – INTRODUÇÃO................................................................................................1
2 – CONTEXTUALIZAÇÃO E REVISÃO DA LITERATURA......................3
2.1 – GESTÃO DO CONHECIMENTO .......................................................................3
2.2 – DESCOBERTA DE CONHECIMENTO ...............................................................4
2.2.1 – Pré-processamento e Transformação..................................................5
2.2.1.1 – Definição e Entendimento do Problema .......................................6
2.2.1.2 – Coleta e Extração dos Dados ........................................................6
2.2.1.3 – Organização dos Dados ................................................................6
2.2.1.4 – Engenharia dos Dados ..................................................................7
2.2.2 – Prospecção de Dados ..........................................................................7
2.2.3 – Pós-processamento ..............................................................................7
2.3 – PROSPECÇÃO DE DADOS ..............................................................................7
2.3.1 – Tipos de Repositórios para Prospecção de Dados..............................8
2.3.2 – Tipos de Conhecimentos Descobertos pela Prospecção de Dados ...11
2.3.3 – Aplicações de Prospecção de Dados.................................................14
2.4 – WEB INTELIGENTE .....................................................................................18
2.4.1 – Técnicas de IA para a Web Inteligente..............................................19
2.4.1.1 – Web Semântica............................................................................19
2.4.1.2 – Prospecção de Dados da Web .....................................................21
2.4.1.3 – Interfaces Inteligentes ou Cooperativas......................................38 v
2.4.1.4 – Agentes Inteligentes....................................................................39
2.4.2 – Aplicações da Web Inteligente...........................................................40
2.4.2.1 – Personalização de Sites da Web ..................................................41
2.4.2.2 – Recomendação............................................................................43
2.4.2.3 – Busca de Informação ..................................................................44
2.5 – TRABALHOS RELACIONADOS.....................................................................44
3 – PROPOSTA DE TRABALHO .....................................................................47
3.1 – ENGENHARIA ONTOLÓGICA.......................................................................47
3.2 – CONHECIMENTO PERSONALIZADO .............................................................49
3.3 – OBJETIVOS.................................................................................................50
3.4 – APLICAÇÃO PRÁTICA.................................................................................52
4 – PROJETO ......................................................................................................87
4.1 – FUNCIONALIDADES E CASOS DE USO .........................................................87
4.2 – PROJETO LÓGICO .......................................................................................93
4.2.1 – Diagrama de Classe UML.................................................................93
4.3 – INTERAÇÕES E RECURSOS TECNOLÓGICOS ................................................94
5 – IMPLEMENTAÇÃO E RESULTADOS.....................................................97
5.1 – PROCESSO DE PROSPECÇÃO DE PADRÕES DE CONSULTAS COOPERATIVAS 97
5.2 – APLICAÇÃO PARA GERAÇÃO DE CONHECIMENTO PARA A MANUTENÇÃO DA
ONTOLOGIA ............................................................................................105
5.3 – APLICAÇÃO DE GERAÇÃO DE CONHECIMENTO PARA O MECANISMO DE
BUSCA ....................................................................................................114
5.4 – RESULTADOS ...........................................................................................116
6 – CONCLUSÕES E TRABALHOS FUTUROS..........................................120
6.1 – CONCLUSÕES ...........................................................................................120
6.2 – TRABALHOS FUTUROS .............................................................................123
7 – BIBLIOGRAFIA .........................................................................................126
APÊNDICE A: ALGORITMOS PARA PROSPECÇÃO DE DADOS........136
ALGORITMOS PARA PROSPECÇÃO DE REGRAS DE ASSOCIAÇÃO........................136
ALGORITMOS PARA PROSPECÇÃO DE PADRÕES SEQÜENCIAIS ..........................150
vi
Lista de Figuras
Figura 2.1: Fluxo Básico do Processo de Descoberta de Conhecimento. ...........................5
Figura 2.2: Representação do Processo de Pré-Processamento...........................................6
Figura 2.3: Categorias de Prospecção de Dados da Web...................................................24
Figura 3.1: Tela principal do Portal SBI-Café..................................................................54
Figura 3.2: Consulta Cooperativa......................................................................................58
Figura 3.3: Mapeamento de Palavras da Consulta para Termos da Ontologia..................59
Figura 3.4: Itens de Conhecimento Associados ao Termo da Ontologia. .........................60
Figura 3.5: Resultado da Expansão da Consulta usando os Termos Selecionados. ..........61
Figura 3.6: Funcionalidades da Ferramenta Proposta. ......................................................63
Figura 3.7: Relacionamentos entre as Tabelas do Log de Busca. .....................................68
Figura 3.8: WAP-mine: Prospecção de Padrões de Acesso em Banco de Dados de
Seqüências de Acesso. ...................................................................................76
Figura 3.9: WAP-tree e WAP-tree Condicional................................................................78
Figura 3.10: Construção da WAP-tree para Seqüências de Acesso Web. .........................79
Figura 3.11: Prospecção de Todos os Padrões Freqüentes em uma WAP-tree.................83
Figura 3.12: Etapas Específicas do Processo Proposto para Apoio à Gestão de
Conhecimento no Portal Web. .....................................................................86
Figura 4.1: Diagrama de Casos de Uso. ............................................................................87
Figura 4.2: Caso de uso “1 - Acessa Arquivos de Log de Buscas”. ..................................88
Figura 4.3: Caso de uso “2 - Faz Pré-processamento”. .....................................................89
Figura 4.4: Caso de uso “3 - Faz Prospecção de Padrões de Consultas Cooperativas”. ...90
Figura 4.5: Caso de uso “4 - Gera Conhecimento para Manutenção da Ontologia”.........91
Figura 4.6: Caso de uso “5 - Gera Conhecimento para Mecanismo de Busca”. ...............92
Figura 4.7: Diagrama de Classes da Ferramenta. ..............................................................93
Figura 4.8: Principais Interações da Ferramenta Proposta. ...............................................94
Figura 5.1: Interface Utilitários. ........................................................................................98
Figura 5.2: Interface para Determinação da Periodicidade. ..............................................98
Figura 5.3: Interface para Determinação de Suporte.........................................................99
Figura 5.4: Interface Principal da Aplicação. ..................................................................100
Figura 5.5: Interface de Simulação da Fase Acessar Log................................................101
vii
Figura 5.6: Interface de Simulação da Fase Limpar Log. ...............................................102
Figura 5.7: Interface de Simulação da Fase Gerar Transações........................................103
Figura 5.8: Interface de Simulação da Fase Descobrir Padrões . ....................................105
Figura 5.9: Interface de Opções de Conhecimento para Manutenção da Ontologia. ......106
Figura 5.10: Interface de Padrões de Acesso para a Manutenção da Ontologia. ............107
Figura 5.11: Interface de Outras Informações para Manutenção da Ontologia...............108
Figura 5.12: Interface das Expansões mais Requisitadas ao Tesauro. ............................109
Figura 5.13: Interface das Expansões mais Acessadas....................................................110
Figura 5.14: Interface das Expansões não Acessadas......................................................111
Figura 5.15: Interface das Expansões sem Respostas......................................................112
Figura 5.16: Interface de Pesquisa dos Documentos Atualmente Retornados. ...............113
Figura 5.17: Interface da Aplicação de Simulação de Busca. .........................................114
Figura 5.18: Interface da Aplicação de Padrões de Expansões Requisitadas à Ontologia...118
Figura A.1: Algoritmo Apriori. .......................................................................................139
Figura A.2: Função GeraCandidato.................................................................................140
viii
Lista de Tabelas
Tabela 3.1: Estrutura da Tabela Acesso. ...........................................................................64
Tabela 3.2: Estrutura da Tabela Consulta..........................................................................65
Tabela 3.3: Estrutura da Tabela Publicação. .....................................................................66
Tabela 3.4: Domínio dos Valores Relacionados ao Campo TipoConsulta da Tabela
Consulta. ........................................................................................................67
Tabela 3.5: Amostra da Tabela Acesso. ............................................................................68
Tabela 3.6: Amostra da Tabela Consulta. .........................................................................69
Tabela 3.7: Seqüências de Acessos de Usuários Individuais. ...........................................74
Tabela 5.1: Resultado da comparação entre os Padrões de Acesso e o Ranqueamento
Atual dos Documentos Retornados pela Biblioteca Virtual do Café. .........119
Tabela A.1: Notação Utilizada na Maioria dos Algoritmos Estudados...........................138
ix
1 – Introdução
Não é exagero dizer que a WWW (Web World Wide) é o mais excitante impacto
para a sociedade humana nos últimos 10 anos. Ela alterou a maneira de se negociar,
prover e receber educação, gerenciar organizações, etc. O efeito mais direto é a
modificação nas coleções de informações, comunicação e intercâmbios. Hoje a Web se
tornou a maior fonte de informação disponível no planeta, sendo um enorme, explosivo,
dinâmico e na maior parte não-estruturado repositório de dados.
Os usuários da Web querem ter ferramentas de buscas eficientes para encontrar
informações relevantes, facilmente e precisamente. Por isto, os provedores de serviços
da Web querem encontrar uma maneira de prever os comportamentos dos usuários e
obter informações personalizadas para reduzir a carga de tráfego, possibilitando o
projeto de sites diferentes para grupos de usuários diferentes. Da mesma forma, os
analistas do domínio querem ter ferramentas para aprender as necessidades dos
usuários/clientes. Assim, para atender a tais exigências, a prospecção de dados da Web
torna-se um ativo e popular campo de pesquisa [Wang, 2000].
Nesse contexto, surgiu uma nova família de ferramentas, as quais, através da
aplicação de algoritmos mais inteligentes, como os de prospecção de dados, são capazes
de extrair conhecimento útil a partir do acesso dos usuários ao conjunto de páginas de
um site. Tais ferramentas foram classificadas como sendo de prospecção de uso da Web
[Cooley et al., 1997].
Prospecção de dados é o termo que se popularizou para denominar o processo de
descoberta de conhecimento em bases de dados, tratando-se da utilização de ferramentas
computacionais a fim de descobrir informações valiosas e potencialmente úteis [Fayyad
et al., 1996], descritas em forma de padrões, a partir dos volumes de dados que estão
coletados e armazenados pelas organizações. A obtenção desses conhecimentos
implícitos tem sido útil, sobretudo para as empresas de negócios conhecerem melhor
seu público-alvo e tomarem decisões mais acertadas objetivando-se o aumento da
competitividade. No entanto, conforme [Feldens, 1997], a aplicabilidade dos resultados
de pesquisas na área de prospecção de dados é bastante ampla, podendo ser útil em
qualquer área do conhecimento onde seja gerado um certo volume de informação.
A proposta de trabalho consiste em mostrar a aplicabilidade de técnicas de
prospecção de dados em soluções destinadas a apoiar a gestão do conhecimento através 1
do desenvolvimento de uma ferramenta que utilize estas técnicas no ambiente Web. Esta
ferramenta foi instanciada (implementada) para uso no portal SBICafé, mantido por
uma comunidade científica de pesquisa formada em torno do Consórcio Brasileiro de
Pesquisa e Desenvolvimento do Café (CBP&D-Café). Em um trabalho anterior,
realizado por [Pontes, 2002], o SBICafé incorporou uma ontologia o que resultou em
melhorias significativas no que diz respeito à eficácia das buscas e navegação sobre os
itens de conhecimento disponíveis. Assim, o presente trabalho constitui-se de um
estudo sobre a utilização de prospecção de dados referentes ao uso da Web e a proposta
de uma ferramenta para a extração e processamento de padrões de acesso ao portal
SBICafé, a partir dos registros de logs de acessos dos usuários ao seu mecanismo de
busca, com o objetivo de maximizar a eficiência deste serviço e a manutenção da
ontologia a ele incorporada, servindo assim como apoio ao processo de gestão de
conhecimento associado a este domínio.
O capítulo 2 apresenta uma contextualização e revisão da literatura, focalizando-
se nos fundamentos dos sistemas de Gestão de Conhecimento destinados à descoberta
de conhecimento, sendo expostas todas as fases deste processo, com suas devidas
características, destacando-se a fase de prospecção de dados. Ainda neste capítulo,
apresenta-se um estudo sobre as tendências de direcionamento para a Web Inteligente,
focalizando-se alguns dos componentes de Inteligência Artificial propostos para esta
nova área, sendo detalhados a prospecção de dados da Web e o uso de ontologias. No
decorrer do capítulo, são expostas algumas aplicações práticas relativas aos temas
destacados, finalizando-se com a indicação de projetos relacionados a este trabalho.
O capítulo 3 apresenta a proposta, estrutura e resultados esperados deste
trabalho, iniciando-se pela descrição das carências atuais ligadas à disciplina de
engenharia ontológica, principalmente na fase de manutenção de ontologias, sendo
seguido pela motivação de otimização de buscas na Web, visando-se a obtenção de
conhecimento personalizado. Neste capítulo também são mais especificamente
explicitados os objetivos do trabalho, bem como a proposta de uma aplicação prática
destinada a demonstrar as funcionalidades propostas.
O capítulo 4 apresenta o projeto da solução proposta e o capítulo 5 mostra a
implementação da aplicação prática proposta, apresentando também os resultados
observados a partir da aplicação da técnica de prospecção de dados na obtenção de
padrões de acesso destinados ao apoio à gestão de conhecimento no portal SBIcafé.
O capítulo 6 relata as conclusões, assim como possibilidades de trabalhos
futuros. 2
2 – Contextualização e Revisão da Literatura
Este capítulo apresenta uma contextualização da área desta dissertação,
definindo a prospecção de dados como uma das etapas da descoberta de conhecimento,
considerada como uma das possibilidades de otimização do processo genérico da gestão
de conhecimento. Com o deslocamento das fontes de conhecimento para a Web, surge a
necessidade de focalizar técnicas e ferramentas apropriadas aos objetivos de uma Web
Inteligente, e assim são detalhados alguns dos componentes desta nova metodologia
mais intimamente ligados ao processo de descoberta de conhecimento no âmbito da
Web. Ao final deste capítulo são apresentados alguns projetos relacionados ao contexto
deste trabalho, assim como suas características e contribuições.
2.1 – Gestão do Conhecimento
Gestão de Conhecimento preocupa-se com a aquisição, manutenção e acesso ao
conhecimento organizacional, sendo um processo cíclico cujos passos podem se resumir
em três atividades: criação, integração e disseminação. Em abordagens tradicionais de
gestão de conhecimento os gerentes coletam e estruturam conteúdos em uma memória
organizacional e então a disseminam, apresentando-se como uma abordagem top-down
em que os trabalhadores são tratados como destinatários passivos de informação. No
entanto, perspectivas inovadoras trazem dois aspectos essenciais: os trabalhadores criam
constantemente novos conhecimentos e o conhecimento é efeito colateral do trabalho
[Fischer & Ostwald, 2001].
Segundo [Becerra-Fernandez, 2001], os sistemas de gestão de conhecimento
podem ser divididos em:
- Sistemas de preservação do conhecimento: preservam e formalizam o
conhecimento de especialistas para que possam ser compartilhados com outros.
- Sistemas de aplicação do conhecimento: extraem e capturam conhecimento
para reuso na solução de novos e recorrentes problemas.
- Repositórios de conhecimento: organizam e distribuem conhecimento, não
sendo destinados à descoberta de novos conhecimentos relacionados ao
conhecimento anteriormente descoberto.
3
- Sistemas de descoberta de conhecimento: auxiliam na descoberta de novos
conhecimentos através da implementação de algoritmos inteligentes tais como
prospecção de dados.
A proposta da gestão de conhecimento é explorar os recursos intelectuais da
organização para aumentar a produtividade, renovar valores e aumentar a
competitividade, habilitando práticas inovadoras a um nível organizacional
(comunidade) para suportar cooperação e comunicação entre trabalhadores do
conhecimento de um mesmo domínio e entre domínios [Fensel et al., 2001], [Fischer &
Ostwald, 2001]. A elevação da complexidade dos produtos, o deslocamento em direção
à globalização, o aumento do foco no cliente e o aparecimento de organizações virtuais
devido ao impacto da Internet, demandam uma abordagem mais completa e sistemática
para a gestão de conhecimento [Staab et al., 2001].
O incrível crescimento da WWW (World Wide Web) estabeleceu uma
infraestrutura de conhecimento compartilhado e este tem sido identificado como um
fator de produção chave, ao lado do trabalho e do capital. Neste contexto, onde a WWW
é tida como uma das principais fontes de informação para o desenvolvimento dos
processos empresariais, bem como para tarefas individuais, seus usuários necessitam de
técnicas mais eficientes para criação, integração e disseminação do conhecimento
através da Web [Studer et al., 2000].
2.2 – Descoberta de Conhecimento
A descoberta de conhecimento pode ser definida como a extração não trivial de
informações potencialmente úteis, previamente desconhecidas e implícitas em dados
brutos [Fayyad et al., 1996], sendo um processo que se dá de forma iterativa e
interativa, na medida em que as etapas podem ser repetidas tantas vezes quanto seja
necessário, de acordo com a validação do usuário, podendo-se acrescentar novos dados,
integrar novas fontes etc., para atingir diferentes e mais significativos resultados
[Zaïane, 1999a].
O processo de descoberta de conhecimento é composto por uma série de
atividades podendo-se enumerar quatro etapas básicas, as quais, partindo-se dos dados
disponíveis e, normalmente, da definição de um problema, conduzem à descoberta do
conhecimento. O fluxo básico do processo é ilustrado na Figura 2.1.
4
Conhecimento
Transformação
Pós-Processamento
Prospecção de Dados
Pré-Processamento
Dados
Figura 2.1: Fluxo Básico do Processo de Descoberta de Conhecimento.
2.2.1 – Pré-processamento e Transformação
Estas etapas, segundo [Brachman & Anand, 1996], são responsáveis pela maior
parte do tempo total do processo, consumindo entre 50% e 80% deste tempo, e visam
criar representações de conjuntos de dados adequados à aplicação de algoritmos de
prospecção de dados, envolvendo a seleção, amostragem, transformação de
representações etc., envolvendo aspectos como a definição do problema, a coleta e
extração dos dados, organização dos dados e a engenharia dos dados, resultando na
criação de um ou mais conjuntos de dados como pode ser visto na Figura 2.2 [Fayyad et
al., 1996].
5
Base para
Prospecção
Dados
Explorados
Dados
Extraídos
Dados
Brutos
Engenharia
dos Dados
Organização
dos Dados
Coleta e
Extração
dos Dados
Definição e
Entendimento
do Problema
Figura 2.2: Representação do Processo de Pré-Processamento.
Como, normalmente, os algoritmos de prospecção de dados não podem acessar
os dados em seu formato nativo, seja em razão da forma em que são armazenados, seja
pela normalização adotada na modelagem do banco de dados, é necessário a conversão
desses dados em um formato apropriado, podendo-se ainda sumarizar os dados a fim de
se reduzir o número de variáveis sob consideração.
2.2.1.1 – Definição e Entendimento do Problema
Devem ser bem definidos os domínios onde serão realizados as análises e os
objetivos do processo de descoberta de conhecimento, pois a falta de clareza nesta etapa
pode levar a resultados totalmente desprezíveis. Assim, o problema deve ser definido
conjuntamente pelo analista da prospecção e engenheiros do domínio específico.
2.2.1.2 – Coleta e Extração dos Dados
Esta fase é destinada à obtenção de dados relevantes para a solução do problema,
onde devem ser realizadas as atividades de definição dos atributos apropriados e a
extração física dos dados de diversas fontes.
2.2.1.3 – Organização dos Dados
Nesta fase, os atributos adquiridos devem se tornar semanticamente claros para o
analista da prospecção. Além disto, deve-se realizar testes de sanidade nos dados
obtidos, visto o alto risco de ocorrência de erros na fase anterior, podendo-se aplicar
6
algoritmos de prospecção os dados visando-se observação de dados e/ou resultados
incorretos.
2.2.1.4 – Engenharia dos Dados
Nesta fase, a base estática de dados está pronta para a prospecção, podendo-se
criar várias bases de dados, ou conjuntos de dados, em contraste com a base de
prospecção única criada a partir da fase de coleta e extração de dados. A engenharia dos
dados é necessária nos casos onde se deve explorar o uso de diferentes atributos e
tamanhos de amostras, análise de subconjuntos de dados e existência de diferentes
enfoques na definição do problema.
2.2.2 – Prospecção de Dados
A prospecção de dados pode ser vista como a aplicação de algoritmos de
aprendizagem aos dados pré-processados. A prospecção de dados e a descoberta de
conhecimento em bancos de dados são freqüentemente tratadas como sinônimos, sendo
uma etapa no processo de descoberta de conhecimento [Zaïane, 1999a], que produz um
conjunto de padrões sob um custo computacional aceitável. Devido a sua importância,
esta etapa será discutida detalhadamente na seção 2.3.
2.2.3 – Pós-processamento
Na etapa de pós-processamento são feitas a análise e interpretação dos resultados
obtidos pela aplicação dos algoritmos de prospecção de dados. Nesta etapa, é de suma
importância a presença de um especialista do domínio onde se está aplicando o processo
de descoberta de conhecimento, pois a seguinte questão deve ser respondida: o
conhecimento gerado é útil, válido, relevante e acionável? Se a resposta não for
satisfatória, então poderá ser necessário repetir todo ou parte do processo de descoberta
de conhecimento.
2.3 – Prospecção de Dados
O grande crescimento no volume de dados disponibilizado pelas organizações,
comunidades científicas e pessoas individuais gera uma necessidade urgente de novas
técnicas que possam inteligentemente e automaticamente transformar os dados
processados em informações úteis e conhecimento. Em resposta a tal demanda,
Prospecção de Dados, ou Data Mining, tornou-se uma área de pesquisa com crescente
7
importância. Prospecção de dados é um processo de extração de informações implícitas,
não previamente conhecidas e potencialmente úteis, a partir de dados que podem estar
contidos em diferentes repositórios [Chen et al., 1996], consistindo de um conjunto de
técnicas usadas em uma abordagem automática para exaustivamente explorar e mostrar
relacionamentos complexos existentes em grandes conjuntos de dados [Moxon, 1996].
A descoberta de conhecimento pode ser aplicada para gerência de informação,
processamento de consultas, tomada de decisão, controle de processo, e muitas outras
aplicações. Dentro do processo de descoberta de conhecimento, a prospecção de dados é
uma etapa que envolve efetivamente as técnicas e algoritmos que produzirão o
conhecimento procurado, sendo considerada o núcleo deste processo.
A prospecção de dados é uma nova metodologia que objetiva a melhoria de
eficiência dos processos de tomada de decisões, sejam elas científicas ou comerciais,
permitindo a exploração e inferência de informação e relacionamentos úteis a partir dos
dados. A grande maioria das ferramentas analíticas tem a capacidade de tratar
sofisticadas perguntas realizadas pelos usuários. No entanto, tais ferramentas são
limitadas em sua habilidade de descobrir padrões complexos e tendências, pois são
dependentes das hipóteses e perguntas feitas pelo usuário, em oposição à metodologia
de prospecção de dados, a qual analisa os dados e formula automaticamente hipóteses
sobre eles, utilizando-se de variados algoritmos para alcançarem os resultados
desejados.
Diferentes esquemas de classificação podem ser usados para categorizar
métodos de prospecção de dados, como o tipo de repositório em que os dados a serem
trabalhados se encontram, o tipo de conhecimento a ser descoberto e os tipos de técnicas
a serem utilizadas. Assim, a prospecção de dados é dependente da aplicação, fazendo
com que aplicações distintas possam requerer diferentes técnicas deste método para
alcançar um grau aceitável de eficiência [Chen et al., 1996].
2.3.1 – Tipos de Repositórios para Prospecção de Dados
Segundo [Zaïane, 1999b], a prospecção de dados deve ser aplicável a qualquer
tipo de repositório de dados. Entretanto, algoritmos e abordagens podem diferir quando
aplicados em diferentes tipos de dados, pois realmente os desafios apresentados pelos
diferentes tipos de dados variam significantemente. Alguns exemplos de repositórios de
dados em que a prospecção de dados tem sido aplicada são:
8
a) Arquivos Flat: constituem a fonte de dados mais comum para algoritmos de
prospecção de dados, podendo ser definidos como arquivos de dados simples
em formato texto ou binário com uma estrutura que deve ser conhecida pelo
algoritmo de prospecção de dados a ser aplicado. Os dados nestes arquivos
podem ser transações, séries de tempo, métricas científicas etc.
b) Bancos de Dados Relacionais: consistem de um conjunto de tabelas
contendo valores de atributos de entidades ou valores de atributos de
relacionamentos entre entidades. As tabelas são formadas por colunas e
linhas, onde colunas representam atributos e linhas representam tuplas, que
correspondem a um objeto ou a um relacionamento entre objetos e são
identificadas por um conjunto de valores de atributos representando uma
chave única. A linguagem de pesquisa mais comumente utilizada para
bancos de dados relacionais é SQL (Structure Query Language), a qual
permite a recuperação e manipulação dos dados armazenados, bem como o
cálculo de funções de agregação tais como médias, somas, etc. Algoritmos
de prospecção de dados utilizando bancos de dados relacionais podem ser
mais versáteis que aqueles especificamente escritos para consultas a bancos
de dados relacionais. Além da prospecção de dados poder beneficiar-se da
SQL para seleção, transformação e consolidação dos dados, ela pode fazer
mais do que isto, provendo prognóstico, comparação, detecção de
divergências etc.
c) Armazéns de Dados: um armazém de dados, ou Data Warehouse, é um
repositório de dados colecionados de múltiplas fontes (freqüentemente
heterogêneas), possibilitando a análise de diferentes fontes sob a mesma
perspectiva. Em outras palavras, dados de diferentes fontes podem ser
carregados, limpos, transformados e integrados conjuntamente. Para facilitar
o processo de tomada de decisão e visões multidimensionais, os armazéns de
dados são geralmente modelados através de uma estrutura multidimensional,
como por exemplo, uma estrutura de cubo de dados. Um cubo de dados
contém células que armazenam medidas de agregação de alguns valores e
células especiais que armazenam somatórios por dimensão. Cada dimensão
de um cubo de dado contém uma hierarquia de valores de um atributo. Por
causa de sua estrutura, somatórios pré-computados que por eles são mantidos 9
e os valores hierárquicos de atributos de suas dimensões, cubos de dados são
muito adaptáveis para pesquisas interativas rápidas e análise de dados de
diferentes níveis conceituais, conhecidas como OLAP (On-Line Analitical
Processing).
d) Bancos de Dados de Transações: são conjuntos de registros representando
transações, cada uma com uma marca de tempo, um identificador e um
conjunto de itens. Associados a arquivos de transações podem também estar
dados descritivos para os seus itens. Uma vez que bancos de dados
relacionais não permitem tabelas aninhadas (isto é, um conjunto de valores
como atributos), as transações são geralmente armazenadas em arquivos flat
ou em duas tabelas normalizadas, uma para as transações e a outra para os
itens das transações. Uma análise típica de prospecção de dados em tais
dados é conhecida como análise de cestas de compras ou estudo de regras de
associações entre itens ocorridos juntos ou em seqüência.
e) Bancos de Dados Multimídia: incluem mídias de vídeo, imagens, áudio e
textos, que podem ser armazenado em bancos de dados objeto-relacionais ou
orientados a objetos, ou simplesmente em um sistema de arquivos.
Prospecção de dados de repositórios multimídia pode requerer metodologias
de computação gráfica, interpretação de imagens e processamento de
linguagem natural.
f) Bancos de Dados Espaciais: são bancos de dados que, além dos dados
habituais, armazenam informações geográficas como mapas, e
posicionamento global ou regional, apresentando novos desafios para os
algoritmos de prospecção de dados.
g) Bancos de Dados de Séries de Tempo: contêm dados relacionados com
tempo, tais como dados de estoque ou registros de atividades, tendo
geralmente um fluxo contínuo de novos dados, que algumas vezes têm a
necessidade de uma análise em tempo real.
h) World Wide Web (WWW): é o repositório mais heterogêneo e dinâmico
disponível, tendo seus dados organizados em documentos interconectados, 10
que podem ser textos, áudio, vídeo, dados brutos e até mesmo, aplicações. A
prospecção de dados da Web tenta apontar as questões relacionadas aos seus
principais componentes: conteúdo, estrutura e uso.
2.3.2 – Tipos de Conhecimentos Descobertos pela Prospecção de Dados
Os tipos de padrões que podem ser descobertos dependem da classe de
prospecção de dados empregada. Existem dois tipos de classes de prospecção de dados:
prospecção de dados descritiva (ou de descoberta de conhecimento), a qual descreve as
propriedades genéricas dos dados existentes, e prospecção de dados preditivas, que tenta
fazer predições baseadas em inferências sobre os dados disponíveis [Zaïane, 1999b].
A predição é o maior objetivo da prospecção de dados, tendo o maior potencial
financeiro e tendo a descrição mais precisa. Problemas de predição são descritos em
termos de objetivos específicos, tais como aqueles relacionados a registros antigos com
respostas conhecidas, que são usados para projetar novos casos. Já a descoberta de
conhecimento é cercada por alguns tópicos relacionados a suporte a decisão. Problemas
de descoberta de conhecimento geralmente descrevem uma etapa anterior a predição,
onde a informação é insuficiente para predição, estando mais próximo ao suporte à
decisão que tomada de decisão e, portanto quando uma aplicação não tem o potencial
para uma solução prevista, a descoberta de conhecimento pode ser o objetivo [Weiss &
Indurkhya, 1998].
Podem ser descritas as funcionalidades de prospecção de dados e a variedade de
conhecimentos que podem ser descobertos [Zaïane, 2000]:
a) Caracterização: é uma sumarização de características genéricas de objetos
em uma classe designada, produzindo o que é conhecido como regras de
caracterização. Os dados relevantes a uma classe específica de usuários são
normalmente recuperados por uma pesquisa feita ao banco de dados e
executada através de um módulo de sumarização para a extração da essência
dos dados em diferentes níveis de abstração. Por exemplo, pode-se querer
caracterizar os clientes de uma locadora de vídeo que regularmente locam
mais de 30 filmes em um ano. Para tal tarefa, com um cubo de dados
contendo o somatório dos dados, operações simples de OLAP (On-Line
Analitical Processing) resolvem o propósito de caracterização dos dados.
11
b) Discriminação: produz as chamadas regras discriminantes e é basicamente a
comparação das características comuns de objetos de duas classes, chamadas
classe designada e classe contrastante. Por exemplo, pode-se querer
comparar as características comuns dos clientes que alugaram mais de 30
filmes no ano passado com aqueles que alugaram menos que 5 filmes. As
técnicas utilizadas para discriminação são muito similares àquelas usadas
para caracterização de dados com a exceção de que os dados resultantes da
discriminação incluem medidas comparativas.
c) Análise de Associação: é a descoberta das comumente chamadas regras de
associação. Aqui se estuda a freqüência de itens que ocorrem juntos em
bancos de dados de transações, e baseado em um valor limiar, chamado
suporte, identifica os conjuntos de itens freqüentes. Um outro limite,
chamado confiança, que é a probabilidade de um item aparecer em uma
transação quando um outro item aparece, é usado para definir regras de
associação. Análise de associação é geralmente usada em análises de cestas
de compras. Por exemplo, pode ser útil para o gerente de uma locadora de
vídeo saber quais filmes são freqüentemente locados juntos ou se existe um
relacionamento entre a locação de um certo tipo de filme e a compra de
pipocas ou refrigerantes. As regras de associação descobertas são da forma
P→Q [s,c], onde P e Q são conjunções de pares de valores de atributos, e s
(suporte) é a probabilidade que P e Q apareçam juntos em uma transação e c
(confiança) é a probabilidade condicional que Q apareça em uma transação
quando P está presente. Por exemplo, a regra de associação hipotética:
TipoLocacao(X, ”jogo”) ∧ Idade (X, “13-19”) → Compra (X,”pipoca”)
[s=2%, c=55%], indica que 2% das transações consideradas são de clientes
com idade entre 13 e 19 anos que locam um jogo e compram uma pipoca, e
existe uma segurança de 55% que clientes jovens que locam um jogo
também compram pipoca.
d) Classificação: é a organização de dados em dadas classes, sendo também
conhecida como classificação supervisionada, que usa rótulos de classes
conhecidos para ordenar os objetos na coleção de dados. Abordagens de
classificação normalmente usam um conjunto de treinamento onde todos os
objetos já são associados com rótulos de classes conhecidos. O algoritmo de
classificação aprende a partir dos dados de treinamento e constrói um
modelo, que é usado para classificar novos objetos. Por exemplo, após 12
iniciar uma política de crédito, o gerente de uma locadora de vídeo pode
analisar o comportamento dos clientes tendo em vista seu crédito, e rotular
os clientes de acordo com os clientes que receberam créditos, com três
possíveis rótulos: seguro, arriscado e muito arriscado. A análise de
classificação poderá gerar um modelo a ser usado para aceitar ou rejeitar
futuras requisições de crédito.
e) Prognóstico: existem dois tipos de prognósticos ou predições: pode-se tentar
prever alguns valores de dados indisponíveis ou tendências pendentes, ou
prever um rótulo de classe para algum dado, sendo este último ligado à
classificação. Uma vez que se tem um modelo de classificação construído
com base em um conjunto de treinamento, o rótulo da classe de um objeto
pode ser previsto baseando-se nos valores dos atributos do objeto e nos
valores dos atributos das classes. Prognóstico é, mais freqüentemente,
relacionado a previsões de valores numéricos indisponíveis ou a tendências
de acréscimo/decréscimo de dados relacionados a tempo, sendo a sua idéia
principal, o uso de um grande número de valores anteriores na consideração
de prováveis valores futuros.
f) Agrupamento: similar à classificação, agrupamento é a organização de dados
em classes. Entretanto, diferentemente de classificação, em agrupamento, os
rótulos das classes não são conhecidos e algoritmos de agrupamento tentam
descobrir classes aceitáveis. Agrupamento é chamado também de
classificação não supervisionada, porque a classificação não é estabelecida
por rótulos de classes dados. Existem diversas abordagens de agrupamento,
todas baseadas no princípio de maximização da similaridade entre os objetos
de uma mesma classe (similaridade intraclasse) e minimização da
similaridade entre objetos de classes diferentes (similaridade interclasses).
g) Análise de Exceções: exceções são objetos que não podem ser agrupados em
uma dada classe ou agrupamento, e, freqüentemente, é importante que sejam
identificadas, pois se por um lado elas possam ser consideradas ruídos e
descartadas em algumas aplicações, por outro elas podem revelar
conhecimento relevante em outros domínios, e assim, podem ser muito
significantes e sua análise valiosa. 13
h) Análise de séries temporais: pertencem ao estudo de dados relacionados ao
tempo e que sofrem mudanças com este, podendo ser classificada em análise
de evolução e divergência. Análise de evolução modela tendências
evolutivas em dados, podendo ser utilizadas em tarefas de caracterização,
discriminação, classificação ou agrupamento de dados relacionados a tempo.
Análise de divergência, por outro lado, considera as diferenças entre valores
medidos e valores esperados, e tentam encontrar a causa das divergências
entre estes valores.
É comum que os usuários não tenham uma idéia clara dos tipos de padrões que
eles podem descobrir ou precisam descobrir em seus dados. Por esta razão, é importante
ter sistemas de prospecção de dados versáteis e inclusivos, que permitam a descoberta
de diferentes tipos de conhecimento em diferentes níveis de abstração, tornando a
interatividade um importante atributo em tais sistemas [Zaïane, 1999b].
2.3.3 – Aplicações de Prospecção de Dados
Prospecção de dados pode ser descrita como uma tecnologia de comércio
inteligente que utiliza várias técnicas para compreensível extração de informações úteis,
identificando tendências, padrões ou regras implícitas em vastas quantidades de dados,
tornando os indivíduos capazes de criar novas oportunidades ou valores para suas
organizações. Os exemplos seguintes mostram aplicações práticas de prospecção de
dados e o valor que ela provê para aqueles que usam esta tecnologia, tanto em
aplicações comerciais quanto científicas:
- Detecção de fraude: na indústria de serviços financeiros tem-se utilizado uma
técnica sofisticada de prospecção de dados, chamada rede neural, para a
detecção de transações potencialmente fraudulentas no uso de cartões de
crédito, a partir da análise da transação e de todos os seus elementos de
dados, baseando-se no conhecimento de casos de fraudes, levando a um
resultado de predição. Pelo motivo da predição poder estar correta ou não, é
necessário que o sistema aprenda vários padrões e características de
transações para refinar sua capacidade de predição, diminuindo assim as
transações fraudulentas.
14
- Localização de mercadorias: a incorporação de técnicas de prospecção de
dados no varejo melhora as localizações das mercadorias, reduzindo o custo
de manipulação, capacitando o varejista a identificar as características de
seus clientes, tais como gênero, número de crianças etc. e os produtos que
eles compram, o que é extremamente importante para a localização das
mercadorias onde elas provavelmente serão compradas.
- Contratos: Algumas empresas utilizam técnicas de prospecção de dados para
detectar as características de seus melhores empregados, tais como
escolaridade, tempo de experiência, habilidades, personalidade etc., para
serem utilizadas como requisitos para os próximos empregados a serem
contratados. Como o perfil é baseado apenas em dados históricos, estes
dados podem não ser indicados para caracterizar os melhores empregados no
futuro por motivo de eventuais mudanças nas condições sociais, econômicas
e ambientais das empresas.
- Análise de defeitos: O controle de qualidade é um fator crítico para qualquer
fábrica e com o uso de técnicas de prospecção de dados, os fabricantes são
capazes de identificar as características que levam a produtos defeituosos,
tais como dia da semana e hora da fabricação, componentes que estão sendo
usados e trabalhos individuais na linha de montagem, podendo-se assim
fazer mudanças no processo de fabricação para melhorar a qualidade dos
produtos fabricados.
- Engenharia Biomédica: coleções de dados em grandes escalas têm emergido
de diferentes fontes de dados, como por exemplo, das seqüências de DNA.
Tais dados da área biológica tendem a ser combinados com dados da
medicina para o entendimento da causas das doenças e melhorar a eficiência
dos tratamentos. O maior desafio de prospecção de dados em biomedicina é
a organização de dados moleculares e celulares e dados clínicos permitindo
que estes sejam integrados para a extração de conhecimento [Han et al.,
2002].
- Telecomunicações: a utilização de prospecção de dados prospera em
telecomunicações devido a disponibilização de vastas quantidades de dados 15
de alta qualidade. Um fluxo significante é o registro de chamadas usado
principalmente para fins de faturamento, mas que também habilita a
utilização de prospecção de dados para a detecção de fraudes e propagandas
[Han et al., 2002].
- Dados Geoespaciais: o alcance, cobertura e volume de conjuntos de dados
geográficos digitais têm crescido rapidamente nos últimos anos devido ao
progresso das tecnologias empregadas na coleta e processamento dos dados
desta área, tornando necessário o estudo de prospecção de dados
geoespaciais para a descoberta de novos e não esperados padrões, tendências
e relacionamentos entre estes dados [Han et al., 2002].
- Dados Climáticos e de Ecossistemas da Terra: a grande coleção de dados
climáticos provenientes de observações de satélites, observações territoriais e
modelos de ecossistemas oferecem uma oportunidade para a previsão e
prevenção de futuros problemas ecológicos através do gerenciamento da
ecologia da Terra. Devido à natureza e quantidade desses dados, técnicas de
prospecção de dados podem ser empregadas na extração automática e análise
de padrões interessantes, complementando as técnicas estatísticas existentes
[Han et al., 2002].
Existem muitas outras aplicações em que prospecção de dados é útil para prover
o conhecimento sobre os padrões ou eventos que podemos não conhecer, e como a
tecnologia de armazenamento de dados avança e os sistemas de informação continuam
coletando e processando dados, um tesouro está sendo acumulado, esperando para ser
descoberto. Os problemas onde prospecção de dados pode ser utilizada não são
limitados ao estudo de informações demográficas de usuários, pelo contrário, seu limite
de atuação vai desde perseguição de criminosos (o FBI já usou técnicas de prospecção
de dados) até análise de crédito (bancos e companhias de cartões de crédito usam
modelos baseados em prospecção de dados para ajudá-los a encontrar bons aplicadores).
Além disto, o campo médico está igualmente considerando prospecção de dados como
uma ferramenta viável para auxiliar nos diagnósticos dos pacientes [Wu, 2002].
16
Podem ser mencionados alguns exemplos onde foram utilizadas técnicas de
prospecção de dados, pois embora recente esta metodologia tem aplicações com
conhecidos sucessos, tais como:
a) Wal-Mart: a cadeia americana Wal-Mart identificou um hábito curioso entre
seus consumidores. Após cinco anos procurando eventuais relações entre o
volume de vendas e os dias da semana, o sistema de prospecção de dados
apontou que, às sextas-feiras, as vendas de cervejas cresciam na mesma
proporção que as de fraldas. Crianças bebendo cerveja? Não, uma
investigação mais detalhada revelou que, ao comprar fraldas para seus bebês,
os pais aproveitavam para abastecer o estoque de cerveja para o final de
semana [Stedman, 1997].
b) ShopKo: esta empresa concorrente da Wal-Mart para reconhecer padrões de
consumo em suas lojas. Descobriu que a venda de certos produtos era
decorrente da venda indireta de outros produtos. A ShopKo resistiu à
agressiva entrada da Wall-Mart em 90% dos mercados [Tucker, 1996].
c) Cassino Harrah's: o The Street Journal relatou que este cassino em Las
Vegas, utilizando a prospecção de dados sobre informações de seus 16
milhões de clientes, descobriu que os apostadores que gastavam entre 100 e
500 dólares em uma visita ao cassino correspondiam a apenas 30% de toda a
sua clientela, mas contribuíam com 80% das receitas. Com estratégias
agressivas de marketing, tais como o oferecimento de almoços, shows e
apostas grátis, o cassino afirma ter dobrado seu faturamento em relação ao
ano anterior [Wasserman, 2000].
d) Spring: uma das empresas líderes no mercado americano de telefonia de
longa distância, desenvolveu um método capaz de prever com 61% de
segurança se um consumidor trocaria de companhia telefônica dentro de um
período de dois meses. Com um marketing agressivo, conseguiu evitar a
deserção de 120.000 clientes e uma perda de US$ 35 milhões no faturamento
[Gurovitz, 1997].
e) Serviço Postal Americano: este serviço passou a utilizar códigos de barras
bidimensionais em suas encomendas. Além das informações operacionais 17
para transporte e entrega das mercadorias, armazenavam informações sobre
o produto enviado, o remetente e o destinatário. Através da coleta desses
dados, o serviço postal teve a possibilidade de agrupar por bairros, já que a
lei americana é rigorosa com relação à invasão de privacidade, informações e
hábitos de consumo [Doug, 1997].
f) Banco Itaú: armazenando e analisando a movimentação financeira de seus 3
milhões de correntistas nos últimos 18 meses, o Banco Itaú conseguiu
aumentar sua taxa de retorno positivo dos clientes quando recebiam malas
diretas de 2% para 30%, diminuindo substancialmente seu antigo gasto com
correio em 80% [Doug, 1997].
2.4 – Web Inteligente
A Web é uma coleção de documentos distribuídos, inter-relacionados,
estruturados, semi-estruturados e não-estruturados, contendo textos, imagens e sons
[Yao et al., 2001]. É previsto que a maior parte do conhecimento humano esteja na Web
em 10 anos [Garofalakis et al., 1999]. Entretanto, ter uma grande quantidade de
conhecimento disponível não é garantia de que os usuários encontrarão o que desejam
em tempo razoável, o que é conhecido como “sobrecarga de informações”. Assim, fica
evidente a necessidade de mecanismos que auxiliem os usuários nos processos de busca
de conhecimento, sendo que estes mecanismos devem ser inteligentes, pois não há
pessoas representando as organizações na Web, somente computadores [Spiliopoulou &
Pohle, 2001]. Focalizando este objetivo, surgiu a área de Web Inteligente, que é um
novo campo de pesquisa que explora a Inteligência Artificial (IA) e a Tecnologia de
Informação avançada para o desenvolvimento de sistemas inteligentes para a Web
[Zhong et al., 2000]. Tais sistemas devem realizar funções relacionadas à inteligência
humana (raciocínio, aprendizado e auto-aprimoramento), podendo a Web Inteligente ser
vista como uma aplicação de IA à Web [Yao et al., 2001].
Nesta seção, serão apresentadas algumas técnicas de IA a serem aplicadas na
Web Inteligente, focalizando-se nos processos relacionados à descoberta de
conhecimento. Assim, dentre as técnicas de IA que, segundo [Loh & Garin, 2001]
visam este objetivo, serão explicitadas a Web Semântica, Prospecção de Dados da Web,
Interfaces Inteligentes ou Cooperativas e Agentes Inteligentes. Além disto, serão
18
discutidas três aplicações da Web Inteligente: personalização, recomendação e busca de
informação.
2.4.1 – Técnicas de IA para a Web Inteligente
2.4.1.1 – Web Semântica
A migração da comunicação e comércio para a Web está alterando o fluxo de
informação no mundo [Kleinberg & Lawrence, 2001], porém o crescimento de
informações disponíveis tem tornado o acesso a informações úteis e necessárias cada
vez mais difícil. As máquinas de busca na Web geralmente tratam as requisições de
forma isolada, fazendo com que uma dada consulta proporcione resultados idênticos,
independentes do usuário ou do contexto em que a requisição foi realizada.
O acesso dirigido à busca de conhecimento tem um papel de grande importância
na gestão de conhecimento e incentiva o direcionamento para a Web Semântica [Kietz
et al., 2000], [Lawrence, 2000], que em oposição a Web que conhecemos hoje,
habilitará as máquinas a estruturar, navegar, integrar e processar informação de uma
maneira significante, focalizando na recuperação de conhecimento de forma mais
concisa [Studer et al., 2000] a partir de métodos que além de facilitar a formulação de
consultas também exploram o domínio semântico da mesma, permitindo aos usuários a
recuperação semântica de dados da Web [Chiang et al., 2001].
Assim, a Web semântica provê estruturação e acesso inteligente a informações
distribuídas e heterogêneas, permitindo que produtos de software (destinados a
processamento semântico) sejam intermediários entre as necessidades dos usuários e as
fontes de informações disponíveis [Fensel, 2000].
Ontologias
A Web semântica visa criar uma Web em que tanto os humanos quanto
máquinas possam tratar as informações nela existentes. Isto com certeza requer que as
informações sejam representadas de tal forma que seu significado (ou “semântica”) seja
processável por máquinas. Se pessoas e computadores - e computadores e computadores
– precisam comunicar, compartilhar e reusar conhecimento de igual maneira,
precisamos de algum vocabulário em comum e especificações mais exatas para
descrever o que queremos dizer. Aqui é onde a ontologia entra na ciência dos dias
modernos.
19
A chave para o processamento automático de dados na Web semântica é provida
pelas estruturas conceituais que definem uma ontologia [Harmelen, 2000], [Maedche &
Staab, 2001], e por isto o conceito “ontologia” tem ganhado grande popularidade e
importância na comunidade de gestão de conhecimento.
Entretanto, o significado de ontologia tende a permanecer um pouco vago, pois o
termo é usado em diversas formas diferentes [Guarino & Giareta, 1995]. Mas a
definição que, em nossa opinião, melhor caracteriza a essência de uma ontologia é:
“Uma ontologia é uma representação formal e explícita de uma conceitualização
compartilhada” [Gruber, 1993]. Neste contexto, uma “conceitualização” refere-se a um
modelo abstrato de algum fenômeno no mundo (domínio), que identifica os conceitos
relevantes deste fenômeno, referindo-se a um modelo abstrato de como as pessoas
pensam sobre as coisas no mundo, geralmente restringindo-se a um tema de uma área
particular. “Explícito” significa que os tipos de conceitos usados e as restrições sobre o
seu uso são explicitamente definidos, especificando-se os termos e definições dos
conceitos e relacionamentos do modelo abstrato. “Formal” se refere ao fato da
ontologia ser processável por máquinas. “Compartilhado” se refere à noção de que uma
ontologia captura conhecimento consensual, isto é, ela não é restrita a um indivíduo,
mas aceita por um grupo [Benjamins & Martin, 2000], [Fensel et al., 2001], [Studer et
al., 2000].
A razão pela qual as ontologias estão se tornando tão populares se deve em
grande parte ao que elas prometem: um comum e compartilhado entendimento de um
domínio que pode ser comunicado entre pessoas e sistemas computacionais
heterogêneos e distribuídos [Fensel et al., 2001].
Uma maneira de formalmente representar conhecimento é baseada em uma
conceitualização, e por isto, basicamente o papel de uma ontologia no processo de
gestão de conhecimento é facilitar a construção de um modelo de um domínio,
fornecendo um vocabulário de termos e relações com os quais se pode modelar este
domínio. Ontologias servem como esquemas de metadados, provendo um vocabulário
controlado de conceitos, cada qual explicitamente definido e semanticamente
processável por máquina. Na prática, ontologias abstraem a essência de um conceito e
ajudam a catalogar e distinguir vários tipos de objetos e seus relacionamentos.
Desta forma, a Web semântica depende essencialmente de ontologias para
estruturar dados, objetivando ajudar pessoas e máquinas a comunicar-se concisamente,
suportando intercâmbio semântico e não somente sintático, [Maedche & Staab, 2001],
compreendendo o seu vocabulário e sua semântica, podendo ser reusadas e
compartilhadas [Chiang et al., 2001], sendo consideradas como a memória
organizacional das empresas (comunidades), em que todas as informações relevantes e 20
conhecimento estão disponíveis [Benjamins & Martin, 2000], abrindo o caminho para
se deslocar da visão de gestão de conhecimento orientada a documentos para uma visão
orientada a conteúdo, onde os itens do conhecimento são interligados, combinados e
então, usados [Staab et al., 2001].
Manutenção de Ontologias
É amplamente reconhecido que a construção de um modelo de domínio, ou
ontologia, é um importante passo no desenvolvimento de sistemas baseados em
conhecimento. Encontramos um crescente número de métodos utilizados no processo de
desenvolvimento de ontologias, tais como Methontology e IDEF5, além das abordagens
baseadas nas experiências de desenvolvimento da ontologia Enterprise e da ontologia
adotada no projeto TOVE (Toronto Virtual Enterprise), não havendo, no entanto, um
método padrão que especificamente trate esta questão. Entretanto, todas as abordagens
incluem no ciclo de desenvolvimento de uma ontologia, a necessidade de técnicas a
serem utilizadas em sua manutenção [Jones et al., 1998].
Ontologias têm que ser mantidas freqüentemente, pois suas especificações
precisam ser alteradas para refletir as constantes mudanças do mundo real. A
manutenção de ontologias é principalmente um processo organizacional, devendo haver
regras restritas para os processos de atualização, deleção e inserção na ontologia, sendo
que o “feedback” dos usuários proporciona a mais valiosa informação para a
identificação das mudanças necessárias [Staab et al., 2001].
A manutenção de ontologias permanece semi-automática, devido à
complexidade envolvida neste processo, com os engenheiros de ontologia geralmente
utilizando ferramentas de suporte que apóiam sua intervenção neste processo, baseando-
se na estrutura da ontologia e em dados de entrada (geralmente advindos de processos
adicionais) que propõem novos conhecimentos sobre conceitos de interesse, relações e
entradas léxicas, ou conexões entre essas entidades, sugerindo adições, deleções ou
alterações a serem feitas nas ontologias [Maedche & Staab, 2001].
2.4.1.2 – Prospecção de Dados da Web
Com o explosivo crescimento de fontes de informações disponíveis na Web,
torna-se necessário que os usuários utilizem ferramentas automáticas para encontrar os
recursos de informação necessários, localizar e analisar seus padrões de uso. Esses
fatores levam à necessidade de criação de sistemas inteligentes do lado do servidor e do
cliente que possam efetivamente extrair o conhecimento [Cooley et al., 1997]. 21
Os repositórios de dados da Web podem ser classificados, segundo [Srivastava et
al., 2000], da seguinte maneira:
a) bancos de dados da organização: armazenamento das transações on-line;
b) servidores Web: arquivos de log de acesso dos servidores da Web;
c) clientes Web: cookies, plug-ins, agentes remotos (Javascripts e Java applets)
e componentes de software instalados no usuário (modificando o código do
browser, por exemplo);
d) servidores proxy: principalmente para analisar páginas armazenadas em
cache.
Os dados contidos nestes repositórios podem estar relacionados a [Schafer,
2001], [Kohavi & Becher, 2001]:
a) atributos demográficos dos usuários (sexo, idade, localização etc.) que
podem ser por eles fornecidos, descobertos no mundo real (ex.: a partir de
endereço de entrega de produtos comprados on-line) ou descobertos pela
rede (ex.: domínio de origem);
b) navegação explícita: páginas requisitadas ou visitadas, links seguidos,
escolhas de atributos ou parâmetros fornecidos como entrada, tempo gasto
etc.;
c) navegação implícita: itens escolhidos e quais itens estão sendo vistos;
d) palavras-chave usadas em buscas;
e) histórico de relacionamentos do usuário com o site: compras feitas, páginas
visitadas, documentos ou elementos baixados por download, revisitas etc.
f) feedback do usuário: preferências, opiniões e comentários;
g) conteúdo visitado;
h) descartes do usuário: produtos colocados no cesto e tirados, páginas não
carregadas totalmente etc.
A prospecção de dados da Web se refere à extração e identificação de padrões na
Web e é sugerido aplicar as técnicas de prospecção de dados para os dados da Web,
podendo-se fazer análises estatísticas sobre páginas visitadas (pageviews), tempo gasto
entre páginas, páginas mais freqüentemente vistas, associações entre páginas
freqüentemente vistas em uma mesma visita e que não estão relacionadas por
hyperlinks, padrões seqüenciais (eventos que precedem outros), padrões transversos
22
(páginas não diretamente ligadas por hyperlinks, mas relacionadas por meio de outras),
dentre outros padrões [Srivastava et al., 2000].
Embora a prospecção de dados da Web seja profundamente baseada em
prospecção de dados em geral, as duas não são equivalentes, pois a característica não-
estruturada dos dados da Web traz uma maior complexidade para a prospecção de dados
da Web [Wang, 2000].
[Etzioni, 1996] e [Kosala & Blockeel, 2000] sugerem uma forma similar às
etapas da prospecção de dados genérica para a decomposição do processo de prospecção
de dados da Web:
a) Descoberta do Recurso: a tarefa de recuperar a informação pretendida da
Web.
b) Extração da Informação: automaticamente selecionar e pré-processar
informações específicas dos recursos recuperados da Web.
c) Generalização: automaticamente descobrir padrões genéricos em sites
individuais e entre múltiplos sites.
d) Análise: analisar o padrão descoberto.
A prospecção de dados da Web, ou Web Mining, pode ser categorizada da
seguinte forma [Becerra-Fernandez, 2001], [Wang, 2000], [Zaïane, 1999a], [Zaïane,
2000] :
- Prospecção de Conteúdo da Web (Web Content Mining): analisa o conteúdo
existente nas páginas da Web, focalizando a descoberta/recuperação de
informações úteis a partir de documentos/dados/conteúdos, estando aí
incluídas a prospecção de dados textuais da Web, a prospecção baseada em
indexação de conceitos e as tecnologias baseadas em agentes, sendo um tipo
de prospecção voltada principalmente para os usuários finais da Web;
- Prospecção de Estrutura da Web (Web Structure Mining): examina como
documentos da Web estão estruturados, enfatizando a descoberta de como
modelar as estruturas de links, sendo voltada principalmente para os
desenvolvedores e projetistas de sites e páginas Web; e
- Prospecção de Uso da Web (Web Usage Mining): objetiva principalmente
descrever técnicas para a descoberta de padrões de uso a partir da
identificação das navegações dos usuários nas páginas da Web, para posterior 23
previsão do comportamento futuro destes usuários, sendo destinada
primordialmente para os desenvolvedores e projetistas.
As categorias acima podem ser visualizadas na Figura 2.3, [Zaïane, 1999a].
Prospecção de
Conteúdo de
Páginas da Web
Prospecção de
Resultados de
Busca na Web
Prospecção de
Padrões de Acesso
Genéricos
Prospecção de Uso
Customizado
Prospecção de
Conteúdo da Web Prospecção de
Estrutura da Web Prospecção de Uso
da Web
Prospecção de
Dados da Web
Figura 2.3: Categorias de Prospecção de Dados da Web.
A divisão da prospecção de dados da Web nas três categorias citadas é baseada
no tipo de dado que será analisado [Wang, 2000]. Assim, enquanto a prospecção de
estrutura e conteúdo utiliza dados reais ou primários da Web, a prospecção de uso tenta
dar sentido aos dados secundários derivados das interações dos usuários com a Web
[Kosala & Blockeel, 2000].
[Cooley et al., 1997] classifica a prospecção de uso da Web de forma mais
simplificada, distinguindo apenas a prospecção de conteúdo e a prospecção de uso,
estando nesta última englobada a prospecção de estrutura da Web, já que os métodos de
preparação de dados, análise e busca de conhecimento sobre o uso das páginas Web
salientam a necessidade de se ter informações estruturais sobre os sites.
Prospecção de Conteúdo da Web
É difícil localizar informações relevantes sobre determinado assunto somente
através dos links dos documentos hipertexto na Web. Para providenciar uma busca de
informação mais eficiente foram criados os indexadores de documentos, conhecidos
24
como máquinas de busca, como AltaVista (www.altavista.digital.com), Google
(www.google.com), Excite (www.excite.com), Infoseek (www.infoseek.com) e Lycos
(www.lycos.com).
Estes tipos de sites podem funcionar basicamente de duas maneiras:
- Coleta de dados e indexação: agentes, conhecidos como robôs, percorrem a
Web, coletam, armazenam e indexam as informações.
- Meta-índices: utilização dos próprios indexadores de documentos para a
realização da busca.
Estes sites, apesar de serem muito utilizados pelos usuários da Web, apresentam
problemas relacionados a questões de relevância e abrangência.
Outros recursos que visam facilitar a pesquisa são os diretórios organizados com
a intervenção humana. Apesar de eficiente, esse tipo de site é difícil de se manter
atualizado devido ao grande dinamismo da Web. Outro problema é que a visão do
categorizador da informação pode ser diferente da do usuário. Exemplos de sites deste
tipo são The Mining Company (home.miningco.com) e Yahoo (www.yahoo.com).
O ponto central da ineficiência da busca por informação está no fato da Web não
ter sido planejada e projetada para armazenar informações de forma organizada e
ordenada, o que faz com que a descoberta automatizada de conhecimento, a organização
e a administração das informações tornem-se atividades de difícil execução.
As ferramentas de busca e indexação tradicionais provêem um pouco de
conforto aos usuários, porém elas geralmente não provêem informação estruturada,
categorização, filtragem e interpretação de documentos.
Já as ferramentas para a prospecção de conteúdo da Web são capazes de efetuar
recuperação inteligente de informações ou de fornecer um alto nível de organização
para os dados semi-estruturados disponíveis na Web, através da extensão de técnicas de
prospecção de dados, trabalhando com dois tipos de enfoques:
Enfoque Baseado em Agentes: ferramentas que utilizam agentes inteligentes para
auxiliar o usuário na busca de informações de interesse possibilitando que o trabalho de
recuperação seja mais produtivo e eficiente. Tais sistemas podem ser classificados em
uma destas três categorias [Cooley et al., 1997]:
a) Agentes Inteligentes de Pesquisa: agentes desenvolvidos para pesquisar
por informação importante, utilizando características do domínio e o 25
perfil do usuário para organizar e interpretar as informações descobertas.
[Spertus, 1998] desenvolveu um agente que permite a interpretação de
documentos da Web codificados em tabelas em um banco de dados
relacional, sendo baseado no Squeal, um sistema desenvolvido para
permitir que sejam feitas consultas SQL à Web. Já o Shopbot [Doorenbos
et al., 1997] é um agente que aprende a partir de fontes de dados de
estrutura previamente desconhecida, oferecendo para os usuários os
preços mais baratos de determinados produtos.
b) Agentes de Filtro/Classificação de Informações: agentes Web que
utilizam técnicas de recuperação de informação e características dos
hiperdocumentos, como, por exemplo, a estrutura incorporada na
estrutura de links, para, automaticamente, recuperar, filtrar e classificar
as informações disponíveis na Web, criando grupos de documentos com
características semelhantes. Os Web crawlers, robôs ou spiders
[Kobayashi & Takeda, 2000] são agentes especializados que podem ser
utilizados para a extração das estruturas ou topologias dos sites Web.
c) Agentes de Personalização da Web: agentes Web que aprendem as
preferências dos usuários a partir da experiência de interação com esses e
descobrem fontes de informações baseadas nessas preferências e nas de
indivíduos com interesses similares. Tais ferramentas podem, ainda,
sugerir informações descobertas, de forma automática, para o usuário.
Letizia [Lieberman, 1995] foi um dos primeiros agentes desse tipo,
auxiliando a navegação a partir dos hábitos do próprio usuário, sem o uso
de palavras-chave ou rating. Já WebWatcher [Joachims et al., 1997],
[Armstrong et al., 1995] aprende a partir dos padrões de navegação de
toda a sua comunidade de usuários, fazendo-lhes recomendações de
páginas consideradas mais interessantes.
Enfoque em Banco de Dados: a abordagem em banco de dados para a
prospecção na Web faz uso de técnicas para a organização dos dados semi-estruturados
da Web de forma mais estruturada e com a utilização de técnicas de consulta e
prospecção de dados em bancos de dados para análise. Esses trabalhos podem ser
agrupados nas seguintes categorias: 26
a) Bancos de Dados Multiníveis: ferramentas que organizam as
informações em diversas camadas, ficando no nível mais baixo os dados
semiestruturados armazenados em diversos repositórios Web; no nível
mais alto, metadados ou generalizações extraídas dos níveis inferiores, os
quais são organizados em coleções estruturadas, isto é, bancos de dados
relacionais ou orientados a objeto. Sobre a utilização destas ferramentas
pode-se citar o trabalho de [Merialdo et al., 1997].
b) Sistemas de Consulta Web: ferramentas que utilizam linguagens de
consulta a bancos de dados, como SQL, informações estruturais sobre os
documentos da Web e, até mesmo, processamento de linguagem natural
para a busca de informações. Um exemplo é W3QS [Konopnicki &
Shmueli, 1996] que é uma linguagem declarativa de consulta, estilo SQL,
que pode ser utilizada em tais sistemas.
[Srivastava et al., 2000] sugerem utilizar técnicas de prospecção tais como
classificação ou agrupamento de páginas Web ou partes destas (textos, imagens),
identificando o assunto ou tipo. Isto permitiria encontrar páginas ou documentos de
conteúdo relacionado para apoiar comunidades virtuais, sendo também possível realizar
agrupamentos de usuários com comportamento similar, para entender padrões na
comunidade virtual.
Prospecção de Estrutura da Web
A maioria das ferramentas de recuperação de informação da Web usa somente a
informação textual, ignorando as informações de links que podem ser muito valiosas. O
objetivo da prospecção de estrutura da Web é gerar sumário estrutural sobre os sites e
páginas da Web. Tecnicamente, a prospecção de conteúdo da Web focaliza
principalmente as estrutura dos documentos, enquanto a prospecção de estrutura da Web
tenta descobrir a estrutura de ligação dos hyperlinks entre documentos. Baseada na
topologia dos hyperlinks, a prospecção de estrutura da Web categoriza as páginas e gera
informações, tais como a similaridade e relacionamentos entre diferentes sites.
Muitas aplicações utilizam em conjunto técnicas de prospecção de conteúdo e de
estrutura da Web. Pode-se citar o sistema Expert Seeker [Becerra-Fernandez, 2001],
desenvolvido pelo Laboratório de Gestão de Conhecimento da Florida International
27
University com o propósito de ser disponibilizado na intranet da NASA para possibilitar
a descoberta de empregados com determinadas habilidades, baseando-se em dados
contidos nas páginas Web do domínio, permitindo uma rápida identificação de
habilidades potenciais dos empregados, especialmente úteis para a organização e
formação de equipes de trabalho.
A prospecção de estrutura da Web pode ser direcionada para a descoberta da
estrutura dos próprios documentos da Web. Este tipo de prospecção de dados pode ser
usado para descobrir a estrutura das páginas, o que pode ser útil para propósitos de
navegação e tornar possível a comparação/integração de esquemas de páginas da Web.
Assim, a prospecção de estrutura da Web facilita a introdução de técnicas de bancos de
dados para informações de acesso a páginas Web por prover um esquema referencial.
No geral, se uma página Web é diretamente ligada a outra, ou as páginas são
vizinhas, pode-se descobrir os relacionamentos entre estas páginas. Tais
relacionamentos podem ser de vários tipos, tais como relacionamentos por sinônimos ou
ontologias, conteúdos similares, utilização de mesmo servidor, etc.
Uma outra tarefa da prospecção de estrutura da Web é descobrir a natureza da
hierarquia ou rede de hyperlinks nos sites da Web de um domínio particular, o que pode
auxiliar na generalização do fluxo de informação nestes sites, que representam o
domínio, tornando o processamento de consultas mais fácil e eficiente [Wang, 2000].
Alguns algoritmos têm sido propostos para modelar a topologia da Web, tais
como HITS [Kleinberg, 1998], PageRank [Brian & Page, 1998] e aperfeiçoamentos de
HITS pela adição de informações de conteúdo para a estrutura de links [Chakrabarti et
al., 1999] e pela utilização de filtragem [Bharat & Henzinger, 1998]. Esses modelos são
principalmente aplicáveis como um método para calcular a qualidade e relevância de
cada página Web. Alguns exemplos são o sistema Clever [Bharat & Henzinger, 1998] e
Google [Brian & Page, 1998]. Algumas outras aplicações dos modelos incluem
categorização de páginas da Web [Chakrabarti et al., 1998] e descoberta de pequenas
comunidades na Web [Kumar et al., 1999].
28
Prospecção de Uso da Web
Prospecção de uso da Web, ou Web Usage Mining, é o processo de aplicação de
técnicas de prospecção de dados para descobrir padrões de uso dos dados da Web
[Srivastava et al., 2000] tendo como sua principal utilização a análise de como os
usuários estão acessando um site, sendo assim essencial para a determinação de
estratégias de mercado e otimização da estrutura lógica de sites da Web [Cooley et al.,
1997].
Atividades de comércio eletrônico estão experimentando uma revolução
significante. A habilidade para rastrear comportamentos de navegação dos usuários e os
cliques de seus mouses individuais, tem tornado os vendedores e os usuários finais mais
íntimos do que nunca, possibilitando que um vendedor personalize suas mensagens de
produtos para usuários individuais em alta escala, fenômeno que está sendo referenciado
como customização em massa. Este é apenas um dos cenários em que são possíveis
aplicações de prospecção de uso da Web.
As organizações coletam grandes volumes de dados de suas operações diárias,
gerados automaticamente e coletados em logs de acesso nos servidores da Web.
Mecanismos para análise destes dados podem determinar o número de acessos feitos ao
servidor e a arquivos individuais, o tempo das visitas, quais URLs foram visitadas etc.
[Srivastava et al., 2000], e para esta tarefa podem ser utilizados alguns algoritmos de
prospecção de dados tais como aqueles destinados à geração de regras de associação,
de padrões seqüenciais e agrupamento [Cooley et al., 1997].
Como qualquer outro processo de descoberta de conhecimento, a prospecção de
uso da Web envolve questões de pré-processamento de dados antes de se aplicar
algoritmos de prospecção, tais como: desenvolver um modelo de acesso ao arquivo de
log, desenvolver técnicas de limpeza/filtragem dos dados para eliminar itens
irrelevantes, agrupar acessos individuais (transações), integrar várias fontes de dados e
especializar algoritmos genéricos de prospecção de dados para eficientemente aplicação
nos dados de natureza específica que compõem os arquivos de log. Além do
desenvolvimento de técnicas para a aplicação de prospecção de uso da Web é necessário
desenvolver técnicas e ferramentas para a análise dos padrões descobertos, que podem
incluir estatísticas, gráficos etc. [Cooley et al., 1997].
Assim, a prospecção de uso da Web pode ser dividida em pelo menos três etapas
distintas, cada uma delas com suas próprias características, procedimentos, métodos,
entradas e saídas: pré-processamento, descoberta de padrões de uso, análise e
visualização dos resultados [Cooley et al., 1997], [Cooley, 2000]. 29
1) Pré-processamento ou preparação de dados
Nesta etapa são realizadas a leitura, filtragem, limpeza e integração das
diferentes fontes de dados de utilização Web, além de poder incluir a
identificação dos usuários e de suas sessões e transações, em casos onde as
fontes de dados não contêm uma correta ou precisa identificação. Considera-
se uma sessão de um usuário um conjunto de páginas acessadas por ele em
uma determinada visita ao site, e transação como um agrupamento
semanticamente significativo de páginas.
Idealmente, a prospecção de padrões deveria ser feita sobre um conjunto
de sessões ou transações de usuários contendo informações precisas e
detalhadas sobre quem acessou o site, que páginas foram visitadas e em que
ordem, e por quanto tempo cada página foi vista [Cooley et al., 1999].
Porém, as principais fontes de dados sobre o uso de um site são os
próprios logs gerados pelos servidores Web, os quais possuem sérias
deficiências em termos de detalhamento e reconhecimento dos usuários e
sessões, sendo que os dados contidos em um log de servidor Web não
representam com total confiabilidade as sessões dos usuários devido a uma
série de características: a presença de grande número de itens irrelevantes (da
mesma forma que nas outras fontes de dados), a ausência de identificação
única dos usuários, sessões e transações, bem como a inexistência dos
registros das visitas a inúmeras páginas, devido ao uso de cache e servidores
proxies.
A etapa de pré-processamento pode incluir as seguintes atividades:
- Limpeza dos Dados
As técnicas de limpeza ou filtragem das fontes de dados são
fundamentais pelo fato delas conterem muitas informações
irrelevantes, tais como acessos a arquivos de imagens, som, vídeo,
animações, etc. Uma entrada de log de utilização contém,
normalmente, o registro do percurso de uma página de origem até uma
página de destino, incluindo o IP da máquina cliente que originou a
chamada, o tipo de acesso (POST ou GET) realizado, além de outros
dados, a depender do padrão utilizado pelo servidor Web.
No protocolo HTTP, um cliente faz ao servidor uma requisição
para cada arquivo necessário à visualização de uma determinada 30
página. Assim, um acesso a uma simples página Web provoca a
gravação de várias entradas de log no servidor, para cada uma das
imagens, scripts ou outros arquivos carregados juntamente com a
página. Em geral, somente as entradas de log associadas aos acessos às
páginas HTML serão de interesse na prospecção de uso, pois os
demais arquivos, especialmente imagens, são baixados
automaticamente à revelia do usuário, e devem ser removidas. A
eliminação de dados irrelevantes pode ser feita de forma razoável
conferindo-se o sufixo do nome de arquivos em uma URL. Por
exemplo, todas as entradas do log com sufixos de nomes de arquivos
como: gif, jpeg, jpg etc., podem ser removidas.
- Identificação dos usuários
Após a limpeza do log, a próxima atividade a se realizar é a
identificação de usuários, caso as fontes de dados em questão não
contenham em si mesmas informações de identificação.
Os logs de servidores Web são bastante incompletos em relação
a identificação do usuário, podendo-se citar várias dificuldades,
causadas principalmente pelo uso de cache e a presença cada vez
maior de servidores proxy, que podem distorcer os dados dos logs
[Pirolli et al., 1996], [Pitkow, 1997].
O cache faz com que a mesma página possa ser acessada várias
vezes pelo usuário, sem que o servidor Web registre no log tais
acessos, sendo um método para tornar mais eficiente o acesso a
páginas muito visitadas pelo usuário e que não sofram muitas
modificações. A página fica armazenada no disco local e, com isso,
nas próximas vezes em que for acessada, não será feita uma nova
requisição ao servidor Web. O uso de servidores de cache em muitos
provedores de acesso é ainda mais problemático, pois as páginas de
maior utilização de todos os usuários do provedor serão armazenadas
para uso futuro. Com isso, mesmo que um usuário nunca tenha
acessado uma determinada página, ao fazê-lo pela primeira vez não
será gerada uma entrada no log do servidor Web onde ela se localiza,
caso a mesma já tenha sido armazenada no servidor de cache do
provedor por ter sido muito acessada por outros usuários. 31
Os servidores proxy também possuem problemas associados
com a identificação de usuários, pois o mesmo número IP em diversas
entradas de log pode estar associado a diferentes máquinas clientes. O
servidor proxy é uma maneira eficiente e segura que muitas
organizações encontram para compartilhar o uso de um número IP por
diversas máquinas da sua intranet. Assim, para os computadores da
rede externa, todas aquelas máquinas serão vistas como uma só, já que
utilizam o mesmo número.
Métodos atuais tentam superar os problemas causados pelo uso
de cache, forçando na página Web, o “by-pass” do cache: obriga-se o
navegador a recarregar a página sempre que ela for visitada, num
processo conhecido como “cache busting”. A identificação do usuário
pode ainda ser facilitada com o uso de cookies, assim as entradas dos
logs terão as informações sobre quais cookies foram utilizados nos
acessos. Outra possibilidade é o registro explícito dos dados pessoais
dos usuários sempre que iniciar a navegação em um determinado site.
Assim, os logs registrariam também um identificador do usuário,
sendo uma solução colaborativa.
Essas soluções são questionadas em [Pitkow, 1997] por
possuírem limitações. Os cookies, por exemplo, podem ser removidos
pelo usuário, ou podem ser desabilitados na configuração do
navegador. O “by-pass” de cache também pode ser desabilitado e,
além disso, é um mecanismo que termina por tirar a principal
vantagem do uso do cache, que é a maior velocidade de navegação.
Finalmente, o registro explícito, apesar das vantagens que traz pelas
informações demográficas adicionais que oferece, levanta questões de
privacidade que podem fazer com que muitos usuários desistam de
navegar num site ou mesmo forneçam informações incorretas sobre si
mesmos.
Com todas essas limitações, deve-se apelar, na maioria das
vezes, para heurísticas que permitam identificar se uma requisição de
página gravada no log veio do mesmo usuário. Pode-se usar
algoritmos ou estratégias que permitam testar diferentes combinações
de números IP, nomes de máquina e informações temporais para se
identificar o usuário [Pitkow, 1997]. 32
- Identificação das sessões
O processo de identificação das sessões é semelhante ao de
identificação dos usuários. Considera-se a sessão como uma passagem
completa de um usuário por um site, desde a página por onde ele
iniciou a passagem até a última página acessada.
Para a identificação de sessões individuais de cada usuário pode-
se adotar o método mais simples de utilizar-se um timeout de controle:
sempre que o tempo entre dois acessos consecutivos para um
determinado usuário for maior do que este timeout, assume-se que ele
iniciou uma nova sessão.
Em [Spiliopoulou & Faulstich, 1998], [Spiliopoulou et al., 1999]
são adotados dois critérios complementares para identificação de
sessões: além de considerar o timeout entre dois acessos consecutivos,
como descrito acima, assume-se também que uma nova sessão é
iniciada quando a duração total de uma seqüência de acessos exceder
um determinado limiar.
Um problema adicional na identificação de sessões é a descoberta
dos acessos que não foram registrados nos logs, devido a dois
mecanismos que já causaram problemas anteriormente na identificação
de usuários: o uso de cache e a presença de servidores proxy [Cooley
et al., 1999]. Ainda que se possa aqui utilizar soluções semelhantes, tal
como a supressão do cache, pode-se também adotar um algoritmo de
completar caminhos para tentar suprir essas lacunas.
Ao final do processo de identificação de sessões, será gerado um
arquivo contendo todas as sessões dos usuários, o qual servirá como
entrada para a fase de descoberta de padrões, ou para a etapa ainda
preparatória de identificação de transações. Alternativamente, os dados
sobre as sessões descobertas podem ser armazenados diretamente em
um SGBD (Sistema Gerenciador de Banco de Dados).
33
- Identificação de transações
Uma transação difere-se da sessão por ser um agrupamento
semanticamente significativo de referências de páginas, podendo
incluir desde apenas uma até todas as páginas acessadas em uma
sessão, o que dependerá dos critérios usados para identificá-la [Cooley
et al., 1999].
O processo de identificação de transações envolve tanto a
divisão de transações em outras menores quanto o agrupamento de
transações pequenas em outras maiores, numa seqüência de passos que
conduza aos tipos de transações apropriados para o algoritmo de
prospecção que será utilizado na próxima etapa.
2) Descoberta dos padrões de utilização
É nesta etapa que são efetivamente aplicados os métodos e algoritmos de
prospecção de dados em busca de padrões úteis e significativos. Após a
identificação das sessões ou transações, há vários tipos possíveis de
prospecção a realizar nos dados, tais como: simples análises estatísticas,
análises dos caminhos percorridos, descoberta de regras de associação,
padrões seqüenciais, agrupamento e classificação, sempre utilizando as
técnicas de prospecção de dados já estabelecidas, modificando-as para o fim
pretendido, ou, eventualmente, desenvolvendo-se novos métodos específicos
para a prospecção de uso da Web.
a) Análise Estatística
Procura identificar simplesmente dados de caráter geral, tais como
número de hits por página, as páginas acessadas mais
freqüentemente, as páginas mais usadas como ponto de partida ou de
saída do site etc., sendo o tipo de padrão mais difundido nas
ferramentas de prospecção de uso disponíveis no mercado.
b) Análises de Caminhos
Diversos tipos diferentes de grafos podem ser formados quando se
executa uma análise de caminho, desde que sejam relacionados ao
caminho percorrido pelo usuário durante a navegação [Pirolli et al.,
1996]. A partir de tais grafos pode-se tentar determinar diversos tipos 34
de padrões, tais como a seqüência de páginas mais visitadas até se
encontrar uma determinada página, a página inicial utilizada pela
maioria dos usuários para se encontrar uma determinada página, os
caminhos mais percorridos etc.
c) Regras de Associação
A descoberta de regras de associação é utilizada em bancos de
dados de transações onde cada transação é um conjunto de itens ou
atributos. O problema é descobrir todas as associações e correlações
entre dados onde a presença de um item no conjunto de dados de
transações implica na presença de outros itens. No contexto da Web,
cada transação pode ser composta de um conjunto de URLs que o
cliente acessou em uma visita ao servidor. Com a utilização de regras
de associação pode-se chegar a correlações que indiquem, por
exemplo, a porcentagem em que duas ou mais páginas foram
acessadas conjuntamente pelos usuários em uma visita ao site.
Para diminuir o impacto do tamanho dos bancos de dados,
costuma-se utilizar medidas de confiança e suporte dos itens,
baseadas no número de ocorrências das transações dentro dos logs.
Confiança é o percentual entre o número de transações que contêm
todos os itens de uma regra e o número de transações que contêm os
antecedentes da regra. Já suporte é o percentual de transações que
contém determinado padrão.
As regras de associação descobertas podem ser de grande
utilidade para o comércio eletrônico, como também para servir de
apoio à organização do próprio servidor.
d) Padrões Seqüenciais
Padrões seqüenciais são aqueles baseados nas seqüências
ordenadas das transações ocorridas, em relação ao tempo, por cada
um dos usuários de um servidor. Na Web, os padrões seqüenciais
encontrados podem, por exemplo, mostrar que um certo percentual de
usuários que acessaram determinada página num servidor também
fizeram uma compra on-line em uma outra página no intervalo de
uma semana. Outro tipo de padrão seqüencial associado ao tempo é 35
aquele em que se determina qual o intervalo em que determinadas
páginas foram mais acessadas, ou procura as características em
comum dos clientes que visitaram estas páginas em um intervalo
específico.
e) Classificação e Agrupamento
Regras de classificação na Web permitem desenvolver perfis de
usuários que tenham acessado o servidor, através de características ou
atributos em comum, como informações demográficas destes
usuários ou seus padrões de acesso, facilitando a designação destes
usuários em agrupamentos. Por exemplo, as regras de classificação
da Web, aplicadas a arquivos de log, podem levar à descoberta de
relações entre as páginas mais acessadas e uma característica
demográfica do usuário.
3) Análise e visualização dos padrões
Nesta etapa são disponibilizados e identificados os principais padrões
encontrados, a partir das preferências e definições dos usuários. A descoberta
de padrões de uso da Web não seria muito útil sem que houvesse mecanismos
e ferramentas para auxiliar o analista a entender os padrões descobertos.
Conseqüentemente, além do desenvolvimento de técnicas para a prospecção
de dados visando a obtenção de padrões, há também a necessidade de se
desenvolver técnicas e ferramentas que possibilitem uma análise dos padrões
descobertos, tais como programas estatísticos, gráficos de visualização e
grades de consultas.
As análises serão feitas através da comparação do conhecimento
descoberto sobre a utilização do site com a perspectiva que os seus projetistas
possuem sobre como ele deveria ser utilizado.
[Kato et al., 2000] apresentam uma ferramenta voltada especificamente
para auxiliar o projetista na análise dos padrões de utilização. Para avaliar as
expectativas do projetista ao projetar o site, a ferramenta analisa a relevância
conceitual entre as páginas e a conectividade dos seus links. Por outro lado,
medindo a ocorrência conjunta de acessos entre diferentes páginas, ela avalia
os padrões de uso dos visitantes. Comparando esses dois aspectos, a
ferramenta mostra ao administrador do site quais são os pontos falhos no seu 36
projeto, apontando as páginas que não estão sendo efetivamente úteis, ou seja,
não apresentando correlação suficiente entre a relevância conceitual e a co-
ocorrência de acessos. A ferramenta disponibiliza de maneira gráfica os
resultados das análises, através de um sistema de coordenadas polares que
torna fácil a comparação das trilhas seguidas pelos usuários com os problemas
detectados, dando pistas bastante úteis de como o site pode ser reestruturado.
Outra área de grande influência na análise dos padrões encontrados é a de
data warehousing juntamente com técnicas de OLAP [Zaïane et al., 1998], já
que os dados de utilização da Web possuem muito em comum com aqueles de
uma data warehouse: tais dados são sempre agregados ao final dos logs, os
quais crescem rapidamente ao longo do tempo, impossibilitando a análise de
todo ele, e levando à necessidade de sumarização para fins de desempenho.
Há também requisitos de segurança, pois certas porções dos logs não devem
ser vistas pelo analista. Assim, [Kimball & Merz, 2000] apresentam uma
visão unificada do processo de prospecção de uso da Web focada
essencialmente em data warehousing, a qual denominam “data Webhousing”,
que além de abordarem temas comuns aos outros trabalhos de prospecção de
uso, fazem-no de modo integrado, incluindo a utilização de técnicas e
ferramentas OLAP.
As aplicações de prospecção de uso da Web podem ser classificadas em duas
categorias: aprendizagem de perfil do usuário ou modelagem de usuários em interfaces
adaptativas (personalização) ou aprendizagem de padrões de navegação (sem
personalização). Usuários da Web podem estar interessados em técnicas que possam
aprender suas necessidades e preferências de informação, que é a modelagem do usuário
possivelmente combinada com prospecção de conteúdo da Web. Por outro lado,
provedores de informação podem estar interessados em técnicas que melhorem a
efetividade das informações, estando interessados em aprendizagem de padrões de
navegação dos usuários, que podem ser usados em aplicações tais como personalização
(nível de site da Web), melhoramento do sistema, modificações no site, comércio
inteligente e caracterização de uso [Kosala & Blockeel, 2000]. No entanto, uma das
mais difíceis tarefas em prospecção de dados é a determinação de qual dos algoritmos
disponíveis é melhor para um dado problema [Wu, 2002].
37
Existe uma ampla variedade de aplicações para as informações obtidas a partir
da análise de uso de um site Web, indo desde a utilização em campanhas promocionais,
análise de estratégias de marketing, reestruturação e adaptação automática do site, até o
gerenciamento mais efetivo das comunicações de um grupo de trabalho e da
infraestrutura organizacional, passando ainda pela distribuição de propaganda para
usuários específicos e venda de espaço de publicidade. Aplicações comuns incluem
usabilidade de sites da Web, direcionamentos para compras, marketing dinâmico, perfis
de usuários através da análise de comportamento e afinidades com determinados
produtos [Jennings, 2002].
2.4.1.3 – Interfaces Inteligentes ou Cooperativas
As interfaces inteligentes ou cooperativas utilizam técnicas de Inteligência
Artificial para auxiliar o usuário em suas tarefas. A interface inteligente deve simular
um intermediário humano, devendo possuir conhecimento sobre a terminologia usada,
sobre o sistema em questão e sobre técnicas de elicitação.
A finalidade da interface inteligente é ajudar o usuário a alcançar seu objetivo.
Conforme [Frainer, 1993], a interface inteligente deve capturar 4 tipos de
informação sobre o usuário:
- objetivo do usuário: estado que o usuário quer atingir;
- seu plano: a seqüência de ações ou eventos que o levam ao estado desejado;
- habilidades do usuário: físicas e mentais;
- comportamento e preferências: estilo de interação e comodidades.
Os objetivos do usuário podem ser explicitamente declarados ou então inferidos
automaticamente por mecanismos de inteligência da interface. Para este último caso,
podem ser empregadas técnicas de aprendizado de máquina (machine learning) para
analisar o comportamento do usuário, o histórico da interação ou de contatos anteriores
e as características do ambiente (por exemplo, observando o que foi recuperado, lido,
ignorado, gravado, excluído, enviado a outros etc.) [Loh & Garin, 2001].
Os procedimentos de cooperação indireta tendem a ser bem sucedidos quando a
captura das informações necessárias à sua implementação é realizada por um
mecanismo automatizado, que registram as atividades comuns e cotidianas dos
membros do grupo, sem lhes atribuir uma carga de trabalho adicional. Caso contrário, o
38
ônus de preencher relatórios, documentar comportamentos ou relatar resultados de
pesquisas, desencoraja a participação do usuário no sistema [Schwartz & Wood, 1993].
Geralmente, as interfaces inteligentes ou cooperativas procuram estabelecer
modelos de usuários para poder auxiliá-los. Isto pode ser conseguido descobrindo-se um
perfil comum em grupos de usuários. Também podem ser utilizados diálogos para que a
interface entenda a necessidade do usuário. As técnicas de processamento de linguagem
natural são utilizadas por interfaces inteligentes ou cooperativas para entender as
entradas fornecidas pelos usuários ou para formular respostas a eles compreensíveis,
também servindo para eliminar ambigüidades na interação, quando os usuários tentam
elicitar as suas necessidades. Eliminar ambigüidades significa determinar o sentido ou
significado das palavras e frases, uma vez que estas podem possuir mais de um
significado ou podem levar a interpretações errôneas, dependendo da construção
formada [Loh & Garin, 2001].
2.4.1.4 – Agentes Inteligentes
Agentes inteligentes são sistemas automatizados (hardware ou software),
imbuídos de mecanismos de Inteligência Artificial, capazes de tomar decisões e auto-
aprimorar seu desempenho [Yao et al., 2001].
Segundo [Fernandes, 1998] e [Wang et al., 2002] agentes inteligentes devem
possuir as seguintes características:
a) autonomia: trabalhar sem a intervenção humana;
b) sociabilidade ou habilidade: saber interagir com humanos ou outros agentes;
c) reatividade: poder receber estímulos do ambiente e responder em tempo
hábil;
d) pró-atividade: ter comportamento direcionado a um objetivo, tomando a
iniciativa da ação sem precisar esperar estímulos;
e) mobilidade: locomover-se para outros ambientes;
f) continuidade temporal: funcionar continuamente.
A prospecção de dados da Web é freqüentemente vista e implementada dentro de
um paradigma de agente, tendo assim um relacionamento estreito com agentes de
software [Kosala & Blockeel, 2000]. Agentes utilizados na prospecção de dados são
considerados agentes inteligentes, pois exploram serviços na Web e buscam entender
regularidades por ela geradas [Yao et al., 2001], executando tarefas de prospecção de
dados para atingir seus objetivos. Dentre as subcategorias de agentes de software as que 39
são relevantes para as tarefas de prospecção de dados compreendem agentes de interface
e agentes distribuídos.
Os agentes de interface de usuário tentam maximizar a produtividade das atuais
interações dos usuários com o sistema através de comportamento adaptativo
(personalização), sendo pertencentes a esta categoria os agentes de recuperação de
informação, agentes de filtragem de informação e agentes assistentes pessoais.
Tecnologia de agentes distribuídos é interessada na resolução de problemas de
um grupo de agentes e nesta categoria temos os agentes distribuídos para descoberta de
conhecimento ou prospecção de dados.
Existem duas abordagens freqüentemente utilizadas para desenvolver agentes
inteligentes que ajudam os usuários a encontrar e recuperar informações relevantes da
Web, chamadas de abordagem baseada em conteúdo e abordagem colaborativa. Na
abordagem baseada em conteúdo os sistemas procuram por emparelhamento de itens a
partir da análise de conteúdo, usando as preferências dos usuários. Na abordagem
colaborativa, os sistemas tentam encontrar usuários com interesses similares para fazer
recomendações a eles, utilizando para isto a análise de perfil do usuário, sessões ou
transações do usuário e assumindo que se alguns usuários acham um item importante,
então os outros usuários com interesses similares irão achá-lo importante também.
Podemos caracterizar os métodos baseados em conteúdo como prospecção de conteúdo
da Web e as abordagens colaborativas como prospecção de uso da Web [Kosala &
Blockeel, 2000].
Quando existem vários agentes inteligentes atuando de forma integrada e
cooperativa, o sistema denomina-se sistema multi-agentes. Geralmente, cada agente
inteligente individual possui conhecimentos próprios e diferentes. Estes indivíduos
interagem entre si, compartilhando informações e conhecimento para soluções de
problemas mais complexos, os quais dificilmente seriam resolvidos por qualquer deles
de maneira isolada [Loh & Garin, 2001]. Um exemplo deste tipo de arquitetura foi
aplicado no desenvolvimento do modelo CIR – Coordinated Intelligent Rational Agent,
que auxilia usuários na localização e recuperação de informação em sistemas de
informações distribuídos [Shakshuki et al., 2002].
2.4.2 – Aplicações da Web Inteligente
40
Existem diversas aplicações que se caracterizam como sistemas de Web
Inteligente, dentre elas: propagandas de produtos/serviços, suporte ao usuário através de
linguagem natural, intermediação de negócios empresa/cliente e B2B (business-to-
business), inteligência competitiva, gerência de redes e sites, personalização de sites da
Web, recomendação e busca de informação, dentre outras, sendo estas três últimas as
mais estreitamente ligadas à descoberta de conhecimento sendo, portanto, analisadas
mais detalhadamente.
2.4.2.1 – Personalização de Sites da Web
Personalização é aplicável a qualquer atividade de navegação na Web, não
somente em comércio eletrônico, e pode ser definida como qualquer ação que utilize a
experiência na Web de um usuário particular, ou um conjunto de usuários. Esta
experiência pode ser algo casual como navegar em um site da Web ou economicamente
significante, como comercializar estoques. As ações podem limitar-se a apresentação
mais agradável para antecipar as necessidades de um usuário, até prover informações de
forma mais customizada [Mobasher et al., 2000a].
Customização é a personalização da apresentação do site de acordo com as
necessidades de cada usuário, tomado individualmente, baseando-se nas informações
sobre o usuário. Qualquer mudança afeta apenas o usuário individualmente,
efetivamente criando numerosas versões do site, uma para cada usuário. Já a
transformação é o aperfeiçoamento da estrutura do site baseado em interações com
todos os usuários. Uma lista de utilizações mais populares é um exemplo simples de
uma transformação global: o site se modifica de acordo com o interesse de usuários que
já o utilizaram para apresentar links que provavelmente serão atraentes para usuários
futuros [Perkowitz & Etzioni, 2000].
Atualmente, a maioria dos sistemas para a Web recai em três categorias: sistemas
manuais de regras de decisão, sistemas de filtragem colaborativa e, por último, agentes
de filtragem baseados em conteúdos.
Sistemas manuais de regras de decisão, tais como Broadvision
(www.broadvision.com), permitem que os administradores de sites da Web
especifiquem regras baseadas em perfis demográficos ou estáticos dos usuários,
coletados a partir de um processo de registro ou de seus históricos de sessões de uso,
sendo que tais regras são usadas para afetar o conteúdo apresentado para um usuário em
particular.
Sistemas de filtragem colaborativa, tais como Firefly [Shardanand & Maes,
1995] e Net Perceptions (www.netperceptions.com), tipicamente tomam informações
explícitas na forma de categorias ou preferências dos usuários, e através de uma
41
máquina de correlação retorna a informação que é prevista ser a de preferência do
usuário.
Abordagens baseadas em conteúdo tais como aquelas usadas por WebWatcher
[Joachims et al., 1997] utilizam similaridade de conteúdo de documentos da Web para
obter perfis pessoais explicitamente ou implicitamente dos usuários.
De forma crescente, a nova geração de ferramentas de personalização da Web
está tentando incorporar técnicas de descoberta de padrões a partir dos dados de uso da
Web. Por exemplo, alguns sistemas de filtragem colaborativa estão realizando
experimentos a partir da obtenção implícita de categorias de usuários a partir de seus
dados de uso. Sistemas de prospecção de uso da Web executam quaisquer algoritmos de
prospecção em dados de uso ou clickstream provenientes de um ou mais sites da Web
para descobrir perfis de usuários. As entradas não são descrições subjetivas dos usuários
propriamente ditos, e assim não estão propensas a preconceitos. Os perfis são
dinamicamente obtidos dos padrões do usuário, e assim o desempenho do sistema não
degrada com o tempo. Além disso, o uso somente de similaridade de conteúdo na
obtenção de perfis agregados pode resultar em importantes perdas de relacionamentos
semânticos entre os objetos da Web. Assim, a prospecção de uso da Web pode reduzir a
necessidade de obtenção de categorias subjetivas dos usuários ou preferências pessoais
baseadas em dados cadastrais.
O processo genérico de personalização é divido em dois componentes. O
componente off-line é composto das tarefas de preparação dos dados e prospecção
específica de uso. As tarefas de preparação dos dados resultam em um arquivo de
sessões do servidor, onde cada sessão é uma seqüência de páginas visitadas
(pageviews). As tarefas de prospecção de uso envolvem a descoberta de regras de
associação, padrões seqüenciais, agrupamentos de páginas visitadas, agrupamentos de
usuários, ou qualquer outro método de descoberta de padrões. Os padrões descobertos
são usados pelo componente on-line para prover conteúdo personalizado aos usuários,
baseado em suas atividades atuais de navegação [Mobasher et al., 2000a].
Pode-se citar alguns tipos de personalização de sites mais populares:
- Portais que provêem uma variedade de customizações manuais feitas pelos
usuários, permitindo a seleção de links particulares, novos tópicos de
interesse etc. Nestes casos, a automatização é mínima, pois os usuários
organizam suas próprias home pages de forma customizada. Exemplos: My
Yahoo!! (my.yahoo.com) e Go2net´s (www.go2net.com).
42
- A customização automática também é comum na Web, AVANTI
(fit.gmd.de/hci/projects/avanti/), por exemplo, usa informações de perfis de
uso e comportamento de uso dos usuários para decidir como apresentar links.
- Uma outra abordagem comum para customização automatizada é a filtragem
colaborativa, em que os usuários avaliam objetos e aqueles que avaliam de
forma similar objetos similares são presumidos terem gostos similares.
Quando um usuário busca recomendações de novos objetos, o site sugere
aqueles objetos que tiveram melhores avaliações pelos outros usuários com
gostos similares. Companhias como a Netperceptions
(www.netperceptions.com/) usam esta tecnologia para uma grande
quantidade de sites da Web, como por exemplo para a Amazon.com.
- Uma abordagem de transformação é usada pela Footprints [Wexelblat &
Maes, 1997], em que as trilhas percorridas pelos usuários são acumuladas e
as trilhas mais utilizadas indicam as páginas mais interessantes a serem
visitadas. As informações geradas são automáticas e anônimas, e qualquer
usuário pode vê-las, não precisando nenhuma informação sobre si para obter
esta vantagem do sistema (wex.www.media.mit.edu/people/wex) [Perkowitz
& Etzioni, 2000].
2.4.2.2 – Recomendação
A recomendação é um tipo especial de personalização que tem como objetivo
decidir quais dos objetos serão apresentados ao usuário e não somente modificar a
forma de apresentação [Loh & Garin, 2001], constituindo o componente on-line de um
sistema de personalização da Web. Assim, o conteúdo personalizado pode tomar a
forma de recomendações de links ou produtos, anúncios, textos, gráficos, etc., de acordo
com as preferências dos usuários. O servidor da Web guarda as trilhas de sessões além
das navegações feitas pelo usuário através de requisições HTTP, e a máquina de
recomendações considera as sessões de atividades do servidor conjuntamente com os
padrões descobertos para prover conteúdo personalizado [Mobasher et al., 2000a].
Entender as necessidades dos usuários de um site da Web requer o entendimento
de como eles vêem os dados disponíveis e como utilizam atualmente o site. A
recomendação é uma forma de se desenvolver sites personalizados através da utilização
de assistentes de gerenciamento da Web, que são sistemas que podem processar grandes
coleções de dados sobre a utilização do site e recomendar adaptações para o Web
master. Desta forma, tais sites semi-automaticamente melhoram sua organização e 43
apresentação através do aprendizado dos padrões de acesso de seus visitantes
[Perkowitz & Etzioni, 2000].
Adaptações de um site baseadas em acesso usam as trilhas seguidas pelos seus
visitantes para guiar como ele deverá ser modificado. Informações de acesso (derivadas
dos logs dos servidores Web, por exemplo) podem conter padrões comuns de
comportamento de usuários em um site, a partir dos quais podem ser descobertas
valiosas recomendações a serem utilizadas nas adaptações.
2.4.2.3 – Busca de Informação
A Web Inteligente é especialmente útil no auxílio aos usuários que realizam
buscas na Web, através de métodos de filtragem de informações ou documentos, que
consistem em formalizar uma consulta ou determinar o perfil de interesse do usuário e
então fazer a recuperação da informação sem que o usuário necessite dar início ao
processo. Assim, o sistema de busca inteligente notifica o usuário quando alguma
informação de interesse é encontrada ou quando algo novo é armazenado na Web e
captado por ele.
Métodos de filtragem mais complexos podem adaptar filtros conforme mude o
interesse do usuário e neste caso, métodos automáticos de aprendizagem supervisionada
realizam a modelagem do usuário com o objetivo de entender seu perfil de interesse sem
que o usuário precise manifestá-lo.
A filtragem colaborativa é um caso especial destes métodos de filtragem. Ela é
utilizada para recomendar conteúdos para um usuário com base em feedback fornecido
por outros usuários de forma explícita (críticas) ou implícita (documentos lidos,
baixados, etc.) [Loh & Garin, 2001].
2.5 – Trabalhos Relacionados
Apesar de ser uma área de pesquisa recente, existe uma grande diversidade de
trabalhos em prospecção de dados da Web, abrangendo suas diferentes categorias,
proporcionando a descoberta de uma variedade de funcionalidades.
Dentro do propósito desta dissertação, os esforços dirigidos à prospecção de uso
visando a descoberta e utilização de padrões de acesso à Web, são os que mais se
relacionam com seus objetivos.
Neste limite contextual pode-se citar, dentre diversos outros, os seguintes
trabalhos:
44
- WebMiner [Mobasher et al., 1996], [Cooley et al., 1997]: o WebMiner
implementa parcialmente uma arquitetura genérica proposta para a mineração
de uso da Web. Seu processo de prospecção de dados foi dividido
originalmente em duas etapas: a primeira incluindo os processos dependentes
do domínio, tais como atividades de limpeza e integração dos dados brutos e a
divisão das entradas dos logs em sessões e transações; e a segunda abarcando
a aplicação de técnicas de prospecção de dados na busca dos padrões de uso.
Posteriormente, a segunda fase foi dividida em outras duas: prospecção de
regras e análise de padrões [Cooley et al., 1999], [Mobasher et al., 2000b].
- WebLogMiner [Zaïane et al., 1998]: o WebLogMiner é uma ferramenta para
descoberta de conhecimento através da prospecção de dados contidos em
arquivos de log do servidor Web, que possui quatro estágios. No primeiro
estágio, os dados são filtrados para a remoção de informações irrelevantes e
um banco de dados relacional é criado contendo os dados significantes
restantes. No segundo estágio, um cubo de dados é construído usando-se as
dimensões disponíveis. Então, é usado OLAP (On-line Analytical Processing)
no terceiro estágio para analisar os dados do cubo. Finalmente, no quarto
estágio, técnicas de prospecção de dados são utilizadas com os dados do cubo
para predição, classificação e descoberta de correlações interessantes sobre o
tráfego na Web e a evolução do comportamento dos usuários ao longo do
tempo e outros tipos de análise de séries temporais.
- WUM [Spiliopoulou & Faulstich, 1998]: o WUM (Web Utilization Miner) é
um sistema que explora a tecnologia de prospecção de dados para a
descoberta de padrões de acesso com interessantes propriedades estatísticas,
prevendo inicialmente os indicadores de importância na navegação do
usuário, indo além de acessos freqüentes a algumas páginas, mas também
suportando especificação subjetiva de um especialista do domínio.
- DS-Web [Ma et al., 2000]: o sistema DS-Web utiliza a Web para auxiliar os
usuários no entendimento de um conjunto de regras descobertas a partir da
prospecção de dados. Primeiramente é encontrado um subconjunto especial
(ou um sumário) das regras que representam os relacionamentos essenciais do
domínio e é construída uma estrutura hierárquica das regras. Em um segundo 45
passo, esta hierarquia de regras é publicada através de múltiplas páginas Web
utilizando-se hyperlinks. DS-Web não apenas permite que o usuário navegue
pelas regras facilmente, mas também permite a criação de um espaço virtual
onde múltiplos usuários podem compartilhar opiniões sobre as regras, o que
contribui para a compreensão do domínio.
- WebViz [Pitkow & Bharat, 1994]: o sistema WebViz é mais voltado para a
análise de padrões, procurando auxiliar principalmente as tarefas de
visualização, entendimento e interpretação dos padrões obtidos. O WebViz
utiliza um paradigma baseado em percursos ou caminhos da Web (seqüências
de links entre as páginas), pelos quais se extraem, a partir dos logs de
utilização, subseqüências dos padrões de navegações nas páginas com o
propósito de facilitar alterações estruturais e contextuais, resultando em um
uso mais eficiente dos documentos do banco de dados.
- WebPersonalizer System [Mobasher et al., 2000a]: o sistema WebPersonalizer
usa uma arquitetura que provê uma lista de recomendações de links hipertexto
para o usuário durante sua navegação através de um site Web. Atualmente, o
WebPersonalizer utiliza somente dados de uso anônimos providos pelos logs
do servidor Web e a estrutura hipertexto de um site. Os passos de pré-
processamento são usados para converter os logs do servidor em sessões e
então são gerados perfis agregados de utilização que são utilizados para se
fazer recomendações.
46
3 – Proposta de Trabalho
Neste capítulo será apresentada a estrutura do trabalho, assim como os objetivos,
aplicação prática e resultados esperados. Inicia-se com uma breve apresentação de
alguns processos relacionados à descoberta e gestão do conhecimento no âmbito da Web
Inteligente, sendo em seguida discutida uma metodologia buscando-se a implantação de
otimizações nesses processos, as quais constituem os objetivos específicos deste
trabalho. Ao final é apresentada uma proposta de utilização da arquitetura em uma
ferramenta de apoio à gestão de conhecimento, na forma de uma aplicação back-end
para um portal Web de uma comunidade científica de pesquisa, bem como os resultados
esperados pela utilização desta ferramenta.
3.1 – Engenharia Ontológica
A emergente disciplina de engenharia ontológica tem como principal objetivo
sustentar o desenvolvimento e uso de ontologias ao longo de seu ciclo de vida: projeto,
avaliação, validação, manutenção, desenvolvimento, utilização, integração,
compartilhamento e reutilização.
Construir ontologias é difícil, consome tempo e custo, principalmente porque o
desenvolvimento de ontologias requer consenso em uma comunidade em que os
membros podem ter visões distintas do domínio em consideração.
Tim Berners-Lee – o criador da Web – considera ontologias como uma parte
crítica nos mais recentes trabalhos em direção a Web Inteligente, a qual ele prevê que
permitirá que nossos agentes de software comuniquem entre si para realizar nossas
tarefas.
Na engenharia ontológica não existe pré-classificação de domínios de
problemas e nenhuma caracterização para avaliação e comparação da adequação ou
desempenho das ontologias. É possível ter-se análise teórica de ontologias. Dada a
especificação de uma ontologia, como um conjunto de axiomas em uma linguagem
lógica, podemos caracterizar os modelos dos axiomas da ontologia e compará-los com
os modelos planejados pelo projetista ou usuário.
Por outro lado, existem algumas questões que somente podem ser resolvidas
empiricamente. Uma ontologia pode ter excelentes propriedades formais, mas se elas
47
não capturam a semântica pretendida pela terminologia do usuário, então a ontologia
tem pouca utilidade prática [Gruninger & Lee, 2002].
Uma ontologia para organizações baseadas em conhecimento fornece termos e
definições de conceitos (entidades, objetos, eventos, processos, objetivos e resultados)
que são julgados importantes na caracterização dessas organizações em um nível
desejável de detalhe. Conceitos e seus relacionamentos são considerados em termos de
axiomas e restrições que podem ser expressos em diversos níveis de formalidade. Entre
aquelas organizações que adotam ontologia, seus termos são usados em questões de
perguntas e respostas, criando afirmações, relatando tendências, descrevendo práticas e
discutindo investigações pertinentes para a administração da gestão de conhecimento.
Desta forma, o comprometimento ontológico é importante pois ele é o acordo
entre múltiplas partes (pessoas e sistemas de software) para adotar uma ontologia
particular quando estas se comunicarem sobre o domínio de interesse, embora elas não
tenham necessariamente as mesmas experiências, teorias ou prescrições sobre o
domínio. Onde falta o compromisso ontológico é difícil conversar claramente sobre o
domínio e beneficiar-se do conhecimento alheio. Assim, o desenvolvimento de uma
ontologia deve ser feito com uma visão direcionada a assegurar que seus usuários
potenciais encontrem caracterizações suficientemente completas, corretas, claras e
concisas.
Pela importância de ontologias na era emergente de organizações baseadas em
conhecimento, é necessário um melhor suporte para seu desenvolvimento. Geralmente,
ontologia é um ramo da filosofia ligado com a ordem e estrutura da realidade e assim,
uma razão típica para se construir uma ontologia é fornecer uma linguagem comum para
compartilhar e reusar conhecimento sobre fenômenos no mundo de interesse.
No desenvolvimento e aplicação de uma ontologia, é importante tornar claras as
seguintes distinções: por um lado, existe a ontologia em si, com conceitos específicos
usados em um domínio. A existência e relacionamentos entre estes conceitos são
verdadeiros por definição ou convenção. Por outro lado, existem fatos empíricos sobre
estes conceitos e relacionamentos. Tais fatos não são parte da ontologia embora sejam
estruturados por ela [Holsapple & Joshi, 2002]. Estes fatos são submetidos ao contexto,
observação e testes, e o engenheiro do domínio deve ser capaz de realizar as
manutenções necessárias na ontologia de acordo com as observações resultantes da
utilização dos fatos por ela estruturados.
Deveríamos ser hábeis a não somente desenvolver e usar aplicações baseadas em
ontologias, mas também realizar testes experimentais para compará-las e avaliá-las 48
[Gruninger & Lee, 2002]. Os resultados destes testes empíricos, validados teoricamente
pelos engenheiros do domínio, poderiam servir como guia para a manutenção de tais
ontologias, mantendo-se o consenso previsto entre a sua comunidade de uso e assim,
mantendo-as coerentemente válidas, visto sua importância nos processos de gestão de
conhecimento em geral e na Web Inteligente.
3.2 – Conhecimento Personalizado
A Web está provendo um meio de comunicação direta entre os provedores de
produtos/serviços e seus clientes, o que junto com à habilidade de coletar dados
detalhados sobre os cliques dos usuários nos sites provê uma grande oportunidade de
personalizar o conhecimento acessado através da Web. A maioria das abordagens para
personalização acredita na participação de humanos na coleta de informações de perfis
sobre usuários, porém com problemas dos dados dos perfis serem subjetivos, bem como
as preferências dos usuários serem alteradas com o tempo. Assim, tem-se provido um
conjunto de técnicas em que as preferências dos usuários são automaticamente
aprendidas dos dados de uso da Web, utilizando-se técnicas de prospecção de dados,
eliminando a subjetividade e dificuldades nas alterações de perfis [Mobasher et al.,
2000a].
Na Web Inteligente as ontologias podem ser vistas como um passo em direção à
busca de conhecimento personalizado, uma vez que refletem conhecimentos
consensuais de especialistas de um domínio. Outro passo neste direcionamento é a
descoberta de padrões de uso da Web com o objetivo de se prover personalizações
individuais ou de sites em geral para melhor atender às necessidades de seus usuários, o
que se caracteriza como aplicações de recomendações baseadas no uso da Web.
Cada site é eletronicamente administrado por um servidor Web, que registra
todas as atividades que acontecem em um arquivo, o log do servidor Web. A partir deste
arquivo de log, podemos extrair informações que indiretamente refletem a qualidade do
site, através da aplicação de técnicas de prospecção de dados [Spiliopoulou, 2000].
Existem dois tipos de tendências em prospecção de uso da Web: descoberta de padrões
de acessos genéricos e descoberta customizada de uso. A análise de padrões genéricos é
destinada ao entendimento de padrões de acesso e tendências, que podem ser utilizados
para a re-estruturação de sites e melhoria nos agrupamentos de recursos, podendo-se
definir localizações mais efetivas para anúncios e direcionar vendas específicas a
usuários específicos etc. Por outro lado, a descoberta customizada de uso analisa
49
tendências individuais, propondo-se a customização de sites da Web para os usuários. A
informação mostrada, a estrutura do site e o formato dos recursos podem ser
dinamicamente customizados para cada usuário baseando-se em seus padrões de acesso
[Zaïane, 1999a].
O processo de descoberta de conhecimento é composto por uma série de etapas,
dentre as quais se destaca a prospecção de dados, que tem por objetivo a descoberta de
padrões interessantes em bases de dados, estando dentre eles os padrões de acesso, que
são padrões descritivos das relações entre conjuntos de itens em bancos de dados de
transações da Web. Tais padrões podem ser utilizados na orientação do usuário na tarefa
de descoberta de conhecimento na Web. A utilização de técnicas de prospecção de
dados da Web para a descoberta de padrões de acessos dos usuários possibilita o
desenvolvimento de aplicações voltadas para a Web Inteligente, tornando o processo de
descoberta de conhecimento no amplo repositório de dados da Web mais eficiente e
personalizado.
3.3 – Objetivos
Gestão de Conhecimento pode ser aplicada além do âmbito das organizações,
onde uma comunidade de usuários com interesses em comum usam a Internet como
infraestrutura para disponibilizar seu conhecimento individual, transformando-o em
conhecimento coletivo.
As máquinas de busca globais, tais como Google, AltaVista e Lycos podem
proporcionar uma grande ajuda aos usuários na busca de informação, retornando os
resultados desejados, desde que sejam utilizadas consultas claras e não ambíguas.
Entretanto, os usuários freqüentemente apresentam consultas obscuras e genéricas que
os levam a encontrar determinados sites como ponto de partida. Uma vez estando em
um site, os usuários devem escolher entre seguir hyperlinks ou usar a máquina de busca
do site para conseguir informação mais específica. Devido à baixa eficiência de se
seguir hyperlinks, existe uma grande necessidade de técnicas eficientes para as buscas
nos sites.
A maioria das máquinas de buscas dos sites meramente utiliza o método “full
text search” que recupera uma grande quantidade de documentos contendo as mesmas
palavras utilizadas como entrada pelo usuário. Algumas técnicas utilizadas em buscas
na Web global também são utilizadas em buscas em sites, tais como análise de links e
ranqueamento baseado em cliques, porém não trabalham bem em tais ambientes.
50
Primeiramente as técnicas de análise de links, tais como HITS [Kleinberg, 1998] e
PageHank [Brin & Page, 1998] usam os hyperlinks entre as páginas da Web para
ranqueá-las, considerando que páginas com maior número de referências tenham alta
pontuação no ranqueamento. Entretanto, a informação de links em um site não é
suficiente para refletir a importância da página. Assim as páginas mais importantes de
um site não são necessariamente as páginas mais referenciadas, sendo que
freqüentemente as páginas de entrada do site, páginas de índices e páginas de ajuda são
as mais referenciadas e geralmente não correspondem ao desejo do usuário. Os métodos
baseados em clickthru, tal como DirectHit, são também problemáticos para uso em
sites, pois de acordo com uma consulta em particular, os logs das sessões anteriores para
esta mesma consulta são utilizados para retornar as páginas que a maioria dos usuários
visitou. Para que pudesse resultar em informações estatisticamente significantes, estes
métodos só poderiam ser aplicados a um pequeno conjunto de consultas populares, pois
a falta de sessões de consultas anteriores e a diversidade de padrões de acesso dos
usuários os impediriam de ser aplicados em sites da Web [Xue et al., 2002].
Visto as dificuldades encontradas pelos métodos utilizados nas máquinas de
busca de sites da Web e tendo-se em mente os benefícios futuros provenientes da
personalização, como a habilidade de melhor servir às necessidades dos usuários,
apresentando-lhe o serviço mais apropriado a qualquer momento, o objetivo desta
dissertação é propor uma solução destinada a apoiar a questão de gestão de
conhecimento em um portal Web de domínio específico, procurando otimizar suas
atividades de filtragem e manutenção de informações. Assim, este trabalho visa a
proposta de uma ferramenta baseada na Prospecção de Uso da Web, como um
componente da Web Inteligente intimamente relacionado ao processo de descoberta de
conhecimento, buscando-se a otimização do processo de gestão de conhecimento neste
portal da Web.
A partir de uma determinada necessidade de informação, um usuário visita um
site Web e segue trilhas de navegação guiadas pelas suas preferências e necessidades.
As trilhas percorridas através dos conteúdos/recursos do site são automaticamente
registradas nos arquivos de logs, e estas podem ser preparadas (pré-processadas) e
depois de agrupadas podem ser submetidas a procedimentos de prospecção de dados. Os
resultados destas análises indicarão padrões e tendências que poderão ser considerados
na definição, na estruturação e no agrupamento dos conteúdos e recursos
disponibilizados pelo site Web.
51
Algoritmos tradicionais de prospecção de dados podem ser falhos na descoberta
de padrões devido à grande diversidade de dados no entanto, quando se tem a
possibilidade de utilização de uma taxonomia pré-definida, contendo informações
semânticas sobre o conteúdo do site, juntamente com os seus arquivos de logs de
acesso, pode-se prover grandes melhorias nos resultados das buscas pois se minimizam
as diversidades de acesso, permitindo a descoberta de padrões mais generalizados.
Assim, a solução aqui proposta implica no desenvolvimento de uma ferramenta
tecnológica baseada na metodologia de Prospecção de Uso da Web, envolvendo a
descoberta de conhecimento no âmbito dos arquivos de log provenientes das consultas
realizadas pelos usuários de um portal Web contendo uma taxonomia de domínio,
permitindo a extração de padrões que efetivamente demonstrem as tendências de busca
por informações no portal. Desta forma, mais especificamente, o objetivo deste
trabalho se destina à disponibilização dos padrões de acesso descobertos ao
mecanismo de busca de um portal específico e aos engenheiros do seu domínio, visando
a efetiva descoberta de conhecimento acerca da sua utilização, para que possam
melhor direcionar suas respectivas atividades relacionadas ao processo de gestão de
conhecimento no portal.
3.4 – Aplicação Prática
Com o propósito de demonstrar a funcionalidade e aplicabilidade da solução
proposta para a obtenção de uma ferramenta tecnológica que contribua para o
aperfeiçoamento do processo de gestão de conhecimento em um portal Web, a mesma
será instanciada em uma aplicação prática destinada a prover conhecimentos para os
engenheiros do domínio e para o mecanismo de busca do portal Web de uma
comunidade científica de pesquisa, no qual foi incorporada uma ontologia que
representa uma taxonomia utilizada para guiar buscas não convencionais no domínio do
portal.
Trata-se de uma comunidade formada em torno do Consórcio Brasileiro de
Pesquisa e Desenvolvimento do Café (CBP&D/Café1). O CBP&D/Café é uma
congregação de instituições de pesquisa e desenvolvimento que têm por objetivo dar
sustentação tecnológica ao agronegócio do café no Brasil. Foi criado em março de 1997
1 Programa coordenado pelo Consórcio Brasileiro de Pesquisa e Desenvolvimento do Café
(CBP&D/Café). O consórcio é formado por cerca de 40 instituições, entre elas universidades, fundações,
institutos, centros de pesquisa e empresas espalhadas por todo o território nacional.
52
por dez instituições brasileiras de P&D do café (EBDA, EMBRAPA, INCAPER,
EPAMIG, IAC, IAPAR, PESAGRO-RIO, MA/SARC, UFLA e UFV), tendo a Embrapa
como instituição coordenadora. O preceito orientador da criação do Consórcio é o do
somatório de recursos humanos, laboratoriais, físicos e financeiros das instituições, com
vista à concepção e execução de atividades de P&D em todas as áreas da cadeia
produtiva do café e na abrangência dos principais estados produtores. A finalidade do
Consórcio é desenvolver estudos, pesquisas e atividades de desenvolvimento capazes de
dar sustentação tecnológica e econômica ao agronegócio do café, por meio da
integração das instituições de P&D e todos os demais componentes do setor cafeeiro, no
sentido de expandir e consolidar a capacidade de identificação de problemas e geração
de alternativas tecnológicas. Atualmente, as atividades de P&D são desenvolvidas por
40 instituições brasileiras, abrangendo doze estados produtores.
O acesso ao conhecimento é condição básica ao desenvolvimento científico e
tecnológico. Um pesquisador necessita saber o que está sendo pesquisado ou
desenvolvido em sua especialidade, quais são os especialistas da área, etc. O
conhecimento adquirido através das pesquisas precisa ser disseminado para que possa se
multiplicar e trazer benefícios para toda a sociedade. Desta forma pretende-se, tanto
mostrar a aplicabilidade prática da ferramenta proposta, quanto contribuir para uma
melhor difusão do conhecimento numa área estratégica para a economia brasileira.
O portal Internet desta comunidade de pesquisa, o SBICafé, cuja interface
principal pode ser visualizada na Figura 3.1, se encontra disponível e conta atualmente
com a Biblioteca Virtual do Café, além de informações sobre projetos de pesquisa
desenvolvidos e em andamento nas instituições participantes do CNP&D-Café e
informações de eventos (congressos, simpósios, palestras, treinamentos etc.)
patrocinados pelas instituições.
53
Figura 3.1: Tela principal do Portal SBICafé.
O SBICafé foi desenvolvido e disponibilizado com o intuito de propiciar um
ambiente adequado para testes comparativos entre a abordagem convencional de busca
de informações usando casamento de padrões com a abordagem baseada em uma
ontologia de domínio.
Assim, em um projeto anterior realizado por [Pontes, 2002] foi incorporada uma
ontologia a este portal, representando um mapa do conhecimento a ser utilizado pela
comunidade envolvida, com a finalidade de aprimorar a funcionalidade do portal Web.
Neste caso, a ontologia é representada por um vocabulário de termos e relacionamentos
entre eles, sendo designada como um tesauro, e proporciona benefícios ao processo de
busca de informação, por ser este baseado em semântica, estendendo a busca
convencional baseada em casamento de padrões.
Este trabalho de destina à continuidade do projeto de [Pontes, 2002], buscando a
utilização de técnicas de prospecção de dados para auxiliar a manutenção da ontologia
utilizada no SBICafé, bem como a obtenção de padrões de acesso ao mecanismo de
busca da Biblioteca Virtual do Café, visando-se analisar indícios de otimizações nestes
serviços.
54
O tesauro utilizado pelo SBICafé é intitulado AgroVoc, sendo um tesauro
multilíngua para o domínio agrícola desenvolvido e mantido pela FAO2 (Food and
Agriculture Organization of the United Nations) através do WAICENT3 (World
Agricultural Information Center).
Um tesauro pode ser considerado um tipo simples de ontologia e a sua aplicação
na era da informação digital pode trazer muitos benefícios, procurando categorizar
termos (assuntos) usando uma variedade de relações simples, sendo as principais:
- Termo Genérico (Broader Term – BT): um termo ou conceito particular é
mais genérico que um outro.
- Termo Específico (Narrower Term – NT): um termo ou conceito particular é
mais específico que um outro.
- Termo Relacionado (Related Term – RT): dois termos ou conceitos são
associados.
- Use para (Use For – UF): um termo ou conceito particular é preferível dentre
outros termos sinônimos.
As relações BT, NT dão origem a taxonomias (organizando termos em
categorias hierárquicas). As relações do tipo RT englobam uma grande variedade de
relações cuja semântica não é definida de forma precisa dentro do tesauro. As relações
UF são tipicamente relações de sinonímia entre termos.
A versão do AgroVoc analisada contém 133.226 termos em 5 idiomas – Inglês,
Espanhol, Francês, Português e Alemão. O princípio adotado pelo AgroVoc é de que
cada termo deve possuir um equivalente em cada um dos idiomas suportados. A
abrangência do AgroVoc engloba todo o domínio agrícola – plantas, animais, sistemas
de produção, agroindústria etc. As relações existentes entre os termos são basicamente
as mesmas encontradas em qualquer tesauro e descritas acima. No total são 96.992
relações estabelecidas entre os termos [Pontes, 2002].
2 http://www.fao.org/ 3 http://www.fao.org/waicent/
55
Após a introdução do uso do tesauro, o SBICafé passou a disponibilizar três
categorias de consultas através da Biblioteca Virtual do Café:
- Consulta Convencional
A Consulta Convencional proporciona as mesmas funcionalidades geralmente
encontradas nos mecanismos de busca textual na Web. Esta opção de consulta faz uso
do mecanismo de busca Microsoft Full Text Search para retornar os resultados assim
como o ranking de relevância dos itens retornados em relação à expressão de consulta.
São três as opções para a busca:
- Busca Lógica: o usuário fornece uma expressão de consulta que pode conter
os operadores AND, OR, NOT e NEAR. A precedência dos operadores na
expressão pode ser fixada com o uso de parêntesis. Caso o usuário forneça
uma seqüência de palavras (sem operador algum) o operador AND deverá ser
automaticamente incorporado. O usuário pode delimitar total ou
parcialmente a expressão com aspas duplas (“”), neste caso a sub-expressão
delimitada deverá ser considerada como frase exata.
- Texto Livre: o usuário fornece uma frase que é repassada diretamente para o
mecanismo de busca que aplica heurísticas para retornar os resultados com
base no significado geral da frase.
- Frase Exata: o usuário fornece uma seqüência de palavras que deve aparecer
na forma exata no conjunto de resultados. Esta opção tem o mesmo efeito do
uso de aspas duplas delimitando totalmente a expressão de consulta na opção
de Busca Lógica.
-
Após fornecer a expressão de consulta e a opção de busca, o usuário pode
selecionar um determinado item na interface contendo os resultados da consulta para ver
os seus detalhes que incluem resumo, autores e outras informações. A partir da interface
de apresentação de detalhes o usuário pode acessar o conteúdo completo do item.
- Consulta Guiada
Esta categoria de consulta foi projetada para uso mais específico por
especialistas do domínio, que ao informar um termo para busca, têm a oportunidade de
selecionar outros termos relacionados que são disponibilizados na interface a fim de
visualizar a sua árvore de relações, as quais são as relações definidas pela ontologia.
Assim, o usuário pode “navegar” na árvore de relações clicando no ícone 56
correspondente a cada termo. Esta ação tem o efeito de posicionar o respectivo termo na
raiz da árvore, exibindo assim uma nova árvore.
Ao “navegar” na árvore de relações, o usuário pode visualizar os detalhes de um
determinado conceito da árvore, que são compostos do status, idioma usado, escopo,
notas, e da tradução do conceito para os outros idiomas. Neste ponto o usuário pode
clicar sobre o conceito em um outro idioma, e assim alterar o idioma em uso pelo
sistema. Outra possibilidade é clicar no ícone que representa os itens de conhecimento,
no respectivo idioma, associados ao conceito. O resultado é a exibição dos itens, no
respectivo idioma, relacionados ao conceito.
– Consulta Cooperativa
A Consulta Cooperativa procura tirar proveito de vantagens oferecidas
isoladamente pelas duas opções de consulta apresentadas anteriormente (Consulta
Convencional e Guiada pela Ontologia), além de oferecer um grau muito maior de
cooperatividade com o usuário durante uma seção de consulta.
Assim como na Consulta Convencional, o usuário pode fornecer uma expressão
de consulta usando qualquer combinação válida dos operadores AND, OR, NOT, e
NEAR. A expressão fornecida é submetida a um processo de validação (parsing) no
qual as noise-words (palavras muito comuns como preposições, artigos etc.) são
retiradas e a expressão é convertida para a sintaxe do mecanismo de busca. Caso o
usuário forneça uma seqüência de palavras sem nenhum operador lógico, o operador
AND é automaticamente adicionado. A Figura 3.2 mostra a tela principal da opção de
Consulta Cooperativa onde o usuário seleciona o idioma a ser usado e fornece a
expressão de consulta.
57
Expressão de consulta analisada e
convertida.
Clicar para visualizar itens retornados
pela consulta inicial.
Para cada palavra pode-se selecionar o
termo da ontologia que melhor a
caracteriza.
Clicar para visualizar relações
envolvendo os termos selecionados.
Figura 3.2: Consulta Cooperativa.
O resultado da consulta é exibido na seção inferior esquerda da tela como pode
ser visto na Figura 3.2. Neste momento o usuário é informado sobre o número de itens
retornados e pode visualizá-los. Ao mesmo tempo, a expressão de consulta tem suas
palavras extraídas, e para cada palavra é feita uma consulta na ontologia a fim de
identificar os termos que o usuário tenha tentado representar usando a palavra-chave.
Como resultado é exibida, para cada palavra, uma lista de termos para a avaliação e
seleção por parte do usuário. A Figura 3.3 mostra o resultado da seleção do usuário
referente a consulta apresentada na figura anterior. O sistema exibe na seção central da
tela o mapeamento de cada palavra para o termo selecionado, assim como as relações
nas quais cada termo está envolvido de acordo com a ontologia.
58
Mapeamento da palavra para o termo “BALANÇO
HÍDRICO”.
Clicar para visualizar itens
relacionados ao termo.
Selecionar ou não Para expansão da consulta inicial.
Clicar para expandir a consulta
inicial com os termos selecionados e
executa-la.
Figura 3.3: Mapeamento de Palavras da Consulta para Termos da Ontologia.
Neste ponto o usuário tem a chance de ver todos os termos relacionados na
ontologia a cada termo resultante do mapeamento de cada palavra da consulta inicial e
selecionar aqueles que são adequados para a expansão da consulta. Aqueles termos que
possuem itens de conhecimento associados são exibidos pré-selecionados para a
avaliação do usuário que tem a chance de desmarcá-los caso sejam julgados não
significativos para a consulta. Não faz sentido a seleção de termos que não possuam
itens de conhecimento associados, mesmo que estes termos sejam significativos para a
consulta, visto que a expansão da consulta com os mesmos não traz nenhum efeito ou
benefício (como a melhoria da precisão ou cobertura da consulta). Neste momento o
usuário também pode visualizar os itens de conhecimento associados a um dado termo e
em seguida acessar os detalhes e o conteúdo dos itens. Para tanto basta clicar sobre o
número à direita do termo, que representa os itens de conhecimento associados.
A Figura 3.4 mostra a tela exibida a partir da seleção dos 25 itens de
conhecimento associados ao termo “EVAPOTRANSPIRAÇÃO” na figura acima.
59
Figura 3.4: Itens de Conhecimento Associados ao Termo da Ontologia.
Após avaliar os termos apresentados na seção central da tela (Figura 3.3) e
manter selecionados aqueles que foram julgados significativos para a consulta, o usuário
pode, clicando no botão Ok, solicitar a expansão da consulta a partir dos termos
selecionados. Para cada termo que foi identificado na ontologia para representar uma
palavra da expressão de consulta, os termos relacionados são adicionados através de
uma disjunção (operador OR) com a respectiva palavra usada na expressão de consulta.
Para o caso da Figura 3.3, a expansão foi a seguinte:
balanco AND hidrico
(balanco OR “evapotranspiracao” OR “agua” OR “murcha” OR “transpiracao”)
AND hidrico
O sistema executa a consulta expandida e exibe os resultados na seção inferior
direita da tela da Figura 3.5. Neste momento o usuário é informado sobre o número de
itens retornados pela nova consulta, assim como o número de itens adicionais, que não
foram retornados pela consulta inicial (antes da expansão), os quais representam o
ganho de cobertura da busca com o uso do tesauro [Pontes, 2002]. 60
Consulta
expandida.
Total de itens retornados.
Total de itens adicionais
retornados.
Clicar para visualizar todos os itens
retornados ou somente os itens
adicionais.
Figura 3.5: Resultado da Expansão da Consulta usando os Termos Selecionados.
A proposta de uma ferramenta tecnológica de apoio à gestão de conhecimento
no Portal SBICafé, a qual corresponde a uma aplicação que instancia o objetivo
específico desta dissertação, se baseia na análise dos registros de utilização da sua
máquina de busca com a finalidade de extrair conhecimento útil para os engenheiros
do domínio que mantêm a ontologia e para o próprio mecanismo de busca restrito ao
âmbito do portal, visando a personalização das relações com os seus visitantes e
favorecendo diretamente as atividades de gestão de conhecimento neste domínio.
Busca-se então, coletar os registros de navegação dos usuários através dos
documentos disponibilizados a partir de uma pesquisa feita ao mecanismo de busca da
Biblioteca Virtual do Café, bem como os registros de palavras-chave utilizadas, as
consultas expandidas pela utilização da ontologia, os respectivos documentos
resultantes e os documentos acessados pelos usuários. A partir de tais coleções de
dados, será feita a aplicação de um algoritmo de prospecção de dados que revele os
padrões de uso do mecanismo de busca do portal.
Para se realizar a proposta acima, dentre as possibilidades de buscas de
informações disponibilizadas pela Biblioteca Virtual do Café, será utilizada a categoria
61
Consulta Cooperativa, por ser esta uma modalidade que utiliza a ontologia incorporada
ao portal, provendo significado semântico às palavras-chaves introduzidas pelos
usuários, o que não ocorre na categoria de Busca Tradicional, além de não ser
direcionada a especialistas do domínio, o que ocorre na categoria de Busca Guiada pelo
Tesauro. Assim, esta categoria de busca, dentre as demais modalidades disponibilizadas
pelo portal, é a que apresenta características que mais se aproximam das expectativas
relacionadas à otimização de buscas nos portais da Web Inteligente. Após a prospecção
dos dados, deve-se gerar conhecimento útil para o mecanismo de busca –
disponibilizados para o re-ranqueamento mais apropriado dos resultados e outras
funções de personalização do portal - e para os engenheiros do domínio - com o
objetivo de prover-lhes o conhecimento necessário para a realização das manutenções
necessárias na ontologia, de acordo com as observações resultantes da utilização dos
fatos por ela estruturados. Assim, este trabalho apresenta uma ferramenta útil destinada
à descoberta e manutenção de padrões de acessos dos usuários do portal, podendo ser
aplicada no apoio à gestão de conhecimento deste domínio, buscando a otimização dos
processos de aquisição, manutenção e acesso às informações disponibilizadas.
Em um âmbito mais específico, a ferramenta proposta se caracteriza como uma
aplicação back-end, sendo composta por um processo off-line no qual são realizados o
processamento e armazenamento dos padrões de acesso dos usuários ao mecanismo de
busca da Biblioteca Virtual do Café, e um processo on-line onde os padrões gerados
serão utilizados. O processo on-line é subdividido em dois subprocessos representados
por: uma aplicação voltada para a manutenção semi-automática da ontologia
incorporada ao portal, através de conhecimentos fornecidos aos engenheiros do
domínio, e uma aplicação on-line automática, visando a disponibilização do
conhecimento necessário ao aprimoramento do mecanismo de busca, para que a partir
da utilização dos padrões encontrados, possa realizar um re-ranqueamento eficiente das
informações a serem disponibilizadas ao usuário, apresentando-lhes conteúdos mais
personalizados.
Tendo-se em vista estas considerações e os objetivos propostos, foi desenvolvido
um protótipo para dar suporte às funcionalidades previstas para a ferramenta destinada
ao portal, as quais podem ser visualizadas nos processos e fluxos destacados na Figura
3.6.
62
Resultados
Mecanismo de Consulta
Cooperativa
Palavra-Chave Re-ranqueamento
On-line Resultados Acessados
Usuário do
Portal Conhecimento (padrão) para
re-ranqueamento do
resultado Dados de Buscas
Arquivos de Logs
de Buscas
Prospecção dos Padrões de Consultas
Cooperativas Pré-Processamento Base de
Padrões de Acessos
à Consultas Cooperativas Informações
Consultas
Cooperativas Histórico das Consultas
Cooperativas
Parâmetros para Prospecção
Aplicação
de Apoio à Manutenção
da Ontologia
Dados de Pesquisa
Conhecimento
para Manutenção da Ontologia Padrões de Acesso
Engenheiros
do Domínio
Histórico de Consultas Cooperativas
Figura 3.6: Funcionalidades da Ferramenta Proposta.
63
A prospecção de uso da Web envolve questões de pré-processamento de dados
antes de se aplicar algoritmos de prospecção, além de serem necessárias o
desenvolvimento de técnicas e ferramentas para a análise dos padrões descobertos.
Seguindo-se as etapas citadas, as seguintes atividades devem ser executadas:
1) Obtenção e Pré-processamento (ou preparação) dos dados
Todas as interações do usuário com a máquina de busca da Biblioteca
Virtual do Café são registradas, mantendo-se o histórico de todas as buscas
realizadas no portal. Deve-se identificar o comportamento dos usuários em
relação às escolhas feitas por ele, sem que este o perceba, atualizando sua
base de conhecimento sobre o estereótipo correspondente. Nesta etapa, deve-
se realizar a leitura, filtragem e limpeza dos arquivos de log de busca do
portal, resultando nas sessões e transações úteis ao propósito da ferramenta.
Atualmente os logs de buscas realizadas no portal são compostos pelas
seguintes tabelas relacionais:
- Tabela Acesso
Esta tabela contém os acessos com status indicando não ocorrência de
qualquer tipo de falha.
Atributo Descrição IDAcesso Identificação única dos acessos feitos ao Portal SBICafé.
Este campo é composto pela concatenação do campo DataHora e SessionID.
DataHora Data e hora do acesso. SessionID Identificação única de um acesso de um usuário ao
SBICafé. IP Endereço IP do usuário. Browser Descrição do Browser Utilizado pelo usuário para acessar
o SBICafé. EmailPessoa E-mail do usuário, caso ele tenha informado este dado ao
se cadastrar no SBICafé. NomePessoa Nome do usuário, caso ele tenha informado este dado ao se
cadastrar no SBICafé.
Tabela 3.1: Estrutura da Tabela Acesso.
64
- Tabela Consulta
Nesta tabela estão apenas as consultas com status indicando a não ocorrência
de qualquer tipo de falha.
Atributo Descrição IDConsulta Identificador único de cada consulta realizada na
Biblioteca Virtual do Café. Cada registro da tabela Consulta possui um IDConsulta diferenciado,
IDAcesso Identificador do Acesso ao qual pertence cada consulta, sendo chave estrangeira relativa à tabela Acesso.
TipoConsulta Identificador do tipo de consulta sendo realizada em cada IDConsulta. Os valores que fazem parte do domínio deste campo podem ser visualizados na Tabela 3.4.
Chave Palavra-chave utilizada pelo usuário ao se executar uma consulta na Biblioteca Virtual do Café, ou a expressão representando a expansão da consulta, caso o usuário utilize este recurso.
NumRetorno Número representando a quantidade de resultados retornados pelo mecanismo de busca da Biblioteca Virtual do Café em resposta à busca realizada.
CodRetorno Conjunto de códigos das publicações retornadas pelo mecanismo de busca da Biblioteca Virtual do Café, sendo chave-estrangeira relativa à tabela Publicação que é exibida na Tabela 3.3.
Tabela 3.2: Estrutura da Tabela Consulta.
65
- Tabela Publicação
Além das tabelas citadas anteriormente, mantém-se uma tabela dos
documentos disponíveis, com toda a sua especificação.
Atributo Descrição CodPublicacao Identificação única de cada documento disponível no
SBICafé. CodTipoPublicacao Descreve o tipo de documento, podendo variar entre
artigo, dissertação de mestrado, etc. CodNucleo Descreve o núcleo de pesquisa do qual se originou o
documento. CodInstituicao Descreve a instituição da qual se originou o documento. CodEvento Descreve o evento para o qual o documento foi
elaborado. NumProjeto Descreve o projeto do qual o documento foi oriundo. AnoPublicacao Descreve o ano de publicação do documento. TemResumo Indica se o resumo do documento está disponível. TemConteudo Indica se o conteúdo do documento está disponível. TituloP Descreve o título do documento em português. AssuntoP Descreve o assunto tratado pelo documento em
português. ResumoP Descreve o resumo do documento em português. TituloI Descreve o título do documento em inglês. AssuntoI Descreve o assunto tratado pelo documento em inglês. ResumoI Descreve o resumo do documento em inglês. Referencia Descreve a referência bibliográfica do documento. DataCatalogacao Descreve a data em que o documento foi catalogado no
SBICafé. TituloSA Descreve o título do documento sem acentuação. AssuntoSA Descreve o assunto tratado pelo documento sem o uso de
acentuação. ResumoSA Descreve o resumo do documento sem acentuação. ReferenciaSA Descreve a referência bibliográfica do documento sem
acentuação.
Tabela 3.3: Estrutura da Tabela Publicação.
66
Na Tabela 3.4 pode-se visualizar o domínio de valores possíveis para o campo
TipoConsulta da Tabela Consulta.
TipoConsulta Descrição
Autor Palavra-chave usada na busca por autor (Busca Convencional).
PubAutor Código do Autor usado na busca por Autor (Busca Convencional).
PalChave/BL Busca Lógica com Palavra-chave (Busca Convencional).
PalChave/FE Busca Frase Exata com Palavra-chave (Busca Convencional).
PalChave/TL Busca Livre com Palavra-chave (Busca Convencional).
ConsGuida/EN Busca Guiada com Palavra-chave em Inglês (Busca Guiada).
ConsGuida/ES Busca Guiada com Palavra-chave em Espanhol (Busca Guiada).
ConsGuida/PT Busca Guiada com Palavra-chave em Português (Busca Guiada).
ConsGuida/ArvoreTermo Escolha da consulta com a própria palavra-chave da busca, clicando no número que a segue (Busca Guiada).
ArvoreTermo Opções apresentadas na árvore de termos relacionadas com palavra-chave da busca (Busca Guiada).
DocsTermo Documentos apresentados ao se escolher uma opção desejada.
DetalheTermo Escolha feita nos detalhes do termo relacionado (em qualquer idioma apresentado) escolhido na árvore de termos (Busca Guiada).
ConsCoop/EN Busca Lógica com palavra-chave em Inglês (Busca Cooperativa).
ConsCoop/ES Busca Lógica com palavra-chave em Espanhol (Busca Cooperativa).
ConsCoop/PT Busca Lógica com palavra-chave em Português (Busca Cooperativa).
ConsCoop_Expandida Busca Lógica Expandida (Busca Cooperativa Aprimorada).
ConsCoop_VerExpansão Resultados da Busca Lógica Cooperativa Expandida e não Expandida (Busca Cooperativa Aprimorada).
ConsCoop_VerAdicional Resultados somente da Busca Lógica Cooperativa Expandida (Busca Cooperativa Aprimorada).
ConsCoop_VerInicial Resultados da Busca Lógica Cooperativa não Expandida (Busca Cooperativa Aprimorada).
PubResumo Código do documento acessado em qualquer busca. Ultimas Últimos documentos catalogados.
67
Tabela 3.4: Domínio dos Valores Relacionados ao Campo TipoConsulta da
Tabela Consulta.
Os relacionamentos entre as tabelas do log de buscas podem ser melhor
visualizados na Figura 3.7:
IDConsulta
CodPublicacao
IDAcesso
0..N 1..1
0..N 0..N 0..N
1..N acessa
retorna Publicacao
Consulta Acesso tem
Figura 3.7: Relacionamentos entre as Tabelas do Log de Busca.
- Limpeza dos Dados
Uma entrada no log de busca do portal inclui os dados destinados à tabela
Acesso e à tabela Consulta, cujas amostras de registros podem ser
visualizadas nas Tabelas 3.5 e 3.6:
IDAcesso DataHora SessionID IP Browser EmailPessoa Nome
Pessoa
27/6/2002
14:53:41
#676635466
27/06/2002
14:53:41
676635466 200.17.79.42 Mozilla/4.0
(compatible;
MSIE 5.0;
Windows 98;
DigExt)
agn_alves
@yahoo.com
Agnaldo Alves
dos Santos
27/6/2002 14:18:20
#413013601
27/06/2002
14:18:20
413013601 200.18.136.59 Mozilla/4.0
(compatible;
MSIE 5.01;
Windows NT
5.0)
[email protected] Flavio
Vieira
Pontes
Tabela 3.5: Amostra da Tabela Acesso.
68
ID
Consulta IDAcesso TipoConsulta Chave
Num
Retorno CodRetorno
7680 27/6/2002
14:18:20
#413013601
PalChave/FE adubacao verde 19 155585_Art343 155984 25526_Art138
Art000029
...
7681 27/6/2002
14:53:41
#676635466
temperatura 261 Art000048 155585_Art080
155585_Art118 155537_Art048
...
7682 27/6/2002
14:18:20
#413013601
Ultimas 50 50 F0021 F0019 F0018 F0013 F0012
RBA_Art033
...
7683 27/6/2002
14:18:20
#413013601
ConsCoop/PT irrigacao 201 ...
7684 27/6/2002
14:18:20
#413013601
ConsCoop_VerInicial irrigacao 201 145933 155552 155585_Art070
103079 155537_Art209
...
7685 27/6/2002
14:18:20
#413013601
PubResumo 155552 1 155552
7686 27/6/2002
14:18:20
#413013601
DocsTermo FERTIRRIGACAO 44 155553 155556 155537_Art233
155552_Art13 155537_Art223
...
7687 27/6/2002
14:18:20
#413013601
DocsTermo FERTIRRIGACAO 44 155553 155556 155537_Art233
155552_Art13 155537_Art223
...
7688 27/6/2002
14:18:20
#413013601
PubResumo 155552 1 155552
7689 27/6/2002
14:18:20
#413013601
PubResumo 155556 1 155556
7690 27/6/2002
14:18:20
#413013601
ConsCoop_Expandida irrigacao 19 ...
7691 27/6/2002
14:18:20
#413013601
ConsCoop/PT irrigacao 201 ...
7692 27/6/2002
14:18:20
#413013601
ConsCoop_Expandida irrigacao 19 ...
7693 27/6/2002
14:18:20
#413013601
ConsCoop_Expandida (irrigacao OR
"FERTIRRIGACAO
" OR "REGA" OR
"AGUA")
20 ...
Tabela 3.6: Amostra da Tabela Consulta.
69
A eliminação de dados irrelevantes pode ser feita analisando-se o campo
TipoConsulta da tabela Consulta. Assim, as entradas na tabela Consulta que
não sejam relacionadas ao fluxo de execução de uma busca do tipo Consulta
Cooperativa na qual tenha se utilizado as relações do tesauro devem ser
removidas obtendo-se um histórico destas interações para serem utilizadas na
etapa de identificação de sessões e transações.
- Identificação dos usuários
A identificação do usuário é automática a partir do campo IDAcesso da
tabela Acesso, no entanto, para os propósitos da ferramenta, esta
identificação não é relevante.
- Identificação das sessões e transações
Deve ser considerada uma sessão, cada interação do usuário com o
mecanismo de busca da Biblioteca Virtual do Café, quando acessando a
categoria Consulta Cooperativa a partir de uma determinada palavra-chave
e utilizando o tesauro para expansão da consulta.
O processo de identificação de transações envolve o agrupamento dos
documentos acessados em cada sessão, criando uma seqüência de
documentos acessados em uma Consulta Cooperativa por uma determinada
palavra-chave e que tiveram uma determinada expansão.
Ao final do processo de identificação de sessões e transações, deve ser
gerado um conjunto composto por registros referentes a cada consulta
considerada, contendo o idioma utilizado na consulta, a palavra-chave, a
chave-expandida pelo tesauro e a seqüência ordenada de documentos
acessados, o qual servirá como entrada para a fase de descoberta de
padrões.
2) Descoberta dos padrões de acesso
A aplicação dos padrões de acesso descobertos é direcionada aos
engenheiros do domínio de conhecimento do portal e ao mecanismo de busca,
possibilitando a manutenção da ontologia incorporada ao portal e o
aprimoramento da efetividade das informações oferecidas aos usuários, ou
seja, apoiando o processo de gestão de conhecimento no portal. É nesta etapa
que são efetivamente aplicados os métodos e algoritmos de prospecção de 70
dados em busca de padrões úteis e significativos, utilizando-se a técnica de
prospecção de uso da Web estabelecida para o fim específico de descoberta de
padrões de acesso ao mecanismo de busca do portal. No entanto, uma das
mais difíceis tarefas em prospecção de dados é a determinação de qual dos
algoritmos disponíveis é mais adequado à solução de um determinado
problema [Wu, 2002].
Após o detalhamento das funcionalidades da ferramenta proposta, foram
estudadas diversas técnicas de prospecção de dados, na tentativa de se
identificar abordagens previstas para problemas similares. Assim, dentre as
técnicas de prospecção de dados, a prospecção de regras de associação foi,
inicialmente, a que mais se identificou com a solução desejada e foram
estudados diversos de seus algoritmos, apresentados no Apêndice A, na
tentativa de se conseguir uma adaptação viável para os propósitos previstos.
No entanto, como as abordagens desta técnica não consideram a ordem
original dos itens nas transações, o que é de essencial importância para a
funcionalidade de otimização das buscas no portal, nenhuma das tentativas de
adaptação se mostrou satisfatória. A outra técnica analisada foi prospecção de
padrões seqüenciais, a qual se mostrou adequada para se atingir as
funcionalidades propostas para a ferramenta. Desta forma, alguns algoritmos
desta técnica, apresentados no Apêndice A, foram estudados até que a
abordagem a ser utilizada para a resolução foi caracterizada como uma de
suas instâncias, especificamente voltada para a Prospecção de Padrões de
Acesso.
Essencialmente, um padrão de acesso Web, é um padrão seqüencial em
um grande conjunto de partes de logs da Web. Prospecção de padrões
seqüenciais, que é a descoberta de padrões freqüentes em bancos de dados de
seqüências, foi introduzida por [Agrawal & Srikant, 1995] como se segue:
dado um banco de dados composto por seqüências, onde cada seqüência é
uma lista de transações ordenadas pelo momento da transação e cada
transação consistindo de um conjunto de itens, o problema é encontrar todos
os padrões seqüenciais com um suporte mínimo especificado pelo usuário,
onde o suporte é o número de seqüências de dados que contém o padrão.
[Srikant & Agrawal, 1996] apresentaram um algoritmo destinado à descoberta
de padrões seqüenciais generalizados, denominado GSP. Tal algoritmo faz a
prospecção de padrões seqüenciais por múltiplas vezes inspecionar o banco de 71
dados de seqüências. Na primeira inspeção, ele encontra todos os 1-itens e
forma um conjunto de seqüências freqüentes de 1-elemento. Nas próximas
inspeções, ele gera seqüências candidatas a partir do conjunto de seqüências
freqüentes e testam seus suportes. Assim, como todos os algoritmos baseados
na abordagem Apriori, ele utiliza o método de geração e teste.
Algumas pesquisas tentam utilizar técnicas de prospecção de padrões
seqüenciais [Agrawal & Srikant, 1995], as quais são na maioria baseadas em
prospecção de regras de associação [Agrawal & Srikant, 1994], para descobrir
padrões de acesso a partir de logs da Web. Como o GSP, os demais resultados
desses esforços, são algoritmos baseados na heurística Apriori, a qual se
caracteriza pela necessidade de múltiplas inspeções na base de dados e,
portanto, quando o tamanho das seqüências aumenta e/ou o conjunto de dados
são grandes, tal abordagem encontra dificuldades. Assim, como este trabalho
se dedica à utilização da Prospecção de Uso da Web como uma técnica de
otimização de determinados serviços em um portal Web, é esperado que a
base de dados a ser utilizada possa ter um crescimento substancial, o que
indicou ser inviável o uso de tais algoritmos na tentativa de se alcançar os
objetivos propostos.
Desta forma, após a realização de outras pesquisas, foi localizado o
algoritmo WAP-mine [Pei et al., 2000], que se mostrou mais adequado ao
problema proposto e portanto, tornou-se o algoritmo escolhido para a sua
resolução. O algoritmo WAP-mine retorna o conjunto completo de padrões de
acesso sem redundância, apresentando vantagens significativas comparado
àqueles baseados em Apriori, sendo resultante de investigações sobre a
questão relacionada à prospecção eficiente de acessos de grandes conjuntos de
partes de logs da Web.
No geral, um log Web pode ser considerado como uma seqüência de
pares de identificadores de usuários e eventos. Na pesquisa de [Pei et al.,
2000], arquivos de log Web são divididos em partes para o propósito de
prospecção. Tarefas de pré-processamento podem ser aplicadas aos arquivos
de log Web originais, de forma que porções dos logs Web possam ser obtidas.
Cada porção de um de log Web é uma seqüência de eventos de um usuário ou
sessão em ordem ascendente de timestamp, isto é, eventos acontecidos
primeiro, vêm primeiro.
72
Tomando-se E como sendo um conjunto de eventos, uma porção de log
Web ou seqüência de acesso S= e1 e2 ... en (ei E) para 1≤ i≤ n é uma
seqüência de acesso, enquanto n representa o tamanho desta seqüência. Uma
seqüência de acesso com tamanho n é também chamada de uma n-seqüência.
Não é necessário que e
∈
i ≠ ej para i ≠ j em uma seqüência de acesso, ou seja,
repetições são permitidas. Por exemplo, aab e ab são duas seqüências de
acesso diferentes, em que a e b são dois eventos.
A seqüência S´= e´1 e´2 ... e´x é chamada de uma subseqüência da
seqüência S = e1 e2 ... en , e S uma superseqüência de S´, denotado como S´⊆
S, se e somente se, existe 1≤ i1 < i2 < ... < ix ≤ n, tal que , para
i≤ j≤ x. A seqüência de acesso S´ é uma subseqüência própria da seqüência S,
denotado como S´ ⊂ S, se e somente se S´ é uma subseqüência de S e S´ ≠ S.
jij ee =´
Em uma seqüência de acesso S= e1 e2... ek ek+1... en, se a subseqüência
Ssuffix = ek+1... en é uma superseqüência do padrão P = e´1 e´2... e´x e ek+1 = e´1,
a subseqüência de S, Sprefix = e1 e2... ek é denominado prefixo de S em relação
a P.
Dado um conjunto de seqüências de acesso WAS = { S1, S2, ... , Sm}, o
suporte de uma seqüência de acesso S em WAS é definido como supWAS(S) =
mSSS ii |}|{| ⊆
. Uma seqüência S é dita um ξ-padrão ou simplesmente um
padrão de acesso Web em WAS, se supWAS (S) ≥ . Embora eventos possam se
repetir em uma seqüência de acesso, seu suporte é no máximo uma vez
contabilizado nesta seqüência ou padrão.
ξ
O problema de prospecção de padrões de acesso pode ser assim
definido: dado um banco de dados de seqüências de acesso Web e um valor
de suporte, fazer a prospecção do conjunto completo dos padrões deste
conjunto que tenham o suporte suficiente.
Exemplo 1: Seja {a, b, c, d, e, f} um conjunto de eventos, e 100, 200, 300
e 400 identificadores de usuários. Um fragmento de log Web registra as
informações seguintes:
73
<100, a> <100, b> <200, e> <300, b> <200, a> <200,e> <100,d>
<400,a> <100, a> <400,f> <400, b> <300, a> <200,b> <100,c> <200, c>
<400, a> <200, a> <300, b> <200, c> <400, c> <400, f> <300, f>
<300,a> <300,e> <300, c> <400,c>
Um pré-processamento divide o arquivo de log em seqüências de acesso
de usuários individuais resultando no banco de dados de seqüências de acesso
WAS, mostrado nas duas primeiras colunas da Tabela 3.7.
Existe um total de 4 seqüências de acesso no banco de dados. A primeira
seqüência de acesso, abdac, é uma 5-seqüência, enquanto ab é uma
subseqüência dela. Na seqüência de acesso do usuário 200, ambos e e eaebc
são prefixos relativos a ac. Note que fc, aparece duas vezes na seqüência do
usuário 400, afbacfc, mas a seqüência contribui somente uma vez para a
contagem de fc.
ID do Usuário Seqüência de Acesso Web Subseqüência Freqüente
100 abdac abac
200 eaebcac abcac
300 babfaec babac
400 afbacfc abacc
Tabela 3.7: Seqüências de Acessos de Usuários Individuais.
O algoritmo WAP-mine para prospecção de padrões de acesso Web é
baseado na seguinte heurística:
Heurística de Sufixo: Se e é um evento freqüente no conjunto de prefixos
de seqüências em WAS, denotado como P, a seqüência eP é um padrão de
acesso de WAS.
Por exemplo, b é um evento freqüente dentro do conjunto de prefixos ac
no exemplo 1, então podemos dizer que bac é um padrão de acesso.
74
Basicamente, a idéia geral deste método pode ser resumida da seguinte
forma:
- Uma estrutura, denominada WAP-tree, registra compactamente as
seqüências de acesso e os respectivos contadores, ou seja, o número de
vezes que a seqüência aparece no banco de dados de seqüências. A
WAP-tree registra todas as informações necessárias para o resto da
prospecção. Uma vez que a estrutura de dados é construída, todo o
processo de prospecção restante é baseado na WAP-tree. O banco de
dados original de seqüências de acesso não é mais necessário para
inspeções. Como o tamanho da WAP-tree é geralmente muito menor
que o tamanho do banco de dados original de seqüências de acesso, o
processo de prospecção se torna mais fácil. A construção da WAP-tree é
totalmente eficiente por percorrer o banco de dados de seqüências de
acesso duas vezes.
- Um algoritmo recursivo eficiente é proposto para enumerar padrões de
acesso da WAP-tree. Nenhuma geração de candidatos é requerida no
procedimento de prospecção, e somente os padrões com suporte
suficiente serão considerados. A filosofia desse algoritmo de
prospecção é a busca condicional, que ao invés de procurar padrões de
forma nivelada como os algoritmos da abordagem Apriori, estreita o
espaço de busca por procurar por padrões com o mesmo sufixo, e faz a
contagem de eventos freqüentes no conjunto de prefixos, sendo um
método baseado no particionamento dividir para conquistar, que evita
gerar grandes conjuntos de candidatos.
A estrutura essencial do algoritmo WAP-mine é a seguinte. O algoritmo
inspeciona o banco de dados de seqüências de acesso duas vezes. Na primeira
inspeção, ele determina o conjunto de eventos freqüentes. Um evento é
chamado de freqüente se e somente se ele aparece em pelo menos (ξ . |WAS|)
seqüências de acesso de WAS, em que |WAS| e ξ denotam o número de
seqüências de acesso em WAS e o suporte mínimo, respectivamente. Os eventos
freqüentes relativos ao Exemplo 1, podem ser visualizados na terceira coluna da
Tabela 3.7. Na próxima inspeção, WAP-mine constrói uma árvore, chamada
WAP-tree, usando os eventos freqüentes, para registrar todas as informações de 75
contagem para a prospecção. então, WAP-mine, recursivamente, faz a
prospecção da WAP-tree usando busca condicional para encontrar todos os
padrões de acesso Web.
A estrutura essencial do algoritmo WAP-mine pode ser vista na Figura
3.8:
Entrada: banco de dados de seqüências de acesso WAS e um suporte mínimo
(0<ξ≤ 1). ξ
Saída: o conjunto completo dos ξ-padrões em WAS.
1. Inspecione WAS uma vez, encontrando todos os eventos freqüentes.
2. Inspecione WAS novamente, construindo uma WAP-tree sobre o conjunto
de eventos freqüentes.
3. Recursivamente faça a prospecção da WAP-tree usando busca condicional.
Figura 3.8: WAP-mine: Prospecção de Padrões de Acesso em Banco de Dados de Seqüências de Acesso.
Existem duas técnicas-chave neste método, a construção da WAP-tree e a
prospecção dos padrões de acesso da WAP-tree.
Construção da WAP-tree
As seguintes observações foram analisadas no projeto de uma árvore
altamente condensada de padrões de acesso Web.
-
-
De todas as 1-seqüências, somente aquelas freqüentes serão úteis na
construção de k-seqüências freqüentes para qualquer k>1. Assim, se
um evento e não está no conjunto de 1-seqüências freqüentes, não é
necessário incluir e na construção da árvore de padrões de acesso
Web.
Se duas seqüências de acesso compartilham um prefixo comum P, o
prefixo P pode ser compartilhado na WAP-tree. Tal
compartilhamento pode trazer algumas vantagens, como resguardar
algum espaço de armazenamento das seqüências de acesso e facilitar
a contagem de suporte de qualquer seqüência do prefixo P.
76
Baseando-se nas observações acima, a estrutura de Árvore de Padrões de
Acesso Web, ou WAP-tree , pode ser resumidamente definida da seguinte forma:
-
-
-
Cada nodo da WAP-tree registra duas informações: rótulo e
contador, denotados como rotulo:contador. A raiz da árvore é um
nodo virtual especial com um rótulo vazio e contador 0. Todos os
outros nodos são rotulados por um evento no conjunto de eventos E,
e associados com um contador que registra o número de ocorrências
do prefixo correspondente terminado com aquele evento no banco de
dados de seqüências de acesso Web.
A WAP-tree é construída da seguinte maneira: para cada seqüência
de acesso no banco de dados, filtra-se qualquer evento não freqüente,
e então se insere a subseqüência freqüente resultante na WAP-tree.
A inserção de subseqüências freqüentes é inicializada pela raiz da
WAP-tree. Considerando o primeiro evento, denotado como e,
incrementa-se os contadores dos nodos filhos com rótulo e de 1 se
eles existem; caso contrário, cria-se um filho rotulado com e e
inicializa-se seu contador com o valor 1. Então, recursivamente
insere-se o restante da subseqüência freqüente para a subárvore cujo
filho é rotulado e.
Estruturas auxiliares são construídas para facilitar a navegação
através dos nodos na árvore. Todos os nodos com o mesmo rótulo
são interligados através do compartilhamento de uma fila, chamada
fila de nodos-eventos. A fila de nodos-eventos com rótulo ei é
também chamada de ei-fila. Existe uma tabela de cabeçalhos H para
uma WAP-tree, e o início de cada fila de nodo-evento é registrada
em H.
Exemplo 2: Levando-se em consideração o banco de dados de seqüências
de acesso do exemplo 1, e supondo-se que o suporte mínimo seja 75%, isto é, é
requerido encontrar todos os padrões de acesso Web suportados pelo menos por
três seqüências de acesso no banco de dados. Uma inspeção no banco de dados
deriva o conjunto dos 1-eventos freqüentes: {a, b, c}. As subseqüências de
acesso freqüentes são listadas na coluna mais à direita da Tabela 3.7.
77
A WAP-tree é mostrada na Figura 3.9, e é construída da seguinte
maneira. Primeiro inseri-se a seqüência abac no início da árvore com apenas um
nodo raiz virtual. Cria-se um novo nodo (a:1) (isto é, rotula-se como a, com
contador igual a 1) como o filho da raiz e então se deriva o braço a “ (a:1) →
(b:1) → (a:1) → (c:1)”, em que as setas apontam dos nodos pais para os nodos
filhos. Segundo, inseri-se a segunda seqüência abcac, começando-se pela raiz.
Uma vez que a raiz tem um filho rotulado como a, o contador de a é
incrementado de 1, isto é (a:2), e similarmente, temos (b:2). O próximo evento,
c, não emparelha com o nodo existente a, e um novo nodo filho é criado e assim,
(c:1) é inserido. O processo de inserção das seqüências restantes pode ser
conseqüentemente derivado.
R a iz
c :1
b :3
a : 2
a : 3
a : 1
b :1
a : 1
b :1
c :1
a : 1 c :2
c :1
c :1
T a b e la d e C a b e ç a lh o s
a
b
c
W A P - t r e e
R a iz
b :3
a : 2
a : 3
a : 1
a : 1
b :1
b :1
T a b e la d e C a b e ç a lh o s
a
b
W A P - t r e e | c C o n d ic io n a l
78
Figura 3.9: WAP-tree e WAP-tree Condicional.
O algoritmo para a construção da WAP-tree para seqüências de acesso da
Web pode ser visualizado na Figura 3.10.
Entrada: Um banco de dados de seqüências de acesso Web WAS e o conjunto de
eventos freqüentes FE ( que é obtido pela inspeção de WAS uma vez).
Saída: Uma WAP-tree T.
Método:
1. Cria-se um nodo raiz para T;
2. Para cada seqüência de acesso S no banco de dados de seqüências de acesso
WAS faça:
a. Extrai-se subseqüências S´ de S pela remoção de todos os eventos que
aparecem em S, mas não estão em FE. Tomando-se S= s1 s2 ... sn, onde si,
1 ≤ i ≤ n, são eventos em S´.
b. Toma-se o nodo corrente apontando para a raiz de T.
c. Para i de 1 até n faça: se o nodo corrente tem um filho rotulado como si
então incremente o contador de si de 1 e faça o nodo corrente apontar para
si, senão, crie um novo nodo filho (si:1), fazendo o nodo corrente apontar
para o novo nodo, e insira-o na si-fila.
3. Retorne (T);
Figura 3.10: Construção da WAP-tree para Seqüências de Acesso Web.
A WAP-tree registra todos os contadores de seqüências de acesso. Como
será mostrado mais à frente, o processo de prospecção para todos os padrões de
acesso Web precisa trabalhar somente na WAP-tree, ao invés do banco de dados
original . Então, WAP-mine precisa inspecionar o banco de dados de seqüências
de acesso somente duas vezes. O tamanho da WAP-tree é no máximo o tamanho
das subseqüências freqüentes no banco de dados. A largura da WAP-tree, isto é,
o número de folhas na árvore, é limitado pelo número de seqüências de acesso
no banco de dados. Assim, WAP-tree pode não gerar um número explosivo de
nodos. Seqüências de acesso com mesmo prefixo compartilharão um pouco da
parte superior do caminho a partir da raiz. Estatisticamente, considerando o fator
de compartilhamento de prefixos, o tamanho da WAP-tree é muito menor que o
tamanho do banco de dados de seqüências de acesso.
79
Do algoritmo da Figura 3.10, pode-se observar um importante lema da
WAP-tree, que é o seguinte:
Lema 1: Para qualquer seqüência de acesso em um banco de dados de
seqüências de acesso WAS, existe um único caminho na WAP-tree começando
da raiz tal que todos os rótulos dos nodos no caminho são, em ordem,
exatamente os mesmos dos eventos da seqüência.
Este lema garante que o número de nodos folhas distintos bem como os
caminhos na WAP-tree não podem ser maior que o número de subseqüências
freqüentes no banco de dados de seqüências de acesso, e o tamanho da WAP-
tree é limitado por no máximo o número de instâncias de 1-eventos freqüentes
em um seqüência de acesso.
Prospecção de Padrões de Acesso Web da WAP-tree
A estrutura WAP-tree construída pelo algoritmo da Figura 3.10 provê
algumas propriedades interessantes que facilitam a prospecção de padrões de
acesso Web.
Propriedade de ligação de nodos: Para qualquer evento freqüente ei,
todos as subseqüências freqüentes contendo ei podem ser visitadas seguindo-se a
ei-fila, começando do registro para ei na tabela de cabeçalhos da WAP-tree.
A propriedade acima facilita o acesso às informações dos padrões
relacionados ao evento freqüente ei por seguir todos os ramos na WAP-tree
ligados pela ei-fila, somente uma vez. Para qualquer nodo rotulado ei em uma
WAP-tree, todos os nodos no caminho da raiz da árvore para este nodo formam
uma seqüência de prefixos de ei . O contador deste nodo rotulado ei é chamado
de contador da seqüência de prefixos.
Note que o caminho da raiz pode ter mais que um nodo rotulado ei,
assim, uma seqüência de prefixos de ei pode conter uma outra seqüência de
prefixos de ei . Por exemplo, a seqüência aba é uma seqüência de prefixos de b
em abab, contendo uma outra seqüência de prefixos de b, que é a. Quando
contamos ab na seqüência abab, devemos ter certeza de não estar contando em
80
dobro, isto é, abab contribui somente com 1 para o contador de ab. Isto é
conseguido pelo conceito de contador não-acumulado. como mostrado a seguir.
Tomando-se G e H sendo duas seqüências de prefixos de ei e G sendo
também formado pelos subcaminhos da raiz da qual H é formada, H é chamada
de superseqüência de prefixo de G, e G é uma subseqüência de prefixo de H. Por
exemplo, aba é uma superseqüência de prefixo de a.
Para uma seqüência de prefixos de ei sem quaisquer superseqüência de
prefixos, definimos o contador não-acumulado daquela seqüência como o seu
contador. Para uma seqüência de prefixos de ei com as algumas superseqüências
de prefixos, o seu contador não-acumulado é o contador da seqüência menos os
contadores não-acumulados de todas as suas superseqüências de prefixos. Por
exemplo, tomando S= (a:6) → (b:5) → (a:2) → (b:2) sendo um caminho da raiz,
o contador não-acumulado do primeiro a, uma seqüência de prefixos de b, deve
ser 3 ao invés de 5, uma vez que 2 do total de 5 contadores no primeiro nodo b
são dedicados à superseqüência de prefixo aba de a.
Propriedade do contador não-acumulado de seqüências de prefixos: O
contador de uma seqüência G terminada com ei é a soma dos contadores não-
acumulados de todas as seqüências de prefixos de ei que sejam uma
superseqüência de G.
Baseando-se nas duas propriedades anteriores, podemos aplicar a busca
condicional para a prospecção de padrões de acesso da Web usando WAP-tree.
Busca condicional significa que, ao invés de procurar por todos os padrões de
acesso de cada vez, é feita a busca pelos padrões de acesso da Web com o
mesmo sufixo. Sufixo é usado como a condição para estreitar o espaço de busca.
À medida que o sufixo se torna maior, o espaço de busca restante torna-se
potencialmente menor.
O paradigma de busca condicional tem algumas vantagens quando
comparado àqueles baseados em Apriori. A propriedade de ligação dos nodos da
WAP-tree assegura que, para qualquer evento freqüente ei todas as seqüências
com sufixo ei podem ser visitadas eficientemente usando a ei-fila da árvore. Por
outro lado, a propriedade de contador não-acumulado da seqüência de sufixos
assegura que para contar todos os eventos freqüentes no conjunto de seqüências
com mesmo sufixo, somente a preocupação com o contador não-acumulado é 81
suficiente. Isto simplifica as operações de contagem. Estas duas propriedades da
WAP-tree tornam a busca condicional eficiente.
A estrutura básica da prospecção de todos os padrões freqüentes em uma
WAP-tree é a seguinte. Se a WAP-tree tem somente um ramo, todas as
combinações ordenadas de eventos no ramo são todos os padrões de acesso Web
na árvore. Assim, o que precisa ser feito é somente retornar o conjunto completo
de tais combinações. Caso contrário, para cada evento freqüente ei na WAP-tree,
seguindo-se a ei-fila começando da tabela de cabeçalhos, uma base ei-
condicional de seqüência de acesso é construída, denotada por PS|ei, que contém
todas e somente todas as seqüências de ei. Cada seqüência de prefixo em PS|ei
tem seu contador proveniente da WAP-tree. Para cada seqüência de prefixo de ei
com contador c, quando ela é inserida em PS|ei, todas as subseqüências de
prefixos de ei são inseridas em PS|ei com contador -c. Por considerar os
contadores de seqüências de prefixos, uma seqüência de prefixo em PS|ei possui
seu contador não acumulado.
Assim, pode-se fazer a prospecção do conjunto completo de padrões de
acesso Web que são seqüências de prefixo de ei pela concatenação de ei a todos
os padrões de acesso Web retornados pela prospecção da WAP-tree condicional,
e o próprio ei, o que pode ser visualizado na Figura 3.11:
82
Entrada: uma WAP-tree T e um suporte mínimo ξ.
Saída: o conjunto completo de ξ-padrões.
Método:
1. se a WAP-tree T tem somente um ramo então retorne todas as combinações
únicas de nodos naquele ramo.
2. Inicialize o conjunto de padrões de acesso Web WAP=∅. Cada evento em
WAP-tree T, que por ele mesmo seja um padrão de acesso Web, é inserido
em WAP.
3. Para cada evento ei em WAP-tree T faça
a. construa uma base condicional de seqüências de ei , isto é PS|ei seguindo
a ei-fila, contando os eventos freqüentes condicionais ao mesmo tempo.
b. se o conjunto de eventos freqüentes condicionais não é vazio então
construa uma WAP-tree condicional para ei sobre PS|ei usando o
algoritmo descrito na Figura 3.10. Recursivamente faça a prospecção da
WAP-tree condicional.
c. para cada padrão de acesso Web retornado da prospecção da WAP-tree
condicional faça concatene ei a ele e insira-o em WAP.
4. Retorne WAP
Figura 3.11: Prospecção de Todos os Padrões Freqüentes em uma WAP-tree.
Para diminuir o impacto do tamanho dos bancos de dados, deve ser
utilizada uma medida de suporte, que é o percentual de transações que contém
determinado padrão.
Exemplo 3: Tomando-se a prospecção dos padrões de acesso da Web na WAP-
tree da Figura 3.9 e supondo-se que o suporte mínimo é 75%, começamos a
busca condicional para o evento freqüente c. A base condicional de seqüências c
é: aba :2, ab:1, abca:1, ab:-1, baba:1, abac:1, aba:-1
Para ser qualificado como um evento freqüente, um evento deve ter
contador 3. Por esta razão, os eventos freqüentes condicionais são a(4) e b(4).
Então, uma WAP-tree condicional, WAP-tree | c, é construída, como mostra a
Figura 3.9.
83
Recursivamente, as bases de seqüências condicionais de ac e bc são
construídas e feitas as prospecções das WAP-trees condicionais. Neste ponto, a
busca condicional de c termina, e usamos os outros eventos freqüentes, para
encontrar todos os outros padrões de acesso da Web.
Seguindo as propriedades apresentadas adiante e considerando a
enumeração de padrões de acesso do algoritmo da Figura 3.11, a corretude do
WAP-mine pode ser mostrada.
Teorema 1: WAP-mine retorna o conjunto completo de padrões de
acesso sem redundância.
A prospecção de padrões de acesso Web usando WAP-tree tem
vantagens significativas. Primeiro, a WAP-tree é uma estrutura de dados eficaz.
Ela registra todas as informações dos contadores para a prospecção de padrões, e
livra o processo de prospecção da contagem de candidatos pelo casamento de
padrões. Segundo, a estratégia de busca condicional estreita o espaço de busca
eficientemente, e faz um melhor uso da estrutura da WAP-tree. Isto evita o
problema de geração explosiva de candidatos como acontece em algoritmos
como o Apriori [Pei et al., 2000].
3) Análise e Utilização dos Padrões
A análise e utilização dos padrões de acesso serão feitas através da
comparação entre o conhecimento descoberto acerca da utilização da
ontologia nas consultas cooperativas realizadas no portal com as perspectivas
que os engenheiros do domínio possuem sobre como elas deveriam ser
utilizadas. Esta comparação será facilitada a partir do desenvolvimento de
uma aplicação de software a ser utilizada pelos engenheiros do domínio. A
análise deste conhecimento possibilitará a utilização do conhecimento
descoberto visando a efetiva melhoria na tarefa de manutenção da ontologia
incorporada ao portal, com o objetivo que esta sempre represente as reais
necessidades de seus usuários.
Outra forma de análise e utilização dos padrões será realizada a partir da
disponibilização ao mecanismo de Busca Cooperativa dos padrões de acesso
identificados, possibilitando sua utilização em termos de re-ranqueamento
baseado na filtragem colaborativa dos resultados. Neste caso, de acordo com 84
uma determinada busca, o mecanismo de busca tem à disposição uma
seqüência ordenada de identificações dos documentos acessados, de acordo
com o grau de sua importância para os usuários. Tal seqüência deve ser
utilizada pelo mecanismo de Busca Cooperativa em sua política de re-
ranqueamento dos resultados, inferindo objetivos e planos do usuário,
apresentando-lhe os documentos relevantes, ordenados de acordo com os
padrões gerados pela ferramenta.
85
A Figura 3.12 demonstra mais especificamente as etapas do processo
proposto para apoio à Gestão de Conhecimento no portão SBICafé
implementadas pela ferramenta:
Para cada palavra pod
termo da ontologia
caracter
Informações
Histórico das Consultas
Cooperativas
Parâmetros
Parâmetros Conhecimento
para Filtragem
Colaborativa
Engenheiros
do Domínio do Portal
Mecanismo
de Busca do
Portal
Padrões de Acesso a Consultas
Cooperativas
Aplicação On-line de
Pós-Processamento para Manutenção da
Ontologia
Prospecção de Padrões de Acesso
à Consultas Cooperativas
(algoritmo WAP-mine)
Pré-Processamento dos Dados
Obtenção dos Registros de Acessos ao
Mecanismo de Busca do Portal
Histórico de Consultas
Cooperativas
Aplicação On-line Automática de Pós-
Processamento para Re-ranqueamento de
Resultados de Consultas Cooperativas
Figura 3.12: Etapas Específicas do Processo Proposto para Apoio à Gestão de Conhecimento no Portal Web.
86
4 – Projeto
Neste capítulo é apresentado o projeto da solução de acordo com a proposta
apresentada no capítulo anterior. São assim apresentadas as funcionalidades da
ferramenta a ser implementada, sua metodologia de projeto, bem como as interações e
recursos tecnológicos a serem utilizados em sua implementação.
4.1 – Funcionalidades e Casos de Uso
Nesta seção são apresentadas as funcionalidades da ferramenta a ser
implementada, sendo apresentados os seus atores e os principais casos de uso. Para
apresentar os casos de uso será adotada a notação sugerida pela UML (Unified
Modeling Language) [Booch et al., 1998].
Mecanismo de Busca da Biblioteca Virtual do Café
Engenheiros do Domínio do SBICafé
1. Acessa Arquivos de Log de Buscas
3. Faz Prospecção de Padrões de Consultas Cooperativas
5. Gera Conhecimento para Mecanismo de Busca
4. Gera Conhecimento para Manutenção da Ontologia
2. Faz Pré-processamento
<<uses>>
<<uses>>
<<uses>>
<<uses>>
<<uses>>
Figura 4.1: Diagrama de Casos de Uso.
87
A seguir são apresentadas as descrições de cada um dos casos de uso da
ferramenta proposta, mostrados na Figura 4.1.
1. Acessa Arquivos de Log de Buscas: Periodicamente, observando-se os
intervalos de tempo determinados pelos Engenheiros do Domínio do SBICafé, o
módulo de Prospecção de Padrões de Consultas Cooperativas obtém os dados
dos arquivos de log do Mecanismo de Busca da Biblioteca Virtual do Café para
a atualização da base de Padrões de Consultas Cooperativas e do Histórico de
Consultas Cooperativas. Veja a Figura 4.2.
1 – Acessa Arquivos de Log de Buscas
Atores
É um caso de uso temporal automático
Pré-Condições
É momento de atualizar a base de conhecimento sobre os Padrões de
Acesso às Consultas Cooperativas da Biblioteca Virtual do Café.
Fluxo de Eventos
Principal
1. Após cada período de tempo, pré-determinado pelos Engenheiros do
Domínio do SBICafé através da definição dos parâmetros para
prospecção, o módulo de Prospecção de Padrões de Consultas
Cooperativas acessa os arquivos de Log atualizados pertencentes ao
Mecanismo de Busca da Biblioteca Virtual do Café e recupera os dados
inseridos desde o seu último acesso.
Pós-Condições
O módulo de Prospecção de Padrões de Consultas Cooperativas tem os
dados atualizados dos arquivos de log do Mecanismo de Busca da Biblioteca
Virtual do Café.
Figura 4.2: Caso de uso “1 - Acessa Arquivos de Log de Buscas”.
88
2. Faz Pré-processamento: Após a obtenção dos Arquivos de Log de Buscas da
Biblioteca Virtual do Café, o módulo de Prospecção de Padrões de Consultas
Cooperativas realiza a etapa de pré-processamentos, executando as tarefas de
limpeza dos dados obtidos, selecionando os dados relacionados a Consultas
Cooperativas, gerando o Histórico das Consultas Cooperativas, identificando as
sessões e transações referentes a cada uma das Consulta Cooperativa realizada
com o uso do tesauro e gerando a entrada para o processo de Prospecção de
Padrões. Veja a Figura 4.3.
2 – Faz Pré-processamento
Atores
É um caso de uso temporal automático
Pré-Condições
O módulo de Prospecção de Padrões de Consultas Cooperativas tem os
dados atualizados dos arquivos de log do Mecanismo de Busca da Biblioteca
Virtual do Café.
Fluxo de Eventos
Principal
1. O módulo de Prospecção de Padrões de Consultas Cooperativas realiza
as tarefas de pré-processamento, acessando os dados atuais obtidos do
log do Mecanismo de Busca da Biblioteca Virtual do Café, tendo como
primeira etapa a limpeza dos dados, selecionando os registros
correspondentes às Consultas Cooperativas.
2. Após a limpeza dos dados, é atualizado o Histórico de Consultas
Cooperativas sendo identificados os registros relacionados a cada
Consulta Cooperativa realizada.
Pós-Condições
O módulo de Prospecção de Padrões de Consultas Cooperativas contém os
dados atuais das Consultas Cooperativas que utilizaram o tesauro e o Histórico de
Consultas Cooperativas está atualizado.
Figura 4.3: Caso de uso “2 - Faz Pré-processamento”.
89
3. Faz Prospecção de Padrões de Consultas Cooperativas: Após a obtenção dos
dados das atuais Consultas Cooperativas, o módulo de Prospecção de Padrões de
Consultas Cooperativas realiza a etapa de descoberta/atualização de padrões
utilizando o algoritmo WAP-mine. Veja a Figura 4.4.
3 – Faz Prospecção de Padrões de Consultas Cooperativas
Atores
É um caso de uso temporal automático
Pré-Condições
O módulo de Prospecção de Padrões de Consultas Cooperativas contém os
dados das atuais Consultas Cooperativas.
Fluxo de Eventos
Principal
1. O módulo de Prospecção de Padrões de Consultas Cooperativas realiza
as tarefas de descoberta de padrões de acesso, executando o algoritmo
WAP-mine .
2. Após a execução da prospecção de dados propriamente dita, os padrões
gerados são armazenados/atualizados na Base de Padrões de Consultas
Cooperativas.
Pós-Condições
A Base de Padrões de Consultas Cooperativas contém os atuais padrões de
acesso referentes a esta categoria de consulta.
Figura 4.4: Caso de uso “3 - Faz Prospecção de Padrões de Consultas Cooperativas”.
90
4. Gera Conhecimento para Manutenção da Ontologia: Os Engenheiros do
Domínio acessam a aplicação de software destinada à Descoberta de
Conhecimento para a Manutenção da Ontologia. Veja a Figura 4.5.
4 – Gera Conhecimento para Manutenção da Ontologia
Atores
Engenheiros do Domínio do SBICafé
Pré-Condições
Os Engenheiros do Domínio do SBICafé acessam a aplicação destinada à
Descoberta de Conhecimento para a Manutenção da Ontologia.
Fluxo de Eventos
Principal
1. Os Engenheiros do Domínio indicam a opção de pesquisa de acordo
com o conhecimento desejado.
2.A aplicação destinada à Descoberta de Conhecimento para a Manutenção
da Ontologia é executada.
3. A aplicação retorna os devidos resultados a partir da Base de Padrões de
Consultas Cooperativas e do Histórico de Consultas Cooperativas.
Pós-Condições
Os Engenheiros do Domínio possuem o conhecimento necessário para
auxílio à tarefa de Manutenção da Ontologia incorporada ao SBICafé.
Figura 4.5: Caso de uso “4 - Gera Conhecimento para Manutenção da Ontologia”.
91
5. Gera Conhecimento para Mecanismo de Busca: Com o propósito de re-
ranqueamento dos resultados de uma Consulta Cooperativa que utilize o
tesauro, o Mecanismo de Busca da Biblioteca Virtual do Café acessa os padrões
contidos na Base de Padrões de Consultas Cooperativas. Veja a Figura 4.6.
5 – Gera Conhecimento para Mecanismo de Busca
Atores
Mecanismo de Busca da Biblioteca Virtual do Café
Pré-Condições
Um usuário do portal faz uma consulta cooperativa utilizando o tesauro.
Fluxo de Eventos
Principal
1. O mecanismo de busca recebe um requisição de Consulta Cooperativa
utilizando o tesauro.
2. A aplicação destinada à descoberta de Conhecimento para Mecanismo
de Busca é executada.
3. A aplicação retorna o atual padrão de acesso relativo à consulta que está
sendo executada, a partir de uma pesquisa na Base de Padrões de
Consultas Cooperativas.
Alternativo
2. Caso não se tenha um padrão relacionado à busca sendo realizada,
nenhum conhecimento é retornado.
Pós-Condições
O Mecanismo de Busca Cooperativa da Biblioteca Virtual do Café possui o
conhecimento necessário para a tarefa de re-ranqueamento dos resultados
provenientes de sua atual política de buscas.
Figura 4.6: Caso de uso “5 - Gera Conhecimento para Mecanismo de Busca”.
92
4.2 – Projeto Lógico
Nesta seção será apresentado o projeto da ferramenta de acordo com as
funcionalidades apresentadas nos casos de usos descritos na seção anterior. Tal projeto
será representado pelo diagrama de classes da ferramenta, desenvolvido usando a
notação sugerida pela UML (Unified Modeling Language) [Booch et al., 1998].
4.2.1 – Diagrama de Classe UML
Apresenta-se aqui o Diagrama de Classes na Figura 4.7 que mostra as principais
classes do sistema (classes persistentes) e suas relações.
Padrões de Consultas Cooperativas BasedePadrõesdeConsultasCooperativas ParâmetrosWAP-mine
AcessaArquivosdeLogdeBuscas() FazPré-Processamento() FazProspecçãodePadrõesdeConsultasCooperativas() GeraConhecimentoParaManutençãodaOntologia() GeraConhecimentoParaMecanismodeBusca()
Mecanismo de Busca da Biblioteca Virtual do Café UtilizaConhecimentodeConsultasCooperativas()
Disponibiliza Padrões
Engenheiros do Domínio do SBICafé
DeterminaParâmetrosParaProspecçãodeConsultasCooperativas() AnalisaConhecimentoParaManutençãodaOntologia()
Utilizam Padrões
Arquivos de Log de Buscas TabelaAcessos TabelaConsultas TabelaPublicações
Faz Prospecção
Mantêm
Utilizam Histórico
Histórico de Consultas Cooperativas
Figura 4.7: Diagrama de Classes da Ferramenta.
93
4.3 – Interações e Recursos Tecnológicos
Esta seção apresenta as principais interações da ferramenta proposta, assim
como os principais recursos tecnológicos a serem usados na sua implementação.
Informações Portal SBICafé
SGBD
Servidor de Aplicação Web
Conhecimento para
Manutenção da Ontologia
Prospecção de Padrões de
Consultas Cooperativas
Engenheiros do Domínio do SBICafé
Aplicação de Geração de Conhecimento para
Mecanismo de Busca
Aplicação de Geração de Conhecimento
para Manutenção da Ontologia
Usuário do SBICafé
Interfaces de Consulta e Navegação
Mecanismo de
Busca do
SBICafé
Base de Padrões
de Acesso a Consultas
Cooperativas
Logs de
Busca
Figura 4.8: Principais Interações da Ferramenta Proposta. 94
A Figura 4.8 apresenta as principais interações da ferramenta. Todo o acesso à
ferramenta poderá ser feito via Internet, (usando TCP-IP / HTTP) através de um
navegador Web padrão.
O Processo de Prospecção de Padrões de Consultas Cooperativas será executado
off-line, porém automaticamente em períodos de tempos pré-determinados, mantendo-se
atualizada a Base de Padrões de Consultas Cooperativas.
A Aplicação de Geração de Conhecimento para Mecanismo de busca da
Biblioteca Virtual do Café será executada on-line automaticamente sempre que o
usuário acessar o portal SBICafé com o objetivo de realização de uma Consulta
Cooperativa com a utilização do tesauro.
A Aplicação de Geração de Conhecimento para Manutenção da Ontologia será
executada on-line a partir de necessidade explícita dos Engenheiros do Domínio do
SBICafé.
O portal SBICafé fica abrigado no Servidor de Aplicações Web, o qual deverá
também abrigar o Processo de Prospecção de Consultas Cooperativas. Já a Aplicação de
Geração de Conhecimento para Manutenção da Ontologia deve ser incorporada ao
SBICafé, tendo seu acesso restrito aos Engenheiros do Domínio do portal . O servidor
usado no SBICafé é o Microsoft Information Server 5.0 rodando sob o sistema
operacional Windows 2000 Server. O Mecanismo de Busca que representa um
importante componente do portal é o Microsoft Full Text Search Engine que faz parte
do sistema operacional Windows 2000 Server, e este mecanismo deverá usar a
Aplicação de Geração de Conhecimento para Mecanismo de Busca para ter a
possibilidade de acessar a Base de Padrões de Consultas Cooperativas sempre que
necessário. O SGBD (Sistema Gerenciador de Banco de Dados) que já abrigava todos
os dados utilizados no Portal do Café é o Microsoft SQL Server 2000, que também irá
abrigar a Base de Padrões de Acesso a Consultas Cooperativas e o Histórico de
Consultas Cooperativas.
O componente mais importante da ferramenta proposta e que merece atenção
especial é o Processo de Prospecção de Padrões de Consultas Cooperativas. Sua
estrutura interna e abrangência certamente vão influenciar profundamente o
desempenho da ferramenta no que diz respeito à eficácia no suporte ao processo de
gestão do conhecimento, mais especificamente nas atividades de geração/manutenção
dos padrões de acesso, utilização na aplicação de software destinada aos engenheiros do
domínio e na disponibilização dos padrões para o mecanismo de busca.
95
O Processo de Prospecção de Padrões de Acessos às Consultas Cooperativas foi
implementado utilizando-se a linguagem Delphi, bem como as interfaces de utilização
da Base de Padrões de Acesso a Consultas Cooperativas gerada. A interface entre o
Mecanismo de Busca da Biblioteca Virtual do Café e a Base de Padrões de Acesso é
realizada através de uma aplicação de software que a partir da base de conhecimento
composta pelos padrões gerados, retorna para uma determinada palavra-chave usada em
uma Consulta Cooperativa que utilize o tesauro, o padrão de acesso correspondente, que
pode ser utilizado para o re-ranqueamento dos resultados originais do mecanismo de
busca, refletindo os atuais interesses dos usuários da Consulta Cooperativa. A interface
entre os Engenheiros do Domínio, a Base de Padrões de Acessos e o Histórico de
Consultas Cooperativas se dá através de uma aplicação de software disponível no Portal
SBICafé, que a partir do Histórico das Consultas Cooperativas realizadas e da Base de
Padrões de Acesso proporciona as reais interpretações do comprometimento ontológico
por eles designados, demonstrando as possíveis necessidades de manutenções na
ontologia incorporada ao portal.
96
5 – Implementação e Resultados
Este capítulo apresenta a implementação do sistema proposto, suas
funcionalidades, assim como os resultados obtidos. São apresentadas inicialmente as
funcionalidades que tratam da manutenção do sistema, ou seja, as tarefas que são
relacionadas às atividades primordiais ao funcionamento do mesmo, e que incluem as
etapas de acesso, pré-processamento e de prospecção de padrões. Tais funcionalidades
correspondem às principais atividades da ferramenta proposta. Em seguida são
apresentadas as funcionalidades que tratam das utilizações dos padrões de acesso
descobertos nas etapas anteriores, estando assim explicitadas uma simulação da
aplicação dos padrões a serem utilizados pelo mecanismo de busca para apoiar o re-
ranqueamento dos documentos retornados aos usuários do portal ao realizarem uma
Consulta Cooperativa, e a aplicação a ser utilizada pelos engenheiros do domínio como
apoio à sua tarefa de manutenção da ontologia incorporada ao SBICafé. Em seguida,
são apresentadas as interfaces destas aplicações e ao final são discutidos os resultados
obtidos.
5.1 – Processo de Prospecção de Padrões de Consultas Cooperativas
O módulo responsável pelo Processo de Prospecção de Padrões de Consultas
Cooperativas realiza as etapas de prospecção de dados citadas no Capítulo 3, que são
implementadas de acordo com os casos de uso determinados no Capítulo 4, sendo o
módulo executado off-line automaticamente em determinados períodos de tempo.
A periodicidade da execução deste módulo é determinada por um parâmetro
informado pelos engenheiros do domínio, em uma opção denominada Utilitários,
existente na interface principal da aplicação, que pode ser visualizada na Figura 5.1.
97
Figura 5.1: Interface Utilitários.
Ao se selecionar a opção Periodicidade dos Padrões, é apresentada a interface da
ferramenta que possibilita a pré-determinação dos dias da semana e horários em que
todas as etapas do processo de Prospecção de Padrões de Consultas Cooperativas serão
automaticamente executadas. Tal interface pode ser visualizada na Figura 5.2.
Figura 5.2: Interface para Determinação da Periodicidade.
98
Além da periodicidade, a opção Utilitários permite informar o valor de suporte a
ser utilizado pelo algoritmo WAP-mine na tarefa de descoberta de padrões. O valor de
suporte indica a porcentagem de buscas em que uma determinada seqüência de acesso
deve aparecer para ser considerada uma seqüência freqüente. Para se determinar este
valor o usuário deve escolher a opção Suporte dos Padrões, cuja interface pode ser
visualizada na Figura 5.3.
Figura 5.3: Interface para Determinação de Suporte.
O valor de suporte, a ser determinado, pode variar no domínio de valores reais
no intervalo ]0, 1]. Este valor, na ferramenta proposta, será utilizado na fase de
descoberta de padrões, para se verificar as seqüências de acesso à documentos
consideradas freqüentes em cada grupo de buscas, constituídos pelas tuplas (Idioma +
Chave + ChaveExpandida), e as seqüências de acesso à ontologia, considerando-se as
tuplas (Idioma + Chave). A escolha de um suporte com valor muito próximo a 0 (zero),
implica considerar praticamente todas as seqüências acessadas em um grupo de buscas
como freqüentes, já o valor 1 (um) implica que uma seqüência para ser considerada
freqüente, deve ter sido acessada em todas as ocorrências de um grupo de buscas.
Assim, na grande maioria dos exemplos encontrados na literatura, o valor típico de
suporte está entre 0.5 e 0.75, sendo um valor mediano entre os extremos citados.
99
A aplicação proporciona em sua interface principal, que pode ser visualizada na
Figura 5.4, a opção de simulação de todas as etapas do módulo responsável pelo
Processo de Prospecção de Padrões de Acesso a Consultas Cooperativas, bastando o
usuário escolher a opção Simulação de Prospecção.
Figura 5.4: Interface Principal da Aplicação.
Ao se escolher a opção Simulação de Prospecção, as etapas do processo de
Prospecção de Padrões de Consultas Cooperativas são simuladas, conforme descrito a
seguir:
1 – Acessa Arquivos de Log de Buscas
Esta tarefa corresponde à fase de obtenção de dados. As tabelas dos
arquivos de Log de Busca estão sempre disponíveis no servidor do SBICafé,
bastando recuperar os dados das consultas realizadas a partir do último
acesso a estes arquivos. Ao se recuperar os dados dos logs, é criada uma
cópia da tabela Consulta, denominada TabHistórico, ordenada pelos campos
(IDAcesso + IDConsulta), e que será utilizada nas próximas etapas, além de
100
guardar informações importantes para a manutenção da ontologia. Caso a
tabela TabHistórico já exista, esta é atualizada com os dados das novas
consultas realizadas.
As atividades pertinentes a este passo do processo são executadas por
uma rotina denominada AcessarLog, cuja interface de simulação de sua pós-
execução pode ser visualizada na Figura 5.5.
Figura 5.5: Interface de Simulação da Fase Acessar Log.
Ao se clicar na opção Acessar Log a tabela TabHistórico é criada ou
atualizada com os dados da tabela Consulta existente no arquivo de log de
buscas, e seus dados são apresentados na tela.
Ao se clicar na opção Continuar, é executada a primeira tarefa
correspondente à etapa de pré-processamento.
101
2 – Faz Pré-Processamento
Após a obtenção das tabelas do log de buscas e da criação/atualização da
tabela TabHistórico, as seguintes tarefas são imediatamente executadas:
2.1 - Limpeza dos Dados
Esta tarefa é responsável por eliminar todas as entradas da tabela
TabHistórico que não forem relacionadas aos fluxos de Consultas
Cooperativas.
As atividades pertinentes a este passo do processo são executadas
por uma rotina denominada LimparLog, cuja interface de simulação de
sua pós-execução pode ser visualizada na Figura 5.6.
Figura 5.6: Interface de Simulação da Fase Limpar Log.
Ao se clicar na opção Limpar Log a tabela TabHistórico passa
pelo processo de limpeza e seus dados são apresentados na tela.
Ao se clicar na opção Continuar, é executada a próxima tarefa da
etapa de pré-processamento.
102
2.2 – Identificação das Sessões e Transações
Esta tarefa é responsável por agrupar os dados de cada Consulta
Cooperativa da tabela TabHistórico, gerando uma tabela denominada
TabTransações, onde cada registro contém os campos Idioma, a Chave
utilizada na busca, a Chave Expandida pelo uso do tesauro e a seqüência
ordenada de documentos acessados pelo usuário em cada busca.
As atividades pertinentes a este passo do processo são executadas
por uma rotina denominada GerarTransações, cuja interface de
simulação de sua pós-execução pode ser visualizada na Figura 5.7.
Figura 5.7: Interface de Simulação da Fase Gerar Transações.
Ao se clicar na opção Gerar Transações a tabela TabTransações é
criada e seus dados são apresentados na tela.
Ao se clicar na opção Continuar, é executada a próxima tarefa que
corresponde à etapa de Descoberta de Padrões de Acesso.
103
- Descoberta dos padrões de acesso
3 – Faz Prospecção de Padrões de Consultas Cooperativas
Este módulo é responsável pela execução do algoritmo de Prospecção de
Padrões de Acesso, WAP-mine (especificado no Capítulo 3), e pelo
armazenamento/atualização das informações na Base de Padrões de
Consultas Cooperativas, sendo implementado pela rotina denominada
DescobrirPadrões.
Na utilização do algoritmo WAP-mine para a Prospecção de Padrões de
Acessos a Consultas Cooperativas, é utilizada a correspondência do
IDUsuário com os campos (Idioma + Chave + ChaveExpandida) da tabela
TabTransações, e a Seqüência de Acessos sendo os documentos acessados
em uma consulta. Assim, cada grupo de registros correspondentes à tupla
(Idioma + Chave + ChaveExpandida) da tabela TabTransações representa
um banco de dados WAS referido no algoritmo, e terá seus padrões de acesso
gerados.
Assim, após aplicação do algoritmo WAP-mine, tendo como entrada a
tabela TabTransações e o suporte pré-definido pelos Engenheiros do
Domínio na interface Utilitários, tem-se como resultado a Base de Padrões
de Acesso a Consultas Cooperativas.
As atividades pertinentes a este passo do processo e que são executadas
pela rotina DescobrirPadrões, tem a interface de simulação de sua pós-
execução demonstrada na Figura 5.8. Nos exemplos apresentados neste
trabalho utilizou-se um valor de suporte = 0.75 (ou seja, as seqüências
freqüentes são aqueles presentes em pelo menos 75% dos registros de seu
banco de dados WAS).
104
Figura 5.8: Interface de Simulação da Fase Descobrir Padrões .
Ao se clicar na opção Gerar Padrões a Base de Dados de Padrões de Acesso a
Consultas Cooperativas é criada e seus dados são apresentados na tela.
Ao se clicar na opção Terminar, é reapresentada a interface principal da
aplicação.
5.2 – Aplicação para Geração de Conhecimento para a Manutenção da Ontologia
Este módulo constitui uma das aplicações representantes da etapa de Análise e
Utilização dos Padrões, citada no Capítulo 3, implementando o caso de uso “Gera
Conhecimento para Manutenção da Ontologia”, apresentado no Capítulo 4, e representa
a interface entre os Engenheiros do Domínio, a Base de Padrões de Buscas Cooperativas
e o Histórico de Consultas Cooperativas .
105
Para se acessar esta aplicação basta escolher a opção Manutenção da Ontologia
na interface principal da aplicação. Em seguida é mostrada a interface correspondente a
esta opção, que pode ser visualizada na Figura 5.9.
Figura 5.9: Interface de Opções de Conhecimento para Manutenção da Ontologia.
Ao se escolher a opção Padrões de Consultas a interface de acesso às
informações relativas aos Padrões de Acessos gerados é ativada, podendo ser
visualizada na Figura 5.10.
106
Figura 5.10: Interface de Padrões de Acesso para a Manutenção da Ontologia.
Nesta interface, o Engenheiro do Domínio deve fornecer o(s) termo(s) a ser(em)
pesquisado(s), que correspondem à Expressão de Consulta, e escolher um idioma. Em
seguida, as expansões correspondentes ao par (Expressão de Consulta + Idioma) que
foram realizadas nas Consultas Cooperativas são apresentadas como Expressão
Expandida da Consulta. Além disto, o engenheiro do Domínio deve determinar a Regra
de Relevância, que é o critério de escolha da seqüência padrão de documentos a ser
apresentada, dentre aquelas que possuem o suporte mínimo estabelecido. O valor padrão
para este critério é ‘Padrão de Maior Suporte’, podendo ser alterado para ‘Padrão de
Maior Tamanho’ ou ‘Todos os Padrões’. Para cada valor de Expressão Expandida é
listada uma seqüência de documentos correspondentes ao seu Padrão de Acesso atual de
acordo com a regra de relevância escolhida.
As opções PróximoPadrão e PadrãoAnterior são habilitadas apenas nos casos
em que existam diversos padrões que atendam à regra de relevância escolhida.
Ao se clicar na opção Nova Pesquisa, o processo é reinicializado, podendo o
Engenheiro do Domínio fornecer outra Expressão de Consulta e outro idioma.
Ao se clicar na opção Voltar, é reapresentada a interface de Opções de
Conhecimento para Manutenção da Ontologia.
107
Além da utilização dos dados dos Padrões de Acesso a Consultas Cooperativas,
são também disponibilizadas opções de pesquisas que utilizam algumas características
desta categoria de consulta, as quais estão armazenadas no Histórico de Consultas
Cooperativas e que podem ser utilizadas no auxílio à manutenção da ontologia. Para se
acessar estas informações, na interface de Opções de Conhecimento para Manutenção
da Ontologia (Figura 5.9), deve-se escolher a opção Outras Informações, e será
ativada a interface que pode ser visualizada na Figura 5.11.
Figura 5.11: Interface de Outras Informações para Manutenção da Ontologia.
108
Ao se escolher a opção Expansões Mais Requisitadas, será apresentada a
interface que pode ser visualizada na Figura 5.12.
Figura 5.12: Interface das Expansões mais Requisitadas ao Tesauro.
Nesta interface são exibidos os termos ou conjunto de termos (Chave) seguidos
pelas expansões requisitadas ao tesauro durante a realização de Consultas Cooperativas.
Para cada par (termo + expansão) é apresentado o campo Nº de Consultas,
representando o número de vezes que este par ocorreu nas Consultas Cooperativas,
sendo a listagem ordenada por este campo.
109
Caso se escolha a opção Expansões Mais Acessadas, será apresentada a
interface que pode ser visualizada na Figura 5.13.
Figura 5.13: Interface das Expansões mais Acessadas.
Também nesta interface são exibidos os termos ou conjunto de termos (Chave)
seguidos pelas expansões requisitadas ao tesauro durante a realização de Consultas
Cooperativas. Para cada par (termo + expansão) é apresentado o campo Nº de Acessos
representando o número de documentos retornados para este par que foram acessados
pelos usuários, sendo a listagem ordenada por este campo.
110
Caso se escolha a opção Expansões Não Acessadas, será apresentada a
interface que pode ser visualizada na Figura 5.14.
Figura 5.14: Interface das Expansões não Acessadas.
Assim como nas opções anteriores, nesta interface são exibidos os termos ou
conjunto de termos (Chave) seguidos pelas expansões requisitadas ao tesauro durante a
realização de Consultas Cooperativas. Para cada par (termo + expansão) é apresentado o
campo Nº de Vezes representando a quantidade de vezes que esta expansão foi
requisitada ao tesauro para o termo Chave, tendo a consulta retornado uma lista de
documentos, mas nenhum destes documentos tenha sido acessado pelo usuário, sendo a
listagem ordenada por este campo.
111
Caso se escolha a opção Expansões Sem Respostas, será apresentada a
interface que pode ser visualizada na Figura 5.15.
Figura 5.15: Interface das Expansões sem Respostas.
De forma idêntica às opções anteriores, nesta interface são exibidos os termos ou
conjunto de termos (Chave) seguidos pelas expansões requisitadas ao tesauro durante a
realização de Consultas Cooperativas. Para cada par (termo + expansão) é apresentado o
campo Nº de Requisições representando o número de vezes que esta expansão
requisitada para este termo ao tesauro não retornou resultados para o usuário, sendo a
listagem ordenada por este campo.
112
Caso se escolha a opção Documentos Retornados, será apresentada a interface
que pode ser visualizada na Figura 5.16.
Figura 5.16: Interface de Pesquisa dos Documentos Atualmente Retornados.
Esta interface, de forma análoga à interface da Figura 5.10 (Interface de Padrões
de Acesso para a Manutenção da Ontologia), requisita que o Engenheiro do Domínio
forneça uma Expressão de Consulta e escolha um idioma. Em seguida as expansões
realizadas para este par (Expressão de Consulta + Idioma) são apresentadas como
Expressão Expandida da Consulta. Para cada valor de Expansão encontrado são listados
os documentos atualmente retornados pela consulta, correspondentes à tupla (Expressão
de Consulta + Expressão Expandida + Idioma).
Ao se clicar na opção Nova Pesquisa, o processo é reinicializado, podendo o
Engenheiro do Domínio fornecer outra Expressão de Consulta e outro idioma.
113
5.3 – Aplicação de Geração de Conhecimento para o Mecanismo de Busca
Este módulo constitui a outra aplicação representante da etapa de Análise e
Utilização dos Padrões, citada no Capítulo 3, implementando o caso de uso “Gera
Conhecimento para Mecanismo de Busca”, apresentado no Capítulo 4. Esta aplicação
deve ser automaticamente executada pelo mecanismo de busca para o re-ranqueamento
dos resultados de cada Consulta Cooperativa realizada pelo usuário, na qual for
requisitado o uso do tesauro. Assim, foi implementada uma interface de simulação da
utilização da Base de Padrões de Acesso a Consultas Cooperativas pelo Mecanismo de
Busca da Biblioteca Virtual do Café, cuja execução pode ser ativada escolhendo-se a
opção Simulação de Busca na interface principal da aplicação (Figura 5.1), sendo
apresentada a interface que pode ser visualizada na Figura 5.17.
Figura 5.17: Interface da Aplicação de Simulação de Busca.
Nesta interface, para cada simulação a ser feita, deve-se fornecer uma Expressão
de Consulta, um idioma e uma Expressão Expandida requisitada para esta Expressão de
Consulta, neste idioma. Estes dados são requisitados, porque são estas as informações
114
que o Mecanismo de Busca possui ao utilizar esta aplicação para acessar a Base de
Padrões de Acesso à Consultas Cooperativas com o objetivo de obter o Padrão de
Acesso correspondente à consulta que está sendo realizada, e posteriormente realizar o
re-ranqueamento dos seus documentos resultantes. A Regra de Relevância utilizada é
‘Padrão de Maior Suporte’ e no caso de existirem vários padrões que atendam a esta
regra, utiliza-se dentre estes padrões, a regra de ‘Padrão de Maior Tamanho’. Ao
persistir mais de um padrão após a aplicação das duas regras, o mecanismo de busca
deverá fazer uma escolha que melhor se adapte à sua política de re-ranqueamento.
Assim, para cada tupla (Expressão de Consulta + Idioma + Expressão Expandida) é
apresentada uma listagem dos documentos correspondentes ao Padrão de Acesso atual
desta consulta, caso este exista.
Os documentos pertencentes a esta listagem podem ser utilizados para o re-
ranqueamento dos resultados originais do Mecanismo de Busca, pois refletem a
seqüência de documentos de interesse atual dos usuários que realizaram esta consulta.
As opções PróximoPadrão e PadrãoAnterior são habilitadas apenas nos casos
em que existam diversos padrões que atendam a aplicação conjunta das duas regras de
relevância: ‘Padrão de Maior Suporte’, e dentre estes, ‘Padrão de Maior Tamanho’.
Ao se clicar na opção Nova Simulação, o processo é reinicializado, podendo-se
fornecer outra Expressão de Consulta, outro idioma e outra Expressão Expandida.
115
5.4 – Resultados
Com o intuito de demonstrar os benefícios do uso de Prospecção de Dados no
apoio à Gestão de Conhecimento em um portal Web, de acordo com os objetivos deste
trabalho, a ferramenta tecnológica cujo desenvolvimento foi proposto, pôde ser avaliada
de acordo os resultados obtidos com a execução das aplicações apresentadas na sessão
anterior.
O processo de Prospecção de Dados foi realizado a partir dos dados disponíveis
nos arquivos de logs de buscas da Biblioteca Virtual do Café, relativos às consultas
realizadas no período de 05/04/2001 a 29/09/2003, utilizando-se um total de 61012
registros constituintes da tabela Consulta. A Consulta Tradicional é a categoria de busca
dominante nos arquivos de log da Biblioteca Virtual do Café devido ser recente a
incorporação das demais categorias. No entanto, optou-se por utilizar os acessos reais
relativos às Consultas Cooperativas, mesmo sendo estes em número reduzido, e não
registros fictícios, o que acarretou a descoberta de poucos padrões de acesso, porém
utilizando-se dados fiéis à atual utilização desta categoria de busca. Esta opção foi feita
para que após a utilização da ferramenta proposta no SBICafé possa-se, futuramente,
avaliar a evolução desta categoria de consulta.
Para se indicar os benefícios atuais que podem ser proporcionados pela
ferramenta aos Engenheiros do Domínio em sua tarefa de manutenção da ontologia, é
listado o conhecimento resultante de cada opção da aplicação desenvolvida para estes
usuários da ferramenta:
- Padrões de Acesso a Consultas Cooperativas: as expansões e os documentos
listados podem ser utilizados pelos Engenheiros do Domínio para o
conhecimento de quais as relações atuais entre os termos existentes na
ontologia são de interesse dos usuários, e quais documentos a elas associados
são mais freqüentemente acessados juntos em uma consulta. Tal
conhecimento possibilita o acesso às características dos documentos que
constituem um padrão de acesso relativo ao uso de determinados termos e
relações da ontologia, podendo sugerir alterações na ontologia com o intuito
de incluir/alterar/excluir termos e relações que propiciem o retorno de um
maior número de documentos com características semelhantes aos
apresentados no padrão de acesso.
116
- Expansões mais Requisitadas ao Tesauro: o conhecimento resultante desta
opção indica quais os termos e relações atuais existentes na ontologia são de
maior necessidade para o usuário.
- Expansões mais Acessadas: o conhecimento resultante desta opção indica
quais os termos e relações atuais existentes na ontologia que são de maior
interesse dos usuários.
- Expansões não Acessadas: o conhecimento resultante desta opção indica
quais as relações atuais entre os termos existentes na ontologia que não são
de interesse dos usuários.
- Expansões sem Respostas: o conhecimento resultante desta opção apresenta
quais são as relações atuais entre os termos existentes na ontologia que
podem ser de interesse dos usuários, mas que não contêm documentos a elas
associados.
- Documentos Retornados: este conhecimento indica quais as relações atuais
entre os termos existentes na ontologia que podem ser de interesse dos
usuários e quais os documentos a elas associados.
As justificativas acima sugerem que as opções disponibilizadas pela ferramenta,
destinadas a auxiliar os Engenheiros do Domínio no processo de manutenção da
ontologia, representam uma forma relevante de aquisição de conhecimento para a
realização desta tarefa, pois apresentam características das utilizações de termos e
relações da ontologia, refletindo as reais necessidades dos usuários do SBICafé.
Tais considerações indicam que aplicações de algoritmos de prospecção de
dados, dentre eles o algoritmo WAP-mine, podem ser desenvolvidas de acordo com as
necessidades explicitadas pelos Engenheiros do Domínio, retornando conhecimentos
que lhes sejam úteis na tarefa de manutenção da ontologia.
Para ilustrar a indicação citada, o algoritmo WAP-mine foi utilizado para a
implementação de uma nova opção destinada à obtenção de Padrões de Acesso à
Ontologia, cuja interface pode ser visualizada na Figura 5.18:
117
Figura 5.18: Interface da Aplicação de Padrões de Expansões Requisitadas à Ontologia.
Nesta opção, para cada agrupamento de duplas (Idioma + Chave), denominado
como um tipo de consulta, foram gerados os padrões das expansões escolhidas pelos
usuários, levando-se em consideração as seqüências de expansões mais freqüentemente
requisitadas conjuntamente em uma determinada consulta.
As expansões pertencentes à listagem permitem que os Engenheiros do Domínio
tenham conhecimento das relações entre os termos existentes na ontologia que
constituem os padrões de interesse dos usuários ao realizarem uma determinada
consulta. Este conhecimento pode ser utilizado para auxiliá-los na manutenção da
ontologia por indicar relações entre termos que devem ser adicionadas, alteradas ou
excluídas, de acordo com o uso atual da ontologia no portal.
As opções PróximoPadrão e PadrãoAnterior são habilitadas apenas nos casos
em que existam diversos padrões que atendam a aplicação conjunta das regras de
relevância. Ao se clicar na opção Nova Simulação, o processo é reinicializado,
podendo o Engenheiro do Domínio fornecer outra Expressão de Consulta, outro idioma
e outra Regra de Relevância.
Tais padrões poderiam, ainda, corresponder à seqüência de expansões mais
freqüentemente escolhidas em cada tipo de consulta ou em todos os tipos de consultas,
considerando-se as seqüências de expansões mais freqüentemente escolhidas
conjuntamente em todos os tipos de consultas etc., utilizando-se o próprio algoritmo
WAP-mine.
118
No caso do Mecanismo de Busca, para se validar os benefícios atuais que lhe
podem ser proporcionados pelo uso da ferramenta, foi realizada uma comparação entre
os Padrões de Acesso a Consultas Cooperativas realizadas na Biblioteca Virtual do Café
e o ranqueamento atual dos documentos exibidos aos seus usuários em suas buscas. O
resultado desta comparação, para o exemplo de padrão mostrado na Figura 5.17, pode
ser visualizado na Tabela 5.1.
Comparativo entre os Padrões de Acesso a Consultas Cooperativas e
ranqueamento atual dos documentos retornados pela Biblioteca Virtual do Café
Chave Chave-Expandida Padrão de Acesso Documentos Retornados
irrigação
FERTIRRIGACAO 155552
155556
155537_Art242 155537_Art245
155585_Art058 156896_Art10
1555537_Art275 155537_Art351
155537_Art229 156896 155553
155537_Art233 155552_Art13
155537_Art223 155556 ...
155552 155552_Art10
Tabela 5.1: Resultado da comparação entre os Padrões de Acesso e o Ranqueamento
Atual dos Documentos Retornados pela Biblioteca Virtual do Café.
Na Tabela 5.1 podemos observar que o documento de código 155552, que
representa o primeiro documento do Padrão de Acesso é o penúltimo do rank, na
posição nº 42 e o documento 155556 ocupa a posição nº 12 do rank. Este resultado, e
outros exemplos testados sugerem que a utilização da Base de Padrões de Acesso a
Consultas Cooperativas no re-ranqueamento dos resultados obtidos pelo Mecanismo de
Busca da Biblioteca Virtual do Café, é capaz de proporcionar um re-ranqueamento dos
documentos que reflita melhor os reais interesses dos usuários, tornando o processo de
busca mais eficiente.
Assim, apesar da ferramenta ainda não ter sido testada in-house, as observações
realizadas acerca das simulações das aplicações destinadas à manutenção da ontologia e
no re-ranqueamento dos resultados do mecanismo de busca, sugerem que a utilização de
“Prospecção de Dados no Apoio à Gestão de Conhecimento em um Portal Web”
possibilita a geração de conhecimentos úteis para a otimização deste processo, o que
indica a possibilidade de obtenção dos benefícios especificados na proposta desta
dissertação. 119
6 – Conclusões e Trabalhos Futuros
Neste capítulo são apresentadas algumas conclusões obtidas após a realização
deste trabalho e algumas possibilidades de trabalhos futuros a partir dos estudos
realizados.
6.1 – Conclusões
A complexidade e a falta de organização formal da Web levam inevitavelmente à
necessidade de mecanismos automáticos que ajudem as pessoas a diminuírem a
sobrecarga de informações e a se comunicarem de forma mais eficaz e eficiente, e assim
a área de Web Intelligence (WI) está impulsionando o desenvolvimento de tecnologias
que tenham estas finalidades, sendo que este trabalho representa uma destas iniciativas.
Quanto à escolha do algoritmo a ser utilizado para se alcançar os propósitos
definidos para a ferramenta utilizando-se a técnica de prospecção de dados, pode-se
confirmar as afirmações da literatura quanto às dificuldades relacionadas a esta etapa.
Inicialmente foram estudados vários algoritmos destinados à geração de regras de
associação, seguido pelo estudo de algoritmos destinados à geração de padrões
seqüenciais sendo que, nos dois casos foram realizadas tentativas de adaptação dos
algoritmos para se propor a solução do problema em questão. No caso de regras de
associação, como a ordem dos elementos acessados não é considerada, nenhuma
adaptação foi satisfatória. Quanto à utilização de padrões seqüenciais, o algoritmo mais
estudado é o GSP [Srikant & Agrawal, 1996], o qual executa prospecção de padrões
através de múltiplas inspeções do banco de dados, o que caracteriza a base da heurística
Apriori. Entretanto, quando o tamanho das seqüências aumenta e/ou quando as
transações são grandes, o número de seqüências candidatas geradas pode crescer
exponencialmente, e o algoritmo GSP encontrará dificuldades. Assim, tratando-se de
um portal Web no qual deseja-se acoplar melhoramentos em seu mecanismo de busca, é
esperado que o número de consultas e resultados acessados apresente um crescimento
substancial, tendo sido descartada a abordagem GSP.
Após a realização de outras pesquisas, foi localizado o algoritmo WAP-mine
[Pei et al., 2000], que se apresentou como o mais adequado às tarefas a serem
executadas e que, portanto tornou-se o algoritmo escolhido para a resolução do
problema proposto, tendo como consideração chave facilitar as tediosas operações de
120
contagem de suporte e geração de candidatos no procedimento de prospecção. O
algoritmo WAP-mine retorna o conjunto completo de padrões de acesso sem
redundância apresentando vantagens significativas comparado àqueles baseados em
Apriori. Em primeiro lugar, a WAP-tree é uma estrutura de dados eficaz, e registra
todas as informações dos contadores para a prospecção de padrões, livrando-se o
processo de prospecção da contagem de candidatos pelo casamento de padrões.
Segundo, a estratégia de busca condicional estreita o espaço de busca eficientemente, e
faz um melhor uso da estrutura da WAP-tree, evitando o problema de geração explosiva
de candidatos como acontece em algoritmos como o Apriori.
Quanto ao desenvolvimento e utilização da ferramenta proposta, foram atingidos
os objetivos específicos de se coletar os registros de utilização do mecanismo de busca
do portal Web pelos seus usuários e a utilização da prospecção de dados para a obtenção
de padrões de acesso visando-se a geração de conhecimento relevante para a
manutenção da ontologia e para o re-ranqueamento dos resultados do mecanismo de
busca, o que pode ser considerado como um encaminhamento à personalização das
informações disponíveis no portal, contribuindo-se assim para o processo de Gestão de
Conhecimento neste domínio específico.
Desta forma, um ponto muito explorado neste trabalho foi o uso do
conhecimento sobre os acessos realizados pelos usuários do portal e suas necessidades
de informação para auxiliá-los em suas consultas. A ferramenta desenvolvida tem
acesso à coleta de informações relacionadas aos termos da ontologia selecionados pelo
usuário em uma consulta cooperativa, bem como do contexto no qual estes termos
foram selecionados. Essas informações foram usadas para gerar o Histórico das
Consultas Cooperativas e a Base de Padrões de Acesso a Consultas Cooperativas.
Como demonstrado no capítulo anterior, o uso destas bases de conhecimento
pode aprimorar a ontologia incorporada ao portal, a partir da possibilidade de maior
eficiência no processo de sua manutenção. Por sua vez, a melhoria deste processo
otimiza o funcionamento do mecanismo de busca cujos padrões de acesso realimentam
as informações necessárias para a manutenção da ontologia. Assim, forma-se um
processo cíclico que deve ser utilizado conjuntamente e continuamente para que se
possa alcançar a solidificação das funcionalidades da ferramenta.
Portanto, o uso de prospecção de dados em um portal Web contendo uma fonte
de conhecimento sobre o domínio a ser consultado, representado por uma ontologia,
mostra-se como uma grande possibilidade de se obter conhecimento útil e inicialmente
desconhecido, relevante ao processo de Manutenção da Ontologia, permitindo que 121
essas representem o real entendimento e interesse do usuário do portal Web. A partir da
indicação da aplicabilidade da prospecção de dados como uma forma de aquisição de
padrões de acessos a documentos retornados em uma busca no portal utilizando-se a
ontologia, outros tipos de padrões podem ser gerados utilizando-se o algoritmo WAP-
mine, por ser uma abordagem eficiente para a questão de geração de padrões a partir de
arquivos de logs da Web, podendo-se oferecer substanciais fontes de conhecimento para
a otimização do processo de manutenção da ontologia.
Da mesma forma, os resultados obtidos indicam ser possível atingir uma
melhoria substancial na eficiência das buscas realizadas com a utilização da ontologia,
possibilitando a ordenação dos documentos retornados de acordo com os reais padrões
de acesso aos documentos, permitindo assim que o mecanismo de busca possa
beneficiar-se da Filtragem Colaborativa em sua política de ranqueamento. A partir da
possibilidade da geração de padrões apresentada neste trabalho, outros padrões podem
ser gerados para a otimização das buscas no portal.
Em ambos os casos, resultados mais significativos poderão ser observados a
partir da incorporação das funcionalidades propostas pela ferramenta ao portal SBICafé,
para com isto ter-se os subsídios necessários para a realização de avaliações mais
detalhadas, que demonstrem a otimização do processo de manutenção da ontologia e do
desempenho das consultas realizadas, e incentivando o trabalho em busca de novos
padrões de uso do portal. No entanto, a real utilização desta proposta depende de
questões de interesse por parte dos responsáveis pelo SBICafé, as quais esperamos ser
favoráveis após tornarem-se conhecedores das suas possibilidades de otimização. Além
disto, necessita-se de um período substancial de experimentação da ferramenta proposta
para se ter uma Base de Padrões de Acesso, quantitativamente e qualitativamente mais
adequada, no que diz respeito à utilização da categoria de Consulta Cooperativa.
122
6.2 – Trabalhos Futuros
Alguns pontos que não foram abordados neste trabalho podem ser citados como
possibilidades de pesquisas futuras e/ou aprimoramentos relacionados à ferramenta
desenvolvida:
- A primeira extensão proposta é a incorporação da ferramenta desenvolvida
ao portal SBICafé, objetivando-se a análise dos resultados in-house. Ao ser
aplicada esta extensão, sugere-se a substituição da Consulta Convencional
pela Consulta Cooperativa, ou seja, para todo usuário que realize uma
consulta deve ser oferecida a oportunidade de expandi-la, caso ele deseje, o
que ampliaria satisfatoriamente a utilização do tesauro, possibilitando uma
melhor análise do comportamento do usuário ao realizar buscas no portal.
- Outras opções podem ser acrescentadas à aplicação destinada aos
Engenheiros do Domínio, de acordo com as necessidades que forem
detectadas para a manutenção da ontologia, a partir do Histórico de Buscas e
da Base de Padrões de Acesso.
- Outros tipos de padrões devem ser gerados utilizando-se o algoritmo WAP-
mine, visto que este se apresentou como um dos algoritmos mais eficientes
no tratamento de dados de uso a partir de logs da Web, podendo-se oferecer
substanciais fontes de conhecimento para a otimização do processo de
manutenção da ontologia. Assim, dentre as atuais possibilidades, pode-se
citar expansões da instância de Padrões de Acesso à Ontologia (Figura 5.18),
podendo-se explorar, dentre diversos outros possíveis interesses dos
Engenheiros do Domínio:
- Padrões de acessos satisfatórios à ontologia: para cada consulta (ou
todos os tipos de consultas) gerar os padrões das expansões
escolhidas pelos usuários que satisfizeram suas expectativas.
- Padrões de acessos insatisfatórios à ontologia: para cada tipo de
consulta (ou todos os tipos de consultas) gerar os padrões das
123
expansões escolhidas pelos usuários que não satisfizeram suas
expectativas.
- Padrões de caminhos de acesso à ontologia: para cada tipo de
consulta (ou todos os tipos de consultas) gerar os padrões dos
caminhos de acessos à ontologia, sendo os possíveis caminhos: o
acesso direto aos documentos a partir da lista de itens da ontologia
disponibilizados ou o acesso a documentos retornados pela consulta
expandida ou o acesso aos documentos adicionais incluídos com o
uso da ontologia.
- A ferramenta desenvolvida poderá ser estendida no sentido de englobar as
Consultas Guiadas pelo Tesauro, caso este tipo de consulta torne-se uma
categoria de uso mais dominante, podendo-se avaliar os resultados
provenientes desta utilização.
- Neste trabalho optou-se pela análise anônima dos padrões de consultas
cooperativas, não se utilizando conhecimento demográfico sobre os usuários,
o que é disponibilizado pelo portal, podendo assim, ser estudada a sua
viabilidade como forma de customização das buscas realizadas por cada um
dos usuários individuais. Assim, na utilização de padrões de acesso pelo
mecanismo de busca, pode-se criar perfis de usuários, baseados em
determinadas características demográficas e/ou seus padrões de consultas e
acessos, podendo utilizá-los como mais um subsídio para o re-ranqueamento
dos resultados das buscas realizadas por estes usuários, constituindo mais um
passo em direção à possibilidade de personalização das buscas no portal.
- Outra, importante e ainda não explorada, possibilidade é a anotação
semântica dos itens de conhecimento com termos da ontologia. Este tipo de
anotação foi previsto pela aplicação de [Pontes, 2002], o que necessita de um
trabalho em volume considerável, devendo ser realizado por pessoas que
possuam conhecimento do domínio. Espera-se que este tipo de anotação
melhore significativamente o desempenho das consultas e possibilite a
geração de conhecimento a ser utilizado na otimização da tarefa de
manutenção da ontologia. Segundo [Pontes, 2002], as iniciativas 124
relacionadas com a Web Semântica trabalham no sentido de criar ontologias,
padrões e ferramentas que façam uso destes padrões para a anotação
semântica das páginas Web. A necessidade de produzir conteúdo
semanticamente anotado representa o principal obstáculo para o surgimento
pleno da Web Semântica.
125
7 – Bibliografia
[Agrawal et al., 1993] AGRAWAL, R.; IMIELINSKI, T.; SWAMI, A. Mining Association Rules between Sets of Items in Large Databases. In: ACM SIGMOD INTERNATIONAL CONFERENCE ON MANAGEMENT OF DATA, 1993, Washington. Proceedings... 1993. p. 207-216.
[Agrawal & Srikant, 1994] AGRAWAL, R.; SRIKANT, R. Fast Algorithms for Mining Association Rules. In: INTERNATIONAL CONFERENCE ON VLDB, 20., 1994, Santiago. Proceedings... 1994. p. 487-499.
[Agrawal & Srikant, 1995] AGRAWAL, R.; SRIKANT, R. Mining Sequential Patterns. In: INTERNATIONAL CONFERENCE DATA ENGINEERING – ICDE, 11., 1995, Taipei. Proceedings... 19995. p. 3-14.
[Armstrong et al., 1995] ARMSTRONG, R.; FREITAG, D.; JOACHIMS, T. Webwatcher: A Learning Apprentice for the World Wide Web. In: AAAI SPRING SYMPOSIUM ON INFORMATION GATHERING FROM HETEROGENEOUS, DISTRIBUTED ENVIRONMENTS, 1995. Papers... 1995. p. 6-12.
[Ayres et al., 2002] AYRES, J., et al. Sequential Pattern Mining Using a Bitmap Representation. In: ACM SIGKDD INTERNATIONAL CONFERENCE ON KNOWLEDGE DISCOVERY AND DATA MINING, 8., 2002, Edmonton. Proceedings... 2002.
[Bastide et al., 2000] BASTIDE, Y., et al. Levelwise Search of Frequent Patterns with Counting Inference. In: DBA'2000, 2000. Proceedings... 2000. p. 177-196.
[Bayardo Jr., 1998] BAYARDO JR., R.. J. Efficiently Mining Long Patterns from Databases. In: ACM-SIGMOD INTERNATIONAL CONFERENCE ON MANAGEMENT OF DATA, 1998. Proceedings... 1998. p. 85-93.
[Becerra-Fernandez, 2001] BECERRA-FERNANDEZ, I. Locating Expertise at NASA: Developing a Tool to Leverage Human Capital. Knowledge Management Review, v. 4, p. 34-37, Sep./Oct. 2001.
[Benjamins & Martin, 2000] BENJAMINS, V. R.; Martin, F. J. Knowledge Management for Internet Companies. In: IFIP WORLD COMPUTER CONGRESS, 16., 2000. Proceedings of International Conference on Intelligent Information... 2000.
[Bharat & Henzinger, 1998] BHARAT, K.; HENZINGER, M. R. Improved Algorithms for Topic Distillation in a Hyperlinked Environment. In: ANNUAL INTERNATIONAL ACM CONFERENCE ON RESEARCH AND DEVELOPMENT IN INFORMATION RETRIEVAL - SIGIR, 21., 1998, Melbourne. Proceedings... 1998. p.104-111.
126
[Booch et al., 1998] BOOCH, G.; RUMBAUGH, J.; JACOBSON, I. The Unified Modeling Language User Guide. Addison Wesley, 1998.
[Brachman & Anand, 1996] BRACHMAN, R.; ANAND, T. The Process of Knowledge Discovery in Databases: A Human-Centered Approach. In: Advances in Knowledge Discovery and Data Mining. Menlo Park: AAAI Press, 1996. p.36-37.
[Brin et al., 1997] BRIN, S., et al. Dynamic Itemset Counting and Implication Rules for Market Basket Data. In: ACM-SIGMOD INTERNATIONAL CONFERENCE ON MANAGEMENT OF DATA, 1997. Proceedings.. 1997.
[Brin & Page, 1998] BRIN, S.; PAGE, L. The Anatomy of a Large-Scale Hypertextual Web Search Engine. In: INTERNATIONAL WORLD WIDE WEB CONFERENCE, 7., 1998, Brisbane. Proceedings... New York: ACM Press, 1998. p. 107-117.
[Chakrabarti et al., 1998] CHAKRABARTI, S.; DOM, B.; INDYK, P. Enhanced Hypertext Categorization Using Hyperlinks. In: ACM SIGMOD INTERNATIONAL CONFERENCE ON MANAGEMENT OF DATA, 1998, Seattle. Proceedings...1998. p.307-318.
[Chakrabarti et al., 1999] CHAKRABARTI, S., et al. Mining the Link Structure of the World Wide Web. IEEE Computer, v. 32, n. 8, p. 60-67, 1999.
[Chen et al., 1996] CHEN, M.; HAN, J.; YU, P. S. Data Mining: An Overview from Database Perspective. Journal IEEE Trans. Knowledge and Data Engineering, n. 8, p. 886-883, 1996.
[Cheung et al., 1996] CHEUNG, D. W., et al. Maintenance of Discovery Association Rules in Large Databases: An Incremental Updating Technique. In: INTERNATIONAL CONFERENCE ON DATA ENGINEERING, 12., 1996. Proceedings...1996.
[Cheung et al., 1997] CHEUNG, D. W.; LEE, S. D.; KAO, B. A General Incremental Technique for Maintaining Discovery Association Rules. In: INTERNATIONAL CONFERENCE ON DATABASES SYSTEMS FOR ADVANCED APPLICATIONS, 5., 1997, Melbourne. Proceedings...1997.
[Chiang et al., 2001] CHIANG, R. H. L.; CHUA, C. E. H.; STOREY, V. C. A Smart Web Query Method for Semantic Retrieval of Web Data. Knowledge and Data Engineering, n. 38, p. 63-84, 2001.
[Cooley, 2000] COOLEY, R. Web Usage Mining: Discovery and Application of Interesting Patterns from Web Data. 2000. Ph.D. Thesis - University of Minnesota, Minneapolis.
[Cooley et al., 1997] COOLEY, R.; MOBASHER, B.; SRIVASTAVA J. Web Mining: Information and Pattern Discovery on the World Wide Web. In: IEEE INTERNATIONAL CONFERENCE ON TOOLS WITH ARTIFICIAL INTELLIGENCE - ICTAI, 9., 1997. Proceedings...1997.
127
[Cooley et al., 1999] COOLEY, R.; MOBASHER, B.; SRIVASTAVA, J. Data Preparation for Mining World Wide Web Browsing Patterns. Journal of Knowledge and Information Systems, v. 1, n. 1, February 1999.
[Das et al., 2001] DAS, A.; NG, W.; WOON, Y. Rapid Association Rule Mining. In: CIKM, 2001. Proceedings... 2001. p. 5-10.
[Doorenbos et al., 1997] DOORENBOS, R. B.; ETZIONI, O.; WELD, D. S. A Scalable Comparison Shopping Agent for the World Wide Web. In: INTERNATIONAL CONFERENCE ON AUTONOMOUS AGENTS – AGENTS’97, 1., 1997, New York. Proceedings... 1997. p. 39-48.
[Doug, 1997] DOUG, D. Data Mining The Mail. Forbes, p. 112, 24, February 1997.
[Etzioni, 1996] ETZIONI, O. The World Wide Web: Quagmire or Gold Mine. Communications of the ACM, v. 39, n.11, p.65-68, 1996.
[Fayyad et al., 1996] FAYYAD, U.; PIATETSKY-SHAPIRO, G.; SMYTH, P. From Data Mining to Knowledge Discovery: An overview. In: Advances in Knowledge Discovery and Data Mining. Menlo Park: AAAI Press, 1996, p.1-36.
[Feldens, 1997] FELDENS, M. A. Engenharia da Descoberta de Conhecimento em Bases de Dados: Estudo e aplicação na área de saúde. 1997. Dissertação de Mestrado – Universidade Federal do Rio Grande do Sul, Porto Alegre.
[Fensel, 2000] FENSEL, D. The Semantic Web and its Languages. IEEE Intelligent Systems, v. 15, n. 6, p. 67, Nov/Dec 2000.
[Fensel et al., 2001] FENSEL, D. et al. OIL: An Ontology Infrastructure for the Semantic Web. IEEE Intelligent Systems, v. 16, n. 2, p. 38-45, Mar/Apr 2001.
[Fernandes, 1998] FERNANDES, J. H.C. Ciberespaço: Modelos, Tecnologias, Aplicações e Perspectivas. In: DE MOURA, Hermano P. XVII Jornada de Atualização em Informática – JAI. 1998. v. 2.
[Fischer & Ostwald, 2001] FISCHER, G.; OSTWALD, J. Knowledge Management: Problems, Promises, Realities and Challenges. IEEE Intelligent Systems, v. 16, n. 1, p. 60-72, Jan/Feb 2001.
[Frainer, 1993] FRAINER, A. S. Planos na Interação Homem-Máquina. 1993. Dissertação de Mestrado. Universidade Federal do Rio Grande do Sul, Porto Alegre.
[Garofalakis et al., 1999] GAROFALAKIS, M. Data Mining and the Web: Past, Present and Future. In: ACM WORKSHOP ON WEB INFORMATION AND DATA MANAGEMENT. 1999, Kansas. Proceedings...1999.
[Gouda & Zaki, 2001] GOUDA, K.; ZAKI, M. J. Efficiently Mining Maximal Frequent Itemset. In: IEEE CONFERENCE ON DATA MINING, 1., 2001. Proceedings...2001.
128
[Gruber, 1993] GRUBER, T. R. A Translation Approach to Portable Ontology Specifications. Knowledge Acquisition, v. 5, p. 199-220, 1993.
[Gruninger & Lee, 2002] GRUNINGER, M.; LEE, J. Ontology - Applications and Design. Communications of the ACM, v. 45, n. 2, p. 39-41, February 2002.
[Guarino & Giaretta, 1995] GUARINO, N., GIARETTA, P. Ontologies and Knowledge Bases: Towards a Terminological Clarification. In: MARS, N. J., Towards Very Large Knowledge Bases, IOS Press, 1995.
[Gurovitz, 1997] GUROVITZ, H. O que Cerveja tem a ver com Fraldas? Exame, p. 23-25, Abril 1997.
[Han et al., 2000a] HAN, J., et al. FreeSpan: Frequent Pattern-Projected Sequential Pattern Mining. In: INTERNATIONAL CONFERENCE ON KNOWLEDGE DISCOVERY AND DATA MINING - KDD'00, 2000, Boston. Proceedings... 2000. p. 355-359.
[Han et al., 2000b] HAN, J.; PEI, J., YIN, Y. Mining Frequent Patterns Without Candidate Generation. In: ACM-SIGMOD INTERNATIONAL CONFERENCE ON MANAGEMENT OF DATA, 2000, Dallas. Proceedings...2000.
[Han et al., 2002] HAN, J., et al. Emerging Scientific Applications in Data Mining. Communications of the ACM, v. 45, n. 8, p. 54-58, August 2002.
[Harmelen, 2000] HARMELEN, F. V. FAQs on OIL: The Ontology Inference Layer. IEEE Intelligent Systems, v. 15, n. 6, p. 69-73, Nov/Dec 2000.
[Holsapple & Joshi, 2002] HOLSAPPLE, C. W.; JOSHI, K. D. A Collaborative Approach to Ontology Design. Communications of the ACM, v. 45, n. 2, p. 42-47, February 2002.
[Jennings, 2002] JENNINGS, M. F. What are the Major Comparisons or Differences Between Web Mining and Data Mining. DM Review Online, June 2002.
[Joachims et al., 1997] JOACHIMS, T.; FREITAG, D.; MITCHELL, T. WebWatcher: A Tour Guide for the World Wide Web. In: INTERNATIONAL JOINT CONFERENCE ON ARTIFICIAL INTELLIGENCE – IJCAI’97, 15., 1997, Nagoya. Proceedings... 1997. p. 770-775.
[Jones et al., 1998] JONES, D.; BENCH-CAPON, T.; VISSER, P. Methodologies for Ontology Development. In: IFIP WORLD COMPUTER CONGRESS, 15., 1998, Budapest. Proceedings of IT & Knowledge Conference...1998.
[Kato et al., 2000] KATO, H.; NAKAYAMA, T.; YAMANE, Y. Navigation Analysis Tool Based on the Correlation Between Contents Distribution and Access Patterns. In: WEBKDD’2000, 2000, Boston.. Proceedings of Workshop On Web Mining For E-Commerce - Challenges And Opportunities... 2000.
129
[Kietz et al., 2000] KIETZ, J.; MAEDCHE, A.; VOLZ, R. A Method for Semi-Automatic Ontology Acquisition from a Corporate Intranet. In: INTERNATIONAL CONFERENCE ON KNOWLEDGE ENGINEERING AND KNOWLEDGE MANAGEMENT, 2000, Juan-Leb-Pins. Proceedings of Workshop on “Ontologies and Text”...2000.
[Kimball & Merz, 2000] KIMBALL, M. The Data Webhouse Toolkit: Building The Web-Enabled Data Warehouse. 1. edition. New York: John Wiley & Sons, 2000.
[Kleinberg, 1998] KLEINBERG, J. M. Authoritate Sources in a Hyperlinked Environment. In: ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, 9., 1998, Baltimore. Proceedings... 1998. p. 668-677.
[Kleinberg & Lawrence, 2001] KLEIBERG, J. M.; LAWRENCE, S. The Structure of the Web. Science, v. 294, p. 1849-1850, November 2001.
[Kobayashi & Takeda, 2000] KOBAYASHI, M.; TAKEDA, K. M. Information Retrieval on the Web. ACM Computing Surveys, v. 32, n. 2, p. 144-173, June 2000.
[Kohavi & Becher, 2001] KOHAVI, R.; BECHER, J. E-commerce and Clickstream Mining: Tutorial. In: SIAM INTERNATIONAL CONFERENCE ON DATA MINING, 2001. Proceedings...2001.
[Konopnicki & Shmueli, 1996] KONOPNICKI, D.; SHMUELI, O. Early Experiences with W3QS - A WWW Information Gathering System. In: IEEE CONVENTION OF ELECTRICAL AND ELECTRONICS ENGINEERS, 19., 1996, Israel. Proceedings... 1996.
[Kosala & Blockeel, 2000] KOSALA, R.; BLOCKEEL, H. Web Mining Research: A Survey. ACM SIGKDD Explorations, v. 2, n. 1, p. 1-15, July 2000.
[Kumar et al., 1999] KUMAR, S. R., et al. Trawling the Web for Emerging Cyber-Communities. In: WORLD WIDE WEB CONFERENCE –WWW’8, 8., 1999. Proceedings...1999.
[Lawrence, 2000] LAWRENCE, S. Context in Web Search. IEEE Data Engineering Bulletin, v. 23, n. 3, p.25-32, 2000.
[Lieberman, 1995] LIEBERMAN, H. Letizia: An agent that Assists Web Browsing. In: INTERNATIONAL JOINT CONFERENCE ON ARTIFICIAL INTELLIGENCE - IJCAI'95, 14., 1995, Montreal. Canada, Proceedings... 1995. p. 924-929.
[Lin & Lee, 1998] LIN, M.; LEE, S. Incremental Update on Sequential Patterns in Large Databases. In: TOOLS FOR ARTIFICIAL INTELLIGENCE CONFERENCE - TAI'98, 1998. Proceedings... 1998. p. 24-31.
[Loh & Garin, 2001] LON, S.; GARIN, R. S. Web Intelligence - Inteligência Artificial para Descoberta de Conhecimento na Web. In: V Oficina de Inteligência Artificial da Universidade Católica de Pelotas. Pelotas: EDUCAT, 2001. p.11-34.
130
[Ma et al., 2000] MA, Y.; LIU, B.; WONG, C.K. Web for Data Mining: Organizing and Interpreting the Discovered Rules Using the Web. ACM SIGKDD Explorations, v. 2, n. 1, p. 16-23, July 2000.
[Maedche & Staab, 2001] MAEDCHE, A.; STAAB, S. Ontology Learning for Semantic Web. IEEE Intelligent Systems, v. 16, n. 2, p. 72-79, Mar/Apr 2001.
[Masseglia et al., 2000] MASSEGLIA, F.; PONCELET, P.; TEISSEIRE, M. Incremental Mining of Sequential Patterns in Large Databases. In: BDA’00, 2000, Blois. Proceedings of Actes des 16 ièmes Journées Bases de Données Avancées...2000.
[Merialdo et al., 1997] MERIALDO, P.; ATZENI, P.; MECCA, G. Semistructured and structured data in the web: Going back and forth. In: ACM SIGMOD, 1997. Proceedings of Workshop on the Management of Semistructured Data...1997.
[Mobasher et al., 1996] MOBASHER, B. et al. Web Mining: Pattern Discovery from World Wide Web Transactions. 1996. Technical Report TR-96050 - Department of Computer Science, University of Minnesota, Minneapolis.
[Mobasher et al., 2000a] MOBASHER, B.; COOLEY, R.; SRIVASTAVA, J. Automatic Personalization Based on Web Usage Mining. Communications of the ACM, v. 43, n. 8, p. 142-151, August 2000.
[Mobasher et al., 2000b] MOBASHER, B., et al. Integrating Web Usage and Content Mining for More Effective Personalization. In: INTERNATIONAL CONFERENCE ON E-COMMERCE AND WEB TECHNOLOGIES – ECWEB, 2000, Greenwich. Proceedings... LNCS - Lecture Notes in Computer Science. London: Springer-Verlag, 2000. v. 1875, p. 165-176.
[Moxon, 1996] MOXON, B. Defining Data Mining. DMS Data Warehouse Supplement, August 1996.
[Park et al., 1995] PARK, J. S.; CHEN, M.; YU, P. S. An Effective Hash-Based Algorithm for Mining Association Rules. In: ACM SIGMOD INTERNATIONAL CONFERENCE ON MANAGEMENT OF DATA, 1995, San Jose. Proceedings...1995. p. 175-186.
[Parthasarathy et al., 1999] PARTHASARATHY, S., et al. Incremental and Interactive Sequence Mining. In: INTERNATIONAL CONFERENCE ON INFORMATION AND KNOWLEDGE MANAGEMENT, 8., 1999, Kansas. Proceedings...1999. p. 251-258.
[Pasquier et al., 1999] PASQUIER, N., et al. Efficient Mining of Association Rules Using Closed Itemset Lattices. Information Systems, v. 24, n. 1, p. 25-46, March 1999.
[Pei et al., 2000] PEI, J., et al. Mining Access Patterns Efficiently from Web Logs. In: PACIFIC-ASIA CONFERENCE ON KNOWLEDGE DISCOVERY AND DATA MINING - PAKDD'00, 2000, Kyoto. Proceedings...2000.
131
[Pei et al., 2001] PEI, J., et al. PrefixSpan: Mining Sequential Patterns Efficiently by Prefix-Projected Pattern Growth. In: INTERNATIONAL CONFERENCE IN DATA ENGINEERING – ICDE'01, 2001. Proceedings...2001. p. 215-224.
[Perkowitz & Etzioni, 2000] PERKOWITZ, M.; ETZIONI, O. Adaptive Web Sites. Communications of the ACM, v. 43, n. 8, p. 152-158, August 2000.
[Pirolli et al., 1996] PIROLLI, P.; PITKOW, J.; RAO, R. Silk from a Sow's Ear: Extracting Usable Structures from the Web. In: CONFERENCE ON HUMAN FACTORS IN COMPUTING SYSTEMS, 1996, Vancouver. Proceedings...1996. p.13-19.
[Pitkow, 1997] PITKOW, J. In Search of Reliable Usage Data on the WWW. In: INTERNATIONAL WWW CONFERENCE, 6., 1997. Proceedings...1997.
[Pitkow & Bharat, 1994 ] PITKOW, J. E.; BHARAT, K. A. WEBVIZ: a Tool for World Wide Web Access Log Analysis. In: INTERNATIONAL WWW CONFERENCE, 1., 1994. Proceedings...1994.
[Pontes, 2002] PONTES, F. V. Gestão de Conhecimento Apoiada por Ontologias. 2002. 142 f. Dissertação de Mestrado (Ciência da Computação) - Universidade Federal de Minas Gerais, Belo Horizonte.
[Sarda & Srinivas, 1998] SARDA, N. L.; SRINIVAS, N. V. An Adaptive algorithm for Incremental mining of association rules. In: CONFERENCE ON DATABASE AND EXPERT SYSTEMS, 9., 1998, Vienna. Proceedings... 1998. p. 240-245.
[Savasere et al., 1995] SAVASERE, A.; OMICCINSKI, E.; NAVATHE, S. An Efficient Algorithm for Mining Association Rules in Large Databases. In: INTERNATIONAL CONFERENCE ON VERY LARGE DATABASES, 21., 1995, Zurich. Proceedings... 1995. p. 432-444.
[Schwartz & Wood, 1993] SCHWARTZ; W. Discovering Shared Interest Using Graph Analysis. COMMUNICATIONS OF THE ACM, v. 36, n. 8, p. 78-89, August 1993.
[Schafer, 2001] SHAFER, J. B. E-commerce Recommendation Applications. Journal of Data Mining and Knowledge Discovery, v. 5, n. 1, January 2001.
[Shakshuki et al., 2002] SHAKSHUKI, E.; GHENNIWA, H.; KAMEL, M. An Architecture for Cooperative Information Systems. Knowledge-Based Systems, v. 16, n. 2003, p. 17-27, 2002.
[Shardanand & Maes, 1995] SHARDANAND, U.; MAES, P. Social information Filtering: Algorithms for Automating " Word of Mouth". In: ACM CONFERENCE ON HUMAN FACTORS IN COMPUTING SYSTEMS – CHI’95, 1995, Denver. Proceedings...1995.
[Spertus, 1998] SPERTUS, E. ParaSite: Mining the Structural Information on the World Wide Web. 1998. Ph.D. Thesis - Department of EECS, MIT, Cambridge, MA.
132
[Spiliopoulou, 2000] SPILIOPOULOU, M. Web Usage Mining for Web Site Evaluation. Communications of the ACM, v. 43, n. 8, p. 127-134, August 2000.
[Spiliopoulou & Faulstich, 1998] SPILIOPOULOU, M.; FAULSTICH, L. C. WUM: A Web Utilization Miner. In: INTERNATIONAL WORKSHOP ON THE WEB AND DATABASES, 1998, Valencia. Proceedings...1998.
[Spiliopoulou et al., 1999] SPILIOPOULOU, M.; FAULSTICH, L. C.; WINKLER, K. A Data Miner Analyzing the Navigational Behavior of the Web Users. In: ACAI’99, 1999, Creta. Proceedings of Workshop On Machine Learning In User Modeling...1999.
[Spiliopoulou & Pohle, 2001] SPILIOPOULOU, M.; POHLE, C. Data Mining to Measure and Improve the Success of Web Sites. Journal of Data Mining and Knowledge Discovery, n. 5, p. 1-2, January 2001.
[Srikant & Agrawal, 1996] SRIKANT, R.; AGRAWAL, R. Mining Sequential Patterns: Generalizations and Performance Improvements. In: INTERNATIONAL CONFERENCE ON EXTENDING DATABASE TECHNOLOGY, 5., 1996, Avignon. Proceedings... 1996. p. 3-17.
[Srivastava et al., 2000] SRIVASTAVA, J., et al. Web Usage Mining: Discovery and Application of Usage Patterns from Web Data. ACM SIGKDD Explorations, v. 1, n. 2, p. 12-23, January 2000.
[Staab et al., 2001] STAAB, S. et al. Knowledge Processes and Ontologies. IEEE Intelligent Systems, v. 16, n. 1, p. 26-34, Jan/Feb 2001.
[Stedman, 1997] STEDMAN, C. Wal-Mart Mines for Forecasts. ComputerWorld, p. 63-64, May 1997.
[Studer et al., 2000] STUDER, R. et al. Situation and Perspective of Knowledge Engineering. In: CUENA, J., et al. Knowledge Engineering and Agent Technology. Amsterdam: IOS Press, 2000.
[Tucker, 1996] TUCKER, J. ShopKo Uses Datamining to Compete. Datamation, p. 42, May 1996.
[Wang, 1997] WANG, Ke. Discovering Patterns from Large and Dynamic Sequential Data. Journal of Intelligent Information System, v. 9, n. 1, p. 33-56, 1997.
[Wang, 2000] WANG, Y. Web mining and Knowledge Discovery of Usage Patterns. In: INTERNATIONAL WEB-AGE INFORMATION MANAGEMENT CONFERENCE - WAIM’2000, 1., 2000, Shanghai. Proceedings... 2000. p. 227-232.
[Wang et al., 2002] WANG, H.; MYLOPOULOS, J.; LIAO, S. Intelligent Agents and Financial Risk Monitoring Systems. Communications of the ACM, v. 45, n. 3, p. 83-88, March 2002.
133
[Wasserman, 2000] WASSERMAN, M. Mining Data. Regional Review, v. 10, n. 3, 2000.
[Weiss & Indurkhya, 1998] WEISS, S. M.; INDURKHYA, N. Predictive Data Mining: A Practical Guide. San Francisco: Morgan Kaufmann Publishers, Inc., 1998.
[Wexelblat & Maes, 1997] WEXELBLAT; M. Footprints: History-rich Web Browsing. In: CONFERENCE ON COMPUTER-ASSISTED INFORMATION RETRIEVAL - RIAO, 1997. Proceedings... 1997. p. 75-84.
[Wu, 2002] WU, J. Business Intelligence: The Value in Mining Data. DM Review Online, February 2002.
[Xue et al., 2002] XUE, G., et al. Log Mining to Improve the Performance of Site Search. In: WISE'02, 2002, Singapore. Proceedings of Workshop On Mining Enhanced Web Search...2002.
[Yao et al., 2001] YAO, Y.Y., et al. Web Intelligent (WI): Research Challenges and Trends in the New Information Age. In: WEB INTELLIGENCE: RESEARCH AND DEVELOPMENT, 2001. Notes... Lecture Notes on Artificial Intelligence. Springer-Verlay, 2001.
[Yen & Cho, 2001] YEN, S.; CHO, C. An Efficient Approach for Updating Sequential Patterns Using Database Segmentation. International Journal of Fuzzy Systems, v. 3, n. 2, p. 422-431, June 2001.
[Zaïane et al., 1998] ZAÏANE, O. R.; XIN, M.; HAN, J. Discovering Web Access Patterns and Trends by Applying OLAP and Data Mining Technology on Web Logs. In: ADVANCES IN DIGITAL LIBRARIES CONFERENCE – ADL’98, 1998, Santa Barbara. Proceedings... 1998. p. 19-29.
[Zaïane, 1999a] ZAÏANE, O. R. Resource and Knowledge Discovery from the Internet and Multimedia Repositories. 1999. Ph.D. thesis - School of Computing Science, Simon Fraser University, Vancouver.
[Zaïane, 1999b] ZAÏANE, O. R. Principles of Knowledge Discovery in Databases. 1999. 15f. Technical Report CMPUT690, Department of Computing Science, University of Alberta, Edmonton.
[Zaïane, 2000] ZAÏANE, O. R. Web Mining: Concepts, Practices and Research. In: BRAZILIAN SYMPOSIUM ON DATABASES - SBBD'2000, 14., 2000, João Pessoa. Conference Notes... 2000. p. 410-474.
[Zaki, 1997] ZAKI, M. J. Fast Mining of sequential Patterns in Very Large Databases. 1997. Technical Report 558, The University of Rochester, New York.
[Zaki, 2001] ZAKI, M. J. SPADE: An Efficient Algorithm for Mining Frequent Sequences. Machine Learning, v. 40, p. 31-60, 2001.
134
[Zheng et al., 2002] ZHENG, Q., et al. The Algorithms of Updating Sequential Patterns. In: SIAM CONFERENCE ON DATA MINING, 2., 2002. Proceedings of 5th International workshop on high performance data mining...2002.
[Zhong et al., 2000] ZHONG, N. et al. Web Intelligence (WI). In: IEEE INTERNATIONAL COMPUTER SOFTWARE AND APPLICATIONS CONFERENCE - COMPSAC, 24., 2000. Proceedings... 2000.
135
Apêndice A: Algoritmos para Prospecção de Dados
Neste apêndice serão apresentados, sumariamente, alguns dos algoritmos de
prospecção de dados que foram estudados durante este trabalho, mas que não se
mostraram compatíveis para a solução do problema proposto.
Algoritmos para Prospecção de Regras de Associação
[Agrawal et al., 1993] introduziu o problema de prospecção de regras de
associação entre conjuntos de itens de um grande banco de dados de transações de
clientes, sendo cada transação constituída de itens escolhidos por um cliente em uma
compra. O problema descrito é modelado formalmente da seguinte forma:
Tomando-se I = I1, I2,..., Im um conjunto de atributos binários chamados itens e
T um banco de dados de transações, cada transação t é representada por um vetor
binário, com t[k]=1 se t foi um item comprado e t[k]=0, caso contrário. Tomando-se X
como um conjunto de alguns itens de I, dizemos que uma transação t satisfaz X se para
todos os itens em X, t[k]=1. Uma regra de associação é representada por uma
implicação da forma X ⇒ Ij, onde X é um conjunto de alguns itens em I, e Ij é um item
simples em I que não está presente em X. A regra X ⇒ Ij é satisfeita no conjunto de
transações T com o fator de confiança 0 <= c <= 1 se, e somente se, pelo menos c% das
transações em T que satisfaçam X também satisfaçam Ij. Usa-se a notação X ⇒ Ij | c para
especificar que a regra X ⇒ Ij tem um fator de confiança c.
Dado o conjunto de transações T, o interesse é gerar todas as regras que
satisfaçam certas restrições adicionais de duas formas diferentes:
1. Restrições sintáticas: restrições que determinam itens que podem aparecer
em uma regra.
2. Restrições de Suporte (s): restrições que se referem ao número de transações
em T que suportam uma regra. O suporte para uma regra é definido como a
fração de transações em T que satisfazem à união de itens no conseqüente e
no antecedente da regra.
136
O problema de prospecção de regras de associação pode ser descomposto em
dois subproblemas:
1. Encontrar todos os itemsets freqüentes.
2. Gerar, a partir de cada large itemset, as regras que usam itens deste itemset
freqüentes.
Em resumo, o problema de prospecção de regras de associação a partir de um
conjunto de transações T, pode ser caracterizado pela busca de todas as regras que
possuem suporte e confiança iguais ou superiores a valores limiares pré-definidos, ou
seja, encontrar associações, correlações e padrões freqüentes em conjuntos de itens ou
objetos de um banco de dados transacional ou outros repositórios de informações.
- Prospecção de padrões freqüentes
Um padrão freqüente é um conjunto de atributos, chamados itens, com um
determinado suporte limiar mínimo, minsup, definido pelo usuário. A prospecção de
padrões freqüentes é a principal fase na maioria das aplicações de prospecção de dados.
A complexidade deste problema é exponencial no tamanho das relações de entrada, pois
estas relações têm que ser percorridas várias vezes durante o processo para a contagem
dos suportes dos padrões, portanto são requeridos algoritmos otimizados para a
prospecção de padrões freqüentes.
Abordagens para prospecção de padrões freqüentes
Três abordagens têm sido propostas para a prospecção de padrões freqüentes
[Bastide et al., 2000]:
1. A primeira abordagem é baseada no processo de iterativamente percorrer o
conjunto de todos os padrões de forma nivelada e durante cada iteração,
correspondente a um nível, é criado um conjunto de padrões candidatos
através da junção de padrões freqüentes descobertos durante as iterações
anteriores, são contados os suportes de todos os padrões candidatos e os
padrões não freqüentes são descartados. O algoritmo mais proeminente
desta abordagem é o Apriori, proposto por [Agrawal et al., 1993], sendo que
uma grande variedade de modificações para esta abordagem tem sido
proposta objetivando-se maximizar diferentes aspectos de eficiência.
2. A segunda abordagem é baseada na extração de padrões freqüentes
máximos, dos quais todos superconjuntos são não freqüentes e todos os
subconjuntos são freqüentes. Essa abordagem combina uma inspeção 137
nivelada bottom-up com uma inspeção top-down para rapidamente encontrar
os padrões freqüentes máximos, dos quais são derivados todos os demais
padrões freqüentes. Resultados experimentais têm mostrado que essa
abordagem é particularmente eficiente para a extração de padrões freqüentes
máximos, mas quando aplicada na extração de todos os padrões freqüentes o
seu desempenho decresce drasticamente, pela necessidade de se percorrer
por mais uma vez o banco de dados realizando-se aproximadamente um teste
de inclusão entre cada padrão freqüente e cada um de seus objetos. O
algoritmo mais proeminente desta abordagem é o Max-Miner [Bayardo Jr.,
1998].
3. A terceira abordagem, representada pelo algoritmo Close [Pasquier et al.,
1999], é baseada na extração de forma nivelada dos padrões freqüentes
fechados e de seus suportes em um banco de dados. Um padrão fechado é o
maior padrão comum de um conjunto de objetos do banco de dados, e
assim, todos os padrões freqüentes e seus suportes são derivados dos padrões
freqüentes fechados e seus suportes, sem acessar o banco de dados.
Conseqüentemente nem todos os padrões são considerados durante a parte
computacionalmente mais dispendiosa do algoritmo (que é a contagem dos
suportes dos padrões) e o espaço de busca é drasticamente reduzido,
especialmente para dados correlacionados, nos quais experimentos têm
mostrado que esta abordagem é muito mais eficiente que as duas anteriores.
Algoritmos representantes da primeira abordagem
A Tabela A.1 resume a notação usada na maioria dos algoritmos estudados:
k-itemset Um itemset contendo k itens.
Gk Conjunto de k-itemsets freqüentes (aqueles com suporte mínimo). Cada membro
desse conjunto tem dois campos: i) itemset e ii) contador de suporte
Ck Conjunto de k-itemsets candidatos (itemsets potencialmente freqüentes). Cada
membro desse conjunto tem dois campos: i) itemset e ii) contador de suporte.
C k Conjunto de k-itemsets candidatos quando TIDs das transações geradas são guardadas
associadas com os candidatos.
Tabela A.1: Notação Utilizada na Maioria dos Algoritmos Estudados.
138
Apriori [Agrawal & Srikant, 1994]
O algoritmo Apriori gera os itemsets candidatos a serem contados em uma
inspeção no banco de dados usando somente os itemsets encontrados como freqüentes
na inspeção anterior – sem considerar as transações no banco de dados. A idéia básica é
que qualquer subconjunto de um itemset freqüente deve ser freqüente.
Conseqüentemente, os itemsets candidatos tendo k itens podem ser gerados pela junção
dos itemsets freqüentes tendo k-1 itens, e excluindo-se aqueles itemsets que contenham
qualquer subconjunto de itens não freqüentes. Este procedimento resulta na geração de
um número muito menor de itemsets candidatos. O primeiro passo do algoritmo
simplesmente conta as ocorrências dos itens para determinar o k-itemset freqüente. Uma
inspeção subseqüente, chamada inspeção k, consiste de duas fases. Primeiro, os itemsets
freqüentes Gk-1 encontrados na (k-1)-ésima inspeção são usados para gerar os itemsets
candidatos Ck, usando a função GeraCandidato, ilustrada na Figura A.2. Em seguida, o
banco de dados é inspecionado e o suporte dos candidatos em Ck é contado. Para uma
contagem mais rápida é necessário determinar eficientemente os candidatos em Ck que
são contados em uma dada transação t, o que é feito pela função Subconjunto.
1) G1 = {Conjunto de itemsets freqüentes de tamanho 1}
2) Para (k = 2; Gk-1 <> ∅; k++) faça
3) início
4) Ck = GeraCandidato (Gk-1); // novos candidatos
5) Para toda transação t ∈ T faça
6) início
7) Ct = Subconjunto (Ck, t); // candidatos contidos em t
8) Para todo candidato c ∈ Ct faça
9) c.contador ++;
10) fim
11) Gk = {c ∈ Ck | c.count >= minsup}
12) fim
13) G = União de todos os Gk's;
Figura A.1: Algoritmo Apriori.
139
A função GeraCandidato é composta por dois passos: a junção e a poda. No
passo de junção, a função toma como argumento Gk-1, o conjunto de todos os (k-1)-
itemsets freqüentes e retorna um superconjunto do conjunto de todos os k-itemsets
freqüentes, a partir da junção de Gk-1(p) e Gk-1 (q). Em seguida, no passo da poda,
exclui-se todos os itemsets c ∈ Ck tais que algum (k-1)-subconjunto de c não esteja em
Gk1.
{Junção}
Insert into Ck
Select p.item1, p.item2, ... , p.itemk-1, q.itemk-1
From Gk-1(p), Gk-1 (q) {elementos p e q de Gk-1}
where p.item1 = q.item1, ..., p.itemk-2 = q.itemk-2, p.itemk-1< q.itemk-
{Poda}
para todo c ∈ Ck faça
para todo s ⊂ c e |s| = k-1 faça
Se s ∉ Gk-1 então elimine c de Ck.
Figura A.2: Função GeraCandidato
Seguindo estes passos, o algoritmo Apriori, ilustrado na Figura A.1, gera um
itemset G dos conjuntos de itens da base de dados com suporte maior que um suporte
mínimo especificado, e de posse deste conjunto G será possível extrair as regras de
associação dos itens.
Algumas Variações do Algoritmo Apriori
AprioriTid [Agrawal & Srikant, 1994]
O algoritmo AprioriTid é uma variação do algoritmo Apriori, e também usa a
função GeraCandidato, ilustrada na figura A.2, para determinar os itemsets candidatos
antes da inspeção inicial. A característica interessante desse algoritmo é que ele tem a
propriedade adicional de não usar o banco de dados para as contagens de suportes dos
itemsets candidatos após a primeira inspeção. O conjunto C k é usado para este
propósito, minimizando muito o esforço de leitura.
140
Cada membro do conjunto C k é da forma <TID, {Xk}>, onde cada Xk é um k-
itemset potencialmente freqüente presente na transação com identificador TID. Para
k=1, C k corresponde ao banco de dados T. Para k > 1, C k é gerado pelo algoritmo. O
membro de C k correspondente à transação t é <t.TID, {c ∈ Ck | c contido em t} >. Se
uma transação não contém qualquer candidato k-itemset, então C k não tem uma entrada
para esta transação. Assim, o número de entradas em C k pode ser menor que o número
de transações no banco de dados, especialmente para valores grandes de k. Entretanto,
para valores pequenos de k, cada entrada pode ser maior que a transação correspondente
pois uma entrada em Ck inclui todos os k-itemsets candidatos contidos na transação.
AprioriHybrid [Agrawal & Srikant, 1994]
Experimentos mostram que nas primeiras inspeções o algoritmo Apriori é mais
eficiente que o AprioriTid. Entretanto, AprioriTid é mais eficiente que o Apriori nos
passos posteriores. Nas últimas inspeções do banco de dados, o número de itemsets
candidatos reduz, porém Apriori ainda examina todas as transações do banco de dados.
Por outro lado, ao invés de inspecionar o banco de dados, AprioriTid inspeciona C k
para obter a contagem de suportes, e a cardinalidade de C k já se tornou menor que o
tamanho do banco de dados. Baseado nesta observação, foi projetado um algoritmo
híbrido, que chama-se AprioriHybrid, que usa Apriori nos passos iniciais e troca para
AprioriTid quando ele espera que o conjunto C k no final da inspeção caiba na memória.
A seguinte heurística é usada para estimar se C k caberá na memória na próxima
inspeção. No fim da inspeção corrente, tem-se a contagem dos candidatos em Ck .
Disto, estima-se qual o tamanho de C k se ele foi gerado. Se C k neste passo for
pequeno o bastante para caber na memória, e há menos candidatos freqüentes no passo
corrente que no passo anterior, troca-se para o algoritmo AprioriTid. A próxima
condição é adicionada para evitar a troca quando C k na inspeção corrente cabe na
memória, mas C k na próxima inspeção possa não caber. Resultados experimentais
mostram que o AprioriHybrid tem desempenho melhor que o Apriori em quase todos os
casos, porém é um pouco pior que o Apriori se a inspeção em que a troca for feita for a
última, pois incorrerá o custo para a troca sem se ter benefícios.
141
Partição [Savarese et al., 1995]
Comparado com os algoritmos anteriores, o algoritmo de Partição é
fundamentalmente diferente de todos eles, pois ele inspeciona o banco de dados no
máximo duas vezes para gerar todas as regras de associação significantes, tendo as
seguintes vantagens adicionais:
1) Pode gerar resultados aproximados na metade do tempo, o que pode ser útil
quando tais resultados são suficientes;
2) É inerentemente paralelo por natureza e pode ser paralelizado com o mínimo
de comunicação e sincronização entre os nós de processamento.
Supondo-se que dado um pequeno conjunto de itemsets freqüentes, então o
suporte para cada um deles pode ser testado em uma inspeção do banco de dados e os
atuais itemsets freqüentes podem ser descobertos. Claramente esta abordagem trabalha
somente se o conjunto dado contêm todos os atuais itemsets freqüentes. O algoritmo de
Partição executa esta tarefa com duas inspeções do banco de dados. Na primeira fase o
algoritmo logicamente divide o banco de dados em um número de partições não
sobrepostas. As partições são consideradas uma de cada vez e todos os itemsets
freqüentes para cada partição são gerados e intercalados para gerar um conjunto de
todos os potenciais itemsets freqüentes. Na segunda fase, o suporte atual desses itemsets
é gerado e os itemsets freqüentes são identificados. O tamanho das partições é escolhido
de tal forma que cada partição possa ser acomodada na memória principal de forma que
as partições são inspecionadas somente uma vez em cada fase. Utilizando-se uma
partição, a performance é melhor que se utilizando 10 partições em todos os casos.
Partição-1 executou melhor que o Apriori exceto nos casos em que o suporte mínimo é
alto. Até mesmo a Partição-10 executou melhor que o Apriori em muitos casos para
suportes baixos. Fatores estudados demonstram que o algoritmo de Partição é
especialmente melhor para banco de dados muito grande e em ambientes com contenção
de recursos.
Pascal [Bastide et al., 2000]
O algoritmo Pascal é uma simples e eficiente otimização do algoritmo Apriori,
que minimiza tanto quanto possível o número de contagens executadas de suporte dos
padrões quando se extraem os padrões freqüentes. Este método baseia-se no conceito de
padrões-chave, onde um padrão-chave é um padrão mínimo de uma classe de
equivalência reunindo todos os padrões comuns dos mesmos objetos do banco de dados.
Conseqüentemente todos os padrões em uma classe de equivalência têm o mesmo 142
suporte e os suportes dos padrões não-chaves de uma classe de equivalência podem ser
determinados usando os suportes dos padrões-chave dessa classe. Com este método
somente o suporte dos padrões-chave (e de alguns padrões não freqüentes) é
determinado a partir do banco de dados, enquanto os suportes dos padrões freqüentes
não-chaves são derivados dos suportes dos padrões-chave freqüentes. Em resumo, o
algoritmo Pascal trabalha exatamente como o algoritmo Apriori, mas conta somente os
suportes que não podem ser derivados de suportes já computados. Assim, pode-se em
cada nível, restringir a contagem no banco de dados de alguns candidatos. Além disto,
em alguns níveis todos os padrões candidatos podem ser conhecidos como padrões não-
chaves, podendo todos os padrões freqüentes restantes e seus suportes serem derivados
sem acessar mais o banco de dados. No pior caso, isto é, em dados fracamente
correlacionados, todos os padrões candidatos são também padrões candidatos-chave, o
algoritmo se comporta exatamente igual ao Apriori sem nenhum overhead significante.
DIC [Brin et al., 1997]
DIC (Dynamic Itemset Counting) é um algoritmo que reduz o número de
inspeções feitas nos dados enquanto guarda o número de itemsets que são contados em
qualquer inspeção. DIC aponta a questão de alto nível de quando contar quais itemsets e
tem uma velocidade substancialmente maior que o Apriori, particularmente quando o
Apriori requer muitas inspeções. Para mostrar que itemsets são freqüentes pode-se
contá-los, entretanto, é impossível contar todos os itemsets não freqüentes. Felizmente,
é suficiente contar somente aqueles mínimos (os itemsets que não incluem qualquer
outro itemset não freqüente) e assim, se um itemset é não freqüente, todos os seus
superconjuntos são não freqüentes também. Eles formam o topo do limite entre os
itemsets freqüentes e não freqüentes, é chamado de limite negativo. DIC começa
contando somente os 1-itemsets e então rapidamente adiciona contadores 2, 3, 4, ..., k-
itemsets. Após somente algumas inspeções nos dados ele termina contando todos os
itemsets. Existem vários benefícios de DIC, sendo o mais importante o desempenho. Se
os dados são razoavelmente homogêneos em todo o arquivo e o intervalo é
razoavelmente pequeno, e o algoritmo geralmente faz duas inspeções, o que o torna
consideravelmente mais rápido que o Apriori que deve fazer tantas inspeções quanto o
tamanho máximo de um itemset candidato. Uma desvantagem de DIC é que ele é
sensível à homogeneidade dos dados. Em particular, se os dados são muito
correlacionados podemos não perceber que um itemset é atualmente freqüente até
termos o contado na maioria das transações. Se isto acontece, então não trocamos nosso 143
limite hipotético e começamos a contar dos superconjuntos dos itemsets até termos
chegado ao fim da contagem do itemset. Conseqüentemente, é vantajoso ter os itens que
ocorrem em muitos itemsets sendo os últimos na ordenação dos itens e os itens que
ocorre em poucos itemsets sendo os primeiros. Implementações de DIC e Apriori são
basicamente as mesmas, visto que Apriori pode ser considerado como um caso especial
de DIC – o caso onde o tamanho do intervalo é o tamanho do arquivo de dados. Ambos,
DIC e Apriori executam nos dados sintéticos e de censo, mas DIC tem melhor
desempenho na maioria dos testes, executando 39% mais rápido para suporte de 0.005.
Existem diversas de variações de DIC, pois sua natureza dinâmica o torna muito flexível
e pode ser adaptado para prospecção paralela e incremental.
RARM [Das et al., 2001]
RARM (Rapid Association Rule Mining) é um algoritmo que tenta quebrar a
barreira da velocidade. RARM foi comparado com o clássico algoritmo Apriori e sua
performance superou o Apriori em duas ordens de magnitude (100 vezes), muito mais
que algoritmos recentes de prospecção estão hábeis a atingir. Para atingir grandes
velocidade até mesmo com baixos valores de suporte, RARM constrói uma nova
estrutura chamada SOTrieIT (Support-Ordered Trie Itemset), que armazena os
contadores de suporte de todos os 1-Itemsets e 2-itemsets no banco de dados. Todas as
transações que chegam são pré-processadas; todos 1-itemsets e 2-itemsets são extraídos
de cada transação. A extração da informação é usada para atualizar a SOTrieIT, que é
então ordenada de acordo com os contadores de suporte de cada nodo em ordem
descendente, possibilitando que rapidamente se descubra os 1-itemsets e 2-itemsets sem
inspecionar o banco de dados. A necessidade de gerar 1-itemsets candidatos e 2-itemsets
candidatos constitui o gargalo na geração de itemsets freqüentes, como observado em
[Sarda & Srinivas, 1998]. Conseqüentemente, pela eliminação desse passo, RARM
atinge aumentos significantes de velocidade, embora subseqüentemente, ele também
aplique o algoritmo Apriori na obtenção de itemsets de tamanhos maiores.
144
DHP [Park et al., 1995]
DHP é um algoritmo eficaz baseado em hash para a geração de 2-itemsets
candidatos. Explicitamente, o número de 2-itemsets candidatos gerados pelo algoritmo
proposto é, em ordem de magnitude, menor que aqueles dos métodos anteriores, assim
resolvendo o gargalo da performance. Quanto maior for o conjunto de candidatos, maior
é o custo de processamento requerido para descobrir os itemsets freqüentes. Uma outra
questão relacionada ao desempenho é a quantidade de dados que tem que ser
inspecionada durante a descoberta dos itemsets freqüentes. Reduzindo-se o número de
transações a serem inspecionadas e podando-se o número de itens em cada transação
pode-se melhorar a eficiência da prospecção de dados nos últimos estágios.
Essencialmente, o algoritmo DHP usa a técnica de hashing para filtrar itemsets
desnecessários para a próxima geração de itemsets candidatos. Inicialmente, o algoritmo
considera um conjunto de 1-itemsets freqüentes e faz uma tabela hash (isto é, H2) para
2-itemsets. No próximo passo, o conjunto de itemsets candidatos Ck baseado na tabela
hash (isto é, Hk) gerada no passo anterior, determina o conjunto de k-itemsets freqüentes
Lk, que reduz o tamanho do banco de dados para os próximos itemsets freqüentes e faz
uma tabela hash para candidatos de (k+1)- itemsets freqüentes. O terceiro passo, é
basicamente o mesmo que o segundo, exceto por não empregar uma tabela hash. Note
que DHP é particularmente poderoso para determinar itemsets freqüentes em estágios
iniciais, assim melhorando o gargalo de desempenho. Como o Apriori, DHP também
gera um k-itemset por Lk-1. Entretanto, DHP é o único que emprega o vetor de bit, que é
construído num passo anterior, para testar a validade de cada k-itemset. Ao invés de
incluir todos os k-itemsets de Lk-1 * Lk-1 em Ck, DHP adiciona um k-itemset em Ck
somente se o k-itemset está ranqueado em uma entrada hash cujo valor é maior ou igual
ao suporte, o que reduz drasticamente o tamanho de Ck. O tempo de execução de DHP
no primeiro passo é levemente maior que do Apriori devido ao overhead extra requerido
para a geração de H2. Entretanto, DHP incorre significantemente em menores tempos de
execução que o Apriori nos demais passos, não apenas no segundo passo quando a
tabela hash é usada pelo DHP para facilitar a geração de C2, mas também nos demais
passos quando o mesmo procedimento é usado, mostrando-se a vantagem de se
inspecionar bancos de dados menores.
145
FP-growth [Han et al., 2000b]
Recentemente, foi proposto o algoritmo Frequent Pattern Growth (FP-growth)
que atingiu impressionantes resultados comparado ao Apriori. Ele elimina
completamente o gargalo da geração de candidatos pelo uso uma nova estrutura
chamada Frequent Pattern Tree (FP-tree) que armazena informações de itemsets
críticos. Essa estrutura compacta também remove a necessidade de inspecionar o banco
de dados e é construída usando somente duas inspeções. Na primeira inspeção, 1-
itemsets freqüentes L1 são obtidas e armazenadas em ordem descendente de suporte. Na
segunda inspeção, itens nas transações são primeiro ordenados de acordo com a ordem
de L1. Esses itens ordenados são usados para construir a FP-tree. O algoritmo FP-
growth então procede recursivamente fazendo a prospecção das FP-trees de tamanho
decrescente para gerar itemsets freqüentes sem a geração de candidatos e inspeções no
banco de dados. Ele faz o exame de todos os padrões base da FP-tree que consiste do
conjunto de itemsets freqüentes ocorrendo com o padrão sufixo. FP-trees condicionais
são construídas desses padrões condicionais bases e a prospecção é feita recursivamente
com tais árvores para descobrir itemsets freqüentes de vários tamanhos. Porém, a
construção e uso das FP-trees é complexa e faz com que o desempenho do FP-growth
seja igualitário ao Apriori com limiares de suportes de 3% para cima, mostrando
aumento de velocidade significante apenas com suportes abaixo de 1.5%.
Algoritmos representantes da segunda abordagem
Max-Miner [Bayardo Jr., 1998]
O Max-Miner é um algoritmo com escala aproximadamente linear ao número de
padrões máximos embutidos em um banco de dados sem levar em consideração o
tamanho do padrão mais longo, enquanto os algoritmos anteriores baseados no Apriori
têm escala exponencial com o tamanho do maior padrão. Experimentos com dados reais
mostram que quando os padrões são longos, este algoritmo é mais eficiente em uma
ordem de magnitude ou mais. Em sua grande parte, algoritmos de prospecção de
padrões têm sido desenvolvidos para operar em bancos de dados onde os padrões
maiores são relativamente curtos. Interessantes conjuntos de dados com padrões longos
incluem aqueles compostos de resultados de questionários (pessoas tendem a responder
similarmente a muitas questões), transações de vendas detalhando as compras feitas por
clientes regulares durante um longo tempo, e dados biológicos dos campos de DNA e
análise de proteínas. Quase sempre todo algoritmo de prospecção de padrões propostos 146
recentemente é uma variação do Apriori. Porém alguns estudos recentes demonstraram
que algoritmos como Apriori são inadequados em conjuntos de dados com padrões
longos. Apriori emprega uma busca bottom-up que enumera todos os conjuntos de
dados simples. Isto implica que para produzir um conjunto de itens freqüentes de
tamanho l, ele deve produzir todos os 2l de seus subconjuntos uma vez que eles também
devem ser freqüentes. Essa complexidade exponencial restringe os algoritmos baseados
no Apriori a serem eficazes apenas para descoberta de padrões curtos. Para superar este
problema, foi proposto o algoritmo Max-Miner para eficientemente extrair somente
conjunto de itens freqüentes máximos, onde um conjunto de itens é freqüente máximo
se ele não tem nenhum superconjunto que é freqüente. Pelo motivo de que qualquer
conjunto de itens freqüentes é um subconjunto de um conjunto de itens freqüentes
máximos, a saída do Max-Miner implicitamente e concisamente representa todos os
conjuntos de itens freqüentes. Em outros conjuntos de dados onde os padrões não são
tão grandes, os ganhos são mais modestos. Na prática, Max-Miner executa em tempo
aproximadamente linear ao número de conjuntos de itens de padrões freqüentes
máximos e o tamanho do banco de dados, não levando em consideração o tamanho do
maior conjunto de itens freqüentes. Max-Miner é próspero porque abandona uma estrita
varredura top-down do espaço de busca, e ao contrário, sempre tenta olhar à frente “look
ahead” para rapidamente identificar longos conjuntos de dados freqüentes. Por
identificar antes um longo conjunto de dados freqüentes, Max-Miner pode podar todos
os seus subconjuntos de consideração. Max-Miner usa uma heurística para refinar sua
busca em um esforço para identificar o que pode freqüentemente determinar quando um
novo conjunto de itens candidato é freqüente antes de acessar o banco de dados. A idéia
é utilizar as informações conseguidas em inspeções anteriores do banco de dados para
computar um bom limite inferior no número de transações que contém o conjunto de
dados. Esse algoritmo eficientemente identifica todos os conjuntos de itens dos padrões
freqüentes máximos até mesmo quando o espaço de todos os conjuntos de itens de
padrões freqüentes máximos tem por si só, intratabilidade por tamanho. Max-Miner
pode usar as mesmas estruturas de dados que o Apriori para eficientemente computar
suportes de conjuntos de itens. A estrutura primária usada pelo Apriori é a árvore hash
para indexar conjuntos de itens candidatos. Max-Miner usa a árvore hash para indexar
somente a cabeça de cada grupo candidato. Para cada transação no conjunto de dados,
Max-Miner usa a árvore hash para rapidamente observar todos os grupos candidatos
cuja cabeça aparece na transação.
147
Teorema (corretude): Max-Miner retorna todos e somente os conjuntos de itens
freqüentes máximos no dado conjunto de dados dado.
Prova: O fato de Max-Miner identificar e armazenar todo conjunto de itens
freqüentes máximos segue da perfeição de uma árvore de busca de enumeração de
conjunto e o fato que ramos da árvore de enumeração de conjunto ser podada se, e
somente se, eles levam apenas a conjuntos de itens não freqüentes ou conjuntos de itens
freqüentes não máximos. O fato de Max-Miner retornar somente aqueles conjuntos de
dados que são freqüentes máximos dá-se a operação dentro do corpo de Max-Miner que
continuamente remove qualquer conjunto de itens I se um superconjunto freqüente de I
é conhecido. Max-Miner, como Apriori, facilmente manipula dados residentes em disco
porque requer somente uma transação por vez na memória. Também como o Apriori, o
número de varreduras nos dados feitas pelo Max-Miner é limitado pelo tamanho do
conjunto de itens freqüentes mais longo. Para Apriori este limite é aproximadamente
ajustado. Max-Miner, por outro lado, freqüentemente executa menos varreduras no
banco de dados, como é mostrado na avaliação.
Teorema (Eficiência): Max-Miner faz no máximo l + 1 varreduras no conjunto
de dados, onde l denota o tamanho do conjunto de itens freqüentes mais longo.
Prova: Pela maneira pela qual Max-Miner gera grupos candidatos, é fácil ver que
durante a varredura K, a cabeça de um grupo candidato tem exatamente K-1 itens. Após
a varredura l + 1, para qualquer grupo candidato g e qualquer de seus itens de rabo i,
h(g) ∪ {i} será não freqüente, caso contrário poderíamos ter um conjunto de itens
freqüentes mais longo que l. Isto implica que o próximo conjunto de grupos candidatos
será vazio, neste caso o algoritmo termina.
GenMax [Gouda & Zaki, 2001]
GenMax é um novo algoritmo que utiliza busca backtracking para
eficientemente enumerar todos os padrões máximos, usando um número de otimizações
para rapidamente podar uma grande porção do subconjunto do espaço de busca. Ele usa
uma nova técnica de enfoque progressivo para eliminar itemsets não-máximos e usa
propagação de diffset para rapidamente verificar a freqüência. Os autores conduziram
uma caracterização experimental extensiva de GenMax comparando-o com métodos
como MaxMiner, e descobrimos que os métodos têm variações de desempenho
dependendo das características do banco de dados (principalmente a distribuição dos
padrões freqüentes máximos por duração). GenMax é atualmente o melhor método para
enumerar o conjunto exato de padrões máximos. 148
Algoritmo representante da terceira abordagem
Algoritmo Close [Pasquier et al., 1999]
O algoritmo Close é um novo método para prospecção em que se utiliza a poda
de conjuntos fechados para fazer a prospecção de regras de associação em grandes
bancos de dados. Ao contrário dos demais algoritmos que são todos baseados na poda
das junções de itemsets, Close é baseado na poda das junções de itemsets fechados, que
é um conjunto máximo de itens comuns a um conjunto de objetos. A estrutura utilizada
por Close pode ser usada como um framework para a descoberta de regras de
associação dadas às propriedades básicas de que todos subitemsets fechados de um
itemset fechado freqüente são freqüentes, todos subitemsets fechados de um itemset
fechado não freqüente são não freqüentes, e de que o conjunto de itemsets freqüentes
máximos é idêntico ao conjunto de itemsets fechados freqüentes máximos. Como o
tamanho das junções dos itemsets fechados de um banco de dados é freqüentemente
muito menor que os itemsets, Close pode reduzir ambos, o número de inspeções do
banco de dados e o overhead da CPU decorrente da busca por itemsets freqüentes. Em
todos os casos, Close tem a habilidade de descobrir regras de associação para baixos
valores de suporte, o que o Apriori não pode realizar, pelo motivo de seus requisitos de
memória. Experimentos comparando Close a versões otimizadas de Apriori mostraram
que Close é muito mais eficiente para prospecção de dados densos e/ou correlacionados,
tais como dados do estilo censo, e executa razoavelmente bem para dados do estilo
cestas de compras.
Outros Algoritmos para Prospecção de Regras de Associação
Existem diversos algoritmos para Prospecção de Regras de Associação e outros
para a descoberta e manutenção destas regras, como FUP [Cheung et al., 1996] e FUP2
[Cheung et al., 1997], porém, tais algoritmos fogem do escopo do trabalho proposto e
assim não são explicitados neste apêndice.
149
Algoritmos para Prospecção de Padrões Seqüenciais
Tratando-se de um grande banco de dados de transações de clientes, onde cada
transação consiste de um ID-cliente, o momento da transação e os itens comprados na
transação, [Agrawal & Srikant, 1995] introduziram o problema de prospecção dos
padrões seqüenciais em tais bancos de dados. Também companhias de catálogos
coletam tais dados usando a ordem em que são recebidos.
Tendo-se um banco de dados D de transações de clientes, sendo cada transação
consistindo dos seguintes campos: ID-cliente, momento da transação, e itens comprados
na transação. Nenhum cliente tem mais que uma transação no mesmo momento da
transação. Não se considerando as quantidades de itens comprados em uma transação:
cada item é uma variável binária representando se um item foi comprado ou não. Um
itemset é um conjunto de itens não vazio. Uma seqüência é uma lista ordenada de
itemsets. Sem perda de generalidade, assume-se que o conjunto de itens é mapeado para
um conjunto de inteiros contíguos. Denota-se um itemset i por (i1 i2 ... im), onde ij um
item e uma seqüência por (s1 s2 ... sm), sendo sj é um itemset. Uma seqüência < a1 a2 ...
an> está contida em uma outra seqüência < b1 b2 ... bm> se existem inteiros i1 < i2 < ...
< in tais que a1 ⊆ bi1, a2 ⊆ bi2, ... , an ⊆ bin,. Todas as transações de um cliente podem
ser vistas conjuntamente como uma seqüência, onde cada transação corresponde a um
conjunto de itens, e a lista de transações, ordenadas crescentemente pelo momento da
transação, corresponde a uma seqüência. Denomina-se cada seqüência de seqüência-
cliente. Formalmente, toma-se as transações de um cliente, ordenamos crescentemente
pelo momento da transação, sendo T1, T2, ... , Tn. Tomamos o conjunto de itens em Ti
sendo denotado por (Ti). A seqüência-cliente para este cliente é a seqüência <itemset
(T1) itemset (T2) ... itemset (Tn)>. Um cliente suporta uma seqüência s se s está contida
na seqüência-cliente para esse cliente. O suporte para uma seqüência é definido como a
fração de clientes totais que suportam esta seqüência. Dado um banco de dados D de
transações de clientes, o problema de prospecção de padrões seqüenciais é encontrar as
seqüências máximas entre todas as seqüências que têm um certo suporte mínimo. Cada
seqüência máxima representa um padrão seqüencial. Chama-se seqüência freqüente uma
seqüência que satisfaz o suporte mínimo. O caso de se encontrar itemsets freqüentes em
um conjunto de transações é considerado um problema de se encontrar padrões intra-
transações, enquanto que encontrar padrões seqüenciais é relacionado com padrões
inter-transações. Um padrão, no primeiro problema consiste de um conjunto não
150
ordenado de itens, enquanto no segundo caso é uma lista ordenada. O tamanho de uma
seqüência é o número de itemsets na seqüência. Uma seqüência de tamanho k é
chamada de k-seqüência. A seqüência formada pela concatenação de duas seqüências x
e y é denotada como x . y. O suporte de um itemset i é definido como a fração de
clientes que compram os itens em i em uma única transação. Assim o itemset i e a 1-
seqüência <i> têm o mesmo suporte. Um itemset com suporte mínimo é chamado de
itemset freqüente ou litemset. O problema de prospecção de padrões seqüenciais foi
dividido em duas fases a seguir:
1- Fase de Ordenação: O banco de dados D é ordenado, através do ID-cliente e
momento da transação. Este passo implicitamente converte o banco de dados
original em um banco de dados de seqüências de clientes.
Fase litemset : Nesta fase encontra-se o conjunto de todos os litemsets L, e
também simultaneamente encontra-se o conjunto de todas as 1-seqüências,
uma vez que esse conjunto é somente {<l > | l ∈ L}. O problema de encontrar
os itemsets freqüentes em um dado conjunto de transações de clientes, embora
com leve diferença na definição de suporte, foi considerado em [Agrawal et
al., 1993] e [Agrawal & Srikant, 1994]. Nestes artigos, o suporte para um
itemset foi definido como a fração de transações em que um itemset está
presente, enquanto que no problema de se encontrar padrões seqüenciais, o
suporte é a fração de clientes que compraram o itemset em qualquer uma de
suas transações. A adaptação de qualquer um dos algoritmos definidos em
[Agrawal & Srikant, 1994] para encontrar itemsets para o problema de
encontrar itemsets é direta aqui. A principal diferença é que o contador de
suporte deve ser incrementado somente uma vez por cliente mesmo se o
cliente compra o mesmo conjunto de itens em duas transações diferentes. O
conjunto de litemsets é mapeado para o conjunto de inteiros contínuos. A
razão para este mapeamento é que tratar litemsets como entidades simples,
podemos comparar a igualdade de dois litemsets em tempo constante, e
reduzir o tempo requerido para verificar se uma seqüência está contida em
uma seqüência-cliente.
2 - Fase de transformação: Precisa-se repetidamente determinar quais dos dados
conjuntos de seqüências freqüentes estão contidos em uma seqüência-cliente.
Para fazer este teste rapidamente, transforma-se cada seqüência-cliente em
uma representação alternativa. Em uma seqüência-cliente transformada, cada
transação é substituída pelo conjunto de todos os itemsets contidos naquela 151
transação. Se uma transação não contém qualquer itemset, não são retidas na
seqüência transformada. Se uma seqüência-cliente não contém qualquer
litemset, essa seqüência é retirada do banco de dados transformado.
Entretanto, ela ainda contribui para a contagem do número total de clientes.
Uma seqüência-cliente é agora representada por uma lista de conjuntos de
litemsets. Cada conjunto de litemsets é representado por {l1, l2, ... , ln}, onde li
é um litemset. Este banco de dados transformado é chamado DT. Dependendo
da disponibilidade de disco, pode-se fisicamente criar esse banco de dados
transformado ou então se pode fazer isto on-the-fly, à medida que lemos cada
seqüência durante uma inspeção (nos experimentos criou-se fisicamente o
banco de dados transformado). Usa-se o conjunto de litemsets para se
encontrar as seqüências desejadas.
3 - Fase de seqüenciação
Fase Máxima: Encontrar as seqüências máximas entre o conjunto de
seqüências freqüentes. Em alguns algoritmos esta fase é combinada com a
fase de seqüenciação para reduzir o tempo gasto na contagem das seqüências
não-máximas. Ou seja, tendo-se encontrado o conjunto de todas as seqüências
S na fase de seqüência, é aplicada uma outra fase do algoritmo para se
encontrar as seqüências máximas, de tamanho n.
AprioriAll [Agrawal & Srikant, 1995]
No algoritmo AprioriAll, em cada inspeção, usa-se as seqüências freqüentes dos
passos anteriores para gerar as seqüências candidatas e então são medidos os seus
suportes fazendo uma inspeção no banco de dados. No fim do passo, o suporte das
candidatas é usado para determinar as seqüências freqüentes. No primeiro passo, a saída
da fase litemset é usada para inicializar o conjunto de 1-seqüências freqüentes. As
candidatas são armazenadas em hash-tree [Agrawal & Srikant, 1994] para rapidamente
encontrar todos os candidatos contidos em uma seqüência cliente. A função
GeraCandidato toma como argumento Lk-1, o conjunto de todas as seqüências
freqüentes, e primeiramente faz a junção de Lk-1 com Lk-1, depois deleta todas as
seqüências c ∈ Ck tais que alguma (k-1)-subseqüência de c não esteja em Lk-1.
AprioriSome [Agrawal & Srikant, 1995]
Nesse algoritmo, na fase de avanço, somente conta-se seqüências de certos
tamanhos. Por exemplo, pode-se contar seqüências de tamanho 1, 2, 4 e 6 na fase de 152
avanço e contar seqüências de tamanho 3 e 5 na fase de retrocesso. A função Proxima
tem como parâmetro o tamanho de seqüências contadas no último passo e retorna o
tamanho de seqüências a serem contadas no próximo passo. Assim, esta função
determina exatamente quais seqüências são contadas, e equilibra o benefício entre o
tempo gasto na contagem de seqüências não máximas versus a contagem de extensões
de pequenas seqüências candidatas. Um extremo é Proxima(k) = k+1 (k é o tamanho
dos candidatos que foram contados na última vez), quando todas as seqüências não
máximas são contadas, mas nenhuma extensão de pequenas seqüências candidatas é
contada. Neste caso, AprioriSome degenera para AprioriAll. O outro extremo é uma
função Proxima(k)=1-k, quando quase nenhuma seqüência freqüente não máxima é
contada, mas um número elevado de extensões de pequenas seqüências candidatas é
contado. Toma-se hitk como o número de k-seqüências freqüentes (isto é, (|Lk| / |Ck|).
A idéia detrás da heurística é que como a porcentagem de candidatas contadas no passo
atual que tem suporte mínimo aumenta, o tempo gasto pela contagem das extensões de
pequenas seqüências candidatas diminui quando se salta um tamanho. Usa-se a função
GeraCandidato para gerar novas seqüências candidatas. Entretanto, no k-ésimo passo,
pode-se ter o conjunto de seqüência freqüente Lk-1 disponível enquanto não se conta as
(k-1)-seqüências candidatas. Neste caso, usa-se o conjunto de candidatas Ck-1 para gerar
Ck. A corretude é mantida, pois Ck-1 ⊇Lk-1. Na fase de retrocesso, conta-se as seqüências
para os tamanhos saltados durante a fase de avanço, após primeiro eliminar todas as
seqüências contidas em algumas seqüências freqüentes. Essas seqüências menores não
podem estar na resposta porque o interesse é somente nas seqüências máximas; assim,
também se elimina as seqüências freqüentes encontradas na fase de avanço que são não
máximas.
DynamicSome [Agrawal & Srikant, 1995]
O algoritmo DynamicSome, como o AprioriSome salta contagens de seqüências
candidatas de certos tamanhos na fase de avanço. As seqüências candidatas que são
contadas são determinadas pela variável Passo. Na fase de inicialização, todas as
seqüências candidatas de tamanho igual ou maior que Passo são contadas. Então na fase
de avanço, todas as seqüências cujos tamanhos são múltiplos de Passo são contadas.
Assim, com Passo igual a 3, contam-se seqüências de tamanhos 1, 2 e 3 na fase de
inicialização, e 6, 9, 12,..., na fase de avanço. Realmente se se deseja contar seqüências
de tamanhos 3, 6, 9, 12,... pode-se gerar seqüências de tamanho 6 pela junção de
153
seqüências de tamanho 3. Pode-se gerar seqüências de tamanho 9 pela junção das
seqüências de tamanho 6 com seqüências de tamanho 3 etc. Entretanto, para gerar as
seqüências de tamanho 3, precisa-se de seqüências de tamanhos 1 e 2, e por isto tem-se
a fase de inicialização. Como no AprioriSome, durante a fase de retrocesso, conta-se
seqüências dos tamanhos que foram saltadas durante a fase de avanço. Entretanto,
diferentemente do AprioriSome, essas seqüências candidatas não são geradas na fase de
avanço, sendo feitas em uma fase intermediária. Então a fase de retrocesso é idêntica à
do AprioriSome. Usa-se a função GeraCandidato na inicialização e nas fases
intermediárias, mas usa-se GeraOff na fase de avanço. A razão de se usar o
procedimento GeraOff é que a função GeraCandidato gera candidatos menores que ela
quando se gera Ck+1 de Lk. Entretanto isto pode não acontecer quando se tenta encontrar
Lk+Passo de Lk e LPasso como é o caso da fase de avanço. Além disto, se o tamanho de |Lk|
+ |LPasso| é menor que o tamanho de Ck+Passo gerado pelo GeraCandidato, pode ser mais
rápido encontrar todos os membros de Lk e LPasso contidos em c que encontrar todos os
membros de Ck+Passo contidos em c. A função GeraOff tem como argumento Lk, o
conjunto de k-seqüências freqüentes, Lj, o conjunto de j-seqüências freqüentes, e a
seqüência-cliente c, e retorna o conjunto de (k+j)-seqüências candidatas contidas em c.
A idéia é que se sk ∈ Lk e sj ∈ Lj estão ambos contidos em c, e não são sobrepostos em
c, então <sk. sj> é uma (k+j)-seqüência candidata.
GSP [Srikant & Agrawal, 1996]
O algoritmo GSP (Generalized Sequential Patterns) faz múltiplas inspeções no
banco de dados. Na primeira inspeção todos os itens simples (1-seqüência) são
contados. Dos itens freqüentes, um conjunto de 2-seqüências candidatas é formado e
uma outra inspeção é feita para contar seu suporte. Os 2-seqüência freqüentes são
usados para gerar os 3-seqüência candidatos, e esse processo é repetido até nenhuma
seqüência freqüente ser encontrada. Existem dois passos principais no algoritmo:
1. Geração de candidatos: Dado o conjunto de (k-1)-seqüência freqüentes, os
candidatos para o próximo passo são gerados pela junção deste conjunto com
ele mesmo. Uma fase de poda elimina qualquer seqüência em que pelo
menos uma de suas subseqüências não seja freqüente. Para uma rápida
contagem, as seqüências candidatas são armazenadas em uma hash-tree. Os
nodos folhas da hash-tree contêm as seqüências, enquanto os nodos internos
têm uma tabela hash. Cada célula não vazia de um tabela hash de
profundidade d aponta para um nodo da hash-tree de profundidade d+1. Os 154
candidatos são inseridos na hash-tree começando pela raiz e vão avançando
até alcançar um nodo folha, onde será inserido.
2. Contagem de suporte: Para encontrar todos os candidatos contidos em uma
seqüência S, conceitualmente todas as k-subseqüências de S são gerados. Para
cada subseqüência uma busca é feita na hash-tree. Se um candidato em um
nodo folha emparelha com a subseqüência, seu contador é incrementado.
Como o próprio nome sugere, o algoritmo GSP não apenas resolve o problema
de padrões seqüenciais, mas também o generaliza por considerar taxonomias nos itens;
por incluir restrições de tempo tais como limites mínimo e máximo entre os elementos
de seqüências sucessivas; e por incorporar janelas de tempo, que relaxam a definição de
uma transação.
Outros Algoritmos para Prospecção de Padrões Seqüenciais
Diversos outros algoritmos para Prospecção de Padrões Seqüenciais foram
encontrados, dentre eles: SPADE [Zaki, 1997], [Zaki, 2001], FreeSpan [Han et al.,
2000a], PrefixSpan [Pei et al., 2001], SSLP [Yen & Cho, 2001], SPAM [Ayres et al.,
2002], etc. Da mesma forma, foram pesquisados diversos algoritmos para a Prospecção
e Atualização de Padrões Seqüenciais, podendo-se citar: USSLP [Yen & Cho, 2001],
ISL [Parthasarathy et al., 1999], Árvore de Sufixo [Wang, 1997], ISE [Masseglia et al.,
2000], FASTUP [Lin & Lee, 1998], IUS [Zheng et al., 2002], DUS [Zheng et al., 2002],
etc. No entanto, tais algoritmos, como não foram aplicados no trabalho em questão, não
terão seu comportamento explicitado, visto o grande volume de informações que
necessitaria ser introduzido neste apêndice.
155
