Induction of Decision Trees based on Generalized Graph Queries

Induction of Decision Trees based on Generalized Graph Queries Pedro Almagro-Blanco and Fernando Sancho-Caparrini October 9, 2018 1 Introduction A decision tree is a classification (and regression) model that, based on the characteristics of a given object, and applying a series of rules, is able to classify it (or return a continuous value in the case of regression). The induction of decision trees from a set of previously classified objects is one of the most popular machine learning models due, among other things, to the low computational demand in their training and the interpretability of their results, so it is a representative white box model. ID3 algorithm presented by R. Quinlan in 1983 for the automatic construction of decision trees from a training set of objects described through a collection of properties. Each object in the training set belongs to a class (usually represented by the value of its target attribute) of a set of mutually exclusive classes. ID3 has been one of the most used techniques in machine learning with applications to tasks as diverse as epidemics prediction, robot control, and automatic classification of clients in banks or insurance entities [19, 18, 7]. The main goal of this work is to offer a methodology that allows to carry out machine learning tasks using decision trees on multi-relational graph data. In this context, the number of possible properties of each object goes far beyond those that it has directly associated, since the properties of the elements that are related to it can also be considered attributes of the object, and even the topological structure formed by the objects in their environment and the various measures that can be taken from the graph structure could be considered as additional attributes. With this objective, we will analyse different techniques that allow automatic induction of decision trees from graph data and we will present our proposal, GGQ-ID3, that aims to provide a framework to classify substructures in a graph, from simple nodes and edges, to larger paths and subgraphs, making use of Generalized Graph Query (GGQ) [1]. This paper is structured as follows: we will start reviewing different techniques of induction of relational decision trees; then, we present our proposal based on the use of Generalized Graph Queries as evaluation tool; once our proposal is presented, we will show some examples of its application; and finally we present some conclusions and future work lines. 1 2 Related Works This section does not pretend to be an exhaustive compilation of the related works that can be found in the literature, but a selection showing their predictive capacity, computational efficiency, or widespread use. Inductive Logic Programming (ILP) [16] is a machine learning area that uses Logic Programming to consistently represent examples, knowledge bases, and hypotheses. Although ILP itself (without proper transformation of the relationships between data to logical predicates) does not allow the generation of relational decision trees, it does allow automatic generation of logical decision trees that can be considered the basis of one of the most important relational decision tree algorithms, Multi-Relational Decision Tree Learning (MRDTL). ILP provides interpretability, but is inefficient when working with complex databases [15]. ALogical Decision Tree [3] is a binary decision tree in which all the tests of the internal nodes are expressed as conjunction of literals of a prefixed First Order Language. The Top-Down Induction of Logical Decision Trees (TILDE) algorithm builds logical decision trees from a set of classified examples [4]. The only difference between this algorithm and ID3 (without taking into account the possible optimizations implemented in C4.5 or others) is found in the tests carried out in each node of the tree. Following the rise of the ILP, some major breakthroughs were made in multi-relational data mining [8, 21]. Yin Xiaoxin [20] designed CrossMine, a multi-relational classification model that merges ILP and relational databases, improving efficiency in this type of tasks through virtual joins [11]. Multi-Relational Decision Tree Learning (MRDTL) is a multi-relational machine learning algorithm [10] based on the ideas of Knobles et al. [9] that works with Selection Graphs. A Selection Graph is a graph representation of a SQL query that selects records which match some constraints expressed by paths connected with them. In order to construct complex selection graphs from an initial one, some atomic operations allow to refine the queries. In addition, in order to be used as tests for ID3-like processes, it must be possible to obtain the complementary selection graph in each case. Essentially, MRDTL works as ID3, but making use of selection graphs as binary attributes in each decision node of the tree. The specification of this method is oriented to relational databases. Graph-Based Induction (GBI) is a data mining technique to perform network motifs mining from labelled and directed graphs through the union of pairs of connected nodes [14]. It is very efficient because it uses a greedy technique. Tree Graph-Based Induction Decision (DT-GBI) is a decision tree construction algorithm to classify graphs using GBI principles. In DT-GBI the attributes (called patterns or substructures) are generated during the execution of the algorithm [5], adding feature extraction capacity [13]. It should be noted that, unlike our proposal or MRDTL, DT-GBI constructs decision trees to classify complete graphs, not general subgraphs (as is the case of GGQ-ID3) or nodes (as is the case of MRDTL). 2 3 Generalized Graph Queries Generalized Graph Query, on which the multi-relational decision tree induction model GGQ-ID3 is based, is briefly presented now. A more comprehensive description of this framework can be found in [1]. AGeneralized Graph (which will also be called Property Graph) is a concept that covers several variants of graphs that can be found in the literature. Definition 1. AGeneralized Graph is a tuple G= (V, E, µ)where: •Vand Eare sets, called, respectively, set of nodes and set of edges of G. •µis a relation (usually functional, but not necessarily) that associates each node or edge in the graph with a set of properties, that is, µ: (V∪E)×R→ S, where Rrepresents the set of possible keys for available properties, and Sthe set of possible values associated. Usually, for each α∈Rand x∈V∪E, we write α(x) = µ(x, α). In addition, we require the existence of a special key for the edges of the graph, called incidences and denote by γ, which associates to each edge of the graph a tuple, ordered or not, of vertices of the graph. Generalized Graph Query allows structural and semantic, accurate, optimal, and based on a type of Regular Pattern Matching queries, associating edges of the pattern with paths on the graph that meet the constraints imposed, and allowing cycles. Let Lbe a First Order Language with equality using a collection containing all the functions of µand constants associated with each element of the graph as non logical symbols (and some additional symbols, for example metrics defined on the elements of the graph). Constructing in the usual way the set of terms of the language and the set of formulas, FORM(L) (which we will call predicates), we can define queries on generalized graphs: Definition 2. AGeneralized Graph Query (GGQ) over Lis a binary generalized graph, Q= (VQ, EQ, µQ), where exist αand θ, properties in µQ, such that: •α:VQ∪EQ→ {+,−} total. •θ:VQ∪EQ→FORM(L)associates a binary predicate, θx, to every element xof VQ∪EQ. The second parameter of θis used to express conditions of membership on subgraphs and the first one will receive elements of the corresponding type to which it is associated (nodes or edges/paths). Given a GGQ, x+, respectively x−, will indicate that α(x) = +, respectively α(x) = −, and V+ Q/V − Q(respectively, E+ Q/E− Q) the set of positive/negative nodes (respectively, edges). If for an element, θxis not explicitly defined, we assume it to be a tautology (generally denoted by T). As we will see below, positive elements of the pattern represent elements verifying the associated predicates that must be present in the graph, while negative ones represent elements that should not be present in the graph. In order to express the necessary conditions that define the application of a GGQ on a graph, the following notations are useful: 3 Definition 3. Given a GGQ, Q= (VQ, EQ, µQ), the set of Q-predicates associated to Qis: 1. For each edge, e∈EQ, we define: Qeo(v, S) = ∃ρ∈ Po v(G)θe(ρ, S)∧θeo(ρo, S)∧θei(ρi, S) Qei(v, S) = ∃ρ∈ Pi v(G)θe(ρ, S)∧θeo(ρo, S)∧θei(ρi, S) In general, we will write Qe∗(v, S), where ∗ ∈ {o, i}, and we will denote: Q+ e∗=Qe∗, Q− e∗=¬Qe∗ 2. For each node, n∈VQ, we define: Qn(S) = ∃v∈V ^ e∈γo(n) Qα(e) eo(v, S)∧^ e∈γi(n) Qα(e) ei(v, S)  =∃v∈V ^ e∈γ∗(n) Qα(e) e∗(v, S)  That can be written generally as: Qn(S) = ∃v∈V ^ e∈γ(n) Qα(e) e(v, S)  In addition, we denote: Q+ n=Qn, Q− n=¬Qn Where eo/eirepresents the source/target node of the edge e,Po v(G)/Pi v(G) represents the paths in Gstarting/ending in node v. From these notations, we can formally define when a subgraph matches a given GGQ: Definition 4. Given a subgraph Sof a property graph, G= (V, E, µ), and a Generalized Graph Query, Q= (VQ, EQ, µQ), both over a language L, we say that Smatches Q,SQ, if it is verified: Q(S) = ^ n∈VQ Qα(n) n(S) Otherwise, we will write: S2Q. In order to obtain controlled query generation methods, refinements can be defined in order to modify a GGQ by unit steps. Given two GGQ, Q1, Q2, we say that Q1refine Q2in a graph G,Q1GQ2, if for all S⊆Gthat SQ1, then SQ2. Definition 5. Given Q∈GGQ,R⊆GGQ is a refinement set of Qin Gif: 1. ∀Q0∈R(Q0GQ) 4 2. ∀S⊆G(SQ⇒ ∃!Q0∈R(SQ0)) In what follows, given Q,ClW Qis the graph obtained from Qby duplicating the nodes in W⊆VQ(with the incident edges if they have). Following [1], we can prove that the following sets of GGQ are refinements of Q: •Add new node: if m /∈VQ, then Q+{m}: Q1= (VQ∪ {m}, EQ, αQ∪(m, +), θQ∪(m, T)) Q2= (VQ∪ {m}, EQ, αQ∪(m, −), θQ∪(m, T)) •Add new edge between positive nodes: if n, m ∈V+ Q, then Q+ {n+e∗ −→ m+}(∗ ∈ {+,−}) (where Q0=Cl{n,m} Q): Q1= (VQ0, EQ0∪ {n+e∗ −→ m+}, θQ0∪(e, T)) Q2= (VQ0, EQ0∪ {n+e∗ −→ m−}, θQ0∪(e, T)) Q3= (VQ0, EQ0∪ {n−e∗ −→ m+}, θQ0∪(e, T)) Q4= (VQ0, EQ0∪ {n−e∗ −→ m−}, θQ0∪(e, T)) •Add predicate to positive edge connecting positive nodes: if n, m ∈V+ Q, with n+e+ −→ m+, and ϕ∈FORM, then Q+{n+e∧ϕ −→ m+} (where Q0=Cl{n,m} Q): Q1= (VQ0, EQ0∪ {n+e0 −→ m+}, θQ0∪(e0, θe∧ϕ)) Q2= (VQ0, EQ0∪ {n+e0 −→ m−}, θQ0∪(e0, θe∧ϕ)) Q3= (VQ0, EQ0∪ {n−e0 −→ m+}, θQ0∪(e0, θe∧ϕ)) Q4= (VQ0, EQ0∪ {n−e0 −→ m−}, θQ0∪(e0, θe∧ϕ)) •Add predicate to positive node with positive environment: if n∈V+ Q,NQ(n)⊆V+ Q, and ϕ∈FORM, then Q+{n∧ϕ}: {Qσ= (VQ0, EQ0, αQ0∪σ, θQ0∪(n0, θn∧ϕ)) : σ∈ {+,−}NQ(n)} where Q0=ClNQ(n) Q, and {+,−}NQ(n)is the set of all possible sign assignations to the elements in NQ(n) (the neighborhood of nin Q). It is an open problem how to automatically obtain a complementary GGQ of a given one. Refinements cover this gap and allow, for example, the construction of an embedded partitions tree with nodes labelled as follows (Fig. 1): •The root node is labelled Q0(any initial GGQ). •If a tree node is labelled Q, and R= (Q1, . . . , Qn) is a refinement set of Q, then its child nodes are labelled with the Relements. Note that the construction of this tree completely depends on the refinement chosen in each branch and the initial GGQ. 5 Figure 1: Refinement tree 4 GGQ-ID3 GGQ-ID3 is an adaptation of ID3 algorithm to create decision trees to classify structures immersed in a property graph using Generalized Graph Query framework as test tools in each decision node of the decision tree. Similarly to ID3, our proposal, using refinements, will look for GGQs that best classify the examples of the training set along the tree construction (feature extraction). For that, in each internal node of the tree a discrimination will be performed between the structures of a graph Gthat fulfil each GGQ resulting from a refinement. As usual, the measure of impurity used is a hyper-parameter of the algorithm. Although GGQ-ID3 has a very similar structure to other algorithms for construction of decision trees, it presents the novelty of receiving structures (subgraphs) immersed in a property graph as training set. By using appropriate predicates, GGQs constructed by the algorithm can not only evaluate properties of the structure under evaluation, but also properties of any element (subgraph) in its environment. The complete training set, L, will consist of pairs of the form (S, value), where Sis a subgraph of Gand value is its associated output value. Consequently, each node nof the decision tree will have associated the following structures: • Ln={(S1, y1), ..., (SN, yN)}⊆L, a subset of the training set. •Qn= (VQn, EQn, αQn, θQn), A GGQ verified by all subgraphs in Ln. Algorithm 1 formally represents GGQ-ID3. Note that the set of available refinements, REFS, to extend the GGQ in each step, as well as the stopping condition and refinement selection criteria, remain as free parameters of the model. In a typical learning process, the input of the algorithm will be: •G= (V, E, µ), graph in which the structures to be classified are immersed. • L ={(S1, y1), ..., (SN, yN)}, set of pairs (Si, yi) where Si⊆Grepresents a subgraph and yiis its associated output value. •Q0= (VQ, EQ, µQ), initial GGQ (usually a GGQ with the largest common structure in S1, ..., SN). 6 Algorithm 1 GGQ-ID3(G, Q, L, REFS) 1: Create a Root node for the tree 2: if Stop criteria is reached then 3: return The single-node tree Root, with most frequent label in L. 4: else 5: (Q1, .., Qk) = Optimal Refinement(G, Q, L, REFS) 6: L1={(S, y)∈ L :SQ1}, ..., Lk={(S, y)∈ L :SQk} 7: Add knew tree branches below Root with values GGQID3(G, Qi,Li, REFS) for every 1 ≤i≤k. 8: end if •REFS, available refinements set. The algorithm follows the usual procedure in ID3. It begins by creating a tree containing a single node (root node) to which all the Lobjects and Q0are associated. If nis the node of the decision tree which we are working with, the algorithm evaluates which refinement divides Lnbetter and it will be chosen to be applied to Qn. Next, as many branches from nas GGQs are in the chosen refinement will be created and each pair of Lnwill be transmitted through the corresponding branch. Each child node of nwill inherit the GGQ resulting from the refinement and proceed to search (if the stop condition is not reached) the best refinement for the new GGQ. Each branch of the tree will receive a set of objects and a GGQ that is verified by all of them. If the stop condition is met, the node will become a leaf node associated with the corresponding class. This process is repeated recursively. Decision trees obtained in most automatic procedures divide the data into binary complementary subsets in a recursive way [17], but in the multi-relational case the production of complementary patterns of this type is not straightforward. This is the reason a set of refinements that generate complementary GGQs, but not necessarily binary, were presented. 5 Some Examples Next we present an example of GGQ-ID3 algorithm application on a small property graph as a demonstration. The available refinements REFS will be those seen in the previous section, we will use the most restrictive stop condition (all the pairs in the current node belong to the same class), and the Information Gain [12] will be used as impurity measure. We will work with the social graph shown in Figure 2, which represents some marital connections between users and information related to photographs publication. There are nodes of types user and photo, and edges of types wife, husband,publish and likes. In this case, Lis not extended with topological measures of the graph. In addition, user nodes have gender property with value F(female) or M(male). photo nodes have the value None associated to gender property. Although GGQ-ID3 algorithm is able to construct decision trees to classify any structure (subgraph), in order to show a simple example, we approach a problem of classifying nodes, specifically trying to predict the gender of nodes. 7 Figure 2: Social Graph In order to make the exposition clearer and to avoid confusion, the nodes belonging to the training set will be called objects, and we will use nodes for the nodes of the decision tree under construction. GGQ-ID3 algorithm constructs the decision tree in Figure 3 (positive nodes/ edges are marked in black and negative ones in red) that correctly classify all nodes from Figure 2 according to their gender: M,For None. Next indications about the construction follow the representation shown in Figure 3. The initial training set, L, is formed by all pairs of nodes and their corresponding gender. Initial GGQ, Q0, is composed of two positive nodes, one with a predicate that requires belonging to the subgraph under evaluation (v∈S) and another with the opposite condition (V /∈S). As previously mentioned, usually the initial GGQ will correspond to the largest common substructure in the subgraphs to be classified, in this case the largest common structure is composed of a single node with no restrictions. In addition, and for reasons of efficiency, in each step of the algorithm an isolated positive node will be created with a predicate that requires non belonging to the subgraph under evaluation (v /∈S) if there is no such isolated node. If the subgraph under evaluation does not cover all the nodes of the graph in which it is immersed (which is true in all the examples presented), adding a node of this type does not modify the meaning of the GGQ but allows to reach optimal GGQ easily. As a first step, the algorithm will analyse what refinement in REF S (and with what parameters) represents the highest impurity reduction, resulting in refinement +{e+ −→}, add edge between the only two existing nodes in Q0. Although refinement add edge generates a refinement of four elements, we consider only those that intervene in the classification process, removing those that transmit an empty set of objects. Because the subgraphs to classify are composed of a single object, this refinement evaluates the existence or not of an outgoing edge in this object. According to Figure 3, the right branch will transmit all objects with no outgoing relations. 8 Figure 3: GGQ Decision Tree (social graph) In this case, all photo objects of the data graph, that have None as gender, so this branch is associated with the output value None and becomes a leaf of the decision tree. The left branch will transmit all objects with an outgoing relation (in this case, all objects of the data graph of type user). As the values of gender are not homogeneous in this set, the algorithm must continue and a new refinement to this branch have to be applied. Here we have nodes that reflect male and female users with an outgoing edge. +{e∧{type=publish} −→ } refinement (add a new predicate to edge) produces the greatest information gain. The refinements applied to this node in the decision tree will discriminate which objects (of those with an outgoing edge) 9 [8] Yusuf Kavurucu, Pinar Senkul, and Ismail Hakki Toroslu. Confidence-based concept discovery in multi-relational data mining. [9] Arno J. Knobbe, Arno Siebes, Danil Van Der Wallen, and Syllogic B. V. Multi-relational decision tree induction. In In Proceedings of PKDD’ 99, Prague, Czech Republic, Septembre, pages 378–383. Springer, 1999. [10] H´ector Ariel Leiva, Shashi Gadia, and Drena Dobbs. Mrdtl: A multirelational decision tree learning algorithm. In Proceedings of the 13th International Conference on Inductive Logic Programming (ILP 2003, pages 38–56. Springer-Verlag, 2002. [11] Juan Li. Improved multi-relational decision tree classification algorithm. [12] Thomas M. Mitchell. Machine Learning. McGraw-Hill, Inc., New York, NY, USA, 1 edition, 1997. [13] Phu Chien Nguyen, Kouzou Ohara, Akira Mogi, Hiroshi Motoda, and Takashi Washio. Constructing Decision Trees for Graph-Structured Data by Chunkingless Graph-Based Induction, pages 390–399. Springer Berlin Heidelberg, Berlin, Heidelberg, 2006. [14] Phu Chien Nguyen, Kouzou Ohara, Hiroshi Motoda, and Takashi Washio. Cl-GBI: A Novel Approach for Extracting Typical Patterns from Graph- Structured Data, pages 639–649. Springer Berlin Heidelberg, Berlin, Heidelberg, 2005. [15] Neelamadhab Padhy and Rasmita Panigrahi. Multi relational data mining approaches: A data mining technique. CoRR, abs/1211.3871, 2012. [16] Gordon Plotkin. Automatic methods of inductive inference. 1972. [17] J. Ross Quinlan. C4.5: Programs for Machine Learning. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 1993. [18] Marcos Salganicoff, Lyle H. Ungar, and Ruzena Bajcsy. Active learning for vision-based robot grasping. Machine Learning, 23(2):251–278, 1996. [19] Anand Takale. Constructing Predictive Models to Assess the Importance of Variables in Epidemiological Data Using A Genetic Algorithm System employing Decision Trees. PhD thesis, UNIVERSITY OF MINNESOTA, 2004. [20] Xiaoxin Yin, Jiawei Han, Jiong Yang, and Philip S. Yu. CrossMine: Efficient Classification Across Multiple Database Relations, pages 172–195. Springer Berlin Heidelberg, Berlin, Heidelberg, 2006. [21] Wei Zhang. Multi-relational data mining based on higher-order inductive logic programming. 2013 Fourth Global Congress on Intelligent Systems, 2:453–458, 2009. 16 Inducci´on de ´ Arboles de Decisi´on basados en Generalized Graph Queries Pedro Almagro-Blanco and Fernando Sancho-Caparrini 9 de octubre de 2018 1. Introducci´on Un ´arbol de decisi´on es un modelo de clasificaci´on (y regresi´on) que, a partir de las caracter´ısticas de un objeto dado, y aplicando una serie de reglas, es capaz de asociar una clase a dicho objeto (o un valor continuo en el caso de regresi´on). La inducci´on de ´arboles de decisi´on a partir de un conjunto de objetos previamente clasificados es uno de los modelos de aprendizaje autom´atico m´as populares debido, entre otras cosas, a la baja demanda computacional en su entrenamiento y a la facilidad de interpretaci´on de sus resultados por parte de los humanos, por lo que se coloca como representante de los llamados modelos de caja blanca. El algoritmo ID3 fue ideado por R. Quinlan en 1983 [22] para crear ´arboles de decisi´on clasificadores a partir de un conjunto de datos conformado por una serie de objetos descritos a trav´es de una colecci´on de propiedades. Cada objeto del conjunto de entrenamiento pertenece a una clase (normalmente, representado por medio del valor del atributo target) de un conjunto de clases mutuamente excluyentes. ID3 ha sido una de las t´ecnicas m´as utilizadas de aprendizaje autom´atico, con aplicaciones a tareas tan diversas como predicci´on de epidemias, control de robots o clasificaci´on autom´atica de clientes en bancos o entidades aseguradoras [25, 24, 10]. El objetivo de este trabajo es ofrecer una metodolog´ıa que permita llevar a cabo tareas de aprendizaje autom´atico haciendo uso de ´arboles de decisi´on sobre datos en forma de grafo. En este contexto, el n´umero de posibles propiedades de cada objeto va mucho m´as all´a de aquellas que tiene asociadas directamente, ya que las propiedades de los elementos que se relacionan con ´el tambi´en pueden ser considerados atributos del mismo, es m´as, incluso la estructura topol´ogica que forman los objetos de su entorno y las diversas medidas que se pueden tomar de esta estructura podr´ıan ser consideradas como atributos. Con este objetivo, analizaremos diferentes t´ecnicas que permiten la construcci´on autom´atica de ´arboles de decisi´on a partir de datos estructurados en forma de grafo y presentaremos nuestra propuesta, GGQ-ID3, que tiene como objetivo proporcionar un marco para clasificar subestructuras en un grafo, desde simples nodos y aristas, hasta caminos y subgrafos de mayor envergadura, haciendo uso del concepto de Generalized Graph Query (GGQ, para abreviar, a partir de ahora) [1]. Este art´ıculo se estructura de la siguiente manera: realizaremos un repaso por las diferentes t´ecnicas existentes de inducci´on de ´arboles de decisi´on relacionales (aquellos que trabajan sobre estructuras de datos en las que hay relaciones entre 1 sus elementos) y a continuaci´on daremos una serie de definiciones previas que nos permitir´an presentar nuestra propuesta basada en el uso de Generalized Graph Queries como herramienta de evaluaci´on en los nodos del ´arbol. Una vez planteada nuestra propuesta, mostraremos algunos ejemplos de aplicaci´on de la misma. Cerraremos el trabajo presentando algunas conclusiones y l´ıneas futuras que han ido surgiendo durante la ejecuci´on del mismo. 2. Trabajos Relacionados Este apartado no pretende ser una recopilaci´on exhaustiva de los trabajos relacionados que se pueden encontrar en la literatura, sino una selecci´on de aquellos que hemos encontrado m´as interesantes, bien sea por su capacidad de predicci´on, su eficiencia computacional, o porque han servido de base a otras t´ecnicas y trabajos relevantes. La Programaci´on L´ogica Inductiva (ILP) [21] es un ´area del aprendizaje autom´atico que utiliza fundamentos de Programaci´on L´ogica para representar de manera uniforme ejemplos, base de conocimientos, e hip´otesis. A pesar de que la ILP por s´ı misma (sin una transformaci´on adecuada de las relaciones entre datos a predicados l´ogicos) no permite generar ´arboles de decisi´on relacionales, s´ı permite generar de manera autom´atica ´arboles de decisi´on l´ogicos que pueden ser considerados la base de uno de los algoritmos m´as importantes de generaci´on autom´atica de ´arboles de decisi´on, como es el algoritmo Multi-Relational Decision Tree Learning (MRDTL). La gran potencia que proporciona ILP en nuestro contexto es su interpretabilidad, pero su punto d´ebil radica en la ineficiencia para trabajar con bases de datos complejas [19]. Un ´ Arbol de Decisi´on L´ogico [3] es un ´arbol de decisi´on binario en el que que todos los test de los nodos internos se expresan como conjunci´on de literales de una L´ogica de Primer Orden prefijada. El algoritmo TILDE (Top-Down Induction of Logical Decision Trees) [3] construye ´arboles de decisi´on l´ogicos para clasificar instancias a partir de un conjunto de ejemplos clasificados, una base de conocimientos, y un lenguaje que indica qu´e tipo de preguntas est´an permitidas en el ´arbol [4]. La ´unica diferencia entre este algoritmo y el ID3 presentado por Quinlan (sin tener en cuenta las posibles optimizaciones implementadas en C4.5 u otros) se encuentra en los tests llevados a cabo en cada nodo del ´arbol. Tras el auge de la ILP se lograron algunos avances importantes en la miner´ıa de datos multi-relacional [11, 28]. Yin Xiaoxin [27] dise˜n´o CrossMine, un modelo de clasificaci´on multi-relacional que mezcla ILP y las bases de datos relacionales, mejorando la eficiencia en este tipo de tareas a trav´es de un m´etodo para realizar uniones virtuales de tablas de la base de datos [15]. Multi-Relational Decision Tree Learning (MRDTL) es un algoritmo para el aprendizaje de ´arboles de decisi´on multi-relacionales [14] basado en las ideas de Knobles et al. [13] que trabaja con el concepto de Grafo de Selecci´on (Selection Graph). Un grafo de selecci´on es una representaci´on en forma de grafo de una consulta SQL que selecciona registros que cumplan con una serie de restricciones expresadas en forma de estructuras con las que debe (o no debe) estar conectado el registro bajo evaluaci´on. Adem´as, los grafos de selecci´on permiten ser refinados usando un conjunto de operaciones at´omicas con el fin de construir grafos de selecci´on complejos a partir de un grafo de selecci´on inicial. Adem´as, para poder ser usados en un proceso similar a ID3, se debe poder obtener el grafo de 2 selecci´on complementario a uno dado. Esencialmente, MRDTL funciona como ID3, pero se caracteriza por hacer uso de grafos de selecci´on como atributos binarios en cada nodo de decisi´on del ´arbol. La especificaci´on de este m´etodo est´a orientada a bases de datos relacionales debido, en parte, a que en el tiempo en el que se present´o a´un no se hab´ıan desarrollado otro tipo de bases de datos m´as adecuadas para este tipo de tareas. Graph-Based Induction (GBI) es una t´ecnica de miner´ıa de datos que extrae patrones frecuentes (network motifs) de grafos etiquetados y dirigidos a trav´es de la uni´on de pares de nodos conectados [18] y que es muy eficiente debido a que utiliza una t´ecnica voraz. A partir de esta t´ecnica, Decisi´on Tree Graph-Based Induction (DT-GBI) es un algoritmo de construcci´on de ´arboles de decisi´on para clasificar grafos utilizando los principios de GBI. En DT-GBI los atributos (llamados patrones o subestructuras) son generados durante la ejecuci´on del algoritmo [7], por lo que DT-GBI es un generador de ´arboles de decisi´on con capacidad de construcci´on de atributos [17]. Hay que indicar que, a diferencia de nuestra propuesta o de MRDTL, DT-GBI construye ´arboles de decisi´on para clasificar grafos completos, y no subestructuras generales inmersas en ´el (como es el caso de GGQ-ID3) o nodos (como es el caso de MRDTL). A continuaci´on presentamos brevemente el concepto de Generalized Graph Query, base del modelo de generaci´on de ´arboles de decisi´on GGQ-ID3, se puede encontrar una descripci´on m´as amplia del mismo en [1]. 3. Generalized Graph Query El Grafo Generalizado (que a veces, y por extensi´on, tambi´en denominaremos Grafo con Propiedades) es un concepto que abarca diferentes variantes de grafos que se pueden encontrar en la literatura, tanto aquellos que sirven desde un punto de vista puramente matem´atico, como los que sirven de sustrato te´orico para las redes sem´anticas o bases de datos en grafo. Definici´on 1. Un Grafo Generalizado es una tupla G= (V, E, µ)donde: VyEson conjuntos, que llamaremos, respectivamente, conjunto de nodos yconjunto de aristas de G. µes una funci´on que asocia a cada nodo o arista en el grafo su conjunto de propiedades, es decir, µ: (V∪E)×R→S, donde Rrepresenta el conjunto de posibles claves para dichas propiedades, y Sel conjunto de posibles valores asociados a las mismas. Habitualmente, para cada α∈Ryx∈V∪E, escribiremos α(x) = µ(x, α). Adem´as, exigiremos la existencia de una clave destacada para las aristas del grafo, que llamaremos incidencias y denotaremos por γ, que asocia a cada arista del grafo una tupla, ordenada o no, de v´ertices del grafo. Las Generalized Graph Queries permiten llevar a cabo consultas estructurales y sem´anticas, exactas, ´optimas, y basadas en un tipo de Regular Pattern Matching que permite, adem´as de proyectar aristas del patr´on en caminos (no necesariamente aristas) que cumplan las restricciones impuestas, expresar restricciones m´as complejas sobre cada elemento del patr´on y realizar consultas que posean ciclos. 3 Si consideramos Lun Lenguaje de Primer Orden con igualdad que usa como s´ımbolos no l´ogicos una colecci´on que contiene todas las funciones de µjunto con constantes asociadas a cada elemento del grafo (y algunos s´ımbolos adicionales, por ejemplo para denotar m´etricas definidas sobre los elementos del grafo), y construimos de la forma usual el conjunto de t´erminos del lenguaje y el conjunto de f´ormulas, FORM(L) (que llamaremos predicados), podemos definir las consultas sobre grafos generalizados haciendo uso de las mismas estructuras como: Definici´on 2. Un Generalized Graph Query (GGQ) sobre Les un grafo generalizado, Q= (VQ, EQ, µQ), donde existen αyθ, propiedades destacadas en µQ, tales que: α:VQ∪EQ→ {+,−} total. θ:VQ∪EQ→FORM(L)asocia un predicado binario, θx, a cada elemento xde VQ∪EQ. Como veremos, la segunda entrada de estos predicados binarios se usar´a para hablar de condiciones de pertenencia sobre subgrafos de G(el grafo general sobre el que estamos evaluando las consultas), mientras que la primera esperar´a recibir como entrada elementos adecuados al tipo de elemento al que est´a asociado. Dado un GGQ en las condiciones anteriores, notaremos x+, respectivamente x−, para indicar que α(x) = +, respectivamente α(x) = −. Si para un elemento x,θxno est´a expl´ıcitamente definida, supondremos que θxes una tautolog´ıa, que podemos denotar en general por T. Intuitivamente los elementos positivos del patr´on representan elementos que deben estar presentes en el grafo sobre el que se realiza la consulta y que verifican los predicados asociados, mientras que los elementos negativos en el patr´on representan elementos que no pueden estar presentes en el grafo. Para poder expresar con m´as facilidad las condiciones necesarias que definen la aplicaci´on de un GGQ sobre un grafo, as´ı como los resultados que veremos m´as adelante, introducimos las notaciones: Definici´on 3. Dado Q= (VQ, EQ, µQ)un GGQ, el conjunto de Q-predicados asociados a Qes: 1. Para cada arista, e∈EQ: Qeo(v, S) = ∃ρ∈ Po v(G)θe(ρ, S)∧θeo(ρo, S)∧θei(ρi, S) Qei(v, S) = ∃ρ∈ Pi v(G)θe(ρ, S)∧θeo(ρo, S)∧θei(ρi, S) En general, escribiremos Qe∗(v, S), donde ∗ ∈ {o, i}, y notaremos: Q+ e∗=Qe∗, Q− e∗=¬Qe∗ 2. Para cada nodo, n∈VQ: Qn(S) = ∃v∈V ^ e∈γo(n) Qα(e) eo(v, S)∧^ e∈γi(n) Qα(e) ei(v, S)  Adem´as, notaremos: Q+ n=Qn, Q− n=¬Qn 4 Donde eorepresenta el nodo del que parte la arista eyeirepresenta el nodo destino de dicha relaci´on, Po v(G) (resp. Pi v(G)) representa los caminos en Gque parten del (resp., terminan en) nodo v. A partir de estas notaciones, podemos definir formalmente cu´ando un subgrafo verifica un GGQ determinado: Definici´on 4. Dado un subgrafo Sde un grafo con propiedades, G= (V, E, µ), y un Generalized Graph Query, Q= (VQ, EQ, µQ), ambos sobre el lenguaje L, diremos que Sverifica Q, y lo denotaremos SQ, si se verifica la f´ormula: Q(S) = ^ n∈VQ Qα(n) n(S) En caso contrario, escribiremos: S2Q. Con el fin de obtener m´etodos controlados de generaci´on de consultas se pueden definir refinamientos para ir modificando un GGQ por pasos unitarios. Dados dos GGQ, Q1, Q2,Q1refina Q2en G,Q1GQ2, si para todo S⊆G, si SQ1, entonces SQ2. Definici´on 5. Dado Q∈GGQ. Diremos que un conjunto de GGQs Res un conjunto de refinamiento de Qen Gsi verifica: 1. ∀Q0∈R(Q0GQ) 2. ∀S⊆G(SQ⇒ ∃!Q0∈R(SQ0)) En lo que sigue, dado Q,ClW Qrepresenta un grafo derivado de Qen el que se han duplicado los nodos presentes en W⊆VQ(con las respectivas aristas si las tuvieran). Siguiendo [1], se puede probar que los siguientes conjuntos de GGQ son refinamientos de Q: A˜nadir nodo nuevo: si m /∈VQ, entonces Q+{m}: Q1= (VQ∪ {m}, EQ, αQ∪(m, +), θQ∪(m, T)) Q2= (VQ∪ {m}, EQ, αQ∪(m, −), θQ∪(m, T)) A˜nadir arista nueva entre nodos positivos: si n, m ∈V+ Q, entonces Q+{n+e∗ −→ m+}(∗∈{+,−}) (donde Q0=Cl{n,m} Q): Q1= (VQ0, EQ0∪ {n+e∗ −→ m+}, θQ0∪(e, T)) Q2= (VQ0, EQ0∪ {n+e∗ −→ m−}, θQ0∪(e, T)) Q3= (VQ0, EQ0∪ {n−e∗ −→ m+}, θQ0∪(e, T)) Q4= (VQ0, EQ0∪ {n−e∗ −→ m−}, θQ0∪(e, T)) A˜nadir predicado a arista positiva entre nodos positivos: si n, m ∈ V+ Q, con n+e+ −→ m+, y ϕ∈FORM, entonces Q+{n+e∧ϕ −→ m+}(donde 5 Q0=Cl{n,m} Q): Q1=(VQ0, EQ0∪ {n+e0 −→ m+}, θQ0∪(e0, θe∧ϕ)) Q2=(VQ0, EQ0∪ {n+e0 −→ m−}, θQ0∪(e0, θe∧ϕ)) Q3=(VQ0, EQ0∪ {n−e0 −→ m+}, θQ0∪(e0, θe∧ϕ)) Q4=(VQ0, EQ0∪ {n−e0 −→ m−}, θQ0∪(e0, θe∧ϕ)) A˜nadir predicado a nodo positivo con entorno positivo: si n∈V+ Q, NQ(n)⊆V+ Q, y ϕ∈FORM, entonces Q+{n∧ϕ}: {Qσ= (VQ0, EQ0, αQ0∪σ, θQ0∪(n0, θn∧ϕ)) : σ∈ {+,−}NQ(n)} donde Q0=ClNQ(n) Q, y {+,−}NQ(n)es el conjunto todas las posibles asignaciones de signo a los elementos de NQ(n) (el entorno en Qdel nodo n). A partir de la estructura de un GGQ no es f´acil obtener un GGQ complementario con ´el. Sin embargo, hay muchos procesos de an´alisis sobre grafos con propiedades en los que necesitamos trabajar con sucesiones de consultas que verifiquen algunas propiedades de contenci´on y complementariedad como predicados. Los refinamientos vistos en esta secci´on vienen a cubrir esta carencia y permiten, por ejemplo, construir un ´arbol de particiones encajadas con los nodos etiquetados de la siguiente forma (Fig. 1): El nodo ra´ız est´a etiquetado con Q0(un GGQ inicial cualquiera). Si un nodo del ´arbol est´a etiquetado con Q, y R= (Q1, . . . , Qn) es un conjunto de refinamiento de Q, entonces sus nodos hijo se etiquetan con los elementos de R. Figura 1: ´ Arbol de refinamientos. Obs´ervese que la construcci´on del ´arbol anterior depende por completo de la elecci´on del conjunto de refinamiento que se elija en cada ramificaci´on. 6 4. GGQ-ID3 GGQ-ID3 es una adaptaci´on del algoritmo ID3 para crear ´arboles de deci- si´on capaces de clasificar correctamente estructuras inmersas en un Grafo con Propiedades haciendo uso de Generalized Graph Queries como herramientas de test en cada nodo interno del ´arbol de decisi´on. De forma similar a como trabaja cualquier algoritmo de tipo ID3, nuestra propuesta buscar´a las consultas que mejor clasifiquen los ejemplos del conjunto de entrenamiento obteniendo los GGQ a evaluar a lo largo de la construcci´on del ´arbol (extracci´on de caracter´ısticas) por medio de refinamientos. De esta forma, en cada nodo interno del ´arbol se realizar´a una discriminaci´on entre las estructuras que cumplen cada GGQ resultante de un refinamiento. Como suele ser habitual, tanto la medida de impureza usada como la estrategia que elige la mejor ampliaci´on del patr´on asociado a un nodo interno es un hiper-par´ametro del algoritmo. Aunque GGQ-ID3 posee una estructura muy similar a los diferentes algoritmos de construcci´on de ´arboles de decisi´on, presenta la novedad de recibir como conjunto de entrenamiento estructuras (subgrafos) inmersas en un grafo con propiedades. Por medio del uso adecuado de predicados, los GGQ del ´arbol resultante del algoritmo podr´an no solo evaluar propiedades de la estructura a clasificar, sino tambi´en propiedades de cualquier elemento (subgrafo) en su entorno. El conjunto de entrenamiento completo, L, estar´a formado por pares de la forma (S, valor), donde Ses un subgrafo de un grafo con propiedades G. En consecuencia, cada nodo, n, del ´arbol de decisi´on construido tendr´a asociadas las siguientes estructuras: Ln={(S1, y1), ..., (SN, yN)}⊆L, un subconjunto del conjunto de entrenamiento. Qn= (VQn, EQn, αQn, θQn), un GGQ que verifican todos los subgrafos de Ln. El algoritmo 1 presenta formalmente el algoritmo GGQ-ID3. N´otese que el conjunto de refinamientos disponibles, REFS, para ampliar el GGQ en cada paso, as´ı como la condici´on de parada y el criterio de selecci´on del refinamiento, permanecen como par´ametros libres del modelo. Algorithm 1 GGQ-ID3(G, Q, L, REFS) 1: Create a Root node for the tree 2: if Stop criteria is reached then 3: return The single-node tree Root, with most frequent label in L. 4: else 5: (Q1, .., Qk) = Optimal Refinement(G, Q, L, REFS) 6: L1={(S, y)∈ L :SQ1}, ..., Lk={(S, y)∈ L :SQk} 7: Add knew tree branches below Root with values GGQID3(G, Qi,Li, REFS) for every 1 ≤i≤k. 8: end if En un proceso habitual de aprendizaje a partir de subgrafos de G, los par´ametros de la llamada inicial del algoritmo ser´an: 7 G= (V, E, µ), grafo en el que se encuentran inmersos las estructuras a clasificar. L={(S1, y1), ..., (SN, yN)}, conjunto de pares (Si, yi) donde Si⊆Grepresenta un subgrafo e yies su valor de salida asociado. Q0= (VQ, EQ, µQ), GGQ inicial (normalmente un GGQ con la estructura com´un m´as grande en S1, ..., SN). REFS, conjunto de refinamientos disponibles. El algoritmo sigue el procedimiento habitual en un algoritmo de tipo ID3. Comienza creando un ´arbol que contiene un ´unico nodo (nodo ra´ız) al que est´an asociados todos los objetos de LyQ0. Si nes el nodo del ´arbol de decisi´on con el que estamos trabajando, el algoritmo eval´ua qu´e refinamiento permite dividir de mejor manera Ln(m´axima reducci´on de impureza) y ´este ser´a elegido para ser aplicado a Qn. A continuaci´on se crear´an tantas ramas a partir de ncomo GGQs tenga el refinamiento elegido y por cada una de ellas se transmitir´an los pares de Lnque cumplan con el GGQ asociado. Cada nodo hijo de nheredar´a cada GGQ resultante del refinamiento y proceder´a a buscar (si no se alcanza la condici´on de parada) el mejor refinamiento para el nuevo GGQ. De esta manera, por cada rama del ´arbol se heredar´a, no s´olo un conjunto de pares, sino un GGQ que verifican todos ellos. En caso de que se cumpla la condici´on de parada, el nodo se convertir´a en un nodo hoja asociada a la clase correspondiente. Este proceso se repite de manera recursiva. Los ´arboles de decisi´on que se obtienen en la mayor´ıa de los procedimientos autom´aticos dividen los datos en subconjuntos complementarios de manera recursiva [23]. Habitualmente, la divisi´on se lleva a cabo mediante la evaluaci´on de una condici´on sobre el conjunto de objetos actual y su correspondiente divisi´on binaria: una rama recibir´a el conjunto de objetos que cumplen con la condici´on, mientras que la otra recibe aquellos que no la cumplen. En los casos simples los patrones complementarios binarios se pueden producir simplemente negando la condici´on, pero en el caso multi-relacional la producci´on de patrones complementarios de este tipo no es tan directa. Es por ello que en la secci´on 3 se presentaron una serie de refinamientos que generan GGQ complementarios, aunque no necesariamente binarios. Nosotros usaremos esos refinamientos como conjunto REFS en la llamada del algoritmo en los ejemplos que se mostrar´an a continuaci´on, pero podr´ıa enriquecerse con cualquier refinamiento adicional que se considerase de valor. 4.1. Ejemplo de aplicaci´on del algoritmo GGQ-ID3 Vamos a presentar un caso concreto de aplicaci´on del algoritmo GGQ-ID3 sobre un peque˜no grafo con propiedades a modo de demostraci´on. Los refinamientos ser´an los vistos en la secci´on 3, usaremos la condici´on de parada m´as restrictiva (que todos los pares del nodo actual pertenezcan a la misma clase), y se usar´a la Ganancia de Informaci´on [16] como medida de impureza. Trabajaremos con el grafo social mostrado en la Figura 2, en el que se representan algunas conexiones de tipo marital entre usuarios, y otras relacionadas con la publicaci´on de fotograf´ıas por estos usuarios. Podemos encontrar nodos de tipo user yphoto, y relaciones de tipo husband,wife,publish y 8 likes. En este caso, no potenciaremos Lpor medio de medidas topol´ogicas del grafo, por lo que en el caso del refinamiento a˜nadir predicado a nodo los predicados disponibles ser´an {type =photo, type =user}, y en el caso del refinamiento a˜nadir predicado a arista, los predicados disponibles ser´an {type =publish, type =likes, type =husband}. Figura 2: Grafo Social. Adicionalmente, tenemos una propiedad en algunos nodos (los de tipo user) que indica su g´enero, con posibles valores F(female) y M(male), los nodos de tipo photo tendr´an asociado un valor de g´enero None. Aunque como hemos indicado el algoritmo GGQ-ID3 est´a preparado para construir ´arboles de decisi´on capaces de clasificar cualquier estructura (subgrafo) en un grafo con propiedades, con el fin de mostrar un primer ejemplo simple, abordamos un problema que solo intenta clasificar nodos, e intentaremos predecir el valor del g´enero en los mismos. Con el objetivo de que la exposici´on resulte m´as clara, y para evitar confusiones con la terminolog´ıa, a los nodos pertenecientes al conjunto de entrenamiento los denominaremos objetos, mientras que dejaremos el t´ermino nodos para los nodos del ´arbol de decisi´on en construcci´on. El algoritmo GGQ-ID3 construye el ´arbol de decisi´on de la Figura 3 (los nodos/aristas positivas son marcados en negro y los negativos en rojo) que es capaz de clasificar correctamente todos los nodos del grafo social de la Figura 2 seg´un su g´enero: F,MoNone. Todas las indicaciones que se hagan acerca de la construcci´on siguen la representaci´on mostrada en la citada figura. El conjunto de entrenamiento inicial, L, lo forman todos los pares formados por objetos del grafo de datos y su correspondiente g´enero. En la ejecuci´on del algoritmo el GGQ inicial, Q0, est´a compuesto por dos nodos positivos, uno de ellos con un predicado que exige pertenencia al subgrafo bajo evaluaci´on (v∈S) y otro que exige la condici´on contraria (v /∈S). Como se ha comentado anteriormente, es habitual que el GGQ inicial corresponda a la mayor subestructura com´un en los subgrafos a clasificar, en este caso, la mayor estructura com´un est´a compuesta por un ´unico nodo sin restricciones. Adem´as, y por motivos de eficiencia, en cada paso del algoritmo se crear´a un nodo positivo aislado con un 9 Figura 7: ´ Arbol de decisi´on GGQ (grafo El Hobbit). que caracterizan diferentes estructuras en el grafo (graph pattern mining) y que pueden ser utilizados como atributos de las estructuras clasificadoras en tareas posteriores (feature extraction). Hemos mostrado un conjunto inicial de refinamientos a la hora de presentar ejemplos de aplicaci´on del algoritmo GGQ-ID3, pero este conjunto puede ser modificado a˜nadiendo refinamientos acordes a la estructura del grafo utilizado en el aprendizaje o a la tarea a la que se orienta el mismo. El algoritmo MRDTL fue desarrollado hace m´as de una d´ecada para trabajar espec´ıficamente en bases de datos relacionales y con tareas simples de clasificaci´on, y puede ser visto como un caso particular del algoritmo GGQ-ID3 en el que s´olo se permiten GGQ con forma de ´arbol (ya que hacen uso de grafos de selecci´on) y donde s´olo se permite aprendizaje a partir de estructuras formadas por un ´unico nodo. En este sentido, GGQ-ID3 supone un salto adelante en una l´ınea de trabajo iniciada hace a˜nos y que se consideraba estancada desde entonces. El principal problema que presentan los algoritmos de construcci´on de ´arboles de decisi´on multi-relacionales es que el espacio de hip´otesis es extremadamente grande, y evidentemente GGQ-ID3 no est´a libre de este problema. Para reducir su complejidad y orientar la b´usqueda se pueden proponer varias soluciones. Por un lado, se puede analizar de manera estad´ıstica la frecuencia de aparici´on de ciertas estructuras atendiendo a las propiedades que intervienen 16 y a las restricciones asociadas con el fin de reducir el n´umero de posibles refinamientos a aplicar en cada caso y reducir el coste de la b´usqueda del mejor refinamiento. Para ello es necesario hacer uso de diversas medidas desarrolladas para grafos generalizados que extienden las medidas de frecuencia m´as simples que se usan en el caso de MRDTL-2 [2]. Por otro lado, se pueden crear familias de refinamientos m´as complejos (por ejemplo, combinar el refinamiento a˜nadir arista con a˜nadir propiedad a una arista en un solo paso) para de esta manera reducir el n´umero de pasos para obtener GGQ complejos y ampliar la reducci´on de impureza que suponen los pasos at´omicos que son menos informativos. Si se lleva a cabo esta ´ultima opci´on de manera adecuada (unificando los refinamientos en funci´on de la frecuencia de aparici´on de estructuras en el grafo) se puede conseguir que el algoritmo se acerque de manera m´as r´apida a la soluci´on. En ambos casos se consigue una mejora en la eficiencia sacrificando la posibilidad de cubrir un espacio de hip´otesis m´as amplio (pero que probablemente ofrece alternativas en las que la reducci´on de impureza es menor). En este sentido, en este trabajo se ha ofrecido un conjunto minimal de refinamientos bien construidos, pero debe tenerse en cuenta que no se ofrecen con la intenci´on de que sea ´optimo para ciertas tareas de aprendizaje. El segundo gran problema que tiene el agoritmo GGQ-ID3 (y que es heredado por todos los algoritmos inspirados en ID3) es la imposibilidad de deshacer las decisiones tomadas durante la construcci´on del ´arbol. De tal manera que las opciones de refinamiento en un paso determinado del algoritmo dependen de los refinamientos elegidos en pasos anteriores y determinan, hasta cierto punto, las opciones futuras. Para solucionar este problema, es habitual utilizar alg´un procedimiento de backtracking que permita deshacer decisiones si han desembocado en un mal resultado, o alg´un procedimiento de Beam-Search, como el utilizado en el algoritmo GBI [8], que permita tomar varias decisiones en paralelo, y finalmente seleccionar la que haya derivado en una mejor soluci´on. Con respecto a los trabajos futuros que derivan del desarrollo aqu´ı presentado, cabe mencionar que, gracias a que los GGQ est´an construidos utilizando la estructura de grafo generalizado, y que dicha estructura permite la definici´on de hipergrafos de manera natural, los GGQ pueden evaluar hipergrafos con propiedades teniendo en cuenta peque˜nas modificaciones sobre las definiciones presentadas, por lo que la extensi´on de los Generalized Graph Queries hacia Generalized Hypergraph Queries y por tanto a un GGQ-ID3 capaz de aprender de hipergrafos es un paso natural que merece la pena ser considerado. Adem´as, el desarrollo de diferentes conjuntos de refinamiento en funci´on del tipo de grafo a consultar o incluso la generaci´on autom´atica de dichos conjuntos a partir de estad´ısticas extra´ıdas del grafo a analizar puede derivar en optimizaciones importantes en procesos de construcci´on autom´atica y efectiva de GGQ. Por ´utlimo, cabe destacar que a pesar de que los GGQ ya est´an siendo utilizados por procedimientos de descubrimiento/aprendizaje como el algoritmo GGQ-ID3, son grandes candidatos para ser utilizados por otros algoritmos de este tipo. Los ´arboles de decisi´on constituyen una herramienta id´onea de Aprendizaje Autom´atico para ser combinada a trav´es de alg´un modelo ensemble, como Random Forest, gracias a su bajo coste computacional en el entrenamiento y a la aletoriedad conseguida en el modelo a partir de peque˜nos cambios en el conjunto de datos de los que aprender. Por ello, disponer de modelos adecuados de generaci´on autom´atica de ´arboles de decisi´on multi-relacionales se convierte en una tarea de gran importancia en el conjunto de la Inteligencia Artificial. 17 El aprendizaje autom´atico que hace uso de informaci´on relacional ha estado (y sigue estando) en un segundo plano en relaci´on al aprendizaje autom´atico m´as est´andar, que hace uso de informaci´on no relacional, habitualmente en forma de tablas y otras estructuras m´as regulares. Las bases de datos que m´as habitualmente se han utilizado, y en las que se encuentra almacenada la informaci´on referente a la mayor´ıa de los fen´omenos estudiados, hacen uso de esquemas y sistemas basados en bases de datos relacionales, que no muestran un desempe˜no ´optimo al trabajar con relaciones complejas. Adem´as, la mayor riqueza expresiva de las estructuras de representaci´on de la informaci´on m´as complejas impone una mayor dificultad a la hora de realizar nuevos algoritmos y proporciona, al menos en las primeras aproximaciones, resultados menos llamativos que los m´etodos m´as depurados y m´as tradicionales. Con respecto al aprendizaje en grafos con propiedades, cabe destacar que existen varias l´ıneas de trabajo que transforman los datos originales (en forma de grafo) hacia otras estructuras que los algoritmos m´as extendidos son capaces de manejar de manera m´as natural (debido a que fueron creados para trabajar espec´ıficamente con dichas estructuras). Es el caso de las inmersiones de grafos en espacios vectoriales [20, 26], as´ı como de la propuesta presentada en [9], que muestrean el grafo a partir de subestructuras para acomodarlo a una colecci´on de objetos (pares (elemento, contexto)) que los algoritmos tradicionales pueden consumir de manera ´optima. Tambi´en es el caso de los trabajos que usan Redes Neuronales Convolucionales para realizar tareas de aprendizaje en grafos [12, 5, 6]. Para poder utilizar este tipo de modelos sobre grafos debemos definir qu´e se entiende por el contexto espacial de un elemento del grafo, haciendo suposiciones que incluyen un sesgo adicional a la informaci´on analizada. Desde nuestro punto de vista, ´estas son aproximaciones v´alidas que deben seguir siendo investigadas, pero se deben considerar otras opciones como la de trabajar directamente con la estructura de grafo, que ha sido una de las l´ıneas de investigaci´on seguidas en este trabajo y que ha demostrado ser v´alida. Otra caractert´ıstica importante de los m´etodos de aprendizaje basados en ´arboles de decisi´on es que representan un modelo de caja blanca, ofreciendo una explicaci´on interpretable por un humano de las decisiones tomadas a la hora de realizar regresi´on o clasificaci´on. En el caso del algoritmo GGQ-ID3, este caracter´ıstica es potenciada gracias a la interpretabilidad de los GGQ. El hecho de que perdamos capacidad en la interpretaci´on de un resultado al combinar ´arboles multi-relacionales no impide que algoritmos como GGQ-ID3 puedan ser combinados en este tipo de m´etodos agregados para llevar a cabo tareas de predicci´on de tipo caja negra. Sin embargo, existen posibilidades para combinar diferentes ´arboles de este tipo y que sigan ofreciendo justificaciones interpretables por los humanos. Una posibilidad es combinar los GGQ de hojas asociadas a la misma clase en los diferentes ´arboles, dando lugar a patrones combinados (posiblemente de manera probabil´ıstica) que son capaces de condensar los diferentes predicados que caracterizan a una misma clase en un predicado m´as potente. Referencias [1] P. Almagro-Blanco and F. Sancho-Caparrini. Generalized Graph Pattern Matching. arXiv e-prints arXiv:1708.03734. 18 [2] Anna Atramentov, Hector Leiva, and Vasant Honavar. A Multi-relational Decision Tree Learning Algorithm – Implementation and Experiments, pages 38–56. Springer Berlin Heidelberg, Berlin, Heidelberg, 2003. [3] Hendrik Blockeel and Luc De Raedt. Top-down induction of logical decision trees. [4] Hendrik Blockeel and Luc De Raedt. Top-down induction of first-order logical decision trees. Artificial Intelligence, 101(1):285 – 297, 1998. [5] Micha¨el Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. CoRR, abs/1606.09375, 2016. [6] David K Duvenaud, Dougal Maclaurin, Jorge Iparraguirre, Rafael Bombarell, Timothy Hirzel, Alan Aspuru-Guzik, and Ryan P Adams. Convolutional networks on graphs for learning molecular fingerprints. In C. Cortes, N. D. Lawrence, D. D. Lee, M. Sugiyama, and R. Garnett, editors, Advances in Neural Information Processing Systems 28, pages 2224–2232. Curran Associates, Inc., 2015. [7] Warodom Geamsakul, Takashi Matsuda, Tetsuya Yoshida, Hiroshi Motoda, and Takashi Washio. Classifier Construction by Graph-Based Induction for Graph-Structured Data, pages 52–62. Springer Berlin Heidelberg, Berlin, Heidelberg, 2003. [8] Warodom Geamsakul, Tetsuya Yoshida, Kouzou Ohara, Hiroshi Motoda, Hideto Yokoi, and Katsuhiko Takabayashi. Constructing a decision tree for graph-structured data and its applications. Fundam. Inf., 66(1-2):131–160, November 2004. [9] Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks, 2016. cite arxiv:1607.00653 Comment: In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2016. [10] Yi He, Jian-chao Han, and Shao-hua Zeng. Classification Algorithm based on Improved ID3 in Bank Loan Application, pages 1124–1130. Springer London, London, 2012. [11] Yusuf Kavurucu, Pinar Senkul, and Ismail Hakki Toroslu. Confidence-based concept discovery in multi-relational data mining. [12] Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv:1609.02907, 2016. [13] Arno J. Knobbe, Arno Siebes, Danil Van Der Wallen, and Syllogic B. V. Multi-relational decision tree induction. In In Proceedings of PKDD’ 99, Prague, Czech Republic, Septembre, pages 378–383. Springer, 1999. [14] H´ector Ariel Leiva, Shashi Gadia, and Drena Dobbs. Mrdtl: A multirelational decision tree learning algorithm. In Proceedings of the 13th International Conference on Inductive Logic Programming (ILP 2003, pages 38–56. Springer-Verlag, 2002. 19 [15] Juan Li. Improved multi-relational decision tree classification algorithm. [16] Thomas M. Mitchell. Machine Learning. McGraw-Hill, Inc., New York, NY, USA, 1 edition, 1997. [17] Phu Chien Nguyen, Kouzou Ohara, Akira Mogi, Hiroshi Motoda, and Takashi Washio. Constructing Decision Trees for Graph-Structured Data by Chunkingless Graph-Based Induction, pages 390–399. Springer Berlin Heidelberg, Berlin, Heidelberg, 2006. [18] Phu Chien Nguyen, Kouzou Ohara, Hiroshi Motoda, and Takashi Washio. Cl-GBI: A Novel Approach for Extracting Typical Patterns from Graph- Structured Data, pages 639–649. Springer Berlin Heidelberg, Berlin, Heidelberg, 2005. [19] Neelamadhab Padhy and Rasmita Panigrahi. Multi relational data mining approaches: A data mining technique. CoRR, abs/1211.3871, 2012. [20] Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. Deepwalk: Online learning of social representations. In Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’14, pages 701–710, New York, NY, USA, 2014. ACM. [21] Gordon Plotkin. Automatic methods of inductive inference. 1972. [22] J. R. Quinlan. Induction of decision trees. Mach. Learn., 1(1):81–106, March 1986. [23] J. Ross Quinlan. C4.5: Programs for Machine Learning. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 1993. [24] Marcos Salganicoff, Lyle H. Ungar, and Ruzena Bajcsy. Active learning for vision-based robot grasping. Machine Learning, 23(2):251–278, 1996. [25] Anand Takale. Constructing Predictive Models to Assess the Importance of Variables in Epidemiological Data Using A Genetic Algorithm System employing Decision Trees. PhD thesis, UNIVERSITY OF MINNESOTA, 2004. [26] Jian Tang, Meng Qu, Mingzhe Wang, Ming Zhang, Jun Yan, and Qiaozhu Mei. Line: Large-scale information network embedding. In Proceedings of the 24th International Conference on World Wide Web, WWW ’15, pages 1067–1077, New York, NY, USA, 2015. ACM. [27] Xiaoxin Yin, Jiawei Han, Jiong Yang, and Philip S. Yu. CrossMine: Efficient Classification Across Multiple Database Relations, pages 172–195. Springer Berlin Heidelberg, Berlin, Heidelberg, 2006. [28] Wei Zhang. Multi-relational data mining based on higher-order inductive logic programming. 2013 Fourth Global Congress on Intelligent Systems, 2:453–458, 2009. 20