Seleção de Características

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



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



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.



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).



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...,



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



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



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



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



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



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



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



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



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) .



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.



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.



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.



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



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



Exemplo: Reconhecimento de Face

http://www.pages.drexel.edu/~sis26/Eigenface%20Tutorial.htm

EigenFaces



Exemplo: Reconhecimento Posturas Manuais

Imagens 100x100Imagens 32x32





Eigenlettershttp://www.cc.gatech.edu/classes/cs7322_97_spring/participants/Sumner/final/report.html

Eigeneyes Eigenvoice Eigenqualquercoisa

Documents

Seleção de Características