1
Seleção de Características
TE073 – Processamento Digital de Sinais II 2
Universidade Federal do ParanáSetor de TecnologiaDepartamento de Engenharia Elétrica
Seleção de Características Objetivo: Dado um conjunto de medidas no espaço
p-dimensional, selecionar entre as componentes deste vetor, t-dimensões que sejam as mais importantes para resolver o problema da classificação.
Seleção decaracterísticas
x(1,2,3,...,100) y=x(2,7,23,54)
p=100-D t=4-D
Ex.: IDM (Interclass Distance Measurement)
3
Extração de Características
TE073 – Processamento Digital de Sinais II 4
Universidade Federal do ParanáSetor de TecnologiaDepartamento de Engenharia Elétrica
Extração de Características
Objetivo: Dado um conjunto de medidas no espaço p-dimensional, extrair destes dados informações que sejam realmente úteis para a classificação reduzindo para um vetor de t-dimensões.
Seleção decaracterísticas
x(1,2,3,...,100) y(1,2,3,4)
p=100-D t=4-D
Ex.: Técnicas de Processamento de Imagens/Voz Análise espectral PCA
5
PCAPCA
TE073 – Processamento Digital de Sinais II 6
Universidade Federal do ParanáSetor de TecnologiaDepartamento de Engenharia Elétrica
Análise de Componentes Principais
Pearson (1901): Procurava linhas e planos que melhor se adequavam a um conjunto de pontos em um espaço p-dimensional. Criou a Componente Principal (PC)
Hotelling (1933): 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 7
Universidade Federal do ParanáSetor de TecnologiaDepartamento 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 8
Universidade Federal do ParanáSetor de TecnologiaDepartamento 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 9
Universidade Federal do ParanáSetor de TecnologiaDepartamento de Engenharia Elétrica
Sem perda de informação, x pode ser expresso como:
Se somente t dimensões são usadas, então teremos alguma perda de informação, e podemos estimar
1
. (1)j jj
x y e
1
ˆ . (2)t
j jj
x y e
TE073 – Processamento Digital de Sinais II 10
Universidade Federal do ParanáSetor de TecnologiaDepartamento de Engenharia Elétrica
Objetivo: Encontrar ej de modo que o erro da estimação seja minimizado.
2 ˆ ˆ. (3)T
e E x x x x
Juntamente com a minimização da Eq.3, precisamos garantirque o conjunto ej seja ortonormal
. (4)Tj i ije e
TE073 – Processamento Digital de Sinais II 11
Universidade Federal do ParanáSetor de TecnologiaDepartamento de Engenharia Elétrica
Substituindo Eq.1 e 2 na Eq. 3
2
1 1
. . . (6)
T
j j i ij t i t
e E
y e y e
2
1 1 1 1
. . . . .
Tt t
j j j j i i i ij j i i
e E
y e y e y e y e
Aplicando a condição de ortonormalidade de ej
2 2
1
(7)jj t
e E
y
TE073 – Processamento Digital de Sinais II 12
Universidade Federal do ParanáSetor de TecnologiaDepartamento de Engenharia Elétrica
Multiplicando ambos os lados da Eq. 1 por ejT
1
. . .
. (9)
T Tj j i i
i
Tj j
e x e y e
y e x
Substituindo na Eq. 7
22
1 1
T T Tj j j
j t j t
e E E
e x e xx e
TE073 – Processamento Digital de Sinais II 13
Universidade Federal do ParanáSetor de TecnologiaDepartamento de Engenharia Elétrica
Invertendo a ordem do somatório e operador Expectativa, e sabendo que ej é determinístico:
2
1 1
(11)T T T Tj j j j
j t j t
e E E
e xx e e xx e
Notando que a matriz entre colchetes é a Matriz de Autocorrelação do conjunto de vetores x
xC E
Tx x ER xx
Podemos, sem perda de generalidade, usar a Matriz de AutoCovariância
T
x x xE C x x
TE073 – Processamento Digital de Sinais II 14
Universidade Federal do ParanáSetor de TecnologiaDepartamento de Engenharia Elétrica
Logo a expressão que devemos minimizar é:
2
1
(12)Tj x j
j t
e
e C e
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 15
Universidade Federal do ParanáSetor de TecnologiaDepartamento 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:
1 1
1 (13)T Tj j x j j j j
j t j t
g
e e C e e e
Derivando a Eq. 13 e igualando a zero, temos:
0 (15)
j x j j j
j x j j
g
g
e C e e
e C I e
onde, I é matriz identidade
TE073 – Processamento Digital de Sinais II 16
Universidade Federal do ParanáSetor de TecnologiaDepartamento 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 0 (16)x j C I
TE073 – Processamento Digital de Sinais II 17
Universidade Federal do ParanáSetor de TecnologiaDepartamento de Engenharia Elétrica
det 0 (16)x j C I
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 18
Universidade Federal do ParanáSetor de TecnologiaDepartamento de Engenharia Elétrica
Matriz de Covariância
A matriz Rxx é conhecida como a matriz de Autocorrelação do conjunto de vetores x. T
xx ER xx
Geralmente se retira o valor médio do conjunto de dados, de modoa definirmos a Matriz Covariância:
x Eμ x T
x x xE C x μ x μ
o j-ésimo autovalor da matriz de covariância é igual à variância do j-ésimo autovetor.
TE073 – Processamento Digital de Sinais II 19
Universidade Federal do ParanáSetor de TecnologiaDepartamento 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 20
Universidade Federal do ParanáSetor de TecnologiaDepartamento 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:
1 2
1 2
1 2
(1) (1) (1)
(2) (2) (2)
( ) ( ) ( )
p
pp p
p
e e e
e e e
e p e p e p
A
onde os p autovetores são as colunas da matriz A.
TE073 – Processamento Digital de Sinais II 21
Universidade Federal do ParanáSetor de TecnologiaDepartamento 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)
1 1(28)T
t p t x p y A x μ
Extração de Características:Espaço de Características t-dimensional
TE073 – Processamento Digital de Sinais II 22
Universidade Federal do ParanáSetor de TecnologiaDepartamento 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 23
Universidade Federal do ParanáSetor de TecnologiaDepartamento de Engenharia Elétrica
Exemplo: Reconhecimento de Face
http://www.pages.drexel.edu/~sis26/Eigenface%20Tutorial.htm
EigenFaces
TE073 – Processamento Digital de Sinais II 24
Universidade Federal do ParanáSetor de TecnologiaDepartamento de Engenharia Elétrica
Exemplo: Reconhecimento Posturas Manuais
Imagens 100x100Imagens 32x32
TE073 – Processamento Digital de Sinais II 25
Universidade Federal do ParanáSetor de TecnologiaDepartamento de Engenharia Elétrica
TE073 – Processamento Digital de Sinais II 26
Universidade Federal do ParanáSetor de TecnologiaDepartamento de Engenharia Elétrica
Eigenlettershttp://www.cc.gatech.edu/classes/cs7322_97_spring/participants/Sumner/final/report.html
Eigeneyes Eigenvoice Eigenqualquercoisa