Vai alla Home Page About me Courseware Federica Living Library Federica Federica Podstudio Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica La Corte in Rete
 
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

Roberto Prevete » 5.Problemi di Classificazione ed approccio probabilistico


Problema di Classificazione: Regioni di decisione

Abbiamo detto che un problema di classificazione può essere affrontato tramite la ricerca di un algoritmo per assegnare ciascun punto dello spazio delle caratteristiche ad una di c classi.

Possiamo allora supporre che lo spazio delle caratteristiche sia suddiviso in c regioni R_1,R_2, ...,R_c , dette regioni di decisioni , in modo tale che se un elemento a cui è associato un vettore di caratteristiche x appartenente alla regione  R_k allora l’elemento in questione è assegnato a C_k .

Regioni di decisione. Esempio di un problema a due classi C1 e C2. In giallo è raffigurata la regione R1 corrispondente alla classe C1, in rosso la regione R2 corrispondente alla classe C2.

Regioni di decisione. Esempio di un problema a due classi C1 e C2. In giallo è raffigurata la regione R1 corrispondente alla classe C1, in rosso la regione R2 corrispondente alla classe C2.


Problema di Classificazione: Regioni di decisione (segue)

Osserviamo che ciascuna R_k può essere composta di varie regioni disgiunte.

Ad esempio in figura R_2 è composto da due regioni disgiunte.

I confini di tali regioni sono detti confini di decisione o superfici di decisione.

Regioni di decisione. Esempio di un problema a due classi C1 e C2. In giallo è raffigurata la regione R1 corrispondente alla classe C1, in rosso la regione R2 corrispondente alla classe C2.

Regioni di decisione. Esempio di un problema a due classi C1 e C2. In giallo è raffigurata la regione R1 corrispondente alla classe C1, in rosso la regione R2 corrispondente alla classe C2.


Classificazione: Regioni di decisione e approccio probabilistico

Un possibile criterio per determinare le regioni di decisione è quello di minimizzare l’errore di errata classificazione cioè l’errore di assegnare x a C_k quando invece questo appartiene a C_m con m \neq k .

Cominciamo con il considerare un problema a due classi C_1 e C_2.

Classificazione: Regioni di decisione e approccio probabilistico (segue)

Nel caso di due classi, allora, la probabilità di commettere tale tipo di errore, allora, sarà dato da:

  • P(error) = P(x\inR_2,C_1)+ P(x\inR_1,C_2) \rightarrow
  • P(error) = P(x\inR_2/C_1)P(C_1)+ P(x\inR_1/C_2)P(C_2) \rightarrow
  • P(error) = {\int}_{R_2}p(x/C_1)P(C_1)+ \int_{R_1}p(x/C_2)P(C_2)dx

dove p(x/C_m) è la funzione di densità di probabilità di x con la condizione che x sia calcolato a partire da elementi appartenenti alla classe C_m con  m=1,2.

Classificazione: Regioni di decisione e approccio probabilistico (segue)

Allora, dato un certo x, se risulta:

p(x/C_1)P(C_1 ) > p(x/C_2)P(C_2 ) al fine di minimizzare la probabilità di errore scegliamo R_1R_2 in modo che x appartenga a R_1.

In questo modo nel calcolo di P(error) viene escluso il contributo maggiore, cioè p(x/C_1)P(C_1 )).

Classificazione: Regioni di decisione e approccio probabilistico (segue)

Se abbiamo c classi, allora, possiamo estendere il ragionamento fatto nel seguente modo:

P(error) = P(x \in R_1, C_2)+ P(x \in R_1, C_3)+ \dots + P(x \in R_1, C_c) +
P(x \in R_2, C_1)+ P(x \in R_2, C_3)+\dots+ P(x \in R_2, C_c)) +

P(x \in R_c, C_2)+ P(x \in R_c, C_3)+\dots+ P(x \in R_c, C_{c-1})

Quindi

P(error)= \sum_k \sum_{m \neq k} \int_{R_k}p(x/C_m) P(C_M)dx

Classificazione: Regioni di decisione e approccio probabilistico (segue)

Per un problema a c Classi, allora, minimizzare l’errore di assegnare x a C_k quando invece appartiene a C_m con  m \neq k significa che se, per un dato x,

p(x/C_k)P(C_k ) > p(x/C_m)P(C_m ) per ogni m \neq k dovremmo scegliere le regioni  R_i in modo che x appartenga a R_k .

Infatti in tal modo p(x/C_k)P(C_k ) non darà alcun contributo nel calcolo dell’errore.

Problema di Classificazione: Regola di classificazione

Sulla base di quanto precedentemente visto è possibile, allora, seguire la seguente regola di classificazione:

  • Se P(C_k /x ) > P(C_m /x ) per ogni m \neq k allora l’elemento rappresentato da x è assegnato a C_k.

Tale regola nasce dall’applicazione del Teorema di Bayes e dal voler minimizzare l’errore di errata classificazione.

Problema di Classificazione: Regola di classificazione (segue)

Infatti P(C_k /x ) > P(C_m /x ) implica, dal teorema di Bayes, p(x/C_k)P(C_k )/p(x) > p(x/C_m)P(C_m )/p(x) e quindi p(x/C_k)P(C_k ) > p(x/C_m)P(C_m )

La regola precedente, allora, è equivalente a dire che:

Se  p(x/C_k)P(C_k ) > p(x/C_m)P(C_m ) per ogni m \neq k allora l’elemento rappresentato da x appartiene a C_k e, di conseguenza, a minimizzare l’errore di errata classificazione.

Problema di Classificazione: Alcune precisazioni

Per chiarire quanto detto nelle precedenti slide, mostriamo ora il Teorema di Bayes:

Sia p(x) la densità di probabilità di una variabile x il cui valore rappresenta gli elementi di un insieme S.

Siano C_k con  k=1,2,...,c le classi a cui tali elementi possono appartenere.

Sia P(C_k) la probabilità di occorrere della generica classe C_k (la probabilità a priori di ), P(C_k/x) la probabilità di C_k dato x (probabilità a posteriori di Ck) e  p(x/C_k) la densità di probabilità di x dato C_k.

Problema di Classificazione: Alcune precisazioni (segue)

Possiamo scrivere:

P(C_k,x)=p(x)P(C_k/x) oppure  P(C_k,x)=p(x/C_k)P(C_k)

Da cui deriva il teorema di Bayes, cioè:

p(x)P(C_k/x) = P(C_k,x)=p(x/C_k)P(C_k) \rightarrow P(C_k/x)=p(x/C_k)P(C_k)/p(x)

supposto che sia p(x) = \sum_k p(x/C_k) P(C_k)

Problema di Classificazione: Alcune precisazioni (segue)

La condizione p(x) = \sum_k p(x/C_k) P(C_k) assicura che \sum_k P(C_k/x) = \sum_k [p(x/C_k) P(C_k) / \sum_k p(x/C_k) P(C_k)]=1

Cioè, dato x, la probabilità che appartenga ad una qualunque delle classi è 1.

Problema di Classificazione: Alcune precisazioni (segue)

Sottolineiamo che:

L’importanza del teorema di Bayes è dovuta al fatto che la probabilità a posteriori di Ck è espressa in termini di quantità che sono in genere più facili da calcolare.

Problema di Classificazione: Alcune precisazioni (segue)

Osservazione:
La funzione densità di probabilità p(x) specifica che la probabilità che la variabile x assuma valori nell’intervallo [a,b] è data da:

P(x \in [a,b])= \int_a^bp(x)dx con P(x \in D) = \int_Dp(x)=1 se D corrisponde all’intero insieme di appartenenza di x.

Se ci sono d variabili  x_1, x_2,...,x_d possiamo considerare il vettore x= (x_1, x_2,...,x_d ) corrispondente ad un punto in uno spazio d-dimensionale. La distribuzione dei valori di x può essere descritta dalla funzione densità di probabilità p(x) tale che la probabilità che x cada in una regione R dello spazio di x è data da:

Problema di Classificazione: Funzioni discriminanti

In generale possiamo riformulare un problema di classificazione con c classi in termini di un insieme di c funzioni discriminanti:  y_1(x), y_2(x), ...,y_c(x) in modo tale che un elemento rappresentato da x è assegnato alla classe C_k se

y_k(x) > y_m(x) per ogni  m \neq k.

Se scegliamo come funzioni discriminanti y_k(x)=P(C_k/x) abbiamo una regola che minimizza la probabilità di errore di errata classificazione.

Problema di Classificazione: Funzioni discriminanti (segue)

Osserviamo che:

  • I confini di decisione sono dati dalle regioni dove le funzioni discriminanti sono uguali, così che se  R_k e R_m sono contigue poi il confine di decisione è dato da y_k(x)=y_m(x).
  • Possiamo sempre trasformare un funzione discriminante tramite funzioni monotoniche ottenendo ancora funzioni discriminanti.

Problema di Classificazione: Funzioni discriminanti (segue)

Osserviamo che:

  • Funzioni discriminanti per un problema a due Classi sono tradizionalmente riscritte in un forma più semplice. In questo caso, invece di usare due funzioni discriminanti y_1(x) ey_2(x), possiamo usare una unica funzione discriminante y(x)=y_1(x)-y_2(x)

e la regola di classificazione

  • SE  y_1(x)>y_2(x) allora C1, altrimenti C2

si trasforma

  • SE  y(x)>0 alllora C1, altrimenti C2.

Problema di Classificazione: Riassumendo

Un problema di classificazione può essere visto in termini di un insieme finito di funzioni discriminanti.

Le funzioni discriminanti possono assumere forme diverse, delimitando dei confini di decisione.

Il “goal”, allora, è trovare un algoritmo che permette di “trovare” tali funzioni.

  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion