Pattern Mining: Basic and Advanced Methods

Pattern Mining: Basic and Advanced Methods

Overview

Exam: ★★★★☆

Pattern mining asks for recurring or otherwise statistically meaningful structures hidden in large data collections. The basic setting is a transaction database, where each transaction contains a set of items and the central task is to discover frequent itemsets and association rules. The main difficulty is combinatorial: a long transaction can induce exponentially many subpatterns, so useful mining systems need both compact representations and aggressive pruning.

The chapter develops a common line of ideas. First, support and confidence formalize frequency and directional implication; closed and maximal patterns compress the frequent-pattern family. Second, the downward-closure property enables scalable mining, leading from Apriori’s level-wise candidate generation to vertical-format ECLAT and pattern-growth FP-growth. Third, pattern evaluation goes beyond support and confidence through lift, , null-invariant measures, Kulczynski, and imbalance ratio. The same principles then generalize to multilevel, multidimensional, quantitative, rare, negative, sequential, and graph patterns. Constraint-based mining makes this process user-directed by pushing constraints into either the pattern space or the data space. Finally, the course illustrates how these ideas support graph indexing, approximate graph search, copy-paste bug detection, and phrase mining.

Foundations: Frequent Patterns, Rules, and Compact Representations

Exam: ★★★★★

Transaction databases, itemsets, and support

A transaction database is a collection of transactions. Each transaction has a transaction identifier (TID) and contains a set of items; in retail data, counts or quantities may also be attached to items. An itemset is a nonempty set of items, and a -itemset contains exactly items. For example, is a 3-itemset.

The absolute support of an itemset is the number of transactions containing all items in ; relative support is the corresponding fraction:

For the five-transaction example in the slides,

• and ;
• and ;
• ;
• .

An itemset is frequent if its support reaches the chosen threshold. With relative threshold , the condition is ; with an absolute threshold, the same test is applied to . At in the five-transaction database, the frequent 1-itemsets are Beer, Nuts, Diaper, and Eggs; the only frequent 2-itemset is ; no frequent 3-itemset exists.

Pattern discovery is broader than retail baskets: the slides treat patterns as itemsets, subsequences, or substructures that occur repeatedly or exhibit strong relationships. Such patterns support association/correlation analysis, sequential and graph mining, discriminative classification, pattern-based clustering, web-log analysis, biological sequence analysis, and mining of spatiotemporal, multimedia, time-series, and stream data.

From itemsets to association rules

A frequent itemset reports co-occurrence but not direction. An association rule is intended to express that transactions containing often also contain . The slides use two primary quantities:

Here is the combined itemset, so its support is the fraction of transactions containing both sides. For the rule , and . Association-rule mining is therefore: given minsup and minconf, enumerate all rules satisfying both thresholds.

Why output compression is necessary

The pattern family can be exponentially large. In the slide example and with absolute minsup = 1, every nonempty subset of is frequent. Hence the number of frequent itemsets is

Even when mining is computationally possible, storing or interpreting all patterns may be impossible. Two boundary representations are therefore important.

A closed frequent itemset is frequent and has no proper super-itemset with exactly the same support. Closed patterns are a lossless compression with respect to support information: if a non-closed frequent pattern is omitted, its support can be recovered from an appropriate closed superpattern with the same support. In the two-transaction example above, the only closed patterns are with support 2 and with support 1.

A maximal frequent itemset is frequent and has no frequent proper super-itemset. Maximal patterns are more aggressively compressed, but they are lossy: they preserve the boundary of the frequent region, not exact support values of omitted subsets. In the same example, the unique maximal pattern is .

Thus the relationship is:

• closed patterns: fewer than all frequent itemsets, but exact frequency information is retained;
• maximal patterns: usually still fewer, but subset supports are lost;
• all maximal frequent itemsets are closed, but not every closed itemset is maximal.

Scalable Frequent-Itemset Mining

Exam: ★★★★★

Downward closure: the pruning principle

The fundamental structural property is support anti-monotonicity: adding items cannot increase support. If , then every transaction containing also contains , so

This gives a safe pruning rule: once a candidate fails minimum support, there is no reason to generate any extension containing it. Three scalable families in the slides exploit this principle in different data organizations: Apriori uses level-wise candidate generation; ECLAT uses vertical TID sets and intersections; FP-growth compresses the database into FP-trees and grows patterns recursively.

Apriori: level-wise candidate generation and testing

Let denote the set of frequent -itemsets and the candidate -itemsets. Apriori proceeds level by level:

• scan the database to obtain ;
• from , generate candidate -itemsets by self-join;
• prune every candidate having an infrequent -subset;
• scan the database to count support of the remaining candidates and retain ;
• repeat until no candidate or frequent itemset remains.

