—

Data Mining

Association Rule Mining

Published: 2026-08-05

Level: postgraduate

Audience: Postgraduate students in Data Mining

Prerequisite Knowledge

This lecture builds on the following concepts from earlier lectures. If any feel unfamiliar, review the linked notes before proceeding.

Previously Covered in This Subject

Association rule mining - covered in Lecture 2
Association rule mining applications - covered in Lecture 2
Market basket analysis - covered in Lecture 2
Descriptive versus predictive methods - covered in Lecture 2

11.1 What Is Association Rule Mining

11.1.1 The Mart Owner's Transaction Log

This session opens a new module. After the earlier classes on classification algorithms and ensemble-based methods, we now turn to association rule mining. The best way to meet it is through the mart example. We all go to a mart — Reliance Mart, Vishal Mega Mart, or D Mart — to buy grocery items. As a mart owner you hold something valuable: the transaction log generated at the billing counter. It looks like this: customer one purchased bread and milk; customer two purchased bread, diaper, beer and egg; customer three purchased some items; customer four purchased some items, and so on. A log like this is generated after each day, after each month, after each year.

Hook: Every mart owner already owns a gold mine — the pile of billing receipts generated at the counter. The only question is whether the owner can read them. That question is the starting point of association rule mining.

A small slice of such a log might look like this:

Transaction	Items purchased
1	bread, milk
2	bread, diaper, beer, egg
3	milk, bread, juice
4	milk, diaper, beer
5	bread, jam

Notice that every row is just a counter record: who bought what, in one visit. No labels, no target column, no "good" or "bad" outcome — only co-occurrence. That detail matters and returns in section 11.1.3.

The question that starts the whole module: given this transaction log, can the owner actually analyze it, find patterns in it, and use those patterns to make the mart better? That is the basic idea of association rule mining — take the raw transaction records and turn them into usable structure.

Visual intuition: Picture the log as a spreadsheet with one row per customer visit. The first column holds the customer number, the second holds the basket contents. Reading down the rows, patterns jump out as repeated co-appearances: milk shows up next to bread often, beer shows up next to diaper often. The axes of this picture are simply "which transaction" (rows) and "which item appears in it" (columns); the landmarks are the dense pairs that keep reappearing. The one-sentence takeaway: a transaction log is a table of co-occurrences, and rule mining is about reading the recurring columns of that table.

11.1.2 The Rules We Want to Find

Given a set of transactions, we want to find rules that help in predicting the sale of one item based on the occurrence of the sale of another item. This is also called mining frequent patterns and rules. We want statements like: if people who bought XYZ have also bought V and W; if diaper is sold, there is a high chance that beer is also sold; if beer and bread are bought, there is a high chance that milk is also bought by the same customer.

The rule form. Association rules are also called conditional dependency — the sale of product A leads to the sale of product B:

$A \to B$

meaning the sale of $A$ leads to the sale of $B$ . The left side $A$ is the antecedent (the trigger item or items), and the right side $B$ is the consequent (the item we expect to follow). The arrow reads "leads to" or "is followed by". In the small log above, the pair diaper $\to$ beer looks promising: diaper appears in transactions 2 and 4, and beer is present in both. The formal evaluation of such statements — how to judge whether "leads to" is actually true and how strong it is — is the heart of the module.

Worked mini-example: Scan the five transactions from section 11.1.1 and ask a simple question: when bread is sold, how often does milk follow?

Bread appears in transactions 1, 2, 3, 5 (4 times).
Milk appears together with bread in transactions 1 and 3 (2 times).

So the statement "bread $\to$ milk" holds for 2 out of 4 bread purchases. The arithmetic behind this fraction — the "2 out of 4" — is exactly the confidence measure the session defines formally later. Sense-check: intuitively, bread is a common item and milk is a common item, so seeing them together often is no surprise — a point that returns when we discuss support.

Once we can generate such rules from a transaction log, we can do a lot with them — the session later shows concrete uses.

Association rule mining works in two stages. First, find frequent patterns: which pattern is frequent, which item is sold multiple times. Second, once we know that a group of items is sold multiple times, find association rules inside that group. The session then spends the rest of its time on how to find frequent patterns and how to write and evaluate the rules.

11.1.3 Descriptive, Not Predictive: An Unsupervised Method

One point to hold onto: association analysis measures the strength of co-occurrence of items. It is not a predictive algorithm. It does not predict anything. It only finds usable patterns and structures in the co-occurrence of items in the data.

Scope: Association rule mining is a branch of unsupervised learning: it discovers hidden patterns in the data in the form of rules — A leads to B, A and B lead to C. There is no target variable to predict and no labelled training set. If the goal is "will this customer churn?", you need a supervised method instead. Association analysis answers a different question: "which things appear together, and how strongly?" It is descriptive — it describes what is there — not predictive.

Because the method only reads patterns of co-occurrence, it also carries a few traps worth naming before we go further.

Pitfalls

Treating co-occurrence as causation: "people who buy beer also buy diaper" is a co-occurrence, not proof that beer causes diaper purchases. The rules describe patterns in the data; business interpretation is still human work.
Expecting a prediction from the rules: a rule like $A \to B$ sounds predictive, but it is a summary of past co-occurrence strength, not a forecast of a new customer's behavior.
Believing the rule explains the customer: two items can co-occur because of a third hidden factor (a seasonal festival, a promotion) — the rule alone does not reveal that.

Association algorithms are widely used in retail analysis, recommendation systems, click systems, and so on. The most popular application is market basket analysis.

Recap: Association rule mining reads a transaction log and produces statements of the form $A \to B$ — "when A is sold, B tends to follow" — by first finding frequently co-occurring groups of items and then evaluating the rules inside those groups. It is unsupervised and descriptive: it structures what is already in the data rather than predicting what comes next. Next, we look at the most famous setting where this plays out: the market basket.

Real-world: the transaction-log framing comes straight from retail practice — every storefront and every online shop accumulates exactly this kind of counter data. E-commerce platforms, loyalty programs, and billing systems all generate the same raw material, and the same analysis pattern — find frequent co-occurrences, then act on them — shows up in retail analytics, recommendation systems, and clickstream analysis.

11.2 Market Basket Analysis and Its Business Uses

11.2.1 What Market Basket Analysis Is

Whenever we enter a mart we pick up a basket; whenever we shop online we fill a virtual cart. From the seller's point of view, analyzing what goes into those baskets is market basket analysis: find what items are purchased together so that the seller can maximize sales.

Intuition — the basket as a sentence: Think of every basket as a sentence written in the language of products. A single item is a word; the basket is the sentence. Market basket analysis is the study of which words keep appearing in the same sentence. Just as a linguist discovers that "morning" follows "good" very often, the retailer discovers that "butter" follows "bread and milk" very often. The everyday version of the same idea: when you order a burger and the counter asks "fries with that?", the restaurant is acting on a learned basket pattern.

This analysis feeds many business decisions: bundling, pricing, product placement, shelf management, catalog design, cross marketing, and understanding customer shopping behavior. Each of these is a different way to convert the same discovered pattern — "these items are bought together" — into money.

Visual intuition: Imagine a grid with items as rows and as columns, and each cell colored by how often the row item and column item co-occur — a co-occurrence heatmap. The diagonal is dark by definition (an item always co-occurs with itself), and the interesting landmarks are the unexpectedly dark off-diagonal cells, such as bread–milk or diaper–beer. Market basket analysis is the search for those dark cells and the business actions that follow from them.

11.2.2 Bundling and Cross Marketing

Bundling packets is a direct business application. A very best-selling packet is bundled with a less common packet: the price of one item is decreased and the price of another is increased, so the bundle pulls the weak product along with the strong one.

Worked mini-example: Suppose shampoo (a fast seller) and conditioner (a slow seller) are bought together in 60% of shampoo transactions. The store bundles them at a combined price: the shampoo gets a small discount, and the conditioner's share of the bundle price is above its standalone price. Customers who would have bought only the shampoo now take the bundle; the slow product rides on the fast one. The retailer's revenue from the pair rises even though the fast item earned slightly less per unit — because the bundle converts "shampoo only" purchases into "shampoo plus conditioner" purchases. Sense-check: the mechanism only works because the co-occurrence pattern is already strong — bundling amplifies an existing association, it does not create one.

Cross marketing is another strong example. For Haldiram it is easy to cross-market a new sweet, say Gulab Jamun, because the brand already sells sweets and the new product rides on that association. For Bajaj it is easy to launch an electrical item because the brand is already associated with electrical appliances. One product forces the sale of another product.

And once we know which items are purchased together, we can also place them closer or farther apart in the store — all of this is available from market basket analysis. Placing co-purchased items together shortens the customer's walk (section 11.3); placing a high-margin item next to its frequent companion raises the chance the companion pulls the expensive item into the basket.

Recap: Market basket analysis turns the transaction log into a map of co-purchase patterns, and each pattern feeds a business lever: bundle the weak product with the strong one, cross-market new products on existing brand associations, and place related items deliberately. Next we see the same map applied to the physical layout of the store itself.

Real-world: Haldiram, Bajaj, and every retailer with a loyalty or billing system live on this kind of co-purchase data. Recommendation engines on e-commerce sites — "customers who bought this also bought that" — are the online form of the same analysis, applied per customer instead of per store.

11.3 Supermarket Shelf Management

11.3.1 Arranging Items by Co-Purchase

A supermarket sells thousands of items. Those items are not arranged randomly — there is a pattern, and the pattern exists to maximize sales. The goal is to identify items that are bought together by a sufficiently large number of customers, using the transaction log generated at the billing counter. Then arrange the store so that items bought together sit close to each other.

The idea in one line: Shelf management = turn co-purchase patterns (from the transaction log) into physical adjacency decisions (where the shelves sit). The input is the same log used everywhere in this module; the output is a store layout. Notice the two ingredients: "bought together" must be established by counting, and "sufficiently large number" is a threshold that the store decides — both ideas recur formally in sections 11.10 and 11.14.

11.3.2 Why Closeness Helps the Whole Store

Suppose bread and milk are bought together heavily in a particular supermarket. It makes common sense to put bread and milk packets very near each other: a person picking up bread quickly picks up milk and leaves.

Intuition — completing the meal: A shopper has a mental list, but part of the list is written in the store. Walking past milk on the way out of the bread aisle completes the purchase that was only half-planned. The store is not forcing anything — it is simply placing the items where the shopper's own habits take them. The analogy from everyday life: a well-planned kitchen keeps salt, pepper, and oil next to the stove; the cook finds them without thinking, and nothing breaks the cooking rhythm.

Quick purchase means the customer leaves the store quickly, which frees space for a new customer to enter, and the cycle repeats — more customers served per hour.

Worked mini-example: A store's bread-and-milk arrangement can be scored in simple numbers. Suppose the bread aisle takes a customer 6 minutes when milk is far away, and 3 minutes when milk sits next to bread. With checkout at 2 minutes, each customer occupies the store for 8 minutes versus 5 minutes. At 60 open minutes per hour, the store serves $60/8 \approx 7.5$ customers per hour in the slow layout versus $60/5 = 12$ customers per hour in the fast layout — a gain of roughly 60% in customer throughput, before counting the extra milk sales themselves. Sense-check: the arithmetic is a model, but the mechanism is exactly what the lecture describes — shorter dwell time per shopper means more shoppers served per hour.

So one idea behind shelf management is to help customers find items quickly, buy quickly, and leave quickly, so the store can serve more people.

Pitfalls

