Reconhecimento de Padrões
1
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
Introdução



O que é RP ?
RP engloba uma literatura tão vasta que sua
definição é polêmica.
RP está ligada a busca de “regularidades”
Deste tempos pré-históricos, o homem buscou
“regularidades” em que pudesse confiar e que
lhe desse uma sensação de segurança num
mundo hostil.
TE073 – Processamento Digital de Sinais II
2
Distâncias na Aprendizagem Automática
3
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
Sumario
•Pesquisa nos dados
• Princípio da similaridade
• Distâncias e Métrica de Distâncias
• Um modelo unificado de distância
TE073 – Processamento Digital de Sinais II
4
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
Pesquisa nos dados
•Pesquisar dados é fundamental na Ciência da Computação
• Tradicionalmente BD organizadas em “dados estruturados”
•Evolução Tec. de Informação: “dados não estruturados”:
•Pesquisa por similaridade ou proximidade (similarity/proximity
searching) Procurar objetos que são parecidos ou próximos
•Similaridade modelada como função da distância que satisfaz
desigualdade do triângulo. Objetos formam “espaço métrico”
TE073 – Processamento Digital de Sinais II
5
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
Espaço métrico
Uma função d(x,y) não negativa que descreve a distância entre
pontos vizinhos num conjunto constitui uma métrica
Espaço métrico um conjunto que possui uma métrica:
(S, d)
Formado por conjunto S de objetos válidos com uma função de
distância global d(x, y) > 0 onde a distância entre pontos está
definida.
Satisfaz x, y, z  S:
(I)
d(x, y)  0
não negativa
(II)
d(x, y) = d(y, x)
simetria
(III) d(x, x) = 0
reflexividade
(IV) x  y  d(x, y) > 0
estritamente positiva
(V)
d(x, y)  d(x, z) + d(z, y) desigualdade triangular
TE073 – Processamento Digital de Sinais II
6
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
Se os objetos do espaço métrico têm k coordenadas de valores
reais, então temos um espaço métrico especial chamado
Espaço Vectorial (vector space)
e os vectores: VECTOR K-DIMENSIONAL
r= (A1|v1, A2|v2,..,Ai|vi,.,Ax|vk , cL )
Em qualquer espaço métrico podemos definir Bolas Abertas:
B(x; r) = {y   | d(x, y) < r} x  , r =raio da bola
TE073 – Processamento Digital de Sinais II
7
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
Objetos no espaço 2-dimensional
A1
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
TE073 – Processamento Digital de Sinais II
O
A2
8
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
Objetos no espaço 3-dimensional
A1
A2
O
O
O
O
O
O
O
O
O
O
O
O
O
TE073 – Processamento Digital de Sinais II
A3
9
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
Principio da Similaridade
A similaridade é uma medida continua de uma simetria imperfeita.
(Sendo a simetria uma medida de algo que não é possível distinguir)
Aplicado nas mais diversas ciências:
Medicina e Homeopatia : A lei dos similares
Psicologia cognitiva: comportamento
Estrutura molecular: entropia e similaridade
Percepção visual
Geometria computacional
Teoria da Informação: entropia - similaridade - informação
Reconhecimento de Padrões: métodos baseados em casos
TE073 – Processamento Digital de Sinais II
10
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
O Principio de similaridade afirma que as coisas que
partilham características visuais tais como a forma, o
tamanho, a cor, textura, valor ou orientação, serão vistas
como pertencentes a um todo.
No exemplo a direita as duas linhas enchidas dão aos nossos
olhos a impressão de duas linhas horizontais, mesmo se todos
os círculos presentes são equidistantes entre eles.
No exemplo a esquerda, os círculos maiores aparecem
pertencer juntos pela sua similaridade em tamanho.
(fonte: Gestalt principles, Bonnie Skaalid)
TE073 – Processamento Digital de Sinais II
11
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
Principio da Similaridade e Classificação
Um registo pertence à classe c, se o(s) registo(s) mais
próximo(s) no espaço n-dimensional dos registos
conhecidos (treino) pertence à mesma classe c
Utiliza: Abstração matemática de distância
TE073 – Processamento Digital de Sinais II
12
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
Aplicações na Pesquisa por Similaridade
Bases de Dados estruturadas
pesquisa de chave, intervalo, proximidade
Objetos Multimédia
Imagens, impressões digitais, áudio, SIG
Texto livre não estruturado
Conceitos semânticos, palavras relevantes, pronuncia
Biologia computacional:
sequências DNA e proteínas
Reconhecimento de Padrões e Funções de Aproximação
Compressão de áudio e vídeo:
enviando frames e sub-frames num canal de comunicação
TE073 – Processamento Digital de Sinais II
13
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
Distâncias
A distância entre dois pontos é o comprimento da linha que os
conecta.
No caso de vetores: muitas funções para calcular as distâncias
Estruturas de pesquisa para espaços vectoriais : SAM
kd-trees, R-trees, X-trees, quad-trees,...
A mais utilizada é aquela da família de distâncias Minkowski:
1/ s
k
s
Ls((x1,...,xk),(y1,...,yk)) =
i
i
i 1


 x  y 


