7HFQRORJLDVGH'HVFREHUWDGH&RQKHFLPHQWRHP,QIRUPDo}HV7H[WXDLV
ÇQIDVHHP$JUXSDPHQWRGH,QIRUPDo}HV
Leandro Krug Wives
(Doutorando PPGC/UFRGS)
[email protected]
Stanley Loh
(Doutorando PPGC/UFRGS, UCPEL, ULBRA)
[email protected]
Programa de Pós-graduação em Ciência da Computação
Universidade Federal do Rio Grande do Sul
http://www.inf.ufrgs.br
Este artigo tem como objetivo apresentar a área de Descoberta de Conhecimento em Textos,
dando uma visão geral dos conceitos e técnicas por ela envolvidas. As seções iniciais apresentam
sua origem e relacionamento com outras áreas da Ciência da Computação. Após, são
apresentados os tipos de descoberta possíveis e já desenvolvidos na área. Em seguida, o
Agrupamento (clustering), que é uma técnica vastamente utilizada para minerar informações
textuais e descobrir conhecimento, é detalhada. Este artigo também discute algumas aplicações
úteis para a teoria apresentada, assim como algumas direções de estudo e pesquisa ainda
necessárias para o aperfeiçoamento da área.
,1752'8d®2
O acesso aos meios de distribuição de informação está cada vez mais facilitado. Com o passar dos anos, um
número cada vez maior de pessoas consegue, facilmente, disponibilizar e acessar informações de qualquer outra
pessoa em qualquer parte do mundo. Atualmente, não só as pessoas mas também as empresas passaram a
disponibilizar seus produtos nestes meios de distribuição, expandindo seus mercados de uma forma globalizada e
maximizando seus lucros. Com isso, a quantidade de informações que uma pessoa tem acesso atualmente é
muito grande e cresce a cada momento. Essa quantidade de informações, além de ser grande, está disposta de
forma desorganizada e não padronizada, o que dificulta a sua localização e acesso. Todos estes fatores acabam
dificultando o tratamento e o entendimento das informações, ocasionando um problema conhecido por
sobrecarga de informações [4].
Todos os problemas relacionados à localização e ao acesso de informações são estudados por uma disciplina
denominada Recuperação de Informações (Information Retrieval) [32]. Já os problemas relacionados ao
entendimento, resumo e tratamento de informações (transformando-as em conhecimento útil e aplicável) são
discutidos por uma área denominada Descoberta de Conhecimento em Textos (Knowledge Discovery from Texts)
[12] ou ainda Mineração de Textos (Text Mining). Apesar dos dois termos serem utilizados como sinônimos na
literatura, a mineração é, na verdade, uma das técnicas de descoberta de conhecimento, sendo esta última,
portanto, mais abrangente.
Nas seções iniciais este artigo apresenta uma visão geral da área de descoberta de conhecimento em textos e suas
áreas associadas. Após, são mostrados os tipos de descoberta de conhecimento existentes na literatura. Em
seguida, o agrupamento (clustering) de informações, que é um dos tipos de descoberta de conhecimento, é
detalhado. Finalmente, as aplicações das técnicas mostradas são comentadas, assim como os problemas ainda
existentes.
5(&83(5$d®2 '( ,1)250$d¯(6
A tarefa de recuperar informações não é nova. Essa é uma necessidade que surgiu junto com as grandes
bibliotecas, há milhares de anos, pois as pessoas necessitavam, de alguma forma, localizar as informações mais
relevantes para as suas necessidades.
Atualmente, apesar do processo de armazenamento de informações estar evoluindo, onde cada vez mais
informações são portadas para meios eletrônicos, o processo de localização e recuperação de informações
continua existindo, e deve ser aprimorado a fim de adaptar-se às novas características destes meios de
armazenamento (exemplo: falta de padronização e distribuição sem controle).
A área de Recuperação de Informações, que tem raízes comuns com a Biblioteconomia, é a área que preocupa-se
em estudar esses novos meios de distribuição e identificar as melhores técnicas de armazenamento e localização
das informações nestes meios.
'(6&2%(57$ '( &21+(&,0(172 A descoberta de conhecimento (genérica) não é uma área nova da computação. Ela surgiu na Inteligência
Artificial [17] e preocupava-se não só em descobrir conhecimento, mas sim, também, em descobrir formas de
aquisição e armazenamento deste conhecimento.
Com o tempo, com o advento dos Sistemas de Gerenciamento de Bancos de Dados (SGBDs) [18], os
pesquisadores da área de Sistemas de Informação (mais especificamente, de Bancos de Dados) passaram a
pesquisar novas aplicações para as informações armazenadas nestes bancos de dados. Ou seja, pensavam que,
além das informações tradicionais armazenadas nestes sistemas, poderiam descobrir informações implícitas (que
não estavam disponíveis de forma clara) que também pudessem ser úteis para as empresas.
Com isso, passaram a surgir os primeiros sistemas de análise de dados e de mineração de dados relacionais,
dando início às pesquisas em áreas como a de Mineração de dados, surgindo novas ferramentas para
Processamento Analítico de Dados (Enterprise Analitical Systems, OLAP) e conceitos (Armazéns de dados ou
Data Warehouses).
Com o advento e a popularização da Internet, informações menos formais (emails, chats, news-groups, páginas
WEB) começaram a surgir e serem armazenadas. Os de descoberta de conhecimento existentes já não eram
capazes de trabalhar com esse novo tipo (na verdade, uma nova estrutura) de informações. Todos estes sistemas
trabalhavam com dados estruturados (exemplo: dados relacionais dispostos em tabelas de um banco de dados) e
não estavam preparados para manipular dados menos estruturados como os que iniciavam a circular pela
Internet.
Logo, sistemas foram criados ou adaptados para que comportassem esse tipo de dado desestruturado – o texto.
Inicialmente, muitos conceitos e técnicas foram re-aproveitados, porém, alguns problemas impediam sua
aplicação direta. Isso ocasionou o surgimento de um novo ramo de pesquisas na área de descoberta de
conhecimento: o ramo da descoberta de conhecimento em textos (ou simplesmente KDT, de Knowledge
Discovery from Texts), que estuda técnicas específicas para esse tipo de informação. Estas técnicas são muitas
vezes, mais trabalhosas, e são o assunto principal deste artigo.
Porém, antes de detalhar cada um destes novos conceitos e técnicas, é necessário deixar claro o que os estudiosos
da área entendem por conhecimento. Na verdade, conhecimento é um conceito muito abstrato que muitas vezes é
utilizado como sinônimo de informação. Porém, apesar de parecerem ter o mesmo significado, há algumas
diferenças nem tão sutis entre estes dois conceitos.
Rosa Viccari [36], por exemplo, considera que informação é a seleção e organização dos dados para um fim
determinado (é a interpretação dos dados), enquanto que o conhecimento é formado por informações (na forma
de fatos) e regras ou heurísticas que permitam derivar outras informações novas. Bell [27], acredita que
informação é o processamento de dados no sentido amplo, e conhecimento são fatos e idéias organizadas,
apresentando um julgamento racional ou um resultado experimental. Já para [1], informação são os dados
interpretados, com significado. Este significado pode ser diferente para diferentes pessoas, sendo então
necessário um intérprete dentro de um contexto e com um propósito. Já o conhecimento é o que permite e o que
é necessário para esta interpretação. O conhecimento pressupõe que a informação foi aprendida e incorporada
nos recursos de raciocínio, sendo portanto o resultado de uma nova informação adquirida. Este conhecimento
tem por função transformar dados em informação (por interpretação), derivar novas informações das existentes
(por elaboração) e adquirir novo conhecimento (pelo aprendizado).
Ou seja, o conhecimento só é útil quando pode ser explorado para que as pessoas alcancem seus objetivos [22].
Com isso, pode-se dizer que o conhecimento é subjetivo e depende muito do usuário, pois o que pode ser
adquirido por um pode não ser por outro (por não interessar, por já ter sido adquirido ou porque o usuário não
tem condições de adquiri-lo). Por este motivo, alguns estudiosos sugerem que o conhecimento deve ser adquirido
de forma construtivista (e não positivista), onde o processo de aquisição é guiado por hipóteses, num processo
interativo homem-máquina [25].
Resumindo, o que distingue o conhecimento de um algoritmo aplicado a dados é o não-determinismo, ou seja, o
conhecimento pode ser usado para gerar e avaliar novas hipóteses, sugerir soluções, gerar explicações, críticas,
justificativas e fazer inferência.
'(6&2%(57$ '( &21+(&,0(172 (0 7(;726
A evolução natural da área de Recuperação de Informações teve como conseqüência o surgimento da área de
Descoberta de Conhecimento em Textos. Assim, ao invés de encontrar os textos que contenham informações e
deixar que o usuário mesmo procure o que lhe interessa, a nova área se preocupa em encontrar informações
dentro dos textos e tratá-las de forma a apresentar ao usuário algum tipo de conhecimento útil e novo. Mesmo
que tal conhecimento novo não seja a resposta direta às indagações do usuário, ele deve contribuir para satisfazer
as necessidades de informação do usuário. A idéia é aproveitar todo o conhecimento humano que há em textos
escritos, tais como dicionários, manuais, enciclopédias, guias, etc.
Apesar do termo Descoberta de Conhecimento em Textos ser novo, tendo sido utilizado pela primeira vez por
Ronan Feldman [12], já há algum tempo, muitos esforços tem sido despendidos para tentar resolver problemas
análogos. Com isso, podem ser encontrados outros termos na literatura que são relevantes ao mesmo contexto.
Seguem alguns exemplos:
•
Busca de Informação (Information Seeking): utilizado para descrever qualquer processo pelo qual usuários
procuram obter informação a partir de sistemas de informação automatizados, incluindo a busca de
informações em textos [26];
•
Recuperação de Conhecimento (Knowledge Retrieval): difere de “recuperação de documentos” e de
“recuperação de dados”, porque usa menos pré-codificação e requer mais poder de inferência [19].
Segundo o ponto-de-vista de Ronan Feldman [12], a área de Descoberta de Conhecimento em Textos (KDT)
pode ser entendida como a aplicação de técnicas de Descoberta de Conhecimento em Bancos de Dados
(Knowledge Discobery in Databases - KDD) sobre dados extraídos de textos (não necessariamente valores
numéricos, mas podendo ser também valores nominais, como palavras do texto).
A descoberta de Conhecimento em Bancos de Dados pode ser definida como um processo não-trivial de
informação implícita, previamente desconhecida e potencialmente útil para o usuário [14]. Esta informação
implícita, geralmente, nada mais é do que um conjunto de padrões válidos, novos, úteis e compreensíveis ao
usuário [11b]. Sendo assim, KDT pode ser definido como o processo de extração não-trivial de informação
implícita, previamente desconhecida e potencialmente útil, contida em textos (e não na forma estruturada). Este
processo inclui técnicas e ferramentas inteligentes e automáticas para auxiliar pessoas em analisar volumes
grandes de dados para garimpar conhecimento útil.
Portanto, as ferramentas de descoberta de conhecimento (em geral) devem ser capazes de descobrir informações
escondidas (geralmente inesperadas), extraindo conhecimento na forma de regras ao observar padrões nos dados.
Entretanto, cabe salientar que KDT não inclui somente a aplicação das técnicas tradicionais de KDD, mas
também qualquer técnica nova ou antiga que possa ser aplicada no sentido de encontrar conhecimento em
qualquer tipo de texto.
$3/,&$d¯(6
As aplicações de sistemas de descoberta de conhecimento em textos são inúmeras. Qualquer domínio que utilize
intensivamente textos não-estruturados (documentos escritos), tal como as áreas jurídicas e policiais, os cartórios
e órgãos de registros, empresas em geral, etc., podem beneficiar-se destes sistemas.
Primeiramente, os usuários da Internet podem ser beneficiados, já que o problema da sobrecarga de informação,
ocasionado pela disponibilidade de volumes grandes de informações e pela falta de ferramentas adequadas para
encontrar informações úteis ou desejadas, pode ser minimizado.
Além disso, atualmente, devido à globalização do mercado de consumo, tais sistemas podem descobrir
estratégias de empresas concorrentes e auxiliar empresas a posicionarem-se melhor no mercado.
(7$3$6 '2 352&(662 '( '(6&2%(57$ '( &21+(&,0(172
A descoberta de conhecimento é um processo grande, envolvendo diversas etapas que vão desde a limpeza dos
dados, passando pela aplicação de um algoritmo de extração e finalizando com a análise e interpretação dos
resultados [11b]. Salientando o que já foi dito anteriormente, a Mineração de Dados é menos abrangente do que
a descoberta de conhecimento. Ela é, na verdade, a parte do processo responsável pela aplicação de algoritmos
de extração de padrões nos dados.
Basicamente, as etapas mais importantes do processo de descoberta são as seguintes:
1.
Definição de objetivos (compreensão do domínio);
2.
Seleção de um subconjunto de dados;
3.
Pré-processamento ou limpeza dos dados, com o intuito de remover ruídos e preparar o dados;
4.
Redução ou projeção dos dados (escolha de características relevantes para a análise);
5.
Escolha da técnica, método ou tarefa de mineração;
6.
Mineração;
7.
Interpretação dos resultados, podendo retornar-se aos passos anteriores;
8.
Consolidação do conhecimento descoberto (documentação ou incorporação dos dados no sistema).
Vale salientar que a descoberta é uma atividade tipicamente iterativa e interativa, com aplicação repetida de
métodos de mineração e interpretação dos resultados pelo usuário.
7,326 '( '(6&2%(57$ '( &21+(&,0(172 (0 7(;726
A seguir, são discutidas várias abordagens ou técnicas para descoberta de conhecimento em textos, extraídas da
literatura. As abordagens de descoberta discutidas permitem extrair conhecimento tanto na forma de informações
(por mecanismos de dedução) quanto na forma de regras (por indução).
'(6&2%(57$ 75$',&,21$/ $3Ð6 (;75$d®2
A descoberta considerada tradicional é a mais simples, pois utiliza técnicas já testadas e consagradas1. Nesta
abordagem, os dados são extraídos dos textos e formatados em bases de dados estruturadas, com o auxílio de
técnicas de Extração de Informações (EI). Depois, são aplicadas técnicas e algoritmos de KDD (mineração de
dados estruturados), para descobrir conhecimento útil para o usuário..
Com base em [8], pode-se dividir tal processo nos seguintes passos:
1.
tratar o problema de erros de digitação nos textos do universo considerado;
2.
recuperar documentos textuais que contenham as informações a serem estruturadas;
3.
extrair as partes que interessam dos documentos recuperados;
4.
extrair as informações destas partes com técnicas de EI;
5.
estruturar as informações coletadas para um formato próprio;
6.
extrair padrões nos dados coletados, com técnicas de descoberta de conhecimento;
7.
formatar a saída para o usuário (por exemplo, em linguagem natural).
Variações deste processo podem ser encontradas na literatura, seguindo, porém, a mesma abordagem.
'(6&2%(57$ 325 (;75$d®2 '( 3$66$*(16
O termo Extração de Passagens foi escolhido para designar um novo tipo de descoberta, situado entre a
recuperação de informações por passagens e a extração de informações. Esta nova abordagem visa encontrar
informações específicas, mas de forma um pouco mais independente de domínio do que as ferramentas
tradicionais de extração.
Neste tipo de descoberta, o usuário pode utilizar regras gerais (formas de procura previamente definidas e
comuns a vários textos) ou ele mesmo definir suas regras. Por exemplo, para encontrar a passagem de um texto
que contenha seu objetivo, o usuário pode procurar por frases onde a palavra “objetivo” apareça (ou seus
sinônimos) ou então procurar por passagens que contenham outros termos, os quais possam “cercar” um possível
objetivo (por exemplo, as palavras “definiu-se”, “apresenta-se”, “será discutido”, etc).
1
As técnicas tradicionais de KDD podem ser vistas com mais detalhes em [2].
A descoberta por extração de passagens auxilia usuários a encontrar detalhes de informação, sem que este
precise ler todo texto. Entretanto, ainda assim, é necessário que o usuário leia e interprete as partes do texto que
forem recuperadas para extrair a informação desejada.
Esta abordagem difere da extração de informações pois permite ao usuário levantar hipóteses e formas de
procura de informações em tempo de execução, não sendo necessário um grande esforço de engenharia do
conhecimento (para definir formas de procura), nem um profundo conhecimento prévio do texto e de sua
estrutura.
'(6&2%(57$ 325 $1É/,6( /,1*hÌ67,&$ Nesta abordagem, informações e regras podem ser descobertas através de análises lingüísticas a nível léxico,
morfológico, sintático e semântico. Existem diversos trabalhos que utilizam alguma técnica de análise lingüística
para descobrir conhecimento.
Estes trabalhos mostram que é possível descobrir generalizações escondidas, analisando padrões sintáticos [3].
Por exemplo, ocorrendo num texto as frases “x compra y” e “z compra y” e sabendo-se que numa hierarquia
auxiliar de conceitos está definido que w é pai de x e z, então deduz-se que “w compra y”. Há estudos que
utilizam classes de verbos (categorias) e examinam as funções dos objetos verbais (entrada, saída, etc.) a fim de
descobrir informações [30]. Algo similar pode ser feito com o intuito de transformar textos em diagramas de
fluxo de dados (DFD’s) [35]. Neste caso, a análise lingüística permite descobrir a seqüência, o tipo dos
processos (entrada, saída, transformação, leitura, etc.) e as relações entre eles (saída de um = entrada de outro).
Há estudos que conseguem inferir relações de tempo [16] e estudos que conseguem descobrir relações
conceituais (definições, exemplos, partições e composições) utilizando técnicas de reconhecimento de padrões
léxicos e sintáticos [BOW96].
'(6&2%(57$ 325 $1É/,6( '( &217(Ó'2 Semelhante aos dois tipos anteriores, a descoberta por análise de conteúdo investiga lingüisticamente os textos e
apresenta ao usuário informações sobre o seu conteúdo.
Entretanto, existem algumas diferenças importantes. A diferença em relação a descoberta por análise lingüística
é que, na análise de conteúdo, há maior esforço no tratamento semântico dos textos, passando em muito o limite
léxico-sintático. Em relação à extração de passagens, a diferença é que, aqui, o objetivo é encontrar o significado
do texto pretendido pelo autor ao invés de partes ou informações específicas.
O conteúdo, neste caso, pode ser o tema ou assunto do texto, ou então um índice ou resumo [MOL94]. Dois tipos
de conteúdo podem ser identificados: o semântico (referencial) e o pragmático (intencional). Essa identificação
permite inferir e registrar o significado dos documentos.
Esse tipo de identificação e inferência é trabalhoso e necessita de apoio de outras áreas, tais como:
•
a psicologia cognitiva: que estudo os processos e estruturas mentais para aquisição, processamento e uso de
conhecimento ou informação;
•
a lógica: estudo de estrutura, fundamentação e uso de expressões de conhecimento, raciocínio
•
a lingüística: para o estudo das estruturas sintáticas e o significado dos elementos.
Além disto, para compreender o significado de um texto, é preciso analisar o contexto de produção e de
recepção. O conteúdo não é função somente de características do texto. A interpretação depende do interesse do
autor e do leitor. A compreensão combina informação explícita do texto e conhecimento prévio (algumas
informações devem ser pressupostas).
Este conhecimento extra-texto inclui saber quem é o autor e quais suas intenções (quem escreve o faz pensando
numa classe de leitor). Cada tipo de texto exige um tipo diferente de análise. Por exemplo, textos científicos
geralmente incluem um objetivo, uma metodologia, os resultados e as conclusões.
'(6&2%(57$ 325 680$5,=$d®2 A sumarização é a abstração das partes mais importantes do conteúdo do texto. Este tipo de descoberta utiliza as
técnicas dos tipos anteriores. Entretanto, a ênfase maior aqui, como o próprio nome diz, é a produção do resumo
ou sumário.
Existem diversas abordagens para esta técnica. Uma delas é apresentada por Mike [21], que consegue gerar
resumos em tempo de execução através de interações com o usuário. O tamanho do resumo e as partes que vão
compô-lo podem ser definidos pelo usuário, dependendo do interesse deste (seu ponto-de-vista).
A análise do texto é feita sobre sua organização (seções, parágrafos, títulos, sub-títulos), sobre as sentenças que o
compõem (análise morfológica e sintática com uso de um dicionário), sobre a estrutura do texto (conetivos
lógicos, expressões idiomáticas entre parágrafos e frases) e com a extração de papéis ou funções (roles)
semânticas por tags2 (para cada função, são definidos tags específicos; por exemplo, para achar tópicos, procurar
pelo tag “... é explicado”).
Já McKeown [20] apresenta técnicas e ferramentas para analisar diversos artigos sobre um mesmo evento e criar
um resumo em linguagem natural. São extraídas informações de partes dos textos (por técnicas tradicionais de
extração de informações), as quais são estruturadas em slots (pares atributo-valor, representando internamente
conceitos).
A saída em linguagem natural é gerada em formatos padrões preenchidos com os slots. Entretanto, ao invés de
unir simplesmente as frases, são utilizados conetivos lógicos e palavra-chave (termos lingüísticos) para formar
resumos mais complexos.
As representações dos textos (em slots) são analisadas para encontrar similaridades e diferenças de informações.
Então, para combinar as informações extraídas de artigos diferentes, são aplicados operadores semânticos sobre
os slots para exprimir contradição, adição, refinamento de informação, concordância, falta de informação, etc.
Tais operadores também decidem que informações incluir no resumo final, com base em graus de importância,
determinados segundo critérios tais como: informações que aparecem em mais artigos tem maior grau. A ordem
de apresentação das frases também é definida automaticamente, respeitando as restrições de espaço definidas
pelo usuário da ferramenta (algumas frases podem não ser apresentadas).
'(6&2%(57$ 325 $662&,$d®2 (175( 3$66$*(16
Este tipo de descoberta busca encontrar automaticamente conhecimento e informações relacionadas no mesmo
texto ou em textos diferentes. Esta abordagem combina a recuperação de informações por passagens com a
recuperação contextual.
Sua aplicação imediata está na definição automática de links nos sistemas de hipertexto. Entretanto, a vantagem
deste tipo de descoberta é apresentar ao usuário partes de textos que tratam do mesmo assunto específico
(detalhe de informação e não conteúdo geral).
Saliminen [31] discute trabalhos sobre conversão automática de textos para hipertextos (geração de links entre as
partes). Spark-Jones [33] sugere a análise de um tipo especial de link, através de marcas (tags) do tipo “veja
também”, como referência de assuntos.
Salton [15] apresenta como novidade a distinção entre relações lógicas entre textos (capítulos, seções, etc.) e
relações semânticas. Vetores (contendo termos e pesos) são sugeridos para representar cada parte dos textos. Há
um processo de avaliação de similaridade entre as partes (vetores) e a posterior associação entre as partes
(geração dos links).
Salton também salienta alguns problemas, como o caso onde documentos sobre um mesmo assunto possuem
termos diferentes (quase-sinônimos). Na prática, espera-se uma certa coincidência de termos em documentos
similares. Por isto também, a avaliação da similaridade pode ser feita por partes (parágrafos) do documento, para
eliminar ambigüidades (uso de contexto local).
Para minimizar o problema dos quase-sinônimos, Jacobs [15] propõe extrair relações entre documentos com
base em afinidades léxicas (mais de um termo associado, como já discutido nas técnicas de representação de
documentos). Estas afinidades léxicas também podem servir como guia para o usuário navegar pelos
documentos, já que permitem interpretar o conteúdo do documento.
'(6&2%(57$ 325 /,67$6 '( &21&(,726&+$9(
Neste tipo de descoberta a idéia é apresentar uma lista com os conceitos principais de um texto. Essa abordagem
é defendida por diversos autores, e seu ponto principal está na idéia de que o significado de um texto não é
determinado por sua leitura linear, mas sim, por uma análise do conjunto de elementos léxicos (palavras-chave)
mais importantes do mesmo [24].
2
Tags são marcas, geralmente de controle, similares aos comandos HTML (<HEAD>, por exemplo).
Para identificar este conjunto de elementos léxicos podem ser utilizadas técnicas simples de extração de termos
mais freqüentes ou ainda técnicas mais complexas de extração de conceitos (frases ou conjuntos de palavras
relacionadas).
Um exemplo de técnica complexa seria a identificação de uma lista de termos próximos (antes e depois), os
quais permitiriam a análise do conteúdo por quase-frases [24]. A idéia é mover-se das palavras para as frases
pela repetição dos elementos no texto. Depois o usuário pode ver o contexto (frases inteiras como no texto
original). A proximidade é dada por propriedades estatísticas e não por análise sintática ou gramatical. Esta
aproximação léxica é vantajosa para uma leitura e uma interpretação rápida de textos grandes. Esta técnica
poderia ser aprimorada com a utilização gráficos de conceitos (termos) ao invés de listas.
'(6&2%(57$ '( (6758785$6 '( 7(;726
Segundo Morris [23], determinar a estrutura de um texto ajuda a entender seu significado. Um texto não é um
conjunto aleatório de frases, mas deve haver uma unidade e também coesão, com as frases funcionando juntas
para a função do todo. A coesão se consegue com referências, conjunções e relações semânticas.
Neste caso, as coesões léxicas de um texto são analisadas e o resultado desta análise são cadeias de termos
relacionados que contribuem para a continuidade do significado léxico. A identificação das cadeias léxicas é
feita pela determinação de seqüências de termos relacionados dentro de uma certa distância, seguindo a premissa
de que conceitos relacionados aparecem fisicamente perto.
Estas cadeias léxicas delimitam partes do texto que têm forte unidade de significado e ajudam também na
resolução de ambigüidades, além da identificação da estrutura do discurso.
Depois, as relações de coesão entre as partes são classificadas em categorias (reiteração, colocação, etc.).
Também são classificadas as relações de coerência entre sentenças (elaboração, suporte, causa, exemplificação) e
as relações de coesão entre os elementos (referência, elipse, substituição, etc.).
Um thesaurus3 é utilizado para determinar as relações que são significativas entre termos próximos, sendo
analisadas associações diretas, indiretas (transitivas só em primeiro grau) e categorias comuns de termos.
Um cuidado a ser tomado é que nem sempre as associações situacionais aparecem nos thesauri (por exemplo,
“luzes” e “carros”). Da mesma forma, termos novos e nomes próprios (que não aparecem no thesaurus) devem
ser relacionados por interpretação humana.
As cadeias léxicas são apresentadas de forma estrutural (na ordem do discurso), e não como uma lista das mais
freqüentes. Também é utilizado o contexto (frases inteiras) ao invés da representação interna (só termos chaves).
Tal forma dá indícios da estrutura intencional do texto, pois há relação entre as cadeias léxicas e as relações
intencionais.
'(6&2%(57$ 325 &/867(5,=$d®2 A técnica de clusterização (ou agrupamento ou generalização) procura separar automaticamente elementos em
classes que serão identificadas durante o processo (não há classes pré-definidas). Geralmente, esta técnica vem
associada com alguma técnica de descrição de conceitos, para identificar os atributos de cada classe.
A clusterização auxilia o processo de descoberta de conhecimento, facilitando a identificação de padrões
(características comuns dos elementos) nas classes. Isso porque a divisão em classes facilita a compreensão
humana das observações e o desenvolvimento subseqüente de teorias científicas.
A clusterização também pode ser utilizada para estruturar e sintetizar o conhecimento, quando este é incompleto
ou quando há muitos atributos a serem considerados, ou para extrair categorias dos textos.
As interpretações das classes identificadas devem ser feitas pelo usuário, os quais necessitam um pouco de
conhecimento do domínio. Entretanto, diferentes usuários são levados às mesmas interpretações. Estas
interpretações avaliam as associações entre termos (revelando o contexto semântico quase em linguagem
natural), a estrutura das coleções por análise da terminologia e a informação qualitativa sobre diferenças e
similaridades entre componentes ou classes.
3
Um tipo de dicionário, porém, contendo relacionamentos entre palavras e termos (estilo uma rede semântica).
'(6&2%(57$ 325 '(6&5,d®2 '( &/$66(6 '( 7(;726
Dada uma classe de documentos textuais (já previamente agrupados) e uma categoria associada a esta classe (por
exemplo, tema ou assunto dos textos), a descoberta por descrição procura encontrar as características principais
desta classe, as quais possam identificá-la para os usuários e distingui-las das demais classes.
Esta abordagem segue geralmente as técnicas para construção do centróide4 de classes e pode ser utilizada em
conjunto com a clusterização. Ela é diferente da abordagem por listas de conceitos-chave, porque descobre
características comuns em vários textos e não em um único texto.
Usando técnicas de tratamento de linguagem natural, é possível identificar uma categoria por sua descrição
distintiva mínima [9], ou seja, o menor conjunto de atributos e seus valores (expressos em termos do texto) para
discriminar um referente ou objeto de outras entidades.
Utilizando técnicas de indução automática (aprendizado de máquina) [6], é possível construir uma base de regras
capaz de identificar classes. Estas regras são descobertas analisando-se amostras de textos com categorias préassociadas. Os documentos são representados por vetores de palavras únicas e de pares de palavras.
'(6&2%(57$ 325 5(&83(5$d®2 '( ,1)250$d¯(6 As técnicas tradicionais de Recuperação de Informações (RI) também podem ser utilizadas em processo de
Descoberta de Conhecimento em Textos. Ao apresentar documentos com informações novas, a RI está
contribuindo para que o usuário aprenda novos conhecimentos. A RI é parte de um processo maior de
exploração, correlação e síntese de informação.
A RI tem valiosas contribuições a dar no processo de descoberta, principalmente possibilitando que usuários
encontrem soluções por analogias. Em muitas aplicações, os problemas e suas soluções estão armazenados em
textos, sem estrutura nenhuma, o que pode dificultar ao usuário encontrar informações para resolver seus novos
problemas.
As técnicas de RI podem ajudar apresentando documentos com visão geral das informações ou assuntos (RI
tradicional) ou apresentando partes de documentos com detalhes de informações (recuperação por passagens).
Também as ferramentas de RI por filtragem contribuem garimpando documentos interessantes para o usuário,
sem que este precise formular consultas.
'(6&2%(57$ 325 $662&,$d®2 (175( 7(;726 Diz-se que cada documento reporta um pedaço de descoberta científica [5]. Assim, a descoberta por associação
entre textos procura relacionar estas descobertas presentes em vários textos diferentes. As descobertas estão
presentes no conteúdo ou significado dos textos.
Esta abordagem é diferente do que acontece na descoberta por associação entre passagens, cujo objetivo é
somente relacionar partes de textos sobre o mesmo assunto. Na associação entre textos, a interpretação semântica
é fundamental.
O conhecimento novo pode emergir de inúmeros fragmentos individualmente não-importantes, sem relação no
momento em que foram elaborados ou adquiridos. Ele pode surgir de bibliotecas e laboratórios por processos de
correlação, síntese, exploração, recuperação e combinação.
McKeown [20] discute uma ferramenta que analisa diversos artigos sobre um mesmo evento e cria um resumo
em linguagem natural. São extraídas informações de partes dos textos (por técnicas tradicionais de extração de
informações), as quais são estruturadas em slots (pares atributo-valor, representando internamente conceitos).
As representações dos textos (em slots) são analisadas para encontrar similaridades e diferenças de informações.
Por exemplo, similaridades podem ser detectadas em dados de um mesmo slot, enquanto as diferenças por trocas
de valores no tempo (atualizações ou refinamentos de valores de um slot) ou valores contraditórios. As
informações extraídas dos artigos são combinadas para exprimir contradição, adição, refinamento de informação,
concordância, falta de informação, etc.
Davies [10] acredita que existe muita informação publicada e conhecida, mas que algumas conclusões a partir
destas informações só poderão ser descobertas recuperando estes documentos e notando as conexões lógicas
entre eles. Para este autor, a criatividade depende da formação de novas combinações e permutações de
4
O centróide é o termo dado a um conjunto de palavras que descrevem determinado objeto ou conjunto de
objetos.
conceitos, sendo que as respostas a consultas surgem pela combinação de dois textos que individualmente não
respondem, mas que juntos fornecem a informação necessária.
Davies [10] organizou algumas categorias de associação (este autor utiliza o termo “conhecimento público nãodescoberto”):
•
refutações ou qualificações escondidas de hipóteses: quando um trabalho prova o contrário de outro
(contradiz com provas), tendo sido publicados em lugares e/ou épocas diferentes;
•
inferências a partir de relações transitivas: quando “A causa B” e “B causa C”; por exemplo: “o óleo de
peixe é bom para a circulação” e “a síndrome de Raynaud está associada com a vaso-constrição”, sendo que
ninguém tinha feito tal relação antes e quem descobriu tal relação não era da área médica;
•
testes fracos cumulativos: hipóteses com várias explicações possíveis vão sendo acumuladas até formar uma
teoria forte;
•
soluções para problemas análogos (analogias): o estruturalismo acredita que é possível identificar certos
padrões de pensamento que são comuns, porque eles são uma conseqüência natural do modo como a mente
humana funciona;
•
correlações escondidas: combinação de conceitos (indexadores) em sistemas de RI.
Segundo Davies [10] ainda, os métodos de descoberta podem-se basear em classificações bibliográficas (por
exemplo, um thesaurus) e cita algumas possibilidades:
•
análise combinatória: processo automático de combinação de tópicos ou unidades para geração de unidades
e tópicos novos;
•
análise morfológica: enumeração de todas as possíveis soluções para um problema (em termos de
características).
Todos estes métodos citados fazem uso de análise léxica, como meio de descobrir as associações. Por exemplo,
pode-se inspecionar termos em títulos e no texto, para levantar idéias e hipóteses.
Entretanto, poucas ferramentas automáticas e concretas existem para este tipo de abordagem. O que geralmente
acontece é haver técnicas sistemáticas, empregadas por pessoas, mas que exigem ainda muita interpretação
humana.
'(6&2%(57$ 325 $662&,$d®2 (175( &$5$&7(5Ì67,&$6
Esta abordagem procura relacionar tipos de informação (atributos) presentes em textos, aplicando técnicas de
correlação estatística ou associação tradicional em KDD diretamente sobre partes do texto. Uma das diferenças é
que os valores para os atributos são partes do texto e não necessariamente dados extraídos por técnicas de
extração de informações.
Stanfill [15] defende o uso de análise estatística sobre textos, para encontrar estruturas em coleções de dados. As
principais técnicas utilizadas para julgar o que constitui estrutura são a clusterização e a teoria da probabilidade.
Feldman [13] marca documentos textuais com palavras-chave tomadas de um vocabulário controlado,
organizado em estruturas hierárquicas de tópicos. Existem tópicos pré-determinados para classificar as palavraschave, por exemplo: países, assuntos, pessoas, organizações, produtos das relações comerciais.
Algum conhecimento prévio do domínio é necessário para definir os tópicos. Entretanto, os valores textuais para
os tópicos são extraídos automaticamente do texto (simplesmente pela presença da palavra-chave).
Depois, ferramentas de descoberta procuram encontrar padrões na coleção de documentos por análise de
distribuições de palavras-chave. Os padrões interessantes geralmente são sub-conjuntos cujas distribuições são
diferentes do conjunto todo.
As consultas do usuário submetidas à ferramenta são hipóteses de conhecimento novo que devem ser avaliados
por interpretação humana, com base nas distribuições de palavras. Por exemplo, hipóteses possíveis são:
•
que proporção de documentos da Argentina estão marcados (labeled) com cada palavra dos tópicos: os
resultados serão apresentados em tabelas com as informações tópico, palavra e proporção;
•
qual a proporção de documentos marcados com UK e USA, por tópico: resultados com tópico e proporção;
•
comparação no tempo (separar duas coleções por tempo ou era): será necessário classificar datas em épocas
e as distribuições de palavras poderão ser apresentadas dentro de cada categoria;
•
proporção de documentos mencionando dois países: o que pode revelar uma guerra ou comércio forte.
Feldman [12] também discute a descoberta de associações (padrões de co-ocorrência) entre termos que marcam
textos.
Este tipo de abordagem não deixa de ser um tipo especial de RI, com uso intensivo de técnicas estatísticas sobre
os termos presentes nos documentos e algum conhecimento prévio do domínio (background knowledge).
Também pode ser considerada uma abordagem entre a estruturada e a não-estruturada, pois utiliza categorias
como atributos e palavras do texto como valores para os atributos. Entretanto, o usuário tem que definir o
objetivo ou hipótese a ser avaliado. Há ainda a possibilidade de uso desta abordagem também sobre campos
textuais de bancos de dados estruturados.
'(6&2%(57$ 325 +,3(57(;726
Um caso especial de descoberta utilizando técnicas de recuperação de informações (RI) é a descoberta com uso
de hipertextos. Nesta abordagem, a descoberta é exploratória e experimental, feita através de mecanismos de
navegação (browsing).
Com tais ferramentas, é possível expandir e comparar o conhecimento através dos links que relacionam as
informações, funcionando de modo análogo à mente humana (memória associativa).
A aprendizagem pode ocorrer acidentalmente e de forma cumulativa, não exigindo estratégias cognitivas. A
criatividade e a curiosidade guiam tal processo.
Tal abordagem é útil quando os problemas de falta de informação são mal-definidos e quando se quer explorar
novos domínios.
As técnicas de RI atualmente estão mais voltadas para o processo de recuperação do que para a compreensão.
Neste sentido, os sistemas de hipertextos podem facilitar as novas descobertas, permitindo ao usuário
complementar seu conhecimento com informações adicionais.
'(6&2%(57$ 325 0$1,38/$d®2 '( )250$/,6026
É possível representar o conteúdo dos textos em formalismos (como a lógica de predicados, por exemplo).
Assim, mecanismos de manipulação simbólica podem inferir novos conhecimentos, simplesmente por
transformações na forma. As representações resultantes podem ser depois transformadas para estruturas na
linguagem natural, facilitando a compreensão de usuários leigos no formalismo.
Geralmente as técnicas de dedução, comuns na área de Inteligência Artificial, executam bem este trabalho.
É possível deduzir conhecimento através da RI, fazendo inferências sobre o que já é conhecido. Textos são
recuperados e representados em formalismos internos. Depois, regras de transformações simbólicas são
aplicadas para manipular a forma, abstraindo o conteúdo. As novas representações geradas são hipóteses para
novos conhecimentos.
'(6&2%(57$ 325 &20%,1$d®2 '( 5(35(6(17$d¯(6
Um caso especial da descoberta por associação entre textos é a descoberta por combinação de representações. A
diferença é que os textos, antes de serem combinados, passam por um processo de representação interna. Então,
na verdade, não são os textos que são combinados, mas sim seus conteúdos, conforme o formalismo e as regras
internas.
A combinação de representações diferentes, permite que pontos de vista diferentes possam ser usadas para criar
novas representações e conseqüentemente novo conhecimento.
Os formalismos internos podem ser modelos conceituais ou tradicionais (por exemplo, o modelo relacional) ou
ontologias, linguagens baseadas em lógica, etc. Também podem ser usados mediadores, como comentado em
Integração Inteligente de Informações.
A saída do processo de combinação deve estar representada em linguagem natural, podendo ser usadas técnicas
de processamento de linguagem natural como as citadas anteriormente.
Grafos podem representar estruturas sintáticas de textos ou conteúdos mais complexos (como redes semânticas).
Estes grafos podem ser combinados por elementos comuns, gerando um grafo novo, hipótese de novos
conhecimentos.
Chen [5] sugere recuperar, juntar (assembling) e entender partes individuais nunca antes confrontadas (metáfora
do quebra-cabeça). Tal abordagem pode revelar novas conexões na literatura (relacionamentos escondidos,
padrões, analogias), através da combinação de partes que se completam.
Chen [5] discute um trabalho que combina resumos (textos curtos). Apesar de as informações de saída estarem
presentes nos textos, o resultado é novo, pois não é idêntico aos originais (é fato construído extraindo-se apenas
material relevante a partir de vários documentos).
Neste trabalho, é utilizada uma representação interna do significado dos documentos. Os textos são formatados
para uma linguagem natural restrita (inglês estilizado de acordo com padrões gramaticais). O formato padrão se
assemelha a:
(artigo) substantivo_1 verbo (artigo) substantivo_2
Os relacionamentos ternários são quebrados em binários.
Depois, estes formatos são representados para uma rede interna (tipo rede semântica), onde os nodos são
substantivos e as conexões são verbos.
O processo de comparação é feito por ativação dos nodos (spreading activation), onde as buscas vindas de duas
direções convergem em algum ponto no meio.
As redes são conectadas quando têm objetos em comum (nomes iguais mas com localizações diferentes). A rede
resultante é convertida para a linguagem natural restrita antes de ser apresentada ao usuário.
'(6&2%(57$ 325 &203$5$d®2 '( 02'(/26 0(17$,6
Esta abordagem procura representar documentos textuais e o estado de conhecimento do usuário (modelo mental
das informações) em um formalismo padrão, para após compará-los.
Se for possível verificar o que há nos documentos que falta no estado mental do usuário, então um conhecimento
novo foi descoberto.
O problema maior desta abordagem está na aquisição ou elicitação do conhecimento ou estado mental do usuário
para poder representá-lo.
Berkin [33] sugere que se utilizem a recuperação associativa (redes e hiperlinks) e o feedback de relevância
(reformulação da consulta para formar documento ideal).
O mesmo autor discute um sistema sem formulação de consulta, onde é feita a construção da imagem da
necessidade (ou estado de conhecimento) do usuário através de grafos, com os nodos representando documentos,
temas e autores e as ligações representando associações.
Nesta técnica, procura-se representar as propriedades estruturais da imagem e não meramente os termos ou
conceitos que a compõe. O usuário entra com frases narrativas sobre os seus problemas e uma análise de
associações é feita estatisticamente.
As premissas do autor são: os conceitos são representados por palavras, estão associados nos estados de
conhecimento individuais e ocorrem próximos dentro dos textos.
Ralha [28] discute o modelo computacional da memória humana definido por Hintzman. Neste modelo, cada
traço de memória é um registro de uma experiência ou episódio, representado por um vetor ou traço (uma lista
ordenada de atributos). O probe é uma representação ativa de uma experiência na memória primária. Cada traço
é ativado de acordo com sua similaridade ao probe. Os pesos ou valores dos atributos podem ser binários ou de 3
estados. A recuperação de traços é feita com base num ranking de similaridade.
Segundo Tazi [34], os leitores constróem uma representação mental da estrutura semântica do documento
enquanto lendo, formando uma hierarquia de proposições. Estas proposições são conectadas por relações
semânticas e podem ser representadas em meios tratáveis através de Grafos Conceituais de Sowa. Depois, estes
grafos podem ser comparados com as representações dos documentos para verificar a existência de novos
conhecimentos ou informações.
2$*583$0(172 '( ,1)250$d¯(6 7(;78$,6 &/867(5,=$d®2
O agrupamento de informações textuais tem como objetivo principal identificar documentos que possuam
alguma informação em comum e colocá-los em um grupo. De acordo com a Hipótese de Agrupamento (cluster
hypothesis) [29], é possível organizar uma série de documentos, dispostos de forma desorganizada, em grupos
ou conjuntos de documentos que possuam algo em comum (mesmo assunto), identificando uma certa
organização.
Este tipo de técnica é recomendada quando não há uma discriminação prévia de classes, sendo útil em casos
onde não há a possibilidade de alocar um especialista na tarefa de separação de objetos em classes
(manualmente).
É interessante deixar claro que este processo difere da classificação (ou categorização), que consiste em
identificar a classe a que pertence determinado objeto. No caso da classificação as classes (ou grupos) possíveis
para todos os objetos é conhecida, e deseja-se saber a que classe (ou grupo) determinado objeto enquadra-se
(dentre as classes já conhecidas).
Por haver esta necessidade de conhecimento prévio, a classificação necessita de duas etapas: uma etapa de
aprendizado, onde as classes são identificadas e caracterizadas, e uma etapa de classificação propriamente dita,
onde os elementos são identificados (classificados) de acordo com as classes existentes. Tendo-se esta visão, é
possível considerar a técnica de agrupamento como uma etapa (passo) anterior à classificação.
Portanto, informalmente, o objetivo genérico do processo de agrupamento é identificar os objetos que possuem
algo em comum (características em comum) e separá-los, colocando-os em grupos de objetos similares. Estes
objetos, antes de serem agrupados, podem ser os mais variados possíveis.
A este grupo de objetos similares dá-se o nome de aglomerado (cluster). Como definição mais formal, o
aglomerado de objetos pode ser definido como [37]:
•
Um aglomerado é um conjunto de entidades que são semelhantes, e entidades pertencentes a aglomerados
diferentes são diferentes;
•
Um aglomerado é uma agregação de pontos no espaço tal que a distância entre os pontos em um mesmo
aglomerado é menor que a distância entre pontos de diferentes aglomerados;
•
Os aglomerados podem ser descritos como regiões conexas de um espaço multidimensional que contém uma
grande densidade relativa de pontos. As regiões estão separadas umas das outras por regiões de baixa
densidade relativa de pontos.
7,326 '( $*583$0(172 7(;78$/
O agrupamento pode ser classificado de acordo com dois critérios: o primeiro em relação à forma como os
grupos são construídos e o segundo em relação à complexidade do tempo de execução do algoritmo.
Quanto à forma com a qual os grupos são constituídos, há dois tipos de agrupamento: o agrupamento por
partição e o agrupamento hierárquico [7].
No primeiro tipo de agrupamento, denominado por partição, os objetos são distribuídos em classes distintas, não
havendo relação direta entre as classes. Este tipo de agrupamento é denominado agrupamento de partição total
(flat partition) e os documentos são separados exaustivamente e colocados em grupos totalmente diferentes.
No segundo tipo, denominado partição hierárquica (hierarchic partition), o processo de identificação de grupos
é geralmente realimentado recursivamente, utilizando tanto objetos quanto grupos já identificados previamente
como entrada para o processamento. Deste modo, constrói-se uma hierarquia de grupos de objetos, estilo uma
árvore.
Quanto à complexidade em relação ao tempo de processamento, os algoritmos de agrupamento podem ser
considerados [37] constantes, lineares ou exponenciais de ordem quadrática.
Os algoritmos de tempo constante tem o objetivo de limitar o tempo máximo de processamento, ou ao menos
descobrir o tempo gasto por cada elemento e estimar um tempo ou número máximo de comparações a ser feito.
Geralmente limitam o tamanho ou o número de clusters. Porém, no estagio atual da tecnologia, não há
algoritmos de tempo constante que possam ser utilizados para processamento em tempo real (tempo constante
não significa, necessariamente, tempo real).
Os chamados de tempo linear possuem a característica de aumentar seu tempo de processamento de acordo com
o número de elementos. Este tempo, porém, ao aumentar, cresce de modo sutil e gradativa (não exponencial), já
que nem todos os elementos necessitam ser comparados com todos.
Os considerados quadráticos crescem exponencialmente, pois sempre que um elemento é adicionado ele deve ser
comparado com todos os outros, aumentando a quantidade de comparações entre os elementos.
7e&1,&$6 '( $*583$0(172
Existem diversas classes de técnicas de agrupamento. No caso de agrupamento de objetos textuais (documentos)
a classe mais estudada e utilizada é a chamada graph-theoretic, que baseia-se em grafos. É esta a classe
abordada e detalhada neste artigo. Por outro lado, a grande maioria das classes, mesmo as não abordadas aqui,
realizam as mesmas etapas básicas: a identificação e seleção de características, o cálculo de similaridades e a
identificação de aglomerados (clusters) – o agrupamento propriamente dito.
A primeira etapa identifica características nos objetos, ou seja, identifica palavras nos documentos e após
seleciona (globalmente ou localmente) aquelas que possuem maior grau de discriminação (que caracterizam
melhor o objeto). Como resultado desta etapa, são geradas listas de palavras (características) relevantes, que
identificam cada documento.
A segunda etapa identifica os graus de similaridade entre os objetos (documentos), utilizando para isso as listas
de características identificadas na etapa anterior. Como resultado desta etapa, obtém-se uma matriz que contém
os valores de similaridade entre todos os objetos. Quanto mais características em comum possuírem os objetos,
mais similares eles são.
Por fim, a etapa de agrupamento (em si) consiste em identificar correlações entre os elementos da matriz, de
acordo com as restrições impostas por cada algoritmo. Dependendo da técnica utilizada para a montagem da
matriz, e do algoritmo de agrupamento, todos os elementos devem ser comparados com todos, o que pode
classificar o algoritmo como sendo de ordem quadrática. Ao final desta etapa, tem-se os grupos e seus
respectivos elementos.
Estas etapas são detalhadas a seguir.
,'(17,),&$d®2 ( 6(/(d®2 '( &$5$&7(5,67,&$6
Para que os objetos possam ser analisados e comparados é necessário, primeiramente, identificar suas
características e selecionar aquelas que são mais marcantes (que caracterizam melhor o objeto). Em documentos
as características mais fáceis de serem identificadas são as palavras que eles contém.
Após terem sido identificadas as palavras do texto, passa-se a etapa de seleção de palavras relevantes. Estas
palavras mais relevantes são passadas para a etapa de cálculo de similaridade entre os objetos (documentos), que
gera uma matriz que contém o quanto cada documento é similar aos demais. Finalmente, o algoritmo de
identificação de grupos processa a matriz, gerando grupos de elementos mais similares. Estas etapas são
detalhadas a seguir.
,'(17,),&$d­2 '( 3$/$95$6 A técnica mais simples de identificação de palavras consiste em criar um analisador léxico que identifiquem os
tokens (palavras) pela simples detecção de um espaço ou pontuação entre os caracteres existentes em um texto.
Porém, pode-se refinar um pouco mais este analisador e definir o conjuntos de caracteres que determinada
palavra deve conter para que seja considerada uma característica de fato (algo similar a definição de um alfabeto,
estudado em disciplinas de Linguagens Formais). Por exemplo, poder-se-ia considerar que toda seqüência
constituída de um ou mais dos caracteres “abcdefghijklmnopqrstuvxyzàáéíóúâêîôûäëïöüç” seja uma palavra.
Esta restrição desconsidera toda palavra que contenha um caracter diferente dos definidos no conjunto anterior,
incluindo caracteres de controle e números. Dependendo da aplicação os números poderiam ser considerados
características relevantes. Para tanto, seria necessário aceitar seqüências de caracteres que não contenham os
caracteres anteriores e contenham somente os caracteres “1234567890”) e, eventualmente, entre estes, o caracter
“.” (ponto) ou “,” (vírgula) correspondentes aos números não inteiros.
Similarmente poderiam ser definidos outros tipos de palavras, como, por exemplo: datas, palavras compostas e
etc. Todos os demais caracteres e seqüências são ignorados.
É interessante também, após ter sido realizada a identificação de palavras, realizar uma etapa de limpeza (a fim
de eliminar erros ortográficos) e normalização de vocabulário (identificação de radicais, identificação de
sinônimos e substituição de pronomes pelos seus respectivos substantivos).
Finalmente, as palavras identificadas no processo são colocadas em uma lista de palavras do documento.
5(02d­2 '( 3$/$95$6 1(*$7,9$6
Nem todas as palavras identificadas no processo anterior podem ser consideradas relevantes como características
do documento. Muitas das palavras que aparecem em um documento são inerentes a linguagem utilizada e só
servem para auxiliar a construção da frase ou oração. Esse é o caso de preposições e conjunções, por exemplo.
Em casos onde o conjunto de documentos sendo trabalhado pertencer a uma única área, podem existir palavras
específicas do contexto, que aparecem em todos ou em quase todos os documentos. Neste caso estas palavras
também podem afetar o processo de agrupamento, constituindo grupos irrelevantes de documentos.
Todas estas palavras que não são relevantes e que podem afetar negativamente o processo são chamadas de
palavras negativas ou stop-words. Geralmente o usuário deve definir a lista de stop-words a serem ignoradas,
excluídas da lista de palavras identificada na etapa anterior. Isso porque, como já citado, podem existir listas de
palavras negativas específicas do contexto ou linguagem dos documentos que o usuário está trabalhando, o que
torna o processo flexível e aplicável a diferentes domínios e linguagens.
Outro fato a favor da eliminação das stop-words é que o número de palavras restantes na lista de palavras dos
documentos torna-se melhor, minimizando o tempo de análise e processamento do agrupamento.
,'(17,),&$d­2 '2 *5$8 '( ,03257Æ1&,$ '$6 &$5$&7(5Ë67,&$6
Antes de iniciar o processo de agrupamento resta identificar o quanto cada uma destas características é relevante
para cada objeto. O último processo básico de seleção de características consiste em agregar um valor de
importância a cada palavra da lista de palavras de um documento.
A forma mais simples de identificação da importância (também chamada de grau de relevância) de uma palavra
em um documento é calcular sua freqüência relativa. O cálculo da freqüência relativa consiste em contar
quantas vezes determinada palavra aparece em um documento e dividir esse total de aparições pelo número total
de palavras do documento. O valor resultante pode ser considerado como sendo o grau de afinidade da palavra
no documento, já que indica o grau de porcentagem ou influência da característica no documento em questão.
Existem outras formas mais complexas de identificação do grau de relevância de uma palavra em um
documento, porém, segundo alguns autores, estas análises podem exigir mais poder de processamento, levando
mais tempo, e não há estudos que indiquem vantagens significativas quanto à utilização de uma ou outra técnica.
Como exemplo, palavras que apareçam em títulos, resumos ou estruturas similares poderiam ser consideradas
mais relevantes para a caracterização de um documento.
A partir deste momento todas as palavras restantes na lista de palavras do documento já podem ser utilizadas no
processo de agrupamento.
6(/(d­2 '( &$5$&7(5Ë67,&$6 0$,6 5(/(9$17(6
Utilizar todas as características de um objeto a fim de analisá-lo pode tornar o processo de agrupamento muito
demorado. Pode-se dizer que quanto maior o número de características utilizadas na análise, melhor tende a ser o
resultado. Dependendo do tipo de análise que deseja-se fazer o tempo pode não ser crucial e o número de
características utilizadas pode ser mantido no máximo. Porém, quando o usuário está interessado em obter uma
visão geral do conteúdo de determinado conjunto de documentos, a qualidade pode não ser tão importante. Neste
caso o número de características a serem analisadas pode ser diminuído, assim como o tempo de processamento.
Portanto, a fim de tornar o processo mais rápido, o usuário pode indicar o grau mínimo de relevancia das
palavras, filtrando aquelas menos relevantes.
Por outro lado, mesmo estabelecendo um limite (um filtro) podem restar ainda muitas palavras relevantes. Neste
caso há a possibilidade do usuário truncar [SCH 97] o número de características, limitando a quantidade de
palavras relevantes por documento. Para tanto, é necessário que as características estejam ordenadas de acordo
com seu grau de relevância (ou importância). Assim, somente as primeiras x características são utilizadas.
É importante salientar que a identificação destes dois parâmetros (grau mínimo e número mínimo de
características) é um processo complicado e difícil, que pode até mesmo variar de coleção para coleção.
&É/&8/2 '( 6,0,/$5,'$'(6
Após identificadas as características relevantes de cada objeto, parte-se para a análise de similaridade entre eles.
Todo o processo de agrupamento está baseado em algum tipo de similaridade entre os objetos, pois agrupa-se
(ou separa-se) estes objetos em grupos de objetos que possuam alguma semelhança (similaridade) entre si.
Esta é a etapa mais crucial do processo, e sua eficiência depende muito das características identificadas como
relevantes. Caso as etapas anteriores não tenham identificado corretamente as características relevantes de cada
objeto, todo o processo pode ser comprometido. Além disso, conforme já citado anteriormente, o tempo
necessário para obter um agrupamento de qualidade é diretamente proporcional ao número de características
utilizadas. Não há como obter um desempenho muito rápido com qualidade, a não ser que as características
escolhidas como relevantes sejam realmente as que mais transmitem informações do objeto.
Existem várias funções (fórmulas) capazes de identificar a similaridade entre objetos. A fórmula utilizada neste
caso, como exemplo, é baseada na teoria dos conjuntos difusos (teoria fuzzy), e leva em conta todas as
semelhanças e diferenças entre as características de cada documento. Todo o referencial teórico referente à
função definida pode ser encontrado em [37].
Os documentos são analisados aos pares. A função apresentada a seguir utiliza um contador que vai acumulando
pontos toda vez que uma palavra é encontrada em ambos os documentos.
k
∑ gi (a, b)
h
gs ( X , Y ) =
h =1
n
onde:
gs é o grau de similaridade entre os documentos X e Y;
gi é o grau de igualdade entre os pesos do termo h (peso a no documento X
e peso b no documento Y);
h é um índice para os termos comuns aos dois documentos;
k é o número total de termos comuns aos dois documentos;
n é o número total de termos nos dois documentos (sem contagem
repetida).
O valor utilizado para atualizar este contador é dado por uma outra fórmula, definida por [PED 93] e apresentada
a seguir, que identifica o grau de igualdade entre os termos comuns. Esta outra fórmula é necessária, porque,
apesar da palavra aparecer em ambos os documentos, ela pode ter graus de importância diferentes em cada
documento. Esta outra fórmula é apresentada a seguir, e leva em conta a freqüência relativa do termo em ambos
os documentos (na realidade, sua média). Os termos que não aparecem em nenhum dos dois documentos sendo
comparados contribuem com o valor zero.
gi ( a , b) =
[
(
) (
1
(a → b ) ∧ (b → a ) + a → b ∧ b → a
2
)]
onde,
x =1− x
a → b = max{c ∈ [0,1] | atc ≤ b}, t = produto
∧ = min
Assim, se um termo aparece em ambos os textos, porém, com pesos muito diferentes, o grau de igualdade tornase baixo. Por outro lado, quando os valores dos pesos são próximos, o grau de igualdade torna-se mais alto. Caso
um termo apareça somente em um dos documentos, a similaridade diminui (já que este termo contribui com um
grau zero). Com isso, obtém-se um valor mais realista para ser considerado na média (similaridade) final.
Ao final desta etapa tem-se a matriz de similaridade triangular (uma propriedade desta fórmula), onde os valores
variam no intervalo [0,1]. Um grau zero (0) indica documentos totalmente díspares; já um grau um (1) indica
documentos similares. Além disso, um documento é igual a ele mesmo, recebendo, portanto, grau um (1). Outro
fator importante: a matriz é simétrica. Com isso, se um elemento A possui um grau de similaridade x com o
elemento B, então, o elemento B também possui o mesmo grau de similaridade com A.
Há, porém, uma advertência: documentos são considerados similares por possuir palavras similares. Um grau de
similaridade de 100% (1) não significa que os documentos sejam iguais, mas sim, que possuem as mesmas
palavras (excluindo as palavras negativas, as palavras infreqüentes e as demais palavras ignoradas no processo
de agrupamento). Estas palavras, mesmo que comuns, não são obrigadas a estar na mesma ordem (de aparição)
em ambos os documentos.
,'(17,),&$d®2 '( ´&/867(56µ
O agrupamento em si consiste em definir algum tipo de restrição que será aplicada na matriz de similaridades,
gerada na etapa anterior. Cada algoritmo possui um tipo de restrição diferente. Com isso, os objetos
(documentos) são então separados em grupos que satisfaçam estas restrições.
Na classe graph-theoretic os algoritmos mais importantes são o cliques, best-star, single-link e strings.
67$5
Este algoritmo seleciona o primeiro objeto da matriz e vasculha-a a procura de objetos similares. O conceito de
objeto similar é importante. Neste caso um objeto é similar a outro desde que satisfaça ao grau mínimo de
similaridade estabelecido pelo usuário. Todos os objetos que possuírem grau de similaridade maior do que o
mínimo estabelecido pelo usuário (em relação ao objeto selecionado) são colocados no mesmo cluster do objeto
selecionado. Deste modo, o cluster passa a ter a configuração de uma estrela, onde o objeto selecionado
inicialmente é o centro da estrela e os objetos adicionados ao grupo são suas extremidades (por isso o nome,
Star). Após, seleciona-se o próximo objeto ainda não atribuído a um cluster. Este passa a ser o objeto central da
nova estrela. O processo repete-se até que não hajam mais objetos a serem analisados.
%(6767$5
O Algoritmo Best-star [37] é uma variação do primeiro, e foi desenvolvido a fim de solucionar alguns
problemas. O maior problema do algoritmo Star refere-se ao fato dele adicionar um documento a um cluster e
não analisá-lo mais. Com isso, o objeto pode não ter sido atribuído ao grupo mais relevante (grupo cuja sua
relação com o objeto principal não é tão forte, podendo haver outro objeto principal com relação maior). O
Algoritmo Best-star elimina este problema, trocando os objetos de grupo até que eles sejam atribuídos ao grupo
que possuírem maior relação.
)8//67$56
Similarmente ao algoritmo anterior, o Full-stars [37] atribui um objeto a todos os grupos cujo o grau de
similaridade com o objeto principal for maior do que o grau de similaridade mínimo. Neste caso, um documento
é colocado em todos os grupos que possui afinidade. Isso é feito porque alguns documentos podem estar
relacionados com mais de um assunto (apesar de, geralmente, possuir mais afinidade ou relevância com somente
um deles).
&/,48(6
Neste algoritmo o processo de atribuição é similar aos dos grupos anteriores, porém, cada objeto atribuído ao
grupo é comparado com todos os outros objetos já existentes no grupo (cluster). O objeto só entra no grupo se
possuir um grau de similaridade mínimo satisfatório com todos os objetos do grupo. Esta restrição faz com que
este algoritmo seja um dos mais coesos, pois constitui grupos fortemente acoplados. Esse fato pode tornar seu
processamento mais demorado.
6,1*/(/,1.
Este também é um algoritmo com configuração de estrela, porém, suas estrelas não são coesas. Isso porque, após
ter sido realizado um processo similar ao do algoritmo stars, onde são adicionados documentos similares a um
objeto principal, o processo é repetido para cada um dos objetos presentes no grupo, ou seja, são identificados
objetos similares aos objetos constituintes da estrela (suas pontas). Assim, pode ocorrer da configuração do
cluster gerar uma estrela desbalanceada, com pontas maiores do que outras, o que pode ocasionar a identificação
de objetos pouco similares entre si (entre as pontas das sub-estrelas).
675,1*6
Ao contrário dos algoritmos anteriores, neste algoritmo não há a configuração de uma estrela. Neste caso, o
primeiro objeto é selecionado e, como nos outros casos, adiciona-se outro objeto que seja similar a ele (rever o
conceito de similaridade no primeiro algoritmo). Após, o segundo objeto passa a ser o principal do grupo e
vasculha-se a matriz em busca de um objeto similar a este novo objeto principal. O processo repete-se e os
objetos adicionados vão sempre tornando-se os objetos principais, constituindo assim uma cadeia (string).
O maior problema deste algoritmo é que ele não garante que o último objeto seja similar ao primeiro,
principalmente se a seqüência da cadeia for muito grande (a não ser que o grau mínimo de similaridade seja
muito alto).
&21&/86¯(6
As técnicas de Descoberta de Conhecimento em textos tem aplicação em quase todas as áreas da ciência.
Inicialmente, é claro que as áreas beneficiadas são todas do domínio da Computação.
O clustering, que é a técnica de mineração discutida na seção anterior, já é aplicado em bancos de dados a fim de
identificar registros que possuam alguma relação. Com esse tipo de informação, um supermercado pode, por
exemplo, aproximar dois ou mais produtos que os consumidores comprem em conjunto, estimulando ainda mais
sua compra, pois quem não pensava em comprar o produto, ao vê-lo é tentado a comprá-lo.
Assim como o banco de dados do supermercado, outros tipos de informação podem ser utilizados. As
informações contidas nas fichas dos clientes ou, futuramente, suas páginas WEB, também são fontes valiosas de
informação que podem ser utilizadas pelas mesmas ferramentas e com os mesmos propósitos: indicar o padrão
ou tendência de um grupo de pessoas – o mercado. Essa informação sobre a tendência do mercado de consumo
facilita com que uma empresa posicione-se melhor no mercado, pois, muitas vezes, a empresa nem sabe qual é
seu público alvo. Os consumidores deste tipo de ferramenta de análise (software) são as pessoas encarregadas do
marketing ou gerentes e administradores de empresas.
O clustering também pode ser utilizado com o propósito de facilitar a recuperação de informações, agrupando
automaticamente o resultado de uma consulta feita pelo usuário em uma base de dados (Internet, por exemplo).
Deste modo, o usuário não necessitaria ler todos os documentos retornados pelo Altavista®, por exemplo.
Bastaria analisar os grupos de documentos e selecionar o grupo mais adequado para a leitura.
Esta técnica, combinada com técnicas de extração, poderia gerar resumos automáticos, retornando para o usuário
somente a informação mais importante de uma quantidade muito grande de documentos ou páginas. Poderia
ainda, indicar os assuntos mais publicados em determinado site na Internet ou até mesmo auxiliar o diagnóstico
de um paciente em uma clínica.
Este último caso é particularmente interessante, pois há a possibilidade de que os prontuários ou laudos médicos
sejam agrupados de acordo com seu diagnóstico. Ao chegar um novo paciente seu laudo de internação seria
comparado com os grupos de prontuários já existentes e este seria classificado em um deles. Um sistema
especialista sugeriria, então, diagnósticos e tratamentos adequados àquele grupo, já que este novo paciente
possui grandes chances de possuir os mesmos problemas de saúde.
Porém, ainda existem muitos problemas não resolvidos. O problema mais grave diz respeito ao fato do usuário
ainda ter que configurar alguns parâmetros para que as ferramentas e técnicas funcionem corretamente. Além
disso, não há valores padrão para estes parâmetros e eles podem variar de acordo com o contexto da aplicação. A
identificação correta depende de que o usuário realize vários experimentos e vá refinando o resultado de forma
iterativa.
Tudo isso significa que não há uma análise completamente automatizada. O usuário sempre tem que determinar
quais são os resultados mais relevantes. Esse fato pode gerar problemas aos usuários menos experientes, pois
eles podem não ser capazes de alcançar bons resultados. Como citado no início deste artigo, o conceito de
conhecimento e informação relevante depende muito do usuário. Em uma empresa, pode ser necessária a figura
de um especialista que interprete corretamente os resultados e identifique o que pode ser aproveitado como
conhecimento útil para a empresa em que trabalha.
Isso não significa que o usuário leigo não seja capaz de utilizar estas ferramentas nem obter conhecimento útil,
mas sim, que ele talvez não consiga explorar todo o potencial que elas poderiam oferecer (geralmente através de
análise de anomalias e exceções que surgem no decorrer do processo de descoberta de conhecimento).
Todas estas aplicações e problemas estimulam a produção e o desenvolvimento da área, que ainda necessita de
muitas contribuições e oferece um ótimo campo de trabalho.
5HIHUrQFLDV%LEOLRJUiILFDV
[1]
AAMODT, Agnar; NYGARD, Mads. Different roles and mutual dependencies of data, information and
knowledge - an AI perspective on their integration. Data & Knowledge Engineering, v.16, n.3,
Setembro de 1995.
[2]
AGRAWAL, Rakesh. Data mining: the quest perspective. In: EDBT SUMMER SCHOOL ON ADVANCES IN
DATABASE TECHNOLOGY. Proceedings... Gubbio-Itália, Setembro de 1995.
[3]
AMBROSIO, Ana P. et alli. The linguistic level: contribution for conceptual design, view integration,
reuse and documentation. Data & Knowledge Engineering, v.21, n.2, Janeiro de 1997.
[4]
CHEN, Hsinchun et alli. A concept space approach to addressing the vocabulary problem in
scientific information retrieval: an experiment on the worm community system.
University of Arizona, Julho de 1996. Disponível por WWW em http://ai.bpa.arizona.edu/
papers/
[5]
CHEN, Z. Let documents talk to each other: a computer model for connection of short documents.
Journal of Documentation, v.49. n.1, Março de 1993.
[6]
CHIDANAND, Apté et alli. Automated learning of decision rules for text categorization. ACM
Transactions on Information Systems, v.12, n.3, Julho de 1994.
[7]
CUTTING, Douglass et al. Scatter/Gather: a cluster-based approach to browsing large document
collections. In: SPECIAL INTEREST GROUP ON INFORMATION RETRIEVAL, SIGIR, 1992.
Proceedings… New York: Association for Computing Machinery, 1992. p.318-329.
[8]
COWIE, Jim; LEHNERT, Wendy. Information extraction. Communications of the ACM, v.39, n.1, Jan
96.
[9]
DALE, R. Generating referring expressions. Cambridge: The MIT Press, 1992.
[10]
DAVIES, Roy. The creation of new knowledge by information retrieval and classification. Journal of
Documentation, v.45, n.4, Dezembro de 1989.
[11]
FAYYAD, Usama M. et alli (eds) Advances in Knowledge Discovery and Data Mining. Menlo Park,
The MIT Press, 1996.
[12]
FELDMAN, Ronen; HIRSH, Haym. Exploiting background information in knowledge discovery from
text. Journal of Intelligent Information Systems, v.9, n.1, Julho/Agosto de 1997.
[13]
FELDMAN, Ronen; DAGAN, Ido. Mining text using keyword distributions. Journal of Intelligent
Information Systems, v.10, 1998. pp.281-300.
[14]
HAN, Jiawei et alli. Intelligente query answering by knowledge discovery techniques. IEEE
Transactions on Knowledge and Data Engineering, v.8, n.3, Junho de 1996.
[15]
JACOBS, Paul S. Text-based intelligent systems: current research and practice in information
extraction and retrieval. New Jersey: Lawrence Erlbaum, 1992.
[16]
KAMEYAMA, M.; PASSONNEAU, R.; POESIO, M. Temporal centering. In: 31ST MEETING OF THE
ASSOCIATION FOR COMPUTATIONAL LINGUISTICS. Proceedings... Columbus - Ohio, 1993.
[17]
KNIGHT, K; RICH, E. Inteligência Artificial. São Paulo: Makron Books, 1993. 2a edição.
[18]
KORTH, H. F; SILBERTCHATZ, A. Sistemas de Gerenciamento de Bancos de Dados. São Paulo:
Makron Books, 1993. 2a edição.
[19]
LEWIS, David D.; SPARCK-JONES, Karen. Natural language processing for information retrieval.
Communications of the ACM, v.39, n.1, Janeiro de 1996.
[20]
McKEOWN, Kathleen; RADEV, Dragomir R. Generating summaries of multiple news articles. In:
SPECIAL INTEREST GROUP ON INFORMATION RETRIEVAL, SIGIR, 1995. Proceedings... New
York: Association for Computing Machinery, 1995.
[21]
MIIKE, Seiji et alli. A full-text retrieval system with a dynamic abstract generation funcion. In: SPECIAL
INTEREST GROUP ON INFORMATION RETRIEVAL, SIGIR, VII. Proceedings... London: SpringerVerlag. 1994.
[22]
MINSKY, Marvin. The society of mind. New York: Simon & Schuster, 1988.
[23]
MORRIS, Jane; HIRST, Graeme. Lexical cohesion computed by thesaural relations as an indicator of the
structure of text. Computational Linguistics, v.17, n.1, Março de 1991.
[24]
MOSCAROLA, Jean et al. Technology watch via textual data analysis. France: Université de Savoie,
Le Sphinx Développement, 1998. (Note de Recherche, n. 98-14)
[25]
MOSCAROLA, Jean; BOLDEN, Richard. From the data mine to the knowledge mill: applying the
principles of lexical analysis to the data mining and knowledge discovery process. France:
Université de Savoie, Le Sphinx Développement, 1998. (Note de Recherche, n. 98-15)
[26]
OARD, Douglas W.; MARCHIONINI, Gary. A conceptual framework for text filtering. Technical
Report,
University
of
Maryland.
Disponível
por
WWW
em
http://www.ee.umd.edu/medlab/filter/ (Maio de 1996)
[27]
PARSAYE, Kamran et alli. Intelligent databases: object-oriented, deductive hypermedia
technologies. New York: John Wiley & Sons, 1989.
[28]
RALHA, Célia G. Structuring information in a distributed hypermedia system. In: IX EUROPEAN
KNOWLEDGE ACQUISITION WORKSHOP. Proceedings... Lecture Notes in Artificial Intelligence,
1076. Maio de 1996.
[29]
RIJSBERGEN, C. van. Information retrieval. 2.ed. London: Butterworths, 1979.
[30]
SAINT-DIZIER, Patrick. Semantic verb classes and lexical conceptual structures for enhancing the
conceptual modelling and the access to databases. Data & Knowledge Engineering, v.21,
n.2, Janeiro de 1997.
[31]
SALIMINEN, Airi et alli. From text to hypertext by indexing. ACM Transactions on Information
Systems, v.13, n.1, Janeiro de 1995
[32]
SALTON, Gerard; McGILL, M. J. Introduction to modern information retrieval. New York:
McGraw-Hill, 1983.
[33]
SPARCK-JONES, Karen; WILLET, Peter (eds). Readings in Information Retrieval. San Francisco:
Morgan Kaufmann, 1997 SPARCK-JONES, Karen; WILLET, Peter (eds). Readings in
Information Retrieval. San Francisco: Morgan Kaufmann, 1997.
[34]
TAZI, Saïd. Using Sowa’s conceptual graphs for enhancing hypertext readers performances. In:
INTELLIGENT HYPERTEXT WORKSHOP. Proceedings... Washington, 1994. Disponível por
WWW em http://lis.univ-tlse1.fr/tazi
[35]
TRINDADE, Carolina S. et alli. Regras Heurísticas para Transformação Automática de Textos em
Diagramas de Fluxo de Dados. In: XXII CONFERÊNCIA LATINO-AMERICANA DE INFORMÁTICA
- CLEI/PANEL'96. Proceedings... Bogotá, 1996.
[36]
VICCARI, Rosa M. Inteligência artificial: representação do conhecimento. Folheto FL1747. Porto
Alegre, CPGCC/UFRGS, 1990.
[37]
WIVES, Leandro Krug; Um Estudo sobre Agrupamento de Documentos Textuais em Processamento
de Informações não Estruturadas Usando Técnicas de "Clustering”. Porto Aegre: PPGC,
1999. (dissertação de mestrado)