Sistema de Navegação Cooperativa para Websites:
Abordagem e Implementação
Wu Man Qi, Li Weigang, Paulo G. Vieira
Departamento de Ciência da Computação
Universidade de Brası́lia - UnB
Caixa Postal 4.466 - 70.919-970 - Brası́lia - DF
Resumo AntWeb is an adaptive navigation system for Websites which approach is inspired
by ant colonies foraging behavior. The system considers the Web users as artificial ants.
This paper presents an extension to AntWeb by considering the human’s complex behavior
during the searching process, using Web usage mining techniques to capture Website visitors
navigation patterns, making it more adequate and applicable to Web´s reality. Our proposal
is based on preprocessing Web log files, discovering clusters of users that exhibit similar
information needs and providing adaptive pages dynamically with marked links that allow
visitors to achieve common interests. In addition, information of ongoing implementation
based on free software of this proposed model is described.
1
Introdução
O AntWeb é um sistema de navegação adaptativo que funciona como uma metáfora ao comportamento das formigas reais a procura de alimento. Assim como as formigas, os usuários navegam pela
Web em busca de informação de seu interesse. O seu modelo básico está detalhado em [10].
No AntWeb, diferentemente de outras aplicações tradicionais [3], as formigas artificiais não são
componentes de software e sim os próprios usuários da Internet. Nessa abordagem, foi sugerida o
uso do algoritmo descrito em [9] para identificação de páginas alvo do usuário. O AntWeb por sua
vez iria levar os usuários com objetivo comum a essas páginas alvo pelo menor caminho existente no
Website. Sendo assim, o comportamento de navegação dos usuários é assemelhado ao das formigas,
sem levar em consideração a complexidade envolvida nesse processo como o interesse atual dos
usuários.
A fim de tornar seu modelo mais adequado e aplicável à realidade da Web, este artigo apresenta uma pesquisa relacionada aos temas como CSCW (Computer Supported Cooperative Work)
e busca e mineração de dados na Web, através da extensão do modelo do AntWeb [10] para grupos
de indivı́duos e da implementação de um protótipo baseado em dados reais do Portal Interlegis
(www.interlegis.gov.br). Este Portal faz parte do primeiro grande projeto [7] de modernização e
integração do Legislativo brasileiro e exerce um papel fundamental na integração entre as Casas Legislativas de diferentes esferas: federal, estadual e municipal. O AntWeb irá permitir que os membros
do Portal com interesses similares cooperem entre si, trocando experiências de uma forma implı́cita,
em prol de um objetivo comum que é alcançar suas páginas alvo de uma forma mais rápida.
As seções seguintes estão organizadas em três partes: logo após esta introdução, apresentaremos
o modelo estendido do AntWeb. Na terceira seção, falaremos brevemente da implementação do
protótipo baseado no Portal Interlegis. E por último, a quarta seção apresenta as considerações
finais.
2
Modelo Estendido do AntWeb
Este modelo do AntWeb surgiu pela junção dos conceitos de navegação social, inteligência coletiva
e filtragem colaborativa. O termo navegação social surgiu da percepção de que fatores sociais influenciam no comportamento navegacional dos indivı́duos. Segundo [4], navegação social é definida
como o movimento em direção a um grupo de pessoas ou a um lugar em particular porque alguém
esteve lá antes ou viu alguma coisa. Inteligência coletiva é definida como a habilidade que um grupo
de indivı́duos (pessoas, insetos, robôs ou agentes de software) possuem em resolver mais problemas
ou encontrar soluções melhores do que seus membros individuais [6]. O conceito de filtragem colaborativa ou filtragem social de informação baseia-se principalmente na automação do processo de
recomendação de produtos ou serviços de uma pessoa para outra[8].
O enfoque do AntWeb é, portanto, auxiliar os usuários na navegação coletando preferências
que estão implı́citas na navegação dos usuários em um Website, não requerendo nenhum esforço
adicional por parte dos usuários ao usar o sistema.
A Figura 1 mostra a estrutura estendida do AntWeb. Como um pré-requisito para o funcionamento deste sistema, é preciso que o módulo de Web mining offline seja executado antes para
identificarmos as possı́veis categorias de usuários existentes num Website com a utilização da técnica
de clustering. Este processo consiste no pré-processamento dos dados registrados nos logs de acesso
do servidor Web e na posterior extração de categorias, onde cada categoria resultante é formada
por sessões representadas por um conjunto de páginas visitadas ou requisitadas pelos usuários pertencentes a esta categoria. Assim, estas páginas são consideradas de interesse para estes usuários,
já que um Website é formado por uma quantidade de páginas, onde cada página pode ser vista
como um ”item de interesse”. Este método é uma alternativa ao uso do método proposto em [9],
uma vez que o nosso foco em questão é tratar a navegação de grupos de indivı́duos e não mais de
um único indivı́duo.
Figura 1. Estrutura estendida do AntWeb
Completado este processo, o sistema funciona da seguinte forma: quando o usuário ativo no
site requisitar uma página ao servidor Web, esta informação é mantida na sessão do usuário. O
sistema por sua vez executa o módulo de Web mining online para classificar dinamicamente este
usuário em uma categoria já identificada baseada na sequência de URLs visitados por ele na sessão
ainda em andamento; caso este usuário faça parte de alguma categoria, o sistema fará o uso das
informações registradas no banco de dados que são as quantidades de feromônio1 contidas nos links
da página para a categoria em questão. A quantidade de feromônio associada a um link (i, j)
representa o quanto é desejável para os usuários desta categoria escolher a página j, estando na
i, em um determinado momento. Em seguida o sistema fará a adaptação da página de forma que
os links contendo uma quantidade razoável de feromônio e que levem às páginas de interesse ainda
não visitadas por este usuário sejam destacados. Finalmente, o sistema retorna a página adaptada
para o usuário e o ciclo é iniciado novamente, porém, uma vez que o usuário já tenha sua categoria
classificada, o módulo de Web mining online não é mais executado e qualquer acesso feito pelo
usuário é gravado no log armazenado no banco de dados que servirá para o processo de atualização
do feromônio.
2.1
Pré-processamento dos Dados
Nesta fase, realiza-se uma limpeza no arquivo log do servidor Web, isto significa eliminar todos os
acessos a arquivos de imagens, de áudio e de vı́deo. Além disso, identificam-se as sessões distintas
contidas nele.
O resultado deste processo é a conversão de cada sessão em um vetor que a represente. Por
exemplo, se um usuário durante uma sessão acessou páginas A, B e C, e sendo o número de acessos
a estas páginas igual a 1, 2 e 1 respectivamente, seu vetor correspondente é <(A,1),(B,2),(C,1)>.
2.2
O Algoritmo para Extração de Categorias
O objetivo deste algoritmo é descobrir grupos de sessões que exibam interesses similares. Similaridade pode ser definida de diversas maneiras. Por exemplo, dois vetores são similares se a distância
euclidiana entre eles é suficientemente curta ou o ângulo formado entre eles é suficientemente pequeno. Neste trabalho, a similaridade é medida pela distância euclidiana.
O algoritmo leader [5] foi escolhido para ser utilizado nesta fase devido a sua eficiência no
processamento de grande quantidade de entradas no arquivo log. O algoritmo é dado a seguir:
Entrada: um conjunto de vetores V, NumMinPag, DistanciaMax, TamMinCategoria
Saı́da: um conjunto de categorias C
Inicialize C = vazio
Para cada v em V faça
Se a cardinalidade de v > NumMinPag ent~
ao
Encontre categoria c em C tal que a dist^
ancia d
entre a média de c e v seja o mı́nimo
d = o mı́nimo encontrado entre todas as categorias existentes em C
Se a dist^
ancia d < DistanciaMax ent~
ao
Adicione v à categoria c
Sen~
ao adicione {v} ao conjunto C
Para cada c em C faça
Se o tamanho de c < TamMinCategoria ent~
ao
Remova c de C
Retorne C
1
O termo feromônio é utilizado em analogia com a substância secretada por insetos, que serve de meio de
comunicação entre indivı́duos da mesma espécie, em especial as formigas.
Este algoritmo inicia-se sem nenhuma categoria e os vetores de entrada são examinados um
a um. Cada vetor é adicionado à categoria mais próxima, se a distância euclidiana for menor do
que a DistanciaMax. Se não existir tal categoria, o vetor forma uma nova categoria. O parâmetro
NumMinPag significa o número mı́nimo de páginas acessadas em uma sessão e o TamMinCategoria
significa o tamanho mı́nimo de uma categoria. Estes dois parâmentros servem para remover respectivamente sessões e categorias que são insignificantes nesse processo, e podendo, com isso, melhorar
também a sua performance.
Os algorimos para classificação online dos usuários e adaptação dinâmica das páginas ainda se
encontram em fase de estudo e análise.
3
Implementação do AntWeb
Um protótipo do modelo estendido do AntWeb está sendo implementado baseado em um escopo
reduzido do Portal Interlegis. Esta implementação utiliza a abordagem orientada a objetos e a
plataforma de desenvolvimento empregada é toda ela baseada em software livre, tendo o Zope [1]
como o servidor de aplicações Web, o PostgreSQL [11] como o banco de dados relacional e o Python
[2] como a linguagem de programação.
4
Considerações Finais
O AntWeb combina a teoria das formigas com a tecnologia da Web adaptativa como uma nova
abordagem no campo de pesquisa de Web Inteligente. Este artigo apresentou uma pesquisa ainda em
andamento, porém, estamos convencidos de que este trabalho merece o conhecimento da comunidade
cientı́fica, especialmente a de Web adaptativa e sistemas formiga para que sejam dadas sugestões
para seu aprimoramento.
Referências
1. Bernstein, M. R., Robertson, S., Team the C. D.: Zope bible. Hungry Minds, Inc., New York, NY. (2002)
2. Brueck, D., Tanner, S.: Python 2.1 bible. Hungry Minds, Inc., New York, NY. (2001)
3. Dorigo, M., Caro, G. D.: The ant colony optimization meta-heuristic. New Ideas in Optimization, McGraw Hill. (1999) 11–32
4. Dourish, P., Chalmers, M.: Running out of space: models of information navigation. Proceedings of BCS
HCI 94, ACM Press, Glasgow. (1994)
5. Hartigan, J.: Clustering algorithms. John Wiley. (1975)
6. Heylighen, F.: Collective intelligence and its implementation on the web: algorithms to develop a collective mental map. Computational and Mathematical Theory of Organizations. 5(3) (1999) 253–280
7. Nascimento, A. R. C., Arroio, R., Damasceno, A. P., Conde, S.: Documento de Projeto InterLegis.
Prodasen, Brası́lia. (1998)
8. Shardanand, U., Maes.: Social information filtering: algorithms for automating ’word of mouth’. Proceedings of CHI’95 - Human Factors in Computing Systems. (1995) 210–217
9. Srikant, R., Yang, Y.: Mining web logs to improve website organization. Proceedings of the Tenth International World Wide Web Conference, Hong Kong. (2001)
10. Teles, W. M., Weigang, L., Ralha, C. G.: AntWeb - the adaptive web server based on the ants’ behavior.
WI (International Conference on Web Intelligence), IEEE/WIC, Halifax, Canada. (2003)
11. Worsley, J. C., Drake, J. D.: Practical PostgreSQL. O’Reilly & Associates, Inc., Sebastopol, CA. (2002)