Computational Structures and Algorithms for Association Rules: the Galois Connection

Jacket Description/Back: Association rules are an essential tool in data mining, for revealing useful relations between different variables in large databases. However, the problem of deriving all frequent attributes subsets and association rules from a relational table is one with very high computational complexity. This focused and concise text/reference presents the development of state-of-the-art algorithms for finding association rules while limiting complexity. The rigorous mathematical construction of each algorithm is described in detail, covering advanced approaches such as formal concept analysis and Galois connection frameworks. The book also carefully presents the relevant mathematical foundations so that the only necessary prerequisite knowledge is an elementary understanding of lattices, combinatorial optimization, probability calculus, and statistics. Topics and features: Presents an extensive use of proofs, definitions, propositions, procedures, and examples throughout the textIntroduces the Galois framework, including definitions of the basic notionDescribes enumeration algorithms for solving problems of finding all formal concepts, all formal anti-concepts, and bridging the gap between concepts and anti-conceptsIncludes a helpful notation section, and useful chapter summariesExamines an alternative non-enumerative approach to solving the same problems, resulting in the construction of an incremental algorithmProposes solutions to the problem of building limited-size and minimal representations for perfect and approximate association rules based on the Galois connection frameworkUndergraduate and postgraduate students of computer science will find the text an invaluable introduction to the theory and algorithms for association rules. The in-depth coverage will also appeal to data mining professionals. Dr. Jean-Marc Adamo is a professor at the Universit de Lyon, France. He is the author of the Springer title Data Mining for Association Rules and Sequential Patterns. Publisher Marketing: Association rules are an essential tool in data mining for revealing useful oriented relations between variables in databases. However, the problem of deriving all frequent attribute subsets and association rules from a relational table is one with very high computational complexity. This focused and concise text/reference presents the development of state-of-the-art algorithms for finding all frequent attribute subsets and association rules while limiting complexity. The rigorous mathematical construction of each algorithm is described in detail, covering advanced approaches such as formal concept analysis and Galois connection frameworks. The book also carefully presents the relevant mathematical foundations, so that the only necessary prerequisite knowledge is an elementary understanding of lattices, formal logic, combinatorial optimization, and probability calculus. Topics and features: Presents the construction of algorithms in a rigorous mathematical style: concept definitions, propositions, procedures, examples. Introduces the Galois framework, including the definition of the basic notion. Describes enumeration algorithms for solving the problems of finding all formal concepts, all formal anti-concepts, and bridging the gap between concepts and anti-concepts. Examines an alternative - non-enumerative - approach to solving the same problems, resulting in the construction of an incremental algorithm. Presents solutions to the problem of building limited-size and minimal representations for perfect and approximate association rules based on the Galois connection framework. Includes a helpful notation section, and useful chapter summaries. Undergraduate and postgraduate students of computer science will find the text an invaluable introduction to the theory and algorithms for association rules. The in-depth coverage will also appeal to data mining professionals. Dr. Jean-Marc Adamo is a professor at the Universite de Lyon, France. He is the author of the Springer title Data Mining for Association Rules and Sequential Patterns.

Contributor Bio:  Adamo, Jean-Marc CPE-Lyon