REPRESENTAÇÃO VISUAL DE BASES DE DOCUMENTOS
Newton Cunha Müller
RESUMO - Há muito tempo a humanidade vem se preocupando com a manutenção e
manuseio da informação. Seja armazenando documentos ou fornecendo meios para recuperálos, sua organização, principalmente em bibliotecas, tem ajudado nesta tarefa.
Em se tratando especificamente de um tipo de informação, a informação textual, existe uma
área de estudos conhecida como Recuperação de Informação (Information Retrieval) que se
preocupa com a pesquisa e desenvolvimento de novos métodos de recuperação e acesso.
Nos Sistemas de Recuperação de Informações (SRI), utilizados para armazenar, recuperar e
acessar informações, a análise da relevância dos documentos recuperados em uma operação de
busca, é de responsabilidade do usuário, que a realiza baseado no grau de similaridade obtido
entre a consulta por ele elaborada e os documentos.
Visando-se auxiliar o usuário na análise e determinação da relevância, propõe-se, neste
trabalho, uma representação visual da similaridade entre a consulta e os documentos
recuperados, associando-se para isso dois estudos, o Modelo Vetorial de Recuperação de
Informações e a Teoria das Coordenadas Paralelas.
1. INTRODUÇÃO
A recuperação da informação (RI) é um processo de comunicação, um meio pelo qual os
usuários de um sistema de informação podem encontrar os documentos que atendam às suas
necessidades [29]. O que caracteriza esta forma de comunicação é o fato de que estes documentos
foram criados e colocados em algum meio de armazenamento e disponibilizados para a pesquisa
[29].
Um Sistema de Recuperação de Informações (SRI) é um sistema usado para armazenar e
acessar informações que podem ser processadas, pesquisadas, recuperadas e colocadas à
disposição de vários tipos de usuários.
Newton Cunha Müller MSc ULBRA– [email protected]
2
Os sistemas de recuperação de informação são normalmente usados para manusear registros
bibliográficos e dados textuais [31], e têm como objetivo fazer com que um usuário encontre a
informação que necessita sem ter ele mesmo que analisar todas as informações relacionadas com
a que deseja obter.
Os SRI devem realizar a análise das necessidades de informação do usuário e retornar a ele as
mais relevantes. Neste caso, o conceito de informação relevante é muito importante para a
recuperação de informações. Segundo Salton [31], relevância é a correspondência contextual
entre uma consulta e uma informação, ou seja, a relevância indica o quanto a informação é
apropriada para o solicitante, ou o quanto é importante para o usuário determinada informação.
Fica claro que a relevância é, em parte, determinada em função de como o usuário formulou sua
consulta.
Os sistemas de recuperação de informações, numa primeira fase (primeira geração),
utilizavam-se basicamente de um conjunto de fichas em que era possível recuperar informações
fornecendo como entrada alguns tipos de dados, como por exemplo, o título do documento ou o
nome do autor.
Posteriormente, avanços nos modos de busca foram sendo acrescentados, permitindo também
pesquisar por assuntos ou palavras-chave e elaborar consultas mais complexas. Atualmente podese contar com o auxílio de interfaces gráficas [6], formulários eletrônicos e hipertextos na
formulação das consultas. Entretanto, muitos dos mecanismos de busca hoje existentes continuam
usando índices muito similares aos que eram utilizadas por bibliotecas há mais de um século [2].
1.1 O paradigma da recuperação de informação
Todos os sistemas de recuperação da informação têm, como já foi dito, o objetivo de
possibilitar ao usuário encontrar a informação desejada o mais rápido possível. Portanto, pode-se
relacionar como componentes de um SRI:
- O usuário e sua necessidade de informação;
- A coleção de documentos que contém ou não a informação que ele deseja;
- A visão lógica da necessidade de informação do usuário, traduzida através da consulta por
ele elaborada;
- A visão lógica dos documentos da coleção, onde é necessário identificar conteúdos e
características e dispor de algum modelo que permita descrevê-las e armazená-las [2].
3
O sistema deve também associar a estes componentes um processo de busca que permita
selecionar entre as informações existentes aquelas que são de fato relevantes para o usuário. É
comum encontrar este processo na literatura especializada como sendo uma função de
similaridade (que determina a semelhança entre os elementos da consulta e os dados
armazenados).
1.1.1
Descrição da necessidade de informação do usuário
No processo de recuperação de informações o usuário deve ser capaz de descrever a
informação procurada e para isto deve identificar o maior número possível de características
desta informação. Este processo pode ser complicado para o usuário por diversos fatores,
descritos a seguir.
O primeiro tem a ver com a sua própria incapacidade de descrever corretamente a informação
que deseja. Quando se realiza alguma busca em grandes massas de informações deve-se possuir
meios que permitam determinar a direção a ser seguida. Os SRI atualmente disponíveis nem
sempre conseguem oferecer formas de acesso eficientes para a busca de informações, ou seja, as
formas de acesso oferecidas por eles muitas vezes não são as ideais.
Em uma consulta, o usuário precisa sempre expressar tão corretamente quanto possível as suas
necessidades de informação. Da mesma forma, esta descrição deve ser sucinta. Uma das formas
mais utilizadas pelos SRI é a consulta por palavras-chave, onde são fornecidas ao sistema uma ou
mais combinações de palavras que identifiquem o assunto desejado.
O SRI tem como tarefa procurar e retornar todos aqueles documentos que utilizem estas
palavras. A ferramenta de busca Altavista (www.altavista.com) é um exemplo de ferramenta que
usa esta técnica na Internet.
A incapacidade do usuário em elaborar uma consulta precisa pode advir das limitações do
sistema e também da própria linguagem natural utilizada e sua natureza ambígua. Várias pessoas
podem descrever um mesmo objeto de maneiras diferentes, e muitos são os motivos que as levam
a isto, como cultura, hábitos e formação.
Estudos indicam que as diversas áreas do conhecimento possuem seus próprios termos
científicos para designar em muitos casos coisas semelhantes [8]. Este problema é conhecido
como Problema do Vocabulário. Há ainda o problema da Busca Incerta, onde o usuário não sabe
quais são as palavras que melhor identificam o assunto a pesquisar.
4
Os resultados desta incapacidade provavelmente serão o retorno de uma longa lista de
informações mais ou menos correlatas e em boa parte irrelevantes para o que se procura. A
dificuldade de analisar todos estes documentos vem sendo conhecida como Sobrecarga de
Informações.
Outras razões contribuem para as dificuldades do usuário em elaborar suas consultas, como
não estar familiarizado com o sistema de busca e portanto não utilizar as facilidades oferecidas
por ele, ou a dificuldade em expressar aquilo que imaginou e também o fato do próprio sistema
não permitir que a consulta seja expressa convenientemente [8]. Esforços vêm sendo feitos no
sentido de dotar os SRI de interfaces que facilitem a elaboração de consultas por parte dos
usuários [6].
A maneira mais utilizada para se mostrar os resultados de uma consulta é por uma lista de
informações. Ordenados pela relevância, os documentos desta lista apresentam normalmente
dados importantes como título, autor, data, origem, tamanho e a descrição do conteúdo.
Pode aparecer também um número ou porcentagem indicando o grau de relevância de cada
documento para a consulta. Este número é chamado de surrogate do documento [2].
Para que o objetivo desejado seja melhor alcançado podem ser feitos refinamentos através de
novas consultas usando como base as consultas já realizadas (relevance feedback).
1.1.2
A visão lógica dos documentos
Nesta etapa do processo de RI é necessário criar um modelo dos dados que
serão tratados pelo sistema. Para a construção deste modelo é importante identificar os atributos
que melhor caracterizam as informações e as diferenciam de outras. Devemos sempre considerar
que uma determinada forma de descrever um tipo de informação pode, às vezes, não ser
adequada para a descrição de outro tipo de informação.
Como exemplo, pode-se citar que a descrição textual de um dado do tipo imagem ou som nem
sempre é capaz de expressar com clareza todas as suas características. Portanto, é de grande
importância a escolha de um modelo que seja capaz de guardar os aspectos fundamentais das
informações, pois esta decisão vai facilitar sua recuperação.
Nos sistemas de recuperação de informações textuais as técnicas utilizadas diferem das
técnicas empregadas nos bancos de dados tradicionais, onde as informações armazenadas estão
agrupadas por propriedades específicas e as categorias conceituais são bem conhecidas.
5
A recuperação de dados textuais envolve a recuperação de textos, que podem ser desde
palavras até frases, parágrafos ou livros. Neste caso, não se tem atributos ou campos que
permitam identificar determinados conjuntos de dados, os dados procurados estão distribuídos ao
longo do texto. Portanto, em se tratando de informações textuais, o meio de acesso que se dispõe
são as palavras ou termos.
Para tornar mais rápida a recuperação de informações textuais utiliza-se uma estrutura de
dados auxiliar, conhecida como índice. Um índice é uma coleção de palavras selecionadas, às
quais são associados ponteiros e que permitem a localização de informações ou documentos.
A transformação de documentos em uma estrutura de dados que possibilite a recuperação de
informações é chamada de indexação. A indexação (chamada originariamente de Catalogação) é
uma antiga técnica usada para identificar o conteúdo de documentos e ajudar em sua posterior
recuperação. O objetivo de indexar é encontrar pontos de acesso para uma coleção que está
disponível a requisições de informação. A indexação pode ser manual ou automática.
A indexação manual é o processo tradicional realizado por pessoas, onde o indexador procura
estabelecer relacionamentos e conceitos entre os assuntos examinados para criar os índices.
A indexação automática apóia-se na utilização de software para extração dos termos dos
documentos e a criação dos índices. É hoje o método predominantemente utilizado, pois a
capacidade dos computadores e a proliferação das informações digitais (a Web possui milhões de
páginas indexáveis com grande taxa de alteração e dinamicidade) tem tornado o processo
automático a melhor alternativa para a indústria da informação.
As principais técnicas de indexação se baseiam na utilização de arquivos (ou listas) invertidos.
Outras estruturas podem ser utilizadas, mas a experiência tem demonstrado que estas estruturas
são das mais adequadas [2].
Um arquivo invertido é composto de dois elementos: a lista de palavras e as ocorrências. A
lista de palavras é o conjunto de todas as palavras diferentes do texto. Para cada palavra desta
lista é guardado o conjunto de locais onde elas aparecem no texto (ponteiros), este conjunto
constitui a lista de ocorrências [16].
1.1.3
A busca de informações relevantes
A última etapa na recuperação da informação é identificar, na base de dados, quais são as
informações relevantes que atendam a consulta do usuário. É o processo de associação da
6
consulta com a visão lógica dos documentos, ou seja, a procura pela similaridade existente entre
os termos componentes da consulta e as informações armazenadas.
Problemas podem ocorrer nesta fase como o já citado Problema do Vocabulário, onde pessoas
diferentes podem utilizar termos diferentes para descrever os mesmos objetos / informações e o
Problema da Busca Incerta, onde o usuário não sabe bem quais palavras identificam o assunto
procurado.
Estudos nesta área indicam que descrever o maior número possível de características da
informação desejada aumenta a possibilidade de recuperar informações relevantes. Dos vários
modelos e técnicas que tratam especificamente deste assunto um deles, o Modelo Vetorial, foi
escolhido e será apresentado no titulo 2.
2. O MODELO VETORIAL
O Modelo Vetorial (Vector Model) é um dos modelos clássicos da recuperação de
informações, que são, segundo Baeza-Yates, aqueles onde cada documento é descrito por um
conjunto de palavras-chaves, representativas do assunto, e que provavelmente integrarão o índice
do documento [2].
Ele foi utilizado por Gerard Salton juntamente com pesquisadores da Universidade de Cornell
no sistema SMART (System for Mechanical Analysis and Retrieval of Text), um dos exemplos de
aplicação do Modelo Vetorial na recuperação de informações [31].
O sistema SMART distingue-se de outros SRI convencionais nos seguintes aspectos:
-
Usa métodos automáticos de indexação para associar conteúdos que identificam os
documentos com as consultas solicitadas;
-
Agrupa documentos similares em classes comuns facilitando a pesquisa em uma área
em particular;
-
Recupera os documentos por similaridade entre os termos armazenados e as consultas.
-
Apresenta ao usuário os resultados da consulta, em uma escala descendente de
similaridade entre os documentos encontrados e os termos da consulta.
No modelo cada documento indexado é representado por um vetor de termos que o
caracteriza. Cada documento é portanto identificado pela forma: Docj = (termo1, termo2, ...,
7
termon), onde Docj é o j-ésimo documento da coleção (base de dados) e o termoi o i-ésimo termo
do documento indexado.
Uma coleção de documentos pode então ser representada em uma matriz, onde cada linha é
um documento da coleção e cada coluna representa a associação de um termo específico com um
documento (tabela 1).
Tabela 1: Matriz de associação de termos e documentos
Termo1
Termo2
...
Termon
Doc1
Peso11
Peso12
...
Peso1n
Doc2
Peso21
Peso22
...
Peso2n
Μ
Μ
Μ
...
Μ
Docj
Pesoj1
Pesoj2
...
Pesojn
Cada par (Docj, Termoi) possui um valor associado, conhecido como peso, que indica a
existência ou não do termo no documento ou a sua importância na identificação do documento.
Assim o vetor que representa cada documento fica sendo Docj = (pesoj1, pesoj2,..., pesojn).
Duas abordagens podem ser utilizadas na determinação deste valor (peso), a binária e a
ponderada. Na abordagem binária dois valores são utilizados, um (1) que indica a existência do
termo no documento e zero (0) a sua ausência (tabela 2).
Tabela 2: Matriz de termos e documentos (abordagem binária)
Termo1
Termo2
...
Termon
Doc1
1
0
...
1
Doc2
0
1
...
0
Μ
Μ
Μ
...
Μ
Docj
1
0
...
0
Na abordagem com peso, a ocorrência de um termo no documento é representada por um valor
positivo. O zero continua sendo o valor utilizado para representar os termos que não estão
presentes. Os valores positivos dos pesos variam de acordo com a importância dos termos no
8
documento. Termos de maior peso são considerados mais importantes porque caracterizam
melhor um documento (tabela 3).
Tabela 3: Matriz de termos e documentos (abordagem com peso)
Termo1
Termo2
...
Termon
Doc1
0
14
...
0
Doc2
0
6
...
9
Μ
Μ
Μ
...
Μ
Docj
15
21
...
0
Existem diversas maneiras de calcular o peso de cada um dos termos que representam o
documento indexado. Uma das mais utilizadas baseia-se na freqüência com que o termo aparece
no documento. Esta técnica considera que uma palavra que está presente muitas vezes em um
documento é boa para caracterizar o seu conteúdo. Pode-se então utilizar esta técnica para
recuperar documentos que atendam as necessidades de informações dos usuários.
A seguir serão descritas duas das funções que são utilizadas pelos sistemas para cálculo dos
pesos dos termos nos documentos, freqüência do termo e freqüência inversa.
Freqüência do Termo (TF)
Esta função adota como peso do termo a sua freqüência no documento, e pode ser definida
como:
Pesoij = Freqij
Freqij é o número de ocorrências do termo i no documento j.
Freqüência Inversa (IDF)
A Freqüência do Termo (TF) não faz distinção entre termos que ocorrem em muitos
documentos e aqueles que aparecem em somente alguns documentos da coleção. Termos que
aparecem em muitos documentos diminuem a precisão do sistema pois tendem a recuperar toda a
coleção. A relação a seguir é conhecida como Freqüência Inversa do documento e tenta
minimizar os problemas acima citados:
Pesoij = Freqij / DocFreqi
DocFreqi representa o número de documentos em que o termo i aparece.
Esta função também pode ser encontrada representada pela seguinte fórmula:
9
Pesoij = Freqij*[log2(n)–log2(DocFreqi)+1]
Pesoij é o peso do termo i no documento j;
Freqij é a freqüência do termo i no documento j;
n é o número de documentos da coleção;
DocFreqi é o número de documentos da coleção que possuem o termo i.
Uma consulta C, quando submetida pelo usuário, é transformada também em um vetor
C=(C1,C2,...,Cn) de características semelhantes aos vetores que representam os documentos,
sendo que os pesos atribuídos aos seus termos indicam sua importância para a recuperação das
informações. De maneira geral adota-se no modelo o valor um (1) para peso de cada um dos
termos da consulta (todos possuem a mesma importância). Os documentos que satisfazem a
consulta (possuem todos ou alguns dos termos) são obtidos pelo grau de similaridade medido
entre o vetor-consulta e os vetores-documentos.
A similaridade entre os vetores consulta e documento pode ser obtida pelo co-seno do ângulo
formado entre eles (Cosine Vector Similarity). Quanto menor for este ângulo, mais próximos
estarão os vetores entre si e maior será a sua similaridade. Assim é possível determinar o grau de
similaridade da consulta com todos os documentos da coleção e fornecer ao usuário uma lista de
documentos recuperados em ordem decrescente de relevância (similaridade).
A recuperação dos documentos, nesse caso, passa a ser uma operação realizada no espaço
euclidiano que procura determinar a relação entre os vetores. O modelo é também conhecido
como espaço de vetores.
A Similaridade por Co-senos (Cosine Vector Similarity) é obtida através da seguinte fórmula:
n
k=1
ck.dock
Sim(C,doc) =
n
2
k =1 (ck) .
n
2
k=1(dock)
doc é o vetor de termos do documento;
C é o vetor de termos da consulta;
ck : são os pesos dos termos da consulta;
dock : são os pesos dos termos nos documentos.
Na função, o numerador representa a similaridade entre os termos da consulta e os termos nos
documentos selecionados (por possuírem os termos da consulta). O denominador serve de fator
10
de normalização, por dividir a expressão pelo produto dos vetores consulta e documentos. Isto
implica que cada item será representado por um vetor de igual comprimento.
O modelo faculta ao usuário refazer a sua consulta com base na análise dos documentos
recuperados e com isto melhorar a busca por documentos que de fato satisfaçam as suas
necessidades de informação. Esta operação, conhecida como Relevance Feedback, implica a
construção de um novo vetor de consulta que será comparado com os vetores dos documentos em
uma nova operação de pesquisa.
Supondo-se um exemplo onde um usuário deseje recuperar informações em uma base de
documentos sobre um determinado assunto como indexação automática. O resultado obtido
pela consulta, neste caso, poderia ser (tabela 4):
Tabela 4: Resultado da consulta
Documento
Indexação
automática
DocA
0
7
DocB
4
10
DocC
5
3
Sendo a consulta
representada por C = (1,1) teria-se como resultado da similaridade,
calculada entre a consulta e os documentos os seguintes valores:
Sim (C, DocA) = (1x0 + 1x7 ) / ((12 + 12).(02 + 72))1/2 = 0.71
Sim (C, DocB) = (1x4 + 1x10) / ((12 + 12).(42 + 102))1/2 = 0.92
Sim (C, DocC) = (1x5 + 1x3) / ((12 + 12).(52 + 32))1/2
= 0.97
Os documentos selecionados seriam retornados ao usuário na ordem decrescente de
similaridade, ou seja:
DocC (0.97)
DocB (0.92)
DocA (0.71)
3. COORDENADAS PARALELAS
11
A utilização de conjuntos de dados com variáveis multidimensionais está se tornando cada vez
mais comum e com isto surge a necessidade de novas técnicas para visualizar essas informações.
As coordenadas paralelas são uma metodologia, desenvolvida por Alfred Inselberg na
Universidade de Illinois, para visualização geométrica em n dimensões [22]. Esta visualização é
obtida pela representação das dimensões em diversos eixos paralelos igualmente espaçados. Em
cada um destes eixos, que reproduzem uma dimensão, podemos representar coordenadas por seus
valores. Traçando-se uma linha ligando os eixos uns aos outros pode-se representar pontos e
planos em n dimensões.
Um determinado vetor P definido pela tupla de coordenadas (p1,p2,...,pn) é representado no
sistema por uma linha poligonal contínua P’ obtida ligando-se as diversas coordenadas p1,p2,...,pn
(figura 1). Assim, partindo da representação obtida, poderemos comparar as variáveis
representadas e tirar conclusões sobre os possíveis relacionamentos que daí podem advir. É
interessante apontar também neste método de visualização que a representação de vários vetores
em um mesmo gráfico vai nos permitir realizar comparações visuais entre eles.
Figura 1: Poligonal que representa o ponto P
Pontos no espaço Euclidiano são representados em coordenadas paralelas por linhas
poligonais, sendo que o número de dimensões que podem ser visualizadas é extremamente
grande e dependente somente das condições técnicas necessárias para apresentação. Entretanto, à
medida que o número de dimensões aumenta, as coordenadas tendem a ser representadas mais
próximas umas das outras podendo criar maiores dificuldades de interpretação.
Para melhor ilustrar esta técnica será apresentado um exemplo da representação de um ponto
A em um espaço de cinco dimensões em coordenadas paralelas. Considerando que o ponto A
esteja definido pela tupla de valores (0, 5, 3, -2, 1), teríamos sua representação conforme mostra a
figura 2.
12
Fig. 2: Poligonal que representa o ponto A
Uma característica importante da técnica de coordenadas paralelas é a possibilidade de
reordenar a posição dos eixos. Isto é particularmente interessante quando a forma de visualização
é importante para uma melhor análise dos dados. A figura 3 mostra a tupla A=(0, 5, 3, -2, 1)
classificada em ordem crescente do valor de suas coordenadas A’=(-2, 0, 1, 3, 5). Observa-se que
os valores originais das coordenadas continuam inalterados, só que agora fora da seqüência
inicial da tupla.
Figura 3: Poligonal que representa o ponto A
(ordenado pelos valores das coordenadas)
Dentre as vantagens desta metodologia podemos ressaltar a possibilidade de representar
diversos tipos de dados, com diferentes escalas para as coordenadas, e em qualquer dimensão.
Isto permite uma forma de visualização de variáveis multidimensionais que pode ser aplicada em
diversas áreas do conhecimento.
Uma das desvantagens a ressaltar seria a representação de grandes volumes de dados, onde a
visualização ficaria comprometida pelo acúmulo e sobreposição de linhas dificultando a análise
pretendida. Uma maneira de minimizar este problema é limitar o conjunto de dados a ser
representado.
13
4. REPRESENTAÇÃO VISUAL DOS DOCUMENTOS
A análise e seleção dos dados obtidos na consulta é uma tarefa que deve ser realizada pelo
usuário. Somente após esta etapa ele poderá obter, de todo conjunto de documentos recuperados,
aqueles que são de fato relevantes para suas necessidades de informação.
Em grande parte dos SRI as informações disponíveis para esta análise são a posição do
documento no conjunto de documentos-resposta, determinada pelo grau de similaridade
calculado pelo sistema. Entretanto, estas informações, nem sempre são suficientes para uma
análise satisfatória dos dados.
Uma solução possível para auxiliar o usuário nesta tarefa seria a representação visual da
similaridade existente entre a consulta e os documentos. A representação visual como uma
maneira de apresentar as informações permitiria identificar características que poderiam passar
desapercebidas.
A possibilidade de adicionar a representação visual ao processo de recuperação de
informações é uma forma de auxiliar o usuário na seleção dos documentos que atendam as suas
necessidades. Esta representação torna-se viável se associarmos o Modelo Vetorial com a Teoria
das Coordenadas Paralelas.
A escolha do Modelo Vetorial para este estudo baseou-se nos seguintes aspectos:
•
O modelo representa consultas, termos e documentos, através de vetores, em um
espaço n dimensional;
•
Os vetores são formados por n-uplas de valores que indicam o peso dos termos no
documento;
•
Estes vetores por serem representáveis em um espaço n dimensional, possibilitam a
utilização da teoria das Coordenadas Paralelas para criar uma representação visual que
permita identificar o relacionamento entre a consulta e os documentos;
•
O Modelo Vetorial, apesar de desenvolvido na década de 80, é considerado como um
dos modelos clássicos da RI e continua sendo usado até hoje.
4.1 Exemplo da representação visual de documentos
A seguir será apresentado um exemplo que procura esclarecer como é realizada a associação
entre o Modelo Vetorial e as Coordenadas Paralelas. A sua execução foi realizada com o auxilio
de um protótipo de software especialmente desenvolvido para apoio a proposta deste trabalho.
14
O exemplo utiliza uma base de documentos sobre a qual será feita uma consulta, e mostra
todos os passos realizados, até a conclusão com a análise da consulta.
4.1.1 A coleção de documentos
Foram selecionados para este exemplo dez documentos digitais obtidos da coleção
Library
of the Future [26], totalizando 207.396 palavras. Os documentos são:
d001 After Three Days (Lewis Carrol);
d002 Alice in Wonderland (Lewis Carrol);
d003 Alone (Edgar Allan Poe);
d005 Around the World in Eighty Days (Julio Verne);
d006 The Battle-Field (William Cullen Bryant);
d014 Cyrano de Bergerac (Edmond Rostand);
d044 The Comedy of Errors (William Shakespeare)
d045 The Merchant of Venice (William Shakespeare);
d046 The Taming of the Shrew (William Shakespeare);
d047 The two Gentlemen of Verona (William Shakespeare);
4.1.2 Cálculo do peso dos termos no documento
Como descrito anteriormente, as funções mais utilizadas para cálculo do peso dos termos no
Modelo Vetorial, Freqüência do Termo (TF) e Freqüência Inversa (IDF), nem sempre obtém
valores para peso dos termos nos documentos, num intervalo entre zero e um. Como necessita-se
de valores para peso neste intervalo, para facilitar a interpretação do gráfico, foi necessário
propor uma nova função peso. Esta função, além de não alterar a ordem de similaridade dos
documentos, obtida pela função da Freqüência do Termo (Pesoij=Freqij), obtém valores para peso
na faixa desejada.
A fórmula proposta é a da Freqüência Inversa com alterações no fator de normalização. Em
vez de utilizar como denominador o número de documentos onde o termo aparece (DocFreqi),
utilizou-se o comprimento do maior vetor que representa os documentos, ou seja,(
n
k=1
(Dock)2)1/2.
4.1.3 Exemplo
Neste exemplo serão mostrados inicialmente os resultados do cálculo da similaridade entre a
consulta e os documentos obtidos com o uso de duas funções, a Freqüência do Termo, descrita no
item 2 deste documento e a Freqüência Inversa Modificada (MF), descrita no item 4.1.2.
15
De acordo com o Modelo Vetorial, adota-se o valor um (1) para peso de cada um dos termos
da consulta. Então o vetor que irá representar a consulta no cálculo da similaridade será C =
(1,1).
Termos submetidos à consulta: beautiful e people.
Resultados obtidos com a pesquisa dos termos da consulta na coleção (tabela 5)
Tabela 5: Resultados da pesquisa
Documento
beautiful
people
vetor
d002
13
14
(13,14)
d005
3
15
(3,15)
d014
1
10
(1,10)
d044
0
3
(0,3)
d045
1
3
(1,3)
d046
3
0
(3,0)
d047
2
0
(2,0)
Os valores em cada um dos documentos acima representam a freqüência de cada termo da
consulta no documento. Os documentos d001, d003 e d006 não estão relacionados por não
possuírem estes termos.
Similaridade adotando para peso dos termos a Freqüência do Termo
Exemplificando para o documento d002
d002 (13,14)
Sim (C,d002) = 1x13 + 1x14 / ((12+12).(132+142))1/2 = 0.99
Similaridade para os demais documentos:
d005 = 0.83
d014 = 0.77
d044 = 0.71
d045 = 0.89
d046 = 0.71
d047 = 0.71
Ordenando por similaridade temos:
16
d002, d045, d005, d014, d044, d046 e d047.
Similaridade adotando para peso a Freqüência Inversa Modificada
Cálculo do tamanho dos vetores:
d002 (13,14) = (132+142)1/2 = 19.10
d005 = 15.29
d014 = 10.04
d044 = 3.00
d045 = 3.16
d046 = 3.00
d047 = 2.00
Fator de normalização (comprimento do maior vetor) = 19.10
Cálculo da similaridade para o documento d002
d002=(13/19.10, 14/19.10)
d002=(0.68, 0.73)
Sim (C,d002) = 1x0.68 + 1x0.73 / ((12+12).((0.68)2+(0.73)2))1/2 = 0.99
Similaridade para os demais documentos:
d005 = 0.83
d014 = 0.77
d044 = 0.71
d045 = 0.89
d046 = 0.71
d047 = 0.71
Ordenando por similaridade temos:
d002, d045, d005, d014, d044, d046 e d047.
Como podemos observar a Função Inversa Modificada não altera a ordem da similaridade
calculada com a Freqüência do Termo, já que os valores finais são os mesmos. Entretanto, ela
obtém valores intermediários para peso dentro da faixa desejada (entre zero e um).
Representação Visual da Consulta e dos Documentos
Os resultados da pesquisa realizada na base de documentos serão sempre apresentados em um
par de telas. A primeira tela (Documentos por similaridade) mostra todos documentos que
possuem os termos da consulta, classificados por ordem decrescente de similaridade. A segunda
tela, (Representação visual dos documentos) mostra através de um gráfico os documentos que
17
integraram a primeira tela, agora representados pelo peso dos seus termos usando Coordenadas
Paralelas.
Importante ressaltar que cada par de telas mostrará no máximo sete documentos com os
resultados. Estas restrições se justificam pela dificuldade de se representar em Coordenadas
Paralelas um grande volume de dados, o que pode vir a dificultar a interpretação (capítulo 3).
Análise dos resultados
A primeira tela (figura 4) apresenta os documentos onde foram encontrados os termos da
pesquisa, classificados em ordem decrescente de similaridade. Este resultado fornece ao usuário
uma idéia inicial do que é ou não relevante.
Na segunda tela (figura 5) vê-se os documentos representados por seus termos (pesos) em
Coordenadas Paralelas. Esta tela, juntamente com a tela anterior, vai permitir ao usuário fazer
uma análise mais completa da relevância dos documentos. O exemplo também mostra, através da
segunda tela (figura 5), que cada documento esta representado por uma linha poligonal que liga
os pesos dos termos. As linhas estão traçadas em cores diferentes para facilitar a interpretação.
Nas telas apresentadas como resultado da consulta observa-se que a representação visual
reflete, de uma maneira geral, a similaridade existente entre a consulta e os documentos
(mostrada pela primeira tela figura 4). O documento d002 (Alice in Wonderland) é, por sua
similaridade, o que tem maiores chances de ser relevante. O documento d045 (The Merchant of
Venice), segundo em similaridade (0.89), não corresponde no gráfico ao que é apontado pela
figura 4. Este documento, pela análise da representação visual, tem menos chances de ser
relevante que por exemplo os documentos d005 (Around in the World in Eighty Days) e d014
(Cyrano de Bergerac), com menor grau de similaridade, mas com valores mais significativos
para o peso dos termos, como mostra a figura 5. Os demais documentos, d044 (The Comedy of
Errors) d046 (The Taming of the Shrew) e d047 (The two Gentlemen of Verona) possuem o
mesmo grau de similaridade e não são muito significativos para a análise de relevância,
principalmente se considerar-se que nesses documentos não se encontra um dos termos da
consulta, o que pode ser facilmente identificado pelo gráfico.
18
Figura 4: Documentos por similaridade
Figura 5: Representação visual dos documentos
O estudo do exemplo acima leva a concluir que a função usada no cálculo na similaridade pelo
Modelo Vetorial favorece documentos que tenham valores aproximados para o peso dos termos.
19
Para encerrar este exemplo relacionou-se algumas observações identificadas com a
representação visual.
•
Ela especializa a seleção dos documentos relevantes, por oferecer também um gráfico
que representa o peso dos termos no documento;
•
Permite que se atribua uma importância diferenciada a cada termo da consulta. Alguns
SRI permitem a opção de atribuir maior ou menor importância aos termos da consulta
durante a sua elaboração, mas nem sempre os usuários estão familiarizados ou
dispostos a utilizar esta opção;
•
Possibilita, com maior facilidade, a interpretação dos resultados apresentados.
•
Permite representar graficamente, através de coordenadas paralelas, qualquer número
de termos incluídos na consulta. A figura 6, a seguir, mostra a representação visual em
duas dimensões do exemplo de consulta realizado neste capitulo usando o modelo
vetorial. Nela podemos observar que a representação gráfica esta limitada a três
dimensões, ou três termos, que cada documento é representado por seu vetor, e que não
é possível identificar o peso de cada termo no documento. A interpretação do gráfico,
por parte do usuário, parece também ficar mais difícil.
Figura 6: Representação visual dos documentos usando o Modelo Vetorial
20
5. CONSIDERAÇÕES FINAIS
Neste estudo foram analisadas as possibilidades de associar o Modelo Vetorial, utilizado na
recuperação de informações textuais, com a teoria das Coordenadas Paralelas, visando obter uma
representação visual da recuperação de documentos.
Nos exemplo apresentado procurou-se mostrar a importância desta representação como
ferramenta de auxílio ao usuário, na seleção de documentos relevantes. Podemos inclusive
observar que a visualização pode vir a facilitar a identificação dos relacionamentos entre a
consulta e os documentos, incluindo seus termos.
O protótipo que foi utilizado neste trabalho para realizar as operações de cadastro, indexação e
consulta aos documentos digitais foi desenvolvido no ambiente operacional GNU/LINUX, com
linguagem de programação “C” e comandos de manipulação de programação Shell Script. Para a
geração dos gráficos foi utilizado o programa de geração de gráficos Gnuplot, disponível na
maioria das distribuições Linux.
A indexação automática dos documentos, que não foi objetivo prioritário neste trabalho, se fez
necessária para obtenção dos resultados. Na indexação realizada pelo protótipo foram seguidas
somente as etapas necessárias à obtenção de índices razoavelmente eficientes e que permitam a
realização das consultas. Dentre estas, propostas por Salton [31] e Baeza-Yates [2], foram
utilizadas a Análise Léxica, que identifica as palavras no texto através das seqüências de
caracteres e a Eliminação de Stopwords, que evita que façam parte dos índices palavras que são
inerentes à linguagem e não ao conteúdo específico dos documentos. A lista de stopwords
(stoplist) em língua inglesa foi obtida em ftp://.cs.cornell.edu/pub/smart/english.stop e inclui
preposições, conjunções e artigos.
Antes de encerramos este trabalho gostaríamos de ressaltar a viabilidade de utilizar o Modelo
Vetorial, juntamente com a Teoria das Coordenadas Paralelas, para representar qualquer tipo de
informação que possa ser expressa em um vetor. Isto permite a aplicação deste estudo em
diversas áreas do conhecimento e não somente na recuperação de documentos textuais como foi
aqui mostrado.
6. REFERÊNCIAS BIBLIOGRÁFICAS
21
1 AMAIA, L. F. Criando gráficos 2D com o Gnuplot. Disponível em
http://latt.if.usp.br/fma215/galeria/lfamaia. Acesso em: ago 2001.
2 BAEZA-YATES, R.; RIBEIRO-NETO, B. Modern Information Retrieval. New York:
ACM Press,1999. 513p.
3 BERRY, M. W.; BROWNE, M. Understanding Search Engines: mathematical modeling and
text retrieval. Philadelphia: Siam, 1999.
4 BROWN, J. R. Visualization and scientific applications. In Earnshow, R. ; Vince, J.; Jones
H. (eds). Visualization & Modeling, Academic Press, Cambridge, 1997. p. 1-11.
5 CAMARÃO, P. C. B. Glossário de Informática. Rio de Janeiro: LTC Editora, 1998.
6 CARDOSO, J. I-Lib, uma proposta de interface personalizável para biblioteca digital.
Porto Alegre: Dissertação de Mestrado em Ciência da Computação, Faculdade de Informática,
PPGCC, PUCRS, 2000.
7 CARVALHO, J. G. Coordenadas Paralelas: Uma Metodologia para Visualização em 3D.
Porto Alegre: Dissertação de Mestrado em Ciência da Computação, Faculdade de Informática,
PPGCC, PUCRS, 2000.
8 CHEN, H. The Vocabulary Problem in Collaboration. Disponível em
http://www.ai.bpa.arizona.edu/papers. Acesso em: jun 2000.
9 CIANCONI, R. Requisitos Mínimos para Gerenciamento e Recuperação de Textos e
Imagens. In: Condex 94, Sucesu, Rio de Janeiro, 1994.
10 CLEVERDON, C. Optimizing convenient online access to bibliographic databases, in
Document Retrieval Systems. London: Ed. Tailor Graham, 1988, p. 32-41.
11 COWIE, J.; LEHNERT, W. Information Extraction. Communications of the ACM, New
York: ACM Press, v.39, n.1, p. 92-101, jan 1996.
12 CROFT, B. What do people want from information retrieval?. Disponível
em
http://www.cnri.dlib/november95-croft. Acesso em: jun 2000.
13 CROSS, V. Fuzzy Information Retrieval. Journal of Intelligent Information System,
Boston, v.3, n.1, p. 23-56, fev, 1994.
14 DATE, C.J. Introdução a Sistemas de Bancos de Dados. Rio de Janeiro: Ed. Campus, 1991.
674 p.
15 FERREIRA, J. R. A Biblioteca Digital. Disponível em
http://www.usp.br/geral/infousp/rincon/rincon.htm. Acesso em: jun 2000.
16 GONZALEZ, M. Recuperação e Extração de Informação. Porto Alegre: Trabalho da
Disciplina de Processamento da Linguagem Natural. Faculdade de Informática, PPGCC,
PUCRS, 1999.
17 GERSHON, N. ; EICK, S. G. Visualization’s new tack: Making sense of information. IEEE
Spectrum, November, p. 38-56, 1995.
18 GERSHON, N. From Perception to Visualization, In Scientifc Visualization, 1994,
Advances and Challenges, Ed: L. Rosenblum, R. A. Earnshaw, J. Encarnacao, H. Hagen, A.
Kaufman, S. Klimenko, G. Nielson, F. Post, D. Thalmann, Academic Press. In DOMIK,
Gitta. Tutorial on Visualization. University of Paderborn. Paderborn Germany. 1996.
22
Disponível em http://www.dcc.ufba.br/mat056/hypervis/domik/folien.html. Acesso em: ago
2001.
19 GERSHON, N. ; EICK, S. G. Information visualization. IEEE Computer Graphics and
Applications. jul / ag, 1997, p. 29-31.
20 HABER, R. B.; MACNABB, D. A. Visualization idioms: A conceptual model for scientific
visualizations systems. In Visualization in Scientific Computing, p. 74-93, Los Alamitos:
IEEE Computer Society Press, 1990.
21 HEUSER, C A. Projeto de Banco de Dados. Porto Alegre: Sagra Luzzato, 2000.
22 INSELBERG, A. Don´t Panic ... just do it in Parallel! Appeared in Comp.Stat. 14:53-77,
1999.
23 INSELBERG, A. Multidimensional Detective. InfoVis Conf. ´97 Proc. 100-107 IEEE
Computer Society.
24 KENT, A. Manual de Recuperação Mecânica da Informação. Ed. Polígono, 1972. 427 p.
25 KOWALSKI, G. Information Retrieval Systems: Theory and Implementation. Boston:
Kluwer Academic Publishers, 1997. 282 p.
26 Library of the Future. Series third Edition 1991-1996. World Library. Inc.
27 Luzzardi, P. R. Visualização de Informações. Porto Alegre: Exame de qualificação em
Ciência da Computação. PPGCC, UFRGS, 2001.
28 MCCORMIC, B. H. et al. Visualization in scientific computing. Computer Grafics vol. 21,
Nº 6, Nov 1987, p. 1-14, in DOMIK, Gitta. Tutorial on Visualization. University of
Paderborn.
Paderborn
Germany.
1996.
Disponível
http://www.dcc.ufba.br/mat056/hypervis/domik/folien.html. Acesso em: ago 2000.
29 MEADOW, C. T.; BOYCE, B. R.; KRAFT, D. H. Text Information Retrieval Systems. San
Diego: Academic Press, Second Edition, 2000.
30 OLIVEIRA, H. M. Seleção de Entes Complexos Usando Lógica Difusa. Porto Alegre:
Dissertação de Mestrado em Informática. Faculdade de Informática. PPGCC, PUCRS, 1996.
31 SALTON, G. Introduction to Modern Information Retrieval. New York: McGraw Hill
Book,1983, 448 p.
32 SALTON, G.; BUCLEY, C. Term Weighting Approaches in Automatic Text Retrieval.
Techinical Report. New York: Department of Computer Science, Cornell University, 1987.
33 SALTON, G. The State of Retrieval System Evaluation. Technical Report p. 91-1206. New
York: Department of Computer Science, Cornell University, 1991.
34 SCHATS, B. Information Retrieval in Digital Libraries: bringing search to the net. Science,
vol. 275, 1997.
35 SCHMID, C.; Hinterberger, H. Institute for Scientific Computing Swiss Federal Institute of
Tecnology (ETH), Zurich. Comparative multivariate visualization across conceptually
different graphic displays. Published in Proceedings of SSDBM’ 94, September 28-30, 1994
in Charlottesville, VA.
23
36 TÁLAMO, M. G. M.; LARA, M. L. G.; KOBASHI, N. Y. Contribuição da Terminologia para
Elaboração de Tesauros. Ciência da Informação, Brasília, v.25, nº 3, p.197-200, 1992.
37 WIVES, L. K. Um estudo sobre Agrupamento de Documentos Textuais em
Processamento de Informações não Estruturadas Usando Técnicas de “Clustering”.
Porto Alegre: Dissertação de Mestrado em Ciência da Computação. Faculdade de
Informática, PPGCC, UFRGS, 1999.
38 WIVES, L. K.; LOH, S. Hiperdictionary: a knowledge discovery tool to help information
retrieval. In: String Processing and Information Retrieval – A South American Symposium,
Spire, 1998.
39 WIVES, L. K.; LOH, S. Recuperação de Informações Usando a Expansão Semântica e a
Lógica Difusa. In: Congreso Internacional en Ingenieria Informatica, ICE,1998. Buenos
Aires: Universidad de Buenos Aires, 1998.
40 WONG, P. C.; BERGERON, R. D. 30 Years of Multidimensional Multivariate
Visualization. In Nielson, G. M., Hagen, H.; Muller, H. Scientific visualization: overviews,
methodologies, and techniques. Los Alamitos, California, 1997, 400p.