Estimating the number of covering relations in a formal concept lattice

dc.contributor.advisor Jennifer Newman
dc.contributor.author Rodriguez, Aaron
dc.contributor.department Mathematics
dc.date 2018-08-11T15:41:20.000
dc.date.accessioned 2020-06-30T02:58:01Z
dc.date.available 2020-06-30T02:58:01Z
dc.date.copyright Thu Jan 01 00:00:00 UTC 2015
dc.date.embargo 2001-01-01
dc.date.issued 2015-01-01
dc.description.abstract <p>Given data organized in a tabular form called a cross table, the multi-dimensional relationships in the data are represented by a directed acyclic graph called a formal concept lattice. For large sets of data, drawing the graph is not reasonable. We focus on quantitative characteristics of the lattice structure that lead to decreased computation time in the determination of nodes and edge sets on large lattices from big data.</p> <p>This work addresses the problem of recovering the covering relations, of a concept lattice, given the set of nodes. We implement one existing algorithm and formally prove that it correctly computes the covering relations of a given concept lattice from its nodes. We also discuss methods for estimating the number of covering relations in a lattice and offer a conjecture for an upper bound for this number. We present experimental results to predict edge frequency distribution for a range of cross table densities. Finally we discuss some open problems.</p>
dc.format.mimetype application/pdf
dc.identifier archive/lib.dr.iastate.edu/etd/14624/
dc.identifier.articleid 5631
dc.identifier.contextkey 8049384
dc.identifier.doi https://doi.org/10.31274/etd-180810-4176
dc.identifier.s3bucket isulib-bepress-aws-west
dc.identifier.submissionpath etd/14624
dc.identifier.uri https://dr.lib.iastate.edu/handle/20.500.12876/28809
dc.language.iso en
dc.source.bitstream archive/lib.dr.iastate.edu/etd/14624/Rodriguez_iastate_0097M_15019.pdf|||Fri Jan 14 20:23:43 UTC 2022
dc.subject.disciplines Mathematics
dc.subject.keywords Applied Mathematics
dc.subject.keywords complete lattices
dc.subject.keywords concept lattices
dc.subject.keywords cover relations
dc.subject.keywords FCA
dc.subject.keywords Formal Concept Analysis
dc.subject.keywords posets
dc.title Estimating the number of covering relations in a formal concept lattice
dc.type article
dc.type.genre thesis
dspace.entity.type Publication
relation.isOrgUnitOfPublication 82295b2b-0f85-4929-9659-075c93e82c48
thesis.degree.level thesis
thesis.degree.name Master of Science
File
Original bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
Rodriguez_iastate_0097M_15019.pdf
Size:
427.96 KB
Format:
Adobe Portable Document Format
Description: