Discovery of the D-basis in binary tables based on hypergraph dualization

DOI10.1016/J.TCS.2015.11.031MaRDI QIDQ507518zbMATH OpenOpenAlexFDO

Authors J. B. Nation, Kira Adaricheva

Publication date 6 February 2017

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1504.02875

zbMATH Keywords

association rulesbinary tableGalois latticehypergraph dualizationimplicational basis

Mathematics Subject Classification ID

Hypergraphs (05C65) Galois correspondences, closure operators (in relation to ordered sets) (06A15) Database theory (68P15) Information storage and retrieval of data (68P20) Logic in artificial intelligence (68T27) Computational methods for problems pertaining to biology (92-08)

Abstract: 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 the lattice theory 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 the data provided by the University of Hawaii Cancer Center.

Recommendations

• Efficient algorithms for dualizing large-scale hypergraphs
• Efficient algorithms for dualizing large-scale hypergraphs
• A data mining formalization to improve hypergraph minimal transversal computation
• Dual-bounded generating problems: Partial and multiple transversals of a hypergraph
• Measuring the implications of the D-basis in analysis of data in biomedical studies

Cites work

• A framework for incremental generation of closed itemsets
• An approach to lattice varieties of finite height
• An efficient implementation of a quasi-polynomial algorithm for generating hypergraph transversals and its application in joint generation
• Attribute exploration with background knowledge
• Computing formal concepts by attribute sorting
• Computing premises of a minimal cover of functional dependencies is intractable
• Constructing a Knowledge Base for Gene Regulatory Dynamics by Formal Concept Analysis Methods
• Data mining. Concepts and techniques
• Dual subimplicants of positive Boolean functions
• Efficient algorithms for dualizing large-scale hypergraphs
• Fast algorithms for implication bases and attribute exploration using proper premises
• Generating dual-bounded hypergraphs
• scientific article; zbMATH DE number 1808289 (Why is no real title available?)
• scientific article; zbMATH DE number 1249514 (Why is no real title available?)
• scientific article; zbMATH DE number 2168560 (Why is no real title available?)
• scientific article; zbMATH DE number 2086380 (Why is no real title available?)
• scientific article; zbMATH DE number 758787 (Why is no real title available?)
• scientific article; zbMATH DE number 7635224 (Why is no real title available?)
• scientific article; zbMATH DE number 3420808 (Why is no real title available?)
• Identifying the Minimal Transversals of a Hypergraph and Related Problems
• Measuring the implications of the D-basis in analysis of data in biomedical studies
• On the Complexity of Dualization of Monotone Disjunctive Normal Forms
• On the complexity of enumerating pseudo-intents
• Ordered direct implicational basis of a finite closure system
• The lattices of closure systems, closure operators, and implicational systems on a finite set: A survey
• The multiple facets of the canonical direct unit implicational basis

Cited in

(10)

• Using congruence relations to extract knowledge from concept lattices
• Translating between the representations of a ranked convex geometry
• The joy of implications, aka pure Horn formulas: mainly a survey
• Algorithms for k-meet-semidistributive lattices
• Measuring the implications of the D-basis in analysis of data in biomedical studies
• Hierarchical decompositions of implicational bases for the enumeration of meet-irreducible elements
• A minimal base or a direct base? That is the question!
• Computing the D-base and D-relation in finite closure systems
• Enumerating minimal solution sets for metric graph problems
• Enumerating minimal solution sets for metric graph problems

This page was built for publication: Discovery of the \(D\)-basis in binary tables based on hypergraph dualization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q507518)