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,),&$d2 '( 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(02d2 '( 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,),&$d2 '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(/(d2 '( &$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)