Exploration de données - Classification basée sur des règles

Règles IF-THEN

Le classificateur basé sur des règles utilise un ensemble de règles IF-THEN pour la classification. Nous pouvons exprimer une règle dans ce qui suit à partir de -

SI condition ALORS conclusion

Considérons une règle R1,

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

Points to remember −

  • La partie IF de la règle est appelée rule antecedent ou precondition.

  • La partie ALORS de la règle est appelée rule consequent.

  • La partie antérieure de la condition consiste en un ou plusieurs tests d'attributs et ces tests sont logiquement AND.

  • La partie conséquente consiste en la prédiction de classe.

Note - On peut aussi écrire la règle R1 comme suit -

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

Si la condition est vraie pour un tuple donné, alors l'antécédent est satisfait.

Extraction de règles

Ici, nous allons apprendre à construire un classificateur basé sur des règles en extrayant des règles IF-THEN à partir d'un arbre de décision.

Points to remember −

Pour extraire une règle d'un arbre de décision -

  • Une règle est créée pour chaque chemin de la racine au nœud feuille.

  • Pour former un antécédent de règle, chaque critère de fractionnement est logiquement ANDé.

  • Le nœud feuille contient la prédiction de classe, formant la règle conséquente.

Induction de règle à l'aide de l'algorithme de couverture séquentielle

L'algorithme de couverture séquentielle peut être utilisé pour extraire les règles IF-THEN des données d'apprentissage. Nous n'avons pas besoin de générer d'abord un arbre de décision. Dans cet algorithme, chaque règle pour une classe donnée couvre de nombreux tuples de cette classe.

Certains des algorithmes de couverture séquentiels sont AQ, CN2 et RIPPER. Selon la stratégie générale, les règles sont apprises une à la fois. Pour chaque fois que les règles sont apprises, un tuple couvert par la règle est supprimé et le processus se poursuit pour le reste des tuples. En effet, le chemin vers chaque feuille dans un arbre de décision correspond à une règle.

Note - L'induction d'arbre de décision peut être considérée comme l'apprentissage d'un ensemble de règles simultanément.

Ce qui suit est l'algorithme d'apprentissage séquentiel dans lequel les règles sont apprises pour une classe à la fois. Lors de l'apprentissage d'une règle à partir d'une classe Ci, nous voulons que la règle couvre tous les tuples de la classe C uniquement et aucun tuple ne forme une autre 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;

Élagage de règle

La règle est élaguée pour la raison suivante -

  • L'évaluation de la qualité est effectuée sur l'ensemble original de données d'entraînement. La règle peut bien fonctionner sur les données d'entraînement, mais moins bien sur les données suivantes. C'est pourquoi la taille de règle est requise.

  • La règle est élaguée en supprimant la conjonction. La règle R est élaguée, si la version élaguée de R a une qualité supérieure à ce qui a été évalué sur un ensemble indépendant de tuples.

FOIL est l'une des méthodes simples et efficaces d'élagage des règles. Pour une règle R donnée,

FOIL_Prune = pos - nég / pos + nég

où pos et neg sont le nombre de tuples positifs couverts par R, respectivement.

Note- Cette valeur augmentera avec la précision de R sur l'ensemble d'élagage. Par conséquent, si la valeur FOIL_Prune est plus élevée pour la version élaguée de R, alors nous élaguons R.