Presentasjon av relevant litteratur og forskning

Como mencionado, para calcular um polígono que delimita a área de um grupo qualquer, se emprega primeiro o fecho convexo nos pontos pertencentes àquele grupo. No entanto, o grupo pode possuir uma distribuição não convexa e o fecho convexo pode incluir pontos que não pertencem ao grupo. Neste caso, utiliza-se um algoritmo para cálculo de contornos implícitos, que reflete melhor o formato do grupo. Uma vez que os grupos são delimitados como polígonos a cada momento na sequência de projeções, é necessário animar esses polígonos nos quadros intermediários da animação, de forma a representar as transições de surgimento, subdivisão, junção, sobrevivência e desaparecimento de grupos detectados.

Por exemplo, supondo a sobrevivência de um grupo X que está presente no instante t e seu equivalente Y presente em t + 1, é possível observar as seguintes modificações: alguns documentos foram removidos; alguns documentos foram adicionados; e a maior parte dos documentos permaneceram, mas podem ter tido sua posição alterada dentro do grupo. Dados

um polígono P olt, que representa o grupo X em t, e outro polígono P olt+1, que representa o

grupo Y em t + 1, a questão resume-se em como calcular uma animação que transforma o

polígono P olt em P olt+1 para os quadros intermediários. Quando um novo documento está

se movendo em direção ao polígono ao qual deve ser adicionado, e inicialmente sua posição de partida é fora deste polígono, o polígono deve lentamente se expandir na direção desse documento de forma a incluí-lo. Já quando um documento deve ser removido do polígono que representa seu grupo, o polígono deve lentamente se contrair na direção dos documentos que irão permanecer. Tanto para a transição de sobrevivência como para as outras transições devemos frequentemente calcular esse tipo de animação que transforma um polígono em outro pela adição e remoção de documentos.

Neste trabalho, a animação de um polígono em outro é dada por uma sequência que contém um polígono para cada um dos N quadros intermediários entre t e t + 1. Cada polígono na sequência apresenta uma pequena alteração em relação ao seu anterior, de forma a promover uma animação suave. O cálculo utilizado para a animação de um polígono é apresentado no Apêndice B.

Para as figuras e vídeo apresentados nesta seção, aplicou-se a técnica de projeção dinâmica T-LSP para a coleção de artigos do pesquisador Alessandro Vespignani entre 1990 e 2012. Os

(a) Entrada em 2011: um grupo. (b) Frame intermediário.

(c) Frame intermediário. (d) Saída em 2012: um grupo.

Figura 4.10: Representação visual da sobrevivência de um grupo.

grupos foram detectados aplicando o algoritmo de agrupamento DBSCAN com parâmetros

ε= 0.06 e MinP ts = 4, enquanto as transições entre estes grupos foram detectadas aplicando

o algoritmo MONIC com parâmetros τ = 0, 5 e τsplit = 0, 2. Já os tópicos foram extraídos

com a técnica baseada em PCA com os parâmetros min_topics = 0, 5 e min_terms = 0, 6. A Figura 4.10 apresenta um exemplo da representação visual utilizada para representar a sobrevivência de um grupo entre 2011 e 2012. Neste caso, é mostrado um único polígono que se expande em uma região do seu perímetro para incluir novos documentos (ver Figura 4.10c) e se contrai em outra região do seu perímetro para remover outros documentos (ver Figura 4.10b). Até a primeira metade dos quadros intermediários (ver Figuras 4.10a e 4.10b), são mostrados os tópicos relativos ao conteúdo deste grupo no instante t. Já na segunda metade (ver Figuras 4.10c e 4.10d), são mostrados os tópicos extraídos com base no conteúdo deste grupo no instante t + 1. É possível observar que os tópicos se mantiveram razoavelmente estáveis durante a transição. A maior parte dos termos dos tópicos permaneceu com alguma mudança às vezes em sua ordem, enquanto alguns outros termos foram removidos ou adicionados.

