IB COMPUTER SCIENCE | A4.3.5 Association Rules (HL)

Lesson objective

Describe how association-rule mining discovers co-occurring attributes, calculate and interpret support, confidence and lift, and assess relationships in context.

Learn

A4.3.5 | ASSOCIATION RULES (HL ONLY)

01 | FIND WHAT TENDS TO OCCUR TOGETHER

An online shop wants to know which products often appear in the same order. It is not asking for a customer segment or a predicted delivery time. It wants relationships between recorded items.

Association-rule learning searches data for useful co-occurrence patterns. A rule such as {Bread} → {Milk} says that transactions containing bread also tend to contain milk under the measured pattern.

The arrow is not proof that buying bread causes someone to buy milk, or that milk is bought afterwards. This HL lesson builds the process from a small visible dataset, then considers how mining scales to large datasets and how results should be interpreted in context.

02 | DEFINE WHAT ONE RECORD MEANS

For market-basket analysis, one transaction is one purchase basket. Its items record which products were present in that basket. A customer making three separate orders contributes three transactions under this definition.

An item need not be a shop product. It can represent an attribute-value fact such as device type = tablet or reported theft = yes within a defined area-week. The unit of observation determines what co-occurrence means.

For ordinary presence-based itemsets, buying three cartons of milk in one basket counts as milk being present once in that transaction. Quantities, sequences and time gaps require explicitly different representations or methods.

03 | START WITH TEN TRANSACTIONS

Transaction Items present
T1 Bread, Milk
T2 Bread, Milk, Eggs
T3 Bread, Butter
T4 Milk, Eggs
T5 Bread, Milk, Butter
T6 Bread, Milk
T7 Eggs
T8 Eggs, Butter
T9 Butter
T10 Milk, Eggs

This fictional dataset contains ten baskets. Bread appears in five, milk in six, eggs in five and butter in four. Bread and milk appear together in four: T1, T2, T5 and T6.

No correct rule label is provided for each basket. The mining procedure discovers and ranks patterns by counting occurrences. The small table makes the arithmetic inspectable; ten baskets do not establish a reliable commercial relationship by themselves.

04 | READ A RULE AS A CONDITIONAL PATTERN

In X → Y, X is the antecedent, the condition on the left. Y is the consequent, the item or itemset on the right. They are nonempty and do not overlap in an ordinary association rule.

For {Bread} → {Milk}, look among baskets that contain bread and ask how often milk is also present. The rule is a measured tendency, not a logical guarantee that every bread basket must include milk.

A rule can have several items on the left: {Bread, Eggs} → {Milk}. A basket must contain every antecedent item to satisfy that condition. The interactive explorer begins with single-item antecedents and consequents so the denominators stay clear.

05 | ITEMSETS COME BEFORE DIRECTIONAL RULES

An itemset is a set of items considered together. {Bread, Milk} is an itemset; {Milk, Bread} is the same set because order does not matter.

A frequent itemset occurs in enough transactions to meet a chosen minimum-support threshold. From a frequent pair, a procedure can generate two directional rules: Bread → Milk and Milk → Bread.

They share the same joint occurrence count, but their confidence can differ because their left-hand conditions occur different numbers of times. Discovering frequent sets and evaluating rules are related but distinct stages.

06 | SUPPORT: HOW COMMON IS THE WHOLE PATTERN?

Here, support is a proportion: support(X → Y) = count(X and Y) / total transactions. The support count is the numerator, a number of transactions.

For Bread → Milk, support count = 4 and total = 10. Support = 4 / 10 = 40%. The same 40% applies to the joint itemset {Bread, Milk} and to the reverse rule Milk → Bread.

A support of 40% does not mean 40% of bread buyers also bought milk. That would use only bread baskets as the denominator. Support describes coverage across all transactions in the defined dataset.

07 | CONFIDENCE: HOW OFTEN DOES THE CONDITION LEAD TO CO-OCCURRENCE?

Confidence(X → Y) = count(X and Y) / count(X). It is the observed conditional frequency of Y among transactions containing X.

Bread occurs in five baskets. Four of them also contain milk, so confidence(Bread → Milk) = 4 / 5 = 80%. One bread basket, T3, does not contain milk.

This confidence is not an 80% probability that the mining algorithm is correct, a statistical confidence interval or a guarantee for future baskets. It is the conditional frequency measured in this dataset.

08 | REVERSE THE RULE, THEN CHANGE THE DENOMINATOR

Rule Joint count Antecedent count Support Confidence
Bread → Milk 4 5 4/10 = 40% 4/5 = 80%
Milk → Bread 4 6 4/10 = 40% 4/6 ≈ 66.7%

Both rules refer to the same four co-occurring baskets. However, milk is present in six baskets while bread is present in five, so the conditional populations differ.

