Approccio parametrico e non parametrico - Unicas

Approccio statistico
alla classificazione
Approccio parametrico e non
parametrico
Finestra di Parzen
Classificatori K-NN 1-NN
Limitazioni dell’approccio
bayesiano
z
Con l’approccio bayesiano, sarebbe possibile
costruire un classificatore ottimo se si
conoscessero:
z
z
le probabilità a priori P(ωi)
le densità condizionate alla classe P(x|ωi)
z
Informazioni che raramente sono disponibili
z
Alternativa: costruire una classificatore da un
insieme di esempi (training set)
z
z
Pro: stima delle P(ωi) semplicemente realizzabile
Contro: training set troppo limitato per una stima affidabile
delle distribuzioni condizionate
F. Tortorella © 2005
Teoria e Tecniche di Pattern Recognition
Approccio parametrico e non parametrico
1
Università degli Studi
di Cassino
1
Approccio parametrico e
non parametrico
z
Due sono le soluzioni più diffuse
z
Approccio parametrico
z
z
Si assume una forma particolare per le pdf (es.
Gaussiane)
Approccio non parametrico
z
Non si assume alcuna conoscenza sulla forma
analitica delle pdf.
F. Tortorella © 2005
Teoria e Tecniche di Pattern Recognition
Approccio parametrico e non parametrico
2
Università degli Studi
di Cassino
Approccio parametrico
z
z
z
In questo tipo di approccio si assume nota la forma
delle densità condizionali; tipicamente si assume
una gaussiana P(x | ωi) ~ N( µi, Σi).
Ci sono quindi due parametri da stimare per ogni
classe.
Le tecniche più usate per la stima sono:
z
z
z
Maximum-Likelihood (ML)
Stima Bayesiana
Sebbene differenti nella logica, le due tecniche
portano a risultati quasi identici.
F. Tortorella © 2005
Teoria e Tecniche di Pattern Recognition
Approccio parametrico e non parametrico
3
Università degli Studi
di Cassino
2
Stima Maximum Likelihood
z
z
z
z
I parametri sono fissati, ma non noti.
I valori ottimali dei parametri sono ottenuti
attraverso la massimizzazione della
probabilità di ottenere i campioni osservati.
La stima ha buone proprietà di convergenza
al crescere dell’insieme di campioni.
E’ più semplice di altre tecniche.
F. Tortorella © 2005
Teoria e Tecniche di Pattern Recognition
Approccio parametrico e non parametrico
4
Università degli Studi
di Cassino
Stima Maximum Likelihood
z
Principi generali
z
assumiamo di avere c classi, con
P(x | ωj) ~ N( µj, Σj)
P(x | ωj) ≡ P (x | ωj, θj) dove:
22
m
n
θ j = (µ j ,Σ j ) = (µ1j,µ2j ,..., σ11
j , σ j , cov(x j , x j )...)
z
z
per ogni classe ωi abbiamo un insieme di
campioni Di
supponiamo, inoltre, che i campioni in Di non
diano informazioni su θj
F. Tortorella © 2005
Teoria e Tecniche di Pattern Recognition
Approccio parametrico e non parametrico
5
Università degli Studi
di Cassino
3
Stima Maximum Likelihood
z
In queste ipotesi si può lavorare indipendentemente su
ogni classe.
z
Consideriamo una classe generica cui corrisponde un
insieme D contenente n campioni, x1, x2,…, xn estratti
indipendentemente.
La probabilità di ottenere l’insieme D dato θ è quindi:
z
n
P(D | θ) = ∏ P(x k | θ)
k =1
z
Per definizione la stima ML di θ è il valore che
massimizza P(D | θ).
E’ il valore di θ che meglio si accorda con i campioni di
training effettivamente osservati
F. Tortorella © 2005
Teoria e Tecniche di Pattern Recognition
Approccio parametrico e non parametrico
Università degli Studi
di Cassino
6
Stima Maximum Likelihood
z
Per valutare più agevolmente l’insieme di parametri
θ, è opportuno osservare che:
θˆ = arg max[ p(D θ )] = arg max[log p(D θ )]
θ
θ
e quindi considerare il problema equivalente:
  n

 n

θˆ = arg max log ∏ p(xk θ ) = arg max ∑ log( p (xk θ ))
θ
θ

 k =1

  k =1
