Análise Tópica de
Links para busca
na Web
Lucas Augusto Scotta Merlo
[email protected]
Agenda
•
Introdução
•
•
Método Tradicional de Ranking
•
•
Web
PageRank
Melhoramento dos métodos de ranking
•
Topical PageRank
•
Implementação e Resultados
•
Comparação
•
Conclusão
Seminário de Recuperação da
Informação
2
Introdução
•
Usuário necessita informação.
•
•
Muitos dados na Web
•
•
Desafios novos para a recuperar a informação.
Web Mundial: + 10 bilhões de páginas.(2006)
•
•
Solução: Máquinas de busca. Ranking de páginas.
Brasil: + de 4 milhões de páginas registradas no
domínio .br (2004)
Padrão da Web auxilia: estrutura de links.
Seminário de Recuperação da
Informação
3
Métodos Tradicionais de Ranking
•
PageRank
•
Desenvolvido pelos fundadores do Google em 1998 para prover
um ranking nos resultados da busca.
•
Baseado na estrutura de links da Web. Toda página tem um
número de links de saída e links de entrada.
•
Algoritmo de análise de ligação que atribui uma pesagem
numérica a cada página da Web, com o propósito de "medir"
sua importância relativa dentro deste conjunto.
Seminário de Recuperação da
Informação
4
PageRank
PR ( i )  (1  d )  ( d * (

j: j  i
•
PR ( j )
O ( j)
)
)
Uma página X tem um alto ranking se:
- Tenha muitos links de entrada;
- Tenha links de entrada com ranking alto;
A
B
C
Seminário de Recuperação da
Informação
5
Melhoramento dos modelos de
ranking

Incorporar distribuição tópica na representação de cada
página da Web como também a contagem de
importância de cada página.

Vetor content Cu:[C(u1),C(u2),..., C(uT)]
 Distribuição de probabilidade que representa o
conteúdo de u, na qual cada componente representa
a contribuição relativa de cada tópico dentro do
conteúdo de u para o conteúdo de u como um todo.
Este vetor é estático e somente determinado pelo
conteúdo.
Seminário de Recuperação da
Informação
6
Melhoramento dos modelos de
ranking

Vetor de autoridade Au:[A(u1),A(u2),...,
A(uT)]:
atribui para cada página u um vetor
para medir sua importância, onde A(uk)
denota página u's importantes para
contagem do tópico k.
Seminário de Recuperação da
Informação
7
Topical PageRank

Assume além da analise de links de entrada e saída
proposto pelo PageRank a análise de transições para se
chegar a uma página desejada(probabilidades
condicionais).
 1ª)
follow-stay
 2ª) follow-jump
 3ª) jump-jump
Seminário de Recuperação da
Informação
8
Topical PageRank

Depois que a propagação converge, cada componente
A(ui) no vetor de autoridade Au:[A(u1),A(u2),..., A(uT)] é
a contagem de autoridade de página u em tópico i. A(u)
é o contagem global de autoridade. Pode-se dizer então
que a distribuição de autoridade de uma página não só
depende de seu conteúdo, mas também das heranças
de suas páginas de transições.
A ( u i )  (1  d )

v :v  u
 A ( v i )  (1   ) C ( v i ) A ( v )
O (v )
Seminário de Recuperação da
Informação

d
N
C (u i )
9
Implementação e Resultados




Utiliza-se grafos. (Nó = página e Aresta = Link)
C/C++.
Base arquivo “grafo.txt”.
Principais Funções “Insere”, “busca_link”, “PageRank” e
“TopicalPageRank”.

Insere: recebe como parâmetro um ponteiro do tipo da estrutura da
lista ligada e um inteiro. Nesta função se aloca a lista ligada na
memória. Os dados são inseridos pelo início e ela retorna a lista
atualizada.

Busca_link: é passada a lista já atualizada e um vetor vazio para se
armazenar os links (entrada ou saída) do nó X. Foi criado vetores
adicionais (links_entradas) e (links_saidas) para armazenarem a
lista de nós de entra e saída respectivamente para cada Nó,
alocando este vetor lista na memória.
Seminário de Recuperação da
Informação
10
Implementação e Resultados

Função PageRank, que é calculada
conforme:

