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 Nf3201723b9554b118615d3d21b1ab7c2
    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 N88a58196b0ab40d2920a5a9afdf3ccce
    16 schema:genre chapter
    17 schema:inLanguage en
    18 schema:isAccessibleForFree true
    19 schema:isPartOf N5888ae4cb85e486181ae7bb6ea43a49a
    20 schema:name Discovering Frequent Closed Itemsets for Association Rules
    21 schema:pagination 398-416
    22 schema:productId N34e90e1170424aba8cb5c935768d7d0f
    23 N71c2c83d37c2499e9b223476714c25f3
    24 N9894ed4bc0aa44718f129899b3309a95
    25 schema:publisher N96ec387c55274b4b946fdc6800a6d0a2
    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 N5ef366be65fc4e69a92906ca07828fb3
    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 N2ae7d290ab6d4fce9c3a19292ab4bdf5 rdf:first Nf67585ba6b024ff883dd7c0339047fbb
    36 rdf:rest rdf:nil
    37 N33098a021c25429598daeb861256517a rdf:first sg:person.010242101441.40
    38 rdf:rest N9e814418957043518a6ad260afbbc860
    39 N34e90e1170424aba8cb5c935768d7d0f schema:name doi
    40 schema:value 10.1007/3-540-49257-7_25
    41 rdf:type schema:PropertyValue
    42 N5888ae4cb85e486181ae7bb6ea43a49a schema:isbn 978-3-540-49257-3
    43 978-3-540-65452-0
    44 schema:name Database Theory — ICDT’99
    45 rdf:type schema:Book
    46 N5bff11919e6b407c8de67d54b59c2d83 schema:familyName Beeri
    47 schema:givenName Catriel
    48 rdf:type schema:Person
    49 N5ef366be65fc4e69a92906ca07828fb3 schema:name Springer Nature - SN SciGraph project
    50 rdf:type schema:Organization
    51 N71c2c83d37c2499e9b223476714c25f3 schema:name readcube_id
    52 schema:value e76cdd485f34d6263f590d05971f1ebd251e89a4aaac9a9cd1882e15c099d3fc
    53 rdf:type schema:PropertyValue
    54 N88a58196b0ab40d2920a5a9afdf3ccce rdf:first N5bff11919e6b407c8de67d54b59c2d83
    55 rdf:rest N2ae7d290ab6d4fce9c3a19292ab4bdf5
    56 N96ec387c55274b4b946fdc6800a6d0a2 schema:location Berlin, Heidelberg
    57 schema:name Springer Berlin Heidelberg
    58 rdf:type schema:Organisation
    59 N9894ed4bc0aa44718f129899b3309a95 schema:name dimensions_id
    60 schema:value pub.1048579740
    61 rdf:type schema:PropertyValue
    62 N9e814418957043518a6ad260afbbc860 rdf:first sg:person.016473541174.35
    63 rdf:rest Nd02cc665370d4e328688f6ca524b22f8
    64 Nd02cc665370d4e328688f6ca524b22f8 rdf:first sg:person.013624074711.07
    65 rdf:rest rdf:nil
    66 Nf3201723b9554b118615d3d21b1ab7c2 rdf:first sg:person.013033261203.06
    67 rdf:rest N33098a021c25429598daeb861256517a
    68 Nf67585ba6b024ff883dd7c0339047fbb schema:familyName Buneman
    69 schema:givenName Peter
    70 rdf:type schema:Person
    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)


    ...