anti-monotonicity concept
| Definition | The property that support cannot increase when an itemset grows, which licenses Apriori to prune every superset of an infrequent itemset without loss. Chapter 5. Also anti-monoton, pruning license. |
|---|---|
| Example | If bread and butter appear together in 30 baskets, then bread, butter, and jam appear together in at most 30. |
| Book | Data Mining as Observation, draft 0.2, commit f3914f0; entry id anti-monotonicity, kind concept. |
| Status | no ledger row names this entry. Corrections: none recorded. |
| Defining equation | none |
| Assumptions and scope |
|
| Prior art | none recorded |
| Evidence | lean/DataMiningAsObservation/SafePruning.lean, lean/DataMiningAsObservation/ItemSet.lean |
| Reviewed | not yet reviewed; generated 2026-09-10 from records at the commits on the provenance page. |
Equation
none
Conditions
- The property that support cannot increase when an itemset grows, since every transaction containing the larger set contains the smaller. It licenses Apriori to prune every superset of an infrequent itemset without loss, because no frequent itemset can lie above an infrequent one.
- The license is a statement about the measure and not about the data, and the book’s sidebar carries it to thresholds outside itemsets, where the analogous license is the ceiling on a score that a Youden bound supplies.
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 chapter 5 section 5.3 of Data Mining as Observation reads it.
Measurements
none
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.
lean/DataMiningAsObservation/ItemSet.lean,
theorems supportFrac_mem_unit,
supportFrac_empty, supportFrac_anti,
supportFrac_union_le, closed_of_maximal, 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.
Related
support; safe pruning; itemset.
See also
Book equations stated beside the entry’s terms, not defining it: 5.1, 5.3.
Sources-table rows that share a record with the entry without naming it: chapter 5 section 5.1 to 5.3, 5.5, chapter 5 section 5.3.
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.