Uma Abordagem para Comparação de Mapas ... - cinted.ufrgs.br · Departamento de Informática CT/UFES 12 a 15 de dezembro/2006 1 Uma Abordagem para Comparação de Mapas Conceituais

Departamento de InformáticaCT/UFES

12 a 15 de dezembro/2006

1

Uma Abordagem para Comparação de Mapas Conceituais utilizando Correspondência de Grafos

Flávio Severiano Lamas de Souza ([email protected])

Maria Claudia Silva Boeres ([email protected])

Davidson Cury ([email protected])

Crediné Silva de Menezes ([email protected])

Guilherme Carlesso ([email protected])

VIII Ciclo de Palestras sobre Novas Tecnologias na

Educação: Saber criar, saber usar



1

Objetivo do Trabalho

O problema de correspondência de grafos (PCG) foi formulado no contexto de Otimização Combinatória para a comparação estrutural de grafos, a partir da identificação de similaridades. Proposto inicialmente para aplicações em reconhecimento de imagens, pretende-se neste trabalho, adaptá-lo para uma aplicação em recuperação inteligente de informação, a saber, a comparação de mapas conceituais em representação de conhecimento, assim como investigar a utilização de algoritmos heurísticos e exatos para a sua resolução.



1

Tópicos

• Mapas Conceituais

• Por que comparar Mapas Conceituais?

• A Arquitetura da Comparação

• O Problema de Correspondência de Grafos (PCG)

• Instanciando a Proposta

• Algoritmos utilizados para a resolução do PCG

• Resultados Computacionais

• Considerações Finais e Trabalhos Futuros



1

Mapas Conceituais

• ferramenta de apoio à representação do conhecimento

• Possibilita a organização e representação do conhecimento acerca de um determinado assunto

• Apoio à avaliação da aprendizagem



1

Exemplo de um Mapa Conceitual



1

Por que comparar mapas?

• Um professor solicita aos seus estudantes que construam, individualmente, um mapa conceitual sobre um determinado tema para, em seguida, compará-los para identificar diferenças e similaridades existentes;

• Um engenheiro de conhecimento solicita que diferentes especialistas construam um mapa conceitual, descrevendo o conhecimento que possuem sobre um determinado assunto. A comparação entre eles permitirá que se obtenha uma descrição mais precisa do assunto considerado;

• A comparação entre diversos mapas, que descrevem diferentes textos, permitirá conhecer o grau de similaridade entre os diferentes textos.



1

Como apoio a estas situações, o computador pode atuar como

um grande aliado, automatizando a identificação de importantes aspectos dos mapas

construídos

Automatização da Comparação de Mapas Conceituais



1

Trabalhos Relacionados

• Métricas para cálculo de similaridades entre

conceitos ou entre relações:

– Performance Scoring Method (Takeya et al 2004)

– Tratamento de ambigüidades semânticas no contexto de bases de dados lexicográficos (Fellbaum 1998)

• Comparadores de mapas conceituais:

– Módulo comparador do CMaps (Novak, Canãs 2006)

– Similarity Flood (Melnik 2002)



1

Mapas Conceituais

x

Grafos com atributos

mamiferos

peixes

água

peixes

baleias

animais

Podem ser

Podem ser

são

Vivem na

Vivem na



1

Mapas Conceituais

x

Grafos com atributos

• Um grafo é uma estrutura matemática composta de vértices e arestas (ou arcos);

G = (V,A)

• Os vértices e as arestas (ou arcos) podem ser valorados.

• Palavras ou frases que descrevem conceitos ou relações podem nos mapas podem ser vistos como atributos.



1

Arquitetura de Comparação

Mapa Conceitual 1 Mapa Conceitual 2

Casamento dos Mapas

Comparador Semântico

Similaridades entre conceitos

O Problema de Correspondência de Grafos (PCG)

Extração de Conceitose relações

GrafoExtração de Conceitose relações

Grafo

Similaridades entre relações



1

O Problema de Correspondência

de GrafosGrafo de Atributos Modelo

Matrizes de similaridadede vértices e de arestas

Obter a solução (um casamento dos grafos) quemaximiza uma função de otimização que mede a

similaridade entre os grafos comparados

Extração dos atributosExtração dos atributos

Grafo de Atributos Imagem



1

Instanciando a proposta

Mapa Conceitual 1 Mapa Conceitual 2

Comparador Semântico:algoritmos de stemming (Rijsbergen 1980),

de desambiguação (Gerrig, Lesk 1990) e de busca em árvore de sinônimos criada

com base no banco de dados WordNet (Fellbaum 1998)

Matrizes de Similaridades Semânticas entre conceitos e entre relações

Resolução do PCG

GrafoExtração de Conceitos

e relaçõesGrafoExtração de Conceitos

e relações

GCMC WCMC



1

O algoritmo GRASP para Resolução do PCG

adaptado à Comparação de Mapas Conceituais (GCMC)

• A meta-heurística GRASP (Greedy RandomizedAdaptative Search Procedure) (Feo, Resende 1995) consiste em um algoritmo de melhoria que gera boas soluções (não necessariamente a ótima) para um problema

• Algoritmo iterativo no qual cada iteração consiste basicamente de duas fases: – construção de uma solução;

– sua utilização como solução inicial para um procedimento de busca local (uma busca local consiste em um procedimento de melhoria que gera a melhor solução pertencente a uma vizinhança de uma solução considerada como ponto de partida da busca).



1

O algoritmo GRASP para Resolução do PCG adaptado à Comparação de Mapas Conceituais (GCMC)

