Seleção de Características
1
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
Seleção de Características

Objetivo: Dado um conjunto de medidas no espaço pdimensional, selecionar entre as componentes deste
vetor, t-dimensões que sejam as mais importantes para
resolver o problema da classificação.
x(1,2,3,...,100)
p=100-D
Seleção de
características
y=x(2,7,23,54)
t=4-D
Ex.: IDM (Interclass Distance Measurement)
TE073 – Processamento Digital de Sinais II
2
Extração de Características
3
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
Extração de Características

Objetivo: Dado um conjunto de medidas no espaço pdimensional, extrair destes dados informações que sejam
realmente úteis para a classificação reduzindo para um
vetor de t-dimensões.
x(1,2,3,...,100)
p=100-D
Seleção de
características
y(1,2,3,4)
t=4-D
Ex.: Técnicas de Processamento de Imagens/Voz
Análise espectral
PCA
TE073 – Processamento Digital de Sinais II
4
PCA
5
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
Análise de Componentes Principais

Pearson (1901):

Hotelling (1933):
Procurava linhas e planos que
melhor se adequavam a um conjunto de pontos em
um espaço p-dimensional. Criou a Componente
Principal (PC)
Procurava encontrar um
pequeno conjunto de variáveis fundamentais que
expressa p variáveis. Hotelling procurou maximizar
suas ‘componentes’ no senso da variância das
variáveis originais. Chamou de Componentes
Principais.
TE073 – Processamento Digital de Sinais II
6
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica




Ambos, Pearson e Hotelling, esbarraram no
problema dos autovetores (difícil de calcular
para ordem > 4).
Como o PCA é mais eficiente para conjuntos
de dados de alta ordem, não se viu muita
aplicação.
O tema ficou em banho-maria até os anos 60,
quando então surgiram os primeiros
computadores capazes de resolver o problema
dos autovetores de maneira rápida.
Karhunen e Loève aplicam PCA para
codificação de sinais (KLT).
TE073 – Processamento Digital de Sinais II
7
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
Desenvolvimento Matemático do PCA


A principal idéia por atrás do PCA é que:
um número , p, de variáveis dependentes podem ser
expressas como um número, t, de variáveis
independentes, t<<p
Considere um conjunto infinito de vetores, x, no espaço
N-dimensional.
É sempre possível gerar uma combinação linear que
mapeia x em um novo ponto y, em um espaço definido
por variáveis ortonormais, ej, j=1,2,3...,
TE073 – Processamento Digital de Sinais II
8
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica

Sem perda de informação, x pode ser
expresso como:

x   y j .e j
(1)
j 1

Se somente t dimensões são usadas, então
teremos alguma perda de informação, e
podemos estimar
t
xˆ   y j .e j
(2)
j1
TE073 – Processamento Digital de Sinais II
9
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica

Objetivo: Encontrar ej de modo que o erro
da estimação seja minimizado.


e  E  x  xˆ  .  x  xˆ 
2
T
(3)
Juntamente com a minimização da Eq.3, precisamos garantir
que o conjunto ej seja ortonormal
e .ei  ij
T
j
TE073 – Processamento Digital de Sinais II
(4)
10
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica

Substituindo Eq.1 e 2 na Eq. 3
T


t
t
  



2
e  E   y j .e j   y j .e j  .   y i .ei   y i .ei 
j 1
i 1

  i 1

 j 1

T










2
e  E   y j .e j  .   yi .ei 

  i t 1

 j t 1

(6)
Aplicando a condição de ortonormalidade de ej



2
2
e  E yj
 j t 1 
(7)
TE073 – Processamento Digital de Sinais II
11
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica

Multiplicando ambos os lados da Eq. 1 por ejT

e .x  e . y i .ei
T
j
T
j
i 1
y j eTj .x
(9)
Substituindo na Eq. 7



2


2
T
T
T
e  E   e j x   E   e j xx e j 
 j t 1

 j t 1

 
TE073 – Processamento Digital de Sinais II
12
Cx  E
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica

Invertendo a ordem do somatório e operador
Expectativa, e sabendo que ej é determinístico:



2
T
T
e  E   e j xx e j  
 j t 1


 
T
T

 e j (11)
e
E
xx

j 

j t 1
Notando que a matriz entre colchetes é a
Matriz de Autocorrelação do conjunto de vetores x
 
R x x  E xxT
Podemos, sem perda de generalidade, usar a Matriz de AutoCovariância

Cx  E  x  x  x  x 
T

TE073 – Processamento Digital de Sinais II
13
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica

Logo a expressão que devemos minimizar é:
e2 

