Scopo dell'algoritmo e' la costruzione automatica di regole di forma if-then che possano essere utilizzate per classificare un insieme di oggetti in base al valore di un gruppo definito di attributi.
Gli esempi sono espressi in forma di tuple di attributi fissati, dove
uno di questi rappresenta il valore della classificazione per l'istanza
relativa.
Le regole vengono prodotte in fasi distinte di elaborazione, dove in
ognuna di queste viene considerato un solo valore dell'attributo di classificazione,
separando gli esempi in positivi e negativi in base al valore di classificazione
considerato.
L'algoritmo produce una di queste regole ad ogni iterazione, costruendola
dalla regola con premessa nulla ed aggiungendo sequenzialmente vincoli
di tipo attributo = valore, fino ad esaurire gli attributi possibili.
La scelta del vincolo da introdurre viene effettuata massimizzando
la stima dell'accuratezza della classificazione in funzione delle possibili
estensioni alla regola.
Piu' precisamente, indicando con n+(c) il numero di
esempi positivi compatibili con la regola c, e con n(c) il
numero di esempi totali anch'essi compatibili con la regola c, si
definisce accuratezza di classificazione della regola c la seguente quantita':
n+ + 1
dove N corrisponde al numero di classi del problema.A(c) = p (+|c ) = ______________n(c) + N
La ricerca delle possibili estensioni della regola considerata viene effettuata con un metodo denominato "beam-search", che, ad ogni passo, considera le estensioni delle k migliori soluzioni parziali, individuate fino al passo precedente. Questa metodo estende l'orizzonte rispetto ad un approccio "hill climbing", evitando l'esplosione combinatoria di una ricerca in ampiezza completa.
Dopo aver ottenuto un regola, vengono rimossi gli esempi coperti positivamente e il procedimento viene rieseguito, finche' la regole ottenute non presentano piu' rilevanza statistica rispetto al problema di classificazione.