Click here to Skip to main content
14,975,411 members
Articles / Programming Languages / C#
Article
Posted 2 Apr 2010

Tagged as

Stats

515.3K views
10.7K downloads
149 bookmarked

Apriori Algorithm

Rate me:
Please Sign up or sign in to vote.
4.91/5 (84 votes)
10 Aug 2012CPOL2 min read
Implementation of the Apriori algorithm in C#.

Image 1

Introduction

In data mining, Apriori is a classic algorithm for learning association rules. Apriori is designed to operate on databases containing transactions (for example, collections of items bought by customers, or details of a website frequentation).

Other algorithms are designed for finding association rules in data having no transactions (Winepi and Minepi), or having no timestamps (DNA sequencing).

Overview

The whole point of the algorithm (and data mining, in general) is to extract useful information from large amounts of data. For example, the information that a customer who purchases a keyboard also tends to buy a mouse at the same time is acquired from the association rule below:

Support: The percentage of task-relevant data transactions for which the pattern is true.

Support (Keyboard -> Mouse) = AprioriAlgorithm/eq_1.JPG

Confidence: The measure of certainty or trustworthiness associated with each discovered pattern.

Confidence (Keyboard -> Mouse) = AprioriAlgorithm/eq_2.JPG

The algorithm aims to find the rules which satisfy both a minimum support threshold and a minimum confidence threshold (Strong Rules).

  • Item: article in the basket.
  • Itemset: a group of items purchased together in a single transaction.

How Apriori Works

  1. Find all frequent itemsets:
    • Get frequent items:
      • Items whose occurrence in database is greater than or equal to the min.support threshold.
    • Get frequent itemsets:
      • Generate candidates from frequent items.
      • Prune the results to find the frequent itemsets.
  2. Generate strong association rules from frequent itemsets
    • Rules which satisfy the min.support and min.confidence threshold.

High Level Design

AprioriAlgorithm/1-Apriori_HLD_Big.JPG

Low Level Design

AprioriAlgorithm/Apriori_LLD.jpg 

Example 

A database has five transactions. Let the min sup = 50% and min con f = 80%.

AprioriAlgorithm/3-DB.JPG

Solution 

Step 1: Find all Frequent Itemsets

AprioriAlgorithm/4-Example.JPG

Frequent Itemsets

{A}   {B}   {C}   {E}   {A C}   {B C}   {B E}   {C E}   {B C E}

Step 2: Generate strong association rules from the frequent itemsets

AprioriAlgorithm/5-StrongRules.JPG

Lattice

Closed Itemset: support of all parents are not equal to the support of the itemset.

Maximal Itemset: all parents of that itemset must be infrequent.

Keep in mind:

AprioriAlgorithm/6-Set.JPG

AprioriAlgorithm/7-Lattice.JPG

Itemset {c} is closed as support of parents (supersets) {A C}:2, {B C}:2, {C D}:1, {C E}:2 not equal support of {c}:3.

And the same for {A C}, {B E} & {B C E}.

Itemset {A C} is maximal as all parents (supersets) {A B C}, {A C D}, {A C E} are infrequent.

And the same for {B C E}.

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

Omar Gameel Salem
Software Developer
Egypt Egypt
Enthusiastic programmer/researcher, passionate to learn new technologies, interested in problem solving, data structures, algorithms, AI, machine learning and nlp.

Amateur guitarist/ keyboardist, squash player.

Comments and Discussions

 
GeneralThanks Pin
himanshu21p6-Jan-12 19:37
Memberhimanshu21p6-Jan-12 19:37 
QuestionMy 5 Pin
theanil6-Jan-12 9:39
Membertheanil6-Jan-12 9:39 
QuestionVisual basics Pin
Member 843790927-Nov-11 11:02
MemberMember 843790927-Nov-11 11:02 
AnswerRe: Visual basics Pin
Jason Vogel5-Jul-12 8:22
MemberJason Vogel5-Jul-12 8:22 
Generalmy vote of 5 Pin
shehbazshkh21-Nov-11 23:29
Membershehbazshkh21-Nov-11 23:29 
GeneralMy vote of 5 Pin
BillWoodruff6-Nov-11 22:44
mveBillWoodruff6-Nov-11 22:44 
QuestionDoes this code only work for single character ? Pin
haem savla15-Oct-11 6:27
Memberhaem savla15-Oct-11 6:27 
Questionproblem Pin
abarna1210-Oct-11 20:00
Memberabarna1210-Oct-11 20:00 
AnswerRe: problem Pin
Omar Gameel Salem10-Oct-11 23:47
professionalOmar Gameel Salem10-Oct-11 23:47 
AnswerRe: problem Pin
rahul_techi25-Jun-12 1:44
Memberrahul_techi25-Jun-12 1:44 
Questionerror i got.. Pin
Member 79873118-Oct-11 8:06
MemberMember 79873118-Oct-11 8:06 
AnswerRe: error i got.. Pin
Omar Gameel Salem8-Oct-11 8:15
professionalOmar Gameel Salem8-Oct-11 8:15 
GeneralRe: error i got.. Pin
Member 79873118-Oct-11 23:43
MemberMember 79873118-Oct-11 23:43 
GeneralRe: error i got.. Pin
Omar Gameel Salem10-Oct-11 23:42
professionalOmar Gameel Salem10-Oct-11 23:42 
Questionapriori algorithm Pin
salv0327-Sep-11 7:03
Membersalv0327-Sep-11 7:03 
GeneralMy vote of 5 Pin
Milad Rk6-Sep-11 22:19
MemberMilad Rk6-Sep-11 22:19 
QuestionHelp on modifications Pin
Member 811009825-Jul-11 0:36
MemberMember 811009825-Jul-11 0:36 
AnswerRe: Help on modifications Pin
Omar Gameel Salem25-Jul-11 1:46
professionalOmar Gameel Salem25-Jul-11 1:46 
GeneralRe: Help on modifications Pin
Member 811009825-Jul-11 3:39
MemberMember 811009825-Jul-11 3:39 
GeneralRe: Help on modifications Pin
Omar Gameel Salem25-Jul-11 23:17
professionalOmar Gameel Salem25-Jul-11 23:17 
GeneralRe: Help on modifications Pin
Member 811009825-Jul-11 23:31
MemberMember 811009825-Jul-11 23:31 
Questionrevision of borderset Pin
Member 40828605-Jul-11 18:28
MemberMember 40828605-Jul-11 18:28 
QuestionInput help in C++ for prices' algorithm(similar to apriori) Pin
adiiscool327-May-11 22:54
Memberadiiscool327-May-11 22:54 
AnswerRe: Input help in C++ for prices' algorithm(similar to apriori) Pin
salv0327-Sep-11 7:05
Membersalv0327-Sep-11 7:05 
GeneralMy vote of 5 Pin
Filip D'haene24-May-11 7:09
MemberFilip D'haene24-May-11 7:09 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.