Apriori is a cornerstone algorithm in association rule mining, widely used in market basket analysis (e.g., identifying which items are frequently bought together in stores). The algorithm’s power lies in its ability to uncover hidden patterns in large transactional datasets.
What Does the Apriori Algorithm Do?
The Apriori algorithm is used for discovering frequent itemsets—groups of items that appear together in a dataset with frequency above a specified threshold (called minimum support). These itemsets form the basis for generating association rules—for example, “if someone buys bread and butter, there’s a good chance they’ll also buy jam.”
Core Steps of Apriori:
- List All Candidate Itemsets: List each individual item as a candidate (C1).
- Count Occurrences (Support) of Each Itemset: For each itemset, count how many transactions contain it.
- Prune Less Frequent Itemsets: Keep those with support at least as high as the minimum support (L1).
- Generate New Composite Candidates: Combine frequent itemsets to form larger sets (pairs, triples, etc.), counting their support and pruning as before.
- Repeat: Continue until no more frequent itemsets can be found.
This recursive process ensures we only consider those itemsets whose subsets are frequent—hence reducing the computational effort (“Apriori property”).
C++ Implementation
#include <iostream>
using namespace std;
const int NUM_TRANSACTIONS = 5;
const int MAX_ITEMS_PER_TRANSACTION = 5;
int main() {
// Step 1: Input all transactions (5 transactions, each up to 5 items)
int transactions[NUM_TRANSACTIONS][MAX_ITEMS_PER_TRANSACTION];
for (int transactionIdx = 0; transactionIdx < NUM_TRANSACTIONS; transactionIdx++) {
cout << "\nEnter items for Transaction " << transactionIdx + 1 << ": ";
for (int itemIdx = 0; itemIdx < MAX_ITEMS_PER_TRANSACTION; itemIdx++) {
cin >> transactions[transactionIdx][itemIdx];
}
}
int minSupport;
cout << "\nEnter minimum support (acceptance level): ";
cin >> minSupport;
// Show the gathered transactions for verification
cout << "\nInput Transactions:\n";
cout << "Transaction\tItems\n";
for (int transactionIdx = 0; transactionIdx < NUM_TRANSACTIONS; transactionIdx++) {
cout << transactionIdx + 1 << ":\t";
for (int itemIdx = 0; itemIdx < MAX_ITEMS_PER_TRANSACTION; itemIdx++) {
cout << transactions[transactionIdx][itemIdx] << "\t";
}
cout << "\n";
}
cout << "\nMinimum support set to: " << minSupport << "\n";
// Step 2: Count support for each item (store in itemSupportCount)
int itemSupportCount[MAX_ITEMS_PER_TRANSACTION] = {0};
for (int candidateItem = 1; candidateItem <= MAX_ITEMS_PER_TRANSACTION; candidateItem++) {
int occurrenceCount = 0;
for (int transactionIdx = 0; transactionIdx < NUM_TRANSACTIONS; transactionIdx++) {
for (int itemIdx = 0; itemIdx < MAX_ITEMS_PER_TRANSACTION; itemIdx++) {
if (transactions[transactionIdx][itemIdx] == candidateItem) {
occurrenceCount++;
}
}
}
itemSupportCount[candidateItem - 1] = occurrenceCount;
}
// Step 3: Show initial item support counts (C1)
cout << "\nItem Support Count (C1):\n";
for (int itemIdx = 0; itemIdx < MAX_ITEMS_PER_TRANSACTION; itemIdx++) {
cout << "Item " << itemIdx + 1 << ": " << itemSupportCount[itemIdx] << "\n";
}
// Step 4: Filter items meeting minimum support (Frequent 1-itemsets: L1)
int frequentItems[MAX_ITEMS_PER_TRANSACTION], frequentItemCount = 0;
for (int itemIdx = 0; itemIdx < MAX_ITEMS_PER_TRANSACTION; itemIdx++) {
if (itemSupportCount[itemIdx] >= minSupport) {
frequentItems[frequentItemCount++] = itemIdx + 1;
}
}
cout << "\nFrequent 1-itemsets (L1):\n";
for (int idx = 0; idx < frequentItemCount; idx++) {
cout << "Item " << frequentItems[idx] << "\n";
}
// Step 5: Generate and count frequent 2-itemsets (pairs of frequent items)
int itemPairSupportCount[MAX_ITEMS_PER_TRANSACTION][MAX_ITEMS_PER_TRANSACTION] = {0};
cout << "\nFrequent 2-itemsets (L2):\n";
for (int i = 0; i < frequentItemCount; i++) {
for (int j = i + 1; j < frequentItemCount; j++) {
int item1 = frequentItems[i];
int item2 = frequentItems[j];
int pairSupportCount = 0;
// Count transactions where both item1 and item2 appear
for (int transactionIdx = 0; transactionIdx < NUM_TRANSACTIONS; transactionIdx++) {
bool item1Exists = false, item2Exists = false;
for (int itemIdx = 0; itemIdx < MAX_ITEMS_PER_TRANSACTION; itemIdx++) {
if (transactions[transactionIdx][itemIdx] == item1) item1Exists = true;
if (transactions[transactionIdx][itemIdx] == item2) item2Exists = true;
}
if (item1Exists && item2Exists) pairSupportCount++;
}
itemPairSupportCount[item1-1][item2-1] = pairSupportCount;
if (pairSupportCount >= minSupport) {
cout << "Items (" << item1 << ", " << item2 << "): " << pairSupportCount << "\n";
}
}
}
// (Optional) Step 6: Extend to 3-itemsets (L3), using similar logic
return 0;
}
Example Output
Enter items for Transaction 1: 1 5 2 0 0
Enter items for Transaction 2: 2 3 4 1 0
Enter items for Transaction 3: 3 4 0 0 0
Enter items for Transaction 4: 2 1 3 0 0
Enter items for Transaction 5: 1 2 3 0 0
Enter minimum support (acceptance level): 3
Item Support Count (C1):
Item 1: 4
Item 2: 4
Item 3: 4
Item 4: 2
Item 5: 1
Frequent 1-itemsets (L1):
Item 1
Item 2
Item 3
Frequent 2-itemsets (L2):
Items (1, 2): 4
Items (1, 3): 3
Items (2, 3): 3
Here’s a brief explanation of the above output:
- Input Transactions: Displays the list of transactions and their items for verification.
- Item Support Count (C1): Shows how many times each item appears in all transactions.
- Frequent 1-itemsets (L1): Lists items that meet the minimum support threshold—these are popular and considered for further analysis.
- Frequent 2-itemsets (L2): Shows pairs of frequent items that appear together in enough transactions, indicating strong associations.
The output identifies frequent single items and item pairs that occur together often enough to be relevant for rule generation or recommendations, based on your chosen minimum support.
The Apriori algorithm is a foundational technique for association mining, and its candidate generation and support counting steps reveal how simple combinatorics can discover powerful relationships in real-world data. While this C++ example uses static arrays and simplified input, the same logic extends to larger datasets and even to other languages like Python or Java.
Understanding and coding basic algorithms like Apriori is a gateway to advanced analytics, data mining, and many real-world applications, from market basket analysis to behavior prediction.
For further exploration:
- Try using dynamic arrays or STL containers for bigger or more varied data.
- Implement 3-itemset (L3) generation using similar loops.
- Experiment by changing
NUM_TRANSACTIONSandMAX_ITEMS_PER_TRANSACTION.
Happy coding and data mining!
hey i am getting this error when i compiling it in dev c++
1 21 C:\Users\chiranjiv\Desktop\Untitled2.cpp [Error] iostream.h: No such file or directory
Write #include(without .h )and “using namespace std;”
#include
using namespace std;
also showing error for the conio.h ……
yes….same error…what should i do ??
Replace
#include<iostream.h>
#include<conio.h>
with following three lines
#include<iostream>
#include<conio>
using namespace std;
keep only #include
I got this error in this prgm:
purches and in ‘was not declared in this scope’
plse reply me what should i do????
purches and In purches ‘was not declared in this scope’
getting same error can you help me to find its solution??
just delete both. the code will run perfect.
Generating junk value output for l3
Yes l3 values is not correct. Something wrong in l3 generating codes . Could you please correct it if you known.
I solved the wrong outputs for l3. Change the code in the following line as:
….
//Third pass
int p3items[100]={-1}; // increase the size of array…
….