PR(A) é o PageRank da página A,
PR(Ti) é o PageRank de páginas Ti que tem um link para a página
A,
C(Ti) é o número de links de saída em uma página Ti e
d é um fator damping (que afeta) 0,85



PR(A) = (1-d) + d (PR(T1)/C(T1) + ... +
PR(Tn)/C(Tn))
Seminário de Recuperação da
Informação
11
Implementação e Resultados

Função Topical PageRank, que é calculada conforme:

ui-> Nó
vi -> Nó
alpha=0.85;
d=0.15;
A(v) = 1 / N
A(vi) = A(v) / N





A Autoridade do Nó (ui) = (1 –d) * Somatório das Páginas V
que tem entrada para U ( (alpha * Autoridade A(vi) +
( 1 - alpha ) * o PR do Nó (vi) * Autoridade de ( v)) /
Número de Links de saída de v ) + d/N * o PR do Nó (ui)
Seminário de Recuperação da
Informação
12
Implementação e Resultados

Lista simplesmente ligada
insere(&links_saidas[num_vertice_origem]->prox,num_vertice_destino);
insere(&links_entradas[num_vertice_destino]->prox,num_vertice_origem);
Seminário de Recuperação da
Informação
13
Telas
3
0
2
1
Seminário de Recuperação da
Informação
4
14
Seminário de Recuperação da
Informação
15
Comparação


Artigo base:
Artigo desenvolvido:


Análise de Páginas.
 TREC.GOV2003.
 20 consultas diferentes.

Classificador ingênuo de
Bayes para gerar Cu:[ ]

Melhoria proposta funciona
muito bem. Melhor
performance que
PageRank.
Análise em grafo.

Nó = página e Aresta = Link
10 grafos para testes.
Melhor eficiência que PageRank
por fazer uma análise global dos
dados com o auxilio do vetor
“content = PR(c)” e da
Autoridade medida de cada
página, e analisando as
transições para se chegar a uma
página desejada.



Diferencia melhor os resultado
Seminário de Recuperação da
Informação
16
Conclusão

A melhoria de PageRank (Topical PageRank)
demonstrou que mesmo com o avanço que o Google
trouxe em 1998 com seu método de ranking para
páginas da Web, existem outras formas eficazes para
chegar ao melhor resultado como combinar a
distribuição de tópicos e estrutura de links.

Incorporarou-se este modelo tópico dentro de PageRank
sem afetar a contagem da autoridade global, e ainda
prover uma distribuição da autoridade entre tópicos.
Seminário de Recuperação da
Informação
17
Referências







Brin, S., Page, L. (1998) “The anatomy of a large-scale hypertextual Web search
engine”, Em: Proc. of the 7th Int’l World Wide Web Conf., pages 107–117,
Brisbane,Australia.
Zaiane, Osmar R.. (2000) “WEB Mining: Concepts, Practices and Research”. Em:
Simpósio Brasileiro de Banco de Dados, Tutorial, XV SBBD, 2000, João
Pessoa.Anais João Pessoa: SBBD, 2000. p. 410-474.
Nie, L., Davison B., Qi, X.,( 2006) Topical Link Analysis for Web Search. Em
Proceedings of the 29th Annual International ACM SIGIR Conference on Research &
Development on Information Retrieval, Seattle, WA. p. 91-98.
“Mean Average Precision” – Disponível em
<http://www.itl.nist.gov/iad/894.02/works/presentations/spie99/tsld016.htm>.Acessad
o em 25 de julho de 2007.
Jones, K S., Wesley, S., Robertson, S.E. (1998) “A probabilistic model of information
retrieval : development and comparative experiments” Em: Information Processing
and Management.
S. Buttcher, C.L.A. Clarke. (2005)“Efficiency vs. Effectiveness in Terabyte-Scale
Information Retrieval”. Em: The Fourteenth Text REtrieval Conference (TREC 2005)
Proceedings. University of Waterloo.
“Rainbow: text classification tool.” – Disponível em
<http://www.cs.umass.edu/~mccallum/bow/rainbow/>.Acessado em 25 de julho de
2007.
Seminário de Recuperação da
Informação
18
Obrigado!!!
Seminário de Recuperação da
Informação
19