Inducing Classification and Regression Trees in First Order Logic View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2001

AUTHORS

Stefan Kramer , Gerhard Widmer

ABSTRACT

In this chapter, we present a system that enhances the representational capabilities of decision and regression tree learning by extending it to first-order logic, i.e., relational representations as commonly used in Inductive Logic Programming. We describe an algorithm named Structural Classification and Regression Trees (S-Cart), which is capable of inducing first-order trees for both classification and regression problems, i.e., for the prediction of either discrete classes or numerical values. We arrive at this algorithm by a strategy called upgrading — we start from a propositional induction algorithm and turn it into a relational learner by devising suitable extensions of the representation language and the associated algorithms. In particular, we have upgraded Cart, the classical method for learning classification and regression trees, to handle relational examples and background knowledge. The system constructs a tree containing a literal (an atomic formula or its negation) or a conjunction of literals in each node, and assigns either a discrete class or a numerical value to each leaf. In addition, we have extended the Cart methodology by adding linear regression models to the leaves of the trees; this does not have a counterpart in Cart, but was inspired by its approach to pruning. The regression variant of S-Cart is one of the few systems applicable to Relational Regression problems. Experiments in several real-world domains demonstrate that the approach is useful and competitive with existing methods, indicating that the advantage of relatively small and comprehensible models does not come at the expense of predictive accuracy. More... »

PAGES

140-159