The arrow expresses the direction of the conditional question, not the order of purchase or a causal mechanism. Do not copy the original confidence when reversing a rule.

09 | HIGH CONFIDENCE CAN HIDE A COMMON CONSEQUENT

Suppose 90% of all transactions contain a popular item. A rule saying 80% of some particular group’s baskets contain that item may sound strong, but that group actually contains it less often than the overall baseline.

Before calling a rule informative, compare its confidence with how often the consequent appears anyway. In the worked dataset, milk’s baseline support is 6 / 10 = 60%.

Bread → Milk has confidence 80%, above the 60% baseline. Eggs → Milk has confidence 3 / 5 = 60%, exactly the milk baseline. The second rule has substantial confidence without an increased co-occurrence rate under this comparison.

10 | LIFT: COMPARE WITH THE BASELINE

Lift(X → Y) = confidence(X → Y) / support(Y). Equivalently, lift = support(X and Y) / (support(X) × support(Y)). Use proportions consistently in these calculations.

For Bread → Milk, lift = 0.80 / 0.60 ≈ 1.333. In these transactions, milk occurs about 1.33 times as frequently among bread baskets as it does overall.

Lift above 1 indicates more co-occurrence than the independence baseline; lift of 1 matches that baseline; below 1 indicates less. Lift is not a percentage, a significance test or evidence that changing X will cause Y. For ordinary nonzero-support itemsets, reversing the rule leaves lift unchanged.

11 | COMPARE THREE RULES

Rule Support Confidence Consequent baseline Lift Interpretation
Bread → Milk 40% 80% Milk 60% 1.333 Above the overall milk rate
Eggs → Milk 30% 60% Milk 60% 1.000 No increase over this baseline
Butter → Milk 10% 25% Milk 60% 0.417 Below the overall milk rate

These measures answer different questions. Support describes pattern coverage, confidence describes conditional frequency and lift compares that frequency with the consequent’s baseline.

A high lift from a tiny number of baskets can be unstable. A frequent but obvious rule may add little business value. Interpret the counts, the metrics and the purpose together rather than selecting the largest single number.

12 | EXPLORE A RULE AND ITS MATCHING TRANSACTIONS

Choose an antecedent and a different consequent. The activity counts occurrences directly from the ten baskets and shows which transactions contain both, only one, or neither.

Start with Bread → Milk, reverse it and compare the denominators. Then try Eggs → Milk and Butter → Milk. The table’s status text identifies each group without relying on colour. This is an exact calculation on a small fictional dataset, not a forecast or causal experiment.

13 | FIND FREQUENT SETS BEFORE GENERATING RULES

Imagine a minimum support of 30% in the ten-basket dataset. An itemset must appear in at least three baskets to qualify. All four individual items qualify.

Pair itemset Support count Support Meets 30%?
Bread, Milk 4 40% Yes
Bread, Eggs 1 10% No
Bread, Butter 2 20% No
Milk, Eggs 3 30% Yes
Milk, Butter 1 10% No
Eggs, Butter 1 10% No

The frequent pairs are {Bread, Milk} and {Milk, Eggs}. From each, generate directional rule candidates and measure confidence. A minimum confidence of 70% retains Bread → Milk at 80%, but not Milk → Bread at approximately 66.7%, Milk → Eggs at 50% or Eggs → Milk at 60%.

Thresholds specify what to keep for investigation; passing them does not prove a relationship is true in the wider population or useful for action.

14 | APRIORI: PRUNE COMBINATIONS THAT CANNOT QUALIFY

Apriori is a frequent-itemset mining approach. It builds candidates from smaller frequent sets and uses the principle that every subset of a frequent itemset must also meet the same minimum support.

Why? Every basket containing Bread, Milk and Eggs must also contain Bread and Eggs. A triple cannot occur more often than any one of its subsets. If {Bread, Eggs} appears in only one basket, no triple containing that pair can reach a three-basket minimum.

This lets the procedure prune some candidates before counting them as larger sets. Lowering the minimum support can uncover rarer patterns, but can also produce many more candidates and rules. You need the principle and interpretation here, not a detailed implementation of the algorithm.

15 | LARGE DATASETS NEED EFFICIENT MINING

With many distinct items, the possible itemsets grow rapidly. For n items, there are 2ⁿ − 1 nonempty subsets before applying restrictions. A store with many products cannot treat exhaustive enumeration as a practical default.

Mining techniques reduce the search using support thresholds, candidate pruning, compact representations and limits on rule size. Apriori and frequent-pattern approaches such as FP-growth are examples with different search strategies.

