Selezione delle caratteristiche - Principal Component
Analysis
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:
Cl ,k
1 M
 E{( xl   l )( xk   k )} 
 ( xtl  l )( xtk   k )
M  1 t 1
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:
X ( M N )
 x11
x
 21
 .

 .
 xM 1
x12
.
x22
.
.
.
xM 2
.
x1N   X 1 
X 

x2 N
 2
  . 
.   
  . 
.   . 
xMN   X M 
C1,1
C1, 2
....
C1, 2
C
....
C1, N
C2 , 2
....
C2 , N
.... C2, N
.... ....
.... C N , N
[email protected]
C1, N
Principal Component Analysis
• Il valore di covarianza Cl,k è nullo se le caratteristiche xl ed xk sono non
correlate:
E{( xl  l )( xk   k )}  E{xl  xk }  l   k  E{xl } E{xk }  l   k  0
• Gli elementi Cii diagonali della matrice simmetrica di covarianza rappresentano
la varianza delle N caratteristiche.
• La direzione di massima varianza è parallela all’autovettore corrispondente
all’autovalore massimo della matrice di covarianza C.
• Gli autovettori di C sono ortogonali tra loro e le loro direzioni sono parallele ai
corrispondenti autovalori.
[email protected]
Principal Component Analysis
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)
[email protected]
Principal Component Analysis
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 e1  e1  1 (la norma di e1 è unitaria)
y1= e1X
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
det(C  1I )  0
[email protected]
Principal Component Analysis
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à
(1  2    N )
Tutte le correlazioni e covarianze del campione tra coppie delle
componenti derivate sono zero.
ej Ce i  i ej ei  0
xk
yl
yk
ek
ji
el

xl
[email protected]
[email protected]
Y1
Y2
Y3
Con e1 = [0.248300612 0.9394863248 0.2360347807]
e2 = [0.1869712323 -0.2519829869 0.9494979382]
e3 = [-0.4889375567 -0.03550023213 0.8715960383]
[email protected]
Principal Component Analysis
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.
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:
 yl   cos  sin  xl 
 y    sin cos  x 
 k 
 k 
y l  x l cos   x k sin
y k  x l sin  x k cos 
[email protected]
Principal Component Analysis
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:
 yl   ell
 y   e
 k   kl
elk   xl 
   oppure y = Ax

ekk   xk 
dove
 ell
A
 ekl
elk   cos  sin 

ekk   sin 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.
[email protected]
Principal Component Analysis
Le nuove caratteristiche possono essere definite con l’origine dei nuovi assi coordinati
yl ed yk coincidente con il centroide del cluster (l, k):
 yl   ell
 y   e
 k   kl
yk
elk   xl  l 


ekk   xk  k 
yk
y  Ax
y  A( x   )
yl
yl
[email protected]
Principal Component Analysis
Gli elementi della matrice di covarianza delle nuove caratteristiche y, sono
dati da:
1 M
'
Clk  E{( yl  ml )( yk  mk )} 
( ytl  ml )( ytk  mk )

M  1 t 1
dove ml ed mk sono le medie delle nuove caratteristiche yl ed yk, che sono
uguali a zero come si può dimostrare:
m  E{y}  E{A( x  )}  A  E{x}  A    0
Si dimostra che la matrice di covarianza C` delle nuove caratteristiche y e`
1 0 0 0
data da:
C '  ACA 
0
2
0
0
.... .... .... ....
0 0 0 N
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.
[email protected]
Principal Component Analysis
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.
[email protected]
PCA - Data Reduction
Component Score Y  e1  eW  X
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).
Primo metodo: proporzione di varianza catturata
COMPONENTE AUTOVALORE VARIANZA %
PRINCIPALE
DI COV(X)
CATTURATA
1
2
3
4
5
4.66
2.90e-001
3.16e-002
1.97e-002
2.75e-003
93.12
5.80
0.63
0.39
0.06
VARIANZA %
TOTALE
93.12
98.92
99.55
99.94
100.00
[email protected]
PCA - Data Reduction
Secondo metodo: Screen test
[email protected]
PCA - Data Reduction
Score plot
[email protected]