References to SciGraph publications

  • 1999-03. Discovery of frequent DATALOG patterns in DATA MINING AND KNOWLEDGE DISCOVERY
  • 1995. Inductive constraint logic in ALGORITHMIC LEARNING THEORY
  • 1990-03. Boolean Feature Discovery in Empirical Learning in MACHINE LEARNING
  • 1999. Experiments in Predicting Biodegradability in INDUCTIVE LOGIC PROGRAMMING
  • 1997-02. First Order Regression in MACHINE LEARNING
  • Book

    TITLE

    Relational Data Mining

    ISBN

    978-3-642-07604-6
    978-3-662-04599-2

    Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/978-3-662-04599-2_6

    DOI

    http://dx.doi.org/10.1007/978-3-662-04599-2_6

    DIMENSIONS

    https://app.dimensions.ai/details/publication/pub.1037730986


    Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
    Incoming Citations Browse incoming citations for this publication using opencitations.net

    JSON-LD is the canonical representation for SciGraph data.

    TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

    [
      {
        "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
        "about": [
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0801", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Artificial Intelligence and Image Processing", 
            "type": "DefinedTerm"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Information and Computing Sciences", 
            "type": "DefinedTerm"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "University of Freiburg", 
              "id": "https://www.grid.ac/institutes/grid.5963.9", 
              "name": [
                "Institut f\u00fcr Informatik, Albert-Ludwigs-Universit\u00e4t Freiburg, Am Flughafen 17, D-79110\u00a0Freiburg, Germany"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Kramer", 
            "givenName": "Stefan", 
            "id": "sg:person.01163477630.27", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01163477630.27"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "University of Vienna", 
              "id": "https://www.grid.ac/institutes/grid.10420.37", 
              "name": [
                "Department of Medical Cybernetics and Artificial Intelligence, University of Vienna, Freyung 6/2, A-1010\u00a0Vienna, Austria"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Widmer", 
            "givenName": "Gerhard", 
            "id": "sg:person.013641401431.40", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013641401431.40"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1023/a:1009863704807", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1011882918", 
              "https://doi.org/10.1023/a:1009863704807"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/s0004-3702(98)00034-4", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1017069030"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1023/a:1007365207130", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1027516929", 
              "https://doi.org/10.1023/a:1007365207130"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0004-3702(94)90070-1", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1029262700"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0004-3702(94)90070-1", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1029262700"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0004-3702(95)00122-0", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1029374130"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1023/a:1022611825350", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1044481825", 
              "https://doi.org/10.1023/a:1022611825350"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-60454-5_30", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1045563174", 
              "https://doi.org/10.1007/3-540-60454-5_30"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-48751-4_9", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1053452453", 
              "https://doi.org/10.1007/3-540-48751-4_9"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1289/ehp.96104s51031", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1064746489"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2001", 
        "datePublishedReg": "2001-01-01", 
        "description": "In this chapter, we present a system that enhances the representational capabilities of decision and regression tree learning by extending it to first-order logic, i.e., relational representations as commonly used in Inductive Logic Programming. We describe an algorithm named Structural Classification and Regression Trees (S-Cart), which is capable of inducing first-order trees for both classification and regression problems, i.e., for the prediction of either discrete classes or numerical values. We arrive at this algorithm by a strategy called upgrading \u2014 we start from a propositional induction algorithm and turn it into a relational learner by devising suitable extensions of the representation language and the associated algorithms. In particular, we have upgraded Cart, the classical method for learning classification and regression trees, to handle relational examples and background knowledge. The system constructs a tree containing a literal (an atomic formula or its negation) or a conjunction of literals in each node, and assigns either a discrete class or a numerical value to each leaf. In addition, we have extended the Cart methodology by adding linear regression models to the leaves of the trees; this does not have a counterpart in Cart, but was inspired by its approach to pruning. The regression variant of S-Cart is one of the few systems applicable to Relational Regression problems. Experiments in several real-world domains demonstrate that the approach is useful and competitive with existing methods, indicating that the advantage of relatively small and comprehensible models does not come at the expense of predictive accuracy.", 
        "editor": [
          {
            "familyName": "D\u017eeroski", 
            "givenName": "Sa\u0161o", 
            "type": "Person"
          }, 
          {
            "familyName": "Lavra\u010d", 
            "givenName": "Nada", 
            "type": "Person"
          }
        ], 
        "genre": "chapter", 
        "id": "sg:pub.10.1007/978-3-662-04599-2_6", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": false, 
        "isPartOf": {
          "isbn": [
            "978-3-642-07604-6", 
            "978-3-662-04599-2"
          ], 
          "name": "Relational Data Mining", 
          "type": "Book"
        }, 
        "name": "Inducing Classification and Regression Trees in First Order Logic", 
        "pagination": "140-159", 
        "productId": [
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/978-3-662-04599-2_6"
            ]
          }, 
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "b3bcd2f3530fd70ebc463d9517d94cc7dd601544308a19d317de6ffc6ddc51f4"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1037730986"
            ]
          }
        ], 
        "publisher": {
          "location": "Berlin, Heidelberg", 
          "name": "Springer Berlin Heidelberg", 
          "type": "Organisation"
        }, 
        "sameAs": [
          "https://doi.org/10.1007/978-3-662-04599-2_6", 
          "https://app.dimensions.ai/details/publication/pub.1037730986"
        ], 
        "sdDataset": "chapters", 
        "sdDatePublished": "2019-04-15T14:26", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        }, 
        "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000001_0000000264/records_8669_00000266.jsonl", 
        "type": "Chapter", 
        "url": "http://link.springer.com/10.1007/978-3-662-04599-2_6"
      }
    ]
     

    Download the RDF metadata as:  json-ld nt turtle xml License info

    HOW TO GET THIS DATA PROGRAMMATICALLY:

    JSON-LD is a popular format for linked data which is fully compatible with JSON.

    curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/978-3-662-04599-2_6'

    N-Triples is a line-based linked data format ideal for batch operations.

    curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/978-3-662-04599-2_6'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-662-04599-2_6'

    RDF/XML is a standard XML format for linked data.

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-662-04599-2_6'


     

    This table displays all metadata directly associated to this object as RDF triples.

    112 TRIPLES      23 PREDICATES      36 URIs      20 LITERALS      8 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/978-3-662-04599-2_6 schema:about anzsrc-for:08
    2 anzsrc-for:0801
    3 schema:author N3fdac6cf7df346e3a0db45a0c0eb906b
    4 schema:citation sg:pub.10.1007/3-540-48751-4_9
    5 sg:pub.10.1007/3-540-60454-5_30
    6 sg:pub.10.1023/a:1007365207130
    7 sg:pub.10.1023/a:1009863704807
    8 sg:pub.10.1023/a:1022611825350
    9 https://doi.org/10.1016/0004-3702(94)90070-1
    10 https://doi.org/10.1016/0004-3702(95)00122-0
    11 https://doi.org/10.1016/s0004-3702(98)00034-4
    12 https://doi.org/10.1289/ehp.96104s51031
    13 schema:datePublished 2001
    14 schema:datePublishedReg 2001-01-01
    15 schema:description In this chapter, we present a system that enhances the representational capabilities of decision and regression tree learning by extending it to first-order logic, i.e., relational representations as commonly used in Inductive Logic Programming. We describe an algorithm named Structural Classification and Regression Trees (S-Cart), which is capable of inducing first-order trees for both classification and regression problems, i.e., for the prediction of either discrete classes or numerical values. We arrive at this algorithm by a strategy called upgrading — we start from a propositional induction algorithm and turn it into a relational learner by devising suitable extensions of the representation language and the associated algorithms. In particular, we have upgraded Cart, the classical method for learning classification and regression trees, to handle relational examples and background knowledge. The system constructs a tree containing a literal (an atomic formula or its negation) or a conjunction of literals in each node, and assigns either a discrete class or a numerical value to each leaf. In addition, we have extended the Cart methodology by adding linear regression models to the leaves of the trees; this does not have a counterpart in Cart, but was inspired by its approach to pruning. The regression variant of S-Cart is one of the few systems applicable to Relational Regression problems. Experiments in several real-world domains demonstrate that the approach is useful and competitive with existing methods, indicating that the advantage of relatively small and comprehensible models does not come at the expense of predictive accuracy.
    16 schema:editor Na94f8cfa2f114820bd3a466a59828dad
    17 schema:genre chapter
    18 schema:inLanguage en
    19 schema:isAccessibleForFree false
    20 schema:isPartOf N15775f8acbc0424bbffef98929521a6b
    21 schema:name Inducing Classification and Regression Trees in First Order Logic
    22 schema:pagination 140-159
    23 schema:productId N3d06b265e24e46e4b264683758448cdf
    24 N6cbcf38c7bd9402cb994270ca9f40989
    25 Ne5445f6e079246bca837df102d774b21
    26 schema:publisher Nb00555ed55cd409cbcb71393d52d3f40
    27 schema:sameAs https://app.dimensions.ai/details/publication/pub.1037730986
    28 https://doi.org/10.1007/978-3-662-04599-2_6
    29 schema:sdDatePublished 2019-04-15T14:26
    30 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    31 schema:sdPublisher N55740e896a2f46c68b5b27f8f0cd8b9f
    32 schema:url http://link.springer.com/10.1007/978-3-662-04599-2_6
    33 sgo:license sg:explorer/license/
    34 sgo:sdDataset chapters
    35 rdf:type schema:Chapter
    36 N15775f8acbc0424bbffef98929521a6b schema:isbn 978-3-642-07604-6
    37 978-3-662-04599-2
    38 schema:name Relational Data Mining
    39 rdf:type schema:Book
    40 N1da0617612e446adbc2831409be431e8 rdf:first N6065856fa97041c7b628b4b8cce4810e
    41 rdf:rest rdf:nil
    42 N3d06b265e24e46e4b264683758448cdf schema:name readcube_id
    43 schema:value b3bcd2f3530fd70ebc463d9517d94cc7dd601544308a19d317de6ffc6ddc51f4
    44 rdf:type schema:PropertyValue
    45 N3fdac6cf7df346e3a0db45a0c0eb906b rdf:first sg:person.01163477630.27
    46 rdf:rest N8b4594fd530441c9b9d2867df5f7a907
    47 N55740e896a2f46c68b5b27f8f0cd8b9f schema:name Springer Nature - SN SciGraph project
    48 rdf:type schema:Organization
    49 N6065856fa97041c7b628b4b8cce4810e schema:familyName Lavrač
    50 schema:givenName Nada
    51 rdf:type schema:Person
    52 N6cbcf38c7bd9402cb994270ca9f40989 schema:name doi
    53 schema:value 10.1007/978-3-662-04599-2_6
    54 rdf:type schema:PropertyValue
    55 N8b4594fd530441c9b9d2867df5f7a907 rdf:first sg:person.013641401431.40
    56 rdf:rest rdf:nil
    57 Na94f8cfa2f114820bd3a466a59828dad rdf:first Nb2688ee8a00e464aba1c3e2bf0cb4c9b
    58 rdf:rest N1da0617612e446adbc2831409be431e8
    59 Nb00555ed55cd409cbcb71393d52d3f40 schema:location Berlin, Heidelberg
    60 schema:name Springer Berlin Heidelberg
    61 rdf:type schema:Organisation
    62 Nb2688ee8a00e464aba1c3e2bf0cb4c9b schema:familyName Džeroski
    63 schema:givenName Sašo
    64 rdf:type schema:Person
    65 Ne5445f6e079246bca837df102d774b21 schema:name dimensions_id
    66 schema:value pub.1037730986
    67 rdf:type schema:PropertyValue
    68 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    69 schema:name Information and Computing Sciences
    70 rdf:type schema:DefinedTerm
    71 anzsrc-for:0801 schema:inDefinedTermSet anzsrc-for:
    72 schema:name Artificial Intelligence and Image Processing
    73 rdf:type schema:DefinedTerm
    74 sg:person.01163477630.27 schema:affiliation https://www.grid.ac/institutes/grid.5963.9
    75 schema:familyName Kramer
    76 schema:givenName Stefan
    77 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01163477630.27
    78 rdf:type schema:Person
    79 sg:person.013641401431.40 schema:affiliation https://www.grid.ac/institutes/grid.10420.37
    80 schema:familyName Widmer
    81 schema:givenName Gerhard
    82 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013641401431.40
    83 rdf:type schema:Person
    84 sg:pub.10.1007/3-540-48751-4_9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1053452453
    85 https://doi.org/10.1007/3-540-48751-4_9
    86 rdf:type schema:CreativeWork
    87 sg:pub.10.1007/3-540-60454-5_30 schema:sameAs https://app.dimensions.ai/details/publication/pub.1045563174
    88 https://doi.org/10.1007/3-540-60454-5_30
    89 rdf:type schema:CreativeWork
    90 sg:pub.10.1023/a:1007365207130 schema:sameAs https://app.dimensions.ai/details/publication/pub.1027516929
    91 https://doi.org/10.1023/a:1007365207130
    92 rdf:type schema:CreativeWork
    93 sg:pub.10.1023/a:1009863704807 schema:sameAs https://app.dimensions.ai/details/publication/pub.1011882918
    94 https://doi.org/10.1023/a:1009863704807
    95 rdf:type schema:CreativeWork
    96 sg:pub.10.1023/a:1022611825350 schema:sameAs https://app.dimensions.ai/details/publication/pub.1044481825
    97 https://doi.org/10.1023/a:1022611825350
    98 rdf:type schema:CreativeWork
    99 https://doi.org/10.1016/0004-3702(94)90070-1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1029262700
    100 rdf:type schema:CreativeWork
    101 https://doi.org/10.1016/0004-3702(95)00122-0 schema:sameAs https://app.dimensions.ai/details/publication/pub.1029374130
    102 rdf:type schema:CreativeWork
    103 https://doi.org/10.1016/s0004-3702(98)00034-4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1017069030
    104 rdf:type schema:CreativeWork
    105 https://doi.org/10.1289/ehp.96104s51031 schema:sameAs https://app.dimensions.ai/details/publication/pub.1064746489
    106 rdf:type schema:CreativeWork
    107 https://www.grid.ac/institutes/grid.10420.37 schema:alternateName University of Vienna
    108 schema:name Department of Medical Cybernetics and Artificial Intelligence, University of Vienna, Freyung 6/2, A-1010 Vienna, Austria
    109 rdf:type schema:Organization
    110 https://www.grid.ac/institutes/grid.5963.9 schema:alternateName University of Freiburg
    111 schema:name Institut für Informatik, Albert-Ludwigs-Universität Freiburg, Am Flughafen 17, D-79110 Freiburg, Germany
    112 rdf:type schema:Organization
     




    Preview window. Press ESC to close (or click here)


    ...