Uma heurística para guiar os usuários da Internet baseada no comportamento da formiga

Uma heurística para guiar os usuários da Internet baseada no comportamento da formiga Wesley Martins Teles, Li Weigang, Célia Ghedini Ralha 1

Departamento de Ciência da Computação – Universidade de Brasília (UnB) Caixa Postal 4.466 – 70.919-970 – Brasília – DF – Brasil {wesley,weigang,ghedini}@cic.unb.br

Abstract. This paper presents a new approach to guide web users, inspired by the ant colonies foraging behavior, to adaptively mark the most significant links, by means of the shortest route to arrive to target pages. Thus, we consider web users as artificial ants, and use the ant theory as a metaphor to guide user’s activity in the Web site. In this paper, we describe the ant’s theory in which AntWeb is based. We also present the AntWeb system and a case study with some experiments. Resumo. Este artigo apresenta uma nova abordagem para guiar usuários web inspirada no comportamento de colônias de formigas quando procuram alimento, onde destacamos de forma adaptativa os links mais significativos, levando os usuários a rotas mais curtas para chegar às páginas desejadas. Em nossa abordagem, consideramos os usuários da Web como formigas artificiais, usando a teoria das formigas como uma metáfora para guiar a atividade dos usuários nos sites da web. Neste artigo, nós descrevemos a heurística das formigas em que o AntWeb é baseado. Nós apresentamos também o sistema AntWeb e um estudo de caso com algumas simulações realizadas.

1. Introdução A Web é um sistema de hipermídia e como tal, os usuários sabem qual o próximo link a clicar através da indicação que o texto do link lhe dá. Mas quase sempre o objetivo do usuário não está no nodo vizinho ao nodo corrente e um novo recurso se torna necessário para auxiliar o usuário em um contexto global. Para resolver este problema foram criados os tradicionais sistemas de busca como o altavista, o yahoo, google, etc. Mas esses sistemas transgridem os objetivos do hipertexto, fazendo com que os usuários encontrem seus objetivos como se estivessem fazendo buscas em um banco de dados. Sistemas de navegação adaptativa [Brusilovsky 1996], [Palazzo 1999] como o webwatcher [Joachins, Freitag e Mitchell 1996], e outros mecanismos [Liu, Yao e Zhong 2002], [Fensel 2002], [Han e Chang 2002] resolvem parte deste problema, uma vez que fornecem indicações globais aos usuários mantendo as características do hipertexto. Mas o problema não é apenas chegar à página alvo. Um sistema de hipermídia é um grafo onde existem vários caminhos possíveis para se chegar a um nodo partindo de outro. Alguns caminhos são menores que outros. A indicação preferencial desses caminhos faz com que os usuários cheguem ao seu objetivo de forma mais rápida.

