Upload
roberto-de-pinho
View
160
Download
2
Embed Size (px)
Citation preview
CCMC – ICMC – USP São Carlos, SP
5 de Junho de 2009 1
2
Contexto Problema Posicionamento incremental Regras de associação para identificar tópicos Mineração visual para conjuntos dinâmicos
de documentos Contribuições Trabalhos futuros
3
Visualização de domínios de conhecimento
Mineração de dados
Mineração de dados textuais
Mineração visual de dados 4
Posicionamento por similaridade
Wise (1999); Börner (2003); Bederson (2001); ...
Identificação de tópicos em mapas
Wise(1999);Skupin (2002); Chen (2004) ...
5
Necessidade de mapa cognitivo para navegar espaços conceituais (Chen,2004)
Visualização de conjuntos dinâmicos como problema relevante
Ao visualizar conjuntos dinâmicos, é importante preservar o contexto dos usuários (Hetzler, 2005)
6
Outras soluções
Refazer toda a visualização
Reutilizar solução inicial, refazer periodicamente Ex. Wong et al (2003)
7
Construir mapas de conjuntos dinâmicos de documentos
Manter representação adequada à medida que elementos são acrescentados ou retirados
Minimizar alterações
8
Técnica incremental de Multidimentional Scaling - MDS
Utiliza medidas de similaridade entre pares
9
6,5 5
2 B A
C
2 4.75
B A C
Técnica incremental de Multidimentional Scaling - MDS
Utiliza medidas de similaridade entre pares
10
5 5
5
5 5
B A
C B A C
2,5 2,5
B A C
ABC
11 demo: cbr-ilp-ir-son
Não refaz a visualização a cada alteração
Não mantem solução inicial fixa Baixo custo: pior caso: O(N2), caso
médio: O(N √N) Disposição consistente de
elementos 12
13
178 documentos 294 documentos
675 documentos
Visualização de conjuntos dinâmicos de documentos
Outros domínios
Navegação em sistema operacional
Tag Clouds
Dados multidimensionais
Coleções de imagens (Rodden et al;1999, 2001)
Não há oclusão
14
Análogo ao um tabuleiro de xadrez Distância de Chebyschev:
Relação com o espaço original (erro ponderado)+ desempate por qtd ponderada
15
Avaliação de alternativas:
16
Elemento aprisionado:
17
Elemento aprisionado:
18
Elemento aprisionado:
19
Movimento em direção ao centro:
20
Novo elemento adicionado na célula do elemento mais similar
Avaliação de alternativas:
Modo completo: utilização do conjunto completo
Modo estocástico: Lista de elementos próximos e lista de elementos aleatórios (Chalmers, 1996)
21
CBR-ILP-IR-SON:
22
O(VxN):O(N) 23
Conjunto inicial
Conjunto intermediário
Conjunto final
24
Mineração de textos com regras de associação
Documentos » Transações
Termos » Itens
25
Nashville, Tenessee -> Tornadoes
com suporte 5% e confiança 100%
26
Co-ocorrência de termos ≈ assunto Tópico: descrição de um conjunto de
documentos relacionados, representada por uma lista de term0s.
Um tópico cobre um conjunto de documentos nos quais os termos co-ocorrem.
27
Quantidade de regras descobertas
Redundância de regras
Relevância dos termos (itens) Medida de relevância para
regras (filtragem) 28
Espaço de regras Alto suporte
29
Espaço de regras Baixo suporte
30
31
1. Sk: conjunto de documentos similares
2. Identificar os termos mais relevantes
32
“Thursday”
33
“Flu”
34
3. Conjunto Inicial de item sets: Tr x T Termos relevantes x Todos os termos
4. Aplicação do Apriori (qtd termos > 2) 5. Ordenados por peso:
35
6. Item set de maior peso é selecionado
7. Documentos cobertos eliminados de Sk
8. Outros item sets são selecionados se há suporte em Sk residual ( repete 6 & 7 )
9 . Se todos os item sets são considerados |Sk residual| ≠ , repete todo o processo com Sk residual
Múltiplo início
Agrupamentos no mapa – vários níveis
Grade
▪ Célula de tamanho variável
▪ Deslocamento da grade
36
37
LWR
Vantagens
Resultados em múltiplos níveis.
▪ Ex [bird, flu]; [bird,flu,swan];
Baixa sensibilidade para parâmetros
Desvantagens
Resultados não satisfatórios para um pequeno número de subconjuntos ou seleções muito grandes (aprox. |Sk| > |C|/4)
38
39
40
41
1. Construção do mapa 2. Extração de tópicos 3. Análise de tópicos centrada no
usuário
i. Remoção de tópicos irrelevantes
ii. Generalização de tópicos
4. Reconstrução do mapa 42
Estratégia de atualização incremental de agrupamentos
Existem soluções: ex. GenIc (Gupta e Grossman, 2004)
Viés adotado: contribuição do posicionamento de elementos no mapa
Estratégia de atualização incremental de tópicos
Heurísticas: não repetir o processo a cada passo
43
44
45
?
Efeito do viés
Tendência a formar agrupamentos coesos no mapa
Solução não ótima
Eventual degeneração da solução
Solução atual: refazer o agrupamento
Espaço para melhoria
46
Perguntas
quando deve um tópico ser eliminado?
quando devem ser acrescentados novos tópicos?
Abordagem
Avaliação dos termos semente
47
1. Extração inicial de tópicos
2. A cada alteração nos agrupamentos, atualiza-se a lista de termos semente
3. Se um tópico existente não possue nenhuma das atuais sementes, ele é excluído
4. Se um novo termo semente aparece, extrair tópicos para aquele termo
5. Novas relações para sementes: controle de alterações no suporte do termo. A cada passo, o termo de maior variação é reavaliado
48
Objetivo: manter o tempo de processamento compatível com o cenário de uso
49
Um novo algoritmo para a projeção incremental de conjuntos dinâmicos de dados multidimensionais
Uma visualização para conjuntos dinâmicos de dados multidimensionais que não sofre problemas de oclusão
50
Um algoritmo seletivo de indução de regras de associação que explora grupos de documentos similares
Um processo iterativo e interativo de mineração visual de textos
Um espaço incremental que: minimiza alterações, mantem uma representação consistente e reflete a dinâmica dos dados
51
aplicação do algoritmo incremental de projeção em cenários específicos de uso e validação
melhoria de pontos específicos do algoritmo Ex. Identificação de elementos similares
investigação de novas possibilidades de interação e visualização Ex. melhoria do refino interativo de
mapas/tópicos Dissertação R. Rodrigues
52
53
Além da discussão constante com as orientadoras, este trabalho contou com
Contribuições do Prof. Dr. Alneu Lopes
Contribuições do Prof. Dr. Chaomei Chen
Desenvolvimento de software e contribuições de Renato Rodrigues
Plataforma PEx (Prof. Dr. Fernando Paulovich) para o teste e incorporação de soluções
Contribuições de colegas na USP e Drexel
54
Bolsa CAPES
Bolsa FAPESP Bolsa CAPES PDDE (doutorado
sanduíche)
55
Roberto Pinho [email protected] www.ascoisas.com 56
PINHO, R.; LOPES, A.; OLIVEIRA, M. C. F. Incremental board: A grid-based space for visualizing dynamic data sets. In: Proceedings of the 2009 Annual ACM Symposium on Applied Computing, New York, NY, USA:ACM, 2009, p. 1757–1764. (Best Paper Award in the Information System Theme - Prêmio de melhor trabalho na área Sistemas de Informação).
57
Photomesa by HCI Lab at the Univ. of Maryland
58
Critério de Desempate
59
Iris Data Set
60
PINHO, R.; OLIVEIRA, M. C. F. HexBoard: Conveying Pairwise Similarity in an Incremental Visualization Space. In: IV ’09: 13th International Conference Information Visualisation (em publicação), 2009.
61
PINHO, R.; LOPES, A.; OLIVEIRA, M. C. F. An incremental space to visualize dynamic data sets. Convidado para submissão para edição especial do Multimedia Tools and Applications Journal (MTAP) com os melhores trabalhos em Multimídia e Visualização (MMV track) do 2009 Annual ACM Symposium on Applied Computing ACM SAC 2009
62
63
α – direção β – ajuste de escala δ – dissimilaridade δ/∑δ – peso relativo
LOPES, A. A., PINHO, R., PAULOVICH, F. V., AND MINGHIM, R. 2007. Visual text mining using association rules. Computer and Graphics. 31, 3 (Jun. 2007), 316-326.
64
65
66
Tamanho, termos distintos, cobertura e suporte mínimo para conjuntos de regras extraídos de corpus de notícias
LWR
1. Elementos são associados a um agrupamento
2. Células assumem o agrupamento do elemento que a ocupa
3. Ao ser movido, o agrupamento do elemento é reavaliado
Se igual à célula destino, permanece
Se diferente, seleciona-se a opção mais adequada (ex. distância ao centróide)
Atualiza a célula 67
ferramentas e aplicações desenvolvidas e com relação direta com a tese
contribuições cujo tema tangencia os temas principais
68
APIs para os algoritmos desenvolvidos; Ferramenta Voromap para avaliação de
visualização com base em partições do plano; Avaliação da ferramenta PEX-WEB; Aplicação de VTM para a realização de
revisões sistemáticas;
69
Ferramentas desenvolvidas:
Topic Pex
incBoard;
Evolução do incBoard:
HexBoard
incScape (não presente na tese)
70
Espaço de documentos
71
Espaço de documentos
72
73
74
75
Ajuste
Sistema de coordenadas: x,y,z
Cálculo de distâncias
76
Em destaque
conjuntos cujos itens são alterados
melhoria do processo de agrupamento incremental
melhoria do refino interativo de mapas/tópicos R. Rodrigues
topical markers
manipulação direta
77
Uma necessidade de informação – materializada como uma descrição, lista de termos ou como uma consulta a ser apresentada a uma ferramenta de recuperação de informação;
Um conjunto de documentos relativos a um mesmo assunto ou que atendem a uma necessidade de informação;
Lista de termos descritivos de um assunto ou conjunto de documentos.
78
Tópico: a descrição dada a um conjunto de documentos, usualmente relacionados entre si, tipicamente representada por uma lista de termos e ao qual corresponde um conjunto de documentos por ele cobertos, i.e., que abordam o tema em questão, o que é, em geral, verificado pela presença da lista de termos nos documentos.
79
Rotina externa de extração em C Limite máximo de termos em regras Limite máximo de regras extraídas Filtro de termos por peso local
Objetivo: manter o tempo de processamento compatível com o
cenário de uso
80