Costi computazionali

Vengono esposti sinteticamente i costi computazionali di alcuni algoritmi utilizzati nel dominio della Text Categorization, con riferimento a quanto illustrato da Fan Li [43].

Nella Tabella 3.3 i simboli hanno i seguenti significati:

• $S$: numero di documenti utilizzati nella fase di training
• $V$: numero di parole (il vocabolario)
• $C$: numero di categorie (classi)
• $L$: lunghezza media di un documento
• $L'$: numero medio di caratteristiche (features) in un documento
• $k$: la lunghezza di un decision tree

I costi di GAME, rispetto a quanto visto nei paragrafi precedenti, sono stati espressi quindi in modo leggermente diverso, per facilitare il confronto con le misurazioni degli altri algoritmi.

Tabella 3.3: costi computazionali di alcuni algoritmi

algoritmo	costo training	costo test
GAME	$O(L \cdot S)$	$O(L \cdot C)$
Naive Bayes	$O(L \cdot S)$	$O(L \cdot C)$
SVM	comparabile a $O(k \cdot S \cdot C \cdot V)$	$O(C \cdot L' \cdot L \cdot S / V)$
Rocchio	$O(L \cdot S) + O(C \cdot V)$	$O(L' \cdot C)$

Dai costi si vede come esso si colloca fra gli algoritmi di classificazione più leggeri (sullo stesso livello del Naive Bayes, del quale però ha migliori prestazioni), mentre l' SVM computazionalmente è più dispendioso e non sempre utilizzabile. Il suo utilizzo per la progettazione di un filtro anti spam è stata dettata quindi dal fatto che risulta essere un ottimo compromesso fra prestazioni ottenibili e complessità computazionale richiesta.