Usuários navegando na imensa rede de hipermídia da Web são como as formigas procurando seu alimento [Weigang, Dib, Teles e etc. 2002]. Elas perambulam por um imenso mundo a procura de alimento, tal qual os usuários navegam na Internet. Ambos possuem uma visão de curto alcance do seu ambiente. Os usuários da internet podem apenas ter alguma idéia do que consiste o conteúdo dos nodos vizinhos através do texto dos links. Similarmente, as formigas podem enxergar somente distâncias muito curtas [Dorigo, Maniezzo e Colorni 1996], [Dorigo, Caro, Sampels 2002], tornando-as praticamente cegas. Mas, diferente dos usuários da internet, as formigas possuem um sistema de cooperação simples e eficiente que permite que elas encontrem o caminho mais curto para fonte de alimento [Beckers, Deneubourg e Goss 1992]. À medida que a formiga anda, ela deixa rastros de feromônio no chão para que outras formigas sigam o mesmo caminho. Caminhos longos recebem menos atualizações de feromônio do que caminhos curtos. Dessa forma, os caminhos longos se extinguem devido à evaporação de feromônio, enquanto os caminhos curtos ficam cada vez mais aromáticos graças a crescente atualização. A engenhosidade desse sistema foi usada para a solução de diversos problemas na Ciência da Computação, como o problema do caixeiro viajante e o roteamento de pacotes [Dorigo, Caro e Gambardella 1999]. O desenvolvimento de AntWeb foi proposto em duas linhas. A primeira se concentrou na avaliação de estruturas de WebSites [Weigang, Dib, Teles e etc. 2002]. A segunda, que está descrita neste trabalho, se concentrou no uso do comportamento da formiga para promover a adaptação da web no sentido de guiar o usuário. Ela se baseou na necessidade de fazer com que o usuário da internet encontre caminhos curtos durante sua navegação. O AntWeb adaptativo consiste na idealização de uma internet coletiva, em que os usuários deixam rastros de feromônio pelo caminho, como as formigas fazem. Desta forma, foi implementado um sistema que simula a web com tais mecanismos. Esse sistema é um “visualizador“ de páginas da Internet, em que o usuário enxerga a web através da perspectiva do AntWeb. Este trabalho está dividido em cinco sessões: logo após esta introdução apresentamos a modelagem da heurística usada para guiar o usuário da Web e o algoritmo desenvolvido. Na terceira sessão, falaremos da implementação do modelo que foi dividido em dois módulos. Os estudos de casos estão descritos na sessão quatro. No final, a sessão cinco apresenta a conclusão e as perspectivas de trabalhos futuros.

2. Modelo do AntWeb O AntWeb é uma heurística adaptada da meta heurística da formiga desenvolvida por Marco Dorigo e colegas [Dorigo, Maniezzo e Colorni 1996], que permite conduzir o usuário à(s) página(s) que desejamos por um caminho menor através do hipertexto. Isto é uma alternativa a fornecer o link direto para a(s) página(s). Quando se faz isso, o usuário perde a oportunidade de passar por muitas páginas, que talvez, lhe interessasse também. É como se você fosse para o supermercado comprar uma caneta. Para chegar até essa caneta no supermercado, você tem que ir para a sessão de materiais escolares. Neste caminho, você vê lápis a venda e se lembra que também precisa de lápis. Se você tivesse ligado para o supermercado e comprado a caneta com entrega a domicilio, você

provavelmente não iria se lembrar que estava precisando de lápis. Normalmente, as páginas que tem conteúdo relacionado estão próximas uma das outras no hipertexto e algumas dessas páginas podem ser de interesse do usuário. 2.1. Modelo básico Em nosso modelo, p ijd expressa o quanto a escolha da página j é boa quando o usuário está na página i procurando a página d. A Equação 1 mostra a restrição que deve ser aplicada a p ij d . ∑ pij d = 1, j ∈ Ni

(1)

Onde Ni é o conjunto dos vizinhos da página i. Cada página do site terá uma tabela de roteamento que é calculada segundo a Equação 2. aij d (p) = [τj d (p)]α [η j(p)]β / ∑{[τl d (p)]α [ηl (p)]β} , j ∈ Ni , l ∈ Ni

(2)

Onde a ijd (p) corresponde aos valores da tabela de roteamento na iteração p, τj d (p) é a quantidade de feromônio na página j na iteração p, α e β são parâmetros que permitem controlar os pesos entre a trilha de feromônio e η j = 1/wt j é uma heurística relacionada ao custo de usar a página j: wt j = ltj + vtj

(3)

Onde wt j é o tempo estimado na página j. Ele inclui ltj o tempo estimado para obter a página j através do browser, e v tj o tempo que o usuário levará para visitar até página. A equação 4 mostra como é feito o cálculo da probabilidade na qual uma formiga escolhe ir da página i para a página j ∈ Ni . p ij d = aijd (p) / ∑ aild (p), l ∈ Ni

(4)

A atualização do feromônio ocorre depois que a formiga termina sua viajem até a página destino. Nesta atualização são feitos a evaporação e o acréscimo do feromônio nos links. A equação 5 mostra como é calculado o acréscimo de feromônio. 1/[(nli d,k (p) + 1) σ ]

