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


    ...