Introducción a Subdue

En esta sección se presenta brevemente los conceptos en que se basan los sistemas Subdue y SubdueCL.

Representación de Conocimiento:

• En un sistema basado en grafos, el algoritmo de aprendizaje utiliza grafos como representación de conocimiento.
• Esto significa que la fase de preparación de datos incluye una transformación de los datos a un formato de grafo.

Espacio de Búsqueda:

• El espacio de búsqueda el algoritmo basado en grafos consiste en todos los sub-grafos que se pueden derivar a partir del grafo de entrada.
• Esto quiere decir que el espacio de búsqueda es exponencial
• de la misma manera que es el tiempo de ejecución de estos algoritmos
• al menos que se restrinjan de alguna manera para que corran en tiempo polinomial

Criterio de Evaluación:

• Una parte muy importante del algoritmo de minería de datos es el criterio de evaluación.
• Este criterio se utiliza para determinar cuales subgrafos del espacio de búsqueda son relevantes y pueden ser considerados como parte de los resultados.
• El método basado en grafos Subdue utiliza el principio de longitud de descripción mínima (MDL) para evaluar los subgrafos descubiertos.
• El principio MDL dice que la mejor descripción del conjunto de datos es aquella que minimiza la longitud de la descripción de todo el conjunto de datos.
• En el método basado en grafos, el principio MDL se utiliza para determinar que tan bien un grafo comprime al grafo de entrada.
• De esta manera, todos los subgrafos que se generan durante el proceso de búsqueda se evaluan de acuerdo al principio MDL y los mejores subgrafos se eligen como parte del resultado.