z In questo modo, l’espressione è più facile da
analizzare (derivate di somme invece che di
prodotti; semplificazioni per p() esponenziali)
F. Tortorella © 2005
Teoria e Tecniche di Pattern Recognition
Approccio parametrico e non parametrico
7
Università degli Studi
di Cassino
4
Stima Maximum Likelihood
Esempio: caso gaussiano, media non nota
z
z
Supponiamo che D contenga n campioni
provenienti da una pdf gaussiana p( x) = N ( µ , σ )
con σ nota.
Qual è la stima ML di µ ?
 1
 (x − θ )2  
exp − k 2   =
 2π σ

2σ
θ
θ
k =1
k =1



2
2
n 
n 
(
xk − θ ) 
 1  ( xk − θ ) 
= arg max ∑ log
−
 = arg max ∑ −

2σ 2 
2σ 2 
θ
θ
 2π σ 
k =1 
k =1 
n
n
θˆ = arg max ∑ log( p(xk θ )) = arg max ∑ log
F. Tortorella © 2005
Teoria e Tecniche di Pattern Recognition
Approccio parametrico e non parametrico
Università degli Studi
di Cassino
8
Stima Maximum Likelihood
Esempio: caso gaussiano, media non nota
z
Calcoliamo la derivata e uguagliamola a 0:
d
dθ
z
Da cui:
 ( xk − θ )2  n  xk − θ 
=0
=∑
−
∑
2σ 2  k =1  σ 2 
k =1 
n
µˆ = θˆ =
F. Tortorella © 2005
Teoria e Tecniche di Pattern Recognition
Approccio parametrico e non parametrico
1 n
∑ xk
n k =1
9
Università degli Studi
di Cassino
5
Stima Maximum Likelihood
Esempio: caso gaussiano, µ e σ non note
z
z
Supponiamo che D contenga n campioni
provenienti da una pdf gaussiana p( x) = N ( µ , σ )
con µ e σ non note.
Questa volta occorre considerare il gradiente
θ
µ
θ =  1  =  2 
θ 2  σ 
1 n

 
 ∂ n
(
)
−
x
θ
(
(
)
)
p
x
θ
log
∑
1
k


∑
k

 ∂θ
θ 2 k =1
k =1
1
 = 0 

= n
∇θ = 
2
n


∂
(
)
−
x
θ
1
 0



1
k


(
(
)
)
p
x
θ
log
−
+
k

 ∑
 ∂θ 2 ∑
2θ 22 
k =1
 k =1  2θ 2
