Home

Federica EU

1/18

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.

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.

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_1$ e $R_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 C_k è 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:

$\text{[math]}$

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