The core workflow remains: define observations, prepare item presence, discover frequent combinations, generate rules, rank or filter them, then assess meaningfulness and stability. Compute speed cannot compensate for duplicated transactions or an inappropriate observation unit.

16 | TRY RULE FILTERS

The teaching miner enumerates the 12 possible directed single-item rules among these four items. Adjust minimum support and confidence to see which qualify. A real large-scale miner needs more efficient strategies and may consider multi-item rules too.

At 30% support and 70% confidence, only Bread → Milk qualifies. Lower confidence to 60% and inspect the newly retained rules and their lift. If no rules qualify under your settings, that is a valid filter result, not a software failure.

17 | FROM NUMERIC ATTRIBUTES TO ITEMS

Association mining is not restricted to products. A record might contain {device = tablet, session = evening, purchase = yes}. A rule can connect attribute-value facts that appear in the same defined record.

Continuous measurements may be converted into agreed ranges, such as basket value = high. This is discretization. The bin boundaries affect which facts co-occur, so explain and test those choices.

Do not include contradictory values of the same single-valued attribute in one observation. Preserve the meaning of “absent”: no recorded event is not always proof an event did not happen, especially where reporting is incomplete.

18 | THE SYLLABUS EXAMPLE: VANDALISM AND THEFT

For a fictional crime-analysis dataset, define one observation as one area during one week. Use consistently defined rate categories such as high vandalism rate and reported theft present, with appropriate exposure and reporting information.

Suppose there are 100 area-weeks, 20 marked high vandalism and 30 with reported theft. Twelve contain both. For {High vandalism} → {Reported theft}, support = 12/100 = 12%, confidence = 12/20 = 60%, and lift = 0.60/0.30 = 2.

The result means recorded theft is present in 60% of the high-vandalism area-weeks in this example, compared with 30% overall. It does not mean theft is certain, that vandalism caused theft or that the theft happened later.

19 | USE THE PATTERN AS EVIDENCE TO INVESTIGATE

An analyst could investigate why the recorded events co-occur and whether the finding is useful for prevention or resource planning. Confirm the pattern in other suitable periods or independent data rather than treating one mined rule as a validated forecast.

Area size, footfall, reporting behaviour, surveillance intensity and shared conditions can affect recorded rates. An area-level association does not establish anything about a particular individual or prove criminal intent.

Deployment decisions require checking accuracy of records, fairness, proportionality and the effect of interventions. Sending more observers to a location may produce more recorded incidents, creating a feedback loop. Association is a starting point for analysis, not sufficient evidence for an individual accusation or automatic enforcement decision.

20 | A RELATIONSHIP IS NOT A CAUSE OR A SEQUENCE

Ice-cream sales and sunscreen purchases may co-occur because sunny weather influences both. A promotion could also make two products appear together. The rule alone cannot distinguish these explanations.

Ordinary basket rules describe presence in the same observation. To ask whether X precedes Y, define time explicitly and use an appropriate temporal or sequential analysis; the arrow by itself does not add that information.

To ask whether recommending or changing X causes more Y, evaluate an appropriate intervention rather than reading a conditional frequency as a causal effect. Historical associations can change when prices, seasons or behaviour change.

21 | RARE RULES AND ACCIDENTAL DISCOVERIES

A pattern observed once can have 100% confidence if its antecedent appears only once. That sounds strong, but one basket provides little evidence about repeatability. Count and support matter alongside confidence or lift.

Searching very many combinations makes chance-looking patterns more likely to be discovered. Minimum thresholds help manage the search but are not tests of statistical significance and do not eliminate this risk.

Check stability across suitable samples or time periods, examine alternative explanations and validate on independent data for the intended use. Report sample sizes and changes in reporting or collection. Do not repeatedly adjust thresholds against the same supposedly independent evaluation until a preferred story appears.

22 | DISTINGUISH THE OUTPUT FROM OTHER LEARNING TASKS

Method Typical output What is being related
Association rules A rule such as Bread → Milk Co-occurring items or attribute-value facts
Clustering Groups of observations with similar features Customers or other entities
Supervised classification A predicted predefined class Inputs and known target categories
Regression A predicted numerical quantity Inputs and observed numerical responses

The methods can support the same business in different ways. A shop might cluster customers, classify returns and explore basket associations, but those outputs answer different questions.

Association rules may support recommendations or predictive features, yet their usual mining process does not need a provided target label for every transaction. Evaluate any resulting recommendation system separately from the rule’s historical support.

23 | CHECK THE INTERPRETATION

Choose the concept that explains each statement. Keep the observation unit, denominator and limits of the rule in mind.

24 | DESCRIBE A COMPLETE MINING PROCESS

A strong description follows the evidence: define transactions or attribute-value observations; clean and encode presence consistently; find itemsets meeting support requirements; generate non-overlapping antecedent/consequent rules; calculate confidence and compare with the consequent’s baseline; interpret and validate useful patterns.