No caso de vectores é conhecida como norma L2 ||x||2 ou Euclidiana
TE073 – Processamento Digital de Sinais II
14
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
Distâncias
m
L= 1, Manhattan (City block)
d ( x, y)   xi  yi
i 1
L = 2, Euclidiana
d ( x, y ) 
m
 (x  y )
i 1
L = , Chebychev
i
m
d ( x, y)  max xi  yi
i 1
d ( x, y )   det V 
1/ m
Mahalanobis
i
2
1
x

y
V


 x  y
TE073 – Processamento Digital de Sinais II
T
15
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
m
d ( x, y )  
Canberra
i 1
xi  yi
xi  yi
 m

d ( x, y )   x  y  Q  x  y       xi  yi  q ji   x j  y j 
j 1  i 1

m
Quadrática
T
m
Correlação
d ( x, y) 
 xi  xi  yi  yi 

i1
m


i1
xi  xi
2 m
 
i1
yi  yi

2
yi 
1  xi
d ( x, y)  



sizey 
i 1 sumi  sizex
m
Chi-quadrado
2
E ainda Hamming , Edit, Housdorff distances
TE073 – Processamento Digital de Sinais II
16
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
Pesquisas de interesse nos espaços métricos:
1) Pesquisa por intervalos: (q, r) d
Obter todos os objetos que estão a uma distância r de q.
{ x  S | d(q, x)  r }
2) Pesquisa do Vizinho mais Próximo: (Nearest Neighbor ou
NN): Obter os objetos mais perto de q  S.
{ x  S, |  y  S, d(q, x)  d(q, y) }
3) k-NN: Tirar os k objetos mais próximos de q S
obter um conjunto A  S tal que |A|= k , e
x A, y S - A, d(q, x)  d(q, y)
TE073 – Processamento Digital de Sinais II
17
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
Exemplo de pesquisa de intervalo para 2
3
pesquisa
4
2
10
5
1
8
7
{x  , d(q, x)  r}
q
6
9
11
12
(q, r)d q  , r é um número real indicando o raio
(tolerância) da pesquisa
Espaço: (n), construção: (n log n), query: (n)
TE073 – Processamento Digital de Sinais II
18
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
Conjunto dos pontos a uma mesma distância do centro. Depende do tipo de distância
TE073 – Processamento Digital de Sinais II
19
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
3
4
pesquisa
2
10
5
1
8
7
p
Para cada distância i > 0:
q
i = { x , d(x, p) = i }
6
9
11
12
p = raiz
i=2
7
3
6, 10
4
5,11
5
6
4,8,9,12
1.2.3
Árvore BKT : pesquisa de intervalo para funções discretas
Dados pesquisa q e distancia r, percorremos todos os filhos i tais que:
d(p, q) - r  i  d(p, q) + r (recursivamente)
Espaço: (n), constr: (n log n), query: (n)
TE073 – Processamento Digital de Sinais II
20
Universidade Federal do Paraná
Setor de Tecnologia
12
Departamento de Engenharia Elétrica
3
p
2
3.1
7
4
10
p
> 3.1
7
9
6
9
<= 2.9
14
15
5
<= 3.1
15
>2.9 <=4
>4
6
3
8
1
13
8
14 4
10 1 13 2 12 5
Espaço: (n), constr: (n log n), query: (log n), r pequeno
Árvore VPT : pesquisa para funções distância continuas
árvore binária recursiva com qualquer objeto p como raiz
Calcula-se a mediana do conjunto de todas as distâncias:
M = mediana {d(p, x) x  S}
sub-árvore esq: d(p, x) <= M
sub-árvore dir: d(p, x) > M
Pesquisa: d = d(q, p). if d - r >= M -----> esquerda
if d + r > M -----> direita
TE073 – Processamento Digital de Sinais II
21
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
Pesquisa método Vizinho mais próximo (NN)
Principio de similaridade
Aprendizagem com dados de treino
A1
A2
TE073 – Processamento Digital de Sinais II
22
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
NN: Método de pesquisa por incremento do raio
Procurar q com raio fixo r = ai  (a > 1),
a começar com i = 0;
Incrementar até obter Sk = {x  S, r = ai }
O valor do raio pode ser refinado mais tarde
entre:
r= ai-1 
e
r = ai 
Complexidade aumenta rapidamente com r
por isto incremento pode ser a --> 1
TE073 – Processamento Digital de Sinais II
23
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
NN: Backtracking com raio descrescente
Iniciar a procura numa estrutura qualquer com
raio r* = 
Cada vez q comparado com elemento p, atualiza raio
de pesquisa: r*  min((r*, d(q, p))
e continua a pesquisa agora com este raio reduzido .....
Importante encontrar rapidamente os objetos próximos
A complexidade da procura dependerá da
estrutura de dados utilizada
TE073 – Processamento Digital de Sinais II
24
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
k-Nearest Neighbors: aprendizagem "preguiçosa"
Ideia: manter os k objetos mais próximos de q,
Fixando o valor de r* como a distância máxima entre
aqueles elementos e q. Inicialmente raio r* = 
Cada novo objeto relevante, é inserido como um dos k
vizinhos mais próximos.
d ( x, y ) 
m
 (x  y )
i 1
i
2
i
Complexidade classificação: ( n x m) n=registos, m atributos
TE073 – Processamento Digital de Sinais II
25
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
Árvores k- dimensionais
Uma árvore binária onde os nós correspondem a regiões no
espaço n-dimensional
A raiz da árvore corresponde a todo o espaço
Os dois filhos num nó correspondem a divisão em uma dimensão
Exemplo árvore 2-dimensional
[2,5]
[8,9]
[3,8]
[6,3]
[3,8]
[2,5]
[8,9]
[6,3]
TE073 – Processamento Digital de Sinais II
26
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
Procura nas Árvores k-d (kd-trees)
Primeira aproximação: procura o nó que contém o alvo
Procura NN num kd-tree
(log n)
Objeto que contem o nó onde está o alvo
Voltamos ao pai do nó atual
x
Solução possível só se há interseção entre o
círculo e a área do pai
não precisamos calcular para este
algoritmo volta ao nó anterior
(acima da horizontal )
TE073 – Processamento Digital de Sinais II
27
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
Procura nas Árvores k-d (kd-trees)
Primeira aproximação: procura o nó que contém o alvo
Pesquisando nós em uma kd-tree
Só uns poucos nós são pesquisados
x
TE073 – Processamento Digital de Sinais II
28
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
Procura nas Árvores k-d (kd-trees)
Primeira aproximação: procura o nó que contem o alvo
Pesquisando nós em uma kd-tree
Uma má distribuição dos objectos
faz com que quase todos os nós
sejam pesquisados
TE073 – Processamento Digital de Sinais II
29
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
Dados
Em geral:
Todos os algoritmos utilizando
índices partilham o conjunto S em
subconjuntos
Index
Indexação em espaços métricos
TE073 – Processamento Digital de Sinais II
30
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
Pesquisa
Percorrer o Índice
q
Pesquisar em classes candidatas
TE073 – Processamento Digital de Sinais II
31
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
Modelo unificado [Chávez et al, 2001]
Todos algoritmos utilizando índices na pesquisa proximidade, constróem relações
equivalentes. A pesquisa só se concentra em algumas classes
relações equivalentes : Dado conjunto  definimos uma partição
() = {1, 2,...n} uma colecção de conjuntos disjuntos cuja união é 
i =  e  i  j, i  j = . Cada elemento da partição: classe equivalente
Uma relação é um subconjunto do produto externo  x  de .
Dois elementos x,y estão relacionados x~y, se o par (x, y) está no subconjunto.
A relação equivalente x  y, se para x, y   satisfaz:
Reflexividade:
Simetria:
(x  x)
(x  y  y  x)
Transitividade:
(x  y  y  z x  z)
TE073 – Processamento Digital de Sinais II
32
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
Relações equivalentes são de 2 tipos:
a) Relacões são definidas em termos de distâncias a um "pivot"
Dois objetos são equivalentes se estão a mesma distância de todos os pivots
x y  d(x, p) = d(y, p)
e a relação de equivalência do pivot:
x  {pi} y  d(x, pi) = d(y, pi)
b) Baseadas na proximidade a "grupos"
Baseadas na relação de equivalência de Voronoi
Grupos ou centros : {g1, g2,..,gm}
X  (gi) y  closest(x, {gi} = closest(y, {gi})
Onde closest(x, S) = {w  S,  w'  S, d(z, w)  d(z, w')}
TE073 – Processamento Digital de Sinais II
33
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
Relações equivalentes tipo "pivot"
A distância d(x, y) não pode nunca ser menor que:
d(x, y)  |d(x, p) - d(y, p)|
para qualquer elemento p, devido à desigualdade triangular.
Alternativamente as relações equivalentes podem ser
consideradas como as projeções no espaço vetorial k
onde k = número de pivots utilizados
TE073 – Processamento Digital de Sinais II
ver--->
34
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
Mapear um espaço métrico em um "vector space"
com métrica L utilizando dois pivots
d(x, p2)
b2
p2
a2
a1
p1
a2
b2
q
b1
Como saber se elemento u   ?
d(x, p1)
a1
b1
Procuramos aleatoriamente em pivots se: |d(q, pi) - d(u, pi) | > r,
logo por desig. Triângulo sabemos d(q, u) > r sem ter que avaliar d(q, u)
Distâncias aos pivots: pre-processamento!!
TE073 – Processamento Digital de Sinais II
35
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
Localidade classes equivalentes
12
3
2
4
Uma classe pode incluir varias
células
10
6
11
7
14
"Localidade":
9
15
Quanto é que as classes se
parecem com as células.
1
5
8
13
11
8
9
2
5
12
13
3
10
1
14
6
15
7
4
Fig.: Relação
equivalente criada pela
intersecção de anéis
centrados em dois
"pivots" e a
transformação na
pesquisa
11
8
TE073 – Processamento Digital de Sinais II
36
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
Diagrama de Voronoi
A divisão de um plano com n pontos em n polígonos convexos, tal que cada
polígono contém exatamente um ponto e cada ponto em um dado polígono está
mais próximo do seu ponto central que de qualquer outro.
TE073 – Processamento Digital de Sinais II
37
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
Ex.:
A região de um ponto chamada Polígono de Voronoi é dada por:
V(pi) = { P | d(P, pi) < d(P, Pj),  j  i}
TE073 – Processamento Digital de Sinais II
38
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
Relações equivalentes de Voronoi
Definir relações equivalentes respeito a proximidade dum dado
conjunto chamados "centros" ou "grupos"
A relação equivalente de Voronoi baseada em centros: {c1, c2,..,cm} é:
x ~{ci} y  proximo(x, {ci}) = proximo(y, {ci})
Onde próximo(z, S) = {w  S, w'  S, d(z, w)  d(z, w')}
A relação equivalente de Voronoi portanto, divide o espaço numa
partição para cada ci, isto é, dos pontos que têm ci como o seu centro
mais próximo.
TE073 – Processamento Digital de Sinais II
39
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
Partição de Voronoi com 4 centros e dois queries
c2
c3
q2
q1
c4
c1
O espaço é dividido com uma partição para cada ci.
A classe dos pontos que têm ci como seu centro mais próximo é ela própria.
Encontramos [q] procurando o vizinho mais próximo de q no conjunto de centros ci
: o conjunto de classes intersectadas pelos círculos das pesquisas.
TE073 – Processamento Digital de Sinais II
40
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
E que acontece quando os
dados são simbólicos ou os
domínios são infinitos?
"verde" "branco" "vermelho“
“Esquerda” “Direita” “Cima” “Baixo”
O que fazemos para calcular as distâncias?
TE073 – Processamento Digital de Sinais II
41