Discovering Frequent Closed Itemsets for Association Rules View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

1999-01-15

AUTHORS

Nicolas Pasquier , Yves Bastide , Rafik Taouil , Lotfi Lakhal

ABSTRACT

In this paper, we address the problem of finding frequent itemsets in a database. Using the closed itemset lattice framework, we show that this problem can be reduced to the problem of finding frequent closed itemsets. Based on this statement, we can construct efficient data mining algorithms by limiting the search space to the closed itemset lattice rather than the subset lattice. Moreover, we show that the set of all frequent closed itemsets suffices to determine a reduced set of association rules, thus addressing another important data mining problem: limiting the number of rules produced without information loss.We propose a new algorithm, called A-Close, using a closure mechanism to find frequent closed itemsets. We realized experiments to compare our approach to the commonly used frequent itemset search approach. Those experiments showed that our approach is very valuable for dense and/or correlated data that represent an important part of existing databases. More... »

PAGES

398-416

References to SciGraph publications

  • 1997-09. Levelwise Search and Borders of Theories in Knowledge Discovery in DATA MINING AND KNOWLEDGE DISCOVERY
  • 1991-09. Finding all closed sets: A general approach in ORDER
  • 1998. Pincer-search: A new algorithm for discovering the maximum frequent set in ADVANCES IN DATABASE TECHNOLOGY — EDBT'98
  • Book

    TITLE

    Database Theory — ICDT’99

    ISBN

    978-3-540-65452-0
    978-3-540-49257-3

    Author Affiliations

    Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/3-540-49257-7_25

    DOI

    http://dx.doi.org/10.1007/3-540-49257-7_25

    DIMENSIONS

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


    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/0806", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Information Systems", 
            "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 Clermont Auvergne", 
              "id": "https://www.grid.ac/institutes/grid.494717.8", 
              "name": [
                "Laboratoire d\u2019Informatique (LIMOS), Universit\u00e9 Blaise Pascal - Clermont-Ferrand II Complexe Scientifique des C\u00e9zeaux, 24, av. des Landais, 63177, Aubi\u00e8re Cedex, France"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Pasquier", 
            "givenName": "Nicolas", 
            "id": "sg:person.013033261203.06", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013033261203.06"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "University of Clermont Auvergne", 
              "id": "https://www.grid.ac/institutes/grid.494717.8", 
              "name": [
                "Laboratoire d\u2019Informatique (LIMOS), Universit\u00e9 Blaise Pascal - Clermont-Ferrand II Complexe Scientifique des C\u00e9zeaux, 24, av. des Landais, 63177, Aubi\u00e8re Cedex, France"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Bastide", 
            "givenName": "Yves", 
            "id": "sg:person.010242101441.40", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010242101441.40"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "University of Clermont Auvergne", 
              "id": "https://www.grid.ac/institutes/grid.494717.8", 
              "name": [
                "Laboratoire d\u2019Informatique (LIMOS), Universit\u00e9 Blaise Pascal - Clermont-Ferrand II Complexe Scientifique des C\u00e9zeaux, 24, av. des Landais, 63177, Aubi\u00e8re Cedex, France"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Taouil", 
            "givenName": "Rafik", 
            "id": "sg:person.016473541174.35", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016473541174.35"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "University of Clermont Auvergne", 
              "id": "https://www.grid.ac/institutes/grid.494717.8", 
              "name": [
                "Laboratoire d\u2019Informatique (LIMOS), Universit\u00e9 Blaise Pascal - Clermont-Ferrand II Complexe Scientifique des C\u00e9zeaux, 24, av. des Landais, 63177, Aubi\u00e8re Cedex, France"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Lakhal", 
            "givenName": "Lotfi", 
            "id": "sg:person.013624074711.07", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013624074711.07"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1023/a:1009796218281", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1011497512", 
              "https://doi.org/10.1023/a:1009796218281"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf00383449", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1020815872", 
              "https://doi.org/10.1007/bf00383449"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf00383449", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1020815872", 
              "https://doi.org/10.1007/bf00383449"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bfb0100980", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1023178884", 
              "https://doi.org/10.1007/bfb0100980"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0898-1221(92)90120-7", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1027696969"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0898-1221(92)90120-7", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1027696969"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/170035.170072", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1028726331"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/69.553155", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1061213547"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/253260.253325", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1098975472"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/276304.276313", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1098992874"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "1999-01-15", 
        "datePublishedReg": "1999-01-15", 
        "description": "In this paper, we address the problem of finding frequent itemsets in a database. Using the closed itemset lattice framework, we show that this problem can be reduced to the problem of finding frequent closed itemsets. Based on this statement, we can construct efficient data mining algorithms by limiting the search space to the closed itemset lattice rather than the subset lattice. Moreover, we show that the set of all frequent closed itemsets suffices to determine a reduced set of association rules, thus addressing another important data mining problem: limiting the number of rules produced without information loss.We propose a new algorithm, called A-Close, using a closure mechanism to find frequent closed itemsets. We realized experiments to compare our approach to the commonly used frequent itemset search approach. Those experiments showed that our approach is very valuable for dense and/or correlated data that represent an important part of existing databases.", 
        "editor": [
          {
            "familyName": "Beeri", 
            "givenName": "Catriel", 
            "type": "Person"
          }, 
          {
            "familyName": "Buneman", 
            "givenName": "Peter", 
            "type": "Person"
          }
        ], 
        "genre": "chapter", 
        "id": "sg:pub.10.1007/3-540-49257-7_25", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": true, 
        "isPartOf": {
          "isbn": [
            "978-3-540-65452-0", 
            "978-3-540-49257-3"
          ], 
          "name": "Database Theory \u2014 ICDT\u201999", 
          "type": "Book"
        }, 
        "name": "Discovering Frequent Closed Itemsets for Association Rules", 
        "pagination": "398-416", 
        "productId": [
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/3-540-49257-7_25"
            ]
          }, 
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "e76cdd485f34d6263f590d05971f1ebd251e89a4aaac9a9cd1882e15c099d3fc"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1048579740"
            ]
          }
        ], 
        "publisher": {
          "location": "Berlin, Heidelberg", 
          "name": "Springer Berlin Heidelberg", 
          "type": "Organisation"
        }, 
        "sameAs": [
          "https://doi.org/10.1007/3-540-49257-7_25", 
          "https://app.dimensions.ai/details/publication/pub.1048579740"
        ], 
        "sdDataset": "chapters", 
        "sdDatePublished": "2019-04-16T05:33", 
        "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/0000000346_0000000346/records_99818_00000003.jsonl", 
        "type": "Chapter", 
        "url": "https://link.springer.com/10.1007%2F3-540-49257-7_25"
      }
    ]
     

    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/3-540-49257-7_25'

    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/3-540-49257-7_25'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-49257-7_25'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/3-540-49257-7_25'


     

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

    118 TRIPLES      23 PREDICATES      34 URIs      19 LITERALS      8 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/3-540-49257-7_25 schema:about anzsrc-for:08
    2 anzsrc-for:0806
    3 schema:author N935ce5092ce440d3be2990b4bbdb23f8
    4 schema:citation sg:pub.10.1007/bf00383449
    5 sg:pub.10.1007/bfb0100980
    6 sg:pub.10.1023/a:1009796218281
    7 https://doi.org/10.1016/0898-1221(92)90120-7
    8 https://doi.org/10.1109/69.553155
    9 https://doi.org/10.1145/170035.170072
    10 https://doi.org/10.1145/253260.253325
    11 https://doi.org/10.1145/276304.276313
    12 schema:datePublished 1999-01-15
    13 schema:datePublishedReg 1999-01-15
    14 schema:description In this paper, we address the problem of finding frequent itemsets in a database. Using the closed itemset lattice framework, we show that this problem can be reduced to the problem of finding frequent closed itemsets. Based on this statement, we can construct efficient data mining algorithms by limiting the search space to the closed itemset lattice rather than the subset lattice. Moreover, we show that the set of all frequent closed itemsets suffices to determine a reduced set of association rules, thus addressing another important data mining problem: limiting the number of rules produced without information loss.We propose a new algorithm, called A-Close, using a closure mechanism to find frequent closed itemsets. We realized experiments to compare our approach to the commonly used frequent itemset search approach. Those experiments showed that our approach is very valuable for dense and/or correlated data that represent an important part of existing databases.
    15 schema:editor N6e3622b4eaf14d6e8002053bcde5f452
    16 schema:genre chapter
    17 schema:inLanguage en
    18 schema:isAccessibleForFree true
    19 schema:isPartOf Nd69a24e7b0bb4375b6681c8a09a5138f
    20 schema:name Discovering Frequent Closed Itemsets for Association Rules
    21 schema:pagination 398-416
    22 schema:productId N11a160cf05584f76a505231f5def25f9
    23 N5dfabde06b2b477786a0e79e0042db47
    24 N605c72a967f640e695dd90a1cf1e8de3
    25 schema:publisher N05c2d7cdb53644d8b087f8f23f8fc6a4
    26 schema:sameAs https://app.dimensions.ai/details/publication/pub.1048579740
    27 https://doi.org/10.1007/3-540-49257-7_25
    28 schema:sdDatePublished 2019-04-16T05:33
    29 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    30 schema:sdPublisher Ndb3992b00dbc43cf9c9db2992d3914e0
    31 schema:url https://link.springer.com/10.1007%2F3-540-49257-7_25
    32 sgo:license sg:explorer/license/
    33 sgo:sdDataset chapters
    34 rdf:type schema:Chapter
    35 N05c2d7cdb53644d8b087f8f23f8fc6a4 schema:location Berlin, Heidelberg
    36 schema:name Springer Berlin Heidelberg
    37 rdf:type schema:Organisation
    38 N11a160cf05584f76a505231f5def25f9 schema:name readcube_id
    39 schema:value e76cdd485f34d6263f590d05971f1ebd251e89a4aaac9a9cd1882e15c099d3fc
    40 rdf:type schema:PropertyValue
    41 N50f78fd733d344609705fad5e0e4a650 rdf:first sg:person.016473541174.35
    42 rdf:rest N7a58f2a79b984852a0968e3e2732b60f
    43 N5901d41a741c43a6805e63ef23dcba0d rdf:first Nb8872611ff8b46b8b5d76e4ec2279360
    44 rdf:rest rdf:nil
    45 N5dfabde06b2b477786a0e79e0042db47 schema:name doi
    46 schema:value 10.1007/3-540-49257-7_25
    47 rdf:type schema:PropertyValue
    48 N605c72a967f640e695dd90a1cf1e8de3 schema:name dimensions_id
    49 schema:value pub.1048579740
    50 rdf:type schema:PropertyValue
    51 N6e3622b4eaf14d6e8002053bcde5f452 rdf:first N9cee0bbad08749d7bbe8844ad2de7223
    52 rdf:rest N5901d41a741c43a6805e63ef23dcba0d
    53 N7a58f2a79b984852a0968e3e2732b60f rdf:first sg:person.013624074711.07
    54 rdf:rest rdf:nil
    55 N8d67ed1829fa400bb39a4ddd4faccb36 rdf:first sg:person.010242101441.40
    56 rdf:rest N50f78fd733d344609705fad5e0e4a650
    57 N935ce5092ce440d3be2990b4bbdb23f8 rdf:first sg:person.013033261203.06
    58 rdf:rest N8d67ed1829fa400bb39a4ddd4faccb36
    59 N9cee0bbad08749d7bbe8844ad2de7223 schema:familyName Beeri
    60 schema:givenName Catriel
    61 rdf:type schema:Person
    62 Nb8872611ff8b46b8b5d76e4ec2279360 schema:familyName Buneman
    63 schema:givenName Peter
    64 rdf:type schema:Person
    65 Nd69a24e7b0bb4375b6681c8a09a5138f schema:isbn 978-3-540-49257-3
    66 978-3-540-65452-0
    67 schema:name Database Theory — ICDT’99
    68 rdf:type schema:Book
    69 Ndb3992b00dbc43cf9c9db2992d3914e0 schema:name Springer Nature - SN SciGraph project
    70 rdf:type schema:Organization
    71 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    72 schema:name Information and Computing Sciences
    73 rdf:type schema:DefinedTerm
    74 anzsrc-for:0806 schema:inDefinedTermSet anzsrc-for:
    75 schema:name Information Systems
    76 rdf:type schema:DefinedTerm
    77 sg:person.010242101441.40 schema:affiliation https://www.grid.ac/institutes/grid.494717.8
    78 schema:familyName Bastide
    79 schema:givenName Yves
    80 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010242101441.40
    81 rdf:type schema:Person
    82 sg:person.013033261203.06 schema:affiliation https://www.grid.ac/institutes/grid.494717.8
    83 schema:familyName Pasquier
    84 schema:givenName Nicolas
    85 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013033261203.06
    86 rdf:type schema:Person
    87 sg:person.013624074711.07 schema:affiliation https://www.grid.ac/institutes/grid.494717.8
    88 schema:familyName Lakhal
    89 schema:givenName Lotfi
    90 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013624074711.07
    91 rdf:type schema:Person
    92 sg:person.016473541174.35 schema:affiliation https://www.grid.ac/institutes/grid.494717.8
    93 schema:familyName Taouil
    94 schema:givenName Rafik
    95 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016473541174.35
    96 rdf:type schema:Person
    97 sg:pub.10.1007/bf00383449 schema:sameAs https://app.dimensions.ai/details/publication/pub.1020815872
    98 https://doi.org/10.1007/bf00383449
    99 rdf:type schema:CreativeWork
    100 sg:pub.10.1007/bfb0100980 schema:sameAs https://app.dimensions.ai/details/publication/pub.1023178884
    101 https://doi.org/10.1007/bfb0100980
    102 rdf:type schema:CreativeWork
    103 sg:pub.10.1023/a:1009796218281 schema:sameAs https://app.dimensions.ai/details/publication/pub.1011497512
    104 https://doi.org/10.1023/a:1009796218281
    105 rdf:type schema:CreativeWork
    106 https://doi.org/10.1016/0898-1221(92)90120-7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1027696969
    107 rdf:type schema:CreativeWork
    108 https://doi.org/10.1109/69.553155 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061213547
    109 rdf:type schema:CreativeWork
    110 https://doi.org/10.1145/170035.170072 schema:sameAs https://app.dimensions.ai/details/publication/pub.1028726331
    111 rdf:type schema:CreativeWork
    112 https://doi.org/10.1145/253260.253325 schema:sameAs https://app.dimensions.ai/details/publication/pub.1098975472
    113 rdf:type schema:CreativeWork
    114 https://doi.org/10.1145/276304.276313 schema:sameAs https://app.dimensions.ai/details/publication/pub.1098992874
    115 rdf:type schema:CreativeWork
    116 https://www.grid.ac/institutes/grid.494717.8 schema:alternateName University of Clermont Auvergne
    117 schema:name Laboratoire d’Informatique (LIMOS), Université Blaise Pascal - Clermont-Ferrand II Complexe Scientifique des Cézeaux, 24, av. des Landais, 63177, Aubière Cedex, France
    118 rdf:type schema:Organization
     




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


    ...