[go: up one dir, main page]
Scribd
Upload
59 views13 pages

Apriori Algorithm Notes

The document explains the Apriori Principle and Algorithm used in association rule mining, which identifies frequent itemsets from transactional data. It outlines the steps of the Apriori algorithm, including generating frequent itemsets and pruning non-promising candidates based on minimum support and confidence. An example with transaction data illustrates how to derive frequent itemsets and the importance of the Apriori Property in reducing search space.

Uploaded by

mohanapriya.c
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
59 views13 pages

Apriori Algorithm Notes

The document explains the Apriori Principle and Algorithm used in association rule mining, which identifies frequent itemsets from transactional data. It outlines the steps of the Apriori algorithm, including generating frequent itemsets and pruning non-promising candidates based on minimum support and confidence. An example with transaction data illustrates how to derive frequent itemsets and the importance of the Apriori Property in reducing search space.

Uploaded by

mohanapriya.c
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
You are on page 1/ 13

The Apriori Principle & Algorithm

Association Rule Mining


The Apriori Principle

• AIS Algorithm is the first for association rule mining.


• Reads transactions, counts items, and generates candidate itemsets.
• If k-itemset is frequent, all (k-1)-item subsets are also frequent.
• Used to prune non-promising itemsets during mining.
Apriori Algorithm

• Uses prior knowledge of frequent items (minsup & minconf).


• Follows Reduce & Conquer principle.
• Extracts significant rules from transactional data.
• Performs level-by-level search for frequent itemsets.
Apriori Algorithm Steps

1. Input minsup, minconf, and DB size N.


2. Scan DB to find frequent 1-itemsets (L1).
3. Use Lk-1 to generate candidate Ck.
4. Count support for each candidate.
5. Prune candidates below minsup.
6. Repeat until no frequent itemsets remain.
Apriori Algorithm Example
Given Data (Transactions):
3010: Milk, Bread, Jam
3011: Bread, Butter, Juice
3012: Soda, Bread, Butter
3013: Bread, Juice, Soda
3014: Milk, Juice
Total number of transactions, N = 5
Step 1: Generate L1 (1-itemsets)
L1 = {Milk, Bread, Soda, Juice, Butter}

Item Support Transactions


Milk 40% 3010, 3014
Bread 80% 3010 - 3013
Soda 40% 3012, 3013
Juice 60% 3011, 3013, 3014
Butter 40% 3011, 3012
Jam 20% 3010
Step 2: Generate L2 (2-itemsets)
L2 Candidates (Support ≥ 40%):

{Bread, Butter} - 40% (3011, 3012)


{Bread, Juice} - 40% (3011, 3013)
{Soda, Bread} - 40% (3012, 3013)
Others eliminated due to low support
Step 2: Generate L2 (2-itemsets)

Now generate all possible 2-item combinations from L1:

1.Bread, Butter → In 3011, 3012 ✅ → Support = 40%


2.Bread, Juice → In 3011, 3013 ✅ → Support = 40%
3.Soda, Bread → In 3012, 3013 ✅ → Support = 40%
4.Milk, Bread → Only in 3010 ❌ (Support = 20%)
5.Juice, Butter → Only in 3011 ❌
6.Milk, Butter → None ❌
7.Soda, Juice → Only in 3013 ❌
8.Milk, Soda → None ❌
9.Milk, Juice → Only in 3014 ❌
So L2 = {Bread, Butter}, {Bread, Juice}, {Soda, Bread}
Each has support ≥ 40%
Step 3: Generate L3 (3-itemsets)
Try {Bread, Butter, Juice} - only in 3011 → 20%
Other combinations not possible
No 3-itemsets meet minsup
Final L3 = ∅

no valid 3-itemset meets minsup.


Final Frequent Itemsets
L1 = {Milk, Bread, Soda, Juice, Butter}
L2 = {Bread, Butter}, {Bread, Juice}, {Soda, Bread}
No L3 itemsets
rulesFound = L1 ∪ L2

The algorithm reduces the search space using the Apriori Property:
If an itemset is frequent, all its subsets are also frequent.
• Support: % of transactions containing itemset.
• Confidence: Likelihood Y occurs with X.
• Apriori Property: All subsets of frequent itemsets must be frequent.
• Optimization: Lexicographic sorting, symbolic encoding.

You might also like