Use context: “Twelve of 20 high-vandalism area-weeks also have recorded theft, so the rule has 60% confidence. Theft occurs in 30% of all area-weeks, so lift is 2. This suggests a recorded co-occurrence to investigate, not a cause or a prediction about an individual.”

For market baskets, explain what a recommendation would use and how you would test its value. For any application, distinguish an interesting historical relationship from evidence that an intervention will work.

Further reading: frequent patterns and rule generation and Apriori, support, confidence and lift.

MATCH THE ASSOCIATION IDEA TO ITS ROLE

Terminology

Terminology

Association-rule learning

Mining co-occurrence relationships between items or attribute-value facts.

Transaction

The defined unit containing a set of recorded items or facts.

Item

A product or attribute-value fact present in an observation.

Itemset

A set of items considered together, without purchase order.

Frequent itemset

An itemset meeting a chosen minimum-support requirement.

Antecedent

The nonempty condition on the left of an association rule.

Consequent

The nonempty itemset on the right of an association rule.

Rule direction

The direction of a conditional question, not proof of time order or cause.

Support count

The number of transactions containing the complete itemset.

Support

The proportion of all transactions containing both antecedent and consequent.

Confidence

The proportion of antecedent-containing transactions that also contain the consequent.

Consequent baseline

The overall support of the consequent used for comparison.

Lift

Confidence divided by consequent support, comparing with an independence baseline.

Independence baseline

The expected co-occurrence reference when the itemsets are statistically independent.

Minimum support

A chosen occurrence threshold used to retain frequent itemsets or rules.

Minimum confidence

A chosen conditional-frequency threshold used to filter rules.

Apriori

Frequent-itemset mining using smaller frequent sets and subset-based pruning.

Apriori principle

Every subset of a frequent itemset must also meet the same minimum support.

Candidate pruning

Discarding combinations that cannot qualify under a justified rule.

FP-growth

A frequent-pattern mining approach using a compact representation of transactions.

Discretization

Converting numerical values into specified categories or intervals.

Co-occurrence

Items or facts being recorded together in the same defined observation.

Conditional frequency

How often a fact appears within observations satisfying a stated condition.

Causation

A cause-and-effect relationship not established by co-occurrence alone.

Confounding

A shared influence that can help explain an observed relationship.

Sequential analysis

Analysis explicitly considering event order rather than only joint presence.

Stability

Repeatability of a useful pattern across appropriate samples or periods.

External validation

Checking a discovered relationship on suitable independent data.

Reporting bias

Distortion arising from differences in what events are observed or recorded.

Feedback loop

A process where actions change recorded evidence and can reinforce later decisions.

Questions

Questions

CHECK YOUR UNDERSTANDING

Select all correct choices. Each exact set earns one point.

1. Which describe association rules?
2. For Bread → Milk, which are correct?
3. Which calculations use the worked counts correctly?
4. Which hold when reversing Bread → Milk?
5. Which describe lift?
6. Which follow from a 30% support threshold in ten transactions?
7. Which explain Apriori pruning?
8. Which are valid crime-example interpretations?
9. Which are limits of mined relationships?
10. Which preserve data meaning?

EXPLAIN AND COMPARE

Write your answers before revealing each sample.

1. Describe how association-rule learning finds relationships in purchase data.

2. Calculate support and confidence for Bread → Milk in the ten baskets.

3. Describe what changes when the rule is reversed.

4. Calculate lift for Bread → Milk and describe its meaning.

5. Describe why a high-confidence rule may add little information.

6. Describe Apriori’s pruning principle with a basket example.

7. Describe why large-scale mining needs thresholds and efficient search.

8. Calculate the rule metrics for 100 area-weeks, 20 high-vandalism, 30 with theft and 12 with both.

9. Describe two cautions when interpreting the crime-analysis rule.

10. Describe the difference between an association, a causal claim and a sequence.

11. Describe why one observed rule with 100% confidence is not necessarily reliable.

12. Describe how association rules differ from customer clustering.

DESCRIBE IT | INTERPRET THE RELATIONSHIP

In 100 area-weeks, high vandalism is recorded in 20, theft in 30 and both in 12. Describe how a mining procedure can identify a rule, calculate its measures and interpret it cautiously for resource planning. Include observation-unit, reporting and causation limitations, then describe an independent check.

Flashcards

Flashcards

Click to flip. Select the ideas you need to revisit.

0 cards selected for revision.

Selections are kept while this page is open.

Workbook

Workbook

COMING SOON

The workbook for A4.3.5 Association Rules (HL) is coming soon. Complete the matching task and written questions in your exercise book.