15,393,837 members
Articles / Programming Languages / C#
Article
Posted 2 Apr 2010

539.9K views
149 bookmarked

# Apriori Algorithm

Rate me:
Implementation of the Apriori algorithm in C#.

## 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) =

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

Confidence (Keyboard -> Mouse) =

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.

## Example

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

## Solution

### Step 1: Find all Frequent Itemsets

#### Frequent Itemsets

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

## 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:

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}.

## Share

 Software Developer 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.

 Thanks himanshu21p6-Jan-12 19:37 himanshu21p 6-Jan-12 19:37
 My 5 theanil6-Jan-12 9:39 theanil 6-Jan-12 9:39
 Visual basics Member 843790927-Nov-11 11:02 Member 8437909 27-Nov-11 11:02
 Re: Visual basics Jason Vogel5-Jul-12 8:22 Jason Vogel 5-Jul-12 8:22
 my vote of 5 shehbazshkh21-Nov-11 23:29 shehbazshkh 21-Nov-11 23:29
 My vote of 5 BillWoodruff6-Nov-11 22:44 BillWoodruff 6-Nov-11 22:44
 Does this code only work for single character ? haem savla15-Oct-11 6:27 haem savla 15-Oct-11 6:27
 problem abarna1210-Oct-11 20:00 abarna12 10-Oct-11 20:00
 Re: problem Omar Gameel Salem10-Oct-11 23:47 Omar Gameel Salem 10-Oct-11 23:47
 Re: problem rahul_techi25-Jun-12 1:44 rahul_techi 25-Jun-12 1:44
 error i got.. Member 79873118-Oct-11 8:06 Member 7987311 8-Oct-11 8:06
 Re: error i got.. Omar Gameel Salem8-Oct-11 8:15 Omar Gameel Salem 8-Oct-11 8:15
 Re: error i got.. Member 79873118-Oct-11 23:43 Member 7987311 8-Oct-11 23:43
 Re: error i got.. Omar Gameel Salem10-Oct-11 23:42 Omar Gameel Salem 10-Oct-11 23:42
 apriori algorithm salv0327-Sep-11 7:03 salv03 27-Sep-11 7:03
 Help on modifications Member 811009825-Jul-11 0:36 Member 8110098 25-Jul-11 0:36
 Re: Help on modifications Omar Gameel Salem25-Jul-11 1:46 Omar Gameel Salem 25-Jul-11 1:46
 Re: Help on modifications Member 811009825-Jul-11 3:39 Member 8110098 25-Jul-11 3:39
 Re: Help on modifications Omar Gameel Salem25-Jul-11 23:17 Omar Gameel Salem 25-Jul-11 23:17
 Re: Help on modifications Member 811009825-Jul-11 23:31 Member 8110098 25-Jul-11 23:31
 revision of borderset Member 40828605-Jul-11 18:28 Member 4082860 5-Jul-11 18:28
 Input help in C++ for prices' algorithm(similar to apriori) adiiscool327-May-11 22:54 adiiscool3 27-May-11 22:54
 Re: Input help in C++ for prices' algorithm(similar to apriori) salv0327-Sep-11 7:05 salv03 27-Sep-11 7:05
 My vote of 5 Filip D'haene24-May-11 7:09 Filip D'haene 24-May-11 7:09
 Last Visit: 31-Dec-99 18:00     Last Update: 12-Aug-22 8:34 Refresh ᐊ Prev123456 Next ᐅ