Recuperação da Informação 2015-1Implementação

Vinicius Pessoni

Universidade Federal de GoiásInstituto de Informática

Mestrado em Ciência da Computação

1

Tópicos de Apresentação

● Revisão● Aplicação na Dissertação● Resultados● Conclusão

2

Revisão

3

Revisão - Conceitos

● Cluster: conjunto (agrupamento, grupo, aglomerado) de “objetos” (documentos, itens) similares;

● Algoritmos de Clusterização: agrupam um conjunto de objetos em subconjuntos ou “clusters”;

○ clusters internamente coerentes e claramente se distinguem;

● Forma mais comum de aprendizado não supervisionado:

○ SEM classificação prévia feita por experts humanos;

○ encontrar estrutura em dados não rotulados;4

Revisão - Conceitos

● Técnicas de Clusterização:

○ Hierarchical clustering (hierárquico):

■ cria uma estrutura hierárquica de clusters (relacionamentos);

■ não define previamente quantos clusters devem ser;

■ maioria determinísticos;

○ Hard Clustering: cada item é membro de um e somente um cluster;

5

Revisão - Otimização da Modularidade

● Sistemas sociais, tecnológicos e de informação podem ser descritos como redes complexas:

○ (grafo) topologia interconectada de nós, organização e aleatoriedade;

● Comunidades ajudam a descobrir informações;

● Alem disso, a meta-rede resultante, na qual os nós são as comunidades, ajuda a compreender a estrutura da rede original;

6

Revisão - Otimização da Modularidade

● A qualidade das partições (comunidades) resultantes é medida pela modularidade;

● Modularidade: é um valor escalar entre -1 e 1 que mede a densidade dos links dentro de uma comunidade em relação aos links entre comunidades:

○ usada para comparar a qualidade de partições obtidas por diferentes métodos de clusterização;

○ também uma função para otimizar ( exata é NP Hard, necessário algoritmos aproximativos );

7

Revisão - Otimização da Modularidade

● O método:

○ hierárquico, encontra partições com alta modularidade, mesmo em grandes volumes de dados (redes gigantes);

○ o algoritmo é dividido em duas fases, repetidas iterativamentes:

■ verificação de maximos locais ( mudança para comunidade vizinha );

■ criação da meta rede ( comunidades identificadas no passo 1);

8

Clusterização - Otimização da Modularidade

9

Implementaçãona

Dissertação

10

Clusterização - Otimização da Modularidade

● Implementação na Dissertação (trabalho da disciplina):

○ queremos medir o nível cognitivo e auxiliar os discentes a melhorá-lo, com isso melhorando o desempenho nos cursos;

● método aplicado: questionário com 24 questões “em duplas”;

○ discentes marcam as respostas e o raciocínio utilizado;

● dados: respostas dos questionários de 250 discentes;

11

Exemplo Questão

12

Clusterização - Otimização da Modularidade

● Aplicação na Dissertação (trabalho da disciplina):

○ passo 1: modelar respostas dos alunos e questões do questionário como um grafo bipartido ( rede complexa ):

○ passo 2: desenvolver programa em java que traduz as respostas do questionário na estrutura de grafos lida pelo programa que trabalha os grafos ( gephi );

○ passo 3: montar o grafo no gephi;

13

Clusterização - Otimização da Modularidade

● Aplicação na Dissertação (trabalho da disciplina):

○ passo 4: aplicar o algoritmo de descoberta de comunidades:

1. montar grafo aleatório;2. executar distribuição por forças ( Force Atlas 2 );3. descobrir parâmetros de estabilização;4. executar com parâmetros descobertos para verificar forma

estável;5. executar descoberta de comunidades;

○ passo 5: analisar as comunidades encontradas e o que isso significa para a pesquisa.

14

Clusterização - Otimização da Modularidade

● Aplicação na Dissertação (trabalho da disciplina):■ uma questão está relacionada a outra pelo erro de um

discente em uma e outra;

Erros João: 1, 2, 5, 6, 8

Arestas: 1 -> 2;1 -> 5;1 -> 6;1 -> 8;

2 -> 5;2 -> 6;2 -> 8;

15

5 -> 6;5 -> 8; 6 -> 8.

1

2

João

1

2

Clusterização - Otimização da Modularidade

4.1 Montar grafo aleatório

16

Clusterização - Otimização da Modularidade

4.2 Distribuição por forças (Force Atlas 2)

17

Clusterização - Otimização da Modularidade

4.3 Parâmetros de estabilização

Tolerância Velocidade: 0.01, pequeno, boa acurárcia e velocidade;

Modo LingLong: evidencia comunidades, é o nosso foco;

18

Clusterização - Otimização da Modularidade

4.4 Verificar forma estável

19

Clusterização - Otimização da Modularidade

4.5 Executar descoberta de comunidades

20

Clusterização - Otimização da Modularidade

4.5 Executar descoberta de comunidades

21

Clusterização - Otimização da Modularidade

Implicações para Pesquisa

● Indica agrupamento de dificuldade:○ fáceis, médias e difíceis;

● Confirmação da qualidade das questões das duplas de padrões:○ 1-2, 3-4, 5-6...;

● Confirma padrão de erro dos grupos ( 11,12, 13, 14 ) identificado por métodos estatísticos não paramétricos;

○ lembrar que nenhuma dessas informações foi informada;

● Diversas outras análises possíveis:○ triângulos (dependência entre 3 padrões);○ intermédio de caminho ( qual padrão fica entre um e outro );○ ... 22

Recuperação da Informação 2015-1Implementação

Vinicius Pessoni

Universidade Federal de GoiásInstituto de Informática

Mestrado em Ciência da Computação

23