Confusing the two directions: the goal is to place frequently co-purchased items together. Placing two unrelated best-sellers together does not create a co-purchase pattern — it just crowds the aisle.
Assuming every customer wants the shortcut: the fast-path design serves shoppers who know what they need; it says nothing about browsers, and stores usually mix the two zones deliberately.
Reading one store's pattern as universal: bread and milk may be adjacent in one city and not another; the layout should follow the store's own log, not a competitor's.

Recap: Shelf management uses the transaction log to find items bought together and places them side by side, so the store serves each customer faster and serves more customers per hour. Note the contrast already forming: this design minimizes walking — the next application flips the idea around and maximizes it.

Real-world: this is why supermarket layouts and end-of-aisle displays are designed from purchase data rather than intuition. Retail chains and store-planning teams routinely mine loyalty-card and checkout data before redesigning aisles, placing impulse items next to their frequent companions and using end caps to push slow movers past high-traffic locations.

11.4 Airport Terminal Management

11.4.1 The Maximum-Distance Design

Here is a different way to manage the same resource: space. After security check-in, a flyer enters the waiting area with some buffer time — say an hour — before reaching the boarding gate. The space between the security check-in gate and the boarding gate belongs to the airport authority, and they want to maximize the revenue it produces. Their trick: put a lot of shops in the middle, and design the airport so that there is a maximum distance between the check-in gate and the boarding gate. The flyer is forced to walk through all the shops to reach the destination.

Intuition — the captive audience: The flyer has an hour of time that cannot be spent anywhere else. The airport designs the walk so that the flyer's only available spending of that hour is inside the shops. This is the opposite of the supermarket: the supermarket rushes the shopper out; the airport stretches the traveler in. Both are the same skill — managing space using a model of what the customer does with their time — applied to opposite goals.

11.4.2 Why Walking Past Shops Pays

If you cross many shops, there is a high chance you look into one, find something interesting, and buy it. With this design the airport can fit many shops into the same space and earn more revenue from it.

Worked mini-example: Suppose an airport corridor with shops between two gates earns, on average, ₹40 per passing passenger in duty-free and food sales, and 5000 passengers walk the corridor daily. That is 5000 × ₹40 = ₹2,00,000 per day in corridor revenue. If the gates were placed 10 metres apart, most passengers would skip the shops entirely and the per-passenger spend would drop to near zero — but the fixed costs (staff, floorspace) stay the same. The design decision is then not "how much shopping space do we need?" but "how much walking are we willing to force, and what revenue does each extra metre of corridor produce?" Sense-check: the estimate depends on assumptions about average spend, but it shows why airports treat the walk itself as the revenue engine.

Notice the contrast with the supermarket: the supermarket design minimizes walking (bought-together items adjacent, fast exit), while the airport design maximizes walking (gates at opposite ends, shops in between). Both are space-management strategies derived from understanding customer behavior.

Design choice	Supermarket	Airport
Walking goal	Minimize	Maximize
Reason	Serve more customers per hour	Sell more per passenger
Pattern used	Items bought together	Time that must be spent walking
Who profits	Store throughput	Corridor retail revenue

When to pick which: minimize walking when the store's revenue comes from many quick visits; maximize walking when the revenue comes from a captive audience that must pass through the space anyway.

Scope: This design works only when the passenger genuinely has buffer time. On short-haul flights with tight schedules, or in airports where gates are reached by bus, the corridor may be walked in minutes — the "hour of shopping time" assumption fails, and the retail corridor earns far less. The strategy is a bet on captive time, not on walking in itself.

Recap: Airport terminal management runs the supermarket idea in reverse: instead of arranging items so the shopper leaves quickly, the airport arranges the journey so the traveler spends the maximum time among shops. Same transaction-log style of customer analysis, opposite layout goal. Next, the module shows that the same structure even explains how advertising works.

Real-world: the long retail corridors between security and boarding gates at modern airports are exactly this design. Terminal planners and airport retailers model passenger dwell time, flow paths, and per-square-metre retail yields the same way the supermarket mines its transaction log — a pattern-based model of customer movement and spending.

11.5 Marketing and Sales Promotion: Confidence as a Brand Tool

11.5.1 Associating Products with Everyday Feelings

Advertising builds associations, and the structure of the association is the same structure rule mining discovers. We get thirsty many times a day; when we are thirsty we want something cold — Thanda, as the tagline says. If a brand can associate that Thanda feeling with itself, the brand is indirectly promoting itself: whenever the feeling comes to mind, the brand comes to mind. The classic tagline works exactly this way: "Thanda means Coca Cola". Similarly, "Things go better with Coca Cola" associates better taste with the drink — when you are eating something like a samosa and want to improve the taste, the first thing that comes to mind is to buy a Coke as well.

Another tagline associates a different everyday feeling with Mountain Dew: "Dar" — a fear-related feeling — linked to the drink. (The full campaign slogan is "Darr ke aage jeet hai", "beyond fear lies victory": the brand pairs the everyday emotion of fear, dar, with itself, exactly as the Thanda tagline pairs thirst with Coca Cola. The lecture referred to the fear feeling itself as "Dar".) It is a clever marketing strategy: take a feeling every customer has every day, attach a product to it, and repeat the message until the association is strong.

Intuition — the mental shortcut: The mind retrieves associations automatically: "Thanda" fires "Coca Cola", "dar" fires "Mountain Dew". The advertiser's job is to build and strengthen that automatic link by repetition. Notice the shared shape with rule mining: the feeling is the left-hand side, the brand is the right-hand side, and every airing of the ad is one more counted co-occurrence. The ad is, in effect, planting transactions into the customer's memory log.

11.5.2 The Informal Idea of Confidence

The reason advertising works this way connects to a core measure of rule mining: confidence. Confidence means: if the left-hand side happens, what is the chance that the right-hand side will also happen? If product A is sold, what is the chance that B will also be sold? Suppose the confidence of a rule is 100% — if A is sold, there is a 100% chance B will also be sold.

Confidence, informally: for the association "feeling $\to$ brand", confidence is the chance that the brand comes to mind when the feeling appears. Formally it will be defined as a fraction of counts:

$confidence (A \to B) = \frac{how often A and B happen together}{how often A happens}$

The advertiser is literally trying to raise this confidence: show the tagline "Thanda means Coca Cola" 100 times during an IPL match, and the bond between the Thanda feeling and Coca Cola gets stronger. Every repetition of the advertisement improves the confidence of the association, exactly the quantity association rule mining measures. This is the informal preview; the formal definition of confidence appears later in this session.

Worked mini-example: Imagine tracking brand recall across a campaign. Before the campaign, among 100 thirsty moments, the thought "Coca Cola" arrives in 30 — an informal confidence of $30/100 = 0.3$ . After a season of repeated taglines, suppose 70 of the next 100 thirsty moments trigger the brand — confidence $70/100 = 0.7$ . The campaign more than doubled the strength of the association. In rule-mining terms: the "rule" thirst $\to$ Coca Cola gained confidence because the advertiser manufactured more co-occurrences of the two "items". Sense-check: recall numbers here are illustrative, but the direction — repetition raises association strength — is exactly the effect advertising budgets chase.

Pitfalls

Confusing confidence with frequency: a strong association is not the same as a frequent one. A brand could fire on 99% of the right moments yet still be forgotten overall if the moments themselves are rare — confidence and support measure different things (sections 11.10 and 11.13).
Forgetting that association is two-way: if "Thanda means Coca Cola" raises confidence in one direction, the reverse association ("Coca Cola means Thanda") is a separate rule with its own strength; advertisers exploit whichever direction helps.
Believing repetition alone guarantees sales: advertising raises association strength; converting that association into a purchase still depends on price, availability, and competition.

Recap: Advertising is association mining by other means: it manufactures co-occurrences between an everyday feeling and a brand, which raises the informal confidence of the rule feeling $\to$ brand. The same quantity — confidence — is what association rule mining measures from transaction data. Next, the module applies the pattern logic to spare-parts stocking.

Real-world: Coca Cola's taglines, Mountain Dew's campaigns, and ad repetition during cricket matches are live experiments in raising association confidence. Brand-equity research, ad recall surveys, and viewership-based media planning all measure exactly this association strength, and the same co-occurrence logic appears in influencer marketing and search-ad retargeting.

11.6 Inventory Management

11.6.1 Stocking Spare Parts by Location

Consider a company like IFB that both sells appliances and manages product repair. Repair means service centers, and each service center must carry an adequate number of spare parts. With thousands of service centers across the country, the company wants to stock parts adequately at each location: identify which item goes bad at a particular location and stock more copies of that spare part there. The overall cost of service then goes down.

The pattern: this is association mining with a place as the left-hand side. The "items" in the transaction are not products but events — a filter failure, a blown fuse — and the transactions are service-center repair records. The rule takes the form

$location \to failed part$

Stocking the spare part in proportion to the rule's strength at that location cuts two costs at once: customers wait less because the part is already on the shelf, and the company avoids shipping parts from a central warehouse to wherever they run out.

11.6.2 Location-Specific Failure Associations

The associations come from the data. Suppose that in a place like Delhi, some filter goes bad again and again because of water quality or another local issue. Once that association is found — Delhi, filters failing — the company stocks more filters at Delhi service centers than anywhere else in the country. Or suppose that because of electricity fluctuation or power fluctuation, a lot of electronic circuitry and fuses blow in a particular part of the country, say Chennai. Then Chennai service centers get more fuses and electrical items than Delhi centers do. Same product, different failure geography, different stock.

Worked mini-example: Suppose the Delhi region runs 20 service centers with 1000 repair tickets in a quarter. Of these, 240 tickets mention a failed filter — Delhi's filter-failure rate is $240/1000 = 24%$ . Chennai, over the same quarter, logs 1000 tickets of which 60 mention a filter but 180 mention fuses or blown circuitry — 18% fuse-related versus Delhi's 6%. If each center's quarterly stock of filters is set by the local rate, Delhi centers carry four times the filters of Chennai centers, and Chennai carries three times the fuses of Delhi. The rule "Delhi $\to$ filter failure" has high local strength; "Chennai $\to$ fuse failure" has high local strength; each stockroom follows its own rules. Sense-check: the numbers are illustrative, but the mechanism — stock proportional to the local failure association — is how location-based spare-part planning actually works.

Scope: The association is only as good as the data behind it. If the log does not record the failure reason (water quality, voltage), the company can see where parts fail but not why, and the stock plan can only react. Also, a seasonal or temporary factor (a heat wave, a construction-driven voltage dip) can inflate a local association; the stock plan should be reviewed against the current quarter, not frozen from one historical analysis.

Recap: Inventory management uses association rules whose left-hand side is a location: where a part keeps failing, that part is stocked more. The same analysis framework — find the association, act on it — now has appeared in store layout, airport design, advertising, and stocking, which shows how general the pattern logic is. Next, the module shows the same machinery at work inside a search box.

Real-world: IFB and similar manufacturers run exactly this location-based failure analysis for spare-part planning. Appliance, automotive, and telecom companies maintain repair-history databases and mine them for location-part associations, and the same idea appears in predictive-maintenance programs that use failure co-occurrence to pre-position parts.

11.7 Next-Word Prediction and Other Applications

Association rule mining also shows up in the Google search box. While you type, the engine predicts the word you are going to write next. The engine has found associations between word pairs together with a certain confidence, and based on that confidence it predicts the next word. The classroom example: typing "good" leads the engine to predict "morning" because the pair has appeared together often enough with strong confidence. Whatever word you type, the engine is applying the same logic: which word follows this one most confidently?

