Simovici / Djeraba Mathematical Tools for Data Mining

Set Theory, Partial Orders, Combinatorics
1. Auflage 2008
ISBN: 978-1-84800-201-2
Verlag: Springer
Format: PDF
Kopierschutz: 1 - PDF Watermark

E-Book, Englisch, 615 Seiten

Reihe: Advanced Information and Knowledge Processing

This volume was born from the experience of the authors as researchers and educators,whichsuggeststhatmanystudentsofdataminingarehandicapped in their research by the lack of a formal, systematic education in its mat- matics. The data mining literature contains many excellent titles that address the needs of users with a variety of interests ranging from decision making to p- tern investigation in biological data. However, these books do not deal with the mathematical tools that are currently needed by data mining researchers and doctoral students. We felt it timely to produce a book that integrates the mathematics of data mining with its applications. We emphasize that this book is about mathematical tools for data mining and not about data mining itself; despite this, a substantial amount of applications of mathematical c- cepts in data mining are presented. The book is intended as a reference for the working data miner. In our opinion, three areas of mathematics are vital for data mining: set theory,includingpartially orderedsetsandcombinatorics;linear algebra,with its many applications in principal component analysis and neural networks; and probability theory, which plays a foundational role in statistics, machine learning and data mining. Thisvolumeisdedicatedtothestudyofset-theoreticalfoundationsofdata mining. Two further volumes are contemplated that will cover linear algebra and probability theory. The ?rst part of this book, dedicated to set theory, begins with a study of functionsandrelations.Applicationsofthesefundamentalconceptstosuch- sues as equivalences and partitions are discussed. Also, we prepare the ground for the following volumes by discussing indicator functions, ?elds and?-?elds, and other concepts.

Autoren/Hrsg.

Simovici, Dan A.

Djeraba, Chaabane

Djeraba, Chabane

Inhaltsverzeichnis

