UNIVERSIDADE CATÓLICA DO SALVADOR
BACHARELADO EM INFORMÁTICA
Alex Chastinet Duarte de Souza
Aprimoramento do Algoritmo de Similaridade
entre Documentos
Baseado no Modelo Vetorial em um SIP
Salvador – BA
Dezembro/2007
Alex Chastinet Duarte de Souza
Aprimoramento do Algoritmo de Similaridade
entre Documentos
Baseado no Modelo Vetorial em um SIP
Monografia apresentada por Alex Chastinet Duarte
de Souza ao Departamento de Informática da
Universidade Católica do Salvador como prérequisito para a obtenção do título de Bacharel em
Informática.
Orientador: Prof. Msc. Edeyson Gomes.
Salvador – BA
Dezembro/2007
UNIVERSIDADE CATÓLICA DO SALVADOR
BACHARELADO EM INFORMÁTICA
Aprimoramento do Algoritmo de Similaridade
entre Documentos
Baseado no Modelo Vetorial em um SIP
Edeyson Andrade Gomes
Eduardo Manuel de Freitas Jorge
Nome do componente da banca
Salvador – BA
Dezembro/2007
CERTIFICADO
Certifico que a presente memória APRIMORAMENTO DO ALGORITMO DE
SIMILARIDADE ENTRE DOCUMENTOS BASEADO NO MODELO VETORIAL EM
UM SIP, foi realizada, sob a minha direção, por Alex Chastinet Duarte de Souza,
constituindo o projeto final do curso de Bacharelado em Informática da Universidade
Católica do Salvador – UCSal.
Salvador, 04 de Dezembro de 2007.
Orientador: _________________________
Edeyson Andrade Gomes
Salvador – BA
Dezembro/2007
DEDICATÓRIA
AGRADECIMENTOS
Resumo
A busca por informação com alto grau de relevância em ambientes heterogêneos
como a internet é uma tarefa que requer sistemas especializados, capazes de prover
uma interação constante com o consumidor a fim de refinar os resultados obtidos,
garantindo o máximo de precisão. Os sistemas de informação personalizados são
adequados a fornecer informação relevante devido a sua característica de utilizar a
resposta do usuário aos resultados retornados como medida de avaliação,
ajustando-se para melhorar a eficácia em pesquisas futuras. Para que a eficácia
deste processo seja maximizada, é necessária a utilização de um algoritmo de
classificação eficiente. Este trabalho pretende aprimorar e avaliar um algoritmo de
classificação baseado no modelo vetorial no sistema personalizado de informação
(SIP) Fidus.
Palavras-chave: Recuperação de informação, RI, modelo vetorial, SIP, Fidus
SUMÁRIO
LISTA DE FIGURAS .................................................................................................11
LISTA DE TABELAS .................................................................................................12
LISTA DE GRÁFICOS...............................................................................................13
LISTA DE LISTAGENS .............................................................................................14
Introdução .................................................................................................................14
1.
Recuperação de Informação ..............................................................................17
1.1.
1.1.1.
Representação da informação .............................................................18
1.1.2.
Operações textuais ..............................................................................19
1.1.3.
Processo de indexação........................................................................20
1.1.4.
Classificação de documentos ..............................................................20
1.2.
Modelos clássicos de RI .............................................................................20
1.2.1.
Modelo booleano .................................................................................21
1.2.2.
Modelo vetorial.....................................................................................21
1.2.3.
Modelo probabilístico ...........................................................................24
1.3.
2.
Arquitetura da básica da recuperação de informação.................................18
Medidas de avaliação de um SRI ...............................................................25
Fidus ..................................................................................................................27
2.1.
Arquitetura simplificada do Fidus ................................................................28
2.1.1.
Perfil do usuário ...................................................................................28
2.1.2.
Indexação de documentos...................................................................29
2.1.3.
Cálculo de pesos .................................................................................30
2.1.4.
Análise de similaridade ........................................................................32
3.
Implementação e teste do modelo vetorial no Fidus ......................................33
3.1.
Implementação ...........................................................................................33
3.1.1.
Ambiente..............................................................................................33
3.1.2.
Diagrama de classe .............................................................................33
3.1.3.
Representação da informação .............................................................34
3.1.4.
Implementação do cálculo de similaridade ..........................................36
3.2.
Teste ...........................................................................................................37
3.2.1.
Metodologia .........................................................................................38
3.2.2.
Primeira iteração..................................................................................39
3.2.3.
Segunda Iteração.................................................................................41
3.2.4.
Terceira iteração ..................................................................................44
3.2.5.
Quarta iteração ....................................................................................47
3.2.6.
Quinta iteração.....................................................................................49
3.2.7.
Sexta iteração ......................................................................................51
3.2.8.
Sétima iteração ....................................................................................54
3.2.9.
Oitava iteração.....................................................................................57
3.2.10.
Nona iteração ...................................................................................59
3.2.11.
Décima iteração ...............................................................................61
3.2.12.
Conclusão dos testes .......................................................................63
Conclusão .................................................................................................................65
Referências ...............................................................................................................66
APÊNDICE A.............................................................................................................68
A1.
Introdução ...................................................................................................68
A2.
Primeira iteração .........................................................................................68
A3.
Segunda iteração ........................................................................................69
A4.
Terceira iteração .........................................................................................69
A5.
Quarta iteração ...........................................................................................70
A6.
Quinta iteração............................................................................................70
A7.
Sexta iteração .............................................................................................71
LISTA DE FIGURAS
Figura 1 - Arquitetura da RI. Adaptado de Baeza-Yates e Ribeiro-Neto (1999). .......18
Figura 2 - Representação de um espaço vetorial. Adaptado de Baeza-Yates e
Ribeiro-Neto (1999)...................................................................................................22
Figura 3 - Tela principal do Fidus ..............................................................................27
Figura 4 - Arquitetura simplificada do Fidus. Adaptado de Gomes (2001) ................28
Figura 5 - Diagrama de classes do módulo de análise de similaridade.....................33
LISTA DE TABELAS
Tabela 1 - Resultado da primeira iteração.........................................................................40
Tabela 2 - Avaliação da primeira iteração .........................................................................41
Tabela 3 - Resultados da segunda iteração......................................................................43
Tabela 4 - Avaliação da segunda iteração ........................................................................44
Tabela 5 – Resultados da terceira iteração.......................................................................45
Tabela 6 - Avaliação da terceira iteração ..........................................................................46
Tabela 7 - Resultado da quarta iteração............................................................................48
Tabela 8 - Avaliação da quarta iteração ............................................................................49
Tabela 9 - Resultado da quinta iteração ............................................................................50
Tabela 10 - Avaliação da quinta iteração...........................................................................51
Tabela 11 - Resultado da sexta iteração ...........................................................................53
Tabela 12 - Avaliação da sexta iteração............................................................................54
Tabela 13 - Resultado da sétima iteração .........................................................................55
Tabela 14 - Avaliação da sétima iteração..........................................................................56
Tabela 15 - Resultado da oitava iteração ..........................................................................58
Tabela 16 - Avaliação da oitava iteração...........................................................................59
Tabela 17 - Resultado da nona iteração............................................................................60
Tabela 18 - Avaliação da nona iteração.............................................................................61
Tabela 19 - Resultado da décima iteração........................................................................62
Tabela 20 - Avaliação da décima iteração.........................................................................63
LISTA DE GRÁFICOS
Gráfico 1 - Comparação de relevância potencial entre os algoritmos ..........................44
Gráfico 2 - Comparação de relevância potencial entre os algoritmos ..........................46
Gráfico 3 - Comparação de relevância potencial entre os algoritmos ..........................48
Gráfico 4 - Comparação de relevância potencial entre os algoritmos ..........................51
Gráfico 5 - Comparação de relevância potencial entre os algoritmos ..........................54
Gráfico 6 - Comparação de relevância potencial entre os algoritmos ..........................56
Gráfico 7 - Comparação de relevância potencial entre os algoritmos ..........................58
Gráfico 8 - Comparação de relevância potencial entre os algoritmos ..........................61
Gráfico 9 - Comparação de relevância potencial entre os algoritmos ..........................63
LISTA DE LISTAGENS
Listagem 1 - Criação do vetor de termos ..................................................................35
Listagem 2 - Cálculo de similaridade através co-seno do angulo entre os vetores. ..36
14
Introdução
É inegável que a popularização do acesso à internet proporcionou uma
ampla difusão de informação, atingindo qualquer pessoa que possua um dispositivo
(computador, celular etc.) capaz de interagir com a rede.
Com o advento da Web e a constante evolução de interfaces humanocomputador, incrementando sua usabilidade, o usuário deixou de ser um ponto
passivo, que apenas recebia as informações disponibilizadas, para tornar-se de fato
um produtor de informação. Baeza-Yates e Ribeiro-Neto (1999) identificam que a
“liberdade para publicar” é um dos três fatores, além do baixo custo e o acesso a
informação, que colaboram para popularidade da Web.
Apesar de favorecer a uma democratização na divulgação de idéias e
conhecimento, a liberdade e facilidade proporcionada ao usuário, para disponibilizar
informação através da internet, tornou-se um problema. Uma grande quantidade de
usuários publicando informação incoercivelmente, resultou em uma explosão de
documentos disponíveis na Web.
Vale ressaltar que estes documentos caracterizam-se por serem
desestruturados, além de não possuírem qualquer tipo de padronização. Por
estruturação entende-se a organização bem definida de regiões em documento onde
se pode encontrar determinada informação como, por exemplo, uma tabela (linhas x
colunas) em um banco de dados (GREENGRASS 2000). A heterogeneidade de
fontes de informação no ambiente Web termina por dificultar a recuperação das
informações contidas neste vasto espaço de busca.
Diversas soluções foram implementadas para tentar extrair informações
da coleção de documentos contidos na internet. As mais usuais são ferramentas de
busca como o Google1, que a partir de palavras-chave que caracterizam o objeto da
pesquisa retornam as fontes onde ocorreu correspondência entre os termos contidos
na pesquisa e também no documento. Esta abordagem se caracteriza por recuperar
conjuntos de publicações com quantidades de elementos que podem ultrapassar
milhões de unidades, superando a capacidade de avaliação do usuário
1
http://www.google.com.br
15
(VENERUCHI 1999). Consequentemente, o número de interações com a ferramenta
para obter um refinamento da pesquisa, reduzindo assim seu espaço de busca, é
muito grande.
Em relação ao usuário, como consumidor de informação, é possível
classificá-lo em dois grupos, o que realiza buscas exploratórias e o que realiza
buscas regulares. A busca exploratória se caracteriza no caso em que o usuário
necessita de uma informação, mas não sabe exatamente como chegar ao resultado
desejado. Assim, as ferramentas de busca tradicionais acabam por ajudar a
determinar o foco da pesquisa, pois fornecem um amplo conjunto de documentos
para serem analisados. No caso do usuário regular, cujo interesse de pesquisa é
bem definido e constante, a abordagem tradicional não é recomendada. Para este
consumidor de informação os critérios de busca já estão suficientemente
caracterizados (GOMES 2001), de maneira que apenas documentos relevantes
deveriam lhe ser apresentados.
Para suprir a necessidade de maior eficiência no processo de busca,
tendo em vista as pesquisas regulares, surgiram sistemas especializados que
reduzem o esforço do usuário durante a recuperação de documentos. Denominados
SIP (Sistemas de Informação Personalizados) estes sistemas de busca possuem
como característica principal o uso de interações sucessivas com o consumidor de
informação para delimitar sua área de interesse, definindo assim o seu perfil. De
posse das informações que caracterizam o interesse do usuário, a ferramenta passa
a executar um pré-julgamento nos documentos retornados, determinando aqueles
que são efetivamente relevantes (GOMES 2001).
O componente principal de um sistema de recuperação de informação
(SRI) como um SIP, no que tange o cálculo de relevância dos documentos, é o
algoritmo de classificação (BAEZA-YATES; RIBEIRO-NETO 1999). Sua função é
calcular o quanto um documento é relevante, a partir de palavras que o compõe, em
relação às características extraídas do perfil de um usuário. Quanto maior a eficácia
do algoritmo, maior é a probabilidade de recuperação de informações relevantes no
contexto definido.
Este trabalho pretende demonstrar o aprimoramento da capacidade de
recuperação de documentos relevantes do Fidus, um SIP desenvolvido por Edeyson
Gomes em seu mestrado (GOMES 2001), através de um novo algoritmo de
16
classificação. Para tanto, será reescrito seu algoritmo de recuperação de
informação, utilizando-se como referência o modelo vetorial, e serão realizados
testes comparativos com o modelo de classificação anterior para determinar os
ganhos obtidos com a nova implementação.
Para cumprir o objetivo proposto, será realizada uma pesquisa
bibliográfica sobre os conceitos básicos relacionados à recuperação de informação
(RI). Uma visão dos modelos clássicos como o booleano, o vetorial e o probabilístico
fará parte do estudo. Serão pesquisadas também as medidas de avaliação aplicadas
a sistemas de RI.
Um estudo do Fidus fará parte do referencial teórico deste trabalho. Nele
será descrita a arquitetura atual do sistema, detalhando os principais processos que
a compõem.
Os testes realizados com os algoritmos pesquisados utilizarão um corpus
composto por 100 documentos, cada um com sua relevância real previamente
determinada. Cada documento será formado por 10 termos previamente
selecionados de diversos temas. Através deste corpus controlado, será possível
comparar os resultados de relevância potencial apresentada pelo algoritmo de
recuperação para cada documento com a relevância real atribuída.
Este trabalho está organizado em três capítulos. O primeiro capítulo
apresenta os conceitos básicos que norteiam a área de recuperação de informação,
incluindo uma visão da arquitetura básica de um sistema de RI.
O segundo capítulo apresenta o Fidus, descrevendo suas características
e também sua arquitetura. Este capítulo contém um detalhamento do algoritmo
utilizado no sistema para calcular a relevância de um documento. O terceiro capítulo
contém a descrição da implementação do novo algoritmo para calcular a relevância
de documentos, a descrição da metodologia de testes aplicada para a validação do
algoritmo e os resultados encontrados para cada teste realizado. Por fim encontra-se
a conclusão do trabalho indicando os resultados obtidos com a utilização do novo
algoritmo de classificação e algumas sugestões para trabalhos futuros.
17
1. Recuperação de Informação
Segundo Ribeiro Neto e Baeza-Yates (1999), a recuperação de
informação é um campo da ciência que trata da representação, armazenamento,
organização e o acesso à informação.
Salton (1986) define recuperação de informação como uma área de
estudos que “lida com análise textual, armazenamento textual e a recuperação de
registros armazenados” que possam estar relacionados a uma necessidade de
informação requisitada por “uma população de usuários”.
As pesquisas realizadas em RI, por muitos anos, estiveram restritas a
resolver problemas relacionados ao gerenciamento e organização de informações
em documentos textuais armazenados em bibliotecas. Com a popularização dos
computadores e o surgimento de redes de comunicação, o volume de informações
disponíveis
cresceu
exponencialmente,
porém
de
forma
desorganizada
e
desestruturada. O esforço de pesquisa nessa área volta-se então para este conjunto
de documentos, tendo o interesse de instituições acadêmicas, como as
universidades
de
Berkeley,
Cambridge
e
Cornell,
além
de
organizações
governamentais como a DARPA (Defense Advanced Research Projects Agency Agência de Pesquisas em Projetos Avançados de Defesa) (VOORHEES 1998).
Desta forma, a RI ressurge como uma solução para atender a demanda por
informação relevante em ambientes complexos cujo espaço de busca é imensurável,
como a WEB.
Sob a ótica da ciência da computação, pode-se afirmar que o principal
objetivo da área de recuperação de informação é estudar métodos eficazes para a
extração de informações em um conjunto amplo de documentos2, armazenados em
repositórios computacionais, que possam atender a uma necessidade definida pelo
usuário.
2
Em RI, entende-se documento como uma composição de informações textuais escritas em
linguagem natural (GREENGRASS 2000).
18
1.1. Arquitetura da básica da recuperação de informação
A Figura 1 apresenta a arquitetura básica do processo de recuperação de
informação. Esta seção descreve os seus principais elementos.
Figura 1 - Arquitetura da RI. Adaptado de Baeza-Yates e Ribeiro-Neto (1999).
1.1.1. Representação da informação
Os documentos podem ser classificados como estruturados, semiestruturados ou não estruturados.
Estruturado é todo documento organizado em regiões de sintaxe bem
definida, onde se extrai com facilidade uma informação desejada. Uma tabela em
banco de dados relacional é um exemplo de documento estruturado, onde cada
coluna identifica a informação contida.
Semi-estruturado é um documento composto por algumas regiões
compostas por metadados que o caracterizam, porém a região onde está localizada
a informação propriamente dita não possui indicadores ou marcações. Documentos
HTML3 (HyperText Markup Language) são considerados como semi-estruturados
pois possuem um cabeçalho, região de metadados e um corpo de texto sem
estruturação definida.
Já um documento não estruturado pode ser definido como aquele que
apresenta apenas informações textuais em linguagem natural, não possuindo
qualquer tipo de indicador que auxilie na recuperação das informações contidas em
3
http://www.w3c.org/TR/html4/ acessado em 14/10/2007.
Exclu
19
seu corpo. Artigos e notícias podem ser exemplos de documentos sem estruturação.
As soluções em RI estão focadas na extração de informação nos dois últimos tipos
de documentos apresentados (GRENGRASS 2000).
A representação da necessidade do usuário, no contexto da RI,
geralmente é realizada através de termos que melhor expressem a informação a ser
obtida. Estes termos, denominados de palavras-chave, possuem uma maior
probabilidade de estarem contidos em documentos relevantes para a necessidade a
ser atendida. As palavras-chave podem ser definidas manualmente pelo usuário ou
podem ser selecionadas com ajuda de um sistema computacional. Vale ressaltar
que, diferentemente da recuperação de dados, RI lida com a linguagem natural e
com a ambigüidade semântica que esta possui. Desta forma, nem todas as
palavras-chave selecionadas para representar a necessidade de informação podem
estar contidas nos documentos pesquisados.
1.1.2. Operações textuais
Os documentos analisados durante a busca por informação relevante
podem ser compostos por milhares de termos. Ocorre que grande parte destes
termos não possui um significado que represente a informação contida no
documento. Artigos, proposições e pronomes são exemplos de termos que não são
relevantes na análise do documento e são denominados stopwords (GOMES 2001).
Desta forma, a determinação da similaridade entre as palavras-chave que compõem
a necessidade do usuário e todos os termos de um documento é um processo pouco
efetivo.
Devido à ambigüidade intrínseca a linguagem natural, as palavras-chave
selecionadas para compor uma consulta podem não corresponder exatamente com
os termos contidos em documento relevante, mas sim com variações dessas. Em
conexo e desconexo tem-se um exemplo onde ocorre a variação do prefixo entre
duas palavras. Assim, para lidar com este tipo de situação, utiliza-se a técnica de
stemming, onde ocorre a redução de termos a um stem, termo resultante da
remoção de afixos (prefixos e sufixos).
20
1.1.3. Processo de indexação
A indexação do documento, isto é, a seleção de termos que melhor
expressem a informação contida no mesmo, pode ser realizada de duas formas
distintas. A primeira corresponde a eleger todos os termos do documento como
índices e é conhecida como indexação full-text (SALTON 1993). Nesta abordagem,
não existe qualquer tipo de diferenciação entre os termos em relação a sua
importância no contexto da informação. A outra técnica de indexação busca capturar
apenas termos que carreguem um significado semântico relevante ao conteúdo do
documento analisado, podendo ser realizada manualmente por especialista ou
automaticamente através de um sistema computacional. Para eliminar os termos de
baixa relevância, são realizadas algumas operações textuais, como a remoção de
stopwords e stemming antes da indexação do documento.
Comumente, a seleção automática de índices em um documento pode ser
realizada através da análise de freqüência dos termos contidos no mesmo (YU; LAN;
SALTON 1982; GOMES 2001), elegendo-se os termos mais freqüentes.
1.1.4. Classificação de documentos
Para determinar a relevância potencial de um documento, um sistema de
RI necessita avaliar a similaridade entre uma consulta realizada pelo consumidor de
informação e os documentos encontrados durante a busca. A avaliação da
similaridade geralmente é realizada com o auxílio de um algoritmo de classificação.
Este algoritmo, baseado em um modelo de recuperação de informação
existente, ordenará os documentos apresentados ao usuário pelo nível de relevância
calculada.
1.2. Modelos clássicos de RI
Existem diversos de modelos de recuperação de informação, porém a
maior parte dos algoritmos de classificação fundamenta-se inteiramente ou em
variações de três tipos de modelos, conhecidos como modelos clássicos de RI. São
eles os modelos booleano, vetorial e o probabilístico.
21
1.2.1. Modelo booleano
O modelo booleano utiliza-se da teoria dos conjuntos e da álgebra
boolena para determinar a relevância potencial de um documento. É um modelo cujo
funcionamento é de fácil compreensão para o usuário, como também é simples a
implementação de um algoritmo de classificação baseado no mesmo. Neste modelo,
um documento é definido como um conjunto de termos. As consultas são realizadas
com expressões booleanas, cuja semântica é precisa, formada por operadores como
AND, OR ou NOT.
Dada uma consulta do usuário, um documento pode ser classificado
apenas como relevante ou irrelevante, não existindo o conceito de graus de
relevância. Para ser classificado como relevante, o conjunto de termos do
documento deve obedecer à relação descrita na expressão booleana que representa
a consulta do usuário, caso contrário o documento será definido como irrelevante.
Considerando uma consulta do usuário com as seguintes palavras-chave,
recuperação e informação, e expressa da seguinte forma:
“Recuperação” AND “Informação”
Através do modelo booleano, qualquer documente que conste pelo menos
um registro de cada uma dessas palavras-chave será considerado como relevante.
As principais desvantagens do modelo booleano são a falta de graduação
de relevância, limitando o sistema a resultados binários (relevante e irrelevante), e a
dificuldade na formulação de consultas complexas por parte de usuários comuns,
devido ao uso de expressões algébricas.
1.2.2. Modelo vetorial
O modelo vetorial, ou modelo espaço vetorial, se caracteriza por permitir
graduar a relevância de um documento em diversos valores, diferentemente do
modelo booleano que permite apenas dois. Neste modelo, a representação de
documentos e consultas é realizada através de vetores cujos elementos são o par
termo peso, onde cada termo possui um peso positivo e não binário. O peso
22
quantifica a importância semântica de um termo em relação aos demais dentro do
contexto da informação contida em um documento.
Os vetores documento e consulta pertencem a um espaço vetorial cuja
dimensão é definida pelo valor máximo de termos contidos em um documento. A
correlação entre os vetores de um espaço vetorial determina a sua proximidade.
Desta forma, para obter-se a similaridade entre um documento em relação a uma
dada consulta, calcula-se o co-seno do ângulo formado por estes dois vetores.
Quanto maior é valor do resultado, mais relevante é um documento para a consulta
realizada.
Na Figura 2 é possível observar um espaço vetorial de 3 (três) dimensões,
onde cada dimensão é representada por um termo contido no sistema (Pa, Pb e Pc).
Os vetores dj e q representam, respectivamente, um documento formado pelos
termos Pa, Pb e Pc e uma consulta composta pelo termo Pb. O ângulo θ indica o
grau de similaridade entre a consulta e o documento no espaço vetorial.
Espaço vetorial t-dimensional, onde t = 3.
Pa
dj
θ
dj =
q
Pb
q =
Pb Pa Pc
Pb
Pc
Pa, Pb e Pc são termos pertencentes
ao documento dj e a consulta q.
Figura 2 - Representação de um espaço vetorial. Adaptado de Baeza-Yates e Ribeiro-Neto
(1999)
Os pesos associados aos termos documento podem ser calculados de
diversas formas, porém as mais citadas (YU; LAN; SALTON 1982; GOMES 2001;
MANNING 2007; BAEZA-YATES; RIBEIRO-NETO 1999) envolvem a utilização da
freqüência do termo em documento diretamente.
Exclu
23
O algoritmo denominado tf (term frequency – freqüência do termo)
considera que o peso de um termo é definido como o valor de sua freqüência em um
documento. Utilizando tf, é possível que ocorram distorções na quantificação dos
pesos. Isoladamente, em um documento, um termo pode apresentar um peso que
não condiz com seu grau de relevância no contexto da busca do usuário, pois, caso
ocorra muitas vezes o valor de seu peso será alto.
Já o algoritmo df (document frequency – freqüência do documento)
ameniza a distorção de termos irrelevantes com altos pesos, pois calcula a
freqüência de termo em relação a um conjunto de documentos. Uma variação do
algoritmo df, o idf (inverse document frequency – freqüência inversa do documento)
associa a um termo um peso igual ao inverso de sua freqüência em conjunto de
documentos. Esta solução justifica-se no caso de buscas realizadas em coleções de
documentos pertencentes a um contexto específico, pois associa altos valores de
peso a termos com baixa freqüência na coleção.
Uma forma muito citada de calcular pesos de termos em documentos
(SALTON 1982; BAEZA-YATES; RIBEIRO NETO 1999) é a união dos algoritmos tf e
idf, resultando no chamado tf-idf. Termos com alta freqüência em alguns
documentos da coleção tendem a possuir pesos elevados, sugerindo alta relevância.
Termos de baixa freqüência que ocorrem em muitos documentos possuem pesos
baixos. Caso o termo ocorra em todos os documentos da coleção seu peso é nulo.
Após o cálculo dos pesos para cada termo do vetor de termo peso do
documento e da consulta, é possível calcular o valor do co-seno do ângulo entre os
vetores para se obter a similaridade entre o documento e a consulta. A fórmula que
representa similaridade é:
24
dj • q
sim( dj, q ) = cos θ =
| dj | X | q |
∑
t
t
i=1
2
2
ωi , j χ ωi , q
=
∑
t
t
i=1
2
ωi , j
χ
∑
t
t
j=1
2
ωi , q
Onde:
•
dj representa o vetor de pares (termo, peso) do documento
•
q representa o vetor de pares (termo, peso) da consulta
•
ω i,j é o peso do termo i no documento j
•
ω i,q é o peso do termo i na consulta q
O modelo vetorial apresenta as seguintes vantagens: incrementa a
precisão da recuperação de informação em relação ao modelo booleano; qualifica os
documentos recuperados em graus de relevância; é flexível, pois caso algum termo
contido na consulta não ocorra em um documento o mesmo não é considerado
irrelevante; é muito eficiente com coleções de documentos genéricos.
1.2.3. Modelo probabilístico
O modelo probabilístico determina a probabilidade de um documento ser
relevante para uma consulta apresentada por um consumidor de informação. O
princípio probabilístico é o pressuposto que fundamenta este modelo.
Conceitualmente, este princípio considera que para cada documento
existente em uma coleção existe uma consulta ótima capaz de retorná-lo. Ocorre
25
que, no início da busca, o usuário pode não ser capaz de descrever esta consulta
por não possuir conhecimento suficiente. Desta forma o modelo probabilístico prevê
que devam ser realizados refinamentos sucessivos da consulta, através de
interações com o usuário, para que a probabilidade de recuperação de um
documento altamente relevante seja elevada.
A probabilidade de um documento d selecionado ser relevante para uma
consulta q é representada por P(+Rq | d), caso contrário, sua probabilidade é P(-Rq |
d). O cálculo da similaridade entre uma consulta do usuário e um documento é
realizado através da fórmula P(+Rq | d) / P(-Rq | d) (CARDOSO, 2001).
Segundo Baeza-Yaetes (1999), a principal vantagem do modelo
probabilístico é o uso da classificação de documentos através da probabilidade de
relevância bem como o princípio probabilístico. As desvantagens do modelo são: a
dependência da precisão das estimativas de probabilidade e a não utilização da
freqüência de termos do documento como referência.
1.3. Medidas de avaliação de um SRI
Antes de entrar em produção, um sistema deve ser testado para garantir
que
está
em
conformidade
com
requisitos
especificados
durante
o
seu
desenvolvimento. Em alguns casos, testes específicos deverão ser aplicados ao
sistema no intuito de avaliar as particularidades referentes ao contexto no qual será
utilizado. Em se tratando de um SRI, as medidas de avaliação específicas mais
difundidas são abrangência (recall) e precisão (precision).
Considerando I como uma consulta do usuário em um conjunto de
documentos de teste T e R como o conjunto de documentos relevantes pertencentes
a T para a consulta I, |R| é o valor numérico que representa o total de documentos
relevantes para a consulta. Assumindo que A é o conjunto de documentos
retornados pelo SRI para a consulta I com base em seu algoritmo de classificação,
então |A| é o valor numérico que representa o total de documentos do conjunto
retornado. Por fim, considera-se |Ra| como o número de documentos na interseção
entre os conjuntos R e A (BAEZA-YATES; RIBEIRO NETO 1999). Desta forma,
infere-se que:
26
•
Abrangência é a fração dos documentos relevantes retornados
pelo sistema.
Abrangência
=
|Ra|
|R|
•
Precisão é a fração dos documentos retornados que são
efetivamente relevantes.
Precisão
=
|Ra|
|A|
Vale ressaltar que estas métricas foram desenvolvidas para serem
utilizadas em testes com conjuntos de documentos controlados. Isto fica claro no
cálculo da abrangência, onde é necessário um conhecimento prévio de todos os
documentos relevantes do conjunto de avaliação (GOMES 2001).
O conjunto de documentos utilizado na avaliação de um sistema de
recuperação de informação é conhecido como coleção de referência (VOORHEES
2007). Esta coleção é composta por três elementos básicos: documentos textuais de
conteúdo variado; consultas, que representam uma necessidade de informação a
ser atendida; um mapeamento entre as consultas e os documentos relevantes para
estas.
Uma das coleções de referência mais citadas (VOORHEES 2007;
BAEZA-YATES; RIBEIRO-NETO 1999; BATISTA JÚNIOR 2006) é a TREC4 (Text
REtrieval Conference). Desenvolvida pela DARPA em conjunto com a NIST
(National Institute of Standards and Technology), a TREC contém um amplo
conjunto de documentos e consultas, denominadas tópicos, bem como as relações
entre cada consulta e os documentos que ela deve retornar.
4
http://trec.nist.gov/ acessado em 08/10/2007.
27
2. Fidus
O Fidus é um SIP que possui como objetivo principal realizar buscas
eficientes a partir de um conjunto de informações que descrevam a necessidade do
usuário de forma estruturada e configurável.
O consumidor de informação regular é o usuário alvo do Fidus. Seus
interesses de pesquisa podem ser descritos através de hierarquias de informação,
associando a cada elemento da estrutura hierárquica palavras-chave que os
representem.
O Fidus, representado na Figura 3, é capaz de realizar buscas em
diversos tipos de repositórios, que podem ser locais, quando os documentos estão
armazenados no computador do usuário, ou na Web, através de metabuscas em
diversos provedores de informação, tanto genéricos, como o Google ou o Yahoo5,
quanto específicos para uma determinada área de conhecimento.
A cada busca de informação efetuada através do Fidus, seu algoritmo de
classificação determina a relevância potencial de cada documento retornado. Esta
avaliação prévia reduz a quantidade de informações irrelevantes a serem exibidas
ao usuário. O Fidus também permite que usuário valide a classificação potencial
realizada. A avaliação efetiva do usuário possibilita ao sistema corrigir qualquer
divergência ocorrida, aumentando sua eficiência em buscas futuras.
Figura 3 - Tela principal do Fidus
5
http://www.yahoo.com
28
2.1. Arquitetura simplificada do Fidus
A Figura 4 representa uma simplificação do modelo arquitetural do
sistema de informação pessoal Fidus. Esta seção detalhará os componentes mais
importantes contidos na Figura.
Figura 4 - Arquitetura simplificada do Fidus. Adaptado de Gomes (2001)
2.1.1. Perfil do usuário
O perfil do usuário é formado por uma estrutura hierárquica que contém
todos os interesses de informação de um usuário que deseja obter documentos
relevantes através do Fidus.
Em um perfil estão associadas as categorias de informação de interesse
do usuário. Basicamente, cada categoria de informação é composta por uma
descrição, um conjunto de palavras-chave e a indicação de sua posição em uma
hierarquia de conhecimento.
A descrição expressa um detalhamento do usuário a respeito de uma
determinada categoria de informação. Sua utilidade é a de expressar que tipo de
informação pode ser encontrado na categoria.
As palavras-chave são os termos definidos pelo usuário que melhor
representam semanticamente a categoria de informação. Essas palavras serão
29
utilizadas como critérios de busca nos diversos provedores de informação
disponíveis para a recuperação de documentos. Além disso, as palavras-chave são
os principais elementos que determinam a relevância potencial de um documento.
A categoria de informação pode possuir também uma indicação de que
pertence a uma hierarquia de conhecimento, de forma que se organize melhor a
busca de informação. Esta indicação é realizada através da referência a uma
categoria de informação superior na hierarquia.
2.1.2. Indexação de documentos
Cada documento retornado pelo componente de busca global dos
repositórios de informação é indexado para que, posteriormente, seja possível
representá-lo através de um vetor de termos.
O processo de indexação consiste basicamente em: recuperar e analisar
o conteúdo textual do documento; eliminação de stopwords; redução de termos a um
radical comum; contagem de termos e cálculo de freqüência dos mesmos em
relação ao documento de origem.
A análise do conteúdo textual é necessária devido a natureza
heterogênea dos espaços de busca. O sistema determina o tipo de documento
recuperado (HTML, PDF, TXT, DOC), acionando o módulo correspondente para a
extração dos termos, e recupera apenas termos que caracterizem a informação
contida neste, evitando que metadados, como tags HTML, sejam recuperados.
O Fidus mantém uma lista de stowords, palavras de baixa representação
contextual como conjunções, artigos e preposições, que são eliminadas no processo
de indexação do documento. Subsequentemente, os termos restantes são reduzidos
a um radical mínimo pelo processo de stemming, descrito na Seção 1.1.2 do
Capítulo 2.
A última etapa do processo de indexação consiste na contagem de
termos do documento e o cálculo da freqüência de cada termo. Duas freqüências
são calculadas, a normal e a normalizada.
A freqüência normal é igual a quantidade de ocorrências de um termo em
seu documento de origem. A freqüência normalizada de cada termo é obtida através
30
da divisão de sua freqüência normal pela maior freqüência normal encontrada em
um documento. Dessa forma evita-se que termos muito freqüentes produzam
anomalias nos cálculos de peso e similaridade.
2.1.3. Cálculo de pesos
O cálculo de pesos dos termos recuperados é realizado através do
algoritmo TF-SENO. Este algoritmo empírico foi desenvolvido com o intuito de
solucionar um problema encontrado ao se utilizar o algoritmo TF-IDF para a
quantificação de pesos.
Segundo Gomes (2001), o TF-IDF tende a atribuir pesos nulos a termos
muito freqüentes nos documentos indexados, porém, termos freqüentes podem
indicar um interesse regular por um campo de pesquisa. Assim o TF-IDF torna-se
inadequado para calcular pesos em sistema de informação para usuários de buscas
regulares. Desta forma, a “... adequação do peso do termo a seu poder de
seletividade requer que o cálculo do peso seja feito tornando-o diretamente
proporcional à freqüência do termo” (GOMES 2001), requisito que o TF-SENO é
capaz de atender.
O algoritmo TF-SENO é definido pela seguinte fórmula:
Peso = TF normalizado * Sin(ângulo) *
Relevância
ângulo = 90 * (DF / N)
Onde:
•
TF normalizado é a freqüência do termo em um documento dividida
pelo valor máximo de freqüência encontrada no mesmo.
•
DF é o número de documentos relevantes em que o termo foi
encontrado.
•
N representa o total de documentos, relevantes e irrelevantes,
indexados pelo sistema.
31
•
Relevância é o valor da relevância efetiva atribuída pelo usuário.
O peso calculado utilizando-se o TF-SENO deve sofrer uma correção a
cada iteração de busca. Isto se deve ao fato que, a cada novo documento analisado,
podem surgir termos altamente representativos, isto é, com alta freqüência no
conjunto de documentos, e assim é necessário que este termo tenha seu peso
atualizado para que possa fazer parte dos critérios de busca.
A correção de pesos também é utilizada para reduzir gradativamente o
peso de termos que não ocorram freqüentemente na coleção de documentos
avaliados. Desta forma, os termos pouco representativos têm seus pesos ajustados
para que não afetem os cálculos de similaridade efetuados posteriormente,
produzindo avaliações erradas.
Em seu trabalho, Gomes (2001) desenvolveu uma fórmula para corrigir o
peso de um termo calculado em iterações anteriores baseado em sua freqüência no
conjunto total de documentos avaliados. Esta correção é aplicada após o usuário
julgar um documento avaliado potencialmente pelo Fidus.
1. TF Normalizado Corrente = TF / frequenciaMaxima;
2. Se (DF > 1) O termo já possui freqüência anterior.
3. TF Normalizado = ((TF Normalizado * (DF -1)) +
TF Normalizado Corrente) / DF;
Senão
5. TF Normalizado = TF Normalizado Corrente;
Na linha 1 (hum), o valor da freqüência de um termo no documento que
foi avaliado é divida pela maior freqüência de termo encontrada no documento. A
linha 2 (dois) verifica se o termo consta em algum documento pertencente à coleção
de documentos avaliados, isto é, se já possui algum valor de peso associado. Caso
positivo, na linha 3 (três), o valor da freqüência normalizada do termo (TF
Normalizado) passa a ser calculada em relação à coleção de documentos. Esta
freqüência é subtraída em relação a DF (TF Normalizado * (DF - 1)) para ajustar seu
valor histórico.
32
2.1.4. Análise de similaridade
O Fidus pode determinar a relevância potencial de um documento através
da comparação entre vetores termo peso do documento e da categoria de
informação a qual uma informação está sendo procurada. Este modelo de
classificação foi desenvolvido por Gomes (2001) e denominado modelo matemático.
Os vetores são compostos pelos 20 (vinte) primeiros termos de maior
peso identificado no documento e na categoria de informação. O cálculo da
similaridade é realizado comparando-se quantos dos 20 termos mais relevantes do
documento correspondem aos 20 termos que melhor representam a categoria de
informação que se deseja obter informação.
A quantidade de termos a serem utilizados para a comparação foi definido
empiricamente através de testes realizados por Gomes (2001) durante a
implementação do sistema.
33
3. Implementação e teste do modelo vetorial no Fidus
Este capítulo descreve a implementação de algoritmo baseado no modelo
vetorial, descrito na seção 1.2.2, no Fidus e a metodologia de testes utilizada para
verificar a sua precisão em relação ao modelo existente.
3.1. Implementação
Esta seção descreve detalhadamente a implementação do algoritmo de
análise de similaridade baseado no modelo vetorial.
3.1.1. Ambiente
O ambiente utilizado para a implementação do modelo vetorial e para
testes é composto por um computador dotado de um processador Intel Pentium 4
HT 3.2 GHz, 512MB de memória RAM. A IDE (Integrated Development Environment
- Ambiente Integrado de Desenvolvimento) utilizada para a implementação do
modelo vetorial foi o Eclipse 3.2 devido a sua estabilidade e facilidade de utilização.
3.1.2. Diagrama de classe
A Figura 4 apresenta o diagrama de classes do módulo de análise de
similaridade do Fidus.
Figura 5 - Diagrama de classes do módulo de análise de similaridade
A interface EstrategiaDeAnaliseIf define a operação que um algoritmo de
análise de similaridade deve possuir. O método definido nesta interface é o
34
calcularSimilaridade que recebe como parâmetro uma categoria de informação e o
documento que será analisado.
O modelo matemático para o cálculo de similaridade entre os vetores,
utilizado
atualmente
no
Fidus,
está
implementado
através
da
classe
EstrategiaDeAnaliseMatematica. A implementação do método calcularSimilaridade é
responsável por executar a comparação entre os vetores descrita na seção 2.1.4 do
capítulo 2.
A classe desenvolvida neste trabalho que implementa o modelo vetorial é
a
EstrategiaDeAnaliseEspacoVetorial.
Esta
classe
realiza
a
interface
EstrategiaDeAnaliseIf implementando o método calcularSimilaridade. Este método é
responsável pelo cálculo da proximidade entre vetores no espaço vetorial, através
da fórmula descrita na seção 1.2.2 do capítulo 2.
3.1.3. Representação da informação
Para representar um documento como um vetor de termo peso, foi
utilizada uma coleção composta por objetos do tipo CriterioBusca. A escolha por
este tipo de objeto se deu devido a sua composição, que é formada por uma
referência a um termo, seu peso em relação ao documento ou a categoria de
informação e seu peso normalizado. Estas informações são essenciais para os
cálculos de similaridade e como já se encontravam encapsuladas em um objeto,
facilitando sua manipulação, foram utilizadas na representação dos vetores.
A Listagem 1 demonstra a criação do vetor termo peso dos documentos
recuperados que serão analisados.
35
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
Collection termosFrequentes =
dao.recuperarTermosFrequentesDocumento(documento);
if (termosFrequentes != null) {
Iterator it = termosFrequentes.iterator();
while ( it.hasNext() && contador < 20) {
DocumentoTermo ft = (DocumentoTermo) it.next();
CriterioBusca termoPeso = new CriterioBusca();
DF = getTotalDocumentosAvaliadosComTermo(
ft.getTermoOID(), categoria);
N = getTotalDocumentosAvaliadosDaCategoria(
categoria);
11.
12.
13.
double peso = calcularTfSeno(N, DF,
ft.getFrequenciaNormalizada());
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
termoPeso.setTermoOID( ft.getTermoOID() );
termoPeso.setPeso(peso);
if(peso > maiorPeso){
maiorPeso = peso;
}
contador++;
}
}
vetorTermoPesoDocumento.put( termoPeso.getTermoOID(),
termoPeso );
Listagem 1 - Criação do vetor de termos
Na linha 1 (hum) é recuperado o conjunto de termos mais freqüentes,
ordenados decrescentemente, encontrados no documento analisado. Estes termos
tiveram sua freqüência calculada durante a indexação do documento. Na linha 6
(seis), apenas os 20 (vinte) termos mais freqüentes são utilizados para o cálculo de
peso, seguindo a orientação do modelo matemático descrito na seção 2.1.4.
Para cada termo freqüente, são recuperados os valores de DF, linha 10
(dez), e os valores de N, linha 11 (onze). Estes valores são necessários para o
cálculo do peso através do algoritmo TF-SENO, que é realizado através do método
calcularTfSeno, observado na linha 13 (treze).
De posse do peso do termo no documento é possível, enfim, criar o
elemento que irá compor o vetor termo peso do documento. O objeto termoPeso,
instância da classe CriterioBusca, é instanciado na linha 8 (oito) e tem os atributos
termoOID e peso preenchidos com os valores do termo e peso corrente na iteração
36
nas linhas 15 (quinze) e 16 (dezesseis). Por fim, o objeto termoPeso é armazenado
no vetor vetorTermoPesoDocumento.
3.1.4. Implementação do cálculo de similaridade
A Listagem 2 apresenta o trecho de código responsável pelo cálculo do
co-seno que representa a distância entre dois vetores no espaço vetorial.
1.
2.
3.
4.
this.ajustarTamanhoVetores();
//etapa 1
for (Iterator iter = vetorTermosDocumento.values().iterator();
iter.hasNext();) {
CriterioBusca termoPeso = (CriterioBusca) iter.next();
5.
6.
7.
double segundoPeso = ((CriterioBusca)
vetorTermosCategoria.get(
termoPeso.getTermoOID() )).getPesoNormalizado();
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
etapa1 += ( Math.pow( termoPeso.getPesoNormalizado() , 2) *
Math.pow( segundoPeso , 2));
}
//etapa2
for (Iterator iter = vetorTermosDocumento.values().iterator();
iter.hasNext();) {
CriterioBusca termoPeso = (CriterioBusca) iter.next();
etapa2 += Math.pow( termoPeso.getPesoNormalizado() , 2);
}
//etapa3
for (Iterator iter = vetorTermosCategoria.values().iterator();
iter.hasNext();) {
CriterioBusca termoPeso = (CriterioBusca) iter.next();
}
etapa3 += Math.pow( termoPeso.getPesoNormalizado() , 2);
produtoRaizPesos = ( Math.sqrt( etapa2 ) * Math.sqrt( etapa3 ) );
if(etapa3 != 0 && produtoRaizPesos != 0){
resultado = etapa1 / produtoRaizPesos;
}
return resultado;
Listagem 2 - Cálculo de similaridade através co-seno do angulo entre os vetores.
Antes de calcular a similaridade entre os vetores é necessário que eles
possuam o mesmo número de elementos, mantendo-os com mesma dimensão e
mesma ordem. Ressalta-se que apenas termos que estejam armazenados nos dois
37
vetores, do documento e da categoria de informação, interferem no cálculo da
similaridade
(MENOTI
2004).
Desta
forma,
termos
que
não
possuam
correspondência nos dois vetores devem ter seu peso definido com o valor nulo.
O método ajustarTamanhoVetores, na linha 1 (hum) identifica os
elementos que não estão contidos na interseção entro os dois vetores e os incluem
no vetor necessário. Os elementos incluídos são instâncias da classe CriterioBusca
contendo a referência do termo e o peso normalizado com o valor nulo, para que
não interfira no cálculo de similaridade.
Para aumentar a legibilidade do código, o cálculo de similaridade foi
dividido em 3 (três) etapas. A primeira etapa, que se inicia na linha 4 (quatro), referese ao somatório dos pesos normalizados ao quadrado do vetor termo peso do
documento multiplicados com os pesos normalizados ao quadrado do vetor termo
peso da categoria de informação, como pode ser observado na linha 9 (nove).
Na linha 13 (treze) começa a segunda etapa do cálculo que representa a
raiz quadrada do somatório dos pesos normalizados ao quadrado do vetor termo
peso do documento, calculado na linha 16 (dezesseis).
A partir da linha 19 (dezenove) tem início a terceira etapa, que representa
a raiz quadrada do somatório dos pesos normalizados ao quadrado do vetor termo
peso da categoria de informação. O trecho final do algoritmo, na linha 28 (vinte e
oito), apresenta a divisão do resultado da primeira etapa com a multiplicação das
raízes quadradas obtidas.
3.2. Teste
A etapa de teste tem o objetivo de validar a solução de análise de
similaridade proposta neste trabalho. A precisão do modelo vetorial deve ser
verificada e comparada com o modelo matemático que é utilizado atualmente no
Fidus.
Esta seção descreve detalhadamente a metodologia dos testes aplicados
na comparação entre a precisão do modelo vetorial e o modelo matemático e os
resultados obtidos.
38
3.2.1. Metodologia
A validação do algoritmo que implementa o modelo vetorial se dará nos
seguintes passos:
•
Seleção de uma categoria de informação;
•
Criação de um conjunto de 100 (cem) documentos (corpus);
•
Determinar a relevância efetiva de cada documento do conjunto;
•
Criação de um perfil de usuário;
•
Cadastrar uma categoria de informação sobre o contexto
selecionado no Fidus;
•
Apresentar grupos de 10 (dez) documentos para análise de
similaridade em 10 iterações;
•
Avaliar os resultados obtidos a cada iteração, comparando entre os
modelos.
Será criado um perfil de usuário cujo interesse de pesquisa estará
direcionado para a área de recuperação de informação, o contexto de informação
que servirá de base para a busca. Este perfil deverá possuir uma categoria de
informação associada, denominada recuperação de informação, que conterá 10
(dez) termos considerados como semanticamente representativos para esta
categoria. Estes termos serão selecionados através de pesquisas nas seguintes
referências (RIBEIRO-NETO; BAEZA-YATES, 1999; MANNING 2007).
O teste se dará como uma simulação de busca em um repositório de
documentos locais. Para isso será necessária a construção de um corpus controlado
de documentos para que seja possível avaliar o algoritmo utilizando a métrica de
avaliação precisão (precision) citada na seção 1.3 do capítulo 2.
O corpus criado será composto por um total de 100 (cem) documentos
HTML, dos quais 20 (vinte) serão de documentos considerados como relevantes
para a categoria de informação e 80 (oitenta) como irrelevantes.
Os documentos poderão variar na quantidade de termos que farão parte
dos mesmos, além da variação no número de ocorrências para cada termo. A
variação de ocorrência tem o objetivo de simular uma tendência do documento a
39
conter informação relevante para determinados termos do contexto de busca. Os
documentos relevantes serão compostos por termos que podem estar presentes nas
palavras-chave definidas para a categoria de informação. Existem também termos
relevantes não explicitados inicialmente, para que o Fidus seja capaz de detectá-los
e utilizá-los em avaliações posteriores. Estes termos ampliarão a representação do
contexto de busca, melhorando a sua eficiência em iterações futuras.
Para avaliar a precisão de cada algoritmo serão realizadas 10 iterações. A
cada interação serão apresentados 10 (dez) documentos sendo que 2 (dois) dois
deles classificados efetivamente como relevantes para o contexto de pesquisa e 8
(oito) classificados como irrelevantes.
Os
resultados
calculados
pelos
algoritmos
que
implementam
respectivamente o modelo vetorial e o modelo matemático serão comparados ao
término de cada iteração realizada.
Será considerado neste trabalho que um documento potencialmente
relevante deverá apresentar um valor de relevância maior ou igual a 40%. Valores
abaixo de 40% representam documentos irrelevantes.
Ao final das 10 interações do teste, os resultados de retorno indicarão
qual dos dois modelos é o mais preciso.
3.2.2. Primeira iteração
Na primeira iteração de teste, os termos utilizados para a análise de
similaridade foram os mesmos considerados como palavras-chave. Eles são
apresentados a seguir:
"recuperação", "informação", "modelo", "vetorial", "vetor",
"termo", "peso", "relevância", "palavra", "chave"
Estes termos poderiam ser utilizados também para a busca em
repositórios externos, ou como critérios de busca em sistemas de busca. Esta
funcionalidade não será avaliada neste trabalho, desta forma considerou-se que os
documentos apresentados a cada iteração sofreram um processo de busca
anteriormente.
40
Nesta iteração, os documentos considerados, pelo usuário, como
relevantes foram os documentos 0000.htm e 0003.htm. Estes documentos possuíam
os seguintes termos:
•
Documento 0000.htm
"recuperação", "informação", “dados”, “web”, “semântica”
“peso”, “termo”, “seleção”, “índice”, “chave”
Os termos “recuperação”, “informação”, “peso”, “termo” possuem um
valor de freqüência de 30 ocorrências. Os demais termos ocorrem 10 vezes no
documento.
•
Documento 0003.htm
“termo”, “palavra”, “chave”, “dados”, “índice”,
“indexação”, “stopword”, “stemming”, “recuperação”,
“informação”
Os termos “termo”, “indexação”, “stopword”, “stemming” possuem
um valor de freqüência de 30 ocorrências. Os demais termos ocorrem 10 vezes no
documento.
Após a execução de busca dos documentos, o Fidus apresentou o
resultado que consta na Tabela 1.
Tabela 1 - Resultado da primeira iteração
Rel.
Matemática %
Rel.
Vetorial %
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
Rel.
Efetiva % Documento
100
0000.htm
0
0001.htm
0
0002.htm
100
0003.htm
0
0004.htm
0
0005.htm
0
0006.htm
0
0007.htm
0
0008.htm
0
0009.htm
41
A primeira coluna, Rel. Matemática, indica a relevância potencial
calculada através do algoritmo baseado no modelo matemático, descrito na seção
2.1.4 do capítulo 2.
A segunda coluna, Rel. Vetorial, armazena os resultados da relevância
potencial calculada através do algoritmo baseado no modelo vetorial descrito na
seção 1.2.2 do capítulo 1.
A terceira coluna exibe os resultados da relevância efetiva apontada pelo
o usuário para cada documento. A última coluna apresenta o nome de cada
documento avaliado.
Os resultados apresentados na tabela indicam que nenhum dos
algoritmos foi capaz de determinar quais dos documentos apresentados eram
relevantes. Isto se justifica pelo fato de que o cálculo de pesos necessário para a
criação do vetor termo peso para o documento e a categoria de informação não
pôde ser realizado. O cálculo de pesos depende da quantidade de documentos
previamente avaliados e, neste caso, não havia documentos que já avaliados na
base de dados.
Mesmo considerando este fator, a avaliação de precisão na primeira
iteração pode ser analisada na Tabela 2.
Tabela 2 - Avaliação da primeira iteração
Algoritmo de
Avaliação
Matemático
Vetorial
Precisão
%
0
0
3.2.3. Segunda Iteração
Na segunda iteração, como já houve uma avaliação de documentos, o
Fidus, a partir dos novos termos capturados nos documentos avaliados, acrescenta
ao vetor da categoria de informação os termos mais relevantes identificados.
A partir desta iteração é possível observar os vetores peso termo
montados para o cálculo de similaridade pelo sistema. Serão exibidos neste trabalho
apenas os vetores que correspondem à categoria de informação pesquisada
montados pelo Fidus a cada iteração.
42
Nesta iteração, os documentos considerados como relevantes são,
respectivamente, os documentos 0013.htm e 0017.htm. Estes documentos possuem
os seguintes termos:
•
Documento 0013.htm
“data”, “termo”, “relevância”, “potencial”, “vetor”,
“modelo”, “vetorial”, “similaridade”, “indexação”,
“documento”
Os termos “modelo”, “vetorial”, “relevância” e “similaridade”
possuem um valor de freqüência de 30 ocorrências. Os demais termos ocorrem 10
vezes no documento.
•
Documento 0017.htm
“modelo”, “clássico”, “vetorial”, “booleano”,
“probabilístico”, “similaridade”, “recuperação”,
“informação”, “termo”, “peso”
Os termos “booleano”, “probabilístico”, “informação” e “peso”
possuem um valor de freqüência de 30 ocorrências. Os demais termos ocorrem 10
vezes no documento.
O vetor termo peso que representa a categoria de informação é composto
pelos seguintes termos e seus respectivos pesos normalizados:
“stemming” (1.0), “index” (1.0), “stopword” (1.0), “pes”
(1.0), “term” (1.0), “inform” (1.0), “recuper” (1.0), “palavr”
(0.33), “indic” (0.33), “dad” (0.33), “selec” (0.33), “seman”
(0.33), “chav” (0.33)
Os termos que apresentam um maior valor de peso normalizado são
aqueles que possuem mais ocorrências no conjunto de documentos. Os termos de
valor mais baixo são aqueles que não constavam na primeira iteração, obtidos dos
documentos avaliados, ou que sofreram uma correção de peso em função de sua
baixa representatividade no contexto de pesquisa, isto é, não ocorreram em muitos
documentos relevantes.
43
Após a execução de busca dos documentos, o Fidus apresentou o
resultado que consta na Tabela 3:
Tabela 3 - Resultados da segunda iteração
Rel.
Matemática %
7
15
7
15
0
0
0
30
0
7
Rel.
Rel.
Vetorial % Efetiva % Documento
36
0
0010.htm
4
0
0011.htm
4
0
0012.htm
44
100
0013.htm
0
0
0014.htm
0
0
0015.htm
0
0
0016.htm
47
100
0017.htm
0
0
0018.htm
36
0
0019.htm
Nesta iteração já é possível visualizar os resultados dos cálculos
efetuados pelos algoritmos de similaridade.
O algoritmo vetorial foi capaz de identificar os dois documentos
relevantes, sendo que sua avaliação foi mais precisa com o documento 0017.htm,
apresentando 47% de relevância potencial para este documento. Em relação ao
documento 0013.htm, sua precisão foi reduzida, avaliando o documento com
relevância potencial de 44%.
A alta relevância potencial atribuída (36%) aos documentos irrelevantes
0010.htm e 0019.htm, como pode ser observado na Tabela 3, justifica-se pela
presença do termo “inform” no conteúdo dos mesmos. Este termo pertence ao
vetor da categoria de informação e possui um peso que representa a máxima
relevância (1,0) no contexto de busca como também no documento, cujo o peso
atribuído também foi elevado.
O cálculo de similaridade através do modelo matemático não obteve êxito
em recuperar os documentos efetivamente relevantes. As suas avaliações
produziram resultados abaixo de 40%, o que significa que os documentos foram
considerados como irrelevantes. Os documentos 0013.htm e 0017.htm foram
classificados com relevância de 15% e 30% respectivamente.
44
A comparação dos resultados obtidos entre os dois algoritmos para cada
documento relevante resulta no Gráfico 1.
Gráfico 1 - Comparação de relevância potencial entre os algoritmos
100
80
60
Algoritmo
Matemático
40
Algoritmo
Vetorial
20
0
Documento
0013.htm
Documento
0017.htm
A Tabela 4 apresenta os resultados da avaliação dos algoritmos na
segunda iteração.
Tabela 4 - Avaliação da segunda iteração
Algoritmo de
Avaliação
Matemático
Vetorial
Precisão
%
0
100
Os resultados indicam que o algoritmo matemático foi menos preciso que
o vetorial, não conseguindo recuperar os documentos relevantes. O algoritmo
vetorial foi capaz de obter todos os documentos efetivamente relevantes e assim
obteve 100% de precisão na segunda iteração.
3.2.4. Terceira iteração
Nesta iteração, os documentos considerados como relevantes são,
respectivamente, os documentos 0022.htm e 0029.htm. Estes documentos possuem
os seguintes termos:
•
Documento 0022.htm
“precisão”, “abrangência”, “termo”, “palavra”, “chave”,
“if”, “informação”, “stemming”, “stopword”, “índice”
45
Os termos “precisão”, “abrangência”, “if” e “stemming” possuem um
valor de freqüência de 30 ocorrências. Os demais termos ocorrem 10 vezes no
documento.
•
Documento 0029.htm
“recall”, “precison”, “avaliação”, “recuperação”,
“informação”, “precisão”, “abrangência”, “termo”,
“stopword”, “índice”
Os termos “recall”, “precison”, “índice” e “termo” possuem um valor
de freqüência de 30 ocorrências. Os demais termos ocorrem 10 vezes no
documento.
Nesta iteração, o Fidus criou o vetor termo peso, que representa a
categoria de informação, com seguintes termos e seus respectivos pesos
normalizados:
“term” (1.0), “inform” (0.93), “recuper” (0.45), “dad” (0.42),
“pes” (0.39), “index” (0.34), “chav” (0.25), “indic” (0.25),
“similar” (0.13), “vetor” (0.13), “model” (0.13), “palavr” (0),
“selec” (0), “seman” (0), “stemming” (0), “probalis” (0),
“relev” (0), “dat” (0), “potenc” (0) , “vet” (0)
Após a execução de busca dos documentos, o Fidus apresentou o
resultado que consta na Tabela 5.
Tabela 5 – Resultados da terceira iteração
Rel.
Matemática %
Rel.
Vetorial %
0
0
30
0
0
0
0
0
0
25
Rel.
Efetiva %
0
0
45
0
0
0
0
0
0
52
0
0
100
0
0
0
0
0
0
100
Documento
0020.htm
0021.htm
0022.htm
0023.htm
0024.htm
0025.htm
0026.htm
0027.htm
0028.htm
0029.htm
46
O algoritmo vetorial foi capaz de identificar os dois documentos
relevantes, sendo que sua avaliação foi mais precisa para o documento 0029.htm,
apresentando 52% de relevância potencial para este documento. Em relação ao
documento 0022.htm, sua relevância potencial foi avaliada em 45%.
O cálculo de similaridade através do modelo matemático não obteve êxito
em recuperar os documentos efetivamente relevantes. As suas avaliações
produziram resultados abaixo de 40%, o que significa que os documentos foram
considerados como irrelevantes. O documento 0022.htm foi classificado com
relevância potencial de 30% enquanto que o documento 0029.htm obteve 25% de
relevância calculada.
A comparação dos resultados obtidos entre os dois algoritmos para cada
documento relevante pode ser observada no Gráfico 2.
Gráfico 2 - Comparação de relevância potencial entre os algoritmos
100
80
60
Algoritmo
Matemático
40
Algoritmo
Vetorial
20
0
Documento
0022.htm
Documento
0029.htm
A Tabela 6 apresenta os resultados da avaliação dos algoritmos na
terceira iteração.
Tabela 6 - Avaliação da terceira iteração
Algoritmo de
Avaliação
Matemático
Vetorial
Precisão
%
0
100
47
3.2.5. Quarta iteração
Para a quarta iteração, os documentos considerados como relevantes
são, respectivamente, os documentos 0030.htm e 0038.htm. Estes documentos
possuem os seguintes termos:
•
Documento 0030.htm
“if”, “df”, “tf”, “seno”, “peso”, “normalizado”, “freqüência”,
“documento”, “termo”, “relevância”
Os termos “freqüência”, “termo”, “tf” e “relevância” possuem um valor
de freqüência de 30 ocorrências. Os demais termos ocorrem 10 vezes no
documento.
•
Documento 0038.htm
“data”, “information”, “retrieval”, “ir”, “recall”, “precision”,
“relevance”, “term”, “corpus”, “TREC”
Os termos “relevance”, “term”, “ir” e “TREC” possuem um valor de
freqüência de 30 ocorrências. Os demais termos ocorrem 10 vezes no documento.
Nesta iteração, o Fidus criou o vetor termo peso, que representa a
categoria de informação, com seguintes termos e seus respectivos pesos
normalizados:
“term” (1.0), “inform” (0.98), “indic” (0.47), “recuper” (0.39),
“chav” (0.25), “pes” (0.24), “stopword” (0.22), “stemming”
(0.20), “dad” (0.17), “model” (0.17), “vetor” (0.14), “index”
(0.14), “similar” (0.14), “palavr” (0.10), “abrang” (0.08),
“precis” (0.08), “seman” (0), “selec” (0), “dat” (0), “recall”
(0)
Após a execução de busca dos documentos, o Fidus apresentou o
resultado que consta na Tabela 7.
48
Tabela 7 - Resultado da quarta iteração
Rel.
Matemática %
Rel.
Vetorial %
15
0
0
0
0
0
0
0
10
0
Rel.
Efetiva %
58
0
0
0
0
0
0
0
60
0
100
0
0
0
0
0
0
0
100
0
Documento
0030.htm
0031.htm
0032.htm
0033.htm
0034.htm
0035.htm
0036.htm
0037.htm
0038.htm
0039.htm
Durante a quarta iteração, o algoritmo vetorial obteve uma precisão
superior ao algoritmo matemático. Foram recuperados todos os documentos
relevantes, sendo que estes foram classificados com o valor de relevância potencial
de 58% para o documento 0030.htm e 60% para o documento 0038.htm.
O cálculo de similaridade através do modelo matemático não obteve êxito
em recuperar os documentos efetivamente relevantes. As suas avaliações
produziram resultados abaixo de 40%, o que significa que os documentos foram
considerados como irrelevantes. O documento 0030.htm foi classificado com
relevância potencial de 15% enquanto que o documento 0038.htm obteve 10% de
relevância.
A comparação dos resultados obtidos entre os dois algoritmos para cada
documento relevante pode ser observada no Gráfico 3.
Gráfico 3 - Comparação de relevância potencial entre os algoritmos
100
80
60
Algoritmo
Matemático
40
Algoritmo
Vetorial
20
0
Documento
0030.htm
Documento
0038.htm
49
A Tabela 8 apresenta os resultados da avaliação dos algoritmos na quarta
iteração.
Tabela 8 - Avaliação da quarta iteração
Algoritmo de
Avaliação
Matemático
Vetorial
Precisão
%
0
100
3.2.6. Quinta iteração
Para a quarta iteração, os documentos considerados como relevantes
são, respectivamente, os documentos 0045.htm e 0048.htm. Estes documentos
possuem os seguintes termos:
•
Documento 0045.htm
“recuperação”, “informação”, “modelo”, “vetorial”, “vetor”,
“termo”, “peso”, “relevância”, “palavra”, “chave”
Os
termos
“recuperação”,
“informação”,
“modelo”,
“vetorial”,
possuem um valor de freqüência de 30 ocorrências. Os demais termos ocorrem 10
vezes no documento.
•
Documento 0048.htm
“vector”, “boolean”, “bayes”, “bayesian”, “information”,
“retrieval”, “model”, “classic”, “ranking”, “weight”
Os termos “information”, “retrieval”, “bayesian”, “vector”, possuem
um valor de freqüência de 30 ocorrências. Os demais termos ocorrem 10 vezes no
documento.
Nesta iteração, o Fidus criou o vetor termo peso, que representa a
categoria de informação, com seguintes termos e seus respectivos pesos
normalizados:
50
"term" (1.0), "inform" (0.62), "indic" (0.29), "recuper" (0.25),
"pes" (0.24), "stopword" (0.15), "chav" (0.12),
"relev" (0.09), "stemming" (0.09), "precis" (0.08),
"document" (0.08), "model" (0.08), "dad" (0.08), "vetor"
(0.06), "similar" (0.06), "index" (0.06), "abrang" (0.06),
"palavr" (0.05), "dat" (0.04), "recall" (0.04)
Após a execução de busca dos documentos, o Fidus apresentou o
resultado que consta na Tabela 9.
Tabela 9 - Resultado da quinta iteração
Rel.
Matemática %
Rel.
Vetorial %
0
0
0
0
0
45
0
5
5
5
Rel.
Efetiva %
0
0
0
0
0
29
0
0
0
0
0
0
0
0
0
100
0
0
100
0
Documento
0040.htm
0041.htm
0042.htm
0043.htm
0044.htm
0045.htm
0046.htm
0047.htm
0048.htm
0049.htm
O algoritmo vetorial não foi capaz de recuperar os documentos relevantes
durante a quinta iteração. O documento 0045.htm obteve o valor de relevância
potencial de 29%. Para o documento 0048.htm, a relevância calculada foi de 0%.
Apesar do documento 0045.htm possuir três dos termos de maior peso no
vetor da categoria de informação (“term”, “recuper” e “inform”), sua relevância
potencial foi consideravelmente baixa. Isto se deve a baixa freqüência do termo
“term” no documento, o que influenciou no cálculo do algoritmo vetorial. Em relação
à avaliação nula para o documento 0048.htm, o único termo do documento que
possuía correspondência no vetor da categoria de informação, “model”, foi
classificado com um peso baixo.
O modelo matemático conseguiu recuperar apenas um documento
efetivamente relevante. O documento 0045.htm foi classificado com relevância
potencial de 45%, superando a avaliação do modelo vetorial, enquanto que o
documento 0048.htm obteve 5% de relevância.
51
Como não sofre influência direta da freqüência dos termos no documento,
o algoritmo matemático pôde se aproveitar da elevada quantidade de termos
relevantes da categoria de informação presentes no documento 0045.htm,
classificando-o como relevante. O documento 0048.htm recebeu 5% de relevância
pela presença de um termo relevante, o “model”.
A comparação dos resultados obtidos entre os dois algoritmos para cada
documento relevante pode ser observada no Gráfico 4.
Gráfico 4 - Comparação de relevância potencial entre os algoritmos
100
80
60
Algoritmo
Matemático
40
Algoritmo
Vetorial
20
0
Documento
0045.htm
Documento
0048.htm
A Tabela 10 apresenta os resultados da avaliação dos algoritmos da
quinta iteração.
Tabela 10 - Avaliação da quinta iteração
Algoritmo de
Avaliação
Matemático
Vetorial
Precisão
%
50
0
3.2.7. Sexta iteração
Na sexta iteração, os documentos considerados como relevantes são,
respectivamente, os documentos 0050.htm e 0059.htm. Estes documentos possuem
os seguintes termos:
•
Documento 0050.htm
52
“model”, “probalistic”, “vector”, “boolean”, “bayes”,
“bayesian”, “neural”, “network”, “key”, “word”
Os termos “probalistic”, “vector”, “boolean”, e “bayes”, possuem um
valor de freqüência de 30 ocorrências. Os demais termos ocorrem 10 vezes no
documento.
•
Documento 0059.htm
“termo”, “chave”, “informação”, “dado”, “radical”, “full”,
“text”, “índices”, “expansão”, “query”
Os termos “índices”, “text”, “dado” e “radical”, possuem um valor de
freqüência de 30 ocorrências. Os demais termos ocorrem 10 vezes no documento.
Nesta iteração, o Fidus criou o vetor termo peso, que representa a
categoria de informação, com seguintes termos e seus respectivos pesos
normalizados:
"term" (1.0), "inform" (0.64), "recuper" (0.33), "pes" (0.26),
"indic" (0.20), "model" (0.19), "chav" (0.14),
"vetor" (0.14), "relev" (0.14), "stopword" (0.1), "retriev"
(0.09), "information" (0.09), "palavr" (0.08),
"stemming" (0.06), "precis" (0.05), "dad" (0.05),
"document" (0.05), "dat" (0.04), "recall" (0.04),
"index" (0.04)
Após a execução de busca dos documentos, o Fidus apresentou o
resultado que consta na Tabela 11.
53
Tabela 11 - Resultado da sexta iteração
Rel.
Matemática %
Rel.
Vetorial %
5
10
5
0
0
0
0
0
0
25
Rel.
Efetiva %
1
28
2
0
0
0
0
0
0
24
100
0
0
0
0
0
0
0
0
100
Documento
0050.htm
0051.htm
0052.htm
0053.htm
0054.htm
0055.htm
0056.htm
0057.htm
0058.htm
0059.htm
Nenhum dos algoritmos obteve êxito em recuperar os documentos
relevantes durante a sexta iteração.
O algoritmo vetorial atribuiu ao documento 0050.htm o valor de relevância
potencial de 1%. Para o documento 0059.htm, a relevância calculada foi de 24%.
A baixa classificação do documento 0050.htm é explicada pelo fato da
presença de apenas um termo relevante conhecido (“model”) no documento, como
se pode observar no vetor da categoria de informação. A mesma situação ocorrera
durante a quinta iteração com o documento 0048.htm, porém, a diferença é que na
sexta iteração, o termo “model” recebeu um peso maior (0,19 contra 0,08 na quinta
iteração) o que proporcionou uma melhoria da avaliação a partir do algoritmo vetorial
para o documento 0050.htm.
A relevância atribuída ao documento irrelevante 0051.htm de 28%, apesar
do mesmo conter apenas 2 (dois) termos que pertenciam ao vetor de termos
(“inform” e “dad”), foi maior que no documento 0059.htm, cuja composição incluía 5
(cinco) termos contidos no vetor da categoria de informação (“term”, “chav”,
“inform”, “dad” e “indic”). A explicação para este fato está na valoração dos pesos
dos termos no documento, pois no caso do documento 0051.htm o termo “inform”
possui um alto valor de peso atribuído, o que não ocorre no documento 0059.htm,
onde o mesmo termo possui um baixo valor associado. Assim é possível observar a
influência do peso do termo no documento como um fator relevante para o cálculo
de similaridade através do algoritmo vetorial.
54
O modelo matemático também não conseguiu recuperar os documentos
efetivamente relevantes. O documento 0050.htm foi classificado com relevância
potencial de 5%, enquanto que o documento 0059.htm obteve 25% de relevância,
valor muito próximo ao obtido pelo algoritmo vetorial.
A comparação dos resultados obtidos entre os dois algoritmos para cada
documento relevante pode ser observada no Gráfico 5.
Gráfico 5 - Comparação de relevância potencial entre os algoritmos
100
80
60
Algoritmo
Matemático
40
Algoritmo
Vetorial
20
0
Documento
0050.htm
Documento
0059.htm
A Tabela 12 apresenta os resultados da avaliação dos algoritmos na
sexta iteração.
Tabela 12 - Avaliação da sexta iteração
Algoritmo de
Avaliação
Matemático
Vetorial
Precisão
%
0
0
3.2.8. Sétima iteração
Para a sétima iteração, os documentos considerados como relevantes
foram, respectivamente, os documentos 0064.htm e 0068.htm. Estes documentos
possuem os seguintes termos:
•
Documento 0064.htm
“Salton”, “Baeza”, “Yates”, “Ribeiro”, “Neto”, “Rijsbergen”,
“Manning”, “autor”, “recuperação”, “informação”
55
Os termos “Baeza”, “Salton”, “recuperação”, e “informação”,
possuem um valor de freqüência de 30 ocorrências. Os demais termos ocorrem 10
vezes no documento.
•
Documento 0068.htm
“SMART”, “modelo”, “vetorial”, “co-seno”, “espaço”,
“peso”, “termo”, “vetor”, “similaridade”, “Salton”
Os termos “SMART”, “Salton”, “vetor” e “co-seno”, possuem um valor
de freqüência de 30 ocorrências. Os demais termos ocorrem 10 vezes no
documento.
Nesta iteração, o Fidus criou o vetor termo peso, que representa a
categoria de informação, com seguintes termos e seus respectivos pesos
normalizados:
"term" (1.0), "inform" (0.62), "model" (0.35), "recuper" (0.29),
"pes" (0.22), "indic" (0. 2), "vetor" (0.19), "chav" (0.13),
"relev" (0.12), "dad" (0.09), "stopword" (0.08), "palavr"
(0.07), "information" (0.05), "vec" (0.05), "stemming"
(0.05), "precis" (0.04), "dat" (0.04), "document" (0.04),
"abrang" (0.03), "similar" (0.03)
Após a execução de busca dos documentos, o Fidus apresentou o
resultado que consta na Tabela 13.
Tabela 13 - Resultado da sétima iteração
Rel.
Matemática %
Rel.
Vetorial %
0
0
0
0
10
0
0
0
25
0
Rel.
Efetiva %
0
0
0
0
26
0
0
0
48
0
0
0
0
0
100
0
0
0
100
0
Documento
0060.htm
0061.htm
0062.htm
0063.htm
0064.htm
0065.htm
0066.htm
0067.htm
0068.htm
0069.htm
56
O algoritmo vetorial obteve êxito em recuperar apenas um documento
relevante durante a sexta iteração.
O algoritmo vetorial atribuiu ao documento 0064.htm o valor de relevância
potencial de 26%. Para o documento 0068.htm, a relevância calculada foi de 48%.
O modelo matemático não foi capaz de recuperar nenhum dos
documentos efetivamente relevantes. O documento 0064.htm foi classificado com
relevância potencial de 10%, enquanto que o documento 0068.htm obteve 25% de
relevância.
A comparação dos resultados obtidos entre os dois algoritmos para cada
documento relevante pode ser observada no Gráfico 6.
Gráfico 6 - Comparação de relevância potencial entre os algoritmos
100
80
60
Algoritmo
Matemático
40
Algoritmo
Vetorial
20
0
Documento
0064.htm
Documento
0068.htm
A Tabela 14 apresenta os resultados da avaliação dos algoritmos na
sétima iteração.
Tabela 14 - Avaliação da sétima iteração
Algoritmo de
Avaliação
Matemático
Vetorial
Precisão
%
0
50
57
3.2.9. Oitava iteração
Para a oitava iteração, os documentos considerados como relevantes
foram, respectivamente, os documentos 0070.htm e 0075.htm. Estes documentos
possuem os seguintes termos:
•
Documento 0070.htm
“recuperação”, “informação”, “consulta”, “perfil”,
“categoria”, “peso”, “normalização”, “relevância”, “termo”,
“frequencia”
Os termos “termo”, “freqüência”, “peso” e “normalização”, possuem
um valor de freqüência de 30 ocorrências. Os demais termos ocorrem 10 vezes no
documento.
•
Documento 0075.htm
“agente”, “informação”, “meta”, “busca”, “repositório”,
“consulta”, “termo”, “palavra”, “chave”, “peso”
Os termos “consulta”, “termo”, “informação” e “busca”, possuem um
valor de freqüência de 30 ocorrências. Os demais termos ocorrem 10 vezes no
documento.
Nesta iteração, o Fidus criou o vetor termo peso, que representa a
categoria de informação, com seguintes termos e seus respectivos pesos
normalizados:
"term" (1.0), "inform" (0.85), "recuper" (0.39), "model"
(0.30), "indic" (0.27), "pes" (0.19), "chav" (0.19), "dad"
(0.17), "vetor" (0.10), "relev" (0.1), "palavr" (0.07),
"stopword" (0.07), "vet" (0.05), "information" (0.04),
"vec" (0.04), "stemming" (0.04),
"similar" (0.04)
Após a execução de busca dos documentos, o Fidus apresentou o
resultado que consta na Tabela 15.
58
Tabela 15 - Resultado da oitava iteração
Rel.
Matemática %
Rel.
Vetorial %
25
5
0
0
0
25
0
5
0
5
Rel.
Efetiva %
59
1
0
0
0
76
0
1
0
1
100
0
0
0
0
100
0
0
0
0
Documento
0070.htm
0071.htm
0072.htm
0073.htm
0074.htm
0075.htm
0076.htm
0077.htm
0078.htm
0079.htm
O algoritmo vetorial foi o mais preciso na oitava iteração. Ele foi capaz de
recuperar todos os documentos relevantes definidos para o teste.
O algoritmo vetorial atribuiu ao documento 0070.htm o valor de relevância
potencial de 59%. O documento 0075.htm foi avaliado com o maior valor de
relevância potencial, 76%.
O modelo matemático não foi capaz de recuperar nenhum dos
documentos efetivamente relevantes. Os documentos 0070.htm e 0075.htm foram
classificados com relevância potencial de 25%, respectivamente.
A comparação dos resultados obtidos entre os dois algoritmos para cada
documento relevante pode ser observada no Gráfico 7.
Gráfico 7 - Comparação de relevância potencial entre os algoritmos
100
80
60
Algoritmo
Matemático
40
Algoritmo
Vetorial
20
0
Documento
0070.htm
Documento
0075.htm
59
A Tabela 16 apresenta os resultados da avaliação dos algoritmos na
oitava iteração.
Tabela 16 - Avaliação da oitava iteração
Algoritmo de
Avaliação
Matemático
Vetorial
Precisão
%
0
100
3.2.10. Nona iteração
Para a nona iteração, os documentos considerados como relevantes
foram, respectivamente, os documentos 0083.htm e 0088.htm. Estes documentos
possuem os seguintes termos:
•
Documento 0083.htm
“dado”, “termo”, “relevância”, “potencial”, “vetor”,
“espaço”, “vetorial”, “similaridade”, “indexação”,
“documento”
Os termos “indexação”, “relevância”, “documento” e “termo”,
possuem um valor de freqüência de 30 ocorrências. Os demais termos ocorrem 10
vezes no documento.
•
Documento 0088.htm
“peso”, “freqüência”, “inversa”, “termo”, “binário”, “vetor”,
“recuperação”, “informação”, “documento”, “categoria”
Os termos “documento”, “categoria”, “freqüência” e “inversa”,
possuem um valor de freqüência de 30 ocorrências. Os demais termos ocorrem 10
vezes no documento.
Nesta iteração, o Fidus criou o vetor termo peso, que representa a
categoria de informação, com seguintes termos e seus respectivos pesos
normalizados:
60
"term" (1.0), "inform" (0.72), "recuper" (0.35), "pes" (0.3),
"model" (0.28), "indic" (0.19), "dad" (0.15), "chav" (0.14),
"vetor" (0.11), "relev" (0.11), "vet" (0.06), "palavr" (0.05),
"similar" (0.05), "stopword" (0.05), "vec" (0.03), "salton"
(0.03), "information" (0.03), "frequenc" (0.03), "stemming"
(0.03)
Após a execução de busca dos documentos, o Fidus apresentou o
resultado que consta na Tabela 17.
Tabela 17 - Resultado da nona iteração
Rel.
Matemática %
Rel.
Vetorial %
0
0
0
30
0
5
0
0
30
0
Rel.
Efetiva %
0
0
0
63
0
1
0
0
56
0
0
0
0
100
0
0
0
0
100
0
Documento
0080.htm
0081.htm
0082.htm
0083.htm
0084.htm
0085.htm
0086.htm
0087.htm
0088.htm
0089.htm
O algoritmo vetorial foi o mais preciso na nona iteração. Ele foi capaz de
recuperar todos os documentos relevantes definidos para o teste.
O algoritmo vetorial atribuiu ao documento 0083.htm o valor de relevância
potencial de 63%. O documento 0088.htm foi avaliado com o valor de relevância
potencial de 56%.
O modelo matemático não foi capaz de recuperar nenhum dos
documentos efetivamente relevantes. Os documentos 0083.htm e 0088.htm foram
classificados com relevância potencial de 30%, respectivamente.
A comparação dos resultados obtidos entre os dois algoritmos para cada
documento relevante pode ser observada no Gráfico 7.
61
Gráfico 8 - Comparação de relevância potencial entre os algoritmos
100
80
60
Algoritmo
Matemático
40
Algoritmo
Vetorial
20
0
Documento
0083.htm
Documento
0088.htm
A Tabela 18 apresenta os resultados da avaliação dos algoritmos na nona
iteração.
Tabela 18 - Avaliação da nona iteração
Algoritmo de
Avaliação
Matemático
Vetorial
Precisão
%
0
100
3.2.11. Décima iteração
Para a nona décima, os documentos considerados como relevantes
foram, respectivamente, os documentos 0098.htm e 0099.htm. Estes documentos
possuem os seguintes termos:
•
Documento 0098.htm
“métrica”, “avaliação”, “recuperação”, “informação”,
“precisão”, “abrangência”, “termo”, “relevância”, “índice”,
“sistema”
Os termos “avaliação”, “relevância”, “recuperação” e “termo”,
possuem um valor de freqüência de 30 ocorrências. Os demais termos ocorrem 10
vezes no documento.
•
Documento 0099.htm
62
“trec”, “voorhees”, “darpa”, “coleção”, “referência”,
“documento”, “recuperação”, “informação”, “corpus”
Os termos “recuperação”, “informação”, “trec” e “coleção”, possuem
um valor de freqüência de 30 ocorrências. Os demais termos ocorrem 10 vezes no
documento.
Nesta iteração, o Fidus criou o vetor termo peso, que representa a
categoria de informação, com seguintes termos e seus respectivos pesos
normalizados:
"term" (1.0), "inform" (0.74), "pes" (0.34), "recuper" (0.32),
"model" (0.20), "indic" (0.14), "relev" (0.13), "chav" (0.13)
"dad" (0.13), "document" (0.11), "vetor" (0.10), "vet" (0.09),
"index" (0.07), "frequenc" (0.06), "palavr" (0.06),
"similar" (0.05), "stopword" (0.03),
"categor" (0.02)
Após a execução de busca dos documentos, o Fidus apresentou o
resultado que consta na Tabela 19.
Tabela 19 - Resultado da décima iteração
Rel.
Matemática %
Rel.
Vetorial %
0
0
5
0
0
0
0
0
25
20
Rel.
Efetiva %
0
0
0
0
0
0
0
0
59
41
0
0
0
0
0
0
0
0
100
100
Documento
0090.htm
0091.htm
0092.htm
0093.htm
0094.htm
0095.htm
0096.htm
0097.htm
0098.htm
0099.htm
Durante a décima iteração algoritmo vetorial foi o mais preciso. Ele foi
capaz de recuperar todos os documentos relevantes definidos para o teste.
63
O algoritmo vetorial atribuiu ao documento 0098.htm o valor de relevância
potencial de 59%. O documento 0099.htm foi avaliado com o valor de relevância
potencial de 41%.
O modelo matemático não foi capaz de recuperar nenhum dos
documentos efetivamente relevantes. O documento 0098.htm obteve 25% de
relevância enquanto o documento 0099.htm foi classificado com 20% de relevância
potencial.
A comparação dos resultados obtidos entre os dois algoritmos para cada
documento relevante pode ser observada no Gráfico 9.
Gráfico 9 - Comparação de relevância potencial entre os algoritmos
100
80
60
Algoritmo
Matemático
40
Algoritmo
Vetorial
20
0
Documento
0098.htm
Documento
0099.htm
A Tabela 20 apresenta os resultados da avaliação dos algoritmos na
décima iteração.
Tabela 20 - Avaliação da décima iteração
Algoritmo de
Avaliação
Matemático
Vetorial
Precisão
%
0
100
3.2.12. Conclusão dos testes
Após a realização dos testes com o conjunto de documentos e,
verificando-se a comparação entre os valores obtidos para cada algoritmo de
classificação, foi possível observar o indicativo de que o modelo vetorial pode ser o
mais preciso para o cálculo de similaridade de documentos recuperados.
64
Durante a realização dos testes verificou-se que um conjunto de termos
não estava sofrendo alterações em relação à quantificação de seus pesos nas
diversas iterações efetuadas. Foi detectado que estes termos pertenciam aos
documentos relevantes da primeira iteração e que, devido às características do
algoritmo, não passavam pelo processo de correção de pesos. Desta forma, os
pesos destes termos não condiziam com a sua representatividade no contexto de
busca, o que resultava em distorções no cálculo de similaridade entre os
documentos e a categoria de informação.
Para solucionar a distorção causada pelos termos de pesos invariáveis
fez-se necessária a modificação do algoritmo de correção de pesos. Após uma
análise minuciosa no fluxo do algoritmo, identificou-se que os termos selecionados
para tornarem-se elementos do vetor da categoria de informação durante a primeira
iteração não sofreriam qualquer correção em seus pesos se não ocorressem em
outros documentos. A alteração implementada consistiu em realizar a correção dos
pesos de todos os elementos que faziam parte do vetor da categoria de informação
durante a análise de similaridade, após o julgamento do usuário.
Esta alteração melhorou a precisão do algoritmo vetorial em alguns
testes, como também evitou que um erro de avaliação ocorrido na sexta iteração do
primeiro teste, que pode ser visualizado com maiores detalhes no Anexo 1, voltasse
a ocorrer.
65
Conclusão
O modelo vetorial obteve êxito em determinar a relevância para a maioria
dos testes efetuados, enquanto o modelo matemático mostrou-se ineficiente em
recuperar documentos relevantes para o corpus desenvolvido neste trabalho.
A vantagem obtida pelo algoritmo vetorial pode ser explicada por sua
característica de utilizar o cálculo do co-seno entre os vetores do documento e da
categoria de informação que é sensível à variação de freqüências dos termos
indexados. O modelo matemático não se beneficia da análise de freqüências dos
termos relevantes, estando limitado apenas a verificar a ocorrência de um termo nos
dois vetores de representação da informação.
Como sugestão para trabalhos futuros estaria a modificação do algoritmo
de stemming do Fidus. Foi verificado durante os testes que palavras menores que 2
(dois) elementos não eram indexadas. Dessa forma siglas semanticamente
representativas (RI no contexto da Recuperação de Informação, por exemplo), não
participavam do processo de cálculo de similaridade. Um outro problema encontrado
com este algoritmo foi a ineficácia em determinar o radical comum de termos como
vetor e vetorial, o que resultou em uma redução do peso deste radical por estar
dividido. Recomenda-se o estudo para viabilidade da implementação do algoritmo de
stemming desenvolvido por Orengo e Huyck (2001).
Uma outra sugestão é a realização de mais testes para a validação do
algoritmo vetorial implementado utilizando um corpus de maior extensão. Estes
testes teriam o objetivo de confirmar os indícios encontrados por este trabalho em
um conjunto de referência mais abrangente.
Por fim a sugestão da modificação da interface do usuário do Fidus,
portando-a para o ambiente Web e ampliando o seu acesso, buscando atender ao
requisito de usabilidade proposto por Gomes (2001) durante o desenvolvimento do
sistema.
66
Referências
BAEZA-YATES, Ricardo; RIBEIRO-NETO, Berthier. Modern Information Retrieval.
1.ed. [S.L]: Addison Wesley, 1999.
BATISTA JÚNIOR, Wilson dos S. Recuperação de Informação com Auxílio de
Extratos
Automáticos.
2006.
Dissertação
(Mestrado
em
Ciência
da
Computação) – Universidade Federal de São Carlos, São Carlos.
CARDOSO, Olinda Nogueira P. Recuperação de Informação. 2001. Disponível na
Internet
http://www.dcc.ufla.br/infocomp/artigos/v2.1/olinda.pdf,
acessado
em
15/09/2007.
GOMES, Edeyson Andrade. Fidus: Uma Ferramenta para Busca de Informações
Personalizadas na Web. 2001. Dissertação (Mestrado em Informática) Universidade Federal da Paraíba, Campina Grande.
GREENGRASS, Ed. Information retrieval: A survey. 2000. Disponível na Internet
http://citeseer.ist.psu.edu/rd/0%2C388821%2C1%2C0.25%2CDownload/http%3A
qSqqSqwww.cs.umbc.eduqSqcadipqSqreadingsqSqIR.report.120600.book.pdf.
Acessado em 07/09/2007.
MANNING,
Christopher
D.;
RAGHAVAN,
Prabhakar;
SCHÜTZE,
Hinrich;
Introduction to Information Retrieval. 1.ed. [S.L]: Cambridge University Press.
2007.
MENOTI, David. Recuperação de Documentos Implementando o Modelo
Vetorial. 2004. Universidade Federal de Minas Gerais, Belo Horizonte.
ORENGO, V.M; HUYCK, C. R. A Stemming Algorithm for the Portuguese
Language. 2001. 8th International Symposium on String Processing and
Information Retrieval (SPIRE). Laguna de San Raphael, Chile.
SALTON, Gerard. Recent Trends in Automatic Information Retrieval. 1986. ACM,
Conferencia Anual sobre Pesquisa e Desenvolvimento em Recuperação de
Informação. Pisa, Itália.
SALTON, Gerard. Approaches to passage retrieval in full text information
systems. 1993. ACM, Conferencia Anual sobre Pesquisa e Desenvolvimento em
Recuperação de Informação. Pittsburgh, Pennsylvania, Estados Unidos.
67
VENERUCHI,
Edilene
A.
Linguagens
de
Consulta
e
Recuperação
de
Documentos Hipermídia no Ambiente Web. 1999. Dissertação (Mestrado em
Ciência da Computação) - Universidade Federal do Rio Grande do Sul, Porto
Alegre.
VOORHEES, Ellen M. The text retrieval conferences (TRECS). 1998. ACL,
Encontro Anual da ACL (Association for Computational Linguistics). Baltimore,
Maryland, Estados Unidos.
VOORHEES, Ellen M. TREC: Continuing information retrieval's tradition of
experimentation. 2007. ACM, Communications of the ACM. Volume 50. Nova
York, Nova York, Estados Unidos.
YU, C. T.; LAN, K.; SALTON, Gerard. Term Weighting in Information Retrieval
Using the Term Precision Model. 1982. Journal of the ACM. Volume 29. Nova
York, Nova York, Estados Unidos.
68
APÊNDICE A
A1. Introdução
Este apêndice contém um resumo dos resultados das iterações de teste,
aplicadas a implementação ao algoritmo vetorial e ao matemático, em que a
implementação do algoritmo de correção de pesos permitia o surgimento de pesos
invariáveis, como descrito na seção 3.2.12 deste trabalho.
Estão disponíveis os resultados até a sexta iteração, porque após a
identificação do problema citado os testes foram interrompidos e reiniciados, quando
se deu a realização da alteração no algoritmo de correção de pesos.
Para obter maiores detalhes destas iterações recomenda-se a leitura do
Anexo 1.
A2. Primeira iteração
Tabela A1 - Resultado da primeira iteração
Rel.
Matemática %
Rel.
Vetorial %
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
Rel.
Efetiva % Documento
100
0000.htm
0
0001.htm
0
0002.htm
100
0003.htm
0
0004.htm
0
0005.htm
0
0006.htm
0
0007.htm
0
0008.htm
0
0009.htm
69
A3. Segunda iteração
Tabela A2 - Resultados da segunda iteração
Rel.
Matemática %
4
9
4
9
0
0
0
21
0
4
Rel.
Rel.
Vetorial % Efetiva % Documento
36
0
0010.htm
4
0
0011.htm
4
0
0012.htm
44
100
0013.htm
0
0
0014.htm
0
0
0015.htm
0
0
0016.htm
47
100
0017.htm
0
0
0018.htm
36
0
0019.htm
A4. Terceira iteração
Tabela A3 – Resultados da terceira iteração
Rel.
Matemática %
Rel.
Vetorial %
0
0
31
0
0
0
0
0
0
20
Rel.
Efetiva %
0
0
61
0
0
0
0
0
0
39
0
0
100
0
0
0
0
0
0
100
Documento
0020.htm
0021.htm
0022.htm
0023.htm
0024.htm
0025.htm
0026.htm
0027.htm
0028.htm
0029.htm
70
A5. Quarta iteração
Tabela A4 - Resultado da quarta iteração
Rel.
Matemática %
Rel.
Vetorial %
16
0
0
0
0
0
0
0
11
0
Rel.
Efetiva %
53
0
0
0
0
0
0
0
55
0
100
0
0
0
0
0
0
0
100
0
Documento
0030.htm
0031.htm
0032.htm
0033.htm
0034.htm
0035.htm
0036.htm
0037.htm
0038.htm
0039.htm
A6. Quinta iteração
Tabela A5 - Resultado da quinta iteração
Rel.
Matemática %
Rel.
Vetorial %
0
0
0
0
0
47
0
0
0
0
Rel.
Efetiva %
0
0
0
0
0
44
0
0
0
0
0
0
0
0
0
100
0
0
100
0
Documento
0040.htm
0041.htm
0042.htm
0043.htm
0044.htm
0045.htm
0046.htm
0047.htm
0048.htm
0049.htm
71
A7. Sexta iteração
Tabela A6 - Resultado da sexta iteração
Rel.
Matemática %
Rel.
Vetorial %
17
0
7
0
0
0
0
0
0
20
Rel.
Efetiva %
31
0
49
0
0
0
0
0
0
21
100
0
0
0
0
0
0
0
0
100
Documento
0050.htm
0051.htm
0052.htm
0053.htm
0054.htm
0055.htm
0056.htm
0057.htm
0058.htm
0059.htm