F. Tortorella © 
2005
Teoria e Tecniche di Pattern Recognition
Approccio parametrico e non parametrico
Università degli Studi
di Cassino
10
Stima Maximum Likelihood
Esempio: caso gaussiano, µ e σ non note
z
La stima ML dei due parametri è quindi:
µˆ = θˆ1 =
z
1 n
∑ xk
n k =1
σˆ 2 = θˆ2 =
1 n
(xk − µˆ )2
∑
n k =1
In effetti, il valore di σˆ 2 è polarizzato in
quanto il valore atteso calcolato su tutti gli
insiemi di dati di ampiezza n è diverso dalla
varianza reale
n −1 2
E σˆ 2 =
σ ≠σ2
n
[ ]
z
Una stima non polarizzata è σˆ 2 =
Teoria e Tecniche di Pattern Recognition
Approccio parametrico e non parametrico
11
1 n
(xk − µˆ )2
∑
n −F.1Tortorella
k =1 © 2005
Università degli Studi
di Cassino
6
Stima bayesiana
z
z
Nella stima ML il parametro θ era assunto fisso
ma non noto.
La soluzione ML è il valore che meglio si
accorda con i campioni di training effettivamente
osservati.
Maximum
Likelihood
D
F. Tortorella © 2005
Teoria e Tecniche di Pattern Recognition
Approccio parametrico e non parametrico
12
Università degli Studi
di Cassino
Stima bayesiana
z
z
z
z
Anche nella stima bayesiana la forma di p(x | θ) è
assunta nota, con θ non noto.
Nella stima bayesiana θ è considerato una variabile
aleatoria di densità nota p(θ).
Il resto della conoscenza a priori è contenuto in un
insieme D di n campioni x1, x2, …, xn indipendenti
estratti da una popolazione avente densità p(x).
Perciò dobbiamo valutare la densità condizionata p(x|D)
che risulta:
p(x | D) = ∫ p(x | θ)p(θ | D)dθ
nota
da stimare
F. Tortorella © 2005
Teoria e Tecniche di Pattern Recognition
Approccio parametrico e non parametrico
13
Università degli Studi
di Cassino
7
Stima bayesiana
z
z
z
z
Di conseguenza, nella stima bayesiana, l’incertezza sul valore
del parametro è modellata tramite una pdf.
Prima dell’osservazione dei dati, il parametro θ è descritto da una
densità a priori p(θ) che è tipicamente di supporto molto ampio
per rappresentare la scarsa conoscenza sul suo vero valore.
Una volta noti i dati, si fa uso del teorema di Bayes per
determinare la densità a posteriori p(θ|D).
La conoscenza dei dati dovrebbe idealmente rendere più definita
la densità p(θ|D); in altre parole, si dovrebbe ridurre l’incertezza
sul valore del parametro θ.
D
D
F. Tortorella © 2005
Teoria e Tecniche di Pattern Recognition
Approccio parametrico e non parametrico
14
Università degli Studi
di Cassino
Stima bayesiana
z
La densità condizionata p ( x D) si calcola integrando
la densità congiunta p( x,θ D) su θ:
p( x D) = ∫ p( x,θ D)dθ
z
Calcoliamo p( x,θ D) :
p (x, θ D ) = p (x θ , D ) p (θ D )
p (x θ , D ) è indipendente da D perché, una volta noto θ,
la densità è completamente specificata. Quindi:
p (x, θ D ) = p (x θ ) p (θ D )
F. Tortorella © 2005
Teoria e Tecniche di Pattern Recognition
Approccio parametrico e non parametrico
15
Università degli Studi
di Cassino
8
Stima bayesiana
z
Per calcolare p(θ D) utilizziamo il teorema di Bayes:
p(θ D ) =
z
p(D θ ) p(θ )
p (D )
=
p(D θ ) p(θ )
∫ p(D θ ) p(θ )dθ
Possiamo calcolare p(D θ ) sfruttando l’ipotesi che i
campioni di D siano i.i.d.:
n
p(D θ ) = ∏ p(xk θ )
k =1
F. Tortorella © 2005
Teoria e Tecniche di Pattern Recognition
Approccio parametrico e non parametrico
16
Università degli Studi
di Cassino
Stima bayesiana
Esempio: caso gaussiano, media non nota
z
z
Supponiamo che D contenga n campioni i.i.d.
provenienti da una pdf gaussiana con µ non
nota e σ nota.
Supponiamo che il parametro θ = µ abbia
anch’esso una pdf normale N(µ0, σ0):
p0 (θ ) =
 (θ − µ 0 )2 

exp −
2σ 02 
2π σ 0

1
F. Tortorella © 2005
Teoria e Tecniche di Pattern Recognition
Approccio parametrico e non parametrico
17
Università degli Studi
di Cassino
9
Stima bayesiana
Esempio: caso gaussiano, media non nota
z
Valutiamo la pdf a posteriori p(θ |D):
p(θ D ) =
p(D θ ) p0 (θ )
p( D)
p0 (θ ) n
∏ p (x k θ ) =
p ( D) k =1
=
 (θ − µ 0 )2  1 n

exp −
p(xk θ )
2
 p( D) ∏
2
σ
2π σ 0
=
1
k
0


1
F. Tortorella © 2005
Teoria e Tecniche di Pattern Recognition
Approccio parametrico e non parametrico
Università degli Studi
di Cassino
18
Stima bayesiana
Esempio: caso gaussiano, media non nota
z
Per comprendere come la stima bayesiana modifica la
densità a posteriori all’aumentare dei dati, consideriamo il
valore massimo di p(θ |D):
n

d
d  1
 −
(µ − µ0 )2 + ∑ − 1 2 (xk − µ )2  = 0
log p (θ D ) = 0 ⇒
2
dθ
dµ  2σ 0
2σ
k =1

