Computational Structures and Algorithms for Association Rules

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 Universit de Lyon, France. He is the author of the Springer title Data Mining for Association Rules and Sequential Patterns.