The word-pair rule: treat each typed word as an item and each sentence (or search query) as a transaction. The engine counts co-occurrences — how often "morning" appears right after "good" — and ranks candidate follow-ups by their confidence. The rule being evaluated for every keystroke is

$word_{1} \to word_{2}$

with confidence "among all the times word $_{1}$ appeared, in what fraction did word $_{2}$ follow?". The engine shows the word whose confidence is highest. This is the same support-and-confidence machinery that evaluates diaper $\to$ beer, applied to text.

Worked mini-example: Suppose the engine's log of past queries contains 10,000 occurrences of the word "good". In 8,000 of them, "morning" follows immediately. The confidence of the pair is $8000/10000 = 0.8 = 80%$ . If "goodbye" follows in only 1,500 of the 10,000 cases, its confidence is 15%. When you type "good", the engine ranks "morning" (80%) far above "goodbye" (15%) and predicts "morning" — the item with the strongest association to what you just typed. Sense-check: this matches experience — autocomplete does not predict every word that can follow, only the ones that do follow with high confidence.

11.7.2 Plagiarism Detection and Time-Series Chains

The same machinery supports plagiarism detection and time-series analysis. In time series we get triggering events: A leads to B, B leads to C, C leads to D, and so on:

$A \to B \to C \to D$

Intuition — a chain of dominoes: a single rule $A \to B$ is one domino; a time series is a row of dominoes. Plagiarism detection looks for chains of unusually matched text fragments (the same ordered sequence appearing in two documents); time-series analysis looks for chains of triggering events in data ordered by time. In both cases the discovery target is the same structure — a chain — and the data lets us find and act on it.

This chain idea is exactly what the next section's case study is about — one event sets off the next, and the data lets us find and act on the chain.

Pitfalls

Confusing co-occurrence order with cause: "B often follows A" says nothing about A causing B — the chain may be driven by a third factor that triggers both.
Forgetting the denominator: a pair can look strong because the first word is rare. Next-word prediction ranks by confidence, but in general you must check support too — a rule with 100% confidence but one occurrence is worthless (section 11.19 returns to exactly this point).
Expecting fixed chains: real sequences are noisy; $A \to B \to C \to D$ is the clean pattern, while the data is full of broken and missing links that must be counted, not assumed away.

Recap: Next-word prediction, plagiarism detection, and time-series analysis all use the same structure — an association chain $A \to B \to C \to D$ measured by confidence — applied to words, text fragments, and ordered events. Next, a famous case study shows a chain with very expensive consequences: the bird strike.

Real-world: next-word prediction is now part of every search engine, keyboard, and autocomplete feature. The same co-occurrence machinery runs behind search suggestions, spam filters, and fraud-pipeline event chain analysis, where one triggered event flags the next in line.

11.8 The Bird-Strike Case Study: Breaking a Failure Chain

11.8.1 The Cascade: Bird to Burned Engine

Aircraft typically have two engines, and every now and then there is news of a bird strike forcing an emergency landing. Bird strike means a bird has entered the engine during takeoff, landing, or flight. This analysis was done heavily, and it helped Boeing and other manufacturers like Airbus improve their engines.

The found chain works like this. The engine has blades. When the aircraft is moving and a bird hits any of the blades, it typically leads to a fracture in the blade. Once a blade is fractured, it breaks and — since the engine sucks in air — the detached blade is sucked inside the engine. The broken blade blocks the airflow and the exhaust: air enters from the front but cannot leave through the exhaust. With air blocked and fuel still being injected, the engine overheats, and overheating leads to the burning and complete destruction of the engine:

$bird hits blade \to blade fracture \to blocked airflow \to overheating \to engine destroyed$

Worked example — the cascade as a chain of events: Read the chain left to right as a sequence of triggers, each link being a small association with high confidence:

bird hits blade — a bird enters the engine during takeoff, landing, or flight;
blade fracture — the impact fractures the blade; with engine blades spinning at high speed, the fracture propagates and the blade comes apart;
blocked airflow — the detached blade is sucked deeper into the engine and blocks the airflow path; air enters the front but can no longer leave through the exhaust;
overheating — with airflow blocked but fuel still injected, combustion cannot exhaust properly and temperatures climb;
engine destroyed — sustained overheating leads to burning and complete destruction of the engine.

That is why a bird strike typically ends in an emergency landing — one small failure triggers a cascade, and they wanted to stop the cascade before the very expensive engine was lost. Sense-check of the chain logic: each link is a plausible high-confidence association found in the failure records; the analysis succeeded not by predicting a single bird strike, but by exposing the sequence of events that follows one.

Why the chain view matters: the danger was not the bird alone — it was that each link had high confidence, so a single initial failure cascades reliably through the whole engine. When failure events form a chain like $A \to B \to C \to D$ , stopping one early link stops the whole chain. If the events were independent, fixing any one link would do little; the chain structure is precisely what makes targeted fixes powerful.

11.8.2 Fixing Part A and Part C

The first idea was the simplest: put a mesh, a jali, on the front face of the engine, so the bird hits the mesh and never enters the engine. They actually tried it. The problem: the mesh disrupted the normal airflow of the engine, so it was not feasible.

Intuition — why the fix must be surgical: the front mesh failed because it attacked the chain at the wrong cost: it blocked the bird but also blocked the engine's working airflow, trading one failure mode for another. The lesson generalizes: a chain can only be broken at links where the fix does not damage the normal operation of the system. The successful fixes attacked the first and third links instead, where the intervention is local.

The solutions that were adopted attack the chain at its first and third links. First, they made the blades much harder so they do not get torn or broken down. Second, even if a blade breaks, they put meshes or filters in the middle of the engine so the broken blade is stopped mid-engine and cannot reach the back and block the airflow. They fixed part A (the blade breakage) and part C (the blockage) so that the chain A to B to C to D is never completed, and the engine is saved.

Recap: The bird-strike study is association mining on failure events: find the chain $A \to B \to C \to D$ , then break it at the links where a fix is cheap and safe — harder blades stop part A, mid-engine containment stops part C. The association rule mining view is what made the whole chain visible in the first place: find the sequence, then break it at the right links. With all the applications in place, the module now turns to the formal vocabulary and the mathematics.

Real-world: engine design changes at Boeing and Airbus — blade material and mid-engine containment — trace back to this kind of failure-chain analysis. The same chain-breaking logic is used today in airline safety investigations, industrial predictive maintenance, and cybersecurity, where one event in a kill chain is neutralized to protect the system behind it.

11.9 Items, Itemsets, and k-Itemsets

11.9.1 Item and Itemset

Now the formal vocabulary. An item is any particular product in a shop: soap is an item, RIN soap is an item, Men+ Mix soap is an item. A supermarket holds multiple — even thousands — of items. When a customer puts items into his basket, the collection of items is called an itemset. Formally: an itemset is a collection of one or more items.

Definitions

An item (written $i$ ) is a single product or attribute value that appears in a transaction: soap, milk, bread, diaper.
An itemset (written $X$ or ${i_{1}, i_{2}, \dots, i_{k}}$ ) is a collection of one or more items taken from the set of all items $I$ . The basket in the customer's hand at checkout is an itemset recorded in the transaction log.

An itemset is a set in the mathematical sense: order does not matter and duplicates are not counted. The basket {milk, bread} is the same itemset as {bread, milk}.

Worked example: In a store selling items ${) so a p, mi l k, b r e a d, d ia p er, b eer, e g g (}$ , a customer who picks soap, milk and bread contributes the itemset {soap, milk, bread}. A second customer who picks milk and bread contributes the itemset {milk, bread}. Both are itemsets; the first has more items. The set of all possible itemsets over 6 items is large — $2^{6} = 64$ including the empty basket — which is why section 11.14 will care about counting them.

11.9.2 The k-Itemset

A k-itemset is an itemset with cardinality k — the number of items in the set is exactly k. It might be three, it might be four, it might be fifty. When we say a three-item set, the set must have exactly three items — not two, not four. When we say a five-item set, it must have exactly five items — not four, not three, not seven, not eight. Cardinality is the word for "how many items this set holds".

Intuition — why "exactly k" matters: the letter $k$ is a label on the size, not a choice the store makes. A 2-itemset is a pair of items, a 3-itemset is a triple, and so on. Later, the mining algorithm will grow itemsets one $k$ at a time — first all 1-itemsets, then all 2-itemsets, then all 3-itemsets — and each level's identity depends on this exact cardinality meaning.

11.9.3 Student Questions on Cardinality

Q: Is it a set of items?

A: Yes — an itemset is a set of products. When I say a three-item set, the set should have cardinality three: only three items, not two, not four. If I say five items, the set should have five items, nothing else. The number in "k-itemset" is exact.

Exam note: know the definitions cold: item, itemset, k-itemset, and cardinality. A common exam question gives a basket and asks for its cardinality, or asks what "3-itemset" means — the answer is always "exactly three items".

Recap: The vocabulary is small but strict: an item is one product, an itemset is a collection of one or more items, and a k-itemset is an itemset whose cardinality is exactly $k$ . Next, the first real measure of an itemset: how often it appears in the log.

11.10 Support Count and Support

11.10.1 Support Count

Support count answers: how many times was this itemset present in the transaction log? Suppose we are trying to find the support count of the itemset {milk, bread, juice}. We scan the log and count every transaction that contains milk, bread and juice together. In the classroom example the itemset {milk, bread, juice} appears in two transactions, so its support count is 2. (While walking through the log the names "juice" and "diaper" were momentarily mixed, but the count itself — two transactions containing the full itemset — was restated consistently.)

Definitions

The support count of an itemset $X$ , written $σ (X)$ (the Greek letter sigma, pronounced "sigma"), is the number of transactions in the log that contain every item in $X$ . In the example, $σ ({milk, bread, juice}) = 2$ .
The support of $X$ , written $support (X)$ , is that count divided by the total number of transactions — a fraction, not a raw count.

Support count is absolute ("how many receipts have this basket?"), support is relative ("what share of all receipts?").

Worked example with a real log. Suppose the transaction log has five transactions:

Transaction	Items
1	milk, bread, juice
2	bread, butter, egg
3	milk, bread, juice
4	bread, jam
5	milk, tea

The support count of {milk, bread, juice}: scan each transaction and ask "does it contain all three items?" Transaction 1 has milk, bread and juice — yes. Transaction 2 has bread but no milk and no juice — no. Transaction 3 — yes. Transactions 4 and 5 — no. Total: $σ ({milk, bread, juice}) = 2$ . Sense-check: only two receipts in the pile ever contained the full triple, matching the classroom count.

11.10.2 Support as a Fraction

Support is the fraction of transactions that contain the itemset. It is the support count divided by the number of transactions in the transaction log:

$support (X) = \frac{support count ( X )}{N}$

where $X$ is the itemset and $N$ is the number of transactions in the log. In the example, the support count is 2 and the log has 5 transactions, so:

$support (X) = \frac{2}{5} = 0.4 = 40%$

Intuition — why we divide: the same itemset can be bought 50 times in a big store and 2 times in a small store. The raw counts look incomparable, but the shares may be identical. Support is the measure that lets a 2-out-of-5 log and a 200-out-of-500 log speak the same language: $2/5 = 200/500 = 40%$ . Think of it as normalizing the count to "out of every 100 transactions".

For a rule $X \to Y$ , support can be rephrased as the fraction of transactions that contain both X and Y — the union of the two sides, ${X \cup Y}$ . Support asks: how often does the whole rule happen?

Pitfalls

