Análise de Query Log
Thuener Silva Diego Cedrim
Julho, 2008
Sumário
1 Introdução
1
2 Trabalhos Relacionados
2
3 Query Log
2
4 Detecção de Perfil de Usuário
3
5 Análise de Palavras
5.1 Grafo de Palavras . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.2 Experimentos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5
6
7
6 Trabalhos Futuros
8
7 Conclusão
8
1
Introdução
Um fator chave para a popularidade das máquinas de busca atuais é a interface amigável que elas apresentam.
As máquinas de busca permitem que os usuários especifiquem consultas simplesmente como listas de palavraschave, seguindo a abordagem de sistemas tradicionais de recuperação de informação [Baeza-Yates & RibeiroNeto (1999)].
Nem sempre uma lista de palavras-chave descreve bem a informação necessitada pelo usuário. Pode não
ser tão fácil formular consultas que resultem em uma coleção de documentos relevantes para o usuário. Uma
das razões dessa dificuldade é ambiguidade encontrada em muitos termos da linguagem natural [Baeza-Yates
et al. (2004)]. Em nosso estudo, pudemos detectar que a maioria das consultas submetidas têm poucos
termos (seção 3), aumentando a probabilidade da consulta ser ambı́gua.
O objetivo do nosso trabalho é analisar um log de consultas e analisar o comportamento e o relacionamento
de palavras ambı́guas e não ambı́guas para tentar reconhecer padrões que as identifiquem exclusivamente.
Se pudermos encontrar com precisão palavras ambı́guas e seus sentidos, poderemos identificar o contexto em
que a consulta está está inserida baseado no perfil de consultas do usuário.
Antes de analisar as palavras das consultas, o foco do nosso trabalho era tentar identificar o perfil de
consultas dos usuários. As tentativas feitas estão detalhadas na seção 4.
Este trabalho é apresentado da seguinte maneira: na seção 2 mostramos alguns trabalhos já realizados na
análise de query logs, na seção 3 falamos detalhadamente sobre o log de consultas que utilizamos, mostrando
algumas estatı́sticas extraı́das, na seção 5 mostramos como foram feitas as análises das palavras ambı́guas
e dos grafos gerados por elas, na seção 6 listamos alguns trabalhos que podem ser feitos futuramente e na
seção 7 podemos ver as considerações finais.
1
2
Trabalhos Relacionados
Baeza-Yates [Baeza-Yates et al. (2004)] propõe um método que, dada uma consulta submetida a uma máquina
de busca, sugere uma lista de consultas relacionadas. As queries relacionadas são baseadas em consultas
anteriormente submetidas. O método proposto é baseado num processo de categorização em que grupos de
consultas semanticamente similares são identificados. Além de descobrir as consultas relacionadas, o método
ordena as recomendações por um critério de relevância.
Zhang [Zhang & Nasraoui (2006)] apresenta um método simples e intuitivo de mineração de log de
consultas para prover recomendações de queries em máquinas de buscas de larga escala. Para obter uma
solução mais compreensiva, foram combinados dois métodos diferentes. O primeiro visa estudar e modelar o
comportamento de buscas sequenciais de usuários e interpretar este comportamento de buscas consecutivas
como um refinamento da consulta, ao passo que o segundo usa técnicas de similaridade baseada em conteúdo.
Broder [Broder et al. (2007)] propõe uma metodologia para construir um sistema robusto de classificação
de queries, que pode identificar milhares de classes de consultas com uma precisão razoável em tempo real,
enquanto negocia processamento com o volume de queries de uma máquina de busca comercial. Dada uma
consulta, seu tópico é identificado classificando os resultados da busca encontrados pela querie. Motivados
pela necessidade de encontrar propagandas relacionadas, os autores focam em consultas raras.
Bianco [Bianco et al. (2005)] foca na identificação e definição de “sessões de usuário”, uma agregação
de várias conexões TCP geradas pelo mesmo host. A identificação das sessões não é trivial. Abordagens
tradicionais se baseiam em mecanismos de limiares de tempo, que são muito sensı́veis ao valor assumido do
limiar e pode ser difı́cil de se estipular o valor do mesmo. Utilizando técnicas de categorização, os autores
definem uma nova metodologia para identificar as sessões sem requerer um valor estipulado a priori para o
limiar de tempo.
Murray [Murray et al. (2006)] introduz uma nova abordagem para identificação de sessões de usuários
baseada na atividade dos mesmos. O método proposto é centralizado no usuário, não na população de
usuários ou no sistema e pode ser aplicado em situações em que o usuário prefere não divulgar informações
pessoais. Os autores adotam técnicas de categorização aglomerativa hierárquica [Jain et al. (1999)] com um
critério de parada que é motivado pelas atividades dos usuários. Uma avaliação feita usando o LOG de
consultas da América Online revela que o algoritmo proposto atinge 98% de precisão em identificar sessões
comparado com julgamentos humanos.
3
Query Log
Utilizamos em nossos experimentos o LOG de consultas do site português SAPO (www.sapo.pt). O LOG
foi armazenado em um arquivo texto de 1.8 GB, formado de consultas coletadas entre 30 de setembro e 31
de outubro de 2007, contabilizando um total de 2.958.444 linhas (consultas).
Em média, as consultas têm 2,5 termos. Dentre as consultas mais submetidas, podemos encontrar “Sexo”
e “Youtube”, além de “Google” e “Gmail”. Na Tabela 1(a) podemos ver as dez consultas mais submetidas
à máquina de busca do SAPO. Na primeira coluna podemos ver a posição da palavra na lista ordenada, na
do meio vemos o número de vezes que a consulta foi enviada e a terceira mostra o texto submetido. Para
chegarmos a esses valores, tratamos cada consulta como uma palavra e contamos quantas vezes ela se repete
em todo o LOG.
Além de encontrar as consultas mais pesquisadas, fizemos uma varredura no LOG para saber quais
palavras mais aparecem nas consultas. Dentre as mais populares estão “Portugal” e “Lisboa”. Na tabela
1(b) podemos ver as dez primeiras palavras buscadas. Na primeira coluna encontramos a posição da palavra
na lista ordenada, na segunda vemos o número de vezes que a palavra aparece e na terceira podemos ver a
palavra procurada.
A maioria das consultas possui apenas um termo de busca (cerca de 43%), mas existe um número
considerável de consultas com dois e três termos (26% e 15% respectivamente). Na figura 1 podemos ver um
gráfico que relaciona o número de termos das consultas com o número de consultas realizadas. É notório
que o número de consultas diminui quando se aumenta o número de termos.
Para trabalharmos com dados mais amigáveis, foi necessário fazer a construção de um dicionário de
palavras. Tivemos que retirar do arquivo contendo as consultas todos os acentos das palavras e transformar
alguns caracteres em formato UTF-8 para ASCII. Foram retiradas também 321 stopwords. Somente foram
Posição
1
2
3
4
5
6
7
8
9
10
Número de Buscas
36969
30228
15455
11628
10051
9301
6315
5773
5649
5344
Consulta
hi5
google
sexo
youtube
gmail
hotmail
rfm
tmn
tempo
google pt
Posição
1
2
3
4
5
6
7
8
9
10
((a)) Consultas mais Submetidas
Número de Figurações
91048
48243
47415
30648
25625
22693
19377
15312
14693
14099
Palavra
pt
hi5
google
sexo
jogos
portugal
sapo
youtube
hotmail
lisboa
((b)) Palavras mais Submetidas
Tabela 1: Dados sobre as consultas
Figura 1: Número de Consultas por Termos
aceitas palavras que aparecem no mı́nimo duas vezes. Todas as palavras que não estavam contidas no
dicionário foram desconsideradas nos experimentos.
4
Detecção de Perfil de Usuário
A nossa meta inicial era identificar o perfil de consultas dos usuários cujos dados estavam no nosso log.
Podemos entender “perfil” como sendo uma indicação do contexto em que o usuário está inserido. Analisando nossos logs pessoais de consultas no Google (www.google.com/history/), podemos ver que fazemos
muitas consultas relacionadas à informática, mostrando que estamos inseridos no mundo da computação. Se
pudermos identificar automaticamente o que fizemos manualmente em nossos logs, podemos trazer alguns
benefı́cios para as máquinas de busca:
• PageRank personalizado;
• Recomendação de produtos;
• Links Patrocinados mais precisos;
• Recomendação de consultas para desambiguação.
Para identificar os perfis, primeiramente tentamos encontrar os tipos de consultas existentes. Representamos cada consulta como um vetor e categorizamos com k-means para encontrar os tipos. Para construir
os vetores a partir das consultas, primeiramente geramos um dicionário de tamanho d de todas as palavras
submetidas à máquina de busca e atribuı́mos um número para cada palavra. Assim, cada vetor tem dimensão
d e possui o valor zero em todas as componentes cujo ı́ndice represente uma palavra que não está na consulta.
Como exemplo, suponha o dicionário da tabela 2(a) e as consultas da tabela 2(b).
Índice
1
2
3
4
5
6
Palavra
Bola
Casa
Cachorro
Mão
de
Carro
Número
1
2
3
4
5
6
Consulta
Bola
Casa de Cachorro
Carro
Carro de mão
Cachorro
Mão
((b)) Consultas
((a)) Dicionário
Tabela 2: Dicionário e Consultas
Representadas como vetores, as consultas da tabela 2(a) aparecem na tabela 3
Número da Consulta
1
2
3
4
5
6
Vetor
(1, 0, 0, 0, 0, 0)
(0, 1, 1, 0, 1, 0)
(0, 0, 0, 0, 0, 1)
(0, 0, 0, 1, 1, 1)
(0, 0, 1, 0, 0, 0)
(0, 0, 0, 1, 0, 0)
Tabela 3: Vetores das Consultas
Antes de mostrar o algoritmo que implementamos (k-means) iremos definir algumas notações. O número
de clusters k é fixo no k-means. Inicialize os k centroides (w1 , w2 , · · · , wk ) com um dos n vetores de entrada
(i1 , i2 , · · · , in ). Cj é o j-ésimo cluster e a qualidade de cada cluster é calculada pela seguinte função de erro:
E=
k X
X
|il − wj |
2
j=1 il ∈Cj
Por questões de otimização, utilizamos uma estrutura que nos permitiu não armazenar em memória os
milhares de zeros nos vetores. Implementamos o algoritmo 1 retirado do artigo de Khaled Alsabti [Alik
(2008)].
1. O tempo necessário para a execução do primeiro Loop é O(nkd);
2. O tempo requerido para calcular os centroids é O(nd);
3. O tempo requerido para calcular a função de erro é O(nd);
Devido ao volume de dados (quase três milhões de consultas e um dicionário com milhares de palavras),
a tentativa de categorizar as consultas não foi bem sucedida e não obtivemos bons resultados.
Algorithm 1 Algoritmo K-means
Inicialize k vetores (w1 , · · · , wk ) tal que wj = il , j ∈ {1, · · · , k}, l ∈ {1, · · · , n}
Cada cluster Cj é associado ao vetor wj
repeat
for all vetor de entrada il , onde l ∈ {1, · · · , n} do
atribua il ao cluster Cj com o mais próximo wj
end for
for all cluster Cj il , onde j ∈ {1, · · · , k}Pdo
atualize o centroide wj tal que wj = il ∈Cj il / |Cj |
end for
compute a função de erro E
until E não mude significativamente ou os membros dos clusters não mudem
5
Análise de Palavras
Usamos o log do site Sapo para analisar o comportamento de palavras ambı́guas e não ambı́guas, com o
intuito de reconhecer padrões para posteriormente identificar se uma palavra é dúbia ou não. Iniciamos
nosso estudo com um conjunto de palavras ambı́guas e outro com não ambı́guas para gerarmos um grafo a
partir das consultas que utilizam as palavras do dicionário. Nas seguintes subseções apresentaremos como
gerar tal grafo (subseção 5.1) e mostraremos alguns resultados (subseção 5.2).
Figura 2: Grafo da Palavra Jaguar
A intuição é que um palavra ambı́gua vai estar ligada a palavras que estão considerando-a com significados
diferentes e essa por serem de assuntos diferentes provavelmente não vão estar ligadas entre si. Nesse trabalho
denominamos esse comportamento de ponto de separação. Um exemplo é a palavra jaguar que poderia ser
utilizada com dois diferentes sentidos de felino e marca de carro. Para formar o grafo obtemos o conjunto
de palavras que estão ligadas diretamente com um palavra ambı́gua, ou seja procura Querys com ambas as
palavras, para cada Query encontrada é adiciona-se aresta ou uma unidade ao peso da aresta se a mesma
já existir. Para essas palavras encontradas, colocar-se um aresta entre pares de palavras que estão contidas
em uma mesma Query. Exemplo : jaguar está ligado diretamente com felino, leopardo, animal, jaguatirica,
onca, porsche, carro, ferrari e motor. Nesse caso nenhuma das palavras encontrada estão juntas em uma
Query, por isso não tem nenhuma arestas entre elas. A figura 2 ilustra como seria o grafo.
A proposta é formar um grafo parecido com a figura 2 e depois rodar um algorı́timo sobre ele para
determinar se a palavra procurada é ambı́gua.
5.1
Grafo de Palavras
Para melhor ilustrar o processo de geração do grafo de palavras, considere o conjunto de consultas apresentado
na tabela 4. Esta tabela lista seis consultas que giram em torno da palavra “tempo”, que é uma palavra que
pode ter mais de um sentido. Observe que no conjunto de consultas apresentado, a palavra tempo aparece
no contexto meteorológico e no cronológico.
Número
1
2
3
4
5
6
Consulta
previsão meteorologia tempo
previsão tempo amanhã barcelona
tempo meteorologia Itália
tempo livre
tempo de andar
tempo de informação
Tabela 4: Consultas Exemplo
A geração do grafo se inicia representando cada palavra do conjunto de consultas como vértices (figura
3 ). Observe que a palavra “de” não aparece no grafo, eliminamos ela junto com todas as outras chamadas
stopwords.
Figura 3: Palavras Representadas por Vértices
Depois de representar cada palavra como um vértice do grafo, inserimos arestas entre as palavras que
aparecem na mesma consulta (figura 4). Uma aresta entre dois vértices quer dizer que em algum momento
as duas palavras aparecem em uma mesma consulta.
Figura 4: Palavras Representadas por Vértices com Arestas
Depois disso, colocamos pesos nas arestas, indicando quantas vezes as palavras apareceram juntas em
uma mesma consulta (figura 5). Essa figura apresenta pesos em apenas alguns vértices para não poluir ainda
mais o grafo.
Figura 5: Palavras Representadas por Vértices com Arestas e Pesos
Depois desta fase, alguns cortes são efetuados para reduzir o número de arestas no grafo. No nosso caso,
eliminamos arestas com pesos menores que cinco. A tı́tulo de ilustração, excluiremos todos os vértices de
peso 1 do nosso grafo (figura 6).
Figura 6: Grafo com Cortes
Depois dos cortes o grafo está completo. Foram grafos dessa natureza que analisamos em nosso trabalho.
Na subseção seguinte mostraremos mais detalhes sobre a análise.
5.2
Experimentos
Foi realizado um experimento com a palavra tempo para determinar quais os seus vizinhos, ou seja quais
palavras aparecem na mesma Query que a palavra tempo. Inicialmente foi feito sem levar em consideração
os pesos das arestas. Foi gerado um grafo com 166 nós e 1674 arestas. Como o grafo ficou muito extenso
e com palavras como madeira, que não fazem muito sentido conectadas com tempo. Por esse motivo foi
utilizado os pesos das arestas como forma de seleção. Pegando somente as arestas com peso acima de 5
foi gerado um grafo com 16 nós e 154 arestas. Tanto no primeiro grafo com 166 nós e no segundo com
16 nós nenhum era induzia a utilização da palavra tempo no sentido de perı́odo. Foram tentados outros
experimentos com as palavras ambı́guas: forte, casa e Porto. A palavra casa pode ser usada porque foram
retirados todos os acentos das palavras contidas no LOG. A intuição da utilização da palavra porto foi dada
por causa da origem do LOG. Mesmo assim não foram obtidos bons resultados no três casos. Foi tentado
ainda um experimento com a palavra mapa, para tentar identificar o comportamento de uma palavra não
ambı́gua e como o esperado a palavra não tinha um comportamento similar com um ponto de separação.
6
Trabalhos Futuros
Como continuação do trabalho, devemos utilizar os resultados dos experimentos para gerar um algoritmo
de detecção de palavras ambı́guas. Este algoritmo seria bastante útil se conseguı́ssemos detectar o perfil
do usuário, já que analisando o perfil poderı́amos saber qual o sentido da palavra que o usuário busca,
melhorando e tornando ainda mais amigável a interface das máquinas.
Em uma fase posterior, seria interessante validarmos os algoritmos em um query log mais completo que
o do Sapo, já que este só conta com informações básicas da busca, impossibilitando várias aplicações de
algoritmos já desenvolvidos. Como o proposto por Baeza-Yates [Baeza-Yates et al. (2004)].
7
Conclusão
Não tivemos exito para detecção do perfil do usuário. Isso foi causado por uma série de fatores com: falta
de informações no LOG, dificuldade de padronização das palavras e pouca capacidade de processamento.
Mas a extração de perfil do usuário através do LOG é possı́vel e há muitos trabalhos nesse assunto. A
análise de palavras ambı́guas somente seria possı́vel com um LOG mais extenso. Principalmente pelo tipo
de informação que se é encontrada nesse tipo de LOG. Por exemplo no experimento com a palavra tempo
não foi possı́vel achar nenhuma com sentido de perı́odo. O que é fácil de entender levando em consideração
ao tipo de informação que normalmente o usuário deseja.
Referências
Alik, K. R. (2008), ‘An efficient k’-means clustering algorithm’, Pattern Recogn. Lett. 29(9), 1385–1391.
Baeza-Yates, R. A. & Ribeiro-Neto, B. (1999), Modern Information Retrieval, Addison-Wesley Longman
Publishing Co., Inc., Boston, MA, USA.
Baeza-Yates, R. A., Hurtado, C. A. & Mendoza, M. (2004), Query recommendation using query logs in
search engines., in W. Lindner, M. Mesiti, C. Türker, Y. Tzitzikas & A. Vakali, eds, ‘EDBT Workshops’,
Vol. 3268 of Lecture Notes in Computer Science, Springer, pp. 588–596. URL
http://dblp.uni-trier.de/db/conf/edbtw/edbtw2004.html#Baeza-YatesHM04.
Bianco, A., Mardente, G., Mellia, M., Munafo, M. & Muscariello, L. (2005), ‘Web user session
characterization via clustering techniques’, Global Telecommunications Conference, 2005. GLOBECOM
’05. IEEE 2, 6 pp.–.
Broder, A. Z., Fontoura, M., Gabrilovich, E., Joshi, A., Josifovski, V. & Zhang, T. (2007), Robust
classification of rare queries using web knowledge, in ‘SIGIR ’07: Proceedings of the 30th annual
international ACM SIGIR conference on Research and development in information retrieval’, ACM, New
York, NY, USA, pp. 231–238.
Jain, A. K., Murty, M. N. & Flynn, P. J. (1999), ‘Data clustering: a review’, ACM Comput. Surv.
31(3), 264–323.
Murray, G. C., Lin, J. & Chowdhury, A. (2006), ‘Identification of user sessions with hierarchical
agglomerative clustering’, ASIST’06 1, 3–8.
Zhang, W., Liu, S., Yu, C. T., Sun, C., Liu, F. & Meng, W. (2007), Recognition and classification of noun
phrases in queries for effective retrieval., in M. J. Silva, A. H. F. Laender, R. A. Baeza-Yates, D. L.
McGuinness, B. Olstad, Øystein Haug Olsen & A. O. Falcão, eds, ‘CIKM’, ACM, pp. 711–720. URL
http://dblp.uni-trier.de/db/conf/cikm/cikm2007.html#ZhangLYSLM07.
Zhang, Z. & Nasraoui, O. (2006), ‘Mining search engine query logs for query recommendation’, Proceedings
of the 15th international conference on World Wide Web pp. 1039–1040.