Title | ||
---|---|---|
Discovering all associations in discrete data using frequent minimally infrequent attribute sets |
Abstract | ||
---|---|---|
Associating categories with measured or observed attributes is a central challenge for discrete mathematics in life sciences. We propose a new concept to formalize this question: Given a binary matrix of objects and attributes, determine all attribute sets characterizing object sets of cardinality t"1 that do not characterize any object set of size t"2t"1. We determine how many such attribute sets exist, give an output-sensitive quasi-polynomial time algorithm to determine them, and show that k-sum matrix decompositions known from matroid theory are compatible with the characterization. |
Year | DOI | Venue |
---|---|---|
2012 | 10.1016/j.dam.2012.03.013 | Discrete Applied Mathematics |
Keywords | Field | DocType |
binary matrix,discrete mathematics,observed attribute,attribute set,central challenge,associating category,object set,discrete data,life science,frequent minimally infrequent attribute,matroid theory,k-sum matrix,boolean functions,systems biology | Matroid,Boolean function,Discrete mathematics,Logical matrix,Matrix (mathematics),Variable and attribute,Cardinality,Data discrimination,Mathematics | Journal |
Volume | Issue | ISSN |
160 | 12 | 0166-218X |
Citations | PageRank | References |
0 | 0.34 | 6 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Elke Eisenschmidt | 1 | 0 | 1.35 |
Utz-Uwe Haus | 2 | 226 | 18.47 |