1;Preface;5
2;Contents;7
3;Part I Set Theory;14
3.1;1 Sets, Relations, and Functions;15
3.1.1;1.1 Introduction;15
3.1.2;1.2 Sets and Collections;15
3.1.3;1.3 Relations and Functions;21
3.1.4;1.4 The Axiom of Choice;46
3.1.5;1.5 Countable Sets;47
3.1.6;1.6 Elementary Combinatorics;50
3.1.7;1.7 Multisets;56
3.1.8;1.8 Relational Databases;58
3.1.9;Exercises and Supplements;61
3.1.10;Bibliographical Comments;67
3.2;2 Algebras;69
3.2.1;2.1 Introduction;69
3.2.2;2.2 Operations and Algebras;69
3.2.3;2.3 Morphisms, Congruences, and Subalgebras;73
3.2.4;2.4 Linear Spaces;76
3.2.5;2.5 Matrices;80
3.2.6;Exercises and Supplements;86
3.2.7;Bibliographical Comments;89
3.3;3 Graphs and Hypergraphs;91
3.3.1;3.1 Introduction;91
3.3.2;3.2 Basic Notions of Graph Theory;91
3.3.3;3.3 Trees;104
3.3.4;3.4 Flows in Digraphs;123
3.3.5;3.5 Hypergraphs;130
3.3.6;Exercises and Supplements;133
3.3.7;Bibliographical Comments;136
4;Part II Partial Orders;139
4.1;4 Partially Ordered Sets;141
4.1.1;4.1 Introduction;141
4.1.2;4.2 Partial Orders;141
4.1.3;4.3 Special Elements of Partially Ordered Sets;145
4.1.4;4.4 The Poset of Real Numbers;149
4.1.5;4.5 Closure and Interior Systems;151
4.1.6;4.6 The Poset of Partitions of a Set;156
4.1.7;4.7 Chains and Antichains;160
4.1.8;4.8 Poset Product;167
4.1.9;4.9 Functions and Posets;170
4.1.10;4.10 Posets and the Axiom of Choice;172
4.1.11;4.11 Locally Finite Posets and M¨ obius Functions;174
4.1.12;Exercises and Supplements;180
4.1.13;Bibliographical Comments;184
4.2;5 Lattices and Boolean Algebras;185
4.2.1;5.1 Introduction;185
4.2.2;5.2 Lattices as Partially Ordered Sets and Algebras;185
4.2.3;5.3 Special Classes of Lattices;192
4.2.4;5.4 Complete Lattices;200
4.2.5;5.5 Boolean Algebras and Boolean Functions;204
4.2.6;5.6 Logical Data Analysis;223
4.2.7;Exercises and Supplements;231
4.2.8;Bibliographical Comments;236
4.3;6 Topologies and Measures;237
4.3.1;6.1 Introduction;237
4.3.2;6.2 Topologies;237
4.3.3;6.3 Closure and Interior Operators in Topological Spaces;238
4.3.4;6.4 Bases;247
4.3.5;6.5 Compactness;251
4.3.6;6.6 Continuous Functions;253
4.3.7;6.7 Connected Topological Spaces;256
4.3.8;6.8 Separation Hierarchy of Topological Spaces;259
4.3.9;6.9 Products of Topological Spaces;261
4.3.10;6.10 Fields of Sets;263
4.3.11;6.11 Measures;268
4.3.12;Exercises and Supplements;277
4.3.13;Bibliographical Comments;284
4.4;7 Frequent Item Sets and Association Rules;285
4.4.1;7.1 Introduction;285
4.4.2;7.2 Frequent Item Sets;285
4.4.3;7.3 Borders of Collections of Sets;291
4.4.4;7.4 Association Rules;293
4.4.5;7.5 Levelwise Algorithms and Posets;295
4.4.6;7.6 Lattices and Frequent Item Sets;300
4.4.7;Exercises and Supplements;302
4.4.8;Bibliographical Comments;304
4.5;8 Applications to Databases and Data Mining;307
4.5.1;8.1 Introduction;307
4.5.2;8.2 Tables and Indiscernibility Relations;307
4.5.3;8.3 Partitions and Functional Dependencies;310
4.5.4;8.4 Partition Entropy;317
4.5.5;8.5 Generalized Measures and Data Mining;333
4.5.6;8.6 Di.erential Constraints;337
4.5.7;Exercises and Supplements;342
4.5.8;Bibliographical Comments;344
4.6;9 Rough Sets;345
4.6.1;9.1 Introduction;345
4.6.2;9.2 Approximation Spaces;345
4.6.3;9.3 Decision Systems and Decision Trees;349
4.6.4;9.4 Closure Operators and Rough Sets;357
4.6.5;Exercises and Supplements;359
4.6.6;Bibliographical Comments;360
5;Part III Metric Spaces;361
5.1;10 Dissimilarities, Metrics, and Ultrametrics;363
5.1.1;10.1 Introduction;363
5.1.2;10.2 Classes of Dissimilarities;363
5.1.3;10.3 Tree Metrics;369
5.1.4;10.4 Ultrametric Spaces;378
5.1.5;10.5 Metrics on;389
5.1.6;10.6 Metrics on Collections of Sets;400
5.1.7;10.7 Metrics on Partitions;406
5.1.8;10.8 Metrics on Sequences;410
5.1.9;10.9 Searches in Metric Spaces;414
5.1.10;Exercises and Supplements;423
5.1.11;Bibliographical Comments;433
5.2;11 Topologies and Measures on Metric Spaces;435
5.2.1;11.1 Introduction;435
5.2.2;11.2 Metric Space Topologies;435
5.2.3;11.3 Continuous Functions in Metric Spaces;438
5.2.4;11.4 Separation Properties of Metric Spaces;439
5.2.5;11.5 Sequences in Metric Spaces;447
5.2.6;11.6 Completeness of Metric Spaces;451
5.2.7;11.7 Contractions and Fixed Points;457
5.2.8;11.8 Measures in Metric Spaces;461
5.2.9;11.9 Embeddings of Metric Spaces;464
5.2.10;Exercises and Supplements;466
5.2.11;Bibliographical Comments;470
5.3;12 Dimensions of Metric Spaces;471
5.3.1;12.1 Introduction;471
5.3.2;12.2 The Dimensionality Curse;471
5.3.3;12.3 Inductive Dimensions of Topological Metric Spaces;474
5.3.4;12.4 The Covering Dimension;484
5.3.5;12.5 The Cantor Set;487
5.3.6;12.6 The Box-Counting Dimension;491
5.3.7;12.7 The Hausdor.-Besicovitch Dimension;494
5.3.8;12.8 Similarity Dimension;498
5.3.9;Exercises and Supplements;502
5.3.10;Bibliographical Comments;505
5.4;13 Clustering;507
5.4.1;13.1 Introduction;507
5.4.2;13.2 Hierarchical Clustering;508
5.4.3;13.3 The;524
5.4.4;Means;524
5.4.5;Algorithm;524
5.4.6;13.4 The PAM Algorithm;526
5.4.7;13.5 Limitations of Clustering;528
5.4.8;13.6 Clustering Quality;532
5.4.9;Exercises and Supplements;535
5.4.10;Bibliographical Comments;537
6;Part IV Combinatorics;539
6.1;14 Combinatorics;541
6.1.1;14.1 Introduction;541
6.1.2;14.2 The Inclusion-Exclusion Principle;541
6.1.3;14.3 Ramsey’s Theorem;545
6.1.4;14.4 Combinatorics of Partitions;548
6.1.5;14.5 Combinatorics of Collections of Sets;551
6.1.6;Exercises and Supplements;556
6.1.7;Bibliographical Comments;561
6.2;15 The Vapnik-Chervonenkis Dimension;563
6.2.1;15.1 Introduction;563
6.2.2;15.2 The Vapnik-Chervonenkis Dimension;563
6.2.3;15.3 Perceptrons;575
6.2.4;Exercises and Supplements;577
6.2.5;Bibliographical Comments;579
7;Part V Appendices;581
7.1;A Asymptotics;583
7.2;B Convex Sets and Functions;585
7.3;C Useful Integrals and Formulas;595
7.3.1;C.1 Euler’s Integrals;595
7.3.2;C.2 Wallis’s Formula;599
7.3.3;C.3 Stirling’s Formula;600
7.3.4;C.4 The Volume of an;602
7.3.5;Dimensional;602
7.3.6;Sphere;602
7.4;D A Characterization of a Function;605
8;References;609
9;Topic Index;617