Abstract
Big data analytics and mining aims to discover implicit, previously unknown, and potentially useful information and knowledge from big data sets that contain huge volumes of valuable veracious data collected or generated at a high velocity from a wide variety of rich data sources. Among different big data analytic and mining tasks, this chapter focuses on frequent pattern mining. By relying on the MapReduce programming model, researchers only need to specify the “map” and “reduce” functions to discover (organizational) knowledge from (i) big data sets of precise data in a breadth-first manner or depth-first manner and/or from (ii) big data sets of uncertain data. Such a big data analytics process can be sped up by focusing the mining according to the user-specified constraints that express the user interests. The resulting (constrained or unconstrained) frequent patterns mined from big data sets provide users with new insights and a sound understanding of users' patterns. Such (organizational) knowledge is useful is many real-life information science and technology applications.
TopBackground
Since the introduction of the research problem of frequent pattern mining (Agrawal, Imieliński, & Swami, 1993), numerous algorithms have been proposed (Hipp, Güntzer, & Nakhaeizadeh, 2000; Ullman, 2000; Ceglar & Roddick, 2006; Aggarwal, Bhuiyan, & Al Hasan, 2014; Leung et al., 2017c). Notable ones include the classical Apriori algorithm (Agrawal & Srikant, 1994) and its variants such as the Partition algorithm (Savasere, Omiecinski, & Navathe, 1995). The Apriori algorithm uses a level-wise breadth-first bottom-up approach with a candidate generate-and-test paradigm to mine frequent patterns from transactional databases of precise data. The Partition algorithm divides the databases into several partitions and applies the Apriori algorithm to each partition to obtain patterns that are locally frequent in the partition. As being locally frequent is a necessary condition for a pattern to be globally frequent, these locally frequent patterns are tested to see if they are globally frequent in the databases. To avoid the candidate generate-and-test paradigm, the tree-based FP-growth algorithm (Han, Pei, & Yin, 2000) was proposed. It uses a depth-first pattern-growth (i.e., divide-and-conquer) approach to mine frequent patterns using a tree structure that captures the contents of the databases. Specifically, the algorithm recursively extracts appropriate tree paths to form projected databases containing relevant transactions and to discover frequent patterns from these projected databases.
Key Terms in this Chapter
Anti-Monotonic Constraint: A constraint C such that, if an itemset S satisfying C, then any subset of S also satisfies C.
Frequent Pattern (Or Frequent Itemset): An itemset or a pattern with its actual support (or expected support) exceeds or equals the user-specified minimum support threshold.
Frequent Pattern Mining: A search and analysis of huge volumes of valuable data for implicit, previously unknown, and potentially useful patterns consisting of frequently co-occurring events or objects. It helps discover frequently co-located trade fairs and frequently purchased bundles of merchandise items.
Big Data: High-velocity, valuable, and/or multi-variety data with volumes beyond the ability of commonly-used software to capture, manage, and process within a tolerable elapsed time. These Big data necessitate new forms of processing to deliver high veracity (& low vulnerability) and to enable enhanced decision making, insight, knowledge discovery, and process optimization.
Data Mining: Non-trivial extraction of implicit, previously unknown and potentially useful information from data.
MapReduce: A high-level programming model, which uses the “map” and “reduce” functions, for processing huge volumes of data.
Itemset: A set of items.
Succinct Constraint: A constraint C such that all itemsets satisfying C can be expressed in terms of powersets of a fixed number of succinct sets using the set union and/or set difference operators. A succinct set is an itemset, in which items are selected from the domain using the usual Structured Query Language (SQL) selection operator. In simple terms, a constraint C is succinct meaning that all and only those itemsets satisfying C can be explicitly and precisely generated using some precise “formula”.