Induction of Decision Trees based on Generalized Graph Queries

• Published in: arXiv.org 2017-08
• Main Authors: Almagro-Blanco, Pedro, Sancho-Caparrini, Fernando
• Format: Article
• Language: English
• Subjects: Algorithms; Complexity; Data mining; Decision trees; Machine learning; Pattern analysis; Pattern matching; Queries
• ISSN: 2331-8422

Usually, decision tree induction algorithms are limited to work with non relational data. Given a record, they do not take into account other objects attributes even though they can provide valuable information for the learning task. In this paper we present GGQ-ID3, a multi-relational decision tree learning algorithm that uses Generalized Graph Queries (GGQ) as predicates in the decision nodes. GGQs allow to express complex patterns (including cycles) and they can be refined step-by-step. Also, they can evaluate structures (not only single records) and perform Regular Pattern Matching. GGQ are built dynamically (pattern mining) during the GGQ-ID3 tree construction process. We will show how to use GGQ-ID3 to perform multi-relational machine learning keeping complexity under control. Finally, some real examples of automatically obtained classification trees and semantic patterns are shown. --- Normalmente, los algoritmos de inducción de árboles de decisión trabajan con datos no relacionales. Dado un registro, no tienen en cuenta los atributos de otros objetos a pesar de que éstos pueden proporcionar información útil para la tarea de aprendizaje. En este artículo presentamos GGQ-ID3, un algoritmo de aprendizaje de árboles de decisiones multi-relacional que utiliza Generalized Graph Queries (GGQ) como predicados en los nodos de decisión. Los GGQs permiten expresar patrones complejos (incluyendo ciclos) y pueden ser refinados paso a paso. Además, pueden evaluar estructuras (no solo registros) y llevar a cabo Regular Pattern Matching. En GGQ-ID3, los GGQ son construidos dinámicamente (pattern mining) durante el proceso de construcción del árbol. Además, se muestran algunos ejemplos reales de árboles de clasificación multi-relacionales y patrones semánticos obtenidos automáticamente.