IA368Q - Classificadores Baseados em Grafos - Floresta de Caminhos Ótimos - Teoria e Aplicações, 1S de 2012

Dados da Disciplina:
  • Professores Responsáveis: Roberto de Alencar Lotufo e Letícia Rittner
  • Horário: 408 409 608 609
  • Sala: PE-26
  • Ajuda
  • Lista de Alunos
Ementa:

Introdução a grafos, representação, conexidade, árvores, floresta. Principais algoritmos de grafos e caminhos mínimos: Dijkstra, árvore geradora mínima (MST). Transformada Imagem Floresta (IFT) e suas aplicações. Relações da IFT com a MST e a Transformada Watershed. Floresta de caminhos mínimos - OPF - Optimum Path Forest. Introdução de classificadores estatísticos, classificadores supervisionados e não supervisionados, classificadores paramétricos e não paramétricos. Aplicações e comparações da OPF com outros classificadores. Classificação de textura, de dígitos manuscritos.

Obs: O curso tem uma parte prática desenvolvida no ambiente Adessowiki, utilizando as linguagens Python e C/C++.

Pré-requisito:
Experiência em programação Python, C ou MATLAB.

Plano de aulas ( detalhamento)

       
01 29fev Introdução ao Adessowiki Exercício 1
02 02mar Introdução a grafos: conceitos básicos / Introdução ao Python e Numpy Exercício 2
03 07mar Introdução a Grafos: representação e visualização  
04 09mar Florestas e Árvores, caminhos, Busca em profundidade e em largura Exercício 3
05 14mar Componentes conexos, Minimum Spanning Tree (teoria)  
06 16mar MST - algoritmos (Boruvka, Kruskal e Prim) Exercício 4
07 21mar Análise das soluções apresentadas para os exercícios 3 e 4  
08 23mar MST - discussão sobre performance dos algoritmos (artigo) Exercício 5
09 28mar Comparação de resultados das implementações para cálculo dos componentes conexos Exercício 6
10 30mar Caminho Mínimo - teoria e algoritmos Exercício 7
11 04abr Calssificadores - conceitos básicos Exercício 8
00 06abr Feriado (não haverá aula)  
12 11abr Classificação de Padrões (teoria)  
13 13abr Extração de Descritores  
14 18abr Classificação de Padrões - OPF (teoria) Aula Classificadores
15 20abr Classificação Supervisionada com OPF  
16 25abr Implementação da OPF Exercício 10
17 27abr Descritores de imagem Exercício 11
18 02mai OPF e 1-NN Exercício 12
19 04mai    
20 09mai 1-NN - Redução de dados  
21 11mai Apresentação sobre SVM / Escolha do tema da monografia de cada um  
22 16mai Francisco, Roberto, Mariana, Fernanda Exercício 13
23 18mai André, Tiago, Thiago  
00 23mai Não houve aula  
24 25mai Giovani, Wendell, Eric, Rodrigo  
25 30mai Definição das funções primitivas em grafo, acompanhamento projetos  
26 01jun Funções CC e MST  
27 06jun Funções Single Linkage, Dijkstra, OPF  
00 08jun Corpus Christi  
00 13jun Dúvidas  
28 15jun Seminários: Roberto, André, Wesley  
29 20jun Seminários: Fernanda, Wendell, Giovani,Tiago  
30 22jun Seminários: Eric, Francisco, Rodrigo, Thiago  

Bibliografia

  1. J. P. Papa, A. X. Falcão, and Celso T. N. Suzuki. Supervised pattern classification based on optimum-path forest. International Journal of Imaging Systems and Technology, 19(2):120-131, 2009: link
  2. L.M. Rocha, F.A.M. Cappabianco, and A.X. Falcão Data clustering as an optimum-path forest problem with applications in image analysis. International Journal of Imaging Systems and Technology, 19(2):50-68, 2009.
  3. A.X. Falcão, J. Stolfi, and R.A. Lotufo. The image foresting transform: Theory, algorithms, and applications. IEEE Transactions on Pattern Analysis and Machine Intelligence, 26(1):19-29, Jan 2004.
  4. Thomas H. Cormen Charles E. Leiserson Ronald L. Rivest Clifford Stein, Introduction to Algorithms. 3rd edition, MIT Press. 2009.
  5. J. P. Papa, F. A. M. Cappabianco, A. X. Falcão. Optimizing Optimum-Path Forest Classification for Huge Datasets. ICPR 2010 link
  6. Hart. The Condensed Nearest Neighbor Rule. 1968. IEEE Trans. on Information Theory. link.
  7. Angiulli. Fast Condensed Nearest Neighbor Rule. 2005. ICML 2005 Proceedings of the 22nd international conference on Machine learning. link.

Forma de Avaliação:

Honor Code

All students participating the class must agree to abide by the following code of conduct:

  • I will only register for one account.
  • My answers to homework, quizzes and exams will be my own work.
  • I will not post or discuss the solutions to homeworks, quizzes or exams until after the answers have been released by the instructors.
  • I will not engage in any other activities that will dishonestly improve my results or dishonestly improve/hurt the results of others.
Recently modified pages
More
Recently commented pages
More