Apriori principle result

Definition	The statement that every subset of a frequent itemset is frequent, the contrapositive of anti-monotonicity. Chapter 5. Also Apriori, anti-monotonic.
Example	If the pair bread and jam is infrequent, every superset such as bread, jam, and milk is skipped without being counted.
Book	Data Mining as Observation, draft 0.2, commit `f3914f0`; entry id `apriori`, kind result.
Status	no ledger row names this entry. Corrections: none recorded.
Defining equation	Book equation 5.3.
Assumptions and scope	Support cannot increase when an itemset grows, so an infrequent itemset has only infrequent supersets and every subset of a frequent itemset is frequent. This holds for any finite collection of transactions. The principle licenses pruning the lattice above an infrequent itemset without counting, and the count of candidates rather than the count of transactions decides whether the run finishes.
Prior art	none recorded
Evidence	`lean/DataMiningAsObservation/SafePruning.lean`
Reviewed	not yet reviewed; generated 2026-09-10 from records at the commits on the provenance page.

Every superset of an infrequent itemset is infrequent.

Equation

Book equation 5.3.

\[X\subseteq Y\ \Longrightarrow\ s(X)\ge s(Y).\]

Book equation 5.1.

\[s(X)=\frac{\sigma(X)}{N},\qquad c(X\to Y)=\frac{\sigma(X\cup Y)}{\sigma(X)}=\frac{s(X\cup Y)}{s(X)}.\]

Conditions

Support cannot increase when an itemset grows, so an infrequent itemset has only infrequent supersets and every subset of a frequent itemset is frequent. This holds for any finite collection of transactions.
The principle licenses pruning the lattice above an infrequent itemset without counting, and the count of candidates rather than the count of transactions decides whether the run finishes.

Conditions are curated in entries.toml rather than read from a record.

Ledger

none

First stated

Agrawal and Srikant, fast algorithms for mining association rules, 1994, as TSK chapter 5 presents it, and chapter 5 section 5.3 of Data Mining as Observation.

Measurements

Where the book states it	Numbers, as the book’s sources table records them	Source
chapter 5 section 5.1 to 5.3, 5.5	support, confidence, lift, the Apriori principle, FP-growth, closed and maximal itemsets, objective measures, Simpson’s paradox, cross-support	TSK 2e chapter 5

Failures and corrections

none

Invariance envelope

none declared

Machine checked

lean/DataMiningAsObservation/SafePruning.lean, theorems support_anti, apriori, subset_of_frequent, at observation-data-mining f3914f0; what the check covers is stated in the book’s appendix C.

Used in

Data Mining as Observation chapters 5.

safe pruning; Monotone Invariance Theorem.

Status

Generated 2026-09-10 by encyclopedia/generate.py; book at observation-data-mining f3914f0; the commit of every record is listed in the encyclopedia’s provenance.

← anti-monotonicityattention →