2.4 Metodologie per la combinazione di classificatori
2.4.2 La fusione di classificatori
Questa metodologia prevede di tenere in considerazione tutte le stime fornite dai classificatori di base; nel seguito vengono illustrate le caratteristiche principali dei più utilizzati algoritmi per la fusione di classificatori.
Voting
Gli algoritmi basati sul Voting sono stati i primi ad essere utilizzati per inte- grare tra loro risultati provenienti da differenti classificatori. Fare riferimento al lavoro di Kuncheva [29] per una analisi approfondita delle varie tipologie di Voting.
Questi algoritmi prevedono che ognuno dei classificatori di base a dispo- sizione effettui la stima della classe di appartenenza dell’item i. Al termine della prima fase di classificazione, per ciascuna classe c e per ciascun item i, si calcola un punteggio pari al numero di metodi base che hanno stimato i come appartenente a c. L’item viene quindi assegnato alla classe che ha ottenuto il punteggio più alto: maggiore sarà il punteggio ottenuto, più elevata sarà l’attendibilità della classificazione.
Avendo a disposizione un numero N di classificatori e definita ˆSnla pre-
dizione fornita dal classificatore n-esimo, il punteggio ottenuto da ciascuna classe c nella classificazione di un item si calcola come:
Scorec= N
X
n=1
sc,n
in cui sc,nè così definito:
sc,n = 1 se ˆSn= c 0 altrimenti (2.25)
La classe ˆcda assegnare all’item si individua determinando il massimo pun- teggio ottenuto:
Class = ˆc
2.4. Metodologie per la combinazione di classificatori | 54|
Il punteggio minimo da raggiungere per assegnare l’utente ad una determi- nata classe varia a seconda del livello di attendibilità richiesto: generalmente si richiede un numero di voti superiore alla metà del numero di classificatori di base utilizzati. Qualora nessuna classe dovesse raggiungere il punteggio minimo prefissato l’item non verrebbe dunque assegnato.
Una variante del voto a maggioranza, detta Unanimity voting, si applica quando il livello di attendibilità richiesto sia particolarmente elevato; questo metodo impone che l’assegnamento avvenga solo se una classe raggiunga un punteggio pari a N, cioè se tutti i classificatori considerati siano concordi nella stima. Nel caso di classificazione binaria, cioè quando il numero di possibili classi a cui assegnare un item è pari a 2, si utilizzano generalmente un numero dispari di classificatori, per evitare che si verifichino situazioni di pareggio tra le due classi, e si richiede che una delle due classi raggiunga la maggioranza dei voti a disposizione.
Utilizzando gli algoritmi appena descritti, il voto di ciascun classificatore di base contribuisce alla determinazione del punteggio finale ottenuto dalle classi nella stessa misura, senza considerare le peculiarità di ciascun classificatore come, ad esempio, l’accuratezza complessiva o l’abilità nell’individuare utenti appartenenti ad una specifica classe. Sono state quindi proposte delle varianti alla metodologia di base, in cui a ciascun classificatore viene assegnato un peso, determinato a seconda delle caratteristiche e dalle performance da esso ottenute. In queste metodologie, dette Weighted voting, il punteggio ottenuto da una classe c nella classificazione di un item i viene ottenuto moltiplicando ciascun voto per il peso assegnatoli e sommando i voti pesati dei singoli classificatori. Scorec= N X n=1 sc,n∗ ωn
in cui ωnè il peso assegnato al classificatore n, mentre sc,nè calcolato come
nell equazione (2.25).
Il peso da assegnare a ciascun classificatore può essere determinato secon- do vari criteri, ad esempio impostando pesi proporzionali all’accuratezza ed alla probabilità di successo del classificatore, o inversamente proporzionali alla probabilità di errore.
Naive Bayes Combination
Questo metodo utilizza il concetto di probabilità a posteriori, considerando tutte le possibili combinazioni di stime fornite dai classificatori di base, e cercando di individuare la classe da assegnare ad un item a seconda della combinazione di stime ottenuta.
In un prima fase, tutti i classificatori di base vengono utilizzati per stimare gli item contenuti in un insieme di apprendimento, dei quali siano note le classi di appartenenza. Per ogni classe c e per ogni possibile combinazione
ˆ
Σ = ( ˆS1, ˆS2, . . . , ˆSN)delle stime fornite dai classificatori di base, si calcola la
probabilità a posteriori che un item appartenga a c, se i classificatori di base hanno fornito una combinazione di stime ˆΣ.
Per il Teorema di Bayes, tale probabilità vale:
P c| ˆΣ) = P c| ˆS1, ˆS2, . . . , ˆSN) =
P cP ( ˆS1, ˆS2, . . . , ˆSN|c
P ˆS1, ˆS2, . . . , ˆSN
in cui P c è la probabilità che un item preso a caso dal campione di apprendi- mento appartenga alla classe c, calcolata come il rapporto tra il numero degli item appartenenti alla classe c e il numero totale di item presenti nel campione. Inoltre, se i classificatori sono tutti indipendenti tra di loro vale che:
P ( ˆS1, ˆS2, . . . , ˆSN|c) = N Y n=1 P ˆSn|c
Il valore di P ˆS1, ˆS2, . . . , ˆSN non dipende dalla classe c, quindi:
P c|( ˆS1, ˆS2, . . . , ˆSN) = P c N Y n=1 P ˆSn|c (2.26)
Nella fase di classificazione degli item si ricava la combinazione di stime ˆΣ, utilizzando i classificatori di base e si assegna la classe ˆcper la quale si ottiene il massimo valore P ˆc| ˆΣ, calcolato attraverso l’equazione (2.26).
Behavior Knowledge Space
Questo metodo, presentato da Huang in [24], è molto simile alla Naive Bayes Combination descritta in precedenza. Anche in questo caso la prima fase consiste nella stima degli item contenuti nell’insieme di apprendimento
2.4. Metodologie per la combinazione di classificatori | 56|
con i classificatori di base. Successivamente, si costruisce una lock-up table formata da un numero di righe pari a quello delle classi presenti ed un numero di colonne pari a quello delle possibili combinazioni ˆΣdelle stime fornite dai classificatori di base. Per ciascuna classe c e per ciascuna combinazione ˆΣsi calcola il numero di item dell’insieme di apprendimento appartenenti a c, per i quali i classificatori di base hanno restituito la combinazione di stime ˆΣe lo si inserisce all’interno della lock-up table nella cella corrispondente.
La Tabella 2.4 è un esempio di lock-up table ricavata per la stima di item utilizzando due possibili classi c1e c2, ed i classificatori S1 e S2.
ˆ S1 = c1 Sˆ1 = c1 Sˆ1= c2 Sˆ1= c2 ˆ S2 = c1 Sˆ2 = c2 Sˆ2= c1 Sˆ2= c2 c1 127 58 92 14 c2 35 62 131 194
Tabella 2.4: esempio di look-up table per l’applicazione del metodo BKS.
Nella fase di caratterizzazione degli item di cui non è nota la classe di appartenenza, si ricava la combinazione delle stime, applicando tutti i classifi- catori di base. In seguito si individua la colonna della lock-up table associata alla combinazione ottenuta per l’item, il quale viene assegnato alla classe corrispondente alla riga con il maggior numero di utenti.
ˆ S1 = c1 Sˆ1 = c1 Sˆ1= c2 Sˆ1= c2 ˆ S2 = c1 Sˆ2 = c2 Sˆ2= c1 Sˆ2= c2 c1 127 58 92 14 c2 35 62 131 194
Tabella 2.5: esempio di attribuzione della classe ad un utente applicando il metodo BKS.
Nell’esempio presentato in precedenza, se per un nuovo item si ricavasse la combinazione ˆS1 = c1 e ˆS2 = c1, esso sarebbe assegnato alla classe c1,
la quale risulta associata alla riga con il valore più elevato per la colonna corrispondente alla stima fornita dai classificatori di base (vedi Tabella 2.5).
É anche possibile stabilire una soglia oltre la quale ritenere affidabili i risultati: ad esempio, nel caso della configurazione delle stime ˆS1 = c1 e
ˆ
S2 = c2la differenza tra i valori associati alle due classi è poco significativa, e
potrebbe dare origini ad errori nella classificazione.