TY - JOUR
T1 - Discovery of the D-basis in binary tables based on hypergraph dualization
AU - Adaricheva, K.
AU - Nation, J. B.
N1 - Publisher Copyright:
© 2015 Elsevier B.V.
Copyright:
Copyright 2016 Elsevier B.V., All rights reserved.
PY - 2017/1/7
Y1 - 2017/1/7
N2 - Discovery of (strong) association rules, or implications, is an important task in data management, and it finds application in artificial intelligence, data mining and the semantic web. We introduce a novel approach for the discovery of a specific set of implications, called the D-basis, that provides a representation for a reduced binary table, based on the structure of its Galois lattice. At the core of the method are the D-relation defined in a lattice theoretic framework and the hypergraph dualization algorithm that allows us to effectively produce the set of transversals for a given Sperner hypergraph. The latter algorithm, first developed by specialists from Rutgers Center for Operations Research, has already found numerous applications in solving optimization problems in data base theory, artificial intelligence and game theory. One application of the method is for analysis of gene expression data related to a particular phenotypic variable, and some initial testing is done for data provided by the University of Hawaii Cancer Center.
AB - Discovery of (strong) association rules, or implications, is an important task in data management, and it finds application in artificial intelligence, data mining and the semantic web. We introduce a novel approach for the discovery of a specific set of implications, called the D-basis, that provides a representation for a reduced binary table, based on the structure of its Galois lattice. At the core of the method are the D-relation defined in a lattice theoretic framework and the hypergraph dualization algorithm that allows us to effectively produce the set of transversals for a given Sperner hypergraph. The latter algorithm, first developed by specialists from Rutgers Center for Operations Research, has already found numerous applications in solving optimization problems in data base theory, artificial intelligence and game theory. One application of the method is for analysis of gene expression data related to a particular phenotypic variable, and some initial testing is done for data provided by the University of Hawaii Cancer Center.
KW - Association rules
KW - Binary table
KW - Galois lattice
KW - Hypergraph dualization
KW - Implicational basis
UR - http://www.scopus.com/inward/record.url?scp=84949239211&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84949239211&partnerID=8YFLogxK
U2 - 10.1016/j.tcs.2015.11.031
DO - 10.1016/j.tcs.2015.11.031
M3 - Article
AN - SCOPUS:84949239211
VL - 658
SP - 307
EP - 315
JO - Theoretical Computer Science
JF - Theoretical Computer Science
SN - 0304-3975
ER -