Classificatore Naive Bayes

Un classificatore Naive Bayes è un semplice metodo per distinguere due classi di oggetti in base a delle proprietà osservate.

Teoria

Potete anche cominciare con un esempio

L’idea di base è quella di definire una funzione q(\b{x}) associata alla probabilità che un dato elemento sia classificato in una delle due classi {0,1} di Y, in questo caso, la probabilità che Y sia Y=1 è data dalla relazione:

q(\b{x}) := Prob\{Y = 1 | X = \b{x}\}

cioè la probabilità che Y sia Y=1 condizionata dal fatto di avere estratto X=\b{x}.

Supponiamo di avere un insieme di addestramento D_l e di avere un nuovo campione (\b{x},y), vogliamo stimare la probabilità che y sia y=1 e cioè la probabilità q(\b{x}) := Prob\{Y = 1 | X = \b{x}\}.

Applicando il teorema di Bayes:

Prob\{A | B\} = \frac{Prob\{B | A\} Prob\{A\}}{Prob\{B\}}

abbiamo:

Prob\{Y = 1 | X = \b{x}\} = \frac{Prob\{X = \b{x} | Y = 1\} Prob\{Y = 1\}}{Prob\{X = \b{x}\}}

Dato che Prob\{X = \b{x}\} non dipende da y, possiamo limitarci a stimare:

Q(\b{x}, 1) = Prob\{X = \b{x} | Y = 1\} Prob\{Y = 1\}
Q(\b{x}, -1) = Prob\{X = \b{x} | Y = -1\} Prob\{Y = -1\}

e quindi scegliere il valore di y pari alla stima più probabile.

Non avendo una stima della distribuzione di probabilità reale, ne facciamo una stima basata sull’insieme di addestramento D_l:

Prob\{Y = 1\} \approx \frac{1}{l}\left|\{y_i=1, i \in [1,l]\}\right|

come valor medio delle occorrenze di y=1.

Per stimare la probabilità condizionata facciamo una ipotesi semplificativa (da cui appunto, Naive Bayes), supponendo gli elementi di \b{x} indipendenti l’un l’altro.

Con questa ipotesi otteniamo:

Prob\{(x_1, x_2, ..., x_d) | Y = 1\} = \prod_{j=1}^{d}{Prob\{x_j | Y = 1\}}

e possiamo stimare ogni probabilità sfruttando l’insieme di addestramento:

Prob\{x_j | Y = 1\} = \frac{\left|\{\b{x_i}_{,j}=x_j, y_i=1, i \in [1,l]\}\right|}{\left|\{y_i=1, i \in [1,l]\}\right|}

cioè il rapporto tra il numero degli esempi positivi y_i=1 che contengono l’elemento x_j sotto esame, ed il numero totale degli esempi positivi.

Concludendo, dato un insieme di addestramento D_l, il classificatore f generato dall’algoritmo Naive Bayes classifica la nuova istanza \b{v} con:

f(\b{v})=\left\{+1\text{ se } Q(\b{v}, 1) \geq Q(\b{v}, -1)\\-1\text{ altrimenti}\right.

dove:

Q(\b{v},1) = \frac{\prod_{j=1}^{d}{\left|\{\b{x_i}_{,j}=v_j, y_i=1, i \in [1,l]\}\right|}}{\left|\{y_i=1, i \in [1,l]\}\right|^{d-1}}
Q(\b{v},-1) = \frac{\prod_{j=1}^{d}{\left|\{\b{x_i}_{,j}=v_j, y_i=-1, i \in [1,l]\}\right|}}{\left|\{y_i=-1, i \in [1,l]\}\right|^{d-1}}

Esempio

Facciamo un semplice esempio, supponiamo di voler classificare della frutta osservando due parametri: colore e forma. Conosciamo solo due tipi di frutta: mele e banane.

Supponiamo di avere una serie di esempi già classificati:

num | colore | forma | frutto
----|--------|-------|--------
 1  | giallo | tondo | mela
 2  | giallo | curvo | banana
 3  | rosso  | tondo | mela

Abbiamo un insieme di esempi di dimensione d=3, ogni esempio è caratterizzato da l=2 parametri.

Possiamo osservare che la stima della probabilità di avere mela è pari a \frac{2}{3}, mentre la stima della probablità di avere banana è \frac{1}{3}.

Supponiamo di rilevare i seguenti parametri: (giallo, tondo)

andiamo a stimare le due funzioni di qualità, prima sulla classe mela:

num |     colore     |    forma     | frutto
----|----------------|--------------|--------
 1  | giallo==giallo | tondo==tondo | mela
 3  | rosso!=giallo  | tondo==tondo | mela

Q((\text{giallo, tondo}),\text{mela}) = \frac{|(\text{giallo, \cancel{giallo}}), \text{mela}|\cdot |(\text{tondo, tondo}), \text{mela}|}{2^2}=\frac{2}{4}

In modo analogo consideriamo il caso della classe banana:

num |     colore     |    forma     | frutto
----|----------------|--------------|--------
 2  | giallo==giallo | curvo!=tondo | banana

Q((\text{giallo, tondo}),\text{banana}) = \frac{|(\text{giallo}), \text{banana}|\cdot |(\cancel{\text{tondo}}), \text{banana}|}{1^2}=\frac{0}{1}

per cui:

f(\text{giallo, tondo})=\text{mela}

Supponiamo di rilevare i parametri di un nuovo frutto: (rosso, curvo)

questo frutto non è presente nell’esperienza del classificatore, ma procediamo ugualmente con la stima delle due funzioni di qualità:

Q((\text{rosso, curvo}),\text{mela}) = \frac{|(\text{\cancel{rosso}, rosso}), \text{mela}|\cdot |(\text{\cancel{tondo}, \cancel{tondo}}), \text{mela}|}{2^2}=\frac{0}{4}

Q((\text{rosso, curvo}),\text{banana}) = \frac{|(\text{\cancel{rosso}}), \text{banana}|\cdot |(\text{curvo}), \text{banana}|}{1^2}=\frac{0}{1}

Le funzioni sono entrambe identicamente nulle, ma se abbiamo avuto l’accortezza di fare in modo che in caso di uguaglianza “vincesse” la classe più probabile, finiremo per stimare l’oggetto sconosciuto come membro della classe più numerosa nell’insieme di test, in questo caso le mele.

f(\b{v})=\left\{\text{mela}\text{ se } Q(\b{v}, \text{mela}) \geq Q(\b{v}, \text{banana})\\\text{banana}\text{ altrimenti}\right.

f(\text{rosso, curvo})=\text{mela}

  • carlo

    Vi ringrazio per la chiara spiegazione di un concetto, che a prima vista, mi sembra difficilissimo e che non puoi studiare o capire se non hai prima studiato 10 libri di statistica…
    Inoltre, vorrei chiedere a chi a scritto questa pagina se cortesemente potrebbe contattarmi, per il seguente motivo: sono al terzo anno di PhD in Computer Science e per il topic che sto trattando, Semantic Web, Ontologie and Search Engine, devo fare uso di una rete bayesiana. Io non sono un esperto ma e’ la prima volta che leggo della teoria che c’e’ dietro ad una rete bayesiana. Avrei, quindi, bisogno di una consulenza, Potresti aiutarmi?

    Grazie in anticipo,
    Carlo