Já a Figura 4.11 mostra um exemplo da representação visual utilizada para representar a junção de dois grupos em 2008 em um único em 2009. Inicialmente, são apresentados dois polígonos (ver Figura 4.11a), representando os dois grupos de entrada que irão se unir. Estes dois polígonos vão se tornando cada vez mais transparentes e passam a exibir também uma borda pontilhada (ver Figuras 4.11b e 4.11c), enquanto outro polígono que engloba esses dois é apresentado inicialmente totalmente transparente e se torna cada vez mais opaco (ver Figuras 4.11b e 4.11c). Este polígono maior representa o grupo formado pela junção dos dois grupos de entrada. Documentos a serem removidos influenciam tanto a animação do polígono maior como dos polígonos de entrada. Já os documentos a serem adicionados influenciam somente na animação do polígono maior. Até a primeira metade dos quadros intermediários

(a) Entrada em 2008: dois grupos. (b) Frame intermediário.

(c) Frame intermediário. (d) Saída em 2009: um grupo.

Figura 4.11: Representação visual da junção de dois grupos.

(a) Entrada em 2006: um grupo. (b) Frame intermediário.

(c) Frame intermediário. (d) Saída em 2007: dois grupos.

Figura 4.12: Representação visual da subdivisão de um grupo.

(ver Figura 4.11a e 4.11b), são mostrados os tópicos relativos aos dois grupos que irão se unir. Já na segunda metade (ver Figuras 4.11c e 4.11d), são mostrados os tópicos extraídos para o resultado dessa junção.

A Figura 4.12 exemplifica da representação visual utilizada para a subdivisão de um grupo em 2006 em dois em 2007. Esta representação visual é o inverso da representação para a junção de grupos. Inicialmente, tem-se apenas um polígono (ver Figura 4.12a) que representa o grupo que será subdividido, que se torna cada vez mais transparente (ver Figuras 4.12b e 4.12c). Ao mesmo tempo, dois polígonos que englobam o resultado dessa subdivisão tornam-se cada vez menos transparentes e mais visíveis (ver Figuras 4.12b e 4.12c). Documentos a serem removidos influenciam somente na animação do polígono maior. Já documentos a serem adicionados influenciam tanto a animação do polígono de saída como os de entrada. Até a primeira metade dos quadros intermediários (ver Figura 4.12a e 4.12b), são mostrados

(a) Entrada em 2000: conjunto de documentos não relacionados.

(b) Frame intermediário.

(c) Frame intermediário. (d) Saída em 2001: um grupo.

Figura 4.13: Representação visual do surgimento de um grupo no canto inferior esquerdo.

(a) Entrada em t: um grupo. (b) Frame intermediário.

(c) Frame intermediário. (d) Saída em t + 1: conjunto de documentos não relacionados.

Figura 4.14: Representação visual do desaparecimento de um grupo seguido pelo surgimento de outro.

os tópicos relativos ao grupo que irá se subdividir. Já na segunda metade (ver Figuras 4.12c e 4.12d), são mostrados os tópicos extraídos para os resultados dessa subdivisão.

Por fim, as Figuras 4.13 e 4.14 ilustram o surgimento de um novo tópico e o desapare- cimento de um tópico, respectivamente. Para representar o surgimento de um novo tópico, tem-se um polígono que vai se tornando cada vez mais visível ao diminuir sua transparência. Enquanto no desaparecimento de um novo tópico, utiliza-se um polígono que se torna cada vez mais transparente. No caso do surgimento de um grupo, os tópicos são exibidos somente depois da primeira metade dos quadros intermediários. No caso do desaparecimento de um grupo, os tópicos somem depois da primeira metade dos quadros intermediários.

Um vídeo mostrando o mapa dinâmico completo para essa coleção encontra-se disponível em http://vicg.icmc.usp.br/~aretha/tlsp/examples/VespignaniDynamicMap.avi.

4.4. Considerações Finais

Nesse capítulo foi apresentada a Time-based Least Square Projection (T-LSP), uma nova técnica de projeção multidimensional dinâmica que é capaz de projetar conjuntos de dados de alta dimensionalidade em um tempo computacional satisfatório, mostrando as mudanças nas relações de similaridade ao longo do tempo entre objetos multidimensionais, como coleções de artigos científicos. A saída é uma sequência de projeções indexada temporalmente, que pode ser animada para evidenciar as mudanças entre dois instantes de tempo. A T-LSP busca obedecer duas propriedades principais conflitantes: a manutenção da acurácia local e a manutenção da coerência espacial global. Nesta tese, a técnica T-LSP é aplicada a coleções de artigos científicos com o intuito de obter um mapa de documentos dinâmico que evidencia a evolução temporal dos tópicos. No entanto, esta técnica também pode ser empregada para mostrar mudanças temporais nas relações de similaridade para qualquer tipo de coleção de dados indexada temporalmente, que possa ser representada em um espaço multidimensional ou para a qual relações de similaridade possam ser definidas.

Com intuito de adicionar informação ao mapa de documentos dinâmico sobre o porquê certos grupos se formaram em determinados instantes de tempo, foram desenvolvidas duas novas técnicas de extração automática de tópicos: a extração de tópicos baseada em Principal

Component Analysis (PCA), um método utilizado para detecção de padrões; e a extração de

tópicos baseada em Latent Dirichlet Allocation (LDA), um modelo que busca representar documentos como uma distribuição probabilística de seus tópicos.

Com base no mapa dinâmico de documentos obtido com a T-LSP, também é possível detectar a evolução temporal de tópicos, buscando por eventos de transição como: a emergência de novos tópicos em instantes de tempo específicos; a subdivisão de um tópico, quando parte dos documentos daquele tópico tornam-se heterogêneos em relação ao restante do grupo e formam um novo tópico; e a junção de dois ou mais tópicos para formar outro. Para detectar essa evolução temporal de tópicos com base na T-LSP, combinamos as técnicas de extração de tópicos com: o algoritmo de detecção de agrupamentos baseado em densidade DBSCAN; e com o algoritmo MONIC para rastreamento das transições temporais entre grupos. Uma vez detectada, a informação sobre a evolução temporal de tópico pode ser adicionada ao mapa dinâmico de documentos por meio de efeitos visuais.

Dessa forma, a T-LSP fornece informações valiosas quanto as mudanças nas relações de similaridade entre os documentos ao longo do tempo. Informações que podem ser analisadas por algoritmos de mineração para extrair outros padrões interessantes, como eventos de transição.

Capítulo

✺

Arcabouço Visual e Estudos de Caso

Este capítulo tem o objetivo de descrever aplicações da abordagem proposta no Capítulo 4, fornecendo evidências de sua aplicabilidade. Na Seção 5.1, são apresentadas as características e funcionalidades da ferramenta Science View, que foi desenvolvida como um arcabouço visual para aplicar e testar as técnicas apresentadas no capítulo anterior. Já na Seção 5.2 são apresentados a abordagem de coleta das coleções de artigos científicos para análise de forma a priorizar a qualidade dos dados, e alguns cenários de análise temporal de coleções, com seus resultados correspondentes. A Seção 5.3 apresenta os tempos de processamento para gerar os mapas de documentos dinâmicos apresentados neste capítulo. Por fim, a Seção 5.4 apresenta um comparativo entre técnicas para construção de mapas de documentos dinâmicos baseados em projeções multidimensionais, que traz uma análise mais crítica e profunda das técnicas segundo uma série de quesitos, contextualizando a contribuição deste trabalho em relação ao estado da arte.

5.1. Arcabouço Visual: Ferramenta Science View

A ferramenta Science View1 _{aceita como entrada coleções de artigos nos formatos ISI, Endnote}

Export Format ou BibTeX. A escolha desses formatos deve-se, principalmente, à sua larga

1

utilização no meio acadêmico. O formato ISI, por exemplo, é adotado pela base de artigos

científicos Thomsons Reuters Web of Science2_{. Essa base permite a navegação e pesquisa em}

mais de 10.000 periódicos e 120.000 conferências, sendo atualizada diariamente. Isto significa que o usuário pode fazer uma pesquisa por artigos utilizando termos de seu interesse e salvar a coleção de artigos resultante no formato ISI para ser analisada na ferramenta Science View. O resultado final não é alterado pelo formato no qual a coleção será fornecida, com exceção do formato BibTeX para o qual não se encontra disponível opções envolvendo as referências, como o modelo vetorial estendido ou arestas baseadas em acoplamento bibliográfico.