Support, confidence and lift, the Apriori algorithm, and faster, parallel and neural approaches to association rules.
13.1 Introduction
An association rule of the form X → Y states that transactions which contain the items X also tend to contain the items Y. This kind of analysis is often called market basket analysis. Each rule is judged by three measures, support, confidence and lift, which are defined below.
ExampleOut of 1,000 bills, 200 contain bread, 150 contain butter and 100 contain both. The support of the rule "bread → butter" is therefore 100 ÷ 1,000 = 0.10, or 10 per cent. Its confidence is support(bread and butter) ÷ support(bread) = 0.10 ÷ 0.20 = 0.50, or 50 per cent. The support of butter alone is 150 ÷ 1,000 = 0.15, so the lift is 0.50 ÷ 0.15 = 3.33.
ExplanationA support of 10 per cent means that the pattern appears in one bill in ten, which is common enough to matter. A confidence of 50 per cent means that half of the customers who buy bread also buy butter. A lift of 3.33 means that bread buyers are 3.33 times more likely than an average customer to buy butter. Because the lift is greater than 1, the link between bread and butter is real and is not just a coincidence between two popular items.
13.2 Large (frequent) itemsets
An itemset is called large, or frequent, if its support count is at least the minimum support. Mining association rules takes two steps: first all the large itemsets are found, and then rules that meet the minimum confidence are generated from them.
Example of the Apriori propertyIn the nine transactions shown in section 13.3, the itemset {Eggs, Jam} appears in only one bill, which is below the minimum support of 2. It follows that the larger itemset {Milk, Eggs, Jam} can also appear in at most one bill.
ExplanationEvery subset of a frequent itemset must itself be frequent. Any candidate itemset that has an infrequent subset can therefore be pruned without being counted, which saves scans of the database.
13.3 Basic algorithms
The Apriori algorithm is the basic method for finding frequent itemsets. The worked example below uses a minimum support count of 2 and the nine transactions in the following table.
| TID | Items |
|---|---|
| T1 | Bread, Milk, Jam |
| T2 | Milk, Butter |
| T3 | Milk, Eggs |
| T4 | Bread, Milk, Butter |
| T5 | Bread, Eggs |
| T6 | Milk, Eggs |
| T7 | Bread, Eggs |
| T8 | Bread, Milk, Eggs, Jam |
| T9 | Bread, Milk, Eggs |
As the figure shows, each pass of Apriori joins the frequent itemsets found in the previous pass to form new candidates, prunes the candidates that cannot be frequent, and then counts the rest. The algorithm stops when no candidates remain.
Example (pass 1)Apriori first scans the nine transactions and counts each single item, which gives the candidate set C1 below. Every count is at least 2, so all five items are frequent and form L1.
| Item | Transactions containing it | Count | Frequent? |
|---|---|---|---|
| Bread | T1, T4, T5, T7, T8, T9 | 6 | Yes |
| Milk | T1, T2, T3, T4, T6, T8, T9 | 7 | Yes |
| Eggs | T3, T5, T6, T7, T8, T9 | 6 | Yes |
| Butter | T2, T4 | 2 | Yes |
| Jam | T1, T8 | 2 | Yes |
Example (pass 2)Joining L1 with itself gives 5 × 4 ÷ 2 = 10 candidate pairs, C2. A second scan counts them, as the table below shows. Six pairs have a count of at least 2 and form L2.
| Pair | Transactions containing it | Count | Frequent? |
|---|---|---|---|
| {Bread, Milk} | T1, T4, T8, T9 | 4 | Yes |
| {Bread, Eggs} | T5, T7, T8, T9 | 4 | Yes |
| {Bread, Butter} | T4 | 1 | No |
| {Bread, Jam} | T1, T8 | 2 | Yes |
| {Milk, Eggs} | T3, T6, T8, T9 | 4 | Yes |
| {Milk, Butter} | T2, T4 | 2 | Yes |
| {Milk, Jam} | T1, T8 | 2 | Yes |
| {Eggs, Butter} | none | 0 | No |
| {Eggs, Jam} | T8 | 1 | No |
| {Butter, Jam} | none | 0 | No |
Example (pass 3)Joining pairs in L2 that share one item gives seven candidate triples. Five of them are pruned without counting, because each has at least one pair that is not in L2. The two that survive are counted in a third scan.
| Candidate triple | Infrequent pair inside it | Result |
|---|---|---|
| {Bread, Milk, Eggs} | none | Counted: T8, T9, so 2, frequent |
| {Bread, Milk, Jam} | none | Counted: T1, T8, so 2, frequent |
| {Bread, Milk, Butter} | {Bread, Butter} | Pruned |
| {Bread, Eggs, Jam} | {Eggs, Jam} | Pruned |
| {Milk, Eggs, Butter} | {Eggs, Butter} | Pruned |
| {Milk, Eggs, Jam} | {Eggs, Jam} | Pruned |
| {Milk, Butter, Jam} | {Butter, Jam} | Pruned |
L3 is therefore {Bread, Milk, Eggs} and {Bread, Milk, Jam}. These two triples share only two items, so joining them would give a set of four items, {Bread, Milk, Eggs, Jam}, which contains the infrequent pair {Eggs, Jam}. That candidate is pruned, C4 is empty, and the algorithm stops.
Rules are then generated from each frequent itemset. The table below shows every rule that can be formed from {Bread, Milk, Jam}, with a minimum confidence of 70 per cent.
| Rule | Confidence | Kept? |
|---|---|---|
| Bread ∧ Milk → Jam | 2 ÷ 4 = 50% | No |
| Bread ∧ Jam → Milk | 2 ÷ 2 = 100% | Yes |
| Milk ∧ Jam → Bread | 2 ÷ 2 = 100% | Yes |
| Jam → Bread ∧ Milk | 2 ÷ 2 = 100% | Yes |
| Bread → Milk ∧ Jam | 2 ÷ 6 = 33% | No |
| Milk → Bread ∧ Jam | 2 ÷ 7 = 29% | No |
ExplanationThe confidence of each rule is the support count of the whole itemset, which is 2, divided by the support count of the items on the left-hand side, taken from the tables above: {Bread, Milk} has 4, {Bread, Jam} has 2, {Milk, Jam} has 2, {Jam} has 2, {Bread} has 6 and {Milk} has 7. Every customer who bought jam also bought bread and milk, so the three rules with Jam on the left-hand side have 100 per cent confidence and are kept.
Apriori needs one full scan of the database for each size of itemset, so several faster algorithms have been developed.
Sampling algorithm. The sampling algorithm mines a sample of the data in memory and then checks its results against the full data.
ExampleA 1 per cent sample of 1 crore bills, which is 1,00,00,000 × 0.01 = 1,00,000 bills, is mined in memory. The real minimum support is 2 per cent, but the sample is mined with a slightly lower threshold of 1.5 per cent, so that itemsets close to the limit are not missed by chance. The itemsets it finds are then checked with one scan of the full data.
ExplanationUsually only one scan of the full data is needed instead of several. A second scan is needed only if the sample missed an itemset.
Partitioning algorithm. The partitioning algorithm divides the data into parts that each fit in memory.
ExampleThe data is split into four parts, and the frequent itemsets in each part are found separately. The union of all these local itemsets is then counted in one more scan of the full data.
ExplanationAny itemset that is frequent in the full data must be frequent in at least one of the parts, so no frequent itemset is missed. As a result, only two scans of the database are needed.
FP-Growth. FP-Growth compresses the database into a structure called an FP-tree and mines the frequent itemsets directly from the tree.
ExampleIn the first scan, FP-Growth counts the items and sorts them by frequency: Milk (7), Bread (6), Eggs (6), Butter (2) and Jam (2). In the second scan, it rewrites each transaction in this order and inserts it into the tree: T1 becomes Milk, Bread, Jam; T2 becomes Milk, Butter; T3 becomes Milk, Eggs; T4 becomes Milk, Bread, Butter; T5 becomes Bread, Eggs; T6 becomes Milk, Eggs; T7 becomes Bread, Eggs; T8 becomes Milk, Bread, Eggs, Jam; and T9 becomes Milk, Bread, Eggs. Seven transactions start with Milk, so they share one Milk node with a count of 7, and four of them continue with Bread, so they share one Milk → Bread node with a count of 4. The frequent itemsets are then mined from this tree.
ExplanationFP-Growth generates no candidate itemsets and needs only two scans of the database. It is therefore much faster than Apriori, especially on dense data.
13.4 Parallel and distributed algorithms
When the data is very large, association rules are mined on several processors at once, and there are two main ways to divide the work.
ExampleA database of 1 crore transactions is mined on four processors, so each processor holds 25 lakh transactions. In Count Distribution, which is a form of data parallelism, each processor counts every candidate itemset in its own 25 lakh transactions, and the four sets of counts are then added together. In Data Distribution, which is a form of task parallelism, the candidate itemsets are divided so that each processor is responsible for a quarter of them. Each processor then sees all the transactions, which are passed around between the processors, but it counts only its own candidates. Hybrid and Intelligent Data Distribution methods mix the two approaches to balance the use of memory against the amount of communication.
For example, under Count Distribution the four processors report the following local counts for the pair {Bread, Milk}: 1.1 lakh, 0.9 lakh, 1.2 lakh and 0.8 lakh. The global count is 1.1 + 0.9 + 1.2 + 0.8 = 4.0 lakh, which is 4,00,000 ÷ 1,00,00,000 = 4 per cent of all transactions. If the minimum support is 3 per cent, the pair is frequent, even though no single processor could have decided this from its own count alone.
ExplanationCount Distribution moves very little data between processors, but every processor must hold all the candidates in its memory. Data Distribution can handle a very large number of candidates, but it must send the data to every processor.
13.5 Neural network approach
A neural network can also learn associations between items, by adjusting the weights of the connections between its input and output nodes.
ExampleThe network has one input node for each product, which is set to 1 when that product is in the basket, and it is trained to predict which other products the customer is likely to buy. After training, the input "phone" strongly activates the outputs "phone cover" and "screen guard".
ExplanationA neural network can capture complex, non-linear associations, and it copes well with noisy data. However, its knowledge is hidden in its weights, so it cannot easily be read as a set of "if–then" rules.
13.6 Advanced rule types
Beyond simple rules between items, there are several more advanced kinds of association rule. The table below gives an example of each.
| Type | Example |
|---|---|
| Multi-level | "Dairy → bakery" at a high level, and "Amul milk → Britannia bread" at a low level |
| Multi-dimensional | age = 20–29 ∧ occupation = student → buys = laptop |
| Quantitative | income = ₹8–12 lakh ∧ age = 30–39 → buys = SUV |
| Correlation | Tea and coffee have high confidence but a lift below 1, so they are negatively correlated |
Exam points
- Support is the fraction of transactions containing both X and Y; confidence = support(X ∪ Y) ÷ support(X).
- Lift above 1 means a positive association; below 1 means a negative one.
- Apriori property: every subset of a frequent itemset is frequent, so candidates with an infrequent subset are pruned.
- Apriori makes one database scan per itemset size; the partitioning algorithm needs only two scans.
- FP-Growth mines frequent itemsets from an FP-tree without generating candidates.
- Count Distribution splits the data among processors; Data Distribution splits the candidates.
Independent study notes for learning purposes. Not affiliated with or endorsed by any university, publisher or course provider. Product and company names are trademarks of their respective owners.