Confusing support count with support: $σ (X) = 2$ and $support (X) = 40%$ are different numbers with different meanings — an absolute count versus a relative share. Exam answers must state which one is being computed.
Forgetting the denominator changes: with 5 transactions the same count of 2 gives 40%; with 10 transactions it gives 20%. Support only means something when the denominator $N$ is known.
Counting partial baskets: a transaction contributes to $σ (X)$ only if it contains all items of $X$ . A transaction with milk and bread but no juice does not count toward {milk, bread, juice}.

Recap: Support count $σ (X)$ is how many transactions contain the whole itemset; support divides that by $N$ , the number of transactions, to get a share. The same two ideas — count first, then normalize — return at section 11.13 in support of rules and confidence. Next: which itemsets are worth mining at all — the frequent ones.

11.11 Frequent Itemsets, Subsequences, and Substructures

11.11.1 Frequent Itemsets and the Tunable Threshold

A frequent itemset is a group of items purchased many times — purchased frequently. How do we define "frequently"? It is a tunable threshold that we choose.

Definition. An itemset $X$ is frequent when its support (or support count) reaches a chosen threshold, called the minimum support. The threshold is a knob the analyst turns: the same log can yield many frequent itemsets with a low knob and few with a high one. No value is correct in the abstract — the threshold depends on the store, the problem, and the goal.

Worked example. Suppose we say: any group of items purchased more than five times in the log counts as frequent. If items A, B and C are purchased more than five times, the itemset {A, B, C} is frequent. If another group XYZ is purchased 10 times, it is frequent too. If DEF is purchased 50 times, it is also frequent, because the threshold we set is five. All three groups clear the same bar — 10 and 50 are both above 5 — and all three are treated identically as frequent. Sense-check: notice the threshold is strict, "more than five"; an itemset bought exactly five times would not make the cut under this particular setting.

The threshold is a knob that depends on the use case — different stores, different problems, different knobs.

11.11.2 Frequent Subsequences

Frequent patterns are not limited to sets. We first find a sequence — A leads to B leads to C leads to D. Once we have a sequence, a subsequence that is frequent in nature is called a frequent subsequence.

Intuition — the partial recipe: a full recipe is a sequence of steps; a frequent subsequence is a chunk of the recipe that shows up again and again. In sales, the full sequence PC $\to$ operating system $\to$ antivirus software may be rare, but the shorter chunk PC $\to$ OS can occur constantly. The complete sequence may or may not be frequent, but a particular subsequence — PC followed by OS — can be frequent on its own. Frequent subsequence work is what powers sequence mining over ordered data.

11.11.3 Frequent Substructures

The same idea extends to structures. Suppose we have built some structure — a graph, a molecule, a tree. The part of the structure that happens again and again is called a frequent substructure.

Pattern family	Data type	Recurring unit	Example
Frequent itemset	Unordered set of items	Group of items	{milk, bread, juice}
Frequent subsequence	Ordered sequence	Contiguous (or embedded) run	PC followed by OS
Frequent substructure	Graph, molecule, tree	Recurring subgraph	A benzene ring appearing in many molecules

When to pick which: if the data has no order, use itemsets; if order matters, use subsequences; if the objects are graphs or molecules, use substructures.

Recap: The family is: frequent itemsets for unordered sets of items, frequent subsequences for ordered sequences, and frequent substructures for structured objects. In every case "frequent" means "appears at or above a threshold we choose". The next section explains why hunting these recurring patterns at all is worth the effort.

Real-world: frequent subsequence mining drives web-session analysis (page visit orders), process mining, and DNA motif discovery; frequent substructure mining is used in cheminformatics to find recurring molecular fragments linked to drug activity and in graph analytics to find repeated community structures.

11.12 Why Frequent Patterns Matter

11.12.1 Relationships Between Items

Finding frequent patterns gives us the relationship between items — sale of A leads to sale of B. That same pattern, expressed as a rule, is what market basket analysis, shelf management, and the other applications are built on.

Two roles of the same pattern. First, a frequent pattern is an end in itself: it tells the business which item pairs, triples, or sequences actually co-occur, and every application seen so far — bundling, shelf adjacency, airport retail, advertising, spare-part stocking — is that pattern converted into an action. Second, the pattern is raw material: once a group of items is known to be frequent, the rules inside that group are the ones worth evaluating (section 11.13).

11.12.2 Feeding Other Data Mining Tasks

There is a second, less obvious use. Pattern analysis can improve classification, clustering, and other data mining tasks. In some research papers, to solve a classification problem, the authors first run association rule mining to find patterns and then build a classification model on the basis of that analysis. We could build the classification model directly, but the association analysis finds patterns that improve the performance of the classification model. So association rule mining also plays a supporting role: it is a search for recurrent relationships in a given dataset, and those relationships feed the other algorithms.

Worked example — the pattern-first pipeline. Consider a fraud-detection problem. Instead of throwing all features at a classifier directly, the pipeline first mines association rules from past fraud cases and finds that {small top-up, immediate withdrawal, new device} $\to$ {fraud} recurs with high confidence. The model then uses the presence of that co-occurring group as a feature, and detection improves because the association has isolated a combination the raw features alone did not surface. Sense-check: the pattern does not replace the classifier — it feeds it; that is the supporting role described in the lecture.

Scope: the supporting role only helps when the data actually contains recurrent structure. In a dataset with weak co-occurrence, mined patterns are noise, and a pattern-first pipeline adds complexity without gain. The pattern stage is also not a free lunch: mining over large logs costs computation (sections 11.14–11.16), so it is worth doing only when the recurring relationships are expected to carry signal.

Recap: Frequent patterns matter twice: they are the rules behind every business application, and they are a feature factory that can improve classification and clustering models built on top of them. That is why the rest of the module is worth the machinery — first, how to evaluate a rule; then, how to find the frequent groups at all. The next section defines the rule and its two measures, support and confidence.

Real-world: pattern-first classification pipelines appear throughout modern research in retail analytics, fraud detection, and biomedical data. Fraud systems mine co-occurrence groups among transaction features, and biomedical pipelines mine frequent substructures before training classifiers on compound activity.

11.13 Association Rules: Form and Evaluation

11.13.1 The Rule Form

An association rule has the form:

$X \to Y$

read as "X leads to Y", "X tends to Y", or "X arrow Y". Here $X$ is the left-hand side (LHS) — the items that must be present — and $Y$ is the right-hand side (RHS), the item we are asserting follows. Example: milk and diaper lead to the sale of butter — if a customer is buying milk and diaper, he is also buying butter.

Anatomy of a rule. The LHS $X$ and the RHS $Y$ are both itemsets, and in the rules studied here they are disjoint — no item appears on both sides. The rule $X \to Y$ asserts a conditional dependency: given that a transaction contains $X$ , it tends to contain $Y$ as well. The arrow is not an implication in logic; it is a summary of observed co-occurrence that we must now evaluate. That evaluation is done with two measures, support and confidence — the only two the session focuses on, though other measures exist (lift, conviction, and others appear in later modules).

Worked example — reading a rule. The rule {milk, diaper} $\to$ {butter} says: whenever a basket contains milk and diaper, expect butter in the same basket. Its LHS is the pair {milk, diaper}, its RHS is {butter}. The rule says nothing about baskets with only milk, or only diaper — only about baskets containing the full LHS. Sense-check: this matches the mart example's phrasing "if a customer is buying milk and diaper, he is also buying butter."

11.13.2 Support of a Rule

The support of a rule $X \to Y$ is the fraction of transactions that contain both X and Y — the same support definition as for itemsets, applied to the union of the two sides:

$support (X \to Y) = \frac{σ ( X \cup Y )}{N}$

where $σ (X \cup Y)$ is the support count of the itemset made of X plus Y, and $N$ is the number of transactions in the transaction database. Support asks: how often does the whole rule happen?

Intuition: support is the rule's reach. It counts the transactions where the full pattern — left side and right side together — actually occurred, then normalizes by the total log size. A rule can have perfect confidence but tiny support, which is why both numbers are always reported together. Support behaves exactly like the itemset support of section 11.10, with the itemset replaced by $X \cup Y$ .

11.13.3 Confidence of a Rule

Confidence is conditional: if A has happened, what is the chance that B will also happen? Suppose the confidence is 100% — if A happens, there is a 100% chance B also happens. Suppose it is 50% — if A happens, B happens half the time. The formula:

$confidence (X \to Y) = \frac{σ ( X \cup Y )}{σ ( X )}$

where $σ (X \cup Y)$ is the support count of the full itemset (both sides together) and $σ (X)$ is the support count of the left-hand side alone. Confidence divides by how often the LHS triggers, not by the total transactions — that is the difference from support.

Confidence as a conditional probability. Confidence is the empirical version of "probability of Y given X":

$confidence (X \to Y) = \frac{σ ( X \cup Y )}{σ ( X )} = P (Y ∣ X)$

Read it as a share: among the transactions where $X$ happens, what fraction also contains $Y$ ? This is why the denominator is $σ (X)$ and not $N$ — we are conditioning on the LHS, not on the whole log. Standard texts (e.g., the association-analysis chapter of the reference text) define it identically as the conditional probability $P (Y ∣ X)$ computed from support counts.

Measure	Numerator	Denominator	Question it answers
$support (X \to Y)$	$σ (X \cup Y)$	$N$	How common is the full rule in the log?
$confidence (X \to Y)$	$σ (X \cup Y)$	$σ (X)$	Among LHS transactions, how often does the RHS follow?

When to use which: support decides whether the rule happens often enough to matter; confidence decides whether the LHS reliably implies the RHS. The mining process uses both (section 11.14).

11.13.4 Worked Example: {Milk, Diaper} → Butter

Consider a transaction log of five transactions, and the rule {milk, diaper} → butter. To make the counts fully explicit, here is a log consistent with every number stated in the lecture: the full itemset appears in 2 of 5 transactions and the LHS appears in 3.

Transaction	Items
1	milk, diaper, butter
2	milk, diaper
3	milk, diaper, butter
4	bread, jam
5	bread, butter

Support of the rule. The itemset {milk, diaper, butter} is present in two of the five transactions (transactions 1 and 3):

$support ({milk, diaper} \to butter) = \frac{σ ({ milk, diaper, butter })}{N} = \frac{2}{5} = 0.4 = 40%$

So milk, diaper and butter are purchased together 40% of the time.

Confidence of the rule. The LHS {milk, diaper} appears in three transactions (1, 2, 3), and in two of those three the RHS butter is also present (1 and 3):

$confidence ({milk, diaper} \to butter) = \frac{σ ({ milk, diaper, butter })}{σ ({ milk, diaper })} = \frac{2}{3} \approx 0.67 = 67%$

Interpretation: if milk and diaper are purchased, there is a 67% chance that butter will also be purchased. If butter had been present in the third LHS transaction as well, the confidence would have been $3/3 = 100%$ . Sense-check against the log: transaction 2 has milk and diaper but no butter — that single "miss" is exactly what keeps the confidence at 67% instead of 100%.

Q: Someone in the chat said the confidence is 2 divided by 3, so 67%.

A: Exactly right. The LHS milk and diaper triggers three times in the log; only two of those transactions also contain butter. Two divided by three is why the confidence is 67%. (The slide read the value as "0.6" in one spot, but $2/3 = 0.666 \dots$ rounds to 0.67, and the discussion used 67%.)

11.13.5 Worked Example: {Milk, Butter} → Diaper

Now evaluate the second rule from the slide, {milk, butter} → diaper. Its support is 0.4: the three items milk, butter and diaper are sold together as a basket 40% of the time. Its confidence is 1:

