Appunti seconda parte Data Mining

Stima della precisione e strategie di apprendimento

Calcolo della precisione e stima di Laplace

Esempi classificati correttamente, cioè il numero di esempi coperti dalla regola, l’accuratezza del training set è data da P(+|c)=n₊/n. Più correttamente, essa è la precisione della regola, perché è la frazione degli esempi classificati come positivi che sono effettivamente positivi (probabilità della classe positiva data la regola). Questa stima prende il nome di stima attraverso la frequenza relativa (si tratta di un rapporto fra conteggi).

Questa stima ha dei problemi nel caso di pochi esempi. Infatti, se n₊ = 0, cioè se la regola copre 0 positivi, allora l’accuratezza sarà P(+|c)=0/n anche se n₊ è molto piccolo, cioè n₊ potrebbe non essere una stima molto affidabile. Inoltre, se la regola copre 0 esempi, cioè n=0, allora P(+|c) diventa 0/0 e non si può calcolare. In questi casi si dimostra che la stima attraverso la frequenza relativa non è affidabile.

È meglio usare la stima di Laplace, che nel caso di due classi vale (n₊+1)/(n+2), mentre nel caso di N classi è (n₊+1)/(n+N). Questo non crea problemi nel caso di n₊ e n pari a 0 e in tal caso la precisione verrà esattamente ½. Per n₊ ed n grandi, i fattori 1 e 2 sono trascurabili ed entrano in gioco solamente per piccoli valori di n₊ e n.

Questa stima di Laplace assume che le 2 (o N) classi siano uniformemente distribuite nel training set. Se non è vero, allora bisogna usare la stima-m, cioè data p la probabilità che un esempio estratto a caso dal training set abbia la classificazione assegnata dalla regola (classe p) e m un peso, allora P(c|n₊,n)=((n₊+mp)/(n+m)).

Questa è una forma generale della stima della precisione e che comprende tutte le altre viste prima. Infatti, se m=0, si ottiene l’accuratezza, mentre se m=N e p=1/N, cioè tutte le classi sono ugualmente probabili, ottengo la stima di Laplace. Infine, si nota che per grandi valori di n₊ e n la stima-m e la stima di Laplace si avvicinano alla frequenza relativa, cioè queste correzioni non influenzano la stima.

Ricerca di regole: da generale a specifico

Tipicamente, la ricerca da generale a specifico è la ricerca hill-climbing senza backtracking, cioè si sceglie di specializzare la regola con le performance più alte (sempre nel caso apprendimento di attributi booleani). Il problema di tale ricerca è che è molto greedy e che può portare a scelte subottimali in alcuni passi. Per ridurre quest’ultimo rischio viene a volte effettuata una ricerca beam, in cui ad ogni passo non si mantiene una sola ipotesi, la migliore, ma una lista dei migliori k candidati (tra i sistemi che compiono ricerca beam top-down ci sono CN2 e AQ, quest’ultimo basato su un esempio seme per guidare la ricerca).

Approccio per attributi non booleani

Se l’attributo target NON è booleano (più di due classi) non apprendiamo più solamente regole che hanno nel conseguente vero, cioè classe positiva, ma si apprende un insieme di regole con diversi conseguenti. In tal caso esistono due approcci:

• Si tiene una lista ordinata di regole, in cui per classificare un nuovo esempio si scorrono dalla prima regola all’ultima e la prima che fa match fornisce nel conseguente la classificazione dell’esempio. L’ultima regola dell’insieme è una regola di default che classifica tutti gli esempi che non fanno match con nessuna regola (procedura utilizzata dal sistema CN2).
• Si tiene una lista NON ordinata di regole, in cui si prende l’esempio da classificare, si controlla se fa match con ogni regola ed infine si raccolgono tutte le regole che fanno match, restituendo come classe quella più frequente fra gli esempi di training coperti dalle regole che fanno match. Se non fa match con nessuna regola, la classificazione è data dalla classe più frequente tra gli esempi di training (procedura utilizzata dal sistema AQ).

Algoritmo di apprendimento sequenziale CN2

Consideriamo ora l’algoritmo d’apprendimento sequenziale di CN2, il quale differisce da quello sequenziale visto prima, perché in grado di imparare regole per diversi concetti e la procedura APPRENDI_UNA_REGOLA non restituisce una regola, ma solo un antecedente e il cui conseguente è aggiunto solo successivamente. Entrando nel dettaglio, l’algoritmo ha come input l’attributo target, gli attributi e gli esempi.

Dopo aver inizializzato l’insieme delle regole apprese con l’insieme vuoto, viene effettuato un ciclo in cui si richiama la procedura APPRENDI_UN_ANTECEDENTE per apprendere il miglior antecedente possibile e con l’attributo di input k è la dimensione del beam. Successivamente chiamo E’ l’insieme di esempi coperti da Best_ant e lo rimuoviamo dall’insieme di esempi. Dopodiché chiamo C la classe più comune fra gli esempi di E’ e aggiungo la regola “if Best_ant then class=C’” alla fine dell’insieme Regole_apprese e ripeto questo procedimento finché Best_ant è nullo, oppure l’insieme degli esempi è vuoto. Infine, aggiungiamo alla fine di Regole_apprese la regola di default “class=C” dove C è la classe più frequente in Esempi e restituisco l’insieme Regole_apprese.