In the slides’ four-transaction example with absolute minsup = 2, the first scan removes ; the second-level candidates are all pairs among , of which are frequent; the only surviving 3-item candidate is , with support 2.

Candidate generation itself has two stages. Suppose itemsets are listed in a fixed order. Two members of are joined when they share their first items and differ in the last item. Then the candidate is pruned if any -subset is absent from . For example, from

self-join can form and . Candidate is removed because is not frequent, leaving .

The weakness of Apriori is not correctness but cost: long patterns may require many database passes, and intermediate candidate sets can become enormous. The remaining methods try to reduce scans, candidates, or both.

Reducing Apriori’s cost: partitioning and DHP

Partitioning exploits a simple theorem.

The proof is by contradiction. If in every partition, then summing over partitions gives , so cannot be globally frequent. This leads to a two-scan algorithm: first partition the data so each partition fits in memory and mine local frequent patterns; then take their union as global candidates and perform one more full scan to obtain true global supports.

Direct Hashing and Pruning (DHP) shrinks candidate sets. While the first scan counts 1-itemsets, it hashes transaction 2-itemsets into buckets. A candidate mapped to a bucket whose bucket count is below minsup cannot itself be frequent, because the bucket count upper-bounds the support of every itemset mapped there. Hash collisions can inflate bucket counts, so a high bucket count does not prove frequency; a low bucket count is the useful safe pruning condition.

The slides also mention dynamic itemset counting, support lower-bound pruning, sampling, tree projection, H-miner, and hypercube/LCM-style decomposition as additional Apriori improvements or alternatives. Their common goal is to reduce scans, reduce candidate materialization, or use a data structure better matched to the search space.

ECLAT: vertical data and set intersections

Apriori stores transactions horizontally. ECLAT instead maps each item or itemset to its TID list:

Then support counting becomes set intersection:

This supports depth-first search without repeatedly scanning the original horizontal database. TID-list relations also carry semantic information: means and always occur in exactly the same transactions; means every transaction containing also contains .

A further optimization is the diffset: instead of storing a child’s full TID list, store what was removed relative to the parent. If and , then the diffset of relative to is . When intersections are large but differences are small, this representation can reduce memory and set-operation cost.

FP-growth: compression plus pattern growth

FP-growth avoids explicit candidate generation. Its first scan obtains frequent 1-items. Frequent items are sorted in descending support to form an f-list; each transaction is filtered to frequent items and reordered by that global order. A second scan inserts these ordered lists into a prefix tree. Shared prefixes share nodes and node counts accumulate, producing an FP-tree plus a header table linking occurrences of the same item.

In the course example with min_support = 3, the frequent items are , and the order is . Transaction 100 becomes , transaction 200 becomes , and so on. Repeated prefixes such as are represented once with counts.

Mining then uses divide and conquer. For a suffix item , collect the prefix paths leading to ; these form the conditional pattern base or conditional database of . Build its conditional FP-tree and recursively grow patterns ending in . For example, the slides give

• -conditional database: , whose frequent extension includes with support 3;
• -conditional database: , which reduces to after local support pruning;
• -conditional database: , which contains no frequent local extension at threshold 3.

A single-path conditional FP-tree is a special case: all nonempty combinations of the nodes on that path can be generated in one shot, with support determined by the minimum count along the chosen path segment. The overall FP-growth recipe is therefore: recursively construct and mine conditional trees until a tree is empty or becomes a single path.

Evaluating Pattern Interestingness

Exam: ★★★★★

Objective and subjective interestingness

Mining often returns far more valid patterns than a user can inspect. The slides separate objective measures, such as support, confidence, lift, and correlation statistics, from subjective criteria such as relevance to a user’s query, unexpectedness relative to prior knowledge, freshness, and timeliness. Objective measures are reproducible from data; subjective measures depend on the task and user context.

Why support and confidence are insufficient

Consider the basketball/cereal contingency table from the slides: among 1000 students, 600 play basketball (), 750 eat cereal (), and 400 do both. The rule has support and confidence

This looks strong under support-confidence thresholds, yet the overall cereal rate is . Knowing that a student plays basketball actually reduces the cereal probability from to . Confidence therefore needs a baseline comparison.

Lift and the chi-square statistic

Lift normalizes confidence by the consequent’s base rate:

Thus lift indicates independence, lift positive association, and lift negative association. In the example,

while

The statistic compares observed contingency-table counts with expected counts under independence:

For the same table, expected counts are and