Confidence of {milk, butter} → diaper.

$confidence ({milk, butter} \to diaper) = \frac{σ ({ milk, butter, diaper })}{σ ({ milk, butter })} = \frac{2}{2} = 1 = 100%$

The LHS {milk, butter} appears in two transactions (1 and 3 in the log above), and both of those transactions also contain diaper. So: if milk and butter are sold, there is a 100% chance that diaper will also be sold. The slide also listed rules like {diaper, butter} → milk and others; each rule in the list gets the same two-number evaluation — a support out of $N$ , a confidence out of the LHS count.

Comparison of the two rules: both share the same full itemset {milk, diaper, butter}, so both have support 0.4. They differ in confidence because their denominators differ: the LHS {milk, diaper} occurs 3 times (2 of them with butter → 67%), while the LHS {milk, butter} occurs 2 times (both with diaper → 100%). One pair, two directions, two different strengths — the direction of a rule matters.

11.13.6 The Bread-Butter Slip

Mid-example, the counting was momentarily confused between bread and butter:

Q: Why did the rule suddenly talk about bread? The rule was about butter.

A: That was a slip between the two words — bread and butter sound similar in this example. The rule is {milk, diaper} → butter. The numbers stay exactly the same: support 0.4 and confidence 0.67. The counting was redone from the log so nothing in the evaluation changes.

This is worth remembering for study purposes: keep the item names and the counts separate in your own work — the numbers in an evaluation only mean something when they are attached to the correct items.

Pitfalls

Swapping the item names (the bread–butter slip): the same numbers attached to the wrong items produce a "correct" arithmetic with a wrong meaning. Always re-read the rule after computing.
Using $N$ in the confidence denominator: confidence divides by $σ (X)$ , the LHS count — not by the total number of transactions. Using $N$ gives support, not confidence.
Trusting confidence alone: a rule can have high confidence yet be uninteresting if its RHS is nearly always present anyway (e.g., {milk} $\to$ {bread} when bread appears in most baskets). Support and confidence together, plus the thresholds of section 11.14, keep the interesting rules.

Exam note: the rule form is $X \to Y$ with LHS $X$ and RHS $Y$ ; support is $σ (X \cup Y) / N$ , confidence is $σ (X \cup Y) / σ (X)$ . Expect a question that gives a small log and asks for both numbers on a given rule — and remember which denominator belongs to which measure.

Recap: A rule $X \to Y$ is evaluated by support (how often the whole rule occurs, out of $N$ ) and confidence (how often the RHS follows the LHS, out of $σ (X)$ ). The worked pair {milk, diaper} → butter (support 0.4, confidence 0.67) and {milk, butter} → diaper (support 0.4, confidence 1) showed the same itemset producing different rules in different directions. Next: the thresholds that decide which rules survive.

11.14 Minimum Support and Minimum Confidence

11.14.1 The Two Thresholds

Two more definitions complete the evaluation picture: min support and min confidence. For an itemset, to call it frequent we compare its support against a threshold called minimum support. If the itemset's support is equal to or above minimum support, it is frequent; otherwise it is not. For rules, we compare confidence against minimum confidence.

The two bars. An itemset is frequent when $support (X) \geq minsup$ . A rule $X \to Y$ is strong (kept) when $confidence (X \to Y) \geq minconf$ . Both thresholds are chosen before mining; the first controls how many itemsets survive step one, the second controls how many rules survive step two. In the classroom example the generated rules had confidence ranging from 0.5 to 1. With a minimum confidence of 0.6, the low-confidence rules get discarded, and only the rules above the bar — the four top rules shown — are considered.

11.14.2 Why Thresholds Exist: The 2^D Explosion

Why do we need these thresholds at all? Think about how many baskets are possible in a mall. If you sell D distinct items, the number of unique itemsets that can possibly exist is:

$2^{D}$

Take two products, A and B. The unique baskets are {A}, {B}, {A, B}, and the empty basket — four baskets, which is $2^{2}$ . If we exclude the empty basket we get $2^{D} - 1$ , i.e. three baskets; the difference of one does not matter much here. With three items, the number of possible itemsets is $2^{3} = 8$ .

Worked example — the explosion, item by item.

Distinct items $D$	Possible itemsets $2^{D}$
2	4
3	8
5	32
10	1024
50	about $1 0^{15}$
1000	about $1 0^{301}$

Now a real mall sells thousands of items, so the theoretically possible itemsets number $2^{1000}$ — an astronomically large count. Sense-check of the pattern: each new item doubles the count of possible baskets, because each existing basket can either include the new item or not. Doubling on top of doubling is exponential growth, and exponential growth outruns any counting plan quickly.

The brute-force plan — generate every possible itemset, look each one up in the transaction log, count its frequency, and only then mine rules — becomes computationally expensive at that scale. We need thresholds to cut the search space, and we need smarter generation than brute force. That is the motivation for everything that follows.

Scope: the $2^{D}$ count is the theoretical search space — every combination that could exist. The thresholds exist precisely because the search space is far larger than the log; most of those combinations never occur, and the ones that occur rarely are not worth rules. If the number of distinct items were tiny, brute force would be fine and thresholds would be unnecessary — they are a response to $D$ being in the thousands.

11.14.3 The Two-Step Process

Finding association rules is a two-step process. Step one: find frequent itemsets — the itemsets that satisfy minimum support. Step two: from those frequent itemsets, find the rules that have confidence more than minimum confidence — the highly confident rules. Frequent itemsets first, rules second. The rest of the session is about making step one fast.

Intuition — why step one first: rules can only be built from itemsets, and only frequent itemsets are worth building rules from. Checking every conceivable rule directly would multiply the explosion of section 11.14.2 by itself. By first shrinking the itemsets to the frequent ones, step two only ever sees a small, meaningful pool — that is the whole design of the two-step process.

Recap: Minimum support and minimum confidence are the two knobs: support decides which itemsets are frequent, confidence decides which rules survive. They exist because the space of possible itemsets is $2^{D}$ , which explodes with $D$ , so the search must be cut before it starts. The next section shows what happens without the cut: brute force.

11.15 The Brute Force Approach

11.15.1 The Procedure

The direct approach is brute force. Take the unique items. Generate all one-item sets, then all two-item sets, then all three-item sets, up to the full set. For each candidate itemset, check the transaction log and count how many times it appears. If the frequency is more than (or equal to) minimum support, the itemset is frequent; otherwise it is not. Only after the frequent itemsets are known do we mine rules inside them.

The brute-force procedure.

Generate the full candidate pyramid: every itemset from size 1 up to size $D$ , over all $D$ distinct items — $2^{D}$ candidates in total.
Count each candidate against every transaction in the log, incrementing its support count whenever the transaction contains it.
Compare each support count with minimum support and keep only the frequent itemsets.
Mine rules inside the frequent itemsets only.

The cost: first we generate the full candidate pyramid, then we count every candidate against the log, then we compare with the threshold. With $2^{D}$ candidates and a log of thousands of transactions, that is a heavy computation. The reference text characterizes the same cost: comparing $M = 2^{D} - 1$ candidates against $N$ transactions costs on the order of $O (N M w)$ operations, where $w$ is the widest transaction — the log size multiplies the exponential candidate count.

11.15.2 The Five-Item Illustration

Suppose the mall sells five items: A, B, C, D and E. The number of unique itemsets is $2^{5} = 32$ — pairs like A and B, A and C, A and D, A and E, B and E, and so on, all the way up.

Worked example — the full pyramid for five items. With items A, B, C, D, E the pyramid contains:

5 one-item sets: {A}, {B}, {C}, {D}, {E};
10 two-item sets: {A,B}, {A,C}, {A,D}, {A,E}, {B,C}, {B,D}, {B,E}, {C,D}, {C,E}, {D,E};
10 three-item sets, 5 four-item sets, and 1 five-item set {A,B,C,D,E};

total $5 + 10 + 10 + 5 + 1 = 31$ , plus the empty set, gives $2^{5} = 32$ . Every one of the 31 non-empty candidates must be looked up in the log and counted. Sense-check: this is the same doubling table as section 11.14 — five items already demand 31 counting jobs.

A typical mall does not have five items; it has around 5000. With 5000 items the candidate count is $2^{5000}$ , and for each candidate we would have to count how many times that combination was purchased — how many times AB appears in the log, how many times AC appears, how many times AD appears, and so on — then decide frequent or not by minimum support.

Pitfalls of brute force

Generating before pruning: the pyramid is built fully even when most of it can never be frequent; every wasted candidate costs a pass over the log.
Counting every candidate against every transaction: the naive plan checks each candidate against each of the thousands of transactions — $N$ comparisons per candidate — which is what makes the approach unusable at mall scale.
Underestimating the empty set's effect: $2^{D}$ versus $2^{D} - 1$ differs by one basket, but the doubling pattern itself is the problem — the difference "does not matter much" only because it is dwarfed by the exponential.

The brute force route does the full pyramid. We can do better.

Recap: Brute force is the honest but hopeless plan: generate all $2^{D}$ candidates, count each against the log, keep the frequent ones. It works for 5 items and fails at 5000. The saving comes from a single observation about support — the next section's apriori principle — which lets us prune the pyramid before counting.

11.16 The Apriori Principle and the Anti-Monotone Property

11.16.1 The Principle and Its Contrapositive

The reduction comes from the apriori principle: if an itemset is frequent, then all its subsets must also be frequent. If {A, B, C} is frequent — its frequency is greater than or equal to minimum support — then every one of its subsets must be frequent too: {A, B}, {B, C}, {A, C}, and the single items {A}, {B}, {C}. The equally important contrapositive: if an itemset is infrequent, all its supersets are infrequent. Written mathematically, for all X and Y where X is a subset of Y:

$support (X) \geq support (Y)$

A superset can only shrink or keep the support count, never grow it. This property has a name: the anti-monotone property — support is anti-monotone with respect to set inclusion.

Why the inequality must hold. Every transaction that contains the superset $Y$ automatically contains every subset $X$ of $Y$ — a basket holding {A, B, C} also holds {A, B}. So the count of $X$ can never be less than the count of $Y$ :

$σ (X) \geq σ (Y) and hence support (X) \geq support (Y)$

In plain words: adding items to an itemset can only lose transactions, never gain them. The reference text states this as the anti-monotone property: for any measure $f$ , if $X \subseteq Y$ then $f (Y) \leq f (X)$ — support is such a measure, which is what makes it usable for pruning.

Intuition — the shrinking guest list: an itemset is like a party with a strict guest list. Every basket that lets in the three guests {A, B, C} also lets in any two of them — so the pair {A, B} is welcomed at least as often as the triple. The bigger the guest list, the fewer baskets admit it. That single fact is the whole engine of pruning: if a pair is already rarely admitted, every triple that contains it is admitted even more rarely.

11.16.2 Pruning in the Five-Item Pyramid

Now use the property to cut the brute force cost. In the five-item example, the full candidate pyramid has $2^{5} = 32$ itemsets. Suppose the count shows AB is infrequent. By the anti-monotone property, everything above AB in the pyramid — ABC, ABD, ABE, and their supersets such as ABCDE — is infrequent too. No need to explore any of them.

Worked example — one infrequent pair kills seven candidates. With items A, B, C, D, E, count the supersets of the pair {A, B}:

3 three-item sets: ABC, ABD, ABE;
3 four-item sets: ABCD, ABCE, ABDE;
1 five-item set: ABCDE;

