Mathematical tools for data mining. Set theory, partial orders, combinatorics (Q5891450)

This book provides an introduction to the mathematical, especially algebraic, foundations of data mining. Its particular focus is on set theory, including partially ordered sets and combinatorics, linear algebra, with its many applications in linear algorithms, topology as used in understanding and structuring data, and graph theory as a powerful tool for constructing data models. The set theory chapter starts with functions and relations and considers applications of these fundamental concepts to issues such as equivalences and partitions. Notions like operations, morphisms and congruences, as well as closure and interior systems, are treated. Partially ordered sets (posets) and certain algebraic structures, such as lattices and Boolean algebras, are considered as well. The chapter on combinatorics presents topics such as the inclusion-exclusion principle, combinatorics of partitions, counting problems related to collections of sets, and the Vapnik-Chervonenkis dimension of collections of sets. An introduction to topology and measure theory is followed by a chapter on the topology of metric spaces, and of various types of generalizations and specializations of the notion of metric. The dimension theory of metric spaces, crucial for applications of fractal theory to data mining, is dealt with. Furthermore, a variety of applications to data mining are discussed, such as the notion of entropy, presented in a new algebraic framework related to partitions rather than random distributions, level-wise algorithms that generalize the apriori technique, and generalized measures and their use in the study of frequent items sets and association rules. Linear algebra is present in the second edition of this monograph with three new chapters that deal with linear spaces, norms and inner products, and spectral theory. These chapters expand substantially the treatment of graph theory in this book. The final chapter covers clustering and includes many basic types of clustering algorithms, techniques for evaluating cluster quality, and spectral clustering. This book is a major revision of the first edition [Zbl 1151.68386] and also contains over 700 exercises (with solutions) and supplements.