Pattern Mining: Basic Concepts and Methods

Pattern Mining: Basic Concepts and Methods

Overview

Exam: ★★★★☆

Pattern mining asks how to discover recurring or strongly associated structures from large data sets. A pattern may be an itemset, a subsequence, or a more general substructure; such patterns summarize intrinsic regularities that can support association and correlation analysis, sequential or structural mining, discriminative classification, pattern-based clustering, and applications such as market-basket analysis, cross-marketing, Web-log analysis, and biological-sequence analysis. The same ideas extend beyond transaction tables to spatiotemporal, multimedia, time-series, and stream data.

The chapter follows one central progression. We first formalize transactions, itemsets, support, and association rules. Because the number of frequent patterns can be exponential, we then study compressed representations. Efficient mining starts from the anti-monotonicity of support, leading to Apriori and its pruning strategies; partitioning, hashing, vertical TID-lists, and FP-growth address the remaining database-scan and candidate-generation bottlenecks. Finally, because frequent or high-confidence patterns are not necessarily interesting, we move from support and confidence to correlation-aware and null-invariant evaluation measures.

Transactions, Frequent Itemsets, and Association Rules

Exam: ★★★★★

Transactional data and support

Let be the universe of items and let a transactional database be , where each transaction has a transaction identifier (TID) and contains a subset of . A transaction may additionally store quantities, although the basic frequent-itemset model uses only item presence or absence. An itemset contains one or more items; if , it is a -itemset.

The absolute support or support count of is the number of transactions containing every item in :

The relative support is

which can be read as the empirical probability that a transaction contains . A pattern is frequent when its support is at least a user-specified minimum-support threshold . Slides use both relative thresholds, such as , and absolute thresholds, such as a minimum support count of or ; the convention must therefore be checked before comparing numbers.

From itemsets to association rules

A frequent itemset says that items occur together; an association rule adds direction, written . Its support is the support of the combined itemset , while its confidence measures how often is present among transactions that already contain :

Given thresholds and , association-rule mining asks for every rule whose support and confidence satisfy both thresholds. The natural decomposition is therefore: first mine frequent itemsets; then generate and test rules from those itemsets.

Pattern Explosion and Compressed Representations

Exam: ★★★★☆

Frequent-pattern output can itself become intractable. Consider and with minimum support count . Every nonempty subset of occurs in at least one transaction, so the database contains

frequent itemsets. This is too large to enumerate or store, motivating compressed descriptions of the frequent-pattern family.

Closed patterns

A frequent itemset is closed if there is no proper super-itemset with and the same support as . Closed patterns retain exact frequency information: although many non-closed itemsets are omitted, their support can be recovered from a closed superpattern having the same transaction set. In this sense, the set of frequent closed patterns is a lossless compression of frequent itemsets with respect to support.

For the two-transaction database above, there are only two closed patterns: with support , and with support . For example, has support because it shares its support with the first closed pattern, while has support because it is contained only in the second transaction.

Maximal frequent patterns

A frequent itemset is maximal if it has no proper super-itemset that is also frequent. In the same two-transaction example with minimum support count , only is maximal. Maximal patterns therefore compress more aggressively than closed patterns, but the compression is lossy: if is contained in a maximal pattern, we can infer that is frequent, but not its exact support.

The lecture therefore favors closed patterns in applications where frequency information matters, while maximal patterns are attractive when storage reduction is the overriding goal. The slides name CHARM and CLOSET+ as later algorithms for closed-itemset mining, but do not develop their procedures in this chapter.

Downward Closure and the Apriori Algorithm

Exam: ★★★★★

Anti-monotonicity of support

The key structural property behind scalable frequent-itemset mining is the downward-closure or Apriori property. If , every transaction containing also contains , so

Consequently, every subset of a frequent itemset must be frequent. The contrapositive is the useful pruning rule: if any subset of a candidate is infrequent, then the candidate and all of its supersets are necessarily infrequent. This avoids exploring large regions of the itemset lattice.

Level-wise candidate generation and testing

Apriori proceeds breadth-first by itemset length. Let be the frequent -itemsets and the candidate -itemsets.

• Scan the database to obtain .
• While is nonempty, self-join compatible members of to form tentative -itemsets.
• Prune any candidate having an infrequent -subset.
• Scan the database to count the survivors and retain those meeting minimum support as .
• Return when no further frequent level can be produced.

If items inside each member of are kept in a common order, two itemsets and can be joined when their first items agree and their final items differ in the prescribed order. The joined candidate is admitted to only if every -subset belongs to .

A separate candidate-generation example makes the pruning step explicit. If , self-joining produces from and , and from and . Candidate is pruned because its subset is absent from , leaving .

Why Apriori still becomes expensive

Downward closure can remove enormous parts of the search space, but Apriori may still require many full database passes and may generate huge candidate sets before discovering that most candidates are infrequent. The slides group common improvements into three directions:

• reduce database scans: partitioning and dynamic itemset counting;
• shrink candidate sets: hashing/DHP, support-bound pruning, and sampling;
• change the search data structure: tree projection, H-miner, and the decomposition method associated with LCM in the slide.

Scaling Frequent-Pattern Mining

Exam: ★★★★☆

Partitioning: two database scans

Partitioning reduces repeated I/O by dividing into partitions that fit in main memory and using the same relative minimum-support threshold locally.

This yields a two-scan method. During the first scan, partition the database and mine the local frequent itemsets of each in-memory partition; their union forms a global candidate set. During the second scan, count only these candidates over the entire database and retain those whose true global support reaches the threshold.

