Algoritmo CN2

El algoritmo de inducción CN2 es un algoritmo de aprendizaje para la inducción de reglas . ^[1] Está diseñado para funcionar incluso cuando los datos de entrenamiento son imperfectos. Se basa en ideas del algoritmo AQ y del algoritmo ID3 . Como consecuencia, crea un conjunto de reglas como el creado por AQ pero es capaz de manejar datos ruidosos como ID3.

Para generar una lista de reglas de clasificación, se debe proporcionar al algoritmo un conjunto de ejemplos, TrainingSet, que ya se han clasificado. Se predefine un conjunto de condiciones, SimpleConditionSet, que se pueden aplicar, solas o en combinación, a cualquier conjunto de ejemplos para su uso en la clasificación.

rutina CN2(Conjunto de entrenamiento)
   Deje que la ClassificationRuleList esté vacía
   repetir
      deje que BestConditionExpression sea Find_BestConditionExpression(TrainingSet)
      Si BestConditionExpression no es nula
         entonces
            deje que TrainingSubset sean los ejemplos cubiertos por BestConditionExpression
            eliminar del TrainingSet los ejemplos del TrainingSubset
            Sea MostCommonClass la clase de ejemplos más común en TrainingSubset
            añadir a ClassificationRuleList la regla
               'si ' es la BestConditionExpression ' entonces la clase es ' la MostCommonClass
   hasta que el TrainingSet esté vacío o la BestConditionExpression sea nula
devuelve la ClassificationRuleList

rutina Find_BestConditionExpression(ConjuntoDeEntrenamiento)
   Deje que ConditionalExpressionSet esté vacío
   Deje que BestConditionExpression sea nula
   repetir
      sea ​​TrialConditionalExpressionSet el conjunto de expresiones condicionales,
         {x e y donde x pertenece al ConditionalExpressionSet e y pertenece al SimpleConditionSet}.
      eliminar todas las fórmulas en TrialConditionalExpressionSet que estén en ConditionalExpressionSet (es decir,
          los no especializados) o nulos (por ejemplo, big = y y big = n)
      para cada expresión, F, en el TrialConditionalExpressionSet
         si
            F es estadísticamente significativo
               y F es mejor que BestConditionExpression
               por criterios definidos por el usuario cuando se prueba en el conjunto de entrenamiento
            entonces
               Reemplace el valor actual de BestConditionExpression por F
      mientras que el número de expresiones en TrialConditionalExpressionSet > máximo definido por el usuario
         eliminar la peor expresión del TrialConditionalExpressionSet
      deje que ConditionalExpressionSet sea TrialConditionalExpressionSet
   hasta que el ConditionalExpressionSet esté vacío
devuelve la BestConditionExpression

• Descripción del algoritmo CN2