Reconhecimento de
Padrões
Métodos, Técnicas e Ferramentas para Aprendizado e
Classificação de Dados
Prof. Dr. rer.nat. Aldo von Wangenheim
Antonio da Luz Jr. (estag. docência)
The Cyclops Project
German-Brazilian Cooperation Programme on IT
CNPq GMD DLR
Noções de Conjuntos de Dados,
Métricas de Distância,
Normalização e Técnicas de
Classificação
The Cyclops Project
German-Brazilian Cooperation Programme on IT
CNPq GMD DLR
The Cyclops Project
German-Brazilian Cooperation Programme on IT
CNPq GMD DLR
Disciplina Reconhecimento de Padrões
Curso de Ciência da Computação
INE/CTC/UFSC
Características: Reconhecimento de Padrões
• Geralmente dados sob a forma de pares atributo-valor
– atributo é definido pela posição do valor em um vetor de dados,
– ex.: (1 2 4 11.01 1), representando: (num_imóveis, num_carros,
num_filhos, idade_media_filhos, bom/mau pagador)
• Dados numéricos ou representações numéricas de dados simbólicos
– ex: 1=fumante, 2=não fumante, 3=fumante eventual.
• Se os padrões são pré-classificados em classes, essas
geralmente são resultado da experiência de usuários humanos
no domínio de aplicação.
• Objetivo quase sempre será o de reconhecer padrões
– classificá-los, porém sem gerar explicações complexas sobre o porquê
desta classificação.
The Cyclops Project
Disciplina Reconhecimento de Padrões
German-Brazilian Cooperation Programme on IT
CNPq GMD DLR
Curso de Ciência da Computação
INE/CTC/UFSC
Como classificamos padrões ?
• Se já sabemos quantas categorias possuímos e temos
exemplos de instâncias de cada categoria: queremos
criar um classificador
– Vai utilizar nossos exemplos para classificar novos dados.
• Se temos dados mas não sabemos como se
organizam, temos de minerá-los: queremos criar um
agrupador
– O resultado desse agrupamento pode ser utilizado para
classificações futuras.
Disciplina Reconhecimento de Padrões
The Cyclops Project
Curso de Ciência da Computação
INE/CTC/UFSC
German-Brazilian Cooperation Programme on IT
CNPq GMD DLR
Conjuntos de Dados
• Conjuntos de dados 2D
(10
2000)
• Conjuntos de dados n-D
(40
(20
4
5
100
1)
4
1)
The Cyclops Project
German-Brazilian Cooperation Programme on IT
CNPq GMD DLR
Disciplina Reconhecimento de Padrões
Curso de Ciência da Computação
INE/CTC/UFSC
Conjunto de Dados em Espiral
• Conjunto de dados 2D distribuídos em um
Sistema de Coordenadas Polares (r, θ)
• Os conjuntos de dados em espiral podem ser
utilizados para testes de performance em
algoritmos de classificação de dados
– podem ser gerados automaticamente com
variados graus de detalhes e ruído.
The Cyclops Project
German-Brazilian Cooperation Programme on IT
CNPq GMD DLR
Disciplina Reconhecimento de Padrões
Curso de Ciência da Computação
INE/CTC/UFSC
Espiral simples
• Temos dados distribuídos em espiral
– Cada ponto representa o protótipo de uma categoria
ou classe.
• A tarefa de reconhecimento de padrões é
classificá-los adequadamente, de forma a associar
outros dados aleatórios a uma das classes
existente na espiral
The Cyclops Project
German-Brazilian Cooperation Programme on IT
CNPq GMD DLR
Disciplina Reconhecimento de Padrões
Curso de Ciência da Computação
INE/CTC/UFSC
The Cyclops Project
German-Brazilian Cooperation Programme on IT
CNPq GMD DLR
Disciplina Reconhecimento de Padrões
Curso de Ciência da Computação
INE/CTC/UFSC
Espiral dupla
• As espirais duplas constituem um problema
diferente da espiral simples.
– Em uma espiral dupla, cada braço da espiral
representa uma categoria ou classe.
– Cada classe é representada por muitos pontos, que
são organizados sob forma de espiral.
• A tarefa aqui é classificar um ponto aleatório
como pertencente a uma determinada classe,
representada através de um braço da espiral.
The Cyclops Project
German-Brazilian Cooperation Programme on IT
CNPq GMD DLR
Disciplina Reconhecimento de Padrões
Curso de Ciência da Computação
INE/CTC/UFSC
• Na espiral dupla, cada classe é representada por
um conjunto de pontos, organizados em espiral
– os dois conjuntos de dados não são linearmente
separáveis.
The Cyclops Project
German-Brazilian Cooperation Programme on IT
CNPq GMD DLR
Disciplina Reconhecimento de Padrões
Curso de Ciência da Computação
INE/CTC/UFSC
The Cyclops Project
German-Brazilian Cooperation Programme on IT
CNPq GMD DLR
Espiral dupla sem ruído
Disciplina Reconhecimento de Padrões
Curso de Ciência da Computação
INE/CTC/UFSC
The Cyclops Project
Disciplina Reconhecimento de Padrões
German-Brazilian Cooperation Programme on IT
CNPq GMD DLR
Espiral dupla com pouco ruído
Curso de Ciência da Computação
INE/CTC/UFSC
The Cyclops Project
Disciplina Reconhecimento de Padrões
German-Brazilian Cooperation Programme on IT
CNPq GMD DLR
Espiral dupla com bastante ruído
Curso de Ciência da Computação
INE/CTC/UFSC
The Cyclops Project
German-Brazilian Cooperation Programme on IT
CNPq GMD DLR
Disciplina Reconhecimento de Padrões
Curso de Ciência da Computação
INE/CTC/UFSC
Métricas de Distância
• O que são métricas de distância?!
– São funções utilizadas para se determinar o grau de
dissimilaridade entre dois ou mais valores
• Onde se aplicam?!
– Avaliação de dissimilaridade entre objetos durante o
processo de classificação ou agrupamento de padrões
– Podem ser utilizados em qualquer situação em que se
queira determinar a quão distante um objeto está do
outro
Disciplina Reconhecimento de Padrões
The Cyclops Project
German-Brazilian Cooperation Programme on IT
CNPq GMD DLR
Curso de Ciência da Computação
INE/CTC/UFSC
Distância de Hamming
• Originalmente criada para vetores binários:
– media distância entre vetores contando o número de
bits diferentes: mismatch count.
dH(1011101 , 1001001) = 2
dH(pato , mata) = 2
The Cyclops Project
Disciplina Reconhecimento de Padrões
German-Brazilian Cooperation Programme on IT
CNPq GMD DLR
Curso de Ciência da Computação
INE/CTC/UFSC
Distância de Hamming Extendida
• Mais útil em RP que a original
– Cálculo extremamente rápido
Disciplina Reconhecimento de Padrões
The Cyclops Project
Curso de Ciência da Computação
INE/CTC/UFSC
German-Brazilian Cooperation Programme on IT
CNPq GMD DLR
Distância de Hamming Extendida
dH+ ( (10
2000
20
4
0
0
0)
(2
3000
40
5
100
4
1) )
= 8 + 1000 + 20 + 1 + 100 + 4 + 1
= 1134
The Cyclops Project
German-Brazilian Cooperation Programme on IT
CNPq GMD DLR
Disciplina Reconhecimento de Padrões
Curso de Ciência da Computação
INE/CTC/UFSC
Distância Euclidiana
• Provê a real distância entre dois pontos em um espaço
n-dimensional qualquer.
– Cálculo demorado para dimensões elevadas
Disciplina Reconhecimento de Padrões
The Cyclops Project
Curso de Ciência da Computação
INE/CTC/UFSC
German-Brazilian Cooperation Programme on IT
CNPq GMD DLR
Distância Euclidiana
dE ( (10
2000
20
4
0
0
0)
(2
3000
40
5
100
4
1) )
= 1.005,23
The Cyclops Project
Disciplina Reconhecimento de Padrões
German-Brazilian Cooperation Programme on IT
CNPq GMD DLR
Curso de Ciência da Computação
INE/CTC/UFSC
Normalização de Valores
• Por que normalizar?!
– Aproximar valores com escalas muito diferentes
– Facilitar a manipulação e interpretação dos dados
• Como normalizar?!
– Um valor normalizado é obtido pela divisão desse valor
pelo resultado da soma de todos os valores existentes
no conjunto
The Cyclops Project
German-Brazilian Cooperation Programme on IT
CNPq GMD DLR
Disciplina Reconhecimento de Padrões
Curso de Ciência da Computação
INE/CTC/UFSC
Técnicas de Classificação de Dados
• É um conjunto de regras que devem ser seguidas
durante o processo de classificação de novos conjuntos
de dados (padrões) dentro de um determinado domínio
• Servem para identificar a qual classe de dados
existente o novo conjunto deve ser associado
• Muitas vezes se utilizam das Métricas de Distância para
determinar o grau de dissimilaridade entre o novo
padrão e os já existentes no domínio
The Cyclops Project
Disciplina Reconhecimento de Padrões
German-Brazilian Cooperation Programme on IT
CNPq GMD DLR
Curso de Ciência da Computação
INE/CTC/UFSC
Nearest Neighbour - NN
• Classifica um novo padrão calculando a
distância deste a todos os outros em alguma
métrica predefinida e escolhe como classe para
ele a classe daquele mais próximo nesta
métrica.
Disciplina Reconhecimento de Padrões
The Cyclops Project
German-Brazilian Cooperation Programme on IT
CNPq GMD DLR
?
Curso de Ciência da Computação
INE/CTC/UFSC
The Cyclops Project
German-Brazilian Cooperation Programme on IT
CNPq GMD DLR
Disciplina Reconhecimento de Padrões
Curso de Ciência da Computação
INE/CTC/UFSC
k-Nearest Neighbour
• k-NN utiliza um critério de votação:
– observa os k padrões mais próximos ao novo padrão a
ser classificado.
• Classifica o padrão com a classe mais freqüente
na lista dos k padrões analisados.
Disciplina Reconhecimento de Padrões
The Cyclops Project
German-Brazilian Cooperation Programme on IT
CNPq GMD DLR
?
Curso de Ciência da Computação
INE/CTC/UFSC
Tesselação:
Triangulação de Delaunay e
Diagrama de Voronoi
The Cyclops Project
German-Brazilian Cooperation Programme on IT
CNPq GMD DLR
The Cyclops Project
German-Brazilian Cooperation Programme on IT
CNPq GMD DLR
Disciplina Reconhecimento de Padrões
Curso de Ciência da Computação
INE/CTC/UFSC
Tesselação
• Uma outra forma de gerarmos um classificador
para padrões é dividirmos o espaço de dados em
regiões através de algum método geométrico.
• Cada região representa então uma categoria ou
classe. Classificamos padrões observando em que
região caem.
• A forma mais tradicional de Tesselação é o
Diagrama de Voronoi.
The Cyclops Project
German-Brazilian Cooperation Programme on IT
CNPq GMD DLR
Disciplina Reconhecimento de Padrões
Curso de Ciência da Computação
INE/CTC/UFSC
O que é um Diagrama de Voronoi ?
• Foi inventado para resolver um problema
simples:
– Como dividir uma cidade em áreas irregulares de
forma a que a área coberta por um carteiro
vinculado a uma determinada agência de correio
seja otimizada ?
The Cyclops Project
German-Brazilian Cooperation Programme on IT
CNPq GMD DLR
Disciplina Reconhecimento de Padrões
Curso de Ciência da Computação
INE/CTC/UFSC
O que é um Diagrama de Voronoi ?
• G. F. Voronoi, em sua tese de doutorado intitulada Ob
odnom obobshchenii algorifma nepreryvnykh drobei
(Sobre uma generalização do algoritmo de quebra de
cadeias.), publicada em Varsóvia, Polônia, em 1896,
desenvolveu um método onde,
– com base em uma triangulação pré-existente de pontos que
representam os centros de alguma coisa (no caso da
primeira aplicação, agências de correio),
– se determina qual a área de influência de cada um destes
centros em função da posição dos outros centros,
delimitando de forma geométrica cada área de influência.
The Cyclops Project
German-Brazilian Cooperation Programme on IT
CNPq GMD DLR
Disciplina Reconhecimento de Padrões
Curso de Ciência da Computação
INE/CTC/UFSC
O que é um Diagrama de Voronoi ?
The Cyclops Project
German-Brazilian Cooperation Programme on IT
CNPq GMD DLR
Disciplina Reconhecimento de Padrões
Curso de Ciência da Computação
INE/CTC/UFSC
O que é um Diagrama de Voronoi ?
• Chamamos estes "centros" de centróides.
– Se nós temos um conjunto de padrões constituído de um elemento
típico para cada categoria que queremos representar (protótipo),
podemos nos utilizar do diagrama de Voronoi para determinar a
extensão de cada uma das categorias, simplesmente utilizando
cada um dos protótipos como um centróide e gerando um
diagrama de Voronoi sobre estes.
• Para podermos gerar um diagrama de Voronoi partimos do
conjunto de protótipos e geramos primeiramente uma
triangulação.
– Para isto utilizamos o método da Triangulação de Delaunay
The Cyclops Project
German-Brazilian Cooperation Programme on IT
CNPq GMD DLR
Disciplina Reconhecimento de Padrões
Curso de Ciência da Computação
INE/CTC/UFSC
The Cyclops Project
German-Brazilian Cooperation Programme on IT
CNPq GMD DLR
Disciplina Reconhecimento de Padrões
Curso de Ciência da Computação
INE/CTC/UFSC
The Cyclops Project
German-Brazilian Cooperation Programme on IT
CNPq GMD DLR
Disciplina Reconhecimento de Padrões
Curso de Ciência da Computação
INE/CTC/UFSC
The Cyclops Project
German-Brazilian Cooperation Programme on IT
CNPq GMD DLR
Disciplina Reconhecimento de Padrões
Curso de Ciência da Computação
INE/CTC/UFSC
The Cyclops Project
German-Brazilian Cooperation Programme on IT
CNPq GMD DLR
Disciplina Reconhecimento de Padrões
Curso de Ciência da Computação
INE/CTC/UFSC
The Cyclops Project
German-Brazilian Cooperation Programme on IT
CNPq GMD DLR
Disciplina Reconhecimento de Padrões
Curso de Ciência da Computação
INE/CTC/UFSC
The Cyclops Project
German-Brazilian Cooperation Programme on IT
CNPq GMD DLR
Disciplina Reconhecimento de Padrões
Curso de Ciência da Computação
INE/CTC/UFSC
The Cyclops Project
German-Brazilian Cooperation Programme on IT
CNPq GMD DLR
Disciplina Reconhecimento de Padrões
Curso de Ciência da Computação
INE/CTC/UFSC
The Cyclops Project
German-Brazilian Cooperation Programme on IT
CNPq GMD DLR
Disciplina Reconhecimento de Padrões
Curso de Ciência da Computação
INE/CTC/UFSC
Exercícios (entregar 25/09/2006)
• Definir 4 conjuntos de dados: 2 qquer (2D e nD) e 2 espirais
– Ex.: dos sites sugeridos
– Espiral: Gerar com e sem ruído e com número variável de elementos
de dados.
• Implementar Hamming+, DE, NN e kNN
– Gerar dados aleatórios e testar com todos os 4 conjuntos.
– Mostrar pela cor com qual categoria foram classificados os dados
aleatórios (interface gráfica).
• Implementar diagrama de Voronoi
– Gerar dados aleatórios e testar no conj. 2D e nas duas espirais
– Apresentar os resultados com interface gráfica
The Cyclops Project
Disciplina Reconhecimento de Padrões
German-Brazilian Cooperation Programme on IT
CNPq GMD DLR
Curso de Ciência da Computação
INE/CTC/UFSC
Sugestões
• http://www.voronoi.com/
• http://www.ics.uci.edu/~eppstein/gina/scot.drysdale.html
• http://www.cs.cornell.edu/Info/People/chew/Delaunay.html
• http://mathworld.wolfram.com/VoronoiDiagram.html
• http://www.msi.umn.edu/~schaudt/voronoi/voronoi.html
• http://www.diku.dk/hjemmesider/studerende/duff/Fortune/
• http://www.cs.unc.edu/~geom/voronoi/
• http://www.csie.ntu.edu.tw/~b5506061/voronoi/Voronoi.html
• http://www.ifor.math.ethz.ch/~fukuda/polyfaq/node27.html
• http://www.dr-mikes-maths.com/DotPlacer.html
• http://wwwp.fc.unesp.br/~mauri/Down/Polares.pdf