fra_8

Francisco Leite | Biblioteca | Página Inicial

Autor:frande
Data:08/04/2012

2.Parte 2

Item 1. Implementar uma função que monta os clusters a partir da MST

A função está implementada na Biblioteca na seção função de análise de cluster, a qual usa o algoritmo de Kruskal para grafos com mais de uma componente conexa.

Item 2. Testes

  • Grafo de teste contendo 3 classes

Neste grafo de testes cada elemento possui uma distância de 1 unidade dentro da mesma classe. A classe 1 possui uma distância de 5 para a classe 2 e 8 para classe 3. A classe 2 possui distância de 5 para classe 1 e 7 para classe 3. Já a classe 3 possui distância de 8 para classe 1 e 7 para a classe 2.

 1 import numpy
 2 import fer_lib as fer
 3 
 4 d=ones((6,6),int)*float('inf')
 5 d[0,1]=1
 6 d[0,2]=5
 7 d[0,3]=5
 8 d[0,4]=8
 9 d[0,5]=8
10 
11 d[1,0]=1
12 d[1,2]=5
13 d[1,3]=5
14 d[1,4]=8
15 d[1,5]=8
16 
17 d[2,0]=5
18 d[2,1]=5
19 d[2,3]=1
20 d[2,4]=7
21 d[2,5]=7
22 
23 d[3,0]=5
24 d[3,2]=1
25 d[3,1]=5
26 d[3,4]=7
27 d[3,5]=7
28 
29 d[4,0]=8
30 d[4,2]=7
31 d[4,3]=7
32 d[4,1]=8
33 d[4,5]=1
34 
35 d[5,0]=8
36 d[5,2]=7
37 d[5,3]=7
38 d[5,1]=8
39 d[5,4]=1
40 
41 mmgraphviz(fer.drawGraph(d ,False,True), title='Grafo teste')
/media/_xsb/courseIA368Q1S2012/fra_8/GRVIZ28884_001.png

Grafo teste

  • Teste usando Threshold
1 import fra_lib
2 import fra_lib_8 as fra
3 print("Usando o threshold de 7 para separar a classe 3 das outras 2")
4 print("2 classes: ",fra.cluster(d,7,0))
5 print("Usando o threshold de 4 para separar as 3 classes")
6 print("3 classes: ",fra.cluster(d,5,0))
7 print("Usando o threshold de 8 só separa a classe 3 da 1, mas não da 2, nem a 2 da 1")
8 print("1 classe: ",fra.cluster(d,5,0))
Usando o threshold de 7 para separar a classe 3 das outras 2
('2 classes: ', [[7.0, 0, 1, 2, 3], [1.0, 4, 5]])
Usando o threshold de 4 para separar as 3 classes
('3 classes: ', [[1.0, 0, 1], [1.0, 2, 3], [1.0, 4, 5]])
Usando o threshold de 8 só separa a classe 3 da 1, mas não da 2, nem a 2 da 1
('1 classe: ', [[1.0, 0, 1], [1.0, 2, 3], [1.0, 4, 5]])
  • Teste usando Número de classes desejadas
1 import fra_lib
2 import fra_lib_8 as fra
3 print("Obtendo 2 classes")
4 print("2 classes: ",fra.cluster(d,0,2))
5 print("Obtendo 3 classes")
6 print("3 classes: ",fra.cluster(d,0,3))
7 print("Obtendo 1 classe")
8 print("1 classe: ",fra.cluster(d,0,1))
Obtendo 2 classes
('2 classes: ', [[7.0, 0, 1, 2, 3], [1.0, 4, 5]])
Obtendo 3 classes
('3 classes: ', [[1.0, 0, 1], [1.0, 2, 3], [1.0, 4, 5]])
Obtendo 1 classe
('1 classe: ', [[15.0, 0, 1, 2, 3, 4, 5]])