da cui
z
µn =
σ2
σ + nσ
2
2
0
µ0 +
nσ 02 1 n
∑x
σ + nσ 02 n k =1 k
2
si comprende come, all’aumentare di n, la stima µn si porta
dalla stima iniziale µ0 verso la stima ML.
In maniera simile, la deviazione standard σn è data da:
1
σ n2
=
n
σ2
+
Teoria e Tecniche di Pattern Recognition
Approccio parametrico e non parametrico
19
1
σ 02
F. Tortorella © 2005
Università degli Studi
di Cassino
10
Stima bayesiana
Esempio: caso gaussiano, media non nota
Supponiamo di dover stimare la media di una pdf gaussiana con
parametri µ=0.8 e σ=0.3. Conosciamo solo σ.
Assumiamo una p0(θ) ugualmente gaussiana con µ0=0.0 e σ0=0.3.
D)
Visualizziamo p(θ |D) al variare del numero di campioni n.
F. Tortorella © 2005
Teoria e Tecniche di Pattern Recognition
Approccio parametrico e non parametrico
20
Università degli Studi
di Cassino
Confronto tra stima ML e
stima bayesiana
z
z
z
Qual è la relazione tra queste due stime ?
All’aumentare dei dati, la stima bayesiana si
avvicina alla stima ML.
In pratica, le due tecniche forniranno risultati
significativamente diversi solo per bassi valori
di n.
F. Tortorella © 2005
Teoria e Tecniche di Pattern Recognition
Approccio parametrico e non parametrico
21
Università degli Studi
di Cassino
11
Approccio non parametrico
z
z
z
Nell’approccio parametrico tutte le densità erano
unimodali (hanno un singolo massimo locale),
mentre in molti problemi pratici le densità sono
multimodali.
Con l’approccio non parametrico si rimuove
l’assunzione della conoscenza delle densità per cui
si può lavorare con distribuzioni di forma arbitraria.
Due tipologie di metodi non parametrici:
z
z
Stimare p(x | ωj)
Stimare direttamente le probabilità a posteriori P( ωj|x)
F. Tortorella © 2005
Teoria e Tecniche di Pattern Recognition
Approccio parametrico e non parametrico
23
Università degli Studi
di Cassino
Stima della densità
z
Consideriamo la probabilità che un vettore x,
la cui densità è p(x), cada in una regione R:
P = ∫ p(ξ )dξ
R
z
Consideriamo n campioni i.i.d. di x x1,…,xn.
La probabilità che k di questi cadranno in R
sarà data da:
Pk (1− P)n−k
Pk =  n
k
 
mentre il valore atteso per k è E[k]=nP.
F. Tortorella © 2005
Teoria e Tecniche di Pattern Recognition
Approccio parametrico e non parametrico
24
Università degli Studi
di Cassino
12
Stima della densità
z
z
z
Possiamo quindi assumere P≅k/n, dove la
stima diventa più accurata al crescere di n.
2
 k
Infatti si ha:  k 
k 
  P(1 − P)
var
=
=E
−P
E  = P
n
 n 

 n
 
 
