Classificazione multidimensionale gerarchica di documenti

2 Indice
L’applicazione pratica che fungerà un po’ da filo conduttore è il terzo
scenario elencato in precedenza, quello dell’INAIL.
Chiudiamo con una nota su alcune convenzioni tipografiche. Useremo:
• il corsivo e il grassetto, per enfatizzare parti salienti del testo;
• il font senza grazie, per distinguere dal testo nomi di entità (categorie,
persone, programmi, ecc.);
• il font monospaziato, per distinguere dal testo nomi riferentesi al
codice (nomi di classi, metodi, ecc.).
Capitolo 1
Il problema della classificazione
Il centro di gravità dell’interesse umano verrà a
spostarsi verso le questioni filosofiche circa ciò che può
essere fatto in linea di principio, e via discorrendo.
Alan M. Turing, Conferenza alla London
Mathematical Society del 20 febbraio 1947
In questo capitolo definiamo formalmente il problema della classifi-
cazione, nelle sue diverse varianti (singola vs. multipla, multidimen-
sionale, gerarchica, “soft”). Vedremo che la disciplina dell’Apprendimento
Automatico risolve questo problema costruendo automaticamente un
classificatore per classificare nuovi oggetti, sulla base di esempi di ogget-
ti già classificati, limitando l’intervento umano alla raccolta degli es-
empi. Illustreremo infine diverse tecniche che permettono di valutare
quanto un classificatore appreso automaticamente sia efficace nel clas-
sificare nuovi oggetti: holdout, cross-validation e bootstrap.
1.1 Definizione generale
Il problema della classificazione può essere formalizzato come segue:
Problema 1.1 (Classificazione - forma generale).
Dati:
• Un insieme D contenente tutti i documenti classificabili
• Un insieme C = {c1, . . . , cn} contenente le possibili categorie a cui può
appartenere un documento d ∈ D.
4 1. Il problema della classificazione
Trovare una funzione f : D × C → {T,F}, detta classificatore (classifier).
In particolare, se n = 2, il classificatore ed il problema di classificazione si
dicono binari.
Esempi di D possono essere, per riprendere l’introduzione, l’insieme
di tutti i possibili curricula vitae, di tutte le possibili e-mail, o di tutte le
possibili denunce di infortunio.
Se, dati un documento d ∈ D ed una categoria c ∈ C, f (d, c) = T, in-
terpretiamo ciò dicendo che f classifica il documento d nella categoria C;
altrimenti, se f (d, c) = F, significa che f non classifica d in c (ma forse in
qualche altra categoria).
Si noti che, in questa formulazione, f può classificare un documento d in
più categorie distinte. Infatti può accadere che f (d, ci1) = f (d, ci2) = . . . =
f (d, cik) = T, con ci1 6= ci2 6= . . . 6= cik , cii , ci2 , . . . , cik ∈ C: in questo caso, f
classifica d nelle k categorie cii , ci2 , . . . , cik : ciò riflettere problemi reali in cui
le categorie in C non sono mutuamente esclusive.
Viceversa, può anche accadere che un documento d non sia classificato in
nessuna categoria, cioè ∀c ∈ C : f (d, c) = F, ossia nessuna categoria di
C viene ritenuta appropriata per d. Se ciò ha senso, vuol dire che le cat-
egorie non sono esaustive. In questo caso, in genere ci si riconduce al ca-
so di categorie esaustive, considerando un’ulteriore categoria altro tale che
∀c ∈ C : f (d, c) = F ⇔ f (d, altro) = T, ottenendo un nuovo insieme di
categorie C ′ = C ∪ {altro}.
Spesso viene introdotta una categoria aggiuntiva anche se le categorie di C
sono semanticamente esaustive, perché molte volte è preferibile non classi-
ficare un documento, piuttosto che classificarlo male: si aggiunge così una
categoria non classificato in cui verranno posti tutti i documenti non classi-
ficati. Non classificato ha le stesse proprietà di altro; in effetti la differenza
sussiste solo a livello semantico.
Non abbiamo ancora detto come si può ottenere il classificatore f .
Il problema può essere brillantemente risolto da un sistema esperto, ossia,
in parole povere, un programma in cui sono state incorporate delle regole
date da esperti che dicono, nel caso della classificazione, quali criteri utiliz-
zare per classificare i documenti. Questo è l’approccio dell’Ingegneria della
Conoscenza, usato in passato. Esso ha il vantaggio di produrre classificatori
1.1. Definizione generale 5
molto accurati1 ma ha due grossi svantaggi:
• La creazione di un classificatore richiede uno sforzo notevole
• I classificatori ottenuti sono legati ad un particolare dominio applica-
tivo (ad esempio, un classificatore di curriculum non può essere facil-
mente modificato per classificare denunce)
Nell’introduzione abbiamo invece accennato ad un altro approccio, quello
dell’Apprendimento Automatico. In questo approccio, esiste un programma,
detto learner2, che è in grado di generare automaticamente un classificatore,
sulla base di esempi di documenti già classificati. L’insieme degli esempi
è detto training set (insieme di addestramento). Restando nella formulazione
generale, esso può essere definito come un sottoinsieme Tr diD×C×{T,F}
tale che ∀ (d, c, v) ∈ Tr∀c′ ∈ C∃v′ ∈ {T,F} : (d, c′, v′) ∈ Tr.
Quest’approccio ha due grossi vantaggi:
• La creazione di un classificatore è totalmente automatica, solo la creazione
del learner richiede sforzo
• Solo gli esempi sono legati al dominio applicativo, non il learner: ciò
significa che, dando in input al learner di volta in volta esempi di doc-
umenti relativi a diversi domini applicativi, esso genererà ogni volta
un classificatore per il dominio applicativo voluto.
Quanto all’accuratezza dei classificatori prodotti, con l’approccio dell’Ap-
prendimento Automatico è possibile ottenere classificatori accurati pressap-
poco quanto quelli costruibili con l’approccio dell’Ingegneria della Conoscen-
za, grazie agli ultimi progressi della ricerca.
Per quanto riguarda la valutazione di un classificatore, ciò richiede che
la categoria corretta sia nota per un sottoinsieme di D, detto test set, che
1L’accuratezza è un aspetto fondamentale rispetto al quale valutare un classificatore, e
consiste sostanzialmente nella probabilità che la classe restituita da un classificatore per un
documento sia corretta. Nel capitolo 8 formalizzeremo questo concetto e vedremo anche
altri criteri per la valutazione di un classificatore.
2Non esiste una parola corrispondente in italiano; una delle traduzioni è l’espressione
programma di apprendimento, ma useremo il termine inglese perché breve e comune in
letteratura.
6 1. Il problema della classificazione
denoteremo con Te. I documenti del test set vengono spesso chiamati doc-
umenti di test o esempi di test. È fondamentale che il training set ed il test
set siano disgiunti. Infatti, un classificatore è in grado di classificare cor-
rettamente almeno gran parte (spesso la totalità) dei documenti di training
utilizzati per l’apprendimento dello stesso, quindi la valutazione dell’accu-
ratezza su documenti di training sarebbe falsata in positivo.
Finora abbiamo visto il problema della classificazione nella formulazione
più generale possibile; nei sottoparagrafi seguenti vedremo alcune formu-
lazioni più specifiche.
1.2 Classificazione singola vs. multipla
Nella formulazione generale del problema di classificazione, un documen-
to può essere classificato in una o più categorie (supponiamo di aver reso
le categorie esaustive, se non lo fossero state, come spiegato nel paragrafo
1.1). In questo caso si parla di classificazione multipla (multi-label). Un caso
particolare si ha imponendo che un documento appartenga ad una ed una
sola categoria: si parla allora di classificazione singola (single-label). Possi-
amo definire formalmente il problema di classificazione singola in questo
modo:
Problema 1.2 (Classificazione singola - forma generale).
Dati:
• Un insieme D contenente tutti i documenti classificabili
• Un insieme C = {c1, . . . , cn} contenente le possibili categorie a cui può
appartenere un documento d ∈ D.
Trovare una funzione f : D × C → {T,F}, detta classificatore singolo (single-
label classifier) tale che ∀d ∈ D∃|c : f (d, c) = T.
1.3 Classificazione multidimensionale
Nella classificazione multidimensionale, si individua una partizione di C
costituita dam insiemi Dim1, . . . ,Dimm, detti dimensioni, tale che ogni doc-
1.4. Classificazione gerarchica 7
umento diD deve appartenere ad una ed una sola classe per ogni Dimi. Più
formalmente:
Problema 1.3 (Classificazione multidimensionale).
Dati:
• Un insieme D contenente tutti i documenti classificabili
• Un insieme C contenente le possibili categorie a cui può appartenere un
documento d ∈ D
• Una partizione {Dim1, . . . ,Dimm} di C, con Dimi = {ci1, . . . , ciki}
Trovare una funzione f : D×C → {T,F}, detta classificatore multidimension-
ale (multidimensional classifier), tale che ∀d ∈ D∀i ∈ {1, . . . ,m} ∃|c ∈ Dimi :
f (d, c) = T.
In particolare, se ∀i ∈ {1, . . . ,m} |Dimi| = 2, il classificatore multidimension-
ale ed il problema di classificazione si dicono binari.
In sintesi, ad ogni documento vengono assegnate m categorie, una per
dimensione: è una classificazione multipla con un numero fisso di categorie
contemporaneamente assegnabili, e tale che all’interno di ciascuna dimen-
sione si ha un problema di classificazione singola.
Le dimensioni corrispondono a diversi punti di vista da cui guardare i doc-
umenti: ciascun documento viene classificato rispetto a tutti i punti di vista.
Per esempio, D potrebbe essere un insieme di articoli giornalistici, e le di-
mensioni potrebbero essere l’argomento, ad esempio {sport, politica, spettacolo}
e la nazione in cui è accaduto l’evento, ad esempio {Italia,Francia,Germania}.
1.4 Classificazione gerarchica
Nella classificazione gerarchica, ogni categoria può avere delle sottocate-
gorie, partendo da una categoria radice; le categorie sono infatti i vertici di
un albero:
Problema 1.4 (Classificazione gerarchica).
Dati:
8 1. Il problema della classificazione
• Un insieme D contenente tutti i documenti classificabili
• Un insieme C = {c1, . . . , cn} contenente le possibili categorie a cui può
appartenere un documento d ∈ D
• Un albero radicato T = (C,E), non orientato3
Trovare una funzione f : D×C → {T,F}, detta classificatore gerarchico (hier-
archical classifier), tale che ∀d ∈ D∀c ∈ C : f (d, c) = T ⇒ f (d, father (c)) =
T, dove father (c) è il padre di c in T .
I figli di una categoria c rappresentano delle categorie più specifiche di c,
ad esempio la categoria sport può avere le sottocategorie calcio, nuoto, ciclismo.
Perciò se un documento appartiene ad un figlio di c, deve appartenere an-
che al padre c (un documento sul calcio parla di sport), mentre il viceversa
non è detto (un documento di sport non sempre è sul calcio).
Abbiamo detto che in genere si aggiunge a C una categoria aggiun-
tiva, detta altro o non classificato, in cui sono classificati tutti i documen-
ti non classificati nelle altre categorie; nel caso della classificazione ger-
archica, questa categoria è la radice dell’albero T . La condizione ∀d ∈
D∀c ∈ C : f (d, c) = T ⇒ f (d, father (c)) = T implica che tutti i docu-
menti vengono classificati nella radice, oltre che, eventualmente, in classi
più specifiche. Un documento potrebbe essere classificato solo nella radice:
ecco che, se le categorie a livello maggiore di zero formano C, la radice
può fungere da altro o non classificato. Questa volta però della condizione
∀c ∈ C : f (d, c) = F⇔ f (d, altro) = T vale solo l’implicazione verso destra.
1.5 Classificazione gerarchica multidimensionale
Nella classificazione gerarchica multidimensionale (o multidimensionale ger-
archica), l’insieme C delle categorie è partizionato in dimensioni, come nel-
la classificazione multidimensionale, ed ogni dimensione ha la struttura di
albero, come nella classificazione gerarchica:
Problema 1.5 (Classificazione gerarchica multidimensionale).
Dati:
3Oppure un’arborescenza, in cui gli archi sono orientati dalla radice verso le foglie.
1.6. Classificazione “soft” 9
• Un insieme D contenente tutti i documenti classificabili
• Un insieme C = {c1, . . . , cn} contenente le possibili categorie a cui può
appartenere un documento d ∈ D
• Una partizione {Dim1, . . . ,Dimm} di C, con Dimi = {ci1, . . . , ciki}
• m alberi radicati non orientati T1 = (Dim1, E1) , . . . , Tm = (Dimm, Em)
Trovare una funzione f : D × C → {T,F}, detta classificatore gerarchico
multidimensionale (hierarchical multidimensional classifier), tale che:
• ∀d ∈ D∀i ∈ {1, . . . ,m} ∃cp, cq ∈ Dimi :
f (d, cp) = f (d, cq) = T⇒ cp = cq ∨ ancestori (cp, cq) ∨ ancestori (cq, cp)
• ∀d ∈ D∀c ∈ C : f (d, c) = T⇒ f (d, fatheri (c)) = T
dove fatheri (c) è il padre di c in Ti ed il predicato ancestori (c, d) è vero se c è
antenato di d in Ti.
Le due condizioni su f implicano che per ogni dimensione è possibile
assegnare ad un documento solo categorie appartenenti allo stesso ramo
dell’albero, di cui una è padre dell’altra (fino alla radice, che non ha padre).
Di queste categorie in genere si considera solo la più specifica, quindi di fat-
to la classificazione su ciascuna dimensione viene considerata singola anche
se, rigorosamente parlando, è multipla.
1.6 Classificazione “soft”
Nel paragrafo 1.1 abbiamo definito un classificatore come una funzione da
D × C in {T,F}. In pratica però si fa un’assunzione più forte, ossia che
il classificatore restituisca un punteggio reale, tipicamente compreso tra 0
e 1, che rappresenta un fattore di certezza: più è alto il punteggio, più
il classificatore ritiene che la categoria sia appropriata per il documento.
Formalizzando:
Problema 1.6 (Classificazione - forma generale “soft”).
Dati:
10 1. Il problema della classificazione
• Un insieme D contenente tutti i documenti classificabili
• Un insieme C = {c1, . . . , cn} contenente le possibili categorie a cui può
appartenere un documento d ∈ D.
Trovare una funzione f : D×C → [0, 1], detta classificatore (classifier), tale che
f (d, c) è tanto più alto, quanto c è ritenuta appropriata per d4.
In particolare, se n = 2, il classificatore ed il problema di classificazione si
dicono binari.
Le specializzazioni di questo problema al caso singolo, multiplo, ger-
archico, multidimensionale e gerarchico multidimensionale sono perfetta-
mente analoghe a quelle già viste.
Il fatto che il classificatore restituisca un punteggio introduce molta in-
formazione. Ad esempio, supponendo che i punteggi indichino probabilità,
è possibile individuare la categoria più probabile, o le k categorie più prob-
abili per qualche k, cosa che sarebbe impossibile se l’output fosse solo T o
F.
1.7 Valutazione di un classificatore
Come abbiamo detto nel paragrafo 1.1, è fondamentale che, in fase di val-
utazione, training set e test set siano disgiunti. In realtà questa condizione
non basta per ottenere stime di efficacia non falsate. A tale scopo, è neces-
saria una condizione più forte: che il training set ed il test set siano indipen-
denti. Spesso nella pratica si dispone di un dataset D′ ⊆ D, costituito da
documenti per cui si conosce la categoria corretta, questo viene bipartizion-
ato ottenendo un training set Tr ed un test set Te (metodo holdout), ed in-
fine si valuta il classificatore rispetto al test set. Ad esempio, l’accuratezza
verrebbe calcolata come:
accHoldout =
∑
xi∈Te
δ (I (Tr , xi) , yi)
|D′|
4Questa precisazione in realtà ha solo una valenza semantica, ma qui non aggiunge
nulla dal punto di vista formale.
1.7. Valutazione di un classificatore 11
dove I (S, xi), per un qualsiasi S ⊆ D, è la categoria restituita dal classi-
ficatore appreso su S per l’esempio xi, yi è la classe a cui appartiene xi e δ
restituisce 1 se e solo se i suoi argomenti sono identici, altrimenti restituisce
0.
Così facendo, però, il training set ed il test set non sono indipendenti,
perché ciascun documento di D′, se appartiene ad uno dei due, non ap-
partiene all’altro. Di conseguenza, una categoria che ha molti esempi di
training ne ha pochi di test, e viceversa. Per dimostrare questo problema,
Ron Kohavi, in [Kohavi 1995] descrive un esperimento condotto sul dataset
Iris considerando un terzo delle istanze come training set e usando un clas-
sificatore che predice la categoria più frequente nel training set. Il dataset
Iris descrive le piante di iris con quattro attributi continui e il compito è
classificare ciascuna istanza, rappresentante un iris, come Iris Setosa, Iris
Versicolour o Iris Virginica. Per tutte e tre le categorie ci sono 50 esempi
riportanti la classe corretta, per un totale di 150: ci aspetteremmo il 33,33%
di accuratezza da parte del classificatore. Tuttavia, poiché il test set con-
tiene meno di un terzo degli esempi della classe prevalente nel training set,
l’accuratezza prevista è inferiore (ripetendo l’esperimento 500 volte si è ot-
tenuta una media di 27,68% con una deviazione standard di 0.13).
Oltre a non mantenere l’indipendenza tra training e test set, un altro prob-
lema del metodo holdout è che, per ottenere stime più affidabili possibile,
spesso metà o più del dataset iniziale viene usata come test set, riducendo
il numero di esempi di training: ciò è uno svantaggio, se si considera che
spesso l’accuratezza di un classificatore aumenta all’aumentare del numero
degli esempi di training.
Un metodo di valutazione che non soffre dei problemi dell’holdout è la
k-fold cross-validation. Essa consiste nello scegliere un intero k, 2 ≤ k <
|D′|, dividere il dataset D′ in k sottoinsiemi D′1, . . . , D′k, detti fold, di uguale
cardinalità, ed apprendere k classificatori, ciascuno dei quali viene appreso
su D′ \ D′
i
e valutato su D′
i
, al variare di i tra 1 e k. La valutazione comp-
lessiva è una media delle valutazioni sui k fold, con macroaveraging o con
microaveraging (per le definizioni di macroaveraging o microaveraging5.
5La microaveraging di m frazioni a1b1 , . . . , ambm è definita come
m∑
i=1
ai
m∑
i=1
bi
: ne consegue che
12 1. Il problema della classificazione
Nel caso dell’accuratezza, la valutazione complessiva con microaveraging
è data da:
accCV =
k∑
i=1
∑
xi∈D′i
δ (I (D′ \D′
i
, xi) , yi)
k∑
i=1
|D′
i
|
=
k∑
i=1
∑
xi∈D′i
δ (I (D′ \D′
i
, xi) , yi)
|D′|
ossia dal numero totale di classificazioni corrette, diviso per |D′|.
Nella cross-validation completa, l’accuratezza viene mediata su tutti i(
|D′|
|D′|
k
)
possibili modi di scegliere |D′|k esempi tra un totale di |D′| esempi,
ma questo è spesso troppo dispendioso in termini di tempo. Tranne per la
|D′|-fold cross-validation, detta leave-one-out, la k-fold cross validation sti-
ma la k-fold cross validation completa usando una sola suddivisione del
dataset in k sottoinsiemi. Nella cross-validation stratificata, il dataset viene
suddiviso in modo tale che tutti i fold abbiano approssimativamente la
stessa percentuale di esempi per ciascuna categoria.
Un learner si dice stabile per un training set Tr ed un insieme di pertur-
bazioni P , se il classificatore appreso su Tr fa le stesse previsioni di quel-
li appresi sul training set ottenuto perturbando Tr con una perturbazione
p ∈ P . Nella cross-validation, al learner vengono dati in input di volta in
volta training set che differiscono per |D
′
|
k esempi, quindi possiamo consid-
erare come perturbazione la sostituzione di |D′|k esempi con altrettanti altri.
L’assunzione di base della cross-validation, per cui si ottengono stime di
efficacia non distorte, è la stabilità del learner rispetto a questo tipo di per-
turbazioni. Quest’assunzione non è quasi mai verificata per perturbazioni
molto grandi, motivo per cui spesso il valore di k è mantenuto basso. Sper-
imentalmente si è osservato che con valori di k compresi tra 10 e 20 si ot-
tengono stime non distorte nella maggior parte dei casi, e comunque meno
distorte di quelle ottenute con l’holdout di 13 (dove cioè
1
3 del dataset viene
usato come test set).
ρH (x,y) è la microaveraging dei margini di (x,y) rispetto a ciascun iperpiano. Rispet-
to alla media aritmetica, detta anche macroaveraging, che pesa in maniera uguale tutti i suoi
argomenti, la microaveraging può far pesare maggiormente le frazioni più grandi.
1.7. Valutazione di un classificatore 13
Un altro metodo di valutazione è il bootstrap. In questo caso, il training
set si ottiene estraendo con rimpiazzamento |D′| esempi da D′, ed il test set
è l’insieme degli esempi non estratti. La probabilità che un esempio non
sia stato scelto dopo |D′| estrazioni è
(
1− 1
|D′|
)
|D′|
≈ e−1 ≈ 0.368, quindi il
test set Te ed il training set Tr sono costituiti in media, rispettivamente, da
0.368 |D′| e 0.632 |D′| esempi. La stima dell’accuratezza del classificatore è
una media dell’accuratezza sul training set e sul test set, pesata rispetto alle
rispettive cardinalità attese:
accB = 0.632 · accTr + 0.368 · accTe (1.1)
dove accTr e accTe sono le stime di accuratezza calcolate rispetto al train-
ing set e al test set, cioè accTr =
∑
xi∈Tr
δ(I(Tr ,xi),yi)
|Tr | e accTe =
∑
xi∈Te
δ(I(Tr ,xi),yi)
|Te| .
Più in generale, si fissa un intero b > 0 – il numero di diversi training set
da prelevare col metodo del bootstrap – e si calcola la media delle stime di
accuratezza ottenute dalla 1.1 per ciascuna coppia (training set, test set):
accB =
1
b
b∑
i=1
(0.632 · accTri + 0.368 · accTei)
dove Tr i e Te i sono rispettivamente l’i-esimo training set e l’i-esimo test
set ottenuti col metodo del bootstrap.
L’assunzione del bootstrap è la stessa della cross-validation, ossia la stabil-
ità del learner. Inoltre, si può dimostrare che le stime di accuratezza ot-
tenute sono distorte se il learner è, totalmente o in parte, un memorizzatore
perfetto (ossia ricorda esattamente gli esempi di training).