total $3 + 3 + 1 = 7$ . In the pyramid shown, this single infrequent pair kills these seven candidates, taking the search from 32 down to $32 - 7 = 25$ candidates — without a single support count being spent on any of the seven. Sense-check: every one of the seven contains AB, so if AB never reaches minimum support, none of them can either — the inequality $support (AB) \geq support (ABC)$ rules them all out.

The same trick repeats at every level: if a one-item set like E is infrequent, then anything containing E is infrequent — we do not even generate those candidates or count them. Prune first, count later.

Visual intuition: picture the itemset lattice as a pyramid: the single items at the bottom, pairs above them, triples higher still, and the full set at the top. When an itemset is declared infrequent, the entire subtree hanging above it collapses out of the picture. The pyramid's surviving shape is decided from the bottom up, one level at a time — which is exactly why the algorithm grows $k$ level by level (section 11.17).

11.16.3 Pruning by Level: From 41 to 30 Computations

A second illustration makes the saving concrete. From a transaction log we generate the one-item sets: bread, Coke, milk, beer, diaper, egg — with their frequency counts. Suppose minimum support is set to 3: an itemset is frequent only when it appears three or more times. Coke and egg fail the threshold, so every superset containing Coke or egg is discarded without being counted. Moving to two-item sets, candidates like bread and milk, bread and beer, milk and beer are generated; bread and beer and milk and beer fail minimum support, so all their supersets are pruned as well. Continue to three-item sets and beyond. The traditional full process required 41 computations; with support-based pruning it drops to 30. Same answer, fewer counts — that is the whole point of pruning.

Worked example — the per-level count. With six items, brute force generates every candidate up to size 3:

$(1 6) + (2 6) + (3 6) = 6 + 15 + 20 = 41 candidates$

With pruning (minimum support count 3, and Coke and egg removed first), the surviving items are four: bread, milk, beer, diaper. The candidate counts become:

$(1 6) + (2 4) + 1 = 6 + 6 + 1 = 13 candidates$

The reference text reports the same example as a reduction from 41 to 13 candidates — a 68% cut. The lecture's slide counted the saving differently, as computations falling from 41 to 30; whichever way the count is defined, the mechanism is identical and the exam-relevant fact is the mechanism: prune the pyramid level by level using minimum support, and never count what cannot be frequent. Sense-check: with 41 candidates the brute-force route must count all 41 against the log; pruned, it counts at most the 13 that survived — every item above an infrequent set is skipped.

11.16.4 Who Sets Minimum Support

Q: Is minimum support fixed by the domain expert based on their knowledge?

A: Yes, correct. The domain expert of that particular mart sets minimum support from knowledge. The expert might say: I only want to process items sold at least 50 times in a day — only then do I treat the item as popular and worth exploring; otherwise there is no use processing it. If a biscuit packet is sold 5000 times, then only am I interested in finding association rules around it. If the item is not sold frequently, there is no point in making an association rule out of it.

Pitfalls

Forgetting the contrapositive direction: the principle prunes supersets of infrequent sets — never the other way. An infrequent triple says nothing about its pairs.
Setting the threshold blindly: a too-low minimum support swamps the search with trivial itemsets; a too-high one starves it. The threshold is domain knowledge, not an automatic default — which is why the expert sets it.
Counting what pruning already saved: after AB fails, counting ABC is pure waste; the whole value of the principle is "prune first, count later".

Exam note: the apriori principle (frequent $\Rightarrow$ all subsets frequent) and its contrapositive (infrequent $\Rightarrow$ all supersets infrequent) rest on the anti-monotone property $support (X) \geq support (Y)$ for $X \subseteq Y$ . Expect a question that gives counts at one level and asks which higher-level candidates can be pruned without counting.

Recap: support is anti-monotone — a superset can only shrink the support — so an infrequent itemset kills its whole superset subtree. That turns a $2^{D}$ brute-force pyramid into a level-by-level shrinking one. Next: why the levels must be grown one $k$ at a time.

11.17 Why We Grow Itemsets One K at a Time

11.17.1 Incremental Candidate Generation

The value of K is not a magic number — it is the level of candidate generation. Start with one-item sets, count them, prune with minimum support. Then generate two-item sets only from the surviving items. Prune again. Then three-item sets, and so on.

The level-wise procedure.

Level $k = 1$ : count the support of every single item; keep the items at or above minimum support (the frequent 1-itemsets).
Level $k = 2$ : build candidate pairs only from the frequent 1-itemsets; count only those; keep the frequent pairs.
Level $k = 3$ : build candidate triples only from the frequent pairs; count only those; keep the frequent triples.
Continue until no larger frequent itemset exists — the generation stops by itself when the last level produced nothing.

Growing K gradually is exactly what makes pruning possible: an infrequent two-item set discards every superset above it, so the search shrinks as K grows instead of exploding.

Intuition — building a house floor by floor: you cannot pour the third floor before the second exists. Each level of candidates is built only from the frequent items of the level below, because any candidate built from an infrequent piece would itself be infrequent (the anti-monotone property of section 11.16). K is not chosen in advance — it is simply the floor the search happens to be on.

This "K is a level, not a choice" point confused a student during the session, and the exchange below settles it.

11.17.2 Student Question: How Is K Decided?

Q: How do we decide the value of K?

A: We do not pick K up front. For generating candidates we start with one-item sets, then two-item sets, then three-item sets. Once a two-item set is found infrequent, all its supersets are discarded — that is why we keep incrementing K gradually. The pruning at each level drives the whole search.

Recap: K is the candidate-generation level, not a chosen parameter: count level 1, prune, count level 2, prune, and keep going until a level yields nothing. The search shrinks with every level, which is why it stays feasible — and why the worked numerical in the next section follows exactly this ladder.

11.18 Worked Numerical: Association Rules from a Four-Transaction Log

11.18.1 The Data and Thresholds

The domain expert sets minimum support at 2 and minimum confidence at 75%. The transaction log has four transactions:

Transaction	Items
1	A, B, C
2	A, C
3	A, D
4	B, E, F

(The last transaction was read aloud as "VEF"; the reading BEF fits, because the support counts stated for each item — B twice, E once, F once — match only the BEF reading, and every count below is consistent with it.)

The task: find the association rules that survive these thresholds.

The thresholds as rules of the game: an itemset survives only if its support count is at least 2 (minimum support), and a rule survives only if its confidence is at least 75% (minimum confidence). Both thresholds were fixed before the counting started, by the domain expert — recall from section 11.16.4 why the expert sets them.

11.18.2 One-Itemsets

First generate the one-item sets from the unique products — A, B, C, D, E, F — and count how many times each item was sold in the log: A is sold 3 times, B twice, C twice, D once, E once, F once. Compare with minimum support 2: A, B and C are frequent (all at least 2), while D, E and F are infrequent. By the anti-monotone property, any superset of D, any superset of E, and any superset of F is infrequent — no need to process them at all. The surviving items are A, B, C.

Level 1 — count and prune.

Item	Support count	Frequent (≥ 2)?
A	3	yes
B	2	yes
C	2	yes
D	1	no
E	1	no
F	1	no

Sense-check: the six counts sum to 10 = the number of item-slots in the log (3 + 2 + 2 + 1 + 1 + 1 = 10), and only A, B, C clear the bar of 2. D, E, F are dead on arrival — no superset containing them will ever be counted.

11.18.3 Two-Itemsets

From {A, B, C} we generate the two-item sets: AB, AC, BC. Count them in the log: AB appears once, AC appears twice, BC appears once. Against minimum support 2, only AC is frequent. AB and BC fail, so every superset of AB and every superset of BC is pruned.

Level 2 — count and prune.

Pair	Where it occurs	Support count	Frequent (≥ 2)?
AB	transaction 1	1	no
AC	transactions 1, 2	2	yes
BC	transaction 1	1	no

Sense-check against the log: AC appears in transactions 1 and 2 (both contain A and C); BC appears only in transaction 1; AB appears only in transaction 1. Only AC survives — and AB and BC take their supersets down with them.

Q: The answer first showed BC as the frequent pair, but the counts say AC appears twice and BC once.

A: Correct — that was a slip in the narration, and a student pointed it out. My bad. The frequent pair is AC. AB appears once and BC appears once; AC appears twice. Everything else follows from AC.

This correction matters: the whole numerical rests on which pair is frequent, so it is worth re-checking the count yourself. AC appears in transactions 1 and 2; BC appears only in transaction 1.

11.18.4 Three-Itemsets

Can we generate three-item sets? The only frequent two-item set is AC, which has exactly two items. To make a three-item set we would have to add another item to AC — but any third item would be D, E, or F (already pruned as infrequent single items), or an item that makes an infrequent pair. So no three-item set is possible, and generation stops here. The frequent-itemset stage is complete: {A}, {B}, {C}, {A, C}.

Why the ladder stops: a candidate 3-itemset must be built from a frequent 2-itemset (section 11.17). The only frequent pair is AC, and adding anything to it produces a superset of an infrequent set: {A, C, D} is a superset of D, {A, C, B} is a superset of AB (infrequent), {A, C, E} a superset of E, {A, C, F} a superset of F. Every option is pruned, so level 3 is empty and the generation loop ends. Final frequent itemsets: {A}, {B}, {C}, {A, C}.

11.18.5 Writing and Evaluating the Rules

From the frequent pair AC there are two candidate rules: A → C and C → A. Evaluate each with confidence.

Rule 1: A → C.

$confidence (A \to C) = \frac{σ ({ A , C })}{σ ({ A })} = \frac{2}{3} \approx 0.67 = 67%$

This is below the minimum confidence of 75%, so the rule A → C is discarded.

Rule 2: C → A.

$confidence (C \to A) = \frac{σ ({ A , C })}{σ ({ C })} = \frac{2}{2} = 1 = 100%$

This meets the threshold, so the only surviving rule is C → A, with confidence 100%. Sense-check: both rules share the same numerator $σ ({A, C}) = 2$ ; they differ only in the denominator — A occurs 3 times, C occurs 2 times — and that is why one fails and the other wins.

11.18.6 Why C → A Wins

Check the winner against the log. C is sold in transaction 1 and transaction 2; in both, A is also sold — 100% of the time, exactly as the rule says. Now check the loser. A is sold in transactions 1, 2 and 3, but C is present only in transactions 1 and 2 — A was sold once without C, and that is why the confidence is 67% and not 100%. In the classroom phrasing, A → C was not a bad rule, it was a poor rule: it fails the minimum confidence bar because A happens too often on its own, while C → A is the strong association — whenever C appears, A follows.

Q: Why is A → C the poor rule and C → A the good one? They use the same pair.

A: Same pair, different direction, different denominator. A sold 3 times but C followed only twice — 67%. C sold 2 times and A followed both times — 100%. The rule with the higher confidence is the better rule, and here it beats the minimum confidence of 75% while the other one does not. So: poor rule, not a bad rule — it is still a true statement about the data, just not a strong or usable one, because it fails the minimum confidence bar.

Pitfalls

Sliding the direction of a rule: A → C and C → A share the same pair but have different denominators; mixing them up changes both the arithmetic and the verdict.
Trusting a count without re-checking it: the BC/AC slip shows how one wrong count flips the whole solution — re-count from the log before pruning.
Calling a weak rule "bad": a rule that fails minimum confidence is not wrong about the data; it is simply too weak to act on. "Poor" and "bad" are different verdicts, and the exam may test exactly this distinction.

Exam note: this numerical is the model procedure for everything that follows: generate one-item sets, prune with minimum support, generate two-item sets, prune again, stop when no larger frequent set exists, write the rules, and keep only the rules whose confidence clears the minimum. Expect this exact recipe as a template for numerical work — a log, two thresholds, and the same four stages.