Direct Hashing and Pruning (DHP)

DHP uses hashing to eliminate candidates before explicit support counting. During the first scan, while counting 1-itemsets, all 2-itemsets occurring inside each transaction are hashed into buckets. A bucket count is an upper bound on the support of any individual itemset mapped into that bucket. Therefore, if a bucket count is below minimum support, every 2-itemset hashing to it can be safely removed from .

The lecture example hashes itemsets such as , , and into a bucket of count . If minimum support is , all candidates mapped to that bucket are pruned without separate counting.

ECLAT and vertical data format

ECLAT changes representation rather than repeatedly scanning horizontal transactions. For each item or itemset , maintain its TID-list , the set of transaction identifiers containing . Support counting becomes set intersection:

The search is depth-first. Equality means that and occur in exactly the same transactions; inclusion means every transaction containing also contains . In the lecture example, and .

A diffset stores only TIDs lost when extending a pattern. For example, and , so the diffset of relative to is . This can reduce memory and intersection cost when TID-lists are long but successive extensions differ only slightly.

FP-Growth: Mining Without Candidate Generation

Exam: ★★★★★

Apriori spends work generating and testing candidates. FP-growth instead compresses the database into an FP-tree and recursively mines conditional databases. Its core strategy is divide-and-conquer: choose a frequent suffix item, collect the prefix paths leading to that item, compress those paths into a conditional FP-tree, and grow the suffix by frequent items found there.

Building the FP-tree

For the lecture database below, minimum support count is .

The first scan keeps the frequent single items , , , , , and . The slide fixes the global frequency order ; ties may be broken consistently, but every transaction must use the same order. Infrequent items are discarded, giving ordered frequent lists such as

• T100: ;
• T200: ;
• T300: ;
• T400: ;
• T500: .

The second scan inserts these lists into a prefix tree. Shared prefixes share nodes and node counts accumulate. The final structure contains a root branch and another root branch ; under , the main chain is , with branching to and , while also has a child. The root-level branch continues . A header table stores item frequencies and links together nodes carrying the same item so that conditional paths can be collected efficiently.

Conditional pattern bases and recursive growth

For an item , its conditional database is the multiset of prefix paths ending immediately before , weighted by the count of the corresponding node. From the lecture FP-tree:

With minimum support , the conditional database of retains only , yielding the larger pattern . The conditional database of has no prefix item reaching support , so has no frequent extension in that conditional tree. For , the paths and reduce to the shared frequent path . Appending suffix produces

, , , , , , , and .

This illustrates the important single-path shortcut: if a conditional FP-tree consists of one path, every nonempty combination of items along that path is a frequent extension of the current suffix, so the combinations can be emitted directly instead of creating another layer of conditional trees.

The slide also depicts a more general shared prefix path before a branching remainder. Such a prefix can be factored out: mine the branching remainder once, then combine its results with subsets of the shared prefix. This is another way FP-growth avoids redundant recursive work.

Pattern Evaluation Beyond Support and Confidence

Exam: ★★★★★

Pattern mining can generate many valid rules, so a second question is which patterns are worth interpreting. The slides distinguish objective interestingness measures, computed from data (support, confidence, correlation measures), from subjective criteria that depend on a user or task, such as query relevance, unexpectedness relative to prior knowledge, freshness, or timeliness.

Why confidence can be misleading

Let denote “plays basketball” and denote “eats cereal.” The lecture contingency table is

The rule has support and confidence . Those values look large, yet the overall cereal rate is . Knowing that a student plays basketball actually reduces the cereal probability from to . Conversely, not playing basketball gives . Confidence therefore needs a baseline comparison.

Lift

Lift compares observed co-occurrence with the level expected under independence:

A lift of corresponds to independence, a value above to positive association, and a value below to negative association. In the example,

while

Thus basketball and cereal are negatively associated in this table, while basketball and not eating cereal are positively associated.

Chi-square test of independence

For a contingency table, the expected count under independence is , and the Pearson statistic is

For the cereal/basketball table, the expected cell counts are , , , and , giving

This is strong evidence against independence when compared with the relevant reference distribution.

Null Invariance and Choosing an Interestingness Measure

Exam: ★★★★★

A null transaction with respect to and contains neither itemset. In very large sparse transaction data, null transactions can dominate: most baskets may contain neither milk nor coffee, and most papers may contain neither of two particular authors. A measure is null-invariant if adding or removing such transactions does not change its value.

The lecture constructs an extreme table with , , , and . Although joint occurrence is small in absolute terms, the huge null count changes the marginal baseline so strongly that and ; the expected count under independence is only about . The example motivates measures that ignore the null cell when null frequency is an incidental property of the data set.

Null-invariant measures

Define the two directional confidences

Both and are null-invariant because their numerators and denominators involve only transactions containing or . Several useful symmetric measures can be expressed through them.

Why Kulczynski needs an imbalance companion

Null invariance alone does not make all measures equivalent. The lecture uses data sets – in which the two directional implications become increasingly asymmetric. If the shared count is :

• has occurrences of each one-sided case, so ;
• has one-sided counts and , giving approximately and ;
• has one-sided counts and , giving approximately and .

Kulczynski remains in all three cases, which correctly says that the average directional association is neutral, but this alone hides the increasing asymmetry. The imbalance ratio supplies that missing information:

The slide reports for , about for , and about for . Thus Kulczynski plus IR distinguishes “neutral and balanced” from “neutral but highly imbalanced.”