A sufficiently large value rejects independence according to the relevant reference distribution. The statistic itself is nonnegative and does not encode direction; here the negative direction is inferred because the observed count, 400, is below its independence expectation, 450.

Null transactions and null invariance

A null transaction for and contains neither. In sparse transaction data there may be enormous numbers of such transactions. Lift and can change dramatically when only the number of null transactions changes. The slides’ example has counts , , , and : intuitively and rarely co-occur relative to their one-sided occurrences, yet lift is about and about because the huge null cell changes the marginal probabilities and independence baseline.

A measure is null invariant if adding or removing transactions leaves its value unchanged. Let

Both and are null invariant. Several useful measures are built only from the co-occurrence and the two one-sided supports:

AllConf, Jaccard, Cosine, Kulczynski, and MaxConf are null invariant; lift and are not. The measures nevertheless respond differently to severe marginal imbalance. The slides emphasize Kulczynski because it averages the two directional implications symmetrically.

Kulczynski plus imbalance ratio

The imbalance ratio separates directional imbalance from average association strength:

In itemset-mining notation is the support of the combined itemset, i.e. transactions containing both and ; therefore the denominator equals the fraction containing at least one of the two. IR is 0 when the two marginal supports are equal and approaches 1 as they become highly imbalanced.

The D4–D6 examples in the slides are designed so that Kulc stays at while IR rises from to about and then . They are all “neutral” in average directional implication, but the latter datasets are increasingly asymmetric. Hence Kulc and IR together distinguish strength from imbalance.

The DBLP coauthor example uses this idea to distinguish collaboration structures: advisor-advisee pairs can have high Kulc because a junior author publishes a large fraction of papers with the advisor, while the advisor has many additional papers, producing asymmetric marginal supports. The slides therefore recommend null-invariant measures in sparse settings and particularly Kulc + IR when null transactions dominate.

Beyond Flat Frequent Itemsets

Exam: ★★★★☆

Multilevel and customized-support mining

Real items often live in concept hierarchies, such as milk -> 2% milk / skim milk. A uniform minimum support across all hierarchy levels can suppress meaningful specific patterns because lower-level items naturally occur less often. In the slides, Milk has support , 2% Milk , and Skim Milk . A uniform threshold keeps Milk and 2% Milk but loses Skim Milk; a reduced lower-level threshold such as retains it.

A shared multilevel miner can use the lowest relevant threshold to pass candidates downward, then test each level with its own threshold. This creates a redundancy problem: a descendant rule may merely restate what its ancestor already predicts. If

• milk -> wheat bread has support , confidence ;
• 2% milk -> wheat bread has support , confidence ;
• 2% milk accounts for roughly one quarter of milk sales,

then support is almost exactly what the ancestor rule predicts, with nearly identical confidence. The descendant rule adds little information and is the natural one to prune as redundant.

More generally, different item groups can have individualized support thresholds. Expensive or rare items such as diamonds and watches may deserve thresholds around , whereas bread and milk may use . The mining algorithms must respect these heterogeneous thresholds without incorrectly pruning rare-but-important groups.

Multidimensional and quantitative associations

A single-dimensional rule repeats one predicate, e.g. buys(X, milk) -> buys(X, bread). A multidimensional rule involves at least two dimensions or predicates. The slides distinguish:

• inter-dimension rules, with no repeated predicate, e.g. age=18--25 and occupation=student -> buys=coke;
• hybrid-dimension rules, where a predicate may repeat, e.g. age=18--25 and buys=popcorn -> buys=coke.

Categorical dimensions can be handled through ordinary discrete values or data-cube-style aggregation. Numerical dimensions require a representation choice. The slides list static discretization from a predefined hierarchy, dynamic discretization from the data distribution, one-dimensional clustering followed by association mining, and deviation analysis.

A quantitative rule may describe an unusual aggregate rather than item co-occurrence, for example Gender=female -> mean wage = $7/hour when the overall mean is . The left-hand side defines a subpopulation and the right-hand side describes an extraordinary behavior of that subset. Such a rule should be accepted only when a statistical test, such as a Z-test, supports the deviation with sufficiently high confidence. Subrules refine the population further, e.g. adding South=yes and obtaining mean wage .

Rare and negative patterns

A rare pattern simply has low support but may still be valuable; individualized minimum supports are one practical solution. A negative pattern instead concerns two individually meaningful itemsets that occur together much less often than expected.

A naive support-based definition compares

This is essentially the lift idea and is not null invariant. In the needle-package example, and each occur 100 times and co-occur once. With only 200 total transactions, while , suggesting strong negative correlation. If the same three relevant counts are embedded in transactions by adding null transactions, then but , reversing the conclusion even though the relationship among transactions containing or has not changed.