Entrando nel dettaglio, la funzione APPRENDI_UN_ANTECEDENTE parte da un beam, che contiene un antecedente vuoto, e da una variabile Best_ant inizializzata anch’essa con l’antecedente vuoto. Dopodiché viene effettuato un ciclo ripetuto finché Beam non è vuoto e in cui si specializzano tutti gli antecedenti di beam predisponendo due insiemi: il primo è All_contraints ed è un insieme di vincoli nella forma attributo=valore (nel caso di attributi tutti discreti), mentre il secondo è Nuovo_beam.

Quest’ultimo è costruito iterando per ciascun h in Beam e in ciascun vincolo c in All_contraints, creando una specializzazione di h aggiungendo c. A questo punto si rimuove da Nuovo_beam tutte le ipotesi duplicate, inconsistenti (es. se aggiungo a=v e a=w, otterrò un antecedente che non sarà mai vero) o che erano già in Beam. Successivamente, come riportato al lato, aggiorniamo il miglior antecedente.

Specificatamente, per ciascun antecedente h in Nuovo_beam se le performance di h sono migliori del miglior antecedente, allora assegno h alla variabile best_ant e aggiorniamo il beam. Quest’ultima operazione farà si che la nuova versione del beam sia i migliori k membri di Nuovo_beam secondo la misura di performance.

Gestione esempi negativi e misura di performance

Dato un concetto c, gli esempi positivi per gli altri concetti sono esempi negativi per c. Di conseguenza, quando tolgo un esempio di un concetto c nel ciclo di covering rimuovo anche degli esempi negativi per gli altri concetti, rischiando di generare regole apprese in seguito troppo generali per gli altri concetti, che quindi ci sia la possibilità che coprano esempi NEGATIVI nel training set. Questo problema è risolto dal fatto che le regole sono valutate in ordine, per cui anche se le ultime regole sono molto generali, non è un problema perché le regole precedenti intercettano gli esempi.

Come misura di performance, in APPRENDI_UN_ANTECEDENTE si usa l’Entropia, ed essa è pari a:

−∑((|S_j|/|S|)log₂(P(c_j))), dove S è l’insieme degli esempi coperti dall’antecedente, c₁...c_k sono le classi e S₁...S_k gli esempi di S che appartengono alla classe j. L’entropia viene calcolata stimando le probabilità delle classi con la frequenza relativa (cardinalità di S_j fratto la probabilità della classe j).

Esempio pratico

Esempio: consideriamo nuovamente l’esempio relativo alle giornate adatte a giocare a tennis, in cui tutti gli attributi sono discreti e applichiamo l’algoritmo. Partiamo dalla prima chiamata di APPRENDI_UN_ANTECEDENTE, inizializzando beam l’insieme con l’antecedente vuoto e best_ant con l’antecedente vuoto. Successivamente specializzo gli antecedenti di beam, prendendoli e tutti specializzandoli in tutti i modi.

Nello specifico, dal momento che l’antecedente è l’insieme vuoto, i vincoli che posso aggiungere sono tutti quelli nella forma attributo = valore (outlook=sunny, outlook=overcast, outlook=rain, ecc.). A questo punto valuto le performance, mediante il calcolo dell’entropia dell’insieme di esempi coperti da questi antecedenti. Per esempio, nel caso di outlook=sunny, abbiamo 2 esempi positivi e 3 negativi (tabella precedente), per cui l’entropia vale 0.97.

Per outlook=overcast, abbiamo esempi provenienti solo dalla classe positiva (D5, D6, D7, D8), per cui avrò l’entropia pari a 0. Si osserva che l’attributo con il valore dell’entropia più basso è proprio quest’ultimo, mentre tutti gli altri hanno valori più alti. A questo punto aggiorno il best_ant, assegnandogli outlook=overcast, e il beam, scegliendo una dimensione pari a 2 e mettendo i due antecendenti migliori, quindi outlook=overcast e humid=normal.

Successivamente procedo con una nuova iterazione, in cui Nuovo_beam sarà dato dall’aggiunta agli antecedenti precedenti di un’altra condizione. Nel nostro caso, per outlook=overcast, dovrò aggiungere le condizioni per tutti gli attributi eccetto outlook (tempo=hot, tempo=mild, ecc.). In maniera analoga procedo anche per l’attributo humid=normal. A questo punto si osserva che calcolando le performance di ciascun antecedente, l’entropia è pari a 0 in ogni caso, perché outlook=overcast identificava già un insieme uniforme, per cui se aggiungo un'altra condizione vado a restringere tale insieme (che rimane comunque uniforme).

Invece, nel caso degli antecedenti che hanno humid=normal, abbiamo valori d’entropia diversi. A questo punto mi chiedo se debba aggiornare il migliore antecedente (NO, perché non ho trovato degli antecedenti con una misura di performance più alta di quella di outlook=overcast). In questo caso aggiorno solo il Beam, tenendo i due antecedenti con le performance migliori.