Data Mining for Association Rules and Sequential Patterns: Sequential and Parallel Algorithms

by Jean-Marc Adamo

Overview

Data mining includes a wide range of activities such as classification, clustering, similarity analysis, summarization, association rule and sequential pattern discovery, and so forth. The book focuses on the last two previously listed activities. It provides a unified presentation of algorithms for association rule and sequential pattern discovery. For both mining problems, the presentation relies on the lattice structure of the search space. All algorithms are built as processes running on this structure. Proving their properties takes advantage of the mathematical properties of the structure. Part of the motivation for writing this book was postgraduate teaching. One of the main intentions was to make the book a suitable support for the clear exposition of problems and algorithms as well as a sound base for further discussion and investigation. Since the book only assumes elementary mathematical knowledge in the domains of lattices, combinatorial optimization, probability calculus, and statistics, it is fit for use by undergraduate students as well. The algorithms are described in a C-like pseudo programming language. The computations are shown in great detail. This makes the book also fit for use by implementers: computer scientists in many domains as well as industry engineers.

Product Details

ISBN-13:	9780387950488
Publisher:	Springer New York
Publication date:	12/28/2000
Edition description:	2001
Pages:	254
Product dimensions:	6.10(w) x 9.25(h) x 0.02(d)

Table of Contents

1. Introduction.- 2. Search Space Partition-Based Rule Mining.- 2.1 Problem Statement.- 2.2 Search Space.- 2.3 Splitting Procedure.- 2.4 Enumerating—-Frequent Attribute Sets (cass).- 2.5 Sequential Enumeration Procedure.- 2.6 Parallel Enumeration Procedure.- 2.7 Generating the Association Rules.- 3. Apriori and Other Algorithms.- 3.1 Early Algorithms.- 3.2 The Apriori Algorithms.- 3.3 Direct Hashing and Pruning.- 3.4 Dynamic Set Counting.- 4. Mining for Rules over Attribute Taxonomies.- 4.1 Association Rules over Taxonomies.- 4.2 Problem Statement and Algorithms.- 4.3 Pruning Uninteresting Rules.- 5. Constraint-Based Rule Mining.- 5.1 Boolean Constraints.- 5.2 Prime Implicants.- 5.3 Problem Statement and Algorithms.- 6. Data Partition-Based Rule Mining.- 6.1 Data Partitioning.- 6.2 cas Enumeration with Partitioned Data.- 7. Mining for Rules with Categorical and Metric Attributes.- 7.1 Interval Systems and Quantitative Rules.- 7.2 k-Partial Completeness.- 7.3 Pruning Uninteresting Rules.- 7.4 Enumeration Algorithms.- 8. Optimizing Rules with Quantitative Attributes.- 8.1 Solving 1-1-Type Rule Optimization Problems.- 8.2 Solving d-1-Type Rule Optimization Problems.- 8.3 Solving 1-q-Type Rule Optimization Problems.- 8.4 Solving d-q-Type Rule Optimization Problems.- 9. Beyond Support-Confidence Framework.- 9.1 A Criticism of the Support-Confidence Framework.- 9.2 Conviction.- 9.3 Pruning Conviction-Based Rules.- 9.4 One-Step Association Rule Mining.- 9.6 Refining Conviction: Association Rule Intensity.- 10. Search Space Partition-Based Sequential Pattern Mining.- 10.1 Problem Statement.- 10.2 Search Space.- 10.3 Splitting the Search Space.- 10.4 Splitting Procedure.- 10.5 Sequence Enumeration.- Appendix 1. Chernoff Bounds.- Appendix 2. Partitioning in Figure 10.5: Beyond3rd Power.- Appendix 3. Partitioning in Figure 10.6: Beyond 3rd Power.- References.