11.19 Why We Mine Only Frequent Items

11.19.1 Rare Items Have No Merit

There is a business reason behind minimum support, beyond computational savings. If an item is purchased very few times, there is no merit in placing it into rules. Suppose a chips-packet brand was sold only one time — it is not popular, and building an association rule around it gives nothing useful. Rules are only meaningful when built on items that actually move.

Intuition — a rule nobody can act on: a rule about an item sold once has zero practical value: the store cannot stock, bundle, or promote around a product that barely exists in the log. The threshold is not just a computation saver — it is a business filter that keeps the analysis on items that actually matter. A rule that is technically true but commercially useless is exactly the "poor rule" distinction from section 11.18, applied one level earlier.

Worked example — the single-sale item. Suppose a chips-packet brand appears in exactly 1 of 1,000 transactions, always together with cola. The rule chips $\to$ cola has confidence $1/1 = 100%$ — perfect by the arithmetic. But its support is $1/1000 = 0.1%$ , and the store cannot build merchandising on one purchase. Compare with a biscuit packet in 5,000 of 10,000 transactions: support 50%, and any rule around it has real reach. Sense-check: 100% confidence on a one-case sample is a mirage — the support bar exists precisely to keep such mirages out of the analysis.

11.19.2 The Domain Expert Decides

That is why minimum support is a tunable, decided by the domain expert of the particular mart. The expert says: I process an item set only when the item is sold, say, 50 times in a day; only then is it popular and heavily sold, and only then do I look for its rules. Otherwise there is no use processing it, because there is no point in making an association rule out of an item nobody buys.

Recap: Mining only frequent items is both a computational necessity and a business decision: rare items produce rules no one can act on, so the domain expert sets a support bar that keeps the analysis on items that actually move. The module continues in the next session: generating frequent itemsets, writing the rules, solving more numericals, and walking through the challenges of the domain one by one in elaborate detail.

Real-world: retailers, e-commerce platforms, and streaming services all set popularity thresholds before mining — a recommendation rule built on a product with one purchase is worse than no rule at all, which is why minimum support appears in every production association-mining pipeline.

Exam Guidance Summary

This session introduced the association rule mining module and made no exam-specific announcements — administrative notices about evaluated mid-sem copies, the upcoming recheck window, and the model answer sheet are not part of the material. What the session establishes as must-own material:

The vocabulary, exactly: item, itemset, k-itemset, support count, support, frequent itemset, frequent subsequence, frequent substructure, minimum support, minimum confidence, LHS, RHS.
The rule form $X \to Y$ and the two evaluation measures — support and confidence — including why the confidence denominator is the LHS support count and not the total transaction count.
The combinatorial fact behind the field: $2^{D}$ possible itemsets, which is why brute force fails and thresholds exist.
The apriori principle and the anti-monotone property: if an itemset is infrequent, all its supersets are infrequent; formally $support (X) \geq support (Y)$ whenever $X \subseteq Y$ .
The two-step process: frequent itemsets first, then confident rules.
The 4-transaction numerical as the model procedure: generate one-item sets, prune by minimum support, generate two-item sets, prune, stop when no larger set exists, write rules, keep only those above minimum confidence. Exam note: expect this exact recipe as a template for numerical work.

How to revise from this session: drill the definitions until they are exact (the vocabulary list above), then redo the 4-transaction numerical from memory — one-item sets, pruning with minimum support, pairs, the confidence comparison, and the discard of the poor rule. The numerical is the single best preparation item the session produced, because it exercises every definition at once.

The session also repeatedly emphasizes that details will be covered in elaborate detail going forward — frequent-itemset generation, rule writing, and the domain's challenges — so the numerical procedure above is the foundation the next session builds on.

Key Industry Applications

Supermarket shelf management: bread and milk placed adjacent because they are bought together, speeding up shoppers and freeing space for new customers (Real-world: store layout planning).
Airport terminal management: maximum distance between security check-in and boarding gates, retail shops in between, forcing passengers past shops to raise revenue (Real-world: airport terminal design).
Marketing and sales promotion: "Thanda means Coca Cola", "Things go better with Coca Cola", and the Mountain Dew feeling-tagline — advertising as repeated reinforcement of association confidence (Real-world: brand advertising, IPL ad repetition).
Inventory management: location-specific failure associations — more filters in Delhi because filters fail there, more fuses in Chennai because power fluctuation blows them (Real-world: IFB service-center spare-part stocking).
Next-word prediction: the search box predicts the next word from learned word-pair confidence (Real-world: Google search suggestions, autocomplete keyboards).
Plagiarism detection and time-series analysis: triggering chains $A \to B \to C \to D$ mined from sequential data (Real-world: fraud pipelines, event-chain analysis).
Failure-chain analysis: the bird-strike cascade from blade fracture to engine destruction, and the design fixes that break the chain — harder blades and mid-engine filters (Real-world: Boeing and Airbus engine design).
Market basket analysis at large: bundling best-sellers with slow movers and cross marketing — Haldiram's new sweets, Bajaj's electrical items — riding on existing brand associations (Real-world: retail bundling, brand portfolios).

The common thread across all eight applications: each one takes the same discovered structure — a co-occurrence association or a chain of associations — and converts it into a decision. Shelf layout, terminal design, ad budgets, spare-part stock, autocomplete suggestions, fraud and failure analysis: the pattern is the product, and the mining is what makes the pattern visible.

DM Lecture 11 notes · Association Rule Mining

Data Mining· postgraduate· 2026-08-05

Sections Breakdown

1What Is Association Rule Mining

What association rule mining is, the mart owner's transaction log, and why the method is descriptive and unsupervised

2Market Basket Analysis and Its Business Uses

Market basket analysis: co-purchase patterns behind bundling, cross marketing, and product placement

3Supermarket Shelf Management

Supermarket shelf management: placing co-purchased items side by side to serve more customers per hour

4Airport Terminal Management

Airport terminal management: maximizing walking between gates to raise corridor retail revenue

5Marketing and Sales Promotion: Confidence as a Brand Tool

Marketing and sales promotion: advertising as repeated reinforcement of the confidence of a feeling-to-brand rule

6Inventory Management

Inventory management: location-to-failed-part rules driving spare-part stocking at service centers

7Next-Word Prediction and Other Applications

Next-word prediction, plagiarism detection, and time-series chains as association mining on ordered data

8The Bird-Strike Case Study: Breaking a Failure Chain

The bird-strike case study: a failure chain from bird to burned engine, broken at links A and C

9Items, Itemsets, and k-Itemsets

The formal vocabulary: item, itemset, and k-itemset with exact cardinality

10Support Count and Support

Support count and support: counting how often an itemset appears, then normalizing by the log size

11Frequent Itemsets, Subsequences, and Substructures

Frequent itemsets, frequent subsequences, and frequent substructures across data types

12Why Frequent Patterns Matter

Why frequent patterns matter: rules behind applications and a feature factory for other mining tasks

13Association Rules: Form and Evaluation

The rule form X to Y and its two measures: support out of N, confidence out of the LHS count

14Minimum Support and Minimum Confidence

Minimum support and minimum confidence: the two thresholds, the 2^D explosion, and the two-step process

15The Brute Force Approach

The brute force approach: generate all 2^D candidates, count each against the log

16The Apriori Principle and the Anti-Monotone Property

The Apriori principle and the anti-monotone property: infrequent sets prune their supersets

17Why We Grow Itemsets One K at a Time

Why candidate itemsets are grown one K at a time: pruning at every level drives the search

18Worked Numerical: Association Rules from a Four-Transaction Log

The worked numerical: four transactions, minimum support 2, minimum confidence 75%, and the rule C to A

19Why We Mine Only Frequent Items

Why only frequent items are mined: rare items produce rules nobody can act on

20Exam Guidance Summary

The vocabulary to drill and the four-transaction numerical as the model exam procedure

21Key Industry Applications

Eight applications from shelf layout to bird-strike analysis, all built on co-occurrence patterns

Postgraduate students in Data Mining

Exam Revision Notes

Below is the distilled, exam-ready core. Every entry comes from the full explanation above. Use this section for rapid review; return to the main notes when a point needs more context.

What Is Association Rule Mining

Must-know: Association rule mining finds statements A -> B ('sale of A leads to sale of B') from a transaction log, in two stages: frequent patterns first, then rules; it is unsupervised and descriptive, not predictive.

$A \to B$

⚠️ Top pitfall: Treating co-occurrence as causation; expecting prediction from a descriptive method.

Self-check: What two stages does association rule mining work in?

Connects to: Market Basket Analysis and Its Business Uses, Association Rules: Form and Evaluation

Market Basket Analysis and Its Business Uses

Must-know: Market basket analysis = analyzing what goes into baskets to maximize sales; bundling pairs a best-seller with a weak product so the bundle pulls the weak product along.

⚠️ Top pitfall: Bundling amplifies an existing association; it does not create one.

Self-check: Name three business decisions fed by market basket analysis.

Connects to: What Is Association Rule Mining, Supermarket Shelf Management, Marketing and Sales Promotion: Confidence as a Brand Tool

Supermarket Shelf Management

Must-know: Items bought together by a large number of customers are placed adjacently; quick purchase -> quick exit -> more customers served per hour.

⚠️ Top pitfall: Placing unrelated best-sellers together creates no co-purchase pattern.

Self-check: Why does placing bread next to milk serve more customers per hour?

Connects to: Airport Terminal Management, Market Basket Analysis and Its Business Uses

Airport Terminal Management

Must-know: The airport maximizes walking (gates at opposite ends, shops in between) while the supermarket minimizes walking — both are space-management strategies from customer behavior.

⚠️ Top pitfall: Assuming every passenger has buffer time; the design fails when the corridor is walked in minutes.

Self-check: How does airport terminal management contrast with supermarket shelf management?

Connects to: Supermarket Shelf Management, Market Basket Analysis and Its Business Uses

Marketing and Sales Promotion: Confidence as a Brand Tool

Must-know: Every repetition of an advertisement improves the confidence of the association feeling -> brand; confidence is 'if the LHS happens, what is the chance the RHS also happens?'.

$confidence (A \to B) = \frac{how often A and B happen together}{how often A happens}$

⚠️ Top pitfall: Confusing confidence with frequency: a strong association can still be rare overall.

Self-check: How does ad repetition relate to the confidence of an association?

Connects to: Association Rules: Form and Evaluation

Inventory Management

Must-know: Association rules of the form location -> failed part drive spare-part stocking: more filters in Delhi (water quality), more fuses in Chennai (power fluctuation).

$location \to failed part$

⚠️ Top pitfall: The association is only as good as the data behind it; seasonal factors can inflate a local association.

Self-check: Why would Delhi service centers stock more filters than Chennai centers?

Connects to: Association Rules: Form and Evaluation

Next-Word Prediction and Other Applications

Must-know: Next-word prediction evaluates word-pair rules by confidence and shows the highest-confidence follower; chains A -> B -> C -> D appear in time-series and plagiarism analysis.

$A \to B \to C \to D$

⚠️ Top pitfall: Forgetting the denominator: 100% confidence on one occurrence is worthless; check support too.

Self-check: Why does typing 'good' predict 'morning' in the search box?

Connects to: The Bird-Strike Case Study: Breaking a Failure Chain, Association Rules: Form and Evaluation

The Bird-Strike Case Study: Breaking a Failure Chain

