[email protected] Selezione delle caratteristiche - Principal Component Analysis dove l e k...

[email protected]@imm.cnr.it

Selezione delle caratteristiche - Principal Component Analysis

dove l e k sono le medie delle caratteristiche xl ed xk, rispettivamente.

Per M oggetti con N caratteristiche (x1,x2,..........xN) è definita una matrice

simmetrica di covarianza C realizzata con i valori di covarianza Cl,k:

M

tktkltlkkllkl xx

MxxEC

1, ))((

1

1)})({(

NNNN

N

N

CCC

CCC

CCC

C

,,2,1

,22,22,1

,12,11,1

....

................

....

....

MNMM

N

N

NM

xxx

xxx

xxx

X

.

...

...

.

.

21

22221

11211

)(

MX

X

X

.

.

.2

1

Sia Cl,k la covarianza delle caratteristiche xl ed xk per tutte le M possibili

osservazioni.La covarianza di due caratteristiche xl ed xk calcolata per gli M esempi è data da:


Principal Component Analysis

• Il valore di covarianza Cl,k è nullo se le caratteristiche xl ed xk sono non correlate:

0}{}{}{)})({( klklklklkkll xExExxExxE

• Gli autovettori di C sono ortogonali tra loro e le loro direzioni sono parallele ai corrispondenti autovalori.

• La direzione di massima varianza è parallela all’autovettore corrispondente all’autovalore massimo della matrice di covarianza C.

• Gli elementi Cii diagonali della matrice simmetrica di covarianza rappresentano la varianza delle N caratteristiche.



La matrice di covarianza può essere diagonalizzata con la procedura di trasformazione agli assi principali (oppure alle componenti principali PCA o trasformata di Karhunen-Loeve)

• Le caratteristiche degli oggetti in questo nuovo sistema di riferimento risultano non correlate.

• L’idea principale è che maggiore informazione corrisponde a maggiore varianza.

•Algoritmi PCA:

• Covarianza/Correlazione

• Singular value decomposition (SVD)



Le nuove caratteristiche (componenti) y=eX sono espresse come combinazione lineare delle xi caratteristiche di input e corrispondono agli autovettori della matrice di covarianza C. Gli autovalori corrispondenti sono la varianza.

Per trovare la prima componente principale, che denoteremo con y1, è necessario trovare il vettore di coefficienti e1=(e11,…,e1N) tale che

la varianza di e1X sia massima rispetto alla classe di tutte le combinazioni lineari di X soggette al vincolo (la norma di e1 è unitaria)

y1= e1X

111 ee

Dalla definizione di autovettore/autovalore:Cy=yλ Ce1X=e1X λ1 e1

’Ce1X= e1’ e1X λ1 e1

’Ce1X = X λ1

e1’Ce1 = λ1 e1

’Ce1 – λ1 I= 0 (C- λ1 I) e1 = 0

0)det( 1 IC



La seconda componente si ottiene trovando il secondo vettore normalizzato e2 ortogonale a e1

y2= e2X che avrà la seconda varianza massima

Le N componenti principali estratte soddisfano la proprietà

Tutte le correlazioni e covarianze del campione tra coppie delle componenti derivate sono zero.

)( 21 N

0 ijiij eeCee ij

lx

kx

kyly

ke le


Con e1 = [0.248300612 0.9394863248 0.2360347807] e2 = [0.1869712323 -0.2519829869 0.9494979382] e3 = [-0.4889375567 -0.03550023213 0.8715960383]

Y1

Y2

Y3



Gli autovettori della matrice di covarianza C sono orientati nella direzione di massima varianza e, conseguentemente, le caratteristiche associate si presentano con grande varianza (caratteristiche più significative). Le caratteristiche con varianza piccola possono essere trascurate in quanto non efficaci al fine della separabilità delle classi.

y x x sin

y x sin xl l k

k l k

cos

cos

y

y

sin

sin

x

xl

k

l

k

cos

cos

Gli assi coordinati delle nuove caratteristiche yl ed yk risultano

ruotati rispetto a quelli di input xl ed xk di un angolo e la loro

relazione è definita dall’equazione:



Considerando i nuovi assi coordinati yl ed yk allineati con gli autovettori el ed

ek della matrice di covarianza C, la trasformata agli assi principali è data

dalla equazione:

oppure y = Ax dove

k

l

kkkl

lkll

k

l

x

x

ee

ee

y

y

Ae e

e e

sin

sinll lk

kl kk

cos

cos

è la matrice di trasformazione delle nuove caratteristiche dove ciascuna riga rappresenta le proiezioni degli autovettori el ed ek sui rispettivi assi xl ed xk.



Le nuove caratteristiche possono essere definite con l’origine dei nuovi assi coordinati yl ed yk coincidente con il centroide del cluster (l, k):

kk

ll

kkkl

lkll

k

l

x

x

ee

ee

y

y

ky

ly

)( xAy

ky

ly

Axy



Gli elementi della matrice di covarianza delle nuove caratteristiche y, sono dati da:

dove ml ed mk sono le medie delle nuove caratteristiche yl ed yk, che sono

uguali a zero come si può dimostrare:

Si dimostra che la matrice di covarianza C` delle nuove caratteristiche y e`

data da:

M

tktkltlkklllk mymy

MmymyEC

1

' ))((1

1)})({(

m E y E A x A E x A { } { ( )} { } 0

N

CAAC

000

................

000

000

2

1

'

dove si evidenzia la proprietà che le nuove caratteristiche yi non sono

correlate, infatti tutti i termini hanno valore 0 ad esclusione di quelli sulla diagonale principale i che esprimono la varianza della caratteristica yi nella

direzione dell’autovettore ei.



In conclusione, con la trasformazione agli assi principali si ha una riduzione anche consistente del numero delle caratteristiche.

Le caratteristiche in questo nuovo spazio, anche se risultano le più significative, non implicano però una migliore separazione dei cluster.

Se i cluster nello spazio di origine sono molto vicini tra loro ed è difficile separarli, anche nello spazio delle nuove caratteristiche si avranno le stesse difficoltà di separazione.

Le componenti principali conducono soltanto alla selezione del miglior sottoinsieme di caratteristiche più significative per semplificare il processo di classificazione avendo eliminato le caratteristiche ridondanti e non necessarie.


PCA - Data Reduction

XeeY W1 ScoreComponent con W<N matrice troncata di [e1,…,eN]

Esempio: da un array di 5 sensori di gas vengono acquisite risposte relative a: Pentanone, Acetone ed Esanale (dimensione input N=5).

COMPONENTEPRINCIPALE

AUTOVALOREDI COV(X)

VARIANZA %CATTURATA

VARIANZA %TOTALE

1 4.66 93.12 93.122 2.90e-001 5.80 98.923 3.16e-002 0.63 99.554 1.97e-002 0.39 99.945 2.75e-003 0.06 100.00

Primo metodo: proporzione di varianza catturata


PCA - Data ReductionSecondo metodo: Screen test


PCA - Data ReductionScore plot

[email protected] Selezione delle caratteristiche - Principal Component Analysis dove l e k...

Documents

Transcript of [email protected] Selezione delle caratteristiche - Principal Component Analysis dove l e k...