n
D’altra parte, se supponiamo p(x) continua ed
R sufficientemente piccola, possiamo porre:
P = ∫ p(ξ )dξ ≅ p(x)∫ dξ = p(x)V
R
z
R
In questo modo, otteniamo una stima di p(x):
k/n
F. Tortorella
p(x) ≅
V
Teoria e Tecniche di Pattern Recognition
Approccio parametrico e non parametrico
25
F. Tortorella © 2005
Teoria e Tecniche di Pattern Recognition
Approccio parametrico e non parametrico
© 2005
Università degli Studi
di Cassino
26
Università degli Studi
di Cassino
13
Stima della densità
Alcuni problemi:
z se fissassimo il volume V e facessimo crescere n,
otterremmo una media di p(x):
P
=
V
∫ p(ξ )dξ
R
∫ dξ
R
z
per cui dovremmo considerare un volume che tende
a zero.
Tuttavia, per n fissato, R diventerebbe talmente
piccola che k=0 (e quindi p(x) ≅0); altrimenti se k>0,
la stima divergerebbe.
F. Tortorella © 2005
Teoria e Tecniche di Pattern Recognition
Approccio parametrico e non parametrico
27
Università degli Studi
di Cassino
Stima della densità
z
z
z
Mettiamoci nell’ipotesi di avere un numero illimitato
di campioni.
Per valutare p(x) consideriamo una sequenza di
regioni R1,R2,…, Rn contenenti x: la regione Rs si
impiega nel caso n=s (1,2,…,n campioni totali).
Se Vn è il volume di Rn, kn il numero di campioni che
cadono in Rn and pn(x) è l n-ma stima di p(x), si ha:
pn(x) = (kn/n)/Vn
F. Tortorella © 2005
Teoria e Tecniche di Pattern Recognition
Approccio parametrico e non parametrico
28
Università degli Studi
di Cassino
14
Stima della densità
z
Perché pn(x) converga a p(x) sono necessarie tre
condizioni:
lim Vn = 0
n→ ∞
z
lim k n = ∞
n→ ∞
lim
n→ ∞
kn
=0
n
Due modi per ottenere tali condizioni:
z
z
ridurre la regione R definita inizialmente specificando il
volume Vn come funzione di n (es.: Vn=1/√n) e dimostrare
che pn(x)Æp(x) per nÆ∞ (metodo della finestra di Parzen).
specificare kn come funzione di n (es.: kn= √n). In questo
caso, Vn cresce fino a contenere kn campioni (stima a kn
vicini).
F. Tortorella © 2005
Teoria e Tecniche di Pattern Recognition
Approccio parametrico e non parametrico
29
Università degli Studi
di Cassino
Stima della densità
Stima della densità con i due metodi. Entrambe le sequenze
rappresentano variabili aleatorie che generalmente convergono,
F. Tortorella © 2005
permettendo
diPattern
stimare
la densità nel punto di interesse.
Teoria e Tecniche di
Recognition
Università degli Studi
Approccio parametrico e non parametrico
30
di Cassino
15
Metodo della finestra di Parzen
z
z
Assumiamo che la regione Rn sia un ipercubo a d
dimensioni, di lato hn e volume Vn= hnd.
Consideriamo una funzione finestra ϕ(u) che unitaria
all’interno di un ipercubo centrato nell’origine e di
lato unitario:
1

j = 1,... , d
1 u j ≤
ϕ (u) = 
2
0 altrimenti
z
ϕ((x-xi)/hn) è uguale a 1 se xi cade all’interno
dell’ipercubo di volume Vn centrato su x e nullo al di
fuori.
F. Tortorella © 2005
Teoria e Tecniche di Pattern Recognition
Approccio parametrico e non parametrico
31
Università degli Studi
di Cassino
Metodo della finestra di Parzen
z
Il numero di campioni che cade all’interno di Vn è quindi
uguale a:
n
 x − xi 

k n = ∑ ϕ 
i=1  hn

z
La stima della densità è quindi:
pn (x) =
z
1 n 1  x − xi 

∑ ϕ
n i=1 Vn  hn 
pn(x) stima p(x) come la media di funzioni di x e dei
campioni (xi) (i = 1,… ,n). La funzione ϕ può essere di
forma generale purchè si verifichi ϕ(u)≥0 e ∫ ϕ(u)du =1.
F. Tortorella © 2005
Teoria e Tecniche di Pattern Recognition
Approccio parametrico e non parametrico
32
Università degli Studi
di Cassino
16
Metodo della finestra di Parzen
z
z
z
z
In corrispondenza di un punto xi, la pdf non è nulla.
Se la pdf è continua sull’intero spazio delle features, allora essa
sarà non nulla anche in un piccolo intorno di xi. Tuttavia, quanto
più ci si allontana dal punto tanto più diminuisce l’influenza del
valore della pdf in xi.
Di conseguenza, la stima di Parzen si basa sulla considerazione
che la conoscenza sulla pdf ottenuta con l’osservazione del
punto xi è rappresentata da una funzione centrata sul punto e
con un supporto ristretto ad un intorno limitato di xi. Di
conseguenza è una funzione che:
z Ha il suo massimo per x=xi
z È monotonicamente decrescente al crescere di d(x,xi) (distanza)
z Ha integrale unitario
La funzione è spesso chiamata kernel e rappresenta il contributo
del punto alla stima. La stima complessiva è quindi ottenuta
sommando i contributi di tutti i punti.
F. Tortorella © 2005
Teoria e Tecniche di Pattern Recognition
Approccio parametrico e non parametrico
Università degli Studi
di Cassino
33
Finestra di Parzen
z
Una scelta frequente è un kernel gaussiano:
ϕ (u) =
z
(
1
2π
Per cui la stima è:
1 n
pn ( x ) = ∑
n i =1
(
)
d
 u2

exp −
 2 


 x − xi
−
exp
d d

2h 2
2π h

1
)