• O algoritmo GRASP utilizado neste trabalho é aquele proposto em (Sarmento 2005). – a cada iteração do algoritmo, uma solução é gradativamente construída

por elementos escolhidos dentre candidatos que não violem critérios de viabilidade estabelecidos no PCG.

– esta solução é utilizada como ponto de partida para a busca local, efetuada em uma vizinhança de soluções obtidas a partir da inicial por meio de trocas de associações estabelecidas entre vértices dos grafos comparados.

• São definidos como parâmetros do algoritmo: – o número máximo de iterações

– uma semente inicial para o gerador de números aleatórios, usados para a escolha aleatória dos elementos que irão compor a solução construída.

• O algoritmo termina com a melhor das soluções obtidas após a execução do número máximo de iterações.



1

Algoritmo de Wong, You e Chan baseado na técnica de Branch-and-Bound para Resolução do PCG adaptado à

Comparação de Mapas Conceituais (WCMC)

• proposto em (Wong et al. 1990) para a resolução do problema de isomorfismo de grafos.

• algoritmo exato

• considera-se que vértices de dois grafos de atributos, de mesmo tamanho, são associados segundo uma árvore de possibilidades. As associações e a construção da árvore são guiadas por uma função de custo (definida em (Wong et al. 1990)) que maximiza a similaridade entre os grafos comparados. A construção da árvore baseia-se na técnica de branch-and-bound.



1

Resultados Computacionais

• foram construídos 27 (vinte e sete) pares de

grafos de atributos representando mapas

conceituais, adquiridos do banco de dados

mundial do CMaptools (Cañas et al. 2004).

• foram gerados apenas pares de grafos de

mesmo tamanho, com estruturas semelhantes

(não necessariamente idênticas) e com alguns

atributos diferentes.



1


• Os pares de mapas construídos foram divididos em três grupos:– Grupo M1: pares de mapas conceituais com

estruturas de relacionamento idênticas e com alguns atributos referentes aos conceitos ou relações substituídos por sinônimos ou significados próximos;

– Grupo M2: pares de mapas conceituais com estruturas de relacionamento modificadas e com atributos idênticos;

– Grupo M3: pares de mapas conceituais com modificações impostas às estruturas de relacionamento e aos atributos dos mapas.



1


• Foram realizadas dez execuções do algoritmo GCMC e uma execução do algoritmo WCMC para cada par de mapas dos grupos M1, M2 e M3. Todos os testes computacionais foram realizados em um computador Athlon XP 2000+ com 768MB de RAM, sistema operacional Windows XP SP2 executando códigos compilados em C# no Visual Studio 2005.



1


19,84479,116660,04779,11666141014129

43,32870,767870,07870,76787131215148

7191,34374,282750,20374,1756221835287

176400Sem Resp.0,12564,36111392341306

3,92280,966660,04680,966667710105

37173,15669,412040,23468,35648282432274

1537,07892,511110,09490,5111114516153

498,12582,656860,07876,1686214918172

586,46989,778570,06389,778579414141

(s)(%)(s)(%)Modif.Modif.|E||V|# Par

TempoWCMCTempo GCMC|E||V|M1



1


17,3131000,0471000014129

31,9371000,0631000015148

3354,2031000,1721000035287

10817,5631000,2181000041306

4,5621000,0461000010105

3171,2811000,1711000032274

76,7191000,0781000016153

214,5781000,09491,764710018172

71,0311000,0631000014141





1


19,82879,116660,06279,11666141014129

41,35970,767870,06370,76787131215148

7234,71974,282750,20374,1756221835287

176400Sem Resp.0,15264,36111392341306

3,81280,966660,04780,966667710105

36880,6469,412040,20368,35648282432274

1521,54792,511110,07892,5111114516153

496,07882,656860,07882,6568614918172

584,7589,778570,04789,778579414141





1


• o algoritmo GCMC obteve:– resultados idênticos ao WCMC para 19 dos

27 pares de mapas

– resultados muito próximos ao WCMC para 7 pares de mapas

– para 2 pares de mapas o WCMC não obteve resposta no limite máximo estipulado de 7200 segundos.

– os tempos do GCMC foram muito menores do que aqueles gastos pelo WCMC



1

Conclusões

• manipular mapas conceituais como grafos de atributos e desta forma, utilizar algoritmos de comparação de grafos, heurísticos e exatos, para efetuar automaticamente a identificação de similaridades entre mapas.

• Os resultados experimentais obtidos indicam que o uso de técnicas automáticas de comparação de mapas conceituais viabiliza de forma eficiente tanto o acompanhamento e avaliação dos processosde construção de conhecimento do aprendiz quanto a classificaçãode documentos representados por mapas conceituais.

• Os resultados experimentais indicam uma qualidade satisfatória na identificação de similaridades entre os mapas comparados

• A proposta é genérica e aplica-se a mapas conceituais que utilizem qualquer idioma para descrever conceitos e relações.

• A adaptação para qualquer outro idioma depende exclusivamente da substituição do módulo de comparação de palavras.



1

Trabalhos Futuros

• validação e posterior aplicação das técnicas descritas em situações reais de aprendizagem, ou seja, utilizando mapas conceituais construídos por aprendizes de uma turma de um curso na área de Computação.

• Comparação desta proposta com outros comparadores de mapas conceituais da literatura

Documents

Uma Abordagem para Comparação de Mapas ... - cinted.ufrgs.br · Departamento de Informática CT/UFES 12 a 15 de dezembro/2006 1 Uma Abordagem para Comparação de Mapas Conceituais