The slides therefore define negative correlation using Kulczynski:

for frequent and . In the same example, each directional conditional probability is , so Kulc is regardless of the number of null transactions. A threshold can therefore identify negative patterns in a null-invariant way.

Compressed, approximate, and redundancy-aware pattern sets

Closed and maximal patterns compress by exact set-inclusion/support relationships. The advanced slides introduce a softer pattern distance based on transaction-ID sets:

This is Jaccard distance between the supporting transaction sets. Under -clustering, a representative pattern covers patterns that it can express and whose distance to is at most . The motivation is to find a middle ground: closed patterns may preserve too many very similar patterns because they insist on exact support distinctions, while maximal patterns may throw away too much support information.

The five-pattern example in the slides illustrates this balance: all five are closed, only one is maximal, but a desired compressed output contains three representative patterns .

A related selection problem is redundancy-aware top- mining: high-scoring patterns should also add new information relative to patterns already selected. The slides cite Maximal Marginal Significance (MMS) as a set-level objective balancing significance and redundancy. Unlike ordinary top-, which may return several nearly equivalent patterns, redundancy-aware selection aims to cover different informative regions of pattern space.

Constraint-Based Pattern Mining

Exam: ★★★★★

Constraint-based mining treats pattern discovery as an interactive query rather than “mine everything, filter later.” Users may constrain the knowledge type, data subset, dimensions/levels, interestingness thresholds, or the rule/pattern itself. The crucial systems idea is constraint pushing: exploit a constraint during search so that irrelevant patterns or data are never explored.

Pattern-space anti-monotonicity and monotonicity

A pattern constraint is anti-monotone if violation propagates upward: if violates , every superset of also violates it. Search below can terminate immediately. Examples from the slides include

• , assuming prices are nonnegative;
• ;
• , which is exactly the Apriori property.

A constraint is monotone if satisfaction propagates upward: if satisfies , every superset also satisfies it. Examples include

• for nonnegative prices;
• ;
• .

Monotonicity is still useful because once a prefix satisfies the constraint, that particular test need not be repeated on its extensions, but it usually prunes less aggressively than anti-monotonicity.

Convertible constraints and why search order matters

Some constraints are neither globally monotone nor globally anti-monotone but become so if items are processed in a suitable order. The slide example is

Order items by descending profit. Along a prefix-growth search in that order, once the running average drops to 20 or below, adding only later items whose profits are no larger cannot raise it above 20. The constraint is therefore convertible anti-monotone for that growth order.

However, this argument does not justify ordinary Apriori subset pruning. With profits , , and ,

If Apriori discards and solely because they violate the average constraint, it will never generate , even though satisfies it. The conversion is safe when pattern growth respects the specified order and only extends prefixes with lower-valued items; it is not a blanket replacement for Apriori’s true subset anti-monotonicity.

Data-space anti-monotonicity and recursive pruning

Pattern anti-monotonicity prunes candidate patterns. Data anti-monotonicity prunes candidate transactions. A constraint is data anti-monotone when, at the current projected search state, a transaction cannot support any extension satisfying the constraint; that transaction can then be removed from further processing.

For , the slide transaction has profits . Even its best achievable positive sum is 20, so no subset of that transaction can satisfy the threshold; the entire transaction can be pruned for this constrained search.

Data pruning should be revisited recursively because ordinary frequency pruning can tighten what remains possible. Under constraint , the slides inspect the database projected on . Item is locally infrequent and removed. After that removal, one projected transaction loses the only value that made a profit range above 25 possible, so the transaction itself becomes useless and can be removed. This in turn reduces support for another item. Constraint pruning and support pruning can therefore reinforce each other recursively.

Succinct constraints

A constraint is succinct if it can be enforced directly by manipulating the data before or during mining. Examples:

• to mine patterns containing item , mine only the -projected database;
• to mine patterns excluding , delete before mining;
• is succinct because qualifying low-price items can be identified directly and transactions containing only higher-price items can be discarded.

By contrast, is not succinct in this sense: whether a pattern reaches the sum threshold depends on how multiple items combine, so the full condition cannot be decided from individual items beforehand.

The constrained FP-growth example uses . After removing infrequent item 4, there is no need to start projected searches from items 3 or 5, because a valid pattern must contain at least one item with price at most 2. Only the projected spaces rooted at items 1 or 2 are relevant.

Combining constraints

Different constraints may require conflicting item orders. The slides propose prioritizing the constraint with greater pruning power, then reordering within projected databases to exploit another. For example, with and , if the profit constraint is stronger, process items first in descending profit; inside each resulting projected database, reorder appropriately for the price constraint.