+
iGather: Refinamento
de Buscas
Diogo Ribeiro
Glauber Ramos
+
Agenda

O problema



Qual o problema?
Relevância do problema
Solução



Modelos
 O que é uma tag?
 O que é um cluster?
Método
 MCL
 Parâmetros
 Extração de resultados
 Nodo mais representativo
Validação

Trabalhos relacionados

Trabalhos futuros

Considerações Finais
+
Qual o problema?

Sistemas de busca baseados em índices quantitativos (Ex:
PageRank, número de visitas, quantidade de referências, etc)

Usuários ao procurar por um domínio semântico especifico
nesses sistemas podem vir a encontrar o primeiro resultado
correspondente muito além da primeira página.

Nesse trabalho procurou-se agrupar resultados de campos
de conhecimento relacionados a fim de facilitar a pesquisa
do usuário.
+
Relevância do problema

É um assunto atual que atinge um grande número de pessoas
e atualmente várias empresas estão investindo nessa área.

O campo de motores de busca é muito importante e bastante
concorido. A resolução do problema de domínios semânticos
pode vir a ser um diferencial diante do grande número de
ferramentas de buscas existentes.
+
Solução

Para a resolução desse trabalho foi utilizado o Flickr.

Para encontrar grupos semânticos distintos dentro de um
resultado é preciso encontrar semelhanças entre os menbros
de um resultado.

Para encontrar essas semelhanças são utilizadas as tags
específicas de cada resultado de busca do Flickr.
+
O que é uma tag?

Uma tag é um metadado fornecido por um usuário com o
objetivo de descrever um item ao qual é relacionado.

A ocorrência de um par de tags em um resultado é referida
como co-ocorrência e é atribuído a esse par um peso.
+
O que é uma tag?

Para calcular o peso das arestas foi utilizado a métrica de Dice.
WAB 
2 | A B
| A|  | B |

A atribuição de peso leva em conta quantas vezes as duas tags
aparecem em resultados de busca, mas também a quantidade em
que elas aparecem juntas. Isso é muito importante para evitar a
supervalorização de tags que aparecem em grandes quantidades
de resultados.

Quando um par de tags sempre aparece junto o valor do peso de
sua aresta é 1.
+
O que é um cluster?

Um agrupamento de tags é chamado de cluster.

Um cluster representa um domínio semântico e a maioria das
suas tags são sobre o mesmo assunto.

A qualidade de um cluster é medida através das métricas de
coesão e separação:
+
MCL

Para a realização do processo de clusterização dos
resultados foi utilizado o algoritmo MCL que é um processo
iterativo proposto pelo autor Stijn van Dong. Ele se baseia na
clusterização de grafos através da simulação de fluxos
dentro de uma cadeia de Markov.

MCL representa o grafo a ser clusterizado através de uma
matriz estocástica. Cada valor dessa matriz representa a
probabilidade de atingir um nodo i a partir de outro nodo j.
Quanto maior o peso da aresta maior a probabilidade de
atingi-lo.
+
MCL

Para conseguir uma matriz estocástica é preciso realizar o
processo de Normalização.

Neste processo o peso de cada aresta é dividido pela soma
de todos os pesos de todas as arestas ligadas ao nodo i.

Cada linha da matriz terá soma 1 e todos seus valores
representam a probabilidade do nodo i atingir o nodo j.
+
MCL