Must-know: One small failure triggers a cascade (bird -> fracture -> blocked airflow -> overheating -> destroyed engine); fixing early links (harder blades, mid-engine filters) stops the chain; the front mesh failed because it disrupted airflow.

$bird hits blade \to blade fracture \to blocked airflow \to overheating \to engine destroyed$

⚠️ Top pitfall: Attacking the chain at a link where the fix damages normal operation (the front mesh).

Self-check: Which two links of the failure chain were fixed, and how?

Connects to: Next-Word Prediction and Other Applications, The Apriori Principle and the Anti-Monotone Property

Items, Itemsets, and k-Itemsets

Must-know: Definitions: item = any particular product; itemset = collection of one or more items; k-itemset = itemset with cardinality exactly k (not more, not fewer).

⚠️ Top pitfall: Thinking a 'three-item set' can be anything other than exactly three items.

Self-check: What is the cardinality of a 5-itemset?

Connects to: Support Count and Support, Why We Grow Itemsets One K at a Time

Support Count and Support

Must-know: support(X) = sigma(X) / N. The itemset {milk, bread, juice} in 2 of 5 transactions has support 2/5 = 0.4 = 40%. Support is relative; the count alone is not.

$support (X) = \frac{support count ( X )}{N}$

⚠️ Top pitfall: Confusing support count (absolute) with support (relative); counting partial baskets toward the full itemset.

Self-check: A log of 5 transactions contains {milk, bread, juice} twice. What are its support count and support?

Connects to: Association Rules: Form and Evaluation, Minimum Support and Minimum Confidence

Frequent Itemsets, Subsequences, and Substructures

Must-know: Frequent = at or above a tunable threshold; the family: frequent itemsets (unordered), frequent subsequences (ordered), frequent substructures (structured objects).

⚠️ Top pitfall: Assuming 'frequent' has one fixed meaning — the threshold is a knob that depends on the use case.

Self-check: What are the three members of the frequent pattern family?

Connects to: Support Count and Support, Minimum Support and Minimum Confidence

Why Frequent Patterns Matter

Must-know: Frequent patterns matter twice: as the rules behind the business applications, and as a supporting stage that improves classification and clustering models.

⚠️ Top pitfall: The supporting role only helps when the data really contains recurrent structure; otherwise mined patterns are noise.

Self-check: In what two ways do frequent patterns matter?

Connects to: What Is Association Rule Mining, Association Rules: Form and Evaluation

Association Rules: Form and Evaluation

Must-know: Rule form X -> Y with LHS X and RHS Y; support = sigma(X union Y)/N; confidence = sigma(X union Y)/sigma(X) = P(Y|X). The confidence denominator is the LHS count, not N.

$support (X \to Y) = \frac{σ ( X \cup Y )}{N}, confidence (X \to Y) = \frac{σ ( X \cup Y )}{σ ( X )}$

⚠️ Top pitfall: Using N in the confidence denominator; swapping the item names (the bread-butter slip) while keeping the numbers.

Self-check: In a 5-transaction log, {milk, diaper} occurs 3 times and {milk, diaper, butter} occurs 2 times. What is the confidence of {milk, diaper} -> butter?

Connects to: Support Count and Support, Minimum Support and Minimum Confidence, Worked Numerical: Association Rules from a Four-Transaction Log

Minimum Support and Minimum Confidence

Must-know: D distinct items give 2^D possible itemsets (2 items -> 4 baskets including empty); thresholds cut the search space; two-step process: frequent itemsets first, confident rules second.

$2^{D}$

⚠️ Top pitfall: Treating 2^D - 1 versus 2^D as the important fact; the doubling explosion is the point.

Self-check: How many possible itemsets do 3 distinct items produce?

Connects to: The Brute Force Approach, The Apriori Principle and the Anti-Monotone Property, Association Rules: Form and Evaluation

The Brute Force Approach

Must-know: Brute force: generate the full candidate pyramid (5 items -> 32 itemsets: 5 + 10 + 10 + 5 + 1 = 31 non-empty), count every candidate against the log (O(NMw)), compare with minimum support. We can do better.

$2^{5} = 32$

⚠️ Top pitfall: Generating before pruning; counting every candidate against every transaction at mall scale.

Self-check: How many unique itemsets do five items A..E produce?

Connects to: Minimum Support and Minimum Confidence, The Apriori Principle and the Anti-Monotone Property

The Apriori Principle and the Anti-Monotone Property

Must-know: Apriori principle: frequent -> all subsets frequent; contrapositive: infrequent -> all supersets infrequent; anti-monotone property support(X) >= support(Y) for X subset of Y. One infrequent pair AB kills 7 candidates (32 -> 25).

$support (X) \geq support (Y) (X \subseteq Y)$

⚠️ Top pitfall: Pruning in the wrong direction (infrequent triple says nothing about its pairs); counting what pruning already saved.

Self-check: If AB is infrequent in a 5-item problem, how many candidate supersets are killed without counting?

Connects to: The Brute Force Approach, Why We Grow Itemsets One K at a Time, Worked Numerical: Association Rules from a Four-Transaction Log

Why We Grow Itemsets One K at a Time

Must-know: We do not pick K up front; we start with one-item sets and increase K gradually, because an infrequent k-itemset discards all supersets above it — pruning at each level drives the search.

⚠️ Top pitfall: Treating K as a chosen parameter instead of the level of candidate generation.

Self-check: How is the value of K decided?

Connects to: The Apriori Principle and the Anti-Monotone Property, Worked Numerical: Association Rules from a Four-Transaction Log

Worked Numerical: Association Rules from a Four-Transaction Log

Must-know: Model procedure: one-item sets counted and pruned (A 3, B 2, C 2 frequent; D, E, F pruned), pairs AB 1 / AC 2 / BC 1, only AC frequent, no 3-itemset possible; confidence(A -> C) = 2/3 = 67% discarded, confidence(C -> A) = 2/2 = 100% survives.

$confidence (C \to A) = \frac{σ ({ A , C })}{σ ({ C })} = \frac{2}{2} = 1 = 100%$

⚠️ Top pitfall: The BC/AC slip: one wrong count flips the whole solution, so re-check counts from the log; also calling a weak rule 'bad' instead of 'poor'.

Self-check: Why does C -> A survive while A -> C is discarded?

Connects to: The Apriori Principle and the Anti-Monotone Property, Why We Grow Itemsets One K at a Time, Association Rules: Form and Evaluation

Why We Mine Only Frequent Items

Must-know: Minimum support is a tunable decided by the domain expert: only items sold often enough (e.g., 50 times a day) are worth rules; rare items produce rules no one can act on.

⚠️ Top pitfall: A perfect confidence on a one-case sample (chips -> cola with 100% confidence but support 0.1%) is a mirage.

Self-check: Why is there no merit in a rule built on an item sold only once?

Connects to: Minimum Support and Minimum Confidence, The Apriori Principle and the Anti-Monotone Property

Exam Guidance Summary

Must-know: Drill the vocabulary exactly, then redo the 4-transaction numerical from memory — it exercises every definition at once.

Previous LectureLecture 10 · Ensemble Algorithms

Next LectureLecture 12 · Association Rule Mining: Apriori and FP-Growth

Was this lecture useful?

Loading comments…

🤖

BitsNotes AI Assistant

Subject Notes Assistant

Configure AI Chat

Choose how to access the chatbot

Have your own API key?

Switch to "Bring Your Own Key" tab above for unlimited access with any OpenAI-compatible provider.

AI Provider Preset

API Endpoint URL (OpenAI-Compatible)

API Key

Model Name

🔑 Enter API key above to fetch live models from provider, or enter model name manually.

Remember key for this session (until tab closes)

OpenAI-Compatible API Support

Choose any provider preset (Gemini, DeepSeek, Kimi, GLM, MiniMax, Qwen, OpenAI, Groq, Ollama, etc.) or enter a custom endpoint URL.

Security & Privacy First

Your API key is sent directly from your browser to your specified provider. BitsNotes servers never store or see your key.

Prerequisite Knowledge

Previously Covered in This Subject

11.1 What Is Association Rule Mining

11.1.1 The Mart Owner's Transaction Log

11.1.2 The Rules We Want to Find

11.1.3 Descriptive, Not Predictive: An Unsupervised Method

11.2 Market Basket Analysis and Its Business Uses

11.2.1 What Market Basket Analysis Is

11.2.2 Bundling and Cross Marketing

11.3 Supermarket Shelf Management

11.3.1 Arranging Items by Co-Purchase

11.3.2 Why Closeness Helps the Whole Store

11.4 Airport Terminal Management

11.4.1 The Maximum-Distance Design

11.4.2 Why Walking Past Shops Pays

11.5 Marketing and Sales Promotion: Confidence as a Brand Tool

11.5.1 Associating Products with Everyday Feelings

11.5.2 The Informal Idea of Confidence

11.6 Inventory Management

11.6.1 Stocking Spare Parts by Location

11.6.2 Location-Specific Failure Associations

11.7 Next-Word Prediction and Other Applications

11.7.1 Search-Box Prediction

11.7.2 Plagiarism Detection and Time-Series Chains

11.8 The Bird-Strike Case Study: Breaking a Failure Chain

11.8.1 The Cascade: Bird to Burned Engine

11.8.2 Fixing Part A and Part C

11.9 Items, Itemsets, and k-Itemsets

11.9.1 Item and Itemset

11.9.2 The k-Itemset

11.9.3 Student Questions on Cardinality

11.10 Support Count and Support

11.10.1 Support Count

11.10.2 Support as a Fraction

11.11 Frequent Itemsets, Subsequences, and Substructures

11.11.1 Frequent Itemsets and the Tunable Threshold

11.11.2 Frequent Subsequences

11.11.3 Frequent Substructures

11.12 Why Frequent Patterns Matter

11.12.1 Relationships Between Items

11.12.2 Feeding Other Data Mining Tasks

11.13 Association Rules: Form and Evaluation

11.13.1 The Rule Form

11.13.2 Support of a Rule

11.13.3 Confidence of a Rule

11.13.4 Worked Example: {Milk, Diaper} → Butter

11.13.5 Worked Example: {Milk, Butter} → Diaper

11.13.6 The Bread-Butter Slip

11.14 Minimum Support and Minimum Confidence

11.14.1 The Two Thresholds

11.14.2 Why Thresholds Exist: The 2^D Explosion

11.14.3 The Two-Step Process

11.15 The Brute Force Approach

11.15.1 The Procedure

11.15.2 The Five-Item Illustration

11.16 The Apriori Principle and the Anti-Monotone Property

11.16.1 The Principle and Its Contrapositive

11.16.2 Pruning in the Five-Item Pyramid

11.16.3 Pruning by Level: From 41 to 30 Computations

11.16.4 Who Sets Minimum Support

11.17 Why We Grow Itemsets One K at a Time

11.17.1 Incremental Candidate Generation

11.17.2 Student Question: How Is K Decided?

11.18 Worked Numerical: Association Rules from a Four-Transaction Log

11.18.1 The Data and Thresholds

11.18.2 One-Itemsets

11.18.3 Two-Itemsets

11.18.4 Three-Itemsets

11.18.5 Writing and Evaluating the Rules

11.18.6 Why C → A Wins

11.19 Why We Mine Only Frequent Items

11.19.1 Rare Items Have No Merit

11.19.2 The Domain Expert Decides

Exam Guidance Summary

Key Industry Applications

DM Lecture 11 notes · Association Rule Mining

Sections Breakdown

Exam Revision Notes

What Is Association Rule Mining

Market Basket Analysis and Its Business Uses