se i ∈ Td,k (p)

∆τi d,k (p) = {

(5) 0

se i ∉ Td,k (p)

Onde Td,k(p) é o conjunto de páginas visitadas pela formiga k na iteração p para chegar a página d, nli d,k(p) é a distância da página i até a página d em Td,k(p) e σ é um parâmetro que determina o quanto a distância entre i e d vai influenciar no decremento do feromônio, normalmente igual a 1. Por exemplo se TP3,k(p) ={P1,P2,P3} então ∆τP1 P3,k(p) = 0.33σ , ∆τP2 P3,k(p) = 0.5σ e ∆τP3 P3,k(p) = σ . A adição de feromônio em cada página é feita de acordo com a equação 6: τi d(p) ← (1- ρ) τi d(p) + ρ∆τi d,k (p) para k = 1, …, m, i ∈ T d,k (p)

(6)

Onde ρ ∈ [0,1] é o coeficiente de evaporação. Observe que essa fórmula é equivalente a uma média continuada fazendo com que o feromônio dos links tendam a uma estabilização. 2.2. Modelo para procura de vários destinos Quando o usuário está procurando sua página, usando o AntWeb, é como se ele estivesse seguindo o cheiro de sua página e seguisse os links que exalem o cheiro mais forte. No modelo anterior, quando se está guiando o usuário para apenas um destino, é como se somente uma página pudesse exalar seu cheiro, ficando todas as outras inodoras. Assim, ficando somente a página que o usuário deseja encontrar exalando cheiro, basta o usuário seguir o cheiro que ele a encontrará. Mas e no caso de existirem duas ou mais páginas que satisfaçam o desejo do usuário de forma similar? Nesse caso, podemos permitir que essas duas ou mais páginas exalem seu cheiro simultaneamente. Dessa forma, como todas as páginas possuem o mesmo cheiro, ganhará a preferência do usuário a página que estiver a uma distância mais curta, lembrando que quando mais um objeto está próximo de nós, mas podemos sentir seu cheiro. O modelo para levar o usuário a mais de um destino é similar ao modelo anterior, mudando apenas na forma como é calculada a probabilidade que expressa o quanto é bom o usuário seguir determinado caminho. p ij D,G = ∑[aij d(p) gd] / ∑[ a ild (p) gd ], l ∈ Ni , d ∈ D, gd ∈ G

(7)

Onde D é o conjunto de páginas destino que desejo levar o usuário, g d é um coeficiente que indica quanto a página d é boa para o usuário e G é o conjunto de coeficientes g atribuídos ao conjunto D. Quanto maior o valor de g d maior o cheiro que esta página exalará em relação a outras páginas 2.3. Identificando a página destino do usuário Para identificação da página destino correspondente a cada navegação ocorrida usando o AntWeb, foi usado os mesmos métodos descritos em [Srikant e Yang 2001]. Existem dois métodos que são utilizados em conjunto: A página é uma página de conteúdo – Em alguns sites existe uma clara separação entre página índice e página conteúdo. Neste caso a página é identificada como uma página destino através da verificação do tipo de página. Utilização de um "threshold" – Neste método é feito a verificação do tempo em que o usuário permaneceu na página. Se o tempo for acima de um "threshold", a página é considera a página destino do usuário. 2.4. O algoritmo para atualização do feromônio A atualização do feromônio será feita usando-se o log de acesso às páginas. No log dispomos de informações como o endereço da página acessada, o IP do usuário e a hora que a página foi acessada. O algoritmo é o seguinte: 1. Particione o log por visitante.

2. Ordene cada partição pela hora em que cada página foi acessada. 3. Para cada visitante, particione de forma que cada partição termine com uma página destino do usuário. 4. Para cada partição criada do passo 3 atualize o feromônio das páginas usando as equações 5 e 6.

3. Implementação na Internet O AntWeb adaptativo foi implementado em linguagem PHP usando banco de dados MySQL. A Figura 1 mostra a página do AntWeb que os usuário acessam para navegar no site do Departamento de Ciência da Computação da UnB. Ao clicar em “clique aqui para começar” o usuário visualizará a mesma página que ele visualizaria se tivesse digitado a URL no campo “adresss” do seu browser, mas com a diferença que o(s) link(s), que presumidamente possui maior probabilidade de levar ao objetivo em menos clicks, são destacados com a figura de uma formiga.

Figura 1. Home page inicial do AntWeb

Quando acessamos uma página e um link aparece destacado, significa que interceptamos uma trilha de feromônio. Ao clicarmos no link destacado, estaremos seguirmos

a trilha de feromônio deixado por outros usuários. Para ele deixar de usar o AntWeb, basta digitar outro endereço na barra de endereço de seu browser que ele sairá do sistema. Para entendermos melhor como funciona este esquema, vamos primeiro imaginar um cenário em que nosso usuário acessaria o site do CIC sem o AntWeb. Primeiro, ele digitaria o endereço do site em seu browser e em seguida seria mandado uma requisição pela Internet ao servidor web do CIC. Em seguida, seu browser receberia o código HTM L da página, e apresentaria a página ao usuário. No caso do AntWeb, primeiro nosso usuário acessa a página do AntWeb e clica no link correspondente. Neste momento, é enviada uma requisição ao servidor do AntWeb (1) conforme mostra a Figura 2. O AntWeb então busca a página requisitada (2, 3) e verifica a quantidade de feromônio em cada link da página e outros dados no Banco de Dados (4) para ele saber qual link será destacado. O AntWeb destaca o(s) link(s) e depois altera a URL de todos os links na página de forma que passem a apontar para o servidor do AntWeb. Em seguida, o AntWeb grava um log no Banco de Dados que servirá para o processo de atualização do feromônio (5). Finalmente o AntWeb retorna a página modificada para o usuário (6). Quando o usuário clicar em algum link da página que ele recebeu, ele mandará uma nova requisição ao AntWeb, recomeçando todo o ciclo novamente. 3.1. Como a implementação se relaciona com o modelo No caso específico desta implementação do AntWeb, os usuários são conduzidos usando a técnica de indicação direta [Brusilovsky 1996], [Palazzo 1999]. Todas as páginas conteúdo do Site do CIC foram incluídas no conjunto D (conjunto de páginas destino) e a heurística que foi usada em gd foi o acesso médio de cada página dos últimos três dias. Assim o sistema levará o usuário para as páginas com melhor proporção entre distância e popularidade. O algoritmo se aplica a cada página da Internet que for requisitada ao AntWeb: 1. Calcule a probabilidade de escolha de cada link conforme equação 7 e 2. Destaque o(s) link(s) que tiverem a maior probabilidade calculada. 3.2. Os dois módulos da implementação O AntWeb foi desenvolvido em dois módulos: Atualização do feromônio e adaptação de páginas. O módulo de atualização do feromônio funciona separadamente do módulo de adaptação de página para que este último dê uma resposta mais rápida ao usuário. O módulo de atualização do feromônio é executado em segundo plano no servidor, sendo responsável por manter as taxas de feromônio das páginas atualizado. O sistema foi desenvolvido utilizando orientação a objetos e como principais classes desse módulo temos: PheromoneUpdaterTrigger: É responsável por disparar todo o processo de atualização. PheromoneUpdater: É responsável pela atualização do feromônio em si. PheromoneIncreser: Nesta classe está a função de acréscimo de feromônio. Configuration: É responsável por controlar os parâmetros usados na atualização de feromônio, como o coeficiente de evaporação e o tempo de iteração.

UpdateRecorder: É a classe responsável por gravar, na tabela Updates, os dados correspondentes de cada atualização feita.

1-requisição da página ao AntWeb

Usuário

6-página modificada

2-requisição da página

Servidor web AntWeb

5-log

3-página

Servidor web CIC UnB

4-feromonio dos links

Servidor Banco de Dados

Figura 2. Como funciona o AntWeb

O módulo de adaptação de página é executado a cada vez que o usuário faz uma solicitação ao AntWeb. Ele é responsável por apresentar a página com os links destacados quando necessário. A descrição das principais classes é apresentada a seguir: Url: Classe responsável por tratar a URL da página que vai ser adaptada. PageLoader: Classe responsável por obter da internet o código HTML da página que vai ser adaptada. InternalLinksProcessor: Classe responsável por fazer com que os caminhos relativos dos links da página se tornem absolutos. LinksSelector: Responsável por selecionar os links que serão destacados baseando na taxa de feromônio de cada um deles e nos parâmetros obtidos de Configuration. LinksHighlighter: Responsável por destacar os links selecionados em LinksSelector na página que esta sendo adaptada. LinksGuider: Altera todas as URLs dos links da página de forma que eles apontem para o AntWeb e contenham um parâmetro informando qual página o link apontava antes. Sender: Classe responsável por enviar via internet o código HTML da página adaptada para o browser do usuário que a solicitou. Log: Classe responsável por fazer o registro de log na tabela logs correspondente ao processo de adaptação.

1A 0,67

0,33

2A

2B 0,5

0,5

3A 0,5

1

3B 0,5

2

3

Figura 3. Estrutura de um site fictício

4. Estudo de caso Neste experimento, foi feita uma simulação com 30 iterações. Suponha que o usuário começa a navegar no site fictício da Figura 3 e que a cada iteração, o usuário escolhe caminhos aleatórios de forma proporcional aos números mostrados nas arestas. No site da Figura 3, as páginas 1, 2 e 3 são páginas conteúdo e as paginas restantes são paginas índices. Foram considerados os seguintes valores para a atualização do feromônio: Coeficiente de evaporação(ρ) = 0,3 ; Coeficiente que diz o quanto a distância de uma página ao destino deve afetar o decremento do feromônio (σ) = 1 e as constantes de controle α = 1 e β = 0. Os feromônios de todas as páginas começaram com o valor 0 na iteração 0 e ficaram com τ1 (30)= 0,9718 , τ2 2 (30)= 0,9176, τ3 3(30)= 0,9718, τ2A1 (30)= 0,3239, τ2A 2(30)= 0,3059, τ2B3 (30)=0,4261, τ3B3 (30)= 0,1794 na iteração 30. 1

4.1. Situação 1 Nesta situação, as páginas destinos que desejamos levar o usuário são D={1,3} com g1 =1 e g3 =1. Como neste caso as páginas destino estão "exalando" a mesma quantidade de cheiro o AntWeb deverá indicar preferencialmente a página que esta mais próxima. Quando o usuário começa a navegar na página 1A as probabilidades de serão p1A,2A{1,3},{1,1} = 0,4319 e p 1A,2B{1,3},{1,1} = 0,5681. Desta forma, o sistema indica a página 2B como melhor caminho para encontrar rápido alguma página que satisfaça o desejo do usuário. Em 2B as probabilidades serão p2B,3{1,3},{1,1} = 0,8442 e p2B,3B{1,3},{1,1} = 0,1558 o que leva o usuário para a página 3, que é uma das páginas destino. Ao examinarmos a Figura 3 veremos que foi indicado o melhor caminho possível para se chegar rápido a alguma página destino. 4.2. Situação 2 Agora teremos uma situação inversa a situação anterior. Temos duas páginas destinos com a mesma distância da home page e com valores diferentes para g. Nesse caso, D={1,2} e g1 =1 e g2 =2. Quando o usuário está na 1A, as probabilidades serão p1A,2A{1,2},{1,2} = 1 e p 1A,2B{1,2},{1,2} = 0. Assim, o sistema indica a página 2A como melhor caminho. Estando na

página 2A, as probabilidades serão p2A,1{1,2},{1,2} = 0,3462 e p2A,2{1,2},{1,2} = 0,6538, o que reflete os valores de g nas definições das probabilidades. Assim, o sistema da preferência pela indicação da página 2 por ser a página com maior g.

5. Conclusão 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 trabalho se relaciona a diferentes tópicos de pesquisa além de web inteligente, como agentes inteligentes de navegação, iteração homem-web inteligente através de interfaces adaptativas para web e web mining. Comparado com outras abordagens existentes, consideramos que o AntWeb completa a função de outras heurísticas, estabelecendo rotas mais curtas para páginas alvo. O AntWeb apresenta uma abordagem flexível e extensível que pode se adaptar com outras abordagens de forma simples tornando-a uma ferramenta poderosa. Durante nossa pesquisa nós observamos alguns pontos que podem ser considerados para trabalhos futuros: - O Banco de dados do AntWeb dispõe de uma rica fonte de informações dos dados de acesso dos usuários, as quais podem servir para a analise de padrões de comportamento e estudo do efeito do AntWeb na navegação. - A geração de estruturas dinâmicas em sites usando o feromônio. O AntWeb ainda está em avaliação e desenvolvimento. Será necessário mais trabalho de implementação para aprimorar o sistema, mas no momento estamos convencidos de que esta pesquisa merece o conhecimento da comunidade científica, especialmente a de web adaptativa e sistemas formiga para que sejam dadas sugestões para o aprimoramento do modelo e futuros trabalhos.

Agradecimento Este trabalho é patrocinado parcialmente pelo CNPq do processo de 303378/20026 e pela CAPES no programa de pós-graduação do Departamento de Ciência da Computação da Universidade de Brasília.

Referências D. Fensel, “Ontology-Based Knowledge Management”, IEEE Web Intelligence, vol. 35, no. 11, 2002, pp. 56-59. J. Han and K. Chang, “Data Mining for Web Intelligence”, IEEE Web Intelligence, vol. 35, no. 11, 2002, pp. 64-70. J. Liu, Y. Yao and N. Zhong, “In Search of the Wisdom Web”, IEEE Web Intelligence, vol. 35, no. 11, 2002, pp. 27-31. L. A. M. Palazzo, “Sistemas de Hipermídia Adaptativa”, Universidade Católica de Pelotas, Escola de Informática, 1999.

L. Weigang, M. V. P. Dib, W. M. Teles, V. M. de Andrade, A. C. M. Alves de Melo, J. T. Cariolano, "Using ants’ behavior based simulation model AntWeb to improve website organization", in Proc. SPIE's Aerospace/Defense Sensing and Controls Symposium: Data Mining, Vol. 4730, pp. 229-240, Orlando, USA, April 2002. M. Dorigo, G. D. Caro, M. Sampels (Eds.), "Ant Algorithms", Third International Workshop, ANTS 2002, Brussels, Belgium, September 12-14, 2002, Proceedings. Lecture Notes in Computer Science 2463 Springer 2002. M. Dorigo, G. Di Caro and L. M. Gambardella, “Ant Algorithms for Discrete Optimization. Artificial Life”, 5(2), 137-172, 1999. M. Dorigo, V. Maniezzo and A. Colorni, “The Ant System: Optimization by a Colony of Cooperating Agents”, IEEE Transactions on Systems, Man, and Cybernetics-Part B, 26(1), 29-41, 1996. P. Brusilovsky, "Methods and Techniques of adaptive Hyermedia". User Modeling and User Adapted Interaction. V.6, n.2-3, pp.87-129. Special issue on adaptive hipertext and hypermedia, 1996. R. Beckers, J. L. Deneubourg and S. Goss, “Trails and U-turns in the selection of the shortest path by the ant Lasius niger”, Journal of theoretical biology, 159, 397-415, 1992. R. Srikant and Y. Yang, “Mining Web Logs to Improve Website Organization”, In Proc. of the Tenth International World Wide Web Conference, Hong Kong, May 2001. T. Joachims, D. Freitag, T. Mitchell, "WebWatcher: A Tour Guide for the World Wide Web" , Proceedings of IJCAI97, August 1997 (longer version internal CMU technical report September 1996).