T
e
 j Cxe j
(12)
j t 1
de modo a encontrar a base ótima ej

Isso é feito derivando-se e igualando a zero.
No entanto a derivada deve ser feita de modo que a
condição da Eq. 4 (ortonormalidade), permaneça
sendo cumprida
TE073 – Processamento Digital de Sinais II
14
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica

Este problema é resolvido através da definição
de uma função de restrição g(ej), e usando a
técnica dos Multiplicadores de Lagrange:
g e j  

T
e
 j Cxe j 
j t 1

T


e
 j  j e j 1
(13)
j t 1
Derivando a Eq. 13 e igualando a zero, temos:
g  e j   C x e j   j e j
g  e j    C x   j I  e j  0
(15)
onde, I é matriz identidade
TE073 – Processamento Digital de Sinais II
15
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
Problema dos Autovalores

A Eq. 15 é chamada de Problema dos Autovalores,
usada em várias áreas.
j é o j-ésimo autovalor associado ao autovetor ej
Desde que a Eq. 15 corresponde a um sistema homogêneo
de equações lineares e que possui uma solução não-trivial,
o determinante da matriz de coeficientes deve ser ZERO.
det  C x   j I   0
TE073 – Processamento Digital de Sinais II
(16)
16
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
det  C x   j I   0
(16)
Desenvolvendo a Eq. 16 o polinômio característico é obtido,
as raízes deste polinômio são os autovalores j da matriz Cx.
Como encontrar algebricamente as raízes de um polinômio de
grau maior que 4 é complicado, usa-se métodos numéricos (HP) .
TE073 – Processamento Digital de Sinais II
17
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
Matriz de Covariância

A matriz Rxx é conhecida como a matriz de
Autocorrelação do conjunto de vetores x.
 
R xx  E xx
T
Geralmente se retira o valor médio do conjunto de dados, de modo
a definirmos a Matriz Covariância:
μ x  E x

Cx  E  x  μ x  x  μ x 
T

o j-ésimo autovalor da matriz de covariância é igual à variância
do j-ésimo autovetor.
TE073 – Processamento Digital de Sinais II
18
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica

Assim, caso o número N de vetores seja
menor que o número de dimensões p:


O numero de autovalores não-nulos é igual ao
número de vetores x do conjunto , se a matriz de
correlação é calculado a partir desse conjunto.
Dado um conjunto de N vetores x, existem apenas
N-1 vetores linearmente independentes, caso seja
usado a matriz de covariância.
TE073 – Processamento Digital de Sinais II
19
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
O Mapeamento


Resolvendo-se o problema dos autovalores,
determina-se os autovetores que minimizam o
erro de representação.
Definindo-se a matriz de transformação A como:
A p p
 e1 (1) e2 (1)
 e (2) e (2)
1
2



e1 ( p ) e2 ( p )
e p (1) 
e p (2) 


e p ( p ) 
onde os p autovetores são as colunas da matriz A.
TE073 – Processamento Digital de Sinais II
20
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica

Podemos mapear cada vetor no espaço p-dimensional
para um vetor no espaço t-dimensional, através do
truncamento das colunas da matriz A utilizando
apenas t autovetores (geralmente considera-se os
autovetores associados aos maiores autovalores)
y t1  A pt
T
 x  μ x  p1
(28)
Extração de Características:
Espaço de Características t-dimensional
TE073 – Processamento Digital de Sinais II
21
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
Utilização do PCA

Objetivo: reduzir a dimensionalidade do espaço de
entrada p-D, mantendo tanta informação quanto
possível, em um novo espaço t-D.





Adquirir os dados: Número de vetores...
Calcular a Matriz de Covariância
Calcular os Autovalores e Autovetores
Escolher os autovetores: Critério da informação...
Mapear os dados para o novo espaço
TE073 – Processamento Digital de Sinais II
22
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
Exemplo: Reconhecimento de Face
EigenFaces

http://www.pages.drexel.edu/~sis26/Eigenface%20Tutorial.htm
TE073 – Processamento Digital de Sinais II
23
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
Exemplo: Reconhecimento Posturas Manuais
Imagens 100x100
Imagens 32x32
TE073 – Processamento Digital de Sinais II
24
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica
TE073 – Processamento Digital de Sinais II
25
Universidade Federal do Paraná
Setor de Tecnologia
Departamento de Engenharia Elétrica

Eigenletters
http://www.cc.gatech.edu/classes/cs7322_97_spring/participant
s/Sumner/final/report.html



Eigeneyes
Eigenvoice
Eigenqualquercoisa
TE073 – Processamento Digital de Sinais II
26