F. Tortorella © 2005
Teoria e Tecniche di Pattern Recognition
Approccio parametrico e non parametrico
2
34
Università degli Studi
di Cassino
17
Metodo della finestra di Parzen
A parità di n, la stima dipende dalla forma della ϕ:
ϕ(u)
p(x) stimata
F. Tortorella © 2005
Teoria e Tecniche di Pattern Recognition
Approccio parametrico e non parametrico
35
Università degli Studi
di Cassino
Più in
generale, la
stima dipende
dalla forma di
ϕ e dal numero
di campioni n.
F. Tortorella © 2005
Teoria e Tecniche di Pattern Recognition
Approccio parametrico e non parametrico
36
Università degli Studi
di Cassino
18
Classificazione
z
Nei classificatori basati sulla stima con la
finestra di Parzen, si stima la densità
condizionata per ogni classe e si esegue
la classificazione con la regola della
massima probabilità a posteriori.
z
Le regioni di decisione dipendono dalla
scelta della funzione finestra.
F. Tortorella © 2005
Teoria e Tecniche di Pattern Recognition
Approccio parametrico e non parametrico
37
Università degli Studi
di Cassino
Classificazione
ampiezza h piccola
ampiezza h grande
La forma della ϕ influisce sulle regioni di decisione.
F. Tortorella © 2005
Teoria e Tecniche di Pattern Recognition
Approccio parametrico e non parametrico
38
Università degli Studi
di Cassino
19
Algoritmo di classificazione
basato sul metodo di Parzen
z
1.
2.
Input: training set Ts, test set T
Determinazione di h a partire da Ts
Per ogni campione x di T si stimano le pdf
condizionate:
1
pˆ (x ωt ) =
nt
3.
∑
i∈Tst
(
 x − xi
−
exp
d d

2h 2
2π h

1
)
2




Il campione viene assegnato alla classe con
criterio MAP: ω = arg max p( x ωt ) Pˆ (ωt )
{
t
}
F. Tortorella © 2005
Teoria e Tecniche di Pattern Recognition
Approccio parametrico e non parametrico
Università degli Studi
di Cassino
39
Stima LOO di h
z
z
Per determinare il valore di h si potrebbe usare un
approccio Maximum Likelihood, ma ciò porterebbe ad un
valore di hÆ0.
Invece di determinare h che massimizza log(P(Ts|h)) si
n
considera h tale che:
hˆ = arg max ∑ log pˆ −i (x i h )
h
n
dove: pˆ (x h ) = 1
∑
i
−i
n − 1 j =1, j ≠i
z
(
i =1
 x −x
i
j

exp −
d d
2
2h

2π h

1
)
2




