Data mining - Classificazione basata su regole

IF-THEN Regole

Il classificatore basato su regole fa uso di un insieme di regole IF-THEN per la classificazione. Possiamo esprimere una regola nel seguito da:

SE condizione ALLORA conclusione

Consideriamo una regola R1,

R1: IF age = youth AND student = yes 
   THEN buy_computer = yes

Points to remember −

Viene chiamata la parte IF della regola rule antecedent o precondition.
Viene chiamata la parte ALLORA della regola rule consequent.
La parte antecedente la condizione consiste in uno o più test di attributi e questi test sono logicamente AND.
La parte conseguente consiste nella previsione della classe.

Note - Possiamo anche scrivere la regola R1 come segue -

R1: (age = youth) ^ (student = yes))(buys computer = yes)

Se la condizione è vera per una data tupla, l'antecedente è soddisfatto.

Estrazione delle regole

Qui impareremo come costruire un classificatore basato su regole estraendo le regole IF-THEN da un albero decisionale.

Points to remember −

Per estrarre una regola da un albero decisionale:

Viene creata una regola per ogni percorso dalla radice al nodo foglia.
Per formare una regola antecedente, ogni criterio di divisione è logicamente AND.
Il nodo foglia contiene la previsione della classe, formando la regola conseguente.

Induzione di regole utilizzando l'algoritmo di copertura sequenziale

L'algoritmo di copertura sequenziale può essere utilizzato per estrarre le regole IF-THEN dai dati di addestramento. Non è necessario generare prima un albero decisionale. In questo algoritmo, ogni regola per una data classe copre molte delle tuple di quella classe.

Alcuni degli algoritmi di copertura sequenziali sono AQ, CN2 e RIPPER. Secondo la strategia generale, le regole vengono apprese una alla volta. Ogni volta che le regole vengono apprese, una tupla coperta dalla regola viene rimossa e il processo continua per il resto delle tuple. Questo perché il percorso di ciascuna foglia in un albero decisionale corrisponde a una regola.

Note - L'induzione dell'albero decisionale può essere considerata come l'apprendimento simultaneo di un insieme di regole.

Quanto segue è l'algoritmo di apprendimento sequenziale in cui le regole vengono apprese per una classe alla volta. Quando si impara una regola da una classe Ci, vogliamo che la regola copra tutte le tuple solo della classe C e nessuna tupla da qualsiasi altra classe.

Algorithm: Sequential Covering

Input: 
D, a data set class-labeled tuples,
Att_vals, the set of all attributes and their possible values.

Output:  A Set of IF-THEN rules.
Method:
Rule_set={ }; // initial set of rules learned is empty

for each class c do
   
   repeat
      Rule = Learn_One_Rule(D, Att_valls, c);
      remove tuples covered by Rule form D;
   until termination condition;
   
   Rule_set=Rule_set+Rule; // add a new rule to rule-set
end for
return Rule_Set;

Regola di potatura

La regola è potata è dovuta al seguente motivo:

La valutazione della qualità viene effettuata sulla serie originale di dati di allenamento. La regola può funzionare bene sui dati di addestramento ma meno sui dati successivi. Ecco perché è richiesta la regola di potatura.
La regola viene potata rimuovendo il congiunto. La regola R viene eliminata, se la versione ridotta di R ha una qualità maggiore di quella valutata su un insieme indipendente di tuple.

FOIL è uno dei metodi semplici ed efficaci per la potatura a regola. Per una data regola R,

FOIL_Prune = pos - neg / pos + neg

dove pos e neg è il numero di tuple positive coperte da R, rispettivamente.

Note- Questo valore aumenterà con la precisione di R sul set di potatura. Quindi, se il valore FOIL_Prune è più alto per la versione ridotta di R, allora potiamo R.