In effetti, pˆ −i (x i h ) è la stima della pdf su xi valutata usando
per la stima l’insieme Ts-{xi} (stima LOO, Leave One Out)
F. Tortorella © 2005
Teoria e Tecniche di Pattern Recognition
Approccio parametrico e non parametrico
40
Università degli Studi
di Cassino
20
Stima della densità a k vicini
z
z
Nalla stima a k vicini il volume che circonda il
punto x cresce fin quando arriva a includere k
punti degli n totali.
La stima della densità che si ottiene è quindi:
pˆ n ( x) =
k
n ⋅ Vn ( x )
F. Tortorella © 2005
Teoria e Tecniche di Pattern Recognition
Approccio parametrico e non parametrico
41
Università degli Studi
di Cassino
Stima della densità a k vicini
z
Stima non
soddisfacente
per diversi
problemi:
z
z
È influenzata
dal rumore
locale
Produce densità
con molte
discontinuità
F. Tortorella © 2005
Teoria e Tecniche di Pattern Recognition
Approccio parametrico e non parametrico
42
Università degli Studi
di Cassino
21
Stima della densità a k vicini
È possibile usare il metodo a k vicini per
stimare direttamente la probabilità a posteriori
P(ωi|x).
Consideriamo un insieme Ts di n campioni
appartenenti alle varie classi e sia ni il numero
di campioni appartenenti alla classe ωi.
Sia x è un campione da classificare non
appartenente a Ts.
z
z
z
F. Tortorella © 2005
Teoria e Tecniche di Pattern Recognition
Approccio parametrico e non parametrico
Università degli Studi
di Cassino
43
Stima della densità a k vicini
z
z
z
Si consideri un’ipersfera centrata su x e di
raggio tale da includere k campioni di Ts.
Sia ki ≤ k il numero di campioni interni
all’ipersfera appartenenti alla classe ωi.
Se V è il volume dell’ipersfera, con il metodo
a k vicini si possono stimare
z
z
z
ki
La pdf condizionata p(x | ωi ) = n ⋅V
k
i
p (x ) =
La pdf incondizionata
n ⋅V
n
La probabilità a priori P(ωi ) = i
n
F. Tortorella © 2005
Teoria e Tecniche di Pattern Recognition
Approccio parametrico e non parametrico
44
Università degli Studi
di Cassino
22
Classificatore k-NN
z
Mettendo tutto insieme, è possibile ottenere
una stima della probabilità a posteriori:
P(ωi | x ) =
z
p(x | ωi )P(ωi )
k n n ⋅ V ki
≅ i i
=
p(x )
ni ⋅ V n k
k
In questo modo è possibile definire una
regola di classificazione (k Nearest Neighbor
rule o k-NN):
k ( x)
α (x) = ωi ωi = arg max i
k (x)F. Tortorella
i
Teoria e Tecniche di Pattern Recognition
Approccio parametrico e non parametrico
45
© 2005
Università degli Studi
di Cassino
Classificatore k-NN
z
z
Il classificatore k-NN è un classificatore non
parametrico che classifica i campioni sulla base
della loro somiglianza con gli esemplari del training
set Ts.
Per definire un
classificatore k-NN
è necessario soltanto
z
z
z
Scegliere un valore k
Un insieme di campioni
con etichette (training set)
Una metrica per definire
la “vicinanza”
F. Tortorella © 2005
Teoria e Tecniche di Pattern Recognition
Approccio parametrico e non parametrico
k=5
46
Università degli Studi
di Cassino
23
Prestazioni del classificatore
k-NN
z
z
Il classificatore è sub-ottimo nel senso che
non garantisce la probabilità di errore minima
esibita dal classificatore bayesiano.
E’ però possibile dimostrare che, con nÆ∞,
la probabilità di errore Pe per il classificatore
k-NN si avvicina alla probabilità di errore del
classificatore bayesiano se kÆ∞.
F. Tortorella © 2005
Teoria e Tecniche di Pattern Recognition
Approccio parametrico e non parametrico
47
Università degli Studi
di Cassino
Prestazioni del classificatore
k-NN
Limiti inferiore (errore di Bayes) e superiore alla
probabilità di errore del classificatore k-NN per un
problema a due classi.
F. Tortorella © 2005
Teoria e Tecniche di Pattern Recognition
Approccio parametrico e non parametrico
48
Università degli Studi
di Cassino
24
Classificatore Nearest-Neighbor
z
z
z
Un caso particolare si ha quando k=1.
Si ottiene un classificatore 1-NN o
classificatore “Nearest Neighbor”
La classificazione di un nuovo campione x
non appartenente a Ts avviene scegliendo
l’etichetta del campione di Ts a minima
distanza da x.
F. Tortorella © 2005
Teoria e Tecniche di Pattern Recognition
Approccio parametrico e non parametrico
49
Università degli Studi
di Cassino
Classificatore Nearest-Neighbor
Il classificatore NN induce sullo spazio delle
F. Tortorella © 2005
degli Studi
features una tassellazione di Voronoi. Università
di Cassino
Teoria e Tecniche di Pattern Recognition
Approccio parametrico e non parametrico
50
25
Prestazioni del classificatore
1-NN
z
z
Anche il classificatore 1-NN è sub-ottimo.
E’ però possibile dimostrare che, al crescere
di n, la probabilità di errore Pe per il
classificatore NN soddisfa la seguente
relazione:
Pe* ≤ Pe ≤ 2Pe*
dove Pe* è la probabilità di errore del
classificatore bayesiano.
F. Tortorella © 2005
Teoria e Tecniche di Pattern Recognition
Approccio parametrico e non parametrico
51
Università degli Studi
di Cassino
Classificatore Nearest-Neighbor
F. Tortorella © 2005
Teoria e Tecniche di Pattern Recognition
Approccio parametrico e